XVII Международная студенческая научная конференция Студенческий научный форум - 2025

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

Исторически исследования в области консенсуса начали активно развиваться благодаря работам Лесли Лэмпорта и его алгоритму Paxos [1], который заложил основу для современных решений. Впоследствии появились другие подходы, такие как Raft и алгоритмы на основе византийской устойчивости, что расширило диапазон применения консенсуса. Таким образом, распределительные системы стали основой для многих современных технологий, включая облачные сервисы, базы данных и блокчейн-платформы.

Проблема консенсуса. В распределительных системах важнейшей задачей является достижение согласия между процессами, даже если некоторые из них вышли из строя. Консенсус становится особенно сложным в системах с возможными отказами (crash failures), где процессы могут внезапно перестать работать. В этом случае корректные процессы, продолжающие функционировать, должны договориться об общем значении (например, 0 или 1), несмотря на потерю связи с отказавшими узлами.

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

1. Единогласие (Agreement): Все корректные процессы должны принять одно и то же значение.

2. Принятие предложенного (Validity): Если все процессы начинают с одного и того же значения, то они должны прийти к решению, соответствующему этому значению.

3. Завершение (Termination): Все корректные процессы должны в конечном итоге принять решение (определиться с одним значением, 0 или 1).

Современные вызовы консенсуса в распределительных системах. В распределительных системах компонент считается неисправным, если он испытывает сбой, который нарушает его нормальное функционирование. Обычно выделяют 4 типа неисправностей:

1. Сбой с отказом (Crash Failures) происходит, когда компонент полностью прекращает работу и перестаёт отвечать на запросы. Неисправный узел больше не отправляет и не принимает сообщения.Эти сбои проще обнаружить и обработать, так как узел становится полностью неактивным. Типичным примером сбоя с отказом может послужить операционная система, которая полностью перестаёт работать, и единственным решением становится её перезагрузка. Многие пользователи персональных компьютеров сталкиваются с подобной настолько часто, что начинают воспринимать их как нормальное явление [3, 4].

2. Сбой пропуска (OmissionFailures) происходит, когда сервер не отвечает на запрос. Это может быть связано с разными причинами [4]:

2. 1. Сбой при приёме (Receive-omission failure) возникает, если сервер не получил запрос. Например, cоединение между клиентом и сервером установлено корректно, но поток, отвечающий за обработку входящих запросов, отсутствует. Этот сбой, как правило, не влияет на текущее состояние сервера, так как он не знает о поступлении сообщения.

   2. Сбой при отправке (Send-omission failure) происходит, если сервер обработал запрос, но не смог отправить ответ. Например, буфер отправки переполнен, и сервер не был готов к такому сценарию. В отличие от сбоя при приёме, состояние сервера может отражать выполнение запроса. Поэтому, если отправка ответа не удалась, сервер должен быть готов к повторному запросу от клиента.

3. Сбой ответа (Responsefailures) является серьезным видом сбоя, при котором сервер попросту выдает неправильный ответ.Возможны два вида таких сбоев:

1. Сбой значения (Value failure) возникает, когда сервер предоставляет неправильный ответ на запрос. Например, если поисковая система систематически возвращает веб-страницы, не имеющие отношения к поисковым запросам, это считается сбоем.

2. Сбой перехода состояния (State-transition failure) происходит, если сервер реагирует на запрос неожиданным образом. Например, если сервер получает сообщение, которое он не может распознать, и при этом не предусмотрены меры для обработки таких сообщений. В частности, неисправный сервер может ошибочно выполнить действия по умолчанию, которые не должны были быть инициированы [4].

4. Византийские сбои (Byzantine Failures).
Это более сложный и трудный для обработки тип неисправностей, когда компонент ведёт себя произвольно, без какого-либо определенного состояния. Он может принимать сообщения от других компонентов или же оставаться в режиме ожидания. Со стороны такие сбои выглядят безопасными и долгое время могут не вызывать никакого подозрения. Византийский сбой часто является следствием неисправности системного процесса или вмешательства злоумышленника. Если в сети присутствует несколько компонентов с византийским поведением, они могут вступить в сговор, чтобы нанести ещё больший ущерб сети. Византийский сбой считается самым серьёзным видом отказов компонентов, в то время как сбой с отказом (crash failure) часто воспринимается как менее вредоносный случай византийского сбоя [3, 4].

