Hash tree (tiger tree)在大量文件实时同步中的应用

April 3, 2011 by
Filed under: algorithm 

大型集群系统常需要进行多个服务器的大量文件的内容同步。

传统的文件同步方案有rsync(单向) 和 unison(双向)等,它们需要扫描所有文件后进行比对,差量传输。文件扫描计算摘要是非常耗时的,我用rsync同步maven中央仓库的内容,每次同步都要花至少几十分钟的时间计算本地的文件摘要后,才会开始从远程取新的内容。

在受控的服务器(有权限管理)的环境中,可以通过Hash Tree,就是tiger tree来实现变化文件的同步。 Sun的ZFS,Amazon的Dynamo中都有用到这种结构。

可参考
http://en.wikipedia.org/wiki/Hash_tree

http://blog.daviesliu.net/2008/04/24/sync/

简言之,Hash Tree是将所有数据的摘要信息存储成树状结构,每个节点的Hash是其所有子节点的Hash的Hash,叶子节点的Hash是其内容的Hash。这样一旦某个节点发生变化,其Hash的变化会迅速传播到根节点。需要同步的系统只需要不断查询根节点的hash,一旦有变化,顺着树状结构就能够在logN级别的时间找到发生变化的内容,马上同步。

Linux下可利用2.6内核的新特性inotify来自动感知某个目录内文件发生变化的信息,当应用程序感知到变化时,更新Hash tree的所有父节点。Windows下可使用文件系统的hook来感知文件的变化。

在需要同步时,若发现根目录的Hash值有变化,顺着目录结构往下找即可有变化的文件,再做同步。

Digg This
Reddit This
Stumble Now!
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

Comments

Comments are closed.