Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1381956
  • 博文数量: 465
  • 博客积分: 8915
  • 博客等级: 中将
  • 技术积分: 6365
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-30 15:05
文章分类

全部博文(465)

文章存档

2017年(33)

2016年(2)

2015年(4)

2014年(29)

2013年(71)

2012年(148)

2011年(178)

分类: 大数据

2013-04-22 15:00:32

数据一致性实现

分布式存储在不同的节点的数据采取什么技术保证一致性,取决于应用对于系统一致性的需求,在关系型数据系统中一般会采用悲观的方法(如加锁),这些方法代价比较高,对系统性能也有较大影响,而在一些强调性能的系统中则会采用乐观的方法。

Quorum系统NRW策略

对于数据不同副本中的一致性,采用类似于 Quorum 系统的一致性协议实现。这个协议有三个关键值N、R和W。

N表示数据所具有的副本数。

R表示完成读操作所需要读取的最小副本数,即一次读操作所需参与的最小节点数目。

W表示完成写操作所需要写入的最小副本数,即一次写操作所需要参与的最小节点数目。

该策略中,只需要保证R+W>N,就可以保证强一致性。

例如:N=3W=2R=2,那么表示系统中数据有3个不同的副本,当进行写操作时,需要等待至少有2个副本完成了该写操作系统才会返回执行成功的状态,对于读操作,系统有同样的特性。由于R+W>N,因此该系统是可以保证强一致性的。

R+W>N会产生类似Quorum的效果。该模型中的读(写)延迟由最慢的R(W)副本决定,有时为了获得较高的性能和较小的延迟,RW的和可能小于N,这时系统不能保证读操作能获取最新的数据。

如果R+W>N,那么分布式系统就会提供强一致性的保证,因为读取数据的节点和被同步写入的节点是有重叠的。在关系型数据管理系统中,如果N=2,可以设置为W=2R=1,这是比较强的一致性约束,写操作的性能比较低,因为系统需要2个节点上的数据都完成更新后才将确认结果返回给用户。

如果R+WN,这时读取和写入操作是不重叠的,系统只能保证最终一致性,而副本达到一致的时间则依赖于系统异步更新的实现方式,不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

RW的设置直接影响系统的性能、扩展性与一致性。如果W设置为1,则一个副本完成更改就可以返回给用户,然后通过异步的机制更新剩余的N-W的副本;如果R设置为1,只要有一个副本被读取就可以完成读操作,RW的值如较小会影响一致性,较大则会影响性能,因此对这两个值的设置需要权衡。

下面为不同设置的几种特殊情况。

W= 1,R=N时,系统对写操作有较高的要求,但读操作会比较慢,若N个节点中有节点发生故障,那么读操作将不能完成。

R= 1,W=N时,系统要求读操作高性能、高可用,但写操作性能较低,用于需要大量读操作的系统,若N个节点中有节点发生故障,那么写操作将无法完成。

R=QR=QQ=N/ 2 + 1)时,系统在读写性能之间取得了平衡,兼顾了性能和可用性,Dynamo系统的默认设置就是这种,即N=3,W=2,R=2。

两阶段提交协议

两阶段提交协议[10]Two Phase Commit Protocol2PC协议)可以保证数据的强一致性,许多分布式关系型数据管理系统采用此协议来完成分布式事务。它是协调所有分布式原子事务参与者,并决定提交或取消(回滚)的分布式算法,同时也是解决一致性问题的一致性算法。该算法能够解决很多的临时性系统故障(包括进程、网络节点、通信等故障),被广泛地使用。但是,它并不能通过配置来解决所有的故障。为了能够从故障中,两阶段提交协议使用日志来记录参与者(节点)的状态,虽然使用日志降低了性能,但是参与者(节点)能够从故障中恢复。

在两阶段提交协议中,系统一般包含两类机器(或节点):一类为协调者(Coordinator),通常一个系统中只有一个;另一类为事务参与者(ParticipantsCohortsWorkers),一般包含多个,在数据存储系统中可以理解为数据副本的个数。协议中假设每个节点都会记录写前日志(Write-ahead Log)并持久性存储,即使节点发生故障日志也不会丢失。协议中还假设节点不会发生永久性故障,而且任意两个节点都可以互相通信。

当事务的最后一步完成之后,协调者执行协议,参与者根据本地事务是否成功完成来回复同意提交事务或者回滚事务。

顾名思义,两阶段提交协议由两个阶段组成。在正常的执行下,这两个阶段的执行过程如下所述。