Проблема византийских генералов (Byzantine Generals Problem). Это известная задача в области компьютерных наук и распределительных систем, которая описывает, как децентрализованные системы могут прийти к единому решению в условиях ненадёжности и потенциально вредоносных участников. Она была впервые сформулирована Лесли Лампортом, Робертом Шостаком и Маршаллом Писом в 1982 году и находит применение в таких областях, как блокчейн, распределённые базы данных и безопасность информационных систем.

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

1. Надёжность коммуникации: некоторые гонцы могут быть задержаны, перехвачены или их сообщения искажены.

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

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

Решение задачи. Основное требование для решения задачи византийских генералов — наличие консенсусного алгоритма, который позволяет системе продолжать функционировать корректно при наличии злонамеренных участников [5].

Ключевые аспекты решения:

1. Кворум: честные участники должны составлять более двух третей всех участников. Это минимальное условие для достижения консенсуса.

2. Протокол передачи сообщений: генералы обмениваются сообщениями, используя определённый протокол, который обеспечивает верификацию данных (например, цифровые подписи)

Теорема FLP. Теорема FLP (Fischer, Lynch, Paterson) утверждает, что в асинхронной распределительной системе невозможно гарантировать достижение консенсуса, если хотя бы один из узлов может выйти из строя. Это фундаментальный результат в области распределенных вычислений, который демонстрирует ограничения асинхронных систем.

Основные идеи теоремы:

1. Асинхронность: сообщения могут задерживаться неопределённое время, и алгоритмы не могут полагаться на синхронное поведение сети.

2. Толерантность к сбоям: если хотя бы один узел выходит из строя (например, перестает отвечать или ведет себя некорректно), это делает невозможным гарантированное согласование всех узлов на едином решении.

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

Следствия теоремы FLP подчеркивают, что разработка распределенных систем требует компромиссов. Например, современные протоколы (такие как Paxos и Raft) решают проблему консенсуса в практических условиях, вводя некоторые предположения о синхронности системы или допускают вероятность временной недоступности решений.

Теорема CAP. Теорема CAP, сформулированная Эриком Брюером, описывает ограничения распределённых систем. Она утверждает, что любая система не может одновременно гарантировать три свойства:

1. Согласованность (C): все узлы системы видят одно и то же состояние данных в одно и то же время.

2. Доступность (A): каждый запрос, отправленный на исправный узел системы, получает ответ, даже если часть системы недоступна.

3. Устойчивость к разделению (P): система продолжает работать корректно, несмотря на разделение сети, которое может разорвать связь между её частями.

Основная идея теоремы заключается в том, что в условиях разделения (Р) система должна выбирать между согласованностью (С) и доступностью (А). Таким образом, невозможно одновременно удовлетворить все три свойства [6].

Алгоритм PAXOS. Paxos, предложенный Лэмпортом, считается одним из первых и наиболее известных алгоритмов консенсуса. Этот протокол консенсуса позволяет достичь согласования на одном значении даже при многочисленных сбоях. Его теоретическая основа обеспечивает два ключевых свойства:

1. Безопасность (safety): конфликтующих решений не будет

2. Гарантия прогресса (liveness): система через определенный промежуток времени сможет прийти к окончательному решению.

Перед тем как начать работу алгоритма, нужно определиться с исполнителями ролей (агентами). Для успешной и эффективной работы PAXOS требует три типа основных участников [1]:

1. Предлагающие (Proposers): предлагают значения для согласования.

2. Акцепторы (Acceptors): голосуют за предложенные значения и формируют "кворум" для принятия решения.

3. Наблюдатели (Learners): узнают о принятом значении после достижения консенсуса.

Теперь, когда мы определились с требованиями, рассмотрим основные фазы работы данного протокола:

1. Фаза подготовки (Prepare Phase): предлагающий выбирает уникальный номер предложения и отправляет его акцепторам. Акцепторы отвечают, сообщая номер самого "важного" предложения, которое они уже приняли.

4. Фаза принятия (Accept Phase): предлагающий отправляет запрос на принятие конкретного значения с соответствующим номером.Акцепторы соглашаются, если номер предложения больше или равен любому ранее принятому.

5. Фаза решения (Decide Phase):когда большинство акцепторов согласны, решение сообщается всем наблюдателям.

Основная критика Paxos обычно связана с его сложностью и непонятностью, что обусловлено использованием в основе протокола варианта с единственным решением (single-decree). Этот вариант является плотным и тонким по своей структуре: он разделён на две стадии, которые сложно объяснить интуитивно и которые трудно понять изолированно друг от друга. Из-за этого разработка чётких представлений о том, как работает протокол single-decree, становится затруднительной. Дополнительно правила объединения решений в Multi-Paxos вносят ещё больше сложности и нюансов [7].

