Как стать автором
Обновить
Dodo Engineering
О том, как разработчики строят IT в Dodo

Как я начал писать симулятор распределённой системы, а закончил WebAssembly

Время на прочтение8 мин
Количество просмотров5.7K

Часть 1. Идея

Несколько месяцев назад мне захотелось сдуть пыль со своего аккаунта в Steam и поиграть в старые игры про программирование. While True Learn в очередной раз показалась слишком скучной, я пару дней позалипал в TIS-100, реализуя свой многопоточный процессор, но в конце концов осознал, что интереснее не играть в игры про программирование, а самому писать такие игры.

Тот самый TIS-100, который вдохновил меня на свою разработку
Тот самый TIS-100, который вдохновил меня на свою разработку

Идея пришла в голову сразу. Моё хобби (если можно так сказать) — распределённые системы и проблемы консенсуса. Я с разной степенью регулярности почитываю книги и статьи на эту тему и никогда не пропускаю конференцию HydraConf. Вообще про проблематику распредёленных систем очень хорошо написал в своей статье мой бывший коллега Миша Кумачёв, и я очень рекомендую её почитать, если тема вас вдруг заинтересуют. А ещё в ней прекрасные картинки.

Назвал я свой проект Distributed game. Мне хотелось, чтобы, с одной стороны, он был про распределённые системы, а с другой — чтобы в нём была игровая составляющая. Например, написать систему, которая работает с одним узлом и одним клиентом, потом систему с несколькими узлами и клиентами, потом систему, устойчивую к отказу узлов и т.д.

На ум пришло одно из технических определений видеоигры: это набор состояний, которые переходят одно в другое с течением времени. Так уж оказалось, что это определение вполне подходит не только для описания видеоигры, но и для описания распределённой системы. Более того, этот подход активно используется как раз для проверки корректности алгоритмов распределённых систем. Один из инструментов, основанных на этом, называется TLA+, и он однозначно заслуживает, чтобы его изучить, если вы интересуетесь распределёнными системами.

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

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


У меня не было цели написать «свой TLA+», более того, я прекрасно понимаю, что до более-менее промышленного инструмента, который проверяет системы вероятностным способом, типа Maelstrom, мне тоже сильно далеко. Что я хотел: иметь возможность хотя бы примерно описывать и запускать некоторые алгоритмы (двухфазный коммит, read/write quorum, консенсус как программа максимум) на Python, визуализировать их, добавить чуть-чуть интерактива, чтобы можно было хотя бы примерно прикинуть проблемные места реализации алгоритмов распределённых систем.

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

Часть 2. Реализация

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

  class SimulatorLoop:  
  	def add_object(self, obj):
        self._objects.append(obj)

    def loop(self):
        while True:
            self.process()

            if self._sleep_interval > 0:
                time.sleep(self._sleep_interval)

    def process(self):
        if self._timer:
            self._timer.process()

        for o in self._objects.copy():
            o.process()
            if _has_method(o, "destroyed") and o.destroyed():
                self._objects.remove(o)

В этом коде не должно быть ничего нового для тех, кто хоть раз пробовал написать свою игру. Все объекты внутри симулятора имеют метод process(), который вызывается в каждом шаге цикла loop(). Также объекты можно добавлять в пул с помощью add_object() , а некоторые из них удаляются, если имеют метод destroyed().

Все объекты реализуют два класса: WebServer , который представляет собой узел нашей распределенной системы, и Signal, который является средством взаимодействия узлов.

WebServer — это класс, содержащий три основных метода:

  • send_message(receiver_id, message)

  • add_message(message)

  • process()

Метод send_message(receiver_id, message) создаёт объект Signal (1), в котором содержится сам «пакет сообщения» и ID сервера-получателя. Фактически Signal через определённое количество шагов (process) симулятора вызывает коллбэк add_message(message) (2) уже на стороне получателя.

Метод add_message(message) с помощью типизации, декораторов и немного «питонячьей» магии отправляет сообщение в один из эндпоинтов сервера (3). В общем, получился такой игрушечный веб-сервер, который обрабатывает приходящие сообщения в эндпоинтах.

