Модуль: Распределённые системы · Уровень: Senior+

TL;DR#

Eventual consistency — гарантия, что при отсутствии новых записей все реплики в конце концов сойдутся к одному значению. Это слабая модель: нет гарантий, когда сойдутся и что прочитает клиент в промежутке. Приемлема там, где временное расхождение не ломает бизнес (лайки, счётчики просмотров, ленты, профили), и опасна там, где нужна линеаризуемость/сильная согласованность (деньги, остатки на складе, уникальность) — там нужны транзакции, кворумы или CRDT с подходящей семантикой. Ключевые механизмы: разрешение конфликтов (LWW — просто, но теряет данные при clock skew; vector clocks / version vectors — детектят causality и concurrent; CRDT — структуры, конфликты которых разрешаются автоматически и детерминированно), и репликация/восстановление (read repair, anti-entropy через Merkle trees и gossip, hinted handoff в стиле Dynamo).

Теория#

Что такое eventual consistency и где её место#

Из CAP: при сетевом разделении (P) система выбирает между Consistency (C, линеаризуемость) и Availability (A). AP-системы (Dynamo, Cassandra, Riak) выбирают доступность и предоставляют eventual consistency: пишем в любую доступную реплику, читаем из любой, а согласование откладываем.

Формально (определение Vogels): «если в систему не поступает новых обновлений, в конце концов все обращения вернут последнее обновлённое значение». Это liveness-гарантия (когда-нибудь), без safety-гарантий на то, что вы прочитаете в моменте.

Более сильные родственники (нужно различать):

• Strong eventual consistency (SEC) — реплики, получившие один и тот же набор апдейтов (в любом порядке), немедленно имеют идентичное состояние. Это свойство CRDT. Сильнее обычной EC, т.к. убирает неопределённость разрешения конфликтов.
• Causal consistency — сохраняется порядок причинно-связанных операций (если B видел A, все увидят A раньше B). Это самая сильная модель, совместимая с доступностью при разделении.
• Read-your-writes, monotonic reads, monotonic writes — session-гарантии, которые часто докручивают поверх EC, чтобы скрыть от пользователя аномалии.

Где приемлемо / где нет#

Правило senior+: EC выбирают осознанно для конкретных данных, а не «на всю систему». Часто гибрид: критичные инварианты — strong, остальное — eventual.

Конвергенция#

Конвергенция — гарантия, что реплики сойдутся. Чтобы это произошло автоматически и детерминированно, либо:

1. есть детерминированная функция разрешения конфликтов (merge), применяемая всеми репликами одинаково (CRDT — частный, математически обоснованный случай), либо
2. конфликты детектятся и решаются прикладным кодом / клиентом (Dynamo возвращает siblings), либо
3. конфликтов «по построению» нет (LWW выбирает «последнюю» запись — детерминированно, но с потерей данных).

Разрешение конфликтов#

Last-Write-Wins (LWW)#

Каждой записи присваивается timestamp; при конфликте побеждает запись с наибольшим timestamp. Проще некуда, не требует хранения истории.

Проблемы:

• Clock skew. Таймстемпы из физических часов разных узлов не синхронизированы идеально (NTP даёт миллисекунды-десятки мс расхождения). Узел с «убегающими вперёд» часами выигрывает все конфликты, даже если записал раньше реально.
• Потеря данных (silent data loss). Из двух конкурентных записей одна молча отбрасывается. Если два пользователя одновременно изменили разные поля — изменения проигравшего пропали без следа. LWW не различает «конкурентные» и «последовательные» записи — он всегда просто выбирает по времени.
• Не отражает причинность. Запись с меньшим timestamp может быть причинно более поздней (видела предыдущую), но проиграет.

LWW допустим, когда потеря одной из конкурентных записей бизнес-приемлема (кэш, последнее известное состояние сенсора) и когда есть приличная синхронизация часов (или используют логические/гибридные часы вместо физических — HLC снижает, но не убирает проблему конкурентности).

Vector clocks / Version vectors#

Механизм для обнаружения причинности и конкурентности (а не для автоматического разрешения). Каждая реплика ведёт счётчик; версия объекта — это вектор {node -> counter}.

Правила сравнения двух версий VA, VB:

• VA «happens-before» VB, если каждый компонент VA ≤ соответствующего в VB и хотя бы один строго меньше → VB новее, безопасно перезаписать.
• Симметрично для VB → VA.
• Если ни одно не доминирует (есть компонент где A>B и компонент где B>A) → версии конкурентны (concurrent), это конфликт, который нельзя разрешить автоматически по версиям.

Узлы X и Y, объект key:

write на X:  V = {X:1}
read+write на X: V = {X:2}              ── X:2 доминирует X:1 (последовательно)

