做了几年二进制分发和镜像升级相关的工具链我一度把Xdelta3当成黑盒用命令行一行旧文件加新文件出补丁简单省事。直到有次把一份500MB左右的固件做增量的时候发现不同窗口参数出来的补丁体积能差出好几个百分点内存占用却翻了一倍这才决定把源码认真读一遍。读完最大的收获不是某个匹配算法多巧妙而是搞明白了增量文件里Window这个概念在源码层面到底是怎么设计、怎么落地的。这篇文章就围绕Xdelta3源码里的Window部分展开记录我对窗口数据结构、窗口建立与推进、窗口编码输出以及相关参数调优的具体理解适合那些已经会用Xdelta3但想往深走一步或者正在写增量同步模块的开发者参考。1. 先定框架Xdelta3的编码主循环里窗口是如何登场的1.1 从命令行到核心编码器调用链梳理如果只从调用链来看Xdelta3并没有想象中复杂。命令行入口解析参数之后会走xd3_main_encode紧接着创建xd3_stream结构体把输入、输出、源文件描述和配置项全部挂上去然后进入xd3_encode_input。真正干活的地方是xd3_process_stream这是一个很大的状态机循环驱动它的核心因素有两个输入缓冲区里有没有数据以及当前窗口有没有被填满。这个循环里最关键的判断逻辑就是比较stream-input_position - stream-winstart和配置的window_size。前者是已经读入的目标数据总量后者是窗口上限。一旦两者之差达到窗口上限编码器就暂停接收新数据先把当前窗口封口调用xd3_emit_window把这一窗的增量数据写出去再重置窗口进度继续处理下一段。也就是说目标文件不是一次全塞进内存而是按窗口切成一段段分别做增量编码。窗口在增量文件里是最顶层的组织单元。一个Xdelta3补丁文件的整体结构可以概括为文件头部在前后面跟着一串窗口数据每个窗口都自带描述信息。解码端也可以独立地从一个窗口开始解读取它的源引用位置、数据长度、指令流然后重建出对应目标文件的片段。搞懂这个结构再看源码就容易定位了。1.2 窗口在增量文件中的位置VCDIFF的基本组成单元Xdelta3是VCDIFFRFC 3284的一个实现。VCDIFF格式本身并不强制要求窗口有多大也不要求源文件必须怎么分块它只是规定一个增量文件由一个头部和若干个delta window组成每个delta window内部包含对源数据段的引用、指令、附加字节和可选的校验信息。从编码器角度看窗口是一个处理周期内连续接收的目标数据块。每个窗口在写出去时会先写窗口自身的总长度然后是delta encoding indicator用来声明这个窗口是否引用了源文件、是否引用了目标文件前缀、是否带Adler32校验和。接着是源分段的位置和长度以及指令流的长度和内容。这一整套结构在源码里对应xd3_emit_window函数从头到尾的组织顺序。理解了窗口是VCDIFF的基本组成单元之后剩下的事情就具体了源码里怎么用结构体表达窗口、怎么建立源窗口、怎么在窗口终结时把它编码成字节流、以及窗口大小这个参数在实际工程里怎么调。下面逐层拆开。2. 两个结构体讲清窗口模型xd3_stream与xd3_source2.1 xd3_stream目标窗口的边界与进度记录xd3_stream是整个编码/解码过程的状态机字段非常多挑窗口相关的看就够了。窗口的边界由winstart、winoff、winlen和wincnt联合表示。winstart是当前窗口在目标流里的绝对起始偏移winoff是当前窗口内已经处理了多少字节winlen是当前窗口最终编码时的有效长度。当编码器判断窗口满了的时候实际就是把winoff固定下来让它等于当前窗口处理到的字节数然后把winlen同步成这个值调用xd3_emit_window输出。输出结束后winstart推进一个窗口大小winoff清零wincnt加一开始下一个窗口。这套逻辑在xd3_process_stream的状态机里循环执行。输入输出缓冲也挂在xd3_stream上next_in、avail_in表示待处理的目标数据指针和剩余量next_out、avail_out表示输出缓冲的写入位置和剩余空间。窗口处理过程中每消化一段输入input_position就向前走同时winoff也跟着走。源码里大量判断语句都在检查avail_in 0和avail_out 0这两个条件因为任何一方的缓冲耗尽都会导致状态机暂时挂起等待上层重新填充。2.2 xd3_source源窗口的分块缓存与回调加载xd3_source描述源文件它和xd3_stream最不一样的地方是引入了块缓存机制。源文件可能非常大不可能把整个文件读进内存所以Xdelta3把源文件切成了固定大小的块通过getblk回调按需加载。窗口相关的字段集中在srcwin_off、srcwin_max、srclen和srcbase上。srcwin_off表示当前源窗口在源文件里的起始偏移srcwin_max表示源窗口最大能覆盖多少字节srclen是当前源窗口实际有效的长度srcbase指向源窗口数据在内存里的缓冲起点。这里有个容易忽视的点Xdelta3的源窗口并不是一次性加载完整的连续区间。它维护的是窗口区间概念实际数据按块缓存匹配器在查找时如果需要某个块的某段数据就通过getblk去取。块缓存内部还有curblk、curblkno、onblk这些字段记录当前缓存的块号和有效字节数。这种设计让大源文件场景下的内存占用可控代价是匹配查找时可能会触发块的换入换出。2.3 窗口计数与输入输出指针的配合窗口计数wincnt在编码和解码端都有用。编码端每写完一个窗口递增一次解码端每读完一个窗口也递增一次两边对不上说明补丁流有问题。增量文件的每个窗口字节长度不是固定的所以解码端不能通过固定步长跳到下一个窗口它必须把当前窗口完整解完才能根据窗口头里记录的字节长度继续往下走。输入输出指针和窗口进度之间是严格的配合关系。编码器写窗口时next_out不断移动avail_out不断减少一旦avail_out耗尽编码器会把当前窗口的中间状态保存在xd3_stream里等待调用方腾出输出缓冲后再继续。这也是Xdelta3能做成流式的原因它不要求整个目标文件都在内存里窗口边界、输入缓冲、输出缓冲三者构成了一个可挂起的状态机。3. 源窗口的建立与推进xd3_srcwin_setup与xd3_srcwin_move的逻辑3.1 编码开始时源窗口如何准备编码启动后Xdelta3会在正式接收目标数据之前先做源窗口的初始化。源码里对应的是xd3_srcwin_setup的逻辑把srcwin_off设为0srclen取min(源文件长度, srcwin_max)然后调用内部函数初始化源窗口的哈希索引。这个哈希索引就是后续匹配查找的基础。Xdelta3的匹配器在源窗口区间内建立checksum表目标数据进入后先算出当前位置的哈希值在表里找候选位置再逐字节验证。源码里的init_source_checksum干的就是这件事匹配查找逻辑对应xd3_string_match和xd3_find_match这两个函数前者做快速初筛后者做精细确认。从增量压缩的原理上讲这一步把所有能用的已知数据先组织好后面每来一段目标数据都先去已知数据里找最像的部分找到就发COPY指令找不到就攒成ADD指令。源窗口大小直接决定了这个已知数据池有多大。3.2 什么时候推进源窗口推进多少源窗口不是固定的。当匹配器发现源窗口的有效区间已经搜索不到对当前目标窗口有价值的匹配而源文件后面还有内容时编码器会调用xd3_srcwin_move把源窗口向前推进。这个推进动作有几个细节值得注意。第一推进发生在窗口切换的间隙不会在一个目标窗口处理到一半时突然改变源窗口否则已经生成的那些COPY地址就失去参照了。第二推进并不是简单把srcwin_off加上一个固定值它会根据当前匹配状态做对齐避免把正在使用的源数据区间挪走。第三推进后旧的哈希索引作废要重新建立这一步有CPU成本所以频繁推进不是好事。从实际效果看源窗口推进最典型的场景是目标文件很大而源文件本身就是目标文件的前缀或接近前缀的演进版本。编码器会先在前面的源窗口里找到大量匹配随着进度推进再逐步向后移动源窗口保持搜索区域始终落在目标进度附近这个合理位置。这种动态窗口策略是Xdelta3压缩率能做到比较好的一个关键原因。3.3 解码端为什么完全不关心这些读源码最容易产生的困惑就是看编码端一堆srcwin_off、srclen的维护逻辑以为解码端也要照做一遍。实际上解码端完全没有这些概念。VCDIFF增量文件里每个窗口头都明确写着本次引用了源文件的哪个位置、多长也就是source segment offset和source segment length。解码器拿到这两个值直接从源文件里把对应区间读出来挂到可寻址空间里然后开始解析指令流。它不关心编码器当时搜索的窗口是多大、哈希表怎么建的、窗口推进过几次那些都是编码端内部优化。这个设计带来的好处是解码器可以做得轻量甚至允许乱序解码只要源文件可随机访问每个窗口理论上可以独立解码。当然Xdelta3的命令行实现为了保持输出顺序还是一个窗口一个窗口顺序解但从格式层面看窗口之间的互依赖其实很弱。4. 窗口终结瞬间xd3_emit_window生成什么样的增量数据4.1 窗口头的字节布局与指示位窗口处理完毕后xd3_emit_window负责把整个窗口序列化成字节流。先处理的是Win_Length它是一个变长整数表示这个窗口除去自身长度字段之外的总字节数。紧接着是Delta_Encoding_Indicator。这是一个位掩码字节最低位VCD_SOURCE表示引用了外部源文件第二个位VCD_TARGET表示引用了目标文件已解码的前缀第三个位VCD_ADLER32表示窗口尾部带Adler32校验和。Xdelta3的常规用法是设置VCD_SOURCE也就是引用外部源文件。如果声明了源引用后面就跟着两个变长整数Length of Source Segment和Source Segment Position。这两个值直接告诉解码器去源文件的哪个偏移读多长数据作为这个窗口的解码上下文。源码在编码端先查这个窗口实际用到的源区间再把它写进窗口头。这里要留意不同窗口的源引用区间可以完全一样也可以是同源文件的不同区域完全由编码期间的匹配情况决定。4.2 指令流的产生ADD、COPY、RUN在源码里怎么落地窗口头写完后剩下的就是本窗口的指令流。VCDIFF指令有三种ADD、COPY、RUN。源码里分别对应xd3_emit_add、xd3_emit_copy、xd3_emit_run的处理路径。ADD指令后面直接跟一段未匹配的原始字节长度由指令字节给出。编码器在匹配失败时不会立刻为每个字节输出一条指令而是把连续未匹配的字节先累积到内部缓冲里攒到一定长度再一次性作为一条ADD指令发出。这个缓冲的flush时机源码里对应xd3_emit_add的触发条件。COPY指令是最核心的它引用可寻址空间里的某个位置并复制一段长度。可寻址空间包括当前窗口引用的源分段还包括目标窗口已经解码的部分。一条COPY指令需要编码长度、地址模式和一个经过预测编码的地址值。源码中的xd3_encode_address就是干这个的它维护一组near指针和一组same指针COPY地址不直接写绝对偏移而是写相对某个历史地址的差或者历史地址低位的命中索引这样短距离COPY的地址常常只占一个字节。窗口越大这种差分编码的收益越明显。RUN指令处理连续重复的字节串指令字节加一个重复字节参数就能展开一段完全相同的数据。源码里有专门的检测路径但在随机性较强的二进制数据里命中率不高它不是主要的压缩来源。整段指令流加数据都写完后窗口的序列化工作就结束了。4.3 Adler32校验与二次压缩对窗口体积的影响当窗口头声明了VCD_ADLER32时窗口数据的最后部分会写入一个Adler32值它是目标窗口原始数据的校验和用于解码端自检。源码在编码时边输出边累计这个值在窗口末尾写出去解码端解完整个窗口后再算一次对不上就报错。对流式传输或存储介质不可靠的场景这个校验很有价值。VCDIFF还允许把整个delta encoding的指令和字面数据再做一层二次压缩。Xdelta3实现了FGK动态哈夫曼等方案源码里可以看到xd3_encode_secondary之类的路径。是否启用取决于编译选项和命令行参数。启用后指令流的字节模式会经过又一轮压缩在literal较多的窗口里能再挤出几个百分点的大小代价是额外的CPU消耗和复杂度。窗口级别组织这些指令、数据和压缩参数的先后顺序也是xd3_emit_window里写字节时严格保证的。5. 窗口大小与内存、压缩率的真实权衡5.1 -B、-P、-S参数分别影响什么窗口大小的直接参数是-B它指定编码端的目标窗口长度同时默认也约束了源窗口的覆盖范围。窗口越大匹配搜索的池子越大目标数据中越远的相似片段越有机会被找到压缩率理论上更好。但代价也直接更大的源窗口需要更大的块缓存和更大的哈希索引建立索引的时间也更长。-P是最小匹配长度。它影响的是多短的重复才算有效匹配。最小匹配长度设得越小越容易命中短匹配但短匹配产生的COPY指令本身有开销可能比直接存原始字节还贵。设得越大匹配越保守速度更快压缩率可能略降。源码里匹配查找时会拿候选长度和这个阈值比对小于阈值的直接放弃。-S控制哈希表的规模准确说是哈希表以2为幂的容量参数。哈希表大了候选点更多匹配质量更高但内存显著上涨哈希表小了查得粗糙大窗口的收益就会打折。理想情况下窗口大小和哈希表规模要配套调而不是只拉大-B。5.2 不同窗口大小下的实测趋势我在某个内部测试项目里对一组二进制分发文件做过失真对照源版本和目标版本之间的差异属于典型的大多数区域相同、少量区域有改动和新增。大致趋势是这样的窗口大小补丁体积趋势峰值内存趋势编码时间趋势64MB最低最高最长16MB略高明显下降明显缩短4MB明显更高很低很短1MB最高最低最短这个趋势可以解释为什么很多人默认用64MB窗口却没觉得有什么问题单次编码可以把压缩率拉满补丁体积最好看。但如果要做流式同步或者目标机器内存有限64MB窗口的内存模型就不是那么友好了。而且数据本身的规律性会放大或抹平这些差异如果源和目标文件相似度极高小窗口也能有很高的匹配率体积差距并不大。一个重要提醒是这里列的是趋势不是绝对数值。Xdelta3对不同的数据特征非常敏感拿到具体文件之后用-B扫一两轮比死记任何推荐值都可靠。5.3 流式场景的窗口策略流式场景下窗口大小还直接决定了解出目标数据的最小时延。解码端必须读完一个完整的窗口才能开始输出这个窗口对应的目标数据块。窗口设成64MB就意味着解码端要等收到64MB的补丁数据才能吐出第一块目标内容。对做实时镜像同步、边下边解这类需求的系统64MB窗口几乎不可接受通常压到1MB到8MB之间。源码层面看解码端的内存模型比编码端轻窗口头加指令流加上源分段按需加载。小窗口让解码器迅速进入输出状态也可以很精确地控制解码端的缓冲占用。所以流式场景的正确思路不是追求最大匹配率而是选一个输出延迟可接受的窗口大小再配合合适的-P和-S把压缩率从其他地方找回来。6. 读源码时最容易被绕晕的四个窗口问题6.1 源窗口不是和目标窗口同步滑动的很多人一听到窗口就以为是两个窗口一起往前滚读源码时却发现编码器里源窗口和目标窗口的推进节奏完全不一样。目标窗口以固定大小向前推进一个接一个连续处理源窗口则是在需要时才会把srcwin_off整体后移而且可能连续几个目标窗口都引用同一个源窗口区间。从增量文件的角度看每个窗口头里的Source Segment Position指向源文件的位置和目标窗口的编号没有固定对应关系。理解了这一点再看xd3_srcwin_move就不会被绕晕它只是在编码端调节搜索范围的手段不是解码端必须照做的流程。6.2 COPY地址的mode与near/same缓存如果把COPY指令后面的地址当成源文件的绝对偏移很容易在后面调试时翻车。VCDIFF的COPY地址是对当前可寻址窗口空间的编码这个空间包含源分段加已解码的目标数据。地址编码还要再过一道预测逻辑xd3_encode_address根据near指针与same指针的历史状态把地址转换成相对差或哈希低位命中的形式。源码里xd3_decode_address必然和编码端完全对称才能在解码侧还原出真实地址。这个设计对压缩率的贡献很大尤其是窗口里连续COPY很多片段时只需要很小的增量信息就能表示下一次跳转。如果把这些地址理解成普通偏移量就会觉得源码里的计算过程莫名其妙。6.3 目标窗口引用与源引用的区别VCDIFF允许窗口同时声明VCD_SOURCE和VCD_TARGET后者表示当前窗口可以引用目标文件里已经解码出来的前缀数据。也就是说目标窗口不仅能从外部源文件里找相同数据还能从自己文件前一段里找。源码层面这两条路径对应不同的可寻址空间组织和不同的地址计算方法。实际使用中外部源引用是主力目标前缀引用的收益通常不如源引用明显但它是VCDIFF格式兼容性的一部分。如果你只是在读Xdelta3源码理解这个区别能避免把VCD_TARGET的位含义搞混。6.4 窗口越多增量文件越大的错觉常有人觉得窗口越小窗口数越多所以头部开销大、补丁一定更大。这个判断并不总是成立。窗口边界如果正好落在源和目标高度相似的位置小窗口也能产生同样高比例的COPY指令体积增长非常有限而窗口过大时哈希表如果跟不上匹配质量反而下降。窗口数量和补丁体积之间不是单调关系数据分布会改变结论。源码层面也能看到原因每个窗口确实要写一个窗口头和若干指示位这部分固定开销客观存在但指令流里的COPY地址编码在小窗口下可能更紧凑因为地址差异更小。两者一抵消结果就取决于具体数据。真要调优拿样本文件跑几组参数对比比在理论上纠结更有用。我自己的实践体会是啃完Window这一层之后最明显的变化是以后调参数不再是瞎试。看增量文件时也能直接辨认出哪个字节是窗口头、哪个位置是source segment、指令流大概是长什么样了。如果想把这块彻底吃透建议自己拿一个小文件做源改几个字节做目标用-B设成很小的窗口生成补丁再用十六进制工具对照源码里的写入顺序一段段看。看到窗口头和指令流的排布和自己预期一致的时候整个增量文件的结构就真正变成你自己的知识了。 
长河君 · 2026/10/22 6:28:08 · 阅读 1.2k 深入Xdelta3源码：窗口机制、推进策略与参数调优实践
做了几年二进制分发和镜像升级相关的工具链我一度把Xdelta3当成黑盒用命令行一行旧文件加新文件出补丁简单省事。直到有次把一份500MB左右的固件做增量的时候发现不同窗口参数出来的补丁体积能差出好几个百分点内存占用却翻了一倍这才决定把源码认真读一遍。读完最大的收获不是某个匹配算法多巧妙而是搞明白了增量文件里Window这个概念在源码层面到底是怎么设计、怎么落地的。这篇文章就围绕Xdelta3源码里的Window部分展开记录我对窗口数据结构、窗口建立与推进、窗口编码输出以及相关参数调优的具体理解适合那些已经会用Xdelta3但想往深走一步或者正在写增量同步模块的开发者参考。1. 先定框架Xdelta3的编码主循环里窗口是如何登场的1.1 从命令行到核心编码器调用链梳理如果只从调用链来看Xdelta3并没有想象中复杂。命令行入口解析参数之后会走xd3_main_encode紧接着创建xd3_stream结构体把输入、输出、源文件描述和配置项全部挂上去然后进入xd3_encode_input。真正干活的地方是xd3_process_stream这是一个很大的状态机循环驱动它的核心因素有两个输入缓冲区里有没有数据以及当前窗口有没有被填满。这个循环里最关键的判断逻辑就是比较stream-input_position - stream-winstart和配置的window_size。前者是已经读入的目标数据总量后者是窗口上限。一旦两者之差达到窗口上限编码器就暂停接收新数据先把当前窗口封口调用xd3_emit_window把这一窗的增量数据写出去再重置窗口进度继续处理下一段。也就是说目标文件不是一次全塞进内存而是按窗口切成一段段分别做增量编码。窗口在增量文件里是最顶层的组织单元。一个Xdelta3补丁文件的整体结构可以概括为文件头部在前后面跟着一串窗口数据每个窗口都自带描述信息。解码端也可以独立地从一个窗口开始解读取它的源引用位置、数据长度、指令流然后重建出对应目标文件的片段。搞懂这个结构再看源码就容易定位了。1.2 窗口在增量文件中的位置VCDIFF的基本组成单元Xdelta3是VCDIFFRFC 3284的一个实现。VCDIFF格式本身并不强制要求窗口有多大也不要求源文件必须怎么分块它只是规定一个增量文件由一个头部和若干个delta window组成每个delta window内部包含对源数据段的引用、指令、附加字节和可选的校验信息。从编码器角度看窗口是一个处理周期内连续接收的目标数据块。每个窗口在写出去时会先写窗口自身的总长度然后是delta encoding indicator用来声明这个窗口是否引用了源文件、是否引用了目标文件前缀、是否带Adler32校验和。接着是源分段的位置和长度以及指令流的长度和内容。这一整套结构在源码里对应xd3_emit_window函数从头到尾的组织顺序。理解了窗口是VCDIFF的基本组成单元之后剩下的事情就具体了源码里怎么用结构体表达窗口、怎么建立源窗口、怎么在窗口终结时把它编码成字节流、以及窗口大小这个参数在实际工程里怎么调。下面逐层拆开。2. 两个结构体讲清窗口模型xd3_stream与xd3_source2.1 xd3_stream目标窗口的边界与进度记录xd3_stream是整个编码/解码过程的状态机字段非常多挑窗口相关的看就够了。窗口的边界由winstart、winoff、winlen和wincnt联合表示。winstart是当前窗口在目标流里的绝对起始偏移winoff是当前窗口内已经处理了多少字节winlen是当前窗口最终编码时的有效长度。当编码器判断窗口满了的时候实际就是把winoff固定下来让它等于当前窗口处理到的字节数然后把winlen同步成这个值调用xd3_emit_window输出。输出结束后winstart推进一个窗口大小winoff清零wincnt加一开始下一个窗口。这套逻辑在xd3_process_stream的状态机里循环执行。输入输出缓冲也挂在xd3_stream上next_in、avail_in表示待处理的目标数据指针和剩余量next_out、avail_out表示输出缓冲的写入位置和剩余空间。窗口处理过程中每消化一段输入input_position就向前走同时winoff也跟着走。源码里大量判断语句都在检查avail_in 0和avail_out 0这两个条件因为任何一方的缓冲耗尽都会导致状态机暂时挂起等待上层重新填充。2.2 xd3_source源窗口的分块缓存与回调加载xd3_source描述源文件它和xd3_stream最不一样的地方是引入了块缓存机制。源文件可能非常大不可能把整个文件读进内存所以Xdelta3把源文件切成了固定大小的块通过getblk回调按需加载。窗口相关的字段集中在srcwin_off、srcwin_max、srclen和srcbase上。srcwin_off表示当前源窗口在源文件里的起始偏移srcwin_max表示源窗口最大能覆盖多少字节srclen是当前源窗口实际有效的长度srcbase指向源窗口数据在内存里的缓冲起点。这里有个容易忽视的点Xdelta3的源窗口并不是一次性加载完整的连续区间。它维护的是窗口区间概念实际数据按块缓存匹配器在查找时如果需要某个块的某段数据就通过getblk去取。块缓存内部还有curblk、curblkno、onblk这些字段记录当前缓存的块号和有效字节数。这种设计让大源文件场景下的内存占用可控代价是匹配查找时可能会触发块的换入换出。2.3 窗口计数与输入输出指针的配合窗口计数wincnt在编码和解码端都有用。编码端每写完一个窗口递增一次解码端每读完一个窗口也递增一次两边对不上说明补丁流有问题。增量文件的每个窗口字节长度不是固定的所以解码端不能通过固定步长跳到下一个窗口它必须把当前窗口完整解完才能根据窗口头里记录的字节长度继续往下走。输入输出指针和窗口进度之间是严格的配合关系。编码器写窗口时next_out不断移动avail_out不断减少一旦avail_out耗尽编码器会把当前窗口的中间状态保存在xd3_stream里等待调用方腾出输出缓冲后再继续。这也是Xdelta3能做成流式的原因它不要求整个目标文件都在内存里窗口边界、输入缓冲、输出缓冲三者构成了一个可挂起的状态机。3. 源窗口的建立与推进xd3_srcwin_setup与xd3_srcwin_move的逻辑3.1 编码开始时源窗口如何准备编码启动后Xdelta3会在正式接收目标数据之前先做源窗口的初始化。源码里对应的是xd3_srcwin_setup的逻辑把srcwin_off设为0srclen取min(源文件长度, srcwin_max)然后调用内部函数初始化源窗口的哈希索引。这个哈希索引就是后续匹配查找的基础。Xdelta3的匹配器在源窗口区间内建立checksum表目标数据进入后先算出当前位置的哈希值在表里找候选位置再逐字节验证。源码里的init_source_checksum干的就是这件事匹配查找逻辑对应xd3_string_match和xd3_find_match这两个函数前者做快速初筛后者做精细确认。从增量压缩的原理上讲这一步把所有能用的已知数据先组织好后面每来一段目标数据都先去已知数据里找最像的部分找到就发COPY指令找不到就攒成ADD指令。源窗口大小直接决定了这个已知数据池有多大。3.2 什么时候推进源窗口推进多少源窗口不是固定的。当匹配器发现源窗口的有效区间已经搜索不到对当前目标窗口有价值的匹配而源文件后面还有内容时编码器会调用xd3_srcwin_move把源窗口向前推进。这个推进动作有几个细节值得注意。第一推进发生在窗口切换的间隙不会在一个目标窗口处理到一半时突然改变源窗口否则已经生成的那些COPY地址就失去参照了。第二推进并不是简单把srcwin_off加上一个固定值它会根据当前匹配状态做对齐避免把正在使用的源数据区间挪走。第三推进后旧的哈希索引作废要重新建立这一步有CPU成本所以频繁推进不是好事。从实际效果看源窗口推进最典型的场景是目标文件很大而源文件本身就是目标文件的前缀或接近前缀的演进版本。编码器会先在前面的源窗口里找到大量匹配随着进度推进再逐步向后移动源窗口保持搜索区域始终落在目标进度附近这个合理位置。这种动态窗口策略是Xdelta3压缩率能做到比较好的一个关键原因。3.3 解码端为什么完全不关心这些读源码最容易产生的困惑就是看编码端一堆srcwin_off、srclen的维护逻辑以为解码端也要照做一遍。实际上解码端完全没有这些概念。VCDIFF增量文件里每个窗口头都明确写着本次引用了源文件的哪个位置、多长也就是source segment offset和source segment length。解码器拿到这两个值直接从源文件里把对应区间读出来挂到可寻址空间里然后开始解析指令流。它不关心编码器当时搜索的窗口是多大、哈希表怎么建的、窗口推进过几次那些都是编码端内部优化。这个设计带来的好处是解码器可以做得轻量甚至允许乱序解码只要源文件可随机访问每个窗口理论上可以独立解码。当然Xdelta3的命令行实现为了保持输出顺序还是一个窗口一个窗口顺序解但从格式层面看窗口之间的互依赖其实很弱。4. 窗口终结瞬间xd3_emit_window生成什么样的增量数据4.1 窗口头的字节布局与指示位窗口处理完毕后xd3_emit_window负责把整个窗口序列化成字节流。先处理的是Win_Length它是一个变长整数表示这个窗口除去自身长度字段之外的总字节数。紧接着是Delta_Encoding_Indicator。这是一个位掩码字节最低位VCD_SOURCE表示引用了外部源文件第二个位VCD_TARGET表示引用了目标文件已解码的前缀第三个位VCD_ADLER32表示窗口尾部带Adler32校验和。Xdelta3的常规用法是设置VCD_SOURCE也就是引用外部源文件。如果声明了源引用后面就跟着两个变长整数Length of Source Segment和Source Segment Position。这两个值直接告诉解码器去源文件的哪个偏移读多长数据作为这个窗口的解码上下文。源码在编码端先查这个窗口实际用到的源区间再把它写进窗口头。这里要留意不同窗口的源引用区间可以完全一样也可以是同源文件的不同区域完全由编码期间的匹配情况决定。4.2 指令流的产生ADD、COPY、RUN在源码里怎么落地窗口头写完后剩下的就是本窗口的指令流。VCDIFF指令有三种ADD、COPY、RUN。源码里分别对应xd3_emit_add、xd3_emit_copy、xd3_emit_run的处理路径。ADD指令后面直接跟一段未匹配的原始字节长度由指令字节给出。编码器在匹配失败时不会立刻为每个字节输出一条指令而是把连续未匹配的字节先累积到内部缓冲里攒到一定长度再一次性作为一条ADD指令发出。这个缓冲的flush时机源码里对应xd3_emit_add的触发条件。COPY指令是最核心的它引用可寻址空间里的某个位置并复制一段长度。可寻址空间包括当前窗口引用的源分段还包括目标窗口已经解码的部分。一条COPY指令需要编码长度、地址模式和一个经过预测编码的地址值。源码中的xd3_encode_address就是干这个的它维护一组near指针和一组same指针COPY地址不直接写绝对偏移而是写相对某个历史地址的差或者历史地址低位的命中索引这样短距离COPY的地址常常只占一个字节。窗口越大这种差分编码的收益越明显。RUN指令处理连续重复的字节串指令字节加一个重复字节参数就能展开一段完全相同的数据。源码里有专门的检测路径但在随机性较强的二进制数据里命中率不高它不是主要的压缩来源。整段指令流加数据都写完后窗口的序列化工作就结束了。4.3 Adler32校验与二次压缩对窗口体积的影响当窗口头声明了VCD_ADLER32时窗口数据的最后部分会写入一个Adler32值它是目标窗口原始数据的校验和用于解码端自检。源码在编码时边输出边累计这个值在窗口末尾写出去解码端解完整个窗口后再算一次对不上就报错。对流式传输或存储介质不可靠的场景这个校验很有价值。VCDIFF还允许把整个delta encoding的指令和字面数据再做一层二次压缩。Xdelta3实现了FGK动态哈夫曼等方案源码里可以看到xd3_encode_secondary之类的路径。是否启用取决于编译选项和命令行参数。启用后指令流的字节模式会经过又一轮压缩在literal较多的窗口里能再挤出几个百分点的大小代价是额外的CPU消耗和复杂度。窗口级别组织这些指令、数据和压缩参数的先后顺序也是xd3_emit_window里写字节时严格保证的。5. 窗口大小与内存、压缩率的真实权衡5.1 -B、-P、-S参数分别影响什么窗口大小的直接参数是-B它指定编码端的目标窗口长度同时默认也约束了源窗口的覆盖范围。窗口越大匹配搜索的池子越大目标数据中越远的相似片段越有机会被找到压缩率理论上更好。但代价也直接更大的源窗口需要更大的块缓存和更大的哈希索引建立索引的时间也更长。-P是最小匹配长度。它影响的是多短的重复才算有效匹配。最小匹配长度设得越小越容易命中短匹配但短匹配产生的COPY指令本身有开销可能比直接存原始字节还贵。设得越大匹配越保守速度更快压缩率可能略降。源码里匹配查找时会拿候选长度和这个阈值比对小于阈值的直接放弃。-S控制哈希表的规模准确说是哈希表以2为幂的容量参数。哈希表大了候选点更多匹配质量更高但内存显著上涨哈希表小了查得粗糙大窗口的收益就会打折。理想情况下窗口大小和哈希表规模要配套调而不是只拉大-B。5.2 不同窗口大小下的实测趋势我在某个内部测试项目里对一组二进制分发文件做过失真对照源版本和目标版本之间的差异属于典型的大多数区域相同、少量区域有改动和新增。大致趋势是这样的窗口大小补丁体积趋势峰值内存趋势编码时间趋势64MB最低最高最长16MB略高明显下降明显缩短4MB明显更高很低很短1MB最高最低最短这个趋势可以解释为什么很多人默认用64MB窗口却没觉得有什么问题单次编码可以把压缩率拉满补丁体积最好看。但如果要做流式同步或者目标机器内存有限64MB窗口的内存模型就不是那么友好了。而且数据本身的规律性会放大或抹平这些差异如果源和目标文件相似度极高小窗口也能有很高的匹配率体积差距并不大。一个重要提醒是这里列的是趋势不是绝对数值。Xdelta3对不同的数据特征非常敏感拿到具体文件之后用-B扫一两轮比死记任何推荐值都可靠。5.3 流式场景的窗口策略流式场景下窗口大小还直接决定了解出目标数据的最小时延。解码端必须读完一个完整的窗口才能开始输出这个窗口对应的目标数据块。窗口设成64MB就意味着解码端要等收到64MB的补丁数据才能吐出第一块目标内容。对做实时镜像同步、边下边解这类需求的系统64MB窗口几乎不可接受通常压到1MB到8MB之间。源码层面看解码端的内存模型比编码端轻窗口头加指令流加上源分段按需加载。小窗口让解码器迅速进入输出状态也可以很精确地控制解码端的缓冲占用。所以流式场景的正确思路不是追求最大匹配率而是选一个输出延迟可接受的窗口大小再配合合适的-P和-S把压缩率从其他地方找回来。6. 读源码时最容易被绕晕的四个窗口问题6.1 源窗口不是和目标窗口同步滑动的很多人一听到窗口就以为是两个窗口一起往前滚读源码时却发现编码器里源窗口和目标窗口的推进节奏完全不一样。目标窗口以固定大小向前推进一个接一个连续处理源窗口则是在需要时才会把srcwin_off整体后移而且可能连续几个目标窗口都引用同一个源窗口区间。从增量文件的角度看每个窗口头里的Source Segment Position指向源文件的位置和目标窗口的编号没有固定对应关系。理解了这一点再看xd3_srcwin_move就不会被绕晕它只是在编码端调节搜索范围的手段不是解码端必须照做的流程。6.2 COPY地址的mode与near/same缓存如果把COPY指令后面的地址当成源文件的绝对偏移很容易在后面调试时翻车。VCDIFF的COPY地址是对当前可寻址窗口空间的编码这个空间包含源分段加已解码的目标数据。地址编码还要再过一道预测逻辑xd3_encode_address根据near指针与same指针的历史状态把地址转换成相对差或哈希低位命中的形式。源码里xd3_decode_address必然和编码端完全对称才能在解码侧还原出真实地址。这个设计对压缩率的贡献很大尤其是窗口里连续COPY很多片段时只需要很小的增量信息就能表示下一次跳转。如果把这些地址理解成普通偏移量就会觉得源码里的计算过程莫名其妙。6.3 目标窗口引用与源引用的区别VCDIFF允许窗口同时声明VCD_SOURCE和VCD_TARGET后者表示当前窗口可以引用目标文件里已经解码出来的前缀数据。也就是说目标窗口不仅能从外部源文件里找相同数据还能从自己文件前一段里找。源码层面这两条路径对应不同的可寻址空间组织和不同的地址计算方法。实际使用中外部源引用是主力目标前缀引用的收益通常不如源引用明显但它是VCDIFF格式兼容性的一部分。如果你只是在读Xdelta3源码理解这个区别能避免把VCD_TARGET的位含义搞混。6.4 窗口越多增量文件越大的错觉常有人觉得窗口越小窗口数越多所以头部开销大、补丁一定更大。这个判断并不总是成立。窗口边界如果正好落在源和目标高度相似的位置小窗口也能产生同样高比例的COPY指令体积增长非常有限而窗口过大时哈希表如果跟不上匹配质量反而下降。窗口数量和补丁体积之间不是单调关系数据分布会改变结论。源码层面也能看到原因每个窗口确实要写一个窗口头和若干指示位这部分固定开销客观存在但指令流里的COPY地址编码在小窗口下可能更紧凑因为地址差异更小。两者一抵消结果就取决于具体数据。真要调优拿样本文件跑几组参数对比比在理论上纠结更有用。我自己的实践体会是啃完Window这一层之后最明显的变化是以后调参数不再是瞎试。看增量文件时也能直接辨认出哪个字节是窗口头、哪个位置是source segment、指令流大概是长什么样了。如果想把这块彻底吃透建议自己拿一个小文件做源改几个字节做目标用-B设成很小的窗口生成补丁再用十六进制工具对照源码里的写入顺序一段段看。看到窗口头和指令流的排布和自己预期一致的时候整个增量文件的结构就真正变成你自己的知识了。