# A Survey of JSON-compatible Binary Serialization Specifications

Juan Cruz Viotti
Department of Computer Science
University of Oxford
Oxford, GB OX1 3QD
<EMAIL_ADDRESS>
https://www.jviotti.com Mital Kinderkhedia
Department of Computer Science
University of Oxford
Oxford, GB OX1 3QD
<EMAIL_ADDRESS>

###### Abstract

In this paper, we present the recent advances that highlight the
characteristics of JSON-compatible binary serialization specifications. We
motivate the discussion by covering the history and evolution of binary
serialization specifications across the years starting from 1960s to 2000s and
onwards. We analyze the use cases of the most popular serialization
specifications across the industries. Drawing on the schema-driven (ASN.1,
Apache Avro, Microsoft Bond, Cap’n Proto, FlatBuffers, Protocol Buffers, and
Apache Thrift) and schema-less (BSON, CBOR, FlexBuffers, MessagePack, Smile,
and UBJSON) JSON-compatible binary serialization specifications, we compare
and contrast their inner workings through our analysis. We explore a set of
non-standardized binary integer encoding techniques (ZigZag integer encoding
and Little Endian Base 128 variable-length integer encoding) that are
essential to understand the various JSON-compatible binary serialization
specifications. We systematically discuss the history, the characteristics,
and the serialization processes of the selection of schema-driven and schema-
less binary serialization specifications and we identify the challenges
associated with schema evolution in the context of binary serialization.
Through reflective exercise, we explain our observations of the selection of
JSON-compatible binary serialization specifications. This paper aims to guide
the reader to make informed decisions on the choice between schema-driven or
schema-less JSON-compatible binary serialization specifications.

##  1 Introduction

###  1.1 Serialization and Deserialization

_Serialization_ is the process of translating a data structure into a _bit-
string_ (a sequence of bits) for storage or transmission purposes. The
original data structure can be reconstructed from the bit-string using a
process called _deserialization_. Serialization specifications define the
bidirectional translation between data structures and bit-strings.
Serialization specifications support persistence and the exchange of
information in a machine-and-language-independent manner.

Figure 1: The process of translating a data structure to a bit-string is
called _serialization_. The process of translating a bit-string back to its
original data structure is called _deserialization_.

Serialization specifications are categorized based on how the information is
represented as a bit-string i.e. textual or binary and whether the
serialization and deserialization processes require a formal description of
the data structure i.e. schema-driven or schema-less. Before we go into a
detailed discussion about textual and binary serialization specifications, we
motivate by discussing the history and evolution of serialization
specifications.

###  1.2 History and Evolution of Serialization Specifications

Figure 2: A timeline showcasing some of the most popular serialization
specifications since the early 1980s.

1960s. In 1969, IBM developed _GML_ (Generalized Markup Language)
111http://www.sgmlsource.com/history/roots.htm, a markup language and schema-
less textual serialization specification to define meaning behind textual
documents. Decades later, XML [100] was inspired by GML.

1970s. In 1972, IBM OS/360 introduced a general-purpose schema-less
serialization specification as part of their FORTRAN suite [65]. The IBM
FORTRAN manuals referred to the serialization specification as _List-Directed
Input/Output_. It consisted of comma-separated or space-separated values that
now resemble the popular CSV [123] schema-less textual serialization
specification.

1980s. Microsoft invented the _INI_ general purpose schema-less textual
serialization specification 222https://docs.microsoft.com/en-us/previous-
versions/windows/it-pro/windows-
server-2008-R2-and-2008/cc731332(v=ws.11)?redirectedfrom=MSDN as part of their
MS-DOS operating system in the early 1980s (the exact year is unclear). In
2021, the Microsoft Windows operating system continues to make use of the INI
specification. INI also inspired the syntax of configuration file formats in
popular software products such as _git_ 333https://git-scm.com and _PHP_
444https://www.php.net. In 1983, the Osborne Executive portable computer
Reference Guide [34] used the term _CSV_ to refer to files containing comma-
separated rows of data. In 1984, the _International Telecommunication Union_
555https://www.itu.int/ITU-T/recommendations/index.aspx?ser=X specified the
_ASN.1_ schema-driven binary serialization specification as part of the [118]
standard. The ASN.1 serialization specification became a standalone standard
in 1988. In 1986, the _SGML_ (Standard Generalized Markup Language), a
descendant of IBM GML to define custom markup languages, was proposed as an
ISO standard [39]. In the late 1980s, NeXT introduced the schema-less textual
ASCII-based [28] _Property List_ serialization format
666https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/PropertyLists/OldStylePlists/OldStylePLists.html
which is now popular in Apple’s operating systems.

1990s. In 1996, the Netscape web browser used stringified representations of
JavaScript data structures for data interchange [36]. This serialization
approach would be standardized as JSON [19] a decade later. Also, the SGML
[39] language inspired the first working draft of a general-purpose schema-
less textual serialization specification named _XML_ (Extensible Markup
Language) [20]. In 1997, The Java programming language JDK 1.1 defined a
_Serializable_ interface
777https://docs.oracle.com/javase/7/docs/api/java/io/Serializable.html that
provided binary, versioned and streamable serialization of Java classes and
their corresponding state. This serialization specification is referred to as
_Java Object Serialization_
888https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serialTOC.html
and it is still in use. In 1998, [98] further improved this object
serialization technique. In 1999, XML became a W3C (World Wide Web Consortium)
999https://www.w3.org recommendation [20].

2000s. In 2000, Apple (who acquired NeXT in 1997) introduced a binary encoding
for the _Property List_ serialization specification
101010https://opensource.apple.com/source/CF/CF-1153.18/CFBinaryPList.c.auto.html.
A year later, Apple replaced the ASCII-based [28] original _Property List_
encoding with an XML-based encoding
111111https://web.archive.org/web/20140219093104/http://www.appleexaminer.com/MacsAndOS/Analysis/PLIST/PLIST.html.
In 2001, Google developed an internal schema-driven binary serialization
specification and RPC protocol named _Protocol Buffers_ [60]. In the same
year, the first draft of the schema-less textual _YAML_ [10] serialization
specification was published as a human-friendly alternative to XML [100].
Refer to [45] for a detailed discussing of the differences between YAML and
JSON. The widely-used _CSV_ [123] schema-less textual serialization
specification was standardized in 2005. The first draft of the _JSON_ schema-
less textual serialization specification was published in 2006 [35]. In the
same year, Facebook developed an open-source schema-driven binary
serialization specification and RPC protocol similar to Protocol Buffers [60]
named _Apache Thrift_ [127]. In 2008, Google open-sourced _Protocol Buffers_
[60]. In 2009, the _MessagePack_ [57] schema-less binary serialization
specification was introduced by Sadayuki Furuhashi
121212https://github.com/frsyuki. Two other binary serialization
specifications were released in 2009: The Apache Hadoop
131313https://hadoop.apache.org framework introduced the _Apache Avro_ [53]
schema-driven serialization specification. The MongoDB database
141414https://www.mongodb.com introduced a schema-less serialization
alternative to JSON [19] named _BSON_ (Binary JSON) [87].

Advances since 2010. Two new schema-less binary serialization specification
alternatives to JSON [19] were conceived in 2010 and 2012: _Smile_ [117] and
_UBJSON_ [18], respectively. In 2011, Microsoft developed _Bond_ [88], a
schema-driven binary serialization specification and RPC protocol inspired by
Protocol Buffers [60] and Apache Thrift [127]. In 2013, the lessons learned
from Protocol Buffers [60] inspired one of its original authors to create an
open-source schema-driven binary serialization specification and RPC protocol
named _Cap’n Proto_ [143]. Two schema-less serialization specifications were
created on 2013: a textual serialization specification inspired by INI named
_TOML_ [110] and a binary serialization specification designed for the
Internet of Things named _CBOR_ [15]. In 2014, Google released _FlatBuffers_
[140], a schema-driven binary serialization specification that was later found
to share some similarities to Cap’n Proto [143]. In 2015, Microsoft open-
sourced _Bond_ [88]. In 2016, Google introduced _FlexBuffers_ [141], a schema-
less variant of FlatBuffers [140].

Figure 3: The most popular serialization specifications by their use case. Table 1: A non-exhaustive list of companies that publicly state that they are using the binary serialization specifications discussed in this paper. Serialization Specification |  Companies
---|---
ASN.1 |  Broadcom, Cisco, Ericsson, Hewlett-Packard, Huawei, IBM, LG Electronics, Mitsubishi, Motorola, NASA, Panasonic, Samsung, Siemens 1515footnotemark: 15
Apache Avro |  Bol, Cloudera, Confluent, Florida Blue, Imply, LinkedIn, Nuxeo, Spotify, Optus, Twitter 1616footnotemark: 16
Microsoft Bond |  Microsoft
Cap’n Proto |  Sandstorm, Cloudflare 1717footnotemark: 17
FlatBuffers / FlexBuffers |  Apple, Electronic Arts, Facebook, Google, Grafana, JetBrains, Netflix, Nintendo, NPM, NVidia, Tesla 1818footnotemark: 18, 1919footnotemark: 19
Protocol Buffers |  Alibaba, Amazon, Baidu, Bloomberg, Cisco, Confluent, Datadog, Dropbox, EACOMM, Facebook, Google, Huawei, Intel, Lyft, Microsoft, Mozilla, Netflix, NVidia, PayPal, Sony, Spotify, Twitch, Uber, Unity, Yahoo, Yandex 2020footnotemark: 20, 2121footnotemark: 21
Apache Thrift |  Facebook, Cloudera, Evernote, Mendeley, last.fm, OpenX, Pinterest, Quora, RapLeaf, reCaptha, Siemens, Uber 2222footnotemark: 22
BSON |  MongoDB
CBOR |  Intel 2323footnotemark: 23, Microsoft 2424footnotemark: 24, Outfox 2525footnotemark: 25, Pelion 2626footnotemark: 26
MessagePack |  Amazon, Atlassian, CODESYS, Datadog, Deliveroo, GitHub, Google, GoSquared, LinkedIn, Microsoft, Mozilla, NASA, National Public Radio, NPM, Pinterest, Sentry, Shopify, Treasure Data, Yelp 2727footnotemark: 27, 2828footnotemark: 28, 2929footnotemark: 29, 3030footnotemark: 30
Smile |  Ning, Elastic 3131footnotemark: 31
UBJSON |  Teradata 3232footnotemark: 32, Wolfram 3333footnotemark: 33
††footnotetext: https://www.oss.com/company/customers.html††footnotetext:
https://lists.apache.org/thread.html/rc11fcfbc294bb064c6e59167f21b38f3eb6d14e09b9af60970b237d6%40%3Cuser.avro.apache.org%3E††footnotetext:
https://www.linkedin.com/in/kenton-varda-5b96a2a4/††footnotetext:
https://github.com/google/flatbuffers/issues/6424††footnotetext:
https://github.com/google/flatbuffers/network/dependents††footnotetext:
https://groups.google.com/g/protobuf/c/tJVbWK3y_TA/m/vpOiSFfqAQAJ††footnotetext:
https://github.com/protocolbuffers/protobuf/network/dependents††footnotetext:
https://thrift.apache.org/about#powered-by-apache-thrift††footnotetext:
https://www.npmjs.com/package/tinycbor††footnotetext:
https://github.com/OneNoteDev/GoldFish††footnotetext:
https://github.com/outfoxx/PotentCodables††footnotetext:
https://github.com/PelionIoT/cbor-sync††footnotetext:
https://github.com/msgpack/msgpack-node/network/dependents††footnotetext:
https://github.com/msgpack/msgpack-ruby/network/dependents††footnotetext:
https://github.com/msgpack/msgpack-
javascript/network/dependents††footnotetext:
https://github.com/msgpack/msgpack/issues/295††footnotetext:
https://github.com/FasterXML/smile-format-
specification/issues/15††footnotetext:
https://docs.teradata.com/reader/C8cVEJ54PO4~YXWXeXGvsA/b9kd0QOTMB3uZp9z5QT2aw††footnotetext:
https://reference.wolfram.com/language/ref/format/UBJSON.html

###  1.3 Textual and Binary Serialization Specifications

A serialization specification is _textual_ if the bit-strings it produces
correspond to sequences of characters in a text encoding such as ASCII [28],
EBCDIC/CCSID 037 [66], or UTF-8 [33], otherwise the serialization
specification is _binary_.

We can think of a textual serialization specification as a set of conventions
within the boundaries of a text encoding such as UTF-8 [33]. The availability
and diversity of computer tools to operate on popular text encodings makes
textual serialization specifications to be perceived as human-friendly. In
comparison, binary serialization specifications are not constrained by a text
encoding. This flexibility typically results in efficient representation of
data at the expense of requiring accompanying documentation and specialized
tools.

Figure 4: Textual and binary representations of the decimal number
$3.1415926535$. The textual representation encodes the decimal number as a
96-bits sequence of numeric characters ("3" followed by ".", followed by "1",
and so forth) that we can easily inspect and understand using a text editor.
On the other hand, the binary representation encodes the decimal number in
terms of its sign, exponent, and mantissa. The resulting bit-string is only 32
bits long - three times smaller than the textual representation. However, we
are unable to understand it using generally-available text-based tools.

###  1.4 Schema-less and Schema-driven Serialization Specifications

A _schema_ is a formal definition of a data structure. For example, a schema
may describe a data structure as consisting of two Big Endian IEEE 754 single-
precision floating-point numbers [52]. A serialization specification is
_schema-less_ if it produces bit-strings that can be deserialized without
prior knowledge of its structure and _schema-driven_ otherwise.

Implementations of schema-less serialization specifications embed the
information provided by a schema into the resulting bit-strings to produce
bit-strings that are standalone with respect to deserialization. In comparison
to schema-driven serialization specifications, schema-less serialization
specifications are perceived as easier to use because receivers can
deserialize any bit-string produced by the implementation and not only the
ones the receivers know about in advance. Alternatively, schema-driven
specification implementations can avoid encoding certain structural
information into the bit-strings they produce. This typically results in
compact space-efficient bit-strings. For this reason, network-efficient
systems tend to adopt schema-driven serialization specifications [108].
Schema-driven serialization specifications are typically concerned with space
efficiency and therefore tend to be binary. However, [26] propose a textual
JSON-compatible schema-driven serialization specification. In the case of
communication links with large bandwidths or small datasets, the gains are
negligible but considering slow communication links or large datasets which
could be terabytes in size, the choice of serialization specification could
have a big impact.

