Системный дизайн key-value хранилища: Dynamo, кворумы, векторные часы и Merkle-деревья

Как спроектировать распределённое key-value хранилище в духе Dynamo: партиционирование, репликация, кворумы N/R/W, векторные часы, hinted handoff и anti-entropy на Merkle-деревьях. Код на Python.

18 мин чтениясистемный дизайн · распределённые системы · базы данных · python

Коротко

ЗадачаРешение в духе DynamoЧем платим
Разложить ключи по узламКонсистентное хеширование с виртуальными узламиНет диапазонных запросов, нужен общий взгляд на кольцо
Не потерять данные при отказеNN реплик на следующих разных узлах кольцаВ NN раз больше диска и трафика записи
Настроить согласованностьКворумы: WW подтверждений записи, RR ответов чтенияПри R+W≤NR + W \le N можно прочитать старое
Писать, даже когда реплика лежитSloppy quorum и hinted handoffКворумы перестают гарантированно пересекаться
Понять, какая версия новееВекторные часы, конфликтующие версии отдаются клиентуКлиент сам сливает siblings, часы растут
Догнать отставшую репликуRead repair и фоновая сверка Merkle-деревьямиФоновая нагрузка на диск и сеть

Главная идея: у хранилища нет лидера. Любой узел принимает запись, реплики сходятся со временем, а все механизмы ниже нужны, чтобы это «со временем» было коротким и не теряло данные.

Постановка задачи

На собеседовании формулировка обычно короткая: «Спроектируйте распределённое key-value хранилище». Прежде чем рисовать, уточните требования, иначе получится Redis на одной машине или, наоборот, Spanner там, где он не нужен.

Функциональные требования:

  • put(key, value) и get(key), ключи до сотни байт, значения до 1 МБ.
  • Нет транзакций между ключами, нет диапазонных запросов, нет вторичных индексов.

Нефункциональные:

  • Запись всегда принимается. Классический пример из статьи Amazon о Dynamo (2007) — корзина покупок: кнопка «добавить в корзину» не должна отвечать ошибкой из-за сбоя сети.
  • Масштабирование добавлением машин без простоя.
  • Задержка p99 — единицы-десятки миллисекунд.
  • Допустима согласованность в конечном счёте (eventual consistency) с настраиваемой строгостью.

Последний пункт — ключевое решение. Если интервьюер скажет «нужна строгая согласованность для каждого ключа», правильный ответ другой: лидер на партицию и консенсус (Raft, Paxos), как в etcd или в самом DynamoDB. Почему нельзя получить всё сразу, разобрано в статье про теорему CAP. Дальше идём по пути Dynamo: выбираем доступность.

Оценка масштаба

Допустим, 1 млрд ключей по 1 КБ — это 1 ТБ полезных данных. С тремя репликами 3 ТБ, с запасом на компакцию и рост ещё в полтора-два раза, то есть 5–6 ТБ. Если на узле 1 ТБ рабочего диска, узлов нужно 6–8, и это без учёта нагрузки. При 100 тыс. запросов в секунду и 3 репликах каждая запись превращается в три записи на диск. Узлы держат по 10–20 тыс. операций, значит, по нагрузке тоже выходит порядка десятка машин. Цифры не надо подгонять: важно показать, что вы связываете объём, репликацию и число узлов.

Архитектура на одной картинке

клиент ──► любой узел (координатор)
             │  1. по кольцу находит N реплик ключа
             │  2. шлёт запись всем N, ждёт W ответов
             │  3. для чтения опрашивает реплики, ждёт R ответов
             ▼
   ┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐
   │ A  │  │ B  │  │ C  │  │ D  │  │ E  │   все узлы равноправны
   └────┘  └────┘  └────┘  └────┘  └────┘
      ▲  gossip: кто жив, какие диапазоны у кого  ▲

