Summary: Flatbuffers is an open source, cross-platform, efficient serialization tool library that provides multiple language interfaces. Implement a serialization format similar to Protocal Buffers. Written primarily by Wouter van Oortmerssen and open source by Google. This article will be based on AutoNavi map data compilation incremental release using Flatbuffers serialization tool, to share the principle of Flatbuffers.

The author to source | | large ali technology to the public

A preface

Flatbuffers is an open source, cross-platform, efficient serialization tool library that provides multiple language interfaces. Implement a serialization format similar to Protocal Buffers. Written primarily by Wouter van Oortmerssen and open source by Google. Oortmerssen originally developed Flatbuffers for Android games and performancefocused applications, and it now has C ++, C #, C, Go, Java, PHP, Python, and JavaScript interfaces.

Flatbuffers serialization tool is used for the incremental release of AutoNavi map data compilation, and the principle of Flatbuffers is studied and shared here. This paper briefly introduces the Flatbuffers Scheme, and focuses on answering the following questions by analyzing the principle of serialization and deserialization of Flatbuffers:

  • Question 1: How does the FlatBuffers do deserialization very quickly (or without decoding)?
  • Problem 2: How do FlatBuffers make the default values not take up storage space (variables in the Table structure).
  • Question 3: How does the FlatBuffers do byte alignment?
  • Question 4: How do FlatBuffers make it backward and forward compatible (except for Struct structures)?
  • Problem 5: Does the FlatBuffers have an order requirement in the Add field (Table structure)?
  • Problem 6: How do Flatbuffers automatically generate codecs based on Scheme?
  • Problem 7: How does Flatbuffers automatically generate JSON according to Scheme?

Two FlatBuffers Scheme

Flatbuffers use Scheme files to define data structures. Schema definitions are similar to the IDL(Interface Description Language) language used by other frameworks. Flatbuffers’ Scheme is a C-like language (although Flatbuffers have their own Interface Definition Language Scheme to define the data to serialize with, it also supports the.proto format in Protocol Buffers). Here is an example of monster. FBS in the official Tutorial:

// Example IDL file for our monster's schema.
namespace MyGame.Sample;
enum Color:byte { Red = 0, Green, Blue = 2 }
union Equipment { Weapon } // Optionally add more tables.
struct Vec3 {
  x:float;
  y:float;
  z:float;
}
table Monster {
  pos:Vec3;
  mana:short = 150;
  hp:short = 100;
  name:string;
  friendly:bool = false (deprecated);
  inventory:[ubyte];
  color:Color = Blue;
  weapons:[Weapon];
  equipped:Equipment;
  path:[Vec3];
}
table Weapon {
  name:string;
  damage:short;
}
root_type Monster;

namespace MyGame.Sample;

Namespace defines namespaces. You can define nested namespaces using.. Segmentation.

enum Color:byte { Red = 0, Green, Blue = 2 };

Enum defines enumerated types. A slight difference from regular enumerated classes is that types can be defined. For example, here Color is a byte type. Enum fields can only be added, not deprecated.

union Equipment {Weapon} // Optionally add more tables

Unions are similar to the concept in C/C++ that multiple types can be placed in a union, using a common memory area. The use here is mutually exclusive, meaning that the memory area can only be used by one of the types. It saves memory relative to a struct. A union is similar to an enum, but a union contains a table, and an enum contains a scalar or struct. UNION can also only be part of a table and cannot be a root type.

struct Vect3{ x : float; y : float; z : float; };

Struct all fields are required, so there is no default value. Fields cannot be added or discarded, and can only contain scalars or other structs. Structs are mainly used in situations where data structures do not change, use less memory than tables, and lookups are faster (structs are stored in parent tables and do not need vtables).

table Monster{};

Table is the primary way to define objects in Flatbuffers, consisting of a name (in this case, Monster) and a list of fields. You can include all of the types defined above. Each Field includes name, type and default value. Each field has a default value, which is 0 or null if not explicitly written. Each field is not required, and you can choose which fields to omit for each object, which is a mechanism for forward and backward compatibility of the FlatBuffers.

root_type Monster;

The root table used to specify the serialized data.

Scheme design needs special attention:

  • New fields can only be appended to the table. The old code ignores this field and still works. The new code reads the old data and fetches the default value of the new field.
  • Fields cannot be removed from Scheme even if they are no longer in use. Can be marked deprecated so that the accessor for this field will not be generated when the code is generated.
  • If you want a nested vector, you can wrap a vector in a table. String can be supported for other encodings using [byte] or [ubyte].

