首页 理论教育分布式数据库的可线性化性质

分布式数据库的可线性化性质

【摘要】:可线性化具有以下性质。参考文献[1]证明了可线性化具有局部(本地)性质。历史H 2是非可线性化的。可线性化可以看成是严格可串行化的一种特殊情况,即将事务限制在由单对象的单操作构成上。图11.1是可线性化执行序列的一个示例,这是一个4字节编址地址存储器,共有4个节点,分别记作X、Y、T、U。图11.1可线性化执行序列如同可串行化定义一样,可线性化的定义也依赖于操作与它们的执行序。

可线性化具有以下性质。

●局部性(locality)。当并发系统的性质P是局部性的时,无论何时,若其中的每个对象都满足P,则该系统将作为整体满足P。参考文献[1]证明了可线性化具有局部(本地)性质。

定理1 H是可线性化的,当且仅当对每个对象x,H|x是可线性化的(证明见参考文献[1])。

局部性的重要性在于它允许并发系统采用模块化方式进行设计和建构,可以按对象独立实现、验证和执行可线性化。

●阻塞性与非阻塞性。可线性化的非阻塞(nonblocking)性表示一个挂起的操作的完成无需等待其他挂起的操作。

定理2 令inv为一个全序操作的调用,如果(x inv P)在一个可线性化历史H中有一个挂起的调用,则存在一个响应(x res P),满足H·(x res P)是可线性化的。[3](证明见参考文献[1])

非阻塞性并不能如预期的那样排除阻塞。例如,若进程试图从空队列里释放一个元素,则阻塞,因为它要等待另一个进程将元素加入队列。

1.与传统一致性比较

与传统一致性比较,顺序一致性要求历史等价于合法的顺序历史。顺序一致性弱于顺序线性化,因为前者不要求保留起源历史的先后次序(original history’s precedence ordering)。历史H 2是非可线性化的。

