innoDB相关

体系结构

20190905103235.png

InnoDB存储引擎由多个内存块组成. 可以认为这些内存块组成了一个很大的内存池. 主要负责:

  • 维护所有进程/线程需要访问的多个内部数据数据
  • 缓存磁盘上的数据. 方便快速的读取.同时在对磁盘文件进行修改之前在这里缓存
  • 重做日志redo log缓冲

后台线程

innoDB是个多线程模型. 因此很多线程都具有不同的分工.

  • Master Thread 核心的后台线程. 负责将缓冲池中的数据异步刷新到磁盘. 保证一致性. 包括脏页, 合并插入缓冲. undo页回收.
  • IO Thread 存储引擎中使用了大量的AIO来处理写IO请求. 而IO Thread工作主要负责这些IO请求的回调(callback)处理. 大致分为几类: read, write, insert buffer, log.
  • purge Thread. 在事务提交之后. 其所使用的undolog可能不再需要了. 因此需要此线程来回收已经使用并分配的undo页.
  • page cleaner Thread 脏页的刷新操作

    内存

缓冲池

innoDB存储引擎是基于磁盘存储的. 存储其中的记录是按照页的方式进行管理. 由于CPU速度和磁盘速度的鸿沟, 采用缓冲池技术来提供数据库整体效率.

缓冲池是一块简单的内存区域. 在数据库读取页时. 首先从磁盘中读到的页存放到缓冲池中, 这个操作称为页FIX, 下次读取相同页的时候, 判断是否在缓冲池中, 若在称该页在缓冲池中被命中. 直接读取.否则读取磁盘上的页.

对于数据库中的页的修改操作. 则首先修改缓冲池中的页. 然后以一定频率刷新到磁盘中上. 缓冲池中的页刷新到磁盘上. 不是每次页发生修改时就触发. 而是通过checkpoint机制刷新回磁盘上.

具体来说缓冲池中的页类型有: 索引页. 数据页, undo页, 插入缓冲, 自适应哈希索引. innoDB存储的锁信息. 数据字典信息等.

innoDB如何管理缓冲池这个很大的内存区域(LRU list,Free list, Flush list)

InnoDB使用优化过的LRU(最近最少使用)算法来管理. 在LRU列表中加入了midpoint位. 新读的页,虽然是最新访问的页. 并不是直接放入LRU列表首部. 而是放入到LRU列表中的midpoint位置. 这个算法在innoDB中成为 midpoint insertion strategy. 默认情况下 midpoint在LRU列表的5/8位置. midpoint之前的称为new列表 之后的称为old列表 可以简单理解为new列表是热点数据.

  • 为什么不采用朴素的LRU算法呢

是因为若是直接把页放在LRU列表首部. 那么某些sql操作可能会使缓冲池中的页被刷新出. 影响缓冲池的效率. 例如索引和数据扫描操作 这里操作可能访问很多页,或者全部页. 而这些操作通常来说仅在这次查询中需要. 斌不是热点数据. 如果放在了首部. 很可能需要的热点数据页从LRU列表中移除. 下次需要读取该页的时候, 就要去磁盘中读取了.

当数据库当启动时,LRU列表是空的.这些页都存放在free列表中,从需要从缓冲池分页时, 先在free列表中查找是否有空闲页, 有在在free中删除, 放入LRU列表中. 否则根据LRU淘汰算法. 淘汰尾端的页. 将腾出来的内存空间分配给新的页.

重做日志缓冲

innoDB引擎首先将重做日志信息放入到这个缓冲区.然后按一定频率将其刷新到重做日志文件中, 这个缓冲区不用很大. 只要保证一秒内事务量在这个缓冲区大小之内即可. 通常8M大小能够满足绝大部分需求.
重做日志在三种情况下会将缓冲区日志刷新到日志文件中.

  1. master Thread每个一秒将重做日志缓冲刷新到重做日志文件中去.
  2. 每个事务提交时, 将重做日志缓冲区刷新到重做日志文件中.
  3. 当重做日志缓冲池剩余空间小于1/2时.

InnDB的关键特性

