HASH GAME - Online Skill Game GET 300

　　随着信息时代的到来，分布式系统得到了广泛的应用，包括个人使用多台主机保存文件与数据，企业利用总部、分部服务器来运行业务数据等。个人由于工作场景、工作需求的不同使用多台主机工作，导致文件数据分散且难以同步更新。企业要求各分部服务器与总部服务器保持实时更新以及通过远程服务器备份来应对异常情况。大型企业及单位需要同步或备份的文件数据量较大且更新频繁，采用传统完全拷贝式同步或备份难以满足其要求。这些需求促使文件数据同步方法的发展［1-2］。目前，国内所进行的同类工作多为远程同步系统或文件备份架构的研究，针对文件数据同步算法的优化研究较少［3］。

　　基于差异的文件同步算法改进了传统文件同步中将文件库所有文件重新传输一遍的缺点［4］，在一定程度上提高了同步的效率。其中Rsync同步算法是被广泛使用的远程同步算法［5-6］，其核心方法是计算服务器端和客户端文件库的差异，以及通过差异计算对不同部分进行同步更新，保证两端文件的一致性。目前，国内外对于文件数据同步的研究主要是基于Rsync算法［7］。ZHANG等［8］提出一种新的增量同步方法SimpleSync，根据服务器端不主动修改云存储服务中备份文件的特点，去掉了Rsync中的冗余步骤，仅通过一次通信就可以实现客户端和服务器端之间的同步。该方法在计算差异部分时仍存在使用大量哈希算法的问题。IRMAK等［9］提出一种基于冗余码的新方法，通过对单轮协议的文件进行同步，以显著地改进Rsync算法。尽管这些方法都在实践中对Rsync进行改进以提升同步效率，但是都未从根本上减少同步过程中时间和资源的消耗。

　　本文提出一种基于操作系统的文件同步方法hcsync。通过对文件库进行差异监视，利用哈希链记录全部文件操作状态。由于有序哈希链的节点包含文件/目录的变化信息，并记录了相关操作的状态，因此通过哈希链的比较能快速找到变化的文件/目录，同时跳过没有变化的文件/目录，从而提高了同步效率［11-12］。链尾哈希值能满足快速验证文件库的变动情况和一致性。通过服务器端链尾哈希值判断文件库是否产生新的更新，利用客户端链尾哈希值判断链尾和服务器端的文件库是否保持一致性。由于哈希链会记录文件库的相关操作状态，因此使用者可以通过溯源哈希链查询认证或撤销某次操作。

　　近年来，哈希链技术的研究和应用在不断地拓展和丰富。HUANG等［15］提出一种基于哈希链的灾后恢复数据可用性监控方法，解决分布式系统中数据备份及数据恢复问题。MOTOHASHI等［16］提出一种基于区块链与客户端哈希链相结合的mHealth系统，确保医疗机构数据管理的安全性、可扩展性和可靠性。YE等［17］提出一种基于哈希链的可信DNP3-BAE广播认证加密协议，解决了广播模式下消息安全认证机制缺失的问题。ZHAO等［18］提出一种基于哈希链的跨境身份认证和隐私保护方案，通过哈希链的安全特性来管理网络中的数据信息。

　　常规策略过程如下：1）客户端将文件f数据分成没有重叠的m字节数据块，如果最后一块不足m字节，则填充为m字节；2）每个数据块分别计算强弱校验码，强校验码是通过可靠的哈希函数获得，并传输给服务器端；3）服务器端遍历搜索文件f1，产生强弱校验码并与客户端发送的强弱校验码进行对比，首先匹配弱校验和，如果相同说明是同一个数据块，如果强校验和也相等，则说明两个数据块相同，继续比较下一个数据块，如果不相等跳转到下一个字节，对数据块进行匹配，记录不匹配数据块索引与偏移量内容，直到得出所有偏移量内容，则停止比较［20］；4）在客户端获取服务器端的不匹配数据块索引和偏移量内容时，通过这些数据重组临时文件，使其内容与文件f1相同，当临时文件重组完成后，修改该临时文件的属性信息（权限、mtime等），然后将该临时文件替换客户端文件f，客户端文件f与服务器端文件f1保持同步。

　　基于哈希树的同步方法是根据文件库的目录结构构建有序哈希树，并利用此哈希树来获取文件库的变化并快速同步［21］。文献［22］提出的基于有序哈希树同步方法中，哈希树各节点由四元组＜p，Hash，firstChild，nextSibling＞表示。其中：p表示路径；Hash表示该节点存储的哈希值，在该方法中Hash值为路径与时间戳拼接进行运算的哈希值；firstChild为该节点的第一个子节点；nextSibling为该节点的后继兄弟节点。因为哈希树的构建过程是遍历目录树，依次计算子节点的哈希值，之后回溯到父节点，按顺序拼接子节点哈希值，并将拼接结果的哈希值作为父节点的哈希值。一旦文件库资料发生变化，其对应有序哈希树的根节点哈希值必定发生变化，如果根节点哈希值未发生变化，则文件库未产生新变化。这就是有序哈希树能快速检测和定位文件库变化的原理。

