Здравствуйте, меня зовут Дмитрий Карловский и я.. да не важно кто я. Важно о чём я говорю, и как аргументирую.

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

PiterJS #84

Это — текстовая расшифровка одноимённого доклада с PiterJS #84. Можете глянуть видео запись тут в конце:

Или читать далее...

Serialization

Для сохранения и передачи объектов, требуется их сериализация. Она бывает двух видов:

? Stringification — текстовая сериализация

? Binarization — бинарная сериализация

Текстовые форматы

Стрингификация упаковывает данные в текстовую строку.

✅ Можно читать глазами.

❌ Бинарные данные не прочитать.

❌ Много весит.

✅ Хорошо жмётся.

❌ Медленная обработка.

❌ Требует ещё и бинаризации.

Однако строку всё равно надо перегонять в последовательность байт, а значит эффективнее было бы сразу бинаризировать.

Бинарные форматы

❌ Нужны спец тулы.

❌ Сложная отладка.

✅ Быстрая обработка.

✅ Может быть компактен.

Нужна ли схема?

Можно выделить следующие виды форматов бинаризации:

? Schema-Full

? Schema-Less

? Schema-Inside

? Shape-Inside

Schema-Full

Эти форматы предполагают существование схемы данных у нас в коде, благодаря которой мы понимаем какие байты что означают, не тратя байты на мета-информацию.

✅ Не тратим байты на типы.

✅ Прекомпилируем обработку.

❌ Схему надо откуда-то брать.

❌ Изменение схемы - боль.

Известные форматы:

Proto Buffers

Flat Buffers

Schema-Less

Эти форматы позволяют сериализовывать произвольные структуры и потом восстанавливать их благодаря поставляемой вместе с ними мета-информации. Схема в коде тут не требуется, но может быть использована для валидации данных.

❌ Тратим байты на типы.

❌ Обобщённый код медленный.

✅ Обобщённый код компактный.

✅ Кодирует любые данные.

Известные форматы:

MsgPack

CBOR

BSON

BSON гвоздями прибит к MongoDB, так что его далее не рассматриваем.

Schema-Inside

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

❌ Тратим байты на имена и типы...

✅ ... но один раз.

❌ Обобщённый код медленный...

✅ ... но его можно кешировать.

✅ Обобщённый код компактный.

✅ Кодирует любые данные.

Таких форматов мне не известно, но частный случай этого подхода — поставлять вместе с денными не всю схему с типами полей, а только шейпы — имена полей.

Shape-Inside

MsgPack + расширение

CBOR + расширения

VaryPack — наш герой

Проектируем

Сперва нам надо определиться с тем, какие типы данных должны поддерживаться нативно в нашем формате.

? Базовые примитивы.

? Структурные типы.

Базовые примитивы

? Логические значения (null, undefined, false, true) — 1B.

? Натуральные числа — 1B, 2B, 4B, 8B, ...

? Целые числа — 1B, 2B, 4B, 8B, ...

? Вещественные числа — 2B, 4B, 8B, ...

? Строки — UTF-8.

? Бинарники — массивы чисел одного типа.

Структурные типы

? Ссылки на любые значения.

? Списки любых элементов.

? Списки именованных элементов.

? Кастомные типы.

Первый байт

Если очень постараться, то все перечисленные типы можно упихнуть в 8 групп, а значит первый байт мы можем разделить на 3 бита для тега типа и оставшиеся 5 для некоторого числа, смысл которого зависит от типа.

Но 5 бит для числа может не хватить, поэтому резервируем несколько старших значений для кодирования числа байт в которых будет далее записано число.

Тип+число

Таким образом мы получили базовый кирпичик: tnum — типизированное число от 1 до 9 байт.

Порядок байт

Байты числа можно записывать в разном порядке:

? Big-Endian

? Little-Endian

Big-Endian

Последовательность от старших байт к младшим более распространена среди форматом, но менее среди процессоров.

? Сетевые протоколы: TCP, IP, ...

? Криптография: SHA, ...

? Картинки: PNG, JPG, ...

? CBOR, MsgPack, ...

✅ Сортировка как строк...

❌ ... но лишь при равных размерах.

❌ Современные процессоры.

Little-Endian

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

? Шины данных: USB, PCI, ...

? VaryPack, ...

✅ Современные процессоры.

✅ Большие числа совместимы с малыми.

