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

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

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

Кто-нибудь может привести пример использования CRDT в распределенных системах? Заранее большое спасибо.

12 голосов | спросил fnaticRC ggwp 10 ThuEurope/Moscow2015-12-10T04:41:02+03:00Europe/Moscow12bEurope/MoscowThu, 10 Dec 2015 04:41:02 +0300 2015, 04:41:02

3 ответа


0

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 /блог /Роши-а-CRDT-система-для-отметками времени-событий

ответил Metin Dagcilar 15 MarpmTue, 15 Mar 2016 16:16:38 +03002016-03-15T16:16:38+03:0004 2016, 16:16:38
0

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

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

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

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

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

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

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

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

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

Еще одна отличная статья на эту тему.

ответил Siddhartha 12 +03002017-10-12T04:02:43+03:00312017bEurope/MoscowThu, 12 Oct 2017 04:02:43 +0300 2017, 04:02:43
0

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

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

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

ответил cliffordheath 10 ThuEurope/Moscow2015-12-10T05:21:10+03:00Europe/Moscow12bEurope/MoscowThu, 10 Dec 2015 05:21:10 +0300 2015, 05:21:10

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132