插入缓冲(提升性能)

在innoDB存储引擎中.主键是行唯一标识符. 因此插入聚集索引是顺序的. 同时页中的行记录按照主键顺序存放的. 因此这种情况下的插入式非常快的.并不是所有主键插入都是顺序的. 比如主键是UUID.插入就是随机的. 或者指定主键的值插入. 也会是随机的.

在大部分应用中,很少出现表中只有一个聚集索引的情况,更多情况下,表上会有多个非聚集的secondary index (辅助索引)对于非聚集索引的插入和更新. innodb不是每一次都插入到索引页中. 而是判断插入的非聚集索引是否在缓冲池中. 若在直接插入. 若不再插入insert buffer对象中. 然后再以一定的频率和情况进行insert buffer和索引页子节点的merge合并操作. 这通常将多个插入合并到一个操作.这就大大提高了对于非聚集索引的插入性能.

这里存在一个问题. 当写密集时. insert buffer会占用过多的内存缓冲区. 默认最大是1/2. 如果这时宕机了, 会导致大量的insert buffer并没有合并到实际的非聚集索引中去. 导致这是恢复会需要很长时间. 极端的时候可能要几小时

  • change buffer. 可以视为insert buffer的升级版, innoDB对DML语句都进行缓存.分别是insert/update/delete buffer.和之前的insert buffer一样, change buffer依然适用于非唯一的辅助索引.

写缓充

双写(提升页可靠性)

双写分为两部分: 一部分是内存中的doublewrite buffer 大小为2MB. 另一部分是物理磁盘上共享表空间中连续的128页, 即两个区, 大小同样为2MB. 当对缓冲区脏页进行刷新时. 先将脏页复制到doublewrite buffer中. 之后通过doublewrite buffer再分两次, 每次1M顺序的写入磁盘上的共享表空间, 马上调用asyc函数, 同步磁盘.

自适应哈希索引

哈希是一种非常快的查找方法. 一般情况下时间复杂大度O(1), 仅需要一次查找就能定位数据. 而B+树的查找次数, 取决于树的高度. 如果是3层 则需要3次查找.
innoDB会监控对表上各个索引的查询. 如果观察到建立哈希索引能提升查询效率.则建立哈希索引, 这种行为叫自适应哈希索引.AHI. innoDB会根据访问分频率和模式来自动的为热点查询建立哈希索引. 条件是以同样的查询条件查询了一定次数, 比如100.页通过该模式访问了N次. 其中N=页中记录*1/16.

异步IO

为了提高磁盘操作效率. 数据库采用异步IO(AIO)的方式来处理磁盘操作.即每次IO操作都不需要等待上次IO的结束. AIO的另一个优势是可以进行IO merge.也就是将多个AIO和并未一个IO

刷新邻接页

当刷新一个脏页时. innoDB引擎会检测改页所在的区(extent)的所有页. 如果有脏页. 那么一起刷新. 在结合AIO可以将多个IO合并为一个IO.

索引和算法

B+树是传统意义上的索引. 叶子节点不是具体行的数据, 而是一页数据. 当查找都数据所在的页. 在通过二分查找的方式去查找具体数据.

B+树索引

B+树是为磁盘或其他直接存取辅助设备设计的一种平衡树. 在树中, 所有的记录节点都是按键值的大小顺序存放在同一层的叶子节点上. 由各个节点的指针相互连接

聚集索引

聚集索引是按照每张表的主键构造一颗B+树. 同时叶子节点中存放的即为整张表的行记录数据. 叶子节点称之为数据页. 每个数据页都通过一个双向链表进行连接. 聚集索引的存储并不是物理上连续的. 而是逻辑上连续的. 页时按照主键的顺序排序. 每个页中的记录也是通过双向链表进行维护的.

辅助索引

也叫非聚集索引. 叶子节点并不包含行记录的全部数据,叶子节点出了包含键值之外. 每个叶子节点中的索引行中还包含了一个书签.该书签用来告诉InnoDB引擎哪里可以找到与索引相对应的行数据.由于InnoDB存储引擎表示索引组织表,因此InnoDB存储引擎的辅助索引书签就是响应的聚集索引键. 辅助索引的存在并不影响数据在聚集索引中的组织.