　　2）当两端哈希链链尾的哈希值不相等时，根据服务器端哈希链新增加的变化节点更新文件库。在执行当前哈希链节点变化操作时，需要对本节点进行哈希值验证，以保证哈希链的不可篡改性和完整性。如果o_type=0 为移动事件，客户端执行相同文件/目录移动操作；o_type=1 为新建事件，客户端同步该新文件至本地；o_type=2 为删除事件，删除客户端文件库的该文件/目录；o_type=3 为修改事件，删除本地文件并同步最新文件。

　　本文实验采用单层哈希链进行对比，使用的哈希函数为SHA-3，将客户端同步服务器端文件库的过程分为以下三种实验：1）当文件库未发生改变时，hcsync 与Rsync 同步时间效率对比；2）hcsync 与使用“quick check”策略的Rsync 同步时间效率对比；3）hcsync 与使用常规策略的Rsync 同步时间效率对比。当Rsync 使用独特的“quick check”策略时，可以实现快速同步备份数据的目的。实验一在文件库未变动时进行同步效率对比，补充了文件库同步时含有变动和未变动的情况。实验二和实验三分别对比两种策略下Rsync 的同步效率。

　　表3 所示为在不同环境下hcsync 与Rsync 的同步性能对比和htsync 与Rsync 的同步性能对比。在文件库未变动的情况下，hcsync、Rsync、htsync 都需要快速判断客户端与服务器端之间文件库的异同，如果未产生变化时便可结束更新，且hcsync 和htsync 都能较快地完成同步。从表3 可以看出，hcsync 和htsync 的平均加速比分别为94.85% 和3.63%。hcsync 和htsync 相较于Rsync 都不需要对文件库进行逐个文件对比，但htsync 需要对比哈希树与节点哈希值，导致时间延长。hcsync 只需对比链尾哈希值即可判断两端文件库的差别。

　　本文在文件库初始大小为0 和每次新增95 MB的条件下进行实验，当客户端文件库同步结束后，文件库大小分别对应为95 MB、190 MB、285 MB、380 MB、475 MB 和570 MB。Rsync使用“quick check”策略，对比两端文件大小与时间戳后进行同步。hcsync 与使用“quick check”策略Rsync 的同步性能对比如表4 所示。由于htsync 缺少关于“quick check”策略的同步效率，因此该实验不与htsync对比。

　　从图7 可以看出，Rsync 使用“quick check”策略的同步效率大幅增加，仅需要对大小和时间戳有改动的文件执行Rsync 具体同步操作。但是这种模式也有其相应的弊端，如果客户端的文件时间戳和大小与服务器端完全一致，但内容恰巧不一致时，在这种模式下Rsync 是无法发现文件库存在更新。因此，Rsync 的“quick check”策略能够减少同步时对比文件所消耗的资源，提升同步效率，但是却无法完全保证同步的完整性。在两端同步文件时，该策略下记录文件大小与时间戳的文件列表容易被窃取与篡改，存在同步的安全性与稳定性等问题。实验结果表明，相比使用“quick check”策略的Rsync，hcsync同步方法在效率上仍存在一定优势，平均同步加速比为6.5%。因此，基于有序哈希链的同步方法具有较优的完整性、稳定性且较高的效率。

　　hcsync 与htsync 同步效率都要高于Rsync，它们都避免了传统Rsync 中需要逐个对比文件数据的弊端，通过树形结构快速捕捉文件变化并进行同步。但哈希链与哈希树的区别在于：一个以时间顺序迭代哈希函数并不断延长链式结构，一个以目录结构创建的需要不断更新的树式结构。但哈希树的缺点是需要不断地维持和更新一个树形结构，即使是一个普通的文件更新，也需从叶子节点溯源到根节点并更新节点与哈希值。当文件库更新时，hcsync只需在哈希链上增加节点，对比两端哈希链节点h_id 即可获取并执行后续变化节点；htsync 则需要遍历比对两端哈希树定位到变化节点，然后从变化节点溯源到根节点并对这些节点进行更新。hcsync 在获取变化节点的效率与更新链式结构的效率上相较于htsync 与Rsync 有较大的提升。因此，hcsync 的同步时间均低于htsync 和Rsync，整体同步效率排序：hcsync＞htsync＞Rsync。