Writing and maintaining schema definitions is a core part of using schema-
driven serialization specifications. Most schema-driven serialization
specifications implement a custom schema language that is not usable by any
other schema-driven serialization specification. A schema-driven serialization
specification may use a low-level or a high-level schema definition language.
Low-level schema definition languages such as _PADS_ [50], _BinX_ [148], and
_Data Format Description Language_ (DFDL) [148] are concerned with describing
the contents of bit-strings while high-level schema definition languages such
as _ASN.1_ [119] and _JSON Schema_ [153] abstractly describe data structures
and depend on the serialization specification implementation to provide the
corresponding encoding rules.

Often, schemas are auto-generated from formal definitions such as database
tables 343434https://github.com/SpringTree/pg-tables-to-jsonschema, other
schema languages 353535https://github.com/okdistribute/jsonschema-protobuf, or
inferred from the data [55] [75] [7] [37] [152] [44] [23] [129] [6]. There are
also examples of domain-specific schema-driven serialization specifications
where the schema definition is implicitly embedded into the serialization and
deserialization implementation routines, such as the SOL binary representation
for sensor measurements [21].

Figure 5: An associative array (also known as a map) that consists of two
decimal number properties, "latitude" and "longitude", serialized with
fictitious schema-less and schema-driven representations. The schema-less
representation (top) is self-descriptive and each property is self-delimited.
Alternatively, schema-driven representations (bottom) omit most self-
descriptive information except for the length of the associative array as an
integer prefix. A reader cannot understand how the schema-driven
representation translates to the original data structure without additional
information such as a schema definition.

###  1.5 Schema-less as a Subset of Schema-driven

Schema-driven serialization specifications avoid embedding structural
information into the resulting bit-strings for space-efficiency purposes. If a
schema fails to capture essential structural information then the
serialization specification has to embed that information into the resulting
bit-strings. We can reason about schema-less serialization specifications as
schema-driven specifications where the schema is generic enough that it
describes any bit-string and as a consequence carries no substantial
information about any particular instance. For example, a schema that defines
bit-strings as sequences of bits can describe any bit-string while providing
no useful information for understanding the semantics of such bit-strings.

The amount of information included in a schema can be thought as being
_inversely proportional_ to the information that needs to be encoded in a bit-
string described by such schema. However, schema-driven serialization
specifications may still embed redundant information into the bit-strings with
respect to the schema for runtime-efficiency, compatibility or error
tolerance. We can rank schema-driven serialization specifications based on the
extent of information that is necessary to include in the bit-strings.

Figure 6: We can compare schema-less and schema-driven serialization
specifications based on how much information their resulting bit-strings
contain. Schema-less specifications are equivalent in that they all consist of
implicit schemas that convey no information. However, not all schema languages
supported by schema-driven specifications can describe the same amount of
information. For this reason, some schema-driven specifications need to encode
more structural information into their resulting bit-strings than others,
placing them on the left hand side of the line. Schema-driven specifications
that enable meticulously defined schemas are placed on the right hand side of
the line.

###  1.6 Related Work

Table 2 and Table 3 list existing literature that discusses different sets of
serialization specifications, both textual and binary, schema-less and schema-
driven. However, many of these publications discuss serialization
specifications that are either not JSON-compatible, cannot be considered
general-purpose serialization specifications, or are out of date. For example,
Java Object Serialization, as its name implies, is only concerned with
serialization of object instances in the Java programming language. The first
Protocol Buffers [60] version 3 release was published on GitHub in 2014
363636https://github.com/protocolbuffers/protobuf/releases/tag/v3.0.0-alpha-1,
yet there are several publications listed in Table 2 and Table 3 released
before that year discussing the now-obsolete Protocol Buffers version 2 [150]
[59] [85] [128] [142] [47]. As another example, [89] discusses an ASN.1 [119]
encoding (LWER) that has been abandoned in the 1990s [80].

Furthermore, many of the publications listed in Table 2 and Table 3 are
concerned with benchmarking. They tend to describe the respective
specifications in a high-level manner and do not get into the encoding details
of non-trivial examples, if any.

Table 2: A list of publications that discuss binary serialization specifications. This table is continued in Table 3. Publication | Year |  Context |  Discussed Serialization Specifications
---|---|---|---
An overview of ASN.1 [93] | 1992 |  Networking |  ASN.1 BER [121], ASN.1 PER [120]
Efficient encoding rules for ASN.1-based protocols [89] | 1994 |  Networking |  ASN.1 BER [121], ASN.1 CER [121], ASN.1 DER [121], ASN.1 LWER [80], ASN.1 PER [120]
Evaluation of Protocol Buffers as Data Serialization Format for Microblogging Communication [150] | 2011 |  Microblogging |  JSON [42], Protocol Buffers [60]
Impacts of Data Interchange Formats on Energy Consumption and Performance in Smartphones [59] | 2011 |  Mobile |  JSON [42], Protocol Buffers [60], XML [100]
Performance evaluation of object serialization libraries in XML, JSON and binary formats [85] | 2012 |  Java Object Serialization |  Apache Avro [53], Apache Thrift [127], Java Object Serialization 3737footnotemark: 37, JSON [42], Protocol Buffers [60], XML [100]
A comparison of data serialization formats for optimal efficiency on a mobile platform [128] | 2012 |  Mobile |  Apache Thrift [127], JSON [42], Protocol Buffers [60], XML [100]
Performance evaluation of Java, JavaScript and PHP serialization libraries for XML, JSON and binary formats [142] | 2012 |  Web Services |  Apache Avro [53], Java Object Serialization 3838footnotemark: 38, JSON [42], MessagePack [57], Protocol Buffers [60], XML [100]
Google protocol buffers research and application in online game [47] | 2013 |  Gaming |  Protocol Buffers [60]
Integrating a System for Symbol Programming of Real Processes with a Cloud Service [77] | 2015 |  Web Services |  JSON [42], MessagePack [57], XML [100], YAML [10]
Table 3: Continuation of Table 2. Publication | Year |  Context |  Discussed Serialization Specifications
---|---|---|---
Serialization and deserialization of complex data structures, and applications in high performance computing [156] | 2016 |  Scientific Computing |  Apache Avro [53], Boost::serialize 3939footnotemark: 39, Cap’n Proto [143], OpenFPM Packer/Unpacker [67], Protocol Buffers [60]
Smart grid serialization comparison: Comparison of serialization for distributed control in the context of the internet of things [105] | 2017 |  Internet of Things |  Apache Avro [53], BSON [87], CBOR [15], FST 4040footnotemark: 40, Hessian 4141footnotemark: 41, Java Object Serialization 4242footnotemark: 42, Kryo 4343footnotemark: 43, MessagePack [57], Protocol Buffers [60], ProtoStuff 4444footnotemark: 44, Smile [117], XML [100], YAML [10]
Binary Representation of Device Descriptions: CBOR versus RDF HDT [116] | 2018 |  Internet of Things |  CBOR [15], JSON [42], RFD HDT 4545footnotemark: 45
Evaluating serialization for a publish-subscribe based middleware for MPSoCs [64] | 2018 |  Embedded Development |  FlatBuffers [140], MessagePack [57], Protocol Buffers [60], YAS 4646footnotemark: 46
Analytical Assessment of Binary Data Serialization Techniques in IoT Context [11] | 2019 |  Internet of Things |  BSON [87], FlatBuffers [140], MessagePack [57], Protocol Buffers [60]
FlatBuffers Implementation on MQTT Publish/Subscribe Communication as Data Delivery Format [109] | 2019 |  Internet of Things |  CSV [123], FlatBuffers [140], JSON [42], XML [100]
Enabling Model-Driven Software Development Tools for the Internet of Things [72] | 2019 |  Internet of Things |  Apache Avro [53], Apache Thrift [127], FlatBuffers [140], JSON [42], Protocol Buffers [60]
Performance Comparison of Messaging Protocols and Serialization Formats for Digital Twins in IoV [111] | 2020 |  Automobile |  Cap’n Proto [143], FlatBuffers [140], Protocol Buffers [60]
Performance Analysis and Optimization of Serialization Techniques for Deep Neural Networks [101] | 2020 |  Machine Learning |  FlatBuffers [140], Protocol Buffers [60]
††footnotetext:
https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serialTOC.html††footnotetext:
https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serialTOC.html††footnotetext:
https://www.boost.org/doc/libs/1_55_0/libs/serialization/doc/index.html††footnotetext:
https://github.com/RuedigerMoeller/fast-serialization††footnotetext:
http://hessian.caucho.com/doc/hessian-serialization.html††footnotetext:
https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serialTOC.html††footnotetext:
https://github.com/EsotericSoftware/kryo††footnotetext:
https://github.com/protostuff/protostuff††footnotetext:
https://www.rdfhdt.org††footnotetext: https://github.com/niXman/yas

###  1.7 Contributions

To the best of our knowledge, there exists gaps in the current literature
resulting in a lack of discussion on a wide range of JSON-compatible binary
serialization specifications in depth. We aim to fill that gap by providing a
detailed comparative analysis of the most popular JSON-compatible binary
serialization specifications. Through the process of conducting a literature
review, we identified and resolved 13 issues with the documentation and
specifications of the Apache Avro [53], Apache Thrift [127], FlatBuffers
[140], FlexBuffers [141], Microsoft Bond [88], and Smile [117] open-source
binary serialization specifications. Our fixes, the corresponding patches and
links are listed in Table 4 and Table 5.

Table 4: A list of open-source contributions made by the authors in the process of writing this survey paper. This table is continued in Table 5. Specification |  Repository | Commit |  Description
---|---|---|---
Apache Avro [53] |  https://github.com/apache/avro | afe8fa1 |  Improve the encoding specification to clarify that records encode fields even if they equal their explicitly-set defaults and that the default keyword is only used for schema evolution purposes
Apache Thrift [127] |  https://github.com/apache/thrift | 2e7f39f |  Improve the Compact Protocol specification to clarify the Little Endian Base 128 (LEB128) variable-length integer encoding procedure and include a serialization example
Apache Thrift [127] |  https://github.com/apache/thrift | 47b3d3b |  Improve the Compact Protocol specification to clarify that strings are not delimited with the _NUL_ ASCII [28] character
FlatBuffers [140] |  https://github.com/google/flatbuffers | 4aff119 |  Extend the binary encoding specification to document how union types are encoded
FlatBuffers [140] |  https://github.com/google/flatbuffers | 7b1ee31 |  Improve the documentation to clarify that the schema language does not permit unions of scalar types but that the C++ [69] implementation has experimental support for unions of structs and strings
FlatBuffers [140] |  https://github.com/google/flatbuffers | 52e2177 |  Remove from the documentation an outdated claim that Protocol Buffers [60] does not support union types
FlatBuffers [140] |  https://github.com/google/flatbuffers | 796ed68 |  Improve the FlatBuffers [140] and FlexBuffers [141] encoding specification to clarify that neither specifications deduplicate vector elements but that vectors may include more than one offset pointing to the same value
Table 5: Continuation of Table 4. Specification |  Repository | Commit |  Description
---|---|---|---
Microsoft Bond [88] |  https://github.com/microsoft/bond | 4acf83b |  Improve the documentation to explain how to enable the Compact Binary version 2 encoding in the C++ [69] implementation
Microsoft Bond [88] |  https://github.com/microsoft/bond | 0012d99 |  Clarify the Compact Binary encoding specification to clarify that ID bits are encoded as Big Endian unsigned integers, that signed 8-bit integers use Two’s Complement [51], formalize the concept of variable-length integers as Little Endian Base 128 (LEB128) encoding, clarify that real numbers are encoded as IEEE 764 floating-point numbers [52], and that enumeration constants are encoded as signed 32-bit integers
Smile [117] |  https://github.com/FasterXML/smile-format-specification | ac82c6b |  Fix the fact that the specification refers to ASCII [28] string of 33 to 64 bytes and Unicode [33] strings of 34 to 65 bytes using two different names
Smile [117] |  https://github.com/FasterXML/smile-format-specification | 7a53b0a |  Improve the specification by adding an example of how real numbers are represented using the custom 7-bit variant of IEEE 764 floating-point number encoding [52]
Smile [117] |  https://github.com/FasterXML/smile-format-specification | 95133dd |  Improve the specification to clarify how the byte-length prefixes from the _Tiny Unicode_ and _Small Unicode_ string encodings are computed differently compared to their ASCII [28] counterparts
Smile [117] |  https://github.com/FasterXML/smile-format-specification | c56793f |  Clarify that the encoding attempts to reserve the 0xff byte for message framing purposes but that reserving such byte is no longer a requirement to make the format suitable for use with WebSockets

###  1.8 Paper Organisation

In section 2, we introduce the JSON serialization specification and discuss
its role and limitations. In section 3, we list the binary serialization
specifications that are discussed in depth in this paper and our approach to
analyzing them. In section 4, we explore a set of non-standardized binary
integer encoding techniques that are essential for understanding the inner
workings of the various binary serialization specifications. In section 5 and
section 6, we systematically study the history, the characteristics, and the
serialization processes of the selection of schema-driven and schema-less
binary serialization specifications. In section 7, we introduce the challenges
associated with schema evolution. Further, we discuss the schema evolution
features that the selection of schema-driven serialization specifications
provide. In section 8, we reflect over what we learned in the process of
closely inspecting the selection of JSON-compatible binary serialization
specifications. In section 9, we provide instructions for the reader to
recreate the bit-strings analyzed in the survey. Finally, in section 10, we
discuss a set of next-steps to continue and broaden the understanding of JSON-
compatible binary serialization specifications.

##  2 JSON

###  2.1 History and Characteristics

JSON (JavaScript Object Notation) is a standard _schema-less_ and _textual_
serialization specification _inspired_ by a subset
474747http://timelessrepo.com/json-isnt-a-javascript-subset of the JavaScript
programming language [43]. Douglas Crockford 484848https://www.crockford.com/,
currently a Distinguished Architect at PayPal, described the JSON
serialization specification online 494949https://www.json.org in 2002 and
published the first draft of the JSON serialization specification in 2006
[35]. Douglas Crockford claims he _discovered_ and _named_ JSON, whilst
Netscape was already using an unspecified variant as an interchange format as
early as in 1996 in their web browser [36].

Figure 7: A JSON document example taken from the official specification [19].

JSON is a human-readable open standard specification that consists of
structures built on key-value pairs or list of ordered items. The data types
it supports are objects, arrays, numbers, strings, null, and boolean constants
true and false. A data structure encoded using JSON is referred to as a _JSON
document_. [42] states that JSON documents are serialized as either UTF-8,
UTF-16, or UTF-32 strings [33]. However, [19] mandate the use of UTF-8 for
interoperability purposes. The serialization process involves recursively
converting keys and values to strings and optionally removing meaningless new
line, tab, and white space characters (a process known as _minification_) as
shown in Figure 8.

