下面先讨论学术界对可串行化理论的修正,即可线性化理论。维基百科[2]对可线性化的定义为:可线性化首先由Herlihy和Wing于1987年在介绍一致性模型时引入。因此,我们可以非形式化地给出可线性化的定义,如下。这个过程是非线性化的。为了实现线性化,要求对每个进程Pi使用自己的寄存器Ri。......
2023-10-28
可线性化具有以下性质。
●局部性(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在所有客户端包含完全相同的步骤,它们有相同的实时序。
有关分布式数据库技术的文章
下面先讨论学术界对可串行化理论的修正,即可线性化理论。维基百科[2]对可线性化的定义为:可线性化首先由Herlihy和Wing于1987年在介绍一致性模型时引入。因此,我们可以非形式化地给出可线性化的定义,如下。这个过程是非线性化的。为了实现线性化,要求对每个进程Pi使用自己的寄存器Ri。......
2023-10-28
前面讨论了面向对象数据库系统的事务管理,本节讨论并发控制的核心问题,即可串行化问题。由面向对象数据库系统的事务可知,这是学术界所说的开放嵌套事务。为此,我们提出了面向对象可串行化的思想。对象调度的面向对象可串行化给出了一个动作序列。我们把一个事务的系统调度称为是面向对象可串行化的,如果所有的对象调度都是面向对象可串行化的,那么所有的附加动作依赖关系不含冲突。如图15.10所示,将三个事务发送给对象En......
2023-10-28
事务的性质可以用ACID来表示,即原子性、一致性、隔离性和持续性。在这类故障中维持事务原子性的机制称为故障恢复。验证事务是否一致是由语义数据控制实现的。 假设有两个并发事务对用户的银行账户x进行处理,它们都要存取数据项x。......
2023-10-28
始制有名,名亦既有,夫亦将知止,知止可以不殆。人为了治理建立了制度,确立了名分,名分已经有了,那也要知道适可而止,知道适可而止可以避免危害。过分的吝啬必定会付出更多,聚财过多而不施以济众,必会引起众怨,招致后患和损失。所以,知道满足就不会受到屈辱,知道适可而止,才不会遭到危险。他们不知足,更不知止,最后栽进了罪恶的泥潭。后赐和自尽,并给他定了20项罪名。从此退而不隐,强而不显。......
2023-12-06
分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。可串行化是涉及并发控制的一个重要理论。条件1表示调度涉及的域是一个由各个事务构成的集合。例9.2所示的是一个串行调度。下面我们讨论可串行化的问题。定义9.3 一个调度Sc是可串行的,当且仅当Sc冲突等价于一个串行调度,这种可串行化通常称为冲突等价可串......
2023-10-28
“人无法选择自然的故乡,但人可以选择心灵的故乡。”人们对外在的渴望和追求已经远远超越了对心灵的关注。过度重视那些物质的、有形的财富,反而会造成心灵的贫穷。当人类对心灵失去关注,就意味着人类对自身失去了关注。......
2023-12-06
纳米粒子体积小,所包含的原子数很少,相应的质量也极小,因此许多现象不能用包含有无限个原子的块状物质的性质进行说明。但大量的实验观察和理论论证发现,纳米粒子的熔点会下降,尤其是处于纳米尺度的粒子的熔点会大大低于其块体材料。......
2023-06-20
将电荷传输性能好的碳基二维材料,如石墨烯[91,123-125,129,155]、碳纳米管、氧化石墨烯等,与钙钛矿材料结合在一起构成异质结构器件,可以获得性能优良的光电探测器。首先,碳基二维材料被广泛用在基于钙钛矿多晶薄膜的晶体管型光电探测器中。由过渡金属化合物WS2[156]、MoS2[121]、WSe2[57]构成的二维材料也被用于提高钙钛矿光电探测器的性能。......
2023-06-24
相关推荐