Привет, Хабр!

Сегодня мы поговорим о том, как справиться с синхронизацией данных в офлайн‑режиме так, чтобы не сваливать на пользователя головную боль слияния конфликтов. Вы наверняка замечали, что многие современные приложения — будь то заметки, менеджеры задач или вики‑редакторы — позволяют работать оффлайн на нескольких устройствах, а при подключении к сети автоматически объединяют изменения. Задача разработчика в таком случае сделать максимально гладкую синхронизацию одновременно изменённых данных на разных узлах, ideally без участия пользователя в разрешении конфликтов.

Классические решения вроде Operational Transformation давно применяются, например, в совместном редактировании документов. Но сегодня я хочу рассказать про другой подход — CRDT.

Offline-first и автоматическое слияние данных

Представим ситуацию: пользователь Аlice и пользователь Bob работают с одним и тем же документом, но без интернета. Оба вносят правки офлайн. Alice переименовала папку в «Проект X», а Bob — в «Project X Final». Когда приложение снова выходит в сеть, изменения нужно объединить. Что делать, если оба одновременно поменяли одно и то же? Наивное объединение строк даст ерунду, а спрашивать у пользователя «чьё название оставить?» — плохой UX. Можно, конечно, просто взять последний по времени вариант (так называемый последний записавший победил), но тогда второй пользователь рискует не понять, куда делись его правки.

Проблема синхронизации офлайн‑изменений упирается в разрешение конфликтов. Либо это делает сервер, либо сами клиенты между собой. CRDT как раз относится к P2P‑подходу: каждая копия данных сама умеет смешивать изменения без центрального арбитра. Идея CRDT в том, что данные организуются особым образом, при котором все параллельные операции коммутативны и идемпотентны. Проще говоря, неважно в каком порядке и сколько раз применить набор всех изменений, итоговое состояние данных станет одинаковым на всех узлах. Конфликтов не возникает вовсе: все реплики автоматически сходятся к единому состоянию без потери правок, а разработчику не нужно прописывать сложную логику разрешения коллизий. Звучит здорово, правда?

Конечно, у такого подхода есть и нюансы. Например, если мы хотим предоставить пользователям выбор при конфликте, с CRDT это непросто, ведь по задумке конфликтов нет, побеждает заранее заданная политика (например, последняя правка). Также придётся мириться с дополнительными метаданными (версии, метки времени), а иногда и с «вечным ростом» структуры (удалённые элементы хранятся как tombstones). Однако, во многих сценариях автоматическое слияние намного выгоднее, чем заставлять пользователя разбираться в хитросплетениях версий данных.

Давайте разберёмся, что же такое эти CRDT и как они работают под капотом.

Что такое CRDT и зачем он нужен

CRDT (Conflict‑free Replicated Data Type) — это «бесконфликтный реплицируемый тип данных». Проще говоря, это такая структура данных, которая может существовать в нескольких копиях, при этом каждая копия может независимо изменяться без координации с другими, а при обмене обновлениями все реплики в итоге автоматически приходят к одному и тому же состоянию. Конфликтующие обновления разрешаются по заранее заданным правилам, встроенным в саму структуру.

CRDT обеспечивают так называемую strong eventual consistency — сильную конечную согласованность. Это значит, что пока один узел не получил чьи‑то изменения, его состояние может временно отличаться (то есть, может быть устаревшим, out‑of‑date), но никогда не бывает неверным с точки зрения бизнес‑логики данных. Рано или поздно (когда все обновления доставятся) состояния выровняются. Для этого не нужен общий мутекс, не нужен распределённый консенсус. Достаточно, чтобы все операции имели свойство коммутативности (меняются местами без влияния на результат) и идемпотентности (повторное применение не изменяет результат). Эти свойства позволяют нам не беспокоиться о порядке или потерях сообщений при рассылке изменений — даже если какие‑то обновления придут позже или дважды, итогу это не повредит.

