区块级访问列表 (BAL)：基准测试与开销

由 Po @ QuarkChain 编写

TL;DR

• 评估了六种 BAL 设计，以权衡数据开销和并行性。
• 类型-2/5/6 支持完全并行执行；类型-3/4 提供了最大的 I/O 减少，类型-1 的开销最低。
• I/O 主导了 Geth 的运行时间（约 70%），主要源于账户和存储读取。
• 执行并不是瓶颈 —— 大部分 CPU 时间消耗在 trie 访问、keccak 哈希和发送者恢复（sender recovery）上。
• 在最新的 Geth 中实现了类型-1、类型-3 和类型-4 的 BAL。
• 基准测试显示，类型-1 减少了约 60% 的总区块处理时间，类型-3 减少了约 68%，类型-4 减少了约 70%。

BAL 设计概述

定义

• 地址（Address）：BAL 中的账户地址。
• 插槽（Slot）：BAL 中引用的合约账户中的存储键。
• 账户值（Account value）：
  • 区块执行前的值：[nonce, balance, codeHash]
  • 交易执行后修改的值：[nonce, balance]
• 插槽值（Slot value）：特定存储插槽的值。
• 区块执行前的值：区块执行前的账户或存储值，表示为：
  • Map[address/slot, account/storage value]
• 交易执行后修改的值：区块中每笔交易修改的账户或存储值，表示为：
  • List[tx_index, modified account and storage values]
• 并行 I/O：通过 Account(addr) 和 Storage(addr, slot) 并发获取账户/插槽值。
• 近零 I/O：几乎消除了 I/O 操作，除了账户/合约代码读取和执行后的提交（commit）。
• 乐观并行执行：在假设没有冲突的情况下并行执行交易，如果检测到冲突则回滚。
• 完全并行执行：并行执行，无需重新执行具有冲突依赖关系的交易。
• BAL 验证开销：验证 BAL 是否准确反映了执行期间的访问模式和状态更改的成本。

BAL 设计变体

我们探索了六种 BAL 设计变体（为简洁起见，不包括合约代码）：

1. 地址和插槽：支持并行 I/O。
2. 地址和插槽 + 交易后修改的值 (EIP-7928)：支持并行 I/O 和完全并行执行。
3. 地址和插槽 + 区块前插槽值：支持近零 I/O。
4. 地址和插槽 + 区块前账户和插槽值：支持近零 I/O。
5. 地址和插槽 + 区块前插槽值 + 交易后修改的值：结合了近零 I/O、完全并行执行和并行状态根计算。
6. 地址和插槽 + 交易前账户和插槽值：支持近零 I/O 和完全并行执行。

类型-5 和类型-6 之间的主要区别在于 BAL 验证：

• 类型-5 支持对提供的 BAL 进行并行验证以及并行计算新状态根。然而，它需要将区块执行前的值与交易执行后修改的值合并，以重建完全并行交易执行所需的预状态（prestate）。
• 类型-6 支持近零 I/O 读取，但需要顺序验证，因为一笔交易的 BAL 只能在所有先前交易执行后才能验证。
• 我们预计类型-5 和类型-6 之间的验证开销差异微乎其微，因为它仅限于内存操作。

开销表格（不包括合约代码大小），2000 个区块：22347001-22349000

虽然这里没有包含合约代码，但对于乐观或完全并行执行，只需要提供新创建的合约代码。对于现有合约，由于现有代码的并行获取速度足够快，因此只需要 codeHash。

一个关键的观察结果是，类型-3 和类型-6 BAL 的平均区块大小开销小于类型-2 (EIP-7928)，因为大多数账户和存储写入可能不会被同一区块内的后续交易访问。这使得类型-6 成为一个极具吸引力的 BAL 选项，在开销和性能之间提供了更好的平衡。

由于类型-1、类型-3 和类型-4 的空间效率，以及在 Geth 中为类型-2、类型-5 和类型-6 启用完全并行执行所涉及的复杂性，我们在最新的 Geth 中仅实现了类型-1、类型-3 和类型-4。

Geth 1.15.8 中 BAL 的原型实现

类型-1 BAL

BAL 数据结构：

var AllBlockAccessLists = map[uint64]types.AccessList{}

在 processBlock 期间，所有 BAL 值在交易执行前被预取。