当通过辅助索引来查询数据时. InnoDB存储引擎会遍历辅助索引并通过叶级别指针获得指向主键索引的主键, 然后在通过主键索引来找到一条完整的行记录. 举例来说. 如果一颗高为3的辅助索引树中查找数据. 首先通过3次查询找到主键. 然后在通过3次对聚集索引的查询. 最终找到一个完整的行数据. 因此需要6次逻辑IO访问以得到最终的一个数据页.

联合索引

由多个表字段组成的索引. 注意联合索引的顺序. 比如索引(a,b,c)

  • where a= “” 是可以应用到索引的
  • where a= “” and b= “” 可以应用
  • where a= “” and b =”” and c=’’ 可以
  • where a= “” order by b 可以. 顺便还使用了索引的有序性.
  • where a=”” order by c 应用了索引但没有应用有序性. 因为c是无序的.
  • where a =”” and c=”” 不能应用索引

覆盖索引

innoDB支持覆盖索引. 即从辅助索引就可以得到查询记录.而不需要查询聚集索引中的记录. 使用覆盖索引的好处是, 辅助索引不包含整行记录的所有信息.故其大小要远远小于聚集索引.因此可以减少IO操作.

覆盖索引的通俗说法就是, 查询条件和返回的数据. 都是索引的内容.

覆盖索引的另一个好处在于对统计而言的.

multi-range read优化

针对range ref eq-ref类的查询的优化, 将随机IO改变为顺序IO.

  • 查询得到的辅助索引键值放在一个缓存中, 辅助索引中的数据是根据辅助索引键值排序的.
  • 将缓存中键值按照RowId进行排序.
  • 根据RowId的顺利访问实际的数据文件.

index condition pushdown优化

首先索引查询时. 先按照索引来查找记录, 在根据where条件过滤数据. 在支持index condition pushdown之后, 在索引查找数据的时候就会判断是否可以进行where条件过滤, 也就是将where条件的部分过滤操作放在存储引擎层. 在某些查询下. 可以大大减少上层sql对数据的索取. 从而提升了性能.

全文检索

倒序索引

全文索引通常使用倒序索引实现, 和索引引用B+树一样. 倒序索引也一种数据结构. 它是以辅助表的形式存在的. 它在辅助表中存储了单词和单词在一个或者文档中所在位置的映射.

  • inverted file index 其表现形式为{单词, 单词所在文档的ID}
  • full inverted index 其表现形式为{单词,(单词所在文档ID, 在具体文档中的位置)}
innoDB的全文索引

采用的full inverted index的形式. 在innoDB中存在ilist, 因此在全文索引中, 有两个列, 一个是ward列 另一个是ilist字段. 并且在word上有索引, 此外ilist字段存放了position信息,

锁的类型

InnoDB支持两种行级锁:

  • 共享锁(S LOCK) 允许事务读一行数据
  • 排它锁(X LOCK) 允许事务删除或更新一行数据

X锁和任何锁都不兼容. S锁也只和S锁兼容. 兼容值的是对同一行数据而言的

此外 innoDB支持引擎多颗粒度锁定. 这种锁允许事务在行级上锁和表级上的锁同时存在. 为了支持在不同颗粒度上进行加锁操作. InnoDB支持一种额外的锁方式. 称之为意向锁(intention Lock). 意向锁是将锁定对象分成多个层次. 意向锁意味着事务希望在更细粒度上进行加锁.

  • 意向共享锁(IS LOCK) 事务想要获得一张表中某几行的共享锁.
  • 意向排他锁(IX LOCK) 事务想要获得一张表中某几行的排他锁.

一致性非锁定读

是指innoDB通过多版本控制的方式来读取当前执行时间数据库中的数据, 如果读取正在执行UPDATE或者DELETE操作,这时读取操作不会等待行的X锁释放. 相反的innoDB存储引擎会去读取快照数据. 快照数据是指行的之前版本数据. 改实现是通过undo段来完成的. 这是没有任何开销的. 读取快照数据也不需要上锁,因为没有事务会修改历史数据.

