装修网站实景图vr怎么做的,品牌建设论文怎么写,兰州网站seo哪家公司好,平面设计教学视频1.写在前面
文件同步的核心问题是新旧版本的对比问题。这里所说的版本是指用于区分文件变更的一种状态标记#xff0c;它可以是我们通常所说的版本号#xff0c;也可以是时间戳#xff0c;如修改时间。本文介绍一种基于diff的文件同步算法#xff0c;共分为两篇#xff0…1.写在前面
文件同步的核心问题是新旧版本的对比问题。这里所说的版本是指用于区分文件变更的一种状态标记它可以是我们通常所说的版本号也可以是时间戳如修改时间。本文介绍一种基于diff的文件同步算法共分为两篇上篇介绍diff算法的服务端实现下篇介绍diff算法的客户端实现。
2.算法概述
从客户端的角度来看文件同步的本质是本地文件集合与云端文件集合的对比。从实现角度来讲客户端会保存一份云端文件集合的快照通过将快照和云端集合对比可以计算出云端文件变更通过将快照和本地集合对比则可以计算出本地文件变更。对于本地文件的变更需要将文件提交至云端对于云端文件的变更需要将文件同步至本地。对于文件同步在云端和本地都有修改的情况下就需要进行冲突处理。
如果每个同步周期需要获取云端文件集合文件量小还可以接受文件量一大对带宽和服务器压力都会存在瓶颈而且很多文件可能根本就没有变更这会造成很多无效的对比浪费计算资源。所以需要一种增量机制用于增量拉取云端变更的文件。
diff算法是利用修改时间作为增量机制其核心是每次diff时会记录下当前diff的时间戳客户端下次diff时带上上次diff时返回的时间戳通常将时间戳编码到cursor中这样就能增量获取到一段时间内的变更记录了。由于每次diff的变更文件集合可能非常大所以需要进行分页操作有两个主要的问题需要解决
首次diff问题用时间维度获取变更记录时如(t1, t2]之间的文件变更由于t1、t2通常是使用秒作为精度每次分页diff出的文件记录时如果存在闭区间t2时刻文件记录则无法判断t2时刻是否存在更多的记录。
3.全量同步
首次diff通常发生在客户端本地快照没有数据且第一次请求时这种情况通常指全量同步。服务器在处理全量同步时是希望尽量将当时请求时刻以内的所有文件数据都分页吐给客户端。由于时间戳存在增量同步的问题可以使用文件惟一标识迭代出全量数据。如果记文件的惟一标识为fid修改时间为mtime分页大小为pagesizeSQL查询具体做法为 select fields from file_meta where fidlast_fid and mtimestime sort by fid ASC limit pagesize其中
stime是第一次全量同步时记录下当前请求的时间戳主要是明确一个时间限界内的全量数据防止在全量同步过程中又出现新的变更last_fid为最近一次查询结果中最后一条记录的fid首次查询last_fid为0判断是否有更多数据通常采用多取一条记录进行判断由于并不知道全量同步过程中是否有新的文件变更需要进行一次增量同步
4.增量同步
前面说到在按时间维度进行增量同步时由于需要分页并不知道闭区间内是否有更多文件变更记录。举个粟子当我们查询出(t1, t2]的文件集合时如果恰好有几个文件的修改时间等于t2而且本次分页并没有拉取完。下次diff时会查询(t3, t4]时间区间内的文件t3t2)由于上次并没有拉取完即t2时间可能还有更多数据如果直接查询(t3, t4]时间区间的文件那么可能会丢失t2时间的文件记录。
对于以上情况当查询(t1, t2]时间区间内的文件时针对返回的文件我们需要对最后一秒的文件进行单独处理。如果返回的文件的修改时间均是在一秒内那么称为单秒增量同步其它情况称为正常增量同步。
4.1.正常增量同步
对于正常增量同步虽然所有文件的mtime不是在同一秒内但需要处理最后一秒问题就像前面的例子当分页未完成时我们没办判断最后一秒是否还有更多数据所以一个简单的做法是从本次查询的文件记录中从最后一个文件开始移除mtime相同的文件即把最后一秒的文件留到下次进行查询。当最后一秒的文件足够多比如超过一个分页时就会触发单秒增量同步。正常增量同步查询SQL表示 select fields from file_meta where mtimet1 and mtimet2 sort by mtime DESC limit pagesize;4.2.单秒增量同步
单秒增量同步是指查询一秒内的文件记录这种查询比较简单如果用SQL表示如下 select fields from file_meta where mtimexxx sort limit pagesize;5.其它工程问题
在工程实现上还需要注意很多问题比如主从同步、频率控制、数据重置等。
5.1.主从同步
对服务器来讲文件数据的存储量通常都比较大不可能采用单机就能搞定一般都会采用分布式进行存储对于分布存储就会存储主从同步问题。当写操作完成后马上读取如果主从同步未完成并不能读取出数据。所以在diff的时间滑动窗口中需要做一定的延迟处理延迟时间肯定需要大于主从同步的时间。
5.2.频率控制
对于diff接口可能会调用的比较频繁如果不进行频率控制高峰期时可能会造成雪崩效率diff接口需要有降级和频控处理。diff接口一般来说是一种后台行为并不需要进行实时调用当客户端进行增量同步时如果在一段很短的时间内连续调用应触发频控策略。
5.3.数据重置
由于客户端会缓存云端数据快照如果客户端存在脏数据将导致同步算法失败。服务器应该和客户端约定一种数据重置机制当服务器端数据升级或出现脏数据时服务端可以下发数据重置命令客户端收到数据重置命令后应该清空本地缓存重新进行全量同步。
6.总结
diff算法需要处理全量同步和增量同步的情况。全量同步按照文件id维度排序分页下发增量同步按照时间维度分页下发由于分页原因以及时间精度问题不能判断最后一秒内是否存在更多的数据需要查询因为把最后一秒的数据进行单独查询。最后就是需要考虑一些工程上的问题如主从同步、频率控制、接口降级、数据重置等问题。 作者AlgoPeek 链接https://www.jianshu.com/p/1d889fb14ca3 来源简书 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
