Разработка инструмента визуализации, отладки и экспериментирования для распределенных алгоритмов

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

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

Стоить заметить, что концепция распределенных вычислений сложнее для восприятия. При этом, на данный момент есть не так много проектов, где предпринимаются попытки визуализировать алгоритм в действии. Одним из самых известных является реализация raft.io [1], которая на основном информационном сайте алгоритма Raft [2] показывает принцип его работы с помощью анимации. Визуализация дает базовое понимание о работе алгоритма Raft, но она реализована для одного конкретного алгоритма и для одного конкретного тестового случая.

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

Для этой цели разрабатывается проект “Parallel and Conquer” (PAC). Проект состоит из backend и frontend частей, взаимодействующих между собой. Frontend-часть отвечает за визуализацию алгоритмов для демонстрации, тестирования и дебага. Backend-часть реализует алгоритмы и тестовые сценарии для некоторых из них (на данный момент это Алгоритм пекарни Лэмпорта (Lamport Mutex) [3], Paxos [4], Raft). В данной работе будет описана frontend-часть проекта.

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

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

1. Простота использования

2. Отсутствие зависимости от платформы

3. Возможность отобразить основные алгоритмы, изучаемые в университетах, показав их особенности

4. Возможность визуализации алгоритмов пользователя, вне зависимости от того, какие языки программирования ему известны

В соответствии с этим был выбран протокол общения между клиентом и сервером через определенный application programming interface (API) так, что, если в дальнейшем базовый backend-сервер меняется на пользовательский, для User Interface (UI) части ничего не меняется, если используется тот же API.

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

1. Обзор существующих решений

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

Xtango [5] -- это система анимации алгоритмов общего назначения, которая помогает программистам реализовывать анимированное отображение своих собственных алгоритмов. Недостатки этой системы:

1. необходимость написания программы на языке C или создание файла трассировки, который читаем драйвером C

2. невозможность отображения дополнительной информации о состояниях процессов для тестирования и отладки

Polka [6] -- это система анимирования, которая подходит для визуализации однопоточных и параллельных программ. Основным недостатком этой реализации является то, что она требует Motif или Xaw (набор виджетов Athena), поэтому пользователь должен приложить дополнительные усилия для использования этой системы.

“A tool for interactive visualization of distributed algorithms” [7] (название проекта не указано) -- это инструмент для визуализации распределенных вычислений. Он имеет ограниченный список алгоритмов, написанных на Java, но пользователь может реализовать свой собственный алгоритм, вызывая определенные методы из своего Java- кода. Требование знать определенный язык программирования может помешать некоторым студентам использовать этот инструмент визуализации, и в этом заключается недостаток данного решения.

У проекта Lydian [8] есть инструмент, разработанный, по словам авторов, для образовательных целей, который помогает в изучении распределенных алгоритмов. В проекте используется библиотека Polka для визуализации, обзор которой приведен выше. Анимация позволяет наблюдать за взаимодействием процессов, причинно-следственными связями и логическими временами. Тем не менее, в окошке приложения может быть отражена только одна компонента из всего приложения, из-за чего у пользователя нет возможности сравнивать и проводить связи между процессами, журналами, уникальным состоянием процесса и тем, как они влияют друг на друга.

Проект ViSiDiA [9] -- это самый современный из перечисленных инструмент для визуализации с настраиваемым интерфейсом. Недостатки этого проекта заключаются в следующем:

1. пользователь должен знать и использовать язык программирования Java

2. для визуализации пользовательского проекта в код должны быть встроены методы библиотеки ViSiDiA

3. загрузка проекта с официального сайта является сложной задачей из-за необходимости прямого контакта с разработчиками

Таким образом, существующие на данный момент решения имеют недостатки, которые могут быть существенны при выборе инструмента для визуализации и тестирования. “Parallel and Conquer” старается учесть проблемы описанных выше реализаций и создать простое в использовании приложение, которое будет понятно пользователю.

2. Описание работы

