DDIA 讀書筆記(四):編碼和演進

語言: CN / TW / HK

DDIA 讀書分享會,會逐章進行分享,結合我在工業界分散式儲存和資料庫的一些經驗,補充一些細節。每兩週左右分享一次,歡迎加入,Schedule 在 這裡 。我們有個對應的分散式&資料庫討論群,每次分享前會在群裡通知。如想加入,可以加我的微訊號:qtmuniao,簡單自我介紹下,並註明:分散式系統群。

第三章講了儲存引擎,本章繼續下探,探討編碼相關問題。

所有涉及跨程序通訊的地方,都需要對資料進行 編碼Encoding ),或者說 序列化Serialization )。因為持久化儲存和網路傳輸都是面向位元組流的。序列化本質上是一種“ 降維 ”操作,將記憶體中高維的資料結構降維成單維的位元組流,於是底層硬體和相關協議,只需要處理一維資訊即可。

作者:木鳥雜記 https://www.qtmuniao.com/2022/04/16/ddia-reading-chapter4 轉載請註明出處

編碼主要涉及兩方面問題:

  1. 如何編碼能夠節省空間、提高效能。
  2. 如何編碼以適應資料的演化和相容。

第一小節,以幾種常見的編碼工具(JSON,XML,Protocol Buffers 和 Avro)為例,逐一探討了其如何進行編碼、如何進行多版本相容。這裡引出了兩個非常重要的概念:

  1. 向後相容 (backward compatibility):當前程式碼可以讀取舊版本程式碼寫入的資料。
  2. 向前相容(forward compatibility):當前程式碼可以讀取新版本程式碼寫入的資料。

翻譯成中文後,很容易混淆,主要原因在於“後”的歧義性,到底指 身後 (過去),還是指 之後 (將來),私以為還不如翻譯為, 相容過去相容將來 。但為了習慣,後面行文仍然用向後/前相容。

其中,向後相容比較常見,因為時間總是向前流逝,版本總是升級,那麼升級之後的程式碼總要處理歷史積壓的資料,自然會產生向後相容的問題。向前相容比較少見,書中給出的例子是多例項滾動升級,但其持續時間也很短。

第二小節,結合幾個具體的應用場景:資料庫、服務和訊息系統,來分別談了相關資料流中涉及到的編碼與演化。

資料編碼的格式

編碼(Encoding)有多種稱謂,如 序列化(serialization) 或  編組(marshalling) 。對應的,解碼(Decoding)也有多種別稱, 解析(Parsing)反序列化(deserialization)反編組 (unmarshalling)。

  • 為什麼記憶體中資料和外存、網路中的會有如此不同呢?

    在記憶體中,藉助編譯器,我們可以將記憶體解釋為各種資料結構;但在檔案系統和網路中,我們只能通過 seek\read 等幾個有限的操作來流式的讀取位元組流。那 mmap 呢?

  • 編碼和序列化撞車了?

    在事務中,也有序列化相關的術語,所以這裡專用編碼,以避免歧義。

  • 編碼(encoding)和加密( encryption )?

    研究的範疇不太一樣,編碼是為了持久化或者傳輸,著重點在格式和演化;而加密是為了安全,著重點在於安全、防破解。

程式語言內建

很多程式語言內建了一些預設的編碼方法:

java.io.Serializable
Marshal
pickle

如果你確定你的資料只會被某種特定的語言所讀取,那麼這種內建的編碼方法很好用。比如深度學習研究員因為基本都用 Python,所以常會把資料以 pickle 的格式傳來傳去。

但這些程式語言內建的編碼格式有以下缺點:

  1. 和特定語言繫結
  2. 安全問題
  3. 相容性支援不夠
  4. 效率不高

JSON、XML 及其二進位制變體

JSON,XML 和 CSV 屬於常用的 文字編碼 格式,其好處在於肉眼可讀,壞處在於不夠緊湊,佔空間較多。

JSON 最初由 JavaScript 引入,因此在 Web Service 中用的較多,當然隨著 web 的火熱,現在成為了比較通用的編碼格式,比如很多日誌格式就是 JSON 的。