Узлы равноправны: нет мастера, нет отдельного сервиса метаданных. Состав кластера и раскладку кольца узлы распространяют через gossip — каждую секунду обмениваются своим видом мира со случайным соседом. Клиент обращается к любому узлу или сам знает кольцо и идёт сразу к нужному (так быстрее на один сетевой переход).

Партиционирование

Ключи раскладываются по кольцу хешей: ключ принадлежит первому узлу по часовой стрелке от hash(key). Каждый физический узел занимает на кольце много точек, виртуальных узлов, чтобы нагрузка распределялась ровно, а при отказе расходилась по всем. Подробно, с замерами, это разобрано в статье про консистентное хеширование. Здесь нам нужен один шаг дальше: не один владелец, а список из NN реплик.

Репликация: список предпочтений

Ключ хранится на первых NN разных физических узлах по часовой стрелке. Dynamo называет этот список preference list. Оговорка про «разные физические» важна: соседние виртуальные точки часто принадлежат одной машине, и наивное «следующие три точки» положит две копии на один сервер.

import bisect import hashlib def h(s: str) -> int: return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], 'big') class Ring: def __init__(self, nodes, vnodes=8): self.points = sorted((h(f'{n}#{i}'), n) for n in nodes for i in range(vnodes)) self.hashes = [p for p, _ in self.points] def preference_list(self, key, n): """Первые n РАЗНЫХ физических узлов по часовой стрелке от hash(key).""" i = bisect.bisect(self.hashes, h(key)) result = [] for step in range(len(self.points)): node = self.points[(i + step) % len(self.points)][1] if node not in result: result.append(node) if len(result) == n: break return result ring = Ring(['A', 'B', 'C', 'D', 'E']) for key in ['user:42', 'cart:7', 'session:abc']: print(key, ring.preference_list(key, 3)) # user:42 ['D', 'E', 'B'] # cart:7 ['B', 'D', 'C'] # session:abc ['E', 'A', 'C']

В продакшене к этому правилу добавляют стойки и дата-центры: реплики раскладывают так, чтобы выход из строя одной стойки не уносил кворум. В Cassandra за это отвечает стратегия размещения реплик и snitch, который знает топологию.

Как это соотносится с классической репликацией «лидер — последователи», описано в статье про шардирование и репликацию. Здесь схема leaderless: каждая из NN реплик принимает запись наравне с остальными.

Кворумы N, R, W

Три числа задают поведение системы:

  • NN — сколько копий у ключа;
  • WW — сколько реплик должны подтвердить запись, прежде чем координатор ответит клиенту «ок»;
  • RR — сколько реплик должны ответить на чтение.

Координатор всегда шлёт запрос всем NN репликам, а WW и RR определяют только, сколько ответов ждать. Если R+W>NR + W > N, множество записавших и множество прочитанных реплик пересекаются хотя бы в одном узле, и чтение увидит последнюю подтверждённую запись.

N, R, WПересечениеПоведение
3, 2, 2даТипичный выбор Dynamo: переживает отказ одной реплики и на чтении, и на записи
3, 1, 3даБыстрое чтение, но запись встаёт при любой упавшей реплике
3, 3, 1даБыстрая запись, чтение ждёт самую медленную реплику
3, 1, 1нетМинимальная задержка, возможны устаревшие чтения

Задержка операции определяется WW-й (или RR-й) по скорости репликой, а не самой медленной. Поэтому кворум 2 из 3 сглаживает хвосты: одна тормозящая машина не портит p99.

Не обещайте интервьюеру линеаризуемость только из-за R+W>NR + W > N. Конкурентные записи, запись, применённая на одной реплике и не набравшая кворума, и sloppy quorum из следующего раздела ломают эту гарантию. Подробнее в разделе про PACELC и настройки кворумов в статье про CAP.

Отказы: sloppy quorum и hinted handoff

Пусть у ключа реплики B, D, C, а B недоступен. При строгом кворуме запись с W=3W = 3 не пройдёт, а с W=2W = 2 пройдёт, но у ключа будет только две копии. Dynamo поступает иначе: берёт следующий здоровый узел за пределами списка, например A, и пишет туда копию с пометкой «на самом деле это для B». Это sloppy quorum: кворум набирается из первых NN здоровых узлов, а не строго из своих.

