Hycz's Blog

Life is a game. Why so serious?

Monthly Archives: August 2011

出现问题的原因总是因为冲突

如果所有的人都能心想事成,那么世界就美好了。

但是,这显然是不可能的,所以当两者对于同一件事都想心想事成时,冲突就发生了。而分布式系统中的很多问题都是来源于冲突。

比如Paxos中,关于Leader选举的冲突,不同的Acceptor对于同一个值同不同意的冲突,同一轮中收到的不同值之间的相互冲突,etc。比如在Cassandra中同时加入2台节点时,对于token ring分割的冲突。

也正是由于这些冲突的存在,才导致了实现的困难。冲突需要detect,冲突需要handle,最好还要non-blocking,于是所有可能发生冲突的地方都需要小心翼翼的实现。

 

Advertisements

Cassandra 0.8.0源码包简介

一、overall

这个是Cassandra 0.8.0在Eclipse中配置完毕之后的有关于源码的部分,截图如下:



在正确配置之后,这个工程中应该有7个文件夹,分别是(1)java源代码(src/java);(2)生成java源代码(src/gen-java);(3)thrift生成java源代码(interface/thrift/gen-java);(4)cql的jdbc源代码(drivers/java/src);(5)cql的jdbc测试代码(drivers/java/gen-java);(6)单元测试代码(test/unit);(7)长时间测试代码(test/long)。

虽然文件夹是这么多,其实可以对所有的代码分个类,第一类是纯源代码,第二类是生成代码,第三类是测试代码。如果按照产品进行分类的话,那么也可以分为:第一类是Cassandra服务器端,第二类是Cassandra的Cli,第三类是CQL的JDBC,不过这里依赖关系比较多,所以也不尽然。

二、生成代码(gen-java)

那么先从不太重要的讲起,生成代码。所谓生成代码,就是在src版本中不存在,而是在build的时候生成的代码,在src版本中只有关于这些内容的中间语言版本。我的理解是,这是为了跨语言,比如我现在用的是java,那么就把那中间语言翻译成java,然后生成相应的java文件进行使用。

在上述的代码中,src/gen-java和interface/thrift/gen-java中的代码都是生成代码。Cassandra现在看来真是一个庞然大物,糅合了各种技术在其中,这里的生成代码的技术就用到了3种。

  • Antlr
    这个东西主要是生成自己的语法解析器,简单来说,用之前的JLine进行命令行的IO,然后把获得的命令在这里与相应的函数进行关联。使用的包是lib文件夹下的antlr-3.2.jar。具体用法见这里:http://wenku.baidu.com/view/d8580e5f804d2b160b4ec074.html。在源代码中,下面2个包使用Antlr生成的:src/gen-java下的org.apache.cassandra.cliorg.apache.cassandra.cql,原始文件是src/java/org/apache/cassandra/cli/Cli.gsrc/java/org/apache/cassandra/cql/Cql.g。具体的生成顺序(根据build.xml中),首先是检查生成语法(check-gen-xxx-grammar),从一个*.g 文件生成一个*.token文件,比如,在CLI中,就是从Cli.g文件生成了Cli.token文件,然后生成语法解析器,用生成xxxLexer.java和xxxParser.java,比如,在CLI中,生成了CliLexer.java和CliParser.java。
  • Avro
  • Thrift
    Avro和Thrift放在一起讲,下面的话引自这里:http://www.webguo.com/2011/02/11/avro_vs_thrift.html。“Avro和Thrift都是跨语言,基于二进制的高性能的通讯中间件. 它们都提供了数据序列化的功能和RPC服务. 总体功能上类似,但是哲学不一样. Thrift出自Facebook用于后台各个服务间的通讯,Thrift的设计强调统一的编程接口的多语言通讯框架. Avro出自Hadoop之父Doug Cutting, 在Thrift已经相当流行的情况下Avro的推出,其目标不仅是提供一套类似Thrift的通讯中间件更是要建立一个新的,标准性的云计算的数据交换和存储的Protocol。 这个和Thrift的理念不同,Thrift认为没有一个完美的方案可以解决所有问题,因此尽量保持一个Neutral框架,插入不同的实现并互相交互。而Avro偏向实用,排斥多种方案带来的 可能的混乱,主张建立一个统一的标准,并不介意采用特定的优化。Avro的创新之处在于融合了显式,declarative的Schema和高效二进制的数据表达,强调数据的自我描述,克服了以往单纯XML或二进制系统的缺陷。Avro对Schema动态加载功能,是Thrift编程接口所不具备的,符合了Hadoop上的Hive/Pig及NOSQL 等既属于ad hoc,又追求性能的应用需求.”在源代码中,使用Avro生成的是以下3个包:src/gen-java中的org.apache.cassandraorg.apache.cassandra.db.migration.avro以及org.apache.cassandra.utils.avro,他们都是从文件src/avro/internode.genavro中生成的。在源代码中,使用Thrift生成的是interface/thrift/gen-java中的org.apache.cassandra.thrift包,原始文件是interface/cassandra.thrift文件。

