工作中接触到了itch.io开源的wharf，所以简单了解一下实现细节和原理。幸运的是itch.io提供了相关的文档。

开篇提到Wharf 是一个支持增量上传和下载的协议，用于保持软件的最新状态。它是

• 一个基于 rsync 的差分与补丁算法
• 一个基于 protobuf 的补丁与签名文件开放格式
• 一个 Go 语言的参考实现
• 包含多种命令的cli工具

术语

container

简单理解就是文件目录元信息，代表某个时刻/版本的目录结构信息。所以我们通过对比两个container知道目录结构的变化。

diff

对两个container里的文件内容进行比较的结果。包含从旧版本升级到新版本需要做出的操作指令

patch

补丁包含进行升级所需的全部信息：旧container、新container，以及它们之间的 diff。.pwr 文件（Wharf patch file）就是这个 Patch

signature

容器中文件数据按块（64KB)划分后每个块的哈希信息

/dev/null

空容器，与/dev/null做diff，用来表示初始版本

Archive

归档是以单个压缩文件形式存储的容器。Wharf 允许对压缩包进行 diff（例如两个 .zip 构建产物）；但代价是必须在内存中解压读取块内容；

Block

块是文件中固定大小的一段字节序列

Wharf 的 diff 算法在块级上比较新旧文件，每个块都有一个弱哈希和强哈希，最后一个块往往是短块（不满块大小），文件的变化会被精确到块级别，从而最大限度地复用旧数据

算法

整个流程涉及两个算法

• diff算法计算前后两个container的差异
• apply算法描述如何从旧版本container升级到新版本

diff算法流程

• 生成旧容器签名 (signature)
  • 将旧容器（old container）中每个文件按固定块大小（默认 64 KB）切分；
  • 为每个块计算：
    • 弱哈希（weak hash） — 通常是 32 位滚动哈希，用于快速匹配；
    • 强哈希（strong hash） — 通常是 256 位（如 Blake2b），用于确认匹配；
  • 同时记录文件路径、类型（文件/目录/符号链接）等元信息，组成完整签名表。
• 扫描新容器数据
  • 新容器（new container）不直接按块对齐计算，而是使用滑动窗口（窗口大小 = 块大小）；
  • 每次滑动 1 字节并计算当前窗口的弱哈希；
  • 如果弱哈希与旧容器签名表中的某块匹配，则进一步计算当前窗口的强哈希；
  • 若强哈希也一致，则认定这是旧容器中的一段已存在数据；
  • 此时生成一个 BLOCK_RANGE 操作，表示在应用补丁时可直接从旧文件复制该区间；
  • 如果连续的 BLOCK_RANGE 来自同一旧文件且块索引连续，则会被合并为一个更大的区间，减少补丁体积。
• 处理未匹配数据
  • 当滑动窗口扫描到一段在旧容器中未找到匹配的区域时，将其作为“新数据”；
  • 以 DATA 操作的形式写入补丁；
  • 每个 DATA 操作包含一个长度字段 + 数据本体，单次写入最大为 4 MB。
• 多文件匹配优先级
  • 如果多个旧文件的哈希与当前窗口匹配，优先选择路径相同的旧文件；
  • 这有助于识别重命名（rename），并生成更紧凑、更稳定的补丁。

apply补丁流程

了解diff步骤以后，apply其实就很明显了

• 扫描新container，创建缺失的文件和目录
• 读取命令并完成数据写入
  • DATA：补丁里自带原始字节，直接写到新文件当前偏移位置
  • BLOCK_RANGE：从旧容器拷贝数据，命令会携带目标文件索引，偏移量以及读取长度等信息
• 删除写入阶段产生的临时文件

到此就了解wharf的功能和细节了。下面挑选一些具体的细节:

weak hash实现

生成diff时每移动1个字节就需要计算一次hash，因此weak hash的计算一定要足够快。下面就是wharf中的实现，可以看到这个就是一个O(n)的算法，计算步骤也比较简单。

a就是简单求和，但这样的求和计算对位置无感，类似”abc”和”acb”的计算结果是一样的。所以又引入另一个b，使得索引位置也对计算产生影响，并且越靠前权重越高。

_M = 1 << 16，a % _M 和 b % _M 分别取出了 a、b 的低 16 位；再乘上 _M 相当于把 b 的低 16 位左移 16 位，两者拼接后就组成了最终的 32 位弱哈希值。

const _M = 1 << 16

func βhash(block []byte) (β uint32, β1 uint32, β2 uint32) {    
	var a, b uint32    
	for i, val := range block {
	        a += uint32(val)
	        b += (uint32(len(block)-1) - uint32(i) + 1) * uint32(val)    
	}
	β = (a % _M) + (_M * (b % _M))    
	β1 = a % _M    
	β2 = b % _M    
	return
}