字符串哈希：Rabin-Karp、滚动哈希与内容定义分块
滚动哈希的保证来自输入确定后才随机选的素数、基或不可约多项式。本文按 Karp-Rabin 原文推导碰撞界，实测 Thue-Morse 串攻破 2^64 自然溢出，并用 LBFS、FastCDC、restic、borg 的源码与模拟说明内容定义分块。
rsync 标签归档
共 3 篇文章 · 返回首页
【rsync 原理】差异同步算法：滚动校验与两级匹配
源端看不到目标端文件，rsync 凭什么只传改动的几 KB？从 Tridgell 的 rsync 算法出发，用 rsync 3.4.4 源码钉住弱滚动校验的 O(1) 更新、弱+强两级匹配、sqrt 块大小与签名长度随文件增长的权衡，讲清差异是怎么在不传整文件的前提下被算出来的。
【rsync 原理】协议、进程模型与实测
rsync 的差异算法落到真实工具里，是 generator/sender/receiver 三个进程在一条管线上跑。本文用 rsync 3.4.4 源码与 wire 行为讲清三角色分工、文件列表与逐文件生命周期、token 字节流格式、强校验协商与版本边界，并在本机内核 6.6 上实测：100 MiB 文件改 1 字节，delta 走约 120 KB，whole-file 走整 100 MiB。