当前NoSQL的分布式存储系统的资料(包括Paper以及各大Blog上的内容),大部分都是关于分布式Key-Value存储下的读写操作、数据一致性、节点失效与修复等问题上,很少有系统的提及有关Load Balance的处理。不过既NoSQL指导型原则是CAP原理,而系统在实现时无论偏重AP还是CP,P都是必选的,因此对于分布式的各个节点的负载均衡也应该是要面对的问题,不过很遗憾,在BigTable, Dynamo以及Cassandra的Paper中对于Load Balance基本都没有提及,都只是很简单的进行了说明。特地花了几天去找了一些资料,总结记录于此。

1. Dynamo

Dynamo的论文上对于Load Balance的提及基本就是一个关键词”uniform hashing”,”A uniform key distribution can help us achieve uniform load distribution assuming the access distribution of keys is not highly skew“。即通过均匀的hash函数,保证将所有的key以及node都可以均匀的分布到同一哈希地址空间上,从而实现负载的均衡,此类常用的函数包括MD5 hash函数和SHA-1 hash函数。

除了利用哈希函数使得整个存储的item被均匀的分配到整个地址空间上,此外Dynamo的Virtual Node机制也对负载均衡进行一定的帮助,根据机器的性能指标不同划分不同的VNode即可。

此外,当新的VNode启动以及离开时,需要将某个VNode的数据迁移至邻居节点,而此种迁移有时会带来比较大的计算量(Merkle Tree等),因此Dynamo又采用了一个将整个地址空间划分成段的策略(如下图所示),然后每个VNode只能在一个段边界位置进行添加,即每一个VNode管理段长的整数倍的地址空间,此种方式对于节点的启动以及恢复,数据的归档等都有好处。

由于Dynamo虽然是NoSQL数据库的雏形以及类white paper,但由于工业界基于此模型构建实际针对业务数据库并是特别认可,因此资料也较少。

2.  Cassandra

Cassandra首先包含了两种Partitioner,这两种Partitioner对负载均衡的影响完全不同。

RandomPartitioner: RandomPartitioner采用均匀的hash函数,将负载均匀的划分到Key space空间上。RandomPartitioner gives you pretty good load balancing with no further work required。不过由于hash函数会将连续的Key映射到不同的环上地址,缺点就是无法进行range query.
OrderPreservingPartitioner:OrderPreservingPartitioner会使得连续的key映射到环上的地址空间后也是连续的,因此支持range query. OrderPreservingPartitioner let u perform range queries on the keys, but requires choosing node tokens carefully and active load balancing.

也就是说RandomPartitioner几乎是不需要进行Load Balancing的,但对于后者,就需要在Load Balancing上下一点功夫。

阅读全文…

, , , ,

paxos算法是为了解决在分布式系统中,多个process有关某一个值达成一致决议的算法,即一种一致性算法(Consensus Algorithm)。Google的分布式锁Chubby和Yahoo的Zookeeper的实现中都采用了此算法思想,Lamport(此人的牛逼程度可以参看他发表的文章和被引用的次数)在《paxos made simple》的第二页给出的abstract就一句话:“The Paxos algorithm, when presented in plain English, is very simple.”,有关paxos发布的背后的事情还挺有趣的,paxos从提出到发布用了9年,<The Part-Time Parliament>,Lamport虚拟了一个希腊的城邦paxos,用该城邦的人如何就一条法令达到一致来描述了整个算法,但计算机界的N多人都不悲剧幽默感,Lamport就在2001年写了一篇相对简短的《paxox made simple》,估计也就是这句abstract的来由

paxos算法将分布式系统的process划分为三种角色,分别为proposer, acceptor以及learner,其中只有proposer和acceptor参加决议过程,learner只是了解决议被批准以后系统具体选择的决议值,整个算法采用基于消息的传递模型,假设整个系统是消息异步,并且没有拜占庭失效问题(non-Byzantine model),就是整个系统中的消息可以延迟到达,可以重复发送甚至可以丢失,但不能被篡改,允许系统中的节点失效和重启,但需要这些节点在失效到重启之间具有永久性存储介质用以记录信息。

整个paxos算法的过程是一个两段式提交,由proposer提出决议(value),acceptor接受并选择决议,用一个{n,v}来对传递的消息进行描述,n表示一个严格递增不重复的编号,有关这个编号的实现在paxos made simple中提到的是让所有的proposer都从不相交的数据集合中进行选择,例如系统有5个proposer,则可以为每一个proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示round),v表示value。

Phase 1a: proposer提出一个决议并选择一个编号N,发送message prepare(N)给大多数(Majority)的Acceptor。

Phase 1b: acceptor接受到prepare(N)的消息后,如果不违法自己给其他proposer的承诺,即没有收到过比N编号更高的prepare请求,则返回给proposer消息{n,v},n是自己上次批准的请求编号,v是自己上次accept的value。并承诺自己不再接受任何小于N的编号的prepare请求。如果acceptor之前已经收到过其他高于N的编号的prepare请求,则忽略prepare(N),也可以给一个deny反馈(出于效率考虑,不反馈不影响正确性)。