非锁定读大大提高了数据库的并发性. 但在不通事务隔离级别下的, 读取方式是同的.

MVCC(多版本并发控制) 快照数据就是当期行的之前的历史版本. 每行记录有多个版本. 一个行记录有多个快照数据.

一致性读锁定

在某些情况下用户需要显示地对数据库读取操作进行加锁, 保证数据逻辑的一致性. 而这种对数据库支持加锁语句. innoDB对于select语句支持两种一致性锁定读:

  1. select….for upadte 在读取是添加行级X锁
  2. select … lock share mode. 在读取是添加行级别S锁

行锁的3种算法

  1. record lock 单个行记录上锁 总是去锁住索引记录, 没有任何一个索引, 就使用隐士的主键进行锁定
    单条索引记录上加锁,record lock锁住的永远是索引,而非记录本身,即使该表上没有任何索引,那么innodb会在后台创建一个隐藏的聚集主键索引,那么锁住的就是这个隐藏的聚集主键索引。所以说当一条sql没有走任何索引时,那么将会在每一条聚集索引后面加X锁,这个类似于表锁,但原理上和表锁应该是完全不同的。

  2. Gap lock 间隙锁 锁定一个范围 不包含记录本身
    在索引记录之间的间隙中加锁,或者是在某一条索引记录之前或者之后加锁,并不包括该索引记录本身.

  3. Next-key lock: 1+2 锁定一个范围 并且锁定记录本身

phantom problem(幻像问题)

phantom problem问题是指 在一个事务下, 连续执行两次同样的SQL语句可能导致不同的结果. 第二次sql可能会返回之前不存在的行.

innoDB的默认隔离级别 repeatable read, 通过使用Next-key lock算法来避免phantom problem问题. 在这算法下 对于索引的扫描, 不仅是锁住扫描的索引. 而且还锁住这些索引覆盖的范围(GAP) 因此在这个范围内插入是不允许的. 这样就避免了另外的事务在这个范围内插入数据导致不可重复读问题.

丢失更新问题

丢失更新问题是数据级别解决不了. 发送情况是A事务select 数据A. B事务也select A 这是A事务更新数据A为C提交, 然后B事务更新数据A为D. 最后导致C数据丢失. 这个问题需要程序加锁 做全局排序.

死锁

innodb采用两种方式解决死锁问题. 1 被动方式: 使用超时锁. 2 主动的方式. wait-for graph(等待图)原理是采用两张链表 1 锁信息链. 2 事务等待链 通过上述链表可以构造出一张图. 如果途中出现回路. 就代表着死锁.

通过深度优先算法. 检测环的存在. 如果出现死锁. innodb选择undo量最小的事务进行回滚.

事务

redo日志

重做日志用来保证事务的持久性.

由两部分组成, 一部分是内存中的redo log buffer.其实是易失的. 一部分是磁盘文件系统中的redo log file. innodb是事务存储引擎. 通过force log at commit机制实现事务的持久性. 即当事务提交时.必须先将该事务的所有日志写入到重做日志文件中并做持久化.待事务的commit操作完成才算完成, 这里指的日志是重做日志. 在innodb引擎中分为两部分 1是redo 2 undo. redo保证事务的持久性. undo 用来帮助事务回滚和MVCC.

为了保证每次都能写入重做日志文件, 在每次重做日志缓冲写入重做日志文件后. innoDB引擎需要一次fsync操作. fsync的效率取决于磁盘的效率. 也决定了事务的效率. 也决定了数据库的效率.

binlog 和 重做日志的区别:

binlog存储的是二进制文件. 重做日志存储的是物理格式的文件.
实现的层面也不一样, binlog是mysql数据库上层实现的. 支持很多引擎使用. 重做日志是innodb引擎实现的.
写入磁盘的时间点也不一样, binlog是只有在事务提交后才写入. 重做日志是事务进行中不停地写入. 这表现为日志并不是随事务提交的顺序写入的.

log block

