同步


分布式系统中, 有一个重要的问题: 如何取得时间上的一致

  • 单CPU系统中, 所有进程使用同一个始终, 内部保持时钟不变
  • 多CPu系统中, 每个CPU有自己的时钟,导致时钟偏移.

##1.1. 时钟同步算法

基础模型: 每台机器有一个每秒产生H次中断的计时器, 当计时器中断时, 终端处理程序将软件时钟加一, 每件时钟记录从过去某个约定时间开始的计数.

  • Cristian算法

适用于只有一台机器有时间服务器(time server), 其他所有机器都要与这台机器同步.

主要问题:

  1. 时间不可倒退(发送请求着时钟快于时间服务器, 接受时钟会导致严重错误)
  2. 时间服务器英法到达发送者有不确定的延迟.
  • Berkeley算法

时间服务器(时间守护进程)主动定时询问每台机器的时间, 基于回答,计算出平均时间并告诉所有其他机器将他们的时钟拨快(拨慢)到一个新的时间

  • 平均值算法

前两种都是集中式算法, 非集中式时钟同步算法是将时间划分成固定长度的再同步间隔. 第i次间隔开始于T + iR,结束于T + (i + 1)R, T为过去某个约定时间, R是系统参数,间隔开始每台机器广播自己时钟, 不同时间时钟不同, 广播开始时间不同. 一台机器广播后, 开始收集在时间间隔S内收到的广播. 结束后,执行算法在这些值中得到一个新的时间值, 最简单的就是计算平均值.

  • 时间戳算法

服务器维护一张表记录所有收到消息的时间戳(消息还有连接标识符), 当接受的消息的时间戳早于服务器保存的时间戳, 则拒绝接受.

为了删除旧的时间戳, 服务器位置一个全局变量(新旧消息的分界线):
G = CurrentTime - MaxLifttime(消息的最大生存时间) - MaxClockSkew(时钟与UTC的最大时钟偏移), 任何时间戳早于比G早的都可以安全删除, 比G新的接受.

##1.2. 逻辑时钟

所有机器的时钟达成内部一致就可以了, 不必要求必须与真实时间相同, 这种时钟称为逻辑时钟

- Lamport算法
定义了一种happen-before关系, 这种关系有两种情况:

  1. 如果a和b是在同一个进程中的两个事件, 且a在b之前发生, 则a→b为真
  2. 如果a是一个进程发送的消息事件, b是另一个进程接收这个消息的事件, 则a→b也为真.

happen-before关系传递关系. a→b,b→c, 则a→c. 如果两事件x,y发生在互不交换信息的进程中, 那么x→y和y→x都不真, 这两事件并发.

分配一个所有进程都认可的时间C(a), 这个时间值有性质如果a→b, 那么C(a) < C(b), 时钟值必须总是增加不能减少.

当消息到达并且接受者的时钟显示的时钟值比消息的发送时间早, 则接受者就将自己的时钟值调到比消息的发送时间大一.以此达到一个一致的时序.

###1.2.1. 向量时间戳

Lamport时间戳只通过事件a和b的时间值C(a)和C(b), 无法说明他们之间的关系. 不能获得因果关系

这个问题可以通过向量时间戳解决, 分配给时间a的向量时间戳VT(a)具有下列性质: 如果对事件b, 有VT(a) < VT(b), 那么认为a事件在因果关系上处于b之前. 向量时间戳的创建是通过让每个进程维护一个向量V来完成.向量的性质:

  1. $V_i[i]$ 是到目前为止进程$P_i$发生的时间的数量
  2. 如果$V_i[j] = k$, 那么进程$P_i$知道进程$P_j$中已经发生了k个事件

##1.3. 选举算法

通过选举算法选举一个协调进程, 一般选举进程号最大的那个

  • Bully算法

当任意进程发现协调进程不再相应要求时, 就发起一次选举, 选举过程为:

  1. 进程P向所有编号比他大的进程发送一个ELECTION消息
  2. 如果无人响应, 则进程P成为协调进程
  3. 如果有编号比它的相应, 则响应者接受选举工作, P工作结束(迭代) 进程号最大的进程总能赢得选举
  • 环算法

