一文读懂以太坊Geth客户端：快照加速机制

以太坊状态

在深入探讨加速结构之前，我们先回顾一下以太坊中“状态”的概念，以及在不同的抽象层次上状态是如何存储的。

以太坊有两种不同类型的状态：账户集合； 以及每个合约的帐户插槽集合。 从完全抽象的角度来看，这两种数据都是键值对。 帐户集合将地址映射到该地址的随机数、余额等。合约的存储字段将任何值（由合约定义和使用）映射到某个值。

不幸的是，虽然将这些键值对存储为平面数据可能非常有效，但验证它们的正确性在计算上变得困难。 每当修改数据时，我们都必须从下到上对所有数据进行哈希处理。

为了避免总是对整个数据库进行哈希处理，我们可以将数据库拆分成连续的部分并创建一种树结构！ 最原始、最有用的数据放在叶子节点上，树上的每个内部节点都是节点下面内容的哈希值。 这样，当我们要修改某个值时，只需要进行对数次的哈希运算即可。 这种数据结构其实有个响亮的名字，就是“默克尔树”。

但是还没完，这个方法在计算复杂度上还是有欠缺的。 虽然 Merkle 树结构在修改现有数据时效率很高，但是如果插入和删除数据改变了底层小数据块的边界，就会使所有计算出的哈希值失效。

这时候，与其盲目地对数据库进行分组，不如利用键本身来组织数据，根据共同的前缀，将数据排列成树状的格式！ 这样，插入和删除操作都不会影响所有节点，而只会影响从树的根到叶子的路径上的（对数）节点。 这种数据结构称为“Patricia 树”。

结合以上两种方法——帕特里夏树的树层次结构和默克尔树的哈希算法——就是所谓的“默克尔-帕特里夏树”，这也是在实践中用来表示以太坊状态的数据结构。 无论是修改、插入、删除还是校验，都只有对数复杂度！ 唯一的小例外是一些键在插入之前被散列以平衡尝试（一个小的额外是键在插入之前被散列以平衡尝试）。

以太坊的状态存储

上面解释了为什么以太坊使用 Merkle Patricia 树结构来存储它的状态。 不幸的是，虽然所需的操作很快，但每个选项都伴随着牺牲。 更新和验证操作的对数复杂性意味着每个单独密钥的读取和存储都是对数的（对数读取和对数存储）。 这是因为树结构的每个内部节点都必须单独存储在硬盘上。

此刻，我不知道账户树到底有多深，但大约一年前，账户状态填满了7级树。 这意味着每个树操作（例如读取平衡、写入随机数）至少涉及 7-8 个内部节点，因此至少进行 7-8 次持久数据库访问。 LevelDB 最多组织 7 层数据，因此有一个额外的乘数。 最终的结果是单次状态访问有望放大到 25-50 次随机磁盘访问。 将其乘以一个区块中所有交易的所有状态读写，就会得到一个可怕的数字。

[当然，所有客户端实现都尽量保持开销尽可能低。 Geth使用更大的内存区域来缓存几个节点； 它还使用内存中的修剪机制来避免将数据写入磁盘，这些数据将在几个块后被删除。 不过这个需要另外一篇文章说清楚。 ]

同样可怕的是，这个数字是运行保证 24/7 全天候验证所有状态的以太坊节点的成本。

我们能做得更好吗？

并非所有访问都是平等的

以太坊的运作依赖于状态的加密证明。 只要我们要保持验证所有数据的能力，就绕不开硬盘读写放大的问题。 也就是说以太坊怎么快照，我们——可以而且确实——相信我们已经验证过的数据。

重复验证每个状态对象是没有意义的，但是如果每次从硬盘拉取数据都要验证，你就是在做这样一件没有意义的事情。 Merkle Patricia 树结构本来就是为写操作而设计的，但反过来又成了读操作的负担。 我们无法摆脱它，也无法让它变得苗条，但这绝不意味着我们必须在任何场合都使用它。

以太坊节点访问状态的场景大致可以分为以下三类：

导入新块时，EVM 代码的执行会产生或多或少平衡的状态读写数。 但是，用于拒绝服务攻击的块可能会生成比写入操作多得多的读取操作。

当节点运营商取回状态时（比如调用eth_call之类的操作），EVM代码执行只产生读操作（当然也可能有写操作，但这些操作产生的数据最终会被丢弃，不会被持久化到硬盘驱动器内部）。

当一个节点在同步区块链时，同步器会向远程节点请求状态，被请求者将挖掘数据并通过网络传播给同步器。

