这篇文章是Geth客户端系列问答的第一篇文章。你可以热情地问关于Geth客户的问题，我会每周用一篇小文章回答投票率最高的问题。本周最流行的问题是：你能告诉我平面数据库结构和遗留结构之间的主要区别吗？

以太网的现状

在深入理解加速结构之前，我们首先回顾一下以太网中的“状态”概念，以及当涉及不同抽象级别时状态是如何存储的。

以太网有两种不同类型的状态：帐户的收集；每个合同账户的存储槽集合。从完全抽象的角度来看，两个数据都是键值对。帐户集将地址映射到现时、余额等。合同的存储域将任意值(由合同定义和使用)映射到某个值。

不幸的是，虽然将这些键-值对存储为平面数据非常有效，但是在计算上很难验证它们的正确性。每当数据被修改时，我们必须从下到上散列所有数据。

为了避免总是散列整个数据库的需要，我们可以把数据库分成连续的小块，然后建立一个树形结构！最原始和最有用的数据放在叶节点上，然后树中的每个内部节点就是节点下内容的哈希值。这样，当我们想要修改一些值时，我们只需要散列几次。事实上，这种数据结构有一个众所周知的名字，那就是“默克尔树”。

但是还没有结束。这种方法仍然缺乏计算复杂性。尽管默克尔树结构在修改现有数据方面非常有效，但如果插入数据和删除数据会改变底层小数据块的边界，所有计算出的哈希值都将无效。

此时，我们可以使用关键字本身来组织数据，并基于公共前缀以树形格式排列数据，而不是盲目地对数据库进行分组！这样，插入和删除操作不会影响所有节点，而只会影响从根到叶的路径上的(几个)节点。这种数据结构被称为“帕特里夏夏树”。

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

以太网的状态存储

上面解释了为什么以太博物馆使用默克尔-帕特里夏-夏树结构来存储它的状态。不幸的是，尽管所需的操作速度非常快，但还是牺牲了所有的选择。更新操作和验证操作的对数复杂性意味着每个单独密钥的读取和存储是对数读取和对数存储。这是因为树结构的每个内部节点必须分别存储在硬盘上。

此时此刻，我不知道账户树到底有多深，但大约一年前，账户状态填满了7层的树。这意味着每一个树操作(如读取余额和写入随机数)必须接触至少7 ~ 8个内部节点，因此它将至少进行7 ~ 8次持久的数据库访问。LevelDB最多在七层中组织数据，因此有一个额外的乘数。最终的结果是，单个状态访问有望扩大到25 ~ 50个随机硬盘访问。如果您将一个块中所有事务的所有状态读取和写入相乘，您将得到一个可怕的数字。

[当然，所有客户端实现都试图减少开销。Geth使用更大的内存区域来缓存几个节点；它还在内存中使用修剪机制，以避免将几个块后将被删除的数据写入硬盘。但这需要另一篇文章来阐明。]

可怕的是，这个数字是运行一个以太网节点并确保所有状态在任何时候都可以被验证的成本。

我们能做得更好吗？

并非所有的访问都应得到平等对待

以太网的运行依赖于状态的密码证明。只要我们想保持所有数据的验证能力，我们就无法避免硬盘读写放大的问题。也就是说，我们可以并且事实上相信我们已经核实的数据。

重复验证每个状态对象是没有意义的，但是如果每次从硬盘中取出数据时都必须进行验证，那么你就是在做这种没有意义的事情。默克尔的帕特里夏夏树结构本质上是为写操作而设计的，但反过来它又成了读操作的负担。我们无法摆脱它，也无法让它变得苗条，但这并不意味着我们必须在任何场合都使用它。

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

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

当节点操作符检索状态时(例如调用eth_call和类似操作)，EVM代码执行仅生成读操作(当然，可能会有写操作，但是这些操作生成的数据最终将被丢弃，并且不会保存在硬盘中)。

当节点正在同步区块链时，同步器将从远程节点请求状态，并且被请求的人将挖掘数据并通过网络将其传输到同步器。

基于上述访问模式，如果我们可以在不接触状态树的情况下短路读操作，许多节点操作会变得更快。通过这种方式，一些新颖的访问模式(比如状态迭代)甚至可以被打开，这使得原始模式可能过于昂贵而不可行。

当然，也有牺牲。如果不删除树结构，任何新的加速结构都会带来额外的开销。唯一的问题是：额外的费用能带来足够的好处吗，值得一试吗？

请按照

我们开发了神奇的默克尔-帕特里夏-夏树结构来解决我们所有的问题。现在，我们希望读操作可以绕过它。那么，我们应该使用什么样的加速结构来使读取操作再次更快呢？显然，如果我们不需要树结构，我们可以抛开伴随树结构的所有复杂性，直接回到初始状态。

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

不久前，Geth引入了快照加速结构(默认情况下不打开)。快照是给定块的以太网状态的完整视图。抽象实现细节，它是将所有帐户和合同存储槽堆叠在一起，它们由平面键值对表示。

