无标签

发布日期: 2020-08-19

InnoDB 索引

数据存储

当 InnoDB 存储数据时，它可以使用不同的行格式进行存储；MySQL 5.7 版本支持以下格式的行存储方式：

Antelope 是 InnoDB 最开始支持的文件格式，它包含两种行格式 Compact 和 Redundant ，它最开始并没有名字； Antelope 的名字是在新的文件格式 Barracuda 出现后才起的， Barracuda 的出现引入了两种新的行格式 Compressed 和 Dynamic ；InnoDB 对于文件格式都会向前兼容，而官方文档中也对之后会出现的新文件格式预先定义好了名字：Cheetah、Dragon、Elk 等等。

两种行记录格式 Compact 和 Redundant 在磁盘上按照以下方式存储：

Compact 和 Redundant 格式最大的不同就是记录格式的第一个部分；在 Compact 中，行记录的第一部分倒序存放了一行数据中列的长度（Length），而 Redundant 中存的是每一列的偏移量（Offset），从总体上上看， Compact 行记录格式相比 Redundant 格式能够减少 20% 的存储空间。

行溢出数据

当 InnoDB 使用 Compact 或者 Redundant 格式存储极长的 VARCHAR 或者 BLOB 这类大对象时，我们并不会直接将所有的内容都存放在数据页节点中，而是将数据中的前 768 个字节存储在数据页中，后面会通过偏移量指向溢出页（off-page），最大768字节的作用是便于创建 前缀索引。溢出页（off-page）不存储在 B+tree 中，使用的是uncompress BLOB page，并且每个字段的溢出都是存储独享。

但是当我们使用新的行记录格式 Compressed 或者 Dynamic 时都只会在行记录中保存 20 个字节的指针，实际的数据都会存放在溢出页面中。

当然在实际存储中，可能会对不同长度的 TEXT 和 BLOB 列进行优化。

想要了解更多与 InnoDB 存储引擎中记录的数据格式的相关信息，可以阅读 InnoDB Record Structure

数据页结构

与现有的大多数存储引擎一样，InnoDB 使用页作为磁盘管理的最小单位；数据在 InnoDB 存储引擎中都是按行存储的，每个 16KB 大小的页中可以存放 2-200 行的记录。

页是 InnoDB 存储引擎管理数据的最小磁盘单位，而 B-Tree 节点就是实际存放表中数据的页面，我们在这里将要介绍页是如何组织和存储记录的；首先，一个 InnoDB 页有以下七个部分：

每一个页中包含了两对 header/trailer：内部的 Page Header/Page Directory 关心的是页的状态信息，而 Fil Header/Fil Trailer 关心的是记录页的头信息。

在页的头部和尾部之间就是用户记录和空闲空间了，每一个数据页中都包含 Infimum 和 Supremum 这两个虚拟的记录（可以理解为占位符）， Infimum 记录是比该页中任何主键值都要小的值， Supremum 是该页中的最大值：

User Records 就是整个页面中真正用于存放行记录的部分，而 Free Space 就是空余空间了，它是一个链表的数据结构，为了保证插入和删除的效率，整个页面并不会按照主键顺序对所有记录进行排序，它会自动从左侧向右寻找空白节点进行插入，行记录在物理存储上并不是按照顺序的，它们之间的顺序是由 next_record 这一指针控制的。

B+ 树在查找对应的记录时，并不会直接从树中找出对应的行记录，它只能获取记录所在的页，将整个页加载到内存中，再通过 Page Directory 中存储的稀疏索引和 n_owned、next_record 属性取出对应的记录，不过因为这一操作是在内存中进行的，所以通常会忽略这部分查找的耗时。这样就存在一个命中率的问题，如果一个page中能够相对的存放足够多的行，那么命中率就会相对高一些，性能就会有提升。

B+树底层的叶子节点为一双向链表，因此 每个页中至少应该有两行记录，这就决定了 InnoDB 在存储一行数据的时候不能够超过 8kb，但事实上应该更小，因为还有一些 InnoDB 内部数据结构要存储。

通常我们认为 blob 这类的大对象的存储会把数据存放在 off-page，其实不然，关键点还是要看一个 page 中到底能否存放两行数据，blob 可以完全存放在数据页中(单行长度没有超过 8kb)，而 varchar 类型的也有可能存放在溢出页中(单行长度超过 8kb，前 768byte 存放在数据页中)。

索引

索引是数据库中非常非常重要的概念，它是存储引擎能够快速定位记录的秘密武器，对于提升数据库的性能、减轻数据库服务器的负担有着非常重要的作用；索引优化是对查询性能优化的最有效手段，它能够轻松地将查询的性能提高几个数量级。

索引优缺点

优点

索引大大减小了服务器需要扫描的数据量
索引可以帮助服务器避免排序和临时表
索引可以将随机IO变成顺序IO
索引对于InnoDB（对索引支持行级锁）非常重要，因为它可以让查询锁更少的元组。在MySQL5.1和更新的版本中，InnoDB可以在服务器端过滤掉行后就释放锁，但在早期的MySQL版本中，InnoDB直到事务提交时才会解锁。对不需要的元组的加锁，会增加锁的开销，降低并发性。 InnoDB仅对需要访问的元组加锁，而索引能够减少InnoDB访问的元组数。但是只有在存储引擎层过滤掉那些不需要的数据才能达到这种目的。一旦索引不允许InnoDB那样做（即索引达不到过滤的目的），MySQL服务器只能对InnoDB返回的数据进行WHERE操作，此时，已经无法避免对那些元组加锁了。如果查询不能使用索引，MySQL会进行全表扫描，并锁住每一个元组，不管是否真正需要。
- 关于InnoDB、索引和锁：InnoDB在二级索引上使用共享锁（读锁），但访问主键索引需要排他锁（写锁）
  缺点
虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存索引文件。
建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重，但如果你在一个大表上创建了多种组合索引，索引文件的会膨胀很快。
如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
对于非常小的表，大部分情况下简单的全表扫描更高效；

如果MySQL有大数据量的表，就为最经常查询和最经常排序的数据列建立索引或者优化查询语句，但是，索引只是提高效率的一个因素。

MySQL里同一个数据表里的索引总数限制为16个

B+树

InnoDB 存储引擎在绝大多数情况下使用 B+ 树建立索引，这是关系型数据库中查找最为常用和有效的索引，但是 B+ 树索引并不能找到一个给定键对应的具体值，它只能找到数据行对应的页，然后正如上一节所提到的，数据库把整个页读入到内存中，并在内存中查找具体的数据行。

B+ 树是平衡树，它查找任意节点所耗费的时间都是完全相同的，比较的次数就是 B+ 树的高度；

B+ 树的叶子节点存放所有指向关键字的指针，节点内部关键字记录和节点之间都根据关键字的大小排列。当顺序递增插入的时候，只有最后一个节点会在满掉的时候引起索引分裂，此时无需移动记录，只需创建一个新的节点即可。而当非递增插入的时候，会使得旧的节点分裂，还可能伴随移动记录，以便使得新数据能够插入其中。一般建议使用一列顺序递增的 ID 来作为主键，但不必是数据库的 autoincrement 字段，只要满足顺序增加即可，如 twitter 的 snowflake 即为顺序递增的 ID 生成器。

B+ 树的高度

这里我们先假设 B+ 树高为2，即存在一个根节点和若干个叶子节点，那么这棵 B+ 树的存放总记录数为：根节点指针数*单个叶子节点记录行数。这里假设一行记录的大小为1k，那么一个页上的能放 16 行数据。假设主键ID为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共14字节，那么可以算出一棵高度为 2 的 B+ 树，能存放 16 \times 1024\div 14\times 16=1872016×1024÷14×16=18720 条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放： 1170\times 1170\times 16=21,902,4001170×1170×16=21,902,400 条这样的记录。所以在 InnoDB 中 B+ 树高度一般为 1~3 层，它就能满足千万级的数据存储。

聚集索引

InnoDB 存储引擎中的表都是使用索引组织的，也就是按照键的顺序存放；聚集索引就是按照表中主键的顺序构建一颗 B+ 树，并在叶节点中存放表中的行记录数据。

如果没有定义主键，则会使用非空的 UNIQUE键做主键 ; 如果没有非空的 UNIQUE键，则系统生成一个6字节的 rowid 做主键;

CREATE TABLE users(
    id INT NOT NULL,
    first_name VARCHAR(20) NOT NULL,
    last_name VARCHAR(20) NOT NULL,
    age INT NOT NULL,
    PRIMARY KEY(id),
    KEY(last_name, first_name, age)
    KEY(first_name)
);

如果使用上面的 SQL 在数据库中创建一张表，B+ 树就会使用 id 作为索引的键，并在叶子节点中存储一条记录中的所有信息。

图中对 B+ 树的描述与真实情况下 B+ 树中的数据结构有一些差别，不过这里想要表达的主要意思是：聚集索引叶节点中保存的是整条行记录，而不是其中的一部分。

聚集索引与表的物理存储方式有着非常密切的关系，所有正常的表应该 有且仅有一个 聚集索引（绝大多数情况下都是主键），表中的所有行记录数据都是按照 聚集索引 的顺序存放的。

当我们使用聚集索引对表中的数据进行检索时，可以直接获得聚集索引所对应的整条行记录数据所在的页，不需要进行第二次操作。

非聚集索引MyISAM(MySQL 5.5之前)

为何使用InnoDB,而非MyISAM

MySQL存储引擎MyISAM与InnoDB区别总结整理

辅助索引

数据库将 所有的非聚集索引都划分为辅助索引，但是这个概念对我们理解辅助索引并没有什么帮助；辅助索引也是通过 B+ 树实现的，但是它的叶节点并不包含行记录的全部数据，仅包含索引中的所有键和一个用于查找对应行记录的『书签』，在 InnoDB 中这个书签就是当前记录的主键。

辅助索引的存在并不会影响聚集索引，因为聚集索引构成的 B+ 树是数据实际存储的形式，而辅助索引只用于加速数据的查找，所以一张表上往往有多个辅助索引以此来提升数据库的性能。

一张表一定包含一个聚集索引构成的 B+ 树以及若干辅助索引的构成的 B+ 树。

如果在表 users 中存在一个辅助索引 (first_name, age)，那么它构成的 B+ 树大致就是上图这样，按照 (first_name, age) 的字母顺序对表中的数据进行排序，当查找到主键时，再通过聚集索引获取到整条行记录。

上图展示了一个使用辅助索引查找一条表记录的过程：通过辅助索引查找到对应的主键，最后在聚集索引中使用主键获取对应的行记录，这也是通常情况下行记录的查找方式。

覆盖索引

聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录，这种行为被称之为回表。回表会导致查询时多次读取磁盘，为减少IO MySQL 在辅助索引上进行优化，将辅助索引作为 覆盖索引（Covering index）。在查询的时候，如果 SELECT 子句中的字段为主键、辅助索引的键则不进行回表。

联合索引

联合索引在B+树上的存储结构及数据查找方式

索引失效

索引并不是时时都会生效的，比如以下几种情况，将导致索引失效：

如果条件中有 or，即使其中有条件带索引也不会使用。要想使用or，又想让索引生效，只能将 or 条件中的每个列都加上索引
对于多列索引，不是使用的最左匹配，则不会使用索引。
如果 mysql 估计使用全表扫描要比使用索引快，则不使用索引。例如，使用<>、not in 、not exist，对于这三种情况大多数情况下认为结果集很大，MySQL 就有可能不使用索引。