Phase 2a: proposer收到多数的acceptor的确认反馈后,即可以进入批准阶段,proposer选择一个value(V)(V所有acceptor回馈的消息中,编号最大的value),或者当任何acceptor都没有value反馈时,proposer可以自己任意选择value值,发送Accept(N,V)给所有的acceptor。

Phase 2b: 当acceptor接受到一个accept(N,V)的请求时,acceptor就批准这个请求,除非该acceptor之前收到了一个比编号N更高的prepare请求。

整个算法的执行过程中,proposer可以任何时间随意的抛弃一个proposal,不影响正确性。算法的执行图解如下(from wikipedia)

 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
   |         |          |  |  |       |  |

Learner需要了解被选择了的value,从上图可以看出在Phase 2b阶段时,当acceptor接受了一个决议后,会给Learner发送消息通知learner,为了尽快的使得Learner了解到被选择的value,可以每一个Acceptor都发送消息给每一个Learner,这样会产生大量的消息,是Acceptor个数和Learner的乘积。另外一种是由于系统中没有拜占庭失效,可以采用一个主Learner接受Acceptor发送的决议并且通知其他的Learner,这样减少了消息总量但会引起单点失效和多一级的传递。因此可以在实践中做一个权衡,选一个主learner集合来对learner进行通知。

由于有可能存在活锁的情况,即两个proposer轮流的用更高的编号提出新的prepare请求,使得没有任何一方的决议能成功的被批准。因此会选择一个主proposer,只有该proposer才能提出决议,如果主proposer提出一个决议遇到了deny,即存在另外一个更高的编号决议,则直接选择一个足够大的编号进行提议。主proposer,即leader包括主learn的选择一般也采用paxos算法,zookeeper中leader的选择就采用了fast paxos算法。

虽然Lamport说paxos算法非常simple,然后文章也很简短,但跟所有学习者的感觉一样,远没有大师的智慧,不会觉得他特别simple,看了几天也还只了解大概,特别是在看到相关引申的各种文章后。有关paxos算法在实现角度的描述以及实现可以参考Lamport在2005年写的<Fast Paxos>,以及他人写的<Paxos Made Live – An Engineering Perspective>,和<Paxos在大型系统中常见的应用场景>。

Reference:

[1] http://en.wikipedia.org/wiki/Paxos_algorithm (对整个paxos系列描述的相当详细)

[2] http://zh.wikipedia.org/wiki/Paxos算法 (paxos made simple的简单译文)

[3] Paxos Made Simple

[4] Paxos Made Live – An Engineering Perspective

Amazon Dynamo的论文做为NoSQL的分布式模型论文中的白皮书,必然也是阅读的第一篇文章,当时读完后对最终一致性,quorum-like以及hinted handoff的概念和去中心化的存储设计有一些记忆外加简单的理解,最近又读了一些有关这个最初模型的文章,大致记录一下。

Dynamo设计的几个原则:

数据分区分布采用一致性哈希(consistent hashing)算法,并结合虚拟节点的思想(virtual nodes)来抑制数据分布存在的不均匀性。

备份之间的不一致采用向量时钟(vector clock)进行冲突解决与合并。

存储过程中采用quorum-like机制,使得R + W > N来保持一致性,如果出现节点失效,采用hinted handoff策略。

当节点加入或者离开Dynamo,数据之间的校验采用merkle tree。

阅读全文…

扯淡:
百度面试的还在门口等的时候,听见前面面试的铁哥们(俺舍友)貌似就在被问如何对数据进行哈希然后分布到多台机器上,在门外各种焦急,就差短信进去了,但估计发五个字又解释不清。很幸运的,我一进门第一道问题也是这个,面试开了个好头后面就比较容易,都是常规的大数据量处理以及字符串处理的一些算法,然后扯了扯搜索广告系统,很顺利的直接去三面聊天谈offer了,很lucky~

一致性哈希的什么四个要素可以看这里。简单的说就是将缓存的数据和存储数据的机器使用相同的哈希函数映射到同一地址空间上上,每个机器负责整个地址空间中的一定范围内的数据。

阅读全文…

CAP理论中提到一致性(Consistent),可用性(Available),分区容忍性(Partition Tolerance)三者在一个系统中只能同时满足两个,在分布式系统中分区是一定要存在的,系统的设计一般是在一致性和可用性之间做tradeoff。

一致性可以从客户端和服务器端分两种角度来进行描述。从客户端来就是做为观察者如何发现数据的更新,从服务端则是服务器如何来进行整个数据的更新来确保数据一致性。

客户端一致性:

假设系统中有A,B,C三个独立的process/thread做为client,A更新了系统中的某个数据。

  • 强一致性: 在数据更新完成后,任何随后的读都能返回A更新后的数据。
  • 弱一致性: 系统不保证后续的访问会访问到更新后的数据,但如果系统保证在A更新之后再没其他任何对于该数据的更新操作及失败,经过一段时间后,“不一致窗口”,后需的访问都可以访问到A更新后的数据,则是最终一致性,即最终一致性是弱一致性的一种特例。“不一致性窗口”的大小一般依赖于交互延迟、系统负载、复制的replica的个数等因素。

