本文首先简单介绍了理论上B+Tree的背景；紧接着从数据索引、并发控制及故障恢复三个方向介绍了B+Tree在InnoDB中的位置以及其不可或缺的作用；之后从B+Tree上维护的行数据入手，从Record到Page，再到B+Tree的从小到大顺序介绍了B+Tree中的数据组织；然后介绍了B+Tree上对数据的查询、修改、插入及删除等操作的基本流程，以及随之带来的树结构的变化，节点分裂合并及树整体的升高降低实现。有了这个准备后，又详细的分析了B+Tree上的并发控制实现及发展过程；最后将B+Tree放回到文件中，介绍B+Tree是如何从文件中申请及释放Page空间的，以及其中的一些实现考虑。

B+Tree是很基础的数据结构，但通常在学术上讨论的时候为了简化，树上维护的数据项都会限定为简单的定长Key Value，这使得实现上对数据的访问，以及判断否需要分裂或合并等操作都非常容易，但对面向现实需求的存储引擎InnoDB来说，这样显然是不够的，再加上上面所讲到的并发控制、故障恢复的需要，InnoDB中的B+Tree数据组织上会显得复杂不少。

InnoDB采用B+Tree来维护数据，处于非常核心的位置，可以说InnoDB中最重要的并发控制及故障恢复都是围绕着B+Tree来实现的。B+Tree本身是非常基础且成熟的数据结构，但在InnoDB这样一个成熟的工业产品里，面对的是复杂的用户

structrw_lock_t是 InnoDB 读写锁的数据结构, 关键的成员变量有lock_word,waiters,recursive,writer_thread, 在我们 GDB 调试 InnoDB 代码时, print rw_lock_t 时这几个成员变量可以帮助我们理解该读写锁的持有情况./** 这个锁是否处于递归加锁的状态, 一个线程允许对一个 rw_lock 加了 SX 锁再次申请 X 锁. */. 判断当前的lock_word是否大于 X_LOCK_HALF_DECR.如果条件 1 满足就使用 CAS 减去 X_LOCK_DECR, 然后等待lock_word的值为 0./* 2. 如果这个锁已经被其他线程加了数量小于 X_LOCK_HALF_DECR 个 S 锁,/* The existing X or SX lock is from this thread */

I previously wrote a blog post to introduce the concept of MySQL B+ Tree splits and explained how to deliberately construct a highly sparse table by hacking the current rules.

MySQL 8.0 introducedinstant add columnandinstant drop columnoperations, allowing multiple data formats to exist within the same table. This added complexity makes developing external tools for record-level parsing and analysis of MySQL.ibdfiles more complex compared to versions 5.6 and 5.7.

By running this script, you can generate an extremely sparse B+Tree in an InnoDB table with just simple INSERT statements:. # Create database and table if not already existing. # 1 leaf page splits into 2 leaf pages: [1 ... 30],[31, 32, 10000001 ... 10000027]. # Insert alternating values starting from 33 to 999. The tbl table contains 2 columns: a pk and a val . Each record has the following size:.

MySQL 从8.0开始先后支持了instant add column和instant drop column，这使得搞一个可以record级别解析.ibd数据文件的外部工具不像5.6/5.7那么简单粗暴。

过去，PolarDB在处理归档的冷数据时，遇到的主要挑战之一是对数据定义语言操作的兼容性和效率问题，尤其是在执行诸如增加列、调整列宽等操作时。

PolarDB for MySQL在优化冷数据查询性能方面，聚焦于两项核心技术策略：OSS数据筛选与OSS冷数据并行查询技术。首先，OSS数据筛选机制通过利用高度针对性的列属性预处理，实现对数据对象的智能过滤。这一策略能够显著缩减数据扫描范围，避免不必要的时间消耗于无关数据的检索上，从而大幅提升查询效率与系统响应速度。另一方面，OSS冷数据并行查询技术，则是通过并发查询执行模型，即增加并发查询线程或任务的数量，来并行处理大规模数据集。此方法充分利用了现代计算资源的多核特性，实现了查询负载在多个处理单元间的均衡分配，极大缩短了查询响应时间。特别是针对数据量庞大的冷数据查询场景，该技术能够有效克服单线程处理的瓶颈，确保查询操作的高效执行与资源的最大化利用。以下详细介绍二者的使用方法和适用场景。