Figure 8: A _minified_ and semantically-equivalent version of the JSON
document from Figure 7.

###  2.2 Relevance of JSON

JSON [42] is popular interchange specification in the context of cloud
computing. In 2019, [144] found that JSON documents constitute a growing
majority of the HTTP [48] responses served by Akamai, a leading Content
Delivery Network (CDN) that serves around 3 trillion HTTP requests daily.
Gartner 505050https://www.gartner.com, a business insight research and
advisory firm, forecasts that the cloud services market will grow 17% in 2020
to total $266.4 billion and that SaaS will remain the largest market segment
515151https://www.gartner.com/en/newsroom/press-releases/2019-11-13-gartner-
forecasts-worldwide-public-cloud-revenue-to-grow-17-percent-in-2020. SaaS
systems typically provide _application programming interfaces_ (APIs) and JSON
was found to be the most common request and response format for APIs
525252https://www.programmableweb.com/news/json-clearly-king-api-data-
formats-2020/research/2020/04/03. According to their study, JSON was used more
than XML [100]. JSON popularity over XML can be attributed to the fact that in
comparison to XML, JSON results in smaller bit-strings and in runtime and
memory efficient serialization and deserialization implementations [95].

There is an on-going interest in JSON within the research community. [16]
describe the first formal framework for JSON documents and introduce a query
language for JSON documents named _JSON Navigational Logic_ (JNL). There is a
growing number of publications that discuss JSON in the context of APIs [152]
[44] [46] and technologies that emerged from the JSON ecosystem such as the
JSON Schema specification [107] [86] [62] [56]. Apart from cloud computing,
JSON is relevant in areas such as databases [32] [75] [9] [55] [106], big data
[155], analytics [99] [83], mobile applications [128] [59], 3D modelling [82],
IoT [147] [94], biomedical research [71], and configuration files, for example
535353https://www.typescriptlang.org/docs/handbook/tsconfig-json.html. [8]
presents a high-level overview of the JSON ecosystem including a survey of
popular schema languages and implementations, schema extraction technologies
and novel parsing tools.

###  2.3 Shortcomings

Despite its popularity, JSON is neither a runtime-efficient nor a space-
efficient serialization specification.

Runtime-efficiency. Serialization and deserialization often become a
bottleneck in data-intensive, battery-powered, and resource-constrained
systems. [99] state that big data applications may spend up to 90% of their
execution time deserializing JSON documents, given that deserialization of
textual specifications such as JSON is typically expensive using traditional
state-machine-based parsing algorithms. [59] and [128] highlight the impact of
serialization and deserialization speed on mobile battery consumption and
resource-constrained mobile platforms. As a solution, [13] propose a promising
JSON encoder and decoder that infers JSON usage patterns at runtime and self-
optimizes by generating encoding and decoding machine code on the fly.
Additionally, [79] propose a novel approach to efficiently parse JSON document
by relying on SIMD processor instructions. [83] claim that applications parse
entire JSON documents but typically only make use of certain fields. As a
suggestion for optimization, they propose a lazy JSON parser that infers
schemas for JSON documents at runtime and uses those schemas to speculate on
the position of the fields that an application requires in order to avoid
deserializing unnecessary areas of the JSON documents.

Space-efficiency. Cloud services are typically accessed over the internet. As
a result, these types of software systems are particularly sensitive to
substandard network performance. For example, in 2007, Akamai, a global
content delivery network (CDN), found out that a 100-millisecond delay in
website load time can hurt conversion rates by 7 percent and that a two-second
delay in web page load time increases bounce rates by 103 percent
545454https://www.akamai.com/uk/en/about/news/press/2017-press/akamai-
releases-spring-2017-state-of-online-retail-performance-report.jsp. Cloud
services frequently run on top of _infrastructure as a service_ (IaaS) or
_platform as a service_ (PaaS) providers such as Amazon Web Services (AWS)
555555https://aws.amazon.com. These providers typically operate on a pay-as-
you-go model where they charge per resource utilization. Therefore,
transmitting data over the network directly translates to operational
expenses. In comparison to JSON, [108] found that using a custom binary
serialization specification reduced the overall network traffic by up to 94%.
[12] conclude that JSON is not an appropriate specification for bandwidth-
constrained communication systems citing the size of the documents as the main
reason. [112] states that network traffic is one of the two biggest causes for
battery consumption on mobile devices and therefore a space-efficient
serialization specification could have a positive impact on energy savings.

There are several JSON-based specifications that highlight a need for compact
JSON encodings:

  * •

JSON Patch [22] is a specification for expressing a sequence of operations on
JSON documents. [24] describe an algorithm called JDR to compute JSON Patch
differences between two JSON documents optimized to keep the number of JSON
Patch operations to a minimum for space-efficiency reasons.

  * •

CityGML is an XML-based specification to represent 3D models of cities and
landscapes. [82] introduce a JSON-based alternative to CityGML called CityJSON
citing that CityGML documents are large enough that makes it difficult or even
impossible to transmit and process them on the web. In comparison to CityGML,
CityJSON results in smaller document size. However, the authors are looking
for a binary JSON encoding to compress the CityJSON documents even further.
Additionally, [139] explores how CityJSON documents can be compressed further
using binary serialization specifications such as BSON [87] and CBOR [15].

  * •

In the context of bioinformatics, _mmJSON_ is a popular serialization
specification used to encode representations of macromolecular structures.
[17] introduce _MMTF_ , a binary serialization specification to encode
macromolecular structures based on MessagePack [57] to address the space-
efficiency and runtime-efficiency concerns of using _mmJSON_ to perform web-
based structure visualization. In particular, using _mmJSON_ , even after
applying GZIP [40] compression, results in large macromolecular structures
that are slow to download. Due to their size, the largest macromolecular
structures results in deserialization memory requirements that exceed the
amount of memory typically available in web browsers.

##  3 Methodology

Our approach to extend the body of literature through meticulous study of
JSON-compatible binary serialization specifications is based on the following
methodology. While several serialization specifications have characteristics
outside of the context of JSON [19], the scope of this study is limited to
those characteristics that are relevant for encoding JSON documents.

  1. 1.

Identify JSON-compatible Binary Serialization Specifications. Research and
select a set of schema-driven and schema-less JSON-compatible binary
serialization specifications.

  2. 2.

Craft a JSON Test Document. Design a sufficiently complex yet succinct JSON
document in an attempt to highlight the challenges of encoding JSON data. This
JSON document is referred to as the _input data_.

  3. 3.

Write Schemas for the Schema-driven Serialization Specifications. Present
schemas that describe the _input data_ for each of the selected schema-driven
serialization specifications. The schemas are designed to produce space-
efficient results given the features documented by the corresponding
specifications.

  4. 4.

Serialize the JSON Test Document. Serialize the _input data_ using each of the
selected binary serialization specifications.

  5. 5.

Analyze the Bit-strings Produced by Each Serialization Specification. Study
the resulting bit-strings and present annotated hexadecimal diagrams that
guide the reader in understanding the inner workings of each binary
serialization specification.

  6. 6.

Discuss the Characteristics of Each Serialization Specification. For each
selected binary serialization specification, discuss the characteristics,
advantages and optimizations that are relevant in the context of serializing
JSON [42] documents.

###  3.1 Serialization Specifications

We selected a set of general-purpose schema-driven and schema-less
serialization specifications that are popular within the open-source
community. Some of the selected schema-driven serialization specifications
support more than one type of encoding. In these cases, we chose the most
space-efficient encoding. The implementations used in this study are freely
available under open-source licenses with the exception of ASN.1 [119], for
which a proprietary implementation is used. The choice of JSON-compatible
serialization specifications, the selected encodings and the respective
implementations are documented in Table 6 and Table 7.

Table 6: The schema-driven binary serialization specifications, encodings and implementations discussed in this study. Specification |  Implementation |  Encoding
---|---|---
ASN.1 |  OSS ASN-1Step Version 10.0.1 (proprietary) |  PER Unaligned [120]
Apache Avro |  Python avro (pip) 1.10.0 |  Binary Encoding 5656footnotemark: 56with no framing
Microsoft Bond |  C++ library 9.0.3 |  Compact Binary v1 5757footnotemark: 57
Cap’n Proto |  capnp command-line tool 0.8.0 |  Packed Encoding 5858footnotemark: 58
FlatBuffers |  flatc command-line tool 1.12.0 |  Binary Wire Format 5959footnotemark: 59
Protocol Buffers |  Python protobuf (pip) 3.13.0 |  Binary Wire Format 6060footnotemark: 60
Apache Thrift |  Python thrift (pip) 0.13.0 |  Compact Protocol 6161footnotemark: 61
††footnotetext: https://avro.apache.org/docs/current/spec.html#binary_encoding††footnotetext: https://microsoft.github.io/bond/reference/cpp/compact__binary_8h_source.html††footnotetext: https://capnproto.org/encoding.html#packing††footnotetext: https://google.github.io/flatbuffers/flatbuffers_internals.html††footnotetext: https://developers.google.com/protocol-buffers/docs/encoding††footnotetext: https://github.com/apache/thrift/blob/master/doc/specs/thrift-compact-protocol.md Table 7: The schema-less binary serialization specifications, encodings and implementations discussed in this study. Specification |  Implementation
---|---
BSON |  Python bson (pip) 0.5.10
CBOR |  Python cbor2 (pip) 5.1.2
FlexBuffers |  flatc command-line tool 1.12.0
MessagePack |  json2msgpack command-line tool 0.6 with MPack 0.9dev
Smile |  Python pysmile (pip) 0.2
UBJSON |  Python py-ubjson (pip) 0.16.1

Figure 9: The binary serialization specifications discussed in this study
divided by whether they are purely JSON compatible (center), whether they
consider JSON compatibility but are a superset of JSON (right), or whether we
found them to be JSON compatible but that’s not one of their design goals
(left).

As part of this study, we chose not to discuss serialization specifications
that could not encode the _input data_ JSON document from Figure 10 without
significant changes, such as _Simple Binary Encoding_ (SBE)
626262https://github.com/real-logic/simple-binary-encoding and Apple’s _Binary
Property List_ (BPList)
636363https://opensource.apple.com/source/CF/CF-550/CFBinaryPList.c or that
could not be considered general-purpose serialization specifications, such as
_Java Object Serialization_
646464https://docs.oracle.com/javase/8/docs/platform/serialization/spec/serialTOC.html
and _YAS_ 656565https://github.com/niXman/yas. We also chose not to discuss
serialization specifications that remain unused in the industry at present,
such as _PalCom Object Notation_ (PON) [94] and as a consequence lack a well-
documented and usable implementation, such as _SJSON_ [4] and the _JSON-B_ ,
_JSON-C_ and _JSON-D_ family of schema-less serialization specifications [63].

Table 8: Each serialization specification report will include a summary reference table following this layout. Website |  The website address of the serialization specification project
---|---
Company / Individual |  The company or individual behind the serialization specification
Year |  The year the serialization specification was conceived
Specification |  A link or pointer to official specification of the serialization specification
License |  The software license used to release the specification and implementations
Schema Language |  The schema language used by the serialization specification, if schema-driven
Layout |  The overall structure of the bit-strings created by the serialization specification
Languages |  The programming languages featuring official and/or third-party implementations of the serialization specification
Types |  A brief description of the data types supported by the serialization specification

###  3.2 Input Data

Figure 10: The JSON test document that will be used as a basis for analyzing
various binary serialization specifications.

We designed a test JSON [42] document that is used to showcase the challenges
of serializing JSON [42] data and attempt to highlight the interesting aspects
of each selected serialization specification. The JSON document we created,
presented in Figure 10, has the following characteristics:

  * •

It contains an empty array, an empty object, and an empty string.

  * •

It contains nested objects and homogeneous and heterogeneous arrays.

  * •

It contains an array of scalars with and without duplicate values.

  * •

It contains an array of composite values with duplicate values.

  * •

It contains a set and an unset nullable string.

  * •

It contains positive and negative integers and floating-point numbers.

  * •

It contains true and false boolean values.

The _input data_ is not representative of every JSON document that the reader
may encounter in practice. We hope that the characteristics of the input data
and output demonstrate how serialization specifications perform with respect
to various JSON documents.

###  3.3 System Specification

The implementations of the serialization specifications were executed on a
MacBook Pro 13" Quad-Core Intel Core i7 2.7 GHz with 4 cores and 16 GB of
memory (model identifier MacBookPro15,2) running macOS Catalina 10.15.7, Xcode
11.3 (11C29), clang 1100.0.33.16, and Python 3.7.3.

##  4 Encoding Processes

###  4.1 Little Endian Base 128 Encoding

_Little Endian Base 128_ (LEB128) variable-length integer encoding stores
arbitrary large integers into a small variable amount of bytes. Decoders do
not need to know how large the integer is in advance. The LEB128 encoding was
introduced by the DWARF [126] debug data format and the concept of variable-
length integers in the context of serialization was popularized by the
Protocol Buffers [60] schema-driven serialization specification.

The encoding process consists of:

  * •

Obtaining the Big Endian binary representation of the input integer.

  * •

Padding the bit-string to make it a multiple of 7-bits.

  * •

Splitting the bit-string into 7-bits groups, prefixing the most-significant
7-bit group with a zero-bit.

  * •

Prefixing the remaining groups with set bits.

  * •

Storing the result as Little Endian.

The decoding process is the inverse of the encoding process. The decoder knows
when to stop parsing the variable-length integer bytes through the most-
significant bit in each group: the most-significant bit in the last byte is
equal to 0.

####  4.1.1 Unsigned Integer

In this example, we consider the unsigned integer $50399$ in Figure 11.

Figure 11: Little Endian Base 128 (LEB128) encoding of the unsigned 32-bit
integer $50399$.

The Big Endian unsigned integer representation of the number $50399$ is
16-bits wide. 16 is not a multiple of 7, therefore we left-pad the bit-string
with five zeroes to make it 21-bit wide. Then, we split the bit-string into
7-bit groups. Next, we prefix the most-significant group with 0 and the rest
of the groups with 1. The Little Endian representation of the bit-string
equals 0xdf 0x89 0x03 which is the Little Endian Base 128 (LEB128) encoding of
the unsigned integer $50399$ as shown in Figure 11.

####  4.1.2 Signed Integer Using Two’s Complement

The canonical approach to encoding signed integers using Little Endian Base
128 (LEB128) encoding is to apply Two’s Complement [51] and proceed as if the
integer is unsigned.

For example, consider the signed integer $-25200$ as shown in Figure 12.

