基于diff的文件同步算法

Qter

https://www.jianshu.com/p/1d889fb14ca3
1.写在前面文件同步的核心问题是新旧版本的对比问题。这里所说的版本是指用于区分文件变更的一种状态标记，它可以是我们通常所说的版本号，也可以是时间戳，如修改时间。本文介绍一种基于diff的文件同步算法，共分为两篇，上篇介绍diff算法的服务端实现，下篇介绍diff算法的客户端实现。
2.算法概述从客户端的角度来看，文件同步的本质是本地文件集合与云端文件集合的对比。从实现角度来讲，客户端会保存一份云端文件集合的快照，通过将快照和云端集合对比可以计算出云端文件变更，通过将快照和本地集合对比则可以计算出本地文件变更。对于本地文件的变更，需要将文件提交至云端；对于云端文件的变更，需要将文件同步至本地。对于文件同步在云端和本地都有修改的情况下，就需要进行冲突处理。
如果每个同步周期需要获取云端文件集合，文件量小还可以接受，文件量一大，对带宽和服务器压力都会存在瓶颈，而且很多文件可能根本就没有变更，这会造成很多无效的对比，浪费计算资源。所以需要一种增量机制，用于增量拉取云端变更的文件。
diff算法是利用修改时间作为增量机制，其核心是每次diff时会记录下当前diff的时间戳，客户端下次diff时，带上上次diff时返回的时间戳（通常将时间戳编码到cursor中），这样就能增量获取到一段时间内的变更记录了。由于每次diff的变更文件集合可能非常大，所以需要进行分页操作，有两个主要的问题需要解决：

• 首次diff问题
• 用时间维度获取变更记录时，如(t1, t2]之间的文件变更，由于t1、t2通常是使用秒作为精度，每次分页diff出的文件记录时，如果存在闭区间t2时刻文件记录，则无法判断t2时刻是否存在更多的记录。
  

3.全量同步首次diff通常发生在客户端本地快照没有数据且第一次请求时，这种情况通常指全量同步。服务器在处理全量同步时是希望尽量将当时请求时刻以内的所有文件数据都分页吐给客户端。由于时间戳存在增量同步的问题，可以使用文件惟一标识迭代出全量数据。如果记文件的惟一标识为fid，修改时间为mtime，分页大小为pagesize，SQL查询具体做法为：
select fields from file_meta where fid>last_fid and mtime<=stime sort by fid ASC limit pagesize；
其中：

• stime是第一次全量同步时，记录下当前请求的时间戳，主要是明确一个时间限界内的全量数据，防止在全量同步过程中又出现新的变更；
• last_fid为最近一次查询结果中最后一条记录的fid，首次查询last_fid为0；
• 判断是否有更多数据通常采用多取一条记录进行判断；
• 由于并不知道全量同步过程中是否有新的文件变更，需要进行一次增量同步；
  

4.增量同步前面说到在按时间维度进行增量同步时，由于需要分页，并不知道闭区间内是否有更多文件变更记录。举个粟子，当我们查询出(t1, t2]的文件集合时，如果恰好有几个文件的修改时间等于t2，而且本次分页并没有拉取完。下次diff时会查询(t3, t4]时间区间内的文件（t3>t2)，由于上次并没有拉取完，即t2时间可能还有更多数据，如果直接查询(t3, t4]时间区间的文件，那么可能会丢失t2时间的文件记录。
对于以上情况，当查询(t1, t2]时间区间内的文件时，针对返回的文件，我们需要对最后一秒的文件进行单独处理。如果返回的文件的修改时间均是在一秒内，那么称为单秒增量同步，其它情况称为正常增量同步。
4.1.正常增量同步对于正常增量同步虽然所有文件的mtime不是在同一秒内，但需要处理最后一秒问题，就像前面的例子，当分页未完成时，我们没办判断最后一秒是否还有更多数据，所以一个简单的做法是从本次查询的文件记录中，从最后一个文件开始，移除mtime相同的文件，即把最后一秒的文件留到下次进行查询。当最后一秒的文件足够多，比如超过一个分页时，就会触发单秒增量同步。正常增量同步查询SQL表示：
select fields from file_meta where mtime>t1 and mtime<=t2 sort by mtime DESC limit pagesize;
4.2.单秒增量同步单秒增量同步是指查询一秒内的文件记录，这种查询比较简单，如果用SQL表示如下：
select fields from file_meta where mtime=xxx sort limit pagesize;
5.其它工程问题在工程实现上还需要注意很多问题，比如主从同步、频率控制、数据重置等。
5.1.主从同步对服务器来讲，文件数据的存储量通常都比较大，不可能采用单机就能搞定，一般都会采用分布式进行存储，对于分布存储就会存储主从同步问题。当写操作完成后，马上读取，如果主从同步未完成，并不能读取出数据。所以在diff的时间滑动窗口中，需要做一定的延迟处理，延迟时间肯定需要大于主从同步的时间。
5.2.频率控制对于diff接口，可能会调用的比较频繁，如果不进行频率控制，高峰期时可能会造成雪崩效率，diff接口需要有降级和频控处理。diff接口一般来说是一种后台行为，并不需要进行实时调用，当客户端进行增量同步时，如果在一段很短的时间内连续调用，应触发频控策略。
5.3.数据重置由于客户端会缓存云端数据快照，如果客户端存在脏数据，将导致同步算法失败。服务器应该和客户端约定一种数据重置机制，当服务器端数据升级或出现脏数据时，服务端可以下发数据重置命令，客户端收到数据重置命令后应该清空本地缓存，重新进行全量同步。
6.总结diff算法需要处理全量同步和增量同步的情况。全量同步按照文件id维度排序分页下发；增量同步按照时间维度分页下发，由于分页原因以及时间精度问题，不能判断最后一秒内是否存在更多的数据需要查询，因为把最后一秒的数据进行单独查询。最后就是需要考虑一些工程上的问题，如主从同步、频率控制、接口降级、数据重置等问题。
--- 上篇完 ---



作者：AlgoPeek
链接：https://www.jianshu.com/p/1d889fb14ca3
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。