三、测试代码(test/unit, test/long and drivers/java/test)

没什么好讲的,就是针对每个包中的代码的测试。

四、源代码(src/java and drivers/java/src)

src/java中有34个包,有内容的有33个。正如同Cassandra的论文中的行文结构一样,Cassandra其实没有什么层次性,甚至连系统架构图都没有,然后再看各个包的话,可以发现其实是针对一个分布式系统的不同方面的实现,比如在论文中的系统架构章节提到的几个部分:Partitioning,Replication,Membership,Bootstrapping,Scaling the Cluster,Local Persistence,还有一些其他的实现技术,比如SEDA等等。这几个部分算是系统的几个主要模块,但是包与包之间又不是简单的模块关系,反而更像是根据分布式系统各部分相关论文的技术而做的实现,然后再以一种粗暴的方法拼接在一起,不牢固的地方再加上其他的实现加以过度。当然,这是我粗看之下的愚见,不能作数,但是Cassandra其实算不上优雅,更像是一个缝合憎恶。

所以,将这些包分成几个大的部分比较好:

  • 存储和数据模型
    这个部分如同名字,其实应该分为2个部分,但是由于这两部分的实现过于紧密(比如SStable和Memtable的实现就在不同的包中),只好归为一类。作为最底层的部分,存储部分的主要参照是Bigtable中的SStable+Memtable模型,使用这个模型就不可避免地需要用到BloomFilter和Compaction,当然还有一些cache的技术也算在这个部分,数据模型部分的主要参照也是Bigtable中的Keyspace+Row+ColumnFamily+Column的模型,不过Cassandra又在其中加上了SuperColumn一层,除了模型的实现,还有模型提供的各种操作的实现也在其中,此外,还要加上CommitLog的相关实现。具体的细节不在这里讨论,相关的包是以下几个:
    org.apache.cassandra.io
    org.apache.cassandra.io.sstable
    org.apache.cassandra.io.util
    org.apache.cassandra.db
    org.apache.cassandra.db.columniterator
    org.apache.cassandra.db.commitlog
    org.apache.cassandra.db.context
    org.apache.cassandra.db.filter
    org.apache.cassandra.db.marshal
    org.apache.cassandra.db.migration 
    org.apache.cassandra.cache 
  • P2P
    这个部分是用来实现P2P,也就是去中心化架构的,主要是实现了一个分布式哈希表(DHT),其中实现了几种不同的Partition方案供选择。相关的包是这个:
    org.apache.cassandra.dht 
  • 副本
    这个部分是用来实现分布式系统中常用的副本机制的,这里也提供了几种副本策略。关于副本的设置问题,在配置文件中有副本策略的设置,此外,还有副本数量的设置是写在每个Keyspace的Metadata中的。相关的包是这个:
    org.apache.cassandra.locator 
  • Gossip
    这个部分实现了Gossip,用来进行分布式系统中的成员管理。相关的类是下面这个:
    org.apache.cassandra.gms 
  • SEDA
    这个部分实现了SEDA的框架,用于更高效的并行操作。相关的类是下面这个:
    org.apache.cassandra.concurrent 
  • 通信
    这个部分实现了分布式系统内部用于通信的消息机制,以及内部传输的数据流机制。相关的包是以下几个:
    org.apache.cassandra.net
    org.apache.cassandra.net.io
    org.apache.cassandra.net.sink 
    org.apache.cassandra.streaming 
  • 请求调度
    对到达的请求进行简单的调度,相关包是:
    org.apache.cassandra.scheduler 
  • 服务封装
    这个部分实现了系统对外的调用接口,无论系统内部是如何实现的,对使用者来说,只需要从这里的服务中进行调用就可以了。此外,与hadoop的接口算在其中。相关的包是下面这2个:
    org.apache.cassandra.service 
    org.apache.cassandra.thrift 
    org.apache.cassandra.hadoop 
  • 客户端
    这个部分包括了用于管理系统的命令行接口和CQL客户端,至于Thrift客户端,那个在生成代码中。相关的包是下面这几个:
    org.apache.cassandra.cli
    org.apache.cassandra.client
    org.apache.cassandra.cql 
    org.apache.cassandra.tools 
  • 配置
    这个部分用来读取配置然后导入到系统中。相关的包是下面这个:
    org.apache.cassandra.config 
  • 授权与安全
    这个部分实现的是简单的用户授权管理和安全管理。相关的包是下面几个:
    org.apache.cassandra.auth
    org.apache.cassandra.security
    org.apache.cassandra.security.streaming  
  • 憎恶的缝合线
    好吧,这里卖萌了,其实这里就是我所说的用来对整个系统进行修修补补的地方,比如为了实现某个功能,但是少了个什么东西,于是就实现了放在这里,具体是下面2个包:
    org.apache.cassandra.utils
    org.apache.cassandra.utils.obs 

