rsync 的核心算法

rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递归拷贝。rsync利用由Andrew Tridgell发明的算法。这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。

本来不想写这篇文章的,因为原先发现有很多中文blog都说了这个算法,但是看了一下,发现这些中文blog要么翻译国外文章翻译地非常烂,要么就是介绍这个算法介绍得很乱让人看不懂,还有错误,误人不浅,所以让我觉得有必要写篇rsync算法介绍的文章。(当然,我成文比较仓促,可能会有一些错误,请指正)

问题

首先, 我们先来想一下rsync要解决的问题,如果我们要同步的文件只想传不同的部分,我们就需要对两边的文件做diff,但是这两个问题在两台不同的机器上,无法做diff。如果我们做diff,就要把一个文件传到另一台机器上做diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。

于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就出现了rsync的算法。

算法

rsync的算法如下:(假设我们同步源文件名为fileSrc,同步目的文件叫fileDst)

1)分块Checksum算法。首先,我们会把fileDst的文件平均切分成若干个小块,比如每块512个字节(最后一块会小于这个数),然后对每块计算两个checksum,

一个叫rolling checksum,是弱checksum,32位的checksum,其使用的是Mark Adler发明的adler-32算法, 另一个是强checksum,128位的,以前用md4,现在用md5 hash算法。 为什么要这样?因为若干年前的硬件上跑md4的算法太慢了,所以,我们需要一个快算法来鉴别文件块的不同,但是弱的adler32算法碰撞概率太高了,所以我们还要引入强的checksum算法以保证两文件块是相同的。也就是说,弱的checksum是用来区别不同,而强的是用来确认相同。(checksum的具体公式可以参看这篇文章)

2)传输算法。同步目标端会把fileDst的一个checksum列表传给同步源,这个列表里包括了三个东西,rolling checksum(32bits),md5 checksume(128bits),文件块编号。

我估计你猜到了同步源机器拿到了这个列表后,会对fileSrc做同样的checksum,然后和fileDst的checksum做对比,这样就知道哪些文件块改变了。

但是,聪明的你一定会有以下两个疑问:

如果我fileSrc这边在文件中间加了一个字符,这样后面的文件块都会位移一个字符,这样就完全和fileDst这边的不一样了,但理论上来说,我应该只需要传一个字符就好了。这个怎么解决?

如果这个checksum列表特别长,而我的两边的相同的文件块可能并不是一样的顺序,那就需要查找,线性的查找起来应该特别慢吧。这个怎么解决? 很好,让我们来看一下同步源端的算法。

3)checksum查找算法。同步源端拿到fileDst的checksum数组后,会把这个数据存到一个hash table中,用rolling checksum做hash,以便获得O(1)时间复杂度的查找性能。这个hash table是16bits的,所以,hash table的尺寸是2的16次方,对rolling checksum的hash会被散列到0 到 2^16 – 1中的某个整数值。(对于hash table,如果你不清楚,建议回去看大学时的数据结构教科书)

顺便说一下,我在网上看到很多文章说,“要对rolling checksum做排序”(比如这篇和这篇),这两篇文章都引用并翻译了原作者的这篇文章,但是他们都理解错了,不是排序,就只是把fileDst的checksum数据,按rolling checksum做存到2^16的hash table中,当然会发生碰撞,把碰撞的做成一个链表就好了。这就是原文中所说的第二步——搜索有碰撞的情况。

4)比对算法。这是最关键的算法,细节如下:

4.1)取fileSrc的第一个文件块(我们假设的是512个长度),也就是从fileSrc的第1个字节到第512个字节,取出来后做rolling checksum计算。计算好的值到hash表中查。

4.2)如果查到了,说明发现在fileDst中有潜在相同的文件块,于是就再比较md5的checksum,因为rolling checksume太弱了,可能发生碰撞。于是还要算md5的128bits的checksum,这样一来,我们就有 2^-(32+128) = 2^-160的概率发生碰撞,这太小了可以忽略。如果rolling checksum和md5 checksum都相同,这说明在fileDst中有相同的块,我们需要记下这一块在fileDst下的文件编号。

4.3)如果fileSrc的rolling checksum 没有在hash table中找到,那就不用算md5 checksum了。表示这一块中有不同的信息。总之,只要rolling checksum 或 md5 checksum 其中有一个在fileDst的checksum hash表中找不到匹配项,那么就会触发算法对fileSrc的rolling动作。于是,算法会住后step 1个字节,取fileSrc中字节2-513的文件块要做checksum,go to (4.1) - 现在你明白什么叫rolling checksum了吧。

