Алгоритм распределенной согласованности, вы точно не знаете об этом

Централизованное и распределенное

централизованный

Это развертывание всех сервисов на центральном хосте (узле), и все функции централизованно обрабатываются этим хостом.

Функции

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

распределенный

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

Функции

1. распределение: Несколько компьютеров могут быть случайным образом распределены в пространстве, по компьютерным комнатам и по городам.
2. эквивалентность: В распределенных системах нет различий между главным и подчиненным, все они являются одноранговыми узлами или службами.
   • копировать: относится к паре распределенных системРезервирование данных или услуг, чтобы обеспечить высокую доступность.
   • копия данных: относится к сохранению части данных на разных узлах.Когда данные, хранящиеся на узле, потеряны, данные могут быть прочитаны из копии, что является наиболее эффективным методом для проблемы потери данных в распределенных системах.
   • служебная копия: относится к нескольким узлам, предоставляющим одну и ту же услугу, и каждый узел имеет возможность получать внешние запросы и соответствующим образом их обрабатывать.
3. **Параллелизм: **Несколько узлов в распределенной системе могут одновременно управлять некоторыми общими ресурсами, такими как базы данных или распределенное хранилище.
4. **Отсутствие глобальных часов** Типичная распределенная система состоит из ряда процессов, случайно распределенных в пространстве, и процессы взаимодействуют друг с другом посредством сообщений. Поэтому невозможно судить, какое из двух событий произошло первым.Можно использовать логические часы.
5. **Ошибки случаются всегда: **Если не позволяют требования, при проектировании системы нельзя упускать из виду исключения. Например, время простоя, сетевой раздел, тайм-аут сети и т. д.

Каждый раз распределенная система запрашивает и отвечает на три состояния:Успех, неудача, тайм-аут.

Ситуация тайм-аута:

1. Оно не было успешно отправлено получателю, и информация была потеряна в процессе отправки.
2. Оно было успешно отправлено получателю и успешно обработано, но при возврате отправителю информация была потеряна.

Поэтому он должен быть идемпотентным.

Распределенная транзакция

Распределенные транзакционные средстваучастники бизнеса,сервер, поддерживающий транзакции,сервер ресурсова такжеменеджер транзакцийОни расположены на разных узлах распределенной системы. **Обычно распределенная транзакция включает операции с несколькими источниками данных или бизнес-системами. Распределенные транзакции также могут быть определены как вложенные транзакции, которые также имеют характеристики транзакций ACID.

теория CAP

• Consistency(последовательность): данные обновляются последовательно, и все изменения данных синхронизируются (строгая согласованность).

• Availability(Доступность): хорошая отзывчивость

• Partition tolerance(Допуск перегородки) : надежность

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

сетевой раздел: Это означает, что в распределенной системе разные узлы распределены по разным подсетям (компьютерный зал или удаленная сеть и т. д.), и по каким-то особым причинам сеть между этими подсетями разъединена, но внутренняя сеть работает нормально, в результате чего вся сетевая среда делится на несколько изолированных областей.

теорема:Любая распределенная система может одновременно удовлетворять только двум требованиям и не может заботиться обо всех трех.

Необходимо выбрать в соответствии с фактическим бизнесом.

• Система CA (отказаться от P): Относится к размещению всех данных (или только данных, связанных с транзакциями) на распределенном узле, при этом сетевых разделов не будет. Таким образом, сильная согласованность и доступность удовлетворены.
• Система CP (заброшенная A): если данные должны быть строго согласованы на каждом сервере, но сетевой раздел приведет к неограниченному увеличению времени синхронизации, то доступность не гарантируется. Традиционные базы данных, которые настаивают на транзакционном ACID (атомарность, согласованность, изоляция и надежность), и приложения, которые очень чувствительны к согласованности результатов, часто делают этот выбор.
• Система AP (откажитесь от C): Упомянутый здесь отказ от согласованности означает не полный отказ от согласованности данных, а отказ от строгой согласованности данных и сохранение возможной согласованности данных. **Если требуется и высокая доступность системы, и отказоустойчивость разделов, то от консистентности нужно отказаться. Поскольку после разделения сети между узлами не будет связи, так почему для обеспечения высокой доступности каждый узел может предоставлять услуги только с локальными данными, что приведет к несогласованности данных. Некоторые базы данных, которые придерживаются принципа BASE (такие как Cassandra, CouchDB и т. д.), как правило, ослабляют требования к согласованности (достаточно для достижения согласованности в конечном итоге), чтобы получить базовую доступность за один раз.

