大量小文件的实时同步的解决方案分析

传统的文件同步方案有rsync(单向) 和 unison(双向)等，它们需要扫描所有文件后进行比对，差量传输。如果文件数量达到了百万甚至千万量级，扫描所有文件将非常耗时。而且正在发生变化的往往是其中很少的一部分，这是非常低效的方式。

之前看了amazon的dynamo的设计文档，它们每个节点的数据是通过hash tree来实现同步，既有通过日志来同步的软实时特点(msyql, bdb等)，也可以保证最终数据的一致性(rsync, unison等)。hash tree的大体思路是将所有数据存储成树状结构，每个节点的hash是其所有子节点的hash的hash，叶子节点的hash是其内容的hash。这样一旦某个节点发生变化，其hash的变化会迅速传播到根节点。需要同步的系统只需要不断查询跟节点的hash，一旦有变化，顺着树状结构就能够在logn级别的时间找到发生变化的内容，马上同步。

文件系统天然的是树状结构，尽管不是平衡的数。如果文件的修改时间是可靠的，可以表征文件的变化，那就可以用它作为文件的hash值。另一方面，文件的修改通常是按顺序执行的，后修改的文件比早修改的文件具有更大的修改时间，这样就可以把一个目录内的最大修改时间作为它的修改时间，以实现hash tree。这样，一旦某个文件被修改，修改时间的信息就会迅速传播到根目录。

一般的文件系统都不是这样做的，目录的修改时间表示的是目录结构最后发生变化的时间，不包括子目录，否则会不堪重负。因为我们需要自己实现这个功能，利用linux 2.6内核的新特性inotify获得某个目录内文件发生变化的信息，并把其修改时间传播到它的上级目录(以及再上级目录)。python 有 ，watch.py的代码如下：

代码如下:
在已经有hash tree的时候，同步就比较简单了，不停地获取根目录的修改时间并顺着目录结构往下找即可。需要注意的是，在更新完文件后，需要设置修改时间为原文件的修改时间，目录也是，保证hash tree的一致性，否则没法同步。mirror.py的代码如下 

代码如下: 
如果源文件不在同一台机器上，可以通过nfs等共享过来。或者可以通过支持列目录的http服务器来访问远程目录，mirror.py 已经支持这种访问方式。server.py 是用webpy做的一个简单的只是列目录的文件服务器。由于瓶颈在io上，它的性能不是关键。server.py的代码如下：

代码如下:
为了获得更好性能，以达到更好的实时性，hash tree最好是平衡的，比如btree。如果一个文件发生变化，同步它需要进行的io操作为n*m，其中n为数的层数，m为每层的文件数目。现在我们n为2，m最大为10000，适当减少它可以获得更好的性能，比如n为4，m为100。在以后创建目录结构时，最好能够考虑这方面的因素。

之前hongqn推荐过一个，同步方式类似于mysql和bdb等，由于过于复杂导致不可靠而没有采用。上面这个方案只用了一百多行python代码就基本解决问题了，是不是很帅？:-)