Натуральные числа

Натуральное число — это просто tnum с типом 000, благодаря чему небольшие значения представляются в одном байте нативно, что позволяет легко читать их в любом hex-вьювере.

⭕ VaryPack: от 0 до 27 — как есть.

✅ MsgPack: от 0 до 127 — как есть.

⭕ CBOR: от 0 до 23 — как есть.

У MsgPack диапазон существенно шире, но это не бесплатно — другие типы требуют больше байт.

Целые числа

Благодаря типу 111 небольшие отрицательные числа тоже представляются в одном байте нативно. Особое значение -32 оставляем для обозначения больших целых чисел, длина которых кодируется дополнительными 2 байтами вначале. Кажется 64КБ для таких чисел должно хватить для любых разумных потребностей.

✅ VaryPack: от -1 до -27 — как есть.

✅ MsgPack: от -1 до -31 — как есть.

❌ CBOR: Тег 001. 8B+ — через расширение

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

Специальные типы

Для загончика с особыми значениями выделим тип 010, особенностью которого является соответствие ему в таблице ASCII кодов заглавных латинских букв. Это позволяет подобрать такие значения первого байта, чтобы hex-вьювер показывал первую букву названия соответствующего специального значения.

Как видно, пока что из спец значений есть лишь логические значения и вещественные числа разных размеров. Остальные зарезервированы на будущее.

✅ VaryPack: ASCII коды первых букв.

⭕ MsgPack: аналогично, но без букв.

⭕ CBOR: аналогично, но без букв.

Бинарники

Для типизированных массивов чисел tnum будет задавать длину бинарника в байтах. А перед самими данными добавим ещё один байт для кодирования типа.

✅ VaryPack: массивы чисел разных типоразмеров.

❌ MsgPack: дикий запад.

⭕ CBOR: расширение Typed Arrays.

Строки

Со строками всё просто — tnum представляет длину строки в символах. И далее идёт UTF-8 представление, ставшее наиболее популярным, благодаря компактности и совместимости с ASCII.

✅ VaryPack: 0xA0..0xBF — первый байт. Длина в символах.

❌ MsgPack: 0xC0..0xDF — первый байт. Длина в байтах.

❌ CBOR: 0x40..0x5F — первый байт. Длина в байтах.

Обратите внимание на выбор кода 101 для этого типа — он даёт значения первого байта начинающиеся на A и B в HEX представлении, что позволяет быстро понимать при отладке, когда перед нами строки.

Длина в байтах

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

❌ Не известна до бинаризации.

❌ А значит длина длины тоже.

✅ Можно декодировать лениво.

❌ Кратно растёт от числа символов.

Длина в символах

Длина в символах же обычно известна заранее, так как в памяти строки обычно хранятся в двухбайтовой кодировке. Это позволяет быстро сериализовывать, однако при парсинге уже не получится делать декодирование utf-8 лениво.

✅ Известна заранее ибо UCS2.

❌ Декодер должен уметь считать символы.

❌ Декодировать приходится сразу.

✅ Растёт монотонно.

Ссылки

Для ссылок tnum хранит номер уже обработанного значения. При сериализации уже ранее сериализованного значения вставляется лишь ссылка на него. А при парсинге встреченная ссылка распаковывается в соответствующее ранее прочитанное значение.

✅ VaryPack: номера уже обработанных значений.

❌ MsgPack: дикий запад.

⭕ CBOR: расширение value-sharing.

Списки

Списки сеариализуются наивно: число элементов, после которого идут сами элементы подряд.

Неопределённая длина

CBOR поддерживает списки (и строки) неопределённой длины. Аргументируется это возможностью потоковой обработки. Однако, в случае обрыва соединения, нельзя будет продолжить обработку — её придётся начинать с начала.

✅ Можно бинаризировать не имея всех данных.

❌ Повтор с начала при обрыве передачи.

Определённая длина

Для потоковой обработки предпочтительнее не поддерживать неопределённые длины списков, а делать каждый чанк полноценным независимым пакетом, обработка которого не полагается на контекст, сформированный предыдущими пакетами в потоке.

? Разбиваем на независимые пакеты.

✅ Не шлём доставленные пакеты дважды.

Кортежи

Наконец, самое интересное — списки именованных элементов. Тут перед первым элементом добавляется шейп (список имён), который при повторениях заменяется на ссылку, давая весьма компактное бинарное представление.