Ниже описано, как происходит процесс использования интерфейса пользователем и как ему трактовать некоторые детали визуализации, если он совсем не знаком с распределенными алгоритмами. Затем разобраны детали реализации с более подробным описанием внутренней логики. После этого в пункте «Общие элементы кастомизации интерфейса» показано, как меняется смысл компонент приложения в зависимости от проигрываемого алгоритма. В последнем пункте основной части описано, как пользователь должен использовать API и особенности приложения для понятной визуализации своего собственного алгоритма.

Во всем документе слова “узел”, “процесс” и “нода” (от англ. node) будут использованы, как синонимы, во избежание излишних повторений.

Функциональность приложения с точки зрения пользователя.

Для пользователя PAC -- это single page application (SPA или одностраничное приложение). Первое, что он видит, заходя в браузер, -- это форма с несколькими полями.

Рис. 1. View конфигурирования алгоритма

Первым этапом предлагается выбрать алгоритм, который нужно визуализировать и тестировать. Пользователь может выбрать один из четырех алгоритмов: Lamport Mutex, Paxos, Raft, Custom.

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

Общими для всех алгоритмов полями являются “Node number”, “Host”, “UI Port”. “Node number” не должно быть меньше одного или превышать 20. Ограничение по числу было сделано из-за редкого изучения и демонстрации в образовательных учреждениях алгоритмах, на числе узлов больше 10, и из-за потенциального нагромождения визуальных элементов. В поле “Host” нужно указать localhost или IPv4 ip-адрес тестирующего сервера. В поле “UI Port” требуется указать порт, по которому происходит общение с UI по Websocket.

При корректном заполнении полей и нажатию кнопки “Apply Config”, будет происходить переход на следующий view.

Рис. 2. View перед запуском алгоритма

В нижнем левом углу доступны 2 кнопки: “PLAY” и “Change Config”. Для запуска теста следует нажать первую, для изменения конфигурации алгоритма -- вторую.

Выше кнопок располагается ScrollBar, с помощью которого при проигрывании теста можно будет отматывать тест назад и перепроигрывать сценарий.

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

В правом верхнем углу можно увидеть 2 формы -- “Time slowdown” и “View slowdown”. “Time slowdown” замедляет (а при желании, ускоряет) время проигрывания теста так, что изменения будут происходить в x * базовая скорость исполнения раз медленнее (или быстрее). “View slowdown” «замедляет» отображение, то есть визуализация становится шире, чем предполагается по линейной зависимости между реальным временем и сеткой координат визуализации. По умолчанию “Time slowdown” -- это 1.0, то есть скорость отображения соотносится 1:1; “View slowdown” -- 10, чтобы все сообщения не сливались в одно при передаче от узла к узлу (процесса к процессу).

Остальные компоненты до запуска теста не несут никакой информации.

При нажатии кнопки “PLAY” происходит запуск тестового сценария выбранного алгоритма в соответствии со сценарием на сервере, и появляются новые детали визуализации.

Рис. 3. View во время исполнения алгоритма

В верхней части слева располагаются стеки (или очереди) внутренних состояний нод. Каждая нода имеет свою очередь, в которой отражается информация, специфичная для алгоритма. При наведении показывается расширенная информация о записи в стеке/очереди и подсвечивается временная метка на линии времени, которая соответствует добавлению этой записи в стек. При желании воспользоваться «ручным режимом» - режим исполнения, при котором пользователь сам инициирует действия со стороны процессов - необходимо кликнуть по номеру ноды над очередью состояния. Появится Popup, в котором можно выбрать действие, которое должна выполнить нода. Для закрытия popup нужно совершить клик в любом месте вне него. На текущем этапе развития проекта, «ручной режим» работает для алгоритмов Lamport Mutex и Raft.

Под стеками/очередями внутренних состояний располагается линии времени, каждая из которых отображает отдельную ноду. Между линиями происходит взаимодействия через сообщения. Сообщения каждой ноды имеют свой цвет. Отдельные типы сообщений могут выделяться и отображаться специфической линией: пунктирной (разной длины), точка-тире. Типы специфических сообщений также зависят от алгоритма.

Если сообщение доставлено (передача прошла успешно), то оно завершается на node-получателе точкой цвета линии сообщения. Если сообщение по каким-то причинам оборвалось, то оно завершается «крестиком» между node-отправителем и node-получателем.