Веб-серверы используют именно сигналы, а не вызывают методы друг друга напрямую, чтобы сымитировать асинхронную суть сетевого взаимодействия. У сигнала может быть произвольное время выполнения, более того, можно добавить возможность, чтобы сигнал «потерялся», имитируя сетевые разрывы.

Клиент, гейтвей, ноды — это всё наследники класса WebServer. Все они отличаются только эндпоинтами.

Диаграмма последовательностей при round-robin
Диаграмма последовательностей при round-robin

На картинке выше изображена диаграмма последовательностей той системы, которую я реализовывал. Клиент знает только о гейтвее. Гейтвей выступает в роли прокси между клиентом и узлами системы, соответственно, он знает обо всех веб-серверах. Гейтвей пересылает запросы клиента узлам по round-robin (первый запрос пришёл на первый узел, второй — на второй). Дальше узлы обмениваются между собой сообщениями и отправляют ответ обратно на гейтвей, а тот возвращает клиенту. Все стрелки на диаграмме — это на самом деле объекты сигналов.

Базовый сценарий, который я в итоге воплотил, это key-value хранилище с одним-единственным key, или, иначе говоря, регистр. У клиента есть два метода: записать в регистр и прочитать из регистра. Алгоритм взаимодействия узлов должен обеспечивать консистентность результатов для клиента.

Первоначальный набросок идеи на бумаге. Тут Gateway еще называется Load Balancer'ом
Первоначальный набросок идеи на бумаге. Тут Gateway еще называется Load Balancer'ом

А где же игровая составляющая? Суть в том, что алгоритм взаимодействия узлов должен реализовать игрок, наследуя класс Node. Минимум нужно реализовать два эндпоинта:

@WebServer.endpoint(message_type=ClientReadRequest)
@abc.abstractmethod
def process_read_request(self, request):
	pass

@WebServer.endpoint(message_type=ClientWriteRequest)
@abc.abstractmethod
def process_write_request(self, request):
	pass

Эти эндпоинты обрабатывают входящие read- и write-запросы от клиента. Естественно, распределённая система не была бы распределённой, если бы узлам не пришлось общаться друг с другом, а для этого придётся создавать свои новые типы сообщений и эндпоинты.

Часть 3. Визуализация

Сперва я думал сделать интерфейс в стиле TIS-100, т.е. чисто консольный вывод, и не заморачиваться с какой бы то ни было визуализацией. Каждый шаг симулятора был отдельной строчкой в выводе консоли, а отображал я отправку клиентами запросов и получение ими ответов. Запустил симулятор и получил что-то похожее на картинку ниже (повернутую на 90°).

Консольная визуализация
Консольная визуализация

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


Снова я вернулся к теме визуализации, когда наткнулся на описание инструмента, строящего диаграммы для таблиц в хранилище данных. Я зашел в GitHub проекта, увидел там ipynb-файлы и тут меня осенило! Есть же визуализация данных в Jupyter! А раз есть визуализация данных, возможно, есть и анимация.

Погуглив, я наткнулся на статью, автор которой заморочился ровно тем, что мне было нужно — созданием и запуском игр в Jupyter. Вооружившись опытом из статьи, вспомнив опыт написания игр на, прости господи, Delphi и используя исходную библиотеку ipycanvas, я собрал, наконец, вариант, из которого стало видно, что внутри симулятора что-то происходит.

Выглядело это примерно вот так:

https://mybinder.org/v2/gh/xneg/distributed-game/main?labpath=%2Fsrc%2Fsandbox_notebook.ipynb
https://mybinder.org/v2/gh/xneg/distributed-game/main?labpath=%2Fsrc%2Fsandbox_notebook.ipynb

Здесь всё, как на диаграмме последовательностей: есть клиенты, гейтвей, ноды (кружки красного цвета), между ними летают сигналы (кружки синего цвета)... Я даже нашёл баг в своей реализации, когда внутренний метод when_any(n) работал, как when_all().

Когда я показал анимацию с работой симулятора паре своих знакомых, они сказали, что это очень похоже на страницу с описанием работы алгоритма Raft. Я был весьма доволен, потому что, похоже, двигался в верном направлении. Я даже позаимствовал из схемы Raft'а центральный круг, который объединяет все узлы.

https://raft.github.io/
https://raft.github.io/

