Комментарии 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 — ещё компактнее.
А я ничего не говорил про общие алгоритмы сжатия. Я только указал на не худшую компактность кодирования.
Все три описанные схемы так или иначе используют механизмы, применённые в BER, когда ни одной из обсуждаемых схем и в планах не было. Нельзя говорить на эту тему без обсуждения ASN.1.
И конечно неплохо бы объяснить, а почему эти описываемые велосипеды вообще появились.
Есть мир за пределами Web'а. Или вы предлагаете заменить протоколы (GSM/3G/LTE) на HTTP? Интересно, как. (Это риторика, если что.)
А есть еще 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, а благодаря вторым — практически не знаем. Просто победили открытые технологии с доступными инструментами.
Поэтому когда мне нужно экспортировать диф в JSON я просто обегаю дерево и диф пишу напрямую в конвертер в виде нод. Первоначально в свой енкодер писал, потом в JSON.NET.
Простое решение сказать ньютоновскому JSON.NET-у что я хочу писать в BSON но там нету сжатия, а ещё имена полей это повторяющиеся строки, нафига они мне в файле нужны 1000 раз.
Не подскажите что почитать под такую задачу. То есть сериализация со сжатием, но не с объекта, а с возможностью писать в конвертер отдельные ноды.
С JSON'ом и .NET — это не ко мне.
когда мне нужно экспортировать диф в JSON я просто обегаю дерево
А почему бы просто не хранить журнал изменений? С каждым клиентом ассоциирован идентификатор (last-id) последней записи, которую он получил. Вот клиенту и передаём последовательность записей с id > last-id. (А никому не нужные старые записи спокойно выкидываем.)
И не надо для каждого клиента каждый раз обходить все узлы сцены (дерева, в вашем случае). Бонусом получаем масштабируемость: журналу всё равно, сто или миллион узлов на сцене.
Ну и сериализуем уже записи журнала.
во что-то бинарненькое со сжатием и исключением дублирующихся строк
Если эти строки есть имена узлов JSON, то может уйти в сторону бинарного метода сериализации со схемой? Если эти строки часть данных, то стоит посмотреть в сторону замены строк на атомы (если это редко меняемые строки).
Не подскажите что почитать под такую задачу. То есть сериализация со сжатием, но не с объекта, а с возможностью писать в конвертер отдельные ноды.
Вы хотите сложного от простого. Разделите абстракции передачи изменений и сериализации. И решайте их проблемы по отдельности. Примеры оптимизаций каждой из двух абстракций я показал (см. выделения текста).
Обходить при этом все ноды дерева не нужно, потому что в них хранится информация о текущей ревизии, и соответственно обход не заходит в ноды, которые не менялись в рамках текущей транзакции.
Разделить полную сериализацию и дифф да, думал как вариант. Жаль терять универсальность, но возможно это оптимальный вариант.
Если оно только ради отладки, то может и ничего вообще менять не нужно?
При аугментировании узлов сцены номером генерации (ревизии) каждое изменение будет требовать обновления номера генерации узла и для всех зависимостей узла. Для иерархических систем — это обновление всех родителей узла. Так что у нас логарифмическая зависимость числа записей от количества узлов сцены.
При генерации разности у нас опять логарифмическая сложность получается: нужно пройти всех родителей.
А что с удалением? Нужно как-то помечать удалённые узлы. Или его просто нет в вашем случае?
В случае с журналом зависимости обновлять/проходить не нужно (лучше масштабируется), проблем с удалением нет, узлы лучше абстрагированы: в них нет информации для реализации алгоритма подсчёта разности.
Но вот
можно у любой точки дерева спросить ExportChanges и увидеть человекочитаемый JSON что в модели поменялось
либо потребует обхода всего неприменённого журнала, либо добавления иерархической индексации.
В общем, если размер сцены не слишком велик, а её динамичность высокая, то, действительно, может и не имеет смысла ничего менять в этой части.
Разделить полную сериализацию и дифф да, думал как вариант. Жаль терять универсальность, но возможно это оптимальный вариант.
Ничего не мешает сравнивать всю сцену с пустотой, и вот, всю сцену можно передавать как обычную разницу.
А вот и не логарифмическая.
- Чтобы не было логарифма, у вас число изменившихся подузлов должно быть одного (или большего) порядка с длиной пути до корня.
- Даже если так, то амортизированное O(1), конечно, хорошо… если вам не нужен real-time.
плюс линейную от максимальной глубины дерева.
Что есть логарифм числа узлов, в общем случае. Если у вас дерево растёт только вширь, то тогда вопросов нет… кроме того, что для генерации разницы всей сцены нужно вширь то пройти, а это теперь O(n).
Чаще всего в реальных командах изменяется не всего по немножку, а много изменений в какой-то одной ноде, так что что проставление ревизии очень мало весит.
«Сколько вешать, в граммах?» Мало — это хорошо, это значит, что можно не думать об оптимизации пока. Что не отменяет того, что у вас там всё равно, скорее всего, O(log n) даже в амортизированном случае.
слабаки, да)
Ваш К.О.
Да, так и есть. Это проблема не JSON-а как такового, а JavaScript-а, который под капотом все числа представляет в виде 64-битных double. С другими языками все зависит от десериализатора. Большинство работают нормально и используют 64-битные целые без проблем. Но когда-то натыкался на какую-то либу, которая во имя "совместимости" на .NET тоже портила числа >= 2^53.
Кроме того, даже если (де-)сериализатор не подвержен проблеме 53 битов, есть вероятность, что он не умеет нормально работать с беззнаковыми 64 битными целыми. Потому что под капотом парсит все целые в знаковый 64-битный инт, не учитывая тип поля-назначения. И в обычно все работает. За исключением случаев когда поле назначения — беззнаковый 64-битный инт и значение превышает 2^63.
Текстовые и двоичные. Надо полагать, что текст хранится не в двоичном виде?
Зачем эта статья?
И где тег "Банальность"?
(ну или "КО")
В Avro появляются лишние заморочки при изменении и осутствии схемы. Protocol Buffers можно и без схем прочитать.
У Protobuf есть неслабое преимущество — для него существует GRPC.
Просто оставлю это здесь: https://msgpack.org/
Ну раз все всё поехали вспоминать форматы без схем, то нельзя не вспомнить CBOR, который между прочим RFC
Но вообще в принципе обсуждать форматы сериализации — это всё равно, что взвешивать коня в вакууме. Гораздо интереснее обсудить фреймворки, которые их используют. Apache thrift например — это rpc фреймворк если что, а не просто формат сериализации. protocol buffers — аналогично ни кому не нужен вне grpc
Я далек от высоконагруженных систем, и не понимаю этого. Разве не распространены сейчас протоколы сжатия на лету? Сколько байт будет занимать хоть сколь-нибудь значимый JSON в сжатом виде, будет ли выигрыш от двоичных форматов? Конечно, время сериализации важно, но о нём авторы совсем не упоминают…
FlatBuffers, например, использует Figma для своих данных.
какое-то неправильное сравнение.
бинарный protobuf логичнее сравнивать с текстовым csv, а текстовый json — с бинарным cbor.
Вы пишите: Например, в XML и CSV нельзя различать строки и числа.
Если у вас сервис SOAP с wsdl, там строгая типизация, и строки и числа и пр. прекрасно различимы.
Вижу, что материал для статьи взят из книги Мартина Клеппмана «Designing Data-Intensive Applications».
Я являюсь счастливым обладателем данной. Там в самом начале написано, что нельзя воспроизводить никакую часть этой книги без разрешения владельцев авторских прав.
То есть не стоило брать оттуда картинки и подобное.
Двоичное кодирование вместо JSON