特别感谢Terry和Fikunmi提前阅读本文的早期版本并提供反馈。
引言
Solana 是一个高吞吐量区块链，旨在保持完整的容量利用率，而不需要人为限制区块空间。与依赖动态基本费用模型（EIP-1559）的以太坊不同，该模型明确使区块空间稀缺，Solana 的设计理念强调丰富的容量和低延迟。然而，这带来了一个独特的挑战：网络如何引导用户支付反映实时竞争的费用，而不依赖于依赖区块饱和的传统费用模型？
最近Fikunmi提出的LRU缓存^1解决方案旨在通过仅跟踪最具争议的账户，并推荐与当前条件紧密相关的费用来改进 Solana 的费用市场。在这篇文章中，我们严格地形式化了这一方法，整合了直接的网络负载信号（如调度程序和QUIC入口积压），并考虑了使费用估算更能响应近实时网络状态的自适应窗口。我们还引入了控制理论视角，以确保在动态交易到达率的情况下，系统的稳定性、均衡性和可预测性。
我们的框架表明，可以接近Toly^2和其他 Solana 社区成员所阐述的愿景：建立一个健康的费用市场，自然鼓励适当的费用竞标——而不强迫生成空块或丢弃低费用交易。
背景
在深入探讨我们的形式化之前，让我们在高层次上重新表述问题：
- 没有人工限制：Solana 希望尽可能使块保持满。交易不应仅仅因为未满足“基本费用”而被丢弃。
- 负载响应：费用推荐应直接响应拥塞信号——调度程序积压、QUIC入口队列深度——而不是等待区块饱和。
- 数据的新鲜性：费用推荐应反映即时状态。过去的热门账户如果冷却不应抬高当前的费用推荐。
我们的方法：一个精细化的 LRU 缓存设计，用于存储最具争议账户的最近中位费用，将这些费用与全局中位费用结合，然后根据实时负载指标进行缩放。我们通过严谨的数学和基本控制理论原则将这些概念结合在一起。
形式化设置
时间和槽：
我们假设离散时间间隔 $t \in \mathbb{N}$，其中每个槽对应一个 Solana 区块。
账户和费用：
- 让 $\mathcal{A}$ 是网络上所有账户的集合。
- 对于每个槽 $t$，让 $A_t \subseteq \mathcal{A}$ 是在该槽中被交易触及的账户集合。
- 让 $f{t}(a)$ 表示在槽 $t$ 中访问账户 $a$ 的交易所支付的观察到的中位优先费用。如果在槽 $t$ 中没有交易触及 $a$，则 $f{t}(a) = \emptyset.$
全局费用：
我们定义全局中位费用 $f_t^{(global)}$ 为在槽 $t$ 中包含的所有交易的中位优先费用。
引入直接负载信号
为了不再关注区块的饱和度，我们考虑：
- $Q(t)$：时间 $t$ 的 QUIC 入口队列深度。
- $S(t)$：时间 $t$ 的调度程序积压。
这些提供了网络拥塞的更直接的衡量标准。我们将它们合并成一个负载向量：
$$L(t) = (Q(t), S(t)) \in \mathbb{R}_{\ge 0}^2.$$
LRU缓存结构
我们维护一个 LRU（最近最少使用）缓存，用于跟踪任何给定时间内最具争议的账户：
- 让 $C(t) \subseteq \mathcal{A}$ 是在槽 $t$ 结束时当前在缓存中的账户集。
- 缓存大小和驱逐规则确保它仅包含在非常近期窗口内有争议的账户。
我们定义一个短的回顾窗口 $w \leq W(t)$，其中 $W(t)$ 是我们考虑的（可能是自适应的）最近槽的数量。对于每个缓存账户 $a \in C(t)$，我们计算 $a$ 在过去 $w$ 个槽中被触及时的中位费用：
$$Ma(t) = \text{median}{ f{\tau}(a) \mid t-w+1 \leq \tau \leq t, f_{\tau}(a) \neq \emptyset }.$$
我们还维护一个最近槽中的全局中位费用：
$$M{global}(t) = \text{median}{ f{\tau}^{(global)} \mid t-W_g+1 \leq \tau \leq t }$$
对于某个全局回顾窗口 $W_g$。
缓存动态：
- 驱逐在过去 $W(t)$ 个槽中未被看到的账户或拥有过时数据的账户。
- 将槽 $t$ 中最具争议的前 $k$ 个账户插入 $C(t)$。
形式化为：
$$C(t) = (C(t-1) \setminus E(t)) \cup I(t)$$
其中 $E(t)$ 是驱逐，$I(t)$ 是新的插入。
自适应回顾窗口
我们希望系统在高负载下反应更快，在低负载下更稳定。为此，我们让回顾窗口 $W(t)$ 依赖于当前负载 $L(t)$。
例如：
$$W(t) = \frac{W0}{1 + \theta L{norm}(t)},$$
其中 $L_{norm}(t) = \alpha Q(t) + \beta S(t)$ 是负载指标的加权和，$\theta, W_0, \alpha, \beta > 0$ 是参数。
当拥塞严重时（$L_{norm}(t)$大），$W(t)$ 会缩小，以确保我们依赖更新的、更即时的数据。当负载稳定且较低时，$W(t) \approx W_0$，为我们提供了稍微平滑的历史视图。
费用推荐函数
对于时间 $t$ 触及账户 $A_T \subseteq \mathcal{A}$ 的交易，我们希望生成推荐费用 $F(t)$。我们结合全局和每个账户的中位数，然后根据负载进行缩放：
$$F(t) = \max{ M{global}(t), \max{a \in A_T \cap C(t)} M_a(t) } \cdot G(L(t)),$$
其中 $G: \mathbb{R}{\ge 0}^2 \to \mathbb{R}{> 0}$ 是一个单调非递减函数，表示我们如何根据负载上下调整费用。
定义负载缩放函数 $G$
可以选择一个简单的指数形式：
$$G(L(t)) = 1 + \alpha Q(t)^\beta + \gamma S(t)^\delta,$$
其中 $\alpha, \beta, \gamma, \delta > 0.$
或者，为了更精细的控制，使用一个控制理论的反馈回路（如 PID 控制器）：
$$G(L(t)) = \exp\bigl( K_p E(t) + Ki \sum{\tau=0}^{t} E(\tau) \Delta\tau + K_d \frac{E(t)-E(t-1)}{\Delta\tau}\bigr),$$
其中 $E(t) = S(t) - S^*$ 测量相对于目标调度程序积压 $S^*$ 的偏差。
均衡分析
目标：显示系统可以达到一个稳定的均衡。均衡发生在费用、负载和到达率稳定时。
- 让 $\lambda$ 是稳态交易到达率。
- 在均衡时，我们有一个固定点 $(F^*, L^*)$，其中：
$$F^ = \Phi(F^, L^) \quad \text{和} \quad L^ = \Psi(F^*, \lambda),$$
对于某些连续函数 $\Phi$ 和 $\Psi$。
均衡的存在：
在合理的假设下——有界负载、平稳到达率、连续和单调的费用响应函数——布劳威尔不动点定理^3保证至少存在一个固定点。简而言之，如果当负载增加时提高费用，且当费用过高时负载减小，系统应能找到一个稳定的操作点。
稳定性：
稳定性取决于 $G$ 的敏感性和调节参数（如 $K_p, K_i, K_d$ 或 $\alpha, \beta, \gamma, \delta$）。通过围绕 $F^*$ 的线性化，标准控制理论（Routh-Hurwitz 条件）^4可以验证是否没有持续的振荡发生。
响应性与可预测性
该方法的一个关键特征是平衡响应性与可预测性：
-
如果没有账户有争议：
如果在缓存中未找到热门账户，且负载较低，我们有：
$$F(t) \approx M_{global}(t).$$
这确保在正常情况下费用稳定且较低。
-
如果某些账户有争议：
如果某个账户需求旺盛，则：
$$\max_{a \in A_T \cap C(t)} Ma(t) > M{global}(t),$$
提高触及该账户的交易 推荐费用。此机制鼓励适当的竞标，而不强制排除。
窗口稳定性和新鲜性
当负载稳定时，$L{norm}(t) \to L{norm}^*$，并且：
$$\lim_{t \to \infty} W(t) = \frac{W0}{1 + \theta L{norm}^*}.$$
这确保系统的回顾窗口收敛到一个稳定范围，平衡即时响应与不必要的波动。
参考文献