索引使用（执行顺序）

(7) - SELECT
(8) - DISTINCT
(1) - FROM
(3) -JOIN
(2) - ON
(4) - WHERE
(5) - GROUP BY
(6) - HAVING
(9) - ORDER BY
(10) - LIMIT

关于 SQL 语句的执行顺序，有三个值得我们注意的地方：

FROM 才是 SQL 语句执行的第一步，并非 SELECT。数据库在执行 SQL 语句的第一步是将数据从硬盘加载到数据缓冲区中，以便对这些数据进行操作。
SELECT 是在大部分语句执行了之后才执行的，严格的说是在 FROM 和 GROUP BY 之后执行的。理解这一点是非常重要的，这就是你不能在 WHERE 中使用在 SELECT 中设定别名的字段作为判断条件的原因。
无论在语法上还是在执行顺序上， UNION 总是排在在 ORDER BY 之前。很多人认为每个 UNION 段都能使用 ORDER BY 排序，但是根据 SQL 语言标准和各个数据库 SQL 的执行差异来看，这并不是真的。尽管某些数据库允许 SQL 语句对子查询（subqueries）或者派生表（derived tables）进行排序，但是这并不说明这个排序在 UNION 操作过后仍保持排序后的顺序。

虽然SQL的逻辑查询是根据上述进行查询，但是数据库也许并不会完全按照逻辑查询处理的方式来进行查询。 MySQL 数据库有两个组件 Parser（分析SQL语句）和 Optimizer（优化）。

从官方手册上看，可以理解为， MySQL 采用了基于开销的优化器，以确定处理查询的最解方式，也就是说执行查询之前，都会先选择一条自以为最优的方案，然后执行这个方案来获取结果。在很多情况下， MySQL 能够计算最佳的可能查询计划，但在某些情况下， MySQL 没有关于数据的足够信息，或者是提供太多的相关数据信息，估测就不那么友好了。

存在索引的情况下，优化器优先使用条件用到索引且最优的方案。当 SQL 条件有多个索引可以选择， MySQL 优化器将直接使用效率最高的索引执行。

索引优化

Explain 关键字

使用EXPLAIN关键字可以模拟优化器执行SQL语句，从而知道MySQL是如何处理你的SQL语句的。分析你的查询语句或是结构的性能瓶颈

（具体展开，见笔记）

具体优化方法

1.在执行常量等值查询时，改变索引列的顺序并不会更改explain的执行结果，因为mysql底层优化器会进行优化，但是推荐按照索引顺序列编写sql语句。

2.范围右边索引列失效，但是范围当前位置的索引是有效的。

3-具体见笔记

慢查询优化

慢查询优化方法

SQL慢查询优化

常见问题

1.数据库索引，如何设计加速数据读取？

2.MySQL和Redis面试题小结

InnoDB 并发控制

InnoDB 锁机制

InnoDB默认使用行锁，实现了两种标准的行锁——共享锁与排他锁；

行锁类型	锁功能	锁兼容性	加锁	释放锁
共享锁（读锁、S锁）	允许获取共享锁的亊务读数据	与共享锁兼容，与排它锁不兼容	只有 `SerializaWe` 隔离级别会默认为：读加共享锁；其他隔离级别下，可显示使用 `select...lock in share model` 为读加共享锁	在事务提交或回滚后会自动同时释放锁；除了使用 `start transaction` 的方式显式开启事务，InnoDB 也会自动为增删改査语句开启事务，并自动提交或回滚；(`autocommit=1`)
排它锁（写锁、X锁）	允许获取排它锁的事务更新或删除数据	与共享锁不兼容，与排它锁不兼容	在默认的 `Reapeatable Read` 隔离级别下，InnoDB 会自动为增删改操作的行加排它锁；也可显式使用 `select...for update` 为读加排它锁	…

除了显式加锁的情况，其他情况下的加锁与解锁都无需人工干预
InnoDB 所有的行锁算法都是基于索引实现的，锁定的也都是索引或索引区间

当前读 & 快照读

当前读：即加锁读，读取记录的最新版本，会加锁保证其他并发事务不能修改当前记录，直至获取锁的事务释放锁；使用当前读的操作主要包括：显式加锁的读操作与插入/更新/删除等写操作，如下所示：

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 ?;

注：当 Update SQL 被发给 MySQL 后， MySQL Server 会根据where条件，读取第一条满足条件的记录，然后 InnoDB 引擎会将第一条记录返回，并加锁，待 MySQL Server 收到这条加锁的记录之后，会再发起一个 Update 请求，更新这条记录。一条记录操作完成，再读取下一条记录，直至没有满足条件的记录为止。因此， Update 操作内部，就包含了当前读。同理， Delete 操作也一样。 Insert 操作会稍微有些不同，简单来说，就是 Insert 操作可能会触发 Unique Key 的冲突检查，也会进行一个当前读。

快照读：即不加锁读，读取记录的快照版本而非最新版本，通过MVCC实现；

InnoDB 默认的 RR 事务隔离级别下，不显式加lock in share mode与for update的 select 操作都属于快照读，保证事务执行过程中只有第一次读之前提交的修改和自己的修改可见，其他的均不可见；

共享锁与独占锁

意向锁

InnoDB 支持多粒度的锁，允许表级锁和行级锁共存。一个类似于 LOCK TABLES ... WRITE 的语句会获得这个表的 x 锁。为了实现多粒度锁，InnoDB 使用了意向锁（简称 I 锁）。I 锁是表明一个事务稍后要获得针对一行记录的某种锁（s or x）的对应表的表级锁，有两种：