CRDT разрабатывались учёными для распределённых систем, и за десятилетия придумано много видов таких структур. Но не пугайтесь грозных терминов полурешётка, монотонная функция слияния или вектор версий. Главное понять: CRDT делает невозможное возможным, позволяет редактировать одни и те же данные в разных местах и получать единый результат без конфликтов.

Добиваются этого двумя основными способами, о которых стоит сказать пару слов, прежде чем писать код:

• State‑based CRDT (CvRDT) — реплики периодически обмениваются состояниями целиком. При получении состояния от соседа узел выполняет операцию merge: объединяет чужое состояние со своим по определённой функции слияния. Эта функция обычно берет некое наибольшее значение для каждого элемента данных (например, максимум двух версий счётчика или объединение двух множеств). Требуется, чтобы слияние было коммутативным и идемпотентным, тогда неважно, в каком порядке и сколько раз придёт одно и то же состояние — результат стабильно сходится. Плюс такого подхода — простота: можно терять или дублировать сообщения, всё равно догоните. Минус — приходится передавать все данные, что накладно для больших структур.

• Operation‑based CRDT (CmRDT) — вместо состояний узлы рассылают операции. Каждая операция (например, «добавить элемент X», «увеличить счётчик на 1») должна применяться у всех и при этом давать корректный результат независимо от порядка применения. Проще говоря, все операции должны коммутировать. Это часто требует дополнительного снабжения операций метаданными (уникальными идентификаторами и пр.), а также надёжной доставки (чтобы не потерять апдейты). Плюс — трафика гораздо меньше (операции обычно компактнее, чем весь state). Минусы — сложнее реализация и больше требований к сети.

Есть и компромиссные варианты, например тот же δ‑based CRDT, когда пересылаются не все данные, а только дельты изменений. Но в этой статье мы не будем углубляться в теорию. Вместо этого перейдём к практике: реализуем несколько простых CRDT‑структур на Go и посмотрим, как они помогут в офлайн‑сценариях.

Реализация G-Counter: grow-only счётчик

Начнём с примитивного, но показательного примера — Grow‑Only Counter (G‑Counter), он же монотонно увеличивающийся счётчик. Такой счётчик может только расти (инкрементироваться), но никогда не уменьшается. Это простейший CRDT типа «счётчик кликов»: каждое увеличение локально суммируется, а при слиянии с другим счётчиком берётся максимум по каждой реплике, чтобы не потерять ничего.

Как это выглядит в коде. Мы заведём структуру GCounter с уникальным идентификатором реплики и мапой счётчиков по каждой реплике:

import "fmt"

type GCounter struct {
    id     string
    counts map[string]int
}

// Конструктор нового счётчика с заданным ID узла
func NewGCounter(id string) *GCounter {
    return &GCounter{
        id:     id,
        counts: make(map[string]int),
    }
}

// Локальное увеличение счётчика на 1 (можно и на любое значение)
func (c *GCounter) Inc() {
    c.IncVal(1)
}

func (c *GCounter) IncVal(delta int) {
    c.counts[c.id] += delta
}

// Получить текущее значение счётчика (сумма по всем репликам)
func (c *GCounter) Value() int {
    total := 0
    for _, v := range c.counts {
        total += v
    }
    return total
}

// Слияние состояний двух счётчиков (результат записывается в получатель)
func (c *GCounter) Merge(other *GCounter) {
    for replica, otherVal := range other.counts {
        if currVal, ok := c.counts[replica]; !ok || otherVal > currVal {
            c.counts[replica] = otherVal
        }
    }
}

Каждый узел (реплика) ведёт свой локальный подсчёт в слоте counts[id]. Когда мы вызываем Inc(), увеличивается значение только для текущей реплики. Допустим, у нас есть два устройства: A и B. Если на A вызвать Inc() три раза, а на B один раз, то локально у A будет counts = {"A": 3}, у B — {"B": 1}. Метод Value() просто суммирует все значения мапы, то есть показывает агрегированный счётчик.

МетодMerge берет другую копию счетчика и для каждого известного идентификатора реплики сравнивает значения: выбираем максимальное. Почему максимум? Потому что счётчик только растёт, и большее значение означает, что где‑то этих инкрементов накопилось больше. Беря максимум, мы не потеряем ни одного увеличения при объединении данных.

