ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据库新技术【分布式数据库】 [打印本页]
作者: 万有斥力    时间: 2024-7-14 14:50
标题: 数据库新技术【分布式数据库】
第一章 概述

1.1 基本概念

1.1.1 分布式数据库

  分布式数据库——多个分布在计算机网络上的逻辑相干的数据库的集合。
  分布式数据库中，存放在差别网络节点上的数据库称作局部数据库，由局部数据库构成的逻辑团体称为全局数据库。全局数据库中的关系称为全局关系，局部数据库中的关系称为逻辑片段，或简称片段。
  全局关系与片段之间的映射关系称为分片。全局数据库与局部数据库之间的映射关系由一组分片模式来表现。一个逻辑片段可以保存在网络的一个节点上，也可以在网络的多个节点上保存多个副本，逻辑片段如何在网络上存放，称为分配。
1.1.2 数据管理的透明性


1.1.3 可靠性

  变乱是数据库上的同等的可靠的计算单元，变乱由一串具有原子性的数据库操纵构成。
  变乱具有ACID四个特性。

  变乱的性子在分布式数据库中必须得到包管。在分布式情况中保障变乱性子显然与集中式情况有很多差别。集中式数据库情况中若服务器节点失效，数据库系统将无法运转，而在分布式数据库情况中，在某些条件满足时，纵然某个服务器节点失效，数据库系统仍能运转。
1.1.4 分布式数据库与集中式数据库的区别

  集中式数据库中数据库存放在网络上的一个节点上，而分布式数据库数据库分布存放在网络上差别节点上。
1.2 体系结构

1.3 全局目录

  全局目录是分布式数据库中描述全局数据库与局部数据库关系的信息集合（分片模式和分配模式的集合）。只有分布式数据库有全局目录的标题。在分布式数据库中全局目录是目录的一部门。
  目录本身也是一个数据库。目录可以集中存放在一个节点上，也可以分为全局目录和局部目录，分布存放在网络的差别节点上。
  分布式数据库的设计技术同样实用于目录。分布式情况中，一个目录可以只在一个节点上存放一个拷贝，也可以在多个节点上存放多个拷贝。
1.4 关系代数

1.4.1 基操


1.4.2 关系表达式

  由关系代数运算经有限次复合而成的式子称为关系代数表达式。这种表达式的运算结果仍旧是一个关系。可以用关系代数表达式表示对数据库的查询和更新操纵。
例如：
数据库中有三个关系如下：
学生关系 Stu1(sid, sname, sage, sgender)，Stu2(sid, sname, sage, sgender)
选课关系 SC(sid, cid, grade)
课程关系 Cou(cid, cname, cteacher)
1.4.3 查询树

  关系表达式可进一步转换为查询树，查询树包罗关系操纵的先后次序，数据库系统可依据查询树控制查询操纵。
例如：
第二章 分布式数据库的设计

2.1 设计谋略

  当数据库的设计是从头开始时，自顶向下的设计是符合的。然而有时一些数据库已经存在，设计是为了集成已存在的一些数据库，这时必要自底向上的设计方法。
  自底向上的设计方法所涉及的必要集成的多个数据库常常是异构的。
2.2 分布设计的目标

2.3 水中分片设计

2.3.1 需求分析



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_1OC\; = \; "Montreal"                  P1​OC="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 = "aris’
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}

最后根据最小谓词集合M进行水中分片：

分片结果如下：

  其中                                   P                         R                         O                                   J                            2                                  ,                         P                         R                         O                                   J                            5                                       PROJ_2, PROJ_5                  PROJ2​,PROJ5​为空，那是由PROJ的当前值决定的，数据库是动态的，PROJ的值也是动态的。
2.3.4 诱导分片


  水中分片可以直接对一个关系搜集应用信息，设计分片，也可以从另一个关系诱导其分片方案。如图所示，关系间存在着link ,如L1,L2,L3。用关系代数的术语来讲，link表示一个关系的外键是另一个关系的主键。例如，L3表示ASG的外键JNO是PROJ的主键。
对于owner关系直接设计其水中分片，对于member关系从owner关系诱导出水中分片的设计。诱导分片的设计方法是半毗连。例如，关于ASG的水中分片可如下设计：

  有的member有多个owner，例如，EMP和PROJ都是ASG的owner。这种情况下，从差别的owner诱导出差别的水中分片方案。最终由设计者根据系统分配的需求选取一种。
