事务的性质可以用ACID来表示，即原子性、一致性、隔离性和持续性。在这类故障中维持事务原子性的机制称为故障恢复。验证事务是否一致是由语义数据控制实现的。 假设有两个并发事务对用户的银行账户x进行处理，它们都要存取数据项x。......
2025-09-30
分布式数据库的可线性化性质
【摘要】：可线性化具有以下性质。参考文献［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(https://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在所有客户端包含完全相同的步骤，它们有相同的实时序。
相关文章
- 详细阅读
-
分布式数据库的可串行化理论及并发控制详细阅读
分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。可串行化是涉及并发控制的一个重要理论。条件1表示调度涉及的域是一个由各个事务构成的集合。例9.2所示的是一个串行调度。下面我们讨论可串行化的问题。定义9.3 一个调度Sc是可串行的，当且仅当Sc冲突等价于一个串行调度，这种可串行化通常称为冲突等价可串......
2025-09-30
-
非线性算子的性质及应用详细阅读
非线性算子的性质包括连续性、有界性、全连续性、可微性等.这是一些基本概念和性质,在后面各章中都要用到.设E1和E2时两个实Banach 空间,D E1.设A∶D→E2为非线性的.定义1设x0∈D.若ε>0,δ=δ(x0,ε)>0 使得当x ∈D且‖x-x0‖ < δ 时,恒有‖Ax -Ax0‖ < ε,则称A 在x0连续;若A 在D 中每一点都连续,则称A 在D 上连续;若上述δ 只与ε 有关而......
2025-09-30
-
聚丙烯纤维的生产与性质详细阅读
目前生产的聚丙烯中，有95%是等规聚丙烯。（二）聚丙烯纤维化学名称：聚丙烯纤维，别名丙纶化学结构：生产方法：只有等规聚丙烯可以用来制造丙纶，等规聚丙烯可通过配位阴离子聚合的方法合成。生产出的聚丙烯粉末经熔融造粒后，获得聚丙烯切片，便可送去纺丝。聚丙烯纤维性能见表1-2-7所示。......
2025-09-29
-
颗粒污泥的性质分析详细阅读
成熟的颗粒污泥，VSS/SS一般为7%～80%，但根据废水性质其范围可在30%～90%。一般来说，反应器沿高度的群落演替遵循9.3.5中所述规律，而单一颗粒污泥的生物构成遵循生物代谢规律，即产酸细菌主要在颗粒表面，产甲烷细菌主要在颗粒内部。......
2025-09-29
-
小尺寸效应：特殊的热学性质和特殊的力学性质详细阅读
纳米粒子体积小，所包含的原子数很少，相应的质量也极小，因此许多现象不能用包含有无限个原子的块状物质的性质进行说明。但大量的实验观察和理论论证发现，纳米粒子的熔点会下降，尤其是处于纳米尺度的粒子的熔点会大大低于其块体材料。......
2025-09-29
-
青铜、黄铜、红铜的构件性质与技术思想详细阅读
进而，更精确地说：在同一座建筑中分类明晰地使用三种铜合金，这是对中国传统中“刚柔并济”的复合材料技术思想的继承和应用。无论材质如何变化，其核心思想都是“刚柔相济”的基本原理。谈到了包括“刚柔”在内的多对范畴，这是较早将“刚柔相济”作为哲学概念进行讨论的记载。综上所论，昆明太和宫铜殿的材料设计是在“六齐”与“刚柔并济”的材料观念下进行的，这是技术思想和哲学概念的双重理论指导。......
2025-09-30
-
合同法：可撤销合同的产生原因详细阅读
依据我国《民法典》第147～151 条的规定，可撤销合同产生的原因可以进一步划分为重大误解、欺诈、胁迫及显失公平这几种。在当事人发生动机的误解时，是否可以主张重大误解撤销合同成为重大误解制度上的一个问题。为此，对于动机欺诈产生的错误，相对人可以主张撤销合同。......
2025-09-29
相关推荐