anti-entropy-merkle.js·4 scenarios
Anti-entropy reconciliation between two replicas using Merkle trees: full repair (root match), partial diff (recurse into mismatched subtree), hinted handoff (short outage), and tombstone resurrection anti-pattern (skipped repair past gc_grace_seconds).
В leaderless/multi-leader репликации (Cassandra, DynamoDB, Riak) реплики расходятся молча: hinted handoff может потерять hint, network partition оставляет stale ack, bit-flip портит блок на диске, баг в одном из коннекторов пишет только в одну реплику. Без активного процесса reconciliation эта дельта никогда не схлопнется сама: quorum read честно вернёт большинство, не зная, что большинство уже неправо; удалённый ключ воскреснет, когда offline-реплика вернётся; audit-отчёты будут показывать разные суммы в зависимости от того, к какой реплике подключился dashboard.
Anti-entropy — это фоновый процесс, который специально для этого случая существует: он периодически сравнивает реплики и насильно сводит их к единому состоянию. Merkle tree — главная техника, позволяющая делать это сравнение bandwidth-efficient: вместо «отправь мне все 100 GB, я сделаю diff» — обменяться парой 32-байтных хешей и спуститься в дерево только там, где видна разница.
Без понимания anti-entropy нельзя осмысленно эксплуатировать Cassandra/Scylla/Riak/DynamoDB: пропуск nodetool repair на неделю-другую — частая причина инцидентов «удалённые ключи вернулись» и «реплики разъехались на гигабайты, repair теперь идёт сутки».
«Три слоя обороны от divergence: read repair (синхронно, при чтении), hinted handoff (для коротких outage'ев), active anti-entropy через Merkle tree (фон, raid-сейфети). Merkle tree сводит сравнение двух датасетов к рекурсивному спуску по дереву хешей: одинаковые поддеревья пропускаем целиком, спускаемся только там, где root mismatch. Bandwidth = O(d × log N), где d — число расходящихся ключей, а не N целиком.»
Ключевая интуиция: anti-entropy — это не «механизм репликации», это safety net поверх репликации. Основной путь данных — это quorum write, replication stream, hinted handoff. Anti-entropy включается тогда, когда основной путь по той или иной причине провалился — и должен «вытянуть» состояние обратно к норме, заплатив за это фоновым CPU/IO/network.
Второй угол: Merkle tree превращает задачу «сравнить два больших состояния» в задачу «сравнить два маленьких дерева хешей». Best case (реплики идентичны) — один обмен root-хешами, ~64 байта на всё сравнение. Worst case (полное расхождение) — ходим по всему дереву и стримим все блоки. Реальный production-кейс — промежуточный: 0.001% ключей разошлись, обмен — несколько KB хешей плюс несколько KB данных.
На канвасе — упрощённый Cassandra-стиль anti-entropy:
Replica A и Replica B в разных AZ. Каждая держит свой data-store (data-a, data-b) и собственное Merkle tree (mt-a, mt-b), построенное поверх данных.nodetool repair или Cassandra Reaper: оркестрирует обмен root-хешами, спуск по дереву, стриминг diverged ranges.data → mt (построение дерева), coordinator → mt (выборка хешей), mt-a ↔ mt-b (стриминг diverged блоков), data-a → hint-store → data-b (буферизация и replay hints). Анимация ходит по этим же ребрам в обе стороны (reverse animation) для ответов.Это сознательно простая топология — две реплики и один координатор. В реальном кластере координатором становится одна из нод (по rotation), Merkle деревья строятся per-token-range, и параллельно гонятся repair-сессии для разных ranges. Идея та же.
1. Full repair — root match, exit in 1 round. Best case: реплики идентичны. Координатор тянет ROOT_A и ROOT_B, видит совпадение, заканчивает сессию. Bandwidth — 2 хеша (~64 байта) вместо 100 GB scan. Учит: Merkle tree даёт O(1) bandwidth в healthy случае — поэтому anti-entropy можно гонять часто и не бояться сетевого storm'а, если реплики на самом деле не разъехались.
2. Partial diff — recurse into mismatched subtree. Один ключ разошёлся (например, write дошёл только до A из-за packet loss на финальной replication-фазе). Координатор видит mismatch root, спускается на следующий уровень, видит что левое поддерево совпадает (пропускает), правое — нет. Рекурсивно спускается вправо до листа, находит конкретный divergent key (user_42), запускает стриминг этой одной строки от A к B. Учит: bandwidth ≈ log N хешей + сами расходящиеся блоки. На триллион строк — около 40 хешей (~1.3 KB) + несколько KB данных, а не миллион+ строк.
3. Hinted handoff — short outage, no AAE needed. Реплика B отключилась на 30 секунд. Координатор буферизирует writes, адресованные B, в hinted-handoff store. B возвращается онлайн, координатор реплейит hints. Merkle pass не нужен — hinted handoff закрыл разрыв. Учит: AAE — это не единственная и не первая линия обороны. Для коротких outage'ев hinted handoff дешевле и быстрее. Gotcha: если у hint'а истёк TTL или координатор сам упал — hints теряются, и тогда уже AAE — единственный способ обнаружить пропажу.
4. Tombstone resurrection — repair AFTER gc_grace_seconds. Самый коварный anti-pattern. Day 0: DELETE foo на A, tombstone записан. B в этот момент offline, tombstone не получила. Day 0..10: никто не запускал repair. Day 11: gc_grace_seconds истёк, A компактит tombstone и забывает о ключе foo навсегда. Day 12: B возвращается, у неё всё ещё foo=value. Запускается repair — координатор видит, что у B есть ключ, у A нет, обращает delete вспять: реплицирует foo=value обратно на A. Удалённая запись воскресает. Учит: операционное правило repair frequency < gc_grace_seconds — не «рекомендация», а математическая необходимость. Любое отклонение = silent corruption.
ADR-001: Anti-entropy = background reconciliation, three-mechanism defense.
nodetool repair (full, incremental, sub-range, primary-range). Riak держит persistent Merkle trees на диске и крутит continuous AAE.ADR-002: Repair cadence — sweet spot 1-3 дня, hard ceiling = gc_grace_seconds.
compaction_throughput_mb_per_sec. Жёсткое правило: repair frequency strictly меньше gc_grace_seconds. Если gc_grace_seconds=10d, repair минимум раз в неделю с запасом. Никогда не отключать repair «временно» без предварительного снижения gc_grace_seconds до 0 — иначе resurrection гарантирован.ADR-003: Merkle tree vs naive bulk-compare.
d << N (типичный healthy case). При d ≈ N (нода восстанавливается с нуля) дешевле bulk-copy / bootstrap, AAE не нужен.nodetool repair (full / incremental / sub-range / primary-range), Cassandra Reaper для scheduling, canonical AAE.gc_grace_seconds. Tombstone resurrection: удалённые записи возвращаются. Cassandra документация прямо предупреждает, но игнорируют постоянно.gc_grace_seconds не снижен до 0 — гарантированный resurrection при включении.N < ~1000 элементов). Merkle overhead не оправдан. Дешевле передать всё.cassandra.apache.org/doc/latest/cassandra/operating/repair.html) — самый прозрачный industrial gold standard, включая sub-range и primary-range nuances.nodetool repair, scheduling и monitoring.