БАЗОВАЯ теория

• В основном доступно: Относится к распределенной системе, которая допускает частичную потерю доступности в случае непредсказуемых сбоев, но не недоступность системы.
  • потеря времени отклика: Если обычный онлайн-поиск возвращается в течение 0,5 секунд, но из-за неисправности (сбой питания в машинном зале или сбой сети) время отклика результата запроса увеличивается до 1-2 секунд.
  • функциональная потеря: если всплеск трафика или запрос требует взаимодействия между несколькими службами, а некоторые службы в это время выходят из строя, для защиты стабильности системы требуется понижение версии службы.
• Мягкое состояние: существует задержка, позволяющая системе синхронизировать данные между репликами данных на разных узлах.
• В конечном итоге последовательный: Достаточно, чтобы конечные данные были непротиворечивыми, а не высокой согласованностью время от времени.

Идея BASE в основном делает упор на базовую доступность.Если вам нужна высокая доступность, то есть чистая высокая производительность, то вы должны пожертвовать согласованностью или отказоустойчивостью.

Протокол соответствия

Протокол согласованности: алгоритм, предназначенный для поддержания атомарности и согласованности в процессе обработки транзакций всех узлов на основе архитектуры распределенной системы. обычно имеютвторой этаппредставить соглашение,три этапапредставить соглашение,Paxos,ZAB-протокол Zookeeper, Raft, PbftЖдать.

2PC, 3PC представили две концепции.

**Координатор: **Отвечает за единое планирование логики выполнения распределенных узлов.

участник: Распределенный узел должен быть запланирован

2PC: двухэтапная фиксация

второй этапВ основном берут:Сначала попробуйте, потом отправьте.

2PC преимущества и недостатки

• Двухступенчатые преимущества: принцип прост и реализация удобна; для решения атомарности распределенных транзакций либо все выполнения успешны, либо все выполнения терпят неудачу
• Этап 2 Недостатки:
  1. синхронная блокировка: В процессе отправки каждый участник ожидает ответа других участников и не сможет выполнять другие операции.
  2. проблема с одной точкой: Координатор только один, координатор зависает, и весь двухэтапный процесс подачи не может быть выполнен, а если серьезно, то на втором этапе, если есть проблема с координатором, участник всегда будет в заблокированной транзакции состояние и не может продолжать завершать транзакцию.
  3. несогласованность данных: на этапе 2 после того, как координатор отправляет запрос на фиксацию, происходит сбой сети, в результате чего только некоторые участники получают запрос на фиксацию и выполняют операцию фиксации, что приводит к несогласованности данных.
  4. слишком консервативен: На этапе 1, если участник терпит неудачу, координатор не может получить ответ участника на запрос и может только прервать транзакцию через свой собственный механизм тайм-аута. Такая стратегия кажется слишком консервативной.

3PC: Трехфазный протокол фиксации

Поскольку у 2PC много проблем, на основе 2PC улучшение3PC: canCommit, preCommit, doCommit три этапа.

Очки улучшения:

1. 3PC делит первый этап 2PC на два этапа, сначала инициируя запрос транзакции, а затем выполняя транзакцию.
2. При этом в координаторе и участниках вводится механизм тайм-аута.

Преимущества и недостатки 3PC

