在 InnoDB中更加快速的全表扫描
一般来讲,大多数应用查询的时候都会用索引，查找很少的几行数据（主键查找或百行内的查询），但有时候我们需要全表查询。典型的全表扫描就是逻辑备份 (mysqldump) 和 online schema changes（ 注：在线上对大表 schema 的操作，也是 facebook 的一个开源项目） (SELECT ... INTO OUTFILE).
在 Facebook我们用 mysqldump 来备份数据库. 正如你所知MySql提供两种备份方式，提供了物理备份和逻辑备份的命令和工具. 相对物理备份，逻辑备份有一定的优势，例如:
- 逻辑备份备份数据要小得多. 3x-10x 尺寸差异并不少见。
- 更容易解析备份数据库. 在物理备份中,在出现严重问题时候，如校验失败。如果我们不能将数据库恢复 ，想知道InnoDB内部数据结构，或者修复损坏是十分困难的。比起物理备份我们更加相逻辑备份。
逻辑备份的主要缺点是数据库的完全备份和完全还原比物理的备份恢复慢得多。
缓慢的完全逻辑备份往往会导致问题.如果数据库中存在很多大小支离破碎的表，它可能需要很长的时间。在 脸书，我们面临 mysqldump 的性能问题，导致我们不能在合理的时间内对一些(基于HDD和Flashcache的)服务器完成完整逻辑备份。我们知道 InnoDB做全表扫描并不高效，因为 InnoDB 实际上并没有顺序读取,在大多情况下是在随机读取。这是一个已知多年的老问题了。我们的数据库存储容量一直在增长，缓慢的全表扫描问题给我们造成了严重的影响,因此,我们决定加强 InnoDB 做顺序读取的速度。最后我们的数据库攻坚工程师团队在InnoDB 中实现了"Logical Readahead"功能。应用"Logical readahead"，在通常生产工作负载下，我们全表扫描速比之从前度提高 9 ~ 10 倍。在超负荷生产中，全表扫描速度达到 15 ~ 20 倍的速度甚至更快。
全表扫描在大的、碎片化数据表上的问题
做全表扫描时,InnoDB 会按主键顺序扫描页面和行。这应用于所有的InnoDB 表，包括碎片化的表。如果主键页表没有碎片（存储主键和行的页表),全表扫描是相当快，因为读取顺序接近物理存储顺序。这是类似于读取文件的操作系统命令(dd/cat/etc) 像下面。
你可能会发现即使在商业HDD服务器上，你可以达到高于比100 MB/s 乘以"驱动器数目"的速度。超过1GB/s并不少见。
不幸的是，在许多情况下主要关键页表存在碎片。例如，如果您需要管理 user_id 和 object_id 映射，主键将会是(user_id,object_id)。插入排序与 user_id并不一致，那么新插入/更新往往导致页拆分。新的拆分页将被分配在远离当前页的位置。这意味着页面将会碎片化。
如果主键页是碎片化的，全表扫描将会变得极其缓慢。图1阐释了这个问题。在InnoDB读取叶子页#3之后，它需要读取页#5230，在那之后还要读页#4。页#5230位置离页#3和页#4很远，所以磁盘读操作顺序开始变得几乎是随机的，而不是连续的。大家都知道HDD上的随机读要比连续读慢得多。一个有效的改进随机读性能的办法是使用SSD。不过SSD每个GB的价钱要比HDD昂贵的多，所以使用SSD通常是不可能的。
图 1.全表扫描实际没有连续读
线性预读取真的有意义吗？
InnoDB支持预读取特性，称作“线性预读取”（ Linear Read Ahead）。拥有线性预读取，如果N个page可以顺序访问（N可以通过innodb_read_ahead_threshold参数进行配置，默认为56），InnoDB可以一次读取一个extent(64个连续的page，如果不压缩每个page为1MB）。但是，实际来说这么做的意义不大。一个extent(64个page)非常小。对于一个支离破碎的较大的数据库表来说，下一个page不一定在同一个extent当中。上面图1就是一个很好的例子。读取page#3之后，InnoDB需要读取page#5230。page#3和page#5230并不在同一个extent当中，所以线性预读取技术在这里用处不大。这对于大表来说是非常常见的情况，所以这也解释了线性预读取技术为什么不能有效改善全表扫描的性能。
物理预读取
正如上面描述的，全表扫描速度较慢的主要原因是InnoDB主要进行随机读取。为了加速全表扫描，需要使InnoDB进行顺序读取。我想到的第一个方法就是创建一个UDF（user defined function)顺序的读取ibd文件(InnoDB的数据文件）。UDF执行完成后，ibd文件的page应当保存在InnoDB的缓存池当中，所以在进行全表扫描时无需再进行随机读取。下面是一个示例用法：
mysql> SELECT buf_warmup ("db1", "large_table"); /* loading into buf pool */
mysql> SELECT * FROM large_application_table; /* in-memory select */
buf_warmup() 是一个用户自定义函数，用来读取数据库“db1"的表”large_table"的整个ibd文件。该函数需要花费时间将ibd文件从硬盘读取，但因为是顺序读取的，所以比随机读取要快的多。在我的测试当中，比普通的线性预读取快差不多5倍左右。
这证明ibd文件的顺序读取能够有效的改善吞吐率，但也存在一些缺点：
- 如果table的大小超过InnoDB缓存池的大小，这种方法就不能工作
- 在全表扫描过程中，读取整个的ibd文件就意味着不但需要读取primary key page还需要读取二级索引page以及一些其他不需要的page，并将其保存在缓存池，尽管只有primary key page是实际需要的。如果拥有大量的二级索引，这种方法就不能有效的工作
- 应用需要做出一定的修改以便调用UDF
这看起来是一个足够好的解决方案，但我们的数据库设计团队想出了一个更好的解决方法叫做“逻辑预读取”（Logical Read Ahead)，所以我们并不选择UDF的方法。
逻辑预读取
逻辑预读取（LRA）的工作流程如下：
- 读取主键的一些分支page
- 计算叶子page的数量
- 以page number的顺序（大多数是顺序磁盘读取）依次读取一些（通过配置控制数量的多少）叶子page
- 以主键的顺序读取行
整个流程如图2所示：
Fig 2: Logical Read Ahead
逻辑预读取解决了物理预读取所存在的问题。LRA使InnoDB仅读取主键page（不需要读取二级索引页面),并且每一次预读取页面的数量是可以控制的。除此之外，LRA对SQL语法不需要做任何修改。
为了使LRA工作，我们需要增加两个session变量。一个是"innodb_lra_size"，用来控制预读取叶子页面(page)大小。另外一个是"innodb_lra_sleep"，用来控制每一次预读取之间休眠多长时间。我们用512MB～4096MB的大小以及50毫秒的休眠时间来进行测试，到目前为止我们还没有遇到任何严重问题（例如崩溃/阻塞/不一致等）。这些session变量仅在需要进行全表的时候进行设置。在我们的应用中，mysqldump以及其他一些辅助脚本启用了逻辑预读取。
一次提交多个async I/O请求
我们注意到，另外一个导致性能问题的原因是InnoDB 每次i/o仅读取一个页面，即使开启了预读取技术。每次仅读取16KB对于顺序读取来说实在是太小了，效率相比大的读取单元要低很多。
在版本5.6中，InnoDB默认使用Linux本地I/O。如果一次提交多个连续的16KB读请求，Linux在内部会将这些请求合并，读操作能够更有效的执行。不幸的是，InnoDB一次只会提交一个页面的i/o请求。我提交了一个bug report#68659.正如bug report中所写，在一个当代的HDD RAID 1+0环境中，如果我一次性提交64个连续的页面读取请求，我可以获得超过1000MB/s的硬盘读取速度；如果每次只提交一个页面读取请求，我们仅可以获得160MB/s的硬盘读取速度。
为了使LRA在我们的应用环境中更好的工作，我们修正了这个问题。在我们的MySQl中，InnoDB在调用io_submit()之前会提交多个页面i/o请求。
基准测试
在所有的测试中，我们使用的都是生产环境下的数据库表（分页的表）。
1. 纯HDD环境全表扫描 (基础的基准测试, 没有其他的工作负载)
2. Online schema change under heavy workload
* dump time only, not counting data loading time
源码
我们做出的所有增强修改都可以在GitHub上获取。
结论
对于全表扫描来说InnoDB的工作效率不高，所以我们对它做了一定的修改。我在两方面进行了改进，一是实现了逻辑预读取；一是实现了一次提交多个async read i/o请求。对于我们生产环境中的数据库表来说，我们获得了8-18倍的性能提高，这对于减少备份时间、模式修改时间等来说是非常有用的。我希望这些特性能够在InnoDB中获得Oracle官方支持，至少是主要的MySQL分支。