XML 比較古老了,比 JSON 冗餘度還高,有時候配置檔案中會用,但總體而言用的越來越少了。

CSV (以逗號\TAB、換行符分割)還算緊湊,但是表達能力有限。資料庫表匯出有時會用。

除了不夠緊湊外, 文字編碼(text encoding) 還有以下缺點:

  1. 數值型別支援不夠 。CSV 和 XML 直接不支援,萬物皆字串。JSON 雖區分字串和數值,但是不進一步區分細分數值型別。可以理解,畢竟文字編碼嘛,主要還是面向字串。
  2. 對二進位制資料支援不夠 。支援 Unicode,但是對二進位制串支援不夠,可能會顯示為亂碼。雖然可以通過 Base64 編碼來繞過,但有點做無用功的感覺。
  3. XML和 JSON 支援額外的模式 。模式會描述資料的型別,告訴你如何理解資料。配合這些模式語言,雖然可以讓 XML 和 JSON 變得強大,但是大大增加了複雜度。
  4. CSV 沒有任何模式

凡事講究夠用,很多場景下需要資料可讀,並且不關心編碼效率,那麼這幾種編碼格式就夠用了。

二進位制編碼

如果資料只被單一程式讀取,不需要進行交換,不需要考慮易讀性等問題。則可以用二進位制編碼,在資料量到達一定程度後,二進位制編碼所帶來的空間節省、速度提高都很可觀。

因此,JSON 有很多二進位制變種:MessagePack、BSON、BJSON、UBJSON、BISON 和 Smile 等。

對於下面例子,

{
    "userName": "Martin",
    "favoriteNumber": 1337,
    "interests": ["daydreaming", "hacking"]
}

如果用 MessagePack 來編碼,則為:

可以看出其基本編碼策略為:使用型別,長度,bit 串,順序編碼,去掉無用的冒號、引號、花括號。

從而將 JSON 編碼的 81 位元組縮小到了 66 位元組,微有提高。

Thrift 和 Protocol Buffers

Thrift 最初由 Facebook,ProtoBuf 由 Google 在 07~08 年左右開源。他們都有對應的 RPC 框架和編解碼工具。表達能力類似,語法也類似,在編碼前都需要由介面定義語言(IDL)來描述模式:

struct Person {
    1: required string       userName,
    2: optional i64          favoriteNumber,
    3: optional list<string> interests
}
message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

IDL 是程式語言無關的,可以利用相關程式碼生成工具,可以將上述 IDL 翻譯為指定語言的程式碼。即,整合這些生成的程式碼,無論什麼樣的語言,都可以使用同樣的格式編解碼。

這也是不同 service 可以使用不同編碼語言,且能夠互相通訊的基礎。

此外,Thrift 還支援多種不同的編碼格式,常用的有:Binary、Compact、JSON。可以讓使用者自行在:編碼速度、佔用空間、可讀性方便進行取捨。

可以看出其特點:

  1. 使用 field tag 編碼 。field tag 其實蘊含了欄位 型別名字
  2. 使用型別、tag、長度、bit 陣列的順序編碼。

相比 Binary Protocol,Compact Protocol 由以下優化:

  1. filed tag 只記錄 delta。
  2. 從而將 field tag 和 type 壓縮到一個位元組中。
  3. 對數字使用變長編碼和 Zigzag編碼

ProtoBuf 與 Thrift Compact Protocol 編碼方式很類似,也用了變長編碼和 Zigzag 編碼。但 ProtoBuf 對於陣列的處理與 Thrift 顯著不同,使用了 repeated 字首而非真陣列,好處後面說。

欄位標號和模式演變

模式,即有哪些欄位,欄位分別為什麼型別。

隨著時間的推移,業務總會發生變化,我們也不可避免的 增刪欄位修改欄位型別 ,即 模式演變

在模式發生改變後,需要:

  1. 向後相容 :新的程式碼,在處理新的增量資料格式的同時,也得處理舊的存量資料。
  2. 向前相容 :舊的程式碼,如果遇到新的資料格式,不能 crash。
  • ProtoBuf 和 Thrift 是怎麼解決這兩個問題的呢?

    欄位標號+ 限定符 (optional、required)

    向後相容:新加的欄位需為 optional。這樣在解析舊資料時,才不會出現欄位缺失的情況。

    向前相容:欄位標號不能修改,只能追加。這樣舊程式碼在看到不認識的標號時,省略即可。