✅ VaryPack: кортеж именованных элементов

❌ MsgPack: дикий запад.

⭕ CBOR: расширение Records.

Объекты и Словари

В виде кортежей как раз и сериализуются любые объекты. Обратите внимание, что словари с произвольным набором ключей, кодируются так же как и объект из двух полей: список ключей и список значений.

✅ VaryPack:

⚽ Объект: ( shape, vals... )

? Словарь: ( [ "keys", "vals" ], keys, vals )

❌ CBOR: только словари, как списки пар.

❌ MsgPack: только словари, как списки пар.

Кастомные типы

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

? Структурная типизация

? Номинативная типизация

Структурная типизация

При обеднении значения (lean) перед бинаризацией поля объекта образуют кортеж. А при обогащении (rich) по шейпу этого кортежа выбирается функция, создающая тип предметной области.

Vary.type({
	type: Coord,
	keys: [ 'x', 'y' ],
	lean: obj => [ obj.x, obj.y ],
	rich: ([ x, y ])=> new Coord( x, y ),
})

Обратите внимание, что тут можно полноценно работать с координатами даже не имея специальной поддержки типа Coord ибо его представление полностью совместимо с обобщённым объектом с полями "x" и "y".

Номинативная типизация

Частный случай структурной типизации — номинативная, где кортеж содержит лишь одно обеднённое значение, именем которого является глобально уникальное название формата представления.

Vary.type({
	type: Moment,
	keys: [ 'ISO8601' ],
	lean: obj => [ obj.toString( 'YYYY-MM-DD' ) ],
	rich: ([ str ])=> Moment.parse( str ),
})

Теги

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

В MsgPack для тега есть лишь диапазон в 256 значений, что даёт высокий риск конфликтов.

❌ MsgPack: дикий запад в 1 байте.

⭕ Типично: +2B

T ; 127 ; [ 123, 456 ]

В случае CBOR ситуация получше — тут и диапазон значений большой (ценой дополнительных байт), и глобальный реестр стандартных расширений. Однако, типам конкретно вашей предметной области нечего делать в общем реестре, а выделенный для кастомных тегов диапазон требует от 5 дополнительных байт.

⭕ CBOR: 1..8B + реестр тегов.

❌ Типично: +5B

T+100500 ; [ 123, 456 ]

Для сравнения, наш подход требует от 1B для ссылки на шейп, а риск совпадения шейпов при этом куда ниже риска совпадения тегов.

Итоговое сравнение

Размеры

Как видно, даже со включёнными спец расширениями, CBOR и MsgPack дают существенно большие бинарники.

А зипование?

⭕ Нивелирует разницу.

❌ Замедляет в несколько раз.

При зиповании размер в большей степени зависит от энтропии исходных данных, а не формата бинаризации. А вот замедление из-за сжатия/разжатия приемлемо далеко не всегда.

Скорость

Референсная реализация VaryPack не сильно уступает самым оптимизированным реализациям CBOR и MsgPack.

Расширения

Разные библиотеки предоставляют разный набор расширенных типов в комплекте.

Одно из пенальти по производительности — обеспечение изоляции кастомных типов. В $mol_vary не возможна ситуация, когда подключаешь библиотеку, которая регистрирует поддержку своих типов, и она вдруг появляется и у тебя, заменяя твою реализацию.

Открытые вопросы

❓ Циклические структуры.

❓ Схемы вместо шейпов.

Поддержка циклов потребовала бы при обработке их детектировать на прикладном уровне, что сложно и багоёмко. А кодирование схем снижает гибкость, не уменьшая бинарник, а наоборот увеличивая его.

Выводы

✅ Существенно компактней даже без расширений.

✅ Проще и гибче альтернатив.

⭕ Достаточно быстро, но можно лучше.

Послесловие

Спецификация формата и референсная реализация на NPM:

Спека VaryPack

mol_vary

Этот формат мы используем в нашей децентрализованной Гипер Базе, на базе которой мы делаем экосистему веб-сервисов нового поколения — Гипер Веб:

Giper Baza

giper_web

Подключайтесь к нашему сообществу Гипер Дев, а также заглядывайте на мою страничку почитать ещё чего интересного:

giper_dev

jin.hyoo.ru

---

Актуальный оригинал на $hyoo_page.