4.4)这样,我们就可以找出fileSrc相邻两次匹配中的那些文本字符,这些就是我们要往同步目标端传的文件内容了。

阅读全文 »

三种东西永远不要放到数据库里

我已经在很多演讲里说过,改进你的系统的最好的方法是先避免做“蠢事”。我并不是说你或你开发的东西“蠢”,只是有些决定很容易被人们忽略掉其暗含的牵连,认识不到这样做对系统维护尤其是系统升级带来多大的麻烦。作为一个顾问,像这样的事情我到处都能见到,我还从来没有见过做出这样的决定的人有过好的结果的。 图片,文件,二进制数据

既然数据库支持BLOB类型的数据,把文件塞进BLOB字段里一定没有错了!?错,不是这样的!别的先不提,在很多数据库语言里,处理大字段都不是很容易。

把文件存放在数据库里有很多问题: 对数据库的读/写的速度永远都赶不上文件系统处理的速度 数据库备份变的巨大,越来越耗时间 对文件的访问需要穿越你的应用层和数据库层

这后两个是真正的杀手。把图片缩略图存到数据库里?很好,那你就不能使用nginx或其它类型的轻量级服务器来处理它们了。 给自己行个方便吧,在数据库里只简单的存放一个磁盘上你的文件的相对路径,或者使用S3或CDN之类的服务。 短生命期数据

使用情况统计数据,测量数据,GPS定位数据,session数据,任何只是短时间内对你有用,或经常变化的数据。如果你发现自己正在使用定时任务从某个表里删除有效期只有一小时,一天或数周的数据,那说明你没有找对正确的做事情的方法。使用redis, statsd/graphite, Riak,它们都是干这种事情更合适的工具。这建议也适用于对于收集那些短生命期的数据。

当然,用挖土机在后花园里种土豆也是可行的,但相比起从储物间里拿出一把铲子,你预约一台挖土机、等它赶到你的园子里挖坑,这显然更慢。你要选择合适的工具来处理手头上的事。 日志文件

把日志数据存放到数据库里,表面上看起来似乎不错,而且“将来也许我需要对这些数据进行复杂的查询”,这样的话很得人心。这样做并不是一个特别差的做法,但如果你把日志数据和你的产品数据存放到一个数据库里就非常不好了。

也许你的日志记录做的很保守,每次web请求只产生一条日志。对于整个网站的每个事件来说,这仍然会产生大量的数据库插入操作,争夺你用户需要的数据库资源。如果你的日志级别设置为verbose或debug,那等着看你的数据库着火吧。

你应该使用一些比如Splunk Loggly或纯文本文件来存放你的日志数据。这样去查看它们也许会不方便,但这样的时候不多,甚至有时候你需要写出一些代码来分析出你想要的答案,但总的来说是值得的。 可是稍等一下,你是那片不一样的雪花,你遇到的问题会如此的不同,所以,如果你把上面提到的三种东西中的某一种放到了数据库里也不会有问题。不,你错了,不,你不特殊。相信我。

阅读全文 »

欧拉计划(Project Euler)

欧拉计划(Project Euler)是一个解题网站,站内提供了一系列数学题供用户解答,解题的用户主要是对数学计算机编程感兴趣的成年人及学生。目前该站包含了250多道不同难度的数学题,每一题都可以通过计算机程序在1分钟内求出结果。该网站自2001年起定期增加新的题目,每题都有对应的讨论区,注册用户在正确提交了某题的答案后才能进入该题的讨论区。 站内根据完成题目的数量将用户分为6个级别,设立了6个排行榜,并用正多面体球体来表示不同的级别。另外还设有一个欧拉人(Eulerians)排行榜。只有最新题目的前20位解答者才可以上榜。   我建立的google code地址:https://code.google.com/p/my-project-euler-code/

阅读全文 »

Python 的闭包和装饰器(转载)

