Двоичное‌ ‌кодирование‌ ‌вместо‌ ‌JSON

Автор оригинала: Shilpi Gupta
  • Перевод
Кодируйте‌ ‌одни‌ ‌и‌ ‌те‌ ‌же‌ ‌данные‌ ‌гораздо‌ ‌меньшим‌ ‌количеством‌ ‌байт.‌ ‌

image

Почему‌ ‌меня‌ ‌это‌ ‌должно‌ ‌волновать ‌


Данные‌ ‌хранятся‌ ‌в‌ ‌памяти‌ ‌в‌ ‌виде‌ ‌структур‌ ‌данных,‌ ‌таких‌ ‌как‌ ‌объекты,‌ ‌списки,‌ ‌массивы‌ ‌и‌ ‌т.д.‌ ‌Но‌ ‌если‌ ‌вы‌ ‌хотите‌ ‌отправить‌ ‌данные‌ ‌по‌ ‌сети‌ ‌или‌ ‌в‌ ‌файле,‌ ‌вам‌ ‌нужно‌ ‌закодировать‌ ‌их‌ ‌в‌ ‌виде‌ ‌последовательности‌ ‌байтов.‌ ‌Перевод‌ ‌из‌ ‌представления‌ ‌в‌ ‌памяти‌ ‌в‌ ‌последовательность‌ ‌байтов‌ ‌называется‌ ‌кодированием,‌ ‌а‌ ‌обратное‌ ‌преобразование‌ ‌–‌ ‌декодированием.‌ ‌Со‌ ‌временем‌ ‌схема‌ ‌данных,‌ ‌обрабатываемых‌ ‌приложением‌ ‌или‌ ‌хранящихся‌ ‌в‌ ‌памяти,‌ ‌может‌ ‌эволюционировать,‌ ‌туда‌ ‌могут‌ ‌добавляться‌ ‌новые‌ ‌поля‌ ‌или‌ ‌удаляться‌ ‌старые.‌ ‌Следовательно,‌ ‌используемая‌ ‌ кодировка‌ ‌должна‌ ‌иметь‌ ‌как‌ ‌обратную‌ ‌(новый‌ ‌код‌ ‌должен‌ ‌быть‌ ‌способен‌ ‌читать‌ ‌данные,‌ ‌написанные‌ ‌старым‌ ‌кодом),‌ ‌так‌ ‌и‌ ‌прямую‌ ‌(старый‌ ‌код‌ ‌должен‌ ‌быть‌ ‌способен‌ ‌читать‌ ‌данные,‌ ‌написанные‌ ‌новым‌ ‌кодом)‌ ‌совместимость.‌ ‌

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

Типы‌ ‌форматов‌ ‌кодирования‌


Существует‌ ‌два‌ ‌типа‌ ‌форматов‌ ‌кодирования:‌ ‌

  • Текстовые‌ ‌форматы‌ ‌
  • Двоичные‌ ‌форматы‌
‌ ‌

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


‌Текстовые форматы в некоторой степени человекочитаемы. Примеры распространенных форматов — JSON, CSV и XML. Текстовые форматы просты в использовании и понимании, но имеют определенные проблемы:

  • Текстовые форматы могут быть очень неоднозначны. Например, в XML и CSV нельзя различать строки и числа. JSON может различать строки и числа, но не может различать целые и вещественные числа, а также не задает точности. Это становится проблемой при работе с большими числами. Так, проблема с числами, большими чем 2^53 встречается в Twitter, который использует 64-битное число для идентификации каждого твита. JSON, возвращаемый API Twitter, включает в себя ID твита дважды — в виде JSON-числа и в виде десятичной строки – все из-за того, что JavaScript-приложения не всегда верно распознают числа.
  • CSV не имеет схемы данных, возлагая определение значения каждой строки и столбца на приложение.
  • Текстовые форматы занимают больше места, чем двоичная кодировка. Например, одна из причин заключается в том, что JSON и XML не имеют схемы, а потому они должны содержать имена полей.

{
    "userName": "Martin",
    "favoriteNumber": 1337,
    "interests": ["daydreaming", "hacking"]
}

JSON-кодировка этого примера после удаления всех символов пробела занимает 82 байта.

Двоичное кодирование


Для анализа данных, которые используются только внутри организации, вы можете выбрать более компактный или более быстрый формат. Несмотря на то, что JSON менее многословен, чем XML, оба они все равно занимают много места по сравнению с двоичными форматами. В этой статье мы обсудим три различных бинарных формата кодирования:

  1. Thrift
  2. Protocol Buffers
  3. Avro

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

Thrift и Protocol Buffers