2011/08/18 计算机,世界,系统

我认为,整个世界是一个巨大的系统。所谓系统,又有三个组成部分,一部分是存在,一部分是规则,最后一部分是使用规则的人或物。

存在,可以理解为是这个系统确实在工作的证明,存在可以是有形的,也可以是无形的。比如世界的存在是有形的,我们就是生活在世界的实体中,比如社会的存在是无形的,但是我们也确实生活在其中,但是却看不见摸不着。

规则,分为不能改变的和可以改变的。简单来说,区分两者的就是看规则是否是人造的。非人造的规则,比如自然的规则,那是这个系统的固有规则,乃是神之领域,这些规则只能不断被发现,被理解,却不能被改变。人造的规则,比如人类社会中的法律,这是可以根据人的意志做出改变的规则。

使用规则的人或物,也就是系统中的主体。对于世界来说,就是所有的生物,人和动物,对于人类社会来说,就是人类,对于计算机来说,就是程序。这些主体自然不是平等的,其强大是与其对规则的理解程度成正比的,动物其实也对规则有自己的理解,但是限于自身的能力所限,无法形成理论,并进一步深入,所以动物有他们的本能,并且有许多在人类看来巧夺天工的设计,人类,是造物主的宠儿,最初也如其他动物一样,但是当人类开始理解并探索世界这个系统的规则时,就获得了超越其他主体的能力,并且随着对规则的进一步理解,变得越来越强大,虽然这只是冰山一角。

同样的道理,计算机科学也是类似的。

计算机这个系统的存在可以认为是其硬件部分,脱离了真正的硬件,计算机的系统实际上就不存在了,只剩下一堆理论(规则)和毫无生气的代码(主体)。

计算机这个系统的规则却是特殊的,之所以说是特殊,是因为人类在计算机的世界中充当了造物主的角色,然而,这个造物主并不完美,人类创造了计算机世界的规则,但是却没有办法完全理解规则,因为人类创造的规则只是最初的规则,更多的规则在不为人质的情况下被创造了出来,这两种规则虽然不是完全不可改变,但是这种最为基础的规则是牵一发而动全身的,改变的代价很大,这些规则时计算机硬件组成的基本理论,然后还有很多主动创造的可改变的规则,例如操作系统的理论。

计算机系统的主体自然是各种各样的程序,操作系统本身也算是一个特殊的强大的程序,它理解了最基础的规则,然后又创造了许多自己的规则,更为常见的普通程序则必须在这些规则的约束下生存下去,完成自己的工作,甚至构建自己的小系统。与现实这个系统一样,对规则的理解越深,那么主体就一定越强大,这也就是为何黑客所写的程序能够透过漏洞完成别人做不到的事,黑客身为计算机世界的神,通过他们对规则的理解,创造着更强大的主体。

如果说人类是计算机世界的造物主,是计算机世界的神的话,那么显然计算机世界的神比现实世界的神要更加频繁地去影响自己的世界。但是无论如何,计算机世界的创造,都仅仅使用了现实世界的极小一部分规则,因此其复杂度也不是一个等级的。不可否认的是,计算机世界的进化速度比现实世界快乐多,不仅仅是计算机世界的计算速度比人类要快得多,而且这是与造物者对自己的世界的关注程度相关的。于是,计算机世界成为了新的伊甸园,神的实验场。

然而,在现在来看,计算机世界也仅仅是伊甸园而已,计算机世界中的亚当和夏娃还没有吃下禁果,计算机世界中的所有主体都没有自己的意识,仅仅是行尸走肉。不过如果出现了计算机世界中的亚当和夏娃的话,那么也就不需要所谓的神,也就是人类了吧。

Paxos学习笔记——overall

一、一些废话

第一次听说Paxos算法,是在2011年的春节期间,与刘君吃饭时听到他提起的。后来,我渐渐了解到,Paxos乃是Google产品的重要基础,最初的使用是在Chubby中,后来似乎在Megastore中再次使用。

6月之后,既然GRE败了,那么还是先把开题的任务搞定。我觉得我开题其实是个巨大的坑,同组的其他人要么开了可以忽悠的题目,要么是别人已经做好了,但是boss不知道的题目。我开的题则是在我某天包夜,喝咖啡喝的恍惚的时候想到的,但是现在想一想,也不是怎么靠谱,甚至有可能毫无意义。无论如何,都要从Paxos算法的实现做起,刘君说,这个算法很难实现,确实如此。可笑的是,算法的实现已经很困难了,而且别人早已有了很多成功的Paxos实现,但是我却妄图在这些成功的方法上加上一些愚蠢的改动,完全是自虐。整个毕业设计的工作计划争取在放假结束前写完,这是后话

