*这是A的第1部分 系列 任何人都可以问有关Geth的问题，我将尝试每周用迷你文章回答最高投票的问题。本周的最高投票问题是： 您能否分享平面DB结构与旧结构的不同？
以太坊的状态
在深入加速结构之前，让我们回顾一下以太坊所说的 状态 以及如何将其存储在目前的各种抽象水平上。
以太坊维持两种不同类型的状态：帐户集；以及每个合同帐户的一组存储插槽。来自 纯粹的抽象观点这两个都是简单的密钥/价值映射。一组帐户地图地址为其nonce，余额等。单个合同的存储区域映射任意键（合同定义和使用）到任意值。
不幸的是，尽管将这些键值对存储为平面数据将非常有效，但验证其正确性在计算上变得棘手。每次进行修改时，我们都需要从头开始哈希所有数据。
我们可以将其拆分为小连续的块，并在顶部建造一棵树！原始有用的数据将在叶子中，每个内部节点都将是其下方所有内容的哈希。这将使我们只能在修改事物时重新计算对数数量的哈希数。这种数据结构实际上有一个名称，这是著名的 默克树。
不幸的是，我们仍然对计算复杂性有些不足。上述默克尔树布局非常有效地纳入现有数据的修改，但是插入和删除会改变块边界并无效 全部 计算出的哈希。
我们可以使用钥匙本身将数据本身组织成基于常见前缀的树格式！这样一来，插入或删除就不会改变所有节点，而是将对数路径从根部变为叶子。该数据结构称为 帕特里夏树。
结合两个想法 – 帕特里夏树的树布局和默克尔树的哈希算法 – 您最终会得到一个 Merkle Patricia树，用于表示以太坊状态的实际数据结构。确保对数的复杂性，以进行修改，插入，删除和验证！ 一个很小的额外是在插入之前将键在插入之前进行悬浮以平衡尝试。
以太坊的国家存储
上面的描述说明了 为什么 以太坊将其状态存储在默克尔帕特里夏树中。 las，就像所需的操作一样，每一个选择都是一种权衡。费用 对数更新和对数验证 是 对数读取和对数存储 为了 每个钥匙。这是因为每个内部Trie节点都需要单独保存到磁盘。
目前，我没有帐户深度的准确数字，但是大约一年前，我们已经饱和7的深度。这意味着，每个Trie操作（例如，读取余额，写入nonce）至少触摸7 -8内部节点，因此将至少进行7-8个持久数据库访问。 LevelDB还将其数据组织到最多7个级别，因此从那里有一个额外的乘数。最终结果是 单身的 州访问有望扩大到 25-50随机 磁盘访问。用所有状态读取并写出所有交易中的所有交易，然后您可以到达一个 可怕的 数字。
[Of course all client implementations try their best to minimize this overhead. Geth uses large memory areas for caching trie nodes; and also uses in-memory pruning to avoid writing to disk nodes that get deleted anyway after a few blocks. That’s for a different blog post however.]
尽管这些数字很恐怖，但这些都是操作以太坊节点的成本，并且具有始终对所有状态进行隐秘验证的能力。但是我们可以做得更好吗？
并非所有访问都是平等创建的
以太坊依靠其状态的加密证明。如果我们要保留验证所有数据的能力，则无法围绕磁盘放大。就是说，我们 可以 – 做 – 相信我们已经验证的数据。
每当我们从磁盘上拉起它时，都没有必要验证和重新验证每个状态项目。默克尔·帕特里夏（Merkle Patricia Tree）对于写作至关重要，但这是阅读的开销。我们无法摆脱它，我们不能缩减它。但那 并不是说 我们必须到处使用它。
以太坊节点在几个不同的地方访问状态：
- 导入新块时，EVM代码执行会执行更多或不平衡的状态读取和写入。但是，拒绝服务块的读取可能比写作要多得多。
- 当节点操作员检索状态时（例如 eth_call 和家人），EVM代码执行只能读取（它也可以写入，但最终被丢弃并且不会持续存在）。
- 当节点同步时，它是从需要挖掘并在网络上提供的远程节点的状态。
基于上述访问模式，如果我们可以短路读取不碰到状态，则会成为一系列节点操作 显著地 快点。它甚至可能使一些新颖的访问模式（例如状态迭代）以前非常昂贵。
当然，总会有一个权衡。在不摆脱Trie的情况下，任何新的加速结构都是额外的开销。问题是，额外的开销是否提供了足够的价值来保证它？
回到根源
我们已经建立了这种神奇的Merkle Patricia树来解决所有问题，现在我们想解决它进行阅读。我们应该使用什么加速结构来使读取再次快速？好吧，如果我们不需要Trie，我们不需要引入任何复杂性。我们可以一直回到起源。
如本文开头所述 理论理想 以太坊状态的数据存储是一个简单的键值商店（分别用于帐户和每个合同）。但是，没有默克尔·帕特里夏树的限制，没有什么可以阻止我们实际实施理想解决方案的！
回到一段时间的Geth介绍了它的 快照 加速结构（默认未启用）。快照是在给定块处的以太坊状态的完整视图。明智的是抽象实现，它是所有帐户和存储插槽的转储，以平坦的键值商店为代表。
每当我们希望访问帐户或存储插槽时，我们只能按照Trie支付1级查找，而不是7-8。在理论上更新快照也很简单，在处理一个块之后，我们进行了1个额外的LevelDB写入每个更新的插槽。
快照基本上将读取从o（log n）减少到o（1）（times leveldb开销），而成本从o（log n）增加到o（log n）到o（1 + log n）（times level leveldb开销）和增加磁盘存储从o（n log n）到o（n + n log n）。
魔鬼的细节
保持以太坊状态的可用快照具有复杂性。只要块又一个接一个，始终在最后一个之上建立，将更改合并到快照作品中的幼稚方法。但是，如果有一个迷你reorg（甚至是一个块），我们会遇到麻烦，因为没有撤消。持续写作是用于平面数据表示的单向操作。更糟糕的是，不可能访问较旧的状态（例如，某些DAPP或64+的快速/snap Sync旧状态）是不可能的。
为了克服这一限制，Geth的快照由两个实体组成：一个持久的磁盘层，它是较旧块的完整快照（例如Head-128）；还有一棵内存的差异图，上面收集写作。
每当处理一个新块时，我们都不会直接将写入磁盘层合并，而只需在更改中创建一个新的内存差异层即可。如果将足够的内存差层堆积在顶部，则底部的差异层开始合并在一起，最终将其推到磁盘上。每当要读取状态项目时，我们都会从最上方的差异层开始，然后向后移动，直到找到它或到达磁盘为止。
该数据表示非常强大，因为它解决了许多问题。由于将内存的差异层组装到树上，因此比128个块较浅的较浅的较浅可以选择属于父块的差异层并从那里向前构建。需要较旧状态的DAPP和远程同步者可以访问128个近期。成本的确增加了128个地图查找，但是128个内存查找的数量级比8个磁盘读取的数量级快，读取4x-5X的leveldb读取的订单级。
当然，有很多陷阱和警告。没有过多的细节，可以快速列出更好的观点：
- 自我毁灭（和删除）是特殊的野兽，因为它们需要短路差层下降。
- 如果比持续的磁盘层深度更深，则需要完全丢弃和再生。这非常昂贵。
- 关闭时，需要将内存差异层持续到日记中并加载，否则快照将在重新启动时变得毫无用处。
- 将最底部的差异层用作累加器，并且仅在超过某些内存使用情况时才齐平。这允许在跨块的相同插槽中删除写入。
- 为磁盘层分配一个读取缓存，以便一遍又一遍地访问相同的古老插槽的合同不会引起磁盘命中。
- 在内存差异层中使用累积的BLOOM过滤器快速检测物品是否有可能出现在差异中，或者我们是否可以立即进入磁盘。
- 密钥不是原始数据（帐户地址，存储密钥），而是这些钥匙，确保快照的迭代顺序与Merkle Patricia树具有相同的迭代顺序。
- 生成持续的磁盘层比状态尝试的修剪窗口要花费的时间要多得多，因此即使发电机也需要动态遵循链条。
好，坏，丑陋
Geth的快照加速结构可将状态读取复杂性降低到一个数量级。这意味着基于读取的dos的数量级难以实现。和 eth_call 调用的数量级更快（如果不是CPU绑定）。
该快照还使最新块的快速状态迭代迅速进行。 这实际上是构建快照的主要原因，因为它允许创建新的 折断 同步算法。描述这是一篇全新的博客文章，但是关于Rinkeby的最新基准会说：
当然，权衡总是存在。最初的同步完成后，主网上大约需要9-10h才能构建初始快照（后来进行了实时），并且大约需要15+GB的其他磁盘空间。
至于丑陋的部分？好吧，我们花了6个月的时间对快照充满信心，但即使是现在，它也是 -snapshot 旗帜，在内存使用情况和崩溃恢复方面仍有调整和抛光。
总而言之，我们为这一改进感到自豪。这是一件疯狂的工作，在黑暗实施所有事物的情况下，这是一个巨大的镜头，并希望它能解决。就像一个有趣的事实一样，第一个版本的Snap Sync（Leaf Sync）是2。5年前写的，此后被阻止了，因为我们缺乏必要的加速度来使其饱和。
结语
希望您喜欢这篇文章 询问格斯。我花了大约两倍的完成，比我的目标是我的目标，但是我觉得这个话题值得额外的时间。下周见。
[PS: I deliberately didn’t link the asking/voting website into this post as I’m sure it’s a temporary thing and I don’t want to leave broken links for posterity; nor have someone buy the name and host something malicious in the future. You can find it among my Twitter posts.]
