P2P 与分布式存储 / 系统课时
最稀缺优先怎样提高块覆盖率
最稀缺优先怎样提高块覆盖率
当多个 Peer 拥有不同的分块时,下载端如果只选择最快节点上的常见分块,可能导致少数稀缺分块长期无人复制。本课通过一个可运行的六节点模拟,统计分块副本数、实现 Rarest First 调度,并验证它怎样提高 Swarm 的分块覆盖能力。
学习目标
- 根据多个 Peer 的 Bitfield 计算每个 Piece 的可用副本数。
- 实现最稀缺优先选择,并正确处理并列、未完成和不可请求的分块。
- 使用具体算例区分分块覆盖率、副本冗余度与下载完成率。
为什么优先下载稀缺分块
BitTorrent 将资源拆成编号从 0 开始的 Piece。Peer 通过 Bitfield 或 Have 消息告知其他节点自己已经拥有并可提供哪些完整分块。
假设一个 Swarm 中有六个节点,资源共有六个 Piece,初始持有情况如下。A 是正在下载的节点,其余五个节点可以提供数据。
| 节点 | P0 | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|---|
| A(本地) | ✓ | — | — | — | — | — |
| B | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| C | ✓ | ✓ | ✓ | — | — | — |
| D | ✓ | ✓ | — | — | — | — |
| E | ✓ | — | — | — | — | — |
| F | ✓ | — | — | — | — | — |
| 远端副本数 | 5 | 3 | 2 | 1 | 1 | 1 |
P3、P4、P5 只有 B 持有。如果 B 在其他节点复制这些分块之前离线,它们就会暂时无法从剩余在线节点获取。相反,P1 已有三个远端副本,短时间内丢失全部副本的风险通常更低。
Rarest First 的选择规则是:在当前可请求、尚未拥有的 Piece 中,优先选择已知持有者数量最少的 Piece。 这里的稀缺度是本地观察到的在线 Peer 副本数,不是全网真实副本数。

统计副本数并决定请求对象
设远端节点集合为 ,节点 的持有集合为 ,则 Piece 的已知远端副本数为:
其中指示函数在节点持有该分块时取 1,否则取 0。调度时必须先排除本地已经拥有的 Piece,再排除当前没有可用持有者的 Piece。
实际请求还受到 Peer 的 Choke 状态、未完成请求、连接容量和 Piece 校验状态影响。一个 Piece 的副本数为 1,不代表当前一定能从对应节点下载。
可采用以下决策顺序:
- 接收并维护各 Peer 的 Bitfield 与 Have 信息;连接断开时移除其持有记录。
- 统计每个 Piece 的已知远端副本数,过滤本地已验证完成的 Piece。
- 在当前允许请求且具有可用持有者的候选 Piece 中,选择副本数最小者。
- 如果多个 Piece 并列最稀缺,随机选择,避免所有下载端始终按固定编号竞争同一 Piece。
- 将选中的 Piece 拆成 Block 请求,接收数据后验证完整 Piece 的哈希,再将其标记为已完成并发送 Have。
用 Python 模拟最稀缺优先
下面使用 Python 3.10 或更新版本的标准库,复现上表的节点分布。示例只演示 Piece 级选择,不实现真实网络连接、Choke 管理或 Block 下载。
from collections import Counter
from random import Random
TOTAL_PIECES = 6
local_have = {0}
peers = {
'B': {0, 1, 2, 3, 4, 5},
'C': {0, 1, 2},
'D': {0, 1},
'E': {0},
'F': {0},
}
# 每个远端 Peer 对同一 Piece 最多贡献一个副本。
availability = Counter(
piece for pieces in peers.values() for piece in pieces
)
candidates = [
i for i in range(TOTAL_PIECES)
if i not in local_have and availability[i] > 0
]
# 先按最小副本数筛选,再对并列候选随机选择。
minimum = min(availability[i] for i in candidates)
rarest = [i for i in candidates if availability[i] == minimum]
selected = Random(7).choice(rarest)
providers = sorted(
name for name, pieces in peers.items() if selected in pieces
)
print('副本数:', [availability[i] for i in range(TOTAL_PIECES)])
print('最稀缺候选:', rarest)
print('选中分块:', selected)
print('可提供节点:', providers)预期输出(Python 3.10 至 3.13 的该随机选择结果):
副本数: [5, 3, 2, 1, 1, 1]
最稀缺候选: [3, 4, 5]
选中分块: 4
可提供节点: ['B']此时 P3、P4、P5 同为最稀缺分块,随机选择 P4,随后可以向 B 请求它的 Block。实际实现应从当前未被 Choke、允许请求的持有者中选取,并根据请求队列容量控制并发。
示例使用固定随机种子以便复现。生产客户端不应依赖某个固定种子决定所有下载任务的并列顺序。
稀缺分块复制后覆盖率怎样变化
假设 B 是唯一拥有 P3、P4、P5 的节点,A 首先从 B 下载并成功校验 P4,然后向其他 Peer 宣告 Have。
如果随后 B 离线,比较 A 是否提前复制 P4 的两种情况:
| 指标 | A 先下载常见 P1 | A 先下载稀缺 P4 |
|---|---|---|
| B 离线后仍有副本的 Piece | P0、P1、P2 | P0、P1、P2、P4 |
| 可用 Piece 数 | 3 | 4 |
| Swarm 分块覆盖率 | 50.0% | 66.7% |
| 暂时不可用的 Piece | P3、P4、P5 | P3、P5 |
这里将覆盖率定义为:
这个算例中,提前复制稀缺 P4,使 B 离线后的覆盖率提高了约 16.7 个百分点。但如果 B 始终在线,两种选择都不会立即改变当前 100% 的覆盖率;变化的是稀缺分块的副本冗余度。