通过前一篇文章的介绍，我们很容易能够动态地得到某个函数的执行时延。当函数的开销只是线程内部的计算时，我们可以判断出造成函数时延较大的原因。在 MySQL 中，用户线程在提交写事务时需要等待写入的 redo 日志先落盘，确保当发生 crash recovery 后，事务能正常恢复。而 redo 日志的落盘是由多个后台线程配合的 [1]，只有后台线程 redo 日志写入的位点 达到事务提交需要的位点 时，由 log flush notifier 通知用户线程，事务才能提交。这类跨线程的开销监测依赖于程序的内部信息以及线程的上下文信息。在程序定义一些探针，由 eBPF 程序进行收集输出。最开始 BPF 是提供在内核用于网络包过滤的性能，来避免大量的上下文切换开销。Trace 期间，用户编写的程序嵌入到内核的事件回调上，当 trace 结束，将 bpf 收集的数据传回给用户态进行分析展示。为了减少 trace 的性能衰减，本文主要基于用户定义的静态 tracepoint 来分析跨线程的性能。

structrw_lock_t是 InnoDB 读写锁的数据结构, 关键的成员变量有lock_word,waiters,recursive,writer_thread, 在我们 GDB 调试 InnoDB 代码时, print rw_lock_t 时这几个成员变量可以帮助我们理解该读写锁的持有情况./** 这个锁是否处于递归加锁的状态, 一个线程允许对一个 rw_lock 加了 SX 锁再次申请 X 锁. */. 判断当前的lock_word是否大于 X_LOCK_HALF_DECR.如果条件 1 满足就使用 CAS 减去 X_LOCK_DECR, 然后等待lock_word的值为 0./* 2. 如果这个锁已经被其他线程加了数量小于 X_LOCK_HALF_DECR 个 S 锁,/* The existing X or SX lock is from this thread */

AWS reInvent 2024 刚刚结束, 笔者作为数据库从业人员主要关注的是AWS Aurora 今年做了哪些改动, 今年最大的可能就是 Aurora DSQL 的发布了.在发布会上, Matt 介绍 DSQL 将多次 commit 合并成一次 commit, 从而实现了 90% 的性能提高, 那么 DSQL 是如何实现的呢?具体做法原先一个事务中包含 10 条 SQL, 每一条 SQL 都需要和数据库交互, 需要对某一些行就先 row lock, 避免事务执行过程中被其他事务修改. 那么如果在跨 region 场景, 延迟可能到了 100ms 以上, 一个事务包含 10 条 SQL 那么就至少需要 1s 才能 commit, 那么自然很容易出现性能问题.那么在跨 region 类似 DSQL 这样场景可以使用吗?除了这个差异, 其实这里两个架构最大的区别是,在 Aurora DSQL 里面取消了每一个实例上面的cache

近几年互联网行业的降本增效浪潮愈演愈烈，如数据压缩、分级存储等技术成为了数据库产品实现降本的核心手段。作为一款云原生数据库，PolarDB 会面向大量行业、场景、需求不同的云用户，同样有必要且已经支持了这些能力。PolarDB 在全链路多个层级上实现了并正逐步商业化数据压缩能力, 如整形、字符串、BLOB 等数据格式类型的压缩，数据列字典压缩、二级索引前缀压缩，存储层的数据块软/硬件压缩等。首先要提到的必然是 MySQL 官方原生的两种压缩能力：表压缩和透明页压缩。因此，对于 PolarDB-MySQL 来说，除了官方的两种原生压缩能力，通过轻量级压缩方法实现页内/行级压缩，也是重要发展路径。本文就主要介绍 PolarDB-MySQL 引擎层的索引前缀压缩能力的技术实现和效果。由于索引的 key 部分数据存在有序性，因此对索引 key 部分进行前缀压缩往往可以取得不错的压缩效果。因此，PolarDB 这里采用的是半静态 prefix base 设计。不在 SMO 时做压缩是因为其持有 index latch 和多个 page latch，对并发操作的影响范围

