10 октября 2011 в 20:33

Universal Binary JSON — ещё один бинарный JSON из песочницы

Статья является вольным переводом информации предоставленной на официальном сайте.

Введение


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

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

Для достижения лучших результатов в таких случаях становится полезным использование двоичного формата JSON.

Почему?


Попытки сделать использование JSON более скоростным, быстрым с помощью двоичных спецификаций, таких, как BSON, BJSON или Smile, существуют, но они терпят неудачу по двум причинам:

  1. Внутренние типы данных. Использование внутренних типов данных, исключительно присущих только двоичным форматам и изначально не включённых в стандарт JSON, делает непригодными для широкого использования вышеуказанные спецификации, так как, в зависимости от реализации, каждый такой тип может интерпретироваться по разному.
  2. Сложность реализации. Одни форматы позволяют добиться более высокой производительности, а другие — более компактного представления за счёт более сложной, запутанной спецификации. Что, в свою очередь, замедляет или делает невозможных их распространение и внедрение. Простота использования — двигатель успеха JSON.

Например, BSON определяет типы данных для регулярных выражений, блоков JavaScript кода и других конструкций, у которых нет соответственного типа данных в JSON. BJSON тоже определяет свои типы данных, оставляя широкие возможности для ошибок, связанных с интерпретацией типов в двух разных реализациях. Smile определяет более сложные типы данных, правила генерирования и разбора, чтобы эффективно использовать место.

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

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

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

Почему не JSON+gzip?


Сжатие JSON может быть лучшим решением, чем использование двоичных форматов. Но тут есть две проблемы:

  1. На 50% падает скорость работы с данными.
  2. Нет возможности исследовать данные и работать с ними напрямую.

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

Цели


Universal Binary JSON спецификация спроектирована исключительно на принципах полной совместимости с JSON, простоты, скорости работы и доступности для понимания. Чтение и запись в данном формате носят тривиальный характер. Как побочный эффект — уменьшение пространства, занимаемого данными, в среднем на 30%.

  1. Полная совместимость. 100% совместимость с JSON и исключительное использование типов данных, поддерживаемых всеми современными языками программирования. Это позволяет эффективно преобразовывать данные между JSON и Universal Binary JSON без использования разработчиками замысловатых структур данных, которые могут и не поддерживаться языком программирования.
  2. Простота использования. Достигается за счёт того, что за основу взята спецификация JSON и используется всего лишь одна двоичная структура для рационального описания типов. Благодаря этому получаем доступность и простоту понимания разработчиками.
  3. Скорость и эффективность. Мотивация использования двоичных форматов заключается в скорости и эффективности разбора данных. При этом, как побочный эффект, снижение потребления пространства на 30%.

Формат данных


Общий вид единственной структуры байтов в спецификации, используемой для описания всех поддерживаемых типов

[type, 1-byte char]([length, 1 or 4-byte integer])([data])

  • type — 1 байт, символ из ASCII. Используется для указания типа данных, что следуют за ним.
  • length (опционально) — 1 или 4 байта (целое значение) в зависимости от длины или размера объекта. Для массива — его длина. Для объекта — количество пар Ключ/Значение. Если длина или количество элементов от 0 и до 254 включительно, то используется 1 байт. Это поле со значением 255 зарезервировано для объектов и массивов неизвестной длины.
  • data (опционально) — последовательность байтов, непосредственно представляющая собой данные объекта.

Поля length и data используются или не используются в зависимости от типа данных. Например, тип 32 разрядное целое имеет стандартный размер в 4 байта. Для записи значения этого типа понадобится 1 байт под указание типа и 4 байта под само значение. В данном случае поле length не используется по причине ненадобности.

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

Возможности


Спецификацией Universal Binary JSON поддерживаются:
  • основные типы данных
  • массивы
  • объекты
  • целые числа, массивы и объекты неизвестной длины или размера
  • потоковая передача данных

Важные особенности: значения числовых типов записываются в порядке байтов от старшего к младшему (Big-Endian) и основная кодировка текстовой информации — UTF-8.

