POLARDB · B+树并发控制机制的前世今生

2020-05-27 00:00:00 修改 操作 节点 并发 结构

前言

1970年，Rudolf Bayer教授在《Organization and Maintenance of Large Ordered Indices》一文中提出了B树[1]，从它基础上演化产生了B+树。B+树采用多叉树结构，降低了索引结构的深度，避免传统二叉树结构中绝大部分的随机访问操作，从而有效减少了磁盘磁头的寻道次数，降低了外存访问延迟对性能的影响。它保证树节点中键值对的有序性，从而控制search/insert/delete/update操作的时间复杂度在O(log(n))的范围内。鉴于上述优势，B+树作为索引结构的构建模块，被广泛应用在大量数据库系统和存储系统中，其中就包括MySQL。

索引结构作为影响系统性能的关键因素之一，对数据库系统在高并发场景下的性能表现具有重大的影响。从上世纪70年代B+树提出至今，学术界有大量论文尝试优化B+树在多线程场景下的性能，这些文章被广泛发表在数据库/系统领域会议VLDB/SIGMOD/EuroSys上。然而，由于过长的时间跨度（1970s-2010s，40多年时间），目前网络上缺乏讨论B+树并发机制的较为系统的分析文章，尤其在中文文章方面。本文尝试选取不同时间点上几个具有代表性的研究工作，分析B+树并发控制机制的发展过程，探讨B+树并发机制在MySQL中的发展及优化。由于篇幅和时间限制，本文的部分观点可能尚不完善，欢迎读者指正。读者也可根据文章末尾的引用论文，深入阅读相关工作。

  • B+树的数据结构及基础操作
  • B+树并发控制机制的基本要求
  • B+树并发控制机制的发展历程（从1970s至今）
  • Mysql5.7的B+树并发控制机制
  • Lock-Free B+树 & 总结

B+树的数据结构及基础操作



一棵传统的B+树需要满足以下几点要求：

  • 从根节点到叶节点的所有路径都具有相同的长度
  • 所有数据信息都存储在叶节点上，非叶节点仅作为叶节点的索引存在
  • 根结点至少拥有两个键值对
  • 每个树节点多拥有M个键值对
  • 每个树节点（除了根节点）拥有至少M/2个键值对

一棵传统的B+需要支持以下操作：

  • 单键值操作：Search/Insert/Update/Delete（下文以Search/Insert操作为例，其它操作的实现相似）
  • 范围操作：Range Search

由于篇幅所限，本文假设读者对B+树的基础结构和操作原理有一定的了解，仅对B+树的基本结构和操作做简单介绍，有需求的读者可根据引用[1]的文章自行阅读。

B+树并发控制机制的基本要求

按照笔者的理解，正确的B+树并发控制机制需要满足以下几点要求：

  • 正确的读操作：
    • R.1 不会读到一个处于中间状态的键值对：读操作访问中的键值对正在被另一个写操作修改
    • R.2 不会找不到一个存在的键值对：读操作正在访问某个树节点，这个树节点上的键值对同时被另一个写操作（分裂/合并操作）移动到另一个树节点，导致读操作没有找到目标键值对
  • 正确的写操作：
    • W.1 两个写操作不会同时修改同一个键值对
  • 无死锁：
    • D.1 不会出现死锁：两个或多个线程发生堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源

不管B+树使用的是基于锁的并发机制还是Lock-Free的并发机制，都必须满足上述需求。在下文中，本文将针对不同的并发机制，分别阐述它们是如何满足上述要求，并达到了什么样的优化效果。

B+树并发控制机制的发展历程（从1970s至今）

本文使用的一些标记

首先，介绍本文伪代码中需要使用的一些标记。

  • SL (Shared Lock): 共享锁 — 加锁
  • SU (Shared Unlock): 共享锁 — 解锁
  • XL (Exclusive Lock): 互斥锁 — 加锁
  • XU (Exclusive Unlock): 互斥锁 — 解锁
  • SXL (Shared Exclusive Lock): 共享互斥锁 — 加锁
  • SXU (Shared Exclusive Unlock): 共享互斥锁 — 解锁
  • R.1/R.2/W.1/D.1: 并发机制需要满足的正确性要求
  • safe nodes：判断依据为该节点上的当前操作是否会影响祖先节点。以传统B+树为例：(1) 对于插入操作，当键值对的数量小于M时，插入操作不会触发分裂操作，该节点属于safe node；反之当键值对数量等于M时，该节点属于unsafe node；（2）对于删除操作，当键值对的数量大于M/2时，不会触发合并操作，该节点属于safe node；反之当键值对数量等于M/2时，该节点属于unsafe node。当然，对于MySQL而言，一个节点是否是安全节点取决于键值对的大小和页面剩余空间大小等多个因素，详细代码可查询MySQL5.7的btr_cur_will_modify_tree()函数。

基础并发控制机制（MySQL5.6）

MySQL5.6以及之前的版本采用了一种较为基础的并发机制：它采用了两种粒度的锁：（1）index粒度的S/X锁；（2）page粒度的S/X锁（本文等同于树节点粒度）。前者被用来控制对树结构访问及修改操作的冲突，后者被用来控制对数据页访问及修改操作的冲突。下文将以伪代码的形式详细分析读写操作的过程。

/* Algorithm1. 读操作 */
1.   SL(index)
2.   Travel down to the leaf node
3.   SL(leaf)
4.   SU(index)
5.   Read the leaf node
6.   SU(leaf)

相关文章