Некоторое время назад я опубликовал свою статью о разработке велосипедного велосипеда, в которой описал причины, побудившие меня этим заняться.
Если вкратце, то мне была нужна миниатюрная библиотека для микроконтроллеров с сериализатором двоичных данных и последующей передачей этих сообщений по низко скоростным линиям связи, тогда как обычные форматы xml, json, bson, yaml, protobuf, Thrift, ASN.1 и др. мне по разным причинам не подходили.
Как и ожидалось, решение оказалось более чем велосипедом, и тем не менее, сама публикация статьи на Хабре мне очень сильно помогла. Дело в том, что при первоначальном анализе возможных библиотек, я почему то упустил из вида сериализаторы MessagePack, CBOR и UBJSON.
Ссылки на них мне написали в комменатриях уже после публикации статьи. И я сразу понял, что скорее всего CBOR, UBJSON легко решают стоящую передо мной задачу. Причем делают этого гораздо лучше, чем моя собственная разработка.
После этого я прикрутил к библиотеке CBOR свой интерфейс (чтобы не перелопачивать исходники), и … решил от этого формата отказаться в пользу MessagePack :-)
На самом деле CBOR и MessagePack форматы используют один и тот же принцип сериализации данных. В их основе лежит практичный метод записи TLV, за тем лишь исключением, что в классическом виде TLV всегда содержит поле тега и поле длины данных. А вот поле с самими данными может отсутствовать (если размер данных ноль).
А в этих сериализаторах разработчики пошли еще дальше, и сделали практически гениальные форматы, в которых наличие поля с размером данных зависит от типа данных, и не требуется для полей фиксированного размера, а в первом байте хранится одновременно и тип поля с размером данных и его непосредственное значение (конечно, если позволяет разрядность).
В исходной статье я писал про то, что мне требуется максимальная упаковка бинарных данных и оба эти формата справляются с такой задачей на ура. Они между собой очень похожи, и отличаются только количеством бит, в котором хранится значения типа поля.
В формате CBOR минимальные накладные расходы на хранение каждого поля составляет три бита, т.е. в первом байте каждого поля первые три бита отвечают за тип содержимого, и в зависимости от него интерпретируют наличие и размер других полей, а оставшиеся 5 бит могут содержать уже само значение поля.
А вот в MessagePack пошли еще дальше! В этом формате минимальные накладные расходы на хранение значения составляют всего 1 (ОДИН!) бит информации. Соответственно, для хранения дополнительной информации может использоваться уже 7 бит, а для указания дополнительной информации о типе поля используются значения с установленным старшим битом.
Понятно, что диапазон представления отрицательных значений при таком способе кодирования уменьшается за счет положительных чисел (в одном байте можно хранить только 32 отрицательных числа, а для остальных значений уже потребуется второй байт). Но это правильный дисбаланс и смещен он в нужную сторону, т.к. на практике положительные числа используются значительно чаще отрицательных.
Именно этот момент, а так же нормальная библиотека с реализацией формата на десятке разных языков и определили мой окончательный выбор в пользу формата MessagePack. Думаю, что я не единственный, кому могут быть интересны данные подробности реализации этих форматов, поэтому считаю правильным такой информацией поделиться.
В итоге, изначальный формат сериализатора удалось сделать еще компактнее, в том числе и за счет некоторых соглашений (например, структуру кодируемых данных ограничить только плоским списком и отказом от использования невостребованных типов), а мой сон стал спокойнее, т.к. уже не болит голова насчет совместимости на уровне форматов пересылаемых сообщений между устройствами.
Спецификация CBOR. Есть хорошая статья с описанием на Хабре.
Спецификация MessagePack очень легко читается в документации и не требует какого либо перевода или дополнительных пояснений.
Если вкратце, то мне была нужна миниатюрная библиотека для микроконтроллеров с сериализатором двоичных данных и последующей передачей этих сообщений по низко скоростным линиям связи, тогда как обычные форматы xml, json, bson, yaml, protobuf, Thrift, ASN.1 и др. мне по разным причинам не подходили.
Как и ожидалось, решение оказалось более чем велосипедом, и тем не менее, сама публикация статьи на Хабре мне очень сильно помогла. Дело в том, что при первоначальном анализе возможных библиотек, я почему то упустил из вида сериализаторы MessagePack, CBOR и UBJSON.
Ссылки на них мне написали в комменатриях уже после публикации статьи. И я сразу понял, что скорее всего CBOR, UBJSON легко решают стоящую передо мной задачу. Причем делают этого гораздо лучше, чем моя собственная разработка.
После этого я прикрутил к библиотеке CBOR свой интерфейс (чтобы не перелопачивать исходники), и … решил от этого формата отказаться в пользу MessagePack :-)
CBOR vs. MessagePack
На самом деле CBOR и MessagePack форматы используют один и тот же принцип сериализации данных. В их основе лежит практичный метод записи TLV, за тем лишь исключением, что в классическом виде TLV всегда содержит поле тега и поле длины данных. А вот поле с самими данными может отсутствовать (если размер данных ноль).
А в этих сериализаторах разработчики пошли еще дальше, и сделали практически гениальные форматы, в которых наличие поля с размером данных зависит от типа данных, и не требуется для полей фиксированного размера, а в первом байте хранится одновременно и тип поля с размером данных и его непосредственное значение (конечно, если позволяет разрядность).
В исходной статье я писал про то, что мне требуется максимальная упаковка бинарных данных и оба эти формата справляются с такой задачей на ура. Они между собой очень похожи, и отличаются только количеством бит, в котором хранится значения типа поля.
В формате CBOR минимальные накладные расходы на хранение каждого поля составляет три бита, т.е. в первом байте каждого поля первые три бита отвечают за тип содержимого, и в зависимости от него интерпретируют наличие и размер других полей, а оставшиеся 5 бит могут содержать уже само значение поля.
А вот в MessagePack пошли еще дальше! В этом формате минимальные накладные расходы на хранение значения составляют всего 1 (ОДИН!) бит информации. Соответственно, для хранения дополнительной информации может использоваться уже 7 бит, а для указания дополнительной информации о типе поля используются значения с установленным старшим битом.
Понятно, что диапазон представления отрицательных значений при таком способе кодирования уменьшается за счет положительных чисел (в одном байте можно хранить только 32 отрицательных числа, а для остальных значений уже потребуется второй байт). Но это правильный дисбаланс и смещен он в нужную сторону, т.к. на практике положительные числа используются значительно чаще отрицательных.
Другими словами, в одном байте в формате CBOR умещаются целочисленные значения от 0 до 23, а в формате MessagePack от 0 до 127!
Именно этот момент, а так же нормальная библиотека с реализацией формата на десятке разных языков и определили мой окончательный выбор в пользу формата MessagePack. Думаю, что я не единственный, кому могут быть интересны данные подробности реализации этих форматов, поэтому считаю правильным такой информацией поделиться.
В итоге, изначальный формат сериализатора удалось сделать еще компактнее, в том числе и за счет некоторых соглашений (например, структуру кодируемых данных ограничить только плоским списком и отказом от использования невостребованных типов), а мой сон стал спокойнее, т.к. уже не болит голова насчет совместимости на уровне форматов пересылаемых сообщений между устройствами.
Большое спасибо Хабра-юзерам Spym и edo1h, что ответили на предыдущую публикацию и тем самым помогли найти решение действительно серьезной проблемы такими малыми усилиями!
Первоисточники:
Спецификация CBOR. Есть хорошая статья с описанием на Хабре.
Спецификация MessagePack очень легко читается в документации и не требует какого либо перевода или дополнительных пояснений.
Spym
В исходных требованиях вы, кажется, не писали о том, что формат должен быть самоописывающим (self-describing). Во встраиваемых системах это применяется сравнительно редко. Мы решали схожую задачу в протоколе, ссылку на статью о котором я давал в комментарии к вашей прошлой публикации; если интересно, можете взглянуть здесь: https://uavcan.org/specification/UAVCAN_Specification_v1.0-beta.pdf#page=15 (раздел "data structure description language"). Удаление метаданных из сериализованного сообщения не только уменьшает избыточность (что важно в вашем случае, как я вижу из требований), но и уменьшает вариативность представлений (есть только один способ закодировать данные, в то время как в TLV формате можно, к примеру, поменять местами поля структуры, не затронув семантику сообщения; этот вопрос рассматривается в спецификациях ASN.1 тоже), что удешевляет тестирование в отказоустойчивых приложениях.
rsashka Автор
Да, вы совершено правы насчет передачи структуры в самом сообщении, чего например нет в формате protobuf. Мне действительно было важно иметь информацию именно о самых полях, а не сообщении в целом, хотя в явном виде это действительно нигде не отмечено.