意向排它锁（简称 IX 锁）表明一个事务意图在某个表中设置某些行的 x 锁
意向共享锁（简称 IS 锁）表明一个事务意图在某个表中设置某些行的 s 锁

SELECT ... LOCK IN SHARE MODE 设置一个 IS 锁, SELECT ... FOR UPDATE 设置一个 IX 锁。意向锁的原则如下：

一个事务必须先持有该表上的 IS 或者更强的锁才能持有该表中某行的 S 锁
一个事务必须先持有该表上的 IX 锁才能持有该表中某行的 X 锁

新请求的锁只有兼容已有锁才能被允许，否则必须等待不兼容的已有锁被释放。一个不兼容的锁请求不被允许是因为它会引起死锁，错误会发生。意向锁只会阻塞全表请求（比如 LOCK TABLES ... WRITE ）。意向锁的主要目的是展示某人正在锁定表中一行，或者将要锁定一行。

Record Lock

记录锁（Record Lock）是加到索引记录上的锁，假设我们存在下面的一张表 users：

    CREATE TABLE users(
        id INT NOT NULL AUTO_INCREMENT,
        last_name VARCHAR(255) NOT NULL,
        first_name VARCHAR(255),
        age INT,
        PRIMARY KEY(id),
        KEY(last_name),
        KEY(age)
    );

如果我们使用 id 或者 last_name 作为 SQL 中 WHERE 语句的过滤条件，那么 InnoDB 就可以通过索引建立的 B+ 树找到行记录并添加索引，但是如果使用 first_name 作为过滤条件时，由于 InnoDB 不知道待修改的记录具体存放的位置，也无法对将要修改哪条记录提前做出判断就会锁定整个表。

Gap Lock

记录锁是在存储引擎中最为常见的锁，除了记录锁之外，InnoDB 中还存在间隙锁（Gap Lock），间隙锁是对索引记录中的一段连续区域的锁；当使用类似 SELECT * FROM users WHERE id BETWEEN 10 AND 20 FOR UPDATE; 的 SQL 语句时，就会阻止其他事务向表中插入 id = 15 的记录，因为整个范围都被间隙锁锁定了。

间隙锁是存储引擎对于性能和并发做出的权衡，并且只用于某些事务隔离级别。

虽然间隙锁中也分为共享锁和互斥锁，不过它们之间并不是互斥的，也就是不同的事务可以同时持有一段相同范围的共享锁和互斥锁，它唯一阻止的就是其他事务向这个范围中添加新的记录。

间隙锁的缺点

间隙锁有一个比较致命的弱点，就是当锁定一个范围键值之后，即使某些不存在的键值也会被无辜的锁定，而造成在锁定的时候无法插入锁定键值范围内的任何数据。在某些场景下这可能会对性能造成很大的危害
当Query无法利用索引的时候， InnoDB会放弃使用行级别锁定而改用表级别的锁定，造成并发性能的降低；
当Quuery使用的索引并不包含所有过滤条件的时候，数据检索使用到的索引键所指向的数据可能有部分并不属于该Query的结果集的行列，但是也会被锁定，因为间隙锁锁定的是一个范围，而不是具体的索引键；
当Query在使用索引定位数据的时候，如果使用的索引键一样但访问的数据行不同的时候（索引只是过滤条件的一部分），一样会被锁定

Next-Key Lock

Next-Key 锁相比前两者就稍微有一些复杂，它是记录锁和记录前的间隙锁的结合，在 users 表中有以下记录：

    +------|-------------|--------------|-------+
    |   id | last_name   | first_name   |   age |
    |------|-------------|--------------|-------|
    |    4 | stark       | tony         |    21 |
    |    1 | tom         | hiddleston   |    30 |
    |    3 | morgan      | freeman      |    40 |
    |    5 | jeff        | dean         |    50 |
    |    2 | donald      | trump        |    80 |
    +------|-------------|--------------|-------+

如果使用 Next-Key 锁，那么 Next-Key 锁就可以在需要的时候锁定以下的范围：

    (-∞, 21]
    (21, 30]
    (30, 40]
    (40, 50]
    (50, 80]
    (80, ∞)

既然叫 Next-Key 锁，锁定的应该是当前值和后面的范围，但是实际上却不是，Next-Key 锁锁定的是当前值和前面的范围。

当我们更新一条记录，比如 SELECT * FROM users WHERE age = 30 FOR UPDATE;，InnoDB 不仅会在范围 (21, 30] 上加 Next-Key 锁，还会在这条该记录索引增长方向的范围 (30, 40] 加间隙锁，所以插入 (21, 40] 范围内的记录都会被锁定。

Next-Key 锁的作用其实是为了解决幻读的问题。

插入意向锁

插入意向锁是在插入一行记录操作之前设置的一种间隙锁，这个锁释放了一种插入方式的信号，亦即多个事务在相同的索引间隙插入时如果不是插入间隙中相同的位置就不需要互相等待。假设有索引值4、7，几个不同的事务准备插入5、6，每个锁都在获得插入行的独占锁之前用插入意向锁各自锁住了4、7之间的间隙，但是不阻塞对方因为插入行不冲突。

自增锁

自增锁是一个特殊的表级锁，事务插入自增列的时候需要获取，最简单情况下如果一个事务插入一个值到表中，任何其他事务都要等待，这样第一个事物才能获得连续的主键值。

锁选择

+——-+————-+
| id | name |
+——-+————-+
| 1 | title1 |
+——-+————-+
| 2 | title2 |
+——-+————-+
| 3 | title3 |
+——-+————-+
| 9 | title9 |
+——-+————-+
| 10 | title10 |
+——-+————-+

