分布式系统的一致性算法简介

标签: 系统 算法 | 发表时间:2015-06-03 03:43 | 作者:welcome66
分享到:
出处:http://www.iteye.com

在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解。在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:

1、任何一次修改保证数据一致性。

2、多次数据修改的一致性。

在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能。例如最终一致性,无所谓每次用户修改后的多副本的一致性及格过,只要求在单调的时间方向上,数据最终保持一致,如此获得了修改极大的并发性能。

在强一致性的算法中,强调单次修改后结果的一致,需要保证了对问题1和问题2要求的实现,牺牲了并发性能。本文是讨论对解决问题1实现算法,这些算法往往在强一致性要求的应用中使用。

解决问题1的方法,通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

 

  • 两阶段提交算法

 

 

在两阶段提交协议中,系统一般包含两类机器(或节点):一类为协调者(coordinator),通常一个系统中只有一个;另一类为事务参与者(participants,cohorts或workers),一般包含多个,在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成,在正常的执行下,这两个阶段的执行过程如下所述:

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

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

  • 阶段2:提交阶段(commit phase)。

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

          举个例子:A组织B、C和D三个人去爬长城:如果所有人都同意去爬长城,那么活动将举行;如果有一人不同意去爬长城,那么活动将取消。用2PC算法解决该问题的过程如下:
  • 首先A将成为该活动的协调者,B、C和D将成为该活动的参与者。
  • 阶段1:A发邮件给B、C和D,提出下周三去爬山,问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排,则发邮件告诉A它们同意下周三去爬长城。由于某种原因,D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候,D发现了A的邮件,然后查看日程安排,发现周三当天已经有别的安排,那么D回复A说活动取消吧。
  • 阶段2:此时A收到了所有活动参与者的邮件,并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D,下周三爬长城活动取消。此时B、C回复A“太可惜了”,D回复A“不好意思”。至此该事务终止。

两阶段提交算法在分布式系统结合,可实现单用户对文件(对象)多个副本的修改,多副本数据的同步。其结合的原理如下:

          1、客户端(协调者)向所有的数据副本的存储主机(参与者)发送:修改具体的文件名、偏移量、数据和长度信息,请求修改数据,该消息是1阶段的请求消息。

2、存储主机接收到请求后,备份修改前的数据以备回滚,修改文件数据后,向客户端回应修改成功的消息。 如果存储主机由于某些原因(磁盘损坏、空间不足等)不能修改数据,回应修改失败的消息。

3、客户端接收发送出去的每一个消息回应,如果存储主机全部回应都修改成功,向每存储主机发送确认修改的提交消息;如果存在存储主机回应修改失败,或者超时未回应,客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。

4、存储主机接收到客户端的提交消息,如果是确认修改,则直接回应该提交OK消息;如果是取消修改,则将修改数据还原为修改前,然后回应取消修改OK的消息。

5、 客户端接收全部存储主机的回应,整个操作成功。

      在该过程中可能存在通信失败,例如网络中断、主机宕机等诸多的原因,对于未在算法中定义的其它异常,都认为是提交失败,都需要回滚,这是该算法基于确定的通信回复实现的,在参与者的确定回复(无论是回复失败还是回复成功)之上执行逻辑处理,符合确定性的条件当然能够获得确定性的结果哲学原理。

  • 分布式锁服务

 分布式锁是对数据被外界修改持保守态度,在整个数据处理过程中将数据处于锁定状态,在用户修改数据的同时,其它用户不允许修改。
      采用分布式锁服务实现数据一致性,是在操作目标之前先获取操作许可,然后再执行操作,如果其他用户同时尝试操作该目标将被阻止,直到前一个用户释放许可后,其他用户才能够操作目标。分析这个过程,如果只有一个用户操作目标,没有多个用户并发冲突,也申请了操作许可,造成了由于申请操作许可所带来的资源使用消耗,浪费网络通信和增加了延时。
      采用分布式锁实现多副本内容修改的一致性问题, 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致, 可以对整个文件修改设置一把锁,修改时申请锁,修改这个文件的多个副本,确保多个副本修改的一致,修改完成后释放锁;也可以对文件分段,或者是文件中的单个字节设置锁, 实现更细颗粒度的锁操作,减少冲突。

常用的锁实现算法有Lamport bakery algorithm (俗称面包店算法), 还有Paxos算法。下面对其原理做简单概述。

 

 

  • Lamport面包店算法

 

 

是解决多个 线程 并发访问一个共享的单用户资源的 互斥问题的算法。 由 Leslie Lamport英语Leslie Lamport)发明。    
    Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购,安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买,就必须重新排队。
     这个类比中的顾客就相当于线程,而入店购货就是进入 临界区独占访问该共享资源。由于计算机实现的特点,存在两个线程获得相同的签到号码的情况,这是因为两个线程几乎同时申请排队的签到号码,读取已经发出去的签到号码情况,这两个线程读到的数据是完全一样的,然后各自在读到的数据上找到最大值,再加1作为自己的排队签到号码。为此,该算法规定如果两个线程的排队签到号码相等,则线程id号较小的具有优先权。