Операция Merge коммутативна и идемпотентна. Если несколько раз применить одни и те же данные, результат не изменится. Также неважно, в каком порядке мерджить несколько реплик: хоть A с B, потом результат с C, хоть по другому пути — в итоге все придут к одной сумме. Этот CRDT‑счётчик гарантирует конвергенцию без гонок.

Протестируем мысленно или на небольшом примере, как это работает. Создадим два счётчика и выполним независимые обновления, а затем сольём их состояния:

func main() {
    a := NewGCounter("A")
    b := NewGCounter("B")

    a.Inc()        // A = 1
    a.IncVal(2)    // A = 3 (суммарно)
    b.Inc()        // B = 1

    fmt.Println("A до слияния:", a.Value()) // 3
    fmt.Println("B до слияния:", b.Value()) // 1

    // Объединяем состояния
    a.Merge(b)
    b.Merge(a)

    fmt.Println("A после слияния:", a.Value()) // 4
    fmt.Println("B после слияния:", b.Value()) // 4
}

После локальных операций значения на A и B различались. Но после обмена состояниями (мы вызвали Merge на обоих — в реальной распределённой среде они обменялись бы пакетами) оба получили сумму 4. Мы добились Strong Eventual Consistency — оба узла сошлись к единому состоянию, учитывающему все инкременты.

Заметим, что G‑Counter решает только очень простой кейс. Например, если нужно ещё и уменьшать значение, G‑Counter уже не подойдёт. Для этого существует расширение — PN‑Counter.

PN-Counter: двунаправленный счётчик

PN‑Counter (Positive‑Negative Counter) позволяет не только увеличивать, но и уменьшать счётчик, сохраняя при этом идемпотентность и сходимость. Идея довольно проста: можно представить общий счётчик как разность двух G‑Counter'ов. Один счётчик учитывает все инкременты, другой — все декременты. Тогда уменьшение на 1 превращается в «увеличить значение во втором (отрицательном) счётчике на 1». Текущая величина — это разность первого и второго.

Реализуем PN‑Counter в Go. По сути, достаточно хранить две мапы (или два экземпляра GCounter) внутри структуры.

type PNCounter struct {
    id  string
    inc map[string]int
    dec map[string]int
}

func NewPNCounter(id string) *PNCounter {
    return &PNCounter{
        id:  id,
        inc: make(map[string]int),
        dec: make(map[string]int),
    }
}

func (c *PNCounter) Inc() {
    c.IncVal(1)
}
func (c *PNCounter) IncVal(delta int) {
    c.inc[c.id] += delta
}
func (c *PNCounter) Dec() {
    c.DecVal(1)
}
func (c *PNCounter) DecVal(delta int) {
    c.dec[c.id] += delta
}

func (c *PNCounter) Value() int {
    totalInc, totalDec := 0, 0
    for _, v := range c.inc {
        totalInc += v
    }
    for _, v := range c.dec {
        totalDec += v
    }
    return totalInc - totalDec
}

func (c *PNCounter) Merge(other *PNCounter) {
    // объединяем положительные счетчики
    for replica, otherVal := range other.inc {
        if currVal, ok := c.inc[replica]; !ok || otherVal > currVal {
            c.inc[replica] = otherVal
        }
    }
    // объединяем отрицательные счетчики
    for replica, otherVal := range other.dec {
        if currVal, ok := c.dec[replica]; !ok || otherVal > currVal {
            c.dec[replica] = otherVal
        }
    }
}

Логика аналогична G‑Counter: каждый узел пишет свои инкременты в inc[ID], а декременты в dec[ID]. Слияние берёт по каждому узлу максимум значений из двух копий, отдельно для карты инкрементов и для карты декрементов. В результате суммарная разность после Merge учтёт все + и — со всех реплик.

