hsynz 同步更新算法的设计和实现

– -- 如何将传统同步算法本身提速10倍

作者: housisong@hotmail.com 2023.06.08
tag: hsynz,sync,patch,同步,diff,hdiffpatch,rsync,zsync

本文是对我开源的 hsynz 库中的同步更新算法的思路介绍；库中也有一个中文的readme，有性能对比测试，可以看看。
阅读前也可以看看我以前的一篇使用了类似思路的相关文章：《HDiffPatch：一个基于字节的流式diff算法》

基于字节的增量更新常见算法的限制

现在常见的基于字节的增量更新算法包括bsdiff、xdelta、HDiffPatch等。
它们一般的使用方式是提前在服务端制作好补丁，这就要求diff算法能够同时访问到old和new版本的全部数据。
diff算法一般比较慢，占资源比较多，但生成的补丁包较小，一般也可以选择对补丁包进行压缩。patch算法一般比较快，而具体资源占用和算法还有优化情况有关。
如果有多个old旧版本，那可能需要用diff制作每个old到最新new版本的直接升级补丁包。（不推荐服务端为节省diff次数而让客户端连续下载和安装多个补丁包的升级方式，体验不好。）
客户端下载需要的增量补丁包，结合已有的old版本数据，使用patch命令得到最新new版本的数据。而客户端的old数据不能够随意修改，否则很可能会patch失败或者生成的new数据有误。
如果客户端的版本比较旧，或者安装该旧版本的人数较少，或者有少量修改，那很可能服务端并不会创建其补丁包，而只能下载全量包来升级了。

rsync 同步更新算法原理和限制

客户端将old数据按blockSize大小分成块，计算出每个块的滚动校验哈希值(Rolling Hash，一般用的adler32)和其强校验哈希值(一般用的是md4或md5)；将这些校验信息上传到服务端。
服务端对new数据从头至尾用Rolling Hash的方式依次计算出当前位置的滚动校验值，去匹配old块的校验值。
roll-hash计算方法：首先计算new开头位置的blockSize大小的数据的adler32值；然后利用rolling原理，根据当前位置的校验值，继续添加后面的一个字节数据并移除最前面的一个字节，用O(1)时间就可以计算出new从下一个位置开始blockSize大小的数据的adler32值。
将old的块adler32校验值储存在一个hash表中，key为old块adler32值，value为old块序号index和其强校验值； new的当前roll-adler32值在hash表中查找匹配，adler32值相等的情况下，再计算出当前new数据块的强校验值，看是否和old块的强校验值相等。注意：这里用强校验值的相等来代替了数据的相等。
服务端遍历完new数据后，就能得知哪些new数据已经能在客户端找到，而哪些new数据需要传递给客户端。完成该diff过程后将匹配信息和缺失的new数据形成补丁包发送到客户端。为了减小需要传递的数据量，可以将补丁包压缩后传递。
客户端接收到服务端的补丁包后执行patch过程，来完成升级。

同步更新算法可以将任意old数据增量更新到new版本数据，不受old版本和是否修改的影响。但相比前面提到的常见增量更新算法来说，需要传输的补丁包数据较大。
另外，如果有大量客户端都需要升级，服务端的压力可能会比较大，diff算法和补丁包压缩都会非常消耗时间和资源。（对于大规模发布，可以考虑缓存补丁包的方案，相同的old数据只需要计算一次补丁包。）
另外，因为是重服务端，所以容易被"攻击",客户端可以轻易的生成随机校验数据提交来让服务端忙不过来，而缓存也对此无效。

zsync 同步更新算法原理

zsync 调整了 rsync 中服务端和客户端的职责，让服务端变轻，而客户端承担更多计算。
服务端计算最新版本new数据的块滚动校验值和强校验值，生成.zsync文件。
客户端下载块校验值文件，执行比较复杂的diff算法，在自己的old数据中查看哪些块已经有了，而哪些块需要从服务端下载。
客户端下载缺失的块和自己old中已有的块合并，从而增量更新到最新的new版本。

为了减小下载量，.zsync文件中的滚动校验值(32bit)和强校验值(128bit)并不需要完全保存，而是根据允许增量更新失败的几率和校验值碰撞几率，计算出需要的总bit数；从而大大减小.zsync文件的大小。 另外：可以额外存储new文件的单个完整强校验值，从而捕获到设定机率下会发生的同步失败。

服务端和客户端的通信比较简单，用http(s)/1.1协议就可以支持。服务端只需要计算一次生成新版new数据的.zsync文件，和新版new数据文件一起提供文件下载就可以了。而客户端下载.zsync文件后执行diff过程，然后利用http的多区域请求来下载缺失的块。
需要注意：个别CDN下载服务器为了防止多区域的请求攻击，只支持单区域请求。这就需要客户端在下载缺失块的时候每次只请求下载一个区域(hsynz支持)；这样处理会放大下载流量，可以适当增大blockSize块大小来降低放大比例。

下载的数据也可以支持压缩。zsync在服务端一次性的用zlib库分块压缩new数据得到一个标准的gzip格式的文件(hsynz也支持)提供下载；并在.zsync文件中存储每个块压缩后在该gzip文件中的编码偏移位置。 客户端按偏移位置描述从服务端的gzip文件中下载到当前缺失块对应的压缩编码数据，结合本地未压缩数据和已经解压的数据作为前缀字典解压出当前的块数据。

hsynz 同步更新算法的设计和实现