2.3.5 正确性检查


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 使用矩阵



                                              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​)=               ​1000​0110​1101​0011​               ​
2.4.2 密切矩阵

  使用矩阵没有包罗应用调用查询的频率信息，不能足够反应出属性之间的密切程度。为此，进一步给出属性间的密切度界说:

其中，                                   a                         c                                   c                            l                                  (                                   q                            k                                  )                              acc_l(q_k)                  accl​(qk​)是应用 I 调用查询                                              q                            k                                       q_k                  qk​的频率。

计算方法：
  2.4.3 聚集的属性密切矩阵（理解即可，有点复杂）

  属性密切度矩阵显然让垂直分片设计工作前进了一步。但是仍旧无法直接给出垂直分片方案。如果密切的属性聚集在一起，设计垂直分片将会比较容易。聚集的属性密切度矩阵就是密切属性聚集在一起的属性密切度矩阵。聚集的属性密切度矩阵是由属性密切度矩阵经过行间交换以及对应的列间交换得到的。为通过算法得到如许的矩阵，界说全局密切度度量：







详细例子：

确定分割点


  对于n个属性，在CA中有n-1个分割点。每个分割点可以计算一个z值，选取z值最大的那个分割点对属性集合进行分别。如许的分别可迭代进行下去，直到给定的条件满足为止。
  假设AS1，AS2，.…. ，ASx是通过上述方法对一个关系进行属性集分别得到的k个属性子集。然后，对这些属性集进行如下处理:

2.4.5 正确性检查


2.5 分解树和重构树

  水中分片和垂直分片可以混合使用，如图所示：

  上图的树被称作分解树，描述了全局关系与逻辑片段之间的关系。全局关系可由逻辑片段通过重构树（下图所示）的操纵序列重构出来。

2.6 分配

每个逻辑片段可以保存在一个节点上，也可以在多个节点上保存多个副本。保存多个副本有利于进步查询的服从，但是却会增加更新的代价。分配是一个非常复杂的优化标题。可简朴表述如下:

第三章 分布式查询

3.1 查询分解

3.1.1 规范化

  查询条件可由谓词表达式表示，将查询的谓词表达式进行规范化处理有助于删除冗余操纵。规范化形式有合取规范化和析取规范化。
3.1.2 规范化规则


3.1.3 逻辑规则


3.1.4 冗余消除




3.1.5 查询树优化

  查询经前述处理后被写成一颗查询树，为减少计算量，需对查询树进行优化处理，优化处理所依据的规则如下。R,S,T表示差别的关
系，A= {A1,A2,……. ,An} 和 B={B1,B2,… ,Bn} 分别表示R, S的属性集。



  下页左图是一颗查询树，查询树优化的目标就是从等价的查询树中找出代价最小的那一颗。但是等价的查询树数量太多，无法比较所有的查询树代价。可行的办法就是接纳启发式的方法探求较优的查询树。一个启发式途径是：接纳下移一元操纵的方式优化查询树。

3.2 数据定位

3.2.1 合并重构树

  优化后的查询树的叶节点是全局关系，在分布式数据库中全局关系是虚拟的，如果操纵没有定位到逻辑片段，查询是无法进行的。将查询操纵落实到详细的逻辑片段上，这一工作称为数据定位。数据定位最简朴的做法是：用全局关系的重构树取代查询树中的全局关系，把重构树合并到查询树中来。
  但是，合并重构树是不够的。因为，对于一个详细的查询有的逻辑片段是不可能有结果，针对如许的逻辑片段进行计算完满是浪费。这里把查询树中不可能有结果的逻辑片段称为无用节点，删除无用节点是必要开展的下一步优化工作。
3.2.2 水中分片的裁剪



例如：
  EMP(ENO, ENAME, TITLE) 和 ASG 被如下分片:


对于查询1：

  该查询经初步优化和合并重构树后得到左图所示的查询树，根据规则1裁剪无用节点，得到右图所示的查询树。显然，右图的查询树与左图的查询树相比，可以省掉很多计算，却能够得到同样的结果。

对于查询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​​

上图的查询树可经过并与毗连转换，规则2的转换，变换为下图的查询树。下图的查询树计算量远低于上图。

