State Synchronization

Два игрока в CS2 нажали стрелять одновременно. У кого засчитается килл? Google Docs: два человека удалили одно слово одновременно - что останется? Figma: дизайнер двигает объект пока другой меняет его цвет. Всё это - задача state synchronization, и у каждой системы свой ответ.

• CS2 64-tick сервер: каждые 15.6 мс сервер отправляет delta-снапшот всем клиентам. Только изменившиеся entity включаются в пакет. При потере пакета клиент интерполирует, не запрашивает повторно - latency критичнее точности.
• Google Docs Operational Transformation: каждое нажатие клавиши - это операция с revision number. Сервер трансформирует параллельные операции и broadcast'ит результат. 18 лет в продакшне, обрабатывает миллиарды документов.
• Figma CRDT: объекты на canvas хранятся как Last-Write-Wins регистры с Hybrid Logical Clocks (HLC) - комбинация физического времени и счётчика. Это позволяет работать offline и синхронизироваться после переподключения без потери данных.
• rsync delta algorithm: разбивает файл на блоки по 700 байт, вычисляет rolling checksum. Передаёт только блоки с изменившимися checksums. Типичная экономия - 97-99% трафика при инкрементальном бэкапе.

Что такое State Sync

State synchronization - это процесс согласования состояния между клиентом и сервером после того как оба прошли через независимые изменения. Ключевой вопрос: как клиент узнаёт, что сервер изменился, и как минимизировать трафик при этой передаче?

Три базовые стратегии: **Full State Transfer** (отправить всё целиком), **Delta Sync** (отправить только изменения), **Operational Sync** (отправить операции, а не данные). Каждая стратегия оправдана в разных условиях: размер состояния, частота изменений, требования к порядку применения.

• **Full state** - клиент получает полный снапшот. Просто, надёжно, но дорого при большом состоянии.
• **Delta** - клиент получает diff между версиями. Экономит трафик, требует контроля версий.
• **Operations** - клиент получает список действий (insert, delete, update). Позволяет merging.

rsync - классический пример гибридного подхода: сначала сравнивает checksums блоков (обнаруживает изменения), потом передаёт только изменившиеся блоки. Протокол rsync передаёт в среднем 1-3% объёма файла при инкрементальном бэкапе.

Snapshot и Delta Compression

Snapshot - полная копия состояния в момент времени T. Delta - разница между снапшотом T и снапшотом T+1. Хранить только дельты выгодно по трафику, но требует baseline для применения цепочки изменений. Если дельта N потеряна - цепочка разрывается.

CS2 (Counter-Strike 2) использует схему с keyframes: каждые 64 тика (1 секунда) сервер отправляет полный снапшот состояния (keyframe), между ними - только дельты. Если пакет потерян, клиент ждёт следующий keyframe вместо запроса ретрансмиссии - latency важнее полноты данных.

React reconciliation работает по схожей схеме: Virtual DOM - это снапшот UI-дерева. Reconciler вычисляет diff (дельту) между предыдущим и новым VDOM, затем применяет минимальное количество DOM-операций. Сложность алгоритма O(n) благодаря эвристикам (одинаковый тип узла, key prop).

1. Сервер присваивает каждому снапшоту монотонный версионный номер (tick/sequence).
2. Клиент при запросе delta передаёт свою текущую версию: `GET /sync?since=42`.
3. Сервер возвращает дельту от версии 42 до текущей, или полный снапшот если 42 слишком старая.
4. Клиент применяет дельту и обновляет локальную версию.

Operational Transformation и CRDT

Когда несколько клиентов редактируют одни и те же данные одновременно, delta-sync недостаточен - дельты могут конфликтовать. Два подхода решают эту проблему: **Operational Transformation (OT)** и **Conflict-free Replicated Data Types (CRDT)**.

**OT** - клиент отправляет операции (insert, delete) с позицией в документе. Сервер трансформирует операцию с учётом параллельно принятых операций от других клиентов. Google Docs использует OT с 2006 года: каждая операция содержит revision number, сервер трансформирует и broadcast'ит результат.

**CRDT** - данные структурированы так, что любое применение операций в любом порядке даёт одинаковый результат (commutative + associative + idempotent). Figma использует CRDT для объектов на canvas: позиция, цвет, z-index представлены как Last-Write-Wins регистры. Notion использует CRDT для блочного дерева документа.

Conflict Detection и Vector Clocks

Конфликт возникает когда два клиента изменяют одни данные, не зная об изменениях друг друга. Простая метка времени ненадёжна: часы на разных серверах/клиентах расходятся. Vector clocks - распределённый механизм определения порядка событий без глобальных часов.

Vector clock - это вектор счётчиков, по одному на каждый узел. Каждый узел инкрементирует свой счётчик при каждом событии. При отправке сообщения узел прикладывает текущий вектор. Получатель берёт max по каждой позиции. Если векторы несравнимы - события произошли параллельно (конфликт).

Amazon DynamoDB использует vector clocks для обнаружения конфликтов в eventually-consistent записях. При конфликте DynamoDB возвращает обе версии, и приложение должно их смёрджить (или выбрать одну). Riak (distributed database) popularized этот подход.

• **Last-Write-Wins (LWW)**: при конфликте побеждает запись с большим timestamp. Просто, но может терять данные. Используется в Cassandra (по умолчанию) и Figma (для большинства свойств).
• **Multi-Version Concurrency Control (MVCC)**: хранить обе версии, дать приложению смёрджить. Используется в PostgreSQL, CouchDB.
• **Application-level merge**: домен-специфичная логика - например счётчики складываются, множества объединяются (CRDT-подход).

Итоги

• **Full state vs delta**: полный снапшот прост и надёжен, delta экономит трафик но требует версионирования. При потере delta - fallback на full state.
• **OT vs CRDT**: Operational Transformation требует центрального сервера-координатора (Google Docs). CRDT работает peer-to-peer и детерминированно мёрджит без координации (Figma, Notion).
• **Vector clocks**: timestamp ненадёжен в распределённых системах. Vector clocks определяют happens-before отношения и обнаруживают concurrent конфликты без глобальных часов.
• **Conflict resolution**: Last-Write-Wins (Cassandra, Figma), MVCC (PostgreSQL, CouchDB), application-level merge (CRDT счётчики/множества). Выбор стратегии зависит от допустимости потери данных.

Связанные темы

State sync пересекается с несколькими фундаментальными темами распределённых систем:

• WebSockets и Server-Sent Events — Транспортный слой для доставки дельт и операций в реальном времени
• CAP теорема — Выбор между consistency и availability определяет допустимые стратегии sync (LWW vs strong consistency)
• Event Sourcing — Хранение истории операций вместо текущего состояния - natural fit для operational sync и построения дельт
• Optimistic UI — Клиент применяет операцию локально до подтверждения сервера, при конфликте откатывает - требует понимания sync протокола

Вопросы для размышления

• Мобильное приложение работает offline и накапливает изменения. При переподключении нужно смёрджить с сервером. Какую стратегию sync выбрать и почему?
• CS2 использует UDP (потери пакетов возможны), Google Docs использует TCP (гарантированная доставка). Как это влияет на выбор стратегии sync в каждом случае?
• CRDT гарантирует eventual consistency без конфликтов. Почему тогда не все системы используют CRDT вместо OT или LWW?

Связанные уроки

• db-04-cap