Например, если устройство A прибавило 5 (inc_A = 5), а устройство B вычло 3 (dec_B = 3), то после обмена данными у объединённого PN‑Counter будет inc_A = 5, dec_B = 3, и итоговое значение Value() станет 2 (5-3). Неважно, в каком порядке и сколько раз эти операции прилетят — благодаря Merge(max) результат стабилен. Кстати, в коде мы могли бы переиспользовать GCounter для частей, но для наглядности написал в лоб.

PN‑Counter не позволит итоговому значению уйти в минус за счёт какой‑то гонки — отрицательное значение получится только если действительно декрементов суммарно больше, чем инкрементов. Зато сам по себе PN‑counter не ограничивает от ухода в бесконечный минус (если постоянно декрементировать на разных репликах). Существуют и более сложные ограниченные счётчики, но их реализация выходит за рамки статьи.

Итак, мы научились считать числа без конфликтов. Перейдём к более сложному типу данных — множество элементов.

LWW-Set: Last-Write-Wins множество

Со счётчиками было довольно просто: их значения естественно агрегируются суммой или максимумом. А вот с множество (set) начинаются интересные моменты. Операции Add(element) и Remove(element) не коммутативны сами по себе: если применить add(X) потом remove(X), элемент убран; а вот в обратном порядке remove потом add — элемент останется. Порядок даёт разный результат. Значит, нужно придумать, как закодировать эти операции так, чтобы итог не зависел от порядка.

Существует несколько видов CRDT‑множеств. Самое простое — G‑Set (Grow‑only Set), аналог нашего G‑Counter: допускает только добавление. Удалять элементы нельзя, поэтому конфликтов нет, а слияние — просто объединение множеств. Но такой тип мало практичен: множество будет расти вечно. Более интересный вариант — 2P‑Set (двухфазное множество). В нём есть два набора: A для добавленных элементов и R для удалённых (tombstones). Когда мы Add(x), мы помещаем x в A; когда Remove(x) — помещаем x в R. Элемент считается присутствующим, если он есть в A и не в R. Слияние выполняется по обоим подмножествам объединением. Ограничение 2P‑Set: повторно добавить элемент после удаления нельзя (две фазы жизни: добавлен → удалён, всё). Где это может не подойти? Например, в совместном документе пользователь удалил слово, а потом другой пользователь опять его вставил — 2P‑Set такое вставленное слово уже не посчитает «новым», оно ведь было в tombstones.

Для возможности повторных операций придумано несколько стратегий. Одна из популярных — LWW‑Set (Last‑Write‑Wins Set). Здесь каждому добавлению и удалению присваивается метка времени (timestamp), и при конфликте «добавить vs удалить» побеждает операция с более новым временем. Проще говоря, последнее действие с элементом выигрывает. Если элемент добавили позже, чем удалили (даже на другом узле), он останется. Если удаление оказалось последней операцией, элемент будет убран.

Реализуем LWW‑Set. Возьмём две структуры данных: addSet и removeSet, которые будут хранить для каждого элемента время последнего добавления и времени последнего удаления соответственно. В качестве времени будем использовать метку UnixNano() (наносекунды текущего времени). В распределённой системе часы на узлах могут идти не синхронно, но в практических системах допустимо предположить, что порядок по wall‑clock приблизительно совпадает с реальным порядком событий. Для надёжности часто добавляют ещё и уникальный ID узла в паре с временем, чтобы разбить ничьи, но мы не будем усложнять.

Вот код LWW‑Set на Go:

import (
    "sync"
    "time"
)

type LWWSet struct {
    mu        sync.Mutex
    addMap    map[string]int64
    removeMap map[string]int64
}

func NewLWWSet() *LWWSet {
    return &LWWSet{
        addMap:    make(map[string]int64),
        removeMap: make(map[string]int64),
    }
}

// Добавить элемент с текущим timestamp
func (s *LWWSet) Add(element string) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.addMap[element] = time.Now().UnixNano()
}

// Удалить элемент с текущим timestamp
func (s *LWWSet) Remove(element string) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.removeMap[element] = time.Now().UnixNano()
}

