世界状态State与StateDB
Last updated
Last updated
1）以太坊状态机（接收器/识别器型状态机）
有限自动机 （Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常称作有限状态机（ Finite State Machine，缩写 FSM），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
$次态 = f(现态，输入)$
通过节点维护运行，以太坊网络是一个去中心化状态机。在任意时刻，只会处于一个全世界唯一的状态，我们把这个状态机，称之为以太坊世界状态，代表着以太坊网络的全局状态。
世界状态(state)由无数的账户信息组成，每个账户均存在一个唯一的账户信息。账户信息中存储着账户余额、Nonce、合约哈希、账户状态等内容，每个账户信息通过账户地址影射。 从创世状态开始，随着将交易作为输入信息，在预设协议标准（条件）下将世界态推进到下一个新的状态中。
2）StateDB
StateDB是EVM State中最高层的封装，直接提供了与StateObject (Account，Contract)相关的 CURD 的接口给其他的模块，充当状态（数据）、Trie(树)、LevelDB（存储）的协调者。
从程序设计角度，StateDB 有多种用途：
维护账户状态到世界状态的映射。
支持修改、回滚、提交状态。
支持持久化状态到数据库中。
是状态进出默克尔树的媒介。
需要注意，世界状态中的所有状态都是以
Account账户为基础单位存在的。所访问的任何数据必然属于某个账户下的状态，世界状态仅仅是通过一颗树来建立安全的映射。比如所访问的数据可以分为如下几种类型：
访问账户基础属性：
Balance、Nonce、Root、CodeHash读取合约账户代码
读取合约账户中存储内容
在代码实现中，为了便于账户隔离管理，使用不开放的
stateObject(见账户结构)来维护
1、trie root：首先，我们要告诉 StateDB ，我们要使用哪个状态。因此需要提供 StateRoot 作为默克尔树根去构建树。StateRoot 值相当于数据版本号，根据版本号可以明确的知道要使用使用哪个版本的状态。
2、database：然后，数据内容本身并没在树中，需要到具体数据库中读取。因此在构建 StateDB 时需要提供 state root 和 db 才能完成构建。
轻节点使用的 odrDatabase，对数据读取方式的封装，因为需要通过向其他节点查询来获得数据
然后，即可初始化一个stateDB
持久化
journal参数(from struct statedb)： 记录修改状态的日志流水，使用此日志流水可回滚状态
在区块中，交易作为输入条件，来根据一系列动作修改状态。
StateDB 可视为一个内存数据库，在完成区块挖矿前，只是获得在内存中的状态树的 Root 值。状态数据先在内存数据库中完成修改，所有关于状态的计算都在内存中完成。
在将区块持久化时，完成有内存到数据库（真正落盘）的更新存储，此更新属于增量更新，仅仅修改涉及到被修改部分。
底层物理存储层DB只有 LevelDB，为了提高读写性能，使用 cachingDB 对其进行一次封装，使用了LRU缓存淘汰算法。
LevelDB：持久化KV单机数据库，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。LevelDB应用了LSM (Log Structured Merge) 策略，lsm_tree对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高效地将更新迁移到磁盘，降低索引插入开销。
3）Merkle Patricia Trie
Trie 是一种有序的树结构，用于存储和检索键值对（key-value），其中 key 可以映射到有限“字符集”组成的字符串，树的每个节点记录了一个字符，并且指向了下一个字符，每个路径可以组成一个完整的 key，这使得节点可以共享相同的前缀。
“Trie” 一词提取自 “retrieval”（数据检索）的中间部分，根据其特征，也叫前缀树（Prefix Tree）、字典树等
优点：
内容可寻址: 每个节点的地址（或键值）是基于其内容的哈希。因此，任何更改都会导致哈希的更改，这有助于确保数据的不变性和验证。
历史完整性: 由于每个状态的更改都会产生新的根哈希，因此可以追踪并验证整个状态的历史。
高效性: Patricia Trie的设计允许以太坊进行高效的插入、查找和删除操作。
节省空间: 使用路径压缩和节点合并策略，MPT可以减少存储和计算的冗余。
MPT = Merkle Tree(节点存储数据块的哈希) + Patricia Trie（压缩前缀树，以节省空间高效查询，如图）
MPT节点类型：
空白节点 NULL
分支节点 branch [ v0 ... v15, vt ]长度为 17 的数组，前 16 个元素表示十六进制字符集，最后一个元素存储该分支对应的value（如果存在）
减小了每个分支节点的容量，但是在一定程度上增加了树高。
叶子节点 leaf [encodedPath, value]
拓展节点 extension [encodedPath, key]
以太坊MPT中Key的定义
1、key的存储内容（两种）：
Origin Key：数据的原始 key，为字节数组（RLP编码）。
Secure Key：为原始 key 计算哈希 Keccak256(Origin Key) 的结果，长度固定为 32 字节，用于防止深度攻击。后文我们将看到以太坊的状态树和存储树使用这种 Key 类型
2、key的存储形式：
Hex Key：将 Origin Key 或 Secure Key 进行半字节（nibble）拆解后的 key，为 MPT 树真正存储的 key。在以上条件的限制下，MPT 树 key 的长度固定为 64 字符（32字节对应）。
其中的一个必要优化手段是HP Key：hex prefix encoding，Hex 前缀编码。当我们使用 nibble 寻找路径时，我们可能最后会剩下奇数个的 nibble，但是由于数据存储的最小单位是字节，所以可能会带来一些歧义，比如我们可能无法区分 1 或 01（都存储为1字节01）。因此，为了区分奇偶长度，叶子节点和拓展节点的 encodedPath 使用一个前缀作为标签，另外，这个标签也用于区分节点类型。
nibble：占4bits ，一位十六进制数即半字节。为HP编码中hex用到的数据结构单位，可以表示数字 0-15，这一步可以看成是将 key 映射到十六进制字符 0-f 组成的字符串，这就是为什么分支节点的数组长度为 17（16+1）
应实现方法：