3.2.3 垂直分片的裁剪


对于查询：

该查询经初步优化和合并重构树后得到下图所示的查询树。

上图的查询树经一元操纵幂等律、投影与毗连的交换、垂直分片的裁剪转换为下图的查询树。

3.2.4 诱导分片的裁剪


对于查询：

查询树如下：

优化【删除空选择】

优化【交换毗连与并】

优化【根据诱导分片，删除空子树】

3.2.5 混合分片的裁剪


查询树为：

优化后

3.3 全局优化

3.3.1 目标


这仍旧是一个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​



3.3.3 主要优化标题

  前面的优化处理已经把操纵落实到了逻辑片段上并尽可能下推了一元运算，这时的主要标题是选择毗连运算的园地和运算次序。



半毗连处理

3.3.4 主要算法

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)。根据调度冲突关系绘制调度冲突图，图中无环则为可串行化调度，否则不能判定为可串行化调度

  调度S本身是串行调度，判断为可串行化调度理所当然。调度S’是一个并发调度，用上述方法判断一下其是否为可串行化的。


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′​ 绘制冲突调度图，然后合并为一张图，若无环则为可串行化调度，否则不能作出此判断。

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为读锁。在对数据项进行操纵前要上锁，如果没有遇到不兼容的锁，上锁成功才气进行现实操纵，否则只有等拥有该锁的变乱释放该锁时才会有时机上锁成功。
例如：


  S是关于变乱T1,T2的一个基于锁的调度，其中                                   l                                   r                            i                                  (                         z                         )                              lr_i(z)                  lri​(z)表示释放变乱                                             T                            i                                       T_i                  Ti​对数据项z的锁。

4.3.2 两段锁协议（2PL）

  2PL指2-phase locking，意指把变乱的加锁息争锁过程分成两个阶段，加锁阶段息争锁阶段。加锁阶段只加锁不解锁，解锁阶段只解锁不加锁。


4.3.2.1 集中式数据库中2PL的可串行性

可串行化理论证明集中式数据库中2PL的可串行性
  假设存在一个环，则意味着存在一组变乱T1, T2, …, Tn，使得T1依赖于T2, T2依赖于T3，…，Tn依赖于T1。但是根据2PL协议的规则，变乱一旦进入紧缩阶段就不会再获取新锁，因此不可能形成如许的环，因为一旦一个变乱开始释放锁，它不会再阻塞其他变乱的锁请求。
  因此，冲突调度图中不可能存在环。
4.3.2.2 分布式数据库中2PL的可串行性

可串行化理论证明分布式数据库中2PL的可串行性

4.4 死锁标题

  接纳基于锁的调度，变乱因为等待锁而形成的一种相互等待关系称为死锁。
  在没有外在干预的情况下，陷入死锁的变乱将永久等待下去。无论是集中式数据库系统，照旧分布式数据库系统，只要接纳基于锁的并发控制，就有可能出现死锁的情况。
  对于接纳2PL的数据库系统，必须处理有可能出现的死锁标题。
4.4.1 死锁的检测和规复

（1）检测
  使用资源分配图，进行检测死锁。


简化：找到可以运行的进程，删去其所有边。
  死锁定理：当且仅当系统状态的资源分配图不可以完全简化，则系统处于死锁状态。
