54chen解读NoSQLDynamo

本文已经首发于InfoQ中文站,版权所有,原文为《解读NoSQL技术之作Dynamo》,如需转载,请务必附带本声明,谢谢。
InfoQ中文站是一个面向中高端技术人员的在线社区,为Java、.NET、Ruby、SOA、敏捷、架构等领域提供及时而有深度的资讯、高端技术大会如QCon、免费迷你书下载如《架构师》等。
NoSQL在过去的一年里,逐渐已经成为了家喻户晓的东西,我(54chen)自从去年开始人人网的NoSQL系统Nuclear的研发以来,一直看着NoSQL越来越热,越来越引来大家的围观。受infoQ霍师傅之托,特作此文,一来作过去一年的总结,二来希望以平白的话语对NoSQL系统在国内的发展献绵薄之力。

1.我眼中的两种模式

NoSQL其实并不是什么妖魔鬼怪,相反的,NoSQL的真谛其实应该是Not Only SQL,其产生是在数据量和访问量的增大下,人为地去添加机器、切分数据到不同的机器,变得越来越困难,人力成本越来越高,于是便开始有了这样的项目,本意是提高数据存储的自动化程度,减少人为干预的时间,让负载更加均匀。在国际上,真正的之作有来自的 BigTable 和Amazon 的Dynamo,他们分别使用了不同的基本原理。

1.1 MapReduce

这是最久的一种模型,典型的是BigTable。Map表示映射,Reduce表示化简。MapReduce通过把对数据集的大规模作分发给网络上的每个节点实现可靠性(Map);每个节点会周期性的把完成的工作和状态的更新报告回来(Reduce)。大多数分布式运算可以抽象为MapReduce作。Map是把输入Input分解成中间的Key/Value对,Reduce把Key/Value合成最终输出Output。这两个函数由程序员提供给系统,下层设施把Map和Reduce作分布在集群上运行。

1.2 dynamo

我把dynamo专门归纳成为了一种,的确是这样的,它与MapReduce不同,自成一派。来说,Amazon于2006年推出了自己的云存储服务S3,2007年其CTO公布了S3的设计方案,从此江湖中就不再太平了,开源项目一个个如雨后春笋般地出现了。比较常见的有开发的Cassandra(如果没有记错,在去年来到他们的项目网页的时候,上面还写着他们之中的一个开发人员是dynamo的设计人员,现在风头紧了,去掉了),还有linkedin的voldemort,国内的话,有豆瓣网的beansDB,人人网的nuclear等等。这次主要讲的也是dynamo的方案细节。

2.入门基础
Dynamo的意思是发电机,的确,这一整套的方案都像发电机一样,源源不断地提供服务,永不间断。以下内容看上去有点教条,但基本上要理解原理,这每一项都是必须知道的。

2.1 CAP原则
先来看,Eric A. Brewer教授,Inktomi公司的创始人,berkeley大学的计算机教授,Inktomi是雅虎搜索现在的台端技术核心支持。最主要的是,他们(Inktomi公司)在最早的时间里,开始研究分布计算。CAP原则的提出,可以追溯到2000年的时候(可以想象有多么早!),Brewer教授在一次talk中,基于他运作inktomi与在伯克利大学里的经验,总结出了CAP原则(后附当年的slide)。图2.1来自Brewer教授当年所画的图: cap 图2.1

Consistency(一致性),数据一致性,简单的说,就是数据复制到了N台机器,如果有更新,要N机器的数据是一起更新的。
Availability(可用性),好的响应性能,此项意思主要就是速度。
Partition tolerance(分区容错性),这里是说好的分区方法,体现具体一点,简单地可理解为是节点的可扩展性。

定理:任何分布式系统只可同时满足二点,没法三者兼顾。
忠告:架构师不要将精力浪费在如何设计能满足三者的完美分布式系统,而是应该进行取舍。

2.2 DHT

DHT(Distributed Hash Table,分布式哈希表),它是一种分布式存储寻址方法的统称。就像普通的哈希表,里面保存了key与value的对应关系,一般都能根据一个key去对应到相应的节点,从而得到相对应的value。
这里随带一提,在DHT算法中,一致性哈希作为第一个实用的算法,在大多数系统中都使用了它。一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。至于一致性哗然的细节就不在这里详细说了,要指明的一点是,在Dynamo的数据分区方式之后,其实内部已然是一个对一致性哈希的改造了。

