Часть 1. Идея

Несколько месяцев назад мне захотелось сдуть пыль со своего аккаунта в Steam и поиграть в старые игры про программирование. While True Learn в очередной раз показалась слишком скучной, я пару дней позалипал в 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 (первый запрос пришёл на первый узел, второй — на второй). Дальше узлы обмениваются между собой сообщениями и отправляют ответ обратно на гейтвей, а тот возвращает клиенту. Все стрелки на диаграмме — это на самом деле объекты сигналов.

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

Первоначальный набросок идеи на бумаге. Тут 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

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

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

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/

В коде узла, который сейчас появляется по умолчанию при открытии страницы, кстати, есть баг, который стопорит систему, если количество узлов = 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)