等待图（WFG）
  死锁的检测依赖WFG ( wait-for graph）, WFG中有环即为存在死锁。
  分布式情况中，分别为每个节点绘制WFG，然后把所有节点的IWFG合并为一个gWFG，gWFG中有环即为存在死锁。检测到死锁后，任选一个变乱，回滚该变乱。
   WFG 是进程及其等待的资源之间的依赖关系的图形表示。在WFG中，节点表示进程，资源表示为边。每个边缘都从正在等待资源的进程指向当前持有该资源的进程。

（2）规复
超时法
  为每个变乱设定一个实行时限。若某个变乱超过了实行时限，数据库系统回滚该变乱。该方法非常简朴，实现较容易。由于变乱的的实行时间通常较短，一样寻常来讲，该方法是可行的。
4.4.2 死锁的预防

4.4.3 死锁的避免

（1）系统安全状态
  所谓系统安全状态，是指系统能安照某种进程推进序列为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以完成。此时，该序列为安全序列。若系统无法找到一个安全序列，则系统处于不安全状态。
（2）银行家算法
（3）WFG
  在每次变乱加锁失败时，先假设该变乱转入等待状态，绘制WFG(IWFG，gWFG)，检测是否有死锁。如果有，回滚该变乱。否则让该变乱真正进入到等待状态。
第五章 分布式规复

5.1 概述


5.1.1 变乱模型


5.1.2 错误范例

5.1.3 稳固命据库与易失数据库

  对数据库的任何操纵都起首在内存中进行，然后才会写到外存。

5.1.4 稳固日志与易失日志

  写日志也是先在内存中完成写操纵，再写到外存上。

5.1.5 错误例子

  DBMS在0时候开始运行，在t时候发生系统故障。

  持久性要求稳固命据库中包罗T的全部操纵结果。当故障发生时，若T的操纵结果还未写入到稳固命据库中，则必要把这些操纵“Redo”到稳固命据库中。
  原子性要求稳固命据库中不包罗T2的任何操纵结果。当故障发生时，若T2的操纵结果已写入到稳固命据库中，则必要关于这些操纵对稳固命据库进行“Undo”操纵。
5.2 局部规复


  全局数据库由多个节点构成，每个节点支持一个局部数据库，局部数据库系统如上图所示。每个局部数据库系统负责本地的规复，同时要保持与其他局部数据库在规复上的同等性。
基本原理
  规复的依据是日志，DBMS对数据库作任何更新操纵前都先写日志。
5.2.1 变乱级与系统级错误规复


5.2.2 检查点

  每次都从头开始扫描日志，代价太大，在数据库系统运行一段时间后，基本上不可能如许做。
  数据库系统通过设置检查点解决该标题。检查点协议如下:
  其中，第2步有多种差别的做法，变乱同等检查点是多种做法之一。变乱同等检查点不允许系统接收新变乱，等所有活动变乱全部完成后，把易失数据库中所有的更新写入到稳固命据库中。
  变乱同等检查点使得日志中的end_checkpoint record对应着稳固命据库的一个同等的状态。数据库系统周期性地运行检查点协议。当遇到系统级错误时，从最新的那个end_checkpoint record开始扫描日志即可。
5.2.3 日志的完备性

  当发生系统级错误时，内存中的易失日志也丢失了。规复时只有稳固日志可用，对于规复而言，是否充实?
  只要公道安排将易失日志写为稳固日志的机遇，就能包管规复的正确性。如果每次把易失数据库中的更新写到稳固命据库前，以及在每次变乱结束前（含变乱提交完成和变乱回滚完成），都把易失日志中的内容全部写到稳固日志中，则可包管日志对规复是充实的。
例如：


  数据库系统根据稳固日志的内容对稳固命据库进行“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协议运行要点

5.4.3 运行状态变化图



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 比特币的诞生


6.1.2 比特币系统的特点

6.1.3 比特币来源

6.1.4 比特币交易


6.1.5 UTXO


6.1.6 账户余额


6.1.7 挖矿

  比特币系统是一个参与节点相互验证的公开记账系统，挖矿本质上是争夺某一区块的记账权。得到记账权的节点得到一定命量的比特币嘉奖，包括系统嘉奖和交易手续费两部门。
  系统嘉奖是比特币发行的本领，最初每得到一次记账权可得50个比特币的系统嘉奖，每隔4年减半。2140年前后发行完毕，最终整个系统有2100万。
  争夺记账权的方式是工作量证明算法（Proof of Work，PoW)，其含义是：把上一个区块的哈希值、本区块交易信息默克尔树根和一个未知的随机数拼在一起计算一个新的哈希值，要求这个哈希值以若干个0开头。开始算出符合要求的结果的节点得到记账权。
  每个节点收集这段时间内（约10分钟）的全网交易信息（部门或全部）进行查验确认打包成一个新区块，取得记账权（挖矿成功）后向所有的节点广播。其他节点收到广播后，对交易信息的正当性和记账权进行验证。如果通过则担当这个区块，并制止自己的挖矿举动，否则继续挖矿至收到一个可担当的广播或自己挖矿成功。
6.2 区块链原理

6.2.1 区块链内容和区块间的链


