如果不能正常显示,请查看原文 , 或返回

分布式的一致性

2013-05-18 19:06 8151人阅读 评论(1) 收藏 举报
本文章已收录于:
分类:

版权声明:本文为博主原创文章,未经博主允许不得转载。

本文来自《分布式原理与泛型》的一致性章节笔记。由于缺乏实践经验,这本书对我来说太过理论,难于理解,现在已经暂停该书的阅读,转而加强实践。另有相关博文《CAP和最终一致性》,可供参考阅读。

1.分布式的一致性概述

分布式系统的一个重要问题是数据的复制。对数据的复制一般有两个原因:

  • 1.增加系统的可靠性,防止单点失效的问题;
  • 2.提高系统性能,利用不同地理位置的副本迅速响应用户需求。

数据复制的主要难题是保持各个副本的一致性。即在更新一个副本时,必须确保同时更新其他的副本,否则数据的各个副本将不再相同。

2.以数据为中心的一致性模型

一致性模型实质上是进程和数据存储之间的一个约定。正常情况下,一个数据项上执行读操作时,它期待该操作返回的是该数据在其最后一次写操作之后的结果。在没有全局时钟的情况下,精确的定义哪次写操作是最后一次写操作是十分困难的。于是就产生了一系列用其他方式定义的一致性模型。

2.1 持续一致性

有人提定义了区分不一致性的三个互相独立的坐标轴:副本之间的数值偏差,副本之间新旧程度偏差以及更新操作顺序的偏差。

数值偏差可以这样理解:已应用于其他的副本,但还没有应用于给定副本的更新数目。

文中使用了向量时钟来举例对一致性单元进行持续抑制性分析,

2.2 严格一致性

任意read(x)操作都要读到最新的write(x)的结果。 依赖于绝对的全局时钟,实际系统不可能做到。

2.3顺序一致性

对于一些读写写操作的集合,所有进程看到的都是同样的顺序。也就是将并行的操作序列化,而且每个进程得到的序列都相同。

那么,很自然对于同一个进程执行的操作,必然要按照它们执行的顺序出现。

2.4因果一致性(Casual Consitency)

要求:

有因果关系的写操作必须按照它们的因果关系的顺序被看到,没有因果关系的写操作可以以任意顺序被别的进程看到。

例如:(其中[....]是占位符,表示没有操作)

进程1 W(x)a 将x写成a 进程2 [..]R(x)a W(x)b 进程3 [....]R(x)a R(x)b 进程4 [....]R(x)b R(x)a

进程3和1、2是满足因果一致性的,加上4就不满足了。因为进程2是由于读到x=a才把x写成b的,所以W(x)a和W(x)b之间有因果关系,必须按照因果的顺序出现。

相比顺序一致性,去掉了那些没有联系的操作达成一致顺序观点的要求,只是保留那些必要的顺序(有因果关系的)。

2.5入口一致性(Entry Consistency)

其实也就是对每个共享数据定义一个同步变量(即:锁)。当然,没有进行同步就进行的读操作结果是不保证的。

3 客户为中心的一致性

也就是从用户视角来看数据是一致的。只是关心数据最终会一致(eventually consitent)。

只要保证对于同一个用户,他访问到的数据是一致的就可以了。如果用户只是访问一个副本,这个就很好实现,否则就需要一定策略了。当没有更多的更新的时候,要保证当前的更新会最终传播到所有的副本上。著名的例子有:DNS系统,万维网。

但最终一致性需要注意一个典型的问题。即当客户访问不同的副本时,问题就出现了。更具体的例子比如,博客作者更改了一篇博文内容,在A地的用户先访问到最新的内容,而B地由于离博客服务器远,看到的还是原先的内容。

对于最终一致性的的数据存储而言,这个示例很有代表性。问题是由用户有时可能对不同的副本进行操作的事实引起的。以客户为中心的一致性分为如下几大类:

3.1 单调读(Monotonic Reads)

当进程从一个地方读出数据x,那么这个以后再读到的x应该是和当前x相同或比当前更新的版本。也就是如果进程迁移到了别的位置,那么对x的更新应该比进程先到达。这里的客户就是指这个进程。

3.2 单调写(Monotonic Writes)

跟单调读相应,如果一个进程写一个数据x,那么它在本地或者迁移到别的地方再进行写操作的时候,原来的写操作必须要先传播到这个位置。也就是进程要在任何地方至少和上一次写一样新的数据。

3.3 Read your writes

一个进程对于数据x的写操作,那么进程无论到任何副本上都应该看到这个写操作的影响,也就是看到和自己写操作的影响或者更新的值。

3.4 Writes follow reads

顾名思义了,也就是在读操作后面的写操作要是基于至少跟上一次读出来一样新的值。也就是如果进程在地点1读了x,那么在地点2要写x的副本的话,至少写的时候应该是基于至少和地点1读出的一样新的值。

4 副本放置(Replica Placement)

4.1 放置的三个方法

Permanent replica/永久副本: 选几个固定位置放置副本,镜像呈现。

Server-initiated/服务端发起: 服务端动态决定什么时候向什么地方分发副本,又称push cache

Client-initiated/客户端发起: 客户端缓存,client cache

4.2 更新传播

4.2.1 传播什么?
  • 可以是更新的通知(客户自己来取)
  • 可以是更新后的数据
  • 可以是更新的操作
4.2.2 谁来传播
  • 服务器push或客户pull
4.2.3 传播协议?
  • 保证最终会收敛到一致

4.3 复制协议(Replication Protocols)

4.3.1 远程写(Remote-Write)协议

对于数据x有一个主副本,当没有x副本的服务器操作x的时候就会得到一个x的副本。而有x副本的服务器响应客户读请求的时候可以立刻返回。而当客户进行写操作的时候,写操作首先在主副本完成,然后再通知其他副本更新。

4.3.2 本地写(Local-Write)协议

和远程写比较类似,不同点是当一个服务器得到了副本以后就成了新的主副本,以后的写操作首先在本地完成,然后再通知其他的副本,本地写的名字由此而来。

4.3.3 主动复制(Active Replication)

对于副本的操作要设计到另外一个单一对象。比如,n个副本代理对象C的一个接口,如果向所有副本发出请求,每个副本都会发一个请求到C,那么同样的操作就执行了n次。所以需要一个协调者。另外,多副本返回值的时候也会有同样的情况。所以这种只执行一次的动作需要副本种有一个协调者,保证操作只被执行一次或者只返回一次。

3.3.4 基于候选团(Quorum-Based)协议

也就是读操作要得到r个服务器的同意,写操作要得到w个进程的同意。总共有n个进程。r和w要满足以下条件:

  • r+w > n 这样就不可能同时发生读写,并且读到的server肯定有一个以上被更新过的
  • w > n/2 这样就不可能同时发生两个写

也就是类似于投票获得读写的锁。在Dynamo系统中可以配置这种wrn参数以自持特定的一致性。


PS:  欢迎访问博客的新家:http://biaobiaoqi.me/blog/2013/05/18/distributed-consistency/

       这里有更好的排版 ;)

1
0

我的同类文章

返回