mysql核心原理

高性能、高可用存储架构

b-tree 和 b+tree

b-tree

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解下磁盘的相关知识。

系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

1show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

一个page 就是树的一个节点

特点：

多叉，多阶
拥有二叉树多一些性质
平衡，每个节点多所有子树高度一致
比较矮

性质：m阶b树，最多拥有m个子节点（m阶，可以理解为高度）

元素个数：假设一个节点存储多元素个数为x

根节点：1 <=x<=m-1
非根节点， (ceil) m/2 <= x <=m-1

子节点个数： y=x+1

根节点:2<= y <=m
非根节点： (ceil) m/2 <= y <= m
每个节点最多有m个子节点
除根节点外，每个节点至少有 ceil(m/2) 个子节点
根节点要么为空，要么就是独根，否则至少有2个子节点
有k个子节点多节点必有k个关键词，
ki(i=1,…n)为关键字，且关键字升序排序。
Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

单个节点(页）可以保存多个数据. 每个节点是保存data数据多，结束16kb页，一行数据是1kb。那么一页就是16个数据。 3层的树只能保存16*16*16=4096条记录，所以高度还是会挺高的。

范围查找要遍历的树节点多。

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

b+tree

叶子节点保存数据信息，非叶子节点不保存

节点保存的元素数等于m

叶子节点通过指针链接（双向链表），方便查找，只需要遍历叶子节点

非叶子节点不保存数据，保存数据，数据更多，一次io获得更多数据。

3阶的树能保存12亿左右的数据

16 （一个页16kb) * 1024/6(关键信息6b) * 16 （一个页16kb) * 1024/6(关键信息6b) * 16 = 12亿左右

为什么mysql使用b+tree, 而不是用b-tree ?

叶子节点基于索引排序更优化

非叶子节点不存包数据，保存索引数据更多，一次i/o获取更多数据条目。

mvcc原理

MVCC，全称Multi-Version Concurrency Control，即多版本并发控制，是乐观锁的一种实现方式，可以做到读不加锁，读写不冲突，解决读-写冲突的无锁并发控制。

MVCC的目的就是多版本并发控制，在数据库中的实现，就是为了解决读写冲突，它的实现原理主要是依赖记录中的 3个隐式字段，undo log ，Read View 来实现的。

InnoDB MVCC的实现基于undo log，通过回滚指针来构建需要的版本记录。通过ReadView来判断哪些版本的数据可见。同时Purge线程是通过ReadView来清理旧版本数据。

MVCC 只在 Read Commited 和 Repeatable Read 两种隔离级别下工作。

快照读与当前读

快照读：简单的select操作，不需要加锁，基于MVCC和undo log来实现的，读取的是记录的可见版本（有可能是历史版本）。

当前读：总是读取最新版本的记录。

insert、update、delete
select … lock in share mode
select …for update

undo log

undo log主要记录的是数据的逻辑变化，为了在发生错误时回滚之前的操作，需要将之前的操作都记录下来，然后在发生错误时才可以回滚。

作用

用于事务的回滚

undo日志用于存放数据修改被修改前的值，如果这个修改出现异常，可以使用undo日志来实现回滚操作，保证事务的一致性。

undo日志，只将数据库逻辑地恢复到原来的样子，在回滚的时候，它实际上是做的相反的工作

用于MVCC

undo log的类型主要分为：

insert undo log
update undo log

insert undo log是指在insert 操作中产生的undo log，因为insert操作的记录，只对事务本身可见，对其他事务不可见。故该undo log可以在事务提交后直接删除，不需要进行purge操作。

update undo log记录的是对delete 和update操作产生的undo log，该undo log可能需要提供MVCC机制，因此不能再事务提交时就进行删除。提交时放入undo log链表，等待purge线程进行最后的删除。

update undo log

具体工作原理分以下情况讨论

更新主键

update table set id=3 where id=1

聚簇索引和二级索引都无法进行in place update，都会产生两个版本

update分两步执行，先删除该行，再插入一行目标行

更新非主键

update table set name=y2 where id =1

聚簇索引可以in place update，二级索引产生两个版本

聚簇索引记录undo log，二级索引不记录undo log

更新二级索引，同时需要判断是否修改索引页面的MAX_TRX_ID

删除操作

删除操作实际上不会直接删除，而只是标记为删除，最终的删除操作是purge线程完成的

purge线程两个主要作用

清理undo log