• Трехступенчатые преимущества:

  • Уменьшен диапазон блокировки синхронизации для второй фазы.(На втором этапе, пока участник получает запрос preCommit, транзакция будет выполняться. После этого, независимо от того, может ли быть получен запрос doCommit от координатора, транзакция будет зафиксирована, и проблемы с блокировкой не будет. )
  • Решайте одноточечные задачи: Есть две ситуации при переходе на этап 3: 1: Проблема с координатором; 2: Ошибка сети между координатором и участниками;
    • Все это приводит к тому, что участник не может получить запрос doCommit, но участник фиксирует транзакцию по истечении тайм-аута.

• Недостатки трех стадий:

  • несогласованность данных: участник получает запрос preCommit.Если в это время существует сетевой раздел, нормальная сетевая связь между координатором и участником не может быть выполнена, и участник все равно зафиксирует транзакцию после тайм-аута, что приведет к несогласованности данных.

Поэтому 2PC и 3PC имеют свои преимущества и недостатки, которые можно выбирать в соответствии с реальными бизнес-сценариями. Так как 2PC и 3PC приведут к несогласованности данных. Давайте взглянем на алгоритмы консенсуса, обычно используемые в распределенной сфере.

Алгоритм Паксос

Алгоритм PaxosЛесли Лэмпортпредложено в 1990 г.на основе передачи сообщенийиСогласованный алгоритм с высокой отказоустойчивостью, который в настоящее время признан одним из самых эффективных алгоритмов для решения задач распределенной непротиворечивости.Проблема, решаемая алгоритмом Paxos, заключается в том, как распределенная система соглашается на некоторое значение (разрешение).

И Paxos, и приведенный ниже RAFT предполагают, что общей византийской проблемы нет, и рассматривают только такие проблемы, как время простоя узла, сетевой раздел и ненадежные сообщения. Он относится к алгоритму CFT (Crash Fault Tolerance).

В системе есть три роли: предлагающие, принимающие и обучающиеся. У узла может быть несколько ролей.

1. proposersПредложите предложение, информация о предложении включает номер предложения и предлагаемую стоимость;
2. acceptorПосле получения предложения вы можете принять предложение.Если предложение принято большинством акцептов, то говорят, что предложение одобрено (выбрано);
3. learnersТолько одобренные предложения могут быть «выучены».

Большинство: относится к n/2+1. n - общее количество узлов.

Алгоритм Paxos делится надва этапа. детали следующим образом:

• Первый этап:

  • Предлагающий выбрать одинПредложение номер N, затем кбольше половиныАкцептор посылает число NПодготовить запрос.

  • Если акцептор получает запрос на подготовку с номером N и Nбольше, чемАкцептор имеетОтветилвсеПодготовить запросномер, то уже его поставитПринятое предложение с наибольшим номером (если есть)Обратная связь Предлагающему как ответ, а Акцептанту обещаетбольше не приниматьлюбойПредложения с номерами меньше N.

    Например: номера предложений, соответствующие всем запросам на подготовку, на которые ответил акцептор, равны 1, 2 и 1 соответственно. . . . 5 и 7, после того как акцептор получит запрос на подготовку под номером 8, он вернет предложение под номером 7 предлагающему в качестве ответа.

• второй этап

  • Если предлагающий получаетбольше половиныЗапрос Prepare с номером N, отправленный ему Акцептантомотклик, то он отправляет сообщение для **[N,V]предложениеизПринять запросдаватьбольше половиныАкцептор. Примечание. V – это значение** предложения с наибольшим номером в ответе, полученном на Этапе 1. Если ответНе содержит предложений, то V определяется ПредлагающимРешайте сами (произвольное значение).
  • Если Акцептант получает запрос на принятие для предложения номер N, пока Акцептантнетномер парыбольше, чем NизПодготовить сделанный запросотклик, будетпринять предложение.

Примечание: предлагающие могут отклонить предложения в любое время и предложить новые предложения; акцепторы также могут ответить в любое время и принять предложения с более высокими номерами.

Мысль: если два предлагающих все еще находятся на первом этапе, предлагают ли они друг другу предложение с более высоким номером? Что случится?

В это время будет состояние «живая блокировка», и он попадет в бесконечный цикл (уничтожающий активность алгоритма).

Как это предотвратить?

Мастер-предлагатель может быть избран, и только мастер-предлагатель может вносить предложения.

