ForkBase：一種面向區塊鏈及可分叉應用的高效存儲引擎！

科技 06-16

ForkBase是一種數據存儲系統，旨在支持需要數據版本控制、分叉和防篡改等功能的應用。一個主要的例子就是區塊鏈系統，但這還可能包括協作應用，比如GoogleDocs。舉例說，如今以太坊和HyperLedger的數據結構就直接建立在鍵值存儲系統上。ForkBase力求改而將上述這些屬性一路推送到存儲層：

一個直接的好處是，它為需要任意組合的上述功能的應用減少了開發工作。另一個好處是，它提供了額外的功能（比如高效的歷史查詢），根本無需額外成本，幫助應用更好地普及開來。最後，該存儲引擎可以利用在應用層很難實現的性能優化。

實際上我們最終得到的是一種建立在底層對象存儲系統上的鍵值存儲系統，直接支持版本控制、分叉和篡改證據。ForkBase的核心是一種新穎的索引結構，名為POS-Tree（面向模式的拆分樹）。

ForkBase架構

從下往上，ForkBase包括塊存儲層、表示層和一套數據訪問API，塊存儲層執行分塊和重複數據刪除，表示層管理版本、分支和防篡改，這套API結合了結構化數據類型和分叉語義。更高級的應用服務（比如訪問控制和自定義合併函數）可以實施在API的上面。

ForkBase是一種鍵值存儲系統，其中存儲的對象是FObject的實例。

數據版本控制

數據版本控制（保留每一個數據項的完整歷史記錄，包括任何分支和合併）方面的主要挑戰是，管理存儲的使用。很顯然，重複數據刪除大有機會，假設一個版本的內容與下一個版本並不完全改變。

基於增量數據（delta）的重複數據刪除功能僅存儲版本之間有差異的數據（delta），並通過遵循增量數據鏈來重構某個特定版本。在這種場景下，你可以嘗試調整存儲/重構成本取捨。

基於內容的重複數據刪除將數據拆分成塊，每個塊都由其內容（即內容的哈希）作為獨特的標識。然後可以檢測到同樣的數據塊，消除冗餘副本。

ForkBase選擇了在塊級進行基於內容的重複數據刪除。與文件系統中使用的類似技術相比，ForkBase使用更小的塊和可感知數據結構的分塊策略。比如說，一個列表只會在元素邊界處被拆分，那樣根本不需要用多個塊來重構列表項。ForkBase可識別許多不同類型的塊，每種類型的塊都由cid作為獨特的標識，cid就是塊內容的哈希。

可分塊的對象類型（Blob、List、Set和Map）以POS樹的形式存儲起來。

FObject的uid只是該對象的Meta塊的塊id的別名。

分叉語義

對分叉的支持基於兩個關鍵操作：分叉和衝突解決。分叉操作創建一個新的分支，分支與其他分支隔離開來的本地修改互相獨立發展。ForkBase支持按需求分叉和按衝突分叉。

通過API顯式請求按需求分叉，用用戶提供的名稱加以標記。一旦並發修改同一個數據項，隱式創建按衝突分叉。因Fork-on-Conflict而創建的分支是未標記的，就由其uid來標識。

標記的分支可以與另一個分支合併，由標記或版本作為標識。合併期間檢測到衝突時，將返回衝突列表，並要求應用層提供解決方案。有內置的解析函數適用於簡單的策略，比如追加、聚合和選擇一個。

篡改證據

FObject的uid是對象的值及其衍生歷史的獨特標識。因此，邏輯對等要求對象不僅有同樣的值，還有同樣的歷史記錄。諸版本用加密哈希鏈連接起來，確保能夠檢測到企圖篡改的任何行為。每個FObject存儲它從bases欄位獲得的之前版本的哈希。

面向模式的拆分樹

大型結構化對象通常不會全部訪問。相反，它們需要細粒度的訪問，比如元素查找、範圍查詢和更新。這些訪問模式需要索引結構（比如B+-tree）很高效。但是現有的索引結構並不適合有許多版本，且版本可以合併的環境。

B+-trees和變體的基於容量的拆分策略對索引的值及其插入順序非常敏感。這樣一來，更難跨版本進行重複數據刪除，合併兩個版本時也更難發現之間的差異。使用固定大小的節點可以避開插入順序問題，但由於結構中間的插入，帶來了另一個問題：邊界移位問題。

研究人員的解決辦法就是使用面向模式的拆分樹，它支持下列屬性：

快速查找和更新

快速確定兩棵樹之間的差異，然後合併

高效的重複數據刪除

篡改證據

樹中的每個節點都是一個塊（索引塊或樹葉處的對象塊）。查找遵循拆分鍵指引的一條路徑。子節點的cid是其內容的密碼哈希，就如默克爾樹（Merkle tree）中那樣。擁有同樣數據的兩個對象將有同樣的POS樹，樹比較提供了一種高效的遞歸解決方案。這裡真正的秘訣在於，POS樹如何決定在哪裡拆分。

其結構受到基於內容的分片的啟發，酷似B+-tree和默克爾樹的組合。在POS樹中，節點（即塊）邊界被定義為通過對象內容來檢測的模式。具體來說，想構建一個節點，我們會從頭開始掃描，直到一個預定義模式出現，然後創建新節點來保存掃描的內容。由於葉節點和內部節點的隨機性程度不一樣，我們為它們定義了不同的模式。

葉節點拆分使用滾動哈希函數來完成。只要滾動哈希中的q最低有效位都是零，模式匹配就會發生。如果模式匹配發生在元素的中間（比如Map的鍵值對），就會擴展塊邊界以覆蓋整個元素。因此，除最後一個節點以外的每個葉節點都以一個模式結束。

索引拆分使用一種更簡單的策略，尋找cid && (2^r -1) == 0的cid模式。可以通過為q和r選擇適當的值來配置期望的塊大小。為了確保塊不會隨意增大，可以強迫塊處於某個閾值。POS樹不是為對象內容僅僅是重複項的序列這種情況設計的――沒有模式，所有節點都傾向於最大塊大小，邊界移位問題又回來了。

ForkBase實戰：Hyperledger

論文的第5部分介紹了在ForkBase上構建區塊鏈平台、維基引擎和協作分析應用程序。我在這裡只想側重於區塊鏈使用場合，研究人員將Hyperledger v0.6移植到ForkBase的上面。

將Hyperledger移到ForkBase上只需要18行新的代碼，並且從Hyperledger代碼庫刪除1918行代碼。（請注意，ForkBase本身大約有3萬行代碼！）。

另一個好處是，數據現在隨時可用於分析。如果是狀態掃描查詢，我們只要關注存儲在最新塊中的版本號，即可獲得所請求的鍵的最新Blob對象。之後，我們關注base_version來檢索以前的值。如果是塊掃描查詢，我們關注存儲在請求塊上的版本號來檢索此塊的二級Map對象。然後，我們遍歷鍵值元組，並檢索相應的Blob對象。

狀態掃描（返回特定狀態的歷史記錄）和塊掃描（返回特定塊的狀態值）在最初的Hyperledger代碼庫中比較慢，該代碼庫是為快速訪問最新狀態而設計的。（注意：這似乎要引用HyperLedger的對等事務管理器即PTM組件。Hyperledger還包含被索引的塊存儲系統）。

在這些掃描操作中，ForkBase顯示出最大的性能優勢。如果我們考慮延遲和吞吐量，基於ForkBase的Hyperledger實現和基於Rocksdb的Hyperledger實現非常接近。（下圖中的ForkBase-KV是Hyperledger使用ForkBase作為純粹的鍵值存儲系統，並沒有充分利用任何高級功能）。