★ FEATURED ARTICLE 简谈差分技术原理很多人在做数据同步的时候第一反应就是把整个文件重新传一遍。比如笔记本上几百MB的日志、服务器之间同步几十GB的数据库备份、给远端的终端设备推送一个几十MB的升级包——看起来最直接的做法就是全量拷贝。但你多传几次就会发现网络带宽、存储空间、传输时长全都耗在了那些根本没有变化的数据上。差分的核心思想就一句话不传没变的部分只把变化的部分想办法表达出来。这篇文章从应用视角来聊差分技术的原理。内容包括差分和全量的本质差异、经典同步算法是怎么设计出来的、软件差分和文件级差分的区别、实际工程里怎么选参数和避坑以及差分在系统升级、云端同步、日志回放几个场景里的真实用法。适合做后端同步、运维工具、客户端升级模块的开发者也适合刚接触分布式数据同步的同学当作入门科普来看。1. 差分的本质把变化压缩成一种描述1.1 全量传输到底浪费了什么全量传输的思路非常朴素源端把整个文件发过去目标端收到之后覆盖旧版本。这种方式的优点是实现简单、状态清晰但代价也极其高昂。假设一个文件大小为 100MB每次改动只有中间 1MB一天改 50 次。全量传输一天的流量是 5GB而真实需要表达的数据只有 50MB。更麻烦的是如果发送端只是做了几个字节的改动文件的整体内容几乎没变但全量传输仍然会把 99% 的重复内容原封不动地送过去。差分技术要解决的核心问题就是一句话怎么用尽量少的通信量描述清楚旧文件应该怎么变成新文件。1.2 差分的两种基本形态差分技术在实际落地中分为两种形态很多人会把它们混为一谈。第一种是传输时差分。这种思路认为源端和目标端各自保存一个原始版本只要知道旧版本是什么样的就能只发送补丁。这个补丁通常描述为在旧文件的某个偏移位置用新内容替换多少字节。这种方式的典型代表就是二进制补丁工具以及系统升级场景中的增量更新包。第二种是存储时差分。这种思路把数据的历史版本以差异链的形式保存在存储系统里每个版本只记录它和前一个版本的差异而不是完整保存每个版本。数据库的预写日志、对象存储的版本快照、备份系统的增量备份都是这种模式的体现。理解这两种形态很重要因为很多工程问题并不是算法不够好而是一开始就把场景搞混了——拿存储时差分的思路去解决传输时差分的问题结果就是效率奇低。1.3 差分不是压缩但两者互补有个常见的误区认为差分和压缩是一样的。实际上两者解决的问题完全不同。压缩是在单个数据块内部消除冗余差分是在两个版本之间消除冗余。打个比方压缩是在一幅画的内部把重复的小色块归纳成一条指令差分是只记录这幅画相比上一幅画哪几块区域颜色变了。如果先做差分再做压缩效果通常更好。因为差分处理完的补丁内容往往更规整压缩器能发挥出比直接压缩全量文件高得多的压缩率。实践里很多增量升级包流程都是先算差分再对生成的差异块做二次压缩。2. 从rsync聊起滚动校验和弱校验的配合逻辑2.1 固定分块的朴素直觉差分最朴素的做法是固定分块。发送方把新文件切成固定大小的块接收方把旧文件也切成同样大小的块然后逐一对比每一块的哈希值相同就跳过不同就传输。这个方案在块对齐的情况下效果不错但它有一个致命的问题如果旧版本在中间插入了一个字节那么从插入点往后所有的块都会错位。哪怕实际只改了一两个字节固定块的对比结果也会是从某个位置起后面全变了差分效率直接归零。很多工程里遇到改动一个字节却同步了半个文件的现象根因就在这。所以在设计差分算法时能不能在数据流中重新定位变化区域是衡量算法优劣的分水岭。2.2 滚动校验让窗口动起来rsync算法解决这个问题的思路非常精彩接收方先按固定块大小把旧文件切成若干块然后计算每一块的校验值发给发送方。发送方拿到这些校验值后并不把新文件也切成固定块而是在新文件上滑动一个同样大小的窗口每滑动一个字节就计算一次当前窗口的校验值。这样做的好处是即使中间插入了一个字节窗口足够小的话后续窗口只会依次错位一个字节但很快就能在某个位置重新匹配上旧文件的某个块。匹配上之后发送方就知道这个位置开始的内容旧端已经有了于是跳过这些不需要传输的内容。这里的关键在于如果每滑动一个字节都要重新计算窗口内全部数据的哈希值那计算量就太大了。滚动校验的精髓就是把哈希计算变成增量式的假设窗口大小是N本次窗口的校验值可以基于上一个窗口的校验值、移出的那个字节、以及新进入的字节直接推导出来而不是重新读一遍N个字节来做哈希。2.3 弱校验与强校验的分工滚动校验有一个问题如果只用一种哈希很容易碰撞。尤其当数据量很大的时候两个不同窗口算出同样的哈希值不用做额外判断就跳过会导致数据错乱。rsync的思路是两次校验。第一次用滚动校验通常是一种32位的滚动校验函数它计算速度快适合在滑动过程中频繁计算一旦滚动校验值匹配上再用一个强校验比如128位或更强的哈希去确认一下防止碰撞。这样分工的理由很实际强哈希计算成本高而滚动过程可能要对每个字节位置都计算一次如果用强哈希做滑动匹配CPU扛不住。先用弱校验粗筛一遍等到疑似匹配的位置才用强校验复核计算量就能大幅下降。我第一次实测这个算法对比全量传输时印象最深的是同步一个内部项目的大文件只改了一行配置差分后实际传输的数据量不到整个文件的百分之一。但要注意这里说的是传输时差分逻辑rsync算法本身还需要发送方临时保存旧文件的校验清单所以它的内存占用和文件块的数量成正比。3. 从块匹配到字节级差异软件差分的选择3.1 块级别差分适合什么场景文件块级别的差分在rsync这类同步工具里非常成熟但它并不适合所有场景。块级别差分的一个特点是它不能精确到修改了几个字节这种细粒度而是以块为单位来决定是否传输。如果修改恰好跨越了块边界那至少有两个块需要重新传输。对同步文件来说这个粒度通常是可接受的因为网络的通信成本远远高于多传几个块。但对软件升级包、固件升级这类场景来说块级别差分带来的补丁体积就显得不够小了。系统升级包往往只有几十到几百MB如果差异集跨越多个块补丁体积可能膨胀到几十MB甚至更大用户下载升级包的流量成本就上来了。3.2 字节级差分的核心思路编辑脚本字节级差分的典型代表是传统文本比较工具里的编辑脚本算法。它的目标是把从旧文件到新文件的变换表示成一个最小的编辑操作序列比如从某个位置删除多少字符在某个位置插入多少内容修改某个子串为另一段内容。这种思路用的底层算法是动态规划。以最常见的编辑距离算法为例定义三种基础编辑操作——插入、删除、替换然后定义一个二维状态表表的每一格表示从字符串A的前i个字符变换到字符串B的前j个字符所需的最小编辑次数。通过递推关系式可以求出最小编辑路径也就能回溯出具体的差异指令。这类算法的优点在于能精确到字节缺点在于时间和空间复杂度都接近O(n*m)文件一大就非常吃力。所以在实际工程中纯粹的字节级动态规划很少直接用于大文件而是先做分块定位缩小范围之后在小片段内部再做精细对比。3.3 Alpha升级包是如何被设计出来的很多产品做增量升级时工程设计上会采用一个分层的策略第一步快速定位新旧版本之间的差异区域。这一步可以用滚动校验也可以用更工程化的分块哈希对比。目的不是生成精确补丁而是先圈出大概哪些区域变了。第二步对差异区域做进一步的精细匹配提取公共部分和差异部分。第三步对差异部分做压缩生成最终的补丁描述文件里面记录着一系列跳过多少字节、然后替换多少字节的操作指令。安装补丁时设备读取补丁描述按指令将旧文件的部分片段拷贝复制并在指定位置插入补丁中的数据最终拼装出新版本的完整文件。这个过程中补丁中剩下的只有真正的差异数据所以体积能做到非常小。我参与过的一个老项目的升级包原来走全量下载大概每个版本要传200MB左右。后来改为差分生成增量包在只改配置类文件的情况下增量包体积能压缩到几MB这对弱网环境下的升级体验提升非常明显。4. 工程选型块大小、内存占用与弱网断点4.1 块大小怎么选在实际工程中差分同步的第一个参数就是块大小。块大小选得太大匹配的粒度粗浪费的传输量增加选得太小块数量膨胀校验值清单的内存占用和传输开销也随之上涨。实践经验里这个参数没有绝对标准。对一个100MB的文件如果网络状况较好用4KB到8KB的块比较常见如果文件很大且在意计算开销用256KB甚至1MB的块也比较常见。我们做过一个内部测试块大小从4KB增加到64KB内存占用下降了一个数量级但差异传输的体积上升了大约百分之三。绝大多数场景下这个交换是划算的。有一个基本公式可以帮助判断校验清单的内存大概等于(文件大小/块大小)×单个校验值字节数。如果文件1GB、块大小1MB、每个校验值16字节那么清单内存大约是16KB可以忽略但如果文件1GB、块大小4KB、每个校验值128字节清单内存会飙升到32MB以上在一些受限设备上就很吃紧了。4.2 弱网下的断点续传设计差分的另一个应用价值被很多团队低估了就是它在弱网条件下能天然地配合断点续传。全量传输在弱网断开后往往需要从头再来差分传输因为把文件切成块了实际网络层可以按块粒度进行完成确认。做法不复杂发送方按块传输新文件的差异块接收方每收到一块就把它写入临时文件并记录确认状态网络断开后重新连接只需要查询哪些块还没收到继续从断点传即可。这里的核心是每个块必须是独立可验证的也就是说每个块都要带自己的校验值这样接收方才能确认这个块是否完整接收到。这个设计和简单断点续传的区别在于简单续传是按字节偏移记录位置如果文件内容发生变化续传位置可能就错乱了而按块校验的续传天然免疫这种错乱因为在块粒度上已经做了强校验。4.3 海量小文件的同步要换个思路上面聊的都是单文件差分。如果遇到的是几十万个图片文件、日志文件这样的目录同步直接对每个文件做差分往往会慢得离谱。这时候有一个行之有效的方法先把所有小文件打包成一个大的归档文件在归档层做一次差分然后再把差异解包回目录。这个思路的优雅之处在于它把海量文件之间的相关性转化成了一个大文件内部的连续性。比如一个目录里有一万个文件只有一个改了归档层差分能自动跳过其他9999个文件的数据。而如果老老实实逐文件对比每个文件都要做一次差分开销和校验通信开销反而大得多。要注意的是打包本身也不是无代价的。归档方案的缺点是每次同步都需要在源端重新打包整个目录尽管差分后的传输量很小但打包的CPU和临时磁盘开销还在。所以我给团队的建议是文件数量少、单文件大就走逐文件差分文件数量多、单文件小优先考虑归档层差分。5. 差分在系统升级、云端同步和日志回放里的表现5.1 系统升级中的增量包机制现在几乎所有的手机系统和桌面软件升级都支持增量差分包。它的工程流程通常是这样首先开发者把旧版本和新版本从仓库取出做一次字节级的差异对比生成一个补丁文件。这个补丁文件里记录了所有需要修改的位置和对应的数据。然后设备端在升级前检查本地版本号确保本地版本和生成补丁时用的旧版本一致。这里有一个非常关键的工程细节如果设备在补丁生成之后又收到了任何修改哪怕是临时缓存文件的修改安装补丁时校验不过升级就会失败。所以量产系统的差分升级包通常要求设备处于完全还原状态或者特定版本否则就要回退到全量升级包。这一点在做终端设备推送时会让人头疼也是为什么有些系统即便支持差分升级仍然会在检测到版本混乱时自动选择全量包的原因。我们团队在早些时候处理过一批设备升级失败的问题排查下来就是设备上的应用缓存文件参差不齐导致补丁校验不通过。后来在设备端加了升级前置校验逻辑如果校验不一致自动切换到全量升级通道整个升级失败率一下就降下来了。5.2 同步盘里的增量上传逻辑云同步盘能够做到本地改了一个字节云端只传一个字节的效果依赖的也是差分但这里的工程选型会更激进。因为客户端并不知道用户改了哪些字节所以它必须在本地扫描文件时比对历史版本状态。一种常见的做法是客户端给每个文件维护一份上次上传成功时的内容校验快照本地文件被修改后客户端把新版本和快照做差分只上传差异部分。云端收到差异后把差异应用到它的旧版本上生成新版本。这个场景和上一节讲的rsync场景有一个重要区别rsync是接收方先发送校验值发送方再做匹配而同步盘场景里校验快照是发送方自己保存的所以它不需要接收方先发清单传输效率理论上更高。代价是每个文件都要多维护一份快照快照的存储开销和生成快照的时间都是成本。5.3 数据库日志里隐含的差分思路数据库的预写日志看起来和差分没什么关系但它的核心机制本质上就是差分它记载的不是数据库每个键值的新值而是对某个页面的一次修改操作。当数据库崩溃后系统只需要重放这些修改操作就能把数据库恢复到最终状态。这个思路对做存储系统的人特别有启发与其每次都把完整数据写到磁盘不如把变化抽象成一条有序的操作记录。补丁文件中描述的是旧数据如何变换成新数据日志中描述的是旧状态如何执行操作变成新状态两者都是在用最小的信息量表达变化。实际写存储系统时我把这个思路迁移到了版本化配置管理上每个配置版本只保存和前一个版本的差异回滚时按差异链反向操作。这样做的收益是历史版本占用的空间从N倍全量大小降到了一份全量加若干差异记录而且因为每个差异都很小加载特定历史版本的速度也能接受。5.4 差分方案对比小结不同场景对差分技术的诉求差异很大列个表方便对照场景差分粒度核心诉求典型代价文件同步rsync块级传输量小、计算快需要旧文件校验清单适配性强系统升级OTA字节级补丁体积最小化版本一致性要求严格校验失败需回退云盘增量上传块级/文件级减少上传流量需维护本地校验快照快照有存储成本数据库日志回放操作级可重放、可恢复日志本身需要定期归档清理版本化配置存储字节级/操作级历史版本空间可控版本多了之后差异链变长需定期合并我在实际做选择的时候一般先问三个问题本地有没有旧版本可供参考网络带宽是不是瓶颈设备端的计算能力够不够滚动校验这三个问题的答案基本就能框定技术路线。6. 实操中容易踩的几个坑差分技术原理看起来简单落地时却有一堆细节问题。这里专门列几个团队里反复出现过的坑都踩过也修复过。第一个坑是直接对被压缩过的文件做差分。很多文件格式本身就是压缩格式比如图片、视频、压缩文档。这些文件的字节流变化非常敏感经常是内容只改了一点压缩后的字节流却完全重排。这种情况下差分算法不但不能缩小传输量反而可能比全量传输还要大。这是因为压缩算法已经把原内容的冗余度降得很低差分根本找不到公共子串。所以对压缩格式文件做差分关键是找上层语义层做差异而不是对压缩字节流做差异。第二个坑是滚动校验的参数没有调好导致弱校验碰撞过多。在数据量极大的场景下32位弱校验的碰撞概率并不是可以忽略的。碰撞会导致频繁触发强校验复核CPU开销暴增同步速度反而变慢。我们在一次同步几万个碎片文件的测试里发现滚动校验碰撞率异常偏高排查后发现是数据里有大量连续的相同字节模式这正是弱校验最容易碰撞的情况。后来按文件类型拆分了块大小和校验策略问题才解决。第三个坑是补丁校验的时机。生成补丁时不校验没关系但应用补丁时一定要做好文件系统层面的原子性保障。如果补丁写到一半设备断电设备会留下一个既不旧也不新的半残文件下一次升级就再也对不上了。工程上典型的做法是先写到临时文件全部落盘并校验通过后再做一次原子重命名。我见过不止一个项目因为图省事直接在原文件上打补丁结果中途出错导致设备变砖的。这种事情说多了都是泪。7. 最后分享一条实操配置经验最后说一个我在实际项目中反复使用的配置习惯。做rsync类差分同步时我会把校验参数拆成两级网络快的场景用相对大一些的块比如64KB能够明显降低CPU开销网络慢的场景用小块并配合断点续传通常选4KB到8KB。文件类型也要纳入考虑源代码目录这种以文本为主的文件小块匹配效果好存档类文件大块反而能更快跳过重复段。还有一个通用的经验在做任何传输时差分之前先跑一次数据统计脚本看看新旧两个版本之间的公共保留比例。如果公共保留比例低于百分之五说明这个文件可能经历了整体重写差分传不上什么便宜这种情况果断用全量传输。这个比例指标对我们判断是否值得走差分流程非常有帮助甚至在产品设计里可以直接作为一个自动化决策开关——公共保留比例高于某个阈值就走差分通道低于阈值就走全量通道。差分不是万能的但先判断是否值得差分再决定差分粒度这个思路几乎在任何一个做数据同步、版本管理、升级分发的系统里都适用。把这一点想清楚比你盲选任何算法都重要。
阅读完成 · 觉得有帮助？
