关于后端:PolarDB-Btree-并发控制优化

简介：PolarDB 解决了 InnoDB 在 B-tree 并发管制上的限度，解决 index lock 竞争问题，并反对了 latch coupling。InnoDB 索引 InnoDB 引擎应用索引组织表，每个表的数据都放在一个对应的索引中，该索引称为汇集索引（clustered index），应用索引组织表的目标是：动静地组织磁盘文件构造，保护数据记录有序；借助索引疾速定位记录；除了 clustered index，一个表中的其它索引称为二级索引（secondary indexes）。二级索引的每个 record 除了蕴含自身的 columns，还蕴含其对应的数据行的 primary key，InnoDB 能够利用 primary key 去主索引找到残缺的 row。InnoDB 应用 B-tree 作为索引的数据结构，B-tree 实质是多级索引，扁平且均衡的树结构能够保障单次访问数据的 IO 次数较小且固定。InnoDB 实现的 B-tree 构造有几点个性：理论数据全副存储在 leaf 层（即 B+ tree，升高树高度、优化程序拜访）；non-leaf 层只存储索引项（key, page no），每个索引项指向惟一一个 child 节点；一个索引项的 key 为 P，它的 child 节点只能存 >= P 并且 < P1 的记录，其中 P1 是下一个索引项的 key；每层节点通过双向链表串起来；B-tree 并发管制如果把 B-tree 索引看成一个黑盒，不关怀外部具体的数据结构，里面看来只有有序排列的 record，所有的读取、插入、删除等操作都能原子地一步实现。这时多线程并发操作不会感知到索引构造，只须要思考事务层面的束缚，例如 InnoDB 中一个事务对 record 加逻辑锁（lock）阻止其它事务拜访。然而理论的 B-tree 操作不是原子的，例如，一个线程在做结构调整（SMO）时会波及多个页面的改变，此时另外一个线程进来会拜访到不正确的 B-tree 构造而产生谬误，另外，页面外部的数据结构改变也不能多线程并发执行。InnoDB 是采纳 page 加锁的形式对 B-tree 进行并发管制，每个 page 有一个对应的物理读写锁（rw latch），线程读取一个 page 要先加 S latch，批改 page 时要加 X latch。因为 B-tree 索引的拜访和批改流程是确定的，所以 InnoDB 有一套设计好的加锁规定，避免多线程死锁。与之对应的是，事务锁（lock）是用户层面的，加锁程序不可控，因而须要死锁检测机制。并发瓶颈 InnoDB 对 B-tree 的并发管制实现细节能够参考 InnoDB btree latch 优化历程 这篇文章，能够看到屡次优化改良的目标都是为了进步 B-tree 的并发拜访能力，即尽量减小每个操作的加锁范畴和工夫。目前 8.0 版本在 B-tree 并发上还有一些限度：SMO 无奈并发：同一时刻只容许有一个 SMO 进行（SMO 线程持有 index SX latch），导致在大批量插入场景下 index latch 会成为全局的瓶颈点，MySQL 官网性能测试人员 Dimitrick 也指出 TPCC 场景下最大的瓶颈在于 index lock contention（MySQL Performance : TPCC “Mystery” [SOLVED]）。构想一下，如果将这个限度放开，多个做 SMO 的线程会同时进入 B-tree，每个线程要拿多个 page，如何设计加锁规定防止线程间死锁，有很多细节须要解决。加锁范畴大：为了防止死锁，乐观读写操作要持有遍历门路上所有 non-leaf page 的 S latch，SMO 操作要持有所有可能批改的 page 的 X latch。繁多操作的加锁范畴比拟大，并发操作越多越会加剧锁竞争，在某些要害节点（例如，root、internal node）的竞争会更显著。实践上采纳 latch coupling 的形式能够减小加锁范畴，遍历过程中最多同时持有 2 个 page 的锁（即沿着一个指针从一个节点到另一个节点时，不能有其余线程去扭转这个指针，因而要拿到后一个节点的 latch 再放开前一个 latch），有利于升高并发操作的竞争。PolarDB 并发管制优化 PolarDB 解决了 InnoDB 在 B-tree 并发管制上的限度：晋升并发度：去除 index 锁，容许所有操作并发拜访 B-tree，线程间抵触只在 page 级别；升高锁粒度：所有操作都实现了 latch coupling，减小锁范畴，大大降低线程间抵触；PolarDB 设计了页级别的 B-tree 并发管制，对索引页的加锁规定如下：规定 1：所有操作采纳 latch coupling 模式遍历 B-tree，遍历过程中对非指标节点加 S latch（相当于读取节点指针），直到找到指标节点，依据操作读 / 写类型对指标节点加 S latch 或 X latch（SMO 操作波及街坊节点更新，还须要加左右街坊节点的 latch）；为了防止死锁，规定加锁方向为，自上而下，从左到右。而 SMO 操作是自下而上的，即 SMO 的加锁方向是毁坏规定的，会造成死锁（InnoDB 的 SMO 操作不应用 latch coupling 形式，开始就从上到下拿到所有相干节点的 latch，从而防止死锁）。规定 2：在 SMO 操作两头，申请父节点或左街坊节点的 latch 之前，对以后持有 X latch 的 page 做 SMO 标记，并开释这些 latch。这里借鉴了 B-link 的设计，将 SMO 操作划分为两个阶段，第一阶段实现提前开释 latch，防止了 SMO 操作反向加锁。这样，在 SMO 中间状态没有持有任何 latch。SMO 中间状态节点设置一个指向其右侧节点的指针（side link），其它读操作拜访到 SMO 中间状态的节点，并能够同时在其 right page 中检索，解决了 B-tree 构造不残缺的问题。其它写操作不应该批改处于 SMO 中间状态的节点，因为之前 SMO 操作还没提交。因而，其它线程的写操作遇到 SMO 节点，要期待其 SMO 实现。规定 3: 其它线程遍历到有 SMO 标记的节点，并想要批改该节点时：立刻开释掉已持有的 latch，期待该节点 SMO 实现再从 root 重试；如果其它线程不开释已持有的 latch，相当于跟 SMO 线程之间相互占有并期待，造成死锁。性能比照采纳上述的 B-tree 并发管制机制，在高并发 TPCC 场景（1000 warehouse）下：当并发小于 64 时，InnoDB 与 Polar index 性能后果靠近，InnoDB 在并发 128 时达到性能峰值；Polar index 在并发 256 时达到峰值，能够看到 Polar index 相比于 InnoDB，峰值进步 141%；

原文链接:https://click.aliyun.com/m/10… 本文为阿里云原创内容，未经容许不得转载。