Figure 12: Little Endian Base 128 (LEB128) encoding of the signed 32-bit
integer $-25200$.

###  4.2 ZigZag Integer Encoding

ZigZag integer encoding, pioneered by Protocol Buffers [60], is an approach to
map signed integers to unsigned integers. The goal of ZigZag integer encoding
is that the absolute values of the resulting unsigned integers are relatively
close to the absolute values of the original negative integers. In comparison,
Two’s Complement [51] converts negative integers into large unsigned integers.
The encoding works in a _zig-zag_ fashion between positive and negative
integers. ZigZag integer encoding does not affect the range of signed integer
values that can be encoded in a given number of bits. _Little Endian Base 128_
(LEB128) (4.1) variable-length integer encoding encodes unsigned integers
using a number of bytes that are proportial to the absolute value of the
unsigned integer. Therefore, ZigZag integer encoding results in space-
efficiency when encoding negative integers in combination with Little Endian
Base 128 (LEB128) encoding.

Figure 13: ZigZag integer encoding "zig-zags" between positive and negative
integers.

ZigZag Encoding:

  * •

Encode the signed integer using Two’s Complement [51].

  * •

Left-shift the bit-string by one position.

  * •

Right-shift the bit-string by the number of desired bits minus one.

  * •

Calculate the exclusive disjunction (XOR) between both bit-shifted bit-
strings.

ZigZag Decoding:

  * •

Right-shift the unsigned integer bit-string by one position.

  * •

Calculate the bitwise conjunction (AND) between the bit-string and $1$.

  * •

Calculate the Two’s Complement [51] of the result of negating the integer
represented by the bit-string.

  * •

Calculate the exclusive disjunction (XOR) between both numbers.

Alternative definition of ZigZag integer encoding is that positive integers
are multiplied by two. Negative integers are equal to their absolute values
multiplied by two, minus one. ZigZag integer decoding is the inverse of the
encoding process.

Figure 14:  A formal definition of ZigZag integer encoding using Z notation
[68]. We capture the relationship between the encoding and decoding functions
by stating that the functional composition of ZigZagDecode and ZigZagEncode
equals the identity function. Decoding an encoded integer equals the original
integer.

####  4.2.1 ZigZag Encoding

The formal definition from Figure 14 states that the ZigZag integer encoding
of the 32-bit signed negative integer $-25200$ is equal to
$(-25200<<1)\thinspace\oplus\thinspace(-25200>>31)$.

First, we calculate the Two’s Complement [51] of the 32-bit signed integer
$-25200$ which involves calculating the unsigned integer representation of its
absolute value, calculating its binary complement, and adding 1 to the result
as shown in Figure 15.

Figure 15: The Two’s Complement [51] of the 32-bit signed integer $-25200$ is
0xffff9d90.

Then, we left-shift 0xffff9d90 by one position and right-shift 0xffff9d90 by
31 positions (32-bits minus 1) as shown in Figure 16.

Figure 16: Bit-shifting the Two’s Complement [51] of the 32-bit signed integer
$-25200$ as per the formal definition of ZigZag integer encoding from Figure
14.

Finally, we calculate the exclusive disjunction (XOR) between the two
hexadecimal strings obtained before as shown in Figure 17.

Figure 17: The exclusive disjunction (XOR) between 0xffff3b20 and 0xffffffff
results in 0x0000c4df.

Therefore, the ZigZag integer encoding of the signed 32-bit integer $-25200$
is 0x0000c4df, which is the 32-bit unsigned integer $50399$.

####  4.2.2 ZigZag Decoding

The formal definition from Figure 14 states that the ZigZag integer decoding
of the bit-string 0x0000c4df we obtained in subsubsection 4.2.1 is equal to
$(\texttt{0x0000c4df}>>1)\oplus-(\texttt{0x0000c4df}\land 1)$.

First, we right-shift 0x0000c4df by one position as shown in Figure 18.

Figure 18: Righ-shifting the ZigZag integer encoding of the 32-bit signed
integer $-25200$ by one position results in 0x0000626f.

Then, we calculate the bitwise conjunction (AND) between 0x0000c4df and
0x00000001 as shown in Figure 19.

Figure 19: The bitwise conjunction (AND) between 0x0000c4df and 0x00000001
results in 0x00000001.

Next, we calculate the Two’s Complement [51] of -0x00000001 as shown in Figure
20.

Figure 20: The Two’s Complement [51] of -0x00000001 is 0xffffffff.

Finally, we calculate the exclusive disjunction (XOR) between 0x0000626f and
0xffffffff as shown in Figure 21.

Figure 21: The exclusive disjunction (XOR) between 0x0000626f and 0xffffffff
results in 0xffff9d90.

The result is 0xffff9d90 which is the Two’s Complement [51] of the negative
32-bit signed integer $-25200$.

##  5 Schema-driven Specifications

###  5.1 ASN.1

Figure 22: Hexadecimal output (xxd) of encoding Figure 10 input data with
ASN.1 PER Unaligned (44 bytes).

History. ASN.1 [119] is a standard schema language used to serialize data
structures using an extensible set of schema-driven encoding rules. ASN.1 was
originally developed in 1984 as a part of the [118] standard and became a
International Telecommunication Union recommendation and an ISO/IEC
international standard [133] in 1988. The ASN.1 specification is publicly
available 666666https://www.itu.int/rec/T-REC-X.680/en and there are
proprietary and open source implementations of its standard encoding rules.
The ASN.1 PER Unaligned encoding rules were designed to produce space-
efficient bit-strings while keeping the serialization and deserialization
procedures reasonably simple.

Characteristics.

  * •

Robustness. ASN.1 is a mature technology that powers some of the highest-
integrity communication systems in the world
676767https://www.itu.int/en/ITU-T/asn1/Pages/Application-fields-of-ASN-1.aspx
686868https://www.oss.com/asn1/resources/standards-use-asn1.html such as Space
Link Extension Services (SLE) [27] communication services for spaceflight and
the LTE S1 signalling service application protocol [2]. Refer to [136] for an
example of formal verification of the encoding/decoding code produced by an
ASN.1 PER Unaligned compiler (Galois 696969https://galois.com) in the
automobile industry.

  * •

Standardization. In comparison to informally documented serialization
specification, ASN.1 is specified as a family of ITU Telecommunication
Standardization Sector (ITU-T) recommendations and ISO/IEC international
standards and has gone through extensive technical review.

  * •

Flexible Encoding Rules. ASN.1 supports a wide range of standardised encodings
for different use cases: BER (Basic Encoding Rules) based on tag-length-value
(TLV) nested structures [121], DER (Distinguished Encoding Rules) and CER
(Canonical Encoding Rules) [121] for restricted forms of BER [121], PER
(Packed Encoding Rules) for space-efficiency [120], OER (Octet Encoding Rules)
for runtime-efficiency [132], JER (JSON Encoding Rules) for JSON encoding
[135], and XER (XML Encoding Rules) for XML encoding [134].

Layout. An ASN.1 PER Unaligned bit-string is a sequence of untagged values,
sometimes nested where the ordering of the values is determined by the schema.
ASN.1 PER Unaligned encodes values in as few bits as reasonably possible and
does not align values to a multiple of 8 bits as the name of the encoding
implies. ASN.1 PER Unaligned only encodes runtime information that cannot be
inferred from the schema, such as the length of the lists or union type.

ASN.1 PER Unaligned encodes unbounded data types and bounded data types whose
logical upper bound is greater than 65536 using a technique called
_fragmentation_ where the encoding of the value consists of one or more
consecutive fragments each consisting of a length prefix followed by a series
of items. The nature of each item depends on the type being encoded. For
example, an item might be a character, a bit, or a logical element of a list.
A value encoded using fragmentation consists of 0 or more fragments of either
16384, 32768, 49152, or 65536 items followed by a single fragment of 0 to
16383 items where each fragment is as large as possible and no fragment is
larger than the preceding fragment. Refer to Table 9 for details on fragment
length prefix encoding.

Table 9: ASN.1 PER Unaligned fragment length prefixes depending on the number of items in the fragment as determined by the _From_ and _To_ ranges. From | To |  Fragment prefix
---|---|---
0 | 127 |  Length as an 8-bit unsigned integer
128 | 16383 |  Length as the 2-bits 10 followed by a Big Endian 14-bit unsigned integer
16384 | 16384 |  1100 0001
32768 | 32768 |  1100 0010
49152 | 49152 |  1100 0011
65536 | 65536 |  1100 0100

Numbers. ASN.1 PER Unaligned supports integer data types of arbitrary widths.
The schema-writer may constraint the integer data type with a lower and upper
bound:

  * •

If the integer type has no bounds or if the integer type only has an upper
bound. ASN.1 PER Unaligned encodes the value as a Big Endian Two’s Complement
[51] signed integer prefixed by its byte-length as a unsigned 8-bit integer.

  * •

If the integer type has a lower bound but not an upper bound. ASN.1 PER
Unaligned substracts the lower bound from the value and encodes the result as
a variable-length Big Endian unsigned integer prefixed by its byte-length as a
unsigned 8-bit integer. For example, the value $-18$ of an integer type whose
lower bound is $-20$ is encoded as the unsigned integer $2=-18-(-20)$ prefixed
with the byte-length definition 0x01.

  * •

If the integer type has both a lower and an upper bound. ASN.1 encodes the
difference between the value and the lower bound using the smallest possible
fixed-length Big Endian unsigned integer that can encode the difference
between the upper and the lower bound. For example, an integer type
constrained between the values 5 and 6 encodes the values as an unsigned 2-bit
integer where 0 corresponds to 5 and 1 corresponds to 6.

In terms of real numbers, ASN.1 PER Unaligned does not support IEEE 764
floating-point numbers [52]. Instead, ASN.1 PER Unaligned encodes a real
numbers as concatenation of its sign, base, scale, exponent, and mantissa
where the real value equals $\textbf{sign}\times\textbf{mantissa}\times
2^{\textbf{scale}}\times\textbf{base}^{\textbf{exponent}}$. Refer to Figure 23
for details on the encoding.

Figure 23: A visual representation of the REAL data type encoding inspired by
[41], page 401. ASN.1 PER Unaligned encodes a real number as an 8-bit unsigned
integer representing the byte-length of the real number, the sign (positive or
negative) as 1-bit, the base as 2-bits (binary, octal, or hexadecimal), the
scale as 2-bits (0, 1, 2, or 3), the exponent as a variable-length signed
integer prefixed by its byte-length, and the mantissa as a Big Endian
variable-length unsigned integer whose width is bounded by the data type
length prefix.

Strings. ASN.1 supports a rich set of string types that are not _NUL_
-delimited. The IA5String represents the full ASCII [28] range. The
VisibleString subtype represents the subset of ASCII [28] that does not
include control characters. The NumericString subtype represents digits and
spaces. Finally, the UTF8String represents Unicode strings that are encoded in
UTF-8 [33]. Schema-authors may subtype the supported string types to contrain
the permitted alphabet. In the case of unconstrained string types and
constrained string subtypes whose permitted alphabet contains more than 64
characters, each character is represented by its standard codepoint.
Otherwise, ASN.1 PER Unaligned creates an ordered list of permitted characters
(its alphabet) and encodes each character as an index of such list represented
using the smallest possible Big Endian unsigned integer that can represent the
set of permitted characters. ASN.1 PER Unaligned encodes strings using
_fragmentation_ when using string types in which the byte-length of the string
is not always a multiple of the logical length of the string like UTF8String,
when the string type has no size upper bound, or when the string type has a
size upper bound which is greater than 65536. Otherwise, the string is
prefixed with the string logical length as a bounded integer encoded as
described in the _Numbers_ section whose lower and upper bounds correspond to
the size bounds of the string type.

Booleans. ASN.1 PER Unaligned encodes booleans as the bit constants $0$
(False) and $1$ (True).

Enumerations. ASN.1 PER Unaligned represents enumeration constants using the
smallest Big Endian unsigned integer width that can encode the range of values
in the enumeration.

Unions. ASN.1 supports a union operator called CHOICE. ASN.1 PER Unaligned
prefixes the encoded value with the index to the choice in the union data type
as the smallest-width Big Endian unsigned integer that can represent the
available choices. ASN.1 also supports the concept of an _open type_. An open
type is a container that holds an arbitrary value of a type known by the
serializer and the deserializer applications. An open type is encoded as the
encoding of the arbitrary value using _fragmentation_. ASN.1 PER Unaligned
does not encode the type of the arbitrary value. Therefore, the byte length
information allows a deserializer to skip the field if it does not know how to
decode it.

Lists. ASN.1 PER Unaligned supports an heterogeneous list type called SEQUENCE
and an homogeneous list type called SEQUENCE OF. Both sequence types can be
bounded or unbounded. Unbounded sequences are encoded using _fragmentation_
and empty unbounded sequences are encoded as an empty fragment. Bounded lists
are encoded as the sequence of its elements with no length metadata. If an
heterogeneous sequence (SEQUENCE) contains $N$ optional values, then the
sequence is prefixed by a sequence of $N$ bits that determine whether each
optional value is set.

Figure 24: ASN.1 schema to serialize the Figure 10 input data.

Figure 25: Annotated hexadecimal output of serializing the Figure 10 input data with ASN.1 PER Unaligned. Table 10: A high-level summary of the ASN.1 PER Unaligned schema-driven serialization specification. Website |  https://www.itu.int/rec/T-REC-X.680/en
---|---
Company / Individual |  International Telecommunication Union
Year |  1984
Specification |  ITU-T X.680-X.693 [119]
License |  Implementation-dependent
Schema Language |  ASN.1
Layout |  Sequential and order-based
Languages |  C, C++, C#, Java, Ada/Spark, Python, Erlang
Types
Numeric |  Big Endian Two’s Complement [51] signed integers of user-defined length Big Endian unsigned integers of user-defined length Real numbers consisting of up to 255 bytes encoding the base, scale, exponent, and mantissa Arbitrary-length ASCII-encoded decimal numbers
String |  ASCII [28], UTF-8 [33]
Composite |  Choice, Enum, Set, Sequence
Scalars |  Boolean, Null
Other |  Octet string (byte array) Bit-string (arbitrary-length bit array) Date, Time, Date-time [70]

###  5.2 Apache Avro

Figure 26: Hexadecimal output (xxd) of encoding Figure 10 input data with
Apache Avro Binary Encoding with no framing (56 bytes).

History. Apache Avro [53] is a schema-driven binary serialization
specification introduced by Douglass Cutting 707070https://github.com/cutting
during 2009 while working at Yahoo! 717171https://yahoo.com/. Apache Avro is
part of the Apache Hadoop 727272https://hadoop.apache.org framework and is
also deeply integrated with other projects from the Big Data field such as
Apache Spark 737373http://spark.apache.org/index.html and Apache Kafka
747474https://kafka.apache.org. Apache Avro is part of the Apache Software
Foundation 757575https://www.apache.org and its released under the Apache
License 2.0 767676http://www.apache.org/licenses/LICENSE-2.0.html. [3]
provides a detailed discussion of the role of the Apache Software Foundation
in the Big Data industry including Apache Avro.

Characteristics.

  * •

Optional Code Generation. Apache Avro implementations can perform
serialization and deserialization by taking the input schema at runtime. This
enables programs to work with new types of data without a recompilation step.
In comparison, schema-driven serialization specifications such as Apache
Thrift [127] require a code generation step at build time for each schema.

  * •

Compactness. Apache Avro Binary Encoding with no framing produces considerably
space-efficient bit-strings as it only encodes minimal metadata
777777https://avro.apache.org/docs/current/spec.html.

Layout. An Apache Avro Binary Encoding with no framing bit-string is a
sequence of values, sometimes nested. The ordering of the values is determined
by the schema. Apache Avro Binary Encoding only encodes runtime information
that cannot be inferred from the schema, such as the length of the lists or
union type information. Fields are encoded even if they equal their default
values.

Numbers. Apache Avro Binary Encoding supports 32-bit and 64-bit ZigZag-encoded
(4.2) Little Endian Base 128 (LEB128) (4.1) signed integers. In terms of real
numbers, Apache Avro Binary Encoding supports Little Endian 32-bit and 64-bit
IEEE 764 floating-point numbers [52] and arbitrary-precision signed decimal
numbers. Arbitrary-precision signed decimal numbers are encoded using
variable-length or fixed-length byte arrays. The byte array represents a Big
Endian signed integer using Two’s Complement [51] whose width is defined by
the byte array length prefix. The schema declares the scale and precision as
integers. The resulting decimal number equals the unscaled integer multiplied
by $10^{-\text{scale}}$. The precision integer determines the maximum number
of decimals stored in the data type.

Strings. Apache Avro Binary Encoding strings are encoded using UTF-8 [33]
without _NUL_ delimiters. Apache Avro Binary Encoding prefixes strings with
64-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128) (4.1) variable-
length signed integers that represent the number of code-points in the string.
Empty strings are encoded with a length prefix of 0 with no following
characters. Apache Avro Binary Encoding does not attempt to deduplicate
multiple occurrences of the same string.