3.进入Dynamo的世界

有了上面一章里的两个基础介绍之后,我们开始进入Dynamo的世界。

3.1 Dynamo的数据分区与作用

在Dynamo的实现中提到一个关键的东西,就是数据分区。
假设我们的数据的 key 的范围是0到2的64次方(不用怀疑你的数据量会超过它,正常甚至变态情况下你都是超不过的,甚至像伏地魔等其他类Dynamo系统是使用的2^31-1),然后设置一个常数,比如说1000,将我们的key的范围分成1000份。然后再将这1000份key的范围均匀分配到所有的节点(s个节点),这样每个节点负责的分区数就是1000/s份分区。
如图3.1,假设我们有A、B、C三台机器,然后将我们的分区定义了12个。 dynamo数据分区 图3.1

因为数据是均匀离散到这个环上的(有人开始会认为数据的key是从1、2、3、4。。。这样子一直下去的,其实不是的,哈希计算出来的值,都是一个离散的结果),所以我们每个分区的数据量是大致相等的。从图上我们可以得出,每台机器都分到了三个分区里的数据,并且因为分区是均匀的,在分区数量是相当大的时候,数据的分布会更加的均匀,与此同时,负载也被均匀地分开了(当然了,如果硬要说你的负载还是只集中在一个分区里,那不是这里讨论的问题了,有可能是你的哈希函数是不是有什么样的问题了)。

为什么要进行这样的分布呢,分布的好处在于,在有新机器加入的时候,只需要替换原有分区即可,如图3.2所示: dynamo数据分区 图3.2

同样是图3.1里的情况,12个分区分到ABC三个节点,图3.2中就是再进入了一个新的节点D,从图上的重新分布情况可以得出,所有节点里只需要转移四分之一的数据到新来的节点即可,同时,新节点的负载也伴随分区的转移而转移了(这里的12个分区太少了,如果是1200个分区甚至是12000个分区的话,这个结论就是正确的了,12个分区只为演示用)

3.2 从Dynamo的NRW看CAP法则

在Dynamo系统中,第一次提出来了NRW的方法。
N - 复制的次数
R - 读数据的最小节点数
W - 写成功的最小分区数
这三个数的具体作用呢,是用来灵活地调整Dynamo系统的可用性与一致性的。
举个例子来说,如果R=1的话,表示最少只需要去一个节点读数据即可,读到即返回,这时是可用性是很高的,但并不能保证数据的一致性,如果说W同时为1的话,那可用性更新是最高的一种情况,但这时完全不能保障数据的一致性,因为在可供复制的N个节点里,只需要写成功一次的话就返回了,也就意味着,有可能在读的这一次并没有真正读到需要的数据(一致性相当的不好)。如果W=R=N=3的话,也就是说,每次写的时候,都保证所有要复制的点都写成功,读的时候也是都读到,这样子一定读出来的数据是正确的,但是这中间的性能大打折扣,也就是说,数据的一致性非常的高,但系统的可用性却非常低了。如果R + W > N能够保证我们“读我们所写”,Dynamo推荐使用322的组合使用可。
Dynamo系统的数据分区让整个网络的可扩展性其实是一个固定值(你分了多少区,实际上网络里扩展节点的上限就是这个数),通过NRW来达到另外两个方向上的调整。

3.3 Dynamo的一些增加可用性的补救
针对一些经常可能出现的问题,Dynamo还提供了一些解决的方法。
第一个是hinted handoff数据的加入:在一个节点出现临时性故障时,数据会自动进入列表中的下一个节点进行写作,并标记为handoff数据,在收到通知原节点恢复时重新把数据推回去。这能使系统的写入成功大大提升。
第二个是向量时钟来做版本控制:用一个向量(比如说[a,1]表示这个数据在a节点第一次写入)来标记数据的版本,这样在有版本冲突的时候,可以追溯到出现问题的地方。这可以使数据的最终一致成为可能。(Cassandra未用vector clock, 而只用client timestamps也达到了同样效果。)
第三个是Merkle tree来提速数据变动时的查找:使用Merkle tree为数据建立索引,只要任意数据有变动,都将快速反馈出来。
第四个是Gossip协议:一种通讯协议,目标是让节点与节点之间通信,省略中心节点的存在,使网络达到去中心化。提高系统的可用性。