每当我们想访问一个账户或一个存储槽时，我们只需要支付一次LevelDB查询操作，而不是查询每棵树7 ~ 8次。理论上，更新快照也非常简单。处理完一个数据块后，我们只需要为每个要更新的存储插槽执行额外的LevelDB写操作。

事实上，快照加速结构降低了从O(log n)到O(1)的读操作的复杂性(乘以LeveDb的开销)，代价是将写操作的复杂性从O(log n)改变为O(1 log n)(乘以LeveDb的开销)，并将硬盘的存储空间从O(n log n)增加到O(n log n)。

魔鬼隐藏在细节中

维护以太网状态快照的可用性并不容易。只要一个接一个地生成数据块，并一个接一个地堆叠在最后一个数据块上，将最新更改合并到快照中的粗略方法就可以正常工作。但是，即使有轻微的区块链重组(即使只有一个块)，快照机制也会崩溃，因为根本没有设计撤销操作。对于平面数据表示模式，持久写入是单向操作。更糟糕的是，我们无法访问旧的状态(例如，一些dApp需要3个块的旧状态；或者要以快速/快照同步模式访问64个块的先前状态)。

为了克服这些限制，Geth客户端的快照由两部分组成：一部分是持久硬盘层，它是旧块(如顶部块的前128个块)状态的完整快照；内存中还有一个由不同层组成的树，用于收集最新的写操作。

当处理新块时，我们不会直接将这些写操作合并到硬盘层，而只是创建一个包含这些更改的新内存差异层。当内存中的差异层累积到足够高的层数时，底部的层开始合并和更新，并将其推到硬盘层。当我们需要读取一个状态对象时，我们从最上面的diff层开始，一直往下，直到我们在diff层或硬盘层找到它。

这种数据表示方法非常强大，解决了许多问题。因为内存中的差异层构成了一棵树，所以128个块中的链重组只需要取出属于父块的差异层，然后开始构建。需要旧状态的DApp和远程同步器可以访问最新的128个最新状态。开销变成了128次映射查找，但是128次内存查找比8次硬盘读取和4 ~ 5倍的数据库级放大快几个数量级。

当然，里面有很多很多坑。我不会说得太深。简单列表中有以下列表：

自毁(合同自毁操作)(和删除操作)特别难以处理，因为它们需要短路差分层的下降。

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

当节点关闭时，内存中的差异层需要保存到日志中并加载备份，否则快照在重新启动后将毫无用处。

使用底部的差异层作为累加器，只有当它超过一定的内存使用量时才刷新到硬盘。这允许跨区数据块在同一内存插槽上执行重复数据消除写入操作。

为硬盘层分配一个读缓存，这样当合同重复访问同一个旧存储槽时，硬盘就不会被损坏。

在内存的差异层中使用累积布隆过滤器，以便快速检测差异层中是否存在状态对象，或者它们是否应该直接跳转到硬盘进行搜索。

不要将原始数据(帐户地址、合同存储密钥)设置为密钥，而是使用这些数据的哈希值作为密钥，以确保快照的迭代序列与默克尔帕特里夏夏树的相同。

生成持久硬盘层要比切断状态树窗口花费更多的时间，所以即使生成器也需要动态跟踪链的运行。

美丑共存

Geth的快照加速结构将状态读取的复杂性降低了一个数量级。这意味着基于读操作发起DoS攻击要困难一个数量级，而eth_call调用要快一个数量级(假设在中央处理器中没有瓶颈)。

快照还使得以非常高的速度迭代最近的块的状态成为可能。事实上，这是我们开发快照机制的主要原因，因为我们可以基于它创建一个新的快照同步算法。需要一篇全新的文章来阐明这一点，但是我们最近在林克比测试网络上的基准测试说明了这个问题：

当然，这一切并非没有代价。初始同步完成后，参与主网络的节点需要9 ~ 10个小时来构建初始快照(并保持其可用性)，还需要一个超过15 GB的额外硬盘。

不好的部分是什么？我们花了六个月的时间来积累足够的信心并释放快照机制，现在它仍然不是默认功能，需要通过主动使用- snapshot标志来打开，并且仍然有一些关于内存使用和崩溃恢复的润色工作要做。

总之，我们为这次晋升感到非常自豪。有一个巨大的工作量，它是在黑暗中摸索，自己实现一切，祈祷它可以工作。另一个有趣的事情是，叶同步的第一个版本是两年半前写的，但是它一直被阻止，因为我们缺乏必要的加速结构来驱动它。

结论

我希望你喜欢这篇关于Geth客户的文章。我花了两倍于我预期的时间，但我并不后悔，因为主题是值得的。下周见。

[再次声明：我有意不在文章中留下网站进行提问/投票，因为我确信这种活动只是暂时的，我不想留下无用的超链接，我也不想有人在将来购买那个域名并发布恶意信息。你可以在我的推特上找到那个网站。]