CBOR — новый бинарный формат представления данных

Concise Binary Object Representation (сжатое бинарное представление объекта) — формат данных, который был спроектирован таким образом, чтобы обеспечить максимально простой код реализации, формирования компактных выходных данных и возможность расширения формата без необходимости обмена информацией о версии.

Стандарт формата CBOR был официально анонсирован комитетом IETF в октябре 2013 года в новом документе RFC 7049, авторами которого являются Carsten Bormann и Paul Hoffman. Взглянув на имя первого автора, можно предположить другую причину происхождения аббревиатуры для названия формата, но возможно это просто совпадение. Формат CBOR получил MIME-тип application/cbor.

На данный момент существует, вероятно, сотни всевозможных бинарных форматов для представления структурированных данных, ряд которых стандартизирован, популярен и широко применяется (например, BER и DER для ASN.1, MessagePack и BSON). Все существующие стандарты решают поставленные перед ними задачи, и CBOR здесь не исключение. К формату было предъявлено семь важных требований, и, поскольку ни один из существующих форматов в полной мере не мог им удовлетворить, был создан новый (да, тут напрашивается картинка ).



Требования к новому бинарному формату



  1. Недвусмысленное кодирование большинства популярных в Интернете стандартов типов данных.
    Формат должен уметь кодировать базовые типы данных и структур, используя бинарное представление. При этом нет требования к уникальному кодированию для абсолютно всех типов данных, например число 7 можно представить и как строку, и как целое.
  2. Компактная реализация для кодировщика/декодировщика, которая позволяла бы создавать реализации, не требовательные к возможностям процессора и доступному объёму памяти.
    Формат должен использовать привычные машинные реализации форматов (например, для целых чисел или чисел с плавающей запятой — IEEE 754)
  3. Отсутствие схемы описания.
    Также, как JSON-формат самоописывает представленные данные (объект, массив, строка и т.д.). Отсутствие схемы описания позволяет создать простой и универсальный декодировщик.
  4. Сереализация данных должна быть как можно более компактной, но не в ущерб простоте написания (де)кодировщика.
    За верхнюю планку объёма закодированных данных принимается объём представления в JSON-формате.
  5. Формат должен быть одинаково применим как в приложениях на ограниченных ресурсах, так и в приложениях работающих с огромными объёмами данных.
    Здесь подразумевается, что реализация должна быть одинакова бережлива к CPU при кодировании и декодировании данных.
  6. Формат должен поддерживать все существующие типы в JSON для конвертирования данных из и в JSON.
  7. Формат должен быть расширяемым и расширенный формат должен успешно декодироваться ранними версиями декодировщика.
    Предполагается, что формат будет использоваться десятилетиями и при этом сохранять обратную совместимость, таким образом, чтобы будущие версии стандарта формата могли нормально обрабатываться декодировщиком для ранних версий. Чтобы в случае обнаружения неизвестного расширения, всё равно иметь возможность раскодировать сообщение.


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

Спецификация CBOR



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

Каждый элемент данных начинается с байта, который содержит описание основного типа (major type) данных и дополнительной информации (additional info). Основной тип занимает 3 старших бита и может иметь значения от 0 до 7. Дополнительная информация может получать значения от 0 до 31.



Как видно на иллюстрации, в значении дополнительной информации выделено три условных диапазона:

  1. Если значение от 0 до 23, то данное значение используется непосредственно как целое число. Например, если основной тип — это целое число, то значение дополнительной информации — это и есть значение элемента. Если основной тип — это строка, то данное число указывает на длину строки.
  2. Если значение от 24 до 27, то последующие байты содержат целое число переменной длины, соответственно 1-, 2-, 4- и 8-байтные неотрицательные целые. Например, если основной тип это целое число, то в последующих байтах содержится его значение, а если строка — то её длина.
  3. Значение 31 является специальным и указывает на то, что длина элемента не определена. Например, в случае строки, это означает, что длина строки неизвестна.


Значения 28-30 зарезервированы для будущих версий стандарта.

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

Тип 0: неотрицательное целое


Дополнительная информация содержит значения числа (если оно меньше 24), в других случаях дополнительная информация указывает на размер целого числа, которое последует далее. Если 24 — то это uint8_t, 25 — uint16_t, 26 — uint32_t и 27 — uint64_t.

Например, число 16 кодируется в 0x10, а число 500 в последовательность из трёх байт 0x19, 0x01f4 (500)

Тип 1: отрицательное целое


Значение кодируется по аналогии с типом 0, с тем лишь отличием, что из абсолютного значения вычитается единица. Например, -16 кодируется в 0x2F, а число -500 — 0x39, 0x01f3 (499)

