数据库新技术【分布式数据库】
第一章 概述1.1 基本概念
1.1.1 分布式数据库
分布式数据库——多个分布在计算机网络上的逻辑相干的数据库的集合。
分布式数据库中，存放在差别网络节点上的数据库称作局部数据库，由局部数据库构成的逻辑团体称为全局数据库。全局数据库中的关系称为全局关系，局部数据库中的关系称为逻辑片段，或简称片段。
全局关系与片段之间的映射关系称为分片。全局数据库与局部数据库之间的映射关系由一组分片模式来表现。一个逻辑片段可以保存在网络的一个节点上，也可以在网络的多个节点上保存多个副本，逻辑片段如何在网络上存放，称为分配。
1.1.2 数据管理的透明性
[*]分片透明：用户使用数据库时，不必要知道全局数据库与多个局部数据库之间的逻辑关系。
[*]复制（分配）透明：用户使用数据库时，不必要知道数据在网络上差别节点间的复制情况。
[*]网络透明：用户使用数据库时，用全局唯一的对象名指代所要操纵的对象，不需知道数据在网络上的位置。
[*]数据独立性（无分布透明）：用户应用不受数据库逻辑结构变化的影响，用户应用不需关注数据库数据保存的物理结构。集中式数据库就具有如许的特性。
1.1.3 可靠性
变乱是数据库上的同等的可靠的计算单元，变乱由一串具有原子性的数据库操纵构成。
变乱具有ACID四个特性。
[*]原子性（Atomicity），构成一个变乱的一串操纵要么全部完成，要么全部没做。
[*]同等性（Consistency），并发实行的变乱总是使得数据库从一个同等的状态变化为另一个同等的状态。
[*]隔离性（lsolation），一个变乱实行过程中无法看到其他并发变乱的中间结果。
[*]持久性（Durability），已完成变乱的结果将会被可靠地永久地保存，直至被另一个变乱所更新。
变乱的性子在分布式数据库中必须得到包管。在分布式情况中保障变乱性子显然与集中式情况有很多差别。集中式数据库情况中若服务器节点失效，数据库系统将无法运转，而在分布式数据库情况中，在某些条件满足时，纵然某个服务器节点失效，数据库系统仍能运转。
1.1.4 分布式数据库与集中式数据库的区别
集中式数据库中数据库存放在网络上的一个节点上，而分布式数据库数据库分布存放在网络上差别节点上。
1.2 体系结构
[*]客户机/服务器模式：多客户机/单服务器、多客户机/多服务器
[*]对等节点模式：
[*]多数据库模式：含全局概念模式、不含全局概念模式。
1.3 全局目录
全局目录是分布式数据库中描述全局数据库与局部数据库关系的信息集合（分片模式和分配模式的集合）。只有分布式数据库有全局目录的标题。在分布式数据库中全局目录是目录的一部门。
目录本身也是一个数据库。目录可以集中存放在一个节点上，也可以分为全局目录和局部目录，分布存放在网络的差别节点上。
分布式数据库的设计技术同样实用于目录。分布式情况中，一个目录可以只在一个节点上存放一个拷贝，也可以在多个节点上存放多个拷贝。
1.4 关系代数
1.4.1 基操
https://img-blog.csdnimg.cn/direct/e0ae2cde6e8a4e03a84be55bcd422bea.png
1.4.2 关系表达式
由关系代数运算经有限次复合而成的式子称为关系代数表达式。这种表达式的运算结果仍旧是一个关系。可以用关系代数表达式表示对数据库的查询和更新操纵。
例如：
数据库中有三个关系如下：
学生关系 Stu1(sid, sname, sage, sgender)，Stu2(sid, sname, sage, sgender)
选课关系 SC(sid, cid, grade)
课程关系 Cou(cid, cname, cteacher)
[*]查询学号为112的学生年龄
π s a g e ( σ s i d = ′ 11 2 ′ ( S t u 1 ) ) \pi_{sage}(\sigma_{sid='112'}(Stu1)) πsage(σsid=′112′(Stu1))
[*]查询学号为112或者212的学生性别
π s g e n d e r ( σ s i d = ′ 11 2 ′ ∨ s i d = ′ 21 2 ′ ( S t u 1 ∪ S t u 2 ) ) \pi_{sgender}(\sigma_{sid='112' \vee sid='212'}(Stu1\cup Stu2)) πsgender(σsid=′112′∨sid=′212′(Stu1∪Stu2))
[*]查询同时出如今两个学生关系中的学生学号和姓名
π s i d , s n a m e ( S t u 1 ∩ S t u 2 ) \pi_{sid, sname}(Stu1\cap Stu2) πsid,sname(Stu1∩Stu2)
[*]查询出如今学生关系1且不在学生关系2中的学生学号和姓名
π s i d , s n a m e ( S t u 1 − S t u 2 ) \pi_{sid, sname}(Stu1-Stu2) πsid,sname(Stu1−Stu2)
[*]查询学号为112的学生的数据库课程结果
π g r a d e ( σ s i d = ′ 11 2 ′ ∧ c n a m e = ′ 数据 库 ′ ( C o u ⋈ C o u . c i d = S C . c i d S C ) ) \pi_{grade}(\sigma_{sid='112'\wedge cname='数据库' }(Cou\Join_{Cou.cid=SC.cid} SC)) πgrade(σsid=′112′∧cname=′数据库′(Cou⋈Cou.cid=SC.cidSC))
[*]查询学生关系1中选过课的学生学号和姓名
π s i d , s n a m e ( S t u 1 ⋉ S t u 1. s i d = S C . s i d S C ) \pi_{sid, sname}(Stu1\ltimes_{Stu1.sid=SC.sid} SC) πsid,sname(Stu1⋉Stu1.sid=SC.sidSC)
【注：半毗连返回左表中与右表至少匹配一次的数据行，通常表现为 EXISTS 或者 IN 子查询】
1.4.3 查询树
关系表达式可进一步转换为查询树，查询树包罗关系操纵的先后次序，数据库系统可依据查询树控制查询操纵。
例如：
[*] 查询学号为112的学生年龄
π s a g e ( σ s i d = ′ 11 2 ′ ( S t u 1 ) ) \pi_{sage}(\sigma_{sid='112'}(Stu1)) πsage(σsid=′112′(Stu1))https://img-blog.csdnimg.cn/direct/476b22621c6a42478ae5d8ac963414db.png#pic_center
[*] 查询学号为112或者212的学生性别
π s g e n d e r ( σ s i d = ′ 11 2 ′ ∨ s i d = ′ 21 2 ′ ( S t u 1 ∪ S t u 2 ) ) \pi_{sgender}(\sigma_{sid='112' \vee sid='212'}(Stu1\cup Stu2)) πsgender(σsid=′112′∨sid=′212′(Stu1∪Stu2))https://img-blog.csdnimg.cn/direct/f0cf936133a84db8814d3f0e8bfe2e4c.png#pic_center
[*] 查询同时出如今两个学生关系中的学生学号和姓名
π s i d , s n a m e ( S t u 1 ∩ S t u 2 ) \pi_{sid, sname}(Stu1\cap Stu2) πsid,sname(Stu1∩Stu2)https://img-blog.csdnimg.cn/direct/7871025979bc46808b1e9cba69934cb0.png#pic_center
[*] 查询出如今学生关系1且不在学生关系2中的学生学号和姓名
π s i d , s n a m e ( S t u 1 − S t u 2 ) \pi_{sid, sname}(Stu1-Stu2) πsid,sname(Stu1−Stu2)https://img-blog.csdnimg.cn/direct/d01a5c11d6294825bc617b53c6dd92f6.png#pic_center
[*] 查询学号为112的学生的数据库课程结果
π g r a d e ( σ s i d = ′ 11 2 ′ ∧ c n a m e = ′ 数据 库 ′ ( C o u ⋈ C o u . c i d = S C . c i d S C ) ) \pi_{grade}(\sigma_{sid='112'\wedge cname='数据库' }(Cou\Join_{Cou.cid=SC.cid} SC)) πgrade(σsid=′112′∧cname=′数据库′(Cou⋈Cou.cid=SC.cidSC))https://img-blog.csdnimg.cn/direct/0e6a0771ea4040bbb24e0c26033b71eb.png#pic_center
[*] 查询学生关系1中选过课的学生学号和姓名
π s i d , s n a m e ( S t u 1 ⋉ S t u 1. s i d = S C . s i d S C ) \pi_{sid, sname}(Stu1\ltimes_{Stu1.sid=SC.sid} SC) πsid,sname(Stu1⋉Stu1.sid=SC.sidSC)https://img-blog.csdnimg.cn/direct/bbf28f89bb2440e787140193ecdd32f2.png#pic_center
第二章 分布式数据库的设计
2.1 设计谋略
当数据库的设计是从头开始时，自顶向下的设计是符合的。然而有时一些数据库已经存在，设计是为了集成已存在的一些数据库，这时必要自底向上的设计方法。
自底向上的设计方法所涉及的必要集成的多个数据库常常是异构的。
2.2 分布设计的目标
[*]分布设计的多个子目标之间相互抵牾，只能进行平衡折中的处理。
[*]分布设计应使每个应用访问的局部数据库尽可能少。
[*]分布设计应尽可能进步应用的并发程度。
[*]分布设计应尽可能减少应用实行过程中的网络通信量。
[*]分布设计应尽可能让用户应用在网络上就近访问。
2.3 水中分片设计
2.3.1 需求分析
[*]收集用户查询所用的谓词。
[*]用户查询无穷无尽，无法全部收集，通常在80/20规则的指导下进行。即:20%的最活泼的查询可以反映80%的数据访问情况。
https://img-blog.csdnimg.cn/direct/e4410a41e8914ac681a9a792964e5fbf.png
2.3.2 简朴谓词集合的精粹处理
谓词： P i : A i θ V a l u e θ ∈ { = , < , > , ≠ , ≤ , ≥ } P_i: A_i \;\theta\; Value\;\;\; \theta \in \{=,<,>,\not=,\le,\ge\} Pi:AiθValueθ∈{=,<,>,=,≤,≥}
例如： P 1 : L O C = " M o n t r e a l " P_1:LOC\; = \; "Montreal" P1:LOC="Montreal"
P r i = { p i 1 , P i 2 , . . . , p i m } P_{ri} = \{p_{i1}, P_{i2},. . ., p_{im}\} Pri={pi1,Pi2,...,pim} 是针对关系 r i r_i ri 收集的简朴谓词集合。
P r i P_{ri} Pri 经算法COM-MIN处理后得到 P r i ′ P'_{ri} Pri′。对于关系 r i r_i ri ， P r i ′ P'_{ri} Pri′ 是满足分布设计要求的最小简朴谓词集合。
例如，针对关系PROJ得到了 P ′ = { p 1 , P 2 , P 3 , P 4 , P 5 } P'= \{p1, P2, P3, P4, P5\} P′={p1,P2,P3,P4,P5}
p1：LOC = “Montreal”
p2：LOC = “New York”
p3：LOC = "Paris’
p4：DUDGET ≤200000
p5：DUDGET > 200000
2.3.3 最小谓词集合处理
M i = { m i j ∣ m j j = ∧ p i k ∗ , 1 < j < z , p i k ∗ = p i k ∣ ¬ p i k , p i k ∈ P r i ′ } M_i = \{m_{ij}|m_{jj} = \wedge p^*_{ik}, \; 1<j<z, \;p^*_{ik}=p_{ik}|\neg p_{ik},\; p_{ik}∈P'_{ri} \} Mi={mij∣mjj=∧pik∗,1<j<z,pik∗=pik∣¬pik,pik∈Pri′} M i M_i Mi是关于关系 r i r_i ri最小项谓词集合从 P r i ′ P'_{ri} Pri′中得到，是进行水中分片的依据。
例如，由 P ′ = { p 1 , p 2 , p 3 , p 4 , p 5 } 可得 M = { m j } ( 1 ≤ j ≤ 2 5 ) P'=\{p_1,p_2,p_3, p_4, p_5\}可得M=\{m_j\}\;(1≤j≤2^5) P′={p1,p2,p3,p4,p5}可得M={mj}(1≤j≤25)。然而，谓词间隐含着一些语意。
i 1 : p 1 ⇒ ¬ p 2 ∧ ¬ p 3 i_1:\; p1\Rightarrow \neg p2 \wedge \neg p_3 i1:p1⇒¬p2∧¬p3
i 2 : p 2 ⇒ ¬ p 1 ∧ ¬ p 3 i_2:\; p2\Rightarrow \neg p1 \wedge \neg p_3 i2:p2⇒¬p1∧¬p3
i 3 : p 3 ⇒ ¬ p 1 ∧ ¬ p 2 i_3:\; p3\Rightarrow \neg p1 \wedge \neg p_2 i3:p3⇒¬p1∧¬p2
i 4 : p 4 ⇒ ¬ p 5 i_4:\; p4\Rightarrow \neg p5 i4:p4⇒¬p5
i 5 : p 5 ⇒ ¬ p 4 i_5:\; p5\Rightarrow \neg p4 i5:p5⇒¬p4
i 6 : ¬ p 4 ⇒ p 5 i_6:\; \neg p4\Rightarrow p5 i6:¬p4⇒p5
i 7 : ¬ p 5 ⇒ p 4 i_7:\; \neg p5\Rightarrow p4 i7:¬p5⇒p4
由 i 1 − 7 i_{1-7} i1−7可知， p 1 − 3 p_{1-3} p1−3不可能同时存在， p 4 − 5 p_{4-5} p4−5不可能同时存在，删除非法和重复的最小谓词项后，得到 M = { m i , 1 ≤ i ≤ 6 } M=\{m_i, 1 \le i \le 6\} M={mi,1≤i≤6}
https://img-blog.csdnimg.cn/direct/8417a86716694086939a758c6712da6f.png
最后根据最小谓词集合M进行水中分片：
https://img-blog.csdnimg.cn/direct/bd41ee0befe3428cbfe9622983e78b2e.png
分片结果如下：
https://img-blog.csdnimg.cn/direct/fb31ea3f310a4b089a94890a285a5c8f.png
其中 P R O J 2 , P R O J 5 PROJ_2, PROJ_5 PROJ2,PROJ5为空，那是由PROJ的当前值决定的，数据库是动态的，PROJ的值也是动态的。
2.3.4 诱导分片
https://img-blog.csdnimg.cn/direct/a08e979c42cf41559d9b33c88b770f26.png
水中分片可以直接对一个关系搜集应用信息，设计分片，也可以从另一个关系诱导其分片方案。如图所示，关系间存在着link ,如L1,L2,L3。用关系代数的术语来讲，link表示一个关系的外键是另一个关系的主键。例如，L3表示ASG的外键JNO是PROJ的主键。
对于owner关系直接设计其水中分片，对于member关系从owner关系诱导出水中分片的设计。诱导分片的设计方法是半毗连。例如，关于ASG的水中分片可如下设计：
https://img-blog.csdnimg.cn/direct/aa0677737ffa4842a15738740a503d80.png
有的member有多个owner，例如，EMP和PROJ都是ASG的owner。这种情况下，从差别的owner诱导出差别的水中分片方案。最终由设计者根据系统分配的需求选取一种。
2.3.5 正确性检查
[*]完备性:全局关系的任何数据至少可在一个分片中找到，而且每个分片被访问的概率相同。
[*]重构性： R = ∪ R i ， ∀ R i ∈ F R 。 R=\cup R_i，\forall R_i ∈ F_R。 R=∪Ri，∀Ri∈FR。
[*]不相交性： R i ∩ R j = ∅ ， ∀ i , j R i , R j ∈ F R 。 R_i∩R_j=\empty ，\forall i,j\; R_i, R_j ∈ F_R。 Ri∩Rj=∅，∀i,jRi,Rj∈FR。
2.4 垂直分片设计
在分布式数据库中可接纳垂直分片分割全局关系，在集中式数据库中也可接纳垂直分片设计存储结构，把经常一起被访问的列聚集存放在一起，进步存储服从。
垂直分片可选方案非常多。m个非主键属性可能的垂直分片方案的数量是B(m),当m = 10时，B(m) ≈ 115000，当m = 15时，B(m) ≈ 1 0 9 10^9 109，当m = 30时，B(m) ≈ 1 0 23 10^{23} 1023。因此，垂直分片的设计黑白常困难的。
两种启发式的途径：成组和切分。
2.4.1 使用矩阵
https://img-blog.csdnimg.cn/direct/b68948537295470eab59f7af8e105940.png
https://img-blog.csdnimg.cn/direct/3cdad4c92acc4a6c945081d500fb1efc.png
A 1 = P N O , A 2 = P N A M E , A 3 = B U D G E T , A 4 = L O C A_1=PNO, A_2=PNAME, A_3=BUDGET, A4=LOC A1=PNO,A2=PNAME,A3=BUDGET,A4=LOC
u s e ( q i , A j ) = ( 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 ) use(q_i,A_j)= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix} use(qi,Aj)= 1000011011010011
2.4.2 密切矩阵
使用矩阵没有包罗应用调用查询的频率信息，不能足够反应出属性之间的密切程度。为此，进一步给出属性间的密切度界说:
https://img-blog.csdnimg.cn/direct/442890e0974b46d3965840faa2bf734a.png
其中， a c c l ( q k ) acc_l(q_k) accl(qk)是应用 I 调用查询 q k q_k qk的频率。
https://img-blog.csdnimg.cn/direct/b6ed8f51546c4217843c5148186f63bd.png
计算方法：
2.4.3 聚集的属性密切矩阵（理解即可，有点复杂）
属性密切度矩阵显然让垂直分片设计工作前进了一步。但是仍旧无法直接给出垂直分片方案。如果密切的属性聚集在一起，设计垂直分片将会比较容易。聚集的属性密切度矩阵就是密切属性聚集在一起的属性密切度矩阵。聚集的属性密切度矩阵是由属性密切度矩阵经过行间交换以及对应的列间交换得到的。为通过算法得到如许的矩阵，界说全局密切度度量：
https://img-blog.csdnimg.cn/direct/bb8df7b01c09489292685510e0a87f10.png
https://img-blog.csdnimg.cn/direct/c08d3aa2d67e4d7fac5f9cda10274baa.png
https://img-blog.csdnimg.cn/direct/c0dda611a43041e6b42df5b871287242.png
https://img-blog.csdnimg.cn/direct/febe2169ce444b1b9f730764ddfebfc1.png
https://img-blog.csdnimg.cn/direct/dca6efabf4294553b1b00f6f26f060a6.png
https://img-blog.csdnimg.cn/direct/e5ac660c0d704b44941f518aac382166.png
https://img-blog.csdnimg.cn/direct/eeb5f1e5ad3145fca6e3dc8bd1cb6b84.png
详细例子：
https://img-blog.csdnimg.cn/direct/4ae9a7aabe6143748dee63bdfb28f997.png
确定分割点
https://img-blog.csdnimg.cn/direct/03f4ae350d6f430486d5e08f7ce82097.png
https://img-blog.csdnimg.cn/direct/3e023cbc29e34b3e91b638d33840ed8b.png
对于n个属性，在CA中有n-1个分割点。每个分割点可以计算一个z值，选取z值最大的那个分割点对属性集合进行分别。如许的分别可迭代进行下去，直到给定的条件满足为止。
假设AS1，AS2，.…. ，ASx是通过上述方法对一个关系进行属性集分别得到的k个属性子集。然后，对这些属性集进行如下处理:
https://img-blog.csdnimg.cn/direct/3094104367164228b2ee3cc667313d15.png
2.4.5 正确性检查
https://img-blog.csdnimg.cn/direct/b1c0235e1e9d460ea83d2416afd1694a.png
2.5 分解树和重构树
水中分片和垂直分片可以混合使用，如图所示：
https://img-blog.csdnimg.cn/direct/934d0ed920d243af8a6c471fe5f47a4f.png#pic_center
上图的树被称作分解树，描述了全局关系与逻辑片段之间的关系。全局关系可由逻辑片段通过重构树（下图所示）的操纵序列重构出来。
https://img-blog.csdnimg.cn/direct/96633d8dae9a4de1b2de84253263ae8c.png#pic_center
2.6 分配
每个逻辑片段可以保存在一个节点上，也可以在多个节点上保存多个副本。保存多个副本有利于进步查询的服从，但是却会增加更新的代价。分配是一个非常复杂的优化标题。可简朴表述如下:
https://img-blog.csdnimg.cn/direct/82397fd70a1a4bf6a5e709ace6f4b090.png
第三章 分布式查询
3.1 查询分解
3.1.1 规范化
查询条件可由谓词表达式表示，将查询的谓词表达式进行规范化处理有助于删除冗余操纵。规范化形式有合取规范化和析取规范化。
[*]合取规范化【 ( a + b ) ∗ ( b + c ) ∗ ( c + d ) ∗ . . . (a+b)*(b+c)*(c+d)*... (a+b)∗(b+c)∗(c+d)∗...】
https://img-blog.csdnimg.cn/direct/0e01028a893442738e42b46e850bff5a.png
[*]析取规范化【 a b + b c + c d + . . . ab+bc+cd+... ab+bc+cd+...】
https://img-blog.csdnimg.cn/direct/34704d9992d247538ec3286815a7eeff.png
3.1.2 规范化规则
https://img-blog.csdnimg.cn/direct/d8ae05f8c5984bf3a7b9b000e364ad41.png
3.1.3 逻辑规则
https://img-blog.csdnimg.cn/direct/486414ba5cc7469fb8997c43e25bec4a.png
3.1.4 冗余消除
https://img-blog.csdnimg.cn/direct/6de6cd3ffa75445d9584a985bc1f5252.png
https://img-blog.csdnimg.cn/direct/e6fc78c4d2d2416d93970e802fc0f201.png
https://img-blog.csdnimg.cn/direct/631cd609240e4dccaaa31c36399d7852.png
3.1.5 查询树优化
查询经前述处理后被写成一颗查询树，为减少计算量，需对查询树进行优化处理，优化处理所依据的规则如下。R,S,T表示差别的关
系，A= {A1,A2,……. ,An} 和 B={B1,B2,… ,Bn} 分别表示R, S的属性集。
https://img-blog.csdnimg.cn/direct/c7d8e7a8b137486ab8155dc2f2a69626.png
https://img-blog.csdnimg.cn/direct/d49f22efabc541a388a4b93fe5724f1d.png
https://img-blog.csdnimg.cn/direct/48ae037d59314549af1f0d0e24c29fa3.png
下页左图是一颗查询树，查询树优化的目标就是从等价的查询树中找出代价最小的那一颗。但是等价的查询树数量太多，无法比较所有的查询树代价。可行的办法就是接纳启发式的方法探求较优的查询树。一个启发式途径是：接纳下移一元操纵的方式优化查询树。
https://img-blog.csdnimg.cn/direct/aea831350a2c40b7b9ad5df0d9ff683c.png
3.2 数据定位
3.2.1 合并重构树
优化后的查询树的叶节点是全局关系，在分布式数据库中全局关系是虚拟的，如果操纵没有定位到逻辑片段，查询是无法进行的。将查询操纵落实到详细的逻辑片段上，这一工作称为数据定位。数据定位最简朴的做法是：用全局关系的重构树取代查询树中的全局关系，把重构树合并到查询树中来。
但是，合并重构树是不够的。因为，对于一个详细的查询有的逻辑片段是不可能有结果，针对如许的逻辑片段进行计算完满是浪费。这里把查询树中不可能有结果的逻辑片段称为无用节点，删除无用节点是必要开展的下一步优化工作。
3.2.2 水中分片的裁剪
https://img-blog.csdnimg.cn/direct/20d0445cff354a2495f3b47d96a712f0.png
https://img-blog.csdnimg.cn/direct/1aa873a769464a619e2611953e7e0ace.png
例如：
EMP(ENO, ENAME, TITLE) 和 ASG 被如下分片:
https://img-blog.csdnimg.cn/direct/c8209d1312e9471ca13b52c9673d39db.png
https://img-blog.csdnimg.cn/direct/717fd04e7ad64a49a110851a394a8b29.png
对于查询1：
https://img-blog.csdnimg.cn/direct/b03befad89324969801c7af5b42c1761.png
该查询经初步优化和合并重构树后得到左图所示的查询树，根据规则1裁剪无用节点，得到右图所示的查询树。显然，右图的查询树与左图的查询树相比，可以省掉很多计算，却能够得到同样的结果。
https://img-blog.csdnimg.cn/direct/abe280892cec4649b873842e8ca469f6.png
对于查询2：
S E L E T E ∗ F R O M E M P ， A S G W H E R E E M P . E N O = A S G . E N O \begin{align} & SELETE\; * \\ & FROM \; EMP，ASG \\ & WHERE \; EMP.ENO=ASG.ENO \end{align} SELETE∗FROMEMP，ASGWHEREEMP.ENO=ASG.ENO
https://img-blog.csdnimg.cn/direct/445e6dabcc0e4aa79947541599f87672.png
上图的查询树可经过并与毗连转换，规则2的转换，变换为下图的查询树。下图的查询树计算量远低于上图。
https://img-blog.csdnimg.cn/direct/fc64c34ee39549a3a84421c3a910ceb3.png
3.2.3 垂直分片的裁剪
https://img-blog.csdnimg.cn/direct/b36ef984d8ef4e7281f241e9440b869b.png
对于查询：
https://img-blog.csdnimg.cn/direct/9b3d6273837c42d8b35b62cbe9219a61.png
该查询经初步优化和合并重构树后得到下图所示的查询树。
https://img-blog.csdnimg.cn/direct/fa6ee8b1b73440be99dc86b82718798b.png
上图的查询树经一元操纵幂等律、投影与毗连的交换、垂直分片的裁剪转换为下图的查询树。
https://img-blog.csdnimg.cn/direct/68dc057a755f4a16abd68854c7e10e8f.png
3.2.4 诱导分片的裁剪
https://img-blog.csdnimg.cn/direct/424a9b4340f94785b1c328d818b9c311.png
对于查询：
https://img-blog.csdnimg.cn/direct/5530c1eb4dff45b787e1f95057c48afb.png
查询树如下：
https://img-blog.csdnimg.cn/direct/18b59c54e51d475bb4c32f44ba91ecae.png
优化【删除空选择】
https://img-blog.csdnimg.cn/direct/87f98a8a2e144ac194e7f54c865009d8.png
优化【交换毗连与并】
https://img-blog.csdnimg.cn/direct/b05d4c7fe7ab4534b63395752e3839dc.png
优化【根据诱导分片，删除空子树】
https://img-blog.csdnimg.cn/direct/1e836a08746a4f57b867b9d49af924b7.png
3.2.5 混合分片的裁剪
https://img-blog.csdnimg.cn/direct/7a3ee3dabff24b1b8e7ef3ac42c9d01b.png
查询树为：
https://img-blog.csdnimg.cn/direct/94644992ac7f4972bcd4051cdedcf3db.png
优化后
https://img-blog.csdnimg.cn/direct/e68f731b94f64945809b537d0796b598.png
3.3 全局优化
3.3.1 目标
[*]在查询操纵落实到逻辑片段并裁剪了无用节点之后，查询还必要进一步优化。进一步优化必要考虑实行操纵的位置，实行操纵的次序，实行操纵的代价等标题。
[*]目标是:探求一个代价最小且与原查询树等价的查询树。
[*]代价包括数据通信量、CPU时间、I/O时间等。
这仍旧是一个NP困难标题，只能接纳启发式方法寻求较优的方案。
3.3.2 代价的估算
查询的代价可以是查询所斲丧的总时间，也可以是查询的响应时间。总时间指实行查询的各个操纵所斲丧的时间总和，响应时间指查询开始到查询完成所经历的时间。
无论是总时间照旧响应时间，都需通过数据库的统计数据来估算。
常用的统计量
关系R的属性集为 A = { A 1 , A 2 , … , A n } A= \{A_1,A_2,…,A_n\} A={A1,A2,…,An}，被分片为 R 1 , R 2 , … , R n R_1,R_2,…,R_n R1,R2,…,Rn
https://img-blog.csdnimg.cn/direct/32968f62f3184e64ba4d009b0fb103b6.png
https://img-blog.csdnimg.cn/direct/2819754a6580427798fcbfd7cadb832b.png
https://img-blog.csdnimg.cn/direct/2f7a63c09d194eb08047558cdf0a6e39.png
3.3.3 主要优化标题
前面的优化处理已经把操纵落实到了逻辑片段上并尽可能下推了一元运算，这时的主要标题是选择毗连运算的园地和运算次序。
https://img-blog.csdnimg.cn/direct/713e818915a34161ac6602f41f86512f.png#pic_center
https://img-blog.csdnimg.cn/direct/49f6a8f7ff084bdd9ce1bb7088c7f6e2.png#pic_center
https://img-blog.csdnimg.cn/direct/bac5e8380df44527945431cbf6be4b5a.png#pic_center
半毗连处理
https://img-blog.csdnimg.cn/direct/ef352783f81b48b5a57866bb53f00d56.png
3.3.4 主要算法
[*]Distributed INGRES Algorithm
[*]R* Algorithm
[*]SDD-1 Algorithm
3.4 局部优化
对那些已经定位到一个园地上的一系列操纵接纳集中式数据库中的优化方法继续进行局部优化。
局部优化有动态优化和静态优化两种计谋，大多数商业关系型数据库系统接纳静态优化的计谋。
第四章 分布式并发控制
4.1 串行化理论
[*]并发控制关系到变乱的隔离性和同等性。
[*]串行化理论是被广泛担当的判断并发控制正确性的标准。
例如，有以下变乱及其之上的调度：
T 1 = { R 1 ( x ) , W 1 ( x ) , G 1 } T_1=\{R_1(x), W_1(x),G_1\} T1={R1(x),W1(x),G1}
T 2 = { W 2 ( x ) , W 2 ( y ) , R 2 ( z ) , C 2 } T2= \{W_2(x),W_2(y), R_2(z),C_2\} T2={W2(x),W2(y),R2(z),C2}
T 3 = { R 3 ( x ) ， R 3 ( y ) , R 3 ( z ) , C 3 } T3=\{R_3(x)，R_3(y),R_3(z),C_3\} T3={R3(x)，R3(y),R3(z),C3}
S = { W 2 ( x ) , W 2 ( y ) , R 2 ( z ) , C 2 , R 1 ( x ) , W 1 ( x ) , C 1 , R 3 ( x ) , R 3 ( y ) , R 3 ( z ) , C 3 } S=\{W_2(x), W_2(y),R_2(z),C_2,R_1(x), W_1(x),C_1, R_3(x), R_3(y),R_3(z),C_3\} S={W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3}
S是对变乱T1，T2，T3的一个调度。s是一个串行调度，实行的次序是T2→T1→T3。串行调度可以包管变乱的隔离性和同等性，串行调度是正确的调度。但是串行调度完全排挤变乱的并发性，服从太低，不可担当。
串行化理论提供了判断并发调度等价于串行调度的方法，把等价于串行调度的调度称为可串行化调度。
4.1.1 集中式可串行化
对同一数据项的读写操纵、写写操纵被称为冲突操纵。例如 W 2 ( x ) , W 1 ( x ) W_2(x),W_1(x) W2(x),W1(x)是一对冲突操纵， W 2 ( y ) , R 3 ( y ) W_2(y),R_3(y) W2(y),R3(y)是另一对冲突操纵。冲突操纵 W 2 ( x ) , W 1 ( x ) W_2(x),W_1(x) W2(x),W1(x)中 W 2 ( x ) W_2(x) W2(x)先于 W 1 ( x ) W_1(x) W1(x)，记为 W 2 ( x ) ≺ W 1 ( x ) W_2(x)\prec W_1(x) W2(x)≺W1(x)。同样地， W 2 ( y ) ≺ R 3 ( y ) W_2(y)\prec R_3(y) W2(y)≺R3(y)。根据调度冲突关系绘制调度冲突图，图中无环则为可串行化调度，否则不能判定为可串行化调度
https://img-blog.csdnimg.cn/direct/92333d670bd54195b3c2ba1fff2b3968.png#pic_center
调度S本身是串行调度，判断为可串行化调度理所当然。调度S’是一个并发调度，用上述方法判断一下其是否为可串行化的。
https://img-blog.csdnimg.cn/direct/bd602a6a38744ffd97dfa63cfe3dda27.png#pic_center
https://img-blog.csdnimg.cn/direct/e35bc2116c2a49319caec29d2bc09ba0.png#pic_center
4.1.2 分布式可串行化
串行化理论扩展到分布式情况上才气解决分布式数据库中的调度标题。
假设调度S’中与x数据项有关的操纵以及C1操纵发生在园地x上，与y数据项有关的操纵以及C2操纵发生在园地y上，与z数据项有关的操纵以及C3操纵发生在园地z上，则S’可改写成：
S x ′ = { W 2 ( x ) , R 1 ( x ) , W 1 ( × ) , C 1 , R 3 ( x ) } S'_x=\{W_2(x),R_1(x), W_1(×),C_1, R_3(x)\} Sx′={W2(x),R1(x),W1(×),C1,R3(x)}
S y ′ = { W 2 ( y ) , R 3 ( y ) , C 2 } S'_y = \{ W_2(y),R_3(y),C_2\} Sy′={W2(y),R3(y),C2}
S z ′ = { R 2 ( z ) , R 3 ( z ) , C 3 } S'_z=\{R_2(z),R_3(z),C_3\} Sz′={R2(z),R3(z),C3}
可分别为 S x ′ , S y ′ , S z ′ S'_x ,S'_y,S'_z Sx′,Sy′,Sz′ 绘制冲突调度图，然后合并为一张图，若无环则为可串行化调度，否则不能作出此判断。
https://img-blog.csdnimg.cn/direct/b2e6bad641f846848e2d21a8cdbbd116.png#pic_center
4.2 并发控制概况
现有的并发控制 ⊂ \subset ⊂可串行化的并发控制 ⊂ \subset ⊂正确的并发控制 ⊂ \subset ⊂并发控制
4.3 基于锁的并发控制
4.3.1 基本概念
R L i ( x ) RL_i(x) RLi(x) W L i ( x ) WL_i(x) WLi(x) R L j ( x ) RL_j(x) RLj(x)兼容互斥 W L j ( x ) WL_j(x) WLj(x)互斥互斥 WL为写锁，RL为读锁。在对数据项进行操纵前要上锁，如果没有遇到不兼容的锁，上锁成功才气进行现实操纵，否则只有等拥有该锁的变乱释放该锁时才会有时机上锁成功。
例如：
https://img-blog.csdnimg.cn/direct/7cdd294ec075419ba9c4e5e19a1a1455.png
https://img-blog.csdnimg.cn/direct/047b0f27afbf4f1b8e675afe605eabad.png
S是关于变乱T1,T2的一个基于锁的调度，其中 l r i ( z ) lr_i(z) lri(z)表示释放变乱 T i T_i Ti对数据项z的锁。
[*]假设在两个变乱实行之前x、y的值分别为 50 和 20，T1, T2串行的结果是多少?
102和38，或者101和39
[*]依据调度S的实行结果是多少?
102和39
[*]这说明S并不是一个可串行化的调度。请用可串行化理论对此作一判断。【并不是基于锁的调度就是可串行化调度】
https://img-blog.csdnimg.cn/direct/7b3d818ca3a546fd813dc0ed0dd1a9a6.png#pic_center
4.3.2 两段锁协议（2PL）
2PL指2-phase locking，意指把变乱的加锁息争锁过程分成两个阶段，加锁阶段息争锁阶段。加锁阶段只加锁不解锁，解锁阶段只解锁不加锁。
https://img-blog.csdnimg.cn/direct/3d60c21463894525bf62f1168dce6981.png#pic_center
https://img-blog.csdnimg.cn/direct/a99c8f558f644b2ca94ba57e61c7fc09.png#pic_center
4.3.2.1 集中式数据库中2PL的可串行性
可串行化理论证明集中式数据库中2PL的可串行性
假设存在一个环，则意味着存在一组变乱T1, T2, …, Tn，使得T1依赖于T2, T2依赖于T3，…，Tn依赖于T1。但是根据2PL协议的规则，变乱一旦进入紧缩阶段就不会再获取新锁，因此不可能形成如许的环，因为一旦一个变乱开始释放锁，它不会再阻塞其他变乱的锁请求。
因此，冲突调度图中不可能存在环。
4.3.2.2 分布式数据库中2PL的可串行性
可串行化理论证明分布式数据库中2PL的可串行性
https://img-blog.csdnimg.cn/direct/9ae2ef46453946fcaf0ea1f2c95b20ce.png
4.4 死锁标题
接纳基于锁的调度，变乱因为等待锁而形成的一种相互等待关系称为死锁。
在没有外在干预的情况下，陷入死锁的变乱将永久等待下去。无论是集中式数据库系统，照旧分布式数据库系统，只要接纳基于锁的并发控制，就有可能出现死锁的情况。
对于接纳2PL的数据库系统，必须处理有可能出现的死锁标题。
4.4.1 死锁的检测和规复
（1）检测
使用资源分配图，进行检测死锁。
https://img-blog.csdnimg.cn/5167be89228c477c890b20e54dd12a47.png
https://img-blog.csdnimg.cn/72a539adb8c04953a14cf06bc20614fc.png
简化：找到可以运行的进程，删去其所有边。
死锁定理：当且仅当系统状态的资源分配图不可以完全简化，则系统处于死锁状态。
等待图（WFG）
死锁的检测依赖WFG ( wait-for graph）, WFG中有环即为存在死锁。
分布式情况中，分别为每个节点绘制WFG，然后把所有节点的IWFG合并为一个gWFG，gWFG中有环即为存在死锁。检测到死锁后，任选一个变乱，回滚该变乱。
WFG 是进程及其等待的资源之间的依赖关系的图形表示。在WFG中，节点表示进程，资源表示为边。每个边缘都从正在等待资源的进程指向当前持有该资源的进程。
https://img-blog.csdnimg.cn/direct/dd91b2ef30ba48599b6a3822f5ce078e.png
（2）规复
[*]资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
[*]撤销进程法（或称终止进程法)。强制撤销部门、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的长处是实现简朴，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
[*]进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要纪录进程的历史信息，设置还原点。
超时法
为每个变乱设定一个实行时限。若某个变乱超过了实行时限，数据库系统回滚该变乱。该方法非常简朴，实现较容易。由于变乱的的实行时间通常较短，一样寻常来讲，该方法是可行的。
4.4.2 死锁的预防
[*]破坏互斥条件：部门互斥资源可以改造为共享资源，如：使用Spooling技术将打印机逻辑上改造为共享资源。（大部门资源不能破坏）
[*]破坏不剥夺条件：但进程无法得到新的资源时，该进程必须释放已经占有的资源。（会增加系统开销，低沉系统吞吐量）
[*]破坏请求和保持条件：进程在运行前一次性申请完所必要的资源。（系统资源严峻浪费，可能会导致“饥饿”现象）
[*]破坏循环等待条件：给资源编号，进程申请资源必须安照编号递增的次序申请，且后面的申请编号不能小于前面。（造成资源浪费，用户编程麻烦，倒霉于系统增加新资源）
4.4.3 死锁的避免
（1）系统安全状态
所谓系统安全状态，是指系统能安照某种进程推进序列为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以完成。此时，该序列为安全序列。若系统无法找到一个安全序列，则系统处于不安全状态。
（2）银行家算法
[*]可使用资源向量（Available）：向量中的每一个元素代表一类可使用资源数目。
[*]最大需求矩阵（Max）：表示每个进程最每类资源的最大需求数目。
[*]分配矩阵（Allocation）：表示每类资源当前已经分配给每个进程的资源数。
[*]需求矩阵（Need）：表示每个进程接下来最多还必要多少资源。
（3）WFG
在每次变乱加锁失败时，先假设该变乱转入等待状态，绘制WFG(IWFG，gWFG)，检测是否有死锁。如果有，回滚该变乱。否则让该变乱真正进入到等待状态。
第五章 分布式规复
5.1 概述
[*]变乱的原子性和持久性依赖数据库系统的规复机制来解决。
[*]在数据库系统运行时，有可能遇到各种错误，即便这些错误发生，数据库系统也应包管变乱的原子性和持久性。
[*]在分布式数据库系统中有些标题是新标题。
5.1.1 变乱模型
[*]分布式数据库中的一个变乱被称为全局变乱。
[*]全局变乱涉及多个站点，涉及一个站点的那一部门被称为一个子变乱。
[*]一个全局变乱由一个或多个子变乱构成。每个子变乱由所在站点的数据库系统所启动的一个进程或线程来实行。
[*]原子性要求，构成一个全局变乱的所有子变乱要么全部提交，要么全部回滚。
5.1.2 错误范例
[*]变乱级错误。错误的数据导致变乱实行过程中出现除0等错误。变乱由于陷入死锁或可能陷入死锁导致变乱无法正常实行完成。变乱级错误在集中式数据库和分布式数据库中都有可能出现。
[*]站点级（系统级）错误。（非存储介质）硬件错误、操纵系统错误、数据库系统错误、应用步调错误等错误导致系统瘫痪。系统级错误在集中式数据库和分布式数据库中都有可能出现。
[*]介质错误。保存数据库的介质（大多数指硬盘）失效，导致数据丢失。介质错误在集中式数据库和分布式数据库中都有可能出现。
[*]通讯故障。网络通讯发生故障，致使网络被分割为几个相互不能联通的区域，分布式数据库的节点在差别的区域之中，相互无法知晓其他区域的情况。通讯故障是分布式数据库中特有的情况。
5.1.3 稳固命据库与易失数据库
对数据库的任何操纵都起首在内存中进行，然后才会写到外存。
[*]外存是稳固的存储，不会因为断电而消失，把DBMS在外存上维持的数据集合称为稳固命据库。
[*]内存中保存的数据会因为断电而消失，把DBMS在内存上维持的数据集合称为易失数据库。
5.1.4 稳固日志与易失日志
写日志也是先在内存中完成写操纵，再写到外存上。
[*]外存上的日志内容称为稳固日志。
[*]内存中的日志内容称为易失日志。
5.1.5 错误例子
DBMS在0时候开始运行，在t时候发生系统故障。
https://img-blog.csdnimg.cn/direct/ef9c310dbbc149dd94b4427e68d2c101.png#pic_center
持久性要求稳固命据库中包罗T的全部操纵结果。当故障发生时，若T的操纵结果还未写入到稳固命据库中，则必要把这些操纵“Redo”到稳固命据库中。
原子性要求稳固命据库中不包罗T2的任何操纵结果。当故障发生时，若T2的操纵结果已写入到稳固命据库中，则必要关于这些操纵对稳固命据库进行“Undo”操纵。
5.2 局部规复
https://img-blog.csdnimg.cn/direct/a78c7e917a0042f5b5a654670592f82e.png#pic_center
全局数据库由多个节点构成，每个节点支持一个局部数据库，局部数据库系统如上图所示。每个局部数据库系统负责本地的规复，同时要保持与其他局部数据库在规复上的同等性。
基本原理
规复的依据是日志，DBMS对数据库作任何更新操纵前都先写日志。
5.2.1 变乱级与系统级错误规复
[*]当发生变乱级错误，根据日志的内容对该变乱实行“Undo”操纵。“Undo”操纵确保数据库规复到变乱实行以前的状态。
[*]对数据库的任何操纵都起首在内存中进行，然后才会写到外存，两者之间一定存在一个时间差。一样寻常情况下，当发生系统级错误时，易失数据库丢失，稳固命据库未包罗易失数据库中的最新版本的更新，必要对数据库进行规复处理。规复包罗对日志的两遍扫描:
[*]第一遍，从头至尾扫描日志，把日志中纪录的操纵“Redo”到稳固命据库中，并纪录下未完成的变乱。
[*]第二遍，从尾到头扫描日志，关于未完成变乱的操纵对稳固命据库进行“Undo”操纵。
5.2.2 检查点
每次都从头开始扫描日志，代价太大，在数据库系统运行一段时间后，基本上不可能如许做。
数据库系统通过设置检查点解决该标题。检查点协议如下:
[*]在日志中写入一条begin_checkpoint纪录。
[*]将检查点数据收集到稳固的存储器中。
[*]将end_checkpoint纪录写入日志。
其中，第2步有多种差别的做法，变乱同等检查点是多种做法之一。变乱同等检查点不允许系统接收新变乱，等所有活动变乱全部完成后，把易失数据库中所有的更新写入到稳固命据库中。
变乱同等检查点使得日志中的end_checkpoint record对应着稳固命据库的一个同等的状态。数据库系统周期性地运行检查点协议。当遇到系统级错误时，从最新的那个end_checkpoint record开始扫描日志即可。
5.2.3 日志的完备性
当发生系统级错误时，内存中的易失日志也丢失了。规复时只有稳固日志可用，对于规复而言，是否充实?
只要公道安排将易失日志写为稳固日志的机遇，就能包管规复的正确性。如果每次把易失数据库中的更新写到稳固命据库前，以及在每次变乱结束前（含变乱提交完成和变乱回滚完成），都把易失日志中的内容全部写到稳固日志中，则可包管日志对规复是充实的。
例如：
[*] t 1 t_1 t1 时候 T 1 T_1 T1 变乱提交完成，数据库系统把易失日志的内容写到稳固曰志中。
[*] t 2 t_2 t2 时候，易失数据库中的更新写到稳固命据库前，数据库系统把易失日志的内容写到稳固日志中。
[*] t 3 t_3 t3 时候，发生系统级错误，易失数据库和易失日志的内容全部丢失。
https://img-blog.csdnimg.cn/direct/144867061c904f3a8b37ccd3352aaf92.png#pic_center
数据库系统根据稳固日志的内容对稳固命据库进行“Redo”操纵，可以把稳固命据库规复到 t 2 t_2 t2 时候的状态，无法规复到 t 3 t_3 t3 时候的状态。是否有标题?
无论是 t 2 t_2 t2 时候的状态照旧 t 3 t_3 t3 时候的状态，都不是一个同等的状态，都要通过对变乱 T 2 T_2 T2 的“Undo”操纵继续把稳固命据库规复一个同等的状态（ T 1 T_1 T1 完成 T 2 T_2 T2 未做的状态）。尽管 t 2 t_2 t2 时候的状态不是 t 3 t_3 t3 时候的状态，也能最终达到这个同等的状态。因此，那些易失日志的丢失对最终的规复没有影响。
5.2.4 介质错误
数据库系统应对介质错误的方法是归档备份。
[*]数据库管理员用数据库系统的备份功能周期性地把数据库和日志备份到脱机存储设备上（一样寻常是磁带或光盘）。
[*]一旦出现介质错误，先修复硬件，再用数据库的规复功能根据脱机设备上的备份把数据库规复到一个同等的状态。这一规复过程必要先把备份的数据库（有时也包括日志）复制到硬盘上，后面的处理在原理上与处理系统错误相同。
[*]通常，稳固命据库和日志是存放在差别的硬盘上的，而且日志还在多个硬盘上同时保存相同的映像。
[*]一样寻常情况下，运行中的日志总会有可用的一个映像。这时只需把备份的数据库复制到硬盘上即可进行后续的规复工作。
[*]在运行中的日志也被破坏了的情况下，必要把备份的数据库和日志都复制到硬盘上才可进行后续的规复工作。这种情况下，由于归档备份是周期性进行的，归档备份的日志很可能未包罗系统最新的更新，因此很可能无法把数据库规复到最新的同等状态。
5.3 全局规复
5.3.1 全局变乱
用户提交给分布式数据库系统的变乱是全局变乱，关于变乱的ACID是针对全局变乱而言的。
用户把全局变乱提交给某个节点，该节点上的数据库系统把该全局变乱分解为若干子变乱，交给差别的节点去处理。每个节点由数据系统启动一个进程或线程来实行子变乱。
就一个全局变乱而言，有分布在多个节点上的进程或线程共同处理这一全局变乱。在发起该变乱的那个节点上的进程或线程被称为协调者，其他节点上的进程或线程被称为参与者。
5.3.2 原子性
[*]变乱级错误
变乱级错误发生在参与全局变乱的某个节点上。发生错误的那个节点上的子变乱起首依据局部规复的方法进行处理(“回滚”)。变乱的原子性要求：无论别的子变乱是否有错，这时都必须回滚。
[*]系统级错误
当某个节点发生系统级错误时，该节点要进行系统级的局部规复。局部规复回滚了在该节点上正在运行的未完成子变乱。变乱的原子性要求：与这些子变乱同属于一个全局变乱的其他子变乱都应该回滚。
[*]介质错误
当某个节点发生介质错误时，该节点要进行介质错误的局部规复。局部规复回滚了在该节点上正在运行的未完成子变乱。变乱的原子性要求：与这些子变乱同属于一个全局变乱的其他子变乱都应该回滚。
[*]通讯故障
通讯故障导致网络分割，有些节点的状况无法知晓。变乱的原子性要求，一个全局变乱的所有子变乱要么全部提交要么全部回滚。只有所有子变乱都成功完成才气提交所有子变乱，否则就要全部回滚。通讯故障导致有些子变乱的情况无法知晓，只能让全部子变乱回滚。
5.3.3 持久性
只要每个节点都能提供对局部数据库的持久性保障，全局数据库的持久性就得到了保障。
每个节点的局部规复保障了每个节点的持久性，因此全局数据库的持久性有保障。
5.3.4 关键标题
分布式数据库系统要确保：
[*]当任一子变乱无法正常完成时或任一子变乱的实行情况无法知晓
时，回滚所有子变乱.
[*]当分布式数据库系统知晓所有子变乱都正常完成时，所有子变乱都
要提交。由于提交过程是不可逆的，所有子变乱都不可自行提交。
5.4 两段提交协议
5.4.1 基本头脑
两段提交协议简称2PC
[*]全局变乱的提交过程分为两个阶段：决策阶段和实行阶段。
[*]协调者负责决策，参与者依据决策实行。
5.4.2 2PC协议运行要点
[*]2PC允许参与者在投票前自行回滚子变乱。一旦一个参与者投票了，就不能再改变。
[*]参与者处于Ready状态后，既可能转入提交状态，也可能转入回滚状态，这由协调者发来的消息决定。
[*]全局变乱提交或回滚由协调者决定。协调者决定的原则是：所有参与者投票提交则决定提交，否则决定回滚。
[*]协调者和参与者进入某一状态时，必须等待对方的消息。
[*]为包管协调者和参与者的进程（或线程）能够最终从这些状态退出并终止，必要为每个进程（或线程）设置计时器。计时器的使用将在失效的情况下讨论。
5.4.3 运行状态变化图
https://img-blog.csdnimg.cn/direct/cc3d41d620934a1a8a7500f9ac2585a3.png#pic_center
[*]协调者的“INITIAL”状态指协调者还未实行到变乱的commit下令前的状态。
协调者处于“INITIAL”状态时发生错误，无论哪种错误，协调者的子变乱被回滚，协调者直接进入“ABORT”状态，然后每隔一段时间向参与者发一个全局回滚下令，直到收到所有参与者的完成回滚简直认消息后，向日志写入变乱完成纪录。
[*]参与者的“INITIAL”状态指参与者还未收到预提交下令前的状态。
参与者处于“INITIAL”状态时发生错误，无论哪种错误，参与者的子变乱被回滚，参与者直接进入“ABORT”状态，等收到协调者的全局回滚下令后向协调者发送实行完回滚简直认消息。
5.4.3.1 协调者超时处理
协调者处于“WAIT”状态超时，可能是由于某个参与者节点发生变乱级错误、系统级错误或介质错误，或者是由于网络通讯故障导致报文无法送达。这时，协调者作出“回滚”决定并向所有参与者发送全局回滚下令，转入“ABORT”状态。
协调者处于“COMMIT”和“ABORT”状态超时，协调者不能确定是否所有的参与者都完成了提交或回滚，协调者再次重发全局提交或全局回滚下令。协调者只有在收到所有参与者的实行确认消息之后，才向日志中写入“end-of-transaction”纪录。
5.4.3.2 参与者超时处理
参与者处于“INITIAL”状态超时，可能是协调者发生变乱级错误、系统级错误或介质错误，或者是由于网络通讯故障导致报文无法送达。这时，参与者自行回滚，转入到“ABORT”状态。如果在这之后，协调者的预提交下令又到达了，参与者可以根据日志纪录复兴投票回滚，也可以不予回答。两种处理都将导致协调者作出回滚的决定。
参与者处于“READY”状态超时。这时，参与者已投票提交，但是并不知道协调者的决定，参与者只能保持阻塞，等待协调者的全局下令。由于协调者处于“COMMIT”和“ABORT”状态超时会再次重发全局提交或全局回滚下令，参与者一定能够收到协调者的全局下令。
参与者处于“READY”状态超时会被阻塞，直至收到协调者的下令为止。如果参与者暂时收不到全局下令的原因是：协调者站点的系统级错误、介质错误，或者是通讯故障导致网络分割，那么，故障修复是很耗时的。在故障修复之前，参与者是不可能收到全局下令的，因此参与者有可能较长时间被阻塞。有可能较长时间被阻塞的现象是2PC的倒霉因素。
5.4.3.3 提交过程开始后协调者站点错误
协调者处于“WAIT”状态时协调者站点堕落，系统局部规复后，协调者将按照处于“WAIT”状态超时来继续处理。
协调者处于“COMMIT”或“ABORT”状态时协调者站点堕落，系统局部规复后，协调者将按照处于“COMMIT”和“ABORT”状态超时继续处理。
5.4.3.4 提交过程开始后参与者站点错误
参与者处于“READY”状态时参与者站点堕落，系统局部规复后，参与者将按照处于“READY”状态超时来继续处理。
参与者处于“COMMIT”或“ABORT”状态时参与者站点堕落，系统局部规复后，参与者无需任何处理。
第六章 区块链技术（理解即可）
6.1 比特币及其原理
6.1.1 比特币的诞生
https://img-blog.csdnimg.cn/direct/fd334b0de17a4b7a9f6e4e7252544d76.png
6.1.2 比特币系统的特点
[*]比特币系统软件全部开源
[*]无中央管理服务器
[*]无任何负责的主体，无外部名誉背书。
6.1.3 比特币来源
[*]挖矿得到
[*]交易得到
6.1.4 比特币交易
https://img-blog.csdnimg.cn/direct/5767b124c08945939608cadba10963f1.png
6.1.5 UTXO
https://img-blog.csdnimg.cn/direct/fcc03c7452ce4a7d82b09e973cc7c062.png
6.1.6 账户余额
[*]比特币账户与一对公私钥对应，公钥的哈希值为账户地址。
[*]比特币系统与平凡的账务系统差别，没有纪录账户余额，只纪录交易信息。
[*]一个账户的余额每次都是通过搜索区块链中该账户的所有交易，累加所有交易的增减得到的。
6.1.7 挖矿
比特币系统是一个参与节点相互验证的公开记账系统，挖矿本质上是争夺某一区块的记账权。得到记账权的节点得到一定命量的比特币嘉奖，包括系统嘉奖和交易手续费两部门。
系统嘉奖是比特币发行的本领，最初每得到一次记账权可得50个比特币的系统嘉奖，每隔4年减半。2140年前后发行完毕，最终整个系统有2100万。
争夺记账权的方式是工作量证明算法（Proof of Work，PoW)，其含义是：把上一个区块的哈希值、本区块交易信息默克尔树根和一个未知的随机数拼在一起计算一个新的哈希值，要求这个哈希值以若干个0开头。开始算出符合要求的结果的节点得到记账权。
每个节点收集这段时间内（约10分钟）的全网交易信息（部门或全部）进行查验确认打包成一个新区块，取得记账权（挖矿成功）后向所有的节点广播。其他节点收到广播后，对交易信息的正当性和记账权进行验证。如果通过则担当这个区块，并制止自己的挖矿举动，否则继续挖矿至收到一个可担当的广播或自己挖矿成功。
6.2 区块链原理
6.2.1 区块链内容和区块间的链
https://img-blog.csdnimg.cn/direct/04385ec39a30419dafbad907ebaaf49d.png
按区块存储交易纪录，下一个区块存储上一个区块的哈希值，形成链接的关系。
6.2.2 数字署名验证交易
https://img-blog.csdnimg.cn/direct/b674e182bda14be487cc64e949418743.png
数字署名依赖于公钥和私钥的配对。每个人都有一对唯一的公钥和私钥。公钥用于验证署名，而私钥用于创建署名。当发送方使用私钥对信息进行署名时，接收方可以使用公钥来验证署名的有效性。如果署名有效，这意味着信息在传输过程中没有被篡改，而且确实来自拥有相应私钥的人。
在区块链中，数字署名确保了交易的来源和不能否认性。每个交易都会被发送者的私钥署名，然后广播到网络中。一旦交易被确认并添加到区块链中，它就不能被撤销或更改。这确保了交易的不能否认性，为双方提供了安全保障。
6.2.3 默克尔树构造块内交易
参考来源：区块链中的Merkle树
https://img-blog.csdnimg.cn/direct/914c0867a1a84ef780631da8c3133940.png
每条交易的哈希值就是一个叶子节点，从下往上将两个相邻叶子节点的组合哈希作为新的哈希值，新的哈希值成为树节点继续与相邻的树节点组合成新的哈希值。在重复一定次数后直到形成唯一的根节点。最后得到的Merkle根必要保存到区块头中，以便仅需通过区块头就可以对交易进行简朴支付验证，这一过程也成为SPV（Simplified Payment Verification）。
对于Merkle树而言，并不必要知道整棵Merkle树中每个节点的值，可以通过节点的值、Merkle根的值和相干路径来快速验证该节点是否属于该Merkle树，从而快速验证该区块中是否包罗了某条交易。
别的，时间戳用于标记区块次序。时间戳表示自格林威治时间 1970 年 1 月 1 日 0 时 0 分 0 秒到当前时候的总秒数，是一种完备且可验证的电子证据，能够为某一数据提供特定时间点的存在性证明。区块链根据时间戳的先后次序通过链式结构将一个个区块关联起来，因此篡改区块数据的难度以时间的指数倍增加，区块链越长篡改难度就越高，这也是确保区块链不可更改性的重要因素之一。
默克尔树作用：
[*]快速比较大量数据：当两个Merkle树的根哈希值相同时，说明所代表的的数据都相同。
[*]快速定位修改：当两个Merkle树的根哈希值相同时，说明所代表的的数据都相同快速定位修改：如下图，如果交易C发生改变，那么就会导致N2、N5和Merkle根发生改变。以是，我们想要快速定位，只必要沿着Merkle根→N5→N2就可以定位到交易C发生改变。
https://img-blog.csdnimg.cn/direct/a06e8a4a3ea6422b8f2d70a4a4c7ef56.png#pic_center3. 零知识证明：例如，想要证明一组交易中包罗某个交易A，但又不想让对方知道交易A的详细内容，那么就可以构建Merkle树，如上图，向对方公布N0、N1、N4和根节点，对方就可以确认交易A的存在，但无法知道交易A的详细内容。
6.2.4 共识机制
区块链由参与节点共同维护，参与节点互不隶属，每个节点都保存区块链的一个副本。每个参与节点都收集验证迩来一段时间的交易信息，差别节点收集验证的交易信息可能差别等，也有可能有的节点被恶意操纵收集了非法交易。共识机制包管所有节点最终能够保存同等且正确的副本。
比特币系统接纳工作量证明算法（PoW)，差别的区块链系统接纳的共识算法有所差别。PoW是一个数学难题，只能通过枚举法逐一实行，只有具备较强算力的节点才可能更快求解。开始得到解的节点得到当前区块的记账权，将当前区块广播给所有节点。其他节点验证被广播来的区块交易信息和记账权的正当性，只有确认正当才担当该区块，否则继续求解PoW，直至自己得到记帐权或收到一个正当的广播来的区块。
6.2.5 P2P
[*]交易信息需广播给所有节点，新天生的区块也必要广播给所有节点，直接广播很容易产生广播风暴，网络将不堪重负。
[*]区块链系统接纳P2P ( Peer to Peer Network）构造参与节点，广播依据P2P协议采取一传十、十传百的方式进行。
6.2.6 智能合约
[*]比特币系统的交易脚本可视为智能合约的雏形，由Vitalik Buterin(V神）提出并在以太坊中实现。
[*]智能合约的引入是区块链的一个里程碑，使得区块链的应用拓展到了金融、政务、供应链、医疗保健、物流、能源、游戏等各个范畴。
https://img-blog.csdnimg.cn/direct/f85e24e0921d4a5abf7ce048bbed4ae0.png#pic_center
[*]智能合约是一种在一定条件下自动实行的计算机步调。
[*]智能合约保存在区块链中不可更改。
[*]区块链系统中的节点通过共识机制验证智能合约的实行结果，包管智能合约的实行结果不会被篡改。
6.2.7 区块链范例
[*]公有链
公共区块链网络是一种向公众开放且不必要任何许可即可进入网络的无限制交易网络。如果您有有效的互联网毗连，您可以加入任何公共区块链网络并成为该网络的授权成员。作为授权成员或节点，您拥有查看网络上进行的操纵的最新和过去信息、真实交易、甚至进行数据发掘工作量证明的所有权限。谈到安全和隐私，如果成员严格遵守规则和准则，公共区块链网络就是安全的。
公共区块链网络主要用于 暗码学开辟 及交流活动。您还可以使用它来获取由可审核的操纵链构成的永久数据纪录。法律宣誓书或产业纪录的电子认证是公共区块链技术的几个例子。
[*]私有链
私有区块链基本上是一个受限制的网络，必要特别许可才气进入。此类区块链网络多用于那些必要一小部门成员参与网络交易的行业和范畴。网络管理员有责任管理安全级别、用户数量、授权以及进入网络的特别权限。与公共区块链网络相比，私有区块链也提供相同的功能，但它使网络仅限于授权用户。
私有区块链网络主要用于必要保护网络免受外部实体侵害的情况。私有区块链的一些常见用例包括公共投票、资产所有权、供应链管理等等。
[*]联盟链
联盟链是一个半去中央化的网络，由多个网络管理员构成。这种范例的区块链网络与私有区块链网络完全相反，在私有区块链网络中，单个网络管理员管理整个网络。在联盟链网络中，多个构造可以作为节点运行，成功完成交易和交换信息。这种范例的区块链通常用于银行和政府机构。
联盟区块链网络用于银行、支付、食品或送货跟踪以及研究。
6.3 区块链与加密货币的关系
[*]区块链是比特币的底层技术和基础构架。
[*]区块链是技术，加密货币是区块链支持的应用。
[*]区块链技术源自加密货币，但其应用可以拓展到其他范畴。
6.4 区块链主要框架
[*]比特币系统
[*]以太坊系统
[*]超级账本——由Linux基金会牵头并创立的分布式账本平台。
6.5 区块链与数据库的比较
[*]数据库系统和区块链系统都支持记账，但记账的方式不一样。数据库系统以账户余额为焦点记账，区块链系统以交易纪录为中央记账。
[*]数据库系统在交易纪录累积到一定量时，可以让交易纪录离线，区块链系统把区块链视为一个团体，不可能剥离任何已经入链的交易纪录。
[*]数据库系统处理交易的服从很高，吞吐量很大；区块链系统处理交易的服从很低，吞吐量很低。
[*]区块链系统能够包管交易信息不能被篡改不能被伪造，数据库系统不能提供如许的包管。
[*]数据库系统的故障规复机制主要依赖日志来实现，区块链系统的故障规复主要依赖节点间的相互复制来实现。
[*]区块链系统处理的数据规模远小于数据库系统。比特币系统运行至今（十年多），整个区块链大约185G巨细。
第七章 NewSQL数据库
7.1 基本概念
[*]NewSQL是对各种新的可扩展高性能数据库的简称，这类数据库不仅具有NoSQL对海量数据的存储管理能力，还保持了传统数据库支持ACID和SQL的特性。
[*]NewSQL数据库支持关系数据模型和SQL。
[*]NewSQL针对数据量巨大且包罗大规模变乱处理的应用。NewSQL差别于数据仓库，数据仓库虽然能够存储大规模数据，但针对的是OLAP。OLAP的焦点是在大规模数据集上实行复杂的只读查询。
[*]NewSQL实行的读写变乱具有以下特点：①时间短，②通过索引定位到一个很小的数据子集上，③同一变乱会被反复实行。
[*]NewSQL的实现应基于非锁的并发控制和shared-nothing的分布式体系结构。
7.2 类别
7.2.1 New Architecture
[*]DBMS不是对旧系统的扩展，而是全新开辟的。网络毗连起来的浩繁节点间shared-nothing，数据库在DBMS的管理下分布在这些节点上，DBMS支持跨节点的并发控制、分布式查询处理、容错处理和流控制。
[*]DBMS实现分布式的查询优化和节点间的通信协议。无论数据保存在内存照旧盘上，DBMS都自己管理存储空间，而不依赖分布式文件系统。
[*]例子：Clustrix，CockroachDB, Google Spanner，H-Store, HyPer, MemSQL, NuoDB, SAP HANA, VoltDB.
7.2.2 Transparent Sharding Middleware
[*]中间件允许数据库被分别成若干子集，每个子集存储在一个单节点DBMS实例中，中间件把这个单节点DBMS实例的集群集成为一个逻辑团体。
[*]中间件将查询定位到详细的节点上，协调变乱的实行，管理数据在节点间的分片、存储和复制。
[*]对于已使用旧的单节点数据库的应用，中间件类别具有上风。
[*]通常，中间件支持MySQL的wire协议，便于集成单节点MySQL实例。单节点上的传统DBMS是面向磁盘存储的，无法使用面向内存存储的存储管理和并发控制优化方法。
[*]例子：AgilData Scalable Cluster, MariaDB MaxScale, ScaleArc, ScaleBase.
7.2.3 Database-as-a-Service
[*]云计算提供的一种Database-as-a-Service的产品。
[*]用户不用维护DBMS，DBaaS提供者负责DBMS安装、升级和配置，负责数据库的创建、物理配置、复制和备份等任务，用户付费即可。
[*]DBMS接纳差别于传统DBMS的体系结构。
[*]例子：Amazon Auora，ClearDB.
7.3 研究热门
7.3.1 内存存储
传统数据库都是面向盘存储的，这在以前简直是必要的，内存的容量和费用都不允许把整个数据库存放在内存中。如今，内存的容量已经足够存储险些最大的OLTP数据库了，费用也不是标题了。内存存储将使得数据库操纵更加优化，数据库访问更加速捷。
内存数据库并非新技术，NewSQL需处理的新标题是: NewSQL应有能力选出不常用的数据子集，将其移出到永久存储介质上，从而能够支持数据量大于内存容量的数据库。实现的途径通常就是一种内部的数据访问跟踪机制。
内存存储的NewSQL DBMS有: H-Store、HyPer、MemSQL、 VoltDB。
7.3.2 数据分片
[*]数据库被分别成不相交的数据子集，分散存放在差别的节点上。这实在就是分布式数据库的理念。分布式数据库并未流行起来的原因有两个：第一，20世纪的硬件太昂贵，一样寻常的机构承受不了把数据库部署在计算机集群上的费用；第二，那时也没有猛烈的对高性能分布式数据库的应用需求，那时所期望的数据库峰值吞吐量一样寻常是每秒几十到几百个变乱。
[*]NewSQL系统把查询分解成对分片的查询，把各节点的查询果组合成一个单一的结果交给用户。很多OLTP数据库应用中，数据库中的表由外键关系形成了一个树状的结构，如许的结构利于水中分片，诱导分片，分片使得同一实体的相干纪录存放在同一个结点上。如许的数据分片也使得多数变乱只用访问一个节点，从而低沉系统运行的通信代价。
[*]有的NewSQL DBMS接纳了异构的节点体系结构。例如 MemSQL 和NuoDB，它们的节点分为存储管理节点和变乱引擎节点。如许的做法，可以在不进行重新分片的情况下，向DBMS集群中增加计算资源。
[*]NewSQL的一个新特点是，DBMS支持数据的动态迁移，数据迁移可以解决负载平衡的标题。在服务不中断而且保障变乱的ACID特性的条件下，在存储节点间迁移数据是很困难的。
7.3.3 并发控制
分布式数据库基本上接纳2PL进行并发控制。由于处理死锁标题太复杂，NewSQL基本上不接纳2PL。当前的趋势是使用Multi-Version Concurrency Control(MVCC)。MVCC既可以基于锁实现，也可以基于时间印实现，大多数NewSQL使用基于时间印的MVCC。
7.3.3.1 基于时间印的MVCC
每个变乱T有一个由系统赋予的唯一的时间印TS(T)，后启动的变乱的时间印大于先启动的变乱的时间印。每个数据项O有一个读时间印RTS(O)和一个写时间印WTS(O)。
实行情况：
[*]如果变乱T想要读数据项O：
[*]如果TS(T)小于WTS(O)，则比T后启动的变乱已改变了O的值，T已经无法读到它想要的那个值，T被回滚并被重新启动。
[*]如果TS(T)不小于WTS(O)，则T读О的值是安全的，允许该操纵，并用max(RTS(O), TS(T))更新RTS(O)。
[*]如果变乱T想要写数据项О：
[*]如果TS(T)小于RTS(O)，则有一个比T后启动的变乱正在使用О的当前值，该写操纵将破坏数据同等性，不被允许，T被回滚并被重新启动。
[*]如果TS(T)小于WTS(O)，则有一个比T后启动的变乱已更改О的值，依据Thomas写规则，该写操纵被忽略。（为什么)【因为比T后启动的变乱要修改O的值，它会修改变乱T修改后的数据，以是此时变乱T的写操纵被忽略】
[*]否则，该写操纵被允许，并用TS(T)更新WTS(O)。
7.3.3.2 基于时间印的MVCC（改进——解决级联依赖标题）
标题：
[*]变乱由一组有序的读写操纵构成，变乱 T i T_i Ti写的数据被变乱 T j T_j Tj读取使用后，变乱 T i T_i Ti被回滚了，变乱 T i T_i Ti要怎么办?
答：变乱 T j T_j Tj也只能被回滚。变乱之间存在依赖关系，一个变乱被回滚，依赖它的一系列变乱都要被回滚。级联依赖将导致级联回滚。
[*]变乱 T i T_i Ti写的数据被变乱 T j T_j Tj读取使用后，变乱 T j T_j Tj先实行至commit，变乱 T j T_j Tj可以先提交吗?
答：不能。变乱 T i T_i Ti在没有提交前都有可能回滚，如果变乱 T j T_j Tj先提交了，当 T i T_i Ti被回滚时，就无法回滚 T j T_j Tj了。而在这种情况下，是必须回滚 T j T_j Tj的。变乱 T j T_j Tj必须等待变乱 T i T_i Ti提交之后才气提交。级联依赖关系也会导致变乱提交的级联等待。
实行情况：
[*]如果变乱T想要读数据项O：
[*]如果TS(T)小于WTS(O)，则比T后启动的变乱已改变了O的值，T已经无法读到它想要的那个值，T被回滚并被重新启动。
[*]如果TS(T)不小于WTS(O)，则T读О的值是安全的，允许该操纵，DEP(T).add(WTS(O))， 并用max(RTS(O), TS(T))更新RTS(O)。
[*]如果变乱T想要写数据项О：
[*]如果TS(T)小于RTS(O)，则有一个比T后启动的变乱正在使用О的当前值，该写操纵将破坏数据同等性，不被允许，T被回滚并被重新启动。
[*]如果TS(T)小于WTS(O)，则有一个比T后启动的变乱已更改О的值，依据Thomas写规则，该写操纵被忽略。（为什么)【因为比T后启动的变乱要修改O的值，它会修改变乱T修改后的数据，以是此时变乱T的写操纵被忽略】
[*]否则，该写操纵被允许，并用TS(T)更新WTS(O)。
[*]若DEP(T)中的变乱还有未提交的，T必须等待，不能提交，当若DEP(T)中的所有变乱都提交了，T可以提交。若DEP(T)中的某个变乱被回滚，T也必须被回滚。
7.3.3.3 基于时间印的MVCC（改进——进步系统服从）
标题：
[*]一样寻常情况，对数据库的读操纵和写操纵，哪个更多?
答：读操纵要多得多。很多变乱是只读变乱，有的只读变乱读取大量数据项。
[*]时间印调度是否可能导致变乱频繁被回滚?
答：有可能。频繁的变乱回滚也会低沉系统服从，还有可能导致长的只读变乱出现饥饿现象。
基于TO的MVCC仍旧使用时间印调度，但保存数据项的多个版本，从而使得所有的读操纵都不会失败。
每个数据项О都保存多个版本，O的任一版本 O i O_i Oi都有它的读时间印RTS( O i O_i Oi)和写时间印WTS( O i O_i Oi)。
实行情况：
[*]如果变乱T想要读数据项О：
[*]若WTS( O i O_i Oi)是O各个版本中写时间印小于等于TS(T)中的最大者，返回 O i O_i Oi的值。DEP(T).add(WTS( O i O_i Oi))，并用max(RTS( O i O_i Oi), TS(T))更新RTS( O i O_i Oi)。
[*]如果变乱T想要写数据项O：
[*]在О的各个版本中，WTS( O i O_i Oi)是最大的写时间印，如果TS(T)大于或等于WTS( O i O_i Oi)且TS(T)小于RTS( O i O_i Oi)，T被回滚并被重新启动。否则，创建O的一个新版本，其读时间印和写时间印都置为TS(T)。
[*]若DEP(T)中的变乱还有未提交的，T必须等待，不能提交，当若DEP(T)中的所有变乱都提交了，T可以提交。若DEP(T)中的某个变乱被回滚，T也必须被回滚。
标题：
[*]MVCC的变乱回滚应怎么处理?
答：逐一删除被回滚变乱所创建的数据版本。
[*]MVCC导致数据版本不停累积，是否有必要保存所有的数据版本。
答：没必要。过多的数据版本也会浪费存储资源。数据库系统每隔一段时间运行垃圾处理步调删除无用的数据版本。判定无用的规则:在写时间印小于系统当前最老变乱的时间印的数据版本中，WTS( O i O_i Oi)最大，保存 O i O_i Oi，写时间印小于WTS( O i O_i Oi)的数据版本均无用。
7.3.4 辅助索引
[*]辅助索引指建立在非主键属性或非分区键属性上的索引。辅助索引能够加速查询条件涉及非主键属性或非分区键属性的那些查询。当数据库面对很多如许的查询时，辅助索引能够非常有效地提升查询性能。
[*]建立辅助索引面对两个标题：①如何保存索引；②如何更新索引。
[*]构建在新构架上的NewSQL都在每个节点上建立局部辅助索引。这种做法，查询必要多个节点共同相互共同，但变乱对一个数据项的写操纵引起的辅助索引更新只要在一个节点上处理即可。
7.3.5 复制
[*]确保高可用性和高可靠性的最好方法就是节点间的复制。对于强同等性的DBMS必须包管在变乱提交前在变乱的所有副本上完成变乱的更新处理。维持副本间的同步要求DBMS使用原子性的提交协议（例如2PC)。
[*]所有的NewSQL都支持强同等性，而NoSQL通常仅支持弱同等性(最终同等性)。NoSQL系统通知应用写完成时，并非所有的副本都确认了更新。
[*]副本间的更新传播可以接纳主从式结构来实现，如果接纳对等结构则必要使用以Paxos算法为代表的一类方法进行协调。
7.3.6 故障规复
[*]传统数据库系统关注的焦点是更新不能丢失，NewSQL除了这个焦点外，还希望最小化数据库系统的服务中断时间。
[*]NewSQL建构在集群之上，基本上每个节点都有若干同步复制的节点，当一个节点瓦解了，与之同步的节点可以替换它的作用（数据库服务险些没有中断)，瓦解的节点依赖自身的日志规复到的状态已经不是数据库的最新状态，还必要与替换它的节点同步才气规复到数据库的最新状态。
7.4 将来的趋势
[*]在新数据和历史数据上的混合分析处理。有的数据在最新的时候代价最高。
[*]支持机器学习算法的运行。
[*]OLTP与OLAP合二为一避免数据库向数据仓库的数据迁移。
第八章 NoSQL数据库（理解即可）
8.1 基本概念
[*]NoSQL=Not Only SQL。
[*]非关系型的数据存储。不必要预界说数据模式。
[*]将数据进行分别，分散在多个节点上存储。
[*]弹性可扩展：可以在系统运行的时候，动态增加或者删除结点，不必要停机维护，数据可以自动迁移。
[*]NoSQL数据库并不严格包管变乱的ACID特性，仅包管最终同等性和软变乱。
[*]NoSQL数据库并没有统一的架构。
8.2 GFS
8.2.1 Bigtable的存储基础
Bigtable的一个表往往必要占用集群中多台服务器的存储空间。GFS ( Google File System）是一个分布式文件系统，统一管理集群中浩繁服务器的存储空间。Bigtable 以GFS为存储基础，无需处理存储位置与物理服务器间的关系。
8.2.2 架构
https://img-blog.csdnimg.cn/direct/ac8f768cd88f4ff2a73ac56e392c8288.png
8.2.3 特点
[*]接纳中央折务器模式: Master服务器管理文件系统的所有元数据，文件被分别成Chunk（默认64MB，对应为本地文件系统的一个文件)，Chunk服务器管理Chunk 为文件提供存储空间。客户端的所有操纵都先经过Master服务器，获取Chunk句柄和位置，客户端直接与Chunk服务器交互来存
取Chunk。Chunk服务器之间没有任何关系，可随时向Master服务器注册加入到文件系统中，也可随时退出文件系统。Chunk服务器之间的负载平衡由Master服务器负责。
[*]不缓存数据
[*]用户态下实现，Master服务器和Chunk服务器都以进程的方式运行。
[*]只提供专用接口，与POSIX规范不兼容。
8.2.4 容错机制
[*]Master服务器保存的元数据包括命名空间（整个文件系统的目录结构)、Chunk与文件名的映射表和Chunk副本的位置信息。
[*]Master服务器依赖日志和远程备份两种机制容错。
[*]每一个Chunk有多个存储副本（默认3个），分布存储在差别的Chunk服务器上。一旦某个Chunk服务器宕机，Master服务器可启动一台新的Chunk服务器替换它。
8.3 Chubby
8.3.1 锁服务
[*]Chubby是一个提供粗粒度锁服务的文件系统。
[*]Chubby锁是一种发起性的锁，而非强制性的锁。
[*]GFS使用Chubby选取一个Master服务器。
[*]Bigtable使用Chubby指定一个主服务器并发现、控制与其相干的子表服务器。
8.3.2 Chubby单元
https://img-blog.csdnimg.cn/direct/f22eff3f7b6e47e19c1a09308ab8b51b.png#pic_center
一个Google数据中央仅运行一个Chubby单元，一个Chubby单元一样寻常由5个配置完全相同的服务器构成，向客户端提供高度可靠的服务。Chubby单元的多个服务器维持同等的副本，恣意一个服务器都可以向客户端提供服务，提供服务的过程中宕机，Chubby单元可以自动选择另一服务器接替其工作。
8.3.3 Chubby服务器
https://img-blog.csdnimg.cn/direct/36fe5355b38140fba07a564007109727.png#pic_center
最底层是一个容错日志，副本之间通过Paxos协议进行通信保障数据同等性，中间层是一个容错的数据库，Chubby构建在这个数据库之上，所有的数据都存储在这个数据库中。Chubby是一个存储大量小文件的文件系统，每个文件代表一个锁，用户通过打开或关闭文件得到或释放锁，通过读取文件获取相干信息。
8.3.4 Chubby通信协议
https://img-blog.csdnimg.cn/direct/33b0377522c645b28935e69cd9296927.png
初始时，客户端向主服务器发出KeepAlive请求（1），如果有必要通知的时间则主服务器会立刻回应，否则主服务器并不立刻回应，而是等到客户端的租约期C1快结束时才回应(2)，并更新主服务器的租约期为M2。客户端接到回应后以为主服务器仍处于活泼状态，将租约期更新为C2，并向主服务器发出新的KeepAlive请求(3）。同样地，主服务器可能不是立刻回应而是等待C2接近结束，但是这个过程中主服务器出现故障制止使用。一段时间后C2到期，客户端清空并暂停使用自己的缓存，进入脱期期（默认45秒)，在脱期期内客户端不断探询服务器的状态。新的主服务器会很快被重新选出，当它接到客户端的第一个KeepAlive请求(4）时，由于这个请求带有旧服务器的标识，发出带有新服务器标识的拒绝回应(5)。
客户端收到后用新服务器标识再次发送KeepAlive请求(6）。新的主服务器担当这个请求并立刻回应（7）。如果客户端在脱期期内收到这个回应，规复到安全状态，租约期更新为C3。如果客户端没有在脱期期内收到这个回应，客户端终止会话。
通常，遇到主服务器宕机时Chubby单元可以在脱期期内完成新旧主服务器的替换，用户感觉不到主服务器宕机了。
8.4 Bigtable
8.4.1 特点
[*]Bigtable构建在GFS和Chubby的基础上。
[*]支持处理各种数据范例。
[*]支持海量的服务请求，可用性高。
[*]可以部署在大量的服务器之上，而且可以随时加入或撤销服务器。
8.4.2 数据模型
[*]Bigtable的存储逻辑可以表示为:
(row:string, column:string, time: int64)—>string
[*]Bigtable的存储格式如下:
https://img-blog.csdnimg.cn/direct/6bc8faf9e06a4be3b5d1fdb939d8c8dc.png#pic_center
[*]Bigtable的行
[*]Bigtable是一个分布式多维映射表，表中的数据通过行关键字、列关键字和时间戳来索引。Bigtable对数据不做解析，同等看作字符串，详细数据结构的实现需用户自行处理。
[*]行关键字可以是恣意字符串，巨细不超过64KB。Bigtable不支持一样寻常意义的变乱，但能包管对行读写操纵的原子性。
[*]表中的数据按照行关键字排序。Bigtable把一个表分成多个子表，每个子表包罗多个行，子表是Bigtable中数据分别和负载平衡的基本单元。
[*]Bigtable的列
[*]包罗哪些列无需事先界说。
[*]范例相同的列构成列族，同族的数据会被压缩在一起保存(相称于垂直分片)。
[*]列关键词的形式为，族名: 限定词( family: qualifier )
[*]Bigtable的时间戳
[*]Bigtable的时间戳是一个由系统天生的代表当前时候的64位整数。
[*]时间戳的作用是区分同一数据的差别版本。
[*]Bigtable处理数据版本有两个差别计谋。一种是保存迩来的N个差别版本，另一种是保存迩来一段时间的所有版本。
8.4.3 系统架构
https://img-blog.csdnimg.cn/direct/adf76a081f624841bdff925bb95e9c72.png#pic_center
Bigtable在Google WorkQueue、GFS和Chubby三个组件基础上构建。Google WorkQueue处理分布式队列分组和任务调度，Google未公布其细节。GFS用来存储数据和日志。Chubby的主要作用包括：1.选取并包管同一时间内只有一个主服务器；2.索引子表位置信息；3.保存Bigtable 模式信息及访问控制列表。
Bigtable由客户端步调库、一个主服务器和多个子表服务器三部门构成。客户端访问Bigtable服务与主服务器的交互少少，客户端通过Open()操纵从Chubby那里取得一个锁后直接与子表服务器交互。
主服务器负责元数据操纵和子表服务器之间的负载调度。一个表被分别为多个子表（相称于水中分片)，子表巨细一样寻常在100M至200M之间，运行过程中子表巨细变化后，系统兵动分割或合并子表。一个子表服务器通常保存多个子表。
8.4.4 主服务器
[*]当一个新的子表产生时，主服务器通过一个加载下令将其分配给一个空间足够的子表服务器。
[*]创建新表和表合并都会产生新的子表，主服务器自动检测并进行处理。
[*]较大子表的分裂由子表服务器发起并完成，子表服务器完成后通过Chubby通知主服务器为新的子表分配子表服务器。
[*]子表服务器的基本信息保存在Chubby中一个称为服务器目录的特别目录中，主服务器通过检测这个目录可以了解子表服务器的状态，子表服务器包罗哪些子表等信息。
[*]主服务器一旦检测到某个子表服务器出现标题，将中止该子表服务器，将其上的子表移到其他子表服务器上。
[*]主服务器一旦检测到某个子表服务器负载过重会自动进行负载平衡操纵。
[*]主服务器自身也有可能出现故障，系统启动新的主服务器的过程包罗4个步调：
[*]从Chubby中得到一个独占锁，确保同一时间只有一个主服务器。
[*]扫描Chubby上的服务器目录，发现当前活泼的子表服务器。
[*]与所有活泼子表服务器取得联系。
[*]扫描元数据表，发现未分配的子表并将其分配给符合的子表服务器。
8.4.5 子表结构
https://img-blog.csdnimg.cn/direct/a6f8cf1411494ccd88b786e14ec634d6.png
[*]每个子表都由多个存储在GFS上的SSTable文件构成，SSTable被分成若干个块（一样寻常64K，可调整)，末端处有一个索引保存块的位置信息。
[*]每个子表服务器维持一个日志文件，日志的内容按键值排序，与子表形身分段对应关系。
8.4.6 元数据表
https://img-blog.csdnimg.cn/direct/760c4f5c152b46dc866144b8e726b390.png
所有的子表地址存储在元数据表中，元数据表由一个个元数据子表构成，其结构与B＋树类似。Chubby中的一个文件存储根子表信息。根子表是元数据表的第一条纪录，也保存其他元数据子表的地址。
8.4.7 读写操纵
https://img-blog.csdnimg.cn/direct/523a5671ddef44a29d8e05da007d64d2.png
[*]Bigtable把较新的数据存储在内存中，称为内存表，把较早的数据以SSTable 格式保存在GFS中。
[*]写数据时先写日志，再写内存表，即完成写操纵，并不急于立刻写入GFS。
[*]读数据时，需合并读出的SSTable和内存表。
[*]内存表容量超过一个阈值时，旧的内存表会被压缩成SSTable格式存入GFS。
第九章 课程设计
9.1 需求
[*]单车信息应按城市水中分片
[*]用户量大，用户描述信息（包罗用户余额）需分片。
[*]行程信息量更大，还需纪录行程轨迹（用 bigtable 类似存储）。
[*]用户的优惠卷信息，到期自动删除。
[*]公司的充值活动、优惠卷活动，活动结束自动删除。
[*]充值、兑现、购买优惠卷的支付处理（跨数据库的同等性提交）。
[*]开锁处理（含判断是否有钱）
[*]上锁处理（含付费）
设计文档包括表及其结构、表间的关联、表的分布设计、<key, value>存储及其与表之间的联系、关键变乱的描述、主要的查询流程。
9.2 设计
9.2.0 类图
[*]旧版
https://img-blog.csdnimg.cn/direct/25589f3d2565486b85c79fc678903fb7.jpeg
[*]新版
https://img-blog.csdnimg.cn/direct/625a55145b4b4c9fb93bc1a30d69dea9.jpeg
[*]最新版
https://img-blog.csdnimg.cn/direct/57e2e15fd9a847f5adce8c557bf8a499.jpeg
9.2.1 表及其结构
[*] 用户表
https://img-blog.csdnimg.cn/direct/95bb7ad6ea39466885354c2f29e17a88.png
[*] 优惠卷表
https://img-blog.csdnimg.cn/direct/1f33701294a94daeab1940d6d37fa393.png
最新版
https://img-blog.csdnimg.cn/direct/af8b4f605e104eb0a979a2a01599db8f.png
[*] 活动表
https://img-blog.csdnimg.cn/direct/af7e9cb09e5a4e9d998b539d7d070f6f.png
[*] 单车表
https://img-blog.csdnimg.cn/direct/8434abd355e44f4493bad0da560ac362.png
[*] 行程表
https://img-blog.csdnimg.cn/direct/19c1f80939264717b1b259ddd07180cf.png
最新版
https://img-blog.csdnimg.cn/direct/e94af47a20604bd48ccd4e4db6980802.png
[*] 轨迹表
https://img-blog.csdnimg.cn/direct/161f040bf04541cc8bd888fbb9674e83.png
最新版
https://img-blog.csdnimg.cn/direct/6bf68cbec52849e4b70e0dd8247ae287.png
[*] 持有优惠卷表【最新版去除这张表】
https://img-blog.csdnimg.cn/direct/b50651d71c2747cfb81c33b40ca45cbf.png
[*] 参与活动表
https://img-blog.csdnimg.cn/direct/63cd32f8022749bc82038a4dec9ac177.png
[*] 骑行表 【最新版去除这张表】
https://img-blog.csdnimg.cn/direct/9eee906526f34e999cb819ddf1356d0e.png
[*] 订单表
https://img-blog.csdnimg.cn/direct/9e267c20c6dc46fdbe3a208d2dd3d777.png
9.2.2 表间的关联（ER图）
[*]旧版
https://img-blog.csdnimg.cn/direct/c117694d7b164636baf155b4f257c3b9.jpeg
[*]新版
https://img-blog.csdnimg.cn/direct/34fd328416a04e98b64a1e7fd44a0d34.jpeg
[*]最新版
https://img-blog.csdnimg.cn/direct/aa3f1a7de13e4284bde1c888b250fd50.jpeg
[*]_user表与其他表的关联
1.1 _activity表：多对多，用户可以参与多个活动，每个活动可以有多名用户参与，他们之间通过_utoa表进行关联，_utoa表中_uid是和_aid是外键，分别对应_user表的_id和_activity表的_id；
1.2 _coupons表：一对多，用户可以拥有多张优惠卷，而一张优惠卷只能属于一个用户，其中_uid是外键，对应_user表中的_id
1.3 _order表：一对多，用户可以创建多个订单，而一个订单只能属于一个用户，其中_uid是外键，对应_user表中的_id
1.4 _trip表：一对多，用户可以拥有多个行程，而一个行程只能属于一个用户，其中_uid是外键，对应_user表中的_id
[*]_activity表与其他表的关联
2.1 _user表：多对多，用户可以参与多个活动，每个活动可以有多名用户参与，他们之间通过_utoa表进行关联，_utoa表中_uid是和_aid是外键，分别对应_user表的_id和_activity表的_id；
[*]_coupons表与其他表的关联
3.1 _user表：多对一，用户可以拥有多张优惠卷，而一张优惠卷只能属于一个用户，_coupons表中_uid是外键，对应_user表中的_id
[*]_bike表与其他表的关联
4.1 _trip表：一对多，单车可以拥有多个行程，而一个行程只能属于一辆单车，其中_bid是外键，对应_bike表中的_id
[*]_trip表与其他表的关联
5.1 _user表：多对一，用户可以拥有多个行程，而一个行程只能属于一个用户，_trip表中_uid是外键，对应_user表中的_id
5.2 _track表：一对多，一个行程可以拥有多个轨迹点，而一个轨迹点只能属于一个行程，其中_tid是外键，对应_trip表中的_id
5.3 _bike表：多对一，单车可以拥有多个行程，而一个行程只能属于一辆单车，_trip表中_bid是外键，对应_bike表中的_id
[*]_track表与其他表的关联
6.1 _trip表：多对一，一个行程可以拥有多个轨迹点，而一个轨迹点只能属于一个行程，_track表中_tid是外键，对应_trip表中的_id
[*]_order表与其他表的关联
7.1 _user表：多对一，用户可以创建多个订单，而一个订单只能属于一个用户，_order表中_uid是外键，对应_user表中的_id
9.2.3 表的分布设计
[*]_user表按账号_id进行水中分片，如：_user1表、_user2表等等
[*]_bike表按所属城市_city进行水中分片，如：_bike_beijing表、_bike_fujian表等等
[*]_trip表按单车编号_bid或者用户账号_uid进行水中分片，如：_bike1表、_bike2表等等
[*]_order表按用户账号_uid进行水中分片，如：_order1表、_order2表等等
9.2.4 <key, value>存储及其与表之间的联系
[*]行程表(_trip)中的数据用Bigtable进行存储，对应关系如下：
row：编号(_id)
column：用户账号(_uid)，单车编号(_bid)，开锁时间(_unlock)，上锁时间(_lock)，费用(_fare)
[*]轨迹表(_track)中的数据使用Bigtable进行存储，对应关系如下：
row：行程编号(_tid)
column：时间(_time)，位置(_location)
9.2.5 关键变乱的描述
9.2.5.1 优惠卷到期自动删除（活动结束自动删除也是一样）
方案一：数据库触发器
如果数据库支持触发器（如MySQL、PostgreSQL），可以创建一个触发器，天天检查并删除过期的优惠券（活动）。
CREATE TRIGGER delete_expired_coupons
AFTER INSERT ON _coupons
FOR EACH ROW
BEGIN
DELETE FROM _coupons
WHERE _deadline < CURDATE();
END;
CREATE TRIGGER delete_expired_activity
AFTER INSERT ON _activity
FOR EACH ROW
BEGIN
DELETE FROM _activity
WHERE _deadline < CURDATE();
END;
方案二：定时任务调度
使用Cron或Quartz等定时任务调度器，通过定期实行脚原来删除过期的优惠券（活动）。
[*]使用Cron定时任务（Linux系统）
起首，创建一个脚本文件（如delete_expired_coupons.sh）；然后，设置Cron任务，天天定时实行该脚本：
[*]使用Quartz定时任务（Java应用）
如果你使用的是Java应用，可以使用Quartz框架来调度任务。起首，添加Quartz依赖；然后，创建定时任务类；最后，配置Quartz调度器；
9.2.5.2 充值（跨数据库的同等性提交）
[*]用户发起充值请求，指定充值金额。
[*]系统天生订单（_order），状态设为1（表示“处理中”）。
[*]调用第三方支付网关，进行现实支付处理。
[*]支付成功后，更新支付订单状态为2（表示“支付成功”）。
[*]增加用户余额（_user的_balance）。
[*]使用分布式变乱（如两阶段提交）确保订单和用户余额的更新同等性。
[*]返回充值成功信息给用户。
9.2.5.3 兑现（跨数据库的同等性提交）
[*]用户发起兑现请求，指定兑现金额。
[*]系统天生订单（_order），状态设为1（表示“处理中”）。
[*]检查用户余额是否足够进行兑现。
[*]调用第三方支付网关，进行现实支付处理。
[*]兑现成功后，更新支付纪录状态为2（表示“支付成功”）。
[*]减少用户余额（_user的_balance）。
[*]使用分布式变乱确保订单和用户余额的更新同等性。
[*]返回兑现成功信息给用户。
9.2.5.4 购买优惠卷（跨数据库的同等性提交）
[*]用户请求购买优惠券。
[*]系统天生订单（_order），状态设为1（表示“处理中”）。
[*]调用支付网关进行处理。
[*]支付成功后，更新支付纪录状态为2（表示“支付成功”）。
[*]创建优惠券纪录（_coupons）。
[*]使用分布式变乱确保数据同等性。
[*]返回购买成功信息给用户
9.2.5.5 开锁（含判断是否有钱）
[*]用户请求开锁，并提供 _user的_id 和 _bike的_id。
[*]检查用户余额（_user的_balance）。
[*]如果余额充足，更新单车状态为1表示"使用中"（_bike的_state）。
[*]创建行程纪录（_trip）并纪录开锁时间
[*]创建轨迹点纪录（_track）并纪录当前时间和位置。
[*]返回开锁成功状态。
9.2.5.6 上锁（含付费）
[*]用户请求上锁，并提供 _user的_id 和 _bike的_id。
[*]更新单车状态为0表示“空闲”（_bike的_state）。
[*]更新行程纪录（_trip），纪录上锁时间。
[*]计算行程费用，纪录费用（_trip表的_fare）
[*]创建订单（_order），纪录金额（_order表的_amount）。
[*]用户支付订单并更新用户余额（_user的_balance）。
[*]返回上锁成功状态。
9.2.6 主要的查询流程
9.2.6.1 查询可用单车流程
[*]用户请求查询附近可用单车的信息。
[*]系统根据 _city 定位到对应的数据库分片。
[*]在单车信息表（_bike）中查询状态为0（表示“空闲”）且位置在用户附近的单车。
[*]返回单车信息，包括单车编号、位置和状态。
9.2.6.2 查询行程信息流程
[*]用户请求查询自己的行程历史。
[*]系统根据 _id 定位到对应的数据库分片。
[*]在行程信息表（_trip）中查询所有 _uid 对应的行程纪录。
[*]返回行程纪录列表，包括每次行程的详细信息。
9.2.6.3 查询行程轨迹流程
[*]用户选择某次行程，查看行程轨迹。
[*]系统根据行程的 _id 在行程轨迹表（_track）中查询轨迹数据。
[*]返回轨迹数据，按时间排序，显示行程门路。
9.2.6.4 查询可使用的优惠券流程
[*]用户请求查询自己的有效优惠券。
[*]系统根据用户的 _id 在优惠卷表（_coupons）中查询状态为0（表示“未使用”）且在有效期内的优惠券。
[*]返回优惠券列表，包括优惠券的详细信息和有效期。
9.2.6.5 查询正在进行的活动流程
[*]用户请求查询当前正在进行的活动。
[*]系统查询活动表（_activity），筛选出状态为1（表示“进行中”）的活动。
[*]返回查询结果，包括活动的详细信息、开始和结束日期。
9.2.6.6 查询订单流程
[*]用户请求查询自己的支付纪录。
[*]系统根据用户账号 _id 定位到订单表（_order）的对应分片。
[*]查询所有 _uid 与用户账号 _id 对应的支付纪录。
[*]返回支付纪录列表，包括每笔支付的详细信息和状态。
9.2.6.7 查询余额流程
[*]用户请求查询自己的余额
[*]系统根据用户账号 _id 定位到用户表（_user）的对应分片。
[*]查询用户账号 _id 对应用户余额。
[*]返回余额信息。
9.2.6.8 查询参与活动的用户信息流程
[*]管理员请求查询某个活动的用户参与情况
[*]系统根据活动编号 _id 在参与活动表（_utoa）查询参与活动的用户账号 _uid
[*]根据查询到的用户账号 _uid，在用户表（_user）查询对应用户信息
[*]返回用户信息列表，包括用户的账号，姓名，联系方式等等
9.2.6.9 查询需维护的单车位置流程
[*]管理员请求查询”维护中"的单车位置
[*]系统根据 _city 定位到对应的数据库分片。
[*]在单车信息表（_bike）中查询状态为3（表示“维护中”）单车信息。
[*]返回单车信息列表，包括单车编号、位置和状态。
第十章 OceanBase 数据库分布式变乱的实现机制
10.1 概述（总结）
我们详细介绍了 OceanBase 数据库的分布式变乱实现机制，焦点是通过优化的两阶段提交协议（2PC）来确保分布式变乱的同等性和可靠性。并解释了分布式变乱的基本概念、ACID特性（原子性、同等性、隔离性、持久性）、CAP理论（同等性、可用性、分区容错性）和 BASE理论（基本可用、软状态、最终同等性）。
在传统 2PC 的基础上，OceanBase 进行了耽误优化，通过异步提交协调者日志和提前决策提交点来减少提交耽误，同时每个参与者需持久化参与者列表以便异通例复。OceanBase数据库的分布式变乱实现的关键技术点还包括全局同等性快照技术，通过快照隔离级别和多版本并发控制 (MVCC) 提供同等的版本号，确保跨节点变乱操纵的同等性；锁机制接纳行级锁粒度，多版本两阶段锁和锁的存储在行上，减少内存开销并进步并发处理能力。
通过这些技术和优化，OceanBase 确保了分布式情况下的数据同等性和变乱处理的高效性，适应各种复杂的分布式应用场景。
10.2 分布式变乱的基本概念
10.2.1 基本概念
分布式变乱就是指变乱的参与者、支持变乱的服务器、资源服务器以及变乱管理器分别位于差别的分布式系统的差别节点之上。以上是百度百科的解释，简朴的说，就是一次大的操纵由差别的小操纵构成，这些小的操纵分布在差别的服务器上，且属于差别的应用，分布式变乱必要包管这些小操纵要么全部成功，要么全部失败。本质上来说，分布式变乱就是为了包管差别数据库的数据同等性。
分布式变乱主要有两种场景，一种仅仅是服务内操纵涉及到对多个数据库资源的访问。当一个服务操纵访问差别的数据库资源，又希望对它们的访问具有变乱特性时，就必要接纳分布式变乱来协调所有的变乱参与者。如下图：
https://img-blog.csdnimg.cn/direct/03115a0864e74846a440fef5410c0f74.png#pic_center
上面介绍的分布式变乱应用场景管一个服务操纵会访问多个数据库资源，但是究竟整个变乱照旧控制在单一服务的内部。如果一个服务操纵必要调用另外一个服务，这时的变乱就必要跨越多个服务了。在这种情况下，起始于某个服务的变乱在调用另外一个服务的时候，必要以某种机制流转到另外一个服务，从而使被调用的服务访问的资源也自动加入到该变乱当中来。下图反映了如许一个跨越多个服务的分布式变乱：
https://img-blog.csdnimg.cn/direct/1abfa8e2a66c4784a5f3e56dbd3d212a.png
如果将上面这两种场景(一个服务可以调用多个数据库资源，也可以调用其他服务)结合在一起，对此进行延伸，整个分布式变乱的参与者将会构成如下图所示的树形拓扑结构。在一个跨服务的分布式变乱中，变乱的发起者和提交均系同一个，它可以是整个调用的客户端，也可以是客户端开始调用的那个服务。
https://img-blog.csdnimg.cn/direct/08bd7a6f02b94c01ba0a1210bb5d74ec.png
10.2.2 ACID特性
分布式变乱页需具备变乱的基本属性：原子性、同等性、隔离性、持久性。这四个属性通常称为ACID特性。
[*]原子性（atomicity）：个变乱是一个不可分割的工作单元，变乱中包括的诸操纵要么都做，要么都不做。
[*]同等性（consistency）：变乱必须是使数据库从一个同等性状态变到另一个同等性状态，变乱的中间状态不能被观察到的。
[*]隔离性（isolation）：一个变乱的实行不能被其他变乱干扰。即一个变乱内部的操纵及使用的数据对并发的其他变乱是隔离的，并发实行的各个变乱之间不能相互干扰。隔离性又分为四个级别：
[*]读未提交(read uncommitted)
[*]读已提交(read committed，解决脏读)
[*]可重复读(repeatable read，解决虚读)
[*]串行化(serializable，解决幻读)
[*]持久性（durability）：持久性也称永久性（permanence），指一个变乱一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操纵或故障不应该对其有任何影响。
10.2.3 CAP理论
CAP原则又称CAP定理，指的是在一个分布式系统中，同等性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP 原则指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。
[*]同等性（C）：在分布式系统中的所有数据备份，在同一时候是否同样的值。（等同于所有节点访问同一份最新的数据副本）
[*]可用性（A）：包管每个请求不管成功或者失败都有响应。
[*]分区容忍性（P）：系统中恣意信息的丢失或失败不会影响系统的继续运作
CAP原则的精髓就是要么AP，要么CP，要么AC，但是不存在CAP。如果在某个分布式系统中数据无副本， 那么系统一定满足强同等性条件， 因为只有独一数据，不会出现数据差别等的情况，此时C和P两要素具备，但是如果系统发生了网络分区状况或者宕机，一定导致某些数据不可以访问，此时可用性条件就不能被满足，即在此情况下得到了CP系统，但是CAP不可同时满足。
10.2.4 BASE理论
BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终同等性）三个短语的简写，BASE 理论是对 CAP 中的同等性和可用性进行一个衡量的结果，理论的焦点头脑就是：我们无法做到强同等，但每个应用都可以根据自身的业务特点，接纳适当的方式来使系统达到最终同等性。
[*]基本可用:分布式系统在出现不可预知故障的时候，允许丧失部门可用性—-留意，这绝不等价于系统不可用。
[*]软状态:允许系统中的数据存在中间状态，并以为该中间状态的存在不会影响系统的团体可用性，即允许系统在差别节点的数据副本之间进行数据同步的过程存在延时。
[*]最终同等性：所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个同等的状态。因此，最终同等性的本质是必要系统包管最终数据能够达到同等，而不必要及时包管系统数据的强同等性。
10.3 OceanBase分布式变乱的协议
10.3.1 传统的2PC（Two-Phase Commit）
二阶段提交协议（Two-phase Commit，即 2PC）是常用的分布式变乱解决方案，即将变乱的提交过程分为准备阶段和提交阶段两个阶段来进行处理。
参与角色
[*]协调者：变乱的发起者
[*]参与者：变乱的实行者
第一阶段
[*]协调者向所有参与者发送变乱内容，询问是否可以提交变乱，并等待答复
[*]各参与者实行变乱操纵，将 undo 和 redo 信息记入变乱日志中（但不提交变乱）
[*]如参与者实行成功，给协调者反馈同意，否则反馈中止
https://img-blog.csdnimg.cn/direct/786e1430571343d1b1c027ffeab22aa4.png
第二阶段
[*]当协调者节点从所有参与者节点得到的相应消息都为同意时：
协调者节点向所有参与者节点发出正式提交(commit)的请求。
参与者节点正式完成操纵，并释放在整个变乱期间内占用的资源。
参与者节点向协调者节点发送ack完成消息。
协调者节点收到所有参与者节点反馈的ack完成消息后，完成变乱。
[*]如果任一参与者节点在第一阶段返回的响应消息为中止，或者协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：
协调者节点向所有参与者节点发出回滚操纵(rollback)的请求。
参与者节点使用阶段1写入的undo信息实行回滚，并释放在整个变乱期间内占用的资源。
参与者节点向协调者节点发送ack回滚完成消息。
协调者节点受到所有参与者节点反馈的ack回滚完成消息后，取消变乱。
https://img-blog.csdnimg.cn/direct/612b7dceeed04ddd93472fe59d0a4842.png
长处：状态简朴，只依赖协调者状态即可确认和推进整个变乱状态
缺点：协调者写日志，commit延时高
10.3.2 OceanBase的2PC
用户能够感知到的最显着的一点，就是变乱提交的耽误。OceanBase从两方面入手优化。一方面，协调者的 Prepare 日志可以异步提交，参与者列表可以由所有参与者携带以解除对其的依赖；另一方面，两阶段提交的提交点完满是可以提前的，一个变乱是否提交除了可以由单个协调者来决定，还可以由所有参与者分布式地决定，即提交点可以提前为所有参与者将 Prepare 日志同步成功来决定。
基于上述两个思绪，OceanBase进行了下列改进：
[*]协调者不写日志，酿成了一个无持久化状态的状态机。
[*]变乱的状态由参与者的持久化状态决定所有参与者都prepare成功即以为变乱进入提交状态，立即返回客户端commit
[*]每个参与者都必要持久化参与者列表，方便异通例复时构建协调者状态机，推进变乱状态
[*]参与者增加clear阶段，标记变乱状态机是否终止
OceanBase 还对两阶段提交协议的时延进行了优化，将变乱提交回应客户端的机遇提前到 Prepare 阶段完成后（标准两阶段提交协议中为 Commit 阶段完成后）。
https://img-blog.csdnimg.cn/direct/cb3fbc21185c4760a0811da62b669fc6.png#pic_center
在上图中（绿色部门表示写日志的动作），左侧为标准两阶段提交协议，用户感知到的提交时延是4次写日志耗时以及2次 RPC 的往返耗时；右侧图中 OceanBase 的两阶段提交实现，由于少了协调者的写日志耗时以及提前了应答客户端的机遇，用户感知到的提交时延是1次写日志耗时以及1次 RPC 的往返耗时。
在 OceanBase 两阶段提交中通过协调者不写日志的思绪，在原子提交延时上直接省去了两条日志同步的延时，而且在资源接纳过程中也省去了 2 次日志同步。不过，我们也增加了一些负担：在资源接纳过程中多了 2 次消息传输，以及在资源消耗上多了 2N 条消息传输和 N 条日志同步。
考虑到在分布式数据库场景中，日志同步负担远大于消息传输（一样寻常部署会把 leader 部署在靠近的区域，而副本必须承受多地的容灾），而且延时的效应远大于资源接纳和资源斲丧，因此，我们以为本次优化确实带了了不少的进步。
10.4 实现机制（其他关键技术）
10.4.1 全局同等性快照技术
源于数据库中的两个传统概念：“快照隔离级别（Snapshot Isolation）”和“多版本并发控制（Multi-VersionConcurrency Control，简称MVCC）”。这两种技术的大致含义是：为数据库中的数据维护多个版本号（即多个快照），当数据被修改的时候，可以使用差别的版本号区分出正在被修改的内容和修改之前的内容，以此实现对同一份数据的多个版本做并发访问，避免了经典实现中“锁”机制引发的读写冲突标题。
因此，这两种技术被很多数据库产品（如Oracle、SQL Server、MySQL、PostgreSQL）所接纳，而OceanBase数据库也同样接纳了这两种技术以进步并发场景下的实行服从。但和传统的数据库的单点全共享（即Shared-Everything）架构差别，OceanBase是一个原生的分布式架构，接纳了多点无共享（即Shared-Nothing）的架构，在实现全局（跨机器）同等的快照隔离级别和多版本并发控制时会面对分布式架构所带来的技术挑战。为了应对这些挑战，OceanBase数据库在2.0版本中引入了“全局同等性快照”技术。
OceanBase数据库是使用一个集中式服务来提供全局同等的版本号。变乱在修改数据或者查询数据 的时候，无论请求源自哪台物理机器，都会从这个集中式的服务处获取版本号，OceanBase则包管 所有的版本号单调向前而且和真实世界的时间次序保持同等。
https://img-blog.csdnimg.cn/direct/18bfd6bc2b4a4fa3a36f41133763cbde.png#pic_center
有了如许全局同等的版本号，OceanBase就能根据版本号对全局（跨机器）范围内的数据做同等性快照，因此我们把这个技术命名为“全局同等性快照”。有了全局同等性快照技术，就能实现全局范围内同等的快照隔离级别和多版本并发控制，而不用担心发生外部同等性被破坏的情况。
10.4.2 锁机制
OceanBase 数据库的锁机制使用了以数据举动级别的锁粒度。同一行差别列之间的修改会导致同一把锁上的互斥；而差别行的修改是差别的两把锁，因此是无关的。OceanBase 数据库的读取是不上锁的，因此可以做到读写不互斥从而进步用户读写变乱的并发能力。对于锁的存储模式，选择将锁存储在行上（可能存储在内存与磁盘上）从而避免在内存中维护大量锁的数据结构。其次，会在内存中维护锁之间的等待关系，从而在锁释放的时候唤醒等待在锁上面的其余变乱。
[*]锁机制的粒度
OceanBase 数据库如今不支持表锁，只支持行锁，且只存在互斥行锁。在更新同一行的差别列时，变乱仍旧会相互阻塞，云云选择的原因是为了减小锁数据结构在行上的存储开销。而更新差别行时，变乱之间不会有任何影响。
[*]锁机制的互斥
OceanBase 数据库使用了多版本两阶段锁，变乱的修改每次并不是原地修改，而是产生新的版本。因此读取可以通过同等性快照获取旧版本的数据，因而不必要行锁仍旧可以维护对应的并发控制能力，因此能做到实行中的读写不互斥，这极大提升了 OceanBase 数据库的并发能力。
[*]锁机制的存储
OceanBase 数据库的锁存储在行上，从而减少内存中所必要维护的锁数据结构带来的开销。在内存中，当变乱获取到行锁时，会在对应的行上设置对应的变乱标记，即行锁持有者。当变乱实行获取行锁时，会通过对应的变乱标记发现自己不是行锁持有者而放弃并等待或发现自己是行锁持有者后得到行的使用能力。当变乱释放行锁后，就会在所有变乱涉及的行上解除对应的变乱标记，从而允许之后的变乱继续实行获取。
[*]锁机制的释放
OceanBase 数据库的锁在变乱结束（提交或回滚）的时候释放的，从而避免数据差别等性的影响。OceanBase 数据库还存在其余的释放机遇，即 SAVEPOINT，当用户选择回滚至 SAVEPOINT 后，变乱内部会将 SAVEPOINT 及之后所有涉及数据的行锁，全部根据 OceanBase 数据库锁机制的互斥 中介绍的机制进行释放。
10.4.3 MVCC（多版本并发控制）
变乱对数据库的任何修改的提交都不会直接覆盖之前的数据，而是产生一个新的版本与老版本共存，使得读取时可以完全不加锁。
MVCC的实现主要包括以下几个关键点：
[*]版本管理
每个数据行都会有多个版本，每个版本都有一个时间戳或者序列号来标识其创建时间。当一个变乱对数据行进行更新时，现实上是创建了该数据行的一个新版本。
旧版本的数据行在更新后不会立即被删除，而是标记为过期（或称为失效），如许已经开始的读变乱仍旧可以读取到旧版本的数据行，包管了变乱的同等性和隔离性。
[*]读操纵
读变乱可以在不受写变乱影响的情况下读取数据行的旧版本，从而实现了读写并发。
读变乱只能读取在其开始之前已经提交的变乱所写入的数据版本，而不能读取未提交或者已经回滚的变乱所写入的数据版本，如许包管了读变乱读取到的数据是同等的。
[*]写操纵
写变乱在实行更新操纵时，会为被更新的数据行创建一个新版本，而且在新版本的数据行上进行修改。如许可以包管在写变乱实行过程中，其他并发的读变乱仍旧可以读取到该数据行的旧版本，从而实现了读写并发。
写变乱在提交之前，会将更新后的新版本数据行的变更信息持久化到磁盘上的日志中，以确保变乱的持久性。
10.5 故障规复
10.5.1 分布式数据库的标题
在分布式数据库中，变乱故障规复的目的仍旧是要包管变乱的原子性和持久性。和单机数据库的差别在于，在分布式数据库中，数据的修改位于差别的节点。
10.5.2 单机变乱故障处理
OceanBase 接纳基于 MVCC 的变乱并发控制，这意味着变乱修改会保存多个数据版本，而且单个数据分片上的存储引擎基于 LSM-tree 结构，会定期进行转储（compaction）操纵。
变乱的修改会以新版本数据的形式写入到内存中最新的活泼 memtable 上，当 memtable 内存使用达到一定量时，memtable 冻结并天生新的活泼 memtable，被冻结的 memtable 会实行转储变化为磁盘上的 sstable。数据的读取通过读取所有的 sstable 和 memtable 上的多版本进行合并来得到所必要的版本数据。
https://img-blog.csdnimg.cn/direct/894c44dc944a4990aea07e5b81b40d9b.png#pic_center
单机变乱故障规复接纳了 Undo/Redo 日志的思绪实现。变乱在写入时会天生 Redo 日志，借助 MVCC 机制的旧版本数据作为 Undo 信息，实现了 Steal & No-Force 的数据落盘计谋。在变乱宕机规复过程中，通过 Redo日志进行重做规复出已提交未落盘的变乱，并通过规复保存的旧版本数据来回滚已经落盘的未提交变乱修改。
10.5.3 分布式变乱故障处理
当变乱操纵多个数据分片时，OceanBase 通过两阶段提交来包管分布式变乱的原子性。
https://img-blog.csdnimg.cn/direct/cb68b93533a949a7956a96ff7aa97cc7.png#pic_center
如上图所示，当分布式变乱提交时，会选择其中的一个数据分片作为协调者在所有数据分片上实行两阶段提交协议。还记得前文提到过的协调者宕机标题么？在 OceanBase 中，由于所有数据分片都是通过 Paxos 复制日志实现多副本高可用的，当主副本发生宕机后，会由同一数据分片的备副本转换为新的主副本继续提供服务，以是可以以为在 OceanBase 中，参与者和协调者都是包管高可用不宕机的（多数派存活），绕开了协调者宕机的标题。
在参与者高可用的实现条件下，OceanBase 对协调者进行了“无状态”的优化。在标准的两阶段提交中，协调者要通过纪录日志的方法持久化自己的状态，否则如果协调者和参与者同时宕机，协调者规复后可能会导致变乱提交状态差别等。但是如果我们以为参与者不会宕机，那么协调者并不必要写日志纪录自己的状态。
https://img-blog.csdnimg.cn/direct/3809d28c154442f1ac0fd65e9d6f7ac9.png#pic_center
上图是两阶段提交协议协调者的状态机，在协调者不写日志的条件下，协调者如果发生切主或宕机规复，它并不知道自己之前的状态是 Abort 照旧 Commit。那么，协调者可以通过询问参与者来规复自己的状态，因为参与者是高可用的，以是一定可以规复出整个分布式变乱的状态。
10.6 性能优化
10.6.1 分布式变乱范例的优化
对于分布式变乱的优化，差别范例的变乱提交耗时差别，性能调优应尽量低沉跨机分布式变乱的比例。变乱模型可以从以下几个方面入手：业务团体逻辑，细化到详细的变乱和了解多表、单表变乱的比例以及各类 SQL 的实行频率。
SQL 的实行计分别为四种：
[*]Local 表示当前语句所涉及的分区 Leader 与 Session 所在的机器相同；
[*]Remote表示当前语句所涉及的分区 Leader 与 Session 所在的机器差别；
[*]Distribute 和 Uncertain 表示不能确定 Leader 和 Session 的关系，可能在同一个机器，也可能跨多机。
对于变乱的性能而言，优先使用单机变乱，其次才是分布式变乱；根据实行计划的范例统计信息，可以大致估算出分布式变乱的比例，进而为调优提供数据支持。相干的 SQL 语句如图所示。
https://img-blog.csdnimg.cn/direct/39a28c5c009c4a15a6f084f567c4e6e0.png#pic_center
其中，plan_type = 1、2、3 分别表示 Local 、Remote 、Distribute 实行计划。一样寻常来讲，0 代表无 plan 的 SQL 语句，比如：set autocommit=0/1，commit 等。
非 Local 计划的请求（0除外），大概率会导致变乱跨机，相对于单机变乱，性能会有一定的影响。可按照以下几种情况进行检查，Primary Zone 为单 Zone & 单 Unit，Primary Zone 为单 Zone & 多 Unit 和 Primary Zone 为 RANDOM。
[*]对于Primary Zone 为单 Zone & 单 Unit 来说，单 Unit 部署的场景如果出现 Remote、Uncertain 计划，是不符合预期的，原因大概有几种：一是直连了该租户的 Follower。可根据实行计划的范例统计信息确认；二是应用毗连了 OBProxy，但变乱的第一条 SQL 无法被 OBProxy 进行正确的转发，导致 Session 和变乱所涉及的分区 Leader 跨机。此时必要去检查本集群所有 OBProxy 的日志，关键日志信息如图；三是部门分区刚刚切主，OBServer 或者 OBPoxy 维护的 Location Cache 尚未革新到最新。如果是情况 1，必要让应用改成毗连 OBProxy；如果是情况 2，说明当前 SQL 较为复杂，OBProxy 在 Parser 过程中无法计算出必要访问的分区，因此随机做了发送。此时必要对 SQL 写法进行调整，带上分区键；如果是情况 3，则不必要处理。
[*]对于Primary Zone 为单 Zone & 多 Unit ，该场景下，同 Zone 的 OBServer 会自动进行分区负载平衡，变乱跨机大概率是可能的。为了避免跨机变乱，结合变乱内语句实行情况，进行 Table Group 分别，尽量包管变乱单机实行。Table Group 的用法如图所示。
[*]最后是Primary Zone 为 RANDOM ，RANDOM 部署，该租户的表 Leader 随机打散，分布式跨机变乱同样是大概率的。
10.6.2 分布式变乱提交的优化
对于单表或多表的单机变乱，OceanBase 数据库 V4.0 版本由于做了单日志流架构的调整，只要变乱涉及的日志流 Leader 在同一个机器，默认会走单日志流变乱。这种变乱模型性能最高，因此不必要任何配置项的调整。而对于跨机变乱的处理，主要有两个标题，尽可能使用多机能力和OBServer 流量负载平衡。详细本领有
[*]结合变乱内语句实行情况，进行 Table Group 分别，尽量包管变乱单机实行，也就是前面讲到的Primary Zone 为单 Zone & 多 Unit；
[*]对于批量导入的场景，尽可能使用 PDML 并行实行的能力，这是Ocean Base 3.2 及之后的版本才具备的；
[*]根据负载情况调整网络线程数量，即net_thread_count，该配置项默以为 0，进程启动之后，根据当前机器 CPU 核数，自适应计算出本机必要的数量，公式为min( 6, cpu_core/8 )，根据现实的情况，手动调整预期值，进程重启生效。
https://img-blog.csdnimg.cn/direct/69fdca34e4ca4053b9fadd173b04f10a.png#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]