func (p *StateProcessor) Process(block *types.Block, statedb *state.StateDB, cfg vm.Config) (*ProcessResult, error) {
    ...
    statedb.PrefetchAccessList(block.Number().Uint64())
    ...
}

预取的状态被存储到 StateDB.stateObjects[addr].originStorage 中。

我们首先并行获取账户，然后并行获取存储值，从而消除了后续执行中几乎所有的 I/O 读取（加载合约代码除外）。（ 注意：这是一个初始版本；尚未应用并行执行以及并行账户和存储获取优化。）

并行预取账户和插槽值，并设置插槽值的代码片段：

type StateObject struct {
    obj  *stateObject
    keys []common.Hash
}

type StorageKV struct {
    obj *stateObject
    key *common.Hash
    val *common.Hash
}

tp := NewThreadPool(25)
tp.Start()

lenAccts := 0
lenMaxSlots := 0
accts := make(chan StateObject, len(bals))

accountReadStart := time.Now()

for _, bal := range bals {
    addr := bal.Address
    lenAccts++
    keys := bal.StorageKeys
    lenMaxSlots += len(keys)

    tp.AddTask(func() {
        // s.reader.Account 因为 keccakhash 不是线程安全的，所以改为 AccountBAL
        acct, err := s.reader.AccountBAL(addr)
        if err != nil {
            log.Error("fail to fetch account:", addr)
        }
        obj := newObject(s, addr, acct)
        accts <- StateObject{obj, keys}
    })
}

acctsArr := []StateObject{}

// 在 stateDB 中设置预取的账户
for range lenAccts {
    state := <-accts
    acctsArr = append(acctsArr, state)
    // 必须先设置它，以避免稍后在 storageBAL 中读取账户
    s.setStateObject(state.obj)
}
close(accts)
s.AccountReads += time.Since(accountReadStart)

storages := make(chan *StorageKV, lenMaxSlots)
lenSlots := 0
storageReadStart := time.Now()
for _, state := range acctsArr {
    obj := state.obj
    keys := state.keys
    addr := obj.Address()

    if obj.origin == nil {
        continue
    }
    lenSlots += len(keys)

    acct := obj.origin
    tr, err := trie.NewStateTrie(trie.StorageTrieID(s.originalRoot, obj.addrHash, acct.Root), s.db.TrieDB())
    if err != nil {
        log.Error("fail to create trie for:", addr)
        panic("fail to create trie for:")
    }

    for _, key := range keys {
        key := key
        tp.AddTask(func() {
            val, err := obj.db.reader.StorageBAL(addr, key, tr)
            if err != nil {
                log.Error("fail to fetch storage:", addr, key)
            }
            kv := &StorageKV{obj, &key, &val}
            storages <- kv
        })
    }
}
tp.Stop()
s.StorageReads += time.Since(storageReadStart)

// 在 stateDB 中设置预取的存储值
for range lenSlots {
    kv := <-storages
    kv.obj.originStorage[*kv.key] = *kv.val
    s.setStateObject(kv.obj)
}

类型-3 BAL

类型-3 的实现与类型-2 大致相似，关键区别在于插槽值直接在 stateDB 中设置，而无需从数据库中获取。

BAL 数据结构：

type StorageKV struct {
    Key common.Hash `json:"key"`
    Val common.Hash `json:"val"`
}

type AccessListKV struct {
    Address   common.Address `json:"address"     gencodec:"required"`
    Nonce     uint64         `json:"nonce"`
    Balance   *uint256.Int   `json:"balance"`
    Root      common.Hash    `json:"root"`
    CodeHash  []byte         `json:"codeHash"`
    StorageKV []StorageKV    `json:"storageKeys" gencodec:"required"`
}

在 processBlock 期间，所有 BAL 值在交易执行前被预取。

预取的状态也存储到 StateDB.stateObjects[addr].originStorage 中。

我们首先并行获取账户，然后直接从 BAL 设置相应的存储值。

并行预取账户和设置存储的代码片段：

tp := NewThreadPool(25)
tp.Start()

lenAccts := 0
accts := make(chan *stateObject, len(bals))

for _, bal := range bals {
    addr := bal.Address
    lenAccts++
    kvs := bal.StorageKV

    tp.AddTask(func() {
        acct, err := s.reader.AccountBAL(addr)
        if err != nil {
            log.Error("fail to fetch account:", addr)
        }
        obj := newObject(s, addr, acct)
        if acct != nil {
            for _, kv := range kvs {
                obj.originStorage[kv.Key] = kv.Val
            }
        }
        accts <- obj
    })
}

