Solana Turbine 分层块传播机制层结构、加权选择与 FEC 恢复率计算【免费下载链接】solanaWeb-Scale Blockchain for fast, secure, scalable, decentralized apps and marketplaces.项目地址: https://gitcode.com/GitHub_Trending/so/solana本文深入讲解 Solana 共识体系中 Turbine涡轮块传播机制的设计与实现集群如何按DATA_PLANE_FANOUT扇出构建多层广播树、如何通过 stake 加权洗牌确定每个节点在树中的位置、shred碎片如何在层间逐级转发以及如何用二项分布计算前向纠错FEC恢复率以保证区块在丢包网络下仍可完整重建。读完本文你将能够理解 Turbine 树的构造与转发算法对应源码 cluster_nodes.rs并能独立复算不同 FEC 比例下的区块传播成功率。一、Turbine 总览为什么需要分层传播一个 Solana 集群使用名为 Turbine 的多层块传播机制将账本条目广播给所有节点。集群被划分为若干层layer每一层中的每个节点只负责把收到的数据转发给下一层中的一小部分节点。这样每个节点只需要与少量节点通信而不是与集群中所有 TVUTransaction And Vote Unit对等节点通信从而把广播复杂度从全连接降低到近似对数级的跳数。Turbine 的运作建立在两个组件之上BroadcastStage负责 slot leader 将 shred 广播给树根节点见 standard_broadcast_run.rsRetransmitStage负责集群中每个节点向下一层节点重传 shred见 retransmit_stage.rs。二、层结构Layer StructureLeader 与一个特殊的根节点通信。可以把该根节点视为第 0 层layer 0它负责与第 1 层通信而第 1 层最多由DATA_PLANE_FANOUT个节点组成。如果集群节点数超过第 1 层容量数据平面扇出机制就会在下方继续添加层之后每一层的节点数量按DATA_PLANE_FANOUT的倍数增长。直观的理解方式是第 0 层1 个节点root第 1 层fanout个节点第 2 层fanout × 第 1 层节点数个节点以此类推。在源码中扇出常量为固定值 200且当前广播协议统一走 UDP// turbine/src/cluster_nodes.rs const DATA_PLANE_FANOUT: usize 200; pub(crate) const MAX_NUM_TURBINE_HOPS: usize 4; #[inline] pub(crate) fn get_broadcast_protocol(_: ShredId) - Protocol { Protocol::UDP }从源码结构看树深上限被MAX_NUM_TURBINE_HOPS 4约束当 fanout 为 200 时第 0 层 1 个节点 第 1 层 200 个 第 2 层 40000 个已远超主网节点规模因此绝大多数节点落在前两层内。另外源码中还保留了一个扇出实验开关get_data_plane_fanout当 featureenable_turbine_fanout_experiments生效且未被关闭时约 2% 的 slot按shred_slot % 359命中特定余数会使用 64、128、256 等不同的实验扇出值其余 slot 仍使用 200。层分配加权选择Weighted Selection要让数据平面扇出工作整个集群必须就集群如何被切分层达成一致。为此所有被认可的验证节点即 TVU peers会按 stake 加权洗牌weighted shuffle存入一个列表这个列表随后以不同方式被索引用于确定层边界和重传对等节点——这就是所谓的turbine 树。例如列表洗牌后leader 选择第一个节点作为 rootroot 再选择接下来的DATA_PLANE_FANOUT个节点组成第 1 层。洗牌偏向高 stake 节点使权重更高的投票更早返回 leader。第 2 层及更深层的节点使用同样的逻辑寻找下一层的对等节点。为减少攻击面列表在每一个 shred 上都会重新洗牌和索引turbine 树基于每个 shred 的验证节点集合生成其随机种子由 slot leader id、slot、shred index 和 shred type 派生。这一点在源码中可以直接印证// ledger/src/shred.rs —— ShredId 定义与种子派生 pub struct ShredId(Slot, /*shred index:*/ u32, ShredType); impl ShredId { pub fn seed(self, leader: Pubkey) - [u8; 32] { let ShredId(slot, index, shred_type) self; hashv([ slot.to_le_bytes(), u8::from(*shred_type).to_le_bytes(), index.to_le_bytes(), AsRef::[u8]::as_ref(leader), ]).to_bytes() } }// turbine/src/cluster_nodes.rs —— 用种子初始化 ChaChaRng fn get_seeded_rng(leader: Pubkey, shred: ShredId) - ChaChaRng { let seed shred.seed(leader); ChaChaRng::from_seed(seed) }即 seed hash(slot, shred_type, index, leader pubkey)所有节点用同一 seed 初始化同一 ChaChaRng再对同一份 stake 加权的WeightedShuffle执行相同洗牌得到的节点顺序全网一致无需任何额外通信。配置值说明DATA_PLANE_FANOUT— 决定第 1 层的规模之后每一层按DATA_PLANE_FANOUT的倍数扩张。每一层会先被填满才会新增层即若某层不满它一定是最后一层。配置当前在集群启动时确定。文档同时指出未来这些参数可能托管在链上允许随着集群规模变化动态调整——这与当前源码中常量 feature 开关实验的实现阶段相符从get_data_plane_fanout的实验设计可以看到参数动态化的探索痕迹。三、Shred 传播流程Shred Propagation Flow在其 slot 期间leader 向位于 turbine 树顶端的特殊 root 节点layer 0做初始广播。该 root 节点基于前文所述加权洗牌每个 shred 轮换一次。root 把数据共享给第 1 层第 1 层节点再把 shred 重传给下一层layer 2的一个子集。一般而言layer-1 中的每个节点都会向下一层的一个互不重叠的子集重传依此类推直到集群中所有节点都收到全部 shred。为防止重复传输每个节点利用确定性生成的 turbine 树、自己在树中的索引和DATA_PLANE_FANOUT遍历树来识别下游节点。每一层的每个节点最多只需把 shred 广播给下一层中DATA_PLANE_FANOUT个节点而不是集群中所有 TVU 对等节点。下图展示了一个 15 节点集群、扇出为 3 时 shred 的传播方式图片随文档存放于docs/static/img/对应仓库路径 />转发对等节点的确定get_retransmit_peers节点向谁重传由纯算术从洗牌后的节点数组中推出。源码注释与实现清晰地刻画了层布局以 fanout 记为 Froot : [0] 1st layer: [1, 2, ..., F] 2nd layer: [[F1, ..., F*2], [F*21, ..., F*3], ..., [F*F1, ..., F*(F1)]] 3rd layer: ...// turbine/src/cluster_nodes.rs fn get_retransmit_peersT: Copy( fanout: usize, index: usize, // 本节点在洗牌后 nodes 切片中的索引 nodes: [T], ) - impl IteratorItem T _ { // 节点在邻域内的偏移 let offset index.saturating_sub(1) % fanout; // 邻域内的第一个节点 let anchor index - offset; let step if index 0 { 1 } else { fanout }; (anchor * fanout offset 1..) .step_by(step) .take(fanout) .map(|i| nodes.get(i)) .while_some() .copied() }规则可以读作第 1 层的节点 k 会重传给fanout k, 2*fanout k, ..., fanout*fanout k第 2 层中同余位置上的节点rootindex 0则直接取接下来的fanout个节点作为第 1 层。对称地get_retransmit_parent用同样的邻域偏移反推出某节点的父节点保证我转发给你的那批节点与它们认定的父节点严格互逆——单测test_get_retransmit_nodes_round_tripfanout 27、节点数 1300即验证了这一往返一致性另有test_get_retransmit_nodes用小型手工构造的树逐节点核对父子关系。根距离与节点集合的构建ClusterNodes::get_retransmit_peers还负责计算本节点距离 root 的层数root_distance用于监控传播延迟// turbine/src/cluster_nodes.rsget_retransmit_peers 内 let root_distance if self_index 0 { 0 } else if self_index fanout { 1 } else if self_index fanout.saturating_add(1).saturating_mul(fanout) { 2 } else { 3 // If changed, update MAX_NUM_TURBINE_HOPS. };值得注意的几点实现细节节点集合的组成get_nodes将本节点 gossip 中所有已知 tvu peers 所有有 stake 的节点合并按 (stake, pubkey) 降序排序并去重因此有 stake 但尚未同步到 contact-info 的节点也占树中位置其地址在转发时被跳过但树形不变全网一致性得以保持排除 leader 自身若 slot leader 就是本节点get_retransmit_peers直接返回Loopback错误防止 leader 自己参与重传形成回环按 epoch 缓存ClusterNodesCache以 epoch 为键、带 TTL 地缓存ClusterNodes每个 epoch 只重算一次 stake 加权洗牌结构而树形顺序则仍按每个 shred 的 seed 现算兼顾一致性与性能重传主循环retransmitretransmit_stage.rs 中fn retransmit从接收队列取出 shred 批先经ShredDeduper去重允许同一 ShredId 最多MAX_DUPLICATE_COUNT个不同副本通过用于跨集群检测重复区块再查 slot leader 与ClusterNodes最终调用retransmit_shred计算下游地址并通过multi_target_send批量发送大批次会用线程池并行处理。四、FEC 恢复率FEC Rate的计算Turbine 依赖验证节点之间对数据包的重传。由于存在重传全网级别的丢包会被逐级放大数据包未能到达目的地的概率随着跳数增加而上升。因此 FEC 恢复率必须同时考虑全网丢包率和传播深度。**Shred 组shred group**是可以互相重建的一组 data 与 coding 包。每个 shred 组都有一定的失败概率取决于失败包数量超过 FEC 容量的可能性。如果某个验证节点未能重建该 shred 组则区块无法被重建该节点只能依赖 repair 机制修复区块。二项分布模型shred 组的失败概率可以用二项分布计算。若 FEC 率为16:4则组大小为 20至少要有 4 个 shred 失败该组才会失败即等于 20 次试验中 4 次及以上失败的概率之和。区块在 turbine 中成功传播的概率模型为数据包失败概率P 1 - (1 - network_packet_loss_rate)^2FEC 率K:M试验次数N K MShred 组失败率S 1 - (SUM of i0 - M for binomial(prob_failure P, trials N, failures i))每区块 shred 数G区块成功率B (1 - S) ^ (G / N)其中二项分布在 N 次试验中以概率 P 恰好出现 i 次定义为(N choose i) * P^i * (1 - P)^(N-i)注意P的平方项正体现了重传导致丢包复利的直觉一次接收需要数据与转发两个方向的可用性文档按1-(1-L)^2建模两次独立失败。算例复现文档给出的场景假设全网丢包率 15%一个 50k TPS 的网络每秒产生 6400 个 shredFEC 率使每区块 shred 总数按 FEC 比例放大。FEC 率 16:4 时G 80006400 × 20/16P 1 - 0.85 × 0.85 1 - 0.7225 0.2775S 1 - (SUM of i0 - 4 for binomial(P 0.2775, N 20, failures i)) 0.689414B (1 - 0.689) ^ (8000 / 20) 10^-203即恢复率严重不足时区块传播几乎必然失败。FEC 率 16:16 时G 12800S 1 - (SUM of i0 - 16 for binomial(P 0.2775, N 32, failures i)) 0.002132B (1 - 0.002132) ^ (12800 / 32) 0.42583成功率约 42.6%仍不可接受。FEC 率 32:32 时G 12800S 1 - (SUM of i0 - 32 for binomial(P 0.2775, N 64, failures i)) 0.000048B (1 - 0.000048) ^ (12800 / 64) 0.99045成功率提升到 99% 以上。结论是在 15% 全网丢包、多层重传的假设下需要接近 1:1 的 data/coding 比例才能让绝大多数 shred 组一次传播即可重建FEC 比例过低时失败组只能退回到 repair 路径。与仓库实现的对应关系从源码结构看文档中的shred group对应代码中的 erasure setErasureSetIdslot fec_set_index标识一个纠删码集合见 ledger/src/shred.rscoding shred 携带num_coding_shreds与position字段以便接收端重建每个 slot 的 data 与 coding shred 上限由 MAX_DATA_SHREDS_PER_SLOT / MAX_CODE_SHREDS_PER_SLOT 界定。文档中若 shred 组重建失败则依赖 repair 修复区块的兜底路径正对应 ledger 层的 repair/请求-响应补全机制——Turbine 负责尽力快速广播repair 负责最终一致补齐FEC 的选型本质是在广播带宽放大倍数与依赖 repair 的频率之间做权衡。五、要点回顾确定性共识于树形全网节点用 (leader, slot, index, shred_type) 派生 seed对 stake 加权洗牌后的节点列表做相同索引运算无需通信即可各自推出同一棵 turbine 树且每个 shred 轮换 root抗针对固定节点的攻击每节点常数出度任何节点最多只向下一层DATA_PLANE_FANOUT当前 200个节点转发get_retransmit_peers的邻域步进公式保证了父子关系全网互逆、互不重叠FEC 决定广播可靠性由于重传使丢包复利FEC 率必须按二项分布模型针对全网丢包率和组大小求解文档算例表明 15% 丢包假设下16:4 与 16:16 的 FEC 率不足以保证区块一次传播成功32:32 可将区块成功率推至约 99%可追溯的实现入口树构建与层边界逻辑在 turbine/src/cluster_nodes.rs重传主循环在 turbine/src/retransmit_stage.rs种子派生在 ledger/src/shred.rs广播端在 turbine/src/broadcast_stage/ 下树形正确性由同文件tests模块中的 round-trip 与小型手工树测试守护。【免费下载链接】solanaWeb-Scale Blockchain for fast, secure, scalable, decentralized apps and marketplaces.项目地址: https://gitcode.com/GitHub_Trending/so/solana创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考