Бесконфликтные реплицированные типы данных (CRDT) против Paxos или Raft
Когда стоит использовать что-то вроде CRDT вместо паксо или плота?
7 ответов
Если вы можете использовать что-то вроде CRDT, сделайте это. Вы должны получить гораздо лучшую производительность. Это также позволяет использовать интересные варианты использования, такие как работа в автономном режиме и последующее слияние. Однако не всегда возможно спроектировать вещи так, чтобы CRDT работал на вас. В этом случае, Paxos может решить сложные проблемы для вас.
Но даже если вы решили использовать paxos, обычно вы должны ограничить объем работы, выполняемой непосредственно с помощью алгоритма paxos. Вместо этого по соображениям производительности вы хотите зарезервировать paxos для необходимых операций, таких как выбор мастера, а затем позволить реплицированной настройке мастера обрабатывать большинство решений. (В среде с высокой пропускной способностью мастер, скорее всего, будет делать что-то вроде делегирования ответственности за определенные сегменты конкретным дочерним элементам, которые дублируют друг друга. Не позволяйте мастеру стать узким местом...)
Тем не менее, гораздо проще утверждать, что вы будете махать волшебной палочкой из паксо, чем на самом деле делать это на практике. В этом свете вы можете найти http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdf интересное описание трудностей, с которыми сталкивается реальный мир. Реализация paxos, вероятно, столкнется.
CRDT и Paxos имеют разные цели и используются в разных сценариях. Общим для них является то, что они помогают программистам справляться с параллелизмом / репликацией. CRDT - это типы данных, которые предполагают одновременное обновление. Paxos - это протокол, который обеспечивает их соблюдение, навязывая им общий порядок. Давайте посмотрим на это более подробно.
Допустим, у нас есть реплицированный набор, который реплицируется в двух разных местах.
Использование Paxos гарантирует, что запись в набор будет выполняться каждой репликой в том же порядке. В более общем смысле это гарантирует, что все реплики СОГЛАСНЫ с тем, как развивается состояние набора.
Если у вас есть, например, пользователь1, выполняющий обновление 1 в реплике 1, добавляющий элемент 1 в реплицируемый набор, в то время как одновременно пользователь 2 выполняет обновление 2, добавляющий элемент 2 в реплику 2, Paxos заставит реплики согласовать заданный порядок этих обновлений или, возможно, согласится выбрать одно. из двух обновлений и отказ от второго, в зависимости от того, как вы используете его и чего вы хотите достичь. Если исход Paxos, скажем, что update1 предшествует update2, каждая реплика будет обновлять набор в этом порядке. Как следствие, пользователи, читающие набор одновременно с этими обновлениями, могут наблюдать, независимо от того, где (в какой реплике) они читают, ТОЛЬКО следующие состояния набора (при условии, что набор был пустым в начале):
{} (пустой набор)
{} Element1
{element1, element2}
Кроме того, эти состояния могут быть видны ТОЛЬКО в таком порядке. Это означает, что если состояние набора равно {element1, element2} (на каждой реплике), никакое последующее чтение не вернет {} или {element1}.
Положительная сторона: этот набор прост для размышления, поскольку он эквивалентен набору, который не реплицируется.
Отрицательная сторона: недоступность: если реплики не могут общаться друг с другом (сетевой раздел), ваш набор не может быть обновлен, так как не может быть никакого соглашения. Низкая производительность, высокая задержка: соглашение требует, чтобы реплики синхронизировались перед ответом клиенту. Это приводит к задержке, пропорциональной задержке между репликами.
У CRDT более слабые гарантии. Набор CRDT не эквивалентен последовательному, единственному экземпляру. Предполагается, что нет соглашения или общего порядка в отношении того, как обновляются реплики.
CRDT гарантируют, что если обе реплики набора видели одинаковые обновления (независимо от того, в каком порядке они их видят), то они будут демонстрировать одинаковое состояние; реплики будут сходиться.
В нашем примере двух пользователей, выполняющих обновления одновременно, система, которая не запускает Paxos для упорядочивания операций на множестве (это происходит, например, при возможной или каузальной согласованности), позволит replica1 добавлять элемент1, в то время как replica2 добавляет элемент2
Итак, состояние в replica1 будет: {element1}
и состояние в replica2 будет: {element2}
На данный момент реплики расходятся. Позже, когда реплики синхронизируются, они будут обмениваться своими обновлениями, наконец, показывая это состояние:
состояние в реплике1 будет: {element1, element2}
состояние в replica2 будет: {element2, element1}
На данный момент реплики слились.
Пользователи, читающие набор одновременно с этими обновлениями, могут наблюдать, в зависимости от того, где (в какой реплике) они читают, следующие состояния набора (при условии, что набор был пуст в начале):
{} (пустой набор)
{element1} (если они читают из replica1)
{element2} (если они читают из replica2)
{element1, element2}
{element2, element1}
Отрицательная сторона: этот набор трудно рассуждать, так как он показывает состояния, которые не могли возникнуть в последовательном наборе. В нашем примере мы наблюдали только случай двух одновременных добавлений к набору, что просто. Параллельные добавления и удаления являются более сложными. Существует много типов данных с различными проблемами:
Комплексное исследование конвергентных и коммутативных реплицированных типов данных
Положительная сторона: высокая доступность: если реплики не могут общаться друг с другом (сетевой раздел), ваш набор МОЖЕТ быть обновлен. Реплики будут синхронизироваться при обратном подключении. Высокая производительность, низкая задержка: реплики немедленно отвечают клиентам и синхронизируются в фоновом режиме, после ответа клиенту.
В примере CRDT Treedoc есть недостаток. Каждый узел требует устранения неоднозначности для случая, когда две системы вставляют одновременно с одним и тем же ключом.
После того, как это произойдет, системы больше не смогут вставлять между записями, которые имеют одинаковые ключи, но разные неоднозначения, так как для этого требуется, чтобы система вставляла другой идентичный ключ, но контролировал порядок устранения неоднозначности. Двусмысленности не плотны, так что это не всегда возможно. Если устранение неоднозначности было еще одним деревом, вы решаете одну проблему, но затем вам нужен еще один механизм разрешения конфликтов еще глубже... и т. Д.
Эта не упомянутая проблема, а также тот факт, что вам нужно выполнить двухэтапную фиксацию, чтобы привести в порядок метаданные, заставляют меня думать, что CRDT все еще находятся в стадии разработки.
Комментарий к ответу @btilly:
Вопрос в теме связан с различными моделями согласованности и, следовательно, шаблонами проектирования:
- CRDT относится к семейству алгоритмов Eventual Consistency,
- Семейство алгоритмов PAXOS относится к Strong Consistency / Linerizability (синхронизация клиента с сервером),
- RAFT эквивалентен PAXOS по алгоритмическому и последовательному принципу, но его легче реализовать.
CRDT и Paxos - это очень разные вещи, и их использование должно определяться исходя из требований вашей архитектуры. Я считаю, что лучший способ справиться с этим - это рассмотреть случаи использования, когда эти алгоритмы были успешно применены.
Используйте шаблоны:
CRDT может использоваться для синхронизации данных между клиентами (т.е. мобильными устройствами) и серверами, совместного редактирования в реальном времени, синхронизации значений в реализациях dist-db и во всех других случаях, когда возможна согласованность.
PAXOS в основном используется в проприетарных системах, поддерживающих системную инфраструктуру (например, Chubby), или для реализации синхронизации в системах распределенных баз данных, таких как BigTable, Datastore, Spinnaker, Spanner и т. Д.
RAFT более популярен в инфраструктурных проектах OSS, таких как ETCD, Consul,...
(не помню, на чем основаны CockroachDB и TiDB)
Существует также BFT, но его используют меньше.
ps PAXOS!= ZooKeeper. ZooKeeper использует другой алгоритм, называемый ZAB, и является не реплицированным конечным автоматом, а реплицированной машиной моментальных снимков с одной записывающей моделью и моделью расслабленного чтения. Chubby от Google основан на Paxos, но его проприетарный.
pss Интересно, как PAXOS развивается все эти годы. За последние 20 лет было изобретено множество вариантов для обработки различных оптимизаций краевых случаев, размеров кворума и реконфигурации кластера.
У нас есть несколько метрик:
- пропускная способность (CRDT и Paxos одинаковы, потому что все запросы в конце реплицируются на все реплики, независимо от того, CRDT или Paxos);
- задержка (CRDT лучше, чем Paxos, потому что он пишет в меньшее количество реплик);
- надежность (CRDT слабее, чем Paxos, потому что пишет в меньшее количество реплик (меньше большинства), что может привести к потере состояния);
- согласованность (CRDT слабее, чем Paxos, потому что он допускает одновременную запись без точки синхронизации (в основном без перекрывающихся реплик), в то время как запись Paxos всегда требует перекрывающейся реплики для выполнения сериализации).
Мое предложение состоит в том, что мы должны использовать Paxos, когда реплики находятся недалеко друг от друга (например, в центре обработки данных), и использовать CRDT, когда сетевое разделение является нормальным (например, отключенное мобильное устройство).
Когда это уместно. Тем не менее, PaxOS не так уж и плох, поскольку его пропускная способность, как правило, такая же, как и у CRDT, не говоря уже о том, что надежность намного выше (CRDT может привести к потере состояния), и его задержка не так уж и плоха, так как требует только большинства из реплик отвечает вместо всех.