乐观复制算法5. 多master的statetransfer系统

5.masterstate-transfer系统

       我们现在开始着手在多master系统中实现一致性。这一章讨论state-transfer系统;对operation-transfer系统的讨论在第6和第7章。

       一个state-transfer系统在每个节点包括下面组成部分:对象内容,描述副本如何更新的信息(比如,a timestamp)。副本一致性管理通常通过下面步骤实施:

1)一个站点决定与另一个站点交换更新。许多系统拉取更新;比如,他们依靠周期性的轮询(例如,FTP镜像,DNS区域传输)。另一些系统,比如NIS,推送更新;比如,他们让一个有更新的副本负责将更新发送到其它副本。拉取与推送的选择是正交的,但它影响到系统的扩展性。我们在9.3节对推送机制进行更详细的讨论.

2)两个站点发现那些对象内容不同。(5.1节)

(注意:这里是两个站点,应该是通过两两比较来发现不同)

3)对每一个修改了的对象,站点需要发现它是否被并发修改。如果是,它们需要解决冲突。(5.2节)

4)解决后的状态被复制到各个副本。

       我们将讨论Thomas写规则,一个流行的技术即可用来发现不同副本,也可解决冲突。我接着将介绍几个能更精细的发现冲突并解决他们的算法。最后,我们将讨论扩展性问题和空间开销。

5.1 使用Thomas写规则的更新传播与冲突处理

       State-transfer系统仅需要在哪个副本存储了最新内容上达成一致,因为将内容从最新副本传输到其它节点能让所有的副本获得更新。Thomas写规则是用于这个目的的最流行算法。[Birrell et al. 1982; Mockapetris and Dunlap 1988; Rabinovich et al. 1996; Gwertzman and Seltzer 1996].它名字来源于一篇介绍基于选举的悲观复制算法的文章[Thomas1979],但现在它被广泛用于乐观环境中。

       Thomas写规则如图4所示。采用Thomas写规则管理的内容是短暂的;一个更新能被并发的另一个用户的更新覆盖,没有人能确定一个更新何时被应用到所有的副本。

采用Thomas写规则,删除一个对象需要特殊处理。简单的删除一个副本以及它的时间戳,会造成update/delete的歧义。考虑站点a更新了对象内容(时间戳Ta,站点b同时删除了这个对象(时间戳Tb).稍后,站点c接收到从b节点的更新,从磁盘上删除掉副本和时间戳。站点c接收与站点a通信。对于站点c如果Ta>Tb那么正确的操作就是创建一个对象,并忽略更新。但站点c没法这样做,因为它不再存储这个时间戳。

说明:在我们实现的Robin中,这个问题在服务器端也存在。假设服务器就是站点c,服务器采用抢占式方式接受请求,站点aupdate与站点bdelete在站点c执行后必将有一个全局序。如果先收到站点bdelete请求并执行,再收到update请求时会返回站点a请求失败,站点aupdate请求转化为create请求发送给服务器并执行,服务器记录下操作日志将是,delete-create,这样其它节点需要同步时,执行delete-create操作即可。这个delete-updatedelete-create的转化就是语义层的转化。

       4. 使用Thomas写规则传播更新。每一个对象保存一个时间戳ts,标记对真实副本数据的最后一次修改。更新在本地发生利用IssueUpdate。每一个站点周期调用ReceiveUpdate,如果它的时间戳小于某一个站点的,那么将下载该站点的内容。

思考:这里的问题是,如何在各个站点提供全局一致的时间

       两种方案来解决udpate/delete的歧义。第一种是采用离线方式,用户干预删除对象,例如在DNSNIS中。第二种方式保存从磁盘上删除对象的时间戳(但不保存内容),例如在UsenetActive Directory,和Clearinghouse。这样的时间戳通常被称作“death certificates”或“tombstones”。

5.2 State-transfer系统中检测与解决冲突

Thomas写规则对冲突解决实现了一个“Last writer wins”策略;他通过让节点最终收敛于最新状态来保证一致性(假设通信是完善的,更新最终不再产生)。这个规则不能显示地发现冲突,对于不能容忍更新丢失的交互应用这不具有吸引力。相关研究发展了两种技术来减缓这种情况:two-timestamp算法和version vectors.

5.2.1 Two-Timestamp 算法

       Two-timstamp算法扩展了Thomas的写规则来检测句法冲突。[Balasubramaniam and Pierce 1998; Gray et al. 1996].它被用在Lotus NotesPalm Pilot中。在operation transfer中一些系统也采用了同样的技术。

       这里,a站点为对象i保存一个时间戳Ti和前一个时间PiTi随每次对象变化而更新。站点ab通信,比较时间戳,采用下面的动作:

1)如果Ta=Tb & Pa=Pb,那么副本没有被修改。

2)如果 Ta>Tb & Pa = Pb,对象仅在站点a修改。站点b从站点a拷贝副本,并将Tb,Pb以及Pa设置为Ta。对称的,如果Tb>Ta & Pb=Pa,那么从站点b拷贝内容到a

3)如果上面两种情况都不满足,则更新冲突。

思考: TaTbPaPb这四个时间,即站点a和站点b是否需要全局时间?

       这项技术的不足是不准确。当Master节点多余两个时,它可能会报告不准确的冲突,如图Figure 5。这个技术只能适用于Master节点很少,冲突也很少的情况下。

Fig 5. 使用two-timstamp算法发现冲突错误的情况。TxPx表示在站点x当前的和前一个时间戳。在第四步,站点ac同步,算法发现了一个冲突,即使严格的来说站点c的数据比a落后。