Paxos的文章很多,最为重要的自然是Lamport所写的那些文章http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html),所以一开始我打算先把他的论文看完,但是,看了几天,我就发现这是一个极为困难的任务,首先,他的文章很多,其次,他的文章确实不太好懂。所以我退而求其次,转向了Paxos的wikihttp://en.wikipedia.org/wiki/Paxos_(computer_science)),wiki比较浅显易懂,而且涵盖了更多的内容,当我完成了这部分的工作之后,再去相应的论文中寻找更多的细节与证明。所以下面的内容大量参考wiki上的内容,许多渣翻译。

二、名字的由来与故事

来自Lamport虚构的希腊的Paxos岛群中所使用的立法一致系统(legislative consensus system)。

具体的故事是这样的(摘自中文Paxos wiki(http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95)):

为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题(Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息);只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议的。

三、Safety and liveness properties,安全性和活性?好吧,我也不知道怎么翻

Paxos中定义了三条安全性质,并且保证在没出错时一直保证之:

  • 非平凡性——Non-triviality
    只有提议(propose)的值(value,下同,具体含义的理解在本节最后)才能被获知(learn)。
  • 一致性——Consistency
    只有一个值能被获知。这意味着两个不同的获知者不会得到不同的值。我的理解是一次Paxos执行中
  • 活性——Liveness(C,L)
    如果值C被提议了,那么最终获知者L将会得到某些值(如果足够多的处理者保持没有出错的话)。

看到这里,恐怕还是云里雾里,不知道这三条性质具体是指什么。这里先讲讲关于value的我的理解,value在这里是一个很抽象的概念,既可以是一个数字,也可以是一套方案,一系列操作,所以value的具体含义在于开发者针对什么问题使用了Paxos算法,此时,value的含义就是这个问题中需要保持一致的对象

这三条性质保证了一致性的需要,所以Paxos算法其实就是围绕这如何保持这三条性质展开的。关于为何满足这三条性质就能保证一致状态,Lamport也给出了证明。

四、假设与定义

1、假设

Paxos的假设分为两方面,一方面是关于处理者的,一方面是关于网络的。我认为,这是由于假设中的限制非常少,才使得满足了这些假设的算法意义非凡。

关于处理者,processors,是指故事中的议员,或是真正的实现中的处理程序,节点。相关的假设如下:

  • 处理者以任意速度进行处理
  • 处理者会失效,无法工作
  • 拥有稳定存储的处理者可以在失效之后再次加入Paxos
  • 处理者不会勾结欺骗,即无拜占庭错误

关于网络,networks,是指故事中的消息传递机制,或是真正的实现中的网络系统,事实上,也就是互联网。相关假设如下:

  • 处理者可以发送消息给其他的处理者
  • 消息被异步地发送,并且花费任意长的时间才能收到
  • 消息会丢失,顺序错误,重复
  • 消息不会出现欺骗,即无拜占庭错误

2、处理者数量

一般来说,一个一致性算法的运行使用2F+1个处理者,并且可以容忍同时F个处理者的失效,即容忍少于一半的失效。然而,经过配置的话,这个协议也可以容忍更多的失效,只要失效不会产生地过快。

所谓不会失效地过快,是指不会同时一起失效,而是一个接一个地失效。这里提到的方法是使用备用处理者代替失效处理者。举例来说,5台服务器,原本可以容忍2台失效,现在使用如下,将3台作为活跃机使用,2台作为备用机使用,当活跃机失效时,就重新配置,让备用机代替活跃机工作,当然,前提是失效只会在重新配置完成后才发生,这样最终可以容忍3台失效。我认为,这样的方法实际上降低了服务器的可用性,意义不太大。

3、角色

终于到了一个很关键的地方,上面提到的处理者有不同的角色,不同角色的处理者作不同的处理动作,他们是:client, acceptor, proposer, learner, and leader。在实现时,往往一个处理者要同时扮演几个角色,这并不会影响协议的正确性,而且这也很平常,因为合并角色可以减少延迟,或者减少消息数量。

  • 客户,Client
    客户会向分布式系统发送请求,然后等待回应。例如,发往分布式文件服务器的写请求。
  • 决议者,Acceptor
    决议者是协议中的容错记忆体。一定数量的决议者被归为一组,称为额定数(Quorum)。任何发往决议者的消息都必须发往额定数量的决议者,任何来自决议者的消息都应该 由额定数量的决议者分别发出同个消息的拷贝,否则将会被忽略。简单来说,消息必须有Quorum份。
  • 提议者,Proposer
    提议者提议各异客户请求,尝试让决议者同意它,并且在发生冲突时作为协调者(Coordinator)推动协议继续进行。
  • 获知者,Learner
    获知者作为协议的副本因子,一旦一个客户请求被决议者所同意,那么获知者将会采取相应的行动,例如,执行请求并回应给客户。额外的获知者可以提供更高的可用性
  • 领导者,Leader
    Paxos需要一个高阶的提议者(成为领导者)来推动协议的进行。有可能很多处理者都会认为自己是领导者,但是协议保证最终仅有一个会被选为领导者。如果两个处理者认为他们都是领导者,将会不停地提出冲突的更新请求,那么会拖延整个协议。安全性无论如何将会被保证。

