Файл: Операции, производимые с данными (Обзор существующих решений операций, производимые с данными).pdf

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. Его устройство предельно просто: он отражает все логи, которые происходили до текущего времени. Логи приходят от сервера со всеми другими данными.

---

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

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

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 – команды, регулирующие жизненное состояние ноды.

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

При желании, любой пользователь может запустить свой алгоритм и визуализировать его, используя 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 — идентификаторы для добавления в стек/очередь процесса.

Примеры:

• “add” — универсальное событие на добавление, используется Lamport Mutex и Paxos, для этих данных предполагает заполнение поля “node”, а для Lamport Mutex также “time_req”
• “promise” — специфическое событие для Paxos, подразумевает наличие “proposal_id”

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

Примеры:

• “pop” — универсальное событие на удаление, удаляет всегда из начала
• “remove” — аналогично предыдущему

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

Примеры:

• “local_state_change” — универсальное, подразумевает заполнение поля "stack_show" необходимым для отображения значением
• “acquiring” — специфичное для алгоритма Lamport Mutex

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

Примеры:

• “shared_state_change” — универсальное, подразумевает заполнение поля "shared_show" необходимым для отображения значением
• “acquired” — специфичное для алгоритма Lamport Mutex

---