Что такое CRDT в распределенных системах?
Я новичок в распределенных системах и пытаюсь понять концепцию CRDT. Я понимаю, что это имеет три обозначения:
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
Кто-нибудь может привести пример, где мы используем CRDT в распределенных системах? Заранее большое спасибо.
3 ответа
CRDT вдохновлены работой Марка Шапиро. В распределенных вычислениях бесконфликтный реплицируемый тип данных (сокращенно CRDT) представляет собой тип специально разработанной структуры данных, используемой для достижения высокой конечной согласованности (SEC) и монотонности (отсутствие откатов). Существует два альтернативных пути обеспечения SEC: операционные CRDT и основанные на состоянии CRDT.
CRDT в разных репликах могут отличаться друг от друга, но в конце они могут быть безопасно объединены, обеспечивая в конечном итоге согласованное значение. Другими словами, CRDT имеют метод слияния, который является идемпотентным, коммутативным и ассоциативным.
Две альтернативы эквивалентны, так как одна может эмулировать другую, но основанные на работе CRDT требуют дополнительных гарантий от коммуникационного промежуточного программного обеспечения. CRDT используются для репликации данных на нескольких компьютерах в сети, выполняя обновления без необходимости удаленной синхронизации. Это может привести к конфликтам слияния в системах, использующих обычную технологию возможной согласованности, но CRDT разработаны так, что конфликты математически невозможны. В соответствии с ограничениями теоремы CAP они обеспечивают самые строгие гарантии согласованности для доступных / терпимых к разделу (AP) настроек.
Несколько примеров, где они используются
Riak является самой популярной библиотекой CRDT с открытым исходным кодом и используется Bet365 и League of Legends. Ниже приведены некоторые полезные ссылки, поддерживающие Riak.
1- Bet365 (использует Erlang и Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2- League of Legends использует реализацию Riak CRDT для своей системы внутриигровых чатов (которая обрабатывает 7,5 млн одновременно работающих пользователей и 11 000 сообщений в секунду).
3- Roshi, реализованный SoundCloud, который поддерживает набор с меткой времени LWW: -Блог: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
CRDT используют Math для обеспечения согласованности в распределенном кластере, не беспокоясь о консенсусе и связанной с ним задержке / недоступности.
Множество значений, которые CRDT может принимать в любое время, подпадает под категорию полурешетки (в частности, полурешетки соединения), которая является POSET (частично упорядоченным множеством) с функцией наименьшей верхней границы (LUB).
Проще говоря, POSET - это набор предметов, в котором не все сопоставимы. Например, в массиве пар: {(2,4), (4, 5), (2, 1), (6, 3)}, (2,4) это < (4,5), но не может сравниться с (6,3) (так как один элемент больше, а другой меньше). Теперь полурешетка - это POSET, в которой заданы две пары, даже если вы не можете сравнить две пары, вы можете найти элемент больше, чем обе (LUB).
Другое условие состоит в том, что обновления этого типа данных должны увеличиваться, CRDT имеют монотонно возрастающее состояние, когда клиенты никогда не наблюдают откат состояния.
Эта превосходная статья использует массив, который я использовал выше в качестве примера. Для CRDT, поддерживающего эти значения, если две реплики пытаются достичь консенсуса между (4,5) а также (6,3) они могут выбрать LUB = (6,5) в качестве консенсуса и назначить обе реплики к нему. Так как значения растут, это хорошее значение для обоснования.
Существует два способа синхронизации CRDT друг с другом по репликам: они могут периодически передавать состояние через (конвергентный реплицируемый тип данных) или могут передавать обновления (дельты) по мере их поступления (коммутативный реплицируемый тип данных). Первый занимает больше пропускной способности.
Roshi SoundCloud - хороший пример (хотя, кажется, больше не в разработке), они хранят данные, связанные с меткой времени, где метка времени явно увеличивается. Любые обновления, поступающие с отметкой времени, меньшей или равной сохраненной, отбрасываются, что обеспечивает идемпотентность (повторные записи в порядке) и коммутативность (неправильные записи в порядке. Коммутативность a=b means b=a, что в данном случае означает, что update1, за которым следует update2, совпадает с update2, за которой следует update1)
Записи отправляются во все кластеры, и если определенные узлы не отвечают из-за такой проблемы, как медлительность или раздел, ожидается, что они позже будут перехвачены через read-repair, который гарантирует, что значения сходятся. Конвергенция может быть достигнута с помощью 2 протоколов, как я уже упоминал выше, распространения состояния или обновления других реплик. Я верю, что Роши делает первое. Как часть read-repair, реплики обмениваются состоянием, и поскольку данные придерживаются свойства полурешетки, они сходятся.
PS. Системы, использующие CRDT, в конечном итоге становятся непротиворечивыми, то есть они принимают AP (высокую доступность и устойчивость к разделам) в теореме CAP.
Все эти три расширения аббревиатуры означают одно и то же.
CRDT сходится, если одни и те же операции, примененные в другой последовательности, дают (сходятся) один и тот же результат. То есть операции могут быть коммутированы - это коммутативный RDT. Причина того, что операции могут применяться в другой последовательности и при этом получать тот же результат, заключается в том, что операции не конфликтуют.
Таким образом, CRDT означает одно и то же, независимо от того, какое из трех расширений вы используете - хотя лично я предпочитаю "Конвергент".