最终一致性又存在如下变体:

因果一致性(Causal consistency): 如果A通知了B它已经更新了数据,那么B的后需操作则读取到A写入的最新值,而与A没有因果关系的C遵守最终一致性语义,并不保证能立即读取到更新。

读自己写一致性(Read-your-writes consistency): 这个名字真难翻译,意思也很好理解,A更新了,A当然总能看到最新的值,这也是因果一致性的特例。

会话一致性(Session consistency): 此是上面那个一致性的实例,访问系统的进程存储在会话中,只要会话存在就能保证read-your-writes一致性,当由于某些失败会话终止后,新建立的会话则不再延续保证。

单调读一致性(Monotonic read consistency): 如果进程已经看到某个数据的值,则后续的读取不会再读到该数据之前的版本。

单调写一致性(Monotonic write consistency): 在此种情况下,系统保证同一个进程的写操作是串行化的。系统如果不保证此一致性就很难编程了。

上述的不同方式在实现中可以进行组合,在最终一致性的实践中,单调读一致性和read-your-write这两种属性经常组合实现。

服务端一致性:

对于服务端而言是如何尽快的将更新分布到系统,以提高用户的体验,有如下三个参数的说明

  • N   数据的备份数
  • W  更新完成时需要确认已经被成功的备份节点个数
  • R   读取数据时需要读取的备份节点个数

当 W + R > N,读和写的备份节点总是有重叠的,可以保证强一致性。当 W + R <= N时数据一致性就无法保证,即弱一致性/最终一致性。

在实际中可根据系统的需要进行W,R,N的配置,R=1,W=N对于读频繁的任务很优化;W=1,R=N对于写操作频繁则比较优化。但当W < (N+1)/2 时,则有可能会导致两个并发的写操作冲突,即他们的写节点不存在重叠。

Amazon Dynamo就设置了R + W > N的quorum-like的备份一致性更新策略,同时也采用了hint handoff的方式实现。即如果一个有N=3个备份的数据分别备份在A,B,C三个节点上,当写到A时,如果A临时的失效,则会把数据写到一个跟此Key无关的节点D上的专用local db,并提示D该数据应该在A上,D会周期的扫描这些数据并试图,当A节点恢复后,D会将该数据发送至A并删除local data.

Hinted Handoff的策略在多个非关系型数据库中都会被采用,包括Cassandra,人人网的Nuclear等。

Cassandra中还提供了多个一致性的Level可供客户端进行选择,包括

  • ZERO: 即一种完全异步的方式实现写,不关心返回
  • ONE:  当有一个节点更新了数据并提交了log,写操作即可返回
  • QUORUM:   N/2 + 1个备份被更新
  • ANY: 在QUORUM上添加了hinted handoff,而其他的一致性模型都要求更新在之前对备份负责的节点上。
  • ALL:  即写操作需要更新成功所有的备份节点。

参考:

Werner Vogels,   Eventually Consistency

Dietrich Featherston,  Cassandra: Principles and Application

    从去年开始接触NoSQL的知识,CAP理论可以说是整个NoSQL运动者的理论指导。

    CAP理论由UC Berkeley的Eric Brewer教授在2000年提出,并于2002年由MIT的Seth Gilbert & Nancy Lynch给出了严谨的证明。

    CAP理论认为以下三者不能同时满足:

    • 一致性(Consistency): 所有的节点在同一时刻看到同样的数据。
    • 可用性(Availability):  节点失效不会影响系统的读写。
    • 分区容忍性(Partition Tolerance): 系统能支持网络分区,即使分区之间的消息丢失系统也正常工作。

    对C、A、P三者的解读很有很多种,具体可以看后面的参考。

    通过上图我们可以看出,根据业务的不同,不同的存储系统会根据自身业务的需求在CAP三者中进行权衡,因此CAP理论的意义应该是一种在分布式数据存储系统设计时tradeoff,而非绝对的认为三者必须舍弃一者,特别是在CAP理论中没有提到系统的响应时间因素,而数据的访问时延是很重要的可用性因素。

    Yale的Daniel Abadi认为CAP理论简单的描述有可能造成错误的解读,重新定义了一个模型PACELC,添加了系统中的Latency描述。

    上图的意思是,如果一个系统需要进行分区,那就必须在可用性(A)或者一致性(C)之间做出一种tradeoff,否则就需要在系统的延迟(L)和一致性(C)之间做出tradeoff,此模型描述了大多数NoSQL数据库中实现CAP理论的方式,也更具备工程中的意义。

    参考:
    Julian Browne, Brewer’s CAP Theory 懒得看英文的可以看译文
    D. Abdi,   Problems with CAP, andYahoo’s little known NoSQL system

    ,