Спроектируйте распределённое key-value хранилище

Требования

Продукт намеренно узкий: хранить и доставать значение по непрозрачному ключу, на масштабе, без простоев. Зафиксировав это, отделяем то, что дизайн обязан делать, от того, чем ему позволено пожертвовать. Спроси себя: какое из требований система может согнуть, а какое убьёт бизнес, если согнётся? Ответ диктует каждое последующее решение.

Функциональные

• get(key) возвращает значение (или значения, если реплики расходятся) для ключа.
• put(key, value, context) пишет значение; context несёт метаданные версии, полученные клиентом при предыдущем чтении.
• Значения — непрозрачные блобы до небольшого предела (Dynamo брал < 1 MB); хранилище их никогда не интерпретирует.
• Никаких запросов, джойнов, вторичных индексов, транзакций между ключами. Один ключ за раз.

Нефункциональные — это и есть дизайн, а не украшение:

• Всегда доступно для записи. put обязан проходить даже при сбоях и сетевых разделениях. Это требование диктует всё остальное.
• Инкрементальный масштаб. Добавлять по одному узлу; кластер ребалансируется без окна обслуживания.
• Симметрия, децентрализация. Ни мастера, ни особого узла, потеря которого останавливает систему. Все узлы крутят один код.
• Настраиваемость. Разные вызывающие хотят разные точки на кривой задержка/надёжность/согласованность из одного хранилища.

Решающий компромисс — доступность над согласованностью (A и C в CAP). Поскольку хранилище обязано принимать записи во время разделения, оно не может одновременно гарантировать, что каждый читатель видит последнюю запись — поэтому принимает итоговую согласованность и переносит разрешение конфликтов на момент чтения.

Оценка

Числа определяют форму. Пусть это хранилище сессий/корзин:

• 100M активных пользователей в день, каждый трогает корзину ~20 раз/день → 2 × 10^9 операций/день. Делим на ~10^5 с/день → ~20 000 операций/с в среднем, при пике 5× — ~100 000 операций/с.
• Микс read-heavy, но записи реальны: пусть отношение чтений к записям 4:1 → ~80K чтений/с, ~20K записей/с на пике.
• Размер значения ~5 КБ в среднем. Горячий рабочий набор: 100M активных корзин × 5 КБ = ~500 ГБ живых данных — влезает в суммарную RAM скромного кластера, так что большинство чтений идут из памяти.
• При N = 3 сырые байты утраиваются до ~1,5 ТБ до накладных; на диске мелочь, смысл числа в том, что ни один узел не держит всё.
• При 100K операций/с один узел на ~10K операций/с — это примерно 10–20 узлов на пике с запасом — мало, чтобы рассуждать, и много, чтобы узел падал каждую неделю.

Последнее число и есть драйвер: при таком числе узлов падение узла — это вторник, а не инцидент. Дизайн обязан считать отказ узла нормой.

Высокоуровневый дизайн

Клиент (или умная клиентская библиотека) хеширует ключ на кольцо consistent hashing, попадает на узел-координатор, который реплицирует на следующие N − 1 узлов по часовой стрелке и применяет кворум. Отдельного слоя маршрутизации нет — любой узел может координировать любой запрос, а членство узнаётся через gossip.

Три строительных блока, по порядку:

1. Партиционирование — consistent hashing раскладывает ключи по узлам и дёшево ребалансирует, когда узел входит или выходит.
2. Репликация + кворум — каждый ключ живёт на N узлах; R и W настраивают, скольким нужно ответить.
3. Версионирование — поскольку записи во время разделения могут попасть на разные реплики, хранилище держит несколько версий и сводит их.

Глубокое погружение

Партиционирование кольцом хеширования

Каждый ключ хешируется на кольцо; его N реплик — следующие N различных физических узлов по часовой стрелке — это preference list ключа. Виртуальные узлы (каждый физический размещён в ~150 точках кольца) держат дуги сбалансированными и раскидывают нагрузку мёртвого узла по многим преемникам, а не давят одного соседа. Выигрыш операционный: добавление узла двигает лишь ~1/N ключей, так что мощность растёт по одной машине без глобальной перетряски. (Пререквизит про consistent hashing разбирает механику кольца; здесь это подложка, на которой стоит всё остальное.)

Репликация и ручка кворума

Каждая запись идёт на все N реплик, но координатор возвращает успех после подтверждения лишь W из них; каждое чтение опрашивает N и возвращает после ответа R. Единственное неравенство, управляющее корректностью:

R + W > N   →   множество чтения и множество записи обязаны пересекаться

Примеры для N = 3:
  W=3, R=1  → надёжно, быстрые чтения, медленная/хрупкая запись
  W=1, R=3  → быстрая запись, медленные чтения, запись жива, если жив любой узел
  W=2, R=2  → баланс; обычный дефолт

