現在越來越多的服務應用使用 Protobuf 來作為資料交換的格式,它被廣泛應用於 RPC 調用和資料存儲。 Protobuf 語言中立、平臺中立,只要定義好一份 .proto 檔案,就可以生成不同的程式語言來處理資料的序列化或反序列化。要了解 Protobuf 序列化/反序列化,首先需要了解一些知識點 :
- Varint Encoding
- Zigzag Encoding
- Wire Type 類型
- T-L-V 儲存方式
熟悉這些可以更加理解 protobuf,也能避免錯誤使用,以及更好的優化性能。本章節會實際把前面學到的知識點一次用上,用實際案例來了解 Protobuf - Serialization。
隨者網路傳輸、頻寬與硬體的設備的改善和增強,能傳遞資料量也越來越大、越來越複雜,這時我們也不再只是追求能夠將資料傳遞完成,而是更加要求短時內傳遞大量的資料,故勢必會需要強化序列化和壓縮的技術。這篇會介紹 Protobuf 編碼後的 byte array 結構,以及會這樣設計的思路,當有了基本的認識後,就會明白 Protobuf 為何它可以比 JSON、XML 傳輸效率更高,更能壓縮資料,實現高效率。
Protobuf 全稱 Protocol Buffers ,是一種輕量級的資料交換格式,最初是由 Google 開發的「可擴展的序列化資料結構」,現已成為一個開源項目,其語⾔中⽴且平台無關,適合高性能且對響應速度有高要求的資料傳輸場景;也因為有資料壓縮的能力,故也可用於資料儲存。Protobuf 的核心思想是先定義好 data schema ,然後可根據所需的語言生成對應的 code base,方便使用者操作 :「序列化寫入、反序列化讀取」。
Profobuf 需要注意的缺點是為二進制格式,故編碼之後不具有可讀性,需要反序列化後才能看得懂資料內容 ; 雖然是個好東西,但並非是個用來完全取代 JSON 的解決方案,JSON 仍有其可讀性高、易操作及通用性高等優點,在多數 API 設計的場景之下,JSON 仍然是最好的選擇。
Avro 是一個 data serialization 框架 ,是 Apache Hadoop 下的一個子項目,是一個可跨多種程式語言和平台的傳輸資料格式。Avro 可使用 JSON 格式來描述 data structure,並且支持架構演進,保持向後、向前的相容性。 Avro 也提供了編解碼和二進制格式,使得在高吞吐量的應用場景中非常有用且高效。
Graph 用於表示物體與物體之間存在某種關係的結構,是內存中不一定連續的資料,每個節點會一個或多個 Reference 指向其他節點
- 可能有環
- 分無向圖和有向圖
- 沒有固定入口
- 可能有多個入口
二元搜尋樹(英語:Binary Search Tree),也稱為有序二元樹(ordered binary tree)或排序二元樹(sorted binary tree)。 從 wiki 上得到的時間與空間複雜度 :
演算法 平均 最差 空間 O(n) O(n) 搜尋 O(log n) O(n) 插入 O(log n) O(n) 刪除 O(log n) O(n)