基本结构
运行流程
页结构
结构
- 每个页通过双向链表连接下一个和上一个页,因此页与页之间不需要物理上联系(及不需要一定使用连续磁盘空间)FIL_PAGE_PREV,FIL_PAGE_NEXT
- 页的大小统一为16kb,空闲区域如果分配完后会申请新的页
- 插入的数据不会引起重新排列,由于行数据库有单链表,因此只会修改链表的指向
- 每个页都存在页头和页尾
- 都存在校验和,用于检验页是否被完整传输
页目录
- 在页尾上面,本质是索引
- 每最多8条记录成为一个槽,每个槽记录8条记录中最大的地址,对槽之间查找可以使用二分搜索
类型
- 数据页(B-tree Node)
- undo页(undo Log Page)
- 系统页 (System Page)
- 事物数据页 (Transaction System Page)
- 插入缓冲位图页(Insert Buffer Bitmap)
- 插入缓冲空闲列表页(Insert Buffer Free List)
- 未压缩的二进制大对象页(Uncompressed BLOB Page)
- 压缩的二进制大对象页 (compressed BLOB Page)
行结构
结构
- 页最少两行,分别是头和尾,不存真实数据
- 被删除的行会组成一个垃圾链表
记录头
记录头信息固定占用5个字节也就是40位,不同位代表不同信息,主要有:
- delete_mask 标记该记录是否被删除
- record_type 表示当前记录的类型 0表示普通记录,1表示B+树非叶子节点记录,2表示最小记录,3表示最大记录
- next_record 表示下一条记录的相对位置
删除行时,会先修改next_record为垃圾链表,而不会直接断开
真实数据首列
隐藏列中的信息因为与事务和主键有关,所以很重要,总共占用19个字节,有三列:
- row_id (不必须) 替补主键id
- trx_id 事务id
- roll_pointer 回滚指针
优先使用用户自定义主键作为主键,如果用户没有定义主键,则选取一个
Unique
键作为主键,如果表中连Unique
键都没有定义的话,则InnoDB
会为表默认添加一个名为row_id
的隐藏列作为主键。
Null值列表
- 某个列如果为NULL,则直接置位(节省空间)
可变长度列表
- 每个最大两个字节(2^16=65535 每个字符最多4个字节,varchar最大为16383字符)
- 如果存储太大,数据会直接放到溢出页之中,本体只储存溢出页的地址
类型
- Dynamic (5.7.0默认)
- Compact
- Compressed
索引
为什么用B+树
- 二叉树高度太高
- B树(实际上就是二叉树中单节点多个值降低高度)范围查找麻烦(跨层),查询效率不稳定(因为结果可能在不同层)
为什么不用跳表
- B-tree索引可以有效地利用磁盘I/O,主要是因为B-tree索引的节点大小和磁盘块大小相当,跳表不可以
- 访问时间不稳定,因为跳表的索引方法有随机成分
- 只能在单个维度上进行排序,不适合多维范围查询
- 跳表的性能表现更依赖于内存的访问速度(因为需要通过指针访问地址,所以需要全部加载到内存中),对于磁盘存储的数据库来说,跳表不如B-tree
B+树
- 所有数据存储在最底层,解决查询效率不一致问题和高度
- 所有的节点都是页,父节点的页的行类型为索引,而且父节点不存储数据,只存储key和下一层页的指针(节约空间)
聚簇索引和非聚簇索引
- 数据库会建立key索引(对于每张表),如果额外出现索引,那么索引的key为要索引的值,val为key
- 非聚簇索引拿到key后还要用key再次在自动生成的索引中再次寻找
联合索引
- index(a,b,c)为例建立这样的索引相当于建立了索引a、ab、abc三个索引
- 这部分是局部有序的,例如下面,a是有序的,当a相同时候,b是有序的
最左匹配原则
- 在 InnoDB 中联合索引只有先确定了前一个(左侧的值)后,才能确定下一个值。如果有范围查询的话,那么联合索引中使用范围查询的字段后的索引在该条 SQL 中都不会起作用
- 意味着重要的有辨识度的字段建立索引的时候需要放在前面(比如姓名)
重要参考
- https://zhuanlan.zhihu.com/p/115778804
覆盖索引
- 普通索引(也叫做二级索引)的查找方式为在普通索引下找到底层之后,拿到key,使用这个key回表查询,如果需要避免回表查询,需要使用覆盖索引,其实只是一种特殊的索引
- 覆盖索引不需要回表查询因为该缩影底层已经包含了需要被查询的数据,==核心是建表的时候二级索引使用联合索引,把需要找到的字段都包含在联合索引中,这样就不需要回表查询==
example:
select a,b,c from table where a=10 and b>10
这条语句使用index(a,b,c)可以使用到索引,index(b,a,c)也可以,但是index(c,a,b)不可以
稀疏和稠密索引
- 稠密索引:在密集索引中,数据库中的每个搜索键值都有一个索引记录。这样可以加快搜索速度,但需要更多空间来存储索引记录本身。索引记录包含搜索键值和指向磁盘上实际记录的指针。
- 稀疏索引: 在稀疏索引中,不会为每个搜索关键字创建索引记录。此处的索引记录包含搜索键和指向磁盘上数据的实际指针。要搜索记录,我们首先按索引记录进行操作,然后到达数据的实际位置。
- 这两种索引都要通过折半查找或者叫做二分查找来确定数据位置,不同的是密集索引,只需要通过二分查找到搜索值=索引的索引记录就能确定准确的数据位置,而稀疏索引则需要先定位到搜索值>索引值的最小的那个,然后在通过起始位置去定位具体的偏移量。
- 在大多数场景密集索引查询效率更高,在大多数场景稀疏索引占用空间更小。
- mysql中密集索引决定了表的物理排列顺序,所以一个表只能有且仅有一个密集索引
- 稀疏索引适用于具有大量重复值的列,或者具有大量空值的列。它可以显著减小索引的大小,从而提高查询性能,并减少存储空间的占用。
事务
Atomic原子性
- 事务不可分割,最小操作单元,要么一起成功,要么一起不成功
- 使用undolog保证
undolog
- 使用的是物理记录而不是逻辑记录
- 用于事务失败时候的回滚
- 原始数据会记录在undolog中,然后把修改后的数据事务版本号改成当前事务版本号,并直接修改数据,并把DB_ROLL_PTR 地址指向undo log数据地址
Isolation隔离性
- 事务之间相对隔离,不能相对干扰,不能查看彼此未提交的数据
- 写和写的隔离使用锁,写和读的隔离通过MVCC
查询类型
快照读
- 简单的select操作,属于快照读,不加锁。它读的是记录的快照版本(这个版本跟MVCC有关)
当前读
- 要加锁的特殊的读操作,它读的是记录的最新版本.
-- 共享读锁
select * from table where ? lock in share mode;
-- 排他锁
select * from table where ? for update;
-- 增删改也属于当前读,因为要先看这条记录在不在
insert into table values (…);
update table set ? where ?;
delete from table where ?;
锁
乐观锁,悲观锁
[!important] 优缺点 乐观锁的缺点在于大量并发时候失败次数多,冲突失败概率高,优点是无锁化,运行速度快(在没多少冲突情况下),适用于冲突少的 悲观锁缺点是需要上数据库级别锁,速度慢,优点是失败概率低,适用于冲突多的
- 乐观锁使用类似于version检测的办法(类似状态机),在修改的时候判断状态,
update ... where version=1
- 悲观锁使用行锁,直接锁定该行不能修改,
select …for update
,悲观锁的实现→ 参考
共享锁S,排他锁X
- 都是悲观锁,和读写锁类似
Gap Lock间隙锁
- 只存在于可重复读隔离级别,目的是为了解决可重复读隔离级别下幻读的现象。 >假设,表中有一个范围 id 为(3,5)间隙锁,那么其他事务就无法插入 id = 4 这条记录了,这样就有效的防止幻读现象的发生。 >间隙锁的意义只在于阻止区间被插入,因此是可以共存的。一个事务获取的间隙锁不会阻止另一个事务获取同一个间隙范围的间隙锁,共享(S型)和排他(X型)的间隙锁是没有区别的,他们相互不冲突,且功能相同。
加锁过程
- select分为当前读和快照读两种类型,除非加上share或者for update为加S或者X锁,其他都为快照读,不加锁
- update,insert,delete都是当前读,会插入插入意向锁,插入成功之后,上行锁,和gap互相排斥
- 记录锁永远都是加在索引上的,即使一个表没有索引,InnoDB也会隐式的创建一个索引,并使用这个索引实施记录锁。
锁实现原理
-
每个事务都有一个链表,链表的元素就是锁,通过这样事务可以快速遍历所有自己加的锁.每个锁结构体都记录有自己所在的page
每个事务会维护一个trx_lock_t的结构体,其中trx_locks指向lock_t的链表,通过lock_t的trx_locks双向链表从而将属于同一个事务持有的锁串联起来,因为一个事务有可能在多个page上面持有锁。另外如果一个事务被阻塞,wait_locks指向阻塞的lock_t。
-
通过计算某一行所在的表空间(space),空间中的数据页码(page_no),通过hash计算属于某个bucket(通过拉链法解决hash冲突的问题),通过遍历bucket的元素(一定需要遍历所有,因为一个page可能嫁了很多个锁)并判断是否是同一个page
通过维护一张lock_sys的hash table将所有的lock_t组织起来,根据(space,page_no)通过hash算法计算出一样的hash value 将会放在同一个bucket中,因为hash算法的局限性,不同的(space,page_no)有可能生成同样的hash value,我们知道解决hash冲突通常都是后面拉出一张链表,所以很自然的同一个bucket中的lock_t组成一个链表结构
-
每个lock_t存放了bitmap,每个位对应每一行数据,如果行对应的bit为1说明已经被上锁
脏读,不可重复读,幻读
- 脏读:读到其他事务还没有提交的数据
- 不可重复读:同一个数据开始读和再次读结果不一样
- 幻读:每次查询到之前没有的数据
不可重复读和幻读区别,不可重复读针对的是update,即对同一行的数据进行操作 幻读针对delete和insert,每次select结果不同,即对一张表进行操作 不可重复读可以通过行锁解决,或者通过乐观锁 幻读需要通过表锁解决
读未提交,读已提交,可重复读,串行读
- 分别对应解决上面三个问题
- mysql默认可重复读,oracle默认读已提交
- RR依旧存在在写场景下的幻读,详情参考
主流方式是使用读已提交,mysql使用的有历史的原因
MVCC
- 这种通过「版本链」来控制并发事务访问同一个记录时的行为就叫 MVCC(多版本并发控制)
- 通过版本链控制
- 核心思想尽量避免使用锁
- readview实际上就是,一个固定的数组,记录事务号的信息
RC和RR流程
- RC中只使用mvcc,不使用gap等锁,只是相当于在undolog中读取提交了事物的快照,RC读取的时候始终读取已提交事务,因此可能出现不可重复读的问题
- RR中只使用mvcc,mvcc中读取事务号小于等于的快照,解决部分幻读问题和不可重复读问题,不上锁依然有幻读问题,快照读的时候使用mvcc(记录第一次读的版本号),因此不出现重复读的问题,RR中涉及当前读的都默认加X锁
- 当前读在 RR 和 RC 两种隔离级别下的实现不一样:RC 只加记录锁,RR 除了加记录锁,还会加间隙锁,用于解决幻读问题。
- 使用gap间隙锁(for update),将查询范围锁定,避免插入和删除(插入意向锁互斥)可以解决幻读问题,仅仅只使用RR不能彻底解决幻读问题
- RC下每一行执行期前重新生成新的readview,因此每次读的都是commit的信息,RR下整个事务执行前生成一次readview,并且整个事务都是这个readview,读的是开启前的commit信息
- update在RC或者RR模式下都会直接加锁,因为要update,直到commit或者rollback,但是RU不会
对于MySQL默认的InnoDB存储引擎而言,在大多数情况下,UPDATE操作都会在更新行上加上排它锁(X锁),这意味着其他事务将无法同时访问该行,直到该事务提交或回滚。因此,在所有事务隔离级别下,都会对被更新的行加锁。 但是,这种锁的类型和范围是受隔离级别影响的。在读取未提交的数据(READ UNCOMMITTED)隔离级别下,其他事务可以读取并修改该行,而在可重复读(REPEATABLE READ)和串行化(SERIALIZABLE)隔离级别下,其他事务将无法读取或修改该行,直到当前事务完成。
Durable持久性
- 事务一旦提交,不会因为外部意外发生变化
- 如果是内存buffer还没写入磁盘就崩了,通过redolog恢复,写道一半崩了导致不完整传输,通过双写缓冲区
redolog
- 相当于在页写入之前先写入redolog buffer,然后redobuffer写入redolog file比页刷入磁盘快(这部分因为redolog是顺序写,表页是随机写,因此写这个更加快)
- redolog作为类似环形缓冲区,通过指针位移进行刷新
- binlog 是追加写,写满一个文件,就创建一个新的文件继续写,不会覆盖以前的日志,保存的是全量的日志。用于备份恢复、主从复制.写的是逻辑
- redo log 是循环写,日志空间大小是固定,全部写满就从头开始,保存未被刷入磁盘的脏页日志。用于掉电等故障恢复.因为 redo log 文件是循环写,是会边写边擦除日志的,只记录未被刷入磁盘的数据的物理日志,已经刷入磁盘的数据都会从 redo log 文件里擦除。写的是实际二进制数据
策略
- 当设置为0,完全不管,等后台1s一次的自动刷,最多丢失1s的记录
- 设置为1,每次提交确认落盘,影响性能,能确保不丢失
- 设置未2,写入os的cache page,操作系统自己决定何时写入,mysql崩没问题,但是操作系统崩会损失记录
双写缓冲
- 因为mysql页大小和系统页大小不一样,有可能页传输到一半就崩了
- doublewrite缓冲区是一个硬盘存储区域,
InnoDB
在将从缓冲池中刷新的page写到InnoDB
数据文件中相应的位置之前,会先将这些page写在doublewrite缓冲区。如果在写page的过程中出现了操作系统、存储子系统或意外的进程退出等情况,InnoDB
可以在崩溃恢复过程中从doublewrite缓冲区中找到一个完整且正确的page副本
Consistency一致性
- 无论多少事务同时执行以及任何操作,执行前,过程中,执行后的状态都是一致确定的
- 上面三条满足自动满足
日志
binlog
- 在innodb上层的日志系统,并非innodb生成
顺序
写redo 预提交日志 写binlog 日志 写redo conmit日志 redo有两条记录
格式区别
- binlog
- 逻辑记录,不可用于崩溃恢复
UPDATE `db_test`.`tb_user` WHERE @1=5 @2='赵白' @3=91 @4='1543571201' SET @1=5 @2='赵白' @3=18 @4='1543571201'
UPDATE `db_test`.`tb_user` WHERE @1=6 @2='赵白' @3=91 @4='1543571201' SET @1=5 @2='赵白' @3=18 @4='1543571201'
UPDATE `db_test`.`tb_user` WHERE @1=7 @2='赵白' @3=91 @4='1543571201' SET @1=5 @2='赵白' @3=18 @4='1543571201'
- redolog
- 物理记录,可以用于崩溃恢复
把表空间10、页号5、偏移量为10处的值更新为18。
把表空间11、页号1、偏移量为2处的值更新为18。
把表空间12、页号2、偏移量为9处的值更新为18。
- undolog
- 记录修改前的原始数据内容,并用指针连接
三大特性
insert buffer
- 用于更新非聚簇索引的,当更新数据时候,一般年需要同时更新索引,但是当索引B+树不在buffer中时,从磁盘读取非常慢
- 因此先写入insert buffer,然后下次加载索引B+树或者定时任务时候在合并到索引中
自适应hash
- innodb存储引擎有一个机制,可以监控索引的搜索,如果innodb注意到查询可以通过建立哈希索引得到优化,那么就可以自动完成这件事.
双写缓冲区
主从复制
- 底层实际上和redis的AOF备份类似,底层使用keepalive保证主从切换
- master服务器将数据的改变记录二进制binlog日志,当master上的数据发生改变时,则将其改变写入二进制日志中;=
- slave服务器会在一定时间间隔内对master二进制日志进行探测其是否发生改变,如果发生改变,则开始一个I/OThread请求master二进制事件
- 同时主节点为每个I/O线程启动一个dump线程,用于向其发送二进制事件,并保存至从节点本地的中继日志中,从节点将启动SQL线程从中继日志中读取二进制日志,在本地重放,使得其数据和主节点的保持一致,最后I/OThread和SQLThread将进入睡眠状态,等待下一次被唤醒。
keepalive
过程
- master需要向所有的slave群发包,如果slave发现太久没有master发送,断定为master宕机,选举出新的master
- 选举过程中slave会交换权重,然后比较权重大小选举出性的master(这里可能出现脑裂问题)
- 发送ARP包给路由器,为了更新由器上的 ARP 缓存,将虚拟 IP 对应的 mac 地址更新为竞选 master 成功的 backup 上的 mac
参考
- https://juejin.cn/post/6974225353371975693
- https://zhuanlan.zhihu.com/p/142139541
- https://www.cnblogs.com/shoshana-kong/p/10516404.html
- https://juejin.cn/post/6931752749545553933
- https://zhuanlan.zhihu.com/p/213770128
- https://zhuanlan.zhihu.com/p/382010436
- https://www.yasinshaw.com/articles/109
- https://www.modb.pro/db/542415 推荐书籍
- MySQL技术内幕:InnoDB存储引擎