Jeffly

1. Lehman–Yao B*-Trees

Lehman–Yao构造了一个供并发进程使用的数据结构。该数据结构是 Wedekind提出的 B*-树的一个简单变体（其基础是 Bayer 和 McCreight定义的 B 树）。
Lehman–Yao B*-树定义如下。

1.1 定义

1. Each path from the root to any leaf has the same length, h.
2. 内部节点（非 root、非叶子）至少要有 k + 1 个孩子（sons）。 (k is a tree parameter; 2k is the maximum number of elements in a node, neglecting the “high key,” which is explained below.)
3. root要么是页节点要么至少有两个孩子（sons）
4. 每个node最多有2k+1个孩子（sons）
5. Lehman–Yao B-tree中的所有数据的键（key）都存储在叶子节点中，叶子节点还包含指向数据库记录的指针（每一条记录都与一个 key 对应）。
   非叶子节点包含指针，以及用于沿着这些指针继续查找的 key 值（b+ tree）。

B*-树的节点看起来如图 1 所示。Ki 表示 key 域的实例Pi 表示指针。Pi 可以指向其他节点，或者——在叶子节点的情况下——指向与存储在叶子节点中的 key 值关联的记录。这种安排使得在我们的模型中，叶子节点和非叶子节点的结构基本相同。M 是一个标记，用于指示该节点是叶子节点，它占据了非叶子节点中第一个指针的位置。图 2 显示了一个 B*-树示例。

1.2 Sequencing（顺序规则）

1. 每个节点内部，key 按升序排列。
2. 在 B*-tree 中，有时会在非叶子节点追加一个额外的值，称为 “high key”（见图 3）。
3. 在任意节点 N 中，每个指针 Pi 指向一个子树 Ti（Pi 指向的节点为 Ti 的根）。Ti 中存储的 key 值被 Pi 左右的两个 key （Ki 和 Ki+1）界定。 这就给非叶子节点提供了一组 (pointer, value) 对

   1	key(Ti) ∈ (Ki-1, Ki]

   其中，k0 = -∞（在 N 中物理上不存在），K2k+1 = high key（如果存在），high key 提供了 Pi 指向的子树的上界，因此它也是以 N 为根的子树中所有值的上界。
   叶子节点 定义类似（见图 3）：Ki = 叶子中存储的 key；Pi = 指向对应记录的指针

1.3 Insertion Rule(插入规则)

1. 如果一个叶子节点的条目（entries）少于 2k 个，那么一个新的条目以及指向其对应记录的指针可以直接插入到该节点中。
2. 如果一个叶子节点已有 2k 个条目，则插入新的条目时，需要通过将该节点分裂为两个节点来进行，每个新节点包含原节点一半的条目。新的条目会被插入到这两个节点中的一个（在合适的位置）。由于其中一个节点是新创建的，因此必须在原单节点的父节点中插入一个新的指针。这个新的指针指向新节点；新的键值是对应于原节点拆分后左半部分的键值。此外，需要为这两个新节点分别设置高键（high key）。图 4 展示了一个节点分裂的示例。
3. 对非叶子节点的插入操作与叶子节点完全相同，只是指针指向的是子节点，而不是数据记录。

一个节点（按照上面给出的规则），如果条目数少于 2k，则称其为“安全节点”（就插入操作而言），因为插入可以通过对该节点的简单操作完成。同样，如果一个节点有 2k 个条目，则称其为“非安全节点”，因为必须进行分裂操作。对节点的删除操作也有类似的定义：如果删除可以在节点内完成而不会影响其他节点，则该节点称为“安全节点”；反之，如果删除会影响其他节点，则称为“非安全节点”。也就是说，如果节点的条目数多于 k + 1，则安全；如果恰好有 k + 1 条目，则非安全。

一个简单的例子就足以说明，对 B*-树进行并发操作的简单做法是错误的。
考虑图 5a 所示的 B*-树片段。假设有两个进程：一个搜索值 15，另一个插入值 9。插入操作应当导致树结构修改为图 5b 所示的样子。现在考虑下面这一系列操作：

问题在于，搜索操作首先返回指向 y 的指针（从 X 获得），然后才读取包含 y 的页面。在这两个操作之间，插入操作已经修改了树的结构。

2. Previous Approaches

前面的例子表明，对并发 B 树问题采取简单做法是行不通的：如果不防范并发操作带来的潜在问题，多个进程的操作可能导致结果不正确。为了更好地理解这个问题，我们在此简要概述一些已经提出的其他方法和解决方案。

针对并发 B 树问题的第一个解决方案是由 Samadi 提出的.他的做法是最直接的一种，并且是最早考虑并发问题的方法。该方案简单地使用信号量来独占锁定任何一次树结构修改可能经过的整条路径。这实际上锁定了受影响的最高节点所在的整个子树

Bayer 和 Schkolnick 提出的算法对 Samadi 的方法进行了实质性的改进。他们提出了一种用于 B*-树并发操作的方案；该方案包含一些参数，可以根据所需的并发程度和类型进行设置。
首先，修改操作会对树的上部节点加写者排他锁（writer-exclusion locks）（这种锁只排斥其他写者，而不会阻止读者）。
当需要真正进行修改操作时，会施加独占锁（exclusive locks），大多应用在树的下部节点。
这种对独占锁的稀疏使用提高了算法的并发性能。

Miller 和 Snyder [12] 研究了一种方案，该方案锁定树中一个有界大小的区域。该算法使用先导锁（pioneer locks）和跟随锁（follower locks），以防止其他进程进入当前进程正在修改的树区域。被锁定的区域沿树向上移动，同时执行相应的修改操作.在使用队列管理的锁策略的帮助下，沿树向下移动的读者可以“越过”被锁定的区域，从而避免死锁。这种算法与本文提出的算法的权衡在于：本文的算法锁定树的区域明显更小，但需要对普通的 B-tree 或 B*-tree 结构进行稍微的修改，以便支持并发。

Ellis [6] 提出了一种针对 2-3 树的并发解决方案。文中采用了几种方法以提高并发能力，并且（据称）这些方法可以很容易地推广到 B 树。
该论文应用了两种思想：一是在相反方向上对一组数据进行读写（由 Lamport [11] 提出）；二是允许数据结构暂时出现轻微退化，同时允许进程不必立即完成操作，可以将工作推迟到更合适的时间再执行。

Guibas 和 Sedgewick [6a] 提出了一种针对平衡树的统一“双色框架”（dichromatic framework）。这是一种研究平衡树的简化方法：它将所有平衡树方案归约为“带颜色”的二叉树的特例，并具有概念上的清晰性。这些作者利用他们的框架研究一种自上而下的并发锁定方案，其中包括在沿树向下访问时对“几乎满的”节点进行分裂。我们预计，他们的方案将锁定比我们的方案更多的节点（降低并发性），并且需要略多的存储空间。

另一种针对 B 树并发操作的方法目前正在由 Kwong 和 Wood [10] 进行研究。

3. Blink-Tree for Concurrency

B-link 树是一种在 B*-树基础上修改而成的结构，它在每个节点中增加了一个“链接（link）”指针字段（记作 P2k+1 ——见图 6）。
（B-link-tree 的发音是 “Blink-tree”。）

这个链接指针指向当前节点所在层的下一个节点；只有在该层最右侧的节点中，这个链接指针才是空指针（null）。这样的链接指针定义是自洽的，因为所有叶子节点都位于树的同一层。

因此，在 B-link 树中，同一层的所有节点都被连接成一条链表，如图 7 所示。

Link 指针的目的，是提供一种到达某个节点的额外途径。
当一个节点因为数据溢出而被分裂时，原来的单一节点会被两个新的节点取代。

在分裂后：

• 第一个新节点的 link 指针指向第二个新节点；

• 第二个新节点的 link 指针则保存了原来旧节点的 link 指针内容。

通常情况下，第一个新节点会占用旧节点在磁盘上的同一个物理页面。

设计这个方案的意图是：
因为这两个新节点被 link 指针连接起来，在父节点中的正确指针尚未更新之前，它们在功能上仍然等价于原来的那个单一节点。
Blink-tree 的精确查找与插入算法将在接下来的两个章节中给出。