按区块存储交易纪录，下一个区块存储上一个区块的哈希值，形成链接的关系。
6.2.2 数字署名验证交易


  数字署名依赖于公钥和私钥的配对。每个人都有一对唯一的公钥和私钥。公钥用于验证署名，而私钥用于创建署名。当发送方使用私钥对信息进行署名时，接收方可以使用公钥来验证署名的有效性。如果署名有效，这意味着信息在传输过程中没有被篡改，而且确实来自拥有相应私钥的人。
  在区块链中，数字署名确保了交易的来源和不能否认性。每个交易都会被发送者的私钥署名，然后广播到网络中。一旦交易被确认并添加到区块链中，它就不能被撤销或更改。这确保了交易的不能否认性，为双方提供了安全保障。
6.2.3 默克尔树构造块内交易

参考来源：区块链中的Merkle树

  每条交易的哈希值就是一个叶子节点，从下往上将两个相邻叶子节点的组合哈希作为新的哈希值，新的哈希值成为树节点继续与相邻的树节点组合成新的哈希值。在重复一定次数后直到形成唯一的根节点。最后得到的Merkle根必要保存到区块头中，以便仅需通过区块头就可以对交易进行简朴支付验证，这一过程也成为SPV（Simplified Payment Verification）。
  对于Merkle树而言，并不必要知道整棵Merkle树中每个节点的值，可以通过节点的值、Merkle根的值和相干路径来快速验证该节点是否属于该Merkle树，从而快速验证该区块中是否包罗了某条交易。
  别的，时间戳用于标记区块次序。时间戳表示自格林威治时间 1970 年 1 月 1 日 0 时 0 分 0 秒到当前时候的总秒数，是一种完备且可验证的电子证据，能够为某一数据提供特定时间点的存在性证明。区块链根据时间戳的先后次序通过链式结构将一个个区块关联起来，因此篡改区块数据的难度以时间的指数倍增加，区块链越长篡改难度就越高，这也是确保区块链不可更改性的重要因素之一。
默克尔树作用：
6.2.4 共识机制

  区块链由参与节点共同维护，参与节点互不隶属，每个节点都保存区块链的一个副本。每个参与节点都收集验证迩来一段时间的交易信息，差别节点收集验证的交易信息可能差别等，也有可能有的节点被恶意操纵收集了非法交易。共识机制包管所有节点最终能够保存同等且正确的副本。
  比特币系统接纳工作量证明算法（PoW)，差别的区块链系统接纳的共识算法有所差别。PoW是一个数学难题，只能通过枚举法逐一实行，只有具备较强算力的节点才可能更快求解。开始得到解的节点得到当前区块的记账权，将当前区块广播给所有节点。其他节点验证被广播来的区块交易信息和记账权的正当性，只有确认正当才担当该区块，否则继续求解PoW，直至自己得到记帐权或收到一个正当的广播来的区块。
6.2.5 P2P


6.2.6 智能合约




6.2.7 区块链范例

6.3 区块链与加密货币的关系

6.4 区块链主要框架

6.5 区块链与数据库的比较

第七章 NewSQL数据库

7.1 基本概念

7.2 类别

7.2.1 New Architecture

7.2.2 Transparent Sharding Middleware

7.2.3 Database-as-a-Service

7.3 研究热门

7.3.1 内存存储

  传统数据库都是面向盘存储的，这在以前简直是必要的，内存的容量和费用都不允许把整个数据库存放在内存中。如今，内存的容量已经足够存储险些最大的OLTP数据库了，费用也不是标题了。内存存储将使得数据库操纵更加优化，数据库访问更加速捷。
  内存数据库并非新技术，NewSQL需处理的新标题是: NewSQL应有能力选出不常用的数据子集，将其移出到永久存储介质上，从而能够支持数据量大于内存容量的数据库。实现的途径通常就是一种内部的数据访问跟踪机制。
  内存存储的NewSQL DBMS有: H-Store、HyPer、MemSQL、 VoltDB。
7.3.2 数据分片


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)。
实行情况：

7.3.3.2 基于时间印的MVCC（改进——解决级联依赖标题）

标题：
实行情况：

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​)。
实行情况：

标题：
7.3.4 辅助索引


7.3.5 复制


7.3.6 故障规复


7.4 将来的趋势