Serialization of three FlatBuffers

Simply FlatBuffers store the object data in a one-dimensional array cached in a ByteBuffer, where each object is divided into two parts. Metadata section: is responsible for storing the index. The real data part: stores the actual value. Unlike most in-memory data structures, however, FlatBuffers use strict alignment rules and byte order to ensure that buffers are cross-platform. In addition, for the table object, Flatbuffers provide forward/backward compatibility and optional fields to support the evolution of most formats. In addition to parsing efficiency, the binary format brings another advantage: the binary representation of the data is generally more efficient. We can use a 4-byte UInt instead of 10 characters to store a 10-digit integer.

Flatbuffers on the basic principles of serialization:

  • Small endian mode. Flatbuffers store all kinds of basic data in the small-endian mode, because this mode is currently the same as the storage mode of most processors, and can speed up data reading and writing.
  • The direction of writing data is different from that of reading data.



The order in which the FlatBuffers write data to the byteBuffer is from the tail of the byteBuffer to the head. Since this growth direction is different from the default byteBuffer growth direction, Therefore, the FlatBuffers cannot rely on the position of the byteBuffer when writing data to the byteBuffer. Instead, they maintain a space variable to indicate the position of the valid data. Pay special attention to the growth characteristics of this variable when analyzing FlatbuffersBuilder. However, instead of writing the data in the same direction, the FlatBuffers parse the data from the byteBuffer in the normal byteBuffer order. The advantage of organizing the data store this way is that when parsed from left to right, the entire ByteBuffer profile (such as the vtable field of the Table type) is guaranteed to be read first and parsed easily.

For each data type serialization:

1 Scalar type

Scalar types are primitive types such as int, double, bool, etc. Scalar types use direct addressing for data access.

Example: short mana = 150; 12 bytes with the following storage structure:

Default values can be set for scalars defined in the schema. The paper initially mentioned that the default value of FlatBuffers does not occupy storage space. For scalars inside the table, the default value can not be stored. If the value of the variable does not need to be changed, the corresponding offset value of the field in the vtable can be set to 0, and the default value is recorded in the decoding interface. When the offset of the field is 0, the decoding interface returns the default value. Since the vtable structure is not used for struct structures, the internal scalar has no default value and must be stored (the serialization principle for struct and table types is explained in more detail below).

// Computes how many bytes you'd have to pad to be able to write an
// "scalar_size" scalar if the buffer had grown to "buf_size" (downwards in
// memory).
inline size_t PaddingBytes(size_t buf_size, size_t scalar_size) {
    return ((~buf_size) + 1) & (scalar_size - 1);
}

Scalar data types are aligned by their own byte size. Calculated by the paddingBytes function, all scalars call this function for byte alignment.

2 Struct type

In addition to the base types, only the Struct type in Flatbuffers uses direct addressing for data access. Flatbuffers specify that Struct types are used to store convention data that never changes. Data structures of this type, once determined, never change. No fields are optional (and there are no defaults), and fields may not be added or deprecated, so structs do not provide forward/backward compatibility. Under this specification, in order to speed up data access, the FlatBuffers use direct addressing for structs alone. The order of the fields is the order of storage. Some features of a struct are generally not considered root of a schema file.

Example: struct Vec3(16, 17, 18); Twelve bytes

A struct defines a fixed memory layout in which all fields are aligned with their sizes, and a struct is aligned with its maximum scalar member.

Three types of vector

The vector type is actually an array type declared in the schema. There is no single type for it in FlatBuffers, but it does have its own set of storage structures. When serializing data, it stores the data inside the vector from top to bottom in sequence. Then write the number of members in the Vector after serializing the data. The data storage structure is as follows:

Byte [] Treasure = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

The vector size is of type int, so the vector is four-byte byte aligned when we initialize the memory request.

4 type String

FlatBuffers strings are encoded in UTF-8, using the encoded array of strings as a one-dimensional vector when writing the strings. A string is also essentially a vector of byte, so the creation process is essentially the same as a vector, except that the string ends in null, meaning the last digit is 0. The structure of the data written to string is as follows:

Example: String name = “Sword”;

The vector size is of type int, so the string is four-byte byte aligned when the memory request is initialized.

5 the Union type

The UNION type is special, and the FlatBuffers specify two limitations on its use:

  • Members of the UNION type can only be of the TABLE type.
  • The UNION type cannot be the root of a schema file.

