作者 | 大向
來源 | 阿裡技術公衆号
一 前言
FlatBuffers 是一個開源的、跨平台的、高效的、提供了多種語言接口的序列化工具庫。實作了與 Protocal Buffers 類似的序列化格式。主要由 Wouter van Oortmerssen 編寫，并由 Google 開源。Oortmerssen 最初為 Android 遊戲和注重性能的應用而開發了 FlatBuffers，現在它具有 C ++、C＃、C、Go、Java、PHP、Python 和 JavaScript 的接口。
高德地圖資料編譯增量釋出使用了FlatBuffers序列化工具，借此契機對FlatBuffers原理進行研究并分享于此。本文簡單介紹 FlatBuffers Scheme，通過剖析 FlatBuffers 序列化與反序列化原理，重點回答以下問題：
- 問題1：FlatBuffers 如何做到反序列化速度極快的（或者說無需解碼）。
- 問題2：FlatBuffers 如何做到預設值不占存儲空間的（Table 結構内的變量）。
- 問題3：FlatBuffers 如何做到位元組對齊的。
- 問題4：FlatBuffers 如何做到向前向後相容的（Struct 結構除外）。
- 問題5：FlatBuffers 在 add 字段時有沒有順序要求（Table 結構）。
- 問題6：FlatBuffers 如何根據 Scheme 自動生成編解碼器。
- 問題7：FlatBuffers 如何根據 Scheme 自動生成 Json。
二 FlatBuffers Scheme
FlatBuffers 通過 Scheme 檔案定義資料結構，Schema 定義與其他架構使用的IDL(Interface description language)語言類似簡單易懂，FlatBuffers 的 Scheme 是一種類 C 的語言（盡管 FlatBuffers 有自己的接口定義語言 Scheme 來定義要與之序列化的資料，但它也支援 Protocol Buffers 中的 .proto 格式）。下面以官方 Tutorial 中的 monster.fbs 為例進行說明：
// 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 定義命名空間，可以定義嵌套的命名空間，用 . 分割。
enum Color:byte { Red = 0, Green, Blue = 2 };
enum 定義枚舉類型。和正常的枚舉類稍有不同的地方是可以定義類型。比如這裡的 Color 是 byte 類型。enum 字段隻能新增，不能廢棄。
union Equipment {Weapon} // Optionally add more tables
union 類似 C/C++ 中的概念，一個 union 中可以放置多種類型，共同使用一個記憶體區域。這裡的使用是互斥的，即這塊記憶體區域隻能由其中一種類型使用。相對 struct 來說比較節省記憶體。union 跟 enum 比較類似，但是 union 包含的是 table，enum 包含的是 scalar 或者 struct。union 也隻能作為 table 的一部分，不能作 root type。
struct Vect3{ x : float; y : float; z : float;};
struct 所有字段都是必填的，是以沒有預設值。字段也不能添加或者廢棄，且隻能包含标量或者其他 struct。struct 主要用于資料結構不會發生改變的場景，相對 table 使用更少的記憶體，lookup 的時候速度更快（struct 儲存在父 table 中，不需要使用 vtable）。
table Monster{};
table 是在 FlatBuffers 中定義對象的主要方式，由一個名稱（這裡是 Monster）和一個字段清單組成。可以包含上面定義的所有類型。每個字段（Field）包括名稱、類型和預設值三部分；每個字段都有預設值，如果沒有明确寫出則預設為 0 或者 null。每個字段都不是必須的，可以為每個對象選擇要省略的字段，這是 FlatBuffers 向前和向後相容的機制。
root_type Monster;
用于指定序列化後的資料的 root table。
Scheme 設計需要特别注意的：
- 新字段隻能加在 table 的後面。舊代碼會忽略這個字段，仍然可以正常執行。新代碼讀取舊的資料，會取到新增字段的預設值。
- 即使字段不再使用了也不能從 Scheme 中删除。可以标記為 deprecated，在生成代碼的時候不會生成該字段的通路器。
- 如果需要嵌套的 vector，可以将 vector 包裝在 table 中。string 對于其他編碼可以使用 [byte] 或者 [ubyte] 支援。
三 FlatBuffers 的序列化
簡單來說 FlatBuffers 就是把對象資料，儲存在一個一維的數組中，将資料都緩存在一個 ByteBuffer 中，每個對象在數組中被分為兩部分。中繼資料部分：負責存放索引。真實資料部分：存放實際的值。然而 FlatBuffers 與大多數記憶體中的資料結構不同，它使用嚴格的對齊規則和位元組順序來確定 buffer 是跨平台的。此外，對于 table 對象，FlatBuffers 提供前向/後向相容性和 optional 字段，以支援大多數格式的演變。除了解析效率以外，二進制格式還帶來了另一個優勢，資料的二進制表示通常更具有效率。我們可以使用 4 位元組的 UInt 而不是 10 個字元來存儲 10 位數字的整數。
FlatBuffers 對序列化基本使用原則：
- 小端模式。FlatBuffers 對各種基本資料的存儲都是按照小端模式來進行的，因為這種模式目前和大部分處理器的存儲模式是一緻的，可以加快資料讀寫的資料。
- 寫入資料方向和讀取資料方向不同。
FlatBuffers 向 ByteBuffer 中寫入資料的順序是從 ByteBuffer 的尾部向頭部填充，由于這種增長方向和 ByteBuffer 預設的增長方向不同，是以 FlatBuffers 在向 ByteBuffer 中寫入資料的時候就不能依賴 ByteBuffer 的 position 來标記有效資料位置，而是自己維護了一個 space 變量來指明有效資料的位置，在分析 FlatBuffersBuilder 的時候要特别注意這個變量的增長特點。但是，和資料的寫入方向不同的是，FlatBuffers 從 ByteBuffer 中解析資料的時候又是按照 ByteBuffer 正常的順序來進行的。FlatBuffers 這樣組織資料存儲的好處是，在從左到右解析資料的時候，能夠保證最先讀取到的就是整個 ByteBuffer 的概要資訊（例如 Table 類型的 vtable 字段），友善解析。
對于每種資料類型的序列化：
1 标量類型
标量類型即基本類型，如：int，double，bool等，标量類型使用直接尋址進行資料通路。
示例：short mana = 150; 12個位元組，存儲結構如下：
schema 中定義标量可以設定預設值。文章最初提到 FlatBuffers 的預設值不占存儲空間的，對于 table 内部的标量，是可以做到預設值不存儲的，如果變量的值不需要改變，該字段在 vtable 中對應的 offset 的值設定為 0 即可，預設值被記錄在解碼接口内，解碼時擷取該字段的 offset 為 0 時，解碼接口則傳回預設值。對于 struct 結構因為沒有使用 vtable 結構，是以内部的标量沒有預設值，必須存儲（struct 類型和 table 類型的序列化原理在下文會詳細說明）。
// 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);
} 标量資料類型是按其本身位元組數大小進行對齊。通過 PaddingBytes 函數計算，所有标量都會調用這個函數，進行位元組對齊。
2 Struct 類型
除了基本類型之外，FlatBuffers 中隻有 Struct 類型使用直接尋址進行資料通路。FlatBuffers 規定 Struct 類型用于存儲那些約定成俗、永不改變的資料，這種類型的資料結構一旦确定便永遠不會改變，沒有任何字段是可選的（也沒有預設值），字段可能不會被添加或被棄用，是以 structs 不提供前向/後向相容性。在這個規定之下，為了提高資料通路速度，FlatBuffers 單獨對 Struct 使用了直接尋址的方式。字段的順序即為存儲的順序。struct 有的特性一般不作為 schema 檔案的根。
示例：struct Vec3(16, 17, 18); 12個位元組
struct 定義了一個固定的記憶體布局，其中所有字段都與其大小對齊，并且 struct 與其最大标量成員對齊。
3 vector 類型
vector 類型實際上就是 schema 中聲明的數組類型，FlatBuffers 中也沒有單獨的類型和它對應，但是它卻有自己獨立的一套存儲結構，在序列化資料時先會從高位到低位依次存儲 vector 内部的資料，然後再在資料序列化完畢後寫入 Vector 的成員個數。資料存儲結構如下：
示例：byte[] treasure = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector size 的類型為 int，是以在初始化申請記憶體時 vector 進行四位元組位元組對齊。
4 String 類型
FlatBuffers 字元串按照 utf-8 的方式進行了編碼，在實作字元串寫入的時候将字元串的編碼數組當做了一維的 vector 來實作。string 本質上也可以看做是 byte 的 vector ，是以建立過程和 vector 基本一緻，唯一的差別就是字元串是以null結尾，即最後一位是 0。string 寫入資料的結構如下：
示例：string name = “Sword”;
vector size 的類型為 int，是以在初始化申請記憶體時字元串進行四位元組位元組對齊。
5 Union 類型
Union 類型比較特殊，FlatBuffers 規定這個類型在使用上具有如下兩個限制：
- Union 類型的成員隻能是 Table 類型。
- Union 類型不能是一個 schema 檔案的根。
FlatBuffers 中沒有特定類型表示 union，而是會生成一個單獨的類對應 union 的成員類型。與其他類型的主要差別是需要先指定類型，在序列化 Union 的時候一般先寫入 Union 的 type，然後再寫入 Union 的資料偏移；在反序列化 Union 的時候一般先
析出 Union 的 type，然後再按照 type 對應的 Table 類型來解析 Union 對應的資料。
6 Enum 類型
FlatBuffers 中的 enum 類型在資料存儲的時候是和 byte 類型存儲的方式一樣的。因為和 Union 類型相似，enum 類型在 FlatBuffers 中也沒有單獨的類與它對應，在 schema 中聲明為 enum 的類會被編譯生成單獨的類。
- enum 類型不能是一個 schema 檔案的根。
7 Table 類型
table 是 FlatBuffers 的基石，為了解決資料結構變更的問題，table 通過 vtable 間接通路字段。每個 table 都帶有一個 vtable（可以在具有相同布局的多個 table 之間共享），并且包含存儲此特定類型 vtable 執行個體的字段的資訊。vtable 還可能表明該字段不存在（因為此 FlatBuffers 是使用舊版本的代碼編寫的，僅僅因為資訊對于此執行個體不是必需的，或者被視為已棄用），在這種情況下會傳回預設值。
table 的記憶體開銷很小（因為 vtables 很小并且共享）通路成本也很小（間接通路），但是提供了很大的靈活性。table 在特殊情況下可能比等價的 struct 花費更少的記憶體，因為字段在等于預設值時不需要存儲在 buffer 中。這樣的結構決定了一些複雜類型的成員都是使用相對尋址進行資料通路的，即先從Table 中取到成員常量的偏移，然後根據這個偏移再去常量真正存儲的位址去取真實資料。
單就結構來講：首先可以将 Table 分為兩個部分，第一部分是存儲 Table 中各個成員變量的概要，這裡命名為 vtable，第二部分是 Table 的資料部分，存儲 Table 中各個成員的值，這裡命名為 table_data。注意 Table 中的成員如果是簡單類型或者 Struct 類型，那麼這個成員的具體數值就直接存儲在 table_data中；如果成員是複雜類型，那麼 table_data 中存儲的隻是這個成員資料相對于寫入位址的偏移，也就是說要獲得這個成員的真正資料還要取出 table_data 中的資料進行一次相對尋址。
- vtable 是一個 short 類型的數組，其長度為（字段個數+2）*2位元組，第一個字段是 vtable 的大小，包括這個大小本身；第二個字段是 vtable 對應的對象的大小，包括到 vtable 的 offset；接下來是每個字段相對于對象開始位置的 offset。
- table_data 的開頭是 vtable 開始位置減去目前table對象開始位置的 INT 型 offset，由于 vtable 可能在任意的地方，這個值有可能是負值。table_data開始用int存儲了vtable的offset，是以進行了四位元組對齊的。
add 的操作是添加 table_data，由于 Table 資料結構的是通過 vtable - table_data 機制存儲的，這個操作沒有強制要求字段的先後順序，對順序沒有要求，因為vtable在記錄每個字段相對于對象開始位置的 offset 時是按照 schema 中定義的順序進行存儲的，是以在add字段的時候即使沒有順序也可以根據 offset 擷取正确的值。需要注意的是，每次add字段時 FlatBuffers 都會做位元組對齊處理。
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 順序 1：最終二進制的大小為 72 位元組。
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 順序 2：最終二進制的大小為 80 位元組。
add 順序 1 和 add 順序 2 對應的 schema 檔案一樣，表達的資料也一樣，Table 結構在 add 字段時有沒有順序要求。序列化後的資料大小差8個位元組，原因就是位元組對齊導緻的。是以 add 字段的時候，盡量把相同類型的字段放在一起進行 add，這樣會避免不必要的位元組對齊，擷取更小的序列化結果。
FlatBuffers 的向前向後相容指的是 table 結構。table 結構每個字段都有預設值，如果沒有明确寫出則預設為 0 或者 null。每個字段都不是必須的，可以為每個對象選擇要省略的字段，這是 FlatBuffers 向前和向後相容的機制。需要注意的是：
- 新的字段隻能加在 table 的後面。舊的代碼會忽略這個字段，仍然可以正常執行。新的代碼讀取舊的資料，新增的字段會傳回預設值。
- 即使字段不再使用了也不能從 schema 中删除。可以标記為 deprecated，在生成代碼的時候該字段不會生成該字段的接口。
四 FlatBuffers 的反序列化
FlatBuffers 反序列化的過程就很簡單了。由于序列化的時候儲存好了各個字段的 offset，反序列化的過程其實就是把資料從指定的 offset 中讀取出來。反序列化的過程是把二進制流從 root table 往後讀。從 vtable 中讀取對應的 offset，然後在對應的 object 中找到對應的字段，如果是引用類型，string / vector / table，讀取出 offset，再次尋找 offset 對應的值，讀取出來。如果是非引用類型，根據 vtable 中的 offset ，找到對應的位置直接讀取即可。對于标量，分 2 種情況，預設值和非預設值。預設值的字段，在讀取的時候，會直接從 flatc 編譯後的檔案中記錄的預設值中讀取出來。非預設值字段，二進制流中就會記錄該字段的 offset，值也會存儲在二進制流中，反序列化時直接根據offset讀取字段值即可。
整個反序列化的過程零拷貝，不消耗占用任何記憶體資源。并且 FlatBuffers 可以讀取任意字段，而不是像 Json 和 protocol buffer 需要讀取整個對象以後才能擷取某個字段。FlatBuffers 的主要優勢就在反序列化這裡了。是以 FlatBuffers 可以做到解碼速度極快，或者說無需解碼直接讀取。
五 FlatBuffers 的自動化
FlatBuffers 的自動化包括自動生成編碼解碼接口和自動生成 Json，自動化生成編解碼接口和自動生成 Json，都依賴 schem 的解析。
1 schema 描述檔案解析
FlatBuffers 描述檔案解析器按遊标的方式順序進行識别 FlatBuffers 支援的資料結構。擷取字段名稱、字段類型、字段預設值、是否棄用等屬性。支援關鍵字：标量類型、非标量類型、include、namespace、root_type。
如果需要嵌套的vector，可以将vector包裝在table中。
2 自動生成編碼解碼接口
FlatBuffers 使用模闆程式設計，編碼解碼接口僅生成h檔案。實作資料結構的定義，并特化出變量的Add函數、Get函數，校驗函數接口。對應的檔案名為filename_generated.h。
3 自動生成Json
FlatBuffers 的主要目标是避免反序列化。通過定義二進制資料協定來實作的，一種将定義好的将資料轉換為二進制資料的方法。由該協定建立的二進制結構無需進一步解碼即可讀取。是以在自動生成json時，隻需要提供二進制資料流和二進制定義結構就可以讀物資料，轉換成json。
- Json結構與 FlatBuffers 結構保持一緻。
- 預設值不輸出 Json。
六 FlatBuffers 的優缺點
FlatBuffers 通過 Scheme 檔案定義資料結構，Schema 定義與其他架構使用的IDL(Interface description language)語言類似簡單易懂，FlatBuffers 的 Scheme 是一種類C的語言（盡管 FlatBuffers 有自己的接口定義語言Scheme來定義要與之序列化的資料，但它也支援 Protocol Buffers 中的 .proto 格式）。下面以官方 Tutorial 中的 monster.fbs 為例進行說明：
1 優點
- 解碼速度極快，将序列化資料存儲在緩存中，這些資料既可以寫出至檔案中，又可以通過網絡原樣傳輸，也可直接讀取而沒有任何解析開銷，通路資料時的唯一記憶體需求就是緩沖區，不需要額外的記憶體配置設定。
- 擴充性、靈活性：它支援的可選字段意味着具有很好的前向/後向相容。FlatBuffers 支援選擇性地寫入資料成員，這不僅為某一個資料結構在應用的不同版本之間提供了相容性，同時還能使程式員靈活地選擇是否寫入某些字段及靈活地設計傳輸的資料結構。
- 跨平台：支援 C++11、Java，而不需要任何依賴庫，在最新的 gcc、clang、vs2010 等編輯器上也工作良好。使用簡單友善 ，僅僅需要自動生成的少量代碼和一個單一的頭檔案依賴，很容易內建到現有系統中，生成的 C++ 代碼提供了簡單的通路和構造接口，可以相容 Json 等其他格式的解析。
2 缺點
- 資料無可讀性，必須進行資料可視化才能了解資料。
- 向後相容性局限，在 schema 中添加或删除字段必須小心。
七 總結
相比其它的序列化工具，FlatBuffers 最大的優勢是反序列化速度極快，或者說無需解碼。如果使用場景是需要經常解碼序列化的資料，則有可能從 FlatBuffers 的特性獲得一定的好處。
招聘
歡迎加入高德地圖智能技術中心團隊。資料是高德的根本，我們的使命是打造高德大資料處理平台，實作高德資料端到端全鍊路的實時化，線上化，智能化。如果你想知道高德的資料從哪裡來，到哪兒去，如何将現實世界轉化為人能夠了解的活地圖，歡迎加入我們。轉崗或者推薦，聯系人張啟鑫：[email protected]
阿裡雲開發者社群邀你參加
《我的Java打怪日記》征文
在技術這條無盡求索的路途中，有誰曾給過你明燈一樣的指引？有沒有一個Java架構，曾讓你歎為觀止？有沒有一個瞬間，點燃了你學習Java的熱情和信心？阿裡雲開發者社群特别推出《我的Java打怪日記》有獎征文活動，通過文章記錄下同學們在Java學習中的思考和感悟！
點選這裡，快來參與吧~