Супер-бонусом было то, что можно было в соседней ячейке написать код своего алгоритма для узлов, подсунуть его тут же в симулятор и наблюдать, как меняется поведение. Была всего пара минусов: не так-то просто прикрутить именно интерактивность, а ещё для запуска нужно было скачать код себе и запустить локально JupyterHub.

Однако из той же статьи я узнал про существование Binder, парой кликов добавил туда свой ноутбук и — вуаля! — прямо сейчас вы можете посмотреть, как это всё выглядит, перейдя по ссылке.

С Jupyter и Binder было всё классно. Они дали мне то, что нужно: основной код симулятора спрятан в модулях бэкенда; игрок может писать свой код в браузере, используя классы моей библиотеки; запустить и посмотреть, как всё работает. Очередной минус — на этот раз единственный, но существенный, — был в том, что в Binder'е предоставляются не очень сильные виртуалки и порой анимация серьёзно тормозит. Кстати, в случае статических вычислений это вообще не недостаток, поэтому рекомендую всем Binder для шаринга своих ноутбуков.


Прошла ещё пара недель. Мы отмечали окончание рабочей недели с коллегой, фронтенд-разработчиком. Я рассказал про проект и попросил поделиться идеями, как бы запустить его на клиентской машине без сервера, потому что я точно видел похожие симуляторы, работающее только в браузере. Коллега упомянул WebAssembly...

Я с фронтендом всегда был на «вы» и старался особо его не касаться, но тут понял, что иного выхода нет. А помните, как всё хорошо начиналось в консольке? Моя цель была найти что-то очень похожее на вариант с запуском игр в Jupyter, только на этот раз уже через WebAssembly в браузере. Сначала попалась эта статья и я понял, что смогу повторить супер-бонус из варианта с Jupyter: можно будет написать код узла прямо в браузере и тут же его использовать без компиляции в WebAssembly. Потом я поискал ещё и наткнулся на пост на Reddit, где пользователь сделал ровно то, что мне было нужно — игру Pong на Python в WebAssembly с помощью PyScript.

Эта библиотечка, скорее всего, была собрана чисто для демонстрационных целей, потому что умела рисовать только прямоугольники. Мне пришлось прикрутить свои круги (простите за каламбур), потом долго и с костылями скрещивать PyScript с CodeMirror...

В результате получилась страница с честным WebAssembly без сервера, которая не требует никаких предварительных установок, но где можно писать код и выполнять на Python. Запустить можно по ссылке.

 https://xneg.github.io/distributed-game/
https://xneg.github.io/distributed-game/

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

И тут я сломался.

Часть 4. Призыв о помощи

Зачем я написал эту статью? Честно говоря, я немного задолбался. Работа над стройным, понятным, хоть и слегка наивным симулятором распределённой системы практически прекратилась на фоне моих приключений с Jupyter, ipycanvas, WebAssembly и запуском в браузере.

В той версии, что открывается сейчас, много чего нет:

  • нельзя добавлять и удалять узлы;

  • нет никакой проверки консистентности ответов, получаемых клиентами;

  • я ещё даже не приступал к системе, которая представляла бы собой распределённый упорядоченный лог (для реализации собственного Raft, например);

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

  • WebAssembly реализация выглядит «вырвиглазно», как, собственно, и вариант с Jupyter.

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

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

Спасибо, что дочитали до конца, жду ваших комментариев! А вот и сам репозиторий с симулятором: https://github.com/xneg/distributed-game.


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

  1. Разработка своего ассемблера на TIS-100

  2. Статья-введение про проблемы распределённых систем от @Ceridan

  3. Язык спецификаций TLA+

  4. Отличная (но сложная) книжка по TLA+

  5. Статья по созданию игр внутри Jupyter с помощью ipycanvas

  6. Хостинг Jupyter-ноутбуков в Binder

  7. Статья, в которой описывается, как написать Python REPL в браузере

  8. Пост на Reddit, который стал стартом для использования PyScript

  9. А вот и сам проект pywebcanvas (почему-то в Gitlab)

Теги:
Хабы:
Всего голосов 37: ↑26 и ↓11+24
Комментарии10

Публикации

Информация

Сайт
dodoengineering.ru
Дата регистрации
Дата основания
Численность
201–500 человек
Местоположение
Россия