傳統的文件同步方案有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 有 pyinotify，watch.py的代碼如下：
#!/usr/bin/python
from pyinotify import *
import os, os.path
flags = IN_CLOSE_WRITE|IN_CREATE|IN_Q_OVERFLOW
dirs = {}
base = '/log/lighttpd/cache/images/icon/u241'
base = 'tmp'
class UpdateParentDir(ProcessEvent):
def process_IN_CLOSE_WRITE(self, event):
print 'modify', event.pathname
mtime = os.path.getmtime(event.pathname)
p = event.path
while p.startswith(base):
m = os.path.getmtime(p)
if m < mtime:
print 'update', p
os.utime(p, (mtime,mtime))
elif m > mtime:
mtime = m
p = os.path.dirname(p)
process_IN_MODIFY = process_IN_CLOSE_WRITE
def process_IN_Q_OVERFLOW(self, event):
print 'over flow'
max_queued_events.value *= 2
def process_default(self, event):
pass
wm = WatchManager()
notifier = Notifier(wm, UpdateParentDir())
dirs.update(wm.add_watch(base, flags, rec=True, auto_add=True))
notifier.loop()
在已經有Hash Tree的時候，同步就比較簡單了，不停地獲取根目錄的修改時間并順著目錄結構往下找即可。需要注意的是，在更新完文件后，需要設置修改時間為原文件的修改時間，目錄也是，保證Hash Tree的一致性，否則沒法同步。mirror.py的代碼如下
#!/usr/bin/python
import sys,time,re,urllib
import os,os.path
from os.path import exists, isdir, getmtime
src = sys.argv[1]
dst = sys.argv[2]
def local_mirror(src, dst):
if exists(dst) and mtime == getmtime(dst):
return
if not isdir(src):
print 'update:', dst
open(dst,'wb').write(open(src).read())
else:
if not exists(dst):
os.makedirs(dst)
for filename in os.listdir(src):
local_mirror(os.path.join(src,filename), os.path.join(dst,filename))
os.utime(dst, (mtime,mtime))
def get_info(path):
f = urllib.urlopen(path)
mtime = f.headers.get('Last-Modified')
if mtime:
mtime = time.mktime(time.strptime(mtime, '%a, %d %b %Y %H:%M:%S %Z'))
content = f.read()
f.close()
return int(mtime), content
p = re.compile(r'([/d.]+?) +([/w/]+)')
def remote_mirror(src, dst):
mtime, content = get_info(src)
if exists(dst) and mtime == int(getmtime(dst)):
return
print 'update:', dst, src
if not src.endswith('/'):
open(dst,'wb').write(content)
else:
if not exists(dst):
os.makedirs(dst)
for mt,filename in p.findall(content):
mt = int(float(mt))
lpath = dst+filename
if not exists(lpath) or int(getmtime(lpath)) != mt:
remote_mirror(src+filename, lpath)
os.utime(dst, (mtime,mtime))
if src.startswith('http://'):
mirror = remote_mirror
else:
mirror = local_mirror
while True:
mirror(src, dst)
time.sleep(1)
如果源文件不在同一臺機器上，可以通過NFS等共享過來。或者可以通過支持列目錄的HTTP服務器來訪問遠程目錄，mirror.py 已經支持這種訪問方式。server.py 是用webpy做的一個簡單的只是列目錄的文件服務器。由于瓶頸在IO上，它的性能不是關鍵。server.py的代碼如下：
#!/usr/bin/python
import os,os.path
import web
import time
root = 'tmp'
HTTP_HEADER_TIME = '%a, %d %b %Y %H:%M:%S %Z'
class FileServer:
def GET(self, path):
path = root + path
if not os.path.exists(path):
return 404
mtime = time.localtime(os.path.getmtime(path))
web.header('Last-Modified', time.strftime(HTTP_HEADER_TIME, mtime))
if os.path.isdir(path):
for file in os.listdir(path):
if file.startswith('.'): continue
p = os.path.join(path,file)
m = os.path.getmtime(p)
if os.path.isdir(p):
file += '/'
print m, file
else:
print open(path,'rb').read()
urls = (
"(/.*)", "FileServer",
)
if __name__ == '__main__':
web.run(urls, globals())
為了獲得更好性能，以達到更好的實時性，Hash Tree最好是平衡的，比如BTree。如果一個文件發生變化，同步它需要進行的IO操作為N*M，其中N為數的層數，M為每層的文件數目。現在我們N為2，M最大為10000，適當減少它可以獲得更好的性能，比如N為4，M為100。在以后創建目錄結構時，最好能夠考慮這方面的因素。
之前hongqn推薦過一個利用inotify的文件同步方案，同步方式類似于mysql和bdb等，由于過于復雜導致不可靠而沒有采用。上面這個方案只用了一百多行Python代碼就基本解決問題了，是不是很帥？:-)