Thrift разработан Facebook, а Protocol Buffers – Google. В обоих случаях для кодирования данных требуется схема. В Thrift схема определяется с помощью собственного языка определения интерфейса (IDL).

struct Person {
  1: string       userName,
  2: optional i64 favouriteNumber,
  3: list<string> interests
}

Эквивалентная схема для Protocol Buffers:

message Person {
    required string user_name        = 1;
    optional int64  favourite_number = 2;
    repeated string interests        = 3;
}

Как видите, у каждого поля имеется тип данных и номер тега (1, 2 и 3). У Thrift есть два различных формата двоичной кодировки: BinaryProtocol и CompactProtocol. Двоичный формат прост, как показано ниже, и занимает 59 байт для кодирования данных, приведенных выше.

image

Кодирование с использованием двоичного протокола Thrift

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

image

Кодирование с использованием протокола Thrift Compact

Protocol Buffers кодирует данные аналогично компактному протоколу в Thrift, и после кодирования эти же данные занимают 33 байта.

image

Кодирование с использованием Protocol Buffers

Номера тегов обеспечивают эволюцию схем в Thrift и Protocol Buffers. Если старый код попытается прочитать данные, записанные с новой схемой, он просто проигнорирует поля с новыми номерами тегов. Аналогично, новый код может прочитать данные, записанные по старой схеме, пометив значения как null для пропущенных номеров тегов.

Avro


Avro отличается от Protocol Buffers и Thrift. Avro также использует схему для определения данных. Схему можно определить, используя IDL Avro (человекочитаемый формат):

record Person {
    string               userName;
    union { null, long } favouriteNumber;
    array<string>        interests;
}

Или JSON (более машиночитаемый формат):

"type": "record",
    "name": "Person",
    "fields": [
        {"name": "userName",        "type": "string"},
        {"name": "favouriteNumber", "type": ["null", "long"]},
        {"name": "interests",       "type": {"type": "array",      "items": "string"}}
    ]
}

Обратите внимание, что у полей нет номеров меток. Те же самые данные, закодированные с помощью Avro, занимают всего 32 байта.

image

Кодирование с помощью Avro.

Как видно из вышеприведенной последовательности байт, поля не могут быть идентифицированы (в Thrift и Protocol Buffers для этого используются метки с номерами), также невозможно определить тип данных поля. Значения просто собираются воедино. Означает ли это, что любое изменение схемы при декодировании будет генерировать некорректные данные? Ключевая идея Avro заключается в том, что схема для записи и чтения не обязательно должна быть одинаковой, но должна быть совместимой. Когда данные декодируются, библиотека Avro решает эту проблему, просматривая обе схемы и транслируя данные из схемы записывающего устройства в схему читающего устройства.

image

Устранение различий между схемой читающего и записывающего устройства

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

  1. При передаче больших файлов или данных, записывающее устройство может однократно включить схему в начало файла.
  2. В БД с индивидуальными записями каждая строка может быть записана со своей схемой. Самое простое решение – указывать номер версии в начале каждой записи и сохранять список схем.
  3. Для отправки записи в сети, читающее и записывающее устройства могут согласовать схему при установке соединения.

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

Заключение


В этой статье мы рассмотрели текстовые и двоичные форматы кодирования, обсудили как одни и те же данные могут занимать 82 байта с кодировкой JSON, 33 байта с кодировкой Thrift и Protocol Buffers, и всего 32 байта с помощью кодировки Avro. Двоичные форматы предлагают несколько неоспоримых преимуществ по сравнению с JSON при передаче данных в сети между внутренними службами.

Ресурсы


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

image

Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя платные онлайн-курсы SkillFactory:



Читать еще


SkillFactory
Онлайн-школа по программированию

Комментарии 37

    0

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

      +1

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


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


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

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

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


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


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

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

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

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

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

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


              Первая проблема 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, а благодаря вторым — практически не знаем. Просто победили открытые технологии с доступными инструментами.

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

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

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


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

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


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


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


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

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


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

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

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

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


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


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


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


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


                    Но вот


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

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


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


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

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

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

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

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

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


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

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

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

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


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

                +1

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

                  +5

                  Зачем эта статья?
                  И где тег "Банальность"?
                  (ну или "КО")

                    +1

                    Это просто реклама.

                    0

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

                      +2

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

                        +2
                        Ещё есть bson bsonspec.org. С приличным списком имплементаций.
                          +4

                          Просто оставлю это здесь: https://msgpack.org/

                            0

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

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

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

                                        0

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


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

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

                                              можно deflate поверх прикрутить

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

                                          Самое читаемое