清除page里面带有Delete_Bit标识的数据行。在InnoDB中，事务中的Delete操作实际上并不是真正的删除掉数据行，而是一种Delete Mark操作，在记录上标识删除，真正的删除工作需要后台purge线程去完成。

三个隐式字段

DB_TRX_ID: 6byte，最近修改(修改/插入)事务ID：记录创建这条记录/最后一次修改该记录的事务ID

DB_ROLL_PTR: 7byte，回滚指针，用于配合undo log，指向这条记录的上一个版本

DB_ROW_ID: 6byte，隐含的自增ID（隐藏主键），如果数据表没有主键，InnoDB会自动以DB_ROW_ID产生一个聚簇索引

注意：实际上每条记录的头信息（record header）里都有一个专门的bit（deleted flag）来表示当前记录是否已经被删除

Read View(读视图)

Read View就是事务进行快照读操作的时候生产的读视图(Read View)，在该事务执行的快照读的那一刻，会生成数据库系统当前的一个快照，记录并维护系统当前活跃事务的ID（当每个事务开启时，都会被分配一个ID, 这个ID是递增的，所以最新的事务，ID值越大）

Read View主要是用来做可见性判断的, 即当我们某个事务执行快照读的时候，对该记录创建一个Read View读视图，把它用来判断当前事务能够看到哪个版本的数据，既可能是当前最新的数据，也有可能是该行记录的undo log里面的某个版本的数据。

隔离级别与 read view 产生的时机

MVCC 只在 Read Commited 和 Repeatable Read 两种隔离级别下工作。

在RC隔离级别下，是每个快照读都会生成并获取最新的Read View；

这就是我们在RC级别下的事务中可以看到别的事务提交的更新的原因

在RR隔离级别下，则是同一个事务中的第一个快照读才会创建Read View, 之后的快照读获取的都是同一个Read View。

即RR级别下，快照读生成Read View时，Read View会记录此时所有其他活动事务的快照，这些事务的修改对于当前事务都是不可见的。而早于Read View创建的事务所做的修改均是可见

核心算法

Read View的三个属性

trx_ids
- 一个数值列表，用来维护Read View生成时刻系统正活跃的事务ID
up_limit_id
- 记录trx_ids列表中事务ID最小的ID
low_limit_id
- ReadView生成时刻系统尚未分配的下一个事务ID，也就是目前已出现过的事务ID的最大值+1

RC隔离级别:每次进行快照读时都生成读视图 RR隔离级别:只有第一次时生成读视图，之后每次都使用第一次时都读视图

可见性判断的流程

遍历DB_TRX_ID执行以下步骤，直到找到当前事务可见的最新数据：

遍历方法：如果当前DB_TRX_ID这条记录不满足当前事务的可见性，可通过这条记录的DB_ROLL_PTR回滚指针去取出undo log中前一个版本的DB_TRX_ID

step1：比较DB_TRX_ID 小于 up_limit_id

如果小于，则当前事务能看到DB_TRX_ID 所在的记录；即该记录是可见的最新的记录，如果大于等于进入step2

step2: 判断 DB_TRX_ID 大于等于 low_limit_id

 如果大于等于则代表DB_TRX_ID 所在的记录在Read View生成后才出现的，那对当前事务肯定不可见，继续遍历下一个DB_TRX_ID。

如果小于则进入step3

step3：判断DB_TRX_ID 是否在活跃事务之中

如果在，则代表当前事务的Read View生成时刻，DB_TRX_ID这个事务还在活跃，还没有Commit，DB_TRX_ID这个事务修改的数据，当前事务也是看不见的；即对当前事务不可见，继续遍历下一个DB_TRX_ID

如果不在，则说明，DB_TRX_ID这个事务在当前事务的Read View生成之前就已经Commit了，DB_TRX_ID这个事务修改的结果，对于当前事务是可见的。

案例分析1,RR级别

事务0	事务1	事务2	事务3	事务4
Insert , commit
	开启	开启	开启	开启
				update commit
		Select 不可见

图中事务2中的select的read view。

trx_list:1,2,3

up_limit_id:1

low_limit_id:5

db_trx_id:4

案例分析2,RR级别

事务0	事务1	事务2	事务3	事务4
Insert , commit
	开启	开启	开启	开启
		select
				update commit
		Select 不可见
		commit
		select 可见

图中事务2中的select的read view。看第一次select时机。

trx_list:1,2,3,4

up_limit_id:1

low_limit_id:5

db_trx_id:0 ( 第一次select 快照的时候 db_trx_id=0)

MVCC查询的工作流程

查询主键索引

生成Read View读视图

