Rsync
之前了解了一下rsync的内部算法，记个笔记。
假设有两台机器A，B。A上和B上共享了同一份文件old。如果我们在A上编辑了这个文件，并需要B上的文件也同步，那么我们必须将A上修改后的文件new发送给B。
但是假如文件是一个视频，非常大，但是我们可能仅仅编辑了其几帧的画面，换言之实际上改变的二进制数据量非常少。这样的话，我们通过网络发送整个文件性价比就非常低，而且浪费的的流量也是难以承受的。
假如A上有old的备份，我们可以利用一般的diff算法计算得到增量，并仅发送增量包，这样可以节省流量，但是假如没有old的备份，我们自然也不可能要求B将old发送过来。rsync中的算法就可以用于解决这个问题，下面讲讲rsync的流程。
首先我们要求B将文件old切分为块，每一块的大小为B。每一块大小一致，除了最后一块。之后我们为每一个文件块都计算摘要，使用两种摘要算法，分别是弱摘要和强摘要。弱摘要使用滚动算法计算。
之后B将所有块对应的两种摘要和偏移都发送到A机器上。之后A得到old上每一块的摘要后，将摘要置入哈希表中。之后A开始处理new中的二进制数据。通过滚动算法计算窗口的弱摘要，如果在哈希表中包含对应的弱摘要，我们就再计算窗口的强摘要，之后再利用强摘要来比对找出new窗口对应old中块的偏移。之后我们追加一个命令copy 偏移量，之后窗口向后平移一个块的距离。如果没有在old中找到对应的块，就直接发送窗口头部的第一个字节，之后窗口右平移一个字节。
之后A将变相的增量包发送到B，让B根据命令列表在old上做一系列操作更新old到new。由于两边网络交互的主要内容均是摘要和操作，因此耗费的流量将大大减少。