第 1 部分：Solana 费用市场的排队理论基础
引言
Solana 对快速、高吞吐量区块链操作的承诺依赖于一个有效的费用市场，即使在高负载下也能保持网络稳定。在传统区块链中，简单的“竞标战”可以通过费用优先处理交易，但 Solana 的架构涉及多个顺序阶段：网络入口、签名验证、调度和执行。
我们为什么需要排队理论的视角？ 因为当请求（交易）的到达率接近或超过系统的容量时，自然会出现拥堵。Solana 本地费用市场的方法—在某些阶段优先处理高费用交易—类似于排队系统中的经典优先级调度。通过将 Solana 的流水线转化为排队模型，我们可以：
- 量化负载（到达率 $\lambda$）和容量（服务率 $\mu$）之间的相互作用
- 确定高费用交易何时真正受益于优先调度
- 确定动态费用下限（入门控制）如何确保稳定，防止无限排队的积累
在第 1 部分，我们介绍基本的 M/M/1 排队（单服务器、泊松到达、指数服务）。然后将其扩展为两类优先级队列，展示高费用交易在拥堵系统中的表现。最后，我们研究负载卸载（费用下限）和多服务器 M/M/k 情景。这个理论基础为第 2 部分奠定了基础，在那里我们将 Solana 的多阶段流水线映射到串联队列，并提出在不同负载下保持系统稳定的控制理论解决方案。
单服务器模型（M/M/1）
M/M/1 排队理论中通常首先教授这个模型，因为它的简单性：
- M = 马尔可夫（泊松）到达率为 $\lambda$
- M = 马尔可夫（指数）服务时间的服务率为 $\mu$
- 1 = 一个服务器
关键方程
利用率：
$$\rho \;=\; \frac{\lambda}{\mu}.$$
稳定性的必要条件是 $\rho < 1$。如果 $\lambda \ge \mu$，队列将无限增长。
利特尔法则：
利特尔法则 是排队理论中的一个基本定理，描述了排队系统中项目的平均数量、项目的平均到达率和项目在系统中逗留的平均时间之间的关系。
$$L \;=\; \lambda \,\times\, W,$$
其中
- $L$ 是系统中交易的平均数量（队列 + 服务器），
- $\lambda$ 是到达率，
- $W$ 是每笔交易在系统中逗留的平均时间（等待 + 服务）。
系统中的平均数量：
$$L \;=\; \frac{\rho}{1 - \rho},$$
假设 $\rho < 1$。
队列中的平均数量（不包括服务）：
$$L_q \;=\; \frac{\rho^2}{1 - \rho}.$$
队列中的平均等待时间：
$$W_q
\;=\; \frac{L_q}{\lambda}
\;=\; \frac{\rho}{\mu(1 - \rho)}.$$
当 $\rho \to 1$ 时，$L_q$ 和 $W_q$ 都会增长到非常大的值，显示出拥堵的特征。
与费用市场的相关性
- 饱和： 如果 $\lambda$（交易到达）接近 $\mu$（吞吐能力），等待时间会激增。
- 本地费用市场： 如果高费用交易不能在饱和系统中绕过低费用交易，支付更多的优势将丧失。
- 控制 $\lambda$： 通过提高费用下限或以其他方式卸载低费用负载，我们有效地减少了 $\lambda$，保持 $\rho$ 远低于 1。
优先排队：M/M/1 的两个类
M/M/1 的两类优先扩展可以捕捉高费用与低费用交易的区别。
- 类别 1: 高费用，到达率 $\lambda_1$。
- 类别 2: 低费用，到达率 $\lambda_2$。
- 总到达率： $\lambda = \lambda_1 + \lambda_2$。
- 单服务器： 速率 $\mu$。
- 利用率： $\rho = \lambda/\mu$。
非抢占优先
在非抢占优先级中：
- 如果服务器空闲，且类别 1 和类别 2 的交易同时到达，类别 1 优先。
- 如果服务器已经正在处理类别 2 的交易，它将在切换到新到达的类别 1 之前完成该工作。
平均等待时间
确切的公式推导可以在 Kleinrock 的排队系统 等书中找到^1。一个简化的表示：
-
类别 1（高费用）平均等待时间，$W_{q,1}$ 可能看起来像：
$$W_{q,1}
\;=\; \frac{\rho_1}{\mu(1 - \rho_1)} + \Phi(\rho_1, \rho_2)，$$
其中 $\rho_1 = \lambda_1/\mu$，$\Phi(\rho_1, \rho_2)$ 捕获类别 1 在某些时候可能需要等待已在服务中的类别 2 作业。
-
类别 2（低费用）平均等待时间，$W_{q,2}$ 必然更长，因为类别 1 在前面插队。
关键洞察
如果 $\rho_1 < 1$，即使类别 2 很大，类别 1 的等待时间仍然较低。然而，如果 $\rho = \rho_1 + \rho_2$ 接近 1，每个人 最终都会受到影响，尽管类别 1 相对表现更好。
动态负载卸载（费用下限）
当 $\lambda_2$（低费用到达）较高时，可以提高 费用下限 $f$，使低于 $f$ 的交易被丢弃：
$$\lambda_2^\text{eff} = \lambda_2 \times \mathbf{1}{\text{fee} \ge f}.$$
这确保了 $\lambda^\text{eff} = \lambda_1 + \lambda_2^\text{eff} < \mu$。如果 $\rho$ 保持在 1 以下，队列长度将停止激增。
多个服务器：M/M/k
实际系统可能有 $k$ 个并行“服务器”（线程、核心等）。那么模型为 M/M/k ，其稳定性条件为 $\lambda < k\mu$。优先级类别仍然可以应用，但如果 $\lambda \gg k\mu$，即使如此也会发生过载。这为 Solana 的流水线如何通过添加更多并行执行线程进行扩展奠定了基础。
综合回顾 - 第 1 部分
让我们简要回顾一下到目前为止学到的内容：
- 平衡 $\lambda$ 和 $\mu$: 稳定等待时间的基本要求。
- 优先队列： 如果 $\rho_1$ 远低于 1，高费用（类别 1）会受益。
- 费用下限与入门控制： 降低低费用到达率 ($\lambda_2$) 以保持 $\rho$ 低于 1。
- 并行化： M/M/k 可以提高总容量，但如果 $\lambda$ 仍超过 $k\mu$，则会出现大型队列。
参考文献
