P2P 与分布式存储 / 系统课时

用 Bitfield 与 Have 同步分块

用 Bitfield 与 Have 同步分块

建立 BitTorrent Peer 连接后,客户端需要知道远端已经拥有哪些 Piece,才能决定向谁请求数据。本课通过真实报文格式、位图解析代码和分块交换案例,完成 Bitfield 与 Have 的编码、解析和可请求分块判断。

学习目标

  • 识别 Bitfield、Have 消息的长度、消息 ID 和有效载荷格式。
  • 正确解析 MSB-first 位图、Piece 索引及末尾填充位。
  • 根据本地与远端分块状态计算候选请求集合,并处理状态更新。

两种消息分别声明什么

BitTorrent v1 Peer Wire Protocol 使用 Bitfield 声明一组已有 Piece,使用 Have 通知某个 Piece 已经完整可用。两者都以 Piece 为单位,而不是以单次请求的 Block 为单位。

消息 Message ID 有效载荷 典型用途
Bitfield 5 ceil(pieceCount / 8) 字节 连接建立后声明已有分块集合
Have 4 4 字节无符号大端整数 通知新增的完整 Piece

例如资源有 10 个 Piece,节点 A 拥有 P0、P2、P7,初始位图可编码为 10100001 00000000。随后 A 完成 P9,就发送 Have(9),不需要重新发送整张 Bitfield。

Bitfield 在协议握手之后作为首条消息发送;没有可用 Piece 的节点可以不发送 Bitfield。传统协议不允许在同一连接中任意重复发送 Bitfield。Have 则可以在连接存续期间多次发送,远端应按幂等方式更新状态。

解析报文的字节布局

普通 Peer 消息采用 4 字节大端长度前缀,后接 1 字节消息 ID 和有效载荷。长度字段包含消息 ID 与有效载荷,但不包含长度字段自身。长度为 0 表示 Keep-alive,此时没有消息 ID。

假设资源共有 10 个 Piece,远端拥有 P0、P2、P7,完整 Bitfield 报文的十六进制字节为:

text
00 00 00 03 05 A1 00
|-- length --| ID |payload|
length = 3
ID = 5
bitfield = A1 00

这里的 A1 等于二进制 10100001,最高位对应 P0,最低位对应 P7。第二字节的最高位对应 P8,次高位对应 P9,其余 6 位必须为零。

Have(9) 则编码为:

text
00 00 00 05 04 00 00 00 09
length = 5
ID = 4
piece index = 9

注意 Piece 索引从 0 开始。对于 10 个 Piece,有效索引是 0~9;收到 Have(10) 应视为无效消息,而不是扩展本地位图。

Bitfield 位序与 Have 报文字节结构

用 Python 解析并更新分块状态

下面的完整示例使用 Python 3.10+ 标准库,先解析 Bitfield,再接收 Have 更新,最后计算远端有而本地没有的 Piece。为避免混淆,示例直接使用完整的 Peer 消息字节串。

python
import struct

PIECE_COUNT = 10


def decode_message(packet: bytes):
    if len(packet) < 4:
        raise ValueError("incomplete length prefix")
    length = struct.unpack(">I", packet[:4])[0]
    if len(packet) != length + 4:
        raise ValueError("message length mismatch")
    if length == 0:
        return 0, b""
    return packet[4], packet[5:]