第八章 NoSQL数据库（理解即可）

8.1 基本概念


8.2 GFS

8.2.1 Bigtable的存储基础

  Bigtable的一个表往往必要占用集群中多台服务器的存储空间。GFS ( Google File System）是一个分布式文件系统，统一管理集群中浩繁服务器的存储空间。Bigtable 以GFS为存储基础，无需处理存储位置与物理服务器间的关系。
8.2.2 架构


8.2.3 特点


8.2.4 容错机制


8.3 Chubby

8.3.1 锁服务


8.3.2 Chubby单元


  一个Google数据中央仅运行一个Chubby单元，一个Chubby单元一样寻常由5个配置完全相同的服务器构成，向客户端提供高度可靠的服务。Chubby单元的多个服务器维持同等的副本，恣意一个服务器都可以向客户端提供服务，提供服务的过程中宕机，Chubby单元可以自动选择另一服务器接替其工作。
8.3.3 Chubby服务器


  最底层是一个容错日志，副本之间通过Paxos协议进行通信保障数据同等性，中间层是一个容错的数据库，Chubby构建在这个数据库之上，所有的数据都存储在这个数据库中。Chubby是一个存储大量小文件的文件系统，每个文件代表一个锁，用户通过打开或关闭文件得到或释放锁，通过读取文件获取相干信息。
8.3.4 Chubby通信协议


  初始时，客户端向主服务器发出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 特点


8.4.2 数据模型


8.4.3 系统架构


  Bigtable在Google WorkQueue、GFS和Chubby三个组件基础上构建。Google WorkQueue处理分布式队列分组和任务调度，Google未公布其细节。GFS用来存储数据和日志。Chubby的主要作用包括：1.选取并包管同一时间内只有一个主服务器；2.索引子表位置信息；3.保存Bigtable 模式信息及访问控制列表。
  Bigtable由客户端步调库、一个主服务器和多个子表服务器三部门构成。客户端访问Bigtable服务与主服务器的交互少少，客户端通过Open()操纵从Chubby那里取得一个锁后直接与子表服务器交互。
  主服务器负责元数据操纵和子表服务器之间的负载调度。一个表被分别为多个子表（相称于水中分片)，子表巨细一样寻常在100M至200M之间，运行过程中子表巨细变化后，系统兵动分割或合并子表。一个子表服务器通常保存多个子表。
8.4.4 主服务器


8.4.5 子表结构



8.4.6 元数据表


  所有的子表地址存储在元数据表中，元数据表由一个个元数据子表构成，其结构与B＋树类似。Chubby中的一个文件存储根子表信息。根子表是元数据表的第一条纪录，也保存其他元数据子表的地址。
8.4.7 读写操纵



第九章 课程设计

9.1 需求

  设计文档包括表及其结构、表间的关联、表的分布设计、<key, value>存储及其与表之间的联系、关键变乱的描述、主要的查询流程。
9.2 设计

9.2.0 类图

9.2.1 表及其结构

9.2.2 表间的关联（ER图）




9.2.3 表的分布设计

9.2.4 <key, value>存储及其与表之间的联系

9.2.5 关键变乱的描述

9.2.5.1 优惠卷到期自动删除（活动结束自动删除也是一样）

方案一：数据库触发器
  如果数据库支持触发器（如MySQL、PostgreSQL），可以创建一个触发器，天天检查并删除过期的优惠券（活动）。
  1. CREATE TRIGGER delete_expired_coupons
  2. AFTER INSERT ON _coupons
  3. FOR EACH ROW
  4. BEGIN
  5.     DELETE FROM _coupons
  6.     WHERE _deadline < CURDATE();
  7. END;
复制代码
  1. CREATE TRIGGER delete_expired_activity
  2. AFTER INSERT ON _activity
  3. FOR EACH ROW
  4. BEGIN
  5.     DELETE FROM _activity
  6.     WHERE _deadline < CURDATE();
  7. END;
复制代码
方案二：定时任务调度
  使用Cron或Quartz等定时任务调度器，通过定期实行脚原来删除过期的优惠券（活动）。
9.2.5.2 充值（跨数据库的同等性提交）

9.2.5.3 兑现（跨数据库的同等性提交）

9.2.5.4 购买优惠卷（跨数据库的同等性提交）