我准备用两篇文章讲述 InnoDB lock manager：第一篇是 lock manager 的设计和实现，第二篇是在不同隔离级别下各种 SQL 语句的加锁方式。=

change buffer是 InnoDB 5.5 引入的一种优化策略，若二级索引页不在 buffer pool 中，则将针对二级索引页的操作暂时缓存起来，等到该页从磁盘读到 buffer pool

InnoDB 事务锁这里的代码陆陆续续看过好几次，但一直没整理过。事务锁这玩意儿思想说起来其实就那么几句话，实现起来的代码却是又臭又硬的好大一坨，各种细节，不把这里啃明白的话在解决具体问题的时候有点虚，和别人讨论也感觉隔靴搔痒说不太透。刚好趁着假期下雨，整理一个源码阅读笔记，把那一坨加锁相关的代码提炼出来，记录一下。Read Committed简单很多，另外快照读是基于MVCC不用加锁，所以不在本文讨论范畴。InnoDB 中的lock是事务中对访问/修改的record加的锁，它一般是在事务提交或回滚时释放。for update及update操作，这3个操作分别对应3个mtr，每个mtr完成：。在InnoDB的实现中，并没有一个一下锁住某个指定区间的锁，而是把一个大的区间锁拆分放在区间中已有的多个record上来完成。接下来从源码实现上来分别看下Insert和Select是如何加lock的，结合着看也就知道InnoDB的RR是如何实现的了。

使用 perf 等剖析工具采集程序栈，分析 CPU 上的活动，然后找到程序的热点。火焰图解决了剖析信息长且很很难读的问题，使用调用栈信息生成可视化的展示出 CPU 上的热点。在 CPU 密集的场景，on-CPU 分析通常可以快速定位到热点函数。off-CPU 火焰图只包含线程阻塞的调用栈，在复杂的程序中，仅使用 off-CPU 分析可能缺少必要的必要的上下文来更精确的定位到具体的性能瓶颈。On-CPU 和 off-CPU 分析是互补的。冷热火焰图提供了结合 on-CPU 火焰图和 off-CPU 火焰图的方案，其中eflame提供了一个理想的解决方案。eflame 可以整合两种火焰图，生成程序的挂钟时间火焰图。但是这个工具是针对 Erlang 设计的，不适用于通用的场景。但是，pstack 等打印调用栈的工具通常速度比较慢，并且会短暂的影响程序运行，不适合长时间反复调用。Intel PT 是 intel 处理器上专门用于追踪处理器执行流的硬件，能以较低的开销、非常高的时间精度完整的记录处理器执行历史。因为 trace 是按照线程回放的，不管是 on-CPU 时间还是 off-CPU 时间都会统计在内。

在上一篇文章PT_PERF: 基于 Intel PT 的时延性能分析工具中，我们介绍了 Intel Processor Trace 时延分析工具的背景，功能和实现。本篇文章我们主=