Part I 原文地址: http://blaag.haard.se/Python-Closures-and-Decorators–Pt–1/ 回想起来,当初我做出了错误的选择,把 Python 的课程削减到了4个小时以至于把装饰器的部分搞砸了,我答应大家我稍后会对闭包和装饰器做一个更好的解说 —— 我是这么打算的。 函数也是对象。实际上,在 Python 中函数是一级对象——也就是说,他们可以像其他对象一样使用而没有什么特别的限制。这给了我们一些有趣的选择,我会由浅到深解释这个问题。 关于函数就是对象的一个最常见的例子就是 C 中的函数指针;将函数传递到其他的将要使用它的函数。为了说明这一点,我们来看看一个重复函数的实现 —— 也就是,一个函数接受另外一个函数以及一个数字当作参数,并且重复调用指定函数指定次数: #A very simple function def greeter(): … print("Hello") … #An implementation of a repeat function def repeat(fn, times): … for i in range(times): … fn() … repeat(greeter, 3) Hello Hello Hello 这种模式在很多情况下都有用 —— 比如向一个排序算法传递比较函数,向一个语法分析器传递一个装饰器函数,通常情况下这些做法可以使一个函数的行为 更专一化 ,或者向已经抽象了工作流的函数传递一个待办的特定部分(比如, sort() 知道怎么排序, compare() 知道怎么比较元素)。 函数也可以在其他函数的内部声明,这给了我们另一个很重要的工具。在一般情况下,这可以用来隐藏实用函数的实现细节: def print_integers(values): … def is_integer(value): … try: … return value == int(value) … except: … return False … for v in values: … if is_integer(v): … print(v) … print_integers([1,2,3,"4", "parrot", 3.14]) 1 2 3 这可能是有用的,但它本身并不算是个强大的工具。相比函数可以当作参数被传递而言,我们可以将它们包装(wrap)在另外的函数中,从而向已经构建好的函数增加新的行为。一个简单的例子是向一个函数增加跟踪输出: def print_call(fn): … def fn_wrap(*args, **args): #take any arguments … print ("Calling %s" % (fn.func_name)) … return fn(*args, **kwargs) #pass any arguments to fn() … return fn_wrap … greeter = print_call(greeter) #wrap greeter repeat(greeter, 3) Calling fn_wrap Hello Calling fn_wrap Hello Calling fn_wrap Hello greeter.func_name 'fn_wrap' 正如你看到的那样,我们可以使用带日志的函数来替换掉现有函数相应的部分,然后调用原来的函数。在例子的最后两行,函数的名字已经反映出了它已经被改变,这个改变可能是我们想要的,也可能不是。如果我们想包装一个函数同时保持它原来的名字,我们可以增加一行 print_call 函数,代码如下: def print_call(fn): … def fn_wrap(*args, **kwargs): #take any arguments … print("Calling %s" % (fn.func_name)) … return fn(*args, **kwargs) #pass any arguments to fn() … fn_wrap.func_name = fn.func_name #Copy the original name … return fn_wrap 因为这是一个很长的话题,我明天会来更新第二部分,我们会讲讲闭包,偏函数(partial),还有(终于到它了)装饰器。 至此,如果这些你之前全部没有接触过,可以先用 print_call 函数作为基础,来创建一个能够在正常调用函数之前先打印出这个函数名字的一个修饰器。 Part II 原文地址: http://blaag.haard.se/Python-Closures-and-Decorators–Pt–2/ 在第一部分中,我们学习了以函数作为参数调用其他的函数,还有嵌套函数,最终我们把一个函数包装在另外的函数中。我们先把第一部分的答案给出: def print_call(fn): … def fn_wrap(*args, **kwargs): … print("Calling %s with arguments: \n\targs: %s\n\tkwargs:%s" %fn.__name__, args, kwargs)) … retval = fn(*args, **kwargs) … print("%s returning '%s'" % (fn.func_name, retval)) … return retval … fn_wrap.func_name = fn.func_name … return fn_wrap … def greeter(greeting, what='world'): … return "%s %s!" % (greeting, what) … greeter = print_call(greeter) greeter("Hi") Calling greeter with arguments: args: ('Hi',) kwargs:{} greeter returning 'Hi world!' 'Hi world!' greeter("Hi", what="Python") Calling greeter with arguments: args: ('Hi',) kwargs:{'what': 'Python'} greeter returning 'Hi Python!' 'Hi Python!' 这稍微有那么点儿用了,但它可以变的更好!你可能听说过或者没有听说过*闭包*,你可能听说过成千上万种闭包定义中的某一种或者某几种 —— 我不会那么挑剔,我只是说闭包就是一个捕捉了(或者关闭)非本地变量(自由变量)的代码块(比如一个函数)。如果你不清楚我在说什么,你可能需要进修一下 CS 的相关课程,但是不要担心 —— 我会给你演示例子。闭包的概念很简单:一个可以引用在函数闭合范围内变量的函数。 比如说,看一下这个代码: a = 0 def get_a(): … return a … get_a() 0 a = 3 get_a ...