Тип 2: байтовая строка


Для байтовой строки дополнительная информация кодирует длину строки в байтах. Например, в случае байтовой строки длиной в 16 байт будет закодировано в 0x50 (тип 2, значение 16) с последующими 16 байтами, содержащие байтовую строку. А для строки длиной в 500 байт — трёхбайтный заголовок: 0x59 (тип 2, значение 25), 0x01f4 (500), с последующими 500 байтами данных строки.

Тип 3: текстовая строка


Текстовая строка представляет собой строку, состоящую из Unicode-символов в кодировке UTF-8. Также, как и в случае байтовой строки, дополнительная информация кодирует длину строки в байтах. В отличие от формата JSON, в текстовой строке не требуется выполнять экранирование символов переноса стоки, в виде \n или \u000a и т.п.

Тип 4: массив элементов


По аналогии с типом строки, дополнительная информация указывает на длину массива, но не в байтах, а в количестве элементов. Элементы в массиве необязательно должны быть одинакового типа, это могут быть набор строк, чисел и т.д. После заголовка, непосредственно следуют элементы массива. Например, массив [0,"A"] кодируется так:

82 - массив из 2-х элементов,
  00 - целое число 0,
  61 - текстовая строка в 1 байт,
    41 - "A"


Тип 5: карта пар (ассоциативный массив, хэш, словарь, JSON-объект...)


Данный тип определяет карту, состоящую из пар «ключ» — «значение». Дополнительная информация определяет количество таких пар. Например, карта из 9 пар кодируется как 0xa9 (тип 5 + значение 9), после чего следует 9 пар элементов: первый ключ, первое значение, второй ключ и т.д. Ключи могут быть разных типов, но как правило, такое редко бывает востребованно.

Тип 6: семантическое тегирование других базовых типов


Данный тип открывает широкие возможности по расширению стандарта. Дополнительная информация задаёт целочисленный номер тега, что задаёт диапазон тегов от 0 до 18446744073709551615. Тег ссылается на какое-то определённое представление базовых типов, позволяя безгранично расширять поддерживаемые типы данных.

Например, стандартом определенно, что тег 0 задаёт текстовую строку даты-времени в формате, описанном в RFC 3339 (с поправками из RFC 4287). К примеру, при кодирования времени 1970-01-01T00:00Z получим:

С0 - элемент с тегом 0
  71 - текстовая строка длиной 17 байт
    31 39 37 30 2d 30 31 2d  30 31 54 30 30 3a 30 30 5a - непосредственно строка 1970-01-01T00:00Z


Обратите внимание, что даже если декодер не знает, что означает тег 0, он всё равно сможет декодировать данные, так как после тега идёт элемент базового типа 3 — текстовая строка.

На данный момент стандартом определены несколько тегов, сопровождением списка тегов занимается IANA, текущее распределение можно увидеть по ссылке

Стоит отдельно отметить тег 55799, который означает, что далее идут данные в формате CBOR. По сути он не несёт никакой полезной нагрузки, но, например, при сохранении данных в формате CBOR в файл, этот тег образует последовательность 0xd9d9f7 в начале, которая может использоваться утилитами, как магическое значение для определения типа файла. Кроме того данная последовательность не встречается ни в одной из существующих кодировок Unicode, поэтому позволяет быстро отличать CBOR от текстовых данных.

Тип 7: числа с плавающей запятой и другие простые типы данных


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

  • 0..23 — Простое значение (код от 0 до 23)
  • 24 — Простое значение (код от 24 до 255)
  • 25 — IEEE 754 число с плавающей запятой половинной точности (16 бит)
  • 26 — IEEE 754 число с плавающей запятой одинарной точности (32 бит)
  • 27 — IEEE 754 число с плавающей запятой двойной точности (64 бит)
  • 28-30 — неопределено
  • 31 — Стоп-код прерывания (break) для элементов с неопределённой длиной


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

  • 20 — False
  • 21 — True
  • 22 — Null
  • 23 — Undefined


Регистрацией других простых значений также занимается IANA, на текущий момент список простых значений доступен по ссылке.

Неопределённая длина элементов некоторых основных типов



Четыре основных типа: массив, карта, байтовая и текстовая строка могут иметь неопределённое значение элементов (что задаётся значением 31 в дополнительной информации). Это позволяет начать кодирование элементов, количество которых ещё неизвестно. Такое может быть востребовано в приложениях, которые ведут потоковую передачу данных.

В случае массивов и карт элементы просто следуют один за другим, и, для индикации завершения используется стоп-код прерывания. Сразу после последнего элемента массива или карты следует элемент типа 7 с дополнительной информацией 31 — это байт 0xFF.

