Является ли журнал репликации, необходимый для достижения линеаризуемости в распределенном хранилище

Question

Алгоритм Плота, используемый алгоритмом etc и ZAB Zookeeper, использует журнал репликации для обновления конечного автомата.

Мне было интересно, можно ли создать подобную систему, просто используя выборы лидеров и версии. И почему эта система решила использовать журнал репликации.

я свой пример, если мы имеем следующую установку

• машин A (Лидер), содержат версию 1
• машина B (Ведомый), содержат версии 1
• машину C (последователь), содержу версия 1

И запись будет идти, как это:

1. машина Приемный запрос на запись и хранить в ожидании записи V2
2. машина отправляющего подготовить запрос на компьютере B и машина C
3. Аудитория (машина B и машина C) отправить Подтверждение лидера (машина А)
4. После лидера (машина A) получает подтверждение от кворума машины, он знает, что V2 теперь совершена и отправляет запрос клиента клиенту
5. Лидер (машина a) отправляет запрос на завершение запроса (машина A и машина B), чтобы сообщить им, что V2 совершается и V1 можно отбросить.

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

Answer 1

Алгоритм плота в ETCD и алгоритме ZAB в Zookeeper оба с помощью журнала репликации для обновления состояния машины. Мне было интересно, можно ли создать подобную систему, просто используя выборы лидеров и версии.

Да, можно достичь консенсуса/линеаризуемости без репликации журнала. Первоначально проблема консенсуса была решена в статье Paxos Made Simple Лесли Лампорт (1998). Он описал два алгоритма: Single Decree Paxos, чтобы построить распределенный линеаризуемый регистр однократной записи и Multi-Paxos, чтобы сделать распределенный конечный автомат поверх добавления только журнала (упорядоченного массива регистров с однократной записью).

Append only logs - гораздо более мощная абстракция, чем регистры с однократной записью, поэтому неудивительно, что люди выбирают журналы через регистры. Кроме того, до публикации Vertical Paxos (2009) репликация журнала была единственным консенсусным протоколом, способным к изменению членства в кластере; что важно для множества задач: если вы не можете заменить неудавшиеся узлы, то в конечном итоге ваш кластер станет недоступным.

Но Vertical Paxos хорошая бумага, это было намного легче для меня, чтобы понять Raft's идею членства кластера через совместный консенсус, поэтому я написал a post о том, как адаптировать путь плота для единого декрета Паксоса.

С течением времени «один раз» характер Единого Декрета Паксос также разрешил превращать регистры с однократной регистрацией в распределенные линеаризуемые переменные, достаточно мощную абстракцию, подходящую для многих вариантов использования. В дикой природе я видел этот подход в Treode database. Если вам интересно, я написал об этом улучшенном SDP в сообщении How Paxos Works.

Так что теперь, когда у нас есть альтернатива регистрирует это имеет смысл рассматривать его, поскольку журнал репликация на основе является сложной и имеет внутренние ограничения:

• бревен, вы должны заботиться о журнале уплотнении и сборке мусора
• размера журнала ограничен размером одного узла
• протоколы для разделения журнала и миграции на новый кластер не очень хорошо известны

И почему эта система решила использовать журнал репликации.

Основанный на журналах подход является более старым, чем альтернатива, поэтому у него больше времени для завоевания популярности.

О вашем примере

Это трудно оценить, потому что вы не описали, как лидер выборов происходит и конфликты между лидерами будут решены, что стратегия для обработки сбоев и как изменить членство кластера.

Я считаю, что если вы их тщательно опишите, вы получите a variant of Paxos.

Answer 2

Ваш пример имеет смысл. Однако рассмотрели ли вы все возможные сценарии отказа? На шаге 2 машина B может получать сообщения минут до или после машины C (или наоборот) из-за сетевых разделов или ошибочных маршрутизаторов. На шаге 3 подтверждения могут быть потеряны, отложены или повторно переданы много раз. Лидер также может потерпеть неудачу и вернуться один раз, дважды или потенциально несколько раз в рамках одного консенсуса. И на шаге 5 сообщения могут быть потеряны, дублированы или Machine A & C может получить уведомление, в то время как B пропустил его ....

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

Реплицированные журналы просты, понятны, предсказуемы и четко уходят в область установленных консенсусных протоколов (paxos, paxos-варианты, & плота). Вот почему они популярны. Это не потому, что они лучше подходят для любого конкретного приложения, но они понятны и надежны.

Для связанных ссылок, вы можете быть заинтересованы в Understanding Paxos и Consensus in the Cloud: Paxos Systems Demystified