文章出處

傳統的文件同步方案有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代碼就基本解決問題了,是不是很帥?:-)


歡迎轉載:http://www.kanwencang.com/bangong/20161104/41068.html

文章列表




Avast logo

Avast 防毒軟體已檢查此封電子郵件的病毒。
www.avast.com


arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()