重做日志的缓存和文件都已512字节大小的块进行保存.和磁盘扇区的大小一致.因此重做日志的写入具有原子性. 不需要doublewrite技术.

重做日志文件中存储的就是log buffer中保存的log block. innodb存储引擎运行过程. log buffer根据一定的规则将内存中的log block刷新到磁盘, 这个规则具体是:

  1. 事务提交时
  2. 当log buffer中的可用空间小于一半时.
  3. log checkpoint时

innodb_flush_log_at_trx_commit用来控制重做日志刷新到磁盘的策略.
0 事务提交时不写入重做日志文件
1 表示事务提交时刷新buffer到文件 并他调用一次fsync.
2 表示事务提交时将日志写入重做日志文件,但仅写入文件系统缓存中. 不执行fsync操作.

LSN 日志序列号

单调递增的. 代表了 重做日志写入的总量 checkpoint的位置 页的版本号.
LSN不仅记录在重做日志中, 每页的头部都记录了该页LSN.表示该页最后刷新时LSN的位置.因为重做日志记录的是每个页的日志.因此页中LSN用来判断页是否需要进行恢复操作.

undo 日志

undo日志保证了事务的回滚和MVCC功能.

  • 事务回滚: undo日志存放在重做日志中, 但和redo日志不同, undo存放在数据库内部一个特殊的段中. 叫做undo段.undo段位于共享表空间中. undo是逻辑日志. 回滚操作也不是将数据库物理的恢复到执行语句或事务之前的样子. undo日志只是将数据库逻辑的恢复到原来的样子, 所有的修改被逻辑的取消了.例如用户insert了10W条记录的事务.这个事务会导致表空间增大. 执行回滚操作. 但是表空间的大小并不会因此缩小, 因为innoBD在执行回滚的时候,它实际上做的是与之前相反的工作. 对于每个insert. 引擎会完成一个delete. 对于每个delete, innodb会完成一个insert. 对于update. innodb会执行一个相反的update.

  • MVCC innodb中的MVCC的实现是通过undo日志完成的. 当用户读取记录时. 发现记录被其他事务占用. 当前事务可以通过undo日志读取之前版本的行记录.以此实现非锁定读

  • undo日志会产生redo日志. 因为undo日志也需要持久化的保护

当事务提交时 innodb引擎会做两件事情. 1将undo log放入列表. 供之后的purge操作 2. 判断undo是否可以重用. 若可以分配给下个事务使用.

事务提交之时. 引擎并不能马上删除undolog及undolog 所有页中的内容.这是因为可能其他事务需要undo日志来得到行记录之前的版本. 故事务提交时将undo log放入一个链表中.是否可以删除相关内容. 则有purge线程判定/.

undo日志类型
  • insert undo log. 因为insert语句只对自己事务可见, 其他事务不可见, 因此该事务在提交之后 undo log可以直接删除. 不需要等到purge.
  • update undo log. 记录的是对delete和update操作产生的undo log. 该日志可能会提供MVCC机制. 因此不能事务提交后删除. 提交时放入undo log链表. 等到purge线程进行最后的删除.
purge线程

为了节省空间 innoDB在设置undolog时. 一个页上可以保存多个事务的undo日志.因此顺序得不到保证. 因此innoDB还维护了一个history列表,它根据事务提交顺序,将undo log日志进行连接. 先提交的总在尾端. purge从list头开始清除undo, 在清除是会顺便把事务所在页中可以清除的事务一起清除掉.

事务控制语句
  • start transaction | begin 显式的开启事务
  • commit 提交事务
  • rollback 回滚
  • savepoint identifier, savepoint允许事务中创建一个保存点,一个事务存在多个保存点
  • release savepoint identifier, 删除一个事务中的保存点
  • rollback to identifier, 回滚到指定保存点
  • set transaction 设置事务隔离级别.
事务隔离级别
  1. read uncommited 会出现脏读. 就是读取了未提交的数据.
  2. read commited 能读取到别的事务已经提交的信息. 读取已提交
  3. repeatable read innodb默认的 通过next-key lock锁解决了 phantom problem.
  4. seriablizale 最严格的的事务级别.