При наведении на линию сообщения можно получить дополнительную информацию об этом сообщении. Она появляется над линией времени.

На линии времени есть засечки -- это штампы, соответствующие изменениям состояния внутреннего стека/очереди узла. При наведении на засечку, запись в стеке/очереди будет подсвечена синим цветом, исключая случай, когда запись уже удалена.

При работающем тесте можно нажать кнопку “PAUSE” (на месте кнопки “PLAY”), и тест будет приостановлен.

При проигрывании и после остановки можно воспользоваться ScrollBar и прокрутить тест до нужного момента времени.

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

Справа от стеков, внутри красной окружности отображается «общее состояние». Оно также специфично для каждого алгоритма.

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

Используемые технологии и детали реализации web-приложения.

Приложение написано на языке программирования JavaScript и работает на базе программной платформы Node.js [10]. В качестве основного Фреймворка, при разработке используется React [11].

В процессе выбора технологий стоял вопрос об использовании React, Angular.js [12], Angular 2 [13]. Вариант с Angular.js не подходил из-за постепенного устаревания технологии, медленной скорости работы и вытеснения его Angular 2, хотя существует достаточное количество активно поддерживаемых web-приложений, написанных на первом.

Angular 2 современен и активно разрабатывается. Сейчас идет активный переход на TypeScript в качестве основного языка разработки, и это повышает качество и читаемость кода. Однако, это создает некоторые трудности: при желании наследовать некоторую JavaScript-библиотеку, разработчик должен собственноручно прописать типизацию, иногда это занимает много времени и порождает сложности.

React -- это Фреймворк, «живущий» за счет JSX, что очень удобно, в условиях разработки приложения с множеством динамических графических элементов. React имеет структуру кода, напоминающую объектно-ориентированное программирование (ООП), что повышает читаемость, при правильном оформлении. Существует множество готовых решений, которые можно использовать «из коробки», упрощающих жизнь разработчику.

Приложение структурировано по компонентам. Каждой компоненте соответствует одноименный файл с кодом класса. Зависимость между классами -- иерархическая система. В корне существует одна главная компонента -- Main, на уровень ниже две другие -- ConfigurationSetup и App. На третьем уровне находятся «сыновья» App - NodeState, SharedState, Actions, Logs. Существует также отдельный Utils файл со вспомогательными функциями и компонента для реализации логики checkbox-а.

Рис. 4. Иерархия компонент системы

Поскольку приложение является SPA, Main -- компонента, регулирующая, какую информацию в данный момент нужно скрыть, а какую отобразить. Логика внутри компоненты такова: если конфигурация алгоритма, который нужно воспроизвести, установлена, то отображается App компонента, иначе -- ConfigurationSetup. Основные методы -- SetConfig и RemoveConfig. Названия полностью соответствуют логике, которую реализовывают функции. Важное замечание: функции работы с конфигурацией никогда не вызываются внутри самой компоненты, они передаются параметрами в дочерние классы и вызываются оттуда исходя из логики, которая будет описана ниже.

Компонента ConfigurationSetup это конструктор конфигурации для запуска теста. Пользователь заполняет необходимые поля формы в соответствии с выбранным алгоритмом. Затем происходит обработка поступивших данных и формирование самого config в формате JSON, по структуре, указанной ниже.

{

"nodes": { // конфигурация нод

"0": { // id ноды, которая конфигурируется

"tunnels": [{ // каналы ноды 0

"id": 1, // нода, с которой конфигурируется канал

"host": "localhost",

"in": 11000, // порт для данных от 1 к 0 (на самом деле до proxy)

"out": 11001 // порт для данных от 0 к 1 (на самом деле от proxy)

}..]

}...

},

"PAC": { // конфигурация для backend-proxy

"nodes": { // id ноды, которая конфигурируется

"0": {

"1": {

"in": 11001, // порт для данных от 1 к 0

"out": 10010 // порт для данных от 0 к 1

}

}...

},

"ctrl_port": 9020, // порт для “тестировщика”

"ui_port": 9040, // порт для общения frontend и backend частей

"alg_support_port": 9060, // порт для сбора данных в json-отчет, который приходит от сервера при запросе данных из ui_port

"host": "localhost" // адрес тестирующего алгоритма

},

"algorithm": {

"type": "Lamport Mutex", // тип алгоритма

"params": {

"command_host": "localhost", // хост для отправки команд при «ручном режиме»

"command_port": 10002, // порт для отправки команд при «ручном режиме»

"manual":false // идентификатор, является ли запуск полностью «ручным» (если нет, начнется проигрывание тестового сценария)

}

}

}

