В статье приводится классификация распределённых систем с точки зрения владения состоянием. Даётся краткий обзор существующих технологий. Исходя из проведённого анализа описывается разработанная архитектура алгоритма консенсуса для интерактивных приложений.
Ключевые слова: распределённая система, модель согласованности, интерактивное приложение, клиент-серверная архитектура, одноранговое взаимодействие, алгоритм консенсуса, REST, Raft, Mirror Networking.
Непрерывный рост популярности распределённых программных систем определяет постоянный спрос на решения как в области системного проектирования, так и в области методов взаимодействия компонентов этих систем. В данной работе будут представлены теоретическое обоснование и результаты проектирования алгоритма консенсуса для интерактивных приложений, полученные в рамках магистерской диссертации автора.
Значительная часть прикладных программистов, сталкиваясь с задачей разработки программного обеспечения, обрабатывающего запросы множества пользователей, интуитивно относит систему к одному из двух неформально определяемых классов.
К первому классу можно отнести системы, реализующие CRUD-семантику конкретной предметной области. Запросы к таким системам, с точки зрения прикладного программиста, обрабатываются изолированно друг от друга. Репрезентативными примерами программного обеспечения этого класса являются веб-клиенты интернет-магазинов или сервисов бронирования.
Ко второму классу относятся системы, предоставляющие возможность совместной работы с каким-либо объектом, где изменения, вносимые в результате действий других пользователей или внешних факторов (например, течения времени), распространяются согласно push-модели [1]. В таких системах запросы агрегируются и упорядочиваются с целью уведомления всех заинтересованных пользователей о результирующем состоянии объекта. Примером такого программного обеспечения может служить многопользовательское сессионное игровое приложение.
Данная неформальная классификация может оказаться полезной при выборе архитектуры и технологий для реализации программного продукта. Более того, она достаточно интуитивна, чтобы проводить границы между модулями одного приложения, выбирая подходящий стиль внутреннего взаимодействия. Однако обе категории относятся к распределённым системам, и для точного определения решаемой проблемы необходимо выявить чёткие критерии их разделения.
Для систем, которые можно отнести к первому классу, характерно взаимодействие согласно архитектурному стилю REST [2]. В соответствии с требованием отсутствия состояния, налагаемого данным стилем, состояние клиента на сервере не хранится, вместо этого вся необходимая информация для выполнения операции передаётся в рамках контекста запроса. Из данного условия непосредственно следует ограничение на проектирование состояний в системе: знание сервером о том, что на клиенте представлена часть состояния, является хранением состояния клиента на сервере, что противоречит данному условию.
Формальным критерием разделения для данных классов можно принять характер владения состоянием в распределённой системе. Пусть распределённым является состояние, к которому могут получить доступ все узлы распределённой системы.
Для первого класса систем — систем с исключительным владением состояния — распределённое состояние полностью представлено состоянием сервера (где сервер, логически представленный единственным узлом, может быть реализован в виде распределённой системы). Такой подход соответствует принципу единого источника истины.
Для систем второго класса — систем с разделяемым владением состояния — распределённое состояние может быть представлено совокупностью частей данного состояния на всех узлах системы.
В качестве примера вышеописанного рассмотрим следующую ситуацию. Распределённое состояние включает в себя объект, представленный набором свойств с определёнными значениями. Пользователь, взаимодействуя через клиентское приложение, изменяет значение одного из свойств данного объекта.
Для обоих классов систем взаимодействие на первый взгляд может выглядеть одинаково: клиент отправляет запрос вида (set, obj_id, prop, value) и получает ответ с дельтой изменений — (set, obj_id, prop, value). Однако семантика операций в рамках этого взаимодействия будет различаться в зависимости от класса системы.
- В случае разделяемого владения, клиент, выполняющий запрос, владеет частью распределённого состояния, представленного объектом с идентификатором obj_id.
- В случае исключительного владения, запрос (set, obj_id, prop, value) интерпретируется как запрос к серверу на изменение распределённого состояния, в то время как для разделяемого владения данный запрос, напротив, является уведомлением о случившемся изменении распределённого состояния клиентом.
- В случае исключительного владения ответ от сервера (set, obj_id, prop, value) является подтверждением выполнения изменения распределённого состояния, в то время как для разделяемого владения ответ является уведомлением, распространённым от сервера для всех заинтересованных (владеющих данной частью распределённого состояния) клиентов об изменении и не обязателен для клиента-отправителя.
- В случае исключительного владения ответ от сервера (set, obj_id, prop, value) сообщает о изменении свойства prop объекта с идентификатором obj_id на основании присутствия их в контексте запроса (set, obj_id, prop, value). При этом сервер не имеет информации о состоянии клиента. Если клиент A в момент до запроса содержит данные о всём состоянии объекта obj, то запрос от клиента B (set, obj_id, another_prop, some_value), выполненный непосредственно после получения obj клиентом A и непосредственно перед запросом клиента A на изменение объекта (set, obj_id, prop, value) приведёт к объекту obj · (set, obj_id, another_prop, some_value) · (set, obj_id, prop, value) как части распределённого состояния и к obj·(set, obj_id, prop, value) как несогласованной информации о состоянии объекта на клиенте A. Для случая разделяемого владения ситуация с конкурентным доступом к распределённому состоянию будет описана далее.
Несмотря на описываемую равнозначность данных классов, при проектировании систем исключительное владение практически всегда является «выбором по умолчанию», а технология для её реализации, взаимодействие вида запрос-ответ, согласно архитектурному стилю REST по протоколу HTTP, хорошо знакома большинству разработчиков.
С одной стороны, это связано с тем, что запрос от клиента к серверу в исключительном владении является запросом на изменение, и может быть отклонён сервером вследствие ошибок валидации или авторизации, что соответствует потребностям большинства систем. С другой стороны, тем, что реализация разделяемого владения связана с решением фундаментальной проблемы синхронизации.
Рассмотрим пункт 4 в вышеизложенном примере с изменением значения свойства объекта. В отличие от исключительного владения, где несогласованная информация о состоянии объекта на клиенте A может являться допустимым поведением системы, для разделяемого владения необходимо, чтобы клиент A увидел изменение, произведённое клиентом B перед внесением своего собственного изменения, в противном случае несогласованным окажется само распределённое состояние.
Распределённой системой является система, представленная как совокупности независимых процессов, взаимодействующих через передачу сообщений [3]. Ввиду асинхронности данного взаимодействия необходимо наличие механизма для гарантирования согласованности распределённого состояния. Данный механизм представляет собой программное обеспечение слоя доступа к распределённой системе (middleware), целью которой является сокрытие сложности работы с множеством независимых процессов путём предоставления гарантий о модели согласованности [4].
Поведение, описанное при рассмотрении примера с изменением значения свойства объекта для разделяемого владения, соответствует модели строгой согласованности, однако, при разработке данного класса ПО делается попытка достигнуть наилучшие характеристики производительности и времени отклика через ослабление модели согласованности и наложение других ограничений, с учётом потребностей конкретной предметной области.
Примером такой технологии для интерактивной системы с разделяемым владением можно считать Mirror Networking [5]. Данная библиотека предоставляет решение для достижения согласованности в конечном счёте распределённого состояния в клиент-серверной модели. Вышеописанный пример с изменением значения свойства объекта в рамках конкретной технологии Mirror Networking представлен следующим образом:
- Распределённое состояние представлено объектами (NetworkBehaviour) и их свойствами (SyncVars).
- Клиент, для изменения свойств объекта, обладая правом на изменение (Authority), локально меняет распределённое состояние (Prediction), а также уведомляет об изменении сервер через механизм удалённого вызова процедур (Command).
- Сервер упорядоченно выполняет запросы от клиентов, тем самым, не допуская несогласованного состояния. В рамках выполнения запроса может происходить восстановление состояния на то, в котором находился клиент в момент вызова данного запроса (Lag Compensation). После выполнения запроса сервер уведомляет клиентов, владеющих данной частью распределённого состояния о случившемся изменении.
- При несовпадении ожиданий клиента о распределённом состоянии с полученным от сервера, клиент выполняет коррекцию своего состояния, возможно с учётом задержки получения уведомления (Correction).
С точки зрения представленной классификации Mirror Networking является системой с разделяемым владением (клиенты владеют частями распределённого состояния), хотя и имеет схожие свойства с исключительным владением:
- Сервер полностью владеет распределённым состоянием.
- Клиенты посылают серверу запросы на изменение распределённого состояния.
Исключительное владение можно рассматривать как частный случай разделяемого владения, где распределённым состоянием владеет только один узел, причём, ввиду отсутствия каких-либо частей состояния, которыми узел не владеет, можно говорить, что он владеет состоянием полностью. Исходя из этого можно выделить ещё один класс систем, являющийся частным случаем разделяемого владения — системы с полным владением, где распределённым состоянием владеют все узлы системы, причём полностью: нет такой части распределённого состояния, которой бы не владел каждый из узлов системы.
Примером технологии, реализующей взаимодействие в системе с полным владением, можно считать реализацию алгоритма консенсуса Raft [6]. Raft изменяет распределённое состояние системы путём упорядочивания производимых операций и выполнения их на всех узах: узлы владеющие одним и тем же распределённым состоянием после воспроизведения одной и той же последовательности операций всё так же будут находиться в одинаковом состоянии. Упорядочивание операций производится на одном из узлов распределённой системы, назначенном путём выбора лидера.
Назначаемый в момент выполнения лидер и обладание узлами одинаковой частью распределённого состояния характеризуют Raft как систему с одноранговым взаимодействием. Более того, Raft делает систему устойчивой к отказу части узлов в fail-stop модели отказа: система будет функционировать пока большинство узлов продолжают корректно взаимодействовать друг с другом.
Однако Raft не подходит для реализации интерактивных приложений. Существенное увеличение времени отклика вызывает необходимость получить подтверждение, что большинство узлов внесли операцию в лог, до фактического выполнения операции. Данное ограничение является частью механизма для предотвращения проблемы несогласованного распределённого состояния на различных узлах из-за переизбрания лидера. Данную проблему можно рассматривать как частный случай возникновения проблемы split-brain [7], при которой кластер разделяется на несколько изолированных групп узлов, каждая из которых считает себя основной. Это может привести к тому, что операции будут выполняться независимо в каждой из групп, вызывая расхождение распределённого состояния.
В рамках магистерской диссертации был спроектирован и разработан алгоритм консенсуса, представляющий собой программное обеспечение слоя доступа к распределённой системе для интерактивных приложений.
Как и Raft, разработанный алгоритм предназначен для использования в распределённой системе с полным владением, а переход между состояниями происходит путём выполнения согласованной последовательности операций, что и определяет основные ограничения на использование алгоритма:
– Представление распределённого состояния должно позволять удовлетворить требования характеристик как передачи его моментальных снимков (при подключении узла к кластеру), так и хранения на целевом аппаратном обеспечении.
– Результат выполнения одних и тех же операций над одним и тем же распределённым состоянием должен быть одинаков на всём целевом аппаратном обеспечении.
При анализе технологии Raft было замечено, что не для всех приложений, в особенности интерактивных, гарантированное отсутствие ситуации split-brain является необходимым требованием. Так, например, желаемым поведением для совместно используемого интерактивного редактора, при возникновении частичного отказа сети, может являться разделение одного кластера пользователей на несколько независимых и возможность последующего слияния нескольких ветвей изменений распределённого состояния в одну результирующую. В особенности это поведение широко представлено в среде игровых сессионных приложений посредством дублирования текущей сессии для всех кластеров пользователей, без необходимости в механизме слияния ветвей изменения.
Разработанный алгоритм не гарантирует отсутствие ситуации split-brain, что позволило снизить количество передаваемых сообщений, устранить необходимость в механизме выбора лидера, а также сделать систему устойчивой к отказу произвольного количества узлов в fail-stop модели отказа.
Алгоритм спроектирован в виде нескольких иерархически структурированных модулей, где каждый модуль может использоваться независимо и использует нижестоящий модуль для своей реализации. Реализация абстрагируется как от технологии межпроцессорного взаимодействия, так и от представления операций путём введения абстракции пакета как контейнера для одной или нескольких операций в форме готовой для передачи согласно выбранной технологии взаимодействия. Это позволило использовать ранее разработанный модуль удалённого вызова методов [8] в качестве интерфейса к системе.
Базовый модуль реализует передачу и обработку пакетов в распределённой системе без установки логического соединения с кластером. Вместо этого кластер определяется неявно через установленные соединения между узлами. При установке соединение между узлами задаётся иерархия: один узел является родительским, другой — дочерним, причём один узел может иметь только одно соединение, относительно которого он является дочерним. Таким образом кластер может рассматриваться как ориентированный граф, где вершины являются узлами, а рёбра отражают установленные соединения. При отсутствии циклов, кластер имеет топологию дерева, в котором один из узлов является корневым (узел не имеет соединения относительно которого он является дочерним). Данное свойство топологии кластера позволяет использовать корневой узел в качестве лидера без наличия механизма его избрания.
Пакет передаётся и обрабатывается кластером согласно одному из трех режимов распространения:
- Direct — Пакет передаётся от узла отправителя к узлу получателю. Пакет будет обработан на узле получателе. Между отправителем и получателем должно быть непосредственное соединение.
- Backward — Пакет передаётся от узла отправителя ко всем его потомкам. Пакет будет обработан всеми узлами, входящими в поддерево, корнем которого представлен узел отправитель, включая его самого.
- Forward — Пакет передаётся от узла отправителя ко всем узлам входящим в кластер. Пакет будет обработан всеми узлами кластера.
Режимы распространения Direct и Backward рассчитаны на использование как для организации протокола вышестоящих модулей, так и для синхронизации состояния узла в момент добавления в кластер. Режим распространения Forward является режимом «по умолчанию» и рассчитан на использование для организации бизнес-логики распределённого приложения.
При использовании режима Forward пакет сначала передаётся от узла отправителя по узлам предкам к корневому узлу кластера, обрабатывается на корневом узле, а затем распространяется ко всем потомкам корневого узла, также обрабатываясь на узле при получении. Согласно данному способу распространения, все пакеты пройдут через корневой узел, что в совокупности с синхронностью операций по обработке и распространению пакетов, а также каналом сообщений без переупорядочивания и потерь гарантирует, что для каждого узла в кластере обработка пакетов, а следовательно, и применение операций, будет происходить в одном и том же порядке.
При передаче пакета родительскому узлу на первом этапе распространения в режиме Forward, пакет будет сохранён в очередь пакетов, ожидающих подтверждения на текущем дочернем узле. Хранение пакета позволяет:
- Родительскому узлу на втором этапе распространения в режиме Forward передавать только специальное сообщение о подтверждении, а не сам пакте целиком.
- Отправить заново пакет при смене родительского узла.
- Обработать и распространить пакет вследствии начала функционирования текущего узла в роли корневого.
- Отложить распространение пакета в случае закрытия соединения с родительским узлом до момента принятия решения о подключении к новому родительскому узлу или о начале функционирования текущего узла в роли корневого.
Одной из задач вышеописанного является гарантирование следующей семантики: если узлом было запрошено Forward распространение некоторого пакета, то в конечном счёте пакет будет обработан данным узлом.
Производным от данного модуля (модуля без установки логического соединения с кластером) является модуль с установкой логического соединения с кластером. Данный модуль хранит на каждом узле древовидную структуру данных, представляющую состояние кластера на текущий момент времени. Для идентификации каждому узлу назначается GUID. Модуль использует различные комбинации Direct, Backward и Forward распространения для того, чтобы гарантировать:
- При подключении к другому родительскому узлу текущего кластера, заново подключившийся узел не может увидеть пакет от себя же, отправленный до смены родительского узла.
- Отправитель пакета указан корректно. Например, отправителем принятого от дочернего узла пакета на первом этапе распространения Forward является либо сам дочерний узел, либо узел, являющийся предком данного дочернего узла.
- При закрытии соединения между двумя узлами (например, вследствие таймаута), состояние кластера будет обновлено на всех узлах в соответствии с отключёнными от кластера узлами.
Производным от модуля с установкой логического соединения с кластером является модуль с возможностью переподключения. Под переподключением подразумевается возможность избежать передачи моментального снимка системы при подключении узла к кластеру: если состояние узла соответствует некоторому состоянию кластера в прошлом, то для достижения согласованности распределённого состояния достаточно передать последовательность пакетов, обработка которых приведёт состояние узла к текущему состоянию кластера.
Для обеспечения возможности переподключение каждый узел хранит как информацию о ранее подключённых к кластеру узлах, так и лог, представленный списком последних обработанных пакетов. При переподключении, последовательность пакетов, которую необходимо отправить узлу определяется на основе информации о последней записи в логе переподключающегося узла.
Режимы распространения пакетов влияют на лог следующим образом:
- Direct — При обработке пакета лог остаётся неизменным.
- Forward — При обработке данный пакет заносится в лог.
- Backward — При обработке пакета лог очищается.
Режим Backward подразумевается для передачи пакетов, содержащих снимки состояний. Очистка лога при получении пакета с режимом распространение Backward позволяет избежать как долгосрочного хранения данных пакетов, так передачи пактов, обработка которых не имеет смысла ввиду последующего применения моментального снимка.
Вышеописанные модули предоставляют семантику строгой согласованности (более точно можно говорить о последовательной согласованности, однако так как всё взаимодействие организованно через описанный слоя доступа к распределённой системе, можно говорить об отсутствии внешнего наблюдателя, а следовательно, и строгой согласованности [9]). Пример Mirror Networking показал, как использование согласованности в конечном счёте может маскировать задержки сетевого взаимодействия путём использования механизма предсказаний.
Разработанная система также может использовать преимущества более слабой модели согласованности. Для этого необходима обёртка, реализующая управление состоянием с использованием предсказаний пакетов. Как было отмечено ранее, если узлом было запрошено Forward распространение некоторого пакета, то в конечном счёте пакет будет обработан данным узлом. Ввиду этого узел может предположить, что наиболее вероятным следующим распределённым состоянием системы, будет состояние, полученное в результате последовательной обработки отправленных узлом пакетов с использованием текущего распределённого состояния. Однако, при ошибке предсказания необходим механизм возврата последнего действительного состояния.
Механизм возврата состояния может оказать существенное влияние на производительность и удобство сопровождения всего приложения в целом, поэтому, при необходимости его использования, должен определяться исходя из способа представления состояния и архитектуры приложения. Далее приведены некоторые способы реализовать возврат состояния:
- Использование неизменяемого состояния — каждое изменение создает новое состояние, не меняя старое. Для возврата достаточно хранить последнее действительное состояние.
- Использование отменяемых операций — каждая операция некоторым образом описывает действие, которое необходимо выполнить для отмены эффекта применения операции. Для возврата необходимо отменить эффекты всех предсказанных операций.
- Очередь неподтверждённых изменений — текущее состояние описывается как результат применения неподтверждённых изменений к действительному состоянию. Фактическое применение происходит при получении следующего действительного состояния.
Описываемое в данной работе программное обеспечение было реализовано на платформе.NET с использованием языка программирования C#. Описанные модули реализованы в виде классов UnconnectedLinearizer, ConnectedLinearizer и ReconnectedLinearizer.
Добавление и удаление узлов осуществляется посредством следующих методов:
– void SetParentConnection(TConnection? connection)
Примечание: изначально узел функционирует в роли корневого, для начала функционирования узла в роли корневого после указания родительского соединения, необходимо вызвать SetParentConnection, где значением connection является null.
– void AddChildConnection(TConnection connection)
– bool RemoveConnection(TConnection connection)
Для каждого из модулей возможно передать обработчик следующих событий:
– void OnConnectionEstablished(TConnection connection, bool parent, bool reconnect);
– void OnConnectionClosed(TConnection connection, bool established, bool parent, bool beheaded);
Для модулей ConnectedLinearizer и ReconnectedLinearizer обработчик также содержит следующие события:
– void OnClusterChanged(bool attached);
– void OnClusterNodeConnected(Guid nodeId);
– void OnClusterNodeDisconnected(Guid nodeId);
Для модуля ReconnectedLinearizer обработчик также содержит следующие событие:
– void OnClusterNodeReconnected(Guid nodeId);
Реализация использует паттерн Ambient Context для того, чтобы предоставить контекст выполнения при обработке пакета. Контекст включает в себя следующую информацию.
– bool IsRoot
Примечание: истинно, если текущий узел является корневым при обработке пакета.
– TConnection? Connection
Примечание: Соединение, ассоциированное с узлом, непосредственно отправившим пакет, null, если пакет был создан текущим узлом.
– PropagationDirection PropagationDirection
Примечание: режим распространения пакета
Для модулей ConnectedLinearizer и ReconnectedLinearizer контекст также включает в себя следующую информацию:
– Guid NodeId
Примечание: идентификатор узла, являющегося отправителем пакета.
Литература:
- Margaret, R. Push Technology / R. Margaret. — Текст: электронный // Techopedia: [сайт]. — URL: https://www.techopedia.com/definition/5732/push-technology (дата обращения: 30.05.2025).
- Roy, T. F. Architectural Styles and the Design of Network-based Software Architectures: специальность «philosophy in information and Computer Science»: диссертация на соискание ученой степени доктора технических наук / Roy Thomas Fielding;. — IRVINE, 2000. — c. — Текст: непосредственный.
- Косяков, М. С. введение в распределенные вычисления / М. С. Косяков. — Санкт-петербург: ИТМО, 2014. — 155 c. — Текст: непосредственный.
- Maarten, v. S. Distributed Systems / v. S. Maarten, S. T. Andrew. — 4-е изд. — Maarten van Steen, 2025. — 685 c. — Текст: непосредственный.
- Mirror Networking. — Текст: электронный // Mirror: [сайт]. — URL: https://mirror-networking.gitbook.io/docs (дата обращения: 30.05.2025).
- The Raft Consensus Algorithm. — Текст: электронный // Raft: [сайт]. — URL: https://raft.github.io/ (дата обращения: 30.05.2025).
- The Split-Brain Phenomenon: A Distributed Systems Dilemma. — Текст: электронный // Java Code Geeks: [сайт]. — URL: https://www.javacodegeeks.com/2023/10/the-split-brain-phenomenon-a-distributed-systems-dilemma.html (дата обращения: 30.05.2025).
- Киселёв, А. И. Архитектура модульной системы удалённого вызова методов для современных платформ программирования / А. И. Киселёв. — Текст: непосредственный // Информационные технологии и системы. — Минск: БГУИР, 2024. — С. 240.
- The Art of Multiprocessor Programming / Herlihy Maurice, Shavit Nir, Luchangco Victor, Spear Michael. — 2-е изд. — Cambridge: Morgan Kaufmann, 2021. — 553 c. — Текст: непосредственный.