阅读全文 »

OOREDIS:一个 Pythonic 的 Redis 库

用Redis的朋友们应该会发现,Redis的很多客户端都只是Redis命令的一个简单包装。 举个例子,在Redis的Python客户端redis-py中,设置一个String键的方法如下: from redis import Redis r = Redis r.set('key_name', 'value') 而要取得一个列表的所有元素,则要使用lrange命令: r.lrange('list', 0, -1) 这种操作方式有几个问题: 1.大量的Redis命令聚在一起,妨碍了对客户端对象的使用。 2.每次操作都要将将key name和命令参数(比如lrange的0和-1)显式地传入方法当中,容易出错。 3.命令之间没有限制,可以互相覆盖而没有错误提示。 比如你可以用set命令覆盖一个Redis列表,Redis本身不会报错。 4.客户端没有利用到语言提供的方便机制。 比如r.lrange('list', 0, -1)在Python中就没有for item in list语句来得直观。 5.Redis只储存字符串值,虽然可以储存整数或浮点数,但每次取出值都要显式类型转换,很不方便。 --- 为了解决以上问题,更好地使用Redis,我用Python写了一个Redis库,基于redis-py,名叫ooredis。 ooredis有以下目标: 1.以Key对象为单位操作Redis的数据结构 在ooredis中,Redis的函数被按类型及作用归为了一个个Python类,每个ooredis类有不同的操作。 比如在ooredis中,将Redis的Hash类函数包裹成了Dict类型,它可以以类似Python内置dict类型的方式,操纵Redis数据。 又比如,Redis的List类函数,在ooredis中被包裹成了List类型,它可以以类似Python内置list类型的方式,操纵Redis数据。 如果ooredis类尝试覆盖不同类型的数据,ooredis将抛出异常。 这样就解决了包括命名空间污染、跨类型覆盖等问题。 2.提供一组Pythonic的API 刚才我们说“以类型Python内置的dict类型的方式来操纵Redis的Hash类型数据“,我们还没详细说明这是什么意思。 比如说,在ooredis中,你可以通过传给Dict类一个key name,之后就可以操纵这个Dict对象,来完成Redis中的各种命令,像这样: form ooredis import * project = Dict('ooredis-project') project['name'] = 'ooredis' project['version'] = 1.0 project['author'] = 'huangz' 以上的语句就相当于执行Redis的命令: redis HSET ooredis name ooredis redis HSET ooredis version 1.0 redis HSET ooredis author huangz 也可以用redis-py来完成上面的任务: r.hset('ooredis-project', 'name', 'ooredis') r.hset('ooredis-project', 'version', 1.0) r.hset('ooredis-project', 'autohr', 'huangz) 可以看到,使用Dict对象比单纯的Redis命令更直观。 又比如在Dict对象中,你可以用Python内置类型set的全部命令:items、keys、values、pop,等等。 project.items() [('name', u'ooredis'), ('version', 1.0), ('author', u'huangz')] 'version' in project True project.pop('name') u'ooredis' 不仅是Dict类,ooredis的所有类都大量使用了Python的魔法方法,致力于让Redis数据的操作更直观、清晰和Pythonic。 3.提供方便的类型转换机制 至于类型问题,ooredis通过使用传入TypeCase的方式,来对Redis数据进行类型转换。 比如如果你需要一个只保存整数对象(int/long)类型的列表,只需要这样做就可: numbers = List('numbers', type_case=IntTypeCase) 如果你需要一个只接受Json对象的字典对象,只需要使用以下语句: json_only_dict = Dict('json_dict', type_case=JsonTypeCase) 其中IntTypeCase和JsonTypeCase都是ooredis默认提供的TypeCase类之一,ooredis总共提供了以下常用TypeCase: GenericTypeCase,接受Python常量值,比如int,long,float,str和unicode。为了世界的和平与正义,传入的字符串值总被转换成unicode类型。 IntTypeCase,接受int和long。 FloatTypeCase,接受浮点数。 StringTypeCase,接受str和unicode类型的值,而且总被转换成unicode。 JsonTypeCase,接受所有可被转换成Json对象的值,比如Python的dict类型。 SerializeTypeCase,使用Pickle的dumps和loads,可以对Python的class进行序列化。 当然,除了以上的TypeCase之外,你也可以很方便地定义自己的TypeCase类,像如下代码: class MyTypeCase: @staticmethod def to_redis(value): pass @staticmethod def to_python(value): pass to_redis将值转换成Redis能接受的类型,to_python则将从Redis取出的数据转回原来的类型。 --- 好的,以上就是关于ooredis的基本介绍了,抱歉因为时间关系我不能写一篇更短的文章。 如果你对ooredis有兴趣,可以访问以下地址,获得更多信息: ooredis的更详细介绍,幻灯: http://bit.ly/rbgn3Z ooredis的项目主页: https://github.com/huangz1990/ooredis ...

阅读全文 »

__init__.py文件的用途

__init__.py 有两个用途 :

1、是表示目录下面的python 程序是module 的一部分

2、module 自身,module 自身以及submodule 的初始化、声明了。

例如:

--- breakfast

|

|- spam.py

|- toast.py

|- jam.py

 

包的结构:

package1/

__init__.py

subPack1/

__init__.py

module_11.py

module_12.py

module_13.py

subPack2/

__init__.py

module_21.py

module_22.py

  ……如果用户 import breakfast.spam 来引入 spam ,这样是不行的,因为在breakfast 目录下面没有 __init__.py 这个文件, 如果在breakfast 目录下面加入 __init__.py 就可以了。

阅读全文 »

python 菜谱(python cookbook) 1.4 字符串对齐

任务:实现字符串对齐:左对齐,居中对齐,或者右对齐 这就是字符串内置函数ljust,rjust,center所能实现的功能。函数类似于S.ljust(width[, fillchar]),默认的fillchar是空格,如果想指定填充字符的话,需要给出指定字符。 x=' hej ' print '|', 'hej'.ljust(20), '|', 'hej'.center(20), 'hej'.rjust(20)

阅读全文 »

PyCon 大会相关资料(视频+PPT)

会议PPT下载: http://cn.pycon.org/2011/schedule 洪强宁-豆瓣的Python应用和创新 http://www.tudou.com/programs/view/fvnGyGXTvLM/ Daniem-Scale web application stack with coro-thread http://www.tudou.com/programs/view/afNO_Yq1kLc/ 沈葳–Python通向未来之路 http://www.tudou.com/programs/view/Dx8LHWMvjps/ 潘俊勇-易度PaaS云开发平台技术内幕 http://www.tudou.com/programs/view/9BfMlTho_1A/ 土豆网黄冬-系统工程师的非专业课 计费与流量管理 http://www.tudou.com/programs/view/kGcDov8GxNM/ 陈正—Introduction_to_SAE_Python http://www.tudou.com/programs/view/iMP1dKMgJYc/ Ryan Ye-Schemaless-data-model-Pycon http://www.tudou.com/programs/view/M8Ku2upwdGg/ 首届中国Python2011大会Q A(1) http://www.tudou.com/programs/view/PXVBJY82JrM/ 李迎辉- Web框架开发思考与实践 http://www.tudou.com/programs/view/7ua4wTEQAac/ 首届中国Python2011大会Q A(2) http://www.tudou.com/programs/view/cWEM79vOYVg/ 赖勇浩-Python 之于 webgame 的应用 http://www.tudou.com/programs/view/PP4K6ZD2r-g/ 王剑锋-OpenERP二次开发 http://www.tudou.com/programs/view/f90a0p3-sQc/ 李俊东-与python一路走来 http://www.tudou.com/programs/view/DAmnmtfwHgQ/ 林君-用tornado搭建实时应用 http://www.tudou.com/programs/view/ATbooIAjpO0/ 王浩飞-openstack_pycon http://www.tudou.com/programs/view/Za52sDDCp-g/ 宋进亮-工程师职业规划探讨 http://www.tudou.com/programs/view/BomiVOnBBe4/ Steven Yang- Workend, where developer meets designer http://www.tudou.com/programs/view/0_VW4SENilQ/ 钟子飞-图形化大规模网络设备 http://www.tudou.com/programs/view/hJD2iyruUqY/ ...

阅读全文 »