Scaling Memcache at Facebook

За последние 4.5 месяца я успел эмигрировать в Дубай, получить лычку Staff Engineer, попасть под сокращение (потерять лычку :D), пройти 22 собеса за 2 недели и найти ещё одну работу. Если кто-то хочет в Дубае найти финтех или перевезти сюда котов, пишите. Я походу стал экспертом.

Когда-то давно у меня был план сделать цикл с разбором работ по алгоритмам консенсуса, но этот план теперь там же где российская экономика и мои нервишки, поэтому ближайшие пару постов будут более расслабленными. А именно: несколько работ о том, как компания X сделала Y. Такие пейперы легко читать, а состоят они в основном из практичных советов и цифр, нежели зубодробительной математики и фундаментальных доказательств. Сегодня поговорю о Scaling Memcache at Facebook от 2013 года (ПДФ на usenix). Формат тоже попроще: больше повествования и меньше тягомотины, но ничего не обещаю. Поехали!

Итак Фейсбук решил доработать и так неплохо работающий memcached, потому что могут. В работе memcached — это сам кеш, а memcache (без d) — кластер, на котором крутятся memcached. Первая интересная находка — использовать UDP для get запросов вместо TCP. Set и delete всё ещё по TCP. Результат: теряются 0.25% запросов, зато -20% latency в среднем. В работе -20% на графике average of medians. Я не очень понимаю этот оборот, но походу это в районе 50% процентиля, потому что медианы...? В любом случае, в 95-ом процентиле прироста почти нет, т.е. быстрее становятся медленные запросы, что хорошо. Правда 0.25% потерь — это всё-таки много, поэтому имплементация оборачивает потерянные пакеты и out-of-order delivery в клиентские ошибки, а клиент там сам уже ретраит. Фейсбуку норм, потому что некоторые страницы делают тысячи обращений в memcache, и сделать пару ретраев недорого.

Кстати о ретраях и ошибках. Фейсбук использует отдельный пул под названием gutter, размером 1% от общего размера memcache для обработки запросов с ошибкой. Клиент делает запрос, не получает ответа (т.е. не cache miss, а прямо Connection Error), далее делает повторный запрос в gutter. Если в gutter данных тоже нет, они добавляются туда. Данные в gutter устаревают быстро, чтобы часто не инвалидировать. Такой подход мало того что защищает от 99% ошибок при доступе к memcache, так ещё и превращает 10-25% промахов в попадания. К тому же дополнительный слой защиты бекенда от запросов. В идеальном мире данные есть в memcahce, если тот умер, то в gutter, только если и в нём нет, запрос идёт в бекенд. Правда трейдофф тоже есть, данные в gutter могут быть старыми. Потому и время жизни записей в gutter короткое.

Ещё пара фишек с удалением и записью. Во-первых, при cache miss, клиенту выдаётся lease token на ~10 секунд (дефолт) на конкретный ID для записи данных. Другие клиенты не могут обновить запись, пока у кого-то есть токен. Это позволяет бороться с циклами запись-перезапись при конкурентном доступе. Во-вторых, lease token помогает в борьбе с thundering herds — ситуации, когда много клиентов пытаются получить один и те же данные. Если клиент пытается получить запись, на которую выпущен lease token, клиент самостоятельно уйдёт в небольшое ожидание и повторит запрос ещё раз, потому что обычно между захватом lease token и самой записью проходит несколько милисекунд. Так запрос не попадёт в cache miss, а вернётся с более долгой задержкой.

Связанная, но немного отдельная проблема — это конкурентные удаления. При удалении, записи какое-то время ещё хранятся в особой структуре данных (какой — не написано) При промахе, клиент может по своему усмотрению либо получить lease token для дальнейшей записи, либо получить устаревшие данные. Опять cache miss превращается в hit, но со старыми данными. Удобно.

В работе есть ещё пара интересных моментов с разогревом нового инстанса из соседнего, а не из бекенда, батчинг запросов, и как решить read-your-writes (спойлер: помечать записи и читать с мастера), но для первого поста за 4.5 месяцев я думаю достаточно.