параллельно read{X:1} → write на Y: V = {X:1, Y:1}

Сравниваем {X:2} и {X:1,Y:1}:
   X: 2 > 1   (A больше)
   Y: 0 < 1   (B больше)
 → ни один не доминирует → CONCURRENT → конфликт (siblings)

Разница терминов: vector clock обычно ассоциируется с событиями процессов (Lamport-style), version vector — с версиями реплицируемых данных. На собеседовании достаточно знать, что оба дают частичный порядок и детектят concurrent.

Что делать с конкурентными версиями: вернуть клиенту все siblings (как Dynamo/Riak) и пусть приложение мерджит (например, объединить корзины), либо применить CRDT-merge, либо как fallback — LWW.

Минус: вектор растёт с числом узлов/клиентов; нужны схемы усечения (pruning) с риском ложного детекта.

CRDT (Conflict-free Replicated Data Types)#

Структуры данных, спроектированные так, что операции merge коммутативны, ассоциативны и идемпотентны → реплики, получившие один набор апдейтов в любом порядке и с повторами, детерминированно сходятся к одному состоянию без координации (Strong Eventual Consistency). Конфликтов «по построению» не бывает — merge всегда определён.

Два класса:

• State-based (CvRDT, convergent). Реплики обмениваются полным состоянием; merge — это операция объединения (join) в решётке (least upper bound). Требования к merge: commutativity, associativity, idempotency (моноидальная/полурешёточная структура). Устойчив к потере/дублированию/переупорядочиванию сообщений (т.к. merge идемпотентен и коммутативен). Минус: гонять полное состояние дорого → дельта-CRDT.
• Op-based (CmRDT, commutative). Реплики рассылают операции, которые применяются на всех репликах. Требование: конкурентные операции коммутативны. Зато требует надёжной доставки exactly-once (или причинной доставки) — операции нельзя терять/дублировать (т.к. применение операции обычно не идемпотентно). Дешевле по трафику.

Канонические типы:

• G-Counter (grow-only counter). Вектор счётчиков по узлам {node -> count}. Инкремент — только своего компонента. Значение = сумма всех компонентов. Merge = поэлементный max. Только растёт.
• PN-Counter (positive-negative). Два G-Counter: P (инкременты) и N (декременты). Значение = sum(P) - sum(N). Позволяет и уменьшать. Важно: PN-Counter сам не запрещает отрицательное значение — для «не уходить в минус» (баланс, остаток) одного CRDT мало, нужны дополнительные инварианты/координация.
• OR-Set (Observed-Remove Set). Множество, где add побеждает concurrent remove корректно. Каждому элементу при добавлении присваивается уникальный тег; remove удаляет только наблюдавшиеся теги. Решает аномалию «удалил, но из-за concurrent add элемент остался/вернулся» лучше, чем 2P-Set или LWW-Set. Семантика «add-wins».
• LWW-Register — регистр с timestamp; merge выбирает значение с большим timestamp. По сути LWW, оформленный как CRDT (наследует проблему clock skew / потери конкурентной записи).

// G-Counter (state-based CvRDT). merge = поэлементный max.
type GCounter struct {
    nodeID string
    counts map[string]uint64
}

func (c *GCounter) Inc()        { c.counts[c.nodeID]++ }
func (c *GCounter) Value() uint64 {
    var s uint64
    for _, v := range c.counts { s += v }
    return s
}

// Merge коммутативен, ассоциативен и идемпотентен:
// max(a, max(b, c)) == max(max(a, b), c); max(a, a) == a; max(a,b)==max(b,a)
func (c *GCounter) Merge(other *GCounter) {
    for node, v := range other.counts {
        if v > c.counts[node] {
            c.counts[node] = v
        }
    }
}

Почему именно commutativity + associativity + idempotency: associativity и commutativity дают независимость от порядка доставки и группировки, idempotency — устойчивость к повторам. Вместе они означают, что merge — операция в join-полурешётке, а значит существует единственный least upper bound → детерминированная конвергенция.

Репликация и восстановление расхождений#

EC-система должна не только разрешать конфликты, но и активно подтягивать отставшие реплики.

Read repair (Dynamo / Cassandra)#

Во время чтения координатор опрашивает несколько реплик. Если обнаружил, что одни вернули устаревшие данные — он на лету записывает свежее значение в отставшие реплики (часто асинхронно, после ответа клиенту). Так «горячие» (читаемые) данные согласуются по ходу обращений. Минус: «холодные» данные, которые никто не читает, read repair не лечит → нужен ещё фоновой механизм (anti-entropy).

Anti-entropy#

Фоновый процесс, сравнивающий реплики целиком и устраняющий расхождения, чтобы и нечитаемые данные сходились.

