Что такое CRDT в распределенных системах?

Question

Я новичок в распределенных системах, и я пытаюсь получить представление о концепции CRDT. Я понимаю, что у него есть три обозначения:

Conflict-free Replicated Data Type 
Convergent Replicated Data Type 
Commutative Replicated Data Type 

Может кто-нибудь привести пример, когда мы используем CRDT в распределенных системах? Большое спасибо.

Answer 1

CRDT вдохновлены работой Марка Шапиро. В распределенных вычислениях тип реплицированных без конфликтов типов (сокращенный CRDT) представляет собой тип специально разработанной структуры данных, используемой для достижения сильной конечной согласованности (SEC) и монотонности (отсутствие откатов). Существует два альтернативных пути обеспечения SEC: основанных на работе CRDT и государственных CRDT.

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

Эти две альтернативы эквивалентны, так как можно эмулировать другую, но основанные на эксплуатации CRDT требуют дополнительных гарантий от промежуточного программного обеспечения связи. CRDT используются для репликации данных на нескольких компьютерах в сети, выполняющих обновления без необходимости удаленной синхронизации. Это приведет к слиянию конфликтов в системах с использованием традиционной технологии последовательной согласованности, но CRDT разработаны таким образом, что конфликты математически невозможны. В соответствии с ограничениями теоремы CAP они обеспечивают самые сильные гарантии согласованности для доступных/разделенных томами (AP) настроек.

Некоторые примеры, в которых они используются

Riak является самым популярным открытым исходным кодом библиотека CRDT и используется на Bet365 и Лиги Легенд. Ниже приведены некоторые полезные ссылки, которые поддерживают Riak.

1- Bet365 (использует Erlang и Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

2- Лига Легенд использует реализацию Riak CRDT для своей системы чата в игре (которая обрабатывает 7,5 млн одновременных пользователей и 11000 сообщений в секунду)

3- Роши реализован SoundCloud, который поддерживает LWW время отметок Set: -Blog поста: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

Answer 2

Эти три расширения аббревиатуры означают в основном одно и то же.

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

Таким образом, CRDT означает то же самое, какой бы из трех расширений вы ни использовали - хотя лично я предпочитаю «конвергентный».

Answer 3

CRDTs использовать математику для обеспечения согласованности между распределенным кластером, не беспокоясь о консенсусе и а ssociated latency/unavailability.

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

Проще говоря, ПОЗЕТ представляет собой набор предметов, в которых не все сопоставимы. Например. в массиве пар: {(2,4), (4, 5), (2, 1), (6, 3)}, (2,4) - < (4,5), но не может сравниться с (6,3) (поскольку один элемент больше, а другой меньше). Теперь полурешетка представляет собой POSET, в котором заданы 2 пары, даже если вы не можете сравнить их, вы можете найти элемент, который больше, чем оба.

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

Этот excellent article использует массив, который я использовал выше в качестве примера. Для CRDT, поддерживающего эти значения, если 2 реплики пытаются достичь консенсуса между и (6,3), они могут выбрать LUB = (6,5) в качестве консенсуса и назначить для него как реплики. Поскольку значения увеличиваются, это хорошее значение для расчета.

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

SoundCloud's Roshi - хороший пример (хотя, по-видимому, он больше не работает), они хранят данные, связанные с меткой времени, где метка времени явно увеличивается. Любые обновления, входящие в временную метку, меньшую или равную той, которая хранится, отбрасываются, что гарантирует, что идемпотентность (повторяющиеся записи в порядке) и коммутативность (из-за отсутствия записи в порядке. Commutativity - a=b means b=a, что в данном случае означает update1, за которым следует update2 то же, что и update2, а затем update1)

Писания отправляются во все кластеры, и если определенные узлы не могут ответить из-за проблемы, например, медленности или раздела, ожидается, что они будут позже догонять через read-repair, что гарантирует, что значения сходятся. Конвергенция может быть достигнута с помощью двух протоколов, как я упоминал выше, распространения состояния или обновлений для других реплик. Я считаю, что Роши делает первое. Как часть read-repair, состояние обмена репликами, и поскольку данные соответствуют свойству полурешетки, они сходятся.

PS. Системы, использующие CRDT, в конечном итоге согласуются, то есть они принимают AP (высокодоступные и устойчивые к перегородке) в CAP theorem.

Another excellent read on the subject.