关于作者
54chen(陈臻),人人网分布式存储研究人员,业余时间混迹于各技术组织且乐此不疲。目前关注实施PHP培训。对flex等前端技术有一点研究。个人技术站点:http://www.54chen.com/ 。可以通过电子邮件 cc0cc@126.com 联系到他。

参考的网站
http://project-voldemort.com/
http://cassandra.apache.org/
http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf
http://timyang.net/data/dynamo-flawed-architecture-chinese/
http://www.cs.berkeley.edu/~brewer/
http://www.54chen.com/document/dynamo-based-systems.html
http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf
http://en.wikipedia.org/wiki/Distributed_hash_table
http://en.wikipedia.org/wiki/Consistent_hashing

跨系统共享键盘鼠标利器分享:synergy

世界杯马蜂窝 是这样的张总, ?在家里的电脑上按了CTRL+C,然后在公司的电脑上再按CTRL+V是。。。肯定不行的。即使同一篇文章也不行。不不,多贵的电脑都不行。

--题记

端午归来,特此总结,实现上述难题,靠一利器:synergy

此利器可打通mac\linux\windows任意两者的联系,使两个系统共享鼠标和键盘。下面以ubuntu 10.04与盗版windows XP为例。

首先,在ubuntu下面,建立服务端。
#sudo apt-get install synergy quicksynergy
#quicksynergy
启动后如图所示: synergy 只需要填写上下左右中的某一个位置修改成另一台机器的机器名,点击执行,常驻运行即可。

然后,在windows下面,安装客户端。
Synergy 1.3 Client
安装运行后如图: Synergy 1.3 输入Ubuntu机器的ip地址,点Start即可连上两机。

连上之后,可以撤掉在你办公桌面上的一个键盘,鼠标移动到哪个桌面上,键盘针对哪个系统输入,非常好用,还支持复制粘贴,对上班时候用两台电脑的同学非常适用。

端午,,图

啥也不说了,下面上图。 老婆

老婆

老婆

老婆

54chen

一场技术的圣战:rose开源框架之portal

作者:人人网架构师 王志亮