需要注意,覆盖率并不等于下载完成率。即使 Swarm 中所有 Piece 都至少有一个副本,也不代表任何单个节点已经完成整个资源。
真实客户端还需要处理哪些边界
最稀缺优先适合作为常规 Piece 选择策略,但不能机械地对所有下载阶段使用同一规则。
| 情况 | 推荐处理 | 原因 |
|---|---|---|
| 新加入 Swarm,尚无完整 Piece | 可以先随机选择一个可下载 Piece | 尽快获得可上传的完整 Piece |
| 多个 Piece 稀缺度相同 | 在并列候选中随机选择 | 降低同步争抢 |
| 唯一持有者当前 Choke 本地节点 | 暂时从可请求集合排除 | 避免发出无法正常完成的请求 |
| 某 Piece 已有未完成请求 | 跟踪请求状态并避免无意义重复 | 控制带宽与重复下载 |
| 下载接近完成且部分请求长期未返回 | 在合适条件下进入 Endgame 模式 | 可向多个 Peer 请求尚未收到的 Block,并取消多余请求 |
另一个常见错误是直接把所有 Peer 的 Bitfield 永久累加。节点离线后仍保留它的副本计数,会把已经消失的分块误判为充足。因此应维护每个连接独立的持有集合,在收到 Have、Bitfield 或断开连接事件时更新统计。
还应避免将收到的数据立即视为有效副本。只有整个 Piece 的数据通过种子元数据规定的完整性校验后,才能将它计入本地已完成集合并向其他节点宣告 Have。
验证调度策略是否有效
可以将模拟扩展为多轮实验:每轮随机移除一个在线节点,分别比较随机选块与 Rarest First 在同样初始条件下的结果。建议至少记录以下三个指标。
- 覆盖率:仍有在线完整副本的 Piece 占全部 Piece 的比例。
- 最小副本数:所有 Piece 在在线节点中的副本数最小值;为 0 表示至少一个 Piece 当前不可用。
- 请求重复率:重复下载且未带来有效新增数据的字节数,占总接收字节数的比例。
验证时固定节点持有矩阵、随机种子、总下载预算和离线时刻,避免把不同网络条件误认为调度算法的收益。还应分别测试唯一持有者离线、Peer 持有信息变化,以及多个稀缺 Piece 并列的情况。
Rarest First 无法创造已经不存在的分块,也不能保证所有网络条件下下载最快。它的实际价值是在仍能获取稀缺 Piece 时优先扩散这些数据,减少 Swarm 对少数持有者的依赖。