阶段1:请求阶段(commit-request phase,或称表决阶段,voting phase

在请求阶段,协调者将通知事务参与者准备提交或取消事务,然后进入表决过程。在表决过程中,参与者将告知协调者自己的决策:同意(事务参与者本地作业执行成功)或取消(本地作业执行发生故障)。

阶段2:提交阶段(commit phase

在该阶段,协调者将基于第一个阶段的投票结果进行决策:提交或取消。当且仅当所有的参与者同意提交,事务协调者才通知所有的参与者提交事务,否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行相应的操作。

注意两阶段提交协议与两阶段锁协议不同,两阶段锁协议为一致性控制协议。

该协议的执行过程可以通过下图2-2来描述

2-2两阶段提交协议

两阶段提交协议最大的缺点在于它是通过阻塞完成的协议,节点在等待消息的时候处于阻塞状态,节点中其他进程则需要等待阻塞进程释放资源。如果协调者发生了故障,那么参与者将无法完成事务而一直等待下去。以下情况可能会导致节点发生永久阻塞。

如果参与者发送同意提交消息给协调者,进程将阻塞直至收到协调者的提交或回滚的消息。如果协调者发生永久故障,参与者将一直等待,这里可以采用的协调者,所有参与者将回复发给备份协调者,由它承担原协调者的功能。

如果协调者发送“请求提交”消息给参与者,它将被阻塞直到所有参与者都回复完,如果某个参与者发生永久故障,那么协调者也不会一直阻塞,因为协调者在某一时间内还未收到某参与者的消息,那么它将通知其他参与者回滚事务。

同时两阶段提交协议没有容错机制,一个节点发生故障整个事务都要回滚,代价比较大。

下面我们通过一个例子来说明两阶段提交协议的工作过程。

A组织BCD三个人去爬长城:如果所有人都同意去爬长城,那么活动将举行;如果有一人不同意去爬长城,那么活动将取消。用两阶段提交协议解决该问题的过程如下。

首先A将成为该活动的协调者,BCD将成为该活动的参与者。

阶段1

A发邮件给BCD,提出下周三去爬山,问是否同意,那么此时A需要等待BCD的邮件。

BCD分别查看自己的日程安排表。BC发现自己在当日没有活动安排,则发邮件告诉A他们同意下周三去爬长城。由于某种原因,D白天没有查看邮件。那么此时ABC均需要等待。到晚上的时候,D发现了A的邮件,然后查看日程安排,发现周三当天已经有别的安排,因此D回复A“活动取消”。

阶段2

此时A收到了所有活动参与者的邮件,并且A发现D下周三不能去爬山,于是A发邮件通知BCD,下周三爬长城活动取消。

此时BC回复A“太可惜了”,D回复A“不好意思”。至此该事务终止。

通过该例子可以发现,两阶段提交协议存在明显的问题。假如D一直不能回复邮件,那么ABC将不得不处于一直等待的状态。并且BC所持有的资源一直不能释放,即下周三不能安排其他活动。其他等待该资源释放的活动也将不得不处于等待状态。

基于此,后来有人提出了三阶段提交协议,在其中引入超时的机制,将阶段1分解为两个阶段:在超时发生以前,系统处于不确定阶段;在超时发生以后,系统则转入确定阶段。

两阶段提交协议包含协调者和参与者,并且二者都有出现问题的可能性。假如协调者出现问题,我们可以选出另一个协调者来提交事务。例如,班长组织活动,如果班长生病了,我们可以请副班长来组织。如果参与者出问题,那么事务将不会取消。例如,班级活动希望每个人都能参加,假如有一位同学不能参加了,那么直接取消活动即可。或者,如果大多数人参加,那么活动如期举行(两阶段提交协议变种)。为了能够更好地解决实际的问题,两阶段提交协议存在很多的变种,例如:树形两阶段提交协议(或称递归两阶段提交协议)、动态两阶段提交协议(D2PC)等。

作者简介

陆嘉恒,人民大学教授,博士生导师。2006年毕业于新加坡国立大学计算机科学系,获博士学位;2006-2008年在美国加利福尼亚大学尔湾分校(University of California, Irvine)进行博士后研究;年加入中国人民大学,2012年破格晋升为教授。主要研究领域包括技术和技术。先后在SIGMODVLDBICDEWWW等国际重要会议和期刊上发表数据库方向的论文40多篇,主编多本云计算和大数据的教材和著作。

本文节选自《大数据挑战与NoSQL数据库技术》一书。陆嘉恒编著,由电子工业出版社出版。

阅读(1125) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~