После обработки конфигурации, вызывается метод SetConfig и config отправляется по WebSocket на легковесный сервер на python, чья работа заключается в запуске теста с заданной конфигурацией.

При установке конфигурации срабатывает конструктор компоненты App. Это компонента, регулирующая общение с тестирующим сервером и объединяющая все дочерние компоненты для визуализации.

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

алгоритм программный интерфейс

Рис. 5. Схема получения данных от сервера

Описание некоторых методов класса:

СonnectSocket

Метод для соединения с тестирующим сервером. В Websocket передаются хост и порт из конфигурации, и происходит соединение, по которому будет происходить общение frontend и backend частей в дальнейшем. Важно заметить, что сокет не пробрасывается в случае, если алгоритм Custom и переданы mock-данные (с которыми будет происходить запуск, вместо запроса их от сервера).

RequestData

Метод для запроса данных от сервера. При запросе через Websocket передается timestamp, начиная с которого нужно возвращать действия, изменения состояния и т.д.

HandleData

Метод, выполняющий обработку при получении данных от сервера. Из приходящего JSON в соответствии с API выделяются ключевая информация и сохраняется в локальный state для дальнейшей передачи дочерним компонентам.

ProcessStates

Метод для обработки приходящих в данных внутренних состояний узлов. Данные приходят в формате «время -- изменение состояния», а не «время -- слепок состояния». Из-за этого требуется обработка данных по получению, так как пользователю понятнее видеть слепок состояния для currentTime.

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

Также результат работы используется компонентой Actions для отражения на линии времени засечек события «внутреннее состояние поменялось».

Изначально обработка состояний процессов была написана отдельно для NodeState и SharedState компонент и реализовывала разную логику обработки одних и тех же данных. После видимых «залипаний» интерфейса в этом месте при проигрывании алгоритма Raft (в этом алгоритме приходит большое количество записей в node_state), обработка state-а была перенесена в App. Сравнительных замеров времени произведено не было, но «залипания» интерфейса при Raft ушли.

DoEveryInterval

Вспомогательная функция, вызываемая каждую секунду (время конфигурируется). Внутри нее происходит изменение текущего времени (currentTime), которое влияет на то, какой момент времени исполнения алгоритма сейчас видит пользователь. Также происходит проверка того, что данных достаточно. Класс хранит в себе переменную timestampTo, который приходит от сервера вместе со всеми данными -- timestamp до которого известно происходящее между нодами взаимодействие в данной порции данных.

Рис. 6. Временная схема запроса данных

ScrollTime

Метод-реакция на прокрутку ScrollBar. В зависимости от отступов от границ ScrollBar, метод высчитывает время, до которого прокрутил пользователь, и устанавливает currentTime.

HandleVisibilityChange

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

Первой дочерней компонентой App является NodeState. Эта компонента отвечает за отображение стеков/очередей состояния узлов. Она почти не делает внутри себя никакую обработку, только визуализирует уже заранее пред обработанные на уровень выше данные внутри ProcessStates. Все методы этого класса касаются только визуальных эффектов, за исключением обработки кликов вызова «ручного режима».

GetPopupContent

Функция формирует view компоненты Popup и определяет обработчики событий. При клике по кнопкам внутри popup срабатывает вызов метода MakeInteractiveRequest компоненты App. Этот метод отправляет запрос backend-серверу через Websocket. Общение при «ручном режиме» происходит с тем же хостом, но по другому порту. Порт настраивается при создании конфигурации полем “Port for Interactive commands”. Данное поле в конфигурации определено только для алгоритмов Lamport Mutex и Raft, так как не имеет смысла для Paxos.