4、额定数(Quorum

额定数表示了Paxos的安全性,说明至少有一些存活的处理者知道结果。

额定数被定义为决议者集合中的一系列子集,并且这一系列子集中的任意两个子集的交集都不为空。典型的额定数是决议者的多数。比如,有决议者集合{A,B,C,D},一个多数额定可以是其中任意的三个决议者:: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}。更一般化的情况是,可以给决议者赋予任意的正权值,此时,额定数就被定义为了子集总权值大于全集总权值的一半的那些子集。

5、提议编号与同意值(Proposal Number & Agreed Value

每次尝试定义一个大家都同意的值,都是通过提议的形式来完成的。一个指定的提议者的每个提议都有一个唯一的提议编号。

五、典型实现方案

在大多数的Paxos实现方案中,只有三种角色:Proposer, Acceptor and Learner。这能显著降低消息复杂度,在不牺牲正确性的前提下。

通过合并角色,整个协议缩减成了一个有效的客户-主人-副本(client-master-replica)风格的部署,这是数据库社区的典型部署。使用Paxos系列方法的好处是安全性的保证。

一个典型实现的数据流将在Typical Multi-Paxos deployment中提到。

六、Paxos的系列算法

1990,Paxos算法就已经被Lamport所创立,但是直到1998年关于Paxos的论文才发表。之后有许多的工作围绕着Paxos展开,但是这都是围绕着Paxos的核心而做的修修补补,或者结合不同的情景与需求所做的改动,最为核心的仍然是Lamport最开始描述的Paxos,因为这个核心才是保证一致性的关键。

1、Basic Paxos

这个协议是Paxos系列中最基础的一个。每个Basic Paxos协议的实例都会决定一个输出值。协议可以进行很多轮(round),每轮有2个阶段(Phase)。当提议者无法与额定数量的决议者通讯时,提议者不应该启动Paxos。

描述如下(名称不翻了,不然感觉怪怪的):

Phase 1a: Prepare
一个提议者(即领导者)创建一个提议,这个提议用一个数字N进行标识。这个数字必须比这个提议者曾使用过的提议编号都大。然后,它发送一个准备(prepare)消息(消息中包括了这个提议)给额定数量的决议者。

Phase 1b: Promise
如果决议者收到的提议编号N比任何之前收到的(来自任何提议者的)提议编号都大的话,那么决议者必须返回一个保证(promise),保证忽略之后收到的任何提议编号小于N的提议。如果一个决议者在之前已经同意了某个值,那么它在回应提议者的时候,必须附加上最新同意的提议编号以及相应的值。
否则,决议者可以忽略收到的提议。甚至可以不用回应它。然后,为了优化的目的,发送回一个拒绝(Nack)回应可以告诉提议者可以停止尝试在提议N上达到一致。

Phase 2a: Accept Request
如果一个提议者从决议者处收到了足够多的保证(额定数个),那么这个提议者需要给它的提议设定一个值(value)。如果某个决议者之前已经同意了某个提议的话,那么它已经将它同意的值发送给了提议者,这时,提议者必须将值设为已经收到的值中(在promise中一起返回的,都是各决议者已经同意的值)编号最大的提议的值。否则,它可以直接设定自己的独立的值。
然后,提议者发送一个请求接受(Accept Request)消息给额定数量的决议者,这个消息中,包含了提议中选择的值。

Phase 2b: Accepted
如果一个决议者(Acceptor)收到了提议N的接受请求消息,它必须接受它,当且仅当它还没有向一个编号大于N的提议进行保证时。这种情况下,它应该注册这个相应的值v,然后发送一个已接受(Accepted)消息给提议者和每个获知者。否则,它可以忽略这个接受请求。

每轮过程会在下面两种情况下失败:多个提议者发送了冲突的准备消息;或者是提议者没有收到额定数目的回应(保证已接受)。在这些情况下,需要开始新的一轮,并使用新的更高的提议编号。

注意到当决议者接受一个请求时,他们也会告知提议者的领导。因此,Paxos也可以用于在一个集群的节点中选择一个领导者(Leader)

下面是 Basic Paxos协议 的图示。注意在保证消息(Va,Vb,Vc)中返回的值在第一轮实例中通常是null,下面写出来是为了完整性。

Message flow: Basic Paxos

(one instance, one successful round)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Basic Paxos中的出错情况

最简单的出错情况是冗余获知者的失效,或者一个决议者的失效,但此时仍有额定数量的决议者存活。这种情况下,不需要恢复操作,也不需要额外的几轮过程或几轮消息。如下所示:

Message flow: Basic Paxos, failure of Acceptor

(Quorum size = 2 Acceptors)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(N,{Va,Vb})
   |         X--------->|->|          |  |  Accept!(N,Vn)
   |         |<---------X--X--------->|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

 Message flow: Basic Paxos, failure of redundant Learner

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |

下一个出错情况是当提议者在提议了一个值之后,但是在达到共识前的时候失效了。忽略选择领导者的问题,例子如下:

Message flow: Basic Paxos, failure of Proposer

(re-election not shown, one instance, two rounds)

Client  Leader         Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(N)
   |      |<------------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(N,Vn)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(N+1)
   |         |<---------X--X--X       |  |  Promise(N+1,{Vn})
   |         X--------->|->|->|       |  |  Accept!(N+1,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N+1,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

最为复杂的情况是多个提议者相信自己是领导者。举例来说,当前的领导者失效了,并且在之后恢复了,但是其他的提议者已经重新选举了一个新的领导者。这个恢复了的领导者并不知道这件事,然后尝试开始新的一轮过程,但是这与当前的领导者冲突了。

Message flow: Basic Paxos, dueling Proposers

(one instance, four unsuccessful rounds)

Client   Proposer      Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(N)
   |      |<------------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows N)
   |         X--------->|->|->|       |  |  Prepare(N+1)
   |         |<---------X--X--X       |  |  Promise(N+1,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries N+1, denied
   |      X------------>|->|->|       |  |  Prepare(N+1)
   |      |<------------X--X--X       |  |  Nack(N+1)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries N+2
   |      X------------>|->|->|       |  |  Prepare(N+2)
   |      |<------------X--X--X       |  |  Promise(N+2,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(N+1,Vn)
   |      |  |<---------X--X--X       |  |  Nack(N+2)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries N+3
   |      |  X--------->|->|->|       |  |  Prepare(N+3)
   |      |  |<---------X--X--X       |  |  Promise(N+3,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(N+2,Vn)
   |      |<------------X--X--X       |  |  Nack(N+3)
   |      |  |          |  |  |       |  |  ... and so on ...

2、Multi-Paxos

典型的Paxos实现需要一个关于同意值(agreed value)的持续流(continuous stream),这些同意值用作分布式状态机的命令。如果每个命令都是一个Basic Paxos的实例的结果,那么这将意味着很大量的开销。

如果领导者相对稳定的话,phase 1就变得不再必要。因此,如果之后的实例都使用相同的领导者,那么phase 1就可以跳过。

为了达到这种方式,实例编号I要被包含在每个值(value)中。Multi-Paxos在保证容错的同时,将消息延迟(从提议到被他人得知)从4步延迟降到了2步延迟。

Message flow: Multi-Paxos, start

(first instance with new leader)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,I,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Message flow: Multi-Paxos, steady-state

(subsequent instances with same leader)

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N+1,I,W)
   |         |<---------X--X--X------>|->|  Accepted(N+1,I,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

典型Multi-Paxos实现

Paxos系列最常见的实现就是Multi-Paxos,特别是参加Paxos的处理者分别是提议者(Proposers),决议者(Acceptors)和获知者(Learners)。于是消息流可以被优化如下:

Message flow: Collapsed Multi-Paxos, start

(first instance with new leader)

 Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N,I,{Va,Vb,Vc})
   |         X->|->|  Accept!(N,I,Vn)
   |         |<-X--X  Accepted(N,I)
   |<--------X  |  |  Response
   |         |  |  |

Message flow: Collapsed Multi-Paxos, steady state

(subsequent instances with same leader)

 Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N+1,I,W)
   |         |<-X--X  Accepted(N+1,I)
   |<--------X  |  |  Response
   |         |  |  |

3、优化

很多的优化降低了消息的复杂度和大小。这些优化总结如下:

“可以以 额外的一个消息延迟 的代价获得消息数量的减少,方式是使用一个特别的获知者,当它发现一个值被选择之后,由它来通知其他的获知者。然后决议者只发送已接受(Accepted)消息给这个特别的获知者。在大多数的应用中,领导者和特别的获知者的角色通常是由相同的处理者所担当的。

“领导者可以只发送准备(Prepare)消息和请求接受(Accept!)消息给额定数量的决议者(而不是全部)。只要额定数中的所有决议者都能正常工作,并且可以和领导者和获知者通信,那么就没有必要让额定数之外的决议者做任何事。

“决议者不在乎被选择的是哪个值。他们仅仅对准备(Prepare)消息和请求接受(Accept!)消息做出回应,并在没有发生失效时保证只有一个值会被选择。然而,如果一个决议者确实获知了是哪个值被选择了之后,那么它可以把值储存在可靠稳定的存储器上,然后擦除它保存在那的任何其他信息。在这之后如果决议者又接到了准备消息或者请求接受消息,就可以略过Phase 1b和Phase 2b,而直接通知领导者它选择的值。

“领导者可以在其请求接受消息中发送值v的哈希(hash of v)给一些决议者,而不是发送整个值v。获知者将会或者哪个值被选择了,如果它从额定数量的决议者处收到了关于值v或者它的哈希的已接受(Accepted)消息,并且这些消息中至少有一条包含了v,而不是它的hash。然而,领导者可能会只接受了包含v的hash的保证(Promise)消息,而不是v的确切值,但是在它的Phase 2a中必须要使用v值。如果这种情况发生的话,领导者就不能执行Phase 2a,直到它与一些知道v的处理者通信并取得v值。

“提议者只可以发送提议给领导者,而不是所有的协调者(Coordinator)。然而,这需要把领导者选择算法的结果广播给所有的提议者,这是昂贵的开销。因此,更好的方案是发送提议给所有的协调者,在这种情况下,只有协调者内部需要知道领导者是谁。

“取代每个决议者发送已接受(Accepted)消息给每个获知者的方案,决议者可以发送已接受消息给领导者,然后领导者可以在一个值被选择时通知获知者。然而,这会增加一个额外的消息延迟。

“最后,观察到Phase 1对于第一轮(Round 1)是不必要的,第一轮的领导者可以从发送请求接受(Accept!)消息开始,请求接受消息中包含提议值(proposed value)。”

4、Cheap Paxos

Cheap Paxos继承了Basic Paxos,使用F+1个主处理者和F个辅处理者,能在每次失效发生后动态重新配置,能够容忍F个失效。

需要的处理者数量的减少,是以活力的损失为代价的;如果太多主处理者在短时间内失效,整个系统就需要暂停,直到辅处理者重新配置系统。在稳定的期间,辅处理者不参加协议的执行。

“只有两个处理者p和q,那么一个处理者不能辨别另一个处理者的失效是真的失效还是由于通信介质的失效。于是需要第三个处理者。然而,第三个处理者并不必加入到选择命令序列的任务中。它需要做的,是当p或者q失效时,它能够启动,当p或者q能够继续操作系统时,它又可以休息了。因此第三个处理者可以是小的/慢的/便宜的(small/slow/cheap)那个处理者,或者是一个主要投入到其他工作中去的处理者。”

Message flow: Cheap Multi-Paxos

3 main Acceptors, 1 Auxiliary Acceptor, Quorum size = 3, showing failure of one main processor and subsequent reconfiguration

            {  Acceptors   }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |

5、Fast Paxos

Fast Paxos推广了Basic Paxos,降低了端到端消息延迟。在Basic Paxos中,从客户端请求到获知结果的消息延迟是3个消息延迟。Fast Paxos只要2个消息延迟,但是需要客户端发送请求到多个目标处。

直觉地,如果领导者没有用来提交的值,那么客户端可以直接发送一个请求接受(Accepted!)消息给决议者。决议者如同在Basic Paxos中一样进行回应,发送已接受(Accepted)消息给领导者,这里从客户端到获知者只要2个消息延迟。

如果领导者检测到了一个冲突,它会用以下的方法来解决冲突,它在新的一轮中发送请求接受(Accepted!)消息,在新的一轮中,可以正常接受(Accepted)。这个协调恢复方法(coordinated recovery technique)从客户端到获知者需要4个消息延迟。

当领导者发现恢复方法正在启动时,可以进行最后的优化,允许决议者自身进行冲突恢复。因此,非协调冲突恢复需要3个消息延迟(如果所有的获知者都是决议者的话,只需要2个消息延迟)。

Message flow: Fast Paxos, non-conflicting

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

Message flow: Fast Paxos, conflicting proposals

Conflicting proposals with uncoordinated recovery. Note: the protocol does not specify how to handle the dropped client request.

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Message flow: Fast Paxos, collapsed roles

(merged Acceptor/Learner roles)

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X--X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X--X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

6、Generalized Paxos

推广的一致性(generalized consensus)探讨了分布式状态机(distributed state machine)的操作和用来处理状态机一致性的一致性协议(consensus protocol)之间的关系。主要的研究当冲突的提议可以以任意顺序被状态机接受时,是一致性协议的优化。例如,由冲突的提议所提议的操作是状态机中的可交换操作。

在这种情况下,冲突的操作可以都被接受,并且避免了解决冲突和重新提议被拒绝的操作所花费的延迟。

这个概念被进一步推广到可交换操作的持续增长集 上,某些这样的持续增长集被认为是稳定的(stable)(因此可以被执行这个协议)。协议追踪这些操作集,确保在允许任何不可交换操作变稳定(stable)前,一个集合中的所有提交的可交换操作都是稳定的。(这段没太懂。。。原文如下:This concept is further generalized into ever-growing sets of commutative operations, some of which are known to be stable (and thus may be executed). The protocol tracks these sets of operations, ensuring that all proposed commutative operations of one set are stabilized before allowing any non-commuting operation to become stable. 关键在于这个stable的理解上,关于stable的词出现了2个,一个是形容词stable,一个是动词stabilize,那么stabilize这个词的意思是将所谓的operation执行,然后把执行的结果输出到稳定的存储中去么,然后stable就是指执行结果已被输出到稳定存储的状态。)

举例

为了阐明Generalized Paxos,这个例子由以下部分进行表示:两个并行执行的客户端间的消息流,以及一个在2个相互独立的注册地址(A和B)处执行read/write注册操作的状态机。
可交换性表(Commutativity Table);做标记的地方表示有干扰:
                 Read(A) Write(A) Read(B) Write(B)
        Read(A) |       |    X   |       |        |
        Write(A)|   X   |    X   |       |        |
        Read(B) |       |        |       |    X   |
        Write(B)|       |        |   X   |    X   |
操作的提交序列(全局顺序):
        1:Read(A)
        2:Read(B)
        3:Write(B)
        4:Read(B)
        5:Read(A)
        6:Write(A)
        7:Read(A)
通过交换之后,一个可能的排列:
        { 1:Read(A),  2:Read(B), 5:Read(A) }
        { 3:Write(B), 6:Write(A) }
        { 4:Read(B),  7:Read(A)  }
观察结果:
  • 5:Read(A) 可以交换到3:Write(B)/4:Read(B) pair之前.
  • 4:Read(B) 可以交换到 the 3:Write(B)/6:Write(A) pair之后.
  • 实际上,交换只会发生在操作是同时提交的情况下.

Message flow: Generalized Paxos (example)

Responses not shown. Note: message abbreviations differ from previous message flows due to specifics of the protocol, see(Generalized Consensus and Paxos)for a full discussion.

           {    Acceptors   }
Client      Leader  Acceptor     Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X--X--X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |    commutative order:
 |  |         |      |  |  |         |  |    V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X--X--X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+2,<WriteA> . <ReadA>)
 |  |         |<--------X--X-------->|->|  Accepted(N+2,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order W
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X--X--X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |

Generalized Paxos vs. Fast Multi-Paxos

上面的数据流显示了Generalized Paxos在10个消息延迟中执行了关于7个值的协议。对相同的提议值序列,Fast Multi-Paxos则需要15-17个延迟(3个需要不协调恢复的并发提议,每个需要3个延迟,加上至少2个延迟给最终需要重新提交的3个被拒绝的提议,并发的重提议可能还要加上2个额外的延迟)。 

7、Byzantine Paxos

Paxos可以被扩充以支持参加者会发生的任意错误,包括撒谎(lying),消息伪造(fabrication of  messages),与其他参加者同谋(collusion with other participants),选择性不参与(selective non-participation),等等。这些类型的错误被称为拜占庭错误(Byzantine failures),Lamport给出了结局方案。

Byzantine Paxos增加了额外的一个消息(verify),用来分发已知信息,以及核实其他处理者的动作。

Message flow: Byzantine Multi-Paxos, steady state

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |

Fast Byzantine Paxos溢出了这个额外的延迟,因为客户端可以直接发送命令给决议者。

注意到在Fast Byzantine Paxos中的已接受(Accepted)消息被发送给所有的决议者和获知者,而Fast Paxos仅将此消息发送给获知者。

Message flow: Fast Byzantine Multi-Paxos, steady state

Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |

这个失效场景与两个与两个协议相同;每个获知者等待F+1个从不同决议者处发出的同样的消息。如果这没有发生,那么决议者本身也会知道(因为他们在广播轮(broadcast round)中交换各自的消息),并且正常的决议者会再次广播这个同意值:

Message flow: Fast Byzantine Multi-Paxos, failure

Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |

 Virtually Synchronous Paxos(虚拟同步Paxos)

虽然虚拟同步模型与Paxos对于创建状态机副本服务和简单应用来说,有时看起来是相反方向的选择,但是近来的工作(“Virtually Synchronous Methodology for Dynamic Service Replication”)证明了合并两种模型到一个统一方案的可能性。这个方法使用虚拟同步来支持执行时期(execution epochs),在执行时期内,成员(membership)被一致性协议决定并被是稳定的(stable)。于是,容错协议就被定义在了每个时期的基础上。这个方法相比于其他方法,加强了虚拟同步模型,使其在动态Paxos服务成员(making the membership of a Paxos service dynamic)的方面,提供了更好的性能。

七、最后的吐槽

首先是我的效率太低了!这篇日志从7月底一直写到了8月中旬,虽然中间经过了开年会,放假等等,前前后后有20多天,但是,主要还是我磨磨蹭蹭的原因,如果拼命写,估计7月底就写完了。。。

嘛,也不能说是写完了,应该是翻译完了,开头还想写点自己的话,后来写到具体的算法介绍时就开始照着wiki翻译了,然后强迫症让我硬生生翻译完了。。。

最后,英转中总是这么蛋疼,讲话思维是反的,于是我的渣翻译就跟机翻一样,感觉还是完全不能看啊!