作者 | 大向
來源 | 阿里技術公眾號
一 前言
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學習中的思考和感悟！
點擊這裡，快來參與吧~