CRDT — различия между версиями
Yeputons (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 10 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
| − | CRDT (Conflict-Free Replicated Data Type) | + | '''CRDT (Conflict-Free Replicated Data Type)''' — типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами. |
| − | ''' | + | == Модель == |
| + | Мы отслеживаем состояние некоторых '''данных'''. | ||
| + | Всем узлам известно '''начальное состояние'''. | ||
| + | На самом деле мы отслеживанием не состояние данных, а '''операцию''', которую надо применить к начальным данным, чтобы получить текущие. | ||
| − | + | Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. | |
| + | Более формально: для любых двух операций $a$, $b$, $c$ верно: | ||
| + | # $a \sqcup a = a$ | ||
| + | # $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$ | ||
| + | # $a \sqcup b = b \sqcup a$ | ||
| − | + | Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. | |
| + | Так как операции коммутативны, нам неважен порядок и не нужен total order. | ||
| + | Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once. | ||
| + | Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию. | ||
| − | + | А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже. | |
| − | + | == Репликация на основе операций == | |
| − | + | Данные: целочисленный счётчик. | |
| − | + | Операция: добавить $x$ к значению счётчика. | |
| − | + | Эта операция коммутативна, но не идемпотентна. | |
| + | Поэтому добавим в каждой операции уникальный идентификатор. | ||
| + | |||
| + | Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций. | ||
| + | |||
| + | Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает. | ||
| + | |||
| + | == Репликация на основе состояния == | ||
| + | |||
| + | Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс. | ||
| + | |||
| + | Операция: установить компоненты в такие-то значения. | ||
| + | |||
| + | Объединение операций: покомпонентный максимум (коммутативно и идемпотентно). | ||
| + | |||
| + | Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем. | ||
| + | |||
| + | == $\delta$-CRDT == | ||
| + | |||
| + | Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение. | ||
| + | |||
| + | То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой. | ||
| + | |||
| + | Относится к обоим видам CRDT. | ||
Текущая версия на 19:44, 4 сентября 2022
CRDT (Conflict-Free Replicated Data Type) — типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
Содержание
Модель
Мы отслеживаем состояние некоторых данных. Всем узлам известно начальное состояние. На самом деле мы отслеживанием не состояние данных, а операцию, которую надо применить к начальным данным, чтобы получить текущие.
Нам требуется, чтобы операции образовывали полурешётку (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций. Более формально: для любых двух операций $a$, $b$, $c$ верно:
- $a \sqcup a = a$
- $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
- $a \sqcup b = b \sqcup a$
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием. Так как операции коммутативны, нам неважен порядок и не нужен total order. Так как операции идемпотентны, нам не нужна надёжная доставка (exactly once), достаточно at least once. Так что достаточно просто когда-нибудь как-нибудь услышать о проведённой операции, чтобы применить её к своему состоянию.
А вот как построить такую полурешётку, чтобы было не больно пересылать — интересный вопрос, см. ниже.
Репликация на основе операций
Данные: целочисленный счётчик.
Операция: добавить $x$ к значению счётчика.
Эта операция коммутативна, но не идемпотентна. Поэтому добавим в каждой операции уникальный идентификатор.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.
Репликация на основе состояния
Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс.
Операция: установить компоненты в такие-то значения.
Объединение операций: покомпонентный максимум (коммутативно и идемпотентно).
Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
$\delta$-CRDT
Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
Относится к обоим видам CRDT.
