一.概述
在以太坊中，資料的儲存大致分為三個部分，分別是：狀態資料、區塊鏈和底層資料。
其中，底層資料存放以太坊中全部資料，儲存形式是[k,v]鍵值對，目前使用資料庫是LevelDB;所有與交易，操作相關的資料，都儲存在鏈上;StateDB 是用來管理賬戶的，每個賬戶都是一個 stateObject。
二.區塊部分
區塊結構：
區塊鏈是以太坊的核心之一，所有交易以及結構都存於一個個區塊中，接下來我們看看以太坊中的區塊結構是怎樣的。
以太坊中所有結構定義基本都可以在 core/types 中找到，區塊結構定義在 block.go
中：
受比特幣區塊鏈資料結構的影響，我以為 block 可以簡單地分為 head 和 body 兩部分。但讀了以太坊原始碼後，我發現 Ethereum 不是這樣設計的。在 block.go 中，定義了以太坊區塊鏈的區塊結構為：
可以看到 body+head!=block。除此之外，block.go 檔案中還定義了許多結構，比如用於
協議的 extblock，用於儲存的 storageblock 等。
可以看到，header 結構用的非常頻繁，接下來看看 header 結構是如何定義的：
Header 成員變數的解釋如下:
ParentHash：指向父區塊(parentBlock)的指標。除了創世塊(Genesis Block)外，每個區塊有且只有一個父區塊。
Coinbase：挖掘出這個區塊的礦工地址。用於發放獎勵。
UncleHash：Block 結構體的成員 uncles 的雜湊值。注意這個欄位是一個 Header 數
組。
Root：StateDB 中的“state Trie”的根節點的雜湊值。Block 中，每個賬戶以 stateObject 物件表示，賬戶以 Address 為唯一標示，其資訊在相關交易(Transaction)的執行中被修改。所有賬戶物件可以逐個插入一個 Merkle-PatricaTrie(MPT)結構裡，形成“state
Trie”。
TxHash: Block 中 “tx Trie”的根節點的雜湊值。Block 的成員變數 transactions 中所有的
tx 物件，被逐個插入一個 MPT 結構，形成“tx Trie”。
ReceiptHash：Block 中的 “Receipt Trie”的根節點的雜湊值。Block 的所有 Transaction 執行完後會生成一個 Receipt 陣列，這個陣列中的所有 Receipt 被逐個插入一個 MPT 結構中，形成”Receipt Trie”。(比特幣區塊中有一顆用於存放交易的梅克爾樹，而以太坊中有不同功能的三棵 M-P 樹)
Bloom：Bloom 過濾器(Filter)，用來快速判斷一個引數 Log 物件是否存在於一組已知的 Log 集合中。
Difficulty：區塊的難度。Block 的 Difficulty 由共識演算法基於 parentBlock 的 Time 和Difficulty 計算得出，它會應用在區塊的‘挖掘’階段。
Number：區塊的序號。Block 的 Number 等於其父區塊 Number +1.
Time：區塊“應該”被建立的時間。由共識演算法確定，一般來說，要麼等於parentBlock.Time + 10s，要麼等於當前系統時間。
GasLimit：區塊內所有 Gas 消耗的理論上限。該數值在區塊建立時設定，與父區塊有關。具體來說，根據父區塊的 GasUsed 同 GasLimit * 2/3 的大小關係來計算得出。
GasUsed：區塊內所有 Transaction 執行時所實際消耗的 Gas 總和。
Nonce：一個 64bit 的雜湊數，用於“挖礦”。
區塊儲存：
區塊的資料最終都是以[k,v]的形式儲存在資料庫中，資料庫在主機中的儲存位置為：
datadir/geth/chaindata。具體程式碼在 core/database_util.go 中。區塊在儲存是，head 和
body 是分開儲存的。
以 writeHeader 為例：
在儲存 header 時，內容部分的 key 為：字首+num(uint64 big endian)+hash;value 是區塊
頭的 rlp 編碼。其餘的模組儲存方式類似：
各種字首也都定義在 database_util.go 檔案中，值得注意的是，在此檔案中還有用於只儲存區塊頭的一套函式，應該是為提高以太坊的靈活性。
三.交易部分
交易部分的內容比較多，已寫在專門的一個文件,請檢視上一篇內容。
四.Merkle-PatriciaTrie
Merkle-PatriciaTrie 簡介：
Ethereum 使用的 Merkle-PatriciaTrie(MPT)結構，源自於 Trie 結構，又分別繼承了
PatriciaTrie 和 MerkleTree 的優點，並基於內部資料的特性，設計了全新的節點體系和插入載入機制。
Trie，又稱為字典樹或者字首樹(prefix tree)，屬於查詢樹的一種。它與平衡二叉樹的主要不同點包括：每個節點資料所攜帶的 key 不會儲存在 Trie 的節點中，而是透過該節點在整個樹形結構裡位置來體現;同一個父節點的子節點，共享該父節點的 key 作為它們各自 key 的字首，因此根節點 key 為空;待儲存的資料只存於葉子節點中，非葉子節點幫助形成葉子節點 key 的字首。下圖來自 wiki-Trie，展示了一個簡單的 Trie 結構。
PatriciaTrie，又被稱為 RadixTree 或緊湊字首樹(compact prefix tree)，是一種空間使用率經過最佳化的 Trie。與 Trie 不同的是，PatriciaTrie 裡如果存在一個父節點只有一個子節點， 那麼這個父節點將與其子節點合併。這樣可以縮短 Trie 中不必要的深度，大大加快搜尋節點速度。
MerkleTree，也叫雜湊樹(hash tree)，是密碼學的一個概念，注意理論上它不一定是 Trie。在雜湊樹中，葉子節點的標籤是它所關聯資料塊的雜湊值，而非葉子節點的標籤是它的所有子節點的標籤拼接而成字串的雜湊值。雜湊樹的優勢在於，它能夠對大量的資料內容迅速作出高效且安全的驗證。假設一個 hash tree 中有 n 個葉子節點，如果想要驗證其中一個葉子節點是否正確-即該節點資料屬於源資料集合並且資料本身完整，所需雜湊計算的時間複雜度是是 O(log(n))，相比之下 hash list 大約需要時間複雜度 O(n)的雜湊計算，hash
tree 的表現無疑是優秀的。
上圖來自 wiki-MerkleTree，展示了一個簡單的二叉雜湊樹。四個有效資料塊 L1-L4. 分別被關聯到一個葉子節點上。Hash0-0 和 Hash0-1 分別等於資料塊 L1 和 L2 的雜湊值， 而 Hash0 則等於 Hash0-0 和 Hash0-1 二者拼接成的新字串的雜湊值，依次類推，根節點的標籤 topHash 等於 Hash0 和 Hash2 二者拼接成的新字串的雜湊值。比特幣在儲存交易時就用的此種資料結構。
實現部分
MPT 的相關程式碼在 tire 資料夾中。
Node.go 中定義了四種型別的節點，分別是：
其中，nodeFlag 是用於在建立/修改節點是存放快取資料的。
fullNode 是一個可以攜帶多個子節點的父(枝)節點。它有一個容量為 17 的 node 陣列成員變數 Children，陣列中前 16 個空位分別對應 16 進位制(hex)下的 0-9a-f，這樣對於每個子節點，根據其 key 值 16 進位制形式下的第一位的值，就可掛載到 Children 陣列的某個位置，fullNode 本身不再需要額外 key 變數;Children 陣列的第 17 位，留給該 fullNode 的資料部分。fullNode 明顯繼承了原生 trie 的特點，而每個父節點最多擁有 16 個分支也包含了基於總體效率的考量。
shortNode 是一個僅有一個子節點的父(枝)節點。它的成員變數 Val 指向一個子節點，而成員 Key 是一個任意長度的字串(位元組陣列[]byte)。顯然 shortNode 的設計體現了PatriciaTrie 的特點，透過合併只有一個子節點的父節點和其子節點來縮短 trie 的深度，結果就是有些節點會有長度更長的 key。
valueNode 充當 MPT 的葉子節點。它其實是位元組陣列[]byte 的一個別名，不帶子節點。在使用中，valueNode 就是所攜帶資料部分的 RLP 雜湊值，長度 32byte，資料的 RLP 編碼值作為 valueNode 的匹配項儲存在資料庫裡。
這三種型別覆蓋了一個普通 Trie(也許是 PatriciaTrie)的所有節點需求。任何一個[k,v]型別資料被插入一個 MPT 時，會以 k 字串為路徑沿著 root 向下延伸，在此次插入結束時首先成為一個 valueNode，k 會以自頂點 root 起到到該節點止的 key path 形式存在。但之後隨著其他節點的不斷插入和刪除，根據 MPT 結構的要求，原有節點可能會變化成其他node 實現型別，同時 MPT 中也會不斷裂變或者合併出新的(父)節點。比如：
假設一個 shortNode S 已經有一個子節點 A，現在要新插入一個子節點 B，那麼會有兩種可能，要麼新節點 B 沿著 A 的路徑繼續向下，這樣 S 的子節點會被更新;要麼 S 的Key 分裂成兩段，前一段分配給 S 作為新的 Key，同時裂變出一個新的 fullNode 作為 S 的子節點，以同時容納 B，以及需要更新的 A。
如果一個 fullNode 原本只有兩個子節點，現在要刪除其中一個子節點，那麼這個fullNode 就會退化為 shortNode，同時保留的子節點如果是 shortNode，還可以跟它再合併。
如果一個 shortNode 的子節點是葉子節點同時又被刪除了，那麼這個 shortNode 就會退化成一個 valueNode，成為一個葉子節點。諸如此類的情形還有很多，提前設想過這些案例，才能正確實現 MPT 的插入/刪除/查詢等操作。當然，所有查詢樹(search tree)結構的操作，免不了用到遞迴。
hashNode 跟 valueNode 一樣，也是字元陣列[]byte 的一個別名，同樣存放 32byte 的雜湊值，也沒有子節點。不同的是，hashNode 是 fullNode 或者 shortNode 物件的 RLP 雜湊值，所以它跟 valueNode 在使用上有著莫大的不同。
在 MPT 中，hashNode 幾乎不會單獨存在(有時遍歷遇到一個 hashNode 往往因為原本的 node 被摺疊了)，而是以 nodeFlag 結構體的成員(nodeFlag.hash)的形式，被 fullNode 和shortNode 間接持有。一旦 fullNode 或 shortNode 的成員變數(包括子結構)發生任何變化，它們的 hashNode 就一定需要更新。所以在 trie.Trie 結構體的 insert()，delete()等函式實現中，可以看到除了新建立的 fullNode、shortNode，那些子結構有所改變的 fullNode、shortNode 的 nodeFlag 成員也會被重設，hashNode 會被清空。在下次 trie.Hash()呼叫時，整個 MPT 自底向上的遍歷過程中，所有清空的 hashNode 會被重新賦值。這樣trie.Hash()結束後，我們可以得到一個根節點 root 的 hashNode，它就是此時此刻這個 MPT結構的雜湊值。
Header 中的成員變數 Root、TxHash、ReceiptHash 的生成，正是源於此。明顯的，hashNode 體現了 MerkleTree 的特點：每個父節點的雜湊值來源於所有子節點雜湊值的組合，一個頂點的雜湊值能夠代表一整個樹形結構。hashNode 加上之前的fullNode，shortNode，valueNode，構成了一個完整的 Merkle-PatriciaTrie 結構，很好的融合了各種原型結構的優點，非常值得研究。
節點增刪查改用到的函式都定義於 trie.go。在 MPT 的查詢，插入，刪除過程中，如果在遍歷時遇到一個 hashNode，首先需要從資料庫裡以這個雜湊值為 k，讀取出相匹配的v，然後再將 v 解碼恢復成 fullNode 或 shortNode。在程式碼中這個過程叫 resolve。
五.StateDB
在系統設計中，底層資料庫模組和業務模型之間，往往需要設定本地儲存模組，它面向業務模型，可以根據業務需求靈活的設計各種儲存格式和單元，同時又連線底層資料庫，如果底層資料庫(或者第三方 API)有變動，可以大大減少對業務模組的影響。在以太坊中，StateDB 就擔任這個角色，它透過大量的 stateObject 物件集合，管理所有“賬戶”資訊。
StateDB 有一個 trie.Trie 型別成員 trie，它又被稱為 storage trie 或 stte trie，這個 MPT 結構中儲存的都是 stateObject 物件，每個 stateObject 物件以其地址(20 bytes)作為插入節點的 Key;每次在一個區塊的交易開始執行前，trie 由一個雜湊值(hashNode)恢復出來。另外還有一個 map 結構，也是存放 stateObject，每個 stateObject 的地址作為 map 的 key。那麼問題來了，這些資料結構之間是怎樣的關係呢?
如上圖所示，每當一個 stateObject 有改動，亦即“賬戶”資訊有變動時，這個stateObject 物件會更新，並且這個 stateObject 會標為 dirty，此時所有的資料改動還僅僅儲存在 map 裡。當 IntermediateRoot()呼叫時，所有標為 dirty 的 stateObject 才會被一起寫入 trie。而整個 trie 中的內容只有在 CommitTo()呼叫時被一起提交到底層資料庫。可見，這個 map 被用作本地的一級快取，trie 是二級快取，底層資料庫是第三級，各級資料結構的界限非常清晰，這樣逐級快取資料，每一級資料向上一級提交的時機也根據業務需求做了合理的選擇。
StateDB 還可以管理賬戶狀態的版本。這個功能用到了幾個結構體：journal，revision，先來看看 UML 關係圖：
其中 journal 物件是 journalEntry 的雜湊，長度不固定，可任意新增元素，介面journalEntry 存在若干種實現體，描述了從單個賬戶操作(賬戶餘額，發起合約次數等)，到account trie 變化(建立新賬戶物件，賬戶消亡)等各種最小事件。revision 結構體，用來描述一個‘版本’，它的兩個整型成員 jd 和 journalIndex，都是基於 journal 雜湊進行操作的。
上圖簡述了 StateDB 中賬戶狀態的版本是如何管理的。首先 journal 雜湊會隨著系統執行不斷的增長，記錄所有發生過的單位事件;當某個時刻需要產生一個賬戶狀態版本時， 程式碼中相應的是 Snapshop()呼叫，會產生一個新 revision 物件，記錄下當前 journal 雜湊的長度，和一個自增 1 的版本號。
基於以上的設計，當發生回退要求時，只要根據相應的 revision 中的 journalIndex，在journal 雜湊上，根據所記錄的所有 journalEntry，即可使所有賬戶回退到那個狀態。每個 stateObject 物件管理著以太坊中的一個“賬戶”。stateObject 有一個成員變數data，型別是 Accunt 結構體，裡面存有賬戶 Ether 餘額，合約發起次數，最新發起合約指令集的雜湊值，以及一個 MPT 結構的頂點雜湊值。
stateObject 內部也有一個 Trie 型別的成員 trie，被稱為 storage trie，它裡面存放的是一種被稱為 State 的資料。State 跟每個賬戶相關，格式是[Hash, Hash]鍵值對。有意思的是，stateObject 內部也有類似 StateDB 一樣的二級資料快取機制，用來快取和更新這些State。
stateObject 定義了一種型別名為 storage 的 map 結構，用來存放[Hash,Hash]型別的資料對，也就是 State 資料。當 SetState()呼叫發生時，storage 內部 State 資料被更新，相應標示為”dirty”。之後，待有需要時(比如 updateRoot()呼叫)，那些標為”dirty”的 State 資料被一起寫入 storage trie，而 storage trie 中的所有內容在 CommitTo()呼叫時再一起提交到底層資料庫。