9.2.5.5 开锁（含判断是否有钱）

9.2.5.6 上锁（含付费）

9.2.6 主要的查询流程

9.2.6.1 查询可用单车流程

9.2.6.2 查询行程信息流程

9.2.6.3 查询行程轨迹流程

9.2.6.4 查询可使用的优惠券流程

9.2.6.5 查询正在进行的活动流程

9.2.6.6 查询订单流程

9.2.6.7 查询余额流程

9.2.6.8 查询参与活动的用户信息流程

9.2.6.9 查询需维护的单车位置流程

第十章 OceanBase 数据库分布式变乱的实现机制

10.1 概述（总结）

  我们详细介绍了 OceanBase 数据库的分布式变乱实现机制，焦点是通过优化的两阶段提交协议（2PC）来确保分布式变乱的同等性和可靠性。并解释了分布式变乱的基本概念、ACID特性（原子性、同等性、隔离性、持久性）、CAP理论（同等性、可用性、分区容错性）和 BASE理论（基本可用、软状态、最终同等性）。
  在传统 2PC 的基础上，OceanBase 进行了耽误优化，通过异步提交协调者日志和提前决策提交点来减少提交耽误，同时每个参与者需持久化参与者列表以便异通例复。OceanBase数据库的分布式变乱实现的关键技术点还包括全局同等性快照技术，通过快照隔离级别和多版本并发控制 (MVCC) 提供同等的版本号，确保跨节点变乱操纵的同等性；锁机制接纳行级锁粒度，多版本两阶段锁和锁的存储在行上，减少内存开销并进步并发处理能力。
  通过这些技术和优化，OceanBase 确保了分布式情况下的数据同等性和变乱处理的高效性，适应各种复杂的分布式应用场景。
10.2 分布式变乱的基本概念

10.2.1 基本概念

  分布式变乱就是指变乱的参与者、支持变乱的服务器、资源服务器以及变乱管理器分别位于差别的分布式系统的差别节点之上。以上是百度百科的解释，简朴的说，就是一次大的操纵由差别的小操纵构成，这些小的操纵分布在差别的服务器上，且属于差别的应用，分布式变乱必要包管这些小操纵要么全部成功，要么全部失败。本质上来说，分布式变乱就是为了包管差别数据库的数据同等性。
  分布式变乱主要有两种场景，一种仅仅是服务内操纵涉及到对多个数据库资源的访问。当一个服务操纵访问差别的数据库资源，又希望对它们的访问具有变乱特性时，就必要接纳分布式变乱来协调所有的变乱参与者。如下图：

  上面介绍的分布式变乱应用场景管一个服务操纵会访问多个数据库资源，但是究竟整个变乱照旧控制在单一服务的内部。如果一个服务操纵必要调用另外一个服务，这时的变乱就必要跨越多个服务了。在这种情况下，起始于某个服务的变乱在调用另外一个服务的时候，必要以某种机制流转到另外一个服务，从而使被调用的服务访问的资源也自动加入到该变乱当中来。下图反映了如许一个跨越多个服务的分布式变乱：

  如果将上面这两种场景(一个服务可以调用多个数据库资源，也可以调用其他服务)结合在一起，对此进行延伸，整个分布式变乱的参与者将会构成如下图所示的树形拓扑结构。在一个跨服务的分布式变乱中，变乱的发起者和提交均系同一个，它可以是整个调用的客户端，也可以是客户端开始调用的那个服务。

10.2.2 ACID特性

  分布式变乱页需具备变乱的基本属性：原子性、同等性、隔离性、持久性。这四个属性通常称为ACID特性。

10.2.3 CAP理论

  CAP原则又称CAP定理，指的是在一个分布式系统中，同等性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP 原则指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。

  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）是常用的分布式变乱解决方案，即将变乱的提交过程分为准备阶段和提交阶段两个阶段来进行处理。
参与角色

第一阶段

第二阶段


