Когда полезно использовать что-то вроде CRDT вместо paxos или плота?
Бесконфликтные реплицируемые типы данных (CRDT) против Paxos или Raft
Ответ 1
Если вы можете использовать что-то вроде CRDT, сделайте это. Вы должны получить гораздо лучшую производительность. Он также позволяет использовать интересные варианты использования, такие как работа в автономном режиме, а затем слияние позже. Однако не всегда можно создавать такие вещи, что CRDT будет работать на вас. В этом случае paxos может решить трудные проблемы для вас.
Но даже если вы решили использовать paxos, как правило, вы должны ограничить, сколько работы выполняется непосредственно через алгоритм paxos. Вместо этого по соображениям производительности вы хотите зарезервировать paxos для необходимых операций, таких как мастер-выборы, а затем позволить реплицированной мастер-настройке обрабатывать большинство решений. (В среде с высокой пропускной способностью мастер, скорее всего, сделает что-то вроде делегирования ответственности за конкретные осколки конкретных детей, которые копируют друг друга. Не позволяйте хозяину стать узким местом...)
Тем не менее, гораздо легче утверждать, что вы будете махать волшебной палочкой паксо, чем на самом деле делать это на практике. В этом свете вы можете найти http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdf, чтобы быть интересным описанием трудностей, с которыми может столкнуться реализация paxos реального мира.
Ответ 2
Я думаю, что этот парень знает, о чем он говорит:
Ответ 3
Существует ошибка с примером CRDT Treedoc. Для каждого node требуется разборчивость для случая, когда две системы вставляются одновременно с одним и тем же ключом.
В этом случае системы не могут вставляться между записями, которые имеют идентичные ключи, но разные разрядники, так как это требует, чтобы система вставляла другой идентичный ключ, но контролировала порядок устранения неоднозначности. Демонстранты не плотные, поэтому это не всегда возможно. Если бы неоднозначность была еще одним деревом, вы решаете одну проблему, но затем нуждаетесь в еще одном механизме разрешения конфликтов глубиной ниже... и т.д.
Эта неявная проблема, плюс тот факт, что вам нужно сделать двухэтапную фиксацию, чтобы привести в порядок метаданные, заставляет меня думать, что CRDT все еще находятся в процессе разработки.
Ответ 4
CRDT и Paxos имеют разные цели и используются в разных сценариях. У них есть общее, что они помогают программистам иметь дело с concurrency/replication. CRDT - это типы данных, которые предполагают одновременное обновление. Paxos - это протокол, который принуждает их использовать, применяя к ним общий порядок. Давайте посмотрим на это более подробно.
Предположим, что у нас есть реплицированный набор, который реплицируется в двух разных местах.
Использование Paxos гарантирует, что запись в набор будет выполняться каждой репликой в том же порядке. В более общем плане он гарантирует, что все реплики СОГЛАСНЫ, как эволюционирует состояние множества.
Если у вас есть, например, user1, выполняющий update1 в replica1, добавляя элемент 1 к реплицированному набору, а одновременно user2 выполняет update2, добавив элемент2 в replica2, Paxos сделает реплики согласованными по данному заказу для этих обновлений или, возможно, согласен при выборе одного из двух обновлений и отбрасывании второго, в зависимости от того, как вы его используете и чего хотите достичь. Если результатом Paxos является, скажем, update1, предшествующий update2, каждая реплика обновит набор в этом порядке. Как следствие, пользователи, просматривающие набор одновременно с этими обновлениями, могут наблюдать, независимо от того, где (в какой реплике) они читают, ТОЛЬКО следующие состояния набора (при условии, что набор был пуст в начале):
{} (пустое множество)
{element1}
{element1, element2}
Кроме того, эти состояния можно видеть ТОЛЬКО в этом порядке, а это означает, что после того, как состояние набора будет {element1, element2} (на каждой реплике), последующее чтение не вернет {} или {element1}.
Положительная сторона: этот набор прост рассуждать, поскольку он эквивалентен множеству, который не реплицируется.
Отрицательная сторона: Недоступность: если реплики не могут разговаривать друг с другом (сетевой раздел), ваш набор не может быть обновлен, так как не может быть никакого соглашения. Низкая производительность, высокая задержка: соглашение требует, чтобы реплики синхронизировались до ответа клиенту. Это приводит к задержке, пропорциональной задержке между репликами.
CRDT имеют более слабые гарантии. Набор CRDT не эквивалентен последовательному, однократному. Он утверждает, что нет соглашения или общего порядка о том, как обновляются реплики.
CRDT гарантируют, что если обе копии набора имеют одинаковые обновления (независимо от порядка, в котором они видят их), то они будут показывать одно и то же состояние; реплики будут сходиться.
В нашем примере двух пользователей, выполняющих обновления одновременно, система, которая не запускает Paxos для выполнения операций по набору (это происходит, например, при возможной или причинной согласованности), позволит replica1 добавлять элемент1, в то время как replica2 добавляет элемент2
Таким образом, состояние в replica1 будет: {element1}
и состояние в replica2 будет: {element2}
На данный момент реплики расходятся. Позже, когда синхронизация реплик, они будут обмениваться своими обновлениями, наконец, демонстрируя это состояние:
состояние в replica1 будет: {element1, element2}
состояние в replica2 будет: {element2, element1}
В этот момент реплики сходились.
Пользователи, просматривающие набор одновременно с этими обновлениями, могут наблюдать, в зависимости от того, где (по какой реплике) они читают, следующие состояния набора (при условии, что набор был пустым в начале):
{} (пустое множество)
{element1} (если они читаются из replica1)
{element2} (если они читаются из replica2)
{element1, element2}
{element2, element1}
Отрицательная сторона: этот набор трудно рассуждать, так как он показывает состояния, которые не могут возникать в последовательном наборе. В нашем примере мы наблюдали только случай двух одновременных добавлений к множеству, что прямолинейно. Параллельные добавления и удаления более сложны. Существует много типов данных с различными проблемами:
Комплексное исследование конвергентных и коммутативных реплицированных типов данных
Положительная сторона: Высокая доступность: если реплики не могут разговаривать друг с другом (сетевой раздел), ваш набор CAN может быть обновлен. Реплики будут синхронизироваться при их подключении. Высокая производительность, низкая задержка: Replicas немедленно отвечает клиентам и синхронизируется в фоновом режиме после ответа клиенту.
Ответ 5
Есть несколько показателей:
- пропускная способность (CRDT и Paxos одинаковы, потому что все запросы реплицируются на все реплики в конце независимо от CRDT или Paxos);
- latency (CRDT лучше, чем Paxos, потому что он записывает меньшее количество реплик);
- надежность (CRDT слабее, чем Paxos, потому что он записывает меньшее количество реплик (меньше большинства), что может привести к потере состояния);
- Консистенция (CRDT слабее, чем Paxos, потому что позволяет одновременную запись без точки синхронизации (в основном, не перекрывающиеся реплики), в то время как записи Paxos всегда требуют дублирования реплики для сериализации).
Мое предположение заключается в том, что мы должны использовать Paxos, когда реплики находятся недалеко друг от друга (например, в центре обработки данных) и используют CRDT, когда сетевое разделение является нормальным (например, отключенным мобильным телефоном).
Ответ 6
Всякий раз, когда это уместно. Тем не менее, PaxOS не так уж плох, так как его пропускная способность, как правило, такая же, как и CRDT, не говоря уже о том, что надежность намного выше (CRDT может привести к потере состояния), и его латентность не так уж плоха, поскольку она требует только большинства ответов replicas вместо всех.