RFT-SIRM/agave-rift-scheduler

## 这是什么 本仓库包含了一个交易调度器的**参考实现**，旨在探索有限重试语义和确定性饥饿可观测性。它的构建目的是： 1. 对持续账户级别写入争用下的调度行为进行建模。 2. 验证可以在不违反不变量的情况下实施有限重试语义。 3. 提供一个具体的提案，以便与 Agave 核心团队进行讨论。 **上游互动：** - 📋 **[RFC] GreedyScheduler 的有限重试语义与饥饿可观测性** — [anza-xyz/agave#14274](https://github.com/anza-xyz/agave/issues/14274) - 🔒 **SVM 运行时中的 CPI 权限泄漏** — [anza-xyz/svm#25](https://github.com/anza-xyz/svm/issues/25)（来自同一实验室的相关安全研究） **这并不是针对 Agave 的生产级补丁。** 它是一个研究产物。请参阅下方的[免责声明](#disclaimer)。 ## 背景：为什么会有这项研究 Agave 中默认的 `GreedyScheduler`（`core/src/banking_stage/transaction_scheduler/greedy_scheduler.rs`）通过将冲突交易重新插入优先级队列来延迟处理它们。这种设计在常见情况下是正确的，但它并未暴露： - 每笔交易的独立重试计数器， - 可配置的延迟次数上限， - 当交易因过度延迟被丢弃时的 `dropped_transactions` 指标。 在热点账户持续存在写入争用的情况下，优先级较低的交易可能会在无限次数的调度遍历中被延迟。该交易**并未丢失**——它仍在队列中——但其调度延迟是**不受限制且无法观测的**。 本仓库实现了一种具有显式边界的替代调度语义，随后通过持续的模糊测试对这些边界进行验证。 ## 架构 ### 热点热度图 每个可写账户都会被跟踪一个热度分数： - 每次计划写入时，热度增加 `initial_heat`。 - 热度按每增加一个 generation 的年龄右移 `hotspot_decay_shift` 位来进行衰减。 - 超过 `max_generation_age` 个 generation 的账户将被驱逐。 ### Generation 老化 每次调用 `schedule()` 都会使 `current_generation` 增加 1。 延迟交易携带一个 `ready_generation` 时间戳。 只有当 `ready_generation ≤ current_generation` 时，交易才会被重试。 ### 重试周期 ``` Transaction arrives | v Priority queue | v Pop highest priority | v try_lock_accounts() | +---|---+ | | Success Conflict | | v v Schedule Increment retry counter | +--- retries > max_retry_count? ---+ | | No Yes | | v v Push to deferred queue Drop with metric increment (ready_generation = next gen) (dropped_transactions += 1) ``` ## 设计目标 **确定性调度** — 在给定相同的输入和配置时，调度器会产生相同的输出。调度路径中不存在随机性。 **有限次重试** — 每笔被延迟的交易要么被调度，要么在有限的次数内被丢弃。从结构上杜绝了永久饥饿的可能。 **冲突感知执行** — 可写账户的争用是通过每个账户的热度分数来跟踪的，而不是基于交易对。这使得系统能够扩展到庞大的账户集，而不会产生组合爆炸的开销。 **饥饿可观测性** — `max_retry_count` 对重试次数强制设定了严格的上限。无法在该限制内调度的交易将被丢弃，并伴随显式的指标增加（`dropped_transactions`），绝不会被静默延迟。 **可预测的内存行为** — 延迟队列受 `max_retry_count` 限制。热点映射受 `hotspot_capacity` 限制。不存在内存无限增长的路径。 ## 与 Agave GreedyScheduler 的关系 本实现**并非** Agave `GreedyScheduler` 的直接替代品。它是一个探索替代语义的研究模型。 | 属性 | Agave GreedyScheduler (当前版本) | 本实现 (研究版本) | |:---------|:----------------------------------|:-------------------------------| | 延迟队列排空 | 每次遍历后重新插入所有不可调度的交易 | 显式的按次遍历排空，带有重试计数器 | | 冲突检测 | 无条件 (当前主分支) | 无条件 | | 重试限制 | 无 — 无限延迟 | 通过 `max_retry_count` 设定硬性上限 | | 丢弃指标 | `SchedulingSummary` 中无此指标 | `dropped_transactions` 计数器 | | 基于热度的限流 | 线程级锁定 | 具有衰减特性的按账户热度分数 | | 模糊测试验证 | 此组件中未包含 | libFuzzer，每天 5 小时 55 分钟 | ## 不变量 在模糊测试期间，每次调度遍历之后都会断言所有不变量。 ### I1: 记账不变量 **陈述：** 每次遍历中 `scheduled + deferred + dropped ≤ scanned`。 **原因：** 每笔进入 `schedule()` 的交易都必须被记录在案。不允许发生静默丢失。 **失效模式：** 交易从所有计数器中消失。预算或队列逻辑中存在某个分支，在未增加任何计数器的情况下返回。 **验证方式：** `fuzz_target` 不变量 1 断言，单元测试 `defers_conflicting_hot_accounts`。 ### I2: Generation 单调性 **陈述：** 每次遍历后 `summary.generation > 0`。 **原因：** Generation 计数器必须严格为正数。Generation 为零会导致所有 `ready_generation = 1` 的延迟交易永远无法重试。 **失效模式：** Generation 计数器发生向下溢出。 **验证方式：** `fuzz_target` 不变量 2 断言。 ### I3: 遍历计数器单调性 **陈述：** 每次调用 `schedule()` 后 `scheduler_passes ≥ 1`。 **原因：** 指标必须能够正确累积。如果不增加遍历计数器，将会破坏所有派生指标。 **失效模式：** 在执行 `metrics.scheduler_passes += 1` 之前提前返回。 **验证方式：** `fuzz_target` 不变量 3 断言。 ### I4: 延迟队列排空 **陈述：** 在所有输入停止后，延迟队列会在有限的遍历次数内变为零。 **原因：** 队列永久增长意味着永久饥饿。每笔延迟交易最终都必须被调度或丢弃。 **失效模式：** 交易的 `ready_generation` 被设置为任何无法到达的 generation 值，或者缺少 `max_retry_count` 检查。 **验证方式：** `fuzz_target` 不变量 4 断言（8192 次排空遍历），单元测试 `deferred_transaction_is_dropped_after_max_retries`。 ## 开发历史 在构建此参考实现的过程中，我们在自己的代码中遇到并解决了几个设计错误。以下内容将其记录为**从零开始构建调度器的经验教训**，而非对 Agave 的论断。 ### 教训 1：死掉的延迟队列 **描述：** 早期版本将延迟交易推入 `self.deferred`，但再也没有读取过它们。该队列是只写的。 **影响：** 在我们自己的实现中，每笔延迟交易都被静默丢失了。 **修复：** 现在，每次 `schedule()` 遍历在处理新交易之前，都会将 `self.deferred` 划分为就绪条目和仍需等待的条目。 **回归测试：** `deferred_transactions_are_retried_and_eventually_scheduled` ### 教训 2：成本过滤交互 **描述：** 早期版本基于 `tx.cost > 0` 来控制冲突延迟。这是我们模型中的一个设计错误。 **影响：** 在我们的模拟中，零成本交易可以绕过冲突检测。 **修复：** 冲突检查现在是无条件的。成本仅与预算执行相关，而与冲突检测无关。 **回归测试：** `zero_cost_tx_does_not_bypass_conflict_detection` ## 测试矩阵 | 测试 | 目的 | 防止的不变量 / Bug | |------|---------|--------------------------| | `deferred_transactions_are_retried_and_eventually_scheduled` | 延迟队列死锁回归 | 教训 1 | | `zero_cost_tx_does_not_bypass_conflict_detection` | 成本过滤回归 | 教训 2 | | `deferred_transaction_is_dropped_after_max_retries` | 强制执行重试上限 | I4 违规 | | `hotspot_decay_reduces_heat_gradually` | 热度衰减正确性 | 饥饿 | | `budget_exhaustion_defers_without_conflict` | 预算与冲突分离 | 错误分类 | | `retried_transaction_succeeds_when_conflict_clears` | 完整重试周期 | I4 违规 | | `read_only_accounts_do_not_cause_conflicts` | 读取隔离 | 假冲突 | | `generation_counter_wraps_safely` | 溢出安全性 | I2 违规 | | `metrics_accumulate_across_scheduling_passes` | 指标正确性 | I3 违规 | | `multiple_independent_accounts_schedule_separately` | 避免假冲突 | 吞吐量损失 | | `budget_backoff_retries_next_generation` | 预算重试路径 | 静默丢弃 | | `max_retry_count_drops_transaction` | 防止饥饿 | I4 违规 | | `zero_cost_tx_in_high_conflict_defers` | 零成本 + 冲突 | 教训 2 变体 | | `defers_conflicting_hot_accounts` | 基本冲突检测 | I1 违规 | | `cleanup_removes_stale_hotspots` | 内存边界 | 无限增长 | | Fuzz target (5h 55m) | 所有 4 个不变量，随机配置 | 以上所有项 | ## 模糊测试 ### 测试组件设计 Fuzz target 生成： - 随机的 `SchedulerConfig`（范围受限以确保终止） - 随机的调度遍历序列 - 带有随机账户访问的随机交易 每次遍历后，都会对所有 4 个不变量进行断言。 所有遍历完成后，通过 8192 次排空遍历来验证 I4。 ### Fuzzer 中的配置边界 ``` // Ensures termination and bounded state space conflict_threshold: 1..=10, max_generation_age: 8..=32, hotspot_decay_shift: 0..=4, max_retry_count: 3..=20, hotspot_capacity: 256..=8192, initial_heat: 1..=10, max_account_heat: 64..=255, ``` ### 为什么长时间的模糊测试增加了信心，但并不能证明正确性 模糊测试通过随机方式探索输入空间。在 GitHub Actions 上以约 4,300 次/秒的执行速度运行 5 小时 55 分钟，大约会产生 9100 万次执行。这增强了我们的信心，即对于这种大小和形状的输入，不存在违反不变量的情况。但这并不构成正式的数学证明。正式验证需要模型检查或定理证明，这超出了本研究的范围。 ### 覆盖率稳定 覆盖率通常在最初的 100,000 次执行内稳定下来（`cov: ~420 ft: ~2600`）。随后的运行会完善语料库，但很少发现新的覆盖路径。这表明对于大小限制范围内的输入，测试组件已经穷尽了可到达的状态空间。 ## 性能 ### CI 运行器 (GitHub Actions, ubuntu-latest) | 指标 | 数值 | |--------|-------| | 每秒执行次数 | ~4,300 | | 稳定时的 RSS | ~612 MB | | 覆盖率 (ft) | ~2,661 | | 语料库条目 | ~436 | 这些数据描述的是在独立内存结构上运行的模糊测试组件。它们不是交易吞吐量数据，绝对不能与验证器的 TPS 基准测试相提并论。 ### 本机 (Apple Silicon M4) | 指标 | 数值 | |--------|-------| | 每秒执行次数 | ~8,500 (60 秒冒烟测试) | ### 未来基准测试占位符 - [ ] 调度器吞吐量 (tx/sec) — 待集成 Criterion - [ ] 重度热点负载下的延迟 - [ ] 90% 冲突交易吞吐量 - [ ] 90% 独立交易吞吐量 - [ ] 重度重试负载下的内存分配 - [ ] 持续负载下的内存使用情况 ## 配置参考 ``` SchedulerConfig { // Minimum heat score to defer a transaction (default: 1) conflict_threshold: u32, // Generations before a hotspot account is evicted (default: 16) max_generation_age: u32, // Heat right-shift per generation of age; 0 = no decay (default: 1) hotspot_decay_shift: u32, // Maximum retries before a transaction is dropped (default: 6) max_retry_count: u8, // Initial HashMap capacity for hotspot tracking (default: 4096) hotspot_capacity: usize, // Heat added on first write to an account (default: 2) initial_heat: u16, // Heat ceiling per account (default: 255) max_account_heat: u16, } ``` ## 路线图 **阶段 1 — 独立调度器 (当前)** 冲突检测，延迟队列排空，重试上限，热度衰减。 所有不变量均已验证。吸取的经验教训已通过回归测试。 **阶段 2 — 集成至 Agave** 与 `anza-xyz/agave` 的 transaction-context crate 集成。 用真实的 `TransactionContext` 和 `AccountId` 替换模拟类型。 **阶段 3 — 真实验证器基准测试** 在具有主网代表性的负载下，与现有的 Agave 调度器进行对比测量。 使用 Criterion 生成前后的对比。 **阶段 4 — RFC / PR** 向 `anza-xyz/agave` 提交一个聚焦的 Draft PR，包含： 模糊测试语料库、基准测试结果以及不变量文档作为证据。 ## 仓库布局 ``` . ├── Cargo.toml # Workspace manifest ├── src/ │ ├── lib.rs # Core scheduler engine │ ├── config.rs # SchedulerConfig │ ├── heat_map.rs # Hotspot tracking │ ├── deferred_queue.rs # Retry and generation logic │ └── metrics.rs # SchedulingSummary ├── tests/ │ └── integration_tests.rs # 15 regression tests ├── fuzz/ │ └── fuzz_targets/ │ └── scheduler_fuzz.rs # libFuzzer harness ├── .github/ │ └── workflows/ │ ├── ci.yml # Unit test + clippy │ └── fuzz-daily.yml # 5h 55m fuzz run └── README.md # This file ``` ## 快速开始 ``` # Clone git clone https://github.com/RFT-SIRM/agave-rift-scheduler.git cd agave-rift-scheduler # Build cargo build --release # 运行所有 tests cargo test --lib # 60 秒本地 fuzz cargo +nightly fuzz run scheduler_fuzz -- -max_total_time=60 # 完整的 5h 55m 运行 cargo +nightly fuzz run scheduler_fuzz -- -max_total_time=21300 ``` ## 生态系统 本仓库是 [RFT-SIRM](https://github.com/RFT-SIRM/UltraCore-RFT) 研究生态系统的一部分： | 仓库 | 角色 | 状态 | |:-----------|:-----|:-------| | [UltraCore-RFT](https://github.com/RFT-SIRM/UltraCore-RFT) | 核心研究中心与文档 | 活跃 | | [Rift-L1-Blockchain](https://github.com/RFT-SIRM/Rift-L1-Blockchain) | 具备 SIRM 不变量的独立验证器核心 | 核心完成 | | [Rift-Network](https://github.com/RFT-SIRM/Rift-Network) | Solana 链上协议 (Anchor) | RC v1.0 | | [agave-abiv2-memory-contexts](https://github.com/RFT-SIRM/agave-abiv2-memory-contexts) | SVM 内存隔离研究 | 活跃 | | **agave-rift-scheduler** | 交易调度研究 | **RFC 已发布** | ## 免责声明 - **非生产级补丁。** 这是一个研究性质的实现。如果不经过广泛的额外测试，不适用于部署在主网验证器上。 - **非针对 Agave 的 Bug 报告。** 该 RFC ([anza-xyz/agave#14274](https://github.com/anza-xyz/agave/issues/14274)) 记录了观察到的调度限制，并提出了一项最小化的可观测性改进建议。它并不意味着 GreedyScheduler 已损坏或不安全。 - **非共识性问题。** 本研究与交易调度延迟和可观测性有关，而与共识安全或交易完整性无关。 - **经验教训源自我们自己的代码。** “开发历史”部分记录了我们在构建此参考实现时犯下的错误。它们并非针对 Agave 中存在 Bug 的指控。 ## 许可证 Apache-2.0 — 参见 [LICENSE](LICENSE) © 2026 Eugeny (RFT-SIRM)

标签：Maven, Solana, 交易调度器, 区块链, 可视化界面, 漏洞验证, 研究项目, 通知系统