这个算法并不使用令牌, 环中每个进程都知道自己的后继进程, 当发现任意进程发现协调进程不工作, 就使用一个带自己进程号的ELECTION消息给后继,每一次传送进程, 都把自己的进程号加入到ELECTION消息中, 直到消息回到选举的发起者, 消息类型变成COORDINATOR消息, 再次循环,告知环中进程新协调者(进程号最大的一个), 然后消息删除

##1.4. 互斥

单处理器中, 使用信号量, Monitor或者类似数据结构保护临界区

  • 集中式算法

进程要进入临界区, 首先要向协调者发送情感求. 如果没有其他进程在临界区,协调者允许进程进入

优点: 简单, 可用于资源管理和一般的资源分配
缺点: 单一的协调进程的崩溃导致整个系统的瘫痪

  • 分布式互斥算法

Lamport完成了事件的排序, 可以用于分布式互斥提供时间戳

每个想要进入临界区的进程构造一个包含临界区名, 进程号和当前时间的消息, 发送给所有进程, 并能收到确认. 进程收到消息后, 根据自己与消息中临界区相关的状态来采取动作.

  1. 若接受者不在临界区也不想进入临界区, 它就向发送者发送一个OK消息
  2. 若接受者已经在临界区, 它不进行应答, 而是将该请求放入队列中
  3. 如果接受者想进入临界区但尚未进入时, 它将对收到的消息的时间戳与包含在在它发送给其他进程的消息的时间戳比较. 时间戳最早的那个进程获胜, 如果收到的消息的时间戳较早, 会给发送这发送OK消息, 如果晚, 接受者将收到的消息放在队列中, 不发送任何消息
    (适用于进程较少的情况)

优点: 一个进程的崩溃, 并不会造成整个系统崩溃
缺点: 比集中式算法更慢, 更复杂, 花费更高, 更不健壮

分布式

  • 令牌环算法

使用软件方法构造一个逻辑环, 环中为每个进程分配一个位置,让每个进程知道谁在他的下一个位置

环初始化后, 进程0得到一个令牌, 令牌让着环运行, 进程从临近进程得到令牌后, 检查自己是否要进入临界区, 如果要进入, 那么就直接进入, 当离开临界区后, 它沿着环继续传递令牌

优点: 不会造成饥饿, 保证只有一个进程在临界区
缺点: 如果令牌丢失, 这种情况难以检测到

环

三个算法进行比较:

比较

##1.5. 分布式事务

事务保护一个共享资源不会被几个并发进程同时访问. 事务允许进程把访问和修改数据项作为一项单独的原子操作完成.事务执行失败应该回复到初始状态

事务的四个特性:

  1. 原子性: 事务不可分割, 保证事务要么不发生, 要么全发生
  2. 一致性: 事务不能破坏系统的恒定性
  3. 独立性: 并发事务不会相互干扰
  4. 持久性: 一旦事务得到提交, 改变将永远存在
  • 单层事务: 原子性是优点也是缺点, 使事务不能分割
  • 嵌套事务: 嵌套事务由许多子事务组成, 顶层事务分支为在不同机器上并行运行的子事务
  • 分布式事务: 嵌套事务是按照逻辑关系分解成一层层子事务的事务, 而分布式事务逻辑上是一个单层的,不可分割的事务, 它的操作对象是分布式的数据.

嵌套事务

分布式事务

事务的实现: 文件系统为例, 进程开始一个事务, 它就分配一个私有工作空间, 这个工作空间包含所有它有权访问的文件. 在事务提交或中止前, 他的所有读写操作都在私有工作空间中进行, 而不是直接对文件系统操作. 复制私有空间的开销很大, 可以进行优化.

  1. 当进程值读取一个文件而修改时, 就不进行复制
  2. 赋值索引到工作空间

事务的另一种实现: 写前日志. 在任何数据块被修改前, 一条记录被写到日志说明修改情况, 只有当日志写入成功后, 此修改才可以被写入文件.

并发控制算法主要是保证多个事务可以同时被执行被保持独立.并发控制的总体思想是正确的调用想冲突的操作.
并发控制算法分为悲观算法和乐观算法:

  • 悲观算法: 如果某事务可以出错, 那么它就会出错, 在悲观算法中, 操作是在他们被执行前同步的, 这意味着冲突在允许发生前就解决了
  • 乐观算法: 基于错误一般不会发生的观点, 在事务结束的时候再进行同步, 如果此时发生了冲突, 一个或者更多的事务就被迫中止.