本文為 Geth 客戶端有問必答系列的第一篇文章，大家可以就 Geth 客戶端的問題踴躍提問，我會每週用一篇小文章回答得票最高的問題。本週呼聲最高的問題是：你能說說 flat 資料庫結構與 legacy 結構的主要區別嗎？以太坊的狀態在深入瞭解加速結構（acceleration structure）之前，我們先回顧一下以太坊的 “狀態” 概念、狀態在涉及到不同層次的抽象時又是如何儲存的。以太坊有兩種不同型別的狀態：賬戶的集合；每一合約賬戶儲存槽的集合。從 完全抽象的角度 來看，兩種資料都是 鍵-值 對。賬戶集合把地址對映到該地址的 nonce、餘額，等等。而一個合約的儲存領域把任意的值（由該合約定義並使用）對映到某個值。但糟糕的是，雖然把這些鍵值對儲存成扁平資料（flat data）可以非常高效，但驗證它們的正確性在計算上就會變得很難。每當對資料修改時，我們都要自下而上對所有資料做雜湊運算。為免去總是對整個資料庫做雜湊運算的需要，我們可以把資料庫分割成連續的小片，然後建立出一種樹狀結構！最原始、最有用的資料就放在葉子節點上，然後樹上每一個內部節點都是該節點以下內容的雜湊值。如此一來，當我們要修改某些值時，就只需做對數次的雜湊運算。這種資料結構其實有一個路人皆知的名字，就是 “默克爾樹”。但還沒完，這種辦法在計算複雜性上還是有所欠缺。默克爾樹結構雖然在修改現有資料時非常高效，但是，如果插入資料和刪除資料會更改底層小資料塊的邊界，那就會讓所有已經算好的雜湊值全都變為無效。這時候，與其盲目地對資料庫分組，我們可以使用鍵本身來組織資料、基於共同字首將資料都安排到樹狀格式中！這樣插入和刪除操作都不會影響到所有節點，只會影響到從樹根到葉子路徑上的（對數個）節點。這種資料結構就叫 “帕特里夏樹”。把上面兩種辦法合在一起 —— 帕特里夏樹的樹狀分層和默克爾樹的雜湊演算法 —— 就是所謂的 “默克爾-帕特里夏樹”，也是實踐中用於代表以太坊狀態的資料結構。無論是修改、插入、刪除還是驗證，都只有對數複雜度！唯一的小小例外是，有些鍵會在插入前做雜湊運算（存入樹中），以平衡整棵樹（A tiny extra is that keys are hashed before insertion to balance the tries）。以太坊的狀態儲存上文解釋了為什麼以太坊要用默克爾帕特里夏樹結構來儲存其狀態。遺憾的是，雖然所需操作的速度都很快，但每一種選擇都有所犧牲。更新操作和驗證操作的對數複雜性 意味著對 每一個單獨的金鑰 的讀取和儲存都是對數複雜的（logarithmic reads and logarithmic storage）。這是因為樹狀結構的每一個內部節點都要單獨儲存在硬碟上。此時此刻，賬戶樹的深度確切是多少我不知道，但在大約一年以前，賬戶狀態就已填滿了 7 層高的樹。這就意味著，每一次樹操作（例如讀取餘額、寫入 nonce）都要觸達至少 7～8 個內部節點，因此會做至少 7～8 次持久資料庫訪問（persistent database accesses）。LevelDB 組織資料時最多也是 7 層，所以還有一個額外的乘數。最終的結果是，單次 狀態訪問預計會放大為 25～50 次隨機的 硬碟訪問。你再乘上一個區塊中的所有交易的所有狀態讀取和寫入，你會得到一個 嚇人 的數字。[當然，所有客戶端實現都在盡力降低開銷。Geth 使用更大的記憶體區域來快取數節點；還使用了記憶體內的修剪機制、避免將幾個塊之後就會刪除的資料寫入硬碟。不過這需要另外一篇文章才能講清楚。]可怕之處還在於，這個數字就是執行一個以太坊節點、保證能全時驗證所有狀態的成本。我們能做得更好一點嗎？並不是所有訪問都要一視同仁以太坊的執行依賴於對狀態的密碼學證明。只要我們還想保持對所有資料的驗證能力，就繞不開硬碟讀寫放大問題。也就是說，我們 —— 可以並且也事實上 —— 相信我們已經驗證過的資料。不斷重複驗證每一個狀態物是沒有意義的，但如果每次從硬碟中拉取資料都要驗證一次的話，就是在做這樣沒有意義的事。默克爾帕特里夏樹結構本質上是為寫入操作設計的，但反過來就成了讀取操作的負擔。我們擺脫不了它，也無法讓它瘦身，但 這絕不意味著 我們在每一個場合都必須使用它。以太坊節點訪問狀態的場景可大致分為以下三類：在匯入一個新區塊的時候，EVM 程式碼的執行會產生或多或少基本平衡的狀態讀取和寫入次數。不過，一個用於拒絕服務式攻擊的區塊可能會產生遠多於寫入操作的讀取操作次數。當節點運營者檢索狀態的時候（例如呼叫 eth_call 及類似操作），EVM 程式碼執行僅產生讀取操作（當然也可能有寫入操作，但這些操作產生的資料最終會丟棄掉，不會持久化到硬碟裡面）。當節點在同步區塊鏈的時候，同步者會向遠端節點請求狀態，被請求者會將資料探勘出來並透過網路傳播給同步者。基於上述訪問模式，如果我們可以短路（short circuit）讀取操作而不觸及狀態樹，則許多節點操作都可以變得快 很多。這樣甚至能開啟一些新奇的訪問模式（比如狀態迭代），讓原來因為太過昂貴而不可行的模式變為可能。當然，還是不免有所犧牲。沒有去掉樹結構，任何新的加速結構都會帶來額外的開銷。問題只在於：額外的開銷是否能帶來足夠多的好處，值得我們一試？請循其本我們已經開發出了神奇的默克爾帕特里夏樹結構來解決我們所有的問題，現在，我們希望讓讀取操作能繞過它。那麼，我們應該用什麼樣的加速結構來讓讀取操作重新變得快起來呢？顯然，如果我們不需要樹結構，那就大可以把伴隨樹結構而生的複雜性都丟在一邊，我們可以直接回到原始狀態。如同在本文開頭說到的那樣，理論上的理想狀態下 以太坊狀態的資料儲存方式應是簡單鍵值對，沒了默克爾帕特里夏樹構成的限制，那就沒有什麼能阻止我們去實現這種理想方案了！不久之前，Geth 引入了 snapshot（快照）加速結構（不是預設開啟的）。一個快照就是給定一個區塊處的以太坊狀態的完整檢視。抽象掉實現方面的細節，它就是把所有賬戶和合約儲存槽堆放在一起，都由扁平的鍵值對來表示。每當我們想要訪問某個賬戶或者某個儲存槽的時候，我們只需付出一次 LevelDB 的查詢操作即可，而不用在每棵樹上查詢 7～8 次。理論上來說，更新快照也很簡單，處理完一個區塊後，我們只需為每個要更新的儲存槽多做 1 次額外的 LevelDB 寫入操作即可。快照加速結構實際上將讀取操作的複雜性從 O(log n) 降到了 O(1) （乘以 LevelDB 的開銷），代價是將寫入操作的複雜性從 O(log n) 變成了 O(1 + log n) （乘以 LevelDB 的開銷），並將硬碟儲存空間從 O(n log n) 增加到了 O(n + n log n)。魔鬼藏在細節中維持以太坊狀態快照的可用性也不容易。只要區塊還在一個接一個地產生，一個接一個地摞在最後一個區塊上，那將最新變更合併到快照中的粗疏辦法就能正常工作。但是，哪怕有微小的區塊鏈重組（即便只有一個區塊），快照機制就崩潰了，因為根本沒有設計撤銷操作。對扁平資料表示模式來說，持久化寫入是單向的操作。而且讓事情變得更糟糕的是，我們沒辦法訪問更老的狀態了（例如某些 dApp 需要 3 個區塊以前的狀態；或者 fast/snap 同步模式中要訪問 64 個區塊以前的狀態）。為了克服這些限制，Geth 客戶端的快照由兩部分組成：一部分持久化的硬碟層，是對舊區塊（例如頂端區塊前 128 個區塊）處狀態的完整快照；還有一棵記憶體內 diff 層組成的樹，用於收集最新的寫入操作。處理新區塊的時候，我們不會直接合並這些寫入操作到硬碟層，而僅僅是建立一個新的、包含這些變更的記憶體內 diff 層。當記憶體內部的 diff 層積累到足夠高的層數時，最底部的一個就開始合併更新並推到硬碟層。當需要讀取一個狀態物時，我們就從最頂端的 diff 層開始查詢，一直往下，直至在 diff 層中或者在硬碟層中找到。這種資料表示方法非常強大，解決了很多問題。因為記憶體內部的 diff 層組成了一棵樹，所以 128 個區塊以內的鏈重組只需取出屬於父塊的 diff 層，然後就此開始構建即可。需要較舊狀態的 dApp 和遠端同步者可以訪問到最近 128 個最近的狀態。開銷變成了 128 次對映查詢，但 128 次記憶體內的查詢比起 8 次硬碟讀取及 Level DB 的 4～5 倍放大要快上幾個數量級。當然，這裡面還有很多很多的坑。就不講太深了，簡單列舉就有下面這張清單：· Self-destruct （合約自毀操作）（以及刪除操作）特別難以對付，因為它們需要短路 diff 層的沉降（descent）。· 如果出現了比持久硬碟層更深的鏈重組，那現在的快照就要完全廢棄掉、重新生成。整套操作非常昂貴。· 在節點關機時，記憶體內的 diff 層需要持久化到日誌並載入備份，不然重啟之後快照就沒用了。· 使用最底層的 diff 層作為一個累加器，僅在其超過一定的記憶體使用時才重新整理到硬碟。這就允許跨區塊對同一儲存槽執行去重寫入操作（deduping write）。· 要為硬碟層分配一個讀取快取，這樣合約重複訪問同一個古老的儲存槽時硬碟才不會損壞。· 在記憶體內 diff 層中使用累積的布隆過濾器（bloom filter），以便快速檢測出狀態物有沒有可能存在於 diff 層中，還是應該直接跳到硬碟中查詢。· 不把原始資料（賬戶地址、合約儲存鍵）設為鍵，而是以這些資料的雜湊值為鍵，以保證快照的迭代順序與默克爾帕特里夏樹相同。· 生成持久化硬碟層的時間要比剪除狀態樹視窗的時間多得多，所以即使是生成器，也需要動態地追蹤鏈的執行。美醜並存Geth 的快照加速結構將狀態讀取的複雜性降低了一個數量級。這就意味著基於讀取操作的 DoS 攻擊的發動難度上了一個數量級，而 eth_call 呼叫也快了一個數量級（假設 CPU 不存在瓶頸的話）。快照還讓對最近的塊進行極速狀態迭代成為可能。實際上這曾是我們開發快照機制的主要理由，因為我們可以此為基礎創造新的 snap 同步演算法。講清楚它需要一篇全新的文章，但最近我們在 Rinkeby 測試網上的基準測試很能說明問題：
當然，這一切同樣不是沒有代價的。當初始同步完成之後，參與主網的節點需要 9～10 小時來建構初始快照（此後再維持其可用性），還需要額外的 15 GB 以上的硬碟。
那糟糕的部分是哪裡呢？我們花了 6 個月時間才積累起足夠的自信、釋出了快照機制，而且現在它仍然不是預設功能，需要主動使用 --snapshot 標記來開啟，而且還有一些圍繞記憶體使用和崩潰恢復的打磨工作要做。
總而言之，對於這一提升，我們非常自豪。其中有巨大的工作量，而且是在黑暗中摸索、自己實現所有東西並祈禱它能工作。還有一個有趣的事情，第一個版本的快照同步（leaf sync）是在兩年半以前寫的，但一直都處於被阻塞的狀態，因為我們缺乏必要的加速結構來驅動它。
結語
希望你能喜歡 Geth 客戶端有問必答 的這一篇文章。我花了比自己所預想的多出一倍的時間，但我並不後悔，因為這個主題值得。下週見。
[又：我故意不在文章裡留下 提問/投票 的網站，因為我確信這個活動只是暫時的，我不想留下一個沒用的超連結，也不希望有人會在未來買下那個域名並託管惡意資訊。你可以在我的 Twitter 中找到那個網站。]