按照原理来说，id>5 and id<7这个查询条件，在表中找不到满足条件的项，因此会对第一个不满足条件的项(id = 9)上加GAP锁，防止后续其他事务插入满足条件的记录。

而 GAP 锁与GAP 锁是不冲突的，那么为什么两个同时执行id>5 and id<7查询的事务会冲突呢？

原因在于，MySQL Server并没有将id<7这个查询条件下降到InnoDB引擎层，因此InnoDB看到的查询，是id>5，正向扫描。读出的记录id=9，先加上next key锁(Lock X + GAP lock)，然后返回给 MySQL Server 进行判断。 MySQL Server 此时才会判断返回的记录是否满足id<7的查询条件。此处不满足，查询结束。

因此，id=9记录上，真正持有的锁是next key锁，而next key锁之间是相互冲突的，这也说明了为什么两个id>5 and id<7查询的事务会冲突的原因。

MVCC

InnoDB 引擎支持 MVCC(Multiversion Concurrency Control)：InnoDB 保存了行的历史版本，以支持事务的并发控制和回滚。这些历史信息保存在表空间的 回滚段（Rollback Segment） 里，回滚段中存储着 Undo Log。当事务需要进行回滚时，InnoDB 就会使用这些信息来进行 Undo 操作，同时这些信息也可用来实现 一致性读。

InnoDB 在存储的每行数据中都增加了三列隐藏属性：

DB_TRX_ID：最后一次插入或更新的事务ID
DB_ROLL_PTR：指向已写入回滚段的 Undo Log 记录。如果这行记录是更新的，那么就可以根据这个 Undo Log 记录重建之间的数据
DB_ROW_ID：自增序列，如果表未指定主键，则由该列作为主键

在回滚段的 Undo Log 被分为 Insert Undo Log 和 Update Undo Log。Insert Undo Log 只是在事务回滚的时候需要，在事务提交后就可丢弃。Update Undo Log 不仅仅在回滚的时候需要，还要提供一致性读，所以只有在所有需要该 Update Undo Log 构建历史版本数据的事务都提交后才能丢弃。MySQL 建议尽量频繁的提交事务，这样可以保证 InnoDB 快速的丢弃 Update Undo Log，防止其过大。

在 InnoDB 中，行数据的物理删除不是立刻执行，InnoDB 会在行删除的 Undo Log 被丢弃时才会进行物理删除。这个过程被称之为 清理（Purge），其执行过程十分迅速。

MVCC 二级索引

InnoDB 在更新时对二级索引和聚集索引的处理方式不一样。在聚集索引上的更新是原地更新（in-place），其中的隐藏属性 DB_ROLL_PTR 指向的 Undo Log 可以重建历史数据。但是二级索引没有隐藏属性，所以不能原地更新。

当二级索引的数据被更新时，旧的二级索引记录标记为 标记删除（delete-marked），然后插入一条新的索引记录，最终标记删除的索引记录会被清除。当二级索引记录被标记为 delete-marked 或者有更新的事务更新时，InnoDB 会查找聚集索引。在聚集索引中检查行的 DB_TRX_ID，如果事务修改了记录，则从 Undo Log 中构建行数据的正确版本。如果二级索引记录被标记为 delete-marked 或者二级索引有更新的事务更新，覆盖索引技术不会被使用（获取行任意数据均需要回表）。

MVCC vs 乐观锁

MVCC 并不是一个与乐观和悲观并发控制对立的东西，它能够与两者很好的结合以增加事务的并发量，在目前最流行的 SQL 数据库 MySQL 和 PostgreSQL 中都对 MVCC 进行了实现；但是由于它们分别实现了悲观锁和乐观锁，所以 MVCC 实现的方式也不同。

MVCC 可以保证不阻塞地读到一致的数据。但是，MVCC 并没有对实现细节做约束，为此不同的数据库的语义有所不同，比如：

postgres 对写操作也是乐观并发控制；在表中保存同一行数据记录的多个不同版本，每次写操作，都是创建，而回避更新；在事务提交时，按版本号检查当前事务提交的数据是否存在写冲突，则抛异常告知用户，回滚事务；
innodb 则只对读无锁，写操作仍是上锁的悲观并发控制，这也意味着，innodb 中只能见到因死锁和不变性约束而回滚，而见不到因为写冲突而回滚，不像 postgres 那样对数据修改在表中创建新纪录，而是每行数据只在表中保留一份，在更新数据时上行锁，同时将旧版数据写入 undo log。表和 undo log 中行数据都记录着事务ID，在检索时，只读取来自当前已提交的事务的行数据。

可见 MVCC 中的写操作仍可以按悲观并发控制实现，而 CAS 的写操作只能是乐观并发控制。还有一个不同在于，MVCC 在语境中倾向于 “对多行数据打快照造平行宇宙”，然而 CAS 一般只是保护单行数据而已。比如 mongodb 有 CAS 的支持，但不能说这是 MVCC。

InnoDB 事务隔离

几种隔离级别

事务的隔离性是数据库处理数据的几大基础之一，而隔离级别其实就是提供给用户用于在性能和可靠性做出选择和权衡的配置项。

ISO 和 ANIS SQL 标准制定了四种事务隔离级别，而 InnoDB 遵循了 SQL:1992 标准中的四种隔离级别：READ UNCOMMITED、READ COMMITED、REPEATABLE READ 和 SERIALIZABLE；每个事务的隔离级别其实都比上一级多解决了一个问题：