// Проверить наличие элемента с учётом приоритета по времени
func (s *LWWSet) Contains(element string) bool {
    s.mu.Lock()
    defer s.mu.Unlock()
    addTS, added := s.addMap[element]
    remTS, removed := s.removeMap[element]
    if !added && !removed {
        return false
    }
    if !removed {
        return true // никогда не удаляли, значит точно есть
    }
    if !added {
        return false // никогда не добавляли (но удаление было) — значит нет
    }
    // И добавление, и удаление были: кто позже, то и определяет состояние
    return addTS > remTS
}

// Слить два LWW-Set в текущий (путём взятия максимальных меток для каждого элемента)
func (s *LWWSet) Merge(other *LWWSet) {
    s.mu.Lock()
    defer s.mu.Unlock()
    // объединяем add-метки
    for elem, otherAddTS := range other.addMap {
        ts, exists := s.addMap[elem]
        if !exists || otherAddTS > ts {
            s.addMap[elem] = otherAddTS
        }
    }
    // объединяем remove-метки
    for elem, otherRemTS := range other.removeMap {
        ts, exists := s.removeMap[elem]
        if !exists || otherRemTS > ts {
            s.removeMap[elem] = otherRemTS
        }
    }
}

Разберём логику LWW‑Set. Метод Add(x) записывает в addMap[x] текущее время, Remove(x) — в removeMap[x]. Таким образом мы фиксируем моменты последних операций. Метод Contains(x) сначала проверяет, встречался ли элемент вообще. Если не было ни добавления, ни удаления — сразу false. Если было добавление, но не было удаления — true. Если наоборот, удаляли, но никогда не добавляли (скажем, кто‑то удалил элемент, которого в его копии не было — такое может быть, если операция дошла в другом порядке) — то элемента нет. Самый интересный случай: элемент и добавляли, и удаляли в этой объединённой истории. Тогда сравниваем два timestamp: чей больше, тот и «победил». Если addTS > remTS, значит последней операцией было добавление, элемент присутствует; иначе (удаление произошло позже) элемента нет.

Операция Merge похожа на предыдущие реализации: мы пробегаем по всем элементам в структурах other и подтягиваем себе все метки времени, которые новее наших. Берём максимум по каждому элементу для добавлений и удалений соответственно. В результате наш LWW‑множество будет содержать информацию о самых свежих операциях со всех реплик.

Как это поможет избежать конфликтов? Представим два устройства, работающие офлайн. В устройстве A пользователь удалил запись «Документ1» в 12:00. В устройстве B в 12:05 (позже) тот же «Документ1» отредактировали и, естественно, он там присутствует (то есть по факту операция добавления/изменения произошла после удаления на другом узле). При синхронизации наш LWW‑Set для «Документ1» получит addTS = 12:05, remTS = 12:00, то есть addTS > remTS, элемент останется. Последняя запись победила, как и задумано. Обратная ситуация: если редактирование (добавление) было раньше, а удаление — позже, тогда remTS будет больше и элемент исчезнет у всех. То есть, мы приходим к согласованному состоянию без явного конфликта — выбор сделан по правилу «чья правка новее, то и считаем истиной».

Важно подчеркнуть: политика LWW (last write wins) — всего лишь одна из возможных. Она удобна и проста, но может быть неуместна, скажем, для банковских транзакций (где «последним записавшим» может оказаться отрицательный баланс). Для чисел обычно применимы коммутативные суммы, для логических флагов — варианты вроде OR‑Set, для строк — часто используют специальные последовательностные CRDT (RGA, WOOT и так далее), которые тут даже не пытаюсь реализовать — это весьма сложно. Однако базовые принципы всё те же: добавить нужные метаданные, чтобы операции не конфликтовали, и определить детерминированное правило слияния.

Синхронизация офлайн-данных на практике