• Merkle trees для эффективного сравнения. Дерево хешей: листья — хеши диапазонов ключей/значений, внутренние узлы — хеши детей, корень — хеш всего. Две реплики сравнивают корни: совпали → данные идентичны, обмен закончен. Не совпали → спускаются по дереву, сравнивая только расходящиеся поддеревья. Это даёт сравнение за O(различий·log N) и передачу только реально различающихся диапазонов, а не всего датасета. Cassandra использует Merkle trees при nodetool repair.

        root hash
        /        \
     h(L)        h(R)        ← реплики обмениваются хешами сверху вниз
    /    \      /    \
  h0     h1   h2     h3      ← спускаемся только туда, где хеши разошлись
  |      |    |      |
range0 range1 range2 range3  ← синхронизируем только различающийся диапазон

• Gossip protocol — эпидемическое распространение информации. Каждый узел периодически обменивается состоянием (membership, версии, метаданные, иногда сами данные) со случайно выбранными соседями. Информация расходится по кластеру за O(log N) раундов, без центрального координатора, устойчиво к отказам узлов. В Dynamo/Cassandra gossip используется для membership и failure detection; для самих данных — anti-entropy через Merkle trees.

Hinted handoff (Dynamo-style)#

Механизм поддержания доступности записи при временном падении реплики. Если узел-владелец данных (один из N реплик для ключа) недоступен в момент записи, координатор всё равно принимает запись и складывает её на другом узле вместе с «hint» — пометкой, какой узел был настоящим адресатом. Когда упавший узел возвращается, держатель hint передаёт ему отложенные записи (handoff) и удаляет hint.

write key=K, реплики {A, B, C}, узел C упал:

  координатор пишет в A, B, и в D с hint("это для C")
  ...
  C возвращается → D отдаёт ему накопленные записи (handoff) → hint удалён

Это поднимает доступность записи (sloppy quorum) ценой временной несогласованности; финальную согласованность гарантируют handoff + read repair + anti-entropy. Связано с понятием sloppy quorum / W кворумы: запись считается успешной, если приняли W узлов (возможно, не «настоящих» владельцев, а временных держателей).

Подводные камни / gotchas#

• LWW и clock skew. Победитель определяется физическими часами → узел с «спешащими» часами съедает чужие записи; конкурентные записи теряются молча. Для критичных данных LWW противопоказан.
• EC ≠ «потом точно правильно». Конвергенция гарантирует одинаковость реплик, но не корректность бизнес-инварианта. PN-Counter сойдётся к согласованному значению, которое может быть отрицательным балансом.
• Vector clocks детектят, но не решают. Они только говорят «конкурентно» — разрешение всё равно за приложением/CRDT/LWW.
• Рост vector clock. С числом клиентов/узлов вектор раздувается; усечение даёт ложные конфликты.
• OR-Set vs наивные множества. 2P-Set не даёт повторно добавить удалённый элемент; LWW-Set теряет данные. OR-Set решает, но хранит теги (память растёт, нужен GC tombstone’ов).
• Op-based CRDT требует надёжной (exactly-once / causal) доставки. Потеря или дубль операции ломает конвергенцию, т.к. операции обычно не идемпотентны. State-based устойчивее, но дороже по трафику (→ delta-CRDT).
• Read repair не лечит холодные данные. Нужен anti-entropy, иначе нечитаемые расхождения живут вечно.
• Hinted handoff и потеря hint’ов. Если узел-держатель hint упал до handoff, запись может потеряться → подстраховка кворумом и anti-entropy. Sloppy quorum ослабляет гарантии R+W>N.
• Tombstones. Удаление в EC-системах — это запись-маркер (tombstone), а не физическое удаление; преждевременный GC tombstone до полной репликации воскрешает удалённые данные (zombie). Cassandra gc_grace_seconds.
• Иллюзия read-your-writes. Записал в одну реплику, прочитал из другой — увидел старое. Нужны session-гарантии / sticky routing / кворумное чтение.

Вопросы на собеседовании#

В: Что именно гарантирует eventual consistency? О: Только то, что при прекращении новых записей все реплики в конце концов сойдутся к одному значению. Это liveness-гарантия без обещаний, когда это случится и что клиент прочитает в промежутке (можно увидеть устаревшее, неупорядоченное, откатывающееся значение). Корректность бизнес-инвариантов она не гарантирует.

В: Какие проблемы у Last-Write-Wins? О: Зависимость от физических часов → clock skew: узел с убегающими часами выигрывает конфликты несправедливо. И главное — тихая потеря данных: из двух конкурентных записей одна молча отбрасывается, изменения проигравшего исчезают. LWW не отличает конкурентные записи от последовательных и не учитывает причинность. Допустим только там, где такая потеря приемлема.