Что касается выбора, то он не относится к категории Paxos, вы можете обратиться к RAFT, чтобы использовать выборы, и кто быстрее будет избран, вы также можете обратиться к PBFT, чтобы стать лидером по очереди.

Алгоритм ОПЦ

Алгоритм RAFT разделен на два этапа: выбор лидера и репликация журнала. Также есть три роли, а именно:

1. Лидер: Отвечает за отправку данных для согласования.Если данные, отправленные клиентом, отправляются не Лидеру, а другим ролям, другие роли пересылают их Лидеру.
2. Последователь: Роль участия в консенсусе
3. Кандидат: Если ведомый не получает ответ сердцебиения ведущего в течение более 150–300 мс, будут выполнены выборы ведущего.

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

• Этап выборов лидера:

  • Начальное состояние всех узлов — состояние ведомого, в это время лидера нет, а пульсация с лидером обязательно истечет по тайм-ауту (обычно 150-300 мс, случайным образом, так что кто первый отправит выборы, кто избран лидером ), в это время Кандидат отправит выборы лидера другим узлам (пожалуйста, проголосуйте за меня, лидер умер); другие узлы ответят на запрос о выборах, и когда кандидат получит ответ от большинства (n/ 2+1) узлов, он станет лидером. Затем поддерживайте связь пульса с Кандидатом. В Raft есть концепция срока, только на этапе выборов лидера срок+1 означает, что новый лидер сгенерирован, нода, которая умерла, или умерший лидер обнаружит, что его срок меньше, чем последний после перезапуска , Он переключается на репликацию журнала для синхронизации ранее потерянных сообщений.
  • Если несколько кандидатов отправляют выборы одновременно, и ни один из них не набирает большинства голосов, выборы будут продолжаться до тех пор, пока не будет избран лидер.

• репликация журнала (это фиксация 2PC)

  • Когда лидер получает значение, отправленное клиентом или другими узлами, и ему требуется консенсус, он передает его другим узлам вместе с тактом для записи.
  • После того, как другие узлы запишут, ответ успешно отправляется ведущему.Когда лидер успешно получает большинство ответов ведомых, он выдает команду фиксации.
  • После того, как другие узлы получили фиксацию, они фиксируют транзакцию, и ответ считается успешным в качестве лидера.Лидер успешно получает большинство коммитов, и Raft завершен.

  Если лидер не зависает или происходит раздел сети, лидер всегда будет инициировать транзакции.

Я просто описываю нормальный поток алгоритма здесь, который настоятельно рекомендуетсяАнимированный ПЛОТ(не пойму, если проиграю, но не забудь вернуться и поставить лайк, хахаха)

Суммировать

В этой статье описываются общие идеи распределенных транзакций от централизованной до распределенной теории процессов CAP, BASE и 2PC, 3PC, а затем подробно описываются процессы алгоритмов Paxos и Raft. Алгоритмы Paxos и Raft относятся к категории алгоритмов CFT и могут допускать до n/2 (округленных в меньшую сторону) узлов с алгоритмами строгой согласованности, такими как время простоя и разделение сети. Paxos — относительно малоизвестный алгоритм, а его инженерная реализация относительно сложна, но его идеи очень полезны для справки. Если вам интересно, вы можете посмотреть процесс вывода Paxos. Я лично считаю, что это очень интересно. Возможность понять каждый шаг также очень полезна для понимания других алгоритмов. Вы также можете посмотреть алгоритм ZAB Zookeerper и У меня будет возможность написать специальную статью позже. . Но на самом деле эти алгоритмы нельзя использовать для консенсуса блокчейна, ведь то, что говорит лидер, будет выполняться другими узлами, а между узлами нет процесса консенсуса. Итак, какой алгоритм можно использовать для достижения консенсуса в блокчейне?

Справочная литература:

«Принцип и практика распределенной согласованности от Paxos до Zookeeper++++»

Ссылка на ссылку:

Алгоритм PAXOS

Анимационная версия РАФТ

В этой статье используетсяmdniceнабор текста