• hsynz 类似于 zsync，但速度更快，补丁可以更小；用同步算法完成增量更新，可用于大规模发布。
• 除了支持源和目标为文件，还为文件夹(目录)的同步更新提供了支持
• 服务端和客户端都支持多CPU并行加速
  对服务端和客户端占用时间大的函数添加了多线程并行支持。
  服务端的并行加速包括对new数据块计算滚动校验信息和强校验信息、带前缀的块压缩；
  客户端对diff算法进行了并行化，而同步通讯过程默认没有提供多线程下载的支持。
• 用自己设计的滚动校验算法falder64替代了adler32
  adler32值的碰撞概率远大于理论最优值1/2^32，有效位数只有约29bit，用其校验固定并较小长度的数据时碰撞概率更大，而每次无效的错误匹配的速度惩罚却很严重。
  falder64用一个查表替换了adler32的一个除法，速度更快，并且有效位数约63bit，截断到约定的更小bit数时碰撞概率也比adler32低很多倍。
• 用xxh128校验算法(默认)替代了md4(或md5)强校验算法
  默认的xxh128校验速度比md4(或md5)快很多倍。
  另外 也支持选择用md5、sha256或sha512作为强校验算法。
• 替换掉了hash表，优化查询速度
  diff过程占用了同步算法中大量的时间，而其中大量时间消耗在了hash查询过程中。
  hash表的key存储了new数据的块滚动校验值，一般查询为O(1)平均复杂度； 这已经很快，但我们还能做到更快，可以快出很多倍！
  • 可以将 new数据的块滚动校验值放在一个数组中进行排序，加上二分查找，就能完整替换掉hash查询功能。数据在内存中的结构布局也更简单。
    但这样做后速度反而会变慢，因为二分查找是O(log(n))复杂度。
  • 使用bloom过滤器，过滤掉无效查询
    我们在遍历old数据时会产生大量的滚动校验值来触发查询；而这些值中大部分是无法查询到的无效值。那我们可以利用bloom过滤器来提前过滤掉这大部分的无效查询。只有命中过滤器的滚动校验值才触发实际的二分查询。
  • 在二分查找之前建立一个缓存表，优化查询速度
    对于二分查询本身，我们还可以用一个缓存来优化其速度；根据滚动校验值的有效bit数据的部分高bit位，建立一个缓存数组； 当一个具体的滚动校验值进来后，截取其高位bit值查询该缓存得到该滚动校验值在原数组中的上下界，从而极大缩短二分查找需要查询的数组长度。
  • 二分查询后，如果相同滚动校验值非常多时，可以限制计算强检验的最大次数(可能会放弃少量匹配机会)来优化最差情况下的速度。
  • 另外当前old数据匹配new块成功时，也可以选择跳过blockSize的长度(可能会放弃少量匹配机会)，从而减少需要检查的滚动校验值数量，优化速度。
  • 记录new中那些完全相同的数据块信息，当old数据匹配到其中1块成功时，也一同标记new中数据相同的那些块。
• 除了支持zlib压缩，也提供 zstd 压缩支持，从而进一步减少需要传输的数据量，解压缩也更快
  注意：不是任意压缩算法都适合用于这种同步更新的提前压缩场景。
  • 直接同步更新伪过程：
    服务端: 最新版本数据B; 将B按2K大小分块; 分块校验信息都存储在infoB。
    客户端: 老版本数据A; 下载infoB, 用diff算法得知哪些块需要从服务端下载。
    假设B中的数据块为： [a,b,c,d,e,f,g,h]
    在本地的A中发现已有块 [a,b,c,e,f]; 客户端需要从服务端下载d,g,h;
    如果 d,g,h 是未压缩的，那下载后，很容易就能将A升级到B。
  • 为了节省需要传输的数据量，服务端可以选择单独压缩每一个数据块，而且只需要这样执行一次。
    服务端: 压缩的B [az,bz,cz,dz,ez,fz,gz,hz]; 其中 az=compress(a), bz=compress(b),…
    客户端: 从服务端下载dz,gz,hz, 并解压 d=decompress(dz),g=decompress(gz),h=decompress(hz); 那将A升级到B也比较简单。
  • 但单独压缩每一个小块，压缩率并不好；我们可以将每个块前面的未压缩数据当作字典，来极大提高数据压缩率。而且服务端同样只需要执行一次。
    服务端: 压缩的B [ap,bp,cp,dp,ep,fp,gp,hp]; 其中 ap=compress(a,prefix()), bp=compress(b,prefix(a)),…,gp=compress(g,prefix(b,d,e,f)),hp=compress(h,prefix(d,e,f,g));
    注意：现在的压缩算法前缀字典可能会非常大，dictSize很可能是以MB为单位，这可能远大于块大小blockSize的KB级，所以要求压缩算法的时间复杂度应该是接近O(blockSize)，而不能是O(dictSize)；否则压缩时间上可能无法接受。
    客户端: 从服务端下载 dp,gp,hp, 并解压 d=decompress(dp,prefix(a,b,c)),g=decompress(gp,prefix(b,d,e,f)),h=decompress(hp,prefix(d,e,f,g));
    可以注意到，每当需要解压X块时, X的前缀总是可以准备好; 这些前缀数据可能是来源于本地未压缩数据 或者是从服务端下载并已经被解压缩。所以将A升级到B也没有问题了，并且传输的数据得到了很好的压缩。
  • zsync当时也是对zlib库进行了少量修改后才能支持的。而hsynz用的较新版本zlib的api接口可以“拼凑”出需要的接口，从而不需要修改zlib库。而zstd默认提供的接口也不能很好的支持该需求，而是fork了zstd库进行了少量修改，添加出了需要的接口。