程序性能一直是开发人员和用户特别关注的指标，但其调优分析也是最为艰难的一个过程。作为系统研发人员，我们会花费大量时间来分析系统的性能瓶颈、定位开发过程中引入的性能回退，并解决可能周期性发生的性能抖动问题。根据线程的执行模型，即是否调度在 CPU 上执行指令，我们通常会从 on-CPU 和 off-CPU 两个角度进行分析[1]。而 off-CPU 分析则关注那些不在 CPU 上执行指令的时间，比如等待磁盘 I/O、锁或网络传输等资源。CPU 是负责执行指令的核心部件。通过在一定频率下的采样，尤其是在 CPU 密集型负载下，我们可以确定大部分的性能瓶颈所在。然而，在非 CPU 密集型的场景下，比如大量 IO 操作、等待锁或主动休眠等情况，CPU 利用率很低。为了实现这一点，这依赖于硬件提供的程序 trace 功能。基于 Intel PT 的程序 trace 技术，我们实现了 PT_PERF 的时延分析工具，使用 PT 的 trace 数据来显示程序执行的关键信息如函数时延，时延曲线，时延火焰图等信息。

Cache Aside模式下，持久化层和缓存层的一致性问题主要是“双写”，即数据既在数据库中保存一份，又在缓存中保存一份，通过应用侧来维护两份数据的一致性。为了面向在线业务场景构建一套完整的数据库+缓存的解决方案，实现对在线业务场景的数据访问、存储和加速，为客户提供一站式的解决方案，PolarDB MySQL版推出了数据与缓存一站式的功能。PolarDB MySQL版数据与缓存一站式的功能中，将Tair作为PolarDB集群的RO节点——Tair缓存节点，并向用户提供关系型数据库和缓存的一站式解决方案。丰富的PolarDB产品能力：提供PolarDB+Tair的能力，同时提供关系型数据库+Key-Value等NoSQL数据库的能力，利用Tair丰富的数据结构，满足多样化的业务场景。对于Redis和PolarDB MySQL版Tair缓存节点，QPS表示每秒执行的查询数。由于Sysbench的输出中只能指定一个分位点，本测试中指定为95%，因此PolarDB MySQL版普通只读节点的测试结果中不包含该指标。

In our user environment, we find deadlock cause by this example.

云数据库实现计算存储分离，支持计算与存储的独立扩展，其用户还可以享受按量付费等特性。这使得基于云数据库的系统更加高效、灵活。因此，构建并使用云原生数据库的势头愈演愈烈。另一方面，云化存储服务已经是云的标准能力，存储侧提供兼容通用的文件接口，并且不对外暴露持久化、容错处理等复杂细节，其易用性和规模化带来的高性价比使得云存储成为了云上系统的第一选择。在通用云存储服务上构建云数据库，无疑是一种既能够享受规模化云存储红利，又能够通过可靠云存储服务实现降低维护成本、加速数据库开发周期的方案。对此，我们在论文里分析了基于B-tree和LSM-tree的存储引擎在云存储上部署时面临的挑战，并提出了一个优化框架CloudJump，以希望能够帮助数据库开发人员在基于云存储构建数据库时使系统更为高效。我们以云原生数据库PolarDB为案例，展示了一系列针对性优化，并将部分工作扩展应用到基于云存储的RocksDB上，以此来演示CloudJump的可用性。

本文主要介绍Undo Segment 的申请流程，以及后续的Insert Undo Record 和Update Undo Record 的写入流程。Innnodb 内部对于Undo Record 分为 Insert 类型和Update 类型， 对于Delete 操作是包含在Update 类型当中的。Undo Record 的格式由于历史原因修改的版本比较多，看起来比较繁琐，

Blob 在做partial update 并且符合small change 记录到undo record ，之后如果读请求走mvcc 读到这个undo record 的时候有概率造成crash。UPDATE t SET b = JSON_REMOVE where a = 1;对于Blob 字段进行partical update，由于是small change ，binary diff 记录到了undo record 里面。很明显这里的处理流程有问题。修复的方法也比较直接，只要不更新lob_undo_data 的m_old_data 字段就可以了。

列压缩是针对某一列非常长的一种压缩策略，通常可压缩列类型为varchar，BLOB等类型。其最早由印风在AliSQL 实现并且提供给了Percona社区。