Ask about Geth: Snapshot acceleration | Ethereum Foundation Blog

核心问题：

“Could you share how the flat db structure is different from the legacy structure?” (“Ask about Geth: Snapshot acceleration”)

意思是，扁平化数据结构 (即 Snapshot) 和原本的传统结构有何不同？

State in Ethereum 以太坊组织数据的方式

MPT (Merkle Patricia Tree) = Merkle Tree + Patricia Tree

  • Merkle Tree 保证了“可验证性”，即无需提供整个数据集，而只需要路径上的一部分数据，即可验证数据真伪。（高效）
  • Patricia Tree 保证了“确定性”，即：对于任何一组确定的键值对，它们组成的 Patricia Tree 的结构是唯一的。（共识）

MPT 为何能解决验证问题呢？

  • 保证了共识：由于 Patricia Tree 的确定性，所有拥有相同世界状态的节点，必然会计算出完全相同的 State Root。这使得全网可以通过比对一个简短的哈希值来确认彼此的状态是否一致，这是共识的基础。
  • 实现了轻客户端验证：由于 Merkle Tree 的可验证性，一个“轻客户端”（只存储区块头，知道 State Root）可以向一个“全节点”请求某个账户的余额。全节点会返回这个余额数据，并附上一条“默克尔证明”。轻客户端就可以在不下载整个世界状态（可能高达数TB）的情况下，仅用这个小小的证明来验证这个余额是否真实、可信，并且确实是包含在那个 State Root 所代表的世界状态里的。

“The cost of logarithmic updates and logarithmic verification is logarithmic reads and logarithmic storage for every individual key.” (“Ask about Geth: Snapshot acceleration”)

使用MPT的代价：当修改和验证都是对数阶时，读取和存储也是对数阶。

而这两者在simple map中应该是常数阶。

如何解决 Trade-Off

我们用 MPT 代替简单的 map 结构，就是为了解决验证方面的问题。现在问题解决了，却导致查找效率下降。那么，我们何不回到最简单的 map 结构呢？

作者给出的解决方式，就是增加一个 map，也就是所谓的 Snapshot。这个 Snapshot 的作用，就是储存当前区块的 State，不用于验证，只用来查找数据。

Snapshot 类似计算机中的 Cache，它始终和一棵权威的 MPT 树的状态保持一致，定期更新，保证自身的正确性。

利用 Snapshot 查找，比只使用 MPT 快得多。

Snapshot 的问题及解决

但是，考虑到存在区块之间的竞争以及链的重组，Snapshot 需要应对“撤销”的情况。因此，我们可以再将 Snapshot 分成两部分：

  • 第一部分就是最终的数据存储。
  • 第二部分是一个内存差分层的树/栈。每一个新区块都会在该部分中生成一个新的、独立的层，这个层只记录该区块带来的状态变更。当发生重组时，只需要丢弃最顶部的那个区块即可。

在链的状态完全稳定后，再将第二部分的数据写入第一部分。

其他

Snapshot 的实现中还有一些细节问题，比如自毁合约、深度重组、重启问题等等，这里不做讨论。

Snapshot 实现了巨大的效率提升，但也有一些代价，比如需要 9-10 小时来初始化这一快照，以及额外需要 15GB 以上的硬盘空间。（现在，这一数字甚至更大了）