openGauss
开源数据库
openGauss社区官网
开源社区
openGauss B-tree索引读写并发实现
openGauss B-tree 索引读写并发实现
openGauss B-tree 索引在实现时,没有完全遵循 L & Y 的理论,本文主要关注 openGauss 中 B-tree 索引的实现。
实现与理论的差异
读锁
介绍 B-tree 索引并发读写原理时讲到,L & Y 的理论中读操作完全不加锁,而是假设 B-tree 节点在内存中的拷贝是非共享的。但实际在 PG 和 openGauss 的实现中,内存中的 buffer 是共享的。所以在实现中,实际读操作需要对节点加读锁,来保证读期间没有修改操作。加锁动作降低了并发性,但保证了数据正确性。
写锁
L & Y 的理论总是将加锁和 moveright 耦合,最多同时会对三个节点加锁(分裂的子节点、父节点、父节点的右兄弟节点)。实现中,同一层的节点不需要都加锁。L & Y 的理论中通过记录从根节点开始查找路径上的节点及 key 的信息来记录父子节点关系,理论中假设所有的 key 都是不同的。实现中,父节点通过记录子节点的 Block Number 来实现父节点指向子节点的指针。理论中如果发生分裂需要更新父节点时,父节点所在层的加锁的顺序是:先对父节点加锁,如果父节点发生了分裂,则对父节点的右兄弟节点加锁,然后释放父节点的锁。而实现中,在对父节点的右兄弟节点加锁前,可以释放父节点的锁,因为 link ptr 实现中是记录的右兄弟节点的 block number, 即使右兄弟节点又发生分裂,依然可以通过 block number 找到分裂后的左侧节点,然后继续向右查找。
link ptr
L & Y 的理论中每一层节点都有指向右侧节点的 link ptr,当执行 scan 的操作时,通过 link ptr 只能支持自左向右的 scan。为支持逆向 scan,OpenGauss 中每个节点都有指向左右两侧的两个指针,将指向同层右侧节点的称为 right link ptr,指向左侧节点的称为 left link ptr。这个修改,导致 L & Y 的理论中节点分裂需要额外的动作。在锁定分裂节点的同时,还需要锁定该节点分裂前的右兄弟,以修改其 left link ptr,如图-1 所示。实际逆向 scan 比正向 scan 要复杂一些,因为如果逆向 scan 的过程中节点发生分裂,可能还需要通过 right link ptr 向右查找(实际比更复杂,我们会在后面讨论)。
在 scan 过程中,只有在需要读一个节点时才会对其加锁,为减少加锁的时长,读操作会一次把所有满足条件的项全部读出来,在处理这些项时就可以释放锁了。有时,为了防止并发的 delete 操作,需要 pin 住某个叶子节点(后面会讲到)。scan 过程中,需要记住当前在扫描节点的 right link ptr,通过 right link ptr 向右 scan 不会遗漏数据;但如果是向左 scan,需要获取最新的 left link ptr。
大多数情况下,在对下一个节点进行 pin 和加锁前,会释放前一个节点的 pin 和锁;但有些情况下会先对下一个节点进行 pin 和加锁,再释放前一个节点的 pin 和锁。之前讲并发原理时证明过,流程中可以避免死锁的出现,但现在由于实现没有完全按照 L & Y 的理论,加了 left link ptr,似乎有死锁的可能。
L & Y 的理论中假设 key 的大小是固定的,实际需要处理变长的 key。因此对每一个 page 而言,key 的个数没有一个固定的最大值,实现中假设一个 page 内至少要有 3 个 item,因此 tuple 的大小不能超过一个 page 最大可用空间的 1/3。节点发生分裂时,按照占用空间来平均分配分裂后的左右节点,而不是按照 item 的个数均分。同时分裂需要将已经在执行中的事务占用的空间考虑在内,否则事务提交时可能出现 page 内没有足够空间的问题。
L & Y 的理论中假设 key 没有重复的,实际是对于非 unique index 可能存在重复 key。
插入
在执行数据插入的流程中,需要更新 heap tuple 和 index tuple,更新 index tuple 执行 ExecInsertIndexTuples 方法,处理的主要流程如下:
{
遍历表上的每一个索引 {
如果索引的 indisready = false,表示索引不可写,则跳过此索引;
如果是分区表的 local 索引,且 pg_partiton 中 indisusable = false,跳过此索引;
调用索引插入函数 index_insert,完成 index tuple 插入
检查索引插入是否违反约束 unique / exclusion constraint
返回结果
}
}
在介绍索引相关的代码实现之前,先介绍一下 OpenGauss 中索引实现的目录结构。
索引的实现主要在 src/gausskernel/storage/access 下,其中
- nbtree: 行存表 btree 索引的实现
- cbtree: 列存表 btree 索引的实现
- gist: gist 索引实现
- gin: 倒排索引实现
- psort: 列存表 psort 索引实现
- index: 索引对外接口
行存表支持的索引类型:btree(缺省值)、gin 和 gist。
列存表支持的索引类型:psort(缺省值)、btree 和 gin。
本文中主要介绍行存表 Btree 索引实现,对应的目录为 nbtree
index_insert
// 实现在 indexam.cpp 所有索引对外接口 { 根据索引类型,找到对应的索引插入处理函数(存储在pg_am中),例如btree索引对应的插入函数为btinsert 调用对应的插入处理函数 返回结果 }
btinsert
// 实现在 nbtree.cpp,行存表btree索引插入实现 { 调用 index_form_tuple 生成 index tuple; 调用 _bt_doinsert 完成索引插入 返回结果 }
_bt_doinsert
// 实现在 nbtinsert.cpp,行存表 btree 索引 index tuple 插入
{ 生成scankey用于在B-tree索引中查找插入位置。 调用 _bt_search 查找插入的叶子节点,返回一个BTStack类型的对象,该对象的实现是一个链表,链表头是叶子节点,后面的每个节点是前一个节点的父节点。由于插入数据可能导致节点分裂,子节点分裂需要更新父节点,可以通过此链表向上查找父节点。 调用 _bt_moveright,找到最终指向插入的叶子节点。因为流程不是全程加锁(先加读锁,然后释放读锁,再加写锁),因此在找到插入的叶子节点后,该节点可能由于新的插入导致分裂,则新的插入位置可能在原节点的右侧,需要向右查找(多次分裂可能需要多次向右查找);如果叶子节点没有发生变化,或者插入位置不需要向右查找,则_bt_moveright实际不做任何事情。这一点涉及Btree索引的并发控制,可以参考前一篇。 检查unique约束,包括进行中的事务,如果有执行中的事务可能导致违反约束,需要等待执行中的事务结束。 page内查找插入位置_bt_findinsertloc 执行插入操作 _bt_insertonpg }
在查找插入节点的实现 _bt_search 中,在每次使用节点时都需要调用一次 _bt_moveright ,因为查找过程中加锁的顺序是先对父节点加 ReadLock,查找到子节点(父节点指向子节点的指针的实现是记录子节点的页号)后释放父节点的 ReadLock,再对子节点加 ReadLock。由于读写并发,查找到子节点到对子节点加 ReadLock 这段时间内子节点有可能已经发生了分裂,因此在使用子节点查找时需要调用一次_bt_moveright。这样实现可以减少加锁的粒度,有利于读写并发。
_bt_search 查找到最终要执行插入的叶子节点后,在使用该节点时也要调用一次_bt_moveright,原因是查找到叶子节点后,对叶子节点加了 ReadLock。但是由于需要执行插入动作,会先释放叶子节点的 ReadLock 再对叶子节点加 WriteLock,放锁到再加锁的间隙叶子节点可能发生分裂。代码实现如下:
stack = _bt_search(rel, indnkeyatts, itup_scankey, false, &buf, BT_WRITE);
offset = InvalidOffsetNumber;
/* trade in our read lock for a write lock */
LockBuffer(buf, BUFFER_LOCK_UNLOCK);
LockBuffer(buf, BT_WRITE);
buf = _bt_moveright(rel, buf, indnkeyatts, itup_scankey, false, true, stack, BT_WRITE);
_bt_moveright
// 实现在 nbtserach.cpp 在获取到将要执行插入的叶子节点后,由于并发操作,实际位置可能发生了变化,需要由当前节点向右查找才能找到实际位置
{ 如果是写入操作insert/update,则在流程中检查是否有未完成的分裂,插入流程不允许插入一个未完成分裂中的page(通过P_INCOMPLETE_SPLIT判断。未完成的分裂可能是程序crash或者其他failure导致,special区域有标记页面的状态),因此先在流程中完成分裂动作。_bt_finish_split 这里流程的实现需要先了解 _bt_split 流程。 如果当前节点的flag是(BTP_DELETED | BTP_HALF_DEAD),表明叶子节点被删除,需要向右移动;如果当前的scan key > 节点的HK,则节点在上次获取之后发生了分裂,需要向右移动。循环检查,直到当前节点是最右节点,或者scan key <= HighKey。 }
对要执行插入操作的叶子节点加锁后,需要在叶子节点内找到具体的插入位置,调用方法 _bt_findinsertloc。
_bt_findinsertloc
// 实现在 nbtinsert.cpp 在 page 内为要插入的 index tuple 查找一个插入位置(page buffer + offset)
{ 检查 tuple size 是否小于page内最大可用空间的1/3,一个page内最少要放3个tuple 如果当前page可用空间不足以放下插入的tuple,可能需要执行节点分裂。在执行分裂之前检查一下是否可以将要插入的tuple放置到右侧的某个节点中(例如 scankey = HK 的场景,可以将tuple插入右侧节点,从而避免执行分裂动作) { a. 如果是叶子节点且page内有垃圾可以清理,则调用 _bt_vacuum_one_page 做一次 page 的 vacuum,执行结束后检查 page 内的剩余空间是否足够插入tuple。 b. 如果 page-vaccum 后仍然不够或是不能执行 vacuum,检查是否满足以下两个条件: - 当前节点是最右侧节点 //不能继续向右查找 - Scan key != HK 或者 有0.99的概率向右移动 // 如果多个page内有相同的key,对查找而言可能需要不断向右查找。此时另一种选择是找一个靠左的节点将其分裂,然后有足够的空间插入要插入的tuple。这里向右继续查找的概率是0.99,有0.01的概率将当前节点分裂后进行插入。 如果当前节点处于分裂未完成的状态,先完成分裂动作 不满足 1、2两个条件,则表明 scan key = HK,则向右查找到一个有足够空间可以插入tuple的节点。 如果查找过程中向右移动了,则预期将tuple插入到节点的第一个位置(非最右节点是偏移是2,因为有HK,最右节点偏移是1)返回 对应的节点 以及 offset(入参传递); 如果没有向右移动,也没有执行vacuum,且当前的offset != INVALID,则 返回节点和offset; 其他情况需要在page内重新查找位置, 调用_bt_binsrch,返回 }
上述流程由于涉及节点分裂,所以看上去有点复杂,此流程主要关注读写并发的问题,分裂后面会详述。此流程是对 page 加 WriteLock,在 page 内找到插入的位置(offset)。
找到位置后,调用 _bt_insertonpg 执行插入操作 // 实现在 nbtinsert.cpp 向page内插入一个tuple,执行时需要对buffer pin + write lock,执行完成后释放pin 和 write lock; 如果插入的节点是非叶子节点,cbuf表示插入的tuple的左子节点,插入操作会清除左子节点上的BTP_INCOMPLETE_SPLIT标记(该标记表示page处于分裂为完成的状态,通常是标记在分裂后的左侧节点上,表明分裂后父节点缺少分裂后右侧节点的信息)。 { 检查不是 incomplete split page 检查page内free space 是否足够插入 tuple,如果不够 执行分裂 调用 _bt_findsplitloc 找到分裂点,执行分裂 _bt_split,在 _bt_split 完成 tuple 的插入,完成分裂后向上更新父节点 如果空间足够,调用 _bt_pgaddtup 执行插入 执行插入的 page buffer 标脏 记Xlog }
写流程中加锁顺序:
对节点加 ReadLock,获取节点信息
释放 ReadLock
加 WriteLock,执行插入操作,(可能继续执行分裂)
执行完成 Unlock
查找
_bt_search
// 实现在 nbtsearch.cpp 中,用于从B-tree的根节点开始向下查找到符合条件的叶子节点 { 获取根page _bt_getroot 调用 _bt_moveright; 如果是write-mode(插入流程查找插入位置),_bt_moveright会完成未完成的split 如果page是叶子page,则返回 否则调用 _bt_binsrch,在当前page进行查找,返回对应的item的offset。如果查找的是叶子节点,则返回的是第一个key >= scan key; 非叶子节点返回的是最后一个 key < scanKey 释放父节点的读锁,获取子节点的读锁,直到找到叶子节点。 返回一个BTStack对象(数据结构为链表,每个节点中有 block number 和 offset信息,同时还有一个指针指向父节点),如果发生分裂,可以通过此链表回溯父节点。(L&Y paper) 返回BTStack对象 }
查找流程的加锁顺序:
先对父节点加 ReadLock,然后获取子节点信息,
父节点 Unlock
子节点加 ReadLock
代码如下:
{ /* drop the read lock on the parent page, acquire one on the child */ *bufP = _bt_relandgetbuf(rel, *bufP, blkno, BT_READ); ... } Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access) { Buffer buf; Assert(blkno != P_NEW); if (BufferIsValid(obuf)) LockBuffer(obuf, BUFFER_LOCK_UNLOCK); buf = ReleaseAndReadBuffer(obuf, rel, blkno); LockBuffer(buf, access); _bt_checkpage(rel, buf); return buf; }
分裂
插入和查找流程都涉及节点的分裂问题,因此在这里有必要介绍一下分裂的实现。
分裂的主要实现也在 nbtinsert.cpp 中,主要逻辑在
_bt_split
// 分裂btree中的一个节点,只实现一个page分裂为两个page,不包括更新父节点信息部分,更新父节点的实现在_bt_insert_parent { // 分裂过程中有三个 page, 原始未分裂的 page 记为 origpage,新申请的分裂后右侧的 page 记为 rightpage,临时 page 用于记录分裂后左侧节点的数据记为 leftpage,最终需要把 leftpage 拷贝回 origpage。 _bt_getbuf 申请一个新的 index page(rightpage),并对 page 进行初始化。FSM 返回一个page后,需要对这个page进行检查确保这个page没有被其他人使用。返回之前会对 page buffer 加锁以及引用计数(lock and pin)。 初始化 leftpage,拷贝 origpage 的 LSN 到 leftpage; 拷贝 origpage 中的 special pointer 中的 flags 到 leftpage ,然后设置 leftpage 中 special pointer 的 flag。将BTP_ROOT、BTP_SPLIT_END、BTP_HAS_GARBAGE三个标记位设置为0。rightpage 此标记位设置为和 leftpage 一致。 设置是 leftpage 的 special pointer 的 flag 中 BTP_INCOMPLETE_SPLIT 设置为1,表明父节点中缺少指向其右兄弟节点的指针。设置 leftpage 和 rightpage 的 link ptr。 如果分裂的节点不是最右节点,则rightpage中的第一个位置是 HighKey,否则是 user data。 确定分裂后左右两侧的数据,将数据插入左右两侧的page 对 rightpage 加 BT_WRITE 锁,用 leftpage 的内容覆盖 origpage (除了data外,special pointer 也一起更新),将 origpage 和 rightpage 的 buffer 标脏。更新原 origpage 的右兄弟节点的 left link ptr,指向rightpage,将页面标脏。 如果分裂的是非叶子节点,节点分裂完成后清除子节点上的BTP_INCOMPLETE_SPLIT标记。非叶子节点分裂是由叶子节点分裂导致,父节点完成分裂是指向表明子节点的downlink插入完成,可以将子节点的BTP_INCOMPLETE_SPLIT标记清除// 叶子节点上BTP_INCOMPLETE_SPLIT标记清除是在父节点中插入分裂后的右侧节点的指针时完成,实现是在_bt_insert_parent -> _bt_insertonpg 记XLog }
分裂过程中的加锁顺序:
origpage 加 WriteLock, 修改数据 和 right link ptr
rightpage 加 WriteLock, 修改数据 和 link ptr
origpage 分裂前的右兄弟节点加 WriteLock, 修改 left link ptr
origpage 分裂前的右兄弟节点 Unlock
rightpage Unlock
origpage Unlock
root 分裂
L & Y 的理论中没有讨论根节点分裂的问题。OpenGauss 实现时按照普通节点分裂的方式,处理根节点的分裂。根节点分裂时,需要新生成一个根节点,原来的根节点成为新根节点的子节点,根节点分裂需要额外更新 meta-page 中根节点的信息,最终结果也是正确的。
在节点分裂时,需要通过回溯的方式来更新上层节点。但如果这个上层节点是 meta-page,那么此次回溯无法正确更新,因为 meta-page 中只是元数据不能分裂。这种情况下 B-tree 产生了新的 root,需要重新走一遍查找,直到找到刚分裂的节点的上一层,然后向右查找到正确的插入位置。这通常需要重新获取 meta-page 以及新的 root-page,可以通过保存节点在 B-tree 中所处的层号(通常叶子节点是 0 层,其父节点是 1 层,以此类推),最终找到要更新的节点所处的层。
这次主要介绍了 B_tree 索引实现与理论中的一些差异点,重点介绍了读写及分裂的流程,及其中加解锁的顺序。索引数据的删除、vacuum、WAL 等内容下次再介绍。