Pull to refresh

Comments 41

В .NET есть как текстовый, так и бинарный XML, он поддерживается DataContractSerializer.

Совсем не раскрыта тема ASN.1 и бинарных схем кодирования BER (и канонические её формы DER и CER), OER, упакованных бинарных PER и UPER (плюс канонические формы CPER и CUPER). (Про XER и JER не говорим, как противоречащие обсуждаемому домену.) Уж что, что, а ASN.1 пропустить в таком сравнении просто непростительно.


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


P.S. Предполагаю, что DER будет часто не хуже любого из описанных в статье, а PER будет компактнее, UPER — ещё компактнее.

Судя по всему здесь принципиально не затронута тема сжатия. Тот же deflate дал бы неплохие результаты в соотношении текстовые/бинарные данные.

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


Все три описанные схемы так или иначе используют механизмы, применённые в BER, когда ни одной из обсуждаемых схем и в планах не было. Нельзя говорить на эту тему без обсуждения ASN.1.


И конечно неплохо бы объяснить, а почему эти описываемые велосипеды вообще появились.

А если использовать http для передачи, то сжатие будет по умолчанию и выгодней будет использовать текстовые данные)

Есть мир за пределами Web'а. Или вы предлагаете заменить протоколы (GSM/3G/LTE) на HTTP? Интересно, как. (Это риторика, если что.)

http я указал исключительно в контексте данной статьи. Стремление все упрощать заставляет выбирать протоколы более высокого уровня, что очевидно влечет за собой геометрический рост оверхеда. А при работе с gsm, лично у меня, никогда не возникало делеммы — человеко-читабельный формат выбирать или гнать сырые данные. Аналогичная риторика)
ASN.1 конечно масштабный протокол. Со всеми его вариациями. Просто зачастую он слишком избыточен и переусложнён для более «домашнего» применения. Понятно, что в пром. использовании (криптография, телеком) — это стандарт.

А есть еще BSON (binary JSON), как и бинарный XML. Есть Fast Infoset — разновидность сжатого XML с нотацией ASN.1

Ну дак вот это вот и должно быть раскрыто в подобного вида статьях.


Первая проблема ASN.1 — излишне перегруженный синтаксис — можно было бы проще. Потом теоретиков понесло совсем не туда с довольно сложным заданием ограничений (constrains). А потом и вовсе не туда: XML-форма записи ASN.1.


И это всё при том, что ASN.1 (как и SQL) создавался для обычных смертных (не только для программистов) — предполагалось, что пользователи будут описывать схему для хранения информации.


При этом, если взять базовую часть синтаксиса ASN.1 (основную) и ограничиться только простыми ограничениями (размер и границы), то ASN.1 весьма прост:


$ wc -l asn1-lexer.l asn1-parser.y se.h asn1-se.h asn1-se.c
  111 asn1-lexer.l
  176 asn1-parser.y
   26 se.h
   73 asn1-se.h
  347 asn1-se.c
  733 total
$ 

— Вон, парсер на flex + bison меньше 300 строчек (se — это реализация специфических конструкторов, можно проще реализовать). Парсер BER/DER не сложнее описанных в статье протоколов:


$ wc -l asn1-input.[ch] ber-input.[ch]
 134 asn1-input.c
  18 asn1-input.h
  95 ber-input.c
  26 ber-input.h
 273 total
$ 

Генерация кода по AST от первого для разбора BER/DER с помощью второго — также достаточно проста. Так что вполне себе ASN.1 подходит для «домашнего» применения.


Понятно, что в пром. использовании (криптография, телеком) — это стандарт.

Вот практически только благодаря первым мы и знаем об ASN.1, а благодаря вторым — практически не знаем. Просто победили открытые технологии с доступными инструментами.