5.2.2 版本向量

版本向量(附件A.3)是另一种Thomas写规则的扩展,比前一种算法要准确许多。它第一次被用在Locus分布式操作系统。

       Thomas写规则中一个时间戳不同,在站点i上的一个副本拥有一个向量时间戳VVi,含有M个元素(对不同的对象,VV是不同的 [即每一个对象都有一个时间戳向量])VVi[i]表示在站点i对对象发生的最后更新时间,VVi[j]表示站点i接收到在站点j发生的最后更新时间。VV的交换、更新、比较采用常用的时间戳向量算法(附件A.3)。站点ab检测冲突的步骤如下:

1)    如果VVa=VVb,副本并没有被修改。

2)    如果VVa主导VVb,对象仅在站点a进行修改。站点b从站点a拷贝内容和VV。对称的,如果VVb主导VVa,内容和VV从站点b拷贝到a

3)    其它情况,存在语法冲突。

two-timestamp算法不同,VVs是完善和准确的;VV只有当真实的语法冲突存在时就能发现。不好的方面是不能方便地增加和移除Master节点,因为VVs已经将master节点编码到它的内部。

思考:这个方法确实能准确的检测出冲突,但是节点扩展很麻烦。Master节点越多,当发生冲突时解决起来越麻烦。

思考:无论是two-timstamp还是 version-vector都有一个问题,分配给对象的时间戳与对象绑定,不同对象的时间戳是相互独立的。但在文件系统中相互独立这一点不成立,因为目录下文件的修改会改变目录的最后修改时间属性。所以在开发文件同步时会放宽同步要求,对于目录的一些属性不进行同步。

5.2.3 State-transfer系统的冲突解决

       一旦在语法层次上的冲突被发现,无论使用前面那一种算法,它必须被解决。很多系统简单的存储对象的两个版本,并请求用户来解决。

有时,挖掘对象的语义信息有可能自动解决冲突。例如Locus,Ficus,Roam,Coda,对孰知的文件类型通过resolver程序,结合语义来检测和解决冲突。比如,在邮件目录文件的一个语法冲突,可以通过计算来自多个冲突副本的信息单元来解决。在另一方面,对于编译产生的文件冲突不用解决,因为他们可以从源文件中编译产生。

       写一个自动冲突解决器并不是一个轻松地工作。首先,在state-transfer系统中语义解决是否有限,前面的mail resolver,如果消息在一个副本重现将删除该消息。其次,resolver必须遵循严格的规则来保证一致性。这是必须确定的;选取和运行在resolver上规则,对于每一个冲突解决站点是统一的。一个resolver仅能依赖当前状态,不能访问随时间或站点变化的信息,比如当前系统时间或站点名。Resolver之间必须通信;例如,假设存在一个更新冲突集合,解决方法必须能生成一致的结果无论他们到达站点的顺序。

最终,解决器如果因为使用了超出限制的资源而失败,必须确切的失败:所有的站点必须采用统一的限制,在CPU、内存、以及文件资源等,在运行时必须强制执行这些限制。

5.3 支持大对象

       (说明: state-transfer系统,同步时传输的就是对象的timestamp,只有当发现需要进行更新时才传输数据对象。)

State传输系统的主要扩展瓶颈是更新(传播的开销)将会随着对象大小的增加而增加。这个问题可以通过多种方式解决,并不失state传输的简单性。

       一些系统采用混合Stateoperation的传输;比如,DNS的增量zone传输,CVS,以及Porcupine。这里,每个站点保存对象过去较短时间内的更新,以及更新对应的时间戳,该时间戳记录何时更新被应用到副本上。当更新其它副本时,如果该副本的时间戳落在已保存的更新历史中,将仅发送差异部分,使得副本达到最新状态。否则,将发送整个对象。这个技术比operation-transfer要简化许多,但它需使用单个时间戳来串行化更新。

       另一种途径是将对象划分为更小的子对象。关键问题是有效的发现子对象的最新更新,因为要简单地选出相互对立的子对象代价是十分高昂的。一些系统将子对象组织成一棵树(对于复制文件系统这十分自然),让每个参与节点记录下对它孩子最新更新的时间戳。然后基于这个写时间戳来应用Thomas写规则,逐步向下深入树,并缩小对数据内容的修改。其他系统明确地保存对子对象的更新日志,并采用与VesionVector类似的数据结构来检测对子对象的修改。他们非常像operation传输系统,但在很多重要方面存在不同。首先,日志是小的、受限的,因为它们仅记录被修改子对象的名字,以及数目非常有限的子对象。其次,他们仍采用Thomas写规则来串行化对每个子对象的修改。

5.4 在空间上的开销

       Tombstonesstate传输系统空间开销的主要源头(VV-based系统仍需要将VVs保存为tombstones)。尽管tombstone很小,当对象频繁的创建和删除时,它仍会填满磁盘。对于绝大多数系统,tombstones会在一个固定周期后删除。这个周期要足够长,从而保证大部分更新能传播完全,当也要足够小从而保证较低的空间开销;比如,一个月的周期。这项技术不绝对安全,当通常在实际中工作的很好。

       一些系统采用一致性算法来安全的删除tombstonesRoamFicus采用两段协议来保证每个站点,在移除对应的tombstone前,获得了更新。阶段一,通知一个站点,所有节点接受到了更新。阶段二,确保所有站点接受到了删除tombstone”请求。相似的协议同样在Porcupine系统中使用。





原文地址:https://www.cnblogs.com/lqxinxin/p/3095682.html