資料型別和模式演變

修改資料型別比較麻煩:只能夠在相容型別中進行修改。

如不能將字串修改為整形,但是可以在整形內修改: 32 bit 到 64 bit 整形。

ProtoBuf 沒有列表型別,而有一個 repeated 型別。其好處在於 相容陣列型別 的同時,支援將可選(optional) 單值欄位 ,修改為 多值欄位 。修改後,舊程式碼在看到新的多值欄位時,只會使用最後一個元素。

Thrift 列表型別雖然沒這個靈活性,但是可以 巢狀 呀。

Avro

Apache Avro 是 Apache Hadoop 的一個子專案,專門為資料密集型場景設計,對模式演變支援的很好。支援 Avro IDLJSON 兩種模式語言,前者適合人工編輯,後者適合機器讀取。

record Person {
    string                userName;
    union { null, long }  favoriteNumber = null;
    array<string>         interests;
}
{
    "type": "record",
    "name": "Person",
    "fields": [
        {"name": "userName", "type": "string"},
        {"name": "favoriteNumber", "type": ["null", "long"], "default": null},
        {"name": "interests", "type": {"type": "array", "items": "string"}}
    ]
}

可以看到 Avro 沒有使用欄位標號。

  • 仍是編碼之前例子,Avro 只用了 32 個位元組,為什麼呢?

    他沒有編入型別。

因此,Avro 必須配合模式定義來解析,如 Client-Server 在通訊的握手階段會先交換資料模式。

寫入模式和讀取模式

  • 沒有欄位標號,Avro 如何支援模式演進呢?

    答案是 顯式的 使用兩種模式。

即,在對資料進行編碼(寫入檔案或者進行傳輸)時,使用模式 A,稱為 寫入模式 (writer schema);在對資料進行解碼(從檔案或者網路讀取)時,使用模式 B,稱為 讀取模式 (reader schema),而兩者不必相同,只需相容。

也就是說,只要模式在演進時,是 相容 的,那麼 Avro 就能夠處理向後相容和向前相容。

向後相容:新程式碼讀取舊資料。即讀取時首先得到舊資料的寫入模式(即舊模式),然後將其與讀取模式(即新模式)對比,得到轉換對映,即可拿著此對映去解析舊資料。

向前相容:舊程式碼讀取新資料。原理類似,只不過是需要得到一個逆向對映。

在由寫入模式到讀取模式建立對映時有一些規則:

  1. 使用欄位名來進行匹配 。因此寫入模式和讀取模式欄位名順序不一樣無所謂。
  2. 忽略多出的欄位
  3. 對缺少欄位填預設值

模式演化規則

  • 那麼如何保證寫入模式的相容呢?
    1. 在增刪欄位時,只能新增或刪除具有預設值的欄位。
    2. 在更改欄位型別時,需要 Avro 支援相應的型別轉換。

Avro 沒有像 ProtoBuf、Thrift 那樣的 optional 和 required 限定符,是通過 union 的方式,裡指定預設值,甚至多種型別:

union {null, long, string} field;

注:預設值必須是聯合的第一個分支的型別。

更改欄位名和在 union 中新增型別,都是向後相容,但是不能向前相容的,想想為什麼?

如何從編碼中獲取寫入模式

對於一段給定的 Avro 編碼資料,Reader 如何從其中獲得其對應的寫入模式?

這取決於不同的應用場景。

  • 所有資料條目同構的大檔案

    典型的就是 Hadoop 生態中。如果一個大檔案所有記錄都使用相同模式編碼,則在檔案頭包含一次寫入模式即可。

  • 支援模式變更的資料庫表

    由於資料庫表允許模式修改,其中的行可能寫入於不同模式階段。對於這種情況,可以在編碼時額外記錄一個模式版本號(比如自增),然後在某個地方儲存所有的模式版本。

    解碼時,通過版本去查詢對應的寫入模式即可。

  • 網路中傳送資料

    在兩個程序通訊的握手階段,交換寫入模式。比如在一個 session 開始時交換模式,然後在整個 session 生命週期內都用此模式。