There is no specific type in FlatBuffers to represent the union; instead, a separate class is generated corresponding to the member type of the union. The main difference with other types is that you need to specify the type first. When serializing a Union, you usually write the type of the Union first, and then write the data offset of the Union. When deserializing a Union, the type of the Union is usually precipitated first, and then the data corresponding to the Union is parsed according to the Table type corresponding to the type.

6 Enum type

The enum type in FlatBuffers is stored in the data in the same way as the byte type. Because, like the UNION type, the ENUM type does not have a single class corresponding to it in the FlatBuffers. Classes declared as ENUM in the Schema are compiled to generate a separate class.

  • The enum type cannot be the root of a schema file.

7 Table type

The table is the cornerstone of Flatbuffers, and in order to address data structure changes, the table indirectly accesses fields through the vtable. Each table comes with a vtable (which can be shared between multiple tables with the same layout) and contains information about the fields that store this particular type of vtable instance. The vTable may also indicate that the field does not exist (because the Flatbuffers are written in older versions of the code, simply because the information is not required for this instance or is considered deprecated), in which case the default value will be returned.

Tables have little memory overhead (because vtables are small and shared) and little access cost (indirect access), but provide a lot of flexibility. In special cases, a table may cost less memory than an equivalent struct, because fields that are equal to their default value do not need to be stored in the buffer. This structure determines that some complex types of members use relative addressing for data access, that is, first fetch the offset of the member constant from the Table, and then use this offset to fetch the real data from the address where the constant is stored.

In terms of structure, the Table can be divided into two parts. The first part is the summary of the variables stored in the Table, which is named vtable. The second part is the data part of the Table, which stores the values of each member in the Table, which is named table_data. Note that if a Table member is of a simple type or Struct type, the value of the member is stored directly in table_data. If a member is of a complex type, all that is stored in table_data is the offset of the member’s data from the address that was written to it. In other words, in order to get the actual data of this member, we need to fetch the data from table_data for a relative address.

  • Vtable is an array of short (number of fields +2) *2 bytes. The first field is the size of the vtable, including the size itself. The second field is the size of the object corresponding to vtable, including offset to vtable. Next is the offset of each field relative to the starting position of the object.
  • Table_data begins with the vtable start position minus the current table object start position of INT offset. Since vtable can be anywhere, this value can be negative. Table_Data starts by storing vtable offset with an int, so it is four-byte aligned.

The operation of add is to add table_data. Since the Table data structure is stored through vtable-table_data mechanism, this operation does not force the order of fields. There is no requirement on the order. Because the vtable stores the offset of each field relative to the start of the object in the order defined in the schema, it is possible to get the correct value from the offset when adding the fields even if the offset is out of order. Note that the FlatBuffers do byte alignment every time a field is added.

std::string e_poiId = "1234567890";
double e_coord_x = 0.1; 
double e_coord_y = 0.2;
int e_minZoom = 10;
int e_maxZoom = 200;

//add
featureBuilder.add_poiId(nameData);
featureBuilder.add_x(e_coord_x);
featureBuilder.add_y(e_coord_y);
featureBuilder.add_maxZoom(e_maxZoom);
featureBuilder.add_minZoom(e_minZoom);
auto rootData = featurePoiBuilder.Finish();
flatBufferBuilder.Finish(rootData);
blob = flatBufferBuilder.GetBufferPointer();
blobSize = flatBufferBuilder.GetSize();

Add order 1: The size of the final binary is 72 bytes.

std::string e_poiId = "1234567890";
double e_coord_x = 0.1; 
double e_coord_y = 0.2;
int e_minZoom = 10;
int e_maxZoom = 200;

//add
featureBuilder.add_poiId(nameData);
featureBuilder.add_x(e_coord_x);
featureBuilder.add_minZoom(e_minZoom);
featureBuilder.add_y(e_coord_y);
featureBuilder.add_maxZoom(e_maxZoom);
auto rootData = featurePoiBuilder.Finish();
flatBufferBuilder.Finish(rootData);
blob = flatBufferBuilder.GetBufferPointer();
blobSize = flatBufferBuilder.GetSize();

Add order 2: The size of the final binary is 80 bytes.

Add order 1 and add order 2 corresponding schema file, the expression of data is the same, whether the Table structure in the add field has order requirements. The serialized data size difference is 8 bytes due to byte alignment. Therefore, when adding fields, try to put fields of the same type together to avoid unnecessary byte alignment and get a smaller serialization result.