Booleans. Apache Avro Binary Encoding encodes booleans using the byte
constants 0x00 (False) and 0x01 (True).

Enumerations. Apache Avro Binary Encoding represents enumeration constants
using 32-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128) (4.1)
variable-length signed integers.

Unions. An Apache Avro schema may declare an ordered list of potential types
for a single field. In these cases, Apache Avro Binary Encoding prefixes the
value with a 32-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128) (4.1)
variable-length signed integer that corresponds to an index of the ordered
list of types. Refer to Figure 27 for a visual example.

Figure 27: A field consisting of more than one possible type is encoded as the
type index followed by the data, if any. For example, if the schema defines a
field whose type is [ "string", "int", "null" ], then the value will be
prefixed with 0x00 if the value is a string, with 0x02 (the ZigZag-encoded
(4.2) integer $1$) if the value is an integer, or with 0x04 (the ZigZag-
encoded (4.2) integer $2$) if the value is null.

Lists. Apache Avro Binary Encoding encodes a list (array) as a series of
blocks. Each block is prefixed with its logical size as a 64-bit ZigZag-
encoded (4.2) Little Endian Base 128 (LEB128) (4.1) variable-length signed
integer followed by its elements in order. As a runtime optimization, if the
logical size signed integer is negative, then the block size is the absolute
value of the integer and the sequence of elements is further prefixed with the
byte-length of the block as another 64-bit ZigZag-encoded (4.2) Little Endian
Base 128 (LEB128) (4.1) variable-length signed integer. Apache Avro Binary
Encoding does not attempt to deduplicate multiple occurrences of the same
element in an array.

Figure 28: Apache Avro schema to serialize the Figure 10 input data.

Figure 29: Annotated hexadecimal output of serializing the Figure 10 input data with Apache Avro Binary Encoding with no framing. Table 11: A high-level summary of the Apache Avro Binary Encoding with no framing schema-driven serialization specification. Website |  https://avro.apache.org
---|---
Company / Individual |  Apache Software Foundation
Year |  2009
Specification |  https://avro.apache.org/docs/current/spec.html
License |  Apache License 2.0
Schema Language |  Avro IDL
Layout |  Sequential and order-based
Languages |  C, C++, C#, Java
Types
Numeric |  32-bit and 64-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128) (4.1) variable-length integers Arbitrary-precision Two’s Complement [51] signed decimal numbers Little Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  Array, Enum, Map, Record, Union
Scalars |  Boolean, Null
Other |  Bytes (variable-length byte array) Fixed (fixed-length byte array) UUID [81] Date (days from the UNIX Epoch) [90] Time (milliseconds and microseconds) [70] Timestamp (milliseconds and microseconds) [90] Duration 787878https://avro.apache.org/docs/current/spec.html#Duration

###  5.3 Microsoft Bond

Figure 30: Hexadecimal output (xxd) of encoding Figure 10 input data with
Microsoft Bond Compact Binary version 1 (77 bytes).

History. Microsoft Bond [88] is an RPC protocol and schema-driven
serialization specification developed by Microsoft in 2011 and was made open-
source in 2015. The Microsoft Bond project was started by Adam Sapek
797979https://github.com/sapek, a Principal Software Engineer at Microsoft
Research, while working on the Microsoft Bing 808080https://www.bing.com
search engine. Microsoft Bond is used at the core of many Microsoft services
and it is released under the MIT license
818181https://opensource.org/licenses/MIT.

Characteristics.

  * •

Rich Type System. The Microsoft Bond schema language supports generic types,
inheritance and a wide range of scalar and composite data types such as sets
and nullable types.

  * •

Custom Type Mappings. To ease integration, Microsoft Bond supports statically
mapping the types supported by the schema language to any compatible
programming language type.

  * •

Opt-in Lazy Deserialization. For runtime-performance reasons, the Microsoft
Bond schema language supports marking certain fields to not be de-serialized
automatically. These fields can be de-serialized when needed or omitted
altogether.

Layout. A Microsoft Bond Compact Binary version 1 (v1) bit-string is a
sequence of values, sometimes nested. Each value is prefixed with a type
definition and the length of the value, where applicable. Each value has a
numeric identifier that must be unique on the current nesting level. Microsoft
Bond Compact Binary v1 only encodes a field if the field is required or if its
value is not equal to the default hence resulting in efficient use of space.

Types. A Microsoft Bond Compact Binary v1 type definition consist of an
positive absolute unique identifier integer and a type identifier constant as
shown in footnote 83. Microsoft Bond Compact Binary v1 defines three type
definition encodings depending on the length of the unique identifier. Refer
to Table 12.

Table 12: The three type definition encodings that Microsoft Bond Compact Binary v1 supports depending on the value of the unique field identifier as determined by the _From_ and _To_ ranges. Note that Microsoft Bond Compact Binary v1 cannot encode unique field identifiers larger than 65535. From | To | Size |  First 3-bits |  Next 5-bits |  Remaining bits
---|---|---|---|---|---
0 | 5 | 1 byte |  The unique identifier as a 3-bit unsigned integer |  The field type identifier constant as shown in footnote 83 |  None
6 | 255 | 2 bytes |  110 |  The field type identifier constant as shown in footnote 83 |  The unique identifier as an 8-bit unsigned integer
256 | 65535 | 3 bytes |  111 |  The field type identifier constant as shown in footnote 83 |  The unique identifier as a Big Endian 16-bit unsigned integer

Figure 31: Microsoft Bond type identifiers definition
838383https://github.com/microsoft/bond/blob/8d0fe6c00cbcd7ea9c54b1f1e947174caff596e4/idl/bond/core/bond_const.bond.

Microsoft Bond schemas can instruct implementations to not de-serialize a
field automatically by marking the field as _bonded_ at the schema level.
Instead, the consumer de-serializes _bonded_ fields when and if needed by the
application. This results in runtime efficiency.

Numbers. Microsoft Bond Compact Binary v1 supports Little Endian IEEE 764
32-bit and 64-bit floating point-numbers [52]. In terms of integers, Microsoft
Bond Compact Binary v1 supports Little Endian 8-bit fixed-length unsigned
integers, 16-bit, 32-bit, and 64-bit Little Endian Base 128 (LEB128) (4.1)
variable-length unsigned integers, 8-bit fixed-length signed integers with
Two’s Complement [51], and 16-bit, 32-bit, and 64-bit Little Endian Base 128
(LEB128) (4.1) variable-length ZigZag-encoded (4.2) signed integers.

Strings. Microsoft Bond can produce strings with UTF-8 and Little Endian
UTF-16 encodings [33] without _NUL_ delimiters. Refer to the BT_STRING and
BT_WSTRING data types from footnote 83. Each string is prefixed with a 32-bit
Little Endian Base 128 (LEB128) (4.1) variable-length unsigned integer
determining the number of code-points in the string. Microsoft Bond Compact
Binary v1 does not attempt to deduplicate multiple occurrences of the same
string.

Booleans. Microsoft Bond Compact Binary v1 encodes booleans using the 1-byte
constants 0x00 (False) and 0x01 (True).

Enumerations. Microsoft Bond Compact Binary v1 represents enumeration
constants using 32-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128)
(4.1) variable-length signed integers.

Unions. Microsoft Bond supports the _nullable_ type union. Nullable fields are
encoded as lists of zero or one value. Refer to Figure 32 for a visual
example. Microsoft Bond Compact Binary v1 does not encode unset optional
fields. Therefore schema-writers can approximate unions by defining a
structure containing multiple fields and ensuring that only one of them is set
at a time. Another common pattern to approximate unions is to rely on
polymorphism and bonded types. In this case, a schema-writer could define a
base structure including a single field: an enumeration denoting the union
choice and extend the base structure with subclasses defining each of the
choices. Other structures refer to the union structure as a bonded field, so
that the client can first deserialize the enumeration and then deserialize the
rest of the fields depending on the enumeration constant value. The serializer
program is responsible for correctly setting the enumeration constant. In
footnote 85, a heterogeneous list using this technique is shown.

Figure 32: A visual representation of Microsoft Bond Compact Binary v1
_nullable_ types. If the value is _NULL_ (top), then it is encoded as the type
definition followed by the length 0x00. If the value is not null (bottom),
then it is encoded as the type definition followed by the length 0x01,
followed by the value.

Figure 33: An adapted example of a polymorphic list definition
858585https://github.com/microsoft/bond/blob/8d0fe6c00cbcd7ea9c54b1f1e947174caff596e4/examples/cpp/core/polymorphic_container/polymorphic_container.bond.

Lists. Microsoft Bond Compact Binary v1 encodes a list as the type definition,
followed by the list definition, followed by the elements encoded in order.
The list definition consists in a byte where the five least-significant bits
encode the element type identifier constant as shown in footnote 83 followed
by the length of the list as a 32-bit Little Endian Base 128 (LEB128) (4.1)
variable-length unsigned integer. Microsoft Bond Compact Binary v1 does not
attempt to deduplicate multiple occurrences of the same element in a list.

Figure 34: Microsoft Bond schema to serialize the Figure 10 input data.

Figure 35: Annotated hexadecimal output of serializing the Figure 10 input data with Microsoft Bond Compact Binary v1. Table 13: A high-level summary of the Microsoft Bond Compact Binary v1 schema-driven serialization specification. Website |  https://microsoft.github.io/bond/
---|---
Company / Individual |  Microsoft
Year |  2011
Specification |  https://microsoft.github.io/bond/reference/cpp/compact__binary_8h_source.html
License |  MIT
Schema Language |  Bond IDL
Layout |  Sequential with field identifiers
Languages |  C++, C#, Java, Python
Types
Numeric |  16-bit, 32-bit, and 64-bit Little Endian Base 128 (LEB128) (4.1) variable-length unsigned integers 16-bit, 32-bit, and 64-bit ZigZag-encoded (4.2) Little Endian Base 128 (LEB128) (4.1) variable-length signed integers Fixed-length 8-bit unsigned integers Fixed-length 8-bit Two’s Complement [51] signed integers Little Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8, Little Endian UTF-16 [33]
Composite |  List, Maybe, Nullable, Set, Struct, Vector
Scalars |  Boolean
Other |  Blob (byte array)

###  5.4 Cap’n Proto

Figure 36: Hexadecimal output (xxd) of encoding Figure 10 input data with
Cap’n Proto Packed Encoding (83 bytes).

History. Cap’n Proto [143] is an RPC protocol and schema-driven binary
serialization specification created in 2013 by Kenton Varda
868686https://github.com/kentonv, the primary author of Protocol Buffers [60]
version 2, while working as a Technology Lead at Sandstorm
878787https://sandstorm.io. Cap’n Proto is designed to support memory-
efficient serialization and deserialization. Cap’n Proto is extensively used
at Sandstorm and at high-profile companies such as Cloudflare
888888https://www.cloudflare.com, where Kenton Varda is currently employed as
a Principal Engineer. Cap’n Proto is released under the MIT license
898989https://opensource.org/licenses/MIT.

Characteristics.

  * •

Efficient Reads. Cap’n Proto produces implementations that perform runtime-
efficiency and memory-efficient incremental and random-access reads as noted
by [156].

  * •

Small Code Footprint. Cap’n Proto includes a small runtime library with
minimal dependencies and generates small amounts of serialization and
deserialization code.

Layout. A Cap’n Proto bit-string consist of a tree hierarchy of pointers that
eventually points at scalar types. These pointers are scattered across the
bit-string close to the data that they point to for cache locality purposes.
For runtime-performance reasons, Cap’n Proto values are aligned to 64-bit
words. As a consequence, Cap’n Proto bit-strings tend to contain significant
zero-byte padding. As a solution, Cap’n Proto defines a simple compression
scheme called _Packed Encoding_ where each 64-bit word in the bit-string is
replaced by a tag byte followed by up to 8 content bytes. The position of the
bits set in the tag byte determines the location of each content byte in the
uncompressed 64-bit word. Refer to Figure 37 for a visual example.
Additionally, Cap’n Proto Packed Encoding compresses sequences of zero-byte
64-bit using the 0x00 byte followed by the amount of zero-byte 64-bit words
minus 1 as an 8-bit unsigned integer. The compression scheme can encode
unpacked data prefixing the unpacked 64-bit word with the 0xff byte and
suffixing it with the amount of unpacked words to follow as an 8-bit unsigned
integer.