動態生成資料中的模式

Avro 沒有使用欄位標號的一個好處是,不需要手動維護欄位標號到欄位名的對映,這對於動態生成的資料模式很友好。

書中給的例子是對資料庫做匯出備份,注意和資料庫本身使用 Avro 編碼不是一個範疇,此處是指匯出的資料使用 Avro 編碼。

在資料庫表模式發生改變前後,Avro 只需要在匯出時依據當時的模式,做相應的轉換,生成相應的模式資料即可。但如果使用 PB,則需要自己處理多個備份檔案中,欄位標號到欄位名稱的對映關係。其本質在於,Avro 的資料模式可以和資料存在一塊,但是 ProtoBuf 的資料模式只能體現在生成的程式碼中,需要手動維護新舊版本備份資料與PB 生成的程式碼間的對映。

程式碼生成和動態語言

Thrift 和 Protobuf 會依據語言無關的 IDL 定義的模式,生成給定語言的編解碼的程式碼。這對靜態語言很有用,因為它允許利用 IDE 和編譯器進行型別檢查,並且能夠提高編解碼效率。

上述思路本質上在於,將模式內化到了生成的程式碼中。

但對於動態語言,或者說解釋型語言,如 JavaScript、Ruby 或 Python,由於沒有了編譯期檢查,生成程式碼的意義沒那麼大,反而會有一定的冗餘。這時 Avro 這種支援不生成程式碼的框架就節省一些,它可以將模式寫入資料檔案,讀取時利用 Avro 進行動態解析即可。

模式的優點

模式的本質是顯式型別約束,即,先有模式,才能有資料。

相比於沒有任何型別約束的文字編碼 JSON,XML 和 CSV,Protocol Buffers,Thrift 和 Avro 這些基於顯式定義二進位制編碼優點有:

  1. 省去欄位名,從而更加緊湊。
  2. 模式是資料的註釋或者文件,並且總是最新的。
  3. 資料模式允許不讀取資料,僅比對模式來做低成本的相容性檢查。
  4. 對於靜態型別來說,可以利用程式碼生成做編譯時的型別檢查。

模式演化 vs 讀時模式

幾種資料流模型

資料可以以很多種形式從一個系統流向另一個系統,但不變的是,流動時都需要編碼與解碼。

在資料流動時,會涉及編解碼雙方模式匹配問題,上一小節已經討論,本小節主要探討幾種程序間典型的資料流方式:

  1. 通過資料庫
  2. 通過服務呼叫
  3. 通過非同步訊息傳遞

經由資料庫的資料流

訪問資料庫的程式,可能:

  1. 只由同一個程序訪問 。則資料庫可以理解為該程序向將來發送資料的中介。
  2. 由多個程序訪問 。則多個程序可能有的是舊版本,有的是新版本,此時資料庫需要考慮向前和向後相容的問題。

還有一種比較棘手的情況:在某個時刻,你給一個表增加了一個欄位,較新的程式碼寫入帶有該欄位的行,之後又被較舊的程式碼覆蓋成缺少該欄位的行。這時候就會出現一個問題:我們更新了一個欄位 A,更新完後,卻發現欄位 B 沒了。

不同時間寫入的資料

對於應用程式,可能很短時間就可以由舊版本替換為新版本。但是對於資料,舊版本的程式碼寫入的資料量,經年累月,可能很大。在變更了模式之後,由於這些舊模式的資料量很大,全部更新對齊到新版本的代價很高。

這種情況我們稱之為: 資料的生命週期超過了其對應程式碼的生命週期

在讀取時,資料庫一般會對缺少對應列的舊資料:

  1. 填充新版本欄位的 預設值 (default value)
  2. 如果沒有預設值則填充 空值 (nullable)

後返回給使用者。一般來說,在更改模式時(比如 alter table),資料庫不允許增加既沒有預設值、也不允許為空的列。

儲存歸檔