The forward and backward compatibility of FlatBuffers refers to the table structure. The table structure has a default value for each field, which is 0 or null if not explicitly written. Each field is not required, and you can choose which fields to omit for each object, which is a mechanism for forward and backward compatibility of the FlatBuffers. What needs to be noted is:

  • New fields can only be added after the table. The old code ignores this field and still works. The new code reads the old data, and the new fields return the default values.
  • Fields cannot be removed from the schema even if they are no longer in use. You can mark it as deprecated so that it does not generate an interface for the field when code is generated.

Deserialization of four FlatBuffers

The FlatBuffers deserialization process is simple. Since the offset of each field is stored during serialization, deserialization is simply reading data from the specified offset. The deserialization process is to read the binary stream backwards from the root table. Read the corresponding offset from the vtable, and then find the corresponding field in the corresponding object. If it is a reference type, string/vector/table, read and take out the offset, look for the corresponding value of offset again, and read out. If the type is non-reference, find the corresponding position of offset in vtable to read directly. For scalars, there are two cases, default and non-default. The default fields, when read, are read directly from the default values recorded in the flatc compiled file. If the field is not a default value, the binary stream will record the offset value of the field, and the value will be stored in the binary stream. During deserialization, the value of the field can be read directly from the offset value.

The entire deserialization process is zero copy and does not consume any memory resources. And Flatbuffers can read any field, unlike JSON and Protocol Buffers, which need to read the entire object before fetching a field. The main advantage of FlatBuffers is in deserialization. So FlatBuffers can decode very quickly, or read directly without decoding.

Five FlatBuffers for automation

The automation of FlatBuffers includes automatic generation of codec interface and automatic generation of JSON, automatic generation of codec interface and automatic generation of JSON, all dependent on the parsing of SCHEM.

1 Schema description file parsing

Flatbuffers describe file parsers that identify data structures supported by FlatBuffers in a cursor-like order. Gets field name, field type, field default value, deprecated or not, and other properties. Key words supported: scalar type, non-scalar type, include, namespace, root_type.

If you want a nested vector, you can wrap a vector in a table.

2. Automatic generation of encoding and decoding interface

Flatbuffers are programmed using templates that encode and decode interfaces to generate only H files. Realize the definition of data structure, and specialize the variable Add function, Get function, check function interface. The corresponding file is named filename_generated.h.

Automatically generate JSON

The main goal of FlatBuffers is to avoid deserialization. Implemented by defining binary data protocols, a method of converting defined data to binary data. The binary structure created by this protocol can be read without further decoding. Therefore, when JSON is generated automatically, you simply need to provide the binary data stream and binary definition structure to read the data and convert it to JSON.

  • The JSON structure is consistent with the Flatbuffers structure.
  • The default value does not output JSON.

Six advantages and disadvantages of FlatBuffers

Flatbuffers use Scheme files to define data structures. Schema definitions are similar to the IDL(Interface Description Language) language used by other frameworks. Flatbuffers’ Scheme is a C-like language (although Flatbuffers have their own Interface Definition Language Scheme to define the data to serialize with, it also supports the.proto format in Protocol Buffers). Here is an example of monster. FBS in the official Tutorial:

1 the advantages

  • The decoding speed is extremely fast, and the serialized data is stored in the cache. The data can be written out to a file, transmitted over the network as it is, or read directly without any parsing overhead. The only memory requirement for accessing the data is the buffer, which does not require additional memory allocation.
  • Extensibility and flexibility: Its support for optional fields means good forward/backward compatibility. Flatbuffers support for selectively writing data members, which not only provides compatibility between different versions of an application for a data structure, but also gives programmers flexibility in writing certain fields or not and in designing the transmitted data structure.
  • Cross-platform: supports C++11, Java, without any dependencies, and works well on the latest GCC, Clang, VS2010 and other editors. It is easy to use and requires only a small amount of code generated automatically and a single header dependency. It is easy to integrate into existing systems. The generated C++ code provides simple access and construction interfaces and is compatible with parsing in other formats such as JSON.

Two shortcomings

  • Data is not readable and must be visualized to understand the data.
  • Backward compatibility is limited, and you must be careful when adding or removing fields from the schema.

Seven summarizes

The biggest advantage of Flatbuffers over other serialization tools is that they can be de-serialized very quickly, or without decoding. If a usage scenario is one where serialized data is often decoded, it is possible to benefit from the FlatBuffers feature.

This article is the original content of Aliyun, shall not be reproduced without permission.