更新的二进制差异算法

替换一个二进制文件有以下两个思路：

使用完整的一个新文件直接覆盖旧的文件。只替换新旧文件之间的差异。通过算法去计算新旧文件之间的差异，然后将差异部分移动到目标机器上。其中方法一制作的更新就叫做全量更新（Full Update）。而方法二就是二进制差分方式，即增量更新（Delta Update）。

增量更新

增量更新有两个方式：文件差量更新、二进制差量更新。
大部分的大软件，如 QQ 等，都会在自动更新的时候都会使用文件差量更新和二进制差量更新一起使用的策略。

二进制差分更新对于就文件的状态有严格的要求，这是因为不同版本之间的二进制差异不同。
举个例子：某个新的文件A的版本是3，需要更新到用户的机器上。但是部分用户机器上安装的文件A版本是1，部分用户的文件A是版本2。这种情况下，就需要分别计算版本3和版本1的差异，以及版本3和版本2的差异。然后根据不同用户的情况分别发送不同的二进制差异文件。
想要进行增量更新，需要构建模块支持才能实现。确定性构建就是在代码没有变更的时候，构建输出的 DLL 或 Exe 一定是不变的。对应的，还应加入确定性混淆的支持，有一些代码接入了混淆过程，要求在代码没有变更的时候，最后混淆输出的文件也没有变更。

增量更新不能热更新，需要重启才能生效。

用到的算法主要有bsdiff，octodiff，xdelta。

bsdiff 算法的时间复杂度和空间复杂度都很高。但优点是更新文件大小比较小。

处理大文件选择Octodiff，处理小文件选择bsdiff.

正向/逆向差分技术

在此之前，为了解决Windows累积更新体积过大的问题，微软使用的是Express Update技术。Express技术确实减小了累积更新的体积，但是却极大的增加了Window更新服务器的计算压力与存储压力。Express更新文件在更新服务器上通常会有大于10GB的体积。Express Update正是使用的增量更新方式，并且把所有文件的所有版本差异都存储到了更新服务器上（海量的文件）。

Windows 10 1809版本之后引入了基于二进制的正向/逆向差分技术。

二进制差分是需要严格比对文件的版本信息的。如果被替换文件的版本不确定，那么就无法应用二进制差分。如果本替换文件的版本非常多，那么就需要针对每一个版本分别计算二进制差分，这样一来，不同版本的二进制差分的总和体积也必然不会小，因此就抵消掉差分带来的体积优势。

正向/逆向差分技术的核心思路是：将被替换文件的版本固定，这样就能唯一确定一个二进制差分了。那么，将被替换的文件版本固定成什么版本呢？
Windows更新用的方法是，将所有需要被更新的文件版本回到Windows 10 基线版本。然后，从基线版本安装二进制差分，完成文件的更新。
这里，从当前的文件版本回退到基线版本的过程被称为逆向，从基线版本更新到最新的版本的过程称为正向，也被称为注水（hydration）。制作差分二进制叫做脱水（dehydration）。
这两次文件更新的行为都使用差分二进制来完成，因此这就是正向/逆向二进制差分技术。

核心逻辑在于通过固定基线版本（RTM）作为唯一中间状态，规避多版本组合带来的差分数爆炸问题。
这样只需要存储一个当前版本到基线版本的二进制差分，然后统一从基线版本升级到新版本。
（eg. 例如有0、1、2、3、4版本。如果用老办法，需要存储0->1，0->2，0->3，0->4，1->2，1->3，1->4，2->3，2->4，3->4的差分包，多了之后数量爆炸，因为增加新版本的时候需要存储之前所有版本到新版本的差分包。
如果采用正向/逆向差分，要存储1->0，2->0，3->0，4->0，然后存储0->1，0->2，0->3，0->4。增加新版本的时候，只需要增加5->0和0->5，从n的累加优化到了n的线性关系的差分包数量。
）

基于正向/逆向二进制差分的Windows累积更新内部包含以下内容：