Figure 37: Cap’n Proto Packed Encoding compresses a 64-bit word by encoding a
tag byte where its bits represent the unpacked bytes followed by up to 8
content bytes. The number of content bytes equal the number if bits set in the
tag byte. If the bit from the tag byte is zero, the corresponding unpacked
byte is zero. If the bit from the tag byte is set, then the byte is the
corresponding unpacked byte following the tag byte.

Cap’n Proto structures consist of a 64-bit type definition, followed by N
64-bit words of scalar values, followed by M 64-bit pointers to composite
values. The structure type definition and the remaining 64-bit words do not
need to be contiguous in memory as the most-significant 30-bits of the
structure type definition consists of a pointer to the data section. The next
2-bits equal $00$ to declare that the type definition corresponds to a
structure. The remaining 32-bits encode two Little Endian 16-bit unsigned
integers corresponding to the word-lengths of the data and pointer sections,
respectively.

Numbers. Cap’n Proto supports Little Endian IEEE 754 32-bit and 64-bit
floating-point numbers [52]. In terms of integers, Cap’n Proto supports Little
Endian 8-bit, 16-bit, 32-bit, and 64-bit unsigned integers and Little Endian
8-bit, 16-bit, 32-bit, and 64-bit Two’s Complement [51] signed integers.

Strings. Cap’n Proto encodes strings as lists of UTF-8 [33] characters. Cap’n
Proto strings are delimited with the _NUL_ ASCII [28] character. However, the
_NUL_ character is typically packed by the Cap’n Proto word compression
scheme. The list definition corresponding to the string encodes the byte-
length of the string as a Little Endian 30-bit unsigned integer. Cap’n Proto
does not attempt to deduplicate multiple occurrences of the same string.

Booleans. Cap’n Proto encodes booleans as the bits $0$ (False) or $1$ (True)
aligned to a multiple of their size on the structure they are defined in.

Enumerations. Cap’n Proto represents enumeration constants using aligned
Little Endian 16-bit unsigned integers. As a consequence, Cap’n Proto does not
support negative enumeration constants.

Unions. Cap’n Proto relies on unique field identifiers to implement union
types. Each alternative in the union type must have a different field
identifier and Cap’n Proto enforces that only one of such unique field
identifiers is present at a given time. Cap’n Proto prefixes the encoded value
with an 8-bit unsigned integer that determines the corresponding union field
identifier.

Lists. Cap’n Proto encodes lists as a 64-bit list type definition with the
elements encoded in order. The list type definition and the list elements do
not need to be contiguous in memory. Cap’n Proto does not attempt to
deduplicate multiple occurrences of the same value in a list. Cap’n Proto
defines two list type definition encodings depending on whether the elements
are scalar or composite as shown in Table 14.

Table 14: The two 64-bit list type definition encodings supported by Cap’n Proto depending on whether the elements of the list are scalar or composite values. Element type |  First 30-bits |  Next 2-bits |  Next 29-bits |  Remaining 3-bits
---|---|---|---|---
Scalar |  Pointer to the start of the list |  01 |  Number of elements in the list as a Little Endian 29-bit unsigned integer |  The element length definition as a 3-bit unsigned integer as shown in footnote 91
Composite |  Pointer to the composite tag word definition |  01 |  Number of 64-bit words in the list as a Little Endian 29-bit unsigned integer |  111

If the list consists of composite elements, then the list definitions points
at a 64-bit word that describes each element. This 64-bit word starts with the
number of elements in the list as a Little Endian 30-bit unsigned integer,
followed by the 2-bit constant 00, followed by the number of 64-bit scalar
words in the element as a Little Endian 16-bit unsigned integer, followed by
the number of 64-bit pointers in the element as another Little Endian 16-bit
unsigned integer.

Figure 38: Cap’n Proto list element size definitions
919191https://github.com/capnproto/capnproto/blob/bbea19f0e0b2ee1ed28d0836b778d8cf3995597d/c%2B%2B/src/capnp/common.h.

Figure 39: Cap’n Proto schema to serialize the Figure 10 input data.

Figure 40: Annotated hexadecimal output of serializing the Figure 10 input data with Cap’n Proto Packed Encoding. Table 15: A high-level summary of the Cap’n Proto schema-driven serialization specification. Website |  https://capnproto.org
---|---
Company / Individual |  Sandstorm
Year |  2013
Specification |  https://capnproto.org/encoding.html
License |  MIT
Schema Language |  Cap’n Proto IDL
Layout |  Pointed-based and order-based
Languages |  C, C++, C#, D, Erlang, Go, Haskell, Java, JavaScript, Lua, Nim, OCaml, Python, Ruby, Rust, Scala
Types
Numeric |  Little Endian 8-bit, 16-bit, 32-bit, and 64-bit Two’s Complement [51] signed integers Little Endian 8-bit, 16-bit, 32-bit, and 64-bit unsigned integers Little Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  Enum, List, Struct, Union
Scalars |  Bool, Void
Other |  Data (byte array)

###  5.5 FlatBuffers

Figure 41: Hexadecimal output (xxd) of encoding Figure 10 input data with
FlatBuffers Binary Wire Format (208 bytes).

History. FlatBuffers [140] is a schema-driven serialization specification
created at Google in 2014 by the _Fun Propulsion Labs_ (FPL) group whose
mission was to improve game-related technologies for Android. FlatBuffers has
been designed to support memory-efficient serialization and deserialization in
the context of games and mobile. The project was started by Wouter van
Oortmerssen 929292https://github.com/aardappel, a Software Engineer at Google,
and was released under the Apache License 2.0
939393http://www.apache.org/licenses/LICENSE-2.0.html. FlatBuffers is also
used in the context Machine Learning as part of the TensorFlow Lite
949494https://www.tensorflow.org/lite/api_docs/cc/class/tflite/flat-buffer-
model framework for mobile and IoT devices developed by Google [138] and in
the DOS spatial system [104].

Characteristics.

  * •

Efficient Reads. FlatBuffers produces implementations that perform runtime-
efficiency and memory-efficient incremental and random-access reads as noted
by [111], [11], [109], [101], and [72]. Given its efficient deserialization
process, [137] proposes FlatBuffers as the specification in a system
architecture for data and video streaming with unmanned aerial vehicles for
natural disaster management.

  * •

Small Code Footprint. FlatBuffers includes a small runtime library with
minimal dependencies and generates small amounts of serialization and
deserialization code.

Layout. A FlatBuffers Binary Wire Format bit-string consist of a tree
hierarchy of 32-bit relative pointers that eventually point at scalar types. A
FlatBuffers bit-string starts with a pointer to the root element. The
FlatBuffers core data structure is a _Table_. A FlatBuffers Table is an
ordered sequence of aligned values prefixed with a pointer to a _vTable_
structure that defines the layout of the Table. A vTable consist of two Little
Endian 16-bit unsigned integers describing the byte-lengths of the vTable and
the Table. The size declarations are followed by a sequence of Little Endian
16-bit unsigned integer offsets to each element in the Table relative to the
vTable pointer. Refer to Figure 42 for a visual example. As a space
optimisation, multiple Tables sharing the same layout may point to the same
vTable. FlatBuffers does not encode values that equal their default.

Figure 42: A Table is an aligned sequence of values. Tables are prefixed with
a pointer to a _vTable_ structure that defines the layout of the Table by
specifying the offsets to each element.

As an alternative to Tables, FlatBuffers supports the concept of _structs_. A
struct is a more space-efficient alternative to a Table, however a struct can
only include scalar values and other structs, and lacks the versioning and
extensibility features of a Table. FlatBuffers encodes structs as the sequence
of its members aligned to the largest scalar element it contains.

Numbers. FlatBuffers supports Little Endian IEEE 754 32-bit and 64-bit
floating-point numbers [52]. In terms of integers, FlatBuffers supports Little
Endian 8-bit, 16-bit, 32-bit and 64-bit unsigned integers and Little Endian
8-bit, 16-bit, 32-bit and 64-bit Two’s Complement [51] signed integers.

Strings. FlatBuffers produces _NUL_ -delimited UTF-8 [33] strings. FlatBuffers
strings are prefixed with a Little Endian 32-bit unsigned integer that
represents the byte-length of the string without taking the _NUL_ delimiter
into consideration. Empty strings are encoded with a length 0 followed by the
_NUL_ character. By default, FlatBuffers does not attempt to deduplicate
multiple occurrences of the same string. However, its serialization interface
allows the application to track and share duplicated string values.

Booleans. FlatBuffers encodes booleans as the Little Endian unsigned integers
$0$ (False) and $1$ (True) aligned to their own size.

Enumerations. FlatBuffers lets the schema-writer decide the data type to
represent enumeration constants. A common choice is the byte type that
represents an 8-bit signed Two’s Complement [51] integer.

Unions. FlatBuffers encodes union data types as the combination of two fields:
an enumeration that represents the union alternative choices and the offset to
the union value. FlatBuffers reserves the union identifier $0$ to mean that
the value is not set. FlatBuffers unions do not support scalar data types.
However, a FlatBuffers union may include a _struct_ consisting of a single
scalar value encoded with no space overhead.

Lists. A FlatBuffers list (vector) consists of the concatenation of its
elements prefixed by the logical size of the vector as a Little Endian 32-bit
unsigned integer. A vector of composite elements is encoded as a list of
32-bit pointers. By default, FlatBuffers does not attempt to deduplicate
multiple occurrences of the same element in a vector. However, its
serialization interface allows the application to track and share duplicated
vector composite elements.

Figure 43: FlatBuffers schema to serialize the Figure 10 input data.

Figure 44: Annotated hexadecimal output of serializing the Figure 10 input data with FlatBuffers Binary Wire Format. Table 16: A high-level summary of the FlatBuffers Binary Wire Format schema-driven serialization specification. Website |  https://google.github.io/flatbuffers/
---|---
Company / Individual |  Google
Year |  2014
Specification |  https://google.github.io/flatbuffers/flatbuffers_internals.html
License |  Apache License 2.0
Schema Language |  FlatBuffers IDL
Layout |  Pointer-based and order-based
Languages |  C, C++, C#, Go, Java, Kotlin, JavaScript, Lobster, Lua, TypeScript, PHP, Python, Rust, Swift
Types
Numeric |  Little Endian 8-bit, 16-bit, 32-bit, and 64-bit unsigned integers Little Endian 8-bit, 16-bit, 32-bit, and 64-bit Two’s Complement [51] signed integers Little Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  Array, Enum, Struct, Table, Union, Vector
Scalars |  Boolean

###  5.6 Protocol Buffers

Figure 45: Hexadecimal output (xxd) of encoding Figure 10 input data with
Protocol Buffers Binary Wire Format (64 bytes).

History. Protocol Buffers [60] is an RPC protocol and schema-driven binary
serialization specification developed by Google in 2001
959595https://developers.google.com/protocol-buffers/docs/faq and open-sourced
under the 3-clause BSD license
969696https://opensource.org/licenses/BSD-3-Clause in 2008
979797https://opensource.googleblog.com/2008/07/protocol-buffers-googles-
data.html. Protocol Buffers was initially maintained by Jon Skeet
989898https://github.com/jskeet, a Staff Software Engineer at Google. Google
uses Protocol Buffers for nearly all of its storage and transmission needs.

Related Literature. Protocol Buffers has been extensively optimized in the
context of data centers. [102] further improve runtime efficiency of the
official Protocol Buffers C++ implementation using hardware acceleration
through a programmed co-processor. [78] describes _ProtoML_ , a tool that
takes complex constrains definitions and generates code to validate and
potentially correct Protocol Buffers messages at runtime. [154] successfully
developed a formally verified subset (most notably missing unions and
recursive messages) of Protocol Buffers version 3 using the Coq
999999https://coq.inria.fr formal proof assistant. Protocol Buffers is used to
encode certain parts of the _ProMC_ specification to store representations of
high-energy physics data for space-efficiency reasons [31]. Protocol Buffers
is also a core component of the Caffe [73] deep learning framework
100100100https://caffe.berkeleyvision.org/tutorial/layers.html used by popular
projects such as OpenPose, an open-source real-time multi-person keypoint
detection library [25].

Characteristics.

  * •

Robustness. The Protocol Buffers schema-driven serialization specification and
official implementations have been battle-tested by Google in high-scale
production environments.

  * •

Security. Protocol Buffers has been designed with security in mind and has
undergone reviews by the Google security team.

  * •

Popularity. Protocol Buffers is one of the most popular schema-driven binary
serialization specifications. As a result, it features excellent
documentation, relevant tools and an active open source community.

Layout. A Protocol Buffers Binary Wire Format bit-string is a sequence of
values, sometimes nested. Each value is prefixed with a type definition and
the length of the value, if applicable. Each value has a numeric identifier
that must be unique on the current nesting level. As a space-optimization,
Protocol Buffers only encodes a field if its value is not equal to the default
or if the field is explicitly marked as optional. The order of fields in a
Protocol Buffers Binary Wire Format bit-string is non-deterministic.

Types. A Protocol Buffers Binary Wire Format type definition is a 32-bit
Little Endian Base 128 (LEB128) (4.1) variable-length integer encoding of the
concatenation of a Big Endian arbitrary-length unsigned integer identifier and
its 3-bit type category identifier. Protocol Buffers groups the data types it
supports into a set of type categories depending on their length
characteristics as shown in Table 17. The de-serializer refers to the schema
for the specific data type.

Table 17: The type categories (wire types) that Protocol Buffers supports. The two other wire types that are deprecated and unused at the time of this writing are not considered. Name | Identifier |  Data types
---|---|---
Variable-length integer values | 000 |  32-bit and 64-bit Little Endian Base 128 (LEB128) (4.1) variable-length signed and unsigned integers, booleans, enumerations
64-bit values | 001 |  64-bit fixed-length signed and unsigned integers, IEEE 764 64-bit floating-point numbers [52]
Length-delimited values | 010 |  Strings, bytes, messages, lists
32-bit values | 101 |  32-bit fixed-length signed and unsigned integers, IEEE 764 32-bit floating-point numbers [52]

For example, a type definition consisting of 64-bit value with a unique field
identifier $5$ is encoded as 0x2a = 00101 (5) 001 (wire type) and a type
definition consisting of a length-delimited value with a unique field
identifier $17$ is encoded as 0x9a 0x02, the Little Endian Base 128 (LEB128)
(4.1) variable-length integer encoding of 100011 (35) 010 (wire type).

