作者：姜承尧等
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
MySQL内核：InnoDB存储引擎（卷1）试读：
前言
为什么要写这本书过去这些年，我一直在和各种不同的数据库打交道，见证了MySQL从一个小型的关系型数据库发展成为各大互联网企业的核心数据库系统的过程。期间我参与了一些大大小小的项目开发工作，成功地帮助开发人员构建了一些可靠的、健壮的应用程序。在这个过程中积累了一些经验，正是这些不断累积的经验赋予了我灵感，于是有了本书。这本书实际上反映了这些年来我做了哪些事情，汇集了很多同行每天可能都会遇到的一些问题，并给出解决方案。
本书是MySQL内核系列的第一本书，与之前出版的MySQL技术内幕不同的是，该系列的书将更靠近数据库内核层面，揭示MySQL数据库内核是如何运行的。MySQL内核系列的第一本书将从InnoDB存储引擎的内核来展开。
毫无疑问，InnoDB存储引擎已经成为MySQL数据库的“标准配置”。Facebook、Twitter、Yahoo、百度、淘宝、腾讯、网易这些互联网公司都将InnoDB作为后台的存储引擎。在时间的长河以及线上高并发验证下，其已经被证明是高性能、高可扩展性的引擎。
身处数据库这个圈子，可以明显地感觉到从2010年开始，各大互联网公司已经不再满足于仅仅使用InnoDB存储引擎，他们开始越来越接触到引擎的内核层面，对引擎进行内核级别的优化以及根据公司的业务需求进行二次开发。即使是DBA本身也开始慢慢地不满足现状开始研究起InnoDB存储引擎的内核，似乎一夜之间不了解点内核实现都不好意思和别人说你是搞MySQL数据库的。
当然，我们需要感谢MySQL数据库，感谢MySQL数据库的创始人和InnoDB存储引擎的创始人。正是他们开源了这些代码，使得我们这些后人可以站在巨人的肩膀上继续学习与进步。在这方面，MySQL/InnoDB比其他数据库都要伟大，更值得我们尊敬。
不可否认的是，国内对于数据库内核的开发学习资料与课程都非常有限。本科阶段几乎没有相关课程，仅特定数据库研究方向的研究生才会去关注这些技术，并且这些人才在国内非常稀少。很多想要踏进数据库内核领域的人在最初都会感到迷茫和无助。
另外，有些人凭着自己的聪明与天赋看似掌握了内核的实现，但是从他们的博客描述来看，其离真正的理解还是有一些距离的，或者说他们仅刚入门。所以我们才会在网上看到不断有人在翻阅过代码后，或者简单设置了几个断点和调试后抱怨InnoDB存储引擎的设计是多么烂。
其实数据库的世界并不如他们想象的那样简单与粗糙，数据库有着自己的理论体系。虽然数据库的实现有很多种，但大多需要遵循一些理论规范，如Fix Rules、Write-Ahead Log、Force-log-at-commit、Lock等。
我从2006年就开始进行数据库的内核开发，现在想来还最多只能称为hack。我在内核开发的路上走了很多弯路，经过高人的指点以及自己不断的学习与探索，终于有了一些经验，现通过本书来完整地展示给读者。希望通过MySQL内核系列，使正在通往或已经在数据库内核开发道路的人员少走弯路。
出于这个目的，我联合了网易MySQL技术组的各位同事，完成了InnoDB存储引擎卷1的书籍撰写工作。其中第1、3、4、5、7、8、9、10、11章由我个人独立完成，第2和第14章由我和温正湖共同完成、第6和第12章由我和饶珑辉共同完成、第13和第15章由我和蒋鸿翔共同完成。
在每章的最后，我还给出了思考题以及继续阅读的参考资料，通过这部分的内容，读者可以加深对于每个知识模块的理解，并继续对某一模块进行深入研究。读者对象
本书面向的读者群：
• 数据库管理员
• 数据库架构设计师
• 数据库内核开发人员
• 其他对数据库内核感兴趣的开发人员如何阅读本书
本书一共有15章，每章都像一本“迷你书”，可以单独成册。用户可以有选择地阅读，但是更推荐根据本书的组织方式进行阅读，这样会更具有条理性。第1章 概览
本章首先介绍了MySQL数据库以及InnoDB存储引擎的历史，之后介绍了InnoDB存储引擎的源码结构与代码风格，最后推荐了阅读InnoDB存储引擎源码的次序。第2章 基本数据结构与算法
本章对InnoDB中常用的数据结构和算法进行了介绍。首先是InnoDB的内存管理系统，从内存管理机制、内存操作基元和内存池及内存区等概念着手进行了详细讲解；之后是哈希表结构，介绍了简单哈希表和带链哈希表两种；然后介绍了双链表结构；最后还介绍了动态数组、标准排序函数。本章的内容是InnoDB的基础，相信读者在阅读后续章节的代码时一定会遇到本章所提的相关数据结构与算法。第3章 同步机制
本章介绍了InnoDB存储引擎中实现的同步机制mutex和rw-lock。InnoDB存储引擎正是通过这些数据结构才能完成正确并发控制的。第4章 重做日志
本章首先介绍与重做日志模块相关的概念，之后具体分析了InnoDB存储引擎重做日志模块的实现。InnoDB存储引擎原先就支持组提交，因此有着相当不错的性能。最后，根据之前所介绍的内容，分析了如何通过重做日志进行有效恢复，从而实现事务系统持久性的要求。第5章 mini-transaction
本章介绍了数据库中的三个协议：FIX Rules、Write-Ahead Log、Force-Log-at-commit，同时介绍了InnoDB存储引擎中mini-transaction的实现，并通过一个示例简单展示了mini-transaction产生的重做日志内容。第6章 存储管理
本章介绍了InnoDB存储引擎的物理存储方式，这包括表空间的构成，段、区、页的存储管理。此外，还介绍了InnoDB存储引擎的文件操作方式，包括文件操作的架构设计、同步读/写方式和异步读/写方式，分别介绍了Windows操作系统、Posix操作系统以及InnoDB模拟的三种异步I/O的实现方法。第7章 记录
本章介绍了InnoDB存储引擎的记录（record），使读者了解在源码中记录可以分为物理记录与逻辑记录，以及各种记录所使用的场合。第8章 索引页
本章介绍了InnoDB存储引擎的索引页，知道在源码中页可以分为物理页与逻辑页，并且详细分析了page header以及page directory。此外，还对InnoDB存储引擎如何在页中进行记录的定位、插入和删除等操作进行了详细介绍。第9章 锁
本章介绍了InnoDB存储引擎锁的实现技术。在InnoDB存储引擎中，其通过next-key locking算法在事务隔离级别REPEATABLE READ实现了完全的隔离性要求。此外，其对锁的设计是一种极其高效的设计方式。每个内核开发人员都应该细读lock模块，从而更为深入地理解锁的内部实现。第10章 B+树索引
本章对InnoDB存储引擎的B+树索引实现做了十分详细的介绍。该部分所需要涉及的内容非常多，与前面章节的联系也比较紧密，是一个极为重要的章节。希望读者可以反复阅读，从而更好地体会InnoDB存储引擎中B+树索引的实现。第11章 Insert Buffer
本章介绍了InnoDB存储引擎中Insert Buffer的实现，首先介绍了Insert Buffer的基本概念，然后介绍了Insert Buffer的物理与逻辑存储结构，并通过一个示例进行展示。最后，介绍了Insert Buffer的源码实现。我认为这个模块是难度最大的模块之一。第12章 缓冲池
本章介绍了InnoDB存储引擎缓冲池的实现，这包括缓冲池的管理、页的读取和页的刷新。此外，还介绍了InnoDB存储引擎使用midpoint insertion strategy LRU的LRU管理机制。第13章 事务处理
本章介绍了InnoDB存储引擎的事务处理模块，介绍了InnoDB存储引擎对于undo记录的存储方式，这其中涉及事务系统段、回滚段、undo段、undo页、undo日志、undo记录等多个概念，读者应该好好地理清这些概念。此外，还讲述了事务的purge、rollback、commit等操作的具体实现。相信通过本章的学习读者可以了解如何设计一个高效的事务系统。第14章 数据字典
本章介绍了InnoDB存储引擎对于数据字典的具体实现，以及其与之前各章的联系。第15章 服务管理
本章介绍了InnoDB存储引擎各服务模块的管理，并展示了这些服务模块的具体实现。勘误和支持
由于水平有限，编写时间仓促，书中难免会出现一些错误或不准确的地方，恳请读者批评指正，我将尽力在线上为你提供最满意的解答。如果你有更多的宝贵意见，也欢迎发送邮件至邮箱jiangchengyao@gmail.com，期待能够得到你最真挚的反馈。致谢
感谢网易研究院的所有同事们，能与一群才华出众的人一起工作让我感到非常荣幸与自豪，同时通过不断地与他人的交流，使我在数据库方面得到了极大的提升和领悟。
感谢电子工业出版社博文视点公司的孙学瑛老师，她在这段时间内始终支持我的写作，正是她的鼓励和帮助引导我顺利完成全部书稿。
谨以此书献给我最亲爱的家人，以及众多热爱MySQL数据库的朋友们！姜承尧（David Jiang）2014年3月于中国杭州第1章概览1.1 InnoDB存储引擎历史
毫无疑问，InnoDB存储引擎是一款伟大的数据库产品，虽然严格意义上来说其只是数据库的一款引擎。但其在数据库从业人员眼中，特别是MySQL数据库相关从业人员心中，犹如Linux操作系统在许多程序员心中那样神圣而不可侵犯。
或许用户已经耳熟能详关于InnoDB存储引擎在各大互联网公司核心生产环境中的应用，如Twitter、Facebook、Google、网易、淘宝、百度等公司。但以古为鉴，可以知兴衰。数据库行业同样也不例外，历史就是一面镜子，通过历史可以让读者更深入地了解InnoDB存储引擎的发展，理解其真正的与众不同与伟大之处。
Heikki Tuuri是InnoDB存储引擎的创始人，1964年生于芬兰赫尔辛基。与著名Linux操作系统的创始人Linus一样毕业于芬兰赫尔辛基大学。从入学时间来看，Heikki Tuuri还是Linus的学长。在1990年取得赫尔辛基大学的数理逻辑博士学位后，Heikki Tuuri于1995年成立Innobase Oy公司并担任CEO。
从公司发展来看，Innobase也是波澜起伏，有惊无险，最终被纳为Oracle公司旗下的一个部门。现在，要翻阅InnoDB存储引擎的源码是非常容易和简单的，打开MySQL数据库官网，下载源码包，用户通过自己最为熟悉的源码查看工具，如sourceinsight、vim、Visual Studio亦或Eclipse等，就能阅读InnoDB存储引擎的源码。然而在最初开始阶段，InnoDB存储引擎却是一款闭源（closed source）的产品。
在公司创业初期，Innobase公司一直在寻找买家。事与愿违的是Heikki Tuuri迟迟未能找到买家。然而MySQL数据库的出现却给了Heikki Tuuri另一种发展考虑。因此在2001年，Innobase公司开始与MySQL AB公司进行合作并开源InnoDB存储引擎的代码。
随着MySQL数据库的盛行，InnoDB存储引擎也开始崭露头角。并且在与MySQL AB公司自有存储引擎MyISAM的比较中，在与BDB存储引擎的比较中，InnoDB存储占据了毫无疑问的优势，因此当时业界纷纷传言MySQL AB即将收购Innobase公司。然而，令人意想不到的是，Oracle公司在2005年以迅雷不及掩耳之势收购了Innobase公司。这笔收购现在来看是具有前瞻性的，同时也是对MySQL数据库命运的改变。这里不得不再次佩服Larry的眼光与手腕。每当戴佩妮的歌曲《怎样》响起时，我往往会想象若Innobase没有被Oracle收购， MySQL数据库现在会是怎样呢？是不是还是深爱着MySQL AB？
或许这样的感叹只是笔者内心所谓的浪漫主义思绪在作祟，但不可否认的是MySQL数据库在之后的发展变得一蹶不振。最终，当所有人认为MySQL AB公司会上市时，而在2008年其竟然选择被Sun公司收购。在被收购后，依靠Sun的技术实力与影响力，MySQL数据库的发展理应能上轨道。事与愿违的是，MySQL数据库还是遭遇了一系列的问题，MySQL创始人的离开，版本的bug较多，依然使得MySQL数据库的发展较为缓慢。最终，随着Oracle收购Sun公司完成，宣布Sun这艘航空母舰的陨落并最终退出了历史舞台，而MySQL数据库最终到了Oracle的手中，InnoDB存储引擎和MySQL终于又在一起了，虽然这个过程用了整整5年（从2005年算起）的时间，但是当初几乎没人会想到竟是以这样的方式团聚。
为什么InnoDB存储引擎和MySQL数据库是相辅相成的呢？这是因为MySQL是一个比较特殊的数据库，根据其定义的接口，允许多种存储引擎同时存在和使用。用户可以根据自己的应用特性来选择或开发最适合自己的引擎。因此这两者需要相互配合，一起发展。举例来说，要实现在线DDL操作，首先需要MySQL数据库上层提供相应的接口，然后各个引擎内部再去实现。
不管怎么说，虽然Oracle公司对待开源软件并不友好，但是在收购Innobase后其还是对MySQL数据库提供了持续的开发工作，并且软件的质量有了较大的提高，版本发布的节奏也得以加快。随着MySQL数据库的不断成熟和InnoDB存储引擎的不断完善，可以断言互联网应用将是MySQL与InnoDB的天下。而Oracle公司一方面持有对于MySQL数据库的控制，另一方面拥有在传统企业中的数据库优势与布局，正所谓进可攻，退可守，已然立于不败之地。1.2 源码版本
虽然InnoDB仅仅是一个存储引擎，但其功能还是非常完善和强大的，因而其代码量还是比较大的。表1-1显示了各MySQL数据库版本中InnoDB存储引擎的代码行数。表1-1 InnoDB存储引擎各版本代码行数统计
功能的完善不可避免地会导致代码量的不断增加，但是一个软件的内核（或者说微内核）却不会有太大的变动，InnoDB存储引擎亦是如此。因此本书选择MySQL 3.23.49版本的InnoDB存储引擎作为源码分析的切入口，讲述InnoDB存储引擎的体系结构及其各主要功能模块实现的分析。即便如此，在MySQL 3.23.49版本中InnoDB存储引擎也有10万多行的代码。
各位读者不要小看MySQL 3.23.49中这个古老的版本，因为即使在最新的MySQL 5.6版本中，InnoDB存储引擎的内核实现也没有进行非常大的改动。正所谓一门深入，心定开慧，一通全通，妙极方法。通过设置断点调试仅能得到非常片面而又主观的内容，而通过本书的介绍可以使读者全面地了解InnoDB存储引擎的体系结构与实现。此外，读者还可以对比新版本的实现，看看两者之间的改进与优化。1.3 源码风格1.3.1 源码结构
除了存储引擎接口文件采用C++，以及少量的嵌入式汇编语言，InnoDB存储引擎绝大部分的代码都采用C语言进行编码实现。其源码结构与另一开源操作系统Linux比较相似，模块划分十分清晰，大部分模块被分解在不同的.c文件中。同时，每个模块的实现放在一个单独的文件夹下，文件的命名规则为“模块名0子模块能名.c”。例如关于B+树索引模块的文件名为btr/btr0xxx.c。
.h头文件与.c文件不同，其统一放在include文件夹下，例如lock模块的头文件位于include/lock0lock.h。在include文件夹下，除了.h文件外，还存在.ic文件。这类文件为每个模块定义了内联函数（非DEBUG模式下）。可以发现在这些文件中，函数的定义都包含宏UNIV_INLINE，该宏的定义位于文件univ.i中，具体定义如下所示。#if (!defined(UNIV_DEBUG) &&!defined(INSIDE_HA_INNOBASE_CC) && !defined(UNIV_MUST_NOT_INLINE))/* Definition for inline version */#ifdef __WIN__#define UNIV_INLINE __inline#else/* config.h contains the right def for ‘inline’ for the current compiler */#if (__GNUC__ == 2)#define UNIV_INLINE extern inline#else/* extern inline doesn’t work with gcc 3.0.2 */#define UNIV_INLINE static inline#endif#endif1.3.2 代码风格
从代码风格来看，InnoDB存储引擎的代码缩进风格更接近于K&R风格。所有的非函数语句块（if、switch、for、while、do），起始大括号放在行尾，而把结束大括号放在行首。函数开头的左花括号放到最左边。
此外，每个文件都包含一段简短说明其功能的注释开头，同时每个函数也注释说明函数的功能，需要哪些种类的参数，参数可能值的含义以及用途。最后，对于变量的声明，使用下画线以分隔单词，坚持使用小写，并把大写字母留给宏和枚举常量。1.4 代码编译
MySQL数据库支持各类常见的操作系统，例如Linux、Solaris、FreeBSD、Windows等。这意味着InnoDB同样支持跨平台的存储引擎。由于MySQL数据库以及各存储引擎都是通过C、C++进行编译的，因此移植这些程序是非常简单的。
我推荐用户使用Windows的Visual Studio工具尝试编译和调试MySQL数据库以及InnoDB存储引擎。MySQL 3.23源码编译文件需要做一些小小的修改以支持最新版本的Visual Studio开发环境。通过这样的修改，在Visual Studio 2013开发环境下也能对代码进行编译与调试。然而，我更推荐用户使用Visual Studio 2003进行源码的编译与调试，因为这基本上不需要做任何的修改。我共享了MySQL 3.23.49的Visual Studio 2003工程文件（http://pan.baidu.com/s/1iPtr），用户需要做的仅仅是打开工程文件，编译即可通过。调试需要将mysqld解决方案设置为启动项，并在属性页设置MySQL数据库的配置文件，如图1-1所示。图1-1 在Windows Visual Studio 2003下配置调试环境
对于喜欢在Linux环境下进行开发的用户，笔者推荐使用vim+gdb的方式。Redhat 9通过下面的方式就可以编译一个包含InnoDB存储引擎的DEBUG版本MySQL 3.23：CFLAGS=”-O0 -mpentiumpro” CXX=gcc CXXFLAGS=”-O0 \ -mpentiumpro -felide-constructors -fno-exceptions -fno-rtti” \./configure --prefix=/usr/local/mysql --enable-assembler --with-mysqld-ldflags=-all-static \--with-innodb --with-debug
其实即使在比较新的Linux发行版本下，如Ubuntu 12.0.4，也能对MySQL 3.23.49版本进行编译。不过这需要首先安装gcc 3.x版本，有兴趣的读者可以自己进行尝试，看看是否可以得到类似如下的结果：david@ubuntu:~/Downloads/mysql$ uname -aLinux ubuntu 3.8.0-29-generic #42~precise1-Ubuntu SMP Wed Aug 14 16:19:23 UTC 2013 x86_64 x86_64 x86_64 GNU/Linuxdavid@ubuntu:~/Downloads/mysql$ ./libexec/mysqld -V./libexec/mysqld Ver 3.23.58 for pc-linux on i6861.5 阅读源码次序
虽然InnoDB存储引擎有着良好的模块设计，源码也易于阅读。然而即使在MySQL 3.23版本中，InnoDB存储引擎的代码量也是非常巨大的。用户想要直接进行深入的阅读会遇到一些困难。因此，笔者更推荐从下至上，从易到难地进行逐层阅读。图1-2是笔者根据个人的理解，对InnoDB存储引擎各模块进行逐层的划分。图1-2 InnoDB存储引擎代码模块划分
图1-2最下方的是一些最基本的模块。它们是比较通用的模块，用户甚至可以自己将这些模块导出到自己的工程中进行使用。File Manager主要封装了InnoDB存储引擎对于文件的各类操作，如读、写、异步I/O等。Concurrency Manager模块主要封装了引擎内部使用的各类mutex和latch。Common Utility模块用于一些基本数据结构与算法的定义，如链表、哈希表等。
图中间虚线标注的部分可以理解为InnoDB存储引擎的内核实现部分，也就是InnoDB存储引擎事务、锁、缓存、日志、存储、索引的实现模块。所以说这些是最关键与重要的模块。通过这些模块用户可以了解InnoDB存储引擎内部的运行机制。
图最上面的两层是接口层，通过这些接口实现上层与存储引擎内部的互动。InnoDB存储引擎可以不依赖MySQL数据库，而作为一个嵌入式数据库存在，因此还存在嵌入式的API接口。
本书的结构采用从下至上的方式进行源码的分析，当然对于有开源软件经验的读者，可以跳过相关章节。但是对于刚入门的读者，或许按部就班地阅读更为适宜。1.6 思考题
[1] indent是一款C代码缩进与格式化工具，尝试该工具，并通过该工具整理相应工程文件代码风格为K&R。1.7 继续阅读
[1] “Indent style”， http://en.wikipedia.org/wiki/Indent_style.
[2] “Linux kernel coding style”，https://www.kernel.org/doc/Documentation/CodingStyle.第2章基本数据结构与算法
本章介绍InnoDB存储引擎的内存管理系统的实现、基本数据结构，如：动态数组、双链表、哈希表结构以及一些内部常见的算法与工具。通过本章的介绍，读者可以快速掌握InnoDB存储引擎的一些基本数据结构与算法，对于后续章节的阅读起到一个铺垫作用。2.1 相关文件
主要文件：dyn0dyn.*、fut0*.*、ha0ha.*、hash0hash.*、mem0*.*、ut0*.*。
代码行数：8164。
与基本数据结构、算法和基本工具集相关的代码分布和说明如表2-1所示。表2-1 与基本数据结构、算法和基本工具集相关的代码分布和说明2.2 内存管理系统
本节介绍InnoDB内存管理系统，此处所说的内存管理不是管理缓存池中的页，而是用于管理在使用InnoDB存储引擎时动态生成的内存数据结构对象。缓存到内存的数据页由缓冲池模块进行管理，这部分内容将在第11章缓冲池进行更为详细介绍。2.2.1 内存管理
InnoDB存储引擎并没有直接使用系统提供的malloc和free方法来进行内存的管理。通过源码的注释可以发现作者的目的主要是为了提高内存管理的性能：on the Solaris + GCCsystem (50 MHz Sparc, 1993) the pair takes 3 microseconds,on Win NT + 100MHz Pentium, 2.5 microseconds.
基于上述原因，InnoDB存储引擎采用内存堆（memory heap）的方式来进行内存对象的管理。其优点是可以一次性分配大块的内存，而不是通常的按需分配方法。这样的分配方式可以将多次的内存分配合并为单次进行，之后的内存请求就可以在InnoDB引擎内部进行，从而减小了频繁调用函数malloc和free带来的时间与潜在性能的开销。此外，InnoDB存储引擎还允许从缓冲池中分配内存来建立内存堆，这样可以更快速地请求整个内存页（通常为16KB）。在InnoDB存储引擎中，将这种分配方法称为缓冲池分配（buffer allocation）。将使用malloc分配内存的方法称为动态分配（dynamic allocation）。
图2-1简单介绍了InnoDB存储引擎内存管理的层次结构。最顶层为一系列各种用途的内存堆对象，其下是通用内存池和缓冲池，通过调用函数mem_area_alloc可从通用内存池建立一个内存堆或者为内存堆增加一个内存块。内存堆也可以通过buf_frame_alloc从缓冲池分配一整页大小的内存空间。最下层为操作系统内存，它是一切InnoDB内存空间的最终来源。如前所述，从操作系统分配内存空间和从缓冲池分配内存空间分别叫做动态分配和缓冲池分配。图2-1 InnoDB内存管理的层次结构示意图
内存堆是InnoDB存储引擎内存管理基本的也是最重要的对象。从概念上讲，内存堆就相当于一个栈（stack），内存堆通过不断增加内存块对象来增长空间。若要释放内存堆中的某个内存块，只能释放位于栈顶，也就是最晚分配得到的内存块，或者可以一次性地释放内存堆中所有的内存块，从这个栈中可以分配更小块的内存，这也是内存栈的功能所在。图2-2为内存堆的栈结构示意图。图2-2 InnoDB内存堆的栈结构示意图
InnoDB存储引擎使用数据结构mem_block_t来表示内存堆中每次从操作系统或者缓冲池中分配的内存块（memory block）。从本质上看，内存堆就是一系列相链的内存块。每个内存块头部都包含mem_block_info_t用来存储内存块元数据信息，表2-2为数据结构mem_block_info_t的说明。表2-2 内存块元数据结构mem_block_info_t简介续表
内存堆使用第一个内存块中的base字段将堆中所有的内存块根据进入堆的先后顺序链接起来，在调用者请求内存对象时获取最后一个内存块用于分配，如果该块已经用完，就会分配新块并插入到块链表中作为最后一个块，图2-3介绍了内存堆是如何将其中的各个内存块组织起来的。图2-3 内存堆中内存块组织示意图
InnoDB存储引擎定义了三种内存堆类型，分别为：
• MEM_HEAP_DYNAMIC堆的内存调用通用内存池接口申请；
• MEM_HEAP_BUFFER堆的内存是从缓冲池申请的；
• MEM_HEAP_BTR_SEARCH是MEM_HEAP_BUFFER的子类型，仅在自适应哈希索引中使用。
内存堆的创建由函数mem_heap_create_func完成，分配的内存空间大小可以通过以下三种方式确定：
• 指定初始块内存指针和大小，该方法无须进行内存分配；
• 指定初始块大小；
• 不指定初始块指针和大小。
若为第三种，系统默认分配大小为MEM_BLOCK_START_SIZE（64B）的内存块来创建堆。如果需要更多的空间，额外的内存块会被分配并且加入到一个链表中。初始块以后每次所分配的内存块大小为前一次的2倍，直至达到所设置的阈值，之后将每次分配阈值大小的内存，如图2-3所示。DYNAMIC类型的阈值为MEM_BLOCK_STANDARD_SIZ（8KB），BUFFER类型为MEM_MAX_ALLOC_IN_BUF（UNIV_PAGE_SIZE – 200，UNIV_PAGE_SIZE为缓存页框大小，默认为16KB）。但若调用者请求分配的内存大小比阈值还大，此时不受阈值限制，不过最大不超过MEM_MAX_ALLOC_IN_BUF。
在开启UNIV_MEM_DEBUG的调试版本中，所有被分配的内存堆会插入到一个哈希表中，这样就能够知道调用者是否二次释放同一个内存堆。此外，每块返回给调用者的内存块都包含起始域和结尾域，起始域包括两个字段：
1．表示所分配的块大小的字段；
2．用于进行校验的字段，内容为生成的随机数。
结尾域为一个校验字段，内容为与起始域中相同的随机数。通过起始域和结尾域就可以知道是否有内存被非法复制超过了内存块的边界。返回给调用者的内存块被初始化为随机字节序列。内存堆释放后，堆中的所有块都被设置为随机数，这样可以检测出使用已释放堆的错误。2.2.2 通用内存池
InnoDB存储引擎启动后，内存实例中会有一个mem_comm_pool对象，称之为通用内存池，其在InnoDB启动进行内存管理初始化时调用函数mem_pool_create创建，大小通过参数innodb_additional_mem_pool_size进行定义。通用内存池服务于之前介绍的内存堆，主要用于进行小块内存的分配，通常用于分配一些InnoDB引擎内存数据结构对象。
对象mem_comm_pool通过内存池数据结构mem_pool_struct来进行定义，具体说明如表2-3所示：表2-3 内存池结构mem_pool_struct简介
变量buf和size分别代表内存池所分配内存的起始位置以及内存池大小，reserved表示当前内存池中有多少内存已经被使用。内存区数据结构mem_area_t用于内存池中内存单位的管理，内存池中所有的内存区指针都保存在free_list[64]数组中，内存区结构mem_area_struct简介如表2-4所示：表2-4 内存区结构mem_area_struct简介
变量size_and_free存储了内存区的大小以及该内存区是否已经被分配的两部分信息，可以通过宏MEM_AREA_FREE获取对应的size和free值。变量free_list用于将每个内存区链接到mem_pool_struct的对应free_list链表中。
通用内存池所规划的容量一般较小，但其缓存的最后两项即数据字典缓存和自适应索引的哈希表可能占据大量的内存空间，甚至大于设定的通用内存池的容量，故在通用内存池容量不足时允许这两项从缓冲池中分配空间。通用内存池的大小可以通过参数srv_mem_pool_size来指定，而该参数与innobase_additional_mem_pool_size相关联，可以在配置文件中进行设定，默认大小为8MB。
从内存池的管理角度分析，如果频繁地请求和释放不同大小的内存，会导致在内存池中存在很多碎片化的小内存区，引发的问题是，即使内存池中有足够多空闲内存可满足请求，但要分配一个大块的连续内存就可能无法满足。与Linux内核的内存管理系统类似，InnoDB的内存池也使用伙伴系统（buddy system）来解决外碎片问题。
通用内存池通过free_list[64]和mem_area_struct来组成其内部的伙伴系统。把内存池中所有内存分组为64个内存区链表，每个区链表分别包含大小为2^0、2^1、2^2，一直到2^64字节的内存区。实际上，内存池仅将内存区拆分到MEM_AREA_MIN_SIZE大小，MEM_AREA_MIN_SIZE为mem_area_struct所占内存空间对齐后的2倍，所以，在free_list[]数组小于MEM_AREA_MIN_SIZE的前几项是空的，每次从伙伴系统中分配的内存大小必须为MEM_AREA_MIN_SIZE的整数倍。
对于通用内存池，若申请一块64B的内存对象，则先在free_list[6]链表中检查是否有一个空闲块。如果没有这样的块，会在free_list[7]链表中找一个空闲块。如果存在这样的块，内存池就把free_list[7]中的第一个128B块分成两等分，一半用来满足请求，另一半插入到free_list[6]链表中。如果在free_list[7]链表中也没找到空闲块，就继续找更大的块进行类似的等分操作，直到满足要求或者发出内存池空间不足的警告信息。图2-4举例说明了伙伴系统通常的分配和回收操作，A、B、C、D、E表示内存分配行为，灰色表示已被分配的内存空间，白色表示还处于空闲状态的内存区。图2-4 伙伴系统分配和回收操作举例
假设内存池大小为1MB，初始化后为完整的整块内存。有个分配请求A要分配128KB内存，由于内存池中没有现成的128KB内存，则需要将256KB的内存区分裂为两个128KB的伙伴，但如果也没有现成的256KB内存，则需要继续向上请求，直到1MB内存区。所以，此次分配行为会导致内存池将1MB的内存区分裂为一个512KB内存区、一个256KB内存区和两个128KB内存区，最后给请求A返回一个128KB内存区。接着如有分配请求B申请256KB内存，那么内存池直接将现有的256KB内存区返回给B。之后，分配请求C申请64KB内存，就需要将内存池中现有的128KB分裂为两个64KB内存区，并将其中一个64KB返回给C。请求D所申请的256KB内存可通过将512KB内存区拆分为两个256KB内存区来满足分配请求。内存池就是通过上述的方式来进行内存分配的。
接着说明回收内存的操作，请求C所申请的64KB内存释放后，由于此时内存池中其伙伴，即与之相邻的另一个64KB是空闲的，所以内存池会将这两个64KB内存区合并为一个128KB的内存区。与之类似，请求E所申请的128KB释放后，也会跟其伙伴合并为一块256KB的内存。2.3 哈希表2.3.1 哈希算法
哈希算法是一种常见算法，时间复杂度为O(1)。设想一个问题，当前服务器的内存为256GB，用户怎么从内存中得到某一个被缓存的页呢？内存中查询速度很快，但是也不可能每次遍历所有内存来进行查找。故这时对于字典操作，只需O(1)的哈希算法就能有很好的用武之处。
哈希表也称散列表，由直接寻址表改进而来。当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都有一个取自全域U={0,1,…,m-1} 的关键字。同时假设没有两个元素具有相同的关键字。
用一个数组(即直接寻址表)T[0..m-1]表示动态集合，其中每个位置(或称槽或桶)对应全域U中的一个关键字。图2-5说明这个方法，槽k指向集合中一个关键字为k的元素。如果该集合中没有关键字为k的元素，则T[k]=NULL。图2-5 直接寻址表
但直接寻址技术存在一个很明显的问题，如果域U很大，在一台典型计算机的可用内存容量限制下，要在机器中存储大小为U的一张表T就有点不实际，甚至是不可能的。如果实际要存储的关键字集合K相对于U来说可能很小，因而分配给T的大部分空间都要浪费掉。
因此，哈希表出现了。在哈希方式下，该元素处于h(k)中，亦即利用哈希函数h，根据关键字k计算出槽（cell）的位置。函数h将关键字域U映射到哈希表T[0..m-1]的槽位上，如2-6图所示。图2-6 哈希表
哈希表技术很好地解决了直接寻址遇到的问题，但是这样做有一个小问题，图2-6所示的两个关键字可能映射到同一个槽上。一般将这种情况称之为发生了冲突(collision)。数据库中一般采用最简单的碰撞解决技术，称之为链接法(chaining)。
在链接法中，把散列到同一槽中的所有元素都放在一个链表中，如图2-7所示。槽j中有一个指针，它指向由所有散列到j的元素构成的链表头部；如果不存在这样的元素，则j中为NULL。图2-7 通过链表法解决碰撞的哈希表
最后要考虑的是哈希函数了，哈希函数h必须可以很好地进行散列。最好的情况是能避免碰撞的发生。即使不能避免，也应该使碰撞在最小限度下产生。一般来说，大多数是将关键字转换成自然数，然后通过除法散列、乘法散列，或全域散列来实现。数据库中一般采用除法散列的方法。2.3.2 数据结构
数据结构hash_table_struct为InnoDB存储引擎定义的哈希表结构，该结构的定义与说明如表2-5所示：表2-5 哈希表数据结构hash_table_struct的定义与说明
变量array的类型为hash_cell_t，表示槽的数量。由于不同的哈希表实例需要保存各种不同类型的数据结构，因此hash_cell_t的类型为void*。
哈希表创建函数须指定槽的数量，但实际创建的哈希表元胞个数却不一定与输入的个数相同。为了能够更为平均地进行哈希数据的分布，InnoDB存储引擎槽的数量设置为一个素数，因此在源码中，槽的数量根据如下规则得到：prime = ut_find_prime(n);table = mem_alloc(sizeof(hash_table_t));array = ut_malloc(sizeof(hash_cell_t) * prime);table->array = array;
函数ut_find_prime用于素数的查找，返回的结果是比n稍大的一个素数。此外，在数据结构hash_table_struct的定义中可以看到互斥量的定义，并且可以指定多个互斥量来提高哈希表的并发性。但在MySQL 3.23.49版本中，并没有直接使用数据结构hash_table_struct提供的互斥量。并发控制由各使用哈希表的数据结构提供，例如缓冲池的哈希表由数据结构buf_pool_struct的互斥量进行并发控制，自适应哈希索引使用的哈希表由全局的读/写锁btr_search_latch进行并发控制。
InnoDB存储引擎使用之前介绍的链表法来解决哈希值相同的冲突问题，但是在上述数据结构定义中，没有看见关于这部分的定义。这是因为在InnoDB存储引擎中，可通过两种方式来实现哈希链：哈希链（chain）保存在哈希的对象中，或者自己创建哈希链。
例如当哈希表存放的是缓冲池中的页时，那么这时哈希链保存在页的数据结构buf_block_t中，其中关于链的定义如下：struct buf_block_struct{ ...... buf_block_t* hash; /* node used in chaining to the page hash table */ ......}；
对于有些数据结构，哈希对象中可能不存有链的信息。对于自适应哈希索引来说，其哈希的对象是记录，记录仅是一个二进制串，没有链的信息（若存有链信息，则记录会有额外的存储开销）。因此对于这种对象需要创建链，链的内存申请通过数据结构hash_table_struct中的heap变量，对象为hash_node_t，其数据结构如表2-6所示。表2-6 哈希链数据结构hash_node_t
对于不同对象，哈希键值的计算方式各不相同。基本思路是先对查询的键进行fold，相应的函数有buf_page_address_fold、rec_fold等。然后通过函数hash_calc_hash映射到哈希表的槽中。
在InnoDB存储引擎中，哈希表支持各种类型对象进行查询，因此采用宏的方式对哈希操作进行封装，这些操作如表2-7所示。表2-7 哈希表对外提供的操作接口列表2.4 双链表
双链表是一种在InnoDB存储引擎中使用极为广泛的数据结构，其用于链接多个同类型的数据，如2.3节所介绍的内存池中的内存块就是使用双链表进行管理的。通过在链表的每个单元中设置两个指针，一个指向后续，另一个指向前继。双链表能够快速地确定表中任一元素的前继和后续元素所在的单元，从而进行数据的存取等操作。在InnoDB存储引擎中，双链表包括两种类型，分别为用于组织内存对象的内存双链表和用于组织磁盘文件中数据的磁盘双链表，本节将分两个小节逐一介绍内存和磁盘双链表。2.4.1 内存双链表
InnoDB存储引擎的内存双链表，即通常意义上的双链表，其使用场景遍布在InnoDB的各模块中，如缓冲池模块、事务处理模块、锁模块和文件系统模块等。双链表的基本定义在各版本的数据结构教科书中都可以了解到，在此无须赘述。下面主要介绍双链表在InnoDB中的实现方式。
为了优化代码执行效率，内存双链表在ut0lst.h头文件中通过一系列宏定义实现，其与被链的数据对象类型无关，可支持各种数据类型。链表由两部分组成，分别为链表基节点UT_LIST_BASE_NODE_T(TYPE)和节点链表UT_LIST_NODE_T(TYPE)，每个需被链接的数据对象必须为结构体，且需包含UT_LIST_NODE_T(TYPE)字段，表2-8、表2-9所示为链表基节点和节点链表的宏定义，其中TYPE为其结构类型，UT_LIST_BASE_NODE_T(TYPE)可位于被链接的数据对象中，也可以在另一种数据对象中，通过UT_LIST_INIT(BASE)来进行链表初始化。图2-8为双链表链接示意图。表2-8 UT_LIST_BASE_NODE_T(TYPE)宏定义表2-9 UT_LIST_NODE_T(TYPE)宏定义图2-8 双链表链接示意图2.4.2 磁盘双链表
InnoDB存储引擎磁盘双链表主要使用在表空间管理模块、事务处理模块和B树模块中，用于建立保存在磁盘中的数据结构间的关系。由于磁盘数据块设备无法像内存一样通过指针进行随机地址访问，要访问某个磁盘数据，需要先将其对应的磁盘块读取到内存中，再通过块内的偏移位置最终定位到所需的数据。
在InnoDB存储引擎的表空间中，与内存双链表基节点和节点链表对应的类型为flst_base_node_t和flst_node_t，两者相关的定义如下所示：typedef byte flst_base_node_t;typedef byte flst_node_t;/* The physical size of a list base node in bytes */#define FLST_BASE_NODE_SIZE (4 + 2 * FIL_ADDR_SIZE)/* The physical size of a list node in bytes */#define FLST_NODE_SIZE (2 * FIL_ADDR_SIZE)/* We define the field offsets of a node for the list */#define FLST_PREV 0 /* 6-byte address of the previous list element; the page part of address is FIL_NULL, if no previous element */#define FLST_NEXT FIL_ADDR_SIZE /* 6-byte address of the next list element; the page part of address is FIL_NULL, if no next element */……/* We define the field offsets of a base node for the list */#define FLST_LEN 0 /* 32-bit list length field */#define FLST_FIRST 4 /* 6-byte address of the first element of the list; undefined if empty list */#define FLST_LAST (4 + FIL_ADDR_SIZE) /* 6-byte address of the first element of the list; undefined if empty list */
磁盘双链表的基节点和节点的组成与内存双链表类似。基节点包含一个用于表示链表节点个数的字段和两个用于链接起始和末尾节点的指针，节点由两个链接前继和后续节点的指针组成。fil_faddr_t用于保存某数据在磁盘中的位置，起到类似内存指针的作用，相关定义如下：typedef byte fil_faddr_t; /* ‘type’ definition in C: an address stored in a file page is a string of bytes */#define FIL_ADDR_PAGE 0 /* first in address is the page offset */#define FIL_ADDR_BYTE 4 /* then comes 2-byte byte offset within page*/#define FIL_ADDR_SIZE 6 /* address size is 6 bytes */
图2-9是磁盘双链表组成部分示意图，FLST_FIRST、FLST_LAST、FLST_PREV和FLST_NEXT保存的对象均为fil_addr_t，其包括两个字段：所在页在表空间中的偏移位置以及数据在页内的相对偏移位置，分别使用FIL_ADDR_PAGE和FIL_ADDR_BYTE来表示两个字段的大小。由于磁盘数据无法通过结构体定义来获取fil_faddr_t的大小，因此需要通过FIL_ADDR_SIZE（6B）显式表示磁盘指针大小。通过这三个宏定义确定fil_faddr_t每个字段所占据的磁盘空间大小分别为4B和2B。与fil_faddr_t对应的内存数据结构为fil_addr_struct，两者的相互比较如表2-10所示。图2-9 磁盘双链表组成部分示意图表2-10 fil_faddr_t在磁盘和内存中的表示方式比较
fut_get_ptr用于获取磁盘中fil_faddr_t位置数据在内存缓冲池中的指针ptr，buf_ptr_get_fsp_addr用于获取内存缓冲池指针ptr对应的表空间中的数据位置fil_faddr_t。flst_write_addr用于往ptr对应的fil_faddr_t缓冲区中写入地址信息，flst_read_addr用于读取ptr中的地址信息。与内存双链表一样，磁盘双链表也实现了一系列的链表操作，在此不再赘述。2.5 其他数据结构和算法
除了上述所介绍的内存管理、双链表和哈希表等基本数据结构和算法外，InnoDB中还使用了很多其他数据结构和算法，在本小节再简单介绍两种，分别是动态数组和排序算法。2.5.1 动态数组
动态数组，顾名思义，指的是存储空间能够动态地增加一种数组结构，InnoDB中动态数组定义为dyn_array_t，当前使用动态数组的场景主要是mtr（mini-transaction）模块，用于保存mtr中的锁和修改日志。
dyn_array_t基于块的方式扩展存储空间，每次申请DYN_ARRAY_DATA_SIZE（512B）大小的数组空间，dyn_array_t将块定义为dyn_block_t结构，如表2-11所示。表2-11 动态数组块结构dyn_block_t简介
动态数组中块的组织方式与内存堆中块的组织方式相类似，只不过内存堆中每次分配的块一般为前一个分配块的2倍；而在动态数组中，每次分配的dyn_block_t结构大小中，包括了用于保存数据的DYN_ARRAY_DATA_SIZE大小。
使用dyn_array_create来创建一个动态数组，其实该函数并不分配动态数组空间，仅对数组中的第一个块进行初始化。若第一个块的空间不够用的话，会调用dyn_array_add_block分配一个新的块。动态数组第一次调用dyn_array_add_block时，会分配一个内存堆对象来初始化heap字段，并对base链表进行初始化。在将数据写入动态数组前需调用dyn_array_open函数将其打开，函数返回用于写入数据的指针，完成写入后，调用dyn_array_close函数将其关闭。2.5.2 排序
InnoDB提供了一种通用的排序实现，默认基于合并算法进行排序操作，算法复杂度最坏为n的对数。算法实现的宏定义为UT_SORT_FUNCTION_BODY(SORT_FUN,ARR,AUX_ARR,LOW,HIGH,CMP_FUN)，其中SORT_FUN为用于对目标数组ARR进行排序的函数。CMP_FUN用于比较ARR中两个元素大小的函数，若前一个元素大则返回1，相等返回0，否则返回-1。AUX_ARR为用于排序的辅助数组，其元素个数不少于ARR，LOW和HIGH分别为所需排序的ARR数组的元素序列，包括LOW而不包括HIGH。
试读结束[说明：试读内容隐藏了图片]