Альтернативный протокол консенсуса: RAFT. Другим распространённым критическим замечанием в адрес Paxos является то, что его архитектура плохо подходит для построения практических систем. Это связано с подходом, основанным на разбиении задачи на отдельные решения. Например, независимый выбор набора записей журнала и их последующее объединение в последовательный журнал только усложняет процесс. Более простым и эффективным подходом является проектирование системы вокруг журнала, где новые записи добавляются последовательно в строгом порядке.

В качестве альтернативного подхода был предложен протокол консенсуса Raft, специально ориентированный на работу с последовательными журналами. Он обеспечивает консенсус между узлами в распределительной системе, гарантируя, что все узлы согласуются на одинаковое состояние. В системе узлы распределены на роли: лидеры, последователи и кандидаты. Лидер отвечает за обработку клиентских запросов и репликацию данных на другие узлы, последователи получают команды от лидера и хранят их в своих логах, а кандидаты претендуют на роль лидера во время выборов. Если узел не получает сигналов от лидера в течение определённого времени, он становится кандидатом, инициирует выборы и отправляет запросы на голосование другим узлам. Узел с большинством голосов становится лидером, а случайный интервал времени ожидания перед выборами помогает избежать конфликтов.

Репликация лога осуществляется через механизм AppendEntries RPC, где лидер записывает команды в свой лог и отправляет их другим узлам. Команды подтверждаются, когда они реплицированы на большинстве узлов, и лог остаётся последовательным благодаря проверке согласованности, которая позволяет лидеру корректировать логи последователей. Безопасность алгоритма достигается за счёт того, что лидер гарантирует неизменность всех предыдущих подтверждённых команд, а во время выборов проверяется актуальность логов кандидатов.

Для обновления конфигурации кластера используется промежуточная фаза «совместного консенсуса», где старые и новые конфигурации работают параллельно, обеспечивая безопасное добавление или удаление узлов. Среди преимуществ Raft выделяют его простоту и лёгкость внедрения, что делает его популярным выбором для распределённых баз данных и файловых систем, требующих высокой доступности и согласованности [8].
Выводы и заключения. Консенсус играет центральную роль в функционировании распределительных систем, предоставляя необходимые механизмы для обеспечения согласованности данных и надёжности при сбоях узлов. Исследования в этой области, начиная с работы Лесли Лэмпорта и его алгоритма Paxos, сформировали основу для многих современных решений. Однако сложность Paxos, связанная с его теоретической изощрённостью и недостаточной адаптацией к практическим реалиям, породила новые подходы, такие как Raft, который сделал акцент на простоте и удобстве реализации.

Алгоритмы консенсуса, такие как Paxos и Raft, помогают преодолевать фундаментальные ограничения, включая теорему FLP и CAP. Paxos демонстрирует теоретическую строгость и возможность достижения консенсуса даже в условиях сбоев, но сложность его структуры ограничивает его применение. Raft, напротив, предлагает более интуитивное разделение задач, упрощая реализацию и обеспечивая ясность при работе с журналами и обработке ошибок.

Проблема консенсуса, включая вызовы византийских сбоев, остаётся актуальной для таких систем, как блокчейны, распределённые базы данных и облачные сервисы. Современные алгоритмы продолжают развиваться, объединяя аспекты безопасности, доступности и эффективности. Они обеспечивают базис для построения надёжных распределённых систем, которые становятся основой цифрового мира.

Списоклитературы

1. Leslie Lamport. Paxos Made Simple. 2001

2. Wan Fokkink, Distributed Algorithms, second edition: An Intuitive Approach (Mit Press). 2018. С. 112-113

3.Yang Xiao, Ning Zhang, Jin Li, Wenjing Lou, Y. Thomas Hou. Distributed Consensus Protocols and Algorithms

4.Maarten van Steen, Andrew S. Tanenbaum. Distributed Systems Third edition Version 3.02 (2018). C. 428-429

5.Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3), С. 382–401.

6.FLP and CAP aren't the same thing. 2012 – Режим доступа: https://www.the-paper-trail.org/post/2012-03-25-flp-and-cap-arent-the-same-thing/

7.Robbert Van Renesse, Deniz Altinbuken, Paxos Made Moderately Complex. 2015

8.Diego Ongaro and John Ousterhout Stanford University. In Search of an Understandable Consensus Algorithm

Код для цитирования: Скопировать