Следующая дочерняя компонента -- SharedState, отображающая текущее состояние некого общего состояния системы, зависящего от алгоритма. Внутри данной компоненты основной метод -- ProcessSharedState, где реализована логика по определению состояния системы из уже обработанных ранее локальных очередей внутри ProcessStates.

Actions -- самая объемная по функционалу компонента и класс. В нем реализована вся логика по обработке и визуализации сообщений между нодами. Ниже приведены некоторые важные для интерфейса функции.

ProcessActions

Метод для обработки сообщений от узла к узлу в данных от сервера. В соответствии с API, для удобства формирования JSON с данными, действия приходят в виде map, где ключом является номер ноды, а значением -- массив действий, которые были выполнены к данному моменту времени. Для отрисовки действий внутри Scalable Vector Graphic (SVG) удобным было выбрано хранение сообщений в виде array.

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

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

После указанной выше обработки происходит вызов функции SetTimeOffset и пост-обработка для установки корректного времени «доставки» для всех сообщений.

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

RenderRequests

Метод для отрисовки взаимодействия процессов между собой. Область отображения процесса передачи сообщений реализована с помощью SVG. Линии сообщений внутри SVG рисуются с помощью тега line, для которых заданы координаты x1, x2, y1, y2. Координаты определяются так:

x1 = TimestampToShape(timestampFrom) + margins

y1 = offset * from + margins

x2 = TimestampToShape(timestampTo) + margins

y2 = offset * to + margins

Где from и to это номера узла, от которого и к которому были отправлены сообщения; TimestampToShape -- функция, переводящая timestamp в координату внутри SVG; offset и margins -- отступы для визуально-аккуратного отображения.

Компонента формируется за счет прохождения в цикле, где для каждого сообщения из результата работы функции ProcessActions вычисляются ее корректные координаты и выбираются style-особенности отображения в зависимости от типа передаваемого сообщения и его статуса (доставлено/не доставлено).

GetCurrentTo.

Метод для корректного отображения действий, которые еще не дошли до отправителя. Как описано выше, бывают события, для которых еще не известно время доставки или же время известно, но оно позже, чем currentTime. В таком случае требуется определение временного timestampTo. Этот функционал реализует функция GetCurrentTo, вычисляя координату на гипотенузе прямоугольного треугольника исходя из координат на катетах.

Рис. 7. Схема вычисления координат линии сообщений

SetTimeOffset (GetTimeOffset)

Метод реализует растягивания линии времени в местах скопления большого количества действий (множества отправок или приема сообщений). Изначально при отправке сообщений нескольким процессам сразу, все действия имели начальную точку в одном месте из-за незначительной разницы между timestamps между ними. Функционал по «расширению» визуального отображения timeline был бесполезен в этом месте, из-за большой разницы между временем доставки сообщения и временем между отправками. Поэтому было принято решение реализовать искусственное растягивание в местах «скопления» отправленных или приходящих сообщений.

Рис. 8. График растягивания времени в промежутках скопления действий

Последней, но не менее важной компонентой, является класс Logs. Его устройство предельно просто: он отражает все логи, которые происходили до текущего времени. Логи приходят от сервера со всеми другими данными.

Общие элементы кастомизации интерфейса.

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

Lamport Mutex

Краткое описание алгоритма:

Алгоритм решает задачу конкурентного доступа к данным. При желании ноды занять критическую секцию, она добавляет запись об этом в свою внутреннюю очередь и отправляет всем другим нодам сообщение о своем намерении. При получении сообщения от узла все другие узлы добавляют в свою очередь запись с указанным timestamp и отправляют подтверждение о получении обратно. Сообщение просеивается в очереди, очередь является priority queue по timestamps. Процесс занимает критическую секцию, когда в своей очереди она первая и она получила подтверждения от всех других нод. При освобождении критической секции, всем нодам сообщается об этом отдельным сообщением. Когда узел получает сообщение об освобождении, он удаляет соответствующую данному процессу запись из своей очереди.

Особенности интерфейса:

В соответствии с описанием выше, визуализация и логика для данного алгоритма функционирует так:

1. При создании конфигурации никакой дополнительной информации, кроме количества нод, не требуется.