В: Зачем vector clocks, если есть таймстемпы? О: Таймстемпы дают только тотальный порядок по (ненадёжному) времени и не умеют отличить «B видел A» от «A и B произошли независимо». Vector clocks дают частичный порядок: точно определяют happens-before и, главное, детектят конкурентность (concurrent), то есть настоящие конфликты, которые нельзя разрешать по времени. Они конфликт обнаруживают, но не разрешают — это уже задача приложения/CRDT.

В: Что делает структуру CRDT и какие математические свойства нужны? О: Merge/операции должны быть коммутативны, ассоциативны и идемпотентны. Тогда реплики, получив один набор апдейтов в любом порядке и с повторами, детерминированно сходятся без координации (strong eventual consistency). Это эквивалентно тому, что merge — least upper bound в join-полурешётке.

В: State-based vs op-based CRDT? О: State-based (CvRDT) шлёт полное состояние, merge — идемпотентный коммутативный join; устойчив к потере/дублям/переупорядочиванию сообщений, но дорогой по трафику (решается delta-CRDT). Op-based (CmRDT) шлёт операции, требует, чтобы конкурентные операции были коммутативны, и требует надёжной exactly-once/causal доставки (операции обычно не идемпотентны), зато дешевле по трафику.

В: Чем OR-Set лучше простого множества с LWW? О: OR-Set присваивает каждому добавлению уникальный тег и при remove удаляет только наблюдавшиеся теги, реализуя семантику add-wins. Это корректно обрабатывает concurrent add/remove (элемент не «воскресает» ошибочно и concurrent add не теряется), в отличие от 2P-Set (нельзя повторно добавить) и LWW-Set (теряет данные по таймстемпу). Цена — хранение тегов и GC tombstone’ов.

В: Можно ли хранить денежный баланс в PN-Counter? О: С осторожностью. PN-Counter сойдётся к согласованной сумме инкрементов минус декрементов, но он не гарантирует инвариант «не ниже нуля» — реплики независимо разрешают списания и сумма может уйти в минус. Для денег нужен либо строгий механизм (транзакции/линеаризуемый CAS/кворум) на критичную операцию, либо резервирование/бухгалтерия с компенсациями. CRDT хорош для счётчиков без жёстких инвариантов.

В: Read repair vs anti-entropy? О: Read repair синхронизирует реплики во время чтения: координатор замечает устаревшие реплики и дописывает им свежее значение. Лечит только читаемые («горячие») данные. Anti-entropy — фоновый процесс, сравнивающий реплики целиком (через Merkle trees) и подтягивающий и нечитаемые данные. Они дополняют друг друга.

В: Зачем Merkle trees в anti-entropy? О: Чтобы сравнить два больших датасета, не передавая их целиком. Реплики сравнивают корневые хеши: совпали — всё идентично, обмен окончен. Разошлись — спускаются по дереву только в расходящиеся поддеревья и синхронизируют лишь различающиеся диапазоны ключей. Стоимость ~ O(различий · log N) вместо полного сканирования.

В: Что такое hinted handoff? О: Механизм Dynamo для доступности записи при временно упавшей реплике: координатор принимает запись и кладёт её на запасной узел с «hint» — для кого она. Когда настоящий владелец оживает, держатель hint передаёт ему отложенные записи и удаляет hint. Это sloppy quorum: повышает доступность ценой временной несогласованности, которую затем добивают read repair и anti-entropy.

На что копают на senior+#

• Понимание разницы между eventual / strong eventual / causal consistency и session-гарантиями, и где каждая нужна.
• Умение объяснить, что EC гарантирует конвергенцию реплик, но не бизнес-инвариант (классический трюк-вопрос про баланс в PN-Counter).
• Глубокое понимание LWW: clock skew, тихая потеря данных, почему HLC/логические часы помогают частично, но не убирают проблему конкурентности.
• Vector/version vectors: happens-before, детект concurrent, рост вектора и pruning, что они только детектят, а разрешение — отдельно.
• CRDT по существу: математические свойства merge, разница CvRDT/CmRDT и вытекающие требования к доставке сообщений; конкретные типы (G/PN-Counter, OR-Set, LWW-Register) и их аномалии; delta-CRDT как оптимизация.
• Эксплуатационные механизмы Dynamo/Cassandra: кворумы R+W>N и sloppy quorum, read repair, hinted handoff, anti-entropy + Merkle trees, gossip, tombstones и gc_grace.
• Способность спроектировать гибрид: какие данные держать strong (consensus/CAS), какие — eventual (CRDT), и обосновать выбор по бизнес-рискам.