有時候需要對資料庫做備份到外存。在做備份(或者說快照)時,雖然會有不同時間點生成的資料,但通常會將各種版本資料轉化、對齊到最新版本。畢竟,總是要全盤拷貝資料,那就順便做下轉換好了。

之前也提到了,對於這種場景,生成的是一次性的不可變的備份或者快照資料,使用 Avro 比較合適。此時也是一個很好地契機,可以將資料按需要的格式輸出,比如面向分析的按列儲存格式: Parquet

經由服務的資料流:REST 和 RPC

通過網路通訊時,通常涉及兩種角色:伺服器(server)和客戶端(client)。

通常來說,暴露於公網的多為 HTTP 服務,而 RPC 服務常在內部使用。

伺服器也可以同時是客戶端:

  1. 作為客戶端訪問資料庫。
  2. 作為客戶端訪問其他服務。

對於後者,是因為我們常把一個大的服務拆成一組功能獨立、相對解耦的服務,這就是 面向服務的架構(service-oriented architecture,SOA) ,或者最近比較火的 微服務架構(micro-services architecture) 。這兩者有一些不同,但這裡不再展開。

服務在某種程度上和資料庫類似:允許客戶端以某種方式儲存和查詢資料。但不同的是,資料庫通常提供某種靈活的查詢語言,而服務只能提供相對死板的 API。

web 服務

當服務使用 HTTP 作為通訊協議時,我們通常將其稱為 web 服務 。但其並不侷限於 web,還包括:

  1. 使用者終端(如移動終端)通過 HTTP 向伺服器請求。
  2. 同組織內的一個服務向另一個服務傳送 HTTP 請求(微服務架構,其中的一些元件有時被稱為中介軟體)。
  3. 不同組織的服務進行資料交換。一般要通過某種手段進行驗證,比如 OAuth。

有兩種設計 HTTP API 的方法:REST 和 SOAP。

  1. REST 並不是一種協議,而是一種設計哲學 。它強調簡單的 API 格式,使用 URL 來標識資源,使用 HTTP 的動作(GET、POST、PUT、DELETE )來對資源進行增刪改查。由於其簡潔風格,越來越受歡迎。
  2. SOAP 是基於 XML 的協議。雖然使用 HTTP,但目的在於獨立於 HTTP。現在提的比較少了。

RPC 面臨的問題

RPC 想讓呼叫遠端服務像呼叫本地(同進程中)函式一樣自然,雖然設想比較好、現在用的也比較多,但也存在一些問題:

  1. 本地函式呼叫要麼成功、要麼不成功。但是 RPC 由於經過網路,可能會有各種複雜情況,比如請求丟失、響應丟失、hang 住以至於超時等等。因此,可能需要重試。
  2. 如果重試,需要考慮 冪等性 問題。因為上一次的請求可能已經到達了服務端,只是請求沒有成功返回。那麼多次呼叫遠端函式,就要保證不會造成額外副作用。
  3. 遠端呼叫延遲不可用,受網路影響較大。
  4. 客戶端與服務端使用的程式語言可能不同,但如果有些型別不是兩種語言都有,就會出一些問題。

REST 相比 RPC 的好處在於,它不試圖隱去網路,更為顯式,讓使用者不易忽視網路的影響。

RPC 當前方向

儘管有上述問題,但其實在工程中,大部分情況下,上述情況都在容忍範圍內:

  1. 比如區域網的網路通常比較快速、可控。
  2. 多次呼叫,使用冪等性來解決。
  3. 跨語言,可以使用 RPC 框架的 IDL 來解決。

但 RPC 程式需要考慮上面提到的極端情況,否則可能會偶然出一個很難預料的 BUG。

另外,基於二進位制編碼的 RPC 通常比基於 HTTP 服務效率更高。但 HTTP 服務,或者更具體一點,RESTful API 的好處在於,生態好、有大量的工具支援。而 RPC 的 API 通常和 RPC 框架生成的程式碼高度相關,因此很難在不同組織中無痛交換和升級。

因此,如本節開頭所說:暴露於公網的多為 HTTP 服務,而 RPC 服務常在內部使用。

資料編碼和 RPC 的演化