2. NodeStates -- это priority queue каждого отдельного процесса, где хранится timestamp и номер ноды, которая запросила доступ с этим timestamp.

3. Под очередью выводится информация, когда нода ожидает доступа к критической секции или освобождает ее (подпись “acquiring” и “releasing”).

4. В Actions сообщения бывают типов lock, release, confirmation.

5. В секции SharedState отображается номер узла, который в данный момент занимает критическую секцию.

6. Cообщения, которые выделяются отличающимся стилем отрисовки линии: release, confirmation.

7. Реализован интерактивный режим с двумя типами команд: lock и release. При выполнении команды lock, с незначительной задержкой по времени, происходит попытка взятия критической секции. При совершении команды release, соответственно - освобождение.

Paxos

Краткое описание алгоритма:

Алгоритм решает задачу консенсуса в распределенных системах. Каждый процесс имеет свою роль: client -- клиент распределенной системы, который может отправить запрос и получить на него ответ (в условиях PAC это тестовый фреймворк), proposer -- нода, отвечающая за организацию процесса голосования, acceptor -- нода, имеющий право голоса за accept или reject предложения, learner -- компонент системы, который запоминает принятое решение.

Proposer делает предложение с определенным порядковым номером и отправляет всем acceptors сообщение-предложение. Если порядковый номер сообщения больше, чем все принятые ранее, acceptor отвечает на это сообщением-обещанием не принимать ничего с номером больше, чем текущий. Если acceptor уже принял предложение с меньшим номером, он возвращает номер этого предложения и принятое значение. Если proposer получил сообщения-обещания от N+1 из 2N+1 нод, значение обрабатывается дальше. Если ответы пришли с несколькими значениями (разными), то выбирается тот, у которого максимальный порядковый номер. После этого proposer отправляет сообщение-принятие всем acceptor с выбранным значением. Если acceptor получает сообщение-принятие, он принимает его, только если ранее не принял предложение с номером больше текущего. Иначе он принимает значение и отвечает сообщением-принятием всем learner. Learner просто запоминает полученное значение.

Особенности интерфейса:

1. При создании конфигурации требуется указывать начальные роли процессов: proposer или acceptor.

2. NodeStates -- это история внутренних действий каждого из узлов (принятие значения, запоминание значения и т.д.).

3. Под очередью отображается текущая роль процесса: proposer, acceptor или leader.

4. В Actions сообщения бывают типов preparation, promise, accept, accepted.

5. В секции SharedState отображается значение, которое было принято последним (learned value).

6. Cообщения, которые выделяются отличающимся стилем отрисовки линии: promise, accept, accepted.

Raft

Краткое описание алгоритма:

Алгоритм решает задачу выбора лидера (leader election algorithm) и репликации (replication algorithm). Каждая нода внутри есть конечный автомат и лог применения команд к этому конечному автомату. Каждый объект представляет собой пару из номера раунда и значения. Когда начинается выполнение алгоритма, у всех нод запускается таймер со случайным временем отсчета. По окончании времени отсчета, узел увеличивает счетчик раунда и отправляет всем процессам свою кандидатуру в качестве лидера с этим номером раунда. Когда узел получает сообщение с запросом на лидерство, если она не является кандидатом и ее счетчик раунда меньше, чем пришедший, то нода отправляет сообщение-согласие на лидерство другой ноде. Узел становится лидером, если получает подтверждение лидерства от более чем половины процессов, иначе у него истекает таймер и он начинает новое голосование. Если нода становится лидером, то она отсылает всем нодам сообщение “heart beat” о том, что она “жива”. С этого момента начинает стадия репликации. С каждым “heart beat” узел присылает длину своего лога и номер раунда в последнем элементе лога. Если у какой-то ноды лог длинее, она игнорирует весь лог после лога лидера и сообщает об этом лидеру. Если значение в логе отличается, то процесс удаляет последнюю запись и сообщает лидеру об ошибке. Лидер хранит для каждого узла номер последней верной записи. Если он получает сообщение об ошибке от ноды, то он уменьшает этот номер и отправляет те корректные значения истории, которые отсутствуют у процесса. При получении узлом такого ответа, она проверяет, что первый элемент совпадает с ее последним, дополняет свой лог и отвечает сообщением-ok. Иначе, процесс повторяется. Если после того, как нода становится лидером и получает информацию о том, что у N + 1 из 2N + 1 нод лог длиннее, то он синхронизируется с ними.

