索引中的谓词锁 GSoC 2017
此页面包含项目“在除 B-tree 之外的索引访问方法中显式支持谓词锁”的结果,以供将来参考。有关 GSoC 评估,此信息收集在 https://sites.google.com/view/shubham-gsoc-2017/home
项目标题
显式支持在除 B-tree 之外的索引访问方法中使用谓词锁。
作者:Shubham Barai
项目描述
可序列化隔离实现策略
几十年来,在许多数据库产品中已经发布并使用了实现完全可序列化隔离的技术。主要的技术是严格两阶段锁定 (S2PL),其通过阻止对并发事务读取的数据进行写入以及阻止对并发事务写入的数据进行任何访问(读取或写入)来运作。阻塞图中的循环表示死锁,需要回滚。高争用工作负载下的 S2PL 阻塞和死锁可能是灾难性的,会严重影响吞吐量和响应时间。从 2008 年开始,文献中出现了一种在 MVCC 数据库中实现完全可序列化隔离的新技术。这种技术被称为可序列化快照隔离 (SSI),它具有快照隔离的许多优点。特别是,读取不会阻塞任何内容,写入也不会阻塞读取。本质上,它运行快照隔离,但监视事务之间的读写冲突,以识别事务图中的危险结构,这些结构表明一组并发事务可能会产生异常,并回滚事务以确保不会发生异常。它会产生一些误报(即使不会发生异常,也会回滚事务),但永远不会让异常发生。在两个已知的原型实现中,许多工作负载的性能(即使需要重启回滚的事务)非常接近快照隔离,通常远远优于 S2PL 实现。
谓词锁定
S2PL 和 SSI 都需要某种形式的谓词锁定来处理读取与后续插入或将数据移动到选定范围内的后续更新发生冲突的情况。PostgreSQL 之前没有谓词锁定,因此需要添加它以支持两种策略下的完全可序列化事务。谓词锁定的实际实现通常涉及在访问数据时获取对数据的锁,使用多粒度(元组、页、表等)并在需要时进行升级,以将锁计数保持在可以在 RAM 结构中跟踪的范围内。这种方法在 PostgreSQL 中使用。粗粒度可能会导致一些误报冲突。误报的数量会受到计划选择的影響。当前实现及其限制 目前,只有 B+-树支持页面级谓词锁定。对于其他索引,它获取关系级锁,这会导致不必要的序列化失败,这是由插入索引引起的 rw 依赖造成的。项目目标 本项目的主要任务是支持剩余索引的页面级谓词锁定,包括 Gist、SP-Gist、哈希、gin 和 rum 索引。页面级谓词锁定的优点 页面级谓词锁定可以通过减少导致不必要的序列化失败的误报数量,在可序列化隔离级别提供更好的性能。
项目实现
1. Gist 索引
GiST 代表广义搜索树。它是一种平衡的树状结构访问方法,充当实现任意索引方案的基模板。B-树、R-树和许多其他索引方案可以在 GiST 中实现。在搜索目标元组时,b-tree 和 gist 索引之间的主要区别在于,在 gist 索引中,我们可以在索引的任何级别确定是否存在匹配。在 gist 中,内部节点的索引条目包含一个谓词,该谓词用作搜索键来搜索该节点可到达的所有元组。要将元组插入索引,我们首先检查表示目标子树的键。如果它不包含我们要插入的键,则必须用旧键和我们要插入的键的并集替换它。考虑到所有这些因素,在每个索引级别获取谓词锁似乎是合乎逻辑的。
谓词锁定策略
在扫描期间,我们在每个索引级别的页面(内部或叶)上获取谓词锁。然后,可以信任叶级别的索引插入会向上级联到可能存在冲突谓词锁的所有级别和位置。如果在插入期间发生拆分,则会将谓词锁从原始页面复制到拆分过程中生成的每个新页面。链接:提交节上的补丁 GitHub 上的代码
2. SP-Gist 索引
SP-GiST 是空间分区 GiST 的缩写。它为实现空间分区数据结构(如四叉树、k-d 树和基数树)提供了一个通用基础架构。从逻辑上讲,SP-GiST 树是一组元组,每个元组可以是内部元组或叶元组。每个内部元组包含“节点”,它们是 (标签,指针) 对,其中指针 (ItemPointerData) 是指向另一个内部元组或指向叶元组列表头的指针。内部元组可以有不同数量的节点(子节点)。分支可以具有不同的深度(实际上,没有控制或代码来支持平衡),这意味着树是非平衡的。但是,叶元组和内部元组不能在同一级别混合:从内部元组的节点向下链接要么指向一个内部元组,要么指向叶元组列表。
谓词锁定策略
当搜索遍历算法到达一个内部元组时,它会选择一组节点以在深度上继续遍历树。如果它到达一个叶页面,它会扫描一个叶元组列表以找到与查询匹配的元组。与 Gist 不同,SP-Gist 无法在索引的内部级别确定是否存在匹配。因此,对于 SP-Gist 搜索,对叶页面的谓词锁就足够了。如果在插入期间发生拆分,则会将谓词锁从原始页面复制到拆分过程中生成的每个新页面。
链接:提交节上的补丁 GitHub 上的代码
3. 哈希索引
哈希索引包含两个或多个“桶”,每当元组的哈希键映射到桶号时,元组就会被放置到这些桶中。键到桶号的映射是选择的,以便索引可以增量扩展。当要向索引添加一个新的桶时,需要对一个现有的桶进行“拆分”,并将其中一些元组根据更新的键到桶号的映射转移到新的桶中。哈希索引中的每个桶包含一个或多个索引页面。桶的第一个页面(称为主页面)在创建桶时永久分配给它。如果桶接收的元组太多,无法容纳在主桶页面中,则会添加附加的页面,称为“溢出页面”。桶的页面使用索引页面特殊空间中的字段在双向链表中链接在一起。
谓词锁定策略
在扫描操作期间,在桶的主页面上获取谓词锁。在插入操作期间,检查桶的主页面上是否存在任何冲突的谓词锁。在桶拆分的情况下,将谓词锁从旧桶的主页面复制到新桶的主页面。链接:提交节上的补丁 GitHub 上的代码
4. Gin 索引
Gin 代表广义倒排索引。广义意味着索引不知道它在加速哪种操作。相反,它使用为特定数据类型定义的自定义策略(在 PostgreSQL 文档中阅读“索引方法策略”)。从这个意义上说,Gin 类似于 GiST,不同于具有预定义的基于比较的操作的 b-tree 索引。Gin 索引包含一个构建在键值上的 B-tree 索引,其中每个键都是一些索引项的元素(数组元素、tsvector 的词素),并且其中叶页面中的每个元组包含指向 B-tree 的指针(发布树),或者如果列表足够小,则包含简单的项目指针列表(发布列表)。
谓词锁定策略
Gin 索引具有一项称为快速更新的功能,它通过将元组临时存储到挂起列表中来推迟元组的插入。挂起列表最终会在 vacuum 期间被刷新。因此,这会造成一个问题,因为即使扫描在挂起列表上获取了页面级谓词锁,我们也无法检测到 rw 冲突,因为新的插入只会将元组追加到挂起列表上。因此,在启用快速更新时,页面级谓词锁定是不可能的。因此,如果启用了快速更新,则需要在索引关系上获取谓词锁。否则,Gin 搜索只需要在叶页面上获取谓词锁,无论是条目树还是发布树。在页面(非根)拆分期间,会将谓词锁从原始页面复制到新页面。如果根(关系中的唯一节点)被拆分,则会将谓词锁从根页面复制到两个(左和右)新页面。
链接:提交节上的补丁 GitHub 上的代码
5. Rum 索引
rum 模块提供了访问方法来处理 rum 索引。它基于 gin 访问方法。与 gin 不同,rum 不支持快速更新。Gin 索引允许使用 tsvector 和 tsquery 类型执行快速的全文搜索。但是,使用 GIN 索引进行全文搜索存在几个问题:1. 缓慢的排名。需要有关词素位置的信息来进行排名。Gin 索引不存储词素的位置。因此,在索引扫描之后,我们需要额外的堆扫描来检索词素位置。2. 使用 gin 索引进行缓慢的短语搜索。这个问题与上一个问题有关。需要位置信息才能执行短语搜索。3. 按时间戳进行缓慢排序。Gin 索引无法在索引中使用词素存储一些相关信息。因此,需要执行额外的堆扫描。Rum 通过在发布树中存储附加信息来解决这些问题。例如,词素的位置信息或时间戳。
谓词锁定策略
Rum 具有与 gin 索引类似的谓词锁定策略,除了 rum 不支持快速更新,因此我们不必担心获取关系级锁。
链接:指向拉取请求的链接
联系
感谢 PostgreSQL
我要感谢 PostgreSQL 给予我参与这个项目的机会。我还想感谢我的导师 Andrey Borodin 在整个项目中给予我大力支持。能够成为 PostgreSQL 社区的一员并从你们所有人那里学习是一段美妙的经历。我希望将来能继续为 PostgreSQL 做出贡献。