В случае строк используется другой подход. Строки передаются частями конечной длины, которые позже объединяются в одну строку (это может сделать как декодировщик, так и конечное приложение). Индикатором завершения последовательности частей строк также служит стоп-код прерывания 0xFF. В случае текстовых строк при передаче фрагментов важно, чтобы разделение строки не происходило внутри кодовой последовательности Unicode-символа, т.е. все части строки должны содержать валидные последовательности Unicode-символов.

Пример:

5F           -- Старт байтовой строки неопределённой длины
  44         -- Байтовая строка длиной 4 байта
    aabbccdd -- Содержимое первого фрагмента
  43         -- Байтовая строка длиной 3 байта
    eeff99   -- Содержимое следующего фрагмента
  FF         -- "break"


После декодирования все фрагменты объединяются в одну строку: aabbccddeeff99

Каноническая реализация формата



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

  • Использование наиболее сжатого представления для кодируемых данных. Например, если кодируется целое число 500, то должно выбираться представление uint16_t, а не, скажем, uint64_t. При кодировании числа 0.0 кодировщик должен выполнить преобразование к целому типу, так как это даст более сжатое представление. Если число с плавающей запятой может быть представлено с одинарной точностью без потери значимых разрядов, то кодировщик не должен использовать двойную точность и т.д.
  • Ключи ассоциативных массивов должны быть отсортированы в возрастающем порядке (байтовая сортировка, сначала идут более короткие ключи)
  • При возможности элементы с неопределённой длиной заменяются с фиксированной длиной
  • Каноническая реализация не должна использовать теги, но при обработке данных с тегами, должна сохранять их


Обработка ошибок



Стандарт CBOR допускает различный подход к обработке ошибок в формате. Ошибки могут быть связаны как с самим форматом (неизвестные значения в дополнительной информации, простых значений, некорректное число элементов массива и т.д.), так и со значениями (например, невалидный UTF-8 код в текстовой строке или дублирующиеся ключи в ассоциативном массиве).

Декодировщик может выдавать предупреждения на некорректных данных, может выполнять преобразования, чтобы исправить ошибку, может игнорировать ошибки или прекращать обработку сразу при обнаружении первой ошибки. Стандарт предлагает использование строгого (strict) режима в случае если данные пришли из ненадёжного источника, в этом случае декодировщик должен отклонять все данные, которые не прошли валидацию или могут быть по разному восприняты разными декодировщиками. Нестрогий режим используется, если данные из надёжного источника и больше важна скорость обработки (например, не проверять валидность UTF-8 строк).

Сравнение с другими бинарными форматами



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

+---------------+-------------------------+-------------------------+
| Format        | [1, [2, 3]]             | [_ 1, [2, 3]]           |
+---------------+-------------------------+-------------------------+
| RFC 713       | c2 05 81 c2 02 82 83    |                         |
|               |                         |                         |
| ASN.1 BER     | 30 0b 02 01 01 30 06 02 | 30 80 02 01 01 30 06 02 |
|               | 01 02 02 01 03          | 01 02 02 01 03 00 00    |
|               |                         |                         |
| MessagePack   | 92 01 92 02 03          |                         |
|               |                         |                         |
| BSON          | 22 00 00 00 10 30 00 01 |                         |
|               | 00 00 00 04 31 00 13 00 |                         |
|               | 00 00 10 30 00 02 00 00 |                         |
|               | 00 10 31 00 03 00 00 00 |                         |
|               | 00 00                   |                         |
|               |                         |                         |
| UBJSON        | 61 02 42 01 61 02 42 02 | 61 ff 42 01 61 02 42 02 |
|               | 42 03                   | 42 03 45                |
|               |                         |                         |
| CBOR          | 82 01 82 02 03          | 9f 01 82 02 03 ff       |
+---------------+-------------------------+-------------------------+


Как видно самый компактный вид представления у MessagePack и CBOR, при этом возможность для кодирования бесконечных последовательностей есть только у BER, UBJSON и CBOR.

Существующие реализации CBOR



Сразу после выпуска стандарта стали появляться и первые реализации (де)кодировщиков на различных языках программирования. Например, C, Perl, Ruby, Python, Java, Go и множество других (правда, бегло поискав на github, я пока не нашёл реализации на JavaScript...).

Не все из этих реализаций полностью поддерживают стандарт и возможно существуют или появятся ещё много других. Всё это отлично подтверждает, что основная цель стандарта достигнута: реализация (де)кодировщика — это задача небольшой сложности. Вполне вероятно, что скоро на собеседованиях программистов начнут просить реализовать нестрогий декодировщик CBOR в качестве тестового задания.