Особенности интерфейса:

1. При создании конфигурации никакой дополнительной информации, кроме количества процессов, не требуется.

2. NodeStates -- это лог изменений каждой отдельной ноды; в логе каждой ноды прокрашиваются записи, которые уже были подтверждены и проверены с помощью алгоритма репликации.

3. Под очередью отображается текущая роль процесса: leader, follower или candidate.

4. В Actions сообщения бывают типов append_entry, heart_beat, request_vote, vote_response, append_entry_response.

5. Секция SharedState в данном алгоритме не используется.

6. Cообщения, которые выделяются отличающимся стилем отрисовки линии: heart_beat, request_vote, vote_response, append_entry_response.

7. Реализован интерактивный режим с тремя типами команд: request, enable, disable. Request -- команда доступная лидеру и реализующая предложение нового значения для добавления в лог. Значение вводит сам пользователь. Enable и disable - команды, регулирующие жизненное состояние ноды.

Документация по использованию интерфейса с произвольным алгоритмом.

При желании, любой пользователь может запустить свой алгоритм и визуализировать его, используя UI PAC. Для этого нужно выбрать среди алгоритмов Custom и заполнить Test Data Json в соответствии со своим подходом. Есть два варианта:

1. написать свой алгоритм и с помощью механизма Websocket отдавать данные в формате предусмотренном API;

2. при создании конфигурации теста в интерфейсе, указать полный набор данных в формате JSON для проигрывания.

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

1. Общение происходит через Websocket;

2. При запросе от UI в host:port по пути “/ui”, возвращаются данные для визуализации; где host и port указаны при создании конфигурации;

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

Запрос от UI:

{

"Content": JSON.stringify({

"timestamp_from": timestamp, // момент времени, начиная с которого требуются данные

})

}

Ответ backend:

{

"response_id": 1, // номер «пачки» данных, должна увеличиваться с каждым запросом

"timestamp_from": 123456, // timestamp_from из запроса

"timestamp_to": 123457, // timestamp последнего действия в «пачке» данных

"node_count": 3, // суммарное количество нод в системе

"actions": { // сообщения от ноде к ноде

"0": [{ // нода отправитель

"to": 1, // нода получатель

"timestamp_from": 123456, // время отправления

"timestamp_to": 1234567, // время доставки

"status": 1, // 1 - сообщение доставлено, 0 - сообщение не доставлено

"text": JSON.stringify({"message": "string"}) // string - это текст, который будет отображаться при наведении на линию передачи сообщения

}...],

},

"node_state": { // изменения состояния

"0": [{ // нода, чье состояния описывается

"timestamp": 123456, // время изменения состояния

"content": {

"action": "add", // тип действия, см. описание ниже

"node": 1, // нода, которую касается изменения состояния

"time_req": 3, // логическое время внутри ноды (может отсутствовать)

"proposal_id": 0, // номер предложения (может отсутствовать)

"role": "learner", // текущая роль ноды 0 (может отсутствовать)

"mode": "leader", // текущая роль ноды 0 (может отсутствовать)

"stack_show": "loading", // состояние ноды, отображаемое под стеков в виде текста (может отсутствовать)

"shared_show": "ended", // общее состояние, отображаемое в разделяемой области (может отсутствовать)

"value" : 15 // текущая роль ноды 0

}

}...],

},

"logs": [{

"timestamp": 123456,

"text": "I am log" // текст лога

}]

}

Существуют несколько групп событий и правила дня них:

ADD_STACK_MESSAGES -- идентификаторы для добавления в стек/очередь процесса.

Примеры:

o “add” -- универсальное событие на добавление, используется Lamport Mutex и Paxos, для этих алгоритмов предполагает заполнение поля “node”, а для Lamport Mutex также “time_req”

o “promise” -- специфическое событие для Paxos, подразумевает наличие “proposal_id”