对于树中的任意一个节点（处于某一层且不是该层的第一个节点），通常会有两种指针指向它：

来自其父节点的“子指针”（son pointer），以及

来自其左兄弟节点的 link 指针。

当一个节点被插入到树中时，这两个指针之中必定有一个会先被创建。
我们规定：在这两个指针中，link 指针必须最先存在。
也就是说，一个节点在树中出现时，可以暂时没有父节点的指针指向它，但必须已经有一个左兄弟指向它的 link 指针。

这种结构依然被定义为一个合法的树结构，因为新的“右兄弟”节点可以通过“左兄弟”到达。（这两个兄弟节点在功能上仍然可以视作一个节点。）

当然，为了保证良好的查找效率，来自父节点的指针必须尽快补上。

Link 指针的优势在于：它会在节点发生分裂时同步建立。
因此，即使针对新节点的常规树指针尚未全部更新完毕，link 指针仍可作为一种“临时修补”机制，使并发操作保持正确性。

当查找键大于节点的最大键值（由 high key 标识）时，这表明树结构已经发生变化，此时应通过 link 指针继续访问右兄弟节点。
虽然这种方式略低效一些（因为需要额外一次磁盘读取来跟随 link 指针），但它仍然是到达目标叶子节点的正确路径。

由于节点分裂本身属于例外情况，link 指针的实际使用频率应该非常低。

Blink-tree 结构的另一个优点是：在对树进行顺序遍历时，link 指针可以用于快速按“按层次优先（level-major）”的顺序检索树中的所有节点，或者，例如，只检索所有叶子节点。

4. THE SEARCH ALGORITHM

4.1 算法示意图（Algorithm Sketch）

要在树中查找一个值 v，搜索过程从根节点开始，沿树向下比较 v 与每个节点中的键值。在每个节点中，比较键值后，决定沿节点中哪条现有指针继续向下搜索，指示应沿该指针前往下一层节点，或直接到达叶子（记录）节点。

如果搜索过程中检查某个节点时，发现该节点中的最大值小于 v，则可以推断出当前节点发生了一些变化，而这些变化在搜索检查其父节点时尚未反映到父节点中。

这意味着当前节点已经被分裂成两个（或更多）新的节点。
此时，搜索必须纠正其在树中的位置错误：不再按照普通的父节点子指针（son pointer）前进，而是沿新分裂节点的 link 指针继续搜索。

搜索过程最终会到达 v 应该所在的叶子节点（如果 v 存在的话）。此时，该节点要么包含 v，要么不包含 v 且节点中的最大值大于 v。
因此，该算法能够正确地判断 v 是否存在于树中。

4.2 算法

搜索（Search）
该过程用于在树中查找一个值 𝑣。如果 𝑣 存在于树中，过程结束时：𝐴包含包含 𝑣 的节点 𝑡
包含指向与 𝑣 关联的记录的指针；如果 𝑣 不存在于树中，𝐴 将包含 𝑣 如果存在的话应该所在的节点。

1
2
3
4
5
6
7
8
9

Search(v):
    ...
    if v exists:
        A = 节点页 containing v
        t = 指向 v 的记录
    else:
        A = 节点页 where v would be
        t = null

下文算法中使用的符号在第 2 节中定义。
在此过程中，我们使用了一个辅助操作 scannode，其定义如下：