RAED UNCOMMITED：使用查询语句不会加锁，可能会读到未提交的行（Dirty Read）；
可以读取未提交记录。此隔离级别，不会使用，忽略。
READ COMMITED：只对记录加记录锁，而不会在记录之间加间隙锁，所以允许新的记录插入到被锁定记录的附近，所以再多次使用查询语句时，可能得到不同的结果（Non-Repeatable Read）；
快照读忽略，本文不考虑。针对当前读，RC隔离级别保证对读取到的记录加锁 (记录锁)，存在幻读现象。
REPEATABLE READ：快照读忽略，本文不考虑。针对当前读，RR隔离级别保证对读取到的记录加锁 (记录锁)，同时保证对读取的范围加锁，新的满足查询条件的记录不能够插入 (间隙锁)，不存在幻读现象。
SERIALIZABLE：从MVCC并发控制退化为基于锁的并发控制。不区别快照读与当前读，所有的读操作均为当前读，读加读锁 (S锁)，写加写锁 (X锁)。
Serializable隔离级别下，读写冲突，因此并发度急剧下降，在MySQL/InnoDB下不建议使用。

MySQL 中默认的事务隔离级别就是 REPEATABLE READ，但是它通过 Next-Key 锁也能够在某种程度上解决幻读的问题。

接下来，我们将数据库中创建如下的表并通过个例子来展示在不同的事务隔离级别之下，会发生什么样的问题：

    CREATE TABLE test(
        id INT NOT NULL,
        UNIQUE(id)
    );

脏读

在一个事务中，读取了其他事务未提交的数据。

当事务的隔离级别为 READ UNCOMMITED 时，我们在 SESSION 2 中插入的未提交数据在 SESSION 1 中是可以访问的。

不可重复读

在一个事务中，同一行记录被访问了两次却得到了不同的结果。

当事务的隔离级别为 READ COMMITED 时，虽然解决了脏读的问题，但是如果在 SESSION 1 先查询了一行数据，在这之后 SESSION 2 中修改了同一行数据并且提交了修改，在这时，如果 SESSION 1 中再次使用相同的查询语句，就会发现两次查询的结果不一样。

不可重复读的原因就是，在 READ COMMITED 的隔离级别下，存储引擎不会在查询记录时添加行锁，锁定 id = 3 这条记录。

幻读

在一个事务中，同一个范围内的记录被读取时，其他事务向这个范围添加了新的记录。

重新开启了两个会话 SESSION 1 和 SESSION 2，在 SESSION 1 中我们查询全表的信息，没有得到任何记录；在 SESSION 2 中向表中插入一条数据并提交；由于 REPEATABLE READ 的原因，再次查询全表的数据时，我们获得到的仍然是空集，但是在向表中插入同样的数据却出现了错误。

这种现象在数据库中就被称作幻读，虽然我们使用查询语句得到了一个空的集合，但是插入数据时却得到了错误，好像之前的查询是幻觉一样。

在标准的事务隔离级别中，幻读是由更高的隔离级别 SERIALIZABLE 解决的，但是它也可以通过 MySQL 提供的 Next-Key 锁解决：

REPEATABLE READ 和 READ UNCOMMITED 其实是矛盾的，如果保证了前者就看不到已经提交的事务，如果保证了后者，就会导致两次查询的结果不同，MySQL 为我们提供了一种折中的方式，能够在 REPEATABLE READ 模式下加锁访问已经提交的数据，其本身并不能解决幻读的问题，而是通过文章前面提到的 Next-Key 锁来解决。

分库分表

垂直拆分

垂直分表 也就是 大表拆小表，基于列字段进行的。一般是表中的字段较多，将不常用的，数据较大，长度较长（比如text类型字段）的拆分到 扩展表。一般是针对那种几百列的大表，也避免查询时，数据量太大造成的 off-page 问题。

垂直分库 针对的是一个系统中的不同业务进行拆分。将多个业务系统的数据放在单个数据库中（服务化拆分），这会让数据库的单库处理能力成为瓶颈。将单个数据库，按业务进行拆分，同一业务领域的数据表放到同一数据库中。并且多个数据库分布在多个机器上，防止由于单机的磁盘、内存、IO等资源造成 MySQL 性能下降。

数据库的连接资源比较宝贵且单机处理能力也有限，在高并发场景下，垂直分库一定程度上能够突破 IO、连接数等单机硬件资源的瓶颈。

水平拆分

目前绝大多数应用采取的两种分库分表规则

离散映射：如 mod 或 dayofweek ，这种类型的映射能够很好的解决热点问题，但带来了数据迁移和历史数据问题。
连续映射；如按 id 或 gmt_create_time 的连续范围做映射。这种类型的映射可以避免数据迁移，但又带来热点问题。

随着数据量的增大，每个表或库的数据量都是各自增长。当一个表或库的数据量增长到了一个极限，要加库或加表的时候，介于这种分库分表算法的离散性，必需要做 数据迁移 才能完成。

考虑到数据增长的特点，如果我们以代表时间增长的字段，按递增的范围分库，则可以避免数据迁移。这样的方式下，在数据量再增加达到前几个库/表的上限时，则继续水平增加库表，原先的数据就不需要迁移了。但是这样的方式会带来一个 热点问题：当前的数据量达到某个库表的范围时，所有的插入操作，都集中在这个库/表了。

结合离散分库/分表和连续分库/分表的优点，可使要热点和新数据均匀分配在每个库，同时又保证易于水平扩展。分库分表的主要经历以下三个阶段：

阶段一

一个数据库，两个表，rule0 = id % 2

分库规则dbRule: “DB0″
分表规则tbRule: “t” + (id % 2)

阶段二

当单库的数据量接近 1千万，单表的数据量接近 500 万时，进行扩容（数据量只是举例，具体扩容量要根据数据库和实际压力状况决定）：增加一个数据库 DB1，将 DB0.t0 整表迁移到新库 DB1.t1。每个库各增加1个表，未来10M-20M的数据mod2分别写入这2个表：t0_1，t1_1：

