Melange — DSL для сетевых протоколов

    Всем программистам рано или поздно приходится передавать данные. Ни для кого не секрет, что библиотек сериализации в Java существует примерно >9000, а в C++ они вроде и есть, а вроде их и нет. К счастью для большинства, несколько лет назад появился Google Protobuf, который принёс достаточно удобный способ определять структуры данных и быстро завоевал всенародную любовь. Это была фактически первая, доступная широким массам библиотека, позволяющая гонять по сети готовые структуры данных, не связываясь при этом с чем-то вроде XML. На дворе был 2008 год.

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

    Анил сразу пошёл дальше, чем Google. Он сразу подумал, для чего люди обычно пересылают по сети какие-то формализованные структуры данных? Чтобы реализовать какой-то протокол. А что такое протокол? Это какой-то конечный автомат. А где мы можем взять хороший пример сложного, хорошо спроектированного и проверенного временем протокола? Да прямо в обычном сетевом стеке! Итак, были взяты набор сетевых структур данных и протоколов: Ethernet frame, IPv4, ICMP, TCP, UDP, SSH, DNS и DHCP и постановка задачи: большая часть этих протоколов (особенно SSH и DNS) реализуются, что называется «руками», а хочется, чтобы не было типичных для C переполнений буфера, все переходы совершались автоматически, это всё можно было верифицировать, и чтобы работало быстро, а не как обычно.

    Поскольку никто не будет читать диссертацию, сразу скажу: это более чем удалось. По результатам работы были написаны референсные реализации DNS и SSH-сервера и произведено сравнение с BIND и OpenSSH. OCaml-реализации давали по сравнению с традиционными прирост производительности от незначительного, до почти двухкратного. Кроме того была найдена ошибка в RFC на SSH (рабочая группа была уведомлена и RFC исправлен). О том, что было сделано, и как с этим жить, читайте под катом.

    MPL

    Первым делом были написаны два языка описаний и их трансляторы на OCaml. Первый язык — это Meta Packet Language или MPL, описывающий структуру пакета. В общих чертах он является аналогом protobuf, но не совсем. Во-первых, MPL не добавляет никакого оверхеда к вашей структуре. Вообще. Никаких дополнительных битов, указывающих тип данных или ещё что-то. С одной стороны, это не позволяет, как в protobuf, легко расширять структуру, добавляя к ней новые поля, с другой — вы никогда не прочитаете с помощью protobuf TCP-заголовок. Во-вторых, MPL сразу реализует всю ту логику, которая бывает необходима в сетевых структурах — упаковку или выравнивания, а также такие вещи, как переменный набор полей или значения полей, зависящие от других полей структуры. Для примера посмотрите на заголовок IPv4:
    packet ipv4 {
        version: bit[4] const(4);
        ihl: bit[4] min(5) value(offset(options) / 4);
        tos_precedence: bit[3] variant {
            |0 => Routine |1 -> Priority
            |2 -> Immediate |3 -> Flash
            |4 -> Flash_override |5 -> ECP
            |6 -> Internetwork_control |7 -> Network_control
        };
        tos_delay: bit[1] variant {|0 => Normal |1 -> Low};
        tos_throughput: bit[1] variant {|0 => Normal |1 -> Low};
        tos_reliability: bit[1] variant {|0 => Normal |1 -> Low};
        tos_reserved: bit[2] const(0);
        length: uint16 value(offset(data));
        id: uint16;
        reserved: bit[1] const(0);
        dont_fragment: bit[1] default(0);
        can_fragment: bit[1] default(0);
        frag_offset: bit[13] default(0);
        ttl: byte;
        protocol: byte variant {|1->ICMP |2->IGMP |6->TCP |17->UDP};
        checksum: uint16 default(0);
        src: uint32;
        dest: uint32;
        options: byte[(ihl * 4) - offset(dest)] align(32);
        header_end: label;
        data: byte[length-(ihl*4)];
    }


    Здесь содержимое пакета описано как массив байтов data (чтобы не описывать все остальные возможные протоколы), но на его месте вполне могла бы быть запись:
    classify (protocol) { 
        |1: "ICMP"-> data: packet icmp(); 
        |2: "TCP" -> data: packet tcp(); 
        |3: "UDP" -> data: packet udp(); 
    }; 


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

    К сожалению, и у этого языка есть свои недостатки. Я насчитал их ровно два. Первый: запрещены рекурсивные пакеты. Это как раз стало причиной невозможности полной реализации MessagePack — MPL нельзя сказать, что в списке или мапе могут лежать списки или мапы, придётся описывать их просто как пачку байтов, а потом разбирать ещё одним вызовом десериализации. Это сделано специально, чтобы каждое чтение пакета было строго конечным, но нам от этого не легче. Вторая проблема: нельзя определять свои типы данных. Анил реализовал стандартные для сети типы, такие, как байты, биты, числа, строки или даже mpint, который присутствует в SSH, но этот список фиксирован. Если вы вдруг захотите реализовать протокол ssh-agent, который использует тип mpint1, вам остаётся только описывать его как массив байтов и разбирать у себя в коде. Единственный способ расширения списка поддерживаемых типов — это написание патчей к компилятору MPL, что является не самой тривиальной задачей.

    SPL

    Вторым языком стал Statecall Policy Language или SPL. Это язык описания конечных автоматов, то есть, сердце нашего протокола. Строго говоря, библиотек для создания конечных автоматов под все языки существует порядочно. Отличий у SPL от них (не считая своего языка описания вместо программного задания автомата) всего несколько. Во-первых, компилятор SPL умеет сразу генерировать описание на языке PROMELA для верификатора программных моделей SPIN. Буду честен, я не смог разобраться со SPIN, поэтому в этом месте был вынужден поверить автору на слово, что это круто. Во-вторых, используя имена состояний Receive_NAME и Transmit_NAME (где NAME — это тип сообщения из MPL), можно тесно интегрировать конечный автомат со структурами данных из MPL. Об этом мы поговорим позже, а пока что посмотрим на пример описания конечного автомата для авторизации в SSH:
    automaton
    auth (bool success, bool failed)
    {
        Receive_Transport_ServiceAccept_UserAuth;
        Transmit_Auth_Req_None;
        Receive_Auth_Failure;
        do {
            either {
                always_allow (Receive_Auth_Banner) {
                    either {
                        Transmit_Auth_Req_Password_Request;
                        auth_decision (success);
                    } or {
                        Transmit_Auth_Req_PublicKey_Request;
                        auth_decision (success);
                    } or {
                        Transmit_Auth_Req_PublicKey_Check;
                        either {
                            Receive_Auth_PublicKeyOK;
                        } or {
                            Receive_Auth_Failure;
                        }
                    }
                }
            } or {
                Notify_Auth_Permanent_Failure;
                failed = true;
            }
        } until (success || failed);
    }

    Как вы видите, конечный автомат в SPL позволяет писать довольно разветвлённую логику, вставлять вызов функций (auth_decision), написанных на том же SPL и даже работать с переменными.

    Как с этим работать?

    К сожалению, проект (весь целиком он называется Melange) не слишком богат на документацию, основным её источником является сама диссертация. Поэтому я решил написать небольшой Proof of concept, демонстрирующий работу всего продукта, а заодно являющийся небольшим таким Quick Start guide. Для этого надо написать какое-нибудь небольшое сетевое приложение. Для роли простого приложения с простым и понятным протоколом я выбрал старую добрую игру — морской бой. Вот так будет выглядеть наша структура сообщения:
    packet message { 
        message_type: byte; 
        message_id: uint16; 
        classify (message_type) { 
            | 0:"Shot" -> 
                row: bit[4]; 
                column: bit[4]; 
            | 1:"ShotResult" -> 
                result: byte variant { |0 -> Missed |1 -> Damaged |2 -> Killed }; 
            | 2:"Disconnect" -> (); 
        }; 
    } 

    У нас бывает три типа сообщения: выстрел, результат выстрела и информация о том, что мы по какой-то причине хотим отсоединиться. Теперь давайте взглянем на предполагаемый протокол:
    automaton seawar () { 
        Initialize; 
        during { 
            multiple(1..) { 
                Ready; 
                either { 
                    Transmit_Message_Shot; 
                    Receive_Message_ShotResult; 
                } or { 
                    Receive_Message_Shot; 
                    Transmit_Message_ShotResult; 
                } 
            } 
        } handle { 
            either { 
                Transmit_Message_Disconnect; 
                exit; 
            } or { 
                Receive_Message_Disconnect; 
                exit; 
            } 
        } 
    }

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

    Теперь посмотрим, как это используется из кода. Для чтения сообщений мы будем использовать специальный буфер MPL, который будет заполняться данными — в нашем случае мы их забираем из сети.
    val mutable env_ = Mpl_stdlib.new_env (String.make 4 '\000'); 
    val mutable tick_ = Protocol.init (); 
    method tick state = tick_ <- Protocol.tick tick_ state; 
    method send_message msg = ( 
        Mpl_stdlib.reset env_; 
        self#tick (msg#xmit_statecall :> Protocol.s); 
        if not (Thread.wait_timed_write sock_ 10.) then self#disconnect ~exc_text:"Timeout"; 
        Mpl_stdlib.flush env_ sock_ 
    ); 
    method receive_message = (  
        Mpl_stdlib.reset env_; 
        if not (Thread.wait_timed_read sock_ 300.) then self#disconnect ~exc_text:"Timeout"; 
        Mpl_stdlib.fill env_ sock_; 
        let msg = Message.unmarshal env_ in 
     
        let state = Message.recv_statecall msg in 
        self#tick state; 
        msg 
    ); 

    Обратите внимание, что каждое сообщение, как посылаемое, так и принимаемое, в обязательном порядке вызывает переход конечного автомата в новое состояние. За это отвечают вызовы msg#xmit_statecall и Message.recv_statecall msg, которые на основании сообщений (типа ShotResult) создают имена соответствующих состояний (Transmit_Message_ShotResult и Receive_Message_ShotResult). Благодаря этому, большая часть потенциальных ошибок программы будет выявляться именно здесь, когда неправильный переход автомата будет вызывать исключение Bad_statecall. Например, если в случае AI всё просто — он работает в один поток, совершенно синхронно и никаких проблем в такой простой задаче там никогда быть не может, то в графическом интерфейсе всё может быть сложнее.


    Например, простой пример, как всё легко может «взорваться». Для графического интерфейса я взял свежевышедший фреймворк Qt 5.2, для которого наш соотечественник Дмитрий Косарев написал биндинги к OCaml (достаточно интересные, если будут желающие, расскажу отдельным постом). При клике по клетке вражеского поля в отдельном треде может быть выполнен следующий код:
    let send_shot col row = 
      ignore(game#send_message (Message.Shot.t ~row:row ~column:col)); 
      let result, state = game#receive_message in 
      (match result with 
          | `ShotResult x -> Board.mark opp_board row col x#result; 
                  next_turn state x#result 
          | `Disconnect x -> game#disconnect ~send:false 
          | _ -> game#disconnect ~exc_text:"Unexpected_Message_Type" ~raise_exc:true ~send:true)

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

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

    Заключение

    Что дальше-то, спросит меня читатель. Ну, какой-то маргинальный, уже 4 года не обновлявшийся инструмент, работающий на непонятном языке. Зачем мне всё это, если у меня есть Node.js, MongoDB и клубничный смузи?

    Читатель прав. Инструмент устарел, у него есть несколько существенных недостатков, которые я упоминал. Но при этом он показывает, в каком направлении надо развиваться. Так, весь код приложения, включая все декларативные описания, графический интерфейс и не самый тупой AI, составляет 850 строк. Это конечно не «30 строк на javascript», но тоже не слишком много.

    Вот уже почти 8 лет назад было показано, как именно должно происходить сетевое взаимодействие и почти 6 лет назад Google популяризовала всего лишь его половину. Никакого рокетсайенса в идее нет, это правда, и по отдельности все компоненты давно написаны. У тебя, %USERNAME%, есть отличная возможность реализовать эту идею в наступающем Новом году, стать всемирно известным и поработить мир. Ну или что-то в этом роде.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 18

      0
      Извините, но причем тут Qt?
        +3
        От Qt конкретно в моём коде весь GUI. Я изначально планировал рассказать ещё и об этом (тем более, что биндингов к Qt на других языках крайне мало), но понял, что в одну статью никак не влезаю. Собственно, поэтому я в тексте написал, что если кому-то это было бы интересно, то я готов рассказать. Из хабов не стал исключать, потому что иначе шанс пересечения с Qt-аудиторией небольшой.
          0
          Понял. А я думал, что в Qt реализовали Melange.
            0
              +1
              Я просто пройдусь по списку:
              Perl — не обновлялся два года
              PySide — остановился на Qt4.8
              qtruby — не обновлялся два года
              KBasic — обновлялся в 2012, платный
              Ada2005 — умеет примерно половину библиотек от Qt4.7
              Lua — 8 месяцев не обновлялся
              QtD — 3 года не обновлялся
              и так далее.
              Из более-менее живых есть PyQt (самый используемый AFAIK), Qt Jambi (я если честно, думал, что он давно умер, ан нет), Qyoto, может быть ещё пара языков.
              Список на сайте выглядит внушительно, но реально, к сожалению, он небольшой. Gtk и тот поддерживает больше языков (причём даже официальных биндингов больше), в силу своего C и GIR. У Qt есть SMOKE, но он что-то не пользуется популярностью.
          +1
          Проекты растут, усложняются. Чтобы бороться со сложностью программы разбивают на независимые части. Сейчас вперед выходят языки не те которые помогают немногословно описывать задачи, а те которые помогают описывать задачи по частям.
            +2
            Мне кажется ваш комментарий опоздал лет на 30.
            +11
            ASN.1 вон вообще в 84 году сделали. Другой вопрос, что и protocol buffers и thrift и ASN.1 могут кодировать только сообщения в своём собственном формате. Произвольный формат пакета ты им не закодируешь. А тут просто DSL для написания бинарных кодеков. Сравнивать его с protobuf etc не совсем корректно.
              +2
              Как раз в ASN.1 формат отделен от схемы данных.
              Там есть отдельно Encoding Rules — хоть в битовый поток засунуть, хоть в XML.
              Сертификаты X.509 например кодируются в DER.

              ru.wikipedia.org/wiki/X.690

              Так что ничто не мешает кодировать ASN.1 данные даже в protobuf
                +1
                Мне кажется, что всё-таки корректно. Объясню, почему. Protobuf был введён, как более удобная и экономная замена XML в вопросах кодирования данных с известной структурой, кроме того был платформонезависим, позволяя прозрачно передавать данные от одного языка программирования и ОС — совершенно другому.
                В такой постановке вопроса, как мне кажется, не слишком важно, как он там кодирует данные внутри (наверное, кого-то расстраивало, что в protobuf нельзя сформировать UDP-пакет, но вряд ли много кого) и основными отличиями между MPL и Protobuf становятся такие вещи, как расширяемость или опциональные поля в Protobuf и более богатая внутренняя логика в MPL.
                ASN.1 и Thrift в этой связи сравнивать с MPL и Protobuf нельзя, потому что ASN.1 — это только описание общей структуры, а Thrift — это уже готовый инструмент для конкретных задач (кроме того, протокол у него внизу может быть разным, мы вполне можем прикрутить Melange как ещё одну реализацию протокола для Thrift).
                ASN.1 может стать кодированием с сочетании с BER/DER/XER, но ему как раз по-прежнему не хватает удобства — инструментов, валидаторов, каких бы то ни было плюсов, по сравнению с другими форматами. Фактически, единственное его достоинство — возраст. Он не имеет никаких достоинств по сравнению с другими форматами, и вот так в 2013 году выглядит инструменты для работы с ним. Если бы кто-нибудь когда-нибудь написал для ASN.1/DER что-нибудь, примерно похожее на protobuf и MPL, оно могло бы стать заменой, но я не вижу смысла ввиду отсутствия каких-то плюсов по сравнению с ними.
                  0
                  Начнем с того, что ASN.1 стандартизирован. Уже это делает его в определенных ситуациях единственным возможным выбором (а не просто является одним из преимуществ, в противовес вашим мечтам). Во-вторых, ASN.1 является великолепным способом описания интерфейса (именно интерфейса, а не какой-то там «общей структуры»; можно очень хорошо и четко конкретизировать и ограничить возможные значения). В некоторой степени, его сложность и количество возможностей, конечно, плохо повлияли на его распространенность (да просто всем западло кодить Unaligned PER энкодер-декодер для всего этого; а тем более генератор парсеров, как, в общем-то, и подобает нормальному инструменту). Поэтому и появились инструменты, вроде Thrift и ProtoBuffers: бывает, что весь имеющийся арсенал — это дичайший оверкилл. Но в тех областях, где он используется (в первую очередь, конечно, телефония и прочие телекомы, где уровень чуть или сильно ниже перегонки личных сообщений по хттп), он используется и замены ему нет. Собственно, единственный минус ASN.1: это малая распространенность.
                    0
                    Вот с малой распространенностью можно и поспорить.
                    Просто она очень не видна с точки зрения программиста.

                    Куча сетевых устройств используют.
                    Другой вопрос, что для программиста это оверкилл и ад.
                0
                Устарел, не устарел, но в Mirage, кадется, вполне себе используется…
                  0
                  Хen умирает (силами Цитрикса). Увы. Проприентарные корни без мощного комьюнити сильно его портят.
                    0
                    Хм, как-то после Xen Dev Summit каждый год у меня такого впечатления не складывается…
                      0
                      Я тоже долгое время так думал. К сожалению, между академической тусовкой и реальной жизнью у зена такие проблемы, на фоне которого игры в паравиртуализацию уже не заметны.

                      Во-первых цитрикс, который очень очень виндовый и которого вполне устраивает продажа vdi'ев. xen server для них уже давно имиджевый проект, для которого продажа саппорта — лишь галочка при разводе энтерпрайз-клиентов. При формальном опенсорсе xenserver совершенно не libre software, так как весь governance намертво в зубах у цитрикса, а фичи они пилят большей частью под нужды десктопа.

                      У xenserver'а ужасный код за пределами самого зена. Я несколько раз показывал этот код, покажу ещё раз:

                      github.com/xapi-project/sm/blob/6e37a85ef88b97c84c6177eccc652e3528bf9b59/tests/faultinjection/util.py

                      cmd = ["ls", path, "-1", "--color=never"]
                      try:
                          text = pread2(cmd).split('\n') 
                      


                      Такой индусный код у них всюду в sm'ах. А block devices — это святая святых виртуализации.

                      Далее, кто, кроме цитрикса там? Амазон. Много амазон своих наработок отдал? Я на 1000% уверен, что у них там свой тулстек и никому они его не отдадут. SUSE подпиливает, oracle ещё.

                      После того, как RH махнул рукой на зен, opensource'ной версии (production ready) де-факто не осталось.

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

                      Как все микроядерные штуки оно хорошо в теории и отвратительно на практике. Например, xenbus, при кажущейся красоте — омерзительный протокол с кучей рейсов, ведущий к тому, что на хостах с xen'ом до сих пор более одного домена в один момент времени стартовать не может. У цитрикса в коде даже есть отдельный хак с sleep'ом, чтобы домены не смели слишком часто рестартовать.

                      То, что у зена до сих пор референсным является 2.6.18-xen — ещё тот показатель. pv_ops при формально заявленной поддержке всего и вся — второсортное ядро для зена (кривое управление памятью, плавающие таймеры и т.д.), а это означает, что зен не с линуксом, а сам по себе (что очень согласуется с идеей «микроядро»).

                      И эта ситуация тянется годами. За это время kvm из поделки для гиков стал очень крутой штукой, основой для RH, самым массовым гипервизором для openstack'а, в то же самое время цитрикс валандается c VDI'ем.

                      То есть зен стремительно теряет все свои преимущества. kvm уже давно работает со скоростями, сравнимыми с xen'ом (по сетевой и дисковой производительности превосходя оный за счёт отсутствия идиотских лимитов ring buffer'ов), а «родной для линукса» много значит в контексте продакт-деплоя.
                • UFO just landed and posted this here
                    0
                    Спасибо. Это очень круто. И своевременно.

                    Only users with full accounts can post comments. Log in, please.