通過服務的資料流通常可以假設:所有的伺服器先更新,然後服務端再更新。因此,只需要在請求裡考慮後向相容性,在響應中考慮前向相容性:

  1. Thrift、gRPC(Protobuf)和 Avro RPC 可以根據編碼格式的相容性規則進行演變。
  2. RESTful API 通常使用 JSON 作為請求響應的格式,JSON 比較容易新增新的欄位來進行演進和相容。
  3. SOAP 按下不表。

對於 RPC,服務的相容性比較困難,因為一旦 RPC 服務的 SDK 提供出去之後,你就無法對其生命週期進行控制:總有使用者因為各種原因,不會進行主動升級。因此可能需要長期保持相容性,或者提前通知和不斷預告,或者維護多個版本 SDK 並逐漸對早期版本進行淘汰。

對於 RESTful API,常用的相容方法是,將版本號做到 URL 或者 HTTP 請求頭中。

經由訊息傳遞的資料流

前面研究了編碼解碼的不同方式:

  1. 資料庫:一個程序寫入(編碼),將來一個程序讀取(解碼)
  2. RPC 和 REST:一個程序通過網路(傳送前會編碼)向另一個程序傳送請求(收到後會解碼)並同步等待響應。

本節研究介於資料庫和 RPC 間的 非同步訊息系統 :一個儲存(訊息 broker、訊息佇列來臨時儲存訊息)+ 兩次 RPC(生產者一次,消費者一次)。

與 RPC 相比,使用訊息佇列的優點:

  1. 如果消費者暫時不可用,可以充當暫存系統。
  2. 當消費者宕機重啟後,自動地重新發送訊息。
  3. 生產者不必知道消費者 IP 和埠。
  4. 能將一條訊息傳送給多個消費者。
  5. 將生產者和消費者解耦。

訊息佇列

書中用的是 訊息代理 (Message Broker),但另一個名字,訊息佇列,可能更為大家熟知,因此,本小節之後行文都用訊息佇列。

過去,訊息佇列為大廠所壟斷。但近年來,開源的訊息佇列越來越多,可以適應不同場景,如 RabbitMQ、ActiveMQ、HornetQ、NATS 和 Apache Kafka 等等。

訊息佇列的 送達保證 因實現和配置而異,包括:

  1. 最少一次 (at-least-once) :同一條資料可能會送達多次給消費者。
  2. 最多一次(at-most-once) :同一條資料最多會送達一次給消費者,有可能丟失。
  3. 嚴格一次(exactly-once) :同一條資料保證會送達一次,且最多一次給消費者。

訊息佇列的邏輯抽象叫做 Queue 或者 Topic ,常用的消費方式兩種:

  1. 多個消費者互斥消費一個 Topic
  2. 每個消費者獨佔一個 Topic

注:我們有時會區分這兩個概念:將點對點的互斥消費稱為 Queue,多點對多點的釋出訂閱稱為 Topic,但這並不通用,或者說沒有形成共識。

一個 Topic 提供一個單向資料流,但可以組合多個 Topic,形成複雜的資料流拓撲。

訊息佇列通常是面向 位元組陣列 的,因此你可以將訊息按任意格式進行編碼。如果編碼是前後向相容的,同一個主題的訊息格式,便可以進行靈活演進。

分散式的 Actor 框架

Actor 模型是一種基於訊息傳遞的併發程式設計模型。 Actor 通常是由狀態(State)、行為(Behavior)和信箱(MailBox,可以認為是一個訊息佇列)三部分組成:

  1. 狀態:Actor 中包含的狀態資訊。
  2. 行為:Actor 中對狀態的計算邏輯。
  3. 信箱:Actor 接受到的訊息快取地。

由於 Actor 和外界互動都是通過訊息,因此本身可以並行的,且不需要加鎖。

分散式的 Actor 框架,本質上是將訊息佇列和 actor 程式設計模型整合到一塊。自然,在 Actor 滾動升級是,也需要考慮前後向相容問題。

我是青藤木鳥,一個喜歡攝影的分散式系統程式設計師。如果你覺得文章還不錯,歡迎關注我的公眾號:“木鳥雜記”,比心~