О! У вас есть знание темы на память! У меня есть к вам вопрос. ВОт у меня тоже появилась проблема сериализации данных во что-то бинарненькое со сжатием и исключением дублирующихся строк. Но у меня у задачки есть особенность. Я сериализую diff, изменение в дельтаобже, и мне не хочется этот диф перед сериализацией превращать в какую-то промежуточную форму, которую потом надо было бы сериализовать. Например потому что диф первоначальной инициализации это просто клон геймстейта и места в памяти он занимает дофига, а главное непонятно зачем, но при этом большинство дифов это 5-10 нод.
Поэтому когда мне нужно экспортировать диф в JSON я просто обегаю дерево и диф пишу напрямую в конвертер в виде нод. Первоначально в свой енкодер писал, потом в JSON.NET.
Простое решение сказать ньютоновскому JSON.NET-у что я хочу писать в BSON но там нету сжатия, а ещё имена полей это повторяющиеся строки, нафига они мне в файле нужны 1000 раз.

Не подскажите что почитать под такую задачу. То есть сериализация со сжатием, но не с объекта, а с возможностью писать в конвертер отдельные ноды.

С JSON'ом и .NET — это не ко мне.


когда мне нужно экспортировать диф в JSON я просто обегаю дерево

А почему бы просто не хранить журнал изменений? С каждым клиентом ассоциирован идентификатор (last-id) последней записи, которую он получил. Вот клиенту и передаём последовательность записей с id > last-id. (А никому не нужные старые записи спокойно выкидываем.)


И не надо для каждого клиента каждый раз обходить все узлы сцены (дерева, в вашем случае). Бонусом получаем масштабируемость: журналу всё равно, сто или миллион узлов на сцене.


Ну и сериализуем уже записи журнала.


во что-то бинарненькое со сжатием и исключением дублирующихся строк

Если эти строки есть имена узлов JSON, то может уйти в сторону бинарного метода сериализации со схемой? Если эти строки часть данных, то стоит посмотреть в сторону замены строк на атомы (если это редко меняемые строки).


Не подскажите что почитать под такую задачу. То есть сериализация со сжатием, но не с объекта, а с возможностью писать в конвертер отдельные ноды.

Вы хотите сложного от простого. Разделите абстракции передачи изменений и сериализации. И решайте их проблемы по отдельности. Примеры оптимизаций каждой из двух абстракций я показал (см. выделения текста).

Мысль понял. Отдельный журнал хранить мне не вариант потому что практически самая главная плюшка моей модели — что можно у любой точки дерева спросить ExportChanges и увидеть человекочитаемый JSON что в модели поменялось. Кратно ускоряет отладку.
Обходить при этом все ноды дерева не нужно, потому что в них хранится информация о текущей ревизии, и соответственно обход не заходит в ноды, которые не менялись в рамках текущей транзакции.
Разделить полную сериализацию и дифф да, думал как вариант. Жаль терять универсальность, но возможно это оптимальный вариант.

Если оно только ради отладки, то может и ничего вообще менять не нужно?


При аугментировании узлов сцены номером генерации (ревизии) каждое изменение будет требовать обновления номера генерации узла и для всех зависимостей узла. Для иерархических систем — это обновление всех родителей узла. Так что у нас логарифмическая зависимость числа записей от количества узлов сцены.


При генерации разности у нас опять логарифмическая сложность получается: нужно пройти всех родителей.


А что с удалением? Нужно как-то помечать удалённые узлы. Или его просто нет в вашем случае?


В случае с журналом зависимости обновлять/проходить не нужно (лучше масштабируется), проблем с удалением нет, узлы лучше абстрагированы: в них нет информации для реализации алгоритма подсчёта разности.


Но вот


можно у любой точки дерева спросить ExportChanges и увидеть человекочитаемый JSON что в модели поменялось

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


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


Разделить полную сериализацию и дифф да, думал как вариант. Жаль терять универсальность, но возможно это оптимальный вариант.

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

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

  1. Чтобы не было логарифма, у вас число изменившихся подузлов должно быть одного (или большего) порядка с длиной пути до корня.
  2. Даже если так, то амортизированное O(1), конечно, хорошо… если вам не нужен real-time.

плюс линейную от максимальной глубины дерева.

Что есть логарифм числа узлов, в общем случае. Если у вас дерево растёт только вширь, то тогда вопросов нет… кроме того, что для генерации разницы всей сцены нужно вширь то пройти, а это теперь O(n).


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

