Что такое СRDT?

---

CRDT - Бесконфликтный, реплицируемый тип данных.

Это своего рода структура данных, которая может храниться на разных компьютерах.

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

Разные компьютеры могут иметь разные сотояние в разные моменты времени, но гарантированно в конечном итоге придут к единому согласованному состоянию.

Это делает эту структуру данных отличным выбором, для создания многофункциональных приложений для совместной работы, таких как Google Docs или Figma, без необходимости использовать центральный сервер для синхронизации состояний.

Существуют два типа CRDT:

1. на основе состояний - передают свое полное состояние между узлами, а новое состояние получается путем слияния всех состояний вместе.

2. на основе операции - передают только действия предпринимаемые пользователями, которые можно использовать для расчета нового состояния.

Основываясь на описании CRDT основанные на операциях звучат лучше, так как если при (условном) изменении списка CRDT на основе операций передадут лишь операцию "удаление элемета", а CRDT на основе состояния придется передать все состояние. Но СRDT на основе операция накладывают ограничение, операции должны быть доставлены узлу только один раз в причинно-следственном порядке каждому узлу.

CRDT - это любая структура данных реализующая данный интерфейс:

interface CRDT<V,S> { value: V; state: S; merge: (state: S): void; }

CRDT - это минимум три вещи:

1. Значение T, о котором заботится остальная часть нашей программы. Вся суть CRDT заключается в синхронизации этих значений

2. State S, необходимые узлам для согласования значений.

3. Функция принимающая состояние и объединяющая его с локальным.

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

обозначение - V = слияние A v V => A слить с V

1. Коммутативность: состояния можно объединять в любом порядке; A v B = B v A;

2. Ассоциативность: при объединении трех (или более) состояний не имеет значения, какое из них будет объединено первым; (A v B) v C = A v (B v C);

3. Идемпотентность: слияние состояния самого с собой не изменяет состояние; A v A = A;

Регистры. Last Writes Win (LWW) регистр

Регистры LWW, как следует из названия, просто перезаписывают свое текущее значение последним записанным значением. Они определяют, какая запись произошла последней, используя временные метки, представленные здесь целыми числами, которые увеличиваются при каждом обновлении значения.

Алгоритм:

• Если полученная временная метка меньше локальной временной метки, регистр не меняет свое состояние.

• Если полученная метка времени больше локальной метки времени, регистр перезаписывает свое локальное значение полученным значением. Он также сохраняет полученную метку времени и своего рода идентификатор, уникальный для узла, который последним записал значение (идентификатор узла).

• Связи разрываются путем сравнения идентификатора локального узла с идентификатором узла в полученном состоянии.

код для регистра в './LWW.ts';

• state - представляет собой кортеж из идентификатора узла, который последним записывал в регистр, метки времени последней записи и значения, хранящегося в регистре.

• value - это просто последний элемент кортежа state.

• merge — метод, реализующий описанный выше алгоритм.

Last Write Wins Map

Большинство программ используют более одного значения,это означает, что нам понадобится более сложный CRDT, чем регистр LWW. Та, о которой мы сегодня узнаем, называется «Last Write Wins Map» (или «Карта LWW»).

Начнем с определения пары типов. Во-первых, наш тип значения:

type Value<T> = { [key: string]: T; };

Если каждое отдельное значение карты имеет тип T, то значение всей карты LWW представляет собой сопоставление строковых ключей с T значениями.

Вот наш тип состояния:

type State<T> = { [key: string]: LWWRegister<T | null>["state"]; };

код для мапы в './LWWMap.ts';