Теперь, когда у нас есть несколько реализованных CRDT‑структур, представим, как их использовать в реальном приложении. Допустим, мы делаем распределённый TODO‑лист с офлайн‑режимом. У каждого пользователя хранится локальная копия списка задач в виде CRDT. Это может быть, например, LWW‑множество задач (где каждая задача — элемент, а удаление/добавление задач решается по last‑write) плюс, скажем, CRDT‑карты для свойств задач (существуют CRDT Map, в которой значения могут быть опять же LWW или счетчиками). Пользователь отмечает задачу выполненной — ставится флажок (можно представить как OR‑Set флагов). Другой пользователь удалил эту задачу практически одновременно. В итоге при синхронизации благодаря нашим структурам данных система сама разрулит ситуацию: либо задача останется (если отметка «выполнено» пришла позже удаления, задача восстановится и будет выполненной), либо исчезнет полностью (если удаление было последней операцией).

CRDT хороши тем, что их можно реплицировать через произвольные коммуникации: можно слать диффы по WebSocket, можно сохранить локально и синхронизировать при подключении — не нужен центральный сервер, достаточно, чтобы рано или поздно каждый узел получил изменения остальных. В офлайн‑first приложениях часто устраивают периодическую фоновую синхронизацию: например, раз в N секунд или при появлении сети отправлять свой state на другие узлы (или на сервер‑хаб, который ретранслирует). При этом нет строгих требований к порядку или единственности доставки. Если какой‑то пакет потерялся, при следующем обмене Merge догонит состояние (так как мы берём максимумы/объединения, мы ничего не пропустим). Дубликаты тоже не проблема: применив одно и то же дважды, мы получим тот же результат (идемпотентность). Это радикально упрощает логику синхронизации по сравнению с традиционными подходами. Не нужна сложная координация, не нужна блокировка записей. Каждый узел автономен в офлайне и всегда может принять локальное изменение, не рискуя испортить данные на других.

Конечно, CRDT — не серебряная пуля. Цена за автоматическую консистентность — более сложные структуры данных и дополнительная память. Например, наше LWW‑множество хранит удалённые элементы навечно (tombstones) — иначе если два человека одновременно удалят один элемент, а потом каждый попробует добавить, система может перепутать старое удаление с новым добавлением. Есть оптимизации (например, выкидывать tombstone, если известно, что все реплики уже видели удаление). Другой нюанс — часы: LWW полагается на метки времени, а они в распределённой среде не идеальны. В продакшене стоит использовать либо монотонные часы, либо добавлять к таймстампу ID узла и сравнивать лексикографически, чтобы гарантировать детерминированный порядок даже при равных метках. И не забываем про авторизацию и права доступа: если данные приходят напрямую от клиентов, надо встроить проверки, кто что может менять (но это уже тема для отдельной статьи).

Однако, несмотря на эти сложности, CRDT‑библиотеки уже применяются на практике. Они легли в основу local‑first подхода, когда пользовательские данные хранятся у самого пользователя с синхронизацией на фоне. Примеры — текстовые редакторы без центрального сервера (на JS известны Automerge, Yjs), распределённые базы данных (Riak использовал внутрь OR‑Set и регистры LWW, Cassandra для колонок применяет LWW‑регистры. В Go тоже есть реализации: можно взглянуть на библиотеку neurodrone/crdt, где представлены и наши G/PN‑Counter, и LWW‑Set, и даже OR‑Set. Но всегда полезно понять внутреннюю кухню, реализовав всё с нуля.

В итоге, Conflict‑free Replicated Data Types позволяют нам писать приложения, которые «просто работают» в офлайне. Пользователь свободно редактирует данные без сети, а при подключении все изменения автоматически совмещаются. Мы рассмотрели, как своими руками сделать несколько базовых CRDT на Go. Они, конечно, упрощены для учебных целей, зато демонстрируют главную идею: добавляя немного метаданных и заранее определив правило слияния, можно избавиться от необходимости разрешать конфликты вообще.

Надеюсь, этот разбор был вам полезен.

Если вы уже знакомы с Go и хотите углубиться в устройство языка, понять, как строятся масштабируемые сервисы и освоить инструменты профессиональной разработки, обратите внимание на курс Golang Developer. Professional. На странице курса можно записаться на бесплатные уроки, а также пройти вступительный тест для оценки знаний.

Рост в IT быстрее с Подпиской — дает доступ к 3-м курсам в месяц по цене одного. Подробнее