P.S. Если вы обнаружили ошибки, опечатки или неточности в тексте, пожалуйста, сообщите, я обязательно поправлю.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 39
  • +1
    Есть еще не плохой protobuf от google
    • +14
      Протобуф требует схему описания данных, а тут нет. И это было одним из требований.
      • 0
        При всех своих достоинствах это достаточно тяжеловесное решение, объем генерированных классов (например, Java) довольно громоздкий + либа весом 666667 байт, в малоресурсных системах вроде j2me практически неприменимо несмотря даже на наличие портов.
      • +4
        Интересно.
        Надо было им для сравнения компактности еще добавить ASN.1 PER.
        • +9
          Такой бы формат лет 20-30 назад и чтобы всем им пользовались. Сейчас бы гемору намного меньше было.
          • +5
            Устранение Фатального Недостатка?
            • 0
              Очень даже интересно, исследую как раз Google Protocol Buffer, но все преимущества этого мне как раз очень даже. Дело за малым — кроссбарузерная клиентская реализация (как ProtoBuff.js) и библиотеки для РНР и Node.JS
              • +4
                … множество других (правда, бегло поискав на github, я пока не нашёл реализации на JavaScript...).


                здесь есть и JavaScript.
                • 0
                  О, действительно. Спасибо.
                  Правда там указано, что
                  The Java and JavaScript versions are translations from the C# version

                  Наверняка кто-нибудь решит сделать с нуля в «натуральном» виде.
                • +1
                  Я так понял что если я хочу закодировать огромный массив одинаковых вещей, то перед каждым элементом будет префикс, что не есть гуд.
                  • +3
                    Всё нормально. Если вы хотите хранить кучу строк — вам же всё равно длину строк надо знать. Для мелких строк размер будет кодироваться прямо в том-же байте, что и префикс. Если кучу мелких чисел — они тоже будут влезать в этот 1 байт. Числа покрупнее будут занимать уже чуть больше байт, но всё равно скорее всего лучше чем оригиналы. Конечно не хаффман но тоже неплохо.
                    • 0
                      Хотя если вы храните толпу char-ов в районе ~240 — использовать на это по два байта конечно не прикольно…
                      • +1
                        Байтовые строки же.
                        • 0
                          Это общая беда всех кодировщиков. На любую схему кодирования найдётся другая, которая на некоторых данных будет лучше.

                          Если хочется оптимальнее положить какой-то блок, можно использовать байтовую строку, и парсить её более оптимально, не протоколом контейнера.

                          upd: опередили ))
                        • +3
                          Более того, уже есть расширение, которое позволят кодировать повторяющиеся строки ссылками. Это позволяет получить ещё более компактное представление, если у вас огромный массив одинаковых объектов:

                            [
                               {
                                 "name" : "Cocktail",
                                 "count" : 417,
                                 "rank" : 4
                               },
                               {
                                 "rank" : 4,
                                 "count" : 312,
                                 "name" : "Bath"
                               },
                               {
                                 "count" : 691,
                                 "name" : "Food",
                                 "rank" : 4
                               }
                            ]
                          


                          Начиная со второго объекта, ключи кодируются как ссылки на строки и занимают 3 байта.
                          • 0
                            Самый простой пример, передать буфер вершин (килобайты флоатов). Аккурат такая задача была, смотрел различные форматы, почти везде такая же схема как и в этом примере. В итоге остановился на RIFF контейнере.
                            • 0
                              Дурововский TL не имеет такой проблемы, можно сделать большой массив float'ов.

                              Будет лишь оверхед в 8 байт (4 байта на тип, 4 байта на кол-во элементов).
                              • 0
                                Спасибо. Но я взял канонический формат RIFF, который настолько простой что любой кто сам захочет написать что то подобное напишет его же. (имя чанка + размер чанка + данные)
                        • +6
                          А если в табличке сравнить [24, [24, 34]]?
                          • +7
                            Спасибо за статью, интересный формат данных. Возможно, когда-нибудь воспользуюсь. Но хочу заметить об одном существенном недостатке формата по сравнению, например, с HDF5. Отсутствие произвольного доступа к элементам, отсутствие возможности быстро выяснить, сколько и каких содержится элементов в файле. Такой формат нужно или грузить в память целиком, или обрабатывать в несколько проходов, если он не влезает в память. Также, если нужна не вся информация из файла — все равно придется прочитать его весь.
                            • +3
                              Разные форматы имеют разные цели. Если нужна метаинформация о количестве элементов, то можно создать своё расширение к CBOR: выбрать свободный номер тега и создать простую структуру из базовых типов, в которой описать всю нужную метаинформацию. Кодировщик после прохода по данным сосчитает число элементов и запишет информацию в теге в конец или начало кодированных данных. Т.о. декодировщик сможет затем извлечь нужную информацию о данных не загружая весь объём данных.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • 0
                                  Concise Binary Object Representation (сжатое бинарное представление объекта) — формат данных, который был спроектирован таким образом, чтобы обеспечить максимально простой код реализации, формирования компактных выходных данных и возможность расширения формата без необходимости обмена информацией о версии.
                                  • 0
                                    1. Потоковый парсер позволит не грузить в память ничего, кроме текущего значения. Потоковый парсер для этого формата возможен.
                                    2. Это же не СУБД и не файловая система, чтобы иметь произвольный доступ к элементам. Произвольный доступ — довольно тяжелое в реализации требование, подтверждением служит многообразие упомянутых систем.
                                  • 0
                                    Хорошо. Про текстовые форматы (типа xml и json) знают все, а бинарные к сожалению не так широко известны (я например знал лишь то что они существуют, но ни разу с ними не сталкивался ни как программист, ни как пользователь).
                                    • +1
                                      Во всех играх используются повсеместно, DOOM, Quake, половина форматов хранения 3D массива данных, практически все ГИС используют свой кастомный внутренний бинарный фрпмат хранения данных, треки GPS так же могут записываться в бинарном формате, фактически зесь описан именно codec — формат хранения данных для передачи, с последующим его получением и декодированием.
                                      • +1
                                        В том-то и дело, что «свой кастомный внутренний бинарный формат хранения данных». Я тоже такой могу придумать и придумывал неоднократно.
                                        А хочется, чтобы был некий универсальный и повсеместно распространенный формат, библиотеки для работы с ним в большинстве языков программирования, софт для просмотра и редактирования этих данных и т.д. Как с XML.
                                    • 0
                                      были у меня идеи, когда положительная и отрицательная бесконечность кодируется 0x7F и 0x81, а NAN — 0x80. Но, видимо, до этого еще далеко. Хоть логика учтена.
                                      • +5
                                        А зачем? Разве они так часто встречаются, чтобы кодировать их одним байтом?
                                        • 0
                                          В NaN есть еще целочисленная диагностическая информация (payload). Изредка она используется.
                                        • 0
                                          Чем это принципиально лучше msgpack'а, помимо фатального недостатка?
                                          • +2
                                            Msgpack изначально не делал различия между байтовыми строками и текстовыми. Можно вспомнить жаркую дискуссию по этому поводу. С проблемой столкнулись ещё в 2011 году. Основная проблема с изменением была связана с тем, что модификация формата приведёт к потере обратной совместимости, т.е. спецификация затрудняла дальнейшие развитие формата. CBOR предусматривает возможность для развития без потери обратной совместимости.
                                            Второе менее значимое отличие — это поддержка массивов/строк неопределённой длины.
                                            • 0
                                              На саму концепцию строк неопределенной длины у меня нет слов. Цензурных.

                                              Ну, JSON, ну ладно. Но двоичный-то формат всегда программа пишет! Уж программе-то размер должен быть известен, раз она память под него выделила! Не понимаю.
                                              • +3
                                                программе-то размер должен быть известен, раз она память под него выделила!

                                                Если она из сокета данные читает, откуда ей размер знать? Даже в http Content-Length не всегда указан.
                                                Заранее известный размер всегда предпочтительнее, но он, к сожалению, далеко не всегда доступен энкодеру.
                                                • 0
                                                  Ну да, ну да. Сначала не делаем Content-length обязательным, а потом жалуемся, что размер неизвестен. А потом и в двоичных форматах.
                                                  • +2
                                                    Посмотрим на тот же хабр: имя юзера сверху, новостные блоки, реклама, комментарии. Длина страницы заранее неизвестна.
                                                    Разве что не сразу в сокет её посылать, а сначала в буфер. Но так пользователю дольше ждать. Сейчас статья видна до загрузки комментариев.
                                                    • 0
                                                      Речь про длину строки, а не всего содержимого. Длина имени пользователя, заголовка новости и текста комментария уже известны серверу на момент отправки.

                                                      Страницу целиком вполне можно рассматривать как набор кадров потокового вещания, тут я не спорю.
                                                      • +2
                                                        Речь о Content-Length в HTTP
                                          • 0
                                            Есть еще из похожего формат сообщений RADIUS & DIAMETER. DIAMETER будет покруче.

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