基于上述访问模式，如果我们可以在不触及状态树的情况下缩短读取操作，则许多节点操作可以变得更快。 这甚至可以开辟一些以前过于昂贵而不可行的新颖访问模式（例如状态迭代）。

当然，牺牲是不可避免的。 在不移除树结构的情况下，任何新的加速结构都会引入额外的开销。 唯一的问题是：额外的开销是否足以值得一试？

请关注它

我们开发了神奇的 Merkle Patricia 树结构来解决我们所有的问题以太坊怎么快照，现在我们想让读取操作绕过它。 那么，我们应该使用什么样的加速结构，才能让读操作再次变快呢？ 显然，如果我们不需要树结构，那么我们可以把树结构带来的所有复杂性都抛到一边，直接回到原来的状态。

正如本文开头所述，理论上，理想状态下以太坊状态的数据存储方式应该是简单的键值对。 没有默克尔帕特里夏树的限制，没有什么能阻止我们去实现这个理想的计划！

前不久，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 个区块之前的状态；或者快速/快照同步模式下的 64 个区块的状态）。

为了克服这些限制，Geth 客户端快照由两部分组成：持久硬盘层，它是旧区块（例如前 128 个区块）状态的完整快照； 内存中的差异层用于收集最近的写操作的组件树。

在处理新块时，我们不会将这些写入直接合并到硬盘层，而只是创建一个新的包含这些变化的内存差异层。 当内存中的差异层积累到足够多的层数时，最底层开始合并更新并将它们推送到硬盘层。 当需要读取状态对象时，我们从最上面的差异层开始搜索，然后向下搜索，直到在差异层或硬盘层中找到它。

这种数据表示非常强大，解决了很多问题。 因为内存内部的diff层形成了一棵树，128个区块内的链重组只需要取出属于父块的diff层，然后开始构建。 需要较旧状态的 dApp 和 farsyncer 可以访问最近的 128 个状态。 开销变成了128次mapping lookup，但是128次in-memory lookup比8次硬盘读取和Level DB的4~5倍放大要快几个数量级。

当然，还是有很多坑。 我不会说得太深，只是简单地列举以下列表：

自毁（合约自毁操作）（和删除操作）特别难处理，因为它们需要短路 diff 层的下降。

如果存在比持久化硬盘层更深的链重组，则当前快照将被完全丢弃并重新生成。 整套操作非常昂贵。

当节点关闭时，需要将内存中的diff层持久化到日志中加载备份，否则重启后快照就没用了。

使用最低的 diff 层作为累加器，只有当它超过一定的内存使用量时才会刷新到磁盘。 这允许跨块对同一插槽进行重复数据删除。

应该为硬盘层分配一个读缓存，这样如果合约重复访问同一个旧存储槽，硬盘就不会损坏。

在内存差异层中使用累积布隆过滤器来快速检测状态对象是否可能存在于差异层中，或者是否应该直接跳转到磁盘。

不将原始数据（账户地址、合约存储密钥）设置为key，而是将这些数据的hash值作为key，保证快照的迭代顺序与Merkle Patricia树的迭代顺序一致。

生成持久化硬盘层的时间比修剪状态树窗口的时间要长得多，所以即使是生成器也需要动态跟踪链的运行。

美与丑并存

Geth的快照加速结构将状态读取的复杂度降低了一个数量级。 这意味着基于读取的 DoS 攻击更难发起一个数量级，eth_call 调用也快一个数量级（假设没有 CPU 瓶颈）。

快照还可以对最近的块进行极快的状态迭代。 事实上，这是我们开发快照机制的主要原因，因为我们可以基于它创建新的快照同步算法。 这需要一篇全新的文章来阐明，但我们最近在 Rinkeby 测试网上的基准测试非常有说服力：

当然，这一切都不是没有代价的。 初始同步完成后，参与主网的节点需要9到10个小时来构建初始快照（然后保持其可用性），并且需要额外的15GB以上的硬盘。

不好的地方在哪里？ 我们花了 6 个月的时间建立足够的信心来发布快照机制，它仍然不是默认功能，需要通过 --snapshot 标志主动启用，并且在内存使用和崩溃恢复方面仍有一些改进工作去做。

总而言之，我们为这一改进感到非常自豪。 涉及的工作量很大，而且是在黑暗中摸索，自己实现一切并祈祷它会起作用。 另一个有意思的是，leaf sync的第一个版本是两年半前写的，但是一直被封杀，因为我们缺少必要的加速结构来驱动它。