(历史H 2

q Enq(x)A

q Ok()A

q Enq(y)B

q Deq()A

q Ok()B

q Ok(y)A

因为x上的Enq操作在y上的Enq操作之前,所以y上的退出队列(Deq)发生在x之前。

顺序一致性不具有本地性质。我们来看下面的历史H 3,其中进程A和进程B操作在队列对象p和q上。

(历史H 3

p Enq(x)A

p Ok()A

q Enq(y)B

q Ok()B

q Enq(x)A

q Ok()A

p Enq(y)B

p Ok()B

p Deq()A

p Ok(y)A

q Deq()B

q Ok(x)B

从上可以看出,H 3|p和H 3|q是顺序一致性的,而H 3却不是顺序一致性的。

再来看历史H 4

(历史H 4

q Enq(x)A(www.chuimin.cn)

q Enq(y)B

q Ok()A

q Ok()B

q Deq()A

q Deq()C

q Ok(y)A

q Ok(y)C

这里的H 4不是可线性化的,因为y入队列一次,退出队列却有两次,不满足先进先出(FIFO)要求。

2.与可串行化比较

如果事务的前后次序与顺序历史中事务的序相容,则该历史是严格可串行化的(strictly serializable)。严格可串行化可由同步机制(如2PL)来保证,多版本时标方式则不能保证严格可串行化。

可线性化可以看成是严格可串行化的一种特殊情况,即将事务限制在由单对象的单操作构成上。

可线性化与严格可串行化的重要区别是,可串行化和严格可串行化都不具有局部(本地)性特征。另一个重要区别是,可串行化具有阻塞性质。

下面进一步讨论将事务限制在由单对象的单操作构成上的思想。

参考文献[2]中讨论了复制数据的一致性模型问题。

无论是分布式系统,还是数据库和多处理器计算机硬件领域,都有数据复制问题。复制一致性模型是一种抽象,不考虑实现细节,只识别给定系统的功能。

3.顺序数据类型

参考文献[1]中讨论了顺序数据类型(sequential data type),这个概念最初由Liskov和Zilles引入。

如前所述,最简单的顺序数据类型可能是读/写单字位寄存器(single-bit register)。三种可能的操作是read()、write(0)和write(1)。读操作的返回值可能是0或1。在多字位的情况下,如读/写32位的寄存器,其操作是read()和write(v),v的取值范围为0x00000000到0x FFFFFFFF。CAS(compare-and-swap)寄存器是一个比较/交换寄存器,提供的是比较操作和交换操作,compare-and-swap(v1,v2)。该操作的语义是,如果v1和寄存器的现有值相等,则用v2替换寄存器内的值,返回值是替换出来的运算前寄存器内的值。

分布计算环境里,还可以有多址读/写存储器(multi-location read-write memory)。下面讨论在多址读/写存储器上的操作。

令A为地址集合,操作为read(a),定义为:

read(a)|for a∈A,or write(a,w)for a∈A and w in some finite domain of values

我们允许在多个地址实施运算,例如,有一个存储值快照运算snapshot(),不改变状态,而是把取自多个地址的一组值返回,每个地址返回一个值。

下面讨论多副本情况下的事务执行历史和一致性问题。在无副本的情况下,可串行化可以有效保证事务的一致性。假如多副本存储系统发生的这个历史类似无副本的环境,动作发生在单个节点上,那么与前面讨论的常规情况类似。相关学者用了可线性化(linearizability)这个词,是为了说明这种形态。

图11.1是可线性化执行序列的一个示例,这是一个4字节编址地址存储器(4-location byte-valued snapshot memory),共有4个节点,分别记作X、Y、T、U。数据有2个副本,分布在X和Y节点上,客户端在T和U节点上执行副本管理算法:读和快照(snapshot)操作只在一个副本上实施,写操作则在所有副本上实施,不同的写操作在副本上的序应当一样,所有副本上的修改都完成后才能返回给客户端。假设4个字节的初始值是0。操作read(1)表示读字节1,write(2,7)表示在字节2写入值7,snap()表示读取4个字节的当前快照值。

图11.1 可线性化执行序列

如同可串行化定义一样,可线性化的定义也依赖于操作与它们的执行序。令E为执行历史,<E,rt为该执行历史中操作之间的实时偏序,p<E,rtq表示操作p(从启动到返回)完全发生在操作q之前。换言之,p在q启动前实施。如果两个操作叠加,则说明这两个操作间不相干。如果E是可线性化的,则存在一个序列H,

●H中包含的操作和E中发生的操作一样,返回值也一样。

●H中的操作构成的全序与实时偏序<E,rt相容。

●H是有复制的顺序数据类型的合法历史。

在图11.1这个执行序列中,read(1)操作完全发生在write(2)、read(2)、snapshot()和write(3)之前,但是与write(1)重叠。同样,read(2)完全发生在snapshot()和write(3)之前,但和write(2)重叠。write(3)和write(2)与snapshot()重叠。例如,read(1)操作完全发生在write(2)、read(2)、snapshot()和write(3)之前,这是一个合适的H,因为它满足上述三个条件,H中操作的序与“完全发生在前面”(occurs entirely before)相容。

对于可线性化,我们考虑一个理想系统,其中只有一个节点用于存放数据,该节点上有一组挂着等待执行的操作请求和一组悬挂请求的响应。无论何时,客户端发出一个请求,该请求就进入悬挂请求的集合。任何时候,只要系统可以,就会在悬挂请求里选出一个挂起的请求,在(唯一)数据上实施操作,在悬挂请求队列里移除该请求。任何时候,系统可以从悬挂响应集合里选择一个响应,移出集合,将之返回给提出操作请求的客户端。

这可以形式化为一种状态转换机制。可线性化执行E的定义是,存在一个无副本的理想系统F,E和F在所有客户端包含完全相同的步骤,它们有相同的实时序。