一、机械磁盘原理
机械盘由动臂，盘片，读写磁头，主轴组成，磁头是固定不能动的，要读取相应的扇区只能通过盘片的旋转。每一个盘片为双面，每一个面上分布有同心圆的磁道，磁道又分为扇区一般为512 BYTES，现代的磁盘一般外边缘磁道的扇区多，内磁道的扇区少，那么一般读写外边缘磁道的速度更快，因为转速为定值。同时各个不同盘片上半径下同的磁道组成了一个柱面。
下图是一个典型的磁盘组织（摘取数据结构（C语言版））
如果我们计ts(seek time)为寻道时间，tl（latency time）为寻道完成后等待盘片旋转到特定扇区的时间tw（transmission time）为传输时间，那么读取一个扇区的时间为：T(I/0) = ts+tl+tw
显然在读取数据一定的情况下，ts和tl的时间成了决定因素，而事实上ts寻道时间相对其他而言占用更长，寻道时间在10毫秒的数量级，7200转的tl时间为1000/7200 约为 100微秒数量级，而传输时间更短。大量的随机I/O会造成频繁的磁道更换导致过长的时间，很可能读完几个扇区马上就要跳到另外的磁道，而顺序I/O则不然一次定位可以读取更多的扇区，从而尽量减少读取时间。
二、随机I/O和顺序I/O模拟
模拟使用C语言调用LINUX API完成，主要方式如下：读取一个大文件程序中限制为900M，而程序顺序和随机读取20000个4096大小的数据，并且复制到其他文件中，复制的文件为81920000字节。为了将写操作的影响降低，而将读操作的影响放大，分别使用O_CREAT | O_WRONLY | O_EXCL打开写文件，启用OS BUFFER，write操作写到OS kernel buffer则结束，同时不能开启O_SYNC，开启O_SYNC每一次wirte会调用fsync()，将写的影响将会放大。O_RDONLY | O_DIRECT打开读取文件，用O_DIRECT打开目的在于禁用OS CACHE当然也禁用了OS的预读，直接读取文件这方面摘取一张图便于理解，实际上我O_DIRECT后读取这个文件是不过内核高速缓存的。
当然这个程序有一点不足，我应该使用排序算法将随机数组中的数据排序后在进行读取，而不是取一个连续的数组。这样更能说明问题，但这也不重要，因为随机读已经慢得离谱了。下面是我程序跑出的结果。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
$ ./a.out p10404530_112030_Linux-x86-64_1of7.zip fisrt sca array: 134709 fisrt sca array: 198155 fisrt sca array: 25305 fisrt sca array: 46515 fisrt sca array: 91550 fisrt sca array: 137262 fisrt sca array: 46134 fisrt sca array: 10208 fisrt sca array: 142115 ...... sequential cpy begin Time: Fri Dec 2 01:36:55 2016 begin cpy use sequential read buffer is 4k: per 25 % ,Time:Fri Dec 2 01:36:56 2016 per 50 % ,Time:Fri Dec 2 01:36:57 2016 per 75 % ,Time:Fri Dec 2 01:36:57 2016 per 100 % ,Time:Fri Dec 2 01:36:58 2016 scattered cpy begin Time: Fri Dec 2 01:36:58 2016 begin cpy use scattered read read buffer is 4k: per 25 % ,Time:Fri Dec 2 01:37:51 2016 per 50 % ,Time:Fri Dec 2 01:38:40 2016 per 75 % ,Time:Fri Dec 2 01:39:29 2016 per 100 % ,Time:Fri Dec 2 01:40:20 2016 |
先输出部分数组中的随机值，可以看到读取的位置是随机的。从而模拟随机读取，然后输出顺序读取写入，然后进行随机读取写入。可以看到差别非常大，其实使用iostat vmstat都能看到读取的速度非常慢。下面给出比较：
–顺序
|
1 2 3 4 5 6 |
Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 0.00 4979.38 2.06 19967.01 32.99 8.03 0.76 0.15 0.14 70.21 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 0.00 7204.12 0.00 28816.49 0.00 8.00 0.98 0.14 0.14 98.04 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 9.09 7114.14 9.09 28456.57 96.97 8.02 1.04 0.15 0.13 95.86 |
—随机
|
1 2 3 4 5 6 |
Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 0.00 107.14 0.00 428.57 0.00 8.00 1.01 9.49 9.42 100.92 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 0.00 104.17 1.04 416.67 0.52 7.93 1.04 9.79 9.81 103.23 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await svctm %util sda 0.00 0.00 104.12 2.06 465.98 32.99 9.40 1.17 11.02 9.68 102.78 |
这里明显看出了问题，程序放到最后给出。
这里可以自己使用sysbench工具直接对磁盘进行压测获得效果，sysbench支持随机、顺序读写IO。
三、MRR（Multi-Range Read）
有了上面的基础，我们明白了顺序读取的重要性，那么我们开始看看MySQL 5.6开始支持的新特性”Multi-Range Read (MRR)”，因为这个特性也是BKA的重要支柱。MRR优化的目的就是为了减少磁盘的随机访问，对于MySQL的二级索引（非聚集索引）而言，过于随机的回表会造成随机读取过于严重，范围扫描（range access）中MySQL将扫描到的数据存入read_rnd_buffer_size，然后对其按照Primary Key（RowID）排序，然后使用排序好的数据进行顺序回表，因为我们知道InnoDB中叶子节点数据是按照PRIMARY KEY（ROWID）进行排列的，那么这样就转换随机读取为顺序读取了。这对于IO-bound类型的SQL查询语句带来性能极大的提升。MRR优化可用于range，ref，eq_ref类型的查询。
MRR优化有以下几个好处：
* 使得数据访问变得较为顺序，在查询辅助索引时，先对得到的查询结果按照主键进行排序，并按照主键排列的顺序进行书签查找。
* 减少缓冲池中页被替换的次数。
* 批量处理对键值的查询操作。
对于InnoDB和MyISAM存储引擎的范围查询和联接查询，MRR的工作方式如下：
* 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。
* 将缓存中的键值根据RowID进行排序。
* 根据RowID的排序顺序来访问实际的数据文件。
此外，若InnoDB存储引擎缓冲池不是足够大，即不能存放下一张表中的所有数据，此时频繁的离散读取操作还会导致将缓存中的页替换出缓冲池，然后又不断地读入缓冲池。若按照主键顺序进行访问，则可以将重复行为的次数降为最低。
如图（图片摘取自MariaDB官方文档）：
例如下面SQL语句：
|
1 2 3 4 5 6 7 8 9 10 |
mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on'; Query OK, 0 rows affected (0.00 sec) mysql> explain select * from salaries where salary>10000 and salary<40000; +----+-------------+----------+------------+-------+---------------+------------+---------+------+-------+----------+----------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+-------+---------------+------------+---------+------+-------+----------+----------------------------------+ | 1 | SIMPLE | salaries | NULL | range | idx_salary | idx_salary | 4 | NULL | 21450 | 100.00 | Using index condition; Using MRR | +----+-------------+----------+------------+-------+---------------+------------+---------+------+-------+----------+----------------------------------+ 1 row in set, 1 warning (0.00 sec) |
salary上有一个辅助索引idx_salary，因此除了通过辅助索引查找键值外，还需要通过书签查找来进行对整行数据的查找。这里使用了ICP（pushed-down conditions）和MRR，因为MRR的代价评估一般较高，所以这里使用mrr_cost_based=off。如图：
此外，MRR还可以将某些范围查询拆分为键值对，以此来完成批量的数据查询。这样做的好处是可以在拆分过程中，直接过滤一些不符合查询条件的数据，例如：
|
1 |
SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1 <= 2000 AND key_part2 = 10000; |
表t中有(key_part1, key_part2)的联合索引，因此索引根据key_part1、key_part2的位置关系进行排序。若没有MRR，此时查询类型为Range，SQL优化器会先将key_part1大于1000小于2000的数据都取出，就是使key_part2不等于10000，待取出行数据后再根据key_part2的条件进行过滤，这会导致无用数据被取出。如果存在大量的数据并且其key_part2不等于10000，则启用MRR优化性能会有巨大的提升。
倘若启用了MRR优化，那么优化器会先将查询条件进行拆分，然后再进行数据的查询。就上述查询语句而言，优化器会将查询条件拆分为(1000, 10000)，(1001, 10000)，(1002, 10000)，…，(1999, 10000)，最后再根据这些拆分出的条件进行数据查询。
而在BKA（batched key access）中则将被连接表使用到ref，eq_ref索引扫描方式的时候，将第一个表中扫描到的键值放到join_buffer_size中，然后调用MRR接口将缓存中的键值根据RowID进行排序，根据RowID的排序顺序来访问实际的数据文件。并且通过join条件得到数据，这样连接条件之间也成为了顺序比对。
当使用BKA（Batched Key Access）算法时，不但需要确保联接的列参与match的操作（联接的列可以是唯一索引或者普通索引，但不能是主键），还要有对非主键列的search操作。例如下列SQL语句：
|
1 2 3 4 5 6 7 8 |
mysql> explain select a.gender, b.dept_no from employees a, dept_emp b where a.birth_date=b.from_date; +----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+ | 1 | SIMPLE | b | NULL | ALL | NULL | NULL | NULL | NULL | 331570 | 100.00 | NULL | | 1 | SIMPLE | a | NULL | ref | idx_birth_date | idx_birth_date | 3 | employees.b.from_date | 62 | 100.00 | Using join buffer (Batched Key Access) | +----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+ 2 rows in set, 1 warning (0.00 sec) |
列a.gender是表employees的数据，但不是通过搜索idx_birth_date索引就能得到数据，还需要回表访问主键来获取数据。因此这时可以使用BKA算法。但是如果联接不涉及针对主键进一步获取数据，内部表只参与联接判断，那么就不会启用BKA算法，因为没有必要去调用MRR接口。比如search的主键（a.emp_no），那么肯定就不需要BKA算法了，直接覆盖索引就可以返回数据了（二级索引有主键值）。如图：
MRR优势：
* 顺序读取不在需要磁盘动臂不断的移动来寻道和等待带盘片旋转的时间。
* 顺序读取有预读的优势。
* 每个块值需要读取一次，而不需要多次读取，这是理所当然，因为一个块中一般存储了多行数据，不使用MRR可能会导致同一块多次读取到。
MRR劣势：
* 排序是额外需要时间的，如果使用order limit n会导致更慢。
四、NLJ、BNL、BKA
- simple nested-loop join (NLJ)
Simple Nested-Loops Join从一张表中每次读取一条记录，然后将记录与嵌套表中的记录进行比较。MySQL文档描述算法伪代码如下：
|
1 2 3 4 |
For each row r in R do For each row s in S do If r and s satisfy the join condition Then output the tuple <r, s> |
这种方式采用逐层调用循环的方式，很显然这种方式适用于任何场景，不过在被连接表没有索引的情况下，那么效率极低。
|
1 2 |
mysql> set optimizer_switch ='block_nested_loop=off'; Query OK, 0 rows affected (0.00 sec) |
—ref 索引扫描
|
1 2 3 4 5 6 7 8 |
mysql> explain select * from testzh force index(id2), testzh10 where testzh.id2 = testzh10.id2; +----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+ | 1 | SIMPLE | testzh10 | NULL | ALL | id2 | NULL | NULL | NULL | 99900 | 100.00 | Using where | | 1 | SIMPLE | testzh | NULL | ref | id2 | id2 | 5 | test.testzh10.id2 | 1 | 100.00 | NULL | +----+-------------+----------+------------+------+---------------+------+---------+-------------------+-------+----------+-------------+ 2 rows in set, 1 warning (0.00 sec) |
—ALL 全表扫描
|
1 2 3 4 5 6 7 8 |
mysql> explain select * from testzh force index(id2), testzh10 where testzh.name = testzh10.name; +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+ | 1 | SIMPLE | testzh10 | NULL | ALL | NULL | NULL | NULL | NULL | 99900 | 100.00 | NULL | | 1 | SIMPLE | testzh | NULL | ALL | NULL | NULL | NULL | NULL | 100031 | 10.00 | Using where | +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+-------------+ 2 rows in set, 1 warning (0.00 sec) |
总结：一般用于被链接表有索引的方式ref或者eq_ref，并且BKA代价较高，被连接表没有索引一般使用BNL。
- Block Nested-Loop (BNL)
很显然这种方式一般是用来优化被连接表没有索引，这被连接表方式为ALL或者index，因为这种join使用NLJ实在太慢了，需要优化他对内层表驱动的次数，那么加入一个缓存叫做join_buffer_size我们考虑2个表连接的方式，如下：
|
1 2 3 4 5 6 7 8 |
mysql> explain select * from testzh, testzh10 where testzh.name = testzh10.name; +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+ | 1 | SIMPLE | testzh10 | NULL | ALL | NULL | NULL | NULL | NULL | 99900 | 100.00 | NULL | | 1 | SIMPLE | testzh | NULL | ALL | NULL | NULL | NULL | NULL | 100031 | 10.00 | Using where; Using join buffer (Block Nested Loop) | +----+-------------+----------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+ 2 rows in set, 1 warning (0.00 sec) |
扫描testzh10表的相关字段，至少testzh10.name包含其中，存入join_buffer_size，当join_buffer_size满后，对testzh进行一次扫描，并且对扫描到的值和join_buffer_size中的数据根据条件testzh.name=testzh10.name进行比对，如果符合则放回，不符合则抛弃，比对完成后，清空buffer，继续扫描testzh10剩下的数据，满了后又读取一次testzh和join_buffer_size中的数据根据条件testzh.name=testzh10.name比对，如此反复直到结束，我们考虑这样的优化方式相对于BNL确实减少读取testzh表的次数，而且是大大减少，那为什么不使用MRR排序后在比对呢？因为testzh 压根没用到索引，你join_buffer_size中的数据排序了，但是testzh表中关于testzh10.name的数据任然是无序的，没有任何意义，使用MRR这种原理类似归并排序，必须两个数据集都是排序好的，所以这里用不到MRR。
总结：一般用于被连接表方式为ALL或者index(索引覆盖扫描)
- Batched Key Access Joins (BKA)
这种方式在MRR中已经讲了很多，其目的在于优化ref或者eq_ref使用NLJ连接的方式。
|
1 2 3 4 5 6 7 8 |
mysql> explain select * from testzh, testzh10 where testzh.id2 = testzh10.id2; +----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+ | 1 | SIMPLE | testzh | NULL | ALL | id2 | NULL | NULL | NULL | 100031 | 100.00 | Using where | | 1 | SIMPLE | testzh10 | NULL | ref | id2 | id2 | 5 | test.testzh.id2 | 1 | 100.00 | Using join buffer (Batched Key Access) | +----+-------------+----------+------------+------+---------------+------+---------+-----------------+--------+----------+----------------------------------------+ 2 rows in set, 1 warning (0.00 sec) |
这种方式的原理上就是通过顺序的连接条件的比对，减少随机读取的可能。
五、随机顺序写代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
/************************************************************************* > File Name: seqsca.c > Author: gaopeng > Mail: gaopp_200217@163.com > Created Time: Wed 21 Dec 2016 02:24:04 PM CST ************************************************************************/ #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <errno.h> #include <time.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <string.h> #define __USE_GNU 1 static int i=1; void eprintf(const char* outp) { write(STDOUT_FILENO,outp,strlen(outp)); i++; exit(i); } void ffprintf(const char* outp) { write(STDOUT_FILENO,outp,strlen(outp)); } void eperror(void) { perror("error"); i++; exit(i); } int main(int argc,char* argv[]) { int sca[20001]; //sca[0] not used char *buffer=NULL; char *ct=NULL; int i; int openwflags = O_CREAT | O_WRONLY |O_EXCL ;//|O_SYNC no sync used os buffer max performance for wirte int openrflags = O_RDONLY | O_DIRECT; //open use o_direct not use os cache disable preread int fdr; int fdwse,fdwsc; off_t file_size; time_t t1; time_t t2;//time used return int m; time(&t1); srand(t1); if(argc !=2 || strcmp(argv[1],"--help")==0 ) { eprintf("./tool readfile \n"); } buffer=valloc(4096); //one block 4K allocate aligned memory //init data array for(i=1;i<=20000;i++) { sca[i] = rand()%200000; } for(i=1;i<=20;i++) { printf("fisrt sca array: %d\n",sca[i]); } umask(0); if ((fdr = open(argv[1],openrflags)) == -1) { eperror(); } if(file_size=lseek(fdr,0,SEEK_END) < 943718400 ) { eprintf("testfile must > 900M \n"); } // start sequential read t2 = time(NULL); ct = ctime(&t2); if ((fdwse = open("tsq",openwflags,0755)) == -1) { eperror(); } lseek(fdr,0,SEEK_SET); printf("sequential cpy begin Time: %s",ct); ffprintf("begin cpy use sequential read buffer is 4k:\n"); m = 0; for(i=1;i<=20000;i++) { if(i%5000 == 0) { m++; t2 = time(NULL); ct = ctime(&t2); printf("per %d % ,Time:%s",25*m,ct); } if(read(fdr,buffer,4096) == -1) { eperror(); } if(write(fdwse,buffer,4096) == -1) { eperror(); } } ffprintf("\n"); close(fdwse); /* close(fdr); if ((fdr = open(argv[1],openrflags)) == -1) { eperror(); } */ // start scattered read if ((fdwsc = open("tsc",openwflags,0755)) == -1) { eperror(); } t2 = time(NULL); ct = ctime(&t2); printf("scattered cpy begin Time: %s",ct); m = 0; ffprintf("begin cpy use scattered read read buffer is 4k:\n"); for(i=1;i<=20000;i++) { if(i%5000 ==0) { m++; t2 = time(NULL); ct = ctime(&t2); printf("per %d % ,Time:%s",25*m,ct); } if (lseek(fdr,4096*sca[i],SEEK_SET) == -1) { ffprintf("lseek\n"); eperror(); } if(read(fdr,buffer,4096) == -1) { ffprintf("read\n"); eperror(); } if(write(fdwsc,buffer,4096) == -1) { ffprintf("write\n"); eperror(); } } ffprintf("\n"); close(fdwsc); close(fdr); free(buffer); } |
<参考>
http://blog.itpub.net/7728585/viewspace-2129502