for range lenAccts {
    obj := <-accts
    s.setStateObject(obj)
}

类型-4 BAL

类型-4 的实现紧随类型-3，但账户值和插槽值都直接在 stateDB 中设置，无需任何获取操作。BAL 数据结构与类型-3 保持一致。

for _, bal := range bals {
    addr := bal.Address
    kvs := bal.StorageKV

    if bal.Balance == nil {
        bal.Balance = ZeroBalance
        bal.Root = types.EmptyRootHash
        bal.CodeHash = types.EmptyCodeHash.Bytes()
    }
    acct := types.StateAccount{
        Nonce:    bal.Nonce,
        Balance:  bal.Balance,
        CodeHash: bal.CodeHash,
        Root:     bal.Root,
    }

    obj := newObject(s, addr, &acct)
    for _, kv := range kvs {
        obj.originStorage[kv.Key] = kv.Val
    }
    s.setStateObject(obj)
}

基准测试结果与讨论

实验设置

• 软件：Geth 1.15.8，使用 state.scheme=path
• 硬件：32 核，7TB SSD，128GB RAM
• BAL 生成与加载： 使用带有 prestateTracer 的 debug_traceTransaction 收集 2000 个区块（[22347001, 22349000]）的 BAL，以 JSON 格式存储，并在 Geth 启动时加载。
• 基准测试方法： 在 2000 个区块（[22347001, 22349000]）范围内使用 Geth 的 export 和 import 命令。

geth export --datadir ./geth_full/snap/ dump.dat 22347001 22349000
geth --pprof.cpuprofile cpu1.prof --datadir ./geth_snap import --nocompaction true dump.dat

结果

时间成本细分涵盖了 I/O、执行、验证和提交阶段：

主要发现：

• 账户和存储读取的 I/O 成本，占原生 Geth 总区块执行时间的近 70%。
• 使用类型-1 BAL（仅账户地址和存储键），我们的原型通过消除 85% 的 I/O 读取，使总执行时间减少了约 60%。类型-4 BAL 消除了所有 I/O 读取，并实现了约 70% 的总执行时间减少。值得注意的是，账户读取时间远低于存储读取时间。
• 在早期的原型（3 年前实现，此处未列出）中，乐观并行执行可以将总执行时间减少 80%。
• 正如 Toni 所指出的，包含每笔交易的执行后存储键值将启用完全并行执行，使总区块执行时间仅受限于最慢的一笔交易。
• 一旦 I/O 读取被消除并且通过 BAL 实现完全并行化执行，提交时间（Commit time）将成为主要的瓶颈。

我们还对 CPU 时间（不包括 I/O）进行了性能分析，前 10 个最耗时的函数如下所示：

详细的调用栈附在这里：

观察结果：

• 大部分 CPU 时间花费在：
  • PathDB 节点获取：16% (keccak, atomic.(*Int32).Add(RLock))
  • 缓存操作：7% (maps.ctrlGroup.matchH2)
  • 发送者恢复：4% (runtime.cgocall)
• 交易执行本身并不是性能的关键路径。

未来工作

• 并行化 trie 节点获取：我们观察到，在 stateDB 的账户和存储读取期间，平均 trie 磁盘读取深度（不包括中间缓存节点贡献的深度）约为 5。通过并行化 trie 节点获取，I/O 读取成本可以降低到当前不带 BAL 的 Geth 实现的约 25%。因此，仅由 BAL 带来的性能增益可能会下降到 15% 左右。因此，在没有 BAL 的情况下对 Geth 在并行 trie 获取下的性能进行基准测试是值得的。同样值得注意的是，其他客户端（例如 Nethermind）也采用了类似的优化方法。

• 尝试使用 BAL 进行完全并行执行：研究由 BAL 启用的完全并行执行的性能影响和可行性。

参考文献

[1] EIP-7928: Block-Level Access Lists

[2] Code for Reproducing BAL Overhead

[3] Type-1, Type-3 and Type-4 BAL Implementations in Geth

[4] Script for Generating BAL

[5] ESP Academic Grant 2023: EthStorage/Quarkchain Earlier BAL Submission

• 原文链接： hackmd.io/X4Z4h-EQRPSiQF...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～