Когда B возвращается, A по gossip узнаёт об этом, передаёт ему подсказку (hint) и удаляет временную копию. Это hinted handoff.

Цена: при разделении сети запись с одной стороны и чтение с другой могут не пересечься вовсе, даже при R+W>NR + W > N. Доступность записи покупается ослаблением гарантии. В Cassandra hinted handoff есть, но запись с подсказкой не засчитывается в кворум, кроме уровня ANY; у Riak sloppy quorum включён по умолчанию.

Версии и конфликты: векторные часы

Без лидера две записи одного ключа могут пройти через разные узлы одновременно. Нужен способ понять: одна версия новее другой или они конкурентные.

Время на часах сервера не подходит: часы расходятся на миллисекунды, а иногда и на секунды, и «последняя запись побеждает» (LWW) молча выбрасывает одну из правок. Так работает Cassandra, и для многих данных этого достаточно. Но для корзины потерянный товар — это потерянные деньги.

Векторные часы — словарь «узел → счётчик». Узел, который координирует запись, увеличивает свой счётчик в часах той версии, которую клиент читал перед записью. Версия aa новее bb, если каждый счётчик aa не меньше соответствующего в bb. Если ни одна не новее другой, версии конкурентные.

def descends(a: dict, b: dict) -> bool: """a видел всё, что видел b (a >= b покомпонентно).""" return all(a.get(node, 0) >= cnt for node, cnt in b.items()) def compare(a: dict, b: dict) -> str: if a == b: return 'equal' if descends(a, b): return 'a newer' if descends(b, a): return 'b newer' return 'concurrent' def merge(a: dict, b: dict) -> dict: return {n: max(a.get(n, 0), b.get(n, 0)) for n in a.keys() | b.keys()} def increment(clock: dict, node: str) -> dict: return {**clock, node: clock.get(node, 0) + 1} # Корзина. Узел A принял первую запись v1 = increment({}, 'A') # {A:1} v2 = increment(v1, 'A') # {A:2} — клиент дописал через A # Сеть разделилась: два клиента прочитали v2 и пишут через разные узлы v3 = increment(v2, 'B') # {A:2, B:1} v4 = increment(v2, 'C') # {A:2, C:1} print(compare(v2, v1)) # a newer — v2 потомок v1, v1 можно выбросить print(compare(v3, v4)) # concurrent — конфликт, храним обе версии merged = increment(merge(v3, v4), 'A') # клиент слил корзины и записал print(dict(sorted(merged.items()))) # {'A': 3, 'B': 1, 'C': 1} print(compare(merged, v3), compare(merged, v4)) # a newer a newer

Конкурентные версии называют siblings. Хранилище не знает семантики значения, поэтому отдаёт клиенту все siblings вместе с их общим контекстом (слитыми часами). Клиент сливает их по своим правилам — для корзины объединением множеств товаров — и пишет результат с этим контекстом. Новая версия перекрывает обе старые.

Побочный эффект объединения известен из статьи о Dynamo: удалённый товар иногда возвращается в корзину, потому что одна из веток его ещё содержала. Лечится хранением удалений явно, например CRDT вроде OR-Set, но это уже отдельная тема.

Ещё одна проблема — размер часов. Если координаторами выступает много узлов, словарь растёт. Dynamo обрезал часы, когда пар становилось больше порога (в статье это 10), выбрасывая самую старую. Обрезка может породить ложный конфликт, но не потерю данных. Riak позже перешёл на dotted version vectors, которые точнее отличают конкурентные записи.

Собираем всё вместе: симуляция кластера

Код ниже продолжает два предыдущих блока: Ring, descends и increment уже определены. Узел хранит для ключа список версий без перекрытых, координатор пишет на NN реплик с подменой упавших, чтение собирает версии с RR реплик и заодно чинит отставшие (read repair).