(54chen按:此文为客座博文,王志亮大侠,人人网架构师,疱丁分词创始人,rose是他的另一开源大作。关于69圣战,请看http://zhidao.baidu.com/question/158643718.html?si=2&wtp=wk

2010年的69日是一个圣战的日子,零点一到就有人开始,好戏也如约在晚上7点发生。人人网战场是SJ的公共主页:http://page.renren.com/sj

 

对不同人,这个日子意味着不同,滋味也不同。作为人人网技术团队,我们要保证服务能力、用户体验能够应付得了这个挑战。

 

某一个服务器的能力总有限,为了应付突然增长的读写量,web服务架构、内部服务架构、数据库架构等要能够轻松通过服务器调配来满足。就web服务器而言,我们增加了1倍的机器。现在再回头来看监控的数据,一切显得美好。这个期间整个服务做到了服务能力没有中断。除此之外,在这次圣战中,其中还有一项我们独有的技术起到了重要的作用:rose portal ,下面作一个介绍:

 

图1是sj的主页:

 

图1 sj在人人网的公共主页

这个页面分为三列:

  • 左边有 “推荐给好友”、“基本信息”、“相册”;
  • 中间有“给SJ留言”、“好友留言”;
  • 右边有“好友”,“人人的用户还关注”等。

在后台,这些被分解为不同的模块,我们称之为”window”。这每一个window都意味着可能连接一个的服务集群,比如基本信息服务、留言服务、好友服务、相册服务等等。这样,一个公共主页就等于多个的、可配置的window模块组成,如图2所示 :

图2 公共主页的window模块组成

随着伟大圣战的深入,这个页面就变成这样(右边的栏目不见了),如图3所示

图3 圣战进行中时模块的自动保护

产品同学看到此情此景,仍然很开心:“只要留言的window能在,其它的没在不要紧”

但是不一会,继续恶化,如图4所示:

图4 圣战进行中压力进一步增加

甚至到了图5的情形:

 

图5 圣战进行中压力进一步增加

看着公共主页呈现出这种状况时,笑着形容这样的图“缺胳膊少腿”:“怎么还没加机器”。当公共主页技术团队把机器逐步增加一倍的时候,这种情况变少了,甚至就没有了。

虽然这些页面看起来“缺胳膊少腿”,但要知道在以前,这种情况,我们整个页面的某个模块堵了可会导致用户浏览器长期空白,直至最后提示网页不可显示。这给用户带来很不好的体验,同时因为网页一直不释放连接,恶性循环导致web服务器最后全哑了。

好在,早在半年前我们开发了rose portal框架,解决了此问题,rose portal是一个服务端portal技术,基于rose框架 (也就是servlet容器) 下的服务端portal技术,rose portal不是Java常说的portlet技术,也不是基于ajax的客户端portal技术。

rose poral提供这些特性;

  1. 能够将一个页面分为多个窗口;
  2. 开发者使用一个主控制器,在主控制器中不断通过portal.addWindow方法,将请求并发转发给多个窗口;
  3. 每个窗口有单独的控制器处理逻辑、可以返回视图就像一个web请求一样;
  4. 框架能够处理并发转发并发逻辑处理并发渲染,并最后统一返回把html输出给浏览器;
  5. 提供了“整体超时控制”手段,使得某个窗口因一时服务能力下降时不影响整个页面的输出;

 

这里有一个portal开发示例:

http://code..com/p/paoding-rose/wiki/Rose_Portal_Demo

 

献上现在最新的sj主页(2010/6/10 10:46作为结束,如图6,目前粉丝 粉丝 21w+、留言146w+,谢谢(另感谢李伟博同学,以上图片均是他收集的)

 

图6 最新的sj主页

Ubuntu 10.04 LTS版本下的Empathy MSN群聊显示昵称方法

54chen ubuntu empathy msn

1.关系普及

Empathy是个托,python-papyon是个python实现的msn库,telepathy-butterfly是个完成msn功能的python客户端。

2.修改办法

sudo vim /usr/share/pyshared/papyon/conversation.py
查找 if message_type == 这个字符串
找到内容为:
if message_type == 'text/plain':
msg = ConversationMessage(unicode(message.body, message_encoding),
TextFormat.parse(message_formatting),
self.__last_received_msn_objects)
try:
display_name = message.get_header('P4-Context')

将if判断后try之前中间定义msg这一堆内容修改为如下:

try:
msg = ConversationMessage(unicode("["+message.get_header('P4-Context')+"]"+message.body, message_encoding),
TextFormat.parse(message_formatting),
self.__last_received_msn_objects)
except KeyError:
msg = ConversationMessage(unicode(message.body, message_encoding),
TextFormat.parse(message_formatting),
self.__last_received_msn_objects)

保存后重新启动empathy,msn群里就能显示昵称鸟。

empathy

点击此处下载我的conversation.py文件

下载下来后执行:

chen@54chen:~$ gunzip conversation.py.gz
chen@54chen:~$ sudo cp conversation.py /usr/share/pyshared/papyon/

我的版本是:Empathy 2.30.1

参加mongodb Workshop

29号,星期六,参加了在ThoughtWorks办公室举行的mongodb workshop。
主讲者Peter Membrey,是个年轻有为的牛人,17岁就获得了RHCE。
这是一个很小团体的技术会议,人数没有超过20人,来参加的都是有名气的牛人们。会上认识了腾讯超群大侠(还不忘记为他们招聘挖人吼一声),以及甲骨文的秋大侠(给人很文雅的感觉:)),以及来自鲜果和新浪的两位大侠(sorry,两位都没带名片,叫不上名字来~hoho~)
Peter的讲话是全英文的,只能听懂一半,另一半完全靠ppt上的内容。。。不过并不妨碍我们交流~~
ThoughtWorks的办公室是非常nice的。。。有图有真相。。。(图从网上找的,忘记现场拍照了)
这是厨房 有点吧台的样子 thougtworks

这是书架,沿着边上全是 thoughtworks

这是办公的地方,没有格子 thoughtworks

另外,创建了一个group,欢迎对no-sql架构有兴趣一起进行深入探讨的同志加入 http://groups..co.nz/group/dynamo_china 目前已经看到豆瓣的洪强宁大侠加进来了,更多的大侠正在加入中。。。