def parse_bitfield(payload: bytes, piece_count: int) -> set[int]:
    expected = (piece_count + 7) // 8
    if len(payload) != expected:
        raise ValueError("invalid bitfield size")
    # 最后一字节未使用的低位必须全部为零。
    padding = expected * 8 - piece_count
    if padding and (payload[-1] & ((1 << padding) - 1)):
        raise ValueError("nonzero padding bits")
    return {
        i for i in range(piece_count)
        if payload[i // 8] & (0x80 >> (i % 8))
    }


def parse_have(payload: bytes, piece_count: int) -> int:
    if len(payload) != 4:
        raise ValueError("invalid have size")
    index = struct.unpack(">I", payload)[0]
    if index >= piece_count:
        raise ValueError("piece index out of range")
    return index


def main():
    remote = set()
    local = {0, 7}
    bitfield_packet = bytes.fromhex("0000000305a100")
    have_packet = bytes.fromhex("000000050400000009")

    message_id, payload = decode_message(bitfield_packet)
    if message_id != 5:
        raise ValueError("expected bitfield")
    remote = parse_bitfield(payload, PIECE_COUNT)
    print("initial remote:", sorted(remote))

    message_id, payload = decode_message(have_packet)
    if message_id != 4:
        raise ValueError("expected have")
    remote.add(parse_have(payload, PIECE_COUNT))
    print("updated remote:", sorted(remote))
    print("candidates:", sorted(remote - local))


if __name__ == "__main__":
    main()

预期输出:

text
initial remote: [0, 2, 7]
updated remote: [0, 2, 7, 9]
candidates: [2, 9]

这里的 remote - local 是集合差集:远端拥有且本地尚未拥有。它只表示候选 Piece,不表示可以立即发送 Request。实际客户端还需要检查 Interested/Choke 状态、Piece 是否已经在下载、请求窗口和 Block 调度策略。

将位图状态接入请求调度

在真实下载器中,Bitfield 和 Have 负责维护每条 Peer 连接的可用性视图。以本地已有 P0、P7,Peer A 拥有 P0、P2、P7、P9,Peer B 拥有 P2、P3、P9 为例:

Piece 本地 Peer A Peer B 调度判断
P0 有 有 无 不请求
P2 无 有 有 两个来源可选
P3 无 无 有 优先考虑稀缺 Piece
P7 有 有 无 不请求
P9 无 有 有 两个来源可选

如果使用 Rarest First 策略,在当前已知的两个 Peer 中,P3 只有一个来源,而 P2、P9 各有两个来源,因此 P3 的优先级更高。但这只是局部可用性统计,仍要结合 Peer 是否 Unchoked、网络吞吐和已经发出的请求判断。

Bitfield 与 Have 驱动的分块可用性更新及请求调度

一次正确的调度顺序可以是:

  1. 解析握手之后的 Bitfield,初始化该 Peer 的可用 Piece 集合。
  2. 收到 Have 时,将合法 Piece 索引加入对应 Peer 的集合,并更新可用来源计数;重复 Have 不重复计数。
  3. 从本地缺失集合中筛选远端拥有的 Piece,排除已完成和不允许重复请求的任务。
  4. 根据稀缺度、请求窗口与连接状态选择 Piece,再拆分为 Block 请求。
  5. 收到 Block 后按 Piece 完成校验;只有整个 Piece 通过哈希验证,才将其标记为本地拥有并向其他 Peer 广播 Have。

处理异常报文与协议边界

实际接收 TCP 字节流时,一次 recv() 不保证取得一条完整消息,也可能同时取得多条消息。必须先缓存至少 4 字节长度前缀,再等待指定长度的消息体,不能把一次网络读取直接当成一条 Bitfield。

以下情况应在解析层明确处理:

输入情况 正确处理
10 个 Piece 却收到 1 字节 Bitfield 拒绝,长度应为 2 字节
Bitfield 为 A1 01 拒绝,末尾填充位非零
Have 载荷只有 3 字节 拒绝,必须恰好 4 字节
Have 索引为 10 拒绝,超出有效范围
重复收到 Have(9) 保持已有状态,不重复增加来源数
收到长度为 0 的 Keep-alive 识别为保活消息,不读取消息 ID

还需要区分基础协议和扩展行为:传统 Bitfield 只在握手后发送一次;采用 Fast Extension 的连接可能使用 Have All、Have None 等额外消息,必须先确认扩展协商结果再解析。不要将未知消息 ID 直接解释成 Bitfield。

最终验收可以使用本课示例的三个断言:初始远端集合为 {0,2,7},收到 Have(9) 后变成 {0,2,7,9},本地已有 {0,7} 时候选集合为 {2,9}。只要这三个结果和报文长度、位序校验同时正确,就具备了接入 Piece 请求调度器的基础。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 Bitfield 与 Have 同步分块

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通