分库规则dbRule:

“DB” + (id % 2)

分表规则tbRule:

    if(id < 1千万){
        return "t"+ (id % 2);   //1千万之前的数据，仍然放在t0和t1表。t1表从DB0搬迁到DB1库
    }else if(id < 2千万){
        return "t"+ (id % 2) +"_1"; //1千万之后的数据，各放到两个库的两个表中: t0_1,t1_1
    }else{
        throw new IllegalArgumentException("id outof range[20000000]:" + id);
    }

这样 10M 以后的新生数据会均匀分布在 DB0 和 DB1; 插入更新和查询热点仍然能够在每个库中均匀分布。每个库中同时有老数据和不断增长的新数据。每表的数据仍然控制在 500万 以下。

阶段三

当两个库的容量接近上限继续水平扩展时，进行如下操作：

新增加两个库：DB2和DB3，以id % 4分库。余数0、1、2、3分别对应DB的下标. t0和t1不变，
将DB0.t0_1整表迁移到DB2; 将DB1.t1_1整表迁移到DB3

20M-40M的数据 mod4 分为 4 个表：t0_2，t1_2，t2_2，t3_2，分别放到4个库中：

新的分库分表规则如下：

分库规则dbRule:

  if(id < 2千万){
      //2千万之前的数据，4个表分别放到4个库
      if(id < 1千万){
          return "db"+  (id % 2);     //原t0表仍在db0, t1表仍在db1
      }else{
          return "db"+ ((id % 2) +2); //原t0_1表从db0搬迁到db2; t1_1表从db1搬迁到db3
      }
  }else if(id < 4千万){
      return "db"+ (id % 4);          //超过2千万的数据，平均分到4个库
  }else{
      throw new IllegalArgumentException("id out of range. id:"+id);
  }

分表规则tbRule:

  if(id < 2千万){        //2千万之前的数据，表规则和原先完全一样，参见阶段二
      if(id < 1千万){
          return "t"+ (id % 2);       //1千万之前的数据，仍然放在t0和t1表
      }else{
          return "t"+ (id % 2) +"_1"; //1千万之后的数据，仍然放在t0_1和t1_1表
      }
  }else if(id < 4千万){
      return "t"+ (id % 4)+"_2";      //超过2千万的数据分为4个表t0_2，t1_2，t2_2，t3_2
  }else{
      throw new IllegalArgumentException("id out of range. id:"+id);
  }

随着时间的推移，当第一阶段的t0/t1，第二阶段的t0_1/t1_1逐渐成为历史数据，不再使用时，可以直接truncate掉整个表。省去了历史数据迁移的麻烦。

分库分表规则的设计和配置，长远说来必须满足以下要求

可以动态推送修改
规则可以分层级叠加，旧规则可以在新规则下继续使用，新规则是旧规则在更宽尺度上的拓展，以此支持新旧规则的兼容，避免数据迁移
用 mod 方式时，最好选 2 的指数级倍分库分表，这样方便以后切割。

数据迁移

在上述的水平扩容方案中，如何进行数据迁移，是在扩容中需要考虑的问题。一般情况下，数据迁移分为：停机迁移、双写迁移。

停机迁移 是最简单、最安全、最快速的迁移方案，但一般线上业务系统很少允许停机迁移。在停机迁移中，首先停掉数据库 A 的写入请求，复制 A 数据到 B，待复制完成后，切换线上数据源。

双写迁移 方案就是同时写两个库，一个是老库，一个是新库。也就是在线上系统里面，除了对所有老库的增删改地方，同时对新库同样执行增删改。主要经历以下三个阶段：

导入历史数据，数据库双写（事务成功以老数据源为准），查询走老数据源，通过定时任务补全新老差异数据
新老数据无差异，依旧双写（事务成功以新数据源为准），查询走新数据源
稳定运行无误后，下线老数据源

Join

在拆分之前，系统中很多列表和详情页所需的数据是可以通过 Join 来完成的。而拆分后，数据库可能是分布式在不同实例和不同的主机上，Join 将变得非常麻烦。首先要考虑下垂直分库的设计问题，如果可以调整，那就优先调整。如果无法调整的情况，可以考虑以下解决方案：

全局表：就是有可能系统中所有模块都可能会依赖到的一些表。为了避免跨库 join 查询，我们可以将这类表在其他每个数据库中均保存一份。同时，这类数据通常也很少发生修改（甚至几乎不会），所以也不用太担心 一致性 问题；
字段冗余：字段冗余能带来便利，是一种 空间换时间 的体现。但其适用场景也比较有限，比较适合依赖字段较少的情况。最复杂的还是数据一致性问题，这点很难保证；
系统层组装：在系统层面，通过调用不同模块的组件或者服务，获取到数据并进行字段拼装；

主从复制

MySQL 主从复制涉及到三个线程，一个运行在主节点（log dump thread），其余两个(I/O thread, SQL thread)运行在从节点。

Log Dump Thread：当从节点连接主节点时，主节点会创建一个 log dump 线程，用于发送 bin-log 的内容。在读取 bin-log 中的操作时，此线程会对主节点上的 bin-log 加锁，当读取完成，甚至在发动给从节点之前，锁会被释放。
I/O Thread：当从节点上执行 start slave 命令之后，从节点会创建一个 I/O 线程用来连接主节点，请求主库中更新的 bin-log。I/O线程接收到主节点 binlog dump 进程发来的更新之后，保存在本地 relay-log 中。
SQL Thread：负责读取 relay log 中的内容，解析成具体的操作并执行，最终保证主从数据的一致性。

一个 slave 节点可同时从多个 master 进行数据复制，在这种情况下，不同 master 的 bin-log 存储在不同的 relay log中。

同步模式