REMOVE_STACK_MESSAGES -- идентификаторы для удаления из очереди/стека процесса.

Примеры:

o “pop” -- универсальное событие на удаление, удаляет всегда из начала

o “remove” -- аналогично предыдущему

STATE_MESSAGES - идентификаторы для отражения статуса под колонкой стека/очереди.

Примеры:

o “local_state_change” -- универсальное, подразумевает заполнение поля "stack_show" необходимым для отображения значением

o “acquiring” -- специфичное для алгоритма Lamport Mutex

SHARED_STATE_CHANGE_MESSAGES -- идентификаторы изменения общего состояния.

Примеры:

o “shared_state_change” -- универсальное, подразумевает заполнение поля "shared_show" необходимым для отображения значением

o “acquired” -- специфичное для алгоритма Lamport Mutex

START_TIMER_MESSAGES -- идентификаторы старта таймера (из реализованных алгоритмов актуальны только для Raft).

Примеры:

o “set_timer” -- подразумевает проставление “value” - то, на сколько заводить таймер

STACK_COMMIT_MESSAGES -- идентификаторы подсветки определенной части стека - пометки этой части как «закоммиченная» (также актуальны только для Raft).

Примеры:

o “apply” -- при получении такого сообщения увеличивается локальный счетчик зафиксированных значений

При выборе варианта с собственным сервером, пользователь оставляет в Test Data Json пустой JSON (дефолтное значение {}), выбирает нужный port и host, и применяет конфигурацию. При выборе варианта с указанием всех данных заранее, пользователь должен указать данные в соответствии с API (ответ backend) в поле Test Data Json, host и port могут быть любые.

Заключение

Дальнейшие пути развития приложения могут быть различны.

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

Можно провести работу по улучшению дизайна, добавить больше деталей интерфейса. При реализации новых алгоритмов на backend-стороне можно произвести кардинальные изменения в компонентах UI для этих алгоритмов, если такие изменения требуются. Например, сделать новый режим отображения аналогичный тому, что реализован на raft.io, на смену режиму линии времени.

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

Основной мотивацией проекта было желание помочь студентам и ученикам в изучении распределенных алгоритмов. Проект PAC, и его frontend-часть, в частности, достигла тех целей, которые ставились изначально. Во время финальных доработок backend-части с помощью визуализации были выявлены некоторые проблемы в реализации алгоритма Raft, которые было сложно «поймать», но которые стали явно видны при тестировании с визуализацией.

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

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

Литература

1. raft.io [Электронный ресурс] // The Raft Consensus Algorithm: [сайт]. URL: https://raft.github.io

2. Ousterhout D.O.A.J. In Search of an Understandable Consensus Algorithm 2013.

3. Lamport L. A New Solution of Dijkstra's Concurrent Programming Problem // Communications of the ACM 17, 8. 1974. pp. 453-455.

4. Shostak L.L.W.M.P.A.R. Reaching Agreement in the Presence of Faults // Journal of the Association for Computing Machinery 27, 2, April 1980.

5. Stasko J. Animating Algorithms with XTango // SIGACT News, Vol. 23, 1992. pp. 67-71.

6. Kraemer J.S.A.E. A methodology for building application specific visualizations of parallel programs // Journal of Parallel and Distributed Computing, 18 (2), June 1993. pp. 258-264.

7. Stefan Gruner M.M.M.B. A tool for interactive visualization of distributed algorithms, 2001.

8. Boris Koldehofe M.P.P.T. Distributed Algorithms Visualisation for Educational Purposes.

9. Cйdric Aguerre T.M.M.M. Fully-Distributed Debugging and Visualization of Distributed Systems in Anonymous Networks // 7th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications. Rome, Italy. 2012. pp. 764-767.

10. Node.Js [Электронный ресурс] // Node.Js: [сайт]. URL: https://nodejs.org/en/

11. React [Электронный ресурс] // React Framework: [сайт]. URL: https://reactjs.org

12. AngularJs [Электронный ресурс] // AngularJs: [сайт]. URL: https://angularjs.org

13. Angular 2 [Электронный ресурс] // Angular: [сайт]. URL: https://angular.io

Размещено на Allbest.ru