def reconcile(versions): """Оставить только версии, которые не перекрыты другими (siblings).""" uniq = {tuple(sorted(c.items())): (v, c) for v, c in versions}.values() return [ (v, c) for v, c in uniq if not any(c != c2 and descends(c2, c) for _, c2 in uniq) ] class Node: def __init__(self, name): self.name, self.up, self.data, self.hints = name, True, {}, [] def store(self, key, versions): self.data[key] = reconcile(self.data.get(key, []) + versions) class Cluster: def __init__(self, names, n=3, r=2, w=2): self.nodes = {x: Node(x) for x in names} self.ring, self.n, self.r, self.w = Ring(names), n, r, w def put(self, key, value, context=None): home = self.ring.preference_list(key, len(self.nodes)) coord = next(self.nodes[x] for x in home if self.nodes[x].up) clock = increment(context or {}, coord.name) spare = [self.nodes[x] for x in home[self.n:] if self.nodes[x].up] acks = 0 for target in home[: self.n]: node = self.nodes[target] if not node.up: # sloppy quorum if not spare: continue node = spare.pop(0) node.hints.append((target, key, [(value, clock)])) node.store(key, [(value, clock)]) acks += 1 if acks < self.w: raise RuntimeError(f'only {acks} acks, need W={self.w}') return clock def get(self, key): home = self.ring.preference_list(key, self.n) alive = [self.nodes[x] for x in home if self.nodes[x].up][: self.r] if len(alive) < self.r: raise RuntimeError('not enough replicas for R') versions = reconcile([v for nd in alive for v in nd.data.get(key, [])]) for nd in alive: # read repair nd.store(key, versions) return versions def recover(self, name): self.nodes[name].up = True for holder in self.nodes.values(): # hinted handoff for hint in [h for h in holder.hints if h[0] == name]: self.nodes[name].store(hint[1], hint[2]) holder.hints.remove(hint) holder.data.pop(hint[1], None) # временная копия больше не нужна c = Cluster(['A', 'B', 'C', 'D', 'E']) key = 'cart:7' print('replicas:', c.ring.preference_list(key, 3)) ctx = c.put(key, ['book']) c.nodes['B'].up = False # одна реплика упала c.put(key, ['book', 'pen'], ctx) print('hints:', {x: len(nd.hints) for x, nd in c.nodes.items() if nd.hints}) c.recover('B') print('B after handoff:', c.nodes['B'].data[key]) # Два клиента прочитали одну версию и пишут параллельно (_, base), = c.get(key) c.put(key, ['book', 'pen', 'lamp'], base) c.nodes['B'].up = False # координатором станет другой узел c.put(key, ['book', 'pen', 'mug'], base) c.nodes['B'].up = True for value, clock in c.get(key): print('sibling:', value, dict(sorted(clock.items())))

Вывод:

replicas: ['B', 'D', 'C']
hints: {'A': 1}
B after handoff: [(['book', 'pen'], {'B': 1, 'D': 1})]
sibling: ['book', 'pen', 'lamp'] {'B': 2, 'D': 1}
sibling: ['book', 'pen', 'mug'] {'B': 1, 'D': 2}

Что здесь видно:

  1. Пока B лежал, его копию принял A с подсказкой. После возвращения B получил пропущенную версию, а у A временная копия удалена.
  2. Две записи от одной базовой версии через разных координаторов дали две конкурентные версии. Хранилище не выбрало победителя, а вернуло обе: решать клиенту.

Симуляция упрощает многое: нет таймаутов, сети и параллельности, подсказки удаляются вместе со всем ключом. Но логика версий та же, что в настоящей системе.

Anti-entropy: Merkle-деревья

Read repair чинит только те ключи, которые кто-то читает. Hinted handoff теряется, если упал сам узел с подсказками. Нужна фоновая сверка реплик, но сравнивать терабайты ключ за ключом слишком дорого.

