有多种并发控制算法的分类方式。按照同步原语可以将并发控制算法分成两类：基于互斥存取共享数据的算法和将事务排序按规则执行的算法。图9.10并发控制算法的分类●在主本封锁中，将每个封锁单元的某个副本指定为主本，在访问该单元时主本必须封锁。这些算法可以分成基本TO、多版本TO和保守TO等。实际上，在某些基于封锁的算法中也使用时标，因为这样可以改进效率和并发性，我们称为混合算法。......
2023-10-28
乐观并发控制算法-分布式数据库技术应用案例
【摘要】：前面讨论的并发控制算法都是悲观算法。反之，夭折该事务，并重新启动它。图9.7乐观事务的执行阶段可以设计一个基于封锁的乐观并发控制算法。不过原始乐观建议是基于时标序的。论文提出，事务冲突并不很频繁时，乐观算法的性能优于封锁算法的性能。乐观算法的一个主要缺点是存储开销较大。为了能够验证，乐观机制必须存储其他已终止事务的读集和写集。然而，减少了并发度，因为这仅让一个事务运行。
前面讨论的并发控制算法都是悲观算法。换言之，它们假设事务间的冲突发生是频繁的，所以不允许事务在存取数据项时有冲突事务对这个数据项执行存取操作。这可以简化为事务按验证（validation，V）、读（read，R）、计算（compute，C）、写（write，W）阶段执行（见图9.6）。
图9.6 悲观事务的执行阶段
反之，乐观算法将验证阶段放到写阶段前来做（见图9.7）。这样提交给乐观调度器的操作不会再延迟。每个事务的读（read）、计算（compute）和写（write）操作不会直接去更新实际的数据库。每个事务对数据项的更新在该数据项的副本上实施。验证阶段包含检验这些更新是否维持数据库的一致性。如果答案是肯定的，则将这些变化全局化（即写入实际数据库）。反之，夭折该事务，并重新启动它。
图9.7 乐观事务的执行阶段
可以设计一个基于封锁的乐观并发控制算法。不过原始乐观建议是基于时标序的。因此下面只介绍使用时标序的乐观方法。
这个算法是Kung和Robinson在1981年提出的。与保守的基于时标序的算法不同，这个算法不仅是乐观的，而且是通过指定时标序实现的。这里，时标只与事务有关，而与数据项无关，而且不是在事务启动时指定时标而是在验证阶段开始时赋予时标，原因是只在验证阶段才需要时标，过早指定时标可能会产生不必要的事务拒绝服务。
现在分析并发事务关系的一些可能状态，如图9.8所示。两个并发事务间的时序关系可以如图9.8（a）、（b）和（c）三种情况所示。图9.8（a）表示一个事务启动时，前一个事务已经结束。图9.8（b）表示一个事务在另一个事务的写阶段启动。图9.8（c）表示一个事务在另一个事务启动后启动，而且启动发生在前一个事务的写阶段之前。
图9.8 可能的执行场景(www.chuimin.cn)
每个事务Ti被原始节点的事务管理器划分为一系列子事务，每个子事务可以在多个节点执行。令Tij为Ti的一个子事务，在节点j执行。直到验证阶段为止，每个本地执行如图9.8所示。在验证开始时将时标赋给该事务，而它又将之赋给子事务。Tij的本地验证按如下规则实行，这些规则是互斥的。
规则1 如果对所有的事务Tk，其中，ts（Tk）＜ts（Tij），Tk在Tij启动读阶段前已经完成写阶段，则验证成功，因为这时事务的执行是串行序的。
规则2 如果有一个事务Tk，使得ts（Tk）＜ts（Tij），表示Tk在Tij进入读阶段前已完成写阶段，则wst（Tk）∩rst（Tij）=∅，验证成功。
规则3 如果有一个事务Tk，使得ts（Tk）＜ts（Tij），表示Tk在Tij完成读阶段前已完成其读阶段，则wst（Tk）∩rst（Tij）=∅和wst（Tk）∩wst（Tij）=∅，验证成功。
规则1是清楚的，它说明事务是按时标序顺序执行的。规则2保证数据项在有些可能发生读/写冲突时检测出潜在冲突，由于它们的读/写集不相交，所以不存在冲突。规则3则讨论事务重叠更严重的情况。
乐观并发控制算法的优点在于它能提供更高的并发性。论文提出，事务冲突并不很频繁时，乐观算法的性能优于封锁算法的性能。乐观算法的一个主要缺点是存储开销较大。为了能够验证，乐观机制必须存储其他已终止事务的读集和写集。特别是，那些在事务Tij到达节点j时正在处理的已终止事务的读集和写集必须存放起来，以便验证Tij。这样就增加了存储开销。
另一个问题称为饥饿（starvation）问题。细节请参阅参考文献［6］。
我们来看一个事务在其验证阶段失败的情况。接下来再试探一次，可能验证时还是失败。
当然，可以通过允许在一系列尝试失败后让该事务排外地存取数据库来解决问题。然而，减少了并发度，因为这仅让一个事务运行。
有关分布式数据库技术的文章
- 详细阅读
-
时标并发控制算法-分布式数据库技术详细阅读
不像基于封锁的算法，基于时标的并发控制算法不通过互相排斥来维持可串行化。这里，唯一性是时标的第一个性质。协调事务管理器为每个事务指定时标，确定每个数据项存放的节点，并向这些节点发送执行相关操作的命令。下面的算法称为基本时标序事务管理算法，记作BTO-TM。严格2PL算法要求封锁必须推迟到事务的提交或夭折才释放，同样也可以给出一个严格的TO算法。......
2023-10-28
-
分布式数据库技术：封锁型并发控制算法详细阅读
基于封锁的并发控制的主要思想是，保证冲突操作共享的数据一次只能由一个操作存取。表9.1封锁模式的兼容矩阵在基于封锁的系统中，这是由封锁管理器来实现的。封锁管理器检查该封锁单元是否已上锁。事务结束时，解除全部封锁。图9.2表示一旦完成对一个数据项的存取，封锁管理器就释放对数据项的封锁。图9.22PL的形态图9.3严格的两阶段封锁图严格的两阶段封锁管理需要对算法9.1略作修改。算法9.2 严格的两阶段封锁LM算法。......
2023-10-28
- 详细阅读
-
分布式数据库技术应用案例详细阅读
政府的各个职能部门也管理着与其职能有关的部门业务数据，主要包含以下几种。工商企业数据库主要具有以下功能。因此，工商企业数据库围绕的是企业法人，以企业法人为核心及其相关实体构建而成。非政府机构组织数据库等可参照工商企业数据库。类似的部门业务数据库很多，在此不再赘述。......
2023-10-28
-
分布式数据库技术：多版本并发控制和快照隔离详细阅读
在多版本并发控制方法中经常采用异地更新技术，即不是直接在旧数据项上修改，而是先创建一个数据项的新版本，然后让新版本取代旧版本。使用MVCC的好处是，读请求不会因为存在写操作而被阻塞。数据库中的只读访问常常检索的是已被提交的数据项版本。系统的开销主要发生在相同数据项的多个版本上。有一种称为快照隔离的技术用于实现支持MVCC的数据库。SI的开销虽然小，但弱化了可串行化。SI包含以下两个重要性质。......
2023-10-28
-
数据库应用实现并发控制详细阅读
事务通过向封锁管理程序的系统组成部分发出请求而对记录加锁。这时其他事务就不能读取和修改订票数，直到甲事务修改完成并将数据写回到数据库，并解除对此数据的封锁之后其他事务才能使用这些数据。加锁是实现并发控制的一个非常重要的技术。表7—1锁的相容矩阵在表7－1的加锁类型相容矩阵中，最左边一列表示事务T1已经获得的数据对象上的锁的类型，最上面一行表示另一个事务T2对同一数据对象发出的加锁请求。......
2023-11-24
-
控制算法的解析与运行-现场总线与应用技术详细阅读
在上位机将控制算法传输到控制卡后，控制卡会将控制算法信息暂存到控制算法缓冲区，并不会立即对控制算法进行解析。所以，控制算法的解析必须选择合适的时机。本系统中将控制算法的解析操作放在本周期的控制算法运算结束后执行，这样不会对本周期内的控制算法运行产生影响，新的控制算法将在下一周期得到执行。上位机下发给控制卡的控制算法包含控制算法的操作信息、回路信息和回路中各功能模块信息。......
2023-11-22
相关推荐