Zookeeper之Zab协议介绍(五)

时间:2021-04-29 08:27:18

B.同因果原子广播的比较

 

主次序原子广播设计成保持了因果次序特性,并瘾式地在增量状态更新创建时产生。在这一章节,我们将比较因果原子广播和主次序原子广播,并将论证,这两者是无法比较的。

 

因果次序的定义,是基于事件的前序(precedence, or happens before)关系。对于广播协议,事件分两种,要么是广播事件,要么是采用事件。我们采用<v, z>  <c  <v’, z’>,来表示abcast(<v, z>)先于abcast(<v’,z’>)发生。对于原子广播而言,因果次序基本定义为:

 

定义III.1. 因果次序:

如果<v, z>  <c  <v’, z’>,并且有进程p采用了<v’, z’>,那么该进程必定采用了<v,z>,并且先于<v’, z’>采用了<v, z>。

 

然而主次序原子广播并不满足因果次序特性。图三给出了一个例子。图中有两个事务<v, z>和<v’’, z’’>是因果关系,满足epoch(z) < epoch(z’) < epoch(z’’),但是事务<v,z>并没有被采用。简化起见,我们仅用事件来代表两个进程:

Zookeeper之Zab协议介绍(五)Zookeeper之Zab协议介绍(五)

 Zookeeper之Zab协议介绍(五)

主次序原子广播下采用的顺序以主因果次序关系<po来表示,它比因果次序关系<c更弱。事实上,不同主进程发送的事务,没有必要必须因果关联,即使它们是被同一个进程发送,也是如此。我们说,一个事件ε以主次序先于ε’,或表示为ε->poε’,当且仅当以下条件之一成立:

1  事件ε和ε属于同一个进程,ε先于ε发生,且以下条件之一成立:a). ε≠abcast(<v, z>)且ε abcast(<v’, z’>),或者b).epoch(z) = epoch(z’);

2  ε= abcast(<v, z>)并且ε=abdeliver(<v’, z’>);

3  存在事件ε’’,使得ε->poε’’且ε’’->poε

 

主因果次序关系<po的定义基于主次序先序关系(PO-precedence)。在因果关系定义中,我们用符号<po来替换<c 的,以此来表明主次序因果次序(PO causal order)。

 

主次序原子广播同样实现了另一个重要的特性,严格因果性(strict causality),即如果某个进程采用<v, z>和<v’, z’>,那么要么<v, z><po<v’, z’>,要么<v’, z’><po<v, z>。严格因果性是需要的,因为事务是基于增量更新方式广播,因此事务必须以产生它们时的相同状态,才能对该进行状态更新。于是这就是产生了因果关系更新链。然而,因果次序可以通过基于事务方式,而非因果关联进行发送。

 

图四展示了一个满足因果次序(也满足主次序因果次序 PO causal oder)的次序图,但它不满足严格因果性,因为<v, z>和<v’, z’>,即使它们没有因果关系,但都可以被采用。这表明严格因果性和主次序因果次序这两个原语,任何一个不比另一个更强(注:两者强弱无法比较)。

Zookeeper之Zab协议介绍(五)

 Zookeeper之Zab协议介绍(五)