x <- scannode(u, A) denotes the operation of examining the tree node in memory block A for value u and returning the appropriate pointer from A (into x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

procedure search(u)
current <- root;
A <- get(current);
while current is not a leaf do 
begin
  current <- scannode(u, A);
  A <- get(current) 
end;

while t <- scannode(u, A) = link ptr of A do
begin
  current + t ;
  A <- get(current)
end;

if v is in A then done “success” else done “failure”

请注意，这种搜索过程非常简单，其行为与非并发搜索完全相同，将 link 指针与其他指针同等对待。

还要注意，该过程不进行任何形式的加锁。
这与传统的数据库搜索算法形成对比（例如 Bayer 和 Schkolnick [3] 所述），在那些算法中，所有搜索操作都会对它们访问的节点进行读锁。

5. THE INSERTION ALGORITHM

5.1 算法示意图（Algorithm Sketch）

要在树中插入一个值 𝑢 我们执行的操作与前面描述的搜索过程类似。从根节点开始，沿树向下扫描，直到到达应该包含 𝑢 的叶子节点。同时，我们在下降过程中记录每一层中被访问过的最右节点。沿树的下降过程实际上就是在搜索 𝑢 的正确插入位置（比如称该节点为节点 𝑎 ）。

将值 u 插入叶子节点时，可能需要对该节点进行分裂（当节点不安全时）。
在这种情况下，我们对节点进行分裂（如图 8 所示），用两个新节点 a’（a 的新版本，写回同一磁盘页面）和 b’ 替换原来的节点 a。节点 a’ 和 b’ 的内容与原节点 a 相同，只是增加了值 u。随后，我们沿着先前记录的搜索路径回溯树的上层，在叶子节点的父节点中插入新节点 b’ 的条目以及 a’ 的新 high key。

死锁的避免是由锁定方案的良序性（well-ordering）所保证的，如下所示。
需要注意的是，当我们沿树向上回溯时，由于节点可能被分裂，我们必须插入新指针的节点可能并不是下降过程中经过的那个节点。换句话说，我们在下降过程中使用的旧节点可能已经被分裂；此时，正确的插入位置就在原预期插入位置右侧的某个节点。我们通过 link 指针 来找到这个节点。

5.2 算法

在下文的算法中，有些过程被视为原语操作（就像上文的 scannode 一样），因为它们容易实现，并且其具体操作对本文的目的而言并不重要。例如：

A <- node.insert (A, w, v) denotes the operation of inserting the pointer w and the value v into the node contained in A.
u <- allocate(2 newpage for B) denotes the operation of allocating a new page on the disk. The node contained in B will be written onto this page, using the pointer u.
“A, B <- rearrange old A, adding ..” denotes the operation of splitting A into two nodes, A and B, in core.

插入（Insert）。该算法负责将一个值 v（以及其关联的记录）插入到树中。当算法结束时，值 v 已成功插入到树中，并且在必要的情况下，算法会在从叶子向上回溯的过程中对相应的节点进行分裂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

procedure insert(v)
initialize stack;
current <- root;
A <- get(current);
while current is not a leaf do
begin
  t <-  current;
  current <- scannode( v, A);
  if new current was not link pointer in A then
    push(t);
  A <- get(current);
end;
lock(current);
A <- get(current);
move.right;
if v is in A then stop “v already exists in tree”;
w <- pointer to pages allocated for record associated with v; 
Doinsertion:
if A is safe then
begin
  A <-  node.insert(A, w, v); 
  put(A, current); 
  unLock(current);
end else begin
  u <- allocate(1 new page for B);
  A, B <- rearrange old A, adding v and w, to make 2 nodes,
    where (link ptr of A, link ptr of B) <- (u, link ptr of old A);
  y <- max value stored in new A;
  put(B, u)
  put(A, current); 
  oldnode <- current;
  v <- Y;
  w <- u;
  current <- pop(stack); 
  lock(current);
  A <- get(current); 
  move.right; 
  unlock(oldnode);
  goto Doinsertion
end

Move.right. This procedure, which is called by insert, follows link pointers at a given level, if necessary.

1
2
3
4
5
6
7
8

procedure move.right
while t <- scannode(u, A) is a link pointer of A do
begin
  lock(t); 
  unlock(current); 
  current <- t;
A <- get(current); 
end

需要注意的是，该过程在向上回溯树时是 逐层进行的。此外，同时最多只会锁定三个节点，而这种情况发生的频率相对较低：仅在插入分裂节点的指针时，需要沿 link 指针向右移动 的情况下才会出现。此时，被锁定的节点包括：

• 分裂节点的原始左半部分

• 分裂节点上一层的两个节点

在插入沿右链移动的过程中需要锁定它们。

与传统方法相比（即只有在确定节点为安全节点时才释放锁），这种做法在 锁粒度和并发性能上都有显著改进。

该算法的正确性依赖于以下事实：树结构的任何变化（即任何节点的分裂）都会伴随一个 link 指针。节点分裂时，条目总是被移动到树的右侧，在右侧的新节点可以通过 link 指针被访问到，从而保证树的结构在并发操作下仍然可达且正确。

具体来说，对于任何层级的一个对象（与某个值相关联），我们总能大致知道它的正确插入位置，即我们在该层搜索时经过的“记录节点”。如果该对象的正确插入位置发生了移动，这种移动方式是可预知的：也就是节点分裂向右，留下的 link 指针使得搜索或插入操作仍然能够找到它。因此，从旧的“预期”插入位置开始，始终可以访问到对象的正确插入位置。

6 CORRECTNESS PROOF

为了证明系统的正确性，我们需要证明以下两个命题对每个进程都成立：

1. 该进程不会发生死锁（定理 1）；
2. 当进程终止时，它已经正确地完成了所需的操作。
   更具体地说：

• 所有磁盘操作都保持树结构的正确性（定理 2）
• 除正在进行修改的进程之外，所有其他进程看到的树都是一致的（交互定理 3）。

6.1 无死锁性（Freedom from Deadlock ）

首先，我们开始证明系统不存在死锁。
为此，我们对节点施加一个顺序：跨层从下到上、同层从左到右。下面的引理（Lemma：一种 辅助性结论，用于证明后续更大、更重要的定理（Theorem））对这一点进行了严格定义。
引理 1 插入操作对节点加锁遵循一个良序（well-ordering：严格定义的、有序的顺序关系）关系
证明 考虑在树的节点集合上定义如下顺序关系（<）：

1. 在任意时刻 t，如果两个节点 a 和 b 与树根的距离不同（不在同一层级），那么当且仅当 b 离树根更近（处于更高层级）时，我们称 a < b。
2. 如果 a 和 b 与树根的距离相同（在同一层级），那么当且仅当 b 能通过从 a 开始沿着一条或多条链接指针到达（即 b 在 a 的右侧）时，我们称 a < b。

通过检查插入算法我们可以看到：如果在时间 t₀ 时 a < b，那么在所有 t > t₀ 的时间点都仍然有 a < b。因为节点创建过程只是把一个节点 x 分裂成两个新节点 x′ 和 x″，并且满足 x′ < x″，而且

1

y<x⟺y<x′

和

1

x<y⟺x′′<y

因此，这些节点形成了一个良序关系，插入者按照良序对节点加锁。一旦在某个节点上加锁，它不会再对该节点之下的任何节点加锁，也不会对同一层中位于左侧的节点加锁。
因此，插入者按照给定的良序对节点加锁。证毕。
由于插入者是唯一对节点加锁的过程，我们可以立即得到以下定理。

定理 1：无死锁性。 给定的系统不会产生死锁。

6.2 树结构修改的正确性

为了确保树结构的完整性，我们必须检查所有修改树结构的操作。首先，需要注意的是，树结构的修改只能通过 “put” 操作 来完成。插入过程中算法中有三个地方会执行 put 操作：

1. 对安全节点重写时使用 “put(A, current)”。
2. 对不安全节点的最右节点使用 “put(B, u)”。通过该操作，我们写入由节点分裂形成的两个新节点中的第二个节点。
3. 对不安全节点使用 “put(A, current)”。这里写入的是两个新节点中的第一个（最左节点）。实际上，我们重写了树中已存在的页面（节点），并修改该页面的链接指针，使其指向由 “put(B, …)” 写入的新节点。

注意，在算法中（针对不安全节点），“put(B, u)” 紧接在 “put(A, current)” 之前执行。我们将在下面的引理中证明，这种顺序实际上将两个 put 操作简化为本质上的一次操作。

引理 2. 操作 ‘put(B, u); put(A, current)’ 相当于对树结构的一次修改。
证明. 假设这两个操作分别写入节点 b 和 a。在执行 “put(B, u)” 时，没有其他节点指向正在写入的节点 b，因此该 put 操作对树结构没有影响。现在，当执行 “put(A, current)” 时，该操作修改了 current 指向的节点（节点 a）。修改内容包括将节点 a 的链接指针指向 b。此时，b 已经存在，并且 b 的链接指针指向与 a 的旧版本相同的节点。这样就实现了同时修改 a 并将 b 引入树结构。证毕。

定理 2. 所有 put 操作都能正确地修改树结构。
证明
case 1： 对安全节点执行 “put(A, current)”。该操作只修改树中一个已加锁的节点，因此树的正确性得到保持。
case 2： 对不安全节点执行 “put(B, u)”。该操作不会改变树结构。
case 3： 对不安全节点执行 “put(A, current)”。根据引理，该操作既修改了当前节点（比如 a），又将另一个节点（比如 b，通过 “put(B, u)” 写入）引入树结构。与情况 1 类似，节点 a 在执行 “put(A, current)” 时已加锁。本例的区别在于该节点是不安全的，需要分裂。但根据引理，我们可以通过一次操作完成，保持树结构的正确性。证毕

6.3 正确的交互

我们还需要证明，无论插入过程对树进行何种修改，其他进程仍能正确操作。
定理 3：交互定理。 插入过程的操作不会破坏其他进程操作的正确性。

为了证明该定理，我们首先考虑搜索过程与插入操作的交互情况，然后考虑两个插入过程的交互情况。一般来说，为了证明插入者的操作不会破坏其他进程的正确性，我们需要考虑该进程相对于该操作的行为。在所有情况下，该操作都是原子的。

假设插入者在时间 t0 对节点 a 执行一次 “put” 操作。考虑另一个进程在时间 t′从磁盘读取节点 a 的情况。由于假设 “get” 和 “put” 操作是不可分割的，要么 t′<t0​，要么 t0​ < t′。我们将在下面的引理中证明，后一种情况不会产生问题。

引理 3
如果进程 𝑃 在某个时间 𝑡′ > 𝑡0 读取节点 𝑎，其中 𝑡0 是插入进程 I 修改节点 𝑎 的时间，那么这一修改不会影响进程 𝑃 的正确性。

证明. 考虑进程 P 通过节点 a 的路径。进程 P 在到达节点 a 之前所经过的路径不会被插入进程 I 改变。此外，根据上面的定理 2，进程 I 对树结构所做的任何修改都会产生一个正确的树（well-ording）。因此，进程 P 在 a 节点开始的路径（在时间 t>t′t > t’t>t′）将无论修改如何都能正确执行。证毕。

为了便于将定理的证明分解成不同情况，这里列出在一个节点上对一个值可能执行的三种插入类型。

类型 1. 简单地将一个值及其关联指针添加到节点中。当节点是安全的（safe）时发生这种类型的插入。
类型 2. 对节点进行分裂，并将插入值放入分裂节点的左半部分。左半部分仍然是原来被分裂的节点。
类型 3. 类似地，对节点进行分裂，并将插入值放入分裂节点的右半部分。右半部分是新分配的节点。

现在我们开始定理的证明。我们注意到，定理的正确性涉及几个方面（情况），并将分别证明这些情况。

证明. 根据引理 3，只需考虑搜索或插入进程 𝑃 在插入进程 𝐼 修改节点之前开始读取该节点的情况。

第 1 部分. 考虑插入进程 I（在时间 t0 修改节点 n）与搜索进程 S（在时间 t′< t0读取节点 n）之间的交互。记 n′ 为修改后的节点。（本节的论证同样适用于另一插入进程 I′与进程 I 交互的情况，且 I′正在执行搜索。）需要考虑的操作顺序是：S 读取节点 n；然后 I 将节点 n 修改为 n′；然后 S 根据 n 的内容继续搜索。
考虑三种插入类型：

第2部分。接下来我们考虑插入进程 I 与另一个插入进程 I’ 的交互情况。进程 I’ 可能正在搜索用于插入的正确节点、回溯到另一层，或者实际尝试将一个值/指针对插入节点 n。如果 I’ 正在搜索一个用于插入值/指针对的节点，则该搜索行为与普通搜索进程完全相同。因此，证明与上文针对搜索进程的证明相同。

第3部分。如果 I’ 因为下层节点分裂而需要回溯上行树，则 I’ 需要回到上层以便将指针插入到分裂节点的新半部分。

• 回溯是使用在下降过程中记录在栈中的信息完成的。
• 在每一层，被压入栈的节点是该层被检查过的最右侧节点。
• 考虑在将某个节点 n 压入栈和回溯时再次访问该节点之间可能发生的情况：该节点可能已经分裂过一次或多次，这些分裂会在节点 n 的“右侧”产生新的节点。
• 由于节点 n 右侧的所有节点都可以通过 link 指针访问，因此插入算法能够找到适当的位置插入值。

第四部分。如果进程 I’ 试图在节点 n 上进行插入，它会尝试锁定该节点。但进程 I 已经持有节点 n 的锁。最终，I 会释放该锁，I’ 再锁定该节点并将其读入内存。根据上面的引理，该交互是正确的，因为 I’ 的读取发生在 I 的插入之前。节点 n 要么就是插入的正确位置——此时 I’ 会执行插入；要么搜索必须沿节点的 link 指针访问其右兄弟。

LiveLock

我们在此指出，我们的算法并不能完全避免活锁(LiveLock)的可能性（即某个进程无限运行）。
如果一个进程因为不断跟随其他进程创建的 link 指针而无法终止，就可能发生这种情况。
然而，根据以下观察，我们认为在实际实现中这种情况极不可能成为问题。
在多处理器系统中，如果该进程运行在相对非常慢的处理器上，这种情况可能发生。

(1) 在我们所知的大多数系统中，处理器的运行速度大致相当。
(2) 在 B 树中，节点的创建和删除只占很小的比例，因此即使是较慢的处理器，也不太可能因节点的创建或删除而遇到困难（也就是说，它只需要跟随少量的 link 指针）。
(3) 在树的任意给定层上，只能创建固定数量的节点，从而限制了较慢处理器需要“追赶”的量。

我们认为，这些想法结合起来可以使实际系统中进程发生活锁的概率几乎为零（除非涉及的进程速度差异极大）。模拟可以帮助我们验证系统在“合理”条件下能够正常工作，并帮助确定进程相对速度的可接受范围。

在进程速度确实存在极大差异的情况下，我们可能会引入一些额外机制来防止活锁。实现这种机制有多种选择。本文不讨论避免活锁的完整方法，但其中一种方法可能是为每个进程分配优先级，优先级可能基于进程的“存在时间”。这将保证每个进程最终会终止，因为它最终会成为最“老”的进程，从而成为拥有最高优先级的进程。

7. DELETION

一种处理删除操作的简单方法是允许叶子节点中的条目少于 K 个。对于非叶子节点则不需要这样做，因为删除操作仅会移除叶子节点中的键；非叶子节点中的键仅作为其对应指针的上界，它在删除过程中并不会被移除。

因此，为了从叶子节点中删除一个条目，我们对该节点执行的操作与插入操作（尤其是插入情况 1）非常类似。具体来说，我们首先搜索出值 u 所在的节点，然后锁定该节点，将其读入内存，对内存中的副本删除值 u 后再将节点重写回磁盘。有时，这样会导致节点中条目数量少于 K。
该算法的正确性证明与插入操作类似。例如，死锁自由性的证明非常简单，因为删除操作只需要锁定一个节点。对于操作的正确性，如果一个搜索进程在删除值 u 之前读取了节点，它仍然会报告节点中存在 u，这与序列化调度（搜索操作先于删除操作执行）是一致的，因此搜索结果仍然正确。

我们刚描述的这种删除处理方法比需要处理节点下溢（underflow）和合并（concatenation）的方案要简单得多。在假设插入操作发生频率高于删除操作的情况下，这种方法几乎不需要额外存储空间。

当然，在删除操作过多导致树节点存储利用率过低的情况下，可以执行批量重组（batch reorganization）或者全树锁定的下溢操作（underflow operation）来重新组织树结构，以保证空间的合理利用。

8. 锁定效率（LOCKING EFFICIENCY）

显然，在并发方案中，至少需要一个锁，以防止不同进程同时更新同一个节点。

上文给出的插入操作方案，在任何时刻对任意进程使用的锁数量最多是一个常数（最多三个）。这种情况仅在特定情况下发生：当插入进程刚刚向某个节点（叶子节点或非叶子节点）插入条目，并导致该节点分裂时。在回溯树的过程中，为了向新分裂节点的一半插入指针，插入进程发现旧的父节点已经不再是正确的插入位置，因此必须沿包含父节点的这一层节点进行链式查找，以找到正确的插入位置。在整个操作过程中，同时锁定三个节点。

在每个节点容量较大的 B*-树中，这种类型的锁定操作发生的频率非常低。因此，除非有大量并发进程运行，否则该结构的锁冲突概率极低。

这种系统的行为可以通过模拟进行量化，模拟参数包括并发进程数量、每个节点的容量，以及搜索、插入和删除操作的相对频率。这样的模拟不仅可以评估当前方案的性能，也可用于与其他并发控制方案进行比较。

9. SUMMARY AND CONCLUSIONS

B 树在维护大型数据库时被发现非常有用。并发操作这样的数据具有明显优势，因为它允许多个用户同时共享数据；而且在大规模数据库中，用户的数据需求通常不会产生冲突，因此并发访问是可行的。

本文给出了一个算法，可以在 B 树的一种变体上执行正确的并发操作。该算法的特点是任意进程在任何时刻只需使用少量常数个锁。算法本身非常直接，其流程与顺序执行的算法仅有轻微差别。（可以通过模拟来量化本文算法与顺序算法或其他并发算法相比的效率提升。）

这一性能的实现依赖于对数据结构的一个小改动，使得当一个进程的位置因其他进程的操作而失效时，能够进行恢复（参见 [8]）。

我们希望将这项工作扩展到更通用的并发数据库操作方案。理想的方案应当仅需对数据结构和顺序算法做极少量修改，同时能够保证当其他进程对数据结构做出改变使某进程的操作失效时，该进程能够正确恢复。

另一条未来研究方向是对算法的“并行化”：研究将一个（已充分理解的）顺序算法转换为并发算法的通用方法。目标是尽可能充分利用问题的并发特性，同时保证算法的正确性不受影响。

准备表数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

test=# create table users(id int generated always as identity primary key, name text);
CREATE TABLE

test=# select oid, relname, relfilenode from pg_class where relname = 'users';
  oid  | relname | relfilenode 
-------+---------+-------------
 40980 | users   |       40980

test=# select c.oid, c.relname, i.indisprimary from pg_class c join pg_index i on c.oid = i.indexrelid where i.indrelid = 'users'::regclass and i.indisprimary;
  oid  |  relname   | indisprimary 
-------+------------+--------------
 40986 | users_pkey | t
(1 row)

test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
ERROR:  block number 0 is out of range for relation "users"
test=# select * from bt_page_items('users_pkey',1);
ERROR:  block number 1 is out of range
test=# ^C

insert values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

test=# insert into users(name) values('jeffrey');
INSERT 0 1
test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
 lp | lp_len |           t_data           
----+--------+----------------------------
  1 |     36 | \x01000000116a656666726579
(1 row)

test=# select * from bt_page_items('users_pkey',1);
 itemoffset | ctid  | itemlen | nulls | vars |          data           | dead | htid  | tids 
------------+-------+---------+-------+------+-------------------------+------+-------+------
          1 | (0,1) |      16 | f     | f    | 01 00 00 00 00 00 00 00 | f    | (0,1) | 
(1 row)

test=# select *  from page_header(get_raw_page('users', 0));
    lsn     | checksum | flags | lower | upper | special | pagesize | version | prune_xid 
------------+----------+-------+-------+-------+---------+----------+---------+-----------
 0/03F5E7A0 |        0 |     0 |    28 |  8152 |    8192 |     8192 |       4 |         0
(1 row)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

test=# insert into users(name) values('Ethan');
INSERT 0 1
test=# select *  from page_header(get_raw_page('users', 0));
    lsn     | checksum | flags | lower | upper | special | pagesize | version | prune_xid 
------------+----------+-------+-------+-------+---------+----------+---------+-----------
 0/03F62810 |        0 |     0 |    32 |  8112 |    8192 |     8192 |       4 |         0
(1 row)

test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
 lp | lp_len |           t_data           
----+--------+----------------------------
  1 |     36 | \x01000000116a656666726579
  2 |     34 | \x020000000d457468616e
(2 rows)

test=# select * from bt_page_items('users_pkey',1);
 itemoffset | ctid  | itemlen | nulls | vars |          data           | dead | htid  | tids 
------------+-------+---------+-------+------+-------------------------+------+-------+------
          1 | (0,1) |      16 | f     | f    | 01 00 00 00 00 00 00 00 | f    | (0,1) | 
          2 | (0,2) |      16 | f     | f    | 02 00 00 00 00 00 00 00 | f    | (0,2) | 
(2 rows)

Prerequisites

To build OceanBase from source code, you need to install the C++ toolchain in your development environment first. If the C++ toolchain is not installed yet, you can follow the instructions in this document for installation.

1

apt-get install git wget rpm rpm2cpio cpio make build-essential binutils m4

Clone

Clone the source code to your development machine:

1

git clone https://github.com/oceanbase/oceanbase.git

Build

Build OceanBase from the source code in debug mode or release mode:

Debug mode

1

bash build.sh debug --init --make

Release mode

1

bash build.sh release --init --make

Run

Now that you built the observer binary, you can deploy an OceanBase instance with the obd.sh utility:

1
2

./tools/deploy/obd.sh prepare -p /tmp/obtest
./tools/deploy/obd.sh deploy -c ./tools/deploy/single.yaml

You can check the mysql_port in ./tools/deploy/single.yaml file to see the listening port. Normally, if you deploy with the root user, the OceanBase server will listen on port 10000, and the examples below are also based on this port.

Connect

You can use the official MySQL client to connect to OceanBase:

1

mysql -uroot -h127.0.0.1 -P10000

Alternatively, you can use the obclient to connect to OceanBase:

1

./deps/3rd/u01/obclient/bin/obclient -h127.0.0.1 -P10000 -uroot -Doceanbase -A

Shutdown

1

./tools/deploy/obd.sh destroy --rm -n single

SSTables：Sorted String Table ： 每个segment文件中key值是有序（根据key值排序）并且唯一的。sstable有如下优势：

• merge简单高效
• 因为有序，不需要维护所有记录的索引，可以是稀疏索引
• 因为有序，可以按block进行压缩同时维护索引，除了降低磁盘占用以外，还可以降低磁盘io

构建和管理SSTables

因为写入是无序的，所以我们需要在内存中借助于红黑树或者avl树等数据结构来保证：任意写入，有序读取.

构建步骤如下:

1. 当写入发生时，将写入的key-value加入内存平衡树（如红黑树）中，称为”memtable”
2. 当memtable增大到一定阈值后（a few megabytes），将memtable写入磁盘生成一个SSTable文件。新写入的SSTable成为数据库中最新的segment文件。 写入SSTable到磁盘时，写入可以继续写入新的memtable
3. 读请求来时，优先在memtable中查找，然后按顺序从新到老查找磁盘上的segment文件
4. 随着时间的推移，可以后台启动合并和压缩segment文件、丢弃或者覆盖掉老的文件

这种机制工作的很好，但是存在一个问题，如果数据库宕机了，内存中的memtable还没有来得及写入磁盘，可能造成数据丢失。可以通过一个单独的log文件来记录所有的操作，这个log的作用只是用于宕机恢复memtable，每当memtable被写入磁盘，相应的log文件就可以被丢弃了

用SSTables构建LSM-tree

LSM-Tree用于 LevelDB 和 RocksDB、嵌入其他应用的key-value存储引擎。参考：Google’s Bigtable paper

SSTables + log = “Log-Structured Merge-Tree ”

LSM-tree两种文件管理策略：

1. Size-Tiered Compaction（STC）

   • 基本思想
     “当某一层（或同一大小区间）的 SSTable 文件数达到阈值时，将它们合并成一个更大的文件。”
     也就是说，不是按“层级”，而是按“文件大小”来触发 compaction。

   • 结构示意
     MemTable → SSTable

   • 优点

     • 写放大低
       每条数据在被 flush 后只会参与少数几次合并；每次合并是“几块 → 一块”，合并次数较少。
     • 写入吞吐高
       flush 后直接落地；合并是批量异步进行；对写性能非常友好。

   • 缺点

     • 读放大高
       同一 key 可能存在于多个 SSTable 中；读时需要查多个文件（除非借助 Bloom Filter）。
     • 空间放大高
       合并不够积极；多个旧版本的数据同时存在；临时文件和重复 key 较多。

   • 应用场景
     适合写多读少的场景；比如日志系统、时间序列数据库（TSDB）、写入密集的监控系统Cassandra 默认采用 STCS（Size-Tiered Compaction Strategy）

2. Level Compaction（LC）
   这种策略是 LevelDB、RocksDB 采用的，更现代化。又叫 leveled compaction 或 分层压实。

   • 基本思想：
     数据被组织成多个层级（Level 0, Level 1, Level 2…），每一层都有固定大小的空间限制，同一层内文件的 key 范围 互不重叠。

   • 层次结构：
     Level 0: 多个小 SSTable，key 范围可能重叠。
     Level 1: 较大文件，key 范围不重叠。
     Level 2: 更大文件，key 范围不重叠。
     …

   • Compaction 逻辑：
     当某一层（如 Level 0）容量超标；就选择一个 SSTable（或一组）与下一层（如 Level 1）中 key 范围重叠的文件；合并、去重、重写为更大的 SSTable，放入下一层。

   • 优点

     • 读性能优异
       除 Level 0 外，其余层内文件 key 范围不重叠；读取某个 key 只需查找每层最多一个文件；查找代价从 O(n_files) 降到 O(levels)。
     • 空间利用率高
       去重及时；每层占用空间接近固定比例；不容易膨胀。

   • 缺点

     • 写放大高
       每条数据会多次参与合并（从 L0 → L1 → L2…）；每次都要重写到下一层； 磁盘写入量是原始写入的数倍。
     • Compaction 代价大
       大文件之间的合并非常消耗 I/O；RocksDB 必须限制后台 compaction 线程数量。

   • 应用场景
     适合读写比较均衡、查询多的系统；比如 RocksDB、LevelDB、TiKV、ClickHouse 的部分引擎。

性能优化

当查找的key在数据库中不存在时，LSM-Tree算法可能会变慢：在你确认key不存在之前，你需要检查所有memtable，所有sstable对应的磁盘文件。可以使用bloom filters：它可以检查key不在数据库中（每个sstable固化时，生成对应的bloom filter文件）

Here are some tips for using omnigraffle

Draw circle

Hold down Shift while drawing a circle

Draw curve

1. select pen tool: draw custome sharps
2. Click one point on the canvas, then click another point — a straight line will appear.
3. Select the line → double-click the middle of the line → drag the new point: a curved effect will appear.

Flexible Control Over Line Arrows

When the endpoint of a line (especially an endpoint with an arrow) is connected to a shape, the default mode is “Connected Line” (automatic snapping). In this mode, the endpoint is “locked” to the shape’s boundary or center, and cannot be freely dragged.

Solution

1. Turn on Magnets
   • Select the target shape.
   • Menu Bar → Edit → Magnets → Show Magnets
   • You will see small red dots (magnets) appear around the shape.
   • These are the connectable positions.
   • Drag the endpoint of a line near the red dot, and it will snap/attach to that point.

What is Magnet?

Magnet (magnetic points) are those positions on the shape (Shape) that can attract the end points of the lines.
When you draw a line with the Line Tool, endpoints that are close to these magnetic points will “snap” to it.

Examples

配置checkpoint

checkpoint持续时间（更准确地说，是将脏缓冲区写入磁盘所需的时间）由参数 checkpoint_completion_target 决定。该参数的值表示checkpoint 期间的 I/O 分布目标，是一个比例。避免将该参数设置为 1：否则可能会导致下一个checkpoint启动时，上一个checkpoint尚未完成。虽然不会发生灾难性的后果（因为同一时间只能执行一个checkpoint），但正常运行可能仍会受到干扰。

在配置其他参数时，我们可以采用以下方法。首先，确定在两个相邻checkpoint之间应存储的 WAL 文件的合理体积。这个体积越大，系统开销就越小，但它仍然会受到可用磁盘空间和可接受的恢复时间的限制。

为了估算在正常负载下生成这一体积所需的时间，你需要记录初始的 insert LSN，并定期检查它与当前 insert 位置之间的差值

我们将前面计算出的数值视为checkpoint之间的典型间隔，因此将其用作 checkpoint_timeout 参数的值。默认设置往往偏小，通常会将其增加，例如设置为 30 分钟。

但也很可能（甚至可以说是很常见）负载会在某些时候升高，从而导致在这个时间间隔内生成的 WAL 文件体积过大。在这种情况下，必须更频繁地执行checkpoint。为了设置这样的触发机制，我们通过 max_wal_size 参数来限制恢复时所需的 WAL 文件总量。当超过这个阈值时，服务器会额外执行一次checkpoint。

恢复所需的 WAL 文件包含了上一个已完成checkpoint和当前尚未完成检查点的所有记录。因此，为了估算这些文件的总体积，应将计算出的检查点之间的 WAL 大小乘以
1 + checkpoint_completion_target。

在 PostgreSQL 11 版本之前，系统会保留两个已完成checkpoint所对应的 WAL 文件，因此估算恢复所需 WAL 总体积的倍数是：2 + checkpoint_completion_target

按照这种方式，大多数checkpoint会按计划执行，即按照 checkpoint_timeout 设置的时间间隔执行一次；但如果系统负载增加，导致生成的 WAL 文件大小超过 max_wal_size 的设定值，就会提前触发一次checkpoint。

系统还会定期将实际进度与预期数值进行比较，以监控写入进度是否达标。

实际进度由已处理的缓存页所占的比例来定义。

按时间计算的预期进度是指已过去的时间占比，其前提假设是checkpoint必须在 checkpoint_timeout × checkpoint_completion_target 的时间内完成。

按大小计算的预期进度是指已写入的 WAL 文件所占的比例，其总量根据 max_wal_size × checkpoint_completion_target 来估算。

如果脏页提前写入磁盘，checkpointer 进程会暂停一段时间；如果在时间或数据大小的任何一个参数上出现延迟，它会尽快赶上进度。由于同时考虑了时间和数据大小，PostgreSQL 能够用同一套机制来管理定时checkpoint和按需checkpoint。

一旦checkpoint完成，不再需要用于恢复的 WAL 文件将被删除；不过，系统会保留若干文件（总大小不超过 min_wal_size），用于重复利用，并通过重命名的方式保留。

这种重命名机制减少了频繁创建和删除文件所带来的开销；如果你不需要这个功能，可以通过参数 wal_recycle 将其关闭。

下图展示了在正常情况下，磁盘上 WAL 文件大小的变化趋势

需要注意的是，磁盘上实际的 WAL 文件大小可能会超过 max_wal_size 的设定值，原因包括：

• max_wal_size 参数只是一个期望目标值，而不是严格限制。如果负载突然上升，写入速度可能会落后于计划，导致 WAL 文件积压。
• 尚未被复制或归档的 WAL 文件，服务器无权删除。如果启用了流复制或持续归档功能，必须持续监控这些机制，否则非常容易导致磁盘空间耗尽。
• 你可以通过配置 wal_keep_size 参数来预留一定的磁盘空间用于存储 WAL 文件，以避免这些问题带来的风险。

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

当数据库服务正常运行时，wal文件持续不断的写入磁盘。这种写入时顺序的（sequential）：几乎没有随机访问，所以即便时hdd硬盘也能处理这样的任务。由于这种负载和典型的数据文件访问非常不一样，值得为WAL文件设置单独的物理存储，并通过符号链接替换PGDATA/PG_WAL目录，该目录链接到mount的文件系统中的目录。

在某些情况下，需要同时写和读取WAL文件。第一种情况是崩溃恢复。第二个是流复制。 Walsender流程直接从文件中读取WALENTRIES。因此，如果必需的页面仍位于主服务器的OS缓冲区中（不在shared_buffer中），replica未接收WAL条目，则必须从磁盘中读取数据。但是访问仍然是顺序而不是随机的。

wal日志条目写入有以下两种模式：

• 同步模式：在事务提交之前，必须把所有相关的 WAL 记录写入磁盘，否则不允许继续执行后续操作。
• 异步模式：事务提交会立刻返回成功，相关的 WAL 记录则由后台进程稍后再写入磁盘。

当前使用的模式由参数：synchronous_commit 确定

同步模式：为了可靠地记录一次提交，仅仅将WAL条目传递给操作系统是不够的；你必须确保磁盘同步已经成功完成。由于同步涉及实际的I/O操作（这相当慢），因此最好尽可能少地执行它。

为此，完成事务并将WAL条目写入磁盘的后端可以进行一次小的暂停，该暂停由commit_delay参数定义。但是，只有当系统中至少有commit_siblings个活跃事务时，这种情况才会发生：在这次暂停期间，其中一些事务可能会完成，而服务器将设法一次性同步所有WAL条目。这很像为某人赶进来而按住电梯门。

默认情况下，没有暂停。仅针对执行大量短时OLTP事务的数据库系统修改commit_delay参数是有意义的。

在可能出现的暂停之后，完成事务的进程会将所有累积的 WAL 条目刷新到磁盘并执行同步操作（关键是要保存提交记录以及与该事务相关的所有前置记录；至于其他记录，则只是顺便写入，因为它们不会增加额外开销）。

从这一刻起，ACID 的持久性要求便得到保证——事务被认为已经可靠提交。这就是为什么默认使用同步模式的原因。

同步提交的缺点在于延迟更长（在同步完成之前，COMMIT 命令不会返回控制权），并且系统吞吐量较低，尤其对于 OLTP loads。

异步模式：要启用异步模式，必须关闭 synchronous_commit 参数。
在异步模式下，WAL 条目由 walwriter 进程写入磁盘，该进程在“工作—休眠”之间交替运行。休眠时长由 wal_writer_delay 参数决定（默认 200ms）。

当 walwriter 从休眠中唤醒时，它会检查缓存中是否存在新的、已经完全填满的 WAL 页面。如果存在，就将这些页面写入磁盘，同时跳过当前未写满的页面；否则，它会写入当前半空的页面，因为既然已经被唤醒了。

这种算法的目的在于避免同一个页面被多次刷盘，这在数据变更频繁的负载下能带来显著的性能提升。

虽然 WAL 缓存采用环形缓冲区（ring buffer）的形式，但 walwriter 在到达缓存的最后一页时会停止；在经过一次休眠后，下一轮写入循环会从缓存的第一页重新开始。因此，在最坏的情况下，walwriter 可能需要 三次循环才能处理某个特定的 WAL 记录：

第一次，它会写出缓存尾部的所有已填满页面；（当前位置之后的所有满块）
第二次，它回到开头；（当前位置之前的所有满块）
第三次，才会处理包含目标记录的那个未填满页面。
不过，在大多数情况下，只需要 一到两次循环 就能完成。

每当写入的数据量达到 wal_writer_flush_after 时，就会执行一次同步操作；在写入循环结束时，也会再次进行同步。

与同步提交相比，异步提交更快，因为它不需要等待物理写入磁盘完成。但可靠性有所下降：在发生故障前的 3 × wal_writer_delay 时间内提交的数据可能会丢失（默认值为 0.6 秒）

在实际应用中，这两种模式是互补的。

• 在 同步模式 下，与长事务相关的 WAL 条目仍然可以 异步写入，以释放 WAL 缓冲区。
• 反之，即使在 异步模式 下，如果某个 WAL 条目所在的页即将被 从缓冲区淘汰，该条目也会被 立即刷盘，否则系统无法继续正常操作。
  在大多数情况下，系统设计者必须在 性能和持久性之间做出权衡。

synchronous_commit 参数也可以针对特定事务进行设置。如果能够在应用层将所有事务分类为 绝对关键（如处理财务数据）或 非关键，就可以在只冒非关键事务丢失风险的前提下，提升整体性能

为了了解 异步提交 可能带来的性能提升，我们可以通过 pgbench 测试，比较两种模式下的 延迟（latency）和吞吐量（throughput）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

postgres@lavm-bar1guved6:/root$ pgbench -i test
dropping old tables...
NOTICE:  table "pgbench_accounts" does not exist, skipping
NOTICE:  table "pgbench_branches" does not exist, skipping
NOTICE:  table "pgbench_history" does not exist, skipping
NOTICE:  table "pgbench_tellers" does not exist, skipping
creating tables...
generating data (client-side)...
vacuuming...                                                                              
creating primary keys...
done in 1.54 s (drop tables 0.11 s, create tables 0.49 s, client-side generate 0.54 s, vacuum 0.18 s, primary keys 0.23 s).
 
postgres@lavm-bar1guved6:/root$ pgbench -T 30 test
pgbench (19devel)
starting vacuum...end.
transaction type: <builtin: TPC-B (sort of)>
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
maximum number of tries: 1
duration: 30 s
number of transactions actually processed: 3522
number of failed transactions: 0 (0.000%)
latency average = <strong>8.518</strong> ms
initial connection time = 4.025 ms
tps = <strong>117.400485</strong> (without initial connection time)

修改参数后跑异步模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

postgres@lavm-bar1guved6:/root$ psql test
psql (19devel)
Type "help" for help.
 
test=# ALTER SYSTEM SET synchronous_commit = off;
ALTER SYSTEM
test=# SELECT pg_reload_conf();
 pg_reload_conf 
----------------
 t
(1 row)
 
postgres@lavm-bar1guved6:/root$ pgbench -T 30 test
pgbench (19devel)
starting vacuum...end.
transaction type: <builtin: TPC-B (sort of)>
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
maximum number of tries: 1
duration: 30 s
number of transactions actually processed: 9510
number of failed transactions: 0 (0.000%)
latency average = <strong>3.154</strong> ms
initial connection time = 4.383 ms
tps = <strong>317.038330</strong> (without initial connection time)

在 异步模式 下，这个简单的基准测试显示出 显著更低的延迟（latency）和更高的吞吐量（tps）。当然，每个具体系统的数值会根据当前负载有所不同，但可以清楚地看出，对于 短事务，性能提升是相当明显的。

恢复参数：

1
2
3
4
5
6
7
8
9
10
11

postgres@lavm-bar1guved6:/root$ psql test
psql (19devel)
Type "help" for help.
 
test=# ALTER SYSTEM RESET synchronous_commit;
ALTER SYSTEM
test=# SELECT pg_reload_conf();
 pg_reload_conf 
----------------
 t
(1 row)

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

昨日和同事探讨了一下pg与mysql，发现对于mysql的innodb存储引擎了解甚少，正好周末，深入学习了解了一下，整理一下这两天学到的东西。

概念介绍

InnoDB：MySQL 的主要存储引擎
heap table：postgres数据库P表在物理上的存储（Heap File）

数据存储方式

innodb 底层存储

innodb是一个基于聚簇索引（Clustered Index）的存储引擎。

数据存储方式

• 聚簇索引存储表数据
  • 表的主键索引就是数据本身的物理存储顺序。
  • 每个页（page）一般 16KB，页内数据按主键顺序排列。
  • 非主键列数据和行信息都在叶子节点。
• 二级索引
  • 非主键索引存储的是主键值而不是行指针。
  • 查询非主键列时，需要先通过二级索引拿到主键，再去主键聚簇索引里查数据（回表，row lookup）。

页与数据组织

• 数据按 B+ 树页组织。
• 插入/更新可能导致页分裂。

postgres heap table

数据存储方式

• 数据按插入顺序存放，没有聚簇索引。
• 行标识符 TID（tuple id） 用于指向表的页和行。
• 页（默认 8KB）内存储多行 tuple。
• 没有聚簇索引，非索引扫描可能会更慢，但插入非常快。

索引

• B+ 树、哈希、GIN、GiST 等索引都是附加结构，存储独立于表。
• 回表操作是通过 TID 定位行。

对比

因为pg的存储结构导致访问数据，多了许多随机io：从索引到数据文件。导致pg的查询性能不如innnodb

pg的一些优化

CLUSTER 命令（物理重排）

1

CLUSTER t USING idx_id;

把表物理顺序按照索引顺序重排 —— 效果类似 InnoDB 聚簇索引。
缺点：

• 是离线操作；
• 之后新插入的行会破坏顺序（除非周期性 recluster）

索引仅扫描（Index Only Scan）

如果查询的字段都在索引里且可见性检查通过（可见性 map 中标记为 all-visible），可以不访问堆表，直接从索引返回结果。

BRIN 索引

BRIN 全称是 Block Range INdex，是一种 非常轻量级的索引，设计理念与 B-Tree 不同：
不是存储每一行的索引它只存储堆表的一段范围（block range）内的最小值和最大值等摘要信息。每个 BRIN 索引条目覆盖 多个物理数据页（例如 128 个 8KB 页面 = 1MB 的行数据）。
通过这些范围信息，可以快速排除不可能匹配的块，再去 heap 查找具体 tuple。
简单理解：BRIN 是“粗粒度索引”，通过块范围（block range）而非单行建立索引
非常适合 大表 + 顺序或局部相关数据：大表 + 顺序或局部相关数据：

服务器启动时，第一个启动的进程是 postmaster（新版本为postgres）。postmaster 接着会生成 startup process（启动进程），startup process 负责在发生故障时进行数据恢复。

startup process 是一个短暂的、一次性的进程，它的主要职责是在数据库启动时执行崩溃恢复或归档恢复。它完成它的工作后，就会退出。

1
2
3

postgres@lavm-bar1guved6:/root$ pg_controldata -D /home/postgres/pgdata/ |grep state
Database cluster state:               in production
postgres@lavm-bar1guved6:/root$ 

一个正常停止的服务器会处于“已关闭”（shut down）状态；而一个未运行的服务器却显示为“生产中”（in production）状态，则表明发生了故障。在这种情况下，启动进程（startup process）将自动从在同一个 pg_control 文件中找到的最新完成的检查点（checkpoint）**的起始 LSN 处开始进行恢复。

如果 PGDATA 目录中包含与备份相关的 backup_label 文件，则起始 LSN 位置会从该文件中获取。

在启动过程中，系统会从指定位置开始，逐一读取WAL（Write-Ahead Log，预写式日志）条目。如果数据页的 LSN（Log Sequence Number，日志序列号）小于当前读取到的 WAL 条目的 LSN，系统会将该 WAL 条目应用到数据页上。如果数据页的 LSN 已经大于 WAL 条目的 LSN，则不应应用该 WAL 条目；事实上，也绝不能应用，因为 WAL 条目被设计为必须严格按顺序重放。

然而，有些 WAL 条目是Full Page Image（FPI）。这类条目可以应用于页面的任何状态，因为它们会完全覆盖页面内容，无论页面原先是什么状态都不重要。因此，这种修改是幂等的（idempotent）——多次应用不会改变结果另一个幂等操作的例子是注册事务状态的变更：每个事务的状态在 CLOG（事务提交日志）中是通过设置特定位来表示的，这种设置不依赖于原来的位值。因此，不需要在 CLOG 页面中记录最近变更的 LSN（日志序列号），因为日志重放时只要设置一次这些位就够了，重复设置也不会有副作用最后，系统会执行一次 checkpoint（检查点），将恢复后的所有修改持久化到磁盘，此时 启动进程（startup process） 的任务就完成了。

WAL 日志条目会被应用到缓冲池（buffer cache）中的页面上，就像正常运行时对数据页的普通修改一样。

文件的恢复也遵循类似方式：例如，若某条 WAL 记录表明某个文件应该存在，但实际却缺失，系统就会重新创建这个文件。
一旦恢复完成，所有 unlogged relations会被它们对应的 初始化副本（init fork） 覆盖。

最后，系统会执行一次 checkpoint，将恢复后的所有修改持久化到磁盘，此时 启动进程（startup process） 的任务就完成了
在其经典形式中，恢复过程包含两个阶段：

• roll-forward阶段：重放 WAL 日志，重复执行在崩溃时丢失的操作；
• roll-back阶段：服务器中止那些在故障发生时尚未提交的事务。
  在 PostgreSQL 中，向后回滚是不需要的。恢复完成后，CLOG（事务状态日志）中对未完成事务既没有提交（commit）标记，也没有中止（abort）标记（这在技术上表示该事务处于活动状态），但因为可以确定该事务已经不再运行，所以系统会将其视为已中止（aborted）。

我们可以通过强制服务器以“立即模式”（immediate mode）停止来模拟故障：

1
2
3
4
5

postgres@lavm-bar1guved6:/root$ pg_ctl stop -m immediate
waiting for server to shut down.... done
server stopped
postgres@lavm-bar1guved6:/root$ pg_controldata -D /home/postgres/pgdata/ |grep state
Database cluster state:               in production

当我们启动服务器时，启动进程会检测到之前发生了故障，因而进入恢复模式：

1
2
3
4
5
6
7
8
9
10
11

2025-08-04 10:23:31.860 CST [487414] LOG:  starting PostgreSQL 19devel on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0, 64-bit
2025-08-04 10:23:31.861 CST [487414] LOG:  listening on IPv4 address "127.0.0.1", port 5432
2025-08-04 10:23:31.878 CST [487414] LOG:  listening on Unix socket "/tmp/.s.PGSQL.5432"
2025-08-04 10:23:31.920 CST [487420] LOG:  database system was interrupted; last known up at 2025-08-01 09:36:11 CST
2025-08-04 10:23:32.098 CST [487420] LOG:  database system was not properly shut down; automatic recovery in progress
2025-08-04 10:23:32.125 CST [487420] LOG:  redo starts at 0/01B75168
2025-08-04 10:23:32.125 CST [487420] LOG:  invalid record length at 0/01B752A8: expected at least 24, got 0
2025-08-04 10:23:32.125 CST [487420] LOG:  redo done at 0/01B75270 system usage: CPU: user: 0.00 s, system: 0.00 s, elapsed: 0.01 s
2025-08-04 10:23:32.132 CST [487418] LOG:  checkpoint starting: end-of-recovery fast wait
2025-08-04 10:23:32.152 CST [487418] LOG:  checkpoint complete: wrote 0 buffers (0.0%), wrote 3 SLRU buffers; 0 WAL file(s) added, 0 removed, 0 recycled; write=0.006 s, sync=0.005 s, total=0.022 s; sync files=2, longest=0.005 s, average=0.003 s; distance=0 kB, estimate=0 kB; lsn=0/01B752A8, redo lsn=0/01B752A8
2025-08-04 10:23:32.155 CST [487414] LOG:  database system is ready to accept connections

如果服务器正在正常关闭，postmaster 会先断开所有客户端连接，然后执行最后一次检查点操作，将所有脏页（未写入磁盘的修改页面）刷写到磁盘上。

看当前的WAL位置

1
2
3
4
5

test=# SELECT pg_current_wal_insert_lsn();
 pg_current_wal_insert_lsn 
---------------------------
 0/01B75358
(1 row)

我们正常停止服务

1
2
3

postgres@lavm-bar1guved6:~$ pg_ctl stop
waiting for server to shut down.... done
server stopped

现在的数据库状态：

1
2

postgres@lavm-bar1guved6:~$ pg_controldata -D /home/postgres/pgdata/ |grep state
Database cluster state:               shut down

在WAL的末尾，我们看到了表示最后一次checkpoint的CHECKPOINT_SHUTDOWN 条目

1
2
3
4

postgres@lavm-bar1guved6:~$ pg_waldump  -p /home/postgres/pgdata/pg_wal -s 0/01B75358
rmgr: XLOG        len (rec/tot):    114/   114, tx:          0, lsn: 0/01B75358, prev 0/01B75320, desc: CHECKPOINT_SHUTDOWN redo 0/01B75358; tli 1; prev tli 1; fpw true; wal_level replica; xid 0:758; oid 24576; multi 1; offset 0; oldest xid 746 in DB 1; oldest multi 1 in DB 1; oldest/newest commit timestamp xid: 0/0; oldest running xid 0; shutdown
pg_waldump: error: error in WAL record at 0/01B75358: invalid record length at 0/01B753D0: expected at least 24, got 0
postgres@lavm-bar1guved6:~$ 

最新的 pg_waldump 消息显示该工具已读取 WAL到末尾。

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

一 相关结构体说明

1
2
3
4
5
6
7
8
9
10

typedef struct LWLock
{
    uint16           tranche;       /* tranche ID */
    pg_atomic_uint32 state;         /* state of exclusive/nonexclusive lockers */
    proclist_head    waiters;       /* list of waiting PGPROCs */
#ifdef LOCK_DEBUG
    pg_atomic_uint32 nwaiters;      /* number of waiters */
    struct PGPROC    *owner;        /* last exclusive owner of the lock */
#endif
} LWLock;

• tranche
  每个 LWLock 都属于某个 tranche，tranche 是一个 int 类型的 ID，代表这把锁的用途

• state （不同版本可能会有变化，本文对应版本：PostgreSQL 19devel（开发版，尚未正式发布的 19））
  bit0..17：共享持有者计数（一个整数计数，不是位图）
  bit18：独占锁哨兵位（LW_VAL_EXCLUSIVE = 1<<18）

bit29: LW_FLAG_LOCKED，是 wait list 自身的小锁（保护等待队列操作）
bit30: LW_FLAG_RELEASE_OK，表示当前可以在释放路径执行唤醒
bit31: LW_FLAG_HAS_WAITERS，表示等待队列里有 waiter

• waiters
  等待队列

二 Interface说明

2.1 LWLockAcquire

加锁，失败进入等待队列，直接加上锁的情况，可能会造成等待队列无效唤醒

acquire a lightweight lock in the specified mode
Side effect: cancel/die interrupts are held off until lock release.

1
2
3
4
5
6
7
8
9
10
11
12

if (mode == LW_EXCLUSIVE)
{
    lock_free = (old_state & LW_LOCK_MASK) == 0;
    if (lock_free)
        desired_state += LW_VAL_EXCLUSIVE;
}
else
{
    lock_free = (old_state & LW_VAL_EXCLUSIVE) == 0;
    if (lock_free)
        desired_state += LW_VAL_SHARED;
}

上述代码确认是否可以加锁

2.2 LWLockRelease

进行唤醒条件：

• oldstate & LW_FLAG_HAS_WAITERS：等待队列非空。这个条件确认有进程在等待锁。
• oldstate & LW_FLAG_RELEASE_OK： 允许唤醒。这个标志表示系统在上次唤醒后，已经将再次唤醒其他等待者的权限交给了被唤醒的进程。
• (oldstate & LW_LOCK_MASK) == 0：锁已空闲。这个条件确认锁当前没有被任何进程占用（无论是独占模式还是共享模式，计数都为零）

三 分配与类型（默认值，版本相关）

1. NUM_INDIVIDUAL_LWLOCKS：核心按表生成的单锁（lwlocklist.h），数量随版本变化，不是固定 56。
2. NUM_BUFFER_PARTITIONS（默认 128）：共享缓冲区 mapping hash 的分区锁 BufferMappingLock[i]。
3. NUM_LOCK_PARTITIONS（默认 16）：heavyweight lock manager 哈希分区锁（LWTRANCHE_LOCK_MANAGER）。
4. NUM_PREDICATELOCK_PARTITIONS（默认 16）：谓词锁哈希分区锁。
5. 扩展自定义：在 postmaster 启动阶段调用 RequestNamedLWLockTranche(name, n) 申请一组锁，重启后 GetNamedLWLockTranche 取基址。需要 shared_preload_libraries 的扩展通常属于此类。