Сообщество



Реализации на других языках программирования будут доступны по мере появления по этой ссылке.

P.S.: Автор спецификации и реализации на Java, Riyad Kalla и я, автор статьи и реализации на C#, будем рады любому вашему участию в процессе работы над спецификацией.
@M1xA
карма
2,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (48)

  • –1
    Комментируем! Создал «первый коммент», чтоб можно было комментить, пока Хабру не починят :) Подробности: habrahabr.ru/qa/12275/
  • +1
    Еще есть MessagePack.
  • +1
    Почему BE, а не LE?
    • 0
      собственно говоря тоже задался таким вопросом. Ведь в мире большинство компьютеров с процессорами основанной на intel архитектуре(x86), где по умолчанию LE. А так получается еще и накладные расходы на преобразование из BE в LE
    • +6
      Network byte order. По стандарту IP протокола.
      • +1
        Да, но почему? Ведь при использовании LE значительно упрощается работа по разбору формата. Смотрите сами:

        const void *lenPtr = ...;
        uint32_t len = *((uint32_t*)lenPtr); // for 4-byte length
        len &= 0xFFFFFF; // for 3-byte length
        uint16_t len = *((uint16_t*)lenPtr); // for 2-byte length
        uint8_t len = *((uint8_t*)lenPtr); // for 1-byte length
        
        • +1
          Зато для строк, целых в BE и флоатов совпадает функция сортировки… хотя хз зачем это тут.
        • 0
          На тему BE vs LE есть хороший текст Danny Cohen`а.
  • +2
    Мда, т.е. они переизобрели TLV и определили теги. Эко достижение!

    С другой стороны, не велосипед (почти) :)

    Буду присматриваться, может и попользуюсь.
  • 0
    Думаю было бы полезно написать про кодирование знака для целых типов, из описания формата это не очевидно, а код отправляет к документации Явы, в которой это тоже не просто ищется.
  • 0
    Немного не понятно на счет 100% совместимости, может быть хотя бы несколько реальных примеров?
    Как будет выглядить в этом формате такое:
    {
    "fruits":["apple", "orange"],
    "sport":[{"football" : {"players" : 11, "goalkeeper" : true}, "hockey" : {"players" : 6, "goalkeeper" : true} }]
    "note" : null
    }

    За счет чего прирост производительности по сравнению с gzip+json, тут разве не нужно преобразовывать обратно для работы как на сервере, так и на клиенте?
    • +1
      запитулю пропустил перед «note»
    • 0
      1: Однозначное соответствие.
      2: В случае gzip, как раз в не использовании этой связки. Проще использовать чистый json. Да и в зависимости от целей.
  • +5
    > [type, 1-byte char]([length, 1 or 4-byte integer])([data])

    на будущее: в nix-like системах принят формат выражений <> — поле, [] — необязательное, т.е. строка должна выглядеть
    <type, 1-byte char>[<length, 1 or 4-byte integer>][<data>]
    я лично долго над ней втуплял. более того, я так понимаю, на деле оно имеет формат
    <type, 1-byte char>[<length, 1 or 4-byte integer>[<data>]]
    • 0
      Не только в nix-like. Большая часть информации преведана «как есть», т.е. была в оригинале. Но, в любом случае, есть пояснения.
      • 0
        Это тонкий намёк, что если вы это тоже заметили, то вам проще связаться с авторами на эту тему :)
        • +1
          Конкретно по этой строке не было необходимости, не возникало как-то вопросов.
    • –1
      Вот это <type, 1-byte char>[<length, 1 or 4-byte integer>][] верный вариант.
      • –1
        Парсер выше съел поле data.
  • +5
    Я пол года назад сравнивал разные бинарные альтернативы JSON, включая MessagePack, Protocol Buffers и свой вариант преобразования JSON в TLV один-к-одному (аналогичный описываемому Вами Universal Binary JSON) — пытался избежать написания своего велосипеда быстрого парсера JSON на C для OS Inferno. Задача была получить максимальную скорость десериализации сложной структуры — чтение файла и создание структуры в памяти. И я был готов пожертвовать читабельностью и стандартностью JSON в пользу любого бинарного формата если бы это дало заметный выигрыш в скорости на наших данных. При этом я учитывал скорость всего процесса десериализации в целом (т.е. если, к примеру, бинарный формат занимал на X% меньше места, то это означало выигрыш в скорости на считывании файла, что тоже учитывалось). Так вот, в результате множества экспериментов и бенчмарков выяснилась любопытная вещь:
    1. бинарные форматы не дают заметного выигрыша, такого, из-за которого стоило бы жертвовать простотой и наглядностью текстового JSON;
    2. производительность десериализации упирается не в скорость парсинга скобочек и кавычек JSON, а в тормоза на большом количестве malloc()-ов, вызываемых для выделения в памяти динамических структур данных (по крайней мере при оптимизированной реализации парсинга на C, на других языках может тормозить сам парсинг).
    Поэтому в результате пришлось оставить надежды значительно ускорить десериализацию перейдя с JSON на какой-нибудь бинарный формат, и таки реализовать парсер для JSON.

    P.S. Впрочем, я всё-таки немного выкрутился и выиграл заметно в производительности реализовав не парсер, а токенайзер — поскольку мне нужно было грузить в память далеко не все поля/данные из десериализуемых структур, то я избежал полноценного разбора и вызовов malloc()-ов для ненужных данных возвращая пользователю отдельные токены по мере разбора и предоставив пользователю возможность управлять дальнейшим разбором (напр. пропуская ненужные ключи/значения объектов).
    • +3
      Кстати, если надумаете сравнивать по скорости свой Universal Binary JSON с другими форматами включая сам JSON — не забудьте сравнить с Perl-модулем JSON::XS — я лично даже не подозревал, насколько он быстрый, пока не сравнил его с MessagePack, Protocol Buffers и своими ранними и ещё не оптимизированными версиями парсера JSON на C.

      Вот цифры из моих тестов, на наших структурах данных (в данном случае все тесты были на perl, использовались модули Data::MessagePack, JSON::XS, и не помню что для ProtoBuf):
      Формат      Кол-во байт на одну     Кол-во десериализуемых
                  структуру данных        структур в 1 секунду
                  (меньше - лучше)        (больше - лучше)
      ProtoBuf    219                     32051/s
      MsgPack     303                     50505/s
      JSON        343                     52356/s
      

      Рекомендую использовать вот такую команду:
      $ time perl -MJSON::XS -ne 'push @a, decode_json($_)' file.json
      Дело в том, что, как я уже упоминал, основное время уходит на выделение (и освобождение) памяти. Использование push в этом примере приводит к тому, что десериализуемые данные будут накапливаться в памяти, и будут удалены из памяти в момент выхода скрипта — т.е. фактически экономия на вызовах free(). Этот мелкий нюанс даёт разницу в 15% при обработке 8MB файла с 35000 json-структурами.
      • 0
        Есть над чем поработать с памятью. Если заранее маллочить весь объём, а потом его тупо раздавать из своего буфера — должно получиться сильно быстрее. Preallocate не просто так придумали.
        • +1
          После десериализации структура данных отдаётся пользователю, и он с ней должен иметь возможность свободно работать. Т.е. в частности удалять из неё элементы, а значит освобождать память. И делать он это будет ничего не зная о том, что библиотека десериализации дооптимизировалась до того, что освобождать память надо не стандартными методами, а через её собственные malloc()/free(). Такое даже на голом C делать чревато. А моя реализация хоть и написана на C, но структуру данных подготавливает для использования из языка Limbo, в котором прямого доступа к памяти нет, и, соответственно, при всём желании невозможно обеспечить вызов нестандартной free() для элементов этой структуры данных.

          Хотя, если совсем честно, я немного лукавлю — как раз в Inferno/Limbo это в принципе вообще-то возможно реализовать. Но, в любом случае, это потребует своей собственной реализации malloc(), free() а заодно и (не уверен, но это не исключено, надо подумать) сборщика мусора. В общем, это в любом случае выходит за все рамки и по факту полный неадекват поставленной задаче.
      • 0
        С тестами дела, как всегда, интереснее. Желательно знать конфигурацию аппаратной и программной частей, и саму структуру. С очень оптимизированнным кодом относительно стабильным результатом было ~6200 нс/оп или 161290 оп/с на С# и .NET 4.5 без каких либо манимпуляций с аппаратной частью. Структура бралась с jvm тестов. И всёравно возникали вопросы. Обычное количество операций для тестов бралось в 1000000.
        • +1
          Зачем Вам конфигурации? Просто сравните скорость обработки на одной и той же тестовой машине. Что касается структуры — сделайте штук 5 максимально разных структур и прогоните тесты по всем.

          Конкретно у нас структура была следующая: объект с 13-ю ключами, значения 12-ти это числа/строки (в основном строки, длиной в среднем 15-20 символов), 13-е значение — массив из 2-3 строк, общий размер одной структуры (в одну строку без опциональных пробельных символов) примерно 330 байт.
          • 0
            Если уж тестировать, то нужно проверить как будут многократно вложенные массивы и объекты работать работать, как будет работать 1000 свойств внутри одного объекта и т.д. Но важнее всего — кейсы реальных случаев, т.к. сторонники сознательно или подсознательно придумывают тесты, дающие красивые результаты, а противники придумают тесты с плохими результатами. На себе убедился.
          • 0
            Для более подрбной информации об условиях и относительной адекватности в результате.
            То, что бралось для предварительных тестов, можно найти здесь.
    • +1
      Абсолютно согласен с мнением powerman. Я неоднократно пытался ужать и ускорить XML, YAML и свои форматы сериализации, еще с 1999 года начиная, и давно уже забросил попытки оптимизации с помощью бинарных структур. JSON же имеет гораздо меньшую избыточность кодирования, чем XML и тут уже выиграть пару процентов сложно: вместо кавычек или скобочек (2 символа на строку любых размеров) будем хранить 1-4 байта длины, и еще нужно хранить типы, на строках выигрыш слишком мал, чтобы так напрягаться. На хранении чисел экономится больше, согласен, но часто ли у нас используются все разряды в 32-битном или 64-битном числе, точность обычно ограничивается 2 знаками после запятой, так что, например 3.14 (4 байта), а в бинарном виде при 32-битном float это займет 5 байт. При всем этом, нет читабильности формата и накладные расходы на обработку.

      Если есть желание что-то соптимизировать, то уж лучше заняться такими направлениями:
      — Одни и те же данные в JSON можно смоделировать многими способами, и прикладные программисты редко лишают себя соблазна лишний раз обвернуть в массив или объект. Т.е. нужно заниматься оптимизацией самих сруктур данных, а не их представления.
      — Для ускорения парсинга можно ввести в JSON свои правила, например приняв конвенции о именовании свойств можно потом не парсить весь пакет/файл/буфер, а найти значение нужного свойства двумя операциями поиска подстроки в строке.
      — В некоторых случаях можно отказаться от null, false, true, а использовать например -1, 0, 1. Это конечно не универсально, но когда вопрос доходит до оптимизации миллионов однотипных записей, то и это прощается.
      — Если не лезть в ПО, а оптимизировать только формат, то можно ввести пре- и пост- обработку реплейсами самых часто повторяющихся фрагментов.
      — Про минификацию (компактный вид) не буду подробно.
      — Введя в протоколе или формате данных договоренности о значениях по умолчанию, часто можно опустить большую часть поле. Потому, что помните, что говорит нам теория информации и кодирования: самый лучший способ передать сообщение, принятое по-умолчанию (наиболее вероятное), это не передавать вообще ничего.
      • +1
        С чего это всё началось, насколько мне известно, есть вот ссылка. Предыстория всего мне не известна.
        Лично для себя использование UBJSON было хорошим решением для внутреннего проекта. То, что бинарный формат, не смущало. В HEX виде всё довольно прилично смотрится.
        Частные случаи мне известны. Они обычно очень специфические и узконаправленные. Тут надо смотреть и разбираться индивидуально.
        Основные цели: соответствие JSON, совместимость, ускорение работы с данными на уровне спецификации. Ускорее на разных платформах, естественно будет зависить от реализации и «своих» доработках.
        • 0
          Чтобы ускорить работу нужно передавать по сети прямо ту же самую структуру памяти, которая получается при парсинге, т.е. дерево. А тут бинарным форматом пробуют решить две противоположные задачи: минимизацию размеров пакета/файла и скорость развертывания при получении. Так это ясно, что увеличение размера пакета/файла, могут существенно увеличить скорость развертывания, а вот уменьшение размера без вариантов приводит только к замедлению. В чем лежит JSON в памяти — в дереве, у кого в каком, это может быть простое двух-связное дерево (где каждый элемент имеет две ссылки: Parent, FirstChild). Если мы будем работать с 5-связным деревом (Parent, FirstChild, LastChild, NextSibling, PreviousSibling), то избыточность немного больше, а скорость работы заметно выше. При передаче нам нужно просто провести маршалинг. При развертывании маршализированного объекта в другом адресном пространстве нужно провести всего лишь сдвиг адресов. Накладных расходов не так много, 2-5 адресов на каждый узел (8-20 байт на узел) при 32-битной адресации. Но все это — решение только для низкоуровневых языков, где можно памятью манипулировать, а вот для высокоуровневых это может быть только встроено в язык, а этого мы вряд ли дождемся.
          • 0
            Уменьшение размера данных — побочный положительный эффект.
            Непосредственное манипулирование памятью довольно опасная штука.
            Задачи, платформы, языки могут иметь разнообразнейшее внутреннее представление подобных внешне вещей. При обмене данными между системами одной платформы освещаемые вопросы обычно не стоят.
            • 0
              Но хочется увидеть результаты сравнительных тестов все же при разных вариантах применения, ну и кейсы какие-то увидеть, например, где без бинарного формата было невозможно что-то сделать или параметры работы системы были значительно хуже. Примеры пакетов в документации, по большей части надуманные, но задача то вышла из реальных проектов, не просто ж так руки зачесались написать. Вот про реальные проекты услышать хочется. Все это нужно по большей части в очень специфических задачах и при больших объемах данных, но типичное решение для этих случаев: вообще избавиться от имен параметров и передавать только значения, ведь имена заранее известны. Кроме того, для больших объемы данных почти всегда характерны повторяющиеся структуры, поэтому логично было бы отдельно описать структуру и имена свойств и потом передавать только данные без имен и даже типов, а длину указывать только для полей с переменной длиной. Это в два раза уменьшает объемы данных, если задача специфическая, то так и делают, но я не исключаю, что есть класс задач, где нужен именно бинарный JSON и с удовольствием бы почитал «истории успеха».
              • 0
                Тут какое дело. Спецификация находится в статусе активной разработки. Всем, у кого есть время и желание поучаствовать, будем только рады.
  • 0
    Для разработки реализаций на других языках было бы здоро иметь набор тестов (а не один тест со сложной структурой как в Java реализации). Пара JSON/UBJSON хорошо подойдёт.

    Мои первые наброски для Node.js: github.com/Sannis/node-ubjson
    • 0
      Напишите, как можно подробнее, о своей реализации, возникших вопросах или пожеланиях Riyad Kalla по одному из его контактов. Любая информация будет полезной.
      Набор тестов, насколько мне известно, в разработке.
      • 0
        Обязательно.
  • +1
    А чем плохи существующие стандарты? Ддя BSON, например, есть имплементация для десятка языков.

    Standards
    • 0
      В разделе «Почему?» описаны основные поводы. Картинка хорошая. В данном случае есть вполне определённые цели.
      Если результаты кому-то пригодятся, будем только рады. А там и реализации появятся ;)
  • +1
    При сильно повторяющихся данных можно паковать, приняв соглашения о последовательности полей (то есть, преобразовать Object в Array, убрав ключи).

    А если, например, нужно передавать массив id-шников, которые последовательные, то можно их отсортировать и потом заменять на разницу:

    было 7000, 7001, 7004, 7010
    стало 7000, 1, 3, 6

    А при распаковке суммировать.
    • +1
      Можно даже не убрать ключи совсем, а задать их один раз (если нужно, то для полей можно даже метаданные один раз задать в заголовке: тип поля, маска/шаблон/регексп, допустимые значения, что угодно, но один раз), например:
      {"Table":{
      "Header":["Id","Time","EventTypeId","ParameterId","UnitId","Multiplier","Value"],
      "Data":[
      [871,"08:12:04",57,12,3,7,120750049],
      [872,"08:12:07",22,79,2,10,288386016],
      ...
      [1325,"10:17:21",13,10,3,10,290537253]
      ]}}

      Для больших объемов данных как раз характерны таблицы, поэтому выносить структуру в шапку — гораздо эффективнее, чем жать в бинарный вид, а можно еще поверх и бинарным форматом.
      • 0
        О круто! Спасибо за идею, добавлю в свой проект =)
        • 0
          Не столько круто, как очевидно, в XML этого вообще невозможно сделать, там массивов нет, а любой тег — именованное значение, я для этих целей 10 лет свои форматы выдумывал один другого лучше, оптимизированные для разных специфических случаев, но с распространением JSON, переступил через свою гордыню и отказался от всех этих изысканий, ведь «Не следует множить сущее без необходимости» Бритва Оккама.
          • 0
            Да я тоже не заморачиваюсь, но просто реально много повторяющихся данных сейчас нужно хранить в js-файле, и я даже такими простыми методами ужал с 1.4 Мб до 200 Кб. +gzip и клиенты со слабым инетом уже могут без последствий быстро пользоваться сайтом =)
            • 0
              Ну тогда еще Вам рекомендую ввести значения по умолчанию, или даже подстановку значений в значения по умолчанию через выбранный символ-маркер, например "%", чтобы сэкономить на повторяющихся частях строки, может пригодится техника (для чисел не так актуально, но для строк полезно), например:
              {«Table»:{
              «Header»:[«Id»,«Date»,«Category»,«City»,«Source»,«Link»],
              «Default»:["%",«2011-10-%»,«Politics»,«Kiev»,«Interfax-Ukraine»,«www.interfax.com.ua/rus%»],
              «Data»:[
              [1,«29»,"","","","/pol/83814/"],
              [2,«29»,"","","","/eco/83943/"],
              [3,«30»,"",«UNIAN»,«www.unian.net/ukr/news/news-465271.html»],
              [4,«30»,"","","","/eco/83914/"],
              [5,«30»,"","","","/eco/83842/"]
              ]}}
              Ну идея понятна, а дальше уже можно от ситуации или просто пустую строку "" значением по умолчанию или подставлять значения из записей в значения по умолчанию или наоборот — подставлять значения по умолчанию в саму запись заменяя маркер или с регулярными выражениями выдумать более сложный способ для специфического случая.
        • +1
          Если необходимо хранить по сути табличные данные, то проще CSV использовать. Если данные фиксированных длины или типа, то можно и разделитель не использовать.
          • 0
            Или даже паковать всё в биты, если нужно запоминать только да или нет coding.smashingmagazine.com/2011/10/19/optimizing-long-lists-of-yesno-values-with-javascript/

            JSON он быстрее в браузер импортируется, потому что для CSV нужна дополнительная операция вида explode (split).
            • 0
              Да, если значения только «да, нет» («вкл, выкл»), то обычно происходит упаковка в флаги, т.е. как по ссылке выше. Это стандартная практика.
              Упаковка нескольких значений в тип достачного размера, тоже очень полезная вещь.

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

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