软件升级：小胡瓜

原文链接：http://www.feelcomes.com/Show.aspxd=33

正如我在《越小就越快（和越安全）①》中所描述的，我们实现了一种用差异的压缩算法，来使得chrome的升级包明显减小。

我们想要更小的升级包，因为它缩小了软件的漏洞窗口。如果升级程序只有1/10的大小，我们可以在同样的带宽下推10次升级，这样意味着更多的用户能够被更早的保护。第二个好处是，对于连接不是很稳定的用户来说，更小的升级包会更好。

我们通过发布一个差异包，用来和以前的版本合成一个新版本，而不是把整个10M的新版本升级包发布出去。我们尝试过几种不同的二进制比较算法，但直到现在还是使用bsdiff。我们是bsdiff的大粉丝，它非常小，而且比其它我们尝试过的任何算法更加好。

但是bsdiff比较出来的差异包仍然比我们预期的要大些，所以我们写了一个新的差异比较算法，更适合我们发布的数据种类—包含编译后的可执行文件的大的文件。这是我们在开发者通道从190.1升级到190.4的文件大小数据(bytes):

小的软件加上谷歌 Chrome浏览器的静默升级， 意味着只要必要，就可以经常升级，来保护用户的安全。

编译后的代码：

对于编译后的程序来说，真正的问题是：即使很小的源码改变，也会导致不成比例的大量二进制级别的变化。如果你加了几行代码，比如，一个范围的检查来防止缓存溢出，所有后面的代码都会被移动来容纳新的指令。一些指令和数据经常是另外的指令和数据的地址，所以编译后的代码到处都是内部引用。但是在这些内部指针改变之前，仅仅是少数的几行代码的变动，而且是大量的内部指针，像chrome.dll大小的程序，大概有50w个。

源代码就没有这个问题，因为源代码所有的元素是符 化的。在编译和链接的过程中，函数是在后面的阶段被转化(commite）成指定地址的。如果我们能够往后退一点，使内部指针再一次符 化，是不是可以得到一个更小的安装包/p>

Courgette用了一个原始的分解器(disassembler)②来找到内部指针。分解器把程序分割成3部分：一个内部指针目的地址的列表；其他的字节和一个指令(Instruction)③序列来决定普通的字节和指针通过调整和穿插来回到原来的输入。我们把这个称为’分解的语言’(assemblylanguage)，因为我们可以跑一个分解器来处理这些指令和发布这个字节序列来恢复到原始的文件。

非指针的部分大概占了原来程序的80%，因为没有混合任何的指针，比较起来效果更好一些，差异包的大小和源代码的改变成线性关系。简单的使用分解的语言比较出来的差异包大概比原来的小30%。

我们引进标签来标识地址，使得指针可以被控制。这些地址被存在数组里面，而指针列表会被数组的下标列表所代替。这个数据是一个原始的符 表，这些符 的名字，或者标签其实是整型的数组下标。利用符 表，我们如何表达程序有一定的自由度。通过改变相应的列表索引，我们可以移动数组周围的地址。

我们怎么利用这个来生成一个更好的差异包呢sdiff将为我们计算出新的文件，从原始文件得到升级文件的原理：

    server:

        差异包 = bsdiff(原来的程序, 新的程序)

        传输差异包

    client:

        接受差异包

        新的程序 = bspatch(原来的程序, 差异包)

（该服务器将预先计算差异，所以它可以被立即传送）

   小胡瓜把程序转换成原始的assemblylanguage，然后在assembly的级别上比较出差异：

    服务端:

       asm_old = disassemble(原来的程序)

       asm_new = disassemble(新的程序)

       asm_new_adjusted = adjust(asm_new, asm_old)

       asm_diff = bsdiff(asm_old, asm_new_adjusted)

       transmit asm_diff

    客户端:

       receive asm_diff

       asm_old = disassemble(原来的程序)

       asm_new_adjusted = bspatch(asm_old, asm_diff)

        新的程序 = assemble(asm_new_adjusted)

特殊的佐料是调节这一步，小胡瓜通过移动asm_new内符 表的地址，来使得差异包的最小化。两个符 表中的地址是匹配的，在它们的统计属性上保证索引列表拥有很多公共的字串。根据周围的代码或者调试信息，对齐的地址不使用任何的探索法来进行匹配。

不止可执行文件，小于可执行文件

基于上面的操作，分解 和 组合必须是严格相反的，而且原来的程序和新的程序必须是一个良好的可执行文件。如果原来的文件和新的文件可以包含几个可执行文件，也可以包含非编译的文件如Javascript和PNG图片，将会更加有用。对于谷歌的chrome浏览器，原来的程序和新的程序是一种存档文件，包含所有安装和运行需要的文件。

我们可以假想一种差异升级，一种预测通过随后的一个猜测游戏的修正。在最简单的形式（仅仅bsdiff / bspatch），客户端只有一种愚笨的猜测——原始的文件，所以服务端把差异包发送过去，通过修正原始的文件来获得想要的答案——新的文件。现在如果服务器发送一个可以产生更好猜测的细节，但是我们不确定这个猜测是否可用过原来的文件和猜测一起作为差异包的基础，来保证不会丢失信息：

    服务端:

       hint = make_hint(original, update)

       guess =make_guess(original, hint)

       diff = bsdiff(concat(original, guess), update)

       transmit hint, diff

    客服端：

       receive hint, diff

        guess= make_guess(original, hint)

       update = bspatch(concat(original, guess), diff)

该系统有些有趣的属性，如果猜测是一个空的字符串，我们的差异包和bsdiff的结果就是一样的。如果猜测是完美的，差别将会是细小的，一个简单的指令来拷贝猜测。

在两个极端之间，猜测可能是新文件一个完美的子集。然后bsdiff可以构造一个差异包来构建新的文件，大部分取材于从完美的预测和原始文件。这就是小胡瓜处理像包含可执行文件和其他文件的tar文件的输入的原理。细节是嵌入的可执行文件和每个asm_diff的位置。

一旦我们有 预测/修正工作体系，我们可以用它来减少客户端工作量。可执行程序经常包含一些大的区域，里面是没有指针的，像资源区经常包含字符串表和各种不同的视觉元素，如图表和位图。分解器产生一个分解的语言程序，这几乎说，“这是一个很大的常量数据块”，其中的数据和原始文件是一样的。通过从分解器中忽略自由指针和让最终的差异包工作，我们可以获得大致相同的效果。

总结

小胡瓜把输入转换成另外一种更有效的二进制差异的形式，在转换空间中做差分压缩，并通过相反的转换来从原始文件中获取打了补丁后的输出。通过精心选择的转换方式之后，我们得到一个更小的升级包。

注：

①《越小就越快（和越安全）》 一篇关于chrome减小升级包体积的文章，小可以占用更少的带宽，可以使软件时时保持最新，所以使得软件更安全。

② disassembler, 分解器，而不是反汇编，是因为chrome没有真正意义上的把软件反汇编，而是遍历代码段，找出和跳转指令二进制相同的代码。而且分解器的功能是把PE文件分成3部分，跳转指令解析只是其中的一部分。

③ Instruction，指令，并非汇编指令，而是一个类，用来存储内部指针移动的信息。

http://dev.chromium.org/developers/design-documents/software-updates-courgette，注释由译者理解后加上