企业官网建设流程全解析

Foundry Anvil 优化解读：eth_feeHistory 奖励百分位缓存的单次扫描（Percentile Sweep）

【免费下载链接】foundryFoundry is a blazing fast, portable and modular toolkit for Ethereum application development written in Rust.项目地址: https://gitcode.com/GitHub_Trending/fo/foundry

导读

eth_feeHistory是 EIP-1559 客户端向钱包、Gas 预言机等上层工具提供历史费用数据的关键 RPC 接口，其中reward字段需要按请求者指定的百分位返回每个区块的交易有效奖励（effective tip）分布。本文基于 Foundry 仓库中的 Anvil 节点实现（变更记录见 .changelog/anvil-fee-history-percentile-sweep.md），深入解析一次针对该接口的 patch 优化：将原本每次构建缓存条目时重复生成的百分位列表，改为一次性构造并全局复用；同时用单遍游标扫描（sweep）替代对每个百分位的独立二分/线性查找，显著降低eth_feeHistory奖励缓存构建的计算开销。读完本文，你将理解 Anvil 内部FeeHistoryCache的数据结构、百分位奖励的计算原理、该优化前后的差异，以及它如何与eth_maxPriorityFeePerGas、fork 模式下的历史数据合并等特性协同工作。

一、变更背景：一次针对奖励缓存构建的 patch

该 changelog 条目属于anvil: patch级别，原文为：

Improvedeth_feeHistoryreward cache construction by sweeping reward percentiles once.

即：通过一次性扫描百分位来改进eth_feeHistory奖励缓存的构建过程。这是一个典型的"低风险、性能收益明确"的内部优化 patch，不改变 RPC 对外返回的数据语义，只改变数据计算的方式。

结合源码（crates/anvil/src/eth/fees.rs 与 crates/anvil/src/eth/api.rs）可以看到，该优化的落点集中在两个核心常量与一个关键函数：

• REWARD_PERCENTILE_RESOLUTION：百分位列表的分辨率；
• REWARD_PERCENTILES：预计算的 0.0～100.0 百分位列表（LazyLock静态常量，全局只计算一次）；
• reward_percentiles()：按百分位列表单遍扫描交易的内部函数。

二、奖励百分位列表：从每次重建到全局一次

2.1 常量定义与静态初始化

在 crates/anvil/src/eth/fees.rs 中，定义如下：

/// Number of cached reward samples per percentile. pub(crate) const REWARD_PERCENTILE_RESOLUTION: f64 = 2.0; /// Percentile list from 0.0 to 100.0 with a 0.5 resolution (201 points). /// /// Constant across blocks, so it is computed once instead of being rebuilt on every /// `create_fee_history_cache_item` call. static REWARD_PERCENTILES: LazyLock<Vec<f64>> = LazyLock::new(|| (0..=200).map(|index| index as f64 / REWARD_PERCENTILE_RESOLUTION).collect());

关键点：

• REWARD_PERCENTILE_RESOLUTION = 2.0表示每个百分位点对应的索引步长为 0.5，即列表覆盖0.0, 0.5, 1.0, ..., 100.0，共0..=200共201 个百分位点；
• REWARD_PERCENTILES使用LazyLock<Vec<f64>>声明为进程级静态常量，仅在首次访问时构造一次；
• 源码注释明确指出该列表"跨区块恒定（Constant across blocks）"，因此被提升为静态常量，避免在每次create_fee_history_cache_item调用时重复构建——这正是 changelog 所描述的优化前半部分："sweeping reward percentiles once" 中"列表只构造一次"的体现。

对比旧实现（可从注释推断）：旧代码在每次构建缓存条目时都重新生成一份完整百分位列表，区块越多、缓存重建越频繁，浪费越大；新实现将其提升为全局惰性常量，首次访问后零重建成本。

2.2 为什么 201 个点？

• 覆盖完整：百分位从 0.0 到 100.0 全覆盖，任何合法请求的百分位（0～100 区间内的任意值）都能在预计算数组中找到对应样本；
• 插值精度：0.5 的分辨率意味着相邻百分位点间隔 0.5%，足以支撑reward_at_percentile通过取整索引近似定位（见下文 §4）；
• 内存成本恒定：每区块缓存条目中rewards: Vec<u128>固定为 201 个u128（约 3.2 KB/区块），在 fees.rs 的FeeHistoryCacheItem中作为普通字段存储。

三、核心算法：单遍游标扫描（sweep）

3.1 计算原理

reward_percentiles函数（crates/anvil/src/eth/fees.rs）接收已按有效奖励升序排序的交易数组(gas_used, effective_reward)与区块总 Gas 消耗，为 201 个百分位点逐一计算对应的有效奖励：