«Сколько вешать, в граммах?» Мало — это хорошо, это значит, что можно не думать об оптимизации пока. Что не отменяет того, что у вас там всё равно, скорее всего, O(log n) даже в амортизированном случае.

… проблема с числами, большими чем 253…
слабаки, да)
2 в 53-й степени. Там еще «перлы» рядышком — «белые пробелы». Автор, видимо, не особо заморачивался вычиткой гуглотранслейта.
Ваш К.О.
Тёмная тема в IDE решает проблему белых пробелов, а мне зато стало любопытно, почему всего 53 в случае 64-битных чисел. Я предположил, что это мантисса от double, это кажется правдоподобным.

Да, так и есть. Это проблема не JSON-а как такового, а JavaScript-а, который под капотом все числа представляет в виде 64-битных double. С другими языками все зависит от десериализатора. Большинство работают нормально и используют 64-битные целые без проблем. Но когда-то натыкался на какую-то либу, которая во имя "совместимости" на .NET тоже портила числа >= 2^53.


Кроме того, даже если (де-)сериализатор не подвержен проблеме 53 битов, есть вероятность, что он не умеет нормально работать с беззнаковыми 64 битными целыми. Потому что под капотом парсит все целые в знаковый 64-битный инт, не учитывая тип поля-назначения. И в обычно все работает. За исключением случаев когда поле назначения — беззнаковый 64-битный инт и значение превышает 2^63.

Текстовые и двоичные. Надо полагать, что текст хранится не в двоичном виде?

В Avro появляются лишние заморочки при изменении и осутствии схемы. Protocol Buffers можно и без схем прочитать.

У Protobuf есть неслабое преимущество — для него существует GRPC.

Ну раз все всё поехали вспоминать форматы без схем, то нельзя не вспомнить CBOR, который между прочим RFC

Самый быстрый из компактных форматов сериализации — FlatBuffers
image
Но вообще в принципе обсуждать форматы сериализации — это всё равно, что взвешивать коня в вакууме. Гораздо интереснее обсудить фреймворки, которые их используют. Apache thrift например — это rpc фреймворк если что, а не просто формат сериализации. protocol buffers — аналогично ни кому не нужен вне grpc
Apache Arrow тогда ещё надо вспомнить (и Parquet иже с ним)
Есть куча сверхбыстрых бинарных кодеков: Cap'n Proto, SBE.
Message Pack же, и не будет проблем. В частности мы его используем в самописном RPC
Автор акцентирует внимание на том, что двоичные форматы занимают меньше места при передаче между сервисами.
Я далек от высоконагруженных систем, и не понимаю этого. Разве не распространены сейчас протоколы сжатия на лету? Сколько байт будет занимать хоть сколь-нибудь значимый JSON в сжатом виде, будет ли выигрыш от двоичных форматов? Конечно, время сериализации важно, но о нём авторы совсем не упоминают…
Оптимизация на спичках. За которую нужно заплатить тысячами человеко-часов.

FlatBuffers, например, использует Figma для своих данных.

какое-то неправильное сравнение.


бинарный protobuf логичнее сравнивать с текстовым csv, а текстовый json — с бинарным cbor.

Эхх… Вот если бы он ещё умел исключать повторяющиеся строки, заменяя их на какой-нибудь код, чтобы сжимать названия полей — было бы вообще идеально.

Вы пишите: Например, в XML и CSV нельзя различать строки и числа.


Если у вас сервис SOAP с wsdl, там строгая типизация, и строки и числа и пр. прекрасно различимы.

Как-то я пытался использовать BSON для обмена между двумя программами, но вовремя вспомнил что 80% данных — строки. Применил JSON, сжатый библиотекой zlib.

Вижу, что материал для статьи взят из книги Мартина Клеппмана «Designing Data-Intensive Applications».
Я являюсь счастливым обладателем данной. Там в самом начале написано, что нельзя воспроизводить никакую часть этой книги без разрешения владельцев авторских прав.
То есть не стоило брать оттуда картинки и подобное.

Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
Location
Россия
Website
www.skillfactory.ru
Employees
201–500 employees
Registered
Representative
Skillfactory School