分类 猪在写代码 下的文章

[译]最终一致性

前几天在网上看到了这篇amazon CTO Werner Vogels的文章,讲分布系统最终一致性的,特意翻过来,学习

Eventually Consistent – Revisited

最终一致

By Werner Vogels

http://www.allthingsdistributed.com/2008/12/eventually_consistent.html

I wrote a first version of this posting on consistency models about a year ago, but I was never happy with it as it was written in haste and the topic is important enough to receive a more thorough treatment. ACM Queue asked me to revise it for use in their magazine and I took the opportunity to improve the article. This is that new version.

一年前我首次发表这篇关于一致性模型的文章,但郁闷的是那篇文章写得太仓促,而且这个主题很大,本应该投入更多精力。ACM Queue(一本很牛B的杂志,ACM办的,http://queue.acm.org/ )希望我能够修改一下这篇文章,他们杂志可以用。我答应了他们,一举两得,这样还可以有机会去完善我的文章。以下是这篇文章的新版本。

Eventually Consistent - Building reliable distributed systems at a worldwide scale demands trade-offs between consistency and availability.

最终一致——在世界范围搭建一个可靠的分布式系统,就要求我们在一致性和可用性上进行权衡,取舍。

At the foundation of Amazon's cloud computing are infrastructure services such as Amazon's S3 (Simple Storage Service), SimpleDB, and EC2 (Elastic Compute Cloud) that provide the resources for constructing Internet-scale computing platforms and a great variety of applications. The requirements placed on these infrastructure services are very strict; they need to score high marks in the areas of security, scalability, availability, performance, and cost effectiveness, and they need to meet these requirements while serving millions of customers around the globe, continuously.

创建亚马逊云计算的时候我们的定位是,一个像亚马逊S3(Simple Storage Service)、Simple DB和EC2(Elastic Compute Cloud)一样的基础设施,他可以提供资源,搭建全网范围的计算平台和大量应用。对这些基础设施的要求是很苛刻的,他们需要在安全性、伸缩性、可用性、性能和性价比上都有上佳的表现,而且要知道,所有的这些要求是建立在不间断的为全球数百万用户提供服务的基础上的。

Under the covers these services are massive distributed systems that operate on a worldwide scale. This scale creates additional challenges, because when a system processes trillions and trillions of requests, events that normally have a low probability of occurrence are now guaranteed to happen and need to be accounted for up front in the design and architecture of the system. Given the worldwide scope of these systems, we use replication techniques ubiquitously to guarantee consistent performance and high availability. Although replication brings us closer to our goals, it cannot achieve them in a perfectly transparent manner; under a number of conditions the customers of these services will be confronted with the consequences of using replication techniques inside the services.

在这些服务的背后是一个存在于世界范围的庞大的分布系统。这种庞大的规模带来很多额外的挑战,由于当一个系统要处理数以万亿计的请求时,正常情况下的小概率事件在这里就可能被认为是必然事件,而且要在设计和构建系统之前就考虑到。考虑到这些系统是世界级规模的,我们无处不在使用冗余技术来保证一致性能和高可用性。虽然冗余让我们更容易达成目标,但这不是一个完美的,清晰的方法;在大量不相同的条件下,这些服务的用户将会面临服务内部冗余技术带来的不良结果。

One of the ways in which this manifests itself is in the type of data consistency that is provided, particularly when the underlying distributed system provides an eventual consistency model for data replication. When designing these large-scale systems at Amazon, we use a set of guiding principles and abstractions related to large-scale data replication and focus on the trade-offs between high availability and data consistency. In this article I present some of the relevant background that has informed our approach to delivering reliable distributed systems that need to operate on a global scale. An earlier version of this text appeared as a posting on the All Things Distributed weblog in December 2007 and was greatly improved with the help of its readers.

解决这个问题的一个途径就是在系统提供的数据一致性类型中声明自己,尤其是当底层分布式系统为数据冗余提供最终一致性模型的时候。在亚马逊设计这些大规模系统,我们使用了一系列的定向原理和大规模数据冗余的抽象关系,并且关注高可用性和数据一致性之间的取舍。本文我提到了一些有关背景,这些是我们即将应用在全球规模的分布式系统上的。本文2007年12月,较早的那个版本在读者的帮助下有了很大的提高。

- 阅读剩余部分 -

如何写出高性能的MySQL查询

想写这样一篇文章很久了,但始终没有下手。最近帮同事看了几个查询,而且自己也在考虑一个索引系统的问题,所以今天就把这个写了。介绍一下MySQL的索引机制,还有一些MySQL查询的优化策略。鄙人才疏学浅,很可能说的不对,请路过的各位大侠批评指正,献丑了。

首先,说说MySQL的索引存储方式。MySQL的索引一般是B-Tree的结构存储的,内存表也有Hash索引,但是内存表的出镜率似乎已经低到了用“可怜”来形容的程度,所以我们只考虑B-Tree索引。
然后说说MySQL的联合索引。联合索引对于一个DBMS总是非常重要的,因为每一条SQL语句的条件子句是单条件的可能性很小,大多数情况下为组合条件,因此对于组合索引的依赖也就很强。MySQL对于联合索引的创建规则通过一个例子说明:
对于一个在列:col_a, col_b和col_c上的联合索引,MySQL会建立

index(col_a), index(col_a, col_b)和index(col_a, col_b, col_c)

这样三个索引。

介绍完一些基本原理,我们来看MySQL对于索引的选取规则和索引的建立原则(这些规则都是个人总结的,多来源于互联网,也有自己的经验)
对于单个索引,一般来说MySQL的查询优化器总能在若干查询条件中选取效率较高的一个使用,所以不必投入太多精力,一般来说查询容易出现的问题容易出现在联合索引。这里以一个两列的索引为例,说明一些问题。
例如:

idx_a_b (col_a, col_b)

建立做和索引的列进行or组合不可使用索引
例如:有条件

col_a = val_a or col_b = val_b

这个条件,是不可以使用idx_a_b索引的。然而同样的查询对于却可以使用这样的索引idx_a(col_a)或者idx_b(col_b)的,因此在建立索引的时候就要考虑到出镜率最高的条件是什么,建立怎样的索引。而如果同时存在idx_a和idx_b两个索引的话,MySQL也只会选择一个使用,尽可能使用索引把结果集缩小,再在这个结果集中遍历,使用其他条件筛选。
联合索引对非前缀列不生效
例如:条件col_b = val_b这个条件是不会使用这个索引的,因为索引idx_a_b的前缀列是col_a。因此在建索引的时候,就要注意到,是否有很多使用这种条件的查询,需要为col_b单独建立索引。
对于组合索引,遇到范围查询则放弃使用剩余部分
例如:条件

col_a = val_a and col_b = val_b

是可以使用整个索引,而对于

col_a between val_a_left and val_a_right and col_b = val_b

这个条件,只会使用索引的col_a这一部分,不会使用整个索引。对于这样的查询,我们有一个优化策略,若col_a是一个离散变量,则建议使用in代替between,例如,

col_a between 1 and 5 and col_b = val_b

建议写成

col_a in (1, 2, 3, 4, 5) and col_b = val_b

这样是可以使用整个idx_a_b的。

现在能想到的对于组合索引的使用就这些,还远远不够全面,不过了解了这些原理,一般的查询都是可以分析的。接下来介绍几个策略性的SQL优化。
尽量少的选择列数
选择你需要的列,不用图省事就直接写个select *,一来是为了减少通信的开销,再有就是如果你所选的列,都建立索引,那么这次查询就不会对表数据进行任何操作,只查索引,就返回。
减少count(*), group by, distinct这样的操作
这三种操作将进行大量的计算,对数据库服务器造成很大压力,而且很慢。这样的查询能避免就避免,能缓存就缓存。
对于limit offset,若offset值较大,则采用分割结果集策略
limit offset操作一般用于翻页,当offset值较小的时候直接使用limit offset效率搞,但当offset值增大到一定程度,这个查询效率就会骤然降低。建议在大offset的情况下,采取这个策略:缓存上一次结果的尾数据,在新的查询中不使用offset,直接根据缓存结果进行查询。
例如:

select * from tb limit 100 offset 500000;

offset值很大,建议这样做:缓存上一次结果的主键值id=id_val,sql改写为:

select * from tb where id>id_val order by id limit 100

这条sql的效率将比上一条高很多倍。

策略性的优化也姑且先想到了这么几条,很不全面。综合上面的这些查询优化策略,我们还有几个提高性能的系统配置和管理策略。例如:
定期重建索引
一张表用的时间久了,数据频繁更新,索引碎片会很多,降低查询效率,重建索引可以整理这些碎片,大大提高查询和写入的效率。
配置恰当的query_buffer
如果你的机器有足够大的内存,那多分给MySQL一点吧,在一台8G内存的机器上,我们一般会分给MySQL 4到6个G,query的缓存会给你带来惊喜的。
选择恰当的引擎
常用的MySQL引擎有Innodb和MyISAM,前者更稳定且支持行级锁,后者处理一般查询效率更高。二者各有特点,一般我们会使用主从策略,主Innodb,从MyISAM的做法。
在恰当的时候分表或分库
MySQL很强大,但对于200到300万以上的数据进行处理,性能就开始有明显的下降了,因此一般到这个数量级,就建议拆分数据了。
别让查询链接阻塞
MySQL可以配置连接的超时时间,这个时间如果做得太长,甚至到了10min,那么很可能发生这种情况,3000个链接都被占满而且sleep在哪,新链接进不来,导致无法正常服务。因此这个配置尽量配置一个符合逻辑的值,60s或者120s等等。

当下能想到的也就是这些~~略显肤浅,不过就写到这里吧,希望可以抛砖引玉,给大家一个优化MySQL的建议。

关于库与框架的思考

周六去参加了D2论坛,嘉宾都是大牛,Baidu的金大为,Tencent的甄焱鲲,去了Douban的克军,Taobao的明城,还有Koubei的秦歌。大家都讲了很多,有很前沿的技术,也有高屋建瓴的理念,但似乎都没有造成太大的振动。只是回来以后脑子里过这一整天听到的东西,对克军讲的从YUI的升级看前端演化有一些想法,对框架与库的概念。也不扯那些冠冕的东西,胡乱引用别人的东西了,就说说我对这两个东西的理解。
所谓库,一个应用的封装集合,旨在增强代码复用,简化开发者的工作。对于开发者,要做的只是找到一个适合自己的库,所谓适合就是说这个库能提供你所期望的输出,了解这个库所要求的输入规则。应用的时候,就把自己的数据按照约定组织,传给库,库将返回你期望的结果,则直接使用这个返回数据就OK了。
所以框架,是一种代码结构的约定和一些为了工程代码的框架代码,旨在让工程代码条理清晰,更易维护,可读性更强,更高的层次,安全性更高,扩展性更强等。对于开发者,适合与不适合之说,并不确切,而是有了很多主观因素,比如开发者对一个框架的代码结构设计是否同意等。使用一个框架,需要了解这个框架的约定和运行机制,然后依据这个框架的约定组织自己的代码。
不论是从存在的意义还是应用方式上,库和框架有非常明显的区别,但江湖上流传的各种框架,各种语言的似乎都对这两个概念稍有混淆,尤其是PHP框架,库和框架混淆比较严重,主流的那些框架,提供各种功能,数据验证器,认证码生成器等等,十分完整,十分强大。也包括我参与的KiwiPHP还有他的升级版lotusphp,都有这种现象。
我认为对于一个好的框架来说,或者用框架这个词并不准确,是框架和库的组合体,作为这样一个东西,要造福PHP开发者,应该把框架和库这两个部分清晰的拆分开,并提供一种有机的组合方式,实现方便的库订制服务,这样一来,所有的库都可以以插件的方式集成进来,扩展性可以大大提高,而且对于框架使用者只需订制自己需要的一些库,使用起来更加轻量,效率也更高。
刚词说道框架和库的组合体,想到一个词:平台,但又感觉平台这个词太大了,一个平台需要提供一项工作所需要的一切服务。针对开发来说,框架和库是远远不够的,还有包括测试工具,IDE等等很多东西。
以上就是我对框架和库的一点个人看法,之后的一段时间,我想我会试着做一些跟这个相关的事吧,有进展了再来回报。

微软LiveLabs Pivot浏览器试用

Pivot是Microsoft Live Labs研发的新一代浏览器,进入live labs的官网(http://livelabs.com/),首页第一个项目就是Pivot(http://www.getpivot.com/),官方说只可以在英文版的Win7上进行安装。今天终于拿到了Pivot的安装码,于是安装试用。大家都知道Live Labs最擅长的是图形处理,所以对这款新一代浏览器的UI我还是抱了很大的期望。

安装过程还是很顺利,只是后边导入IE数据的时候有些慢,因为平时几乎不用IE,所以本来数据就很少,但仍然倒了好几分钟,我个人分析可能是Pivot在对这些数据进行必要的分析和数据结构重组。

安装完成打开Pivot,第一感觉就是:这完全不是IE。淡蓝色的主界面风格,非常的干净,清爽,没有Windows标题栏,顶端就是导航栏,主体是像chrome一样的历史记录的豆腐块,最底下是一派按钮,主页、历史记录以及标签栏还有推荐的Collections。

打开一个Google日历,因为这个有很多JS,来测试一下Pivot对JS的解析效率,并跟Chrome做一些对比。从感观上,打开速度貌似 Pivot要快一点,但运行起来似乎Chrome更加流畅,但差别并不明显,不仔细感觉是感觉不到的。从这一点上看,Pivot跟IE比绝对是一个质的提升。

但打开两三个大JS页面以后,就突然觉得机器有点卡了,于是打开任务管理器去看。Pivot会给每一打开的页面,分配一个渲染器(TridentHostServer),独立于一个Pivot主进程之外。页面有动作的时候这个渲染器就会占用大量的CPU和内存。于是我拿新浪体育的首页做测试,这个页面的数据比较多,而且效率不高,我觉得适合测试。当浏览页面的时候,渲染进程会占用50%的CPU,也就是跑慢一个核。内存大概在 60M上下,而主进程却占用了130M左右的内存。从这个角度讲,Pivot的性能远远未达到可以发布的程度,还有很长的一段路要走。

浏览简单的看完以后,看历史记录的一些操作,可以说Pivot把浏览记录的分类和搜索带到了一个新的层次,否则他们不会把主页按钮旁边这么重要的位置给历史记录。历史记录有两种浏览视图,列表方式和缩略图,又可以按照网站,搜索记录,日期和浏览数来进行分类,而且可以把每个页面细化到最小粒度,另外还可以使用各种条件进行搜索。这是功能上,UI上做的就更到位了,支持放大缩小,带惯性滑动等,让人感觉这中浏览体验就是为多点触控屏而生的。到这里,稍微有点了解微软只支持win7的意思了。

这两个比较引人注目的功能之后,就是一些小的设计,很有意思。比如地址栏左边的一个GO按钮,这里提供了历史记录,标签和筛选的快捷方式,相比 chrome只能通过快捷键或打地址的方式更加傻瓜了,也就更友好。还有就是前进和后退的缩略图预览,更加直观。还有就是主界面左侧的导航栏,是IE的经典风格,不知道是为了照顾用户是习惯还是什么。另外,这个版本的Pivot还提供了Tips功能,打开Tips几乎在每一个地方都会有个气泡,告诉你这是什么,干啥用的。

Pivot是一个款很强大的浏览器,跟Bing整合又非常紧密,而且UI也一改之前的风格,并且加入了很多先进的UI技术,但目前来看这种为每一个页面开启一个渲染器进程的设计,似乎是有些霸道,占用了太多太多的系统资源,当然我们相信微软会在以后的时间里,对这个渲染器进行大量优化,使之能用。

总的来说,Pivot是一款值得期待的产品,是一款可以跟当前的Chrome媲美的产品(我的意思是如果Chrome仅仅是浏览器的话)。

最后,附上我的安装码,还剩下9次:1CAA E85C 1C96 99A6。大家可以在第一段里给出的地址去下载。

【补充】另外一个邮箱申请的也到了,这个可以用10次:A6BF E975 FADF A133

貌似我很少给微软说好话,但这个Pivot的确让我打心里期待,哈哈。

约瑟夫问题的解答

约瑟夫问题是一个很臭名昭著的算法题,今天闲着没事在网上乱逛,又看到了这个问题,在大脑里搜索,记忆中已经找不到这个算法的描述了,于是乎从0开始又做了一遍。这里是一个比较传统的算法,对题目描述的完全模拟,比较笨,复杂度姑且认为是o(n)吧。之后我会考虑江湖上曾经盛传的一个逆向思维的算法,貌似效率要好一点,我做出来了再写文章。

闲言少叙,说归正传。问题描述(来自互联网):n个人围成一圈,每人有一个各不相同的编号,选择一个人s作为起点,然后顺时针从1到k数数,每数到k的人退出圈子,圈子缩小,然后从下一个人继续从1到k数数,重复上面过程。求最后推出圈子的那个人原来的编号x。

解题思路(来自我本人):这明显是个循环问题,而且是可知的有限循环,循环次数n-1,所以就for吧。

一般来说从正向去考虑,头脑中出现如下场景:就是n个人排排坐,然后随便找个人,告诉他数1,然后他就数,接下来按照顺时针或者逆时针方向走下去,数了一圈又一圈,知道有个倒霉蛋数到k,当然他也可能是幸运儿,如果最后剩下的那个要被扔到河里之类的。基本就是这么个思路,然后按照数据结构的思想去建模,应该是个头尾相接的链表,然后元素被一个一个的拿掉。

至于算法,首先我需要构造一个n个人的数组,为了图省事,我把它做成2维的,如下:

1 => 1 => 1

2 => 2 => 2

3 => 3 => 3

...

n => n => 4

这是一张map,第一列是下标是内存偏移量,不可变,或者变起来麻烦,所以有了第二列,作为序号;第三列数字是这n个人的原始编号。这样构造数组的原因是,在运算过程中,人会不断的减少,所以序列的序号会变,我们变第二列,而最后我们需要知道这个人的原始序号,直接从第三列读取就OK了。

其实还有个办法就是把每次序号变化记录下来,这样会节约空间,但是我认为这些都不是核心的东西,所以无所谓,就这么办吧,如果有人追求完美可以搞一下。

然后就是从中一个一个的把元素抽掉,我们完全模拟题目描述:

设有n个人,编号为0,1,2...n-1,数1的人的编号是s,最后数到k的人出局(n,s和k是整数, -1< s

则,第一轮出局的人的编号是o (o = s + (k % n) - 1),此人出局;进入下一轮计算:s = o + 1,让o他之后的人编号向前滑动一个,覆盖o,n -= 1。根据新的s和k值进行计算,依此循环,直到n=2的时候,那个最后留下的人x = s,然后通过s的地址去那个2维数组里找到相应的号码就OK了。

以上就是这个最本,最直接的算法:写出来就是一个for(;n>1;n++) 的一个循环,具体的代码实现就不写了,很简单,有兴趣的同学可以试试。

接下来想一想那个江湖上盛传的一个逆向解答的,就是从n=2开始的算到n=n,这个算法的复杂度貌似会更低,稍后奉上,敬请期待。