Numbers. Protocol Buffers supports Little Endian IEEE 754 32-bit and 64-bit
floating-point numbers [52]. In terms of integers, Protocol Buffers supports
32-bit and 64-bit fixed-length and Little Endian Base 128 (LEB128) (4.1)
variable-length unsigned integers, 32-bit and 64-bit fixed-length and Little
Endian Base 128 (LEB128) (4.1) variable-length Two’s Complement [51] signed
integers, and 32-bit and 64-bit Little Endian Base 128 (LEB128) (4.1)
variable-length ZigZag-encoded (4.2) signed integers. Fixed-length numbers
make use of the _32-bit values_ or _64-bit values_ wire types while variable-
length integers make use of the _variable-length integer values_ wire type as
shown in Table 17.

Strings. Protocol Buffers Binary Wire Format produces UTF-8 [33] strings that
are not _NUL_ delimited encoded using the _length-delimited_ wire type as
shown in Table 17. A Protocol Buffers Binary Wire Format string is prefixed
with a 32-bit Little Endian Base 128 (LEB128) (4.1) variable-length unsigned
integer that declares the byte-length of the string. Protocol Buffers Binary
Wire Format encodes empty strings with a zero-length prefix and no additional
data. Protocol Buffers Binary Wire Format does not deduplicate multiple
occurrences of the same string.

Booleans Protocol Buffers Binary Wire Format encodes booleans using the
_variable-length integer_ wire type as shown in Table 17 and the 32-bit Little
Endian Base 128 (LEB128) (4.1) variable-length integers $0$ (False) and $1$
(True). In practice, these variable-length integers are encoded as the 8-bit
constants 0x00 and 0x01, respectively.

Enumerations. Protocol Buffers Binary Wire Format represents enumeration
constants using 32-bit Little Endian Base 128 (LEB128) (4.1) variable-length
Two’s Complement [51] signed integers.

Unions. Protocol Buffers relies on unique field identifiers to implement union
types called _oneof_. Each alternative in the union type must have a different
field identifier and Protocol Buffers enforces that only one of such unique
field identifiers is present at a given time. The de-serializer knows the type
of the encoded value by comparing its field identifier against the union
definition.

Lists. Protocol Buffers Binary Wire Format encodes a list (a _repeated_ field)
by encoding more than one value with the same unique field identifier. The
type definitions corresponding to each element in the list use the _length-
delimited_ wire type as shown in Table 17, and include the byte-length of the
value as a 32-bit Little Endian Base 128 (LEB128) (4.1) variable-length
unsigned integer followed by the value. Lists that consist of scalar values of
the same type can be encoded as a single _length-delimited_ field, followed by
the cummulative byte-length of the elements as a 32-bit Little Endian Base 128
(LEB128) (4.1) variable-length unsigned integer, followed by the elements
encoded in order. Protocol Buffers does not natively support heterogeneous or
multi-dimensional lists. As a workaround, schema-writers may define lists of
structures including unions or lists. Protocol Buffers Binary Wire Format does
not deduplicate multiple occurrences of the same element in a list.

Figure 46: Protocol Buffers schema to serialize the Figure 10 input data.

Figure 47: Annotated hexadecimal output of serializing the Figure 10 input data with Protocol Buffers Binary Wire Format. Table 18: A high-level summary of the Protocol Buffers Binary Wire Format schema-driven serialization specification. Website |  https://developers.google.com/protocol-buffers/
---|---
Company / Individual |  Google
Year |  2001
Specification |  https://developers.google.com/protocol-buffers/docs/encoding
License |  3-clause BSD
Schema Language |  Proto3
Layout |  Sequential with field identifiers
Languages |  C++, C#, Dart, Go, Java, Objective-C, Python, Ruby
Types
Numeric |  32-bit and 64-bit Two’s Complement [51] Little Endian Base 128 (LEB128) (4.1) variable-length signed integers 32-bit and 64-bit Little Endian Base 128 (LEB128) (4.1) variable-length unsigned integers 32-bit and 64-bit ZigZag-encoded (4.2) Little Endian Base 128 (4.1) variable-length signed integers Little Endian 32-bit and 64-bit fixed-length unsigned integers Little Endian 32-bit and 64-bit fixed-length Two’s Complement [51] signed integers Little Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  Any, Enum, List, Map, Message, Oneof, Struct
Scalars |  Boolean
Other |  Bytes (byte array) Timestamp [76] Duration 101101101https://developers.google.com/protocol-buffers/docs/proto3#json

###  5.7 Apache Thrift

Figure 48: Hexadecimal output (xxd) of encoding Figure 10 input data with
Apache Thrift Compact Protocol (64 bytes).

History. Apache Thrift [127] is an RPC protocol and schema-driven binary
serialization specification developed at Facebook in 2006 and donated to the
Apache Software Foundation 102102102https://www.apache.org. Apache Thrift
graduated from the Apache Incubator in 2010 and is released under the Apache
License 2.0 103103103http://www.apache.org/licenses/LICENSE-2.0.html. Apache
Thrift is used in a large number of scalable backend services at Facebook.
Apache Thrift is also used as the transmission format of the Carat [97] large-
scale research project to collect energy-related analytics from iOS and
Android devices which collected 1.5 TB of data as of 2016 [103].

Related Literature. [84] attempts to re-implement Apache Thrift using model-
driven engineering technologies such as Xtext
104104104https://www.eclipse.org/Xtext/, Eclipse Modeling Framework (EMF)
105105105https://www.eclipse.org/modeling/emf/, and Eclipse Epsilon
106106106https://www.eclipse.org/epsilon/ resulting in a significantly more
concise implementation in terms of lines of code. The results are published on
GitHub 107107107https://github.com/SMadani/ThriftMDE/. [122] explores
automatically generating Apache Thrift service definitions as space and
runtime efficient proxies to XML-based [100] SOAP [61] web services. [5]
proposes an architecture to compose Apache Thrift services with with other
Apache Thrift, SOAP [61], and REST [49] services using the Web Services
Business Process Execution Language (BPEL) [131]. [30] performs high-
performance large-scale datacenter backups using Apache Thrift on the Apache
HBase 108108108https://hbase.apache.org and Apache Cassandra
109109109http://cassandra.apache.org NoSQL databases. [58] explores the
implications of a microservices architecture based on Apache Thrift for a
movie renting, streaming, and reviewing system comprised of 33 microservice.
[29] proposes an offline and online database system based on Conflict-free
Replicated Data Types (CRDT) [124] which uses Apache Thrift as the middleware
serialization specification.

Characteristics.

  * •

Native Type Mappings. To ease integration, Apache Thrift implementations do
not introduce Apache Thrift-specific types or wrapper objects. Instead, the
implementations make use of programming language native types.

  * •

Portability. Apache Thrift has well-maintained official implementations for a
large number of programming languages.

Layout. An Apache Thrift Compact Protocol bit-string is a sequence of values,
sometimes nested. Each value is prefixed with a type definition and the length
of the value, if applicable. Each value has a numeric identifier that must be
unique on the current nesting level. Based on our observations, Apache Thrift
Compact Protocol encodes fields even if their values equal their explicitly-
set defaults. Apache Thrift Compact Protocol structures are suffixed with the
constant byte 0x00.

Keys. Apache Thrift Compact Protocol type definitions consist in a unique
field identifier and a type identifier as shown in footnote 111. Apache Thrift
Compact Protocol supports two type definition encodings: the _Short form_ and
the _Long form_ depending on whether the field identifiers are encoded in a
relative or absolute manner. Refer to Table 19 for details.

Table 19: Apache Thrift Compact Protocol supports two structure type definition encodings. The _Long form_ encoding represents the field identifier as an absolute integer while the _Short form_ encoding represents the field identifier as the difference from the previous field identifier as a space optimization. Name |  Size |  First 4-bits |  Next 4-bits |  Remaining bits
---|---|---|---|---
Short form |  1 byte |  The unique identifier delta as a 4-bit unsigned integer greater than 0 |  The field type identifier constant as shown in footnote 111 |  None
Long form |  2 to 4 bytes |  0000 |  The field type identifier constant as shown in footnote 111 |  The unique identifier as a 16-bit Little Endian Base 128 (LEB128) (4.1) variable-length ZigZag-encoded (4.2) signed integer

Figure 49 illustrates a visual representation of the field identifier delta
approach from the _Short form_ encoding. Apache Thrift Compact Protocol
implementations will choose the _Short form_ delta-based encoding unless the
unique identifier delta exceeds the value $15$ or if the unique identifier is
negative. Apache Thrift encourages schema-writer to set explicit unique field
identifiers, which must be positive. However, Apache Thrift will automatically
assign negative unique field identifiers by default.

Figure 49: We can think of Apache Thrift fields as triplets consisting of a
field delta, a field type, and a field value. Field deltas determine the
unique identifier of the current field based on the previous delta values. A
field identifier is the sum of all the deltas up to that field.

Figure 50: Apache Thrift Compact Protocol struct type identifiers definition
111111111https://github.com/apache/thrift/blob/05bb55148608b4324a8c91c21cf9a6a0dff282fa/lib/cpp/src/thrift/protocol/TCompactProtocol.tcc.

Numbers. Apache Thrift supports 16-bit, 32-bit, and 64-bit Little Endian Base
128 (LEB128) (4.1) variable-length ZigZag-encoded (4.2) signed integers.
Apache Thrift does not support fixed-length integer types. However, Apache
Thrift supports a byte type that can represent a fixed-length 8-bit ZigZag-
encoded (4.2) signed integer. In terms of real numbers, Apache Thrift supports
Little Endian IEEE 764 64-bit floating-point numbers [52].

Strings. Apache Thrift Compact Protocol produces UTF-8 [33] strings that are
not _NUL_ delimited. Apache Thrift Compact Protocol strings are prefixed with
positive 32-bit Little Endian Base 128 (4.1) variable-length ZigZag-encoded
(4.2) signed integers declaring the byte-length of the string. Apache Thrift
Compact Protocol encodes empty strings with a zero-length prefix and no
additional data. Apache Thrift Compact Protocol does not attempt to
deduplicate multiple occurrences of the same string.

Booleans. Apache Thrift Compact Protocol encodes a boolean field and a list of
booleans in different manners. If the value is a standalone field, then Apache
Thrift Compact Protocol encodes the boolean value at the type definition level
using the CT_BOOLEAN_TRUE and CT_BOOLEAN_FALSE data types shown in footnote
111. If the boolean value is a member of a list, then it is encoded using the
8-bit ZigZag-encoded (4.2) signed integers 0x02 (True) and 0x00 (False).

Enumerations. Apache Thrift Compact Protocol represents enumeration constants
using positive 32-bit ZigZag-encoded (4.2) Little Endian Base 128 (4.1)
variable-length signed integers.

Unions. Apache Thrift relies on unique field identifiers to implement union
types. Each alternative in the union type must have a different field
identifier and Apache Thrift enforces that only one of such unique field
identifiers is present at a given time. The de-serializer knows the type of
the encoded value by comparing its field identifier against the union
definition.

Lists. Apache Thrift Compact Protocol encodes a list as the type definition,
followed by the list definition, followed by the elements encoded in order.
Apache Thrift Compact Protocol specifies two encodings for the list definition
depending on the length of the list as shown in Table 20. Apache Thrift
Compact Protocol does not attempt to deduplicate multiple occurrences of the
same element in a list. Apache Thrift natively supports lists of lists and
list of unions as a mechanism to support heterogeneous lists.

Table 20: The two list definition encodings supported by Apache Thrift Compact Protocol depending on the list length as determined by the _From_ and _To_ ranges. Note that Apache Thrift Compact Protocol cannot encode lists containing more than $2^{32}-1$ elements. From | To | Size |  First 4-bits |  Next 4-bits |  Remaining bits
---|---|---|---|---|---
0 | 14 | 1 byte |  Length of list as a 4-bit unsigned integer |  Element type identifier constant as shown in footnote 113 |  None
15 | $2^{32}-1$ | 2 to 6 bytes |  1111 |  Element type identifier constant as shown in footnote 113 |  Length of list as a positive 32-bit Little Endian Base 128 (4.1) variable-length ZigZag-encoded (4.2) signed integer

Figure 51: Apache Thrift Compact Protocol list type identifiers definition
113113113https://github.com/apache/thrift/blob/05bb55148608b4324a8c91c21cf9a6a0dff282fa/lib/cpp/src/thrift/protocol/TCompactProtocol.tcc.
The indexes represent the type identifier constants. For example, the
CT_DOUBLE type is encoded as 0x04 because it is the fourth element of the
TTypeToCType array.

Figure 52: Apache Thrift schema to serialize the Figure 10 input data.

Figure 53: Annotated hexadecimal output of serializing the Figure 10 input data with Apache Thrift Compact Protocol. Table 21: A high-level summary of the Apache Thrift Compact Protocol schema-driven serialization specification. Website |  https://thrift.apache.org
---|---
Company / Individual |  Apache Software Foundation
Year |  2006
Specification |  https://github.com/apache/thrift/tree/master/doc/specs
License |  Apache License 2.0
Schema Language |  Thrift IDL
Layout |  Sequential with field identifiers
Languages |  ActionScript, C, C++, C#, Common LISP, D, Dart, Erlang, Haskell, Haxe, Go, Java, JavaScript, Lua, OCaml, Perl, PHP, Python, Ruby, Rust, Smalltalk, Swift
Types
Numeric |  16-bit, 32-bit, and 64-bit ZigZag-encoded (4.2) Little Endian Base 128 (4.1) variable-length signed integers Little Endian 64-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  List, Map, Set, Struct, Union
Scalars |  Boolean
Other |  Binary (byte array) Byte

##  6 Schema-less Specifications

In this section, we discuss the history and characteristics of JSON-compatible
schema-less binary serialization specifications: BSON [87], CBOR [15],
FlexBuffers [141], MessagePack [57], Smile [117] and UBJSON [18].

###  6.1 BSON

Figure 54: Hexadecimal output (xxd) of encoding Figure 10 input data with BSON
(223 bytes).

History. BSON [87] is a schema-less binary serialization specification created
by MongoDB, Inc 114114114https://www.mongodb.com in 2009, which was called
_10gen_ at that time 115115115https://www.mongodb.com/press/10gen-announces-
company-name-change-mongodb-inc. BSON is a superset of JSON [19] as it
includes additional data types relevant to the MongoDB NoSQL database. BSON is
a core component of the MongoDB NoSQL database storage layer and drivers. The
BSON project was started by Mike Dirolf 116116116https://github.com/mdirolf, a
Software Engineer at 10gen. The BSON specification is released to the public
domain under the Creative Commons 1.0 license
117117117https://creativecommons.org/publicdomain/zero/1.0/. There is also a
minimal BSON C third-party implementation targetted at embedded devices called
_BINSON_ 118118118https://github.com/alialavia/binson.