Когда R + W > N, любой кворум чтения и любой кворум записи делят хотя бы один узел, так что чтение гарантированно увидит хотя бы одну копию последней подтверждённой записи. Опусти сумму ниже N + 1 — и обменяешь эту гарантию на задержку, иногда верный выбор для кеш-подобной нагрузки.

Загвоздка — слово подтверждённой. Во время разделения координатор может не достучаться до «настоящих» N узлов, поэтому пишет на первые N здоровых узлов, до которых может достучаться — нестрогий кворум (sloppy quorum) — и помечает смещённые записи подсказкой (hint), чтобы вернуть их законному узлу при его возвращении (hinted handoff). Так хранилище остаётся доступным для записи сквозь сбои: оно не блокируется в ожидании конкретного узла, а просто пишет куда-то надёжно и сводит позже.

Версионирование: векторные часы против last-write-wins

Нестрогие кворумы и конкурентные записи означают, что две реплики могут законно держать разные значения для одного ключа без глобальных часов для их упорядочивания. Хранилищу нужно знать, происходит ли одна версия от другой (оставить новее) или они действительно конкурентны (конфликт). Две стратегии:

• Last-write-wins (LWW): прицепить временную метку; побеждает наибольшая. Предельно просто, но молча выбрасывает проигравшего — а при расхождении часов между узлами «наибольшая метка» может быть неверной записью. Годится для кешей; опасно для корзин.
• Векторные часы: каждое значение несёт вектор пар (узел, счётчик). Сравнение двух векторов говорит, произошла-до ли одна другой (оставить потомка) или они конкурентны (ни один не доминирует) — тогда оба возвращаются клиенту на слияние. Каноничный пример Dynamo: два конкурентных добавления в корзину дают расходящиеся векторы, а слияние — объединение множеств, так что ни один товар не теряется.

Цена векторных часов в том, что приложение должно уметь сливать — хранилище отдаёт «вот два сиблинга, решай сам». Для корзины слияние очевидно (объединить товары); для счётчика — нет, ровно поэтому существуют специальные CRDT. Выбор дизайна семантический: LWW там, где потеря записи приемлема, векторные часы там, где нет.

Anti-entropy: gossip, read-repair, деревья Меркла

У хранилища нет мастера для отслеживания членства, поэтому узлы крутят gossip-протокол: каждый периодически выбирает случайного соседа и обменивается своим взглядом на то, кто жив, какой узел владеет какой дугой, и подозрениями в отказе. За секунды весь кластер сходится к одной карте — без координатора, без единой точки отказа для самого членства.

Реплики всё равно дрейфуют (подсказка не доставлена, узел упал во время записи), поэтому непрерывно работают два механизма починки. Read-repair: когда R ответов чтения расходятся, координатор проталкивает самую свежую версию назад на устаревшие реплики на пути ответа — починка едет на обычном трафике. Anti-entropy по деревьям Меркла: реплики одного диапазона ключей периодически сравнивают хеш-деревья своих данных; обмениваются только ветви с разными хешами, так что две реплики обнаруживают и лечат расхождение, почти ничего не передавая, когда уже согласны.

Узкие места и компромиссы

• Горячие ключи. Consistent hashing балансирует пространство ключей, а не нагрузку — один ключ-знаменитость (вирусная корзина, глобальная строка конфига) гонит весь трафик на одни и те же N узлов независимо от vnodes. Митигации: клиентское кеширование горячих ключей, разбиение горячего ключа на шарды или bounded-load хеширование для маршрутизации. Кольцо не спасает от одного бело-горячего ключа.
• Бремя слияния. Векторные часы перекладывают сведение на клиента; ошибёшься (или по удобству поставишь LWW) — молча потеряешь данные. Векторы могут расти неограниченно при многих координирующих узлах, поэтому реальные системы подрезают старые записи — что изредка может потерять причинную информацию.
• Усиление чтения при низком R. R = 1 быстр, но максимизирует устаревание и работу read-repair; R = N согласован, но превращает одно логическое чтение в N сетевых вызовов, и одна медленная реплика тянет хвост (tail-at-scale). Ручка R/W пооперационна именно потому, что одна настройка не годится для всех вызовов.
• Итоговая согласованность — контракт, не баг — но он протекает. «Прочитай свою запись» не гарантирована, если не маршрутизировать чтения клиента через тот же координатор или не использовать R + W > N со строгим (не нестрогим) кворумом. Команды, считающие read-after-write данностью, обжигаются; честный дизайн заявляет окно устаревания и даёт приложению выбрать более сильные настройки там, где это важно.