/// Calculates percentile rewards from transactions sorted by effective reward. /// /// [`REWARD_PERCENTILES`] must remain ascending because the transaction cursor never rewinds. fn reward_percentiles(transactions: &[(u64, u128)], block_gas_used: f64) -> Vec<u128> { let mut rewards = Vec::with_capacity(REWARD_PERCENTILES.len()); let mut transactions = transactions.iter().copied(); let Some((mut cumulative_gas, mut current_reward)) = transactions.next() else { return rewards; }; for &percentile in REWARD_PERCENTILES.iter() { let target_gas = (percentile * block_gas_used / 100f64) as u64; while target_gas > cumulative_gas { let Some((tx_gas_used, effective_reward)) = transactions.next() else { return rewards }; cumulative_gas += tx_gas_used; current_reward = effective_reward; } rewards.push(current_reward); } rewards }

算法要点：

1. 语义定义：百分位p的奖励 = 当累计 Gas 首次达到p / 100 * block_gas_used时，所落到的那笔交易的有效奖励；
2. 单遍扫描：由于REWARD_PERCENTILES严格递增（源码注释明确要求"必须保持升序，因为交易游标从不回退"），外层循环逐点推进，内层while只在当前目标百分位超过累计 Gas 时才消费下一笔交易——每个百分位点共享同一个前向游标，交易数组最多被完整遍历一次；
3. 无回退（never rewinds）：这是该实现正确性的前提，也是其性能优于"对每个百分位独立从头遍历"方案的根本原因；
4. 提前终止：当交易耗尽（如区块 Gas 未满）时直接返回已收集的结果，剩余百分位点保持为空。

3.2 优化前后的复杂度对比

• 朴素实现（优化前）：对每个百分位点，都需要从头（或在累积意义上）遍历交易直到达到目标 Gas。201 个百分位 × 每区块交易数，单区块最坏为 O(201 × n)。
• 单遍扫描（优化后）：201 个百分位点共享一个游标，交易数组整体只被扫描一遍，单区块最坏为 O(201 + n)。

在自动化测试驱动的本地链（Anvil 常用于测试，区块频繁产生、交易密度高）上，该优化直接降低eth_feeHistory奖励构建的热路径成本。

3.3 单元测试的验证

fees.rs 内嵌的测试模块专门验证了新算法与参考实现的一致性：

• reward_percentile_sweep_preserves_boundaries_and_empty_results：覆盖空交易数组（返回空奖励）、零 Gas 边界（如[(0, 10), (1, 20)]时前 200 个百分位点奖励恒为 10、第 201 个点为 20）等边界情况；
• reward_percentile_sweep_matches_reference_for_randomized_inputs：用确定性伪随机数生成器（LCG，见next_random）随机生成 2000 组交易序列与 Gas 组合，逐一断言单遍扫描结果与参考实现（reward_percentiles_reference，即朴素逐点遍历）完全一致，验证了算法正确性不受交易数、Gas 缺口、零 Gas 交易等因素影响。

四、缓存条目的构建与消费链路

4.1 数据来源：从区块头与收据提取交易信息

create_fee_history_cache_item（crates/anvil/src/eth/fees.rs）负责为单个区块构建FeeHistoryCacheItem：

1. 从区块头提取base_fee、excess_blob_gas、blob_gas_used，并通过blob_params计算base_fee_per_blob_gas；
2. 若区块与收据均可用（从storage_info.block(hash)/storage_info.receipts(hash)获取）：
   • 计算gas_used_ratio（gas_used / gas_limit）与blob_gas_used_ratio（相对blob_params.max_blob_gas_per_block()）；
   • 逐笔交易计算gas_used（当前收据cumulative_gas_used减上一收据的累积值）与effective_reward（即effective_tip_per_gas(base_fee)）；
   • 按有效奖励升序排序后交给reward_percentiles生成 201 个百分位样本；
3. 若区块或收据缺失，则以 201 个 0 填充rewards（vec![0; REWARD_PERCENTILES.len()]），保证缓存条目结构完整。

注意：这里"按奖励升序排序"（transactions.sort_by_key(|(_, reward)| *reward)，见 fees.rs）正是上游reward_percentiles前置条件"已排序"的保证。

4.2 双路径写入：异步服务 + RPC 兜底

FeeHistoryCache的类型为Arc<Mutex<BTreeMap<u64, FeeHistoryCacheItem>>>（fees.rs），以区块号为键有序存储。缓存写入存在两条路径：

1. 异步服务：FeeHistoryService（fees.rs）实现Future，轮询ChainNotifications新区块通知，对每个新块调用insert_cache_entry_for_block；
2. RPC 兜底：由于异步服务可能落后于链头（只在节点任务被 poll 时运行），eth_feeHistory处理器在缓存缺失或哈希不匹配时按需现场计算同一条create_fee_history_cache_item逻辑，再以单次加锁批量回填缓存（crates/anvil/src/eth/api.rs）。

