Часть 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)

Комментарии (10)


  1. MentalBlood
    22.07.2022 13:01

    У вас же граф, он описывается таблицей — вот ее и можно рисовать в консоли. Не уверен, что это прям удобный интерфейс, но будет видно {что, от кого, кому} отправляется на данном шаге


    1. Xneg Автор
      22.07.2022 13:08

      Не совсем вас понял. Граф как набор состояний объектов системы? Такую таблицу строит TLA+, но выглядит не очень интуитивно, если честно. И то, эту таблицу читаешь в статике, по сути дебажишь. Или вы о другом представлении?


      1. MentalBlood
        22.07.2022 13:34
        +1

        Я про визуализацию отправки и получения сигналов. Например, строки — от кого, столбцы — кому. В клетках представление сигнала, статус (насколько близок к получению) можно цветом отображать


        1. Xneg Автор
          22.07.2022 13:43
          +2

          Согласен, это мог быть хороший первый вариант. Но я в итоге пошёл другим путём, и вроде похожесть на raft.github.io даёт надежду на то, что путь правильный)


  1. georgepolevoy
    22.07.2022 17:28

    Круто! Хотелось бы иметь возможность создавать симулятор распределенной системы не в коде, а визуально. Есть такие планы?


    1. Xneg Автор
      22.07.2022 17:30

      Спасибо! А что значит "визуально"? В идеальном будущем добавление/отключение узлов, конечно, хочется сделать по клику. Но сам код обработки реквестов, логику алгоритма вряд ли можно будет "накликать".


  1. belonesox
    23.07.2022 10:27
    +1

    А вы не смотрели в сторону SymPy или Salabim (как база именно для симуляции, не визуализации)?


    1. Xneg Автор
      23.07.2022 14:01

      Эх, чукча не читатель... SymPy, пишут, библиотека для выполнения символьных вычислений, как будто не очень в тему.

      А вот Salabim выглядит очень интересно, спасибо, надо изучить.


      1. belonesox
        23.07.2022 14:04
        +1

        О, сорри, SimPy конечно. Он правда как-то притих в развитии в последние пару лет, но все же это (с Salabimом — название шутка про «Сим-салабим») относительно продуманные системы. Визуализации правда там слабые, но они нафиг и не нужны — их надо отдельно делать, в интеграции с игровыми движками (в блендер можно вставлять, там уже питон, на panda3d писать) или вот на вебе...


        1. Xneg Автор
          24.07.2022 10:49

          Да, спасибо. Посмотрел туторилс SimPy - я что-то очень похожее переизобрёл) Чучка не читатель, с другой стороны, если бы я знал о наличии такого фреймворка, то не было бы повода поупражняться самому.

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