读书报告信息学院计算机科学与技术杨凌雯201320602019一、并发控制中的概念和理论1.1 并发控制中的概念数据库的特点就是数据的集中管理和共享。
在通常情况下它总是有若干个事务在执行，这些事务可能并发地存取相同的数据，称为事务的并发操作。
并发控制是负责正确协调并发事务的执行，保证这种并发的存取操作不致破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确的运行并获得正确的结果。
分布式并发控制主要解决多个分布式事务对数据并发执行的正确性。
1.丢失更新问题在图5. 1(a)中，数据库中数据项x的初值是100，事务I对x的值减30,事务T2对x的值增加一倍,如果执行次序是先T1后T2,那么结果x的值是140。
如果是先T2后T1，那么x 的值是170。
这两种情况都应该是正确的，因为具体实现时只有其中一种情况.但是若按图5. 1 (a)那样的并发执行,结果x的值是200，这个值肯定是错误的。
因为在时间t7丟失了事务T1对数据库的更新操作，因此这个并发操作是不正确的。
2.不一致分析问题在图5. 1(b)中，事务T1对x值的值减30，而車务T2只要读出x的值。
但在t5时刻，由于T1已更新了x的值，此时T2使用的x值仍是100，因此就造成了不一致，这个问题称为不一致分析问题。
3.依赖于未提交更新的问題在数据库技术中，把未提交的随后又被撤销的更新数据称为“脏数据”。
这里事务T2在t4时刻读的x值就是脏数据。
1.2事务可串行化理论的基本概念一般来说，对一组并发的分布式事务可能存在多种正确调度，可串行化调度是分布式事务能否正确执行的基本方法。
事务的可串行性是指若千个事务并发执行的结果与按希望的顺序执行的结果相同时，称诸事务是可串行的。
这就是说，如果事务的并发执行能够通过以一定顺序串行执行就可使数据库处于新的一致状态，那么诸如丢失更新的问题就可能得到解决，这就是串行化理论的观点。
1.分布式事务的一个调度在数据库系统中，事务访问数据库中数据的方式是通过发出读操作和写操作原语来实现的。
通常，以T1表示某个事务，以Ri(x)表示该事务对数据项x的读操作，以Wi(x)表示该事务对数据项x的写操作，这里不考虑数据项x的粒度。
事务的一个操作序列称为一个调度（schedule，也称历史history)，一般以字母S表示。
例如：S：R1(x),R2(y),W2(y),R2(x), W1(x),W2(x)S是关于两个事务的一个调度。
两个同时访问同一数据项x的操作，如果其中至少有一个是写操作，那么称这两个操作是冲突的。
1）读操作不相互冲突，因此只有两种冲突：读-写冲突（或写-读冲突），及写-写冲突。
2）两个操作可以属于同一事务或者两个不同的事务，在后者的情况下，称为两个事务冲突。
3）如果有两个事务Ti和Tj，Ti的所有操作都先于Tj的操作，那么这两个事务为串行执行的，必定不会有冲突。
2.串行调度对一个串行调度来说，它总是可以正确的执行，执行它可以使数据库保持一致状态。
1) 如果S正确执行完成，则S中的每一个事务都被提交，由于事务的原子性保证了数据库的一致性。
2) 如果S在执行时发生故障，若Tk之前的事务都已提交，则夭折Tk，使数据库的状态恢复到Tk前的状态。
该状态的数据库也是一致的，因力Tk之前的事务都已提交。
3) 如果S在执行时发生故障，若Tk之前的事务有被夭折的，则夭折Tk，重做Tk以前已被提交的事务，撤销Tk以前被夭折的事务，此时数据库也是一致的。
串行调度总是可以使数据库保持一致。
但是，串行调度时系统的运行效率较低。
3.可串行化调度串行调度对不会引起冲突的操作要求过高，它们可以进行并行操作。
如果在两个操作间存在冲突，这两个操作的执行顺序就很重要；而对于两个不会引起冲突的操作，它们的执行顺序则并不重要。
事务的并发控制主要是正确处理并发执行的事务对数据库的冲突操作。
可串行化调度，直观上看，是让有冲突的操作串行执行，非冲突的操作并行执行，所以可串行化调度就是事务并发控制要寻求的基本方法。
通常分布式事务的可串行化调度可以转化为子事务的可串行化调度，但涉及多副本选择时,分布式事务调度要多做一个选择副本的操作，以避免冲突操作。
1.3 分布式事务的可串行化理论现在给出关下分布式事务的可串行化理论的一些定义。
1.事务2.冲突操作如果有两个操作P和Q对同一个数据x进行操作，其中有一个是写操作W[x]，则P 和Q称为冲突操作。
3. 并发事务的一个调度（简称并发调度）第一种情况简单地说明了调度的域是每个事务域的并集。
第二种情况定义排序关系为每个事务排序关系的超集，这保证了每一事务内部的操作的顺序。
最后一种情况定义了冲突操作的执行顺序。
4.串行调度5.一致性调度如果执行一个调度S，使数据库从一个一致状态转变到另一个一致状态，则称调度S 为一致性调度。
显然，串行调度是一致性调度，但是一致性调度不一定是串行调度。
6.两个调度等价（冲突等价）7.可串行化调度与串行调度等价的调度称为可串行化调度。
例1考虑两个事务，分别定义为对于这两种调度，可以产生如下五种调度：S1={R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1, R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2}S2={R1(x),x=x+10,W1(x), R2(x),x=x-20,W2(x), R1(y),y=y-15,W1(y),C1, R2(y),y=y*2,W2(y),C2}S3={R1(x),x=x+10,W1(x), R2(x), x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1}S4={R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1}S5={R2(x),x=x-20,W2(x), R1(x),x=x+10,W1(x), R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1}如果将事务提交延迟到两个事务操作完成之后执行，有：1）调度S1和S4是串行调度2）调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度3）调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度4）调度S5和S4等价，所以S5是一致调度，也是可串行化调度有以下推论：1）一个可串行化调度必定与某个串行调度等价，且是一致性调度2）一致性调度不一定是可串行化调度3）同一事务集几个可串行化调度，他们的结果未必相同1.4 分布式事务的可串行化调度测试1.使用优先图判别可串行化调度调度S 的优先图是一个有向图G(N,E) ，其中N: 一组节点N={T1T2,…,Tn}, S中的事务E: 一组有向边E={e1,e2,…,en}, Ti，Tj 是图中的一条边，当且仅当p Ti, q Tj 使得p, q 冲突，并且p <S q。
算法5.1 测试调度S的可串行化1）对于调度S中的事务Ti，在图中创建一个节点Ti。
2）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（Ti→Tj ）。
3）对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj ）。
4）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj ）。
5）当且仅当优先图中没有闭环时，调度S是可串行化的。
一般来说，如果调度S的优先序图不存在环路,那么就可有若干个与S等价的串行调度。
但如果优先图存在环路，那么不可能创建任何等价的串行调度，从而S是不可串行的。
2.分布式数据库中可串行化理论的扩展可串行化理论是事务并发控制的基础，判别一个调度是否为一个一致调度，只需判别其是否可串行化就行，即并发控制程序的主要功能就是为并发执行的诸事务产生一个可串行化的调度。
在分布式数据库中，只涉及一个站点上的调度称为局部调度，涉及多个站点上的调度称为全局调度。
很有可能局部调度都是可串行化的，而分布式数据库的相互一致性却仍不能保证。
3. 单副本可串行化相互一致性要求所有数据项副本的值都是相同的，能维持相互一致性的调度称作单副本可串行化(one-copy serifdizable)的调度。
一个单副本可串行化的全局调度必须满足以下条件：1) 每一个局部调度必须是可串行化的。
2) 两个冲突操作在它们同时出现的各个局部调度中，必须具有相同的相对顺序。
4. 读一个/写全部副本控制协议1. 5并发控制机制的常用方法及其分类1.使用协议或规则保证调度是可串行化的如果任意地执行事务，然后再测试结果调度的可串行化，那么一旦它的结果是不可串行化的，就必须取消这个调度的影响。
在大多数实际系统中采取的方法是确定保证可串行化的方法，而不必去测试调度本身。
在大多数商业DBMS中采取的方法是去设计协议（规则的集合），如果协议被每个单独事务遵循，或者被一个DBMS并发控制子系统执行，就将确保事务参与的所有调度都是可串行化的。
2. 并发控制机制常用的方法及其分类并发控制机制划分为两神类型：悲观并发控制法和乐观并发控制法。
悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法则将同步化延迟到事务执行周期的结束。
具体分类如下图：二、分布式数据库系统并发控制的封锁技术2.1基于封锁的并发控制方法概述基于封锁(locking)的并发控制方法，是一种最常见的并发控制算法，其基本思想是事务访问数据项前要对该数据项封锁，如果已被其他事务锁定，就要等待，直到那个事务释放该锁为止。
1.锁的粒度、类型和操作（1）锁的粒度锁的粒度(gmmilarity)是指锁定数据项的范围。
所有的并发控制技术都假定，数据库是由许多命名的数据项组成。
一个数据项可以是下列的任何一种：1) 一个数据库记录；2) 数据库记录中的一个字段值；3) 一个磁盘块（页面）；4> 一个完整的文件；5) 整个数据库。
粒度会影响并发控制和恢复的性能，粒度小，并发度高，锁开销大；粒度大，并发度低，锁开销省。
数据项尺寸越大，允许的并发程度越低。
数据项尺寸越小,数据库中项的数量越多。
（2）.锁的类型：共享锁：Share锁，S锁或者读锁。
排它锁：eXclusive锁，X锁，拒绝锁或写锁。
更新锁：Update锁，U锁。
数据项既可以读也可以写，则要用X锁；如果数据项只可以读，则要用S锁。
（3）. 锁的操作：Read_lock(x):读锁Write_lock(x)：写锁unlock(x)：解锁数据项的状态：read_locked: 读锁Write_locked:写锁具体操作方法：1）在系统锁表中记录关于锁的信息。