异步模式（mysql async-mode）：MySQL增删改操作会全部记录在 binary log 中，当 slave 节点连接 master 时，会主动从 master 处获取最新的 bin log 文件。

半同步模式(mysql semi-sync)：这种模式下主节点只需要接收到其中一台从节点的返回信息，就会 commit ；否则需要等待直到超时时间然后切换成异步模式再提交；这样做的目的可以使主从数据库的数据延迟缩小，可以提高数据安全性，确保了事务提交后，binlog 至少传输到了一个从节点上，不能保证从节点将此事务更新到 db 中。性能上会有一定的降低，响应时间会变长。

全同步模式 是指主节点和从节点全部执行了commit并确认才会向客户端返回成功。

主从复制的延迟问题

进行主从同步的过程中，如果使用异步或半异步模式，均会有主从节点数据不一致的窗口时间。同时，从节点上的 SQL Thread 只能串行执行 relay-log 中的记录，当某条 DDL/DML 耗时较长时，会加剧这个窗口时间；再者在某些场景下会使用 slave 节点进行数据读取，这也可能导致数据加锁等待。基于以上原因在处理主从复制延迟问题上有以下几种方向：

优化主从节点之间的网络延迟
降低 master 负载，以减少 TPS
降低 slave 负载，slave 只做备份使用，不提供服务
调整 slave 参数：关闭 slave bin-log 等
多线程的主从复制：不同 schema 下的表并发提交时的数据不会相互影响，即 slave 节点可以用对 relay log 中不同的 schema 各分配一个SQL Thread，来重放 relay log 中主库已经提交的事务

全局ID

数据库自增 id
设置数据库 sequence 或者表自增字段步长
UUID
Snowflake 算法

Snowflake

twitter 开源的分布式 id 生成算法，采用 Scala 语言实现，是把一个 64 位的 long 型的 id ，1 个 bit 是不用的，用其中的 41 bit 作为毫秒数，用 10 bit 作为工作机器 id ，12 bit 作为序列号。

|–1位符号位–|--41位时间戳–|--10位机器ID–|--12位序列号–|

1 bit：不用，为啥呢？因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
41 bit：表示的是时间戳，单位是毫秒。41 bit 可以表示的数字多达 2^41 - 1，也就是可以标识 2^41 - 1 个毫秒值，换算成年就是表示69年的时间。
10 bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10台机器上哪，也就是1024台机器。但是 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2^5个机房（32个机房），每个机房里可以代表 2^5 个机器（32台机器）。
12 bit：这个是用来记录同一个毫秒内产生的不同 id，12 bit 可以代表的最大正整数是 2^12 - 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。

Snowflake 的问题

Snowflake 这样依赖时间的 ID 生成算法注定存在一个问题：时间的准确度问题。这一算法有一个默认前提：分布式环境下时间获取总是准确的，即时间总是递增的。而现实环境中，这样的条件很难满足。总会因为硬件、软件、人的原因造成时间变化。如果你的硬件时间本身就比正常时间快，而你接入了一个 NTP 服务，每当进行 NTP 时间校准时，你的机器时间总会向后回拨一段时间，这时悲剧就来了：有极大可能性生成重复ID。

针对上面提到的两个问题，可如下改进：

时间戳由毫秒变为秒
使用环形列表对时间戳对应的序列进行缓存
使用 CAS 操作避免大粒度悲观锁

为了缓解时钟回拨问题，对之前的序列进行缓存，而原生算法很显然是不利于缓存的，最坏的情况下每秒需要缓存 1000 个值，这显然对内存很不友好。于是我将时间戳改为秒为单位，同时可以把省出来的位交给序列。此时缓存一个小时的数据（即可以容忍一个小时的时钟回拨）也就只需要缓存 3600 个序列，完全可以接受。改进后的 Snowflake 生成的ID是这样组成的：

|–1位符号位–|--32位时间戳–|--10位机器ID–|--21位序列号–|

环形列表：即整个列表的容量是一定的，当列表满了以后再加入的元素会按照入列的先后顺序覆盖之前的元素。

参考

【】

yulin

https://hyl2048.github.io/63394.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 yulin !

无标签

Linux应用

Linux 概览Linux 常用命令操作文件以及目录命令ls: pwd: clear: cd: mkdir: cp: mv: rm: touch:创建一个空文件 tar:解压缩文件常用参数：

2020-08-19 Basic

操作系统

计算机系统概述基本构成处理器内存输入/输出模块系统总线微处理器的演化指令的执行中断分类：程序中断（算术溢出、除数为零、执行非法的机器指令、访问用户不允许的存储位置）；时钟中断；I/O中断；硬件失效中断；中断和指令周期中断

2020-08-19 Basic

数据库

InnoDB 索引

数据存储

行溢出数据

数据页结构

索引

索引优缺点

优点

缺点

B+树

B+ 树的高度

聚集索引

非聚集索引MyISAM(MySQL 5.5之前)

辅助索引

覆盖索引

联合索引

索引失效

索引使用（执行顺序）

索引优化

Explain 关键字

具体优化方法

慢查询优化

常见问题

InnoDB 并发控制

InnoDB 锁机制

当前读 & 快照读

共享锁与独占锁

意向锁

Record Lock

Gap Lock

间隙锁的缺点

Next-Key Lock

插入意向锁

自增锁

锁选择

MVCC

MVCC 二级索引

MVCC vs 乐观锁

InnoDB 事务隔离

几种隔离级别

脏读

不可重复读

幻读

分库分表

垂直拆分

水平拆分

阶段一

阶段二

阶段三

数据迁移

Join

主从复制

同步模式

主从复制的延迟问题

全局ID

Snowflake

Snowflake 的问题

参考

你的赏识是我前进的动力