Characteristics.

  * •

Traversal Runtime-performance. The MongoDB NoSQL database stores documents
using BSON. Database data access patterns typically involve searching for
fields and values within documents and [149] shows that BSON documents can be
traversed at least four times faster than JSON [42]. However, in the context
of Big Data, [130] note that BSON collections are often larger than their JSON
[42] and CSV [123] counterparts due to the additional metadata included to
support fast traversals.

  * •

In-place Updates. BSON has been designed to support updates that do not
involve re-serializing the entire document.

Layout. A BSON bit-string (a document) is a sequence of key-value pairs
prefixed with the byte-size of the rest of the document as a positive Little
Endian signed Two’s Complement [51] 32-bit integer. Each key-value pair
consists of a 1-byte type definition, followed by the property name as a _NUL_
-delimited UTF-8 string [33], followed by the value. BSON documents are
suffixed with the 0x00 byte.

Types. BSON declares 29 1-byte type definitions as shown in footnote 121. Many
of these type definitions correspond to MongoDB-specific extensions to JSON
[19] such as the DBPointer and ObjectId (OID)
119119119https://docs.mongodb.com/manual/reference/method/ObjectId/ data
types. BSON also supports binary values annotated with a sub-type such as UUID
[81] and MD5 [113].

Figure 55: BSON type definitions
121121121https://github.com/mongodb/libbson/blob/ffc8d983ecf6b46d5404f5cc20e756a85dfcbfd2/src/bson/bson-
types.h.

Numbers. BSON supports Little Endian 64-bit and 128-bit IEEE 764 floating-
point numbers [52]. In terms of integers, BSON supports Little Endian 32-bit
and 64-bit signed Two’s Complement [51] integers and Little Endian 64-bit
unsigned integers. BSON implementations pick the smallest data type that can
encode the given number.

Strings. BSON produces _NUL_ -delimited UTF-8 [33] strings for property names
and for string values. In comparison to property names, string values are
prefixed with the byte-length of the string as a positive Little Endian signed
Two’s Complement [51] 32-bit integer. BSON does not attempt to deduplicate
multiple occurrences of the same property name or string value.

Booleans. Booleans values are encoded with the 1-byte type tag 0x08 as shown
in footnote 121 followed by the byte constants 0x00 (False) or 0x01 (True).

Lists. BSON treats arrays as JSON objects [19] with stringified integral keys.
For example, the JSON document { "foo": [ true, false ] }  is encoded as {
"foo": { "1": true, "2": false } }. BSON can distinguish an array from a user-
supplied JSON object with stringified integral keys by their different 1-byte
type definition prefixes. BSON does not attempt to deduplicated multiple
occurrences of the same value in an array.

Figure 56: Annotated hexadecimal output of serializing the Figure 10 input data with BSON. Table 22: A high-level summary of the BSON schema-less serialization specification. Website |  http://bsonspec.org
---|---
Company / Individual |  MongoDB
Year |  2010
Specification |  http://bsonspec.org/spec.html
License |  Creative Commons 1.0
Layout |  Sequential
Languages |  C, C++, C#, Go, Java, Node.js, Perl, PHP, Python, Ruby, Scala
Types
Numeric |  Little Endian Two’s Complement [51] signed 32-bit and 64-bit integers Little Endian unsigned 64-bit integers Little Endian 64-bit and 128-bit IEEE 764 floating-point numbers [52]
String |  UTF-8 [33]
Composite |  Array, Document (object)
Scalars |  Boolean, Null, Undefined
Other |  Binary data (byte array) ObjectId 122122122http://dochub.mongodb.org/core/objectids Epoch [90] DBPointer JavaScript code Function UUID [81] MD5 [113] Symbol MongoDB Timestamp Regular expression

###  6.2 CBOR

Figure 57: Hexadecimal output (xxd) of encoding Figure 10 input data with CBOR
(118 bytes).

History. Concise Binary Object Representation (CBOR) [15] is a schema-less
binary serialization specification first published by Carsten Bormann
123123123https://www.linkedin.com/in/cabo/ and Paul Hoffman
<EMAIL_ADDRESS>as an
Internet Engineering Task Force (IETF) 125125125https://www.ietf.org document
in 2013. CBOR has been primarily designed for the Internet of Things. In fact,
CBOR is the recommended serialization layer for the CoAP [125] Internet of
Things transfer protocol. CBOR is natively supported as part of the RIOT
operating system for the Internet of Things [14]. Outside of IoT, CBOR is also
used as the serialization specification behind the _piChain_ fault-tolerant
distributed state machine [91]. [114] provides an alternative introduction to
the CBOR specification and describes how to translate XML documents [100] into
CBOR.

Characteristics.

  * •

Resource Efficient. CBOR has been designed to produce implementations to run
on memory and processor constrained devices
126126126https://tools.ietf.org/html/rfc7049#section-1.1.

  * •

Standardization. In comparison to informally documented serialization
specifications, CBOR is specified as an IETF RFC document [15] and has gone
through extensive technical review as a result.

Layout. A CBOR bit-string is a sequence of key-value pairs, sometimes nested.
Each CBOR key or value starts with a type definition. A CBOR key-value pair is
a concatenation of the key followed by the value and a CBOR map is a
concatenation of key-value pairs.

Types. CBOR groups the types it supports into 8 _major types_ as shown in
footnote 128. A CBOR type definition consists of 1-byte whose most-significant
3-bits encode the major type. The remaining 5-bits encode type-specific
information as shown in Table 23.

Table 23: A definition of CBOR major types as specified in [15]. Major type |  Description |  Remaining 5-bits
---|---|---
0 |  Unsigned integers |  The integer itself or the byte-length of the integer to follow
1 |  Negative integers |  The integer itself or the byte-length of the integer to follow
2 |  Byte strings |  The length of the byte-string to follow
3 |  Text strings |  The length of the string to follow
4 |  Arrays |  The logical length of the array or the byte-length of the integer representing the logical length of the array following the type definition
5 |  Maps |  The number of keys in the map or the byte-length of the integer representing the number of keys in the map following the type definition
6 |  Optional metadata |  Additional semantic information
7 |  Floats and types without content |  The sub-type followed by the content if the value is a floating-point number

Figure 58: CBOR major types definition
128128128https://github.com/intel/tinycbor/blob/fc42a049853b802e45f49588f8148fc29d7b4d9c/src/cborinternal_p.h.

Numbers. CBOR supports Big Endian IEEE 764 16-bit, 32-bit, and 64-bit
floating-point numbers [52]. Floating-point numbers are defined with the major
type 7 as shown in Table 23 and with the floating-point precision as a sub-
type. CBOR makes a distinction between positive integers (major type 0) and
negative integers (major type 1) at the type level. In terms of positive
integers, CBOR supports Big Endian 5-bit, 8-bit, 16-bit, 32-bit and 64-bit
unsigned integers. Negative integers do not use Two’s Complement [51] nor
ZigZag encoding (4.2). Instead, CBOR encodes the negative number as a Big
Endian 5-bit, 8-bit, 16-bit, 32-bit, or 64-bit unsigned integer where the
final value is equal to minus one minus the unsigned integer. For example, the
negative integer $\mathbf{-25200}$ is encoded as $\mathbf{25199}$ given that
$\mathbf{-1-25199=-25200}$.

Additionally, CBOR supports arbitrary-length positive and negative integers
and arbitrary-precision decimal numbers. Arbitrary-length integers are encoded
as unsigned integers represented as potentially-indefinite byte strings
prefixed with a major type 6 as shown in Table 23 and a positive or negative
sub-type annotation. Negative arbitrary-length integers are encoded similarly
to fixed-length negative numbers: as unsigned integers where the value is
equal to minus one minus the unsigned integer. Arbitrary-precision decimal
numbers are encoded as arrays of exactly two integer elements: the scale as a
fixed-length positive or negative integer, and the mantissa as a fixed-length
or arbitrary-length positive or negative integer. The resulting decimal number
is equal to $\mathbf{\textbf{mantissa}\times 10^{\textbf{scale}}}$.

Strings. CBOR property names and string values are encoded using UTF-8 [33]
without _NUL_ delimiters. CBOR can encode fixed-length strings where the type
definition prefix includes the byte-length of the string as a Big Endian
5-bit, 16-bit, 32-bit, or 64-bit unsigned integer. Additionally, CBOR can
encode arbitrary-length strings by splitting the input string into a sequence
of fixed-length string values suffixed with the 0xff stop code. CBOR does not
attempt to deduplicate multiple occurrences of the same property name or
string value.

Booleans CBOR encodes boolean values at the type level through a type
definition byte that consists of the major type 7 as shown in Table 23 and the
Big Endian 5-bit unsigned integer sub-types 20 (False) or 21 (True). For
example, the boolean value _True_ is encoded as 0xf5 = 111 (major type 7)
10101 = 21.

Lists. CBOR supports fixed-length and arbitrary-length arrays both constisting
of a major type 4 as shown in Table 23 type definition and the array elements
encoded in order. Fixed-length arrays use the least-significant 5-bits of the
type definition to store the logical length of the array as a Big Endian 5-bit
unsigned integer or to store the byte-length of the logical length of the
array following the type definition represented as a Big Endian unsigned
16-bit, 32-bit, or 64-bit integer.

In comparison to fixed-length arrays, arbitrary-length arrays do not encode
the logical length of the array. Instead, all the least-significant 5-bits of
the type definition are set and the array is suffixed with the 0xff stop code.
CBOR does not attempt to deduplicate multiple occurrences of the same scalar
or composite value in an array.

Figure 59: Annotated hexadecimal output of serializing the Figure 10 input data with CBOR. Table 24: A high-level summary of the CBOR schema-less serialization specification. Website |  http://cbor.io
---|---
Company / Individual |  Carsten Bormann and Paul Hoffman
Year |  2013
Specification |  RFC-7049 [15]
License |  Implementation-dependent
Layout |  Sequential
Languages |  C, C++, C#, Clojure, Crystal, D, Dart, Elixir, Erlang, Go, Haskell, Java, JavaScript, Julia, Lua, OCaml, Perl, PHP, Python, Ruby, Rust, Scala, Scala, Swift
Types
Numeric |  Big Endian 5-bit, 8-bit, 16-bit, 32-bit, and 64-big unsigned integers Big Endian 5-bit, 8-bit, 16-bit, 32-bit, and 64-big negative integers (encoded as $-1$ minus the value) Big Endian 32-bit and 64-bit IEEE 764 floating-point numbers [52] Big Endian arbitrary-length positive and negative integers Arbitrary-precision signed decimals (mantissa and scale-based)
String |  UTF-8 [33]
Composite |  Array, Map
Scalars |  Boolean, Null, Undefined
Other |  Byte string Datetime [76] Epoch [90] Base64 [74] Regular expression MIME message [54]

###  6.3 FlexBuffers

Figure 60: Hexadecimal output (xxd) of encoding Figure 10 input data with
FlexBuffers (176 bytes).

History. FlexBuffers [141] is the official schema-less variant of the
FlatBuffers [140] schema-driven binary serialization specification developed
by Google. The FlexBuffers serialization specification was developed in 2016
by Wouter van Oortmerssen 129129129https://github.com/aardappel, the main
author of FlatBuffers. FlexBuffers has the same use cases as FlatBuffers:
memory-efficient serialization and deserialization mainly in the context of
games and mobile. FlexBuffers is also released under the Apache License 2.0
130130130http://www.apache.org/licenses/LICENSE-2.0.html.

Characteristics.

  * •

Efficient Reads. FlexBuffers also produces implementations that perform
runtime-efficiency and memory-efficient incremental and random-access reads.

  * •

Embeddable. FlexBuffers can be used in conjunction with FlatBuffers [140] by
storing a part of a FlatBuffers bit-string in the FlexBuffers specification.

Layout. A FlexBuffers bit-string consist of a tree hierarchy of pointers that
eventually point at scalar types. The FlexBuffers core data structure is the
_map_. A FlexBuffers map consist of a values vector and a keys vector as shown
in Figure 61 and as follows:

  * •

Values Vector. The values vector starts with a pointer to its corresponding
keys vector, the byte-length of each key in the keys vector as a Little Endian
unsigned integer, and the logical size of the values vector as a Little Endian
unsigned integer. The values vector then sequentially encodes its elements
followed by a sequence of 1-byte type definitions that correspond to each
value in the map.

  * •

Keys Vector. The keys vector consists of the logical size of the vector as a
Little Endian unsigned integer followed by the sequence of keys, which are
typically pointers to string values. Individual keys may be shared and
multiple values vectors can point to the same keys vector if they share the
same structure resulting in efficient use of space.

Every vector element is aligned to the largest element that the vector
contains. The parent structure that points to the vector encodes the size of
the elements. Scalar values are encoded at the beginning of the bit-string
while map definitions are encoded at the end of the bit-string. FlexBuffers
bit-strings end with a footer vector that consists of a pointer to the root
element, the type definition of the root element, and the byte-length of each
element in the footer vector as a Little Endian 8-bit unsigned integer.

Figure 61: FlexBuffers maps consist of values vectors that include $N$ number
of elements followed by $N$ type definitions. These vectors point to keys
vectors consisting of $N$ elements that typically consist of pointers to
strings.

Types. FlexBuffers uses 1-byte type definitions. The most-significant 6-bits
encode the data type as an unsigned integer as shown in footnote 132. The
least-significant 2-bits encode the bit-width of the data type as shown in
footnote.

Figure 62: FlexBuffers type identifiers definition
132132132https://github.com/google/flatbuffers/blob/8778dc7c2bc20b3165a86d62e2e499d2b86912f0/include/flatbuffers/flexbuffers.h.

Figure 63: FlexBuffers bit-width definition ††footnotemark: .
132132footnotetext:
https://github.com/google/flatbuffers/blob/8778dc7c2bc20b3165a86d62e2e499d2b86912f0/include/flatbuffers/flexbuffers.h

Numbers. FlexBuffers supports Little Endian 8-bit, 16-bit, 32-bit, and 64-bit
unsigned and signed integers. Signed integers use Two’s Complement [51].
FlexBuffers defines four bit-widths for all its types as shown in footnote.
Therefore, FlexBuffers theoretically supports Little Endian 8-bit, 16-bit,
32-bit, and 64-bit IEEE 764 [52] floating-point numbers. While [52] does not
define 8-bit floating-point numbers, these type of reduced-precision floats
are useful in the context of artificial intelligence [146].