Merkle-дерево решает это так. Пространство ключей узла делится на диапазоны, каждый лист — хеш содержимого своего диапазона, каждый внутренний узел — хеш детей. Две реплики сравнивают корни. Совпали — данные одинаковые, сверка закончена за один хеш. Не совпали — спускаются только в несовпадающие поддеревья и в итоге обмениваются ключами лишь из расходящихся листьев.

import hashlib BUCKETS = 16 # листья: диапазоны пространства ключей (степень двойки) def digest(*parts: bytes) -> bytes: return hashlib.sha256(b'|'.join(parts)).digest() def bucket_of(key: str) -> int: return int.from_bytes(hashlib.md5(key.encode()).digest()[:4], 'big') % BUCKETS def build(store: dict) -> list: """Дерево в виде уровней: levels[0] — листья, levels[-1] — [корень].""" leaves = [[] for _ in range(BUCKETS)] for key in sorted(store): leaves[bucket_of(key)].append(digest(key.encode(), store[key].encode())) level = [digest(*items) if items else digest() for items in leaves] levels = [level] while len(level) > 1: level = [digest(level[i], level[i + 1]) for i in range(0, len(level), 2)] levels.append(level) return levels def diff(a: list, b: list, depth=None, idx=0, stats=None) -> list: """Спуститься только в несовпадающие поддеревья, вернуть номера листьев.""" if depth is None: depth = len(a) - 1 stats['compared'] += 1 if a[depth][idx] == b[depth][idx]: return [] if depth == 0: return [idx] return (diff(a, b, depth - 1, 2 * idx, stats) + diff(a, b, depth - 1, 2 * idx + 1, stats)) replica1 = {f'user:{i}': f'v{i}' for i in range(10_000)} replica2 = dict(replica1) replica2['user:777'] = 'v777-new' # пропущенное обновление del replica2['user:4242'] # пропущенная запись stats = {'compared': 0} bad = diff(build(replica1), build(replica2), stats=stats) to_sync = [k for k in replica1.keys() | replica2.keys() if bucket_of(k) in bad and replica1.get(k) != replica2.get(k)] print('different buckets:', bad) # [12, 13] print('hashes compared:', stats['compared'], 'of', 2 * BUCKETS - 1) # 9 of 31 print('keys to sync:', sorted(to_sync)) # ['user:4242', 'user:777']

Из 31 хеша сравнили 9, а ключи передавать нужно только из двух листьев из 16. В настоящей системе листьев десятки тысяч, и экономия становится огромной: при единичных расхождениях передаётся ничтожная доля данных.

Практические детали, о которых стоит упомянуть:

  • Дерево на каждый диапазон кольца. Узел хранит отдельное дерево на каждый свой диапазон, потому что с разными соседями у него разные общие ключи. При изменении раскладки кольца деревья пересчитываются, и это дорого.
  • Когда строить. Cassandra строит деревья во время nodetool repair, читая данные с диска. Это тяжёлая операция, её запускают по расписанию, по частям.
  • Удаления. Удалённый ключ нельзя просто стереть: сверка решит, что на другой реплике он есть, и вернёт его обратно. Поэтому удаление — это запись-надгробие (tombstone), которая живёт какое-то время. В Cassandra это gc_grace_seconds, по умолчанию 10 дней, и repair должен проходить чаще.

Хранение на одном узле

Внутри каждого узла нужен локальный движок. Под нагрузку «много записей» обычно берут LSM-дерево, как в Cassandra и RocksDB:

  1. Запись сначала идёт в журнал (commit log) на диск, затем в отсортированную структуру в памяти, memtable.
  2. Заполненная memtable сбрасывается на диск неизменяемым отсортированным файлом, SSTable.
  3. Фоновая компакция сливает SSTable, выкидывая перекрытые версии и старые надгробия.
  4. Чтение проверяет memtable, затем SSTable от новых к старым. Чтобы не открывать файлы зря, у каждого SSTable есть фильтр Блума: «ключа точно нет» отсекает лишнее чтение с диска.

