CRDT в AP-распределённых NoSQL СУБД
2012-12-20 12:44 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
waqurRiak — AP-распределённая NoSQL база данных, которая реализует интересный подход к автоматическому разрешению конфликтов данных — они используют "свободные от конфликтов реплицируемые типы данных" (CRDT).
Презентация
PDFка статьи
Вкратце, идея заключается в том, чтобы вместо простого скалярного значения (например целое, строка, множество) хранить больше информации — payload. На множестве всех payload заданы две основных операции: операция отображения в скаляр (query), и операция устранения конфликтов при репликации (merge). Также, все модифицирующие операции над объектом редактируют payload, а не скаляр.
Согласно теореме из статьи, если merge построена корректно (порождает на множестве всех payload верхнюю полурешётку), и части распределённой системы хотя-бы изредка могут обмениваться сообщениями, тогда это является достаточным условием для "согласованности в конечном итоге" (eventual consistency).
Презентация и статья объясняют, как именно можно реализовать стандартные CRDT-типы: LWW-строка (last write wins), целочисленный счётчик (одно- и двунаправленный), множество (с исключением элементов и без него). Для каждого из этих типов строится payload, query и merge.
Основной недостаток этого подхода заключается в том, что для множеств с включением-исключением они фактически хранят полный список всех когда-либо включённых и исключённых элементов; так что множество, которое активно редактируется, будет разрастаться в памяти до неприличных размеров. Для борьбы с этим безобразием применяется чисто инженерный подход: сборка мусора (хотя распределённая сборка мусора и partition tolerance — плохо совместимые вещи).
Авторы Riak'а додумались написать его на наркоманском Erlang'е, но в целом как исследовательский проект он довольно интересен. Это своего рода аналог IBM System/R или NSCA Mosaic.
Кстати, есть более поздняя статья тех же авторов, о которой мало кто знает:
http://arxiv.org/abs/1210.3368
(An optimized conflict-free replicated set)
Там они всё-таки придумали способ, как можно сконструировать payload, query и merge для "множеств с включением-исключением", чтобы payload не включал в себя все те элементы, которые когда-то очень давно были удалены из множества. В общем, payload больше не разрастается в памяти до бесконечности, так что сборка мусора теперь не нужна.
Это намного, намного лучше первой попытки. Optimized Observed Remove Set (OOR-множество) — так это теперь называется.
По сути, первая статья была только обобщением идеи векторных часов; вторая статья представляет некоторую новую технику, ещё пока не воплощённую в программном коде (по состоянию на данный момент).
Презентация
PDFка статьи
Вкратце, идея заключается в том, чтобы вместо простого скалярного значения (например целое, строка, множество) хранить больше информации — payload. На множестве всех payload заданы две основных операции: операция отображения в скаляр (query), и операция устранения конфликтов при репликации (merge). Также, все модифицирующие операции над объектом редактируют payload, а не скаляр.
Согласно теореме из статьи, если merge построена корректно (порождает на множестве всех payload верхнюю полурешётку), и части распределённой системы хотя-бы изредка могут обмениваться сообщениями, тогда это является достаточным условием для "согласованности в конечном итоге" (eventual consistency).
Презентация и статья объясняют, как именно можно реализовать стандартные CRDT-типы: LWW-строка (last write wins), целочисленный счётчик (одно- и двунаправленный), множество (с исключением элементов и без него). Для каждого из этих типов строится payload, query и merge.
Основной недостаток этого подхода заключается в том, что для множеств с включением-исключением они фактически хранят полный список всех когда-либо включённых и исключённых элементов; так что множество, которое активно редактируется, будет разрастаться в памяти до неприличных размеров. Для борьбы с этим безобразием применяется чисто инженерный подход: сборка мусора (хотя распределённая сборка мусора и partition tolerance — плохо совместимые вещи).
Авторы Riak'а додумались написать его на наркоманском Erlang'е, но в целом как исследовательский проект он довольно интересен. Это своего рода аналог IBM System/R или NSCA Mosaic.
Кстати, есть более поздняя статья тех же авторов, о которой мало кто знает:
http://arxiv.org/abs/1210.3368
(An optimized conflict-free replicated set)
Там они всё-таки придумали способ, как можно сконструировать payload, query и merge для "множеств с включением-исключением", чтобы payload не включал в себя все те элементы, которые когда-то очень давно были удалены из множества. В общем, payload больше не разрастается в памяти до бесконечности, так что сборка мусора теперь не нужна.
Это намного, намного лучше первой попытки. Optimized Observed Remove Set (OOR-множество) — так это теперь называется.
По сути, первая статья была только обобщением идеи векторных часов; вторая статья представляет некоторую новую технику, ещё пока не воплощённую в программном коде (по состоянию на данный момент).