长处：状态简朴，只依赖协调者状态即可确认和推进整个变乱状态
缺点：协调者写日志，commit延时高
10.3.2 OceanBase的2PC

  用户能够感知到的最显着的一点，就是变乱提交的耽误。OceanBase从两方面入手优化。一方面，协调者的 Prepare 日志可以异步提交，参与者列表可以由所有参与者携带以解除对其的依赖；另一方面，两阶段提交的提交点完满是可以提前的，一个变乱是否提交除了可以由单个协调者来决定，还可以由所有参与者分布式地决定，即提交点可以提前为所有参与者将 Prepare 日志同步成功来决定。
  基于上述两个思绪，OceanBase进行了下列改进：
  OceanBase 还对两阶段提交协议的时延进行了优化，将变乱提交回应客户端的机遇提前到 Prepare 阶段完成后（标准两阶段提交协议中为 Commit 阶段完成后）。

  在上图中（绿色部门表示写日志的动作），左侧为标准两阶段提交协议，用户感知到的提交时延是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则包管 所有的版本号单调向前而且和真实世界的时间次序保持同等。

  有了如许全局同等的版本号，OceanBase就能根据版本号对全局（跨机器）范围内的数据做同等性快照，因此我们把这个技术命名为“全局同等性快照”。有了全局同等性快照技术，就能实现全局范围内同等的快照隔离级别和多版本并发控制，而不用担心发生外部同等性被破坏的情况。
10.4.2 锁机制

  OceanBase 数据库的锁机制使用了以数据举动级别的锁粒度。同一行差别列之间的修改会导致同一把锁上的互斥；而差别行的修改是差别的两把锁，因此是无关的。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 上的多版本进行合并来得到所必要的版本数据。

  单机变乱故障规复接纳了 Undo/Redo 日志的思绪实现。变乱在写入时会天生 Redo 日志，借助 MVCC 机制的旧版本数据作为 Undo 信息，实现了 Steal & No-Force 的数据落盘计谋。在变乱宕机规复过程中，通过 Redo日志进行重做规复出已提交未落盘的变乱，并通过规复保存的旧版本数据来回滚已经落盘的未提交变乱修改。
10.5.3 分布式变乱故障处理

  当变乱操纵多个数据分片时，OceanBase 通过两阶段提交来包管分布式变乱的原子性。

  如上图所示，当分布式变乱提交时，会选择其中的一个数据分片作为协调者在所有数据分片上实行两阶段提交协议。还记得前文提到过的协调者宕机标题么？在 OceanBase 中，由于所有数据分片都是通过 Paxos 复制日志实现多副本高可用的，当主副本发生宕机后，会由同一数据分片的备副本转换为新的主副本继续提供服务，以是可以以为在 OceanBase 中，参与者和协调者都是包管高可用不宕机的（多数派存活），绕开了协调者宕机的标题。
  在参与者高可用的实现条件下，OceanBase 对协调者进行了“无状态”的优化。在标准的两阶段提交中，协调者要通过纪录日志的方法持久化自己的状态，否则如果协调者和参与者同时宕机，协调者规复后可能会导致变乱提交状态差别等。但是如果我们以为参与者不会宕机，那么协调者并不必要写日志纪录自己的状态。

  上图是两阶段提交协议协调者的状态机，在协调者不写日志的条件下，协调者如果发生切主或宕机规复，它并不知道自己之前的状态是 Abort 照旧 Commit。那么，协调者可以通过询问参与者来规复自己的状态，因为参与者是高可用的，以是一定可以规复出整个分布式变乱的状态。
10.6 性能优化

10.6.1 分布式变乱范例的优化

  对于分布式变乱的优化，差别范例的变乱提交耗时差别，性能调优应尽量低沉跨机分布式变乱的比例。变乱模型可以从以下几个方面入手：业务团体逻辑，细化到详细的变乱和了解多表、单表变乱的比例以及各类 SQL 的实行频率。
  SQL 的实行计分别为四种：
  对于变乱的性能而言，优先使用单机变乱，其次才是分布式变乱；根据实行计划的范例统计信息，可以大致估算出分布式变乱的比例，进而为调优提供数据支持。相干的 SQL 语句如图所示。

  其中，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。
10.6.2 分布式变乱提交的优化

  对于单表或多表的单机变乱，OceanBase 数据库 V4.0 版本由于做了单日志流架构的调整，只要变乱涉及的日志流 Leader 在同一个机器，默认会走单日志流变乱。这种变乱模型性能最高，因此不必要任何配置项的调整。而对于跨机变乱的处理，主要有两个标题，尽可能使用多机能力和OBServer 流量负载平衡。详细本领有


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4