Альтернатива — B-дерево, как в классических реляционных базах: чтения быстрее и предсказуемее, а случайная запись дороже. Сравнение структур есть в статье про B-деревья.

Членство и обнаружение отказов

  • Gossip. Каждый узел периодически обменивается со случайным соседом таблицей «узел → состояние, версия». Информация расходится по кластеру за O(log⁡n)O(\log n) раундов.
  • Временный или постоянный отказ. Узел, переставший отвечать, считается временно недоступным: его подменяют через hinted handoff, данные не переносят. Окончательное удаление узла из кольца — явное действие администратора, иначе одна перезагрузка запускала бы переезд терабайтов.
  • Детектор отказов. Вместо фиксированного таймаута Cassandra использует phi accrual detector: он оценивает подозрительность узла по распределению интервалов между heartbeat и меньше ошибается на нестабильной сети.
  • Seed-узлы. Несколько известных адресов, к которым подключается новый узел, чтобы не получилось двух кластеров, не знающих друг о друге.

Как рассказывать на собеседовании

Удобный порядок на 30–40 минут:

  1. Требования и выбор. «Запись всегда доступна, согласованность в конечном счёте, настраиваемая на запрос. Без лидера». Если нужна строгая согласованность, честно сказать, что дизайн будет другим.
  2. Оценка. Объём, реплики, число узлов, операции в секунду на узел.
  3. API. get(key) -> (values[], context), put(key, value, context). Контекст — это векторные часы, без них клиент не сможет разрешить конфликт.
  4. Партиционирование. Кольцо и виртуальные узлы, ссылкой на известную технику, без долгого вывода.
  5. Репликация и кворумы. N=3N = 3, R=W=2R = W = 2, почему пересечение и что оно не гарантирует.
  6. Отказы. Sloppy quorum, hinted handoff, read repair, Merkle-деревья — от быстрых механизмов к медленным.
  7. Конфликты. LWW или векторные часы, и почему выбор зависит от данных.
  8. Узел изнутри. LSM, commit log, фильтр Блума.

Вопросы, которые спросят дальше

ВопросЧто ответить
Зачем векторные часы, если есть timestamp?Часы серверов расходятся, LWW молча теряет одну из конкурентных записей. Векторные часы конфликт обнаруживают
Что будет, если запись дошла до одной реплики из трёх?Клиент получит ошибку, но значение останется на реплике и может всплыть при чтении или repair. Запись нужно повторять идемпотентно
Как добавить узел?Новый узел забирает виртуальные точки и стримит соответствующие диапазоны с текущих владельцев
Чем sloppy quorum опасен?При разделении записи и чтения могут не пересечься, даже если R+W>NR + W > N
Как работают удаления?Надгробия, которые живут дольше интервала repair. Иначе удалённое воскреснет
Как поддержать горячий ключ?Кэш перед хранилищем, чтение с любой из NN реплик, для записей — разнесение по нескольким ключам
Что выбрать для счётчика лайков?CRDT-счётчик: каждая реплика считает свои инкременты, слияние — сумма. Конфликтов нет

Частые ошибки

  • Начинать с кольца. Сначала требования: от выбора между доступностью и строгой согласованностью зависит вся остальная схема.
  • «R + W > N — значит, строгая согласованность». Это пересечение кворумов, а не линеаризуемость. Тем более при sloppy quorum.
  • Реплики на соседних виртуальных точках. Две копии на одной машине — это одна копия.
  • Забыть про удаления. Без надгробий anti-entropy воскрешает удалённые ключи.
  • Путать Dynamo и DynamoDB. Статья 2007 года описывает внутреннюю leaderless-систему Amazon. Сервис DynamoDB устроен иначе: у каждой партиции есть лидер, реплики согласуются через Paxos, а векторные часы клиенту не отдаются.
  • Объяснять механизмы без цены. Каждый пункт таблицы «Коротко» чем-то платит: это интервьюер и хочет услышать.

Потренироваться в спокойной обстановке

Все задачи