通过主键查找记录，根据记录里的DB_TRX_ID与Read View读视图进行可见性判断

配合DB_ROLL_PTR回滚指针和undo log来找到当前事务可见的数据记录

查询二级索引

生成Read View读视图

比较读视图的up_limit_id与MAX_TRX_ID大小

如果MAX_TRX_ID小于本次Read View的up_limit_id，则全部可见，过滤记录中的有效记录

否则，无法通过二级索引判断可见性，需要一次遍历每条记录，反查到聚簇索引记录，通过聚簇索引记录来判断可见性

RR级别，每次都是读取第一次快照读的数据吗

不是，幻读， 1个事务插入数据，并提交，另外一个事务一开始没查到这条记录，但是去更新这个刚插入id的记录（当前读），下次就能查到了。

解决方案:select …. for update ,加锁，保证执行期间不被插入。

2阶段提交

主从复制和读写分离

mysql单服务器配置多实例运行

 1[mysqld_multi]
 2#mysqld = /usr/local/mysql/bin/mysqld_safe
 3mysqladmin = /usr/local/mysql/bin/mysqladmin
 4user = root
 5password   = 123456
 6[mysqld3307]
 7server-id=3307
 8port=3307
 9log-bin=mysql-bin
10log-error=/Users/zhja/mysql-cluster/master/mysqld.log
11tmpdir=/Users/zhja/mysql-cluster/master
12 
13slow_query_log=on
14slow_query_log_file =/Users/zhja/mysql-cluster/master/mysql-slow.log
15long_query_time=1
16socket=/Users/zhja/mysql-cluster/master/mysql_3307.sock
17pid-file=/Users/zhja/mysql-cluster/master/mysql.pid
18 
19basedir=/Users/zhja/mysql-cluster/master
20datadir=/Users/zhja/mysql-cluster/master/data
21 
22[mysqld3308]
23server-id=3308
24port=3308
25log-bin=mysql-bin
26log-error=/Users/zhja/mysql-cluster/slave/mysqld.log
27tmpdir=/Users/zhja/mysql-cluster/slave
28slow_query_log=on
29slow_query_log_file =/Users/zhja/mysql-cluster/slave/mysql-slow.log
30long_query_time=1
31socket=/Users/zhja/mysql-cluster/slave/mysql_3308.sock
32 
33pid-file=/Users/zhja/mysql-cluster/slave/mysql.pid
34basedir=/Users/zhja/mysql-cluster/slave
35datadir=/Users/zhja/mysql-cluster/slave/data
36 
37read_only=1

执行和查看

1killall mysqld  
2mysqld_multi --defaults-extra-file=/etc/my.cnf start
3mysqld_multi --defaults-file=/etc/my.cnf report  
4mysql -uroot -p -P3308 -h127.0.0.1

主库执行sql

1grant replication slave on *.* to "coyp@%" identified by 'copy'; -- copy 用户任意地址，所有库和表
2show master status; -- 看日志的位置，文件名

主库已经有数据，mysqldump 出sql文件，给从库，从库先导入改导出的sql。

从库，不开bin log。

1change master to master_host='192.168.0.107',master_user='copy',master_password='copy',master_log_file='mysql-bin.000001',master_log_pos=730;
2
3start slave; -- 开启主从复制
4show slave status;

读写分离：一般框架会提供这个功能，读从库，写主库，可以指定使用主库进行查询。因为从库的数据有延迟。

Mysql核心原理

高性能、高可用存储架构

b-tree 和 b+tree

b-tree

b+tree

为什么mysql使用b+tree, 而不是用b-tree ?

mvcc原理

快照读与当前读

undo log

作用

update undo log

purge线程两个主要作用

三个隐式字段

Read View(读视图)

隔离级别与 read view 产生的时机

核心算法

案例分析1,RR级别

案例分析2,RR级别

MVCC查询的工作流程

查询主键索引

查询二级索引

2阶段提交

主从复制和读写分离

links

版权

Mysql核心原理

高性能、高可用存储架构

b-tree 和 b+tree

b-tree

b+tree

为什么mysql使用b+tree, 而不是用b-tree ?

mvcc原理

快照读与当前读

undo log

作用

update undo log

purge线程两个主要作用

三个隐式字段

Read View(读视图)

隔离级别与 read view 产生的时机

核心算法

案例分析1,RR级别

案例分析2,RR级别

MVCC查询的工作流程

查询主键索引

查询二级索引

2阶段提交

主从复制和读写分离

links

版权

相关文章