把该算法原理与分布式系统相结合,即可实现分步锁。

 

 

  • Paxos算法

 

 

 该算法比较热门,参见WIKI, http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95

Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。节点通信存在两种模型:共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby,而Chubby使用Paxos算法来保证备份的一致性。

  • 采用乐观锁原理实现的同步

      我们举个例子说明该算法的实现原理。如一个金融系统,当某个操作员读取用户的数据,并在读出的用户数据的基础上进行修改时(如更改用户帐户余额),如果采用 前面的分布式锁服务机制,也就意味着整个操作过程中(从操作员读出数据、开始修改直至提交修改结果的全过程,甚至还包括操作员中途去煮咖啡的时间), 数据库记录始终处于加锁状态,可以想见,如果面对几百上千个并发,这样的情况将导致怎样的后果。
      乐观锁机制在一定程度上解决了这个问题。乐观锁,大多是基于数据版本( Version)记录机制实现。何谓数据版本?即为数据增加一个版本标识,在基于数据库表的版本解决方案中,一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时,将此版本号一同读出,之后更新时,对此版本号加一。此时,将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对,如果提交的数据版本号大于数据库表当前版本号,则予以更新,否则认为是过期数据。
       对于上面修改 用户帐户信息的例子而言,假设 数据库中帐户信息表中有一个 version 字段,当前值为 1 ;而当前帐户余额字段( balance )为 $100 。

  1. 操作员 A 此时将其读出(version=1 ),并从其帐户余额中扣除 $50($100-$50 )。
  2. 在操作员 A 操作的过程中,操作员B也读入此用户信息( version=1 ),并从其帐户余额中扣除 $20 ( $100-$20 )。
  3. 操作员 A 完成了修改工作,将数据版本号加一( version=2 ),连同帐户扣除后余额( balance=$50 ),提交至 数据库更新,此时由于提交数据版本大于数据库记录当前版本,数据被更新,数据库记录 version 更新为 2 。
  4. 操作员 B 完成了操作,也将版本号加一( version=2 )试图向 数据库提交数据( balance=$80 ),但此时比对数据库记录版本时发现,操作员 B 提交的数据版本号为 2 ,数据库记录当前版本也为 2 ,不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略,因此,操作员 B 的提交被驳回。这样,就避免了操作员 B 用基于 version=1 的旧 数据修改的结果覆盖操作员A 的操作结果的可能。

乐观锁机制与分布式系统相结合上, 我整理了伪代码如下:

obj  操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本,每次修改该值递增
set( obj, value)
{
     //从每个节点上取出修改前的对象版本
    get original_ver = obj.atom_update_ver from each node;
     //将值赋到每个节点的obj目标
    set obj = value from each node;
     //条件修改每个节点的obj版本,目标版本加一
     //比较和修改操作是原子操作
    result = (set obj.atom_update_ver = original_ver + 1
                  where  original_ver + 1 >  obj.atom_update_ver
                   for each node);
    if(result == ok)
        return set_ok;
    else
        return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题,在后续我将分析采用乐观锁原理实现一致性算法,解决问题2、节点失效、通信失败等问题。



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [系统 算法] 推荐:

推荐系统的常见推荐算法的性能比较

- - ITeye博客
数据集是movielens-1M( 下载)版本. 使用SlopeOne算法,每次随机选取6%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:. 绘制成折线图,如下图所示:.  由此可知,训练集越大,则推荐的准确率越高. 使用ItemCF算法,训练集大小为数据集的90%,每次随机选取30%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:.

分布式系统的一致性算法简介

- - 互联网 - ITeye博客
在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解. 在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:. 1、任何一次修改保证数据一致性. 2、多次数据修改的一致性. 在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能.

工作职位推荐系统的算法与架构

- - IT瘾-bigdata
作者:Preetha Appan. Indeed.com 每个月有两亿不同的访客,有每天处理数亿次请求的推荐引擎. 在这篇文章里,我们将描述我们的推荐引擎是如何演化的,如何从最初的基于Apache Mahout建立的最简化可用行产品,到一个在线离线混合的成熟产品管道. 我们将探索这些变化对产品性能指标的影响,以及我们是如何通过使用算法、架构和模型格式的增量修改来解决这些挑战的.

一致性哈希算法及其在分布式系统中的应用

- BeerBubble - 博客园-EricZhang&#39;s Technology Blog
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用. 首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题.

揭秘Facebook 广告系统核心算法Pacing工作原理 (含案例)

- - 互联网的那点事
Pacing是Facebook广告系统中花费预算的节奏的一个算法,Google Adwords里面有一个功能是设定好预算和最高出价,Adwords就可以自动通过出价调节,让你在这个限定的预算下获取最多的点击,Pacing这个算法和Adwords的这个功能很类似,都是通过调节出价,让广告主获得最大的ROI.

推荐系统中常用算法 以及优点缺点对比

- - 人人都是产品经理
【Martin导读】随着互联网特别是社会化网络的快速发展,我们正处于信息过载的时代. 用户面对过量的信息很难找到自己真正感兴趣的内容,而内容提供商也很难把优质的内容准确推送给感兴趣的用户. 推荐系统被认为是解决这些问题的有效方法,它对用户的历史行为进行挖掘,对用户兴趣进行建模,并对用户未来的行为进行预测,从而建立了用户和内容的关系.

基于Spark MLlib平台的协同过滤算法---电影推荐系统

- - zzm
又好一阵子没有写文章了,阿弥陀佛...最近项目中要做理财推荐,所以,回过头来回顾一下协同过滤算法在推荐系统中的应用.     说到推荐系统,大家可能立马会想到协同过滤算法. 本文基于Spark MLlib平台实现一个向用户推荐电影的简单应用. 基于模型的协同过滤应用---电影推荐.     一、协同过滤算法概述.

用Hadoop流实现mapreduce版推荐系统基于物品的协同过滤算法

- - CSDN博客推荐文章
       以个性化新闻推荐为例,整个过程分成两个mapreduce阶段,由于hadoop流不支持多个mapreduce过程的自动化,所以所有mapreduce过程命令必须人工一个一个的执行. 1、首先需要将原始数据处理成如下形式的两个文件. 文件一:Item_user_score.txt. 如下图中第一行,物品100655565被用户1634974浏览过,则将分数记为1.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.