两条路径共用同一个构建函数，保证数据口径一致；缓存写入统一走insert_fee_history_cache_item，并在超出MAX_FEE_HISTORY_CACHE_SIZE（2048，见 fees.rs）时通过pop_first()裁剪最旧区块（fees.rs）。

4.3 百分位请求的解析：reward_at_percentile

FeeHistoryCacheItem中存储的是固定 201 点的奖励样本，而请求方可能只要求少数几个百分位（如[50.0]）。RPC 处理器通过reward_at_percentile（crates/anvil/src/eth/api.rs）从预计算样本中按索引取近似值：

fn reward_at_percentile(rewards: &[u128], percentile: f64) -> u128 { let index = (percentile * REWARD_PERCENTILE_RESOLUTION).round() as usize; rewards.get(index).copied().unwrap_or_default() }

即请求的百分位p对应样本索引round(p × 2.0)，与 §2.1 中 0.5 分辨率的列表一一对应。这正是"预计算一次、任意请求即时查表"的设计闭环：无论请求方要 1 个还是 50 个百分位，区块侧都只做一次 201 点的扫描，后续全部是 O(1) 查表。

4.4 请求参数校验

在进入计算前，fee_history处理器会先做参数校验（api.rs）：

• 任何百分位必须落在[0.0, 100.0]区间内；
• 百分位列表必须严格递增（pair[0] >= pair[1]即非法）；
• block_count为 0 时直接返回空FeeHistory；
• block_count上限 1024（MAX_BLOCK_COUNT），并受缓存范围约束（超出best_number - fee_history_limit返回InvalidBlockRange）。

对应的行为由集成测试覆盖：fee_history_rejects_invalid_reward_percentiles（api.rs）断言非法百分位返回FeeHistoryError::InvalidRewardPercentiles，合法值正常通过。

五、优化带来的连锁收益

5.1 eth_maxPriorityFeePerGas 的基石

lowest_suggestion_tip（api.rs）依赖FeeHistoryCacheItem.rewards获取当前区块所有百分位奖励的最小值作为建议小费，再与MIN_SUGGESTED_PRIORITY_FEE（1 gwei，fees.rs）取较大者，最终由eth_maxPriorityFeePerGas返回。由于奖励样本是预计算的 201 点列表，小费建议无需额外遍历交易，直接读取缓存即可——优化后的单遍扫描间接加速了该路径。

5.2 fork 模式下的一致性

在 fork 模式下，eth_feeHistory处理器先对 pre-fork 区块段调用 fork provider 的fee_history，再对 post-fork 段走本地缓存/兜底计算，并通过merge_pre_fork_fee_history（api.rs）合并（详见 api.rs 的注释说明）。本地段无论来自异步缓存还是兜底计算，都走同一条create_fee_history_cache_item，因此本优化对 fork 场景的本地侧同样生效，且不会改变合并后的数据语义。

5.3 对外的可观测行为

本 patch 不改变eth_feeHistory响应的字段结构、数值语义或错误码，属于纯内部性能优化。对于通过该接口获取 Gas 预估（如钱包估算maxPriorityFeePerGas）的工具来说，返回结果保持一致，但 Anvil 在频繁出块、交易密集的测试场景下构建奖励缓存的开销更低。

六、小结与扩展阅读

anvil-fee-history-percentile-sweep这个 patch 的核心是把"每区块重复构造百分位列表"重构为"全局一次性构造 + 单遍游标扫描 + O(1) 查表"三段式设计：

1. 静态化：REWARD_PERCENTILES（201 点）由LazyLock全局构造一次；
2. 单遍化：reward_percentiles用不回退的游标一次性为全部百分位点计算奖励，交易数组只遍历一遍；
3. 查表化：reward_at_percentile按索引直接取样本，任意请求即时响应。

对于希望深入源码的读者，建议按以下路径阅读：

• 缓存数据结构与裁剪策略：crates/anvil/src/eth/fees.rs（FeeHistoryService、insert_fee_history_cache_item）；
• 奖励百分位算法与边界测试：crates/anvil/src/eth/fees.rs 与 测试模块；
• RPC 入口与参数校验：crates/anvil/src/eth/api.rs（fee_history处理器）；
• 缓存缺失兜底与回填：crates/anvil/src/eth/api.rs；
• 小费建议的消费方：crates/anvil/src/eth/api.rs（lowest_suggestion_tip）。

【免费下载链接】foundryFoundry is a blazing fast, portable and modular toolkit for Ethereum application development written in Rust.项目地址: https://gitcode.com/GitHub_Trending/fo/foundry