MySQL

参考资料：

万字总结：学习MySQL优化原理，这一篇就够了！

架构

逻辑架构

MySQL逻辑架构整体分为三层，最上层为客户端层，并非MySQL所独有，诸如：连接处理、授权认证、安全等功能均在这一层处理。

MySQL大多数核心服务均在中间这一层，包括查询解析、分析、优化、缓存、内置函数(比如：时间、数学、加密等函数)。所有的跨存储引擎的功能也在这一层实现：存储过程、触发器、视图等。

最下层为存储引擎，其负责MySQL中的数据存储和提取。和Linux下的文件系统类似，每种存储引擎都有其优势和劣势。中间的服务层通过API与存储引擎通信，这些API接口屏蔽了不同存储引擎间的差异。

查询过程：

客户端/服务端通信协议

MySQL客户端/服务端通信协议是“半双工”的：在任一时刻，要么是服务器向客户端发送数据，要么是客户端向服务器发送数据，这两个动作不能同时发生。一旦一端开始发送消息，另一端要接收完整个消息才能响应它，所以我们无法也无须将一个消息切成小块独立发送，也没有办法进行流量控制。

客户端用一个单独的数据包将查询请求发送给服务器，所以当查询语句很长的时候，需要设置max_allowed_packet参数。但是需要注意的是，如果查询实在是太大，服务端会拒绝接收更多数据并抛出异常。

与之相反的是，服务器响应给用户的数据通常会很多，由多个数据包组成。但是当服务器响应客户端请求时，客户端必须完整的接收整个返回结果，而不能简单的只取前面几条结果，然后让服务器停止发送。因而在实际开发中，尽量保持查询简单且只返回必需的数据，减小通信间数据包的大小和数量是一个非常好的习惯，这也是查询中尽量避免使用SELECT *以及加上LIMIT限制的原因之一。

查询优化器

MySQL的查询优化器是一个非常复杂的部件，它使用了非常多的优化策略来生成一个最优的执行计划：

• 重新定义表的关联顺序（多张表关联查询时，并不一定按照SQL中指定的顺序进行，但有一些技巧可以指定关联顺序）
• 优化MIN()和MAX()函数（找某列的最小值，如果该列有索引，只需要查找B+Tree索引最左端，反之则可以找到最大值）
• 提前终止查询（比如：使用Limit时，查找到满足数量的结果集后会立即终止查询）
• 优化排序（在老版本MySQL会使用两次传输排序，即先读取行指针和需要排序的字段在内存中对其排序，然后再根据排序结果去读取数据行，而新版本采用的是单次传输排序，也就是一次读取所有的数据行，然后根据给定的列排序。对于I/O密集型应用，效率会高很多）

索引

b+ tree

介绍

浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

性质

间距越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。

意义

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

简单点说说内存读取，内存是由一系列的存储单元组成的，每个存储单元存储固定大小的数据，且有一个唯一地址。当需要读内存时，将地址信号放到地址总线上传给内存，内存解析信号并定位到存储单元，然后把该存储单元上的数据放到数据总线上，回传。

写内存时，系统将要写入的数据和单元地址分别放到数据总线和地址总线上，内存读取两个总线的内容，做相应的写操作。

内存存取效率，跟次数有关，先读取A数据还是后读取A数据不会影响存取效率。而磁盘存取就不一样了，磁盘I/O涉及机械操作。磁盘是由大小相同且同轴的圆形盘片组成，磁盘可以转动(各个磁盘须同时转动)。磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不动，磁盘转动，但磁臂可以前后动，用于读取不同磁道上的数据。磁道就是以盘片为中心划分出来的一系列同心环(如图标红那圈)。磁道又划分为一个个小段，叫扇区，是磁盘的最小存储单元。

磁盘读取时，系统将数据逻辑地址传给磁盘，磁盘的控制电路会解析出物理地址，即哪个磁道哪个扇区。于是磁头需要前后移动到对应的磁道，消耗的时间叫寻道时间，然后磁盘旋转将对应的扇区转到磁头下，消耗的时间叫旋转时间。所以，适当的操作顺序和数据存放可以减少寻道时间和旋转时间。为了尽量减少I/O操作，磁盘读取每次都会预读，大小通常为页的整数倍。即使只需要读取一个字节，磁盘也会读取一页的数据(通常为4K)放入内存，内存与磁盘以页为单位交换数据。因为局部性原理认为，通常一个数据被用到，其附近的数据也会立马被用到。

B-Tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率也就上去了。

B+Tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，I/O操作更少了。所以B+Tree拥有更好的性能。

索引实现

MyISAM：MyISAM引擎使用B+Tree作为索引结构。MyISAM索引文件和数据文件是分离的，叶节点的data域存放的是数据记录的地址。MyISAM主键索引和辅助索引结构是一样的。

InnoDB：InnoDB的数据文件本身就是索引文件。在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

• 为什么不建议使用过长的字段作为主键：
  因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
• 用非单调的字段作为主键在InnoDB中不是个好主意：
  因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
• 为何自增主键好：
  InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。
  
  这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
  如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，如下：
  
  此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

最左前缀原则

https://www.jianshu.com/p/b7911e0394b0

https://www.cnblogs.com/wmbg/p/6800354.html

联合索引会按照b+tree排序，例如(a,b,c)，索引的结果是order by a,b,c ,所以当查询(a),(a,b),(a,b,c)时都可以使用索引。而查询(b,c),(c)

1. 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

索引规则

• 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
• =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式
• 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录
• 索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
• 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可，当然要考虑原有数据和线上使用情况

隔离级别

1. 原子性
   事务必须是原子工作单元；对于其数据修改，要么全都执行，要么全都不执行。
2. 一致性
   事务的一致性指的是在一个事务执行之前和执行之后数据库都必须处于一致性状态。事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。
3. 隔离性（关于事务的隔离性数据库提供了多种隔离级别）
   一个事务的执行不能干扰其它事务。即一个事务内部的操作及使用的数据对其它并发事务是隔离的，并发执行的各个事务之间不能互相干扰。
4. 持久性
   事务完成之后，它对于数据库中的数据改变是永久性的。该修改即使出现系统故障也将一
   直保持。
   在介绍数据库提供的各种隔离级别之前，我们先看看如果不考虑事务的隔离性，会发生的几种问题：

• 脏读
  脏读是指在一个事务处理过程里读取了另一个未提交的事务中的数据。
• 不可重复读
• 幻读
  幻读和不可重复读都是读取了另一条已经提交的事务,不可重复读重点在于update和delete，而幻读的重点在于insert。

在可重复读中，该sql第一次读取到数据后，就将这些数据加锁，其它事务无法修改这些数据，就可以实现可重复 读了。但这种方法却无法锁住insert的数据，所以当事务A先前读取了数据，或者修改了全部数据，事务B还是可以insert数据提交，这时事务A就会 发现莫名其妙多了一条之前没有的数据，这就是幻读，不能通过行锁来避免。需要Serializable隔离级别 ，读用读锁，写用写锁，读锁和写锁互斥，这么做可以有效的避免幻读、不可重复读、脏读等问题，但会极大的降低数据库的并发能力。

现在来看看MySQL数据库为我们提供的四种隔离级别：

1. Serializable (串行化)：可避免脏读、不可重复读、幻读的发生。在可串行化级别上，MySQL执行S2PL并发控制协议, 一阶段申请，一阶段释放。读写都要加锁。
2. Repeatable read (可重复读)：可避免脏读、不可重复读的发生。读不加锁，只有写才加锁，读写互不阻塞，并发度相对于可串行化级别要高，但会有Write Skew异常。事务在开始时创建一个ReadView，当读一条记录时，会遍历版本链表，通过当前事务的ReadView判断可见性，找到第一个对当前事务可见的版本，读这个版本。对于写操作，包括Locking Read(SELECT … FOR UPDATE), UPDATE, DELETE，需要加写锁。根据谓词条件上索引使用情形，锁定有不同的方式：
   1. 有索引：对于索引上有唯一约束且为等值条件的情形，不用GAP LOCK，只锁定索引记录。对于其它情形，使用GAP LOCK，相当于谓词锁。
   2. 没有索引：由于MySQL没有实现通用的谓词锁，这时就相当于锁全表。
3. Read committed (读已提交)：可避免脏读的发生。MySQL的读已提交实际是语句级别快照。与可重复读级别主要有两点不同：
   1. 获得ReadView的时机。每个语句开始执行时，获得ReadView，可见性判断是基于语句级别的ReadView。读的策略与可重复读类似。
   2. 写锁的使用方式。这里不需要GAP LOCK，只使用记录锁。并且事务只持有被UPDATE/DELETE记录的写锁（可重复读需要保留全部写锁直到事务结束，而读已提交只保留真正更改的）。
4. Read uncommitted (读未提交)：最低级别，任何情况都无法保证。读最新的数据，不管这条记录是不是已提交。不会遍历版本链，少了查找可见的版本的步骤。这样可能会导致脏读。

在MySQL数据库中默认的隔离级别为Repeatable read (可重复读)。

innodb可重复读级别可以避免读数据时产生的幻读问题（mvcc缘故，读不到版本号大于当前版本号的行），但不能避免写数据时产生的幻读问题。

因为读是快照度，写是当前读。要解决幻读需要用间隙锁或者串行化。

锁

共享锁，排它锁

间隙锁

调优

explain

返回结果

• id : 表示SQL执行的顺序的标识,SQL从大到小的执行
• select_type：表示查询中每个select子句的类型
• table：显示这一行的数据是关于哪张表的，有时不是真实的表名字
• type：表示MySQL在表中找到所需行的方式，又称“访问类型”。常用的类型有： ALL, index, range, ref, eq_ref, const, system, NULL（从左到右，性能从差到好）
• possible_keys：指出MySQL能使用哪个索引在表中找到记录，查询涉及到的字段上若存在索引，则该索引将被列出，但不一定被查询使用
• Key：key列显示MySQL实际决定使用的键（索引），如果没有选择索引，键是NULL。
• key_len：表示索引中使用的字节数，可通过该列计算查询中使用的索引的长度（key_len显示的值为索引字段的最大可能长度，并非实际使用长度，即key_len是根据表定义计算而得，不是通过表内检索出的）
• ref：表示上述表的连接匹配条件，即哪些列或常量被用于查找索引列上的值
• rows： 表示MySQL根据表统计信息及索引选用情况，估算的找到所需的记录所需要读取的行数，理论上行数越少，查询性能越好
• Extra：该列包含MySQL解决查询的详细信息

EXPLAIN的特性

• EXPLAIN不会告诉你关于触发器、存储过程的信息或用户自定义函数对查询的影响情况
• EXPLAIN不考虑各种Cache
• EXPLAIN不能显示MySQL在执行查询时所作的优化工作
• 部分统计信息是估算的，并非精确值
• EXPALIN只能解释SELECT操作，其他操作要重写为SELECT后查看执行计划。

log

Bin Log:是mysql服务层产生的日志，常用来进行数据恢复、数据库复制，常见的mysql主从架构，就是采用slave同步master的binlog实现的

Redo Log:记录了数据操作在物理层面的修改，mysql中使用了大量缓存，修改操作时会直接修改内存，而不是立刻修改磁盘，事务进行中时会不断的产生redo log，在事务提交时进行一次flush操作，保存到磁盘中。当数据库或主机失效重启时，会根据redo log进行数据的恢复，如果redo log中有事务提交，则进行事务提交修改数据。

Undo Log: 除了记录redo log外，当进行数据修改时还会记录undo log，undo log用于数据的撤回操作，它记录了修改的反向操作，比如，插入对应删除，修改对应修改为原来的数据，通过undo log可以实现事务回滚，并且可以根据undo log回溯到某个特定的版本的数据，实现MVCC

MVCC

MySQL InnoDB实现了多版本并发控制（MVCC），在多版本存储上，MySQL采用从新到旧（Newest To Oldest）的版本链。B+Tree叶结点上，始终存储的是最新的数据（可能是还未提交的数据）。而旧版本数据，通过UNDO记录（做DELTA）存储在回滚段（Rollback Segment）里。每一条记录都会维护一个ROW HEADER元信息，存储有创建这条记录的事务ID，一个指向UNDO记录的指针。通过最新记录和UNDO信息，可以还原出旧版本的记录。

MVCC是通过在每行记录后面保存三个隐藏的列来实现的。一个保存了行的创建版本号，一个保存行的过期版本号，一个指向最近的undo log。每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来和查询到的每行记录的版本号进行比较。

下面看一下在REPEATABLE READ隔离级别下，MVCC具体是如何操作的。

• SELECT
  InnoDB会根据以下两个条件检查每行记录：
  InnoDB只查找版本早于当前事务版本的数据行（也就是，行的系统版本号小于或等于事务的系统版本号），这样可以确保事务读取的行，要么是在事务开始前已经存在的，要么是事务自身插入或者修改过的。
  行的删除版本要么未定义，要么大于当前事务版本号。这可以确保事务读取到的行，在事务开始之前未被删除。
  只有符合上述两个条件的记录，才能返回作为查询结果
• INSERT
  InnoDB为新插入的每一行保存当前系统版本号作为行版本号。
• DELETE
  InnoDB为删除的每一行保存当前系统版本号作为行删除标识。
• UPDATE
  InnoDB为插入一行新记录，保存当前系统版本号作为行版本号，同时保存当前系统版本号到原来的行作为行删除标识。
  保存这两个额外系统版本号，使大多数读操作都可以不用加锁。这样设计使得读数据操作很简单，性能很好，并且也能保证只会读取到符合标准的行，不足之处是每行记录都需要额外的存储空间，需要做更多的行检查工作，以及一些额外的维护工作

Innodb vs Myisam

1. InnoDB 支持事务，MyISAM 不支持事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；
2. InnoDB 支持外键，而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败；
3. InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。
4. InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；
5. InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

如何选择：

1. 是否要支持事务，如果要请选择 InnoDB，如果不需要可以考虑 MyISAM；
2. 如果表中绝大多数都只是读查询，可以考虑 MyISAM，如果既有读写也挺频繁，请使用InnoDB。
3. 系统奔溃后，MyISAM恢复起来更困难，能否接受，不能接受就选 InnoDB；
4. MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的。如果你不知道用什么存储引擎，那就用InnoDB，至少不会差。

微服务一致性

CAP

CAP 是指在一个分布式系统下，包含三个要素：Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），并且三者不可得兼。

• 一致性（Consistency），是指对于每一次读操作，要么都能够读到最新写入的数据，要么错误，所有数据变动都是同步的。
• 可用性（Availability），是指对于每一次请求，都能够得到一个及时的、非错的响应，但是不保证请求的结果是基于最新写入的数据。即在可以接受的时间范围内正确地响应用户请求。
• 分区容错性（Partition tolerance），是指由于节点之间的网络问题，即使一些消息丢包或者延迟，整个系统仍能够提供满足一致性和可用性的服务。

事务模式 -两阶段提交(2PC)

事物模式的代表就是两阶段提交，它的含义就是每个服务有自己的子事务，服务之间其实也是通过分布式事务来保障事务的一致性。

所以它在第一阶段的时候，这个协调器会发一个propose的请求给三个服务，如果每个服务都可以接受接下来的事务请求，它就会回复yes或者是no。回复之后就会到第二个阶段，如果前面三个服务回复的都是一个yes，那协调器就会发送commit这个请求，去执行这三个服务的事务操作，否则就会发送一个abort请求。执行完成之后，三个服务会回来一个ack，表示这个事务已经结束，或者是已经取消。

优点：有事务的原子性，因为在每次做事务操作的时候，都会锁定资源，所以所有进入协调器的请求，其实都是一个线性的请求，它不能去同步所有的事务。

缺点：它是一个阻塞式的模式，它需要锁定资源，它的复杂度也会相对比较高，比较难扩展。

预约模式 -TCC(Try-Confirm/Cancel)

预约模式比较典型的叫Try-Confirm/Cancel，缩写就是TCC。它也是一个两阶段的模式。第一个阶段它会发一个try的请求给三个服务，如果三个服务可以执行，它们就会回复yes，不能回复no，这和两阶段提交是一致的。不一样的地方是它不会锁定资源。所以在A处理完它的子事务，B可能还没有处理完它的子事务的时候，A可以接受其他的请求。在第二阶段，像两阶段提交一样，协调器会根据第一阶段ABC的返回结果去发送Confirm或者Cancel，这样的请求，最后ABC会返回ack。

优点：

在try阶段如果失败，服务会回复至原状，什么意思呢？比如说要发一个会议邀请，如果用TCC的模式，第一阶段会先发一个询问的请求给所有的与会人员，询问是否可以在这一个时间点来参会，如果所有的参会人员都回答yes，第二步就会发送一个确认请求，实际的一个会议邀请，如果有任何一个人员不能参加，就会发送一个Cancel，取消这个会议。

缺点：

• 它不是原子操作，它可以并行处理好多的分布式的事务，然后它在Confirm这个阶段，只能重试，如果有一个服务失败的话，只能重试，直到成功，或者是采取回退措施，需要人工去做干预。
• 它需要一个额外的try流程，服务需要提供额外的try的结构，也就需要提供额外的reserved的状态。

可靠消息最终一致性

可靠事件模式属于事件驱动架构，微服务完成操作后向消息代理发布事件，关联的微服务从消息代理订阅到该 事件从而完成相应的业务操作，关键在于可靠事件投递和避免事件重复消费。

可靠事件投递有两个特性：

• 每个服务原子性的完成业务操作和发布事件；
• 消息代理确保事件投递至少一次 (at least once)。避免重复消费要求消费事件的服务实现幂等性。

有两种实现方式：

本地事件表

本地事件表方法将事件和业务数据保存在同一个数据库中，使用一个额外的“事件恢复”服务来恢 复事件，由本地事务保证更新业务和发布事件的原子性。考虑到事件恢复可能会有一定的延时，服务在完成本 地事务后可立即向消息代理发布一个事件。

使用本地事件表将事件和业务数据保存在同一个数据库中，会在每个服务存储一份数据，在一定程度上会造成代码的重复冗余。同时，这种模式下的业务系统和事件系统耦合比较紧密，额外增加的事件数据库操作也会给数据库带来额外的压力，可能成为瓶颈。

外部事件表

针对本地事件表出现的问题，提出外部事件表方法，将事件持久化到外部的事件系统，事件系统 需提供实时事件服务以接收微服务发布的事件，同时事件系统还需要提供事件恢复服务来确认和恢复事件。

%!(EXTRA markdown.ResourceType=, string=, string=)

Saga的补偿机制

Saga支持向前和向后恢复：

向后恢复：如果任意一个子事务失败，则补偿所有已完成的事务

向前恢复：如果子事务失败，则重试失败的事务

BBR

今天花了一个下午学习bbr，真的是太奇妙了这个东西。计算机网络的东西我都忘得差不多了，一边学习一边回顾，也不敢写什么研究心得，主要是看了知乎上李博杰关于bbr的回答，然后看了原文（以下简称，对于一些不太清楚的概念做一些笔记，以便时候回顾。

一些概念

• 加性增，乘性减：简单讲就是说，tcp loss-based拥塞控制传输时，拥塞窗口会已加的形式增大，而一旦遇到包丢失的情况，就会以除二的方式减小窗口。详情可以查看tcp慢启动和指数退避相关内容。

这张图我看了半个小时（学渣！），图的整体意思是说：单位时间内，随着发送数据的增加，到达链路运输能力（实际带宽）前发送速率（数据成功到达receiver的）增加，数据延迟不变；一旦达到链路的运输能力，发送速率不会变化，而数据发送耗时会增加。BBR将数据发送量限制到带宽，从而达到发送速率最大同时耗时最短，而传统的基于丢包的拥塞控制则控制的是数据量为buffer的极限。一点上图中的概念解析：

• inflight:拥塞窗口（？不确定），可以理解为发送的数据量
• loss-based congestion control:基于包丢失的拥塞控制。传统TCP拥塞控制方法，由于链路中存在buffer，buffer容量会比链路大，当buffer缓冲区到达limit时，会产生丢包行为，因此会把‘丢包’这个行为视为拥塞控制信号。因此，在高丢包率的长肥管道（带宽大，延迟高）中，这种机制表现非常差，会不停地进行指数退避。
• RTT：round-trip time，指一个包从sender方到达receiver方耗时
• RTprop:物理延迟。当链路中没有任何排队和其他耗时时，RTprop=RTT
• deliveryRate：发送速率。虽然有rate但并不是说的比率，Delivery Rate = CWND/SRTT，其中CWND = 可发送包的个数 * 包的大小；SRTT 是平滑RTT，动态测量的结果。所以deliveryRate 其实可以解释为每单位时间可以发送的数据量。中有个公式，大意为BtlBw=max(deliveryRatet)，也就是评估瓶颈带宽的方式。
• BtlBw:瓶颈带宽，也就是链路的最大传输能力。
• BDP带宽时延积：（Bandwidth-Delay Product ，BDP）即链路上的最大比特数，也称以比特为单位的链路长度。计算方法：Bandwidth-Delay Product = delay_bandwidth=RTprop_BtlBw
  BBR的方法可以理解为将链路上的比特数控制为BDP的值。
  论文：
  一开始讲了RTprop和BtlBw的回归方程计算。表明BBR需要实时统计deliveryRate和RTT的值来获得RTprop和BtlBw的值。
  然后说了RTprop和BtlBw不能同时测得。

锁

自旋锁 ，自旋锁的其他种类，阻塞锁，可重入锁 ，读写锁 ，互斥锁 ，悲观锁 ，乐观锁 ，公平锁 ，偏向锁， 对象锁，线程锁，锁粗化， 锁消除，轻量级锁，重量级锁， 信号量，独享锁，共享锁，分段锁

不可不说的Java“锁”事

乐观锁 VS 悲观锁

对于同一个数据的并发操作，悲观锁认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。Java中，synchronized关键字和Lock的实现类都是悲观锁。

而乐观锁认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试）。

1. 乐观锁在Java中是通过使用无锁编程来实现，最常采用的是CAS算法，Java原子类中的递增操作就通过CAS自旋实现的。例如AtomicInteger.incrementAndGet()
2. 版本号机制。一般是在数据表中加上一个数据版本号version字段，表示数据被修改的次数，当数据被修改时，version值会加一。当线程A要更新数据值时，在读取数据的同时也会读取version值，在提交更新时，若刚才读取到的version值为当前数据库中的version值相等时才更新，否则重试更新操作，直到更新成功。

场景：

• 悲观锁适合写操作多的场景，先加锁可以保证写操作时数据正确。
• 乐观锁适合读操作多的场景，不加锁的特点能够使其读操作的性能大幅提升。

CAS虽然很高效，但是它也存在三大问题：

1. ABA问题。CAS需要在操作值的时候检查内存值是否发生变化，没有发生变化才会更新内存值。但是如果内存值原来是A，后来变成了B，然后又变成了A，那么CAS进行检查时会发现值没有发生变化，但是实际上是有变化的。ABA问题的解决思路就是在变量前面添加版本号，每次变量更新的时候都把版本号加一，这样变化过程就从“A－B－A”变成了“1A－2B－3A”。
   • JDK从1.5开始提供了AtomicStampedReference类来解决ABA问题，具体操作封装在compareAndSet()中。compareAndSet()首先检查当前引用和当前标志与预期引用和预期标志是否相等，如果都相等，则以原子方式将引用值和标志的值设置为给定的更新值。
2. 循环时间长开销大。CAS操作如果长时间不成功，会导致其一直自旋，给CPU带来非常大的开销。
3. 只能保证一个共享变量的原子操作。对一个共享变量执行操作时，CAS能够保证原子操作，但是对多个共享变量操作时，CAS是无法保证操作的原子性的。
   • Java从1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行CAS操作。

自旋锁 VS 适应性自旋锁

阻塞或唤醒一个Java线程需要操作系统切换CPU状态来完成，这种状态转换需要耗费处理器时间。如果同步代码块中的内容过于简单，状态转换消耗的时间有可能比用户代码执行的时间还要长。

在许多场景中，同步资源的锁定时间很短，为了这一小段时间去切换线程，线程挂起和恢复现场的花费可能会让系统得不偿失。如果物理机器有多个处理器，能够让两个或以上的线程同时并行执行，我们就可以让后面那个请求锁的线程不放弃CPU的执行时间，看看持有锁的线程是否很快就会释放锁。

而为了让当前线程“稍等一下”，我们需让当前线程进行自旋，如果在自旋完成后前面锁定同步资源的线程已经释放了锁，那么当前线程就可以不必阻塞而是直接获取同步资源，从而避免切换线程的开销。这就是自旋锁。

自旋锁本身是有缺点的，它不能代替阻塞。自旋等待虽然避免了线程切换的开销，但它要占用处理器时间。如果锁被占用的时间很短，自旋等待的效果就会非常好。反之，如果锁被占用的时间很长，那么自旋的线程只会白浪费处理器资源。所以，自旋等待的时间必须要有一定的限度，如果自旋超过了限定次数（默认是10次，可以使用-XX:PreBlockSpin来更改）没有成功获得锁，就应当挂起线程。

自旋锁的实现原理同样也是CAS，AtomicInteger中调用unsafe进行自增操作的源码中的do-while循环就是一个自旋操作，如果修改数值失败则通过循环来执行自旋，直至修改成功。

自旋锁在JDK1.4.2中引入，使用-XX:+UseSpinning来开启。JDK 6中变为默认开启，并且引入了自适应的自旋锁（适应性自旋锁）。

自适应意味着自旋的时间（次数）不再固定，而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定。如果在同一个锁对象上，自旋等待刚刚成功获得过锁，并且持有锁的线程正在运行中，那么虚拟机就会认为这次自旋也是很有可能再次成功，进而它将允许自旋等待持续相对更长的时间。如果对于某个锁，自旋很少成功获得过，那在以后尝试获取这个锁时将可能省略掉自旋过程，直接阻塞线程，避免浪费处理器资源。

例：

• TicketLock，基于先进先出(FIFO) 队列的自旋锁，保证首先注册的线程有更高级别优先性获取锁。有两个值，一个当前处理队列号，一个等待处理队列号。TicketLock 虽然解决了公平性的问题，但是多处理器系统上，每个进程/线程占用的处理器都在读写同一个变量queueNum ，每次读写操作都必须在多个处理器缓存之间进行缓存同步，这会导致繁重的系统总线和内存的流量，大大降低系统整体的性能。CLHLock和MCSLock是更好的解决方式
• CLHLock，基于隐式链表的自旋锁，线程将会获取上一个线程注册的CLHNode对象，只有当CLHNode.isLocked==false时，自己才获得了锁
• MCSLock，基于显式链表的自旋锁

无锁 VS 偏向锁 VS 轻量级锁 VS 重量级锁

偏向锁通过对比Mark Word解决加锁问题，避免执行CAS操作。而轻量级锁是通过用CAS操作和自旋来解决加锁问题，避免线程阻塞和唤醒而影响性能。重量级锁是将除了拥有锁的线程以外的线程都阻塞。随着锁的竞争，锁可以从偏向锁升级到轻量级锁，再升级的重量级锁（但是锁的升级是单向的，也就是说只能从低到高升级，不会出现锁的降级）

Java并发——关键字synchronized解析

Java锁—偏向锁、轻量级锁、自旋锁、重量级锁

synchronized & Java对象头

synchronized是悲观锁，在操作同步资源之前需要给同步资源先加锁，这把锁就是存在Java对象头里的，而Java对象头又是什么呢？

我们以Hotspot虚拟机为例，Hotspot的对象头主要包括两部分数据：Mark Word（标记字段）、Klass Pointer（类型指针）。

Mark Word：默认存储对象的HashCode，分代年龄和锁标志位信息。这些信息都是与对象自身定义无关的数据，所以Mark Word被设计成一个非固定的数据结构以便在极小的空间内存存储尽量多的数据。它会根据对象的状态复用自己的存储空间，也就是说在运行期间Mark Word里存储的数据会随着锁标志位的变化而变化。

下面给出四种锁状态对应的的Mark Word内容

Klass Point：对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。

Monitor

Monitor可以理解为一个同步工具或一种同步机制，通常被描述为一个对象。每一个Java对象就有一把看不见的锁，称为内部锁或者Monitor锁。

Monitor是线程私有的数据结构，每一个线程都有一个可用monitor record列表，同时还有一个全局的可用列表。每一个被锁住的对象都会和一个monitor关联，同时monitor中有一个Owner字段存放拥有该锁的线程的唯一标识，表示该锁被这个线程占用。

结构如下：

Owner：初始时为NULL表示当前没有任何线程拥有该monitor record，当线程成功拥有该锁后保存线程唯一标识，当锁被释放时又设置为NULL

EntryQ：关联一个系统互斥锁（semaphore），阻塞所有试图锁住monitor record失败的线程

RcThis：表示blocked或waiting在该monitor record上的所有线程的个数

Nest：用来实现重入锁的计数

HashCode：保存从对象头拷贝过来的HashCode值（可能还包含GC age）

Candidate：用来避免不必要的阻塞或等待线程唤醒，因为每一次只有一个线程能够成功拥有锁，如果每次前一个释放锁的线程唤醒所有正在阻塞或等待的线程，会引起不必要的上下文切换（从阻塞到就绪然后因为竞争锁失败又被阻塞）从而导致性能严重下降。Candidate只有两种可能的值0表示没有需要唤醒的线程1表示要唤醒一个继任线程来竞争锁

这四种锁是指锁的状态，专门针对synchronized的,synchronized通过Monitor来实现线程同步，Monitor是依赖于底层的操作系统的Mutex Lock（互斥锁）来实现的线程同步。

依赖于操作系统Mutex Lock所实现的锁我们称之为“重量级锁”，JDK 6中为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”。

所以目前锁一共有4种状态，级别从低到高依次是：无锁、偏向锁、轻量级锁和重量级锁。锁状态只能升级不能降级。

无锁

无锁没有对资源进行锁定，所有的线程都能访问并修改同一个资源，但同时只有一个线程能修改成功。

无锁的特点就是修改操作在循环内进行，线程会不断的尝试修改共享资源。如果没有冲突就修改成功并退出，否则就会继续循环尝试。如果有多个线程修改同一个值，必定会有一个线程能修改成功，而其他修改失败的线程会不断重试直到修改成功。上面我们介绍的CAS原理及应用即是无锁的实现。无锁无法全面代替有锁，但无锁在某些场合下的性能是非常高的。

偏向锁

偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁，降低获取锁的代价。

在大多数情况下，锁总是由同一线程多次获得，不存在多线程竞争，所以出现了偏向锁。其目标就是在只有一个线程执行同步代码块时能够提高性能。

当一个线程访问同步代码块并获取锁时，会在Mark Word里存储锁偏向的线程ID。在线程进入和退出同步块时不再通过CAS操作来加锁和解锁，而是检测Mark Word里是否存储着指向当前线程的偏向锁。引入偏向锁是为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行路径，因为轻量级锁的获取及释放依赖多次CAS原子指令，而偏向锁只需要在置换ThreadID的时候依赖一次CAS原子指令即可。

偏向锁只有遇到其他线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁，线程不会主动释放偏向锁。偏向锁的撤销，需要等待全局安全点（在这个时间点上没有字节码正在执行），它会首先暂停拥有偏向锁的线程，判断锁对象是否处于被锁定状态。撤销偏向锁后恢复到无锁（标志位为“01”）或轻量级锁（标志位为“00”）的状态。

偏向锁在JDK 6及以后的JVM里是默认启用的。可以通过JVM参数关闭偏向锁：-XX:-UseBiasedLocking=false，关闭之后程序默认会进入轻量级锁状态。

轻量级锁

是指当锁是偏向锁的时候，被另外的线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，从而提高性能。

在代码进入同步块的时候，如果同步对象锁状态为无锁状态（锁标志位为“01”状态，是否为偏向锁为“0”），虚拟机首先将在当前线程的栈帧中建立一个名为锁记录（Lock Record）的空间，用于存储锁对象目前的Mark Word的拷贝，然后拷贝对象头中的Mark Word复制到锁记录中。

拷贝成功后，虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针，并将Lock Record里的owner指针指向对象的Mark Word。

如果这个更新动作成功了，那么这个线程就拥有了该对象的锁，并且对象Mark Word的锁标志位设置为“00”，表示此对象处于轻量级锁定状态。

如果轻量级锁的更新操作失败了，虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧，如果是就说明当前线程已经拥有了这个对象的锁，那就可以直接进入同步块继续执行，否则说明多个线程竞争锁。

若当前只有一个等待线程，则该线程通过自旋进行等待。但是当自旋超过一定的次数，或者一个线程在持有锁，一个在自旋，又有第三个来访时，轻量级锁升级为重量级锁。

重量级锁

轻量级锁自旋

升级为重量级锁时，锁标志的状态值变为“10”，此时Mark Word中存储的是指向重量级锁的指针，此时等待锁的线程都会进入阻塞状态。

锁的转换

公平锁 VS 非公平锁

公平锁是指多个线程按照申请锁的顺序来获取锁，线程直接进入队列中排队，队列中的第一个线程才能获得锁。公平锁的优点是等待锁的线程不会饿死。缺点是整体吞吐效率相对非公平锁要低，等待队列中除第一个线程以外的所有线程都会阻塞，CPU唤醒阻塞线程的开销比非公平锁大。

非公平锁是多个线程加锁时直接尝试获取锁，获取不到才会到等待队列的队尾等待。但如果此时锁刚好可用，那么这个线程可以无需阻塞直接获取到锁，所以非公平锁有可能出现后申请锁的线程先获取锁的场景。非公平锁的优点是可以减少唤起线程的开销，整体的吞吐效率高，因为线程有几率不阻塞直接获得锁，CPU不必唤醒所有线程。缺点是处于等待队列中的线程可能会饿死，或者等很久才会获得锁。

可重入锁 VS 非可重入锁

可重入锁又名递归锁，是指在同一个线程在外层方法获取锁的时候，再进入该线程的内层方法会自动获取锁（前提锁对象得是同一个对象或者class），不会因为之前已经获取过还没释放而阻塞。Java中ReentrantLock和synchronized都是可重入锁，可重入锁的一个优点是可一定程度避免死锁。

独享锁 VS 共享锁

独享锁也叫排他锁，是指该锁一次只能被一个线程所持有。如果线程T对数据A加上排它锁后，则其他线程不能再对A加任何类型的锁。获得排它锁的线程即能读数据又能修改数据。JDK中的synchronized和JUC中Lock的实现类就是互斥锁。

共享锁是指该锁可被多个线程所持有。如果线程T对数据A加上共享锁后，则其他线程只能对A再加共享锁，不能加排它锁。获得共享锁的线程只能读数据，不能修改数据。

独享锁与共享锁也是通过AQS来实现的，通过实现不同的方法，来实现独享或者共享。

锁粗化/锁消除

锁消除：

锁消除是指虚拟机即时编译器在运行时，对一些代码上要求同步，但是被检测到不可能存在共享数据竞争的锁进行消除。锁消除的主要判定依据来源于逃逸分析的数据支持，如果判断在一段代码中，堆上的所有数据都不会逃逸出去从而被其他线程访问到，那就可以把它们当做栈上数据对待，认为它们是线程私有的，同步加锁自然就无须进行。

锁粗化：

如果一系列的连续操作都对同一个对象反复加锁和解锁，甚至加锁操作是出现在循环体中的，那即使没有线程竞争，频繁地进行互斥同步操作也会导致不必要的性能损耗。如果虚拟机探测到有这样一串零碎的操作都对同一个对象加锁，将会把加锁同步的范围扩展（粗化）到整个操作序列的外部

1
2
3
4
5
6
7
8
9
10
11

package com.paddx.test.string;

public class StringBufferTest {
    StringBuffer stringBuffer = new StringBuffer();

    public void append(){
        stringBuffer.append("a");
        stringBuffer.append("b");
        stringBuffer.append("c");
    }
}

这里每次调用stringBuffer.append方法都需要加锁和解锁，如果虚拟机检测到有一系列连串的对同一个对象加锁和解锁操作，就会将其合并成一次范围更大的加锁和解锁操作，即在第一次append方法时进行加锁，最后一次append方法结束后进行解锁。

Yarn

背景

hadoop1.0中架构：

问题：

• 由于大量的数据处理Job提交给Job Tracker，且Job Tracker需要协调的Data Node可能有数千台，Job Tracker极易成为整个系统的性能、可用的瓶颈。
• 无法有效地调配资源，导致资源分配不均。如以下例子，假设有3台Data Node（DN），每个DN的内存为4GB。用户提交了6个Job，每个Job需要1GB内存进行处理，且数据均在DN2上。由于DN2只有4GB内存，所以Job1-4在DN2上运行，Job5和6则在排队等待。但是，此时DN1和3均在闲置的状态下，而未能有效的被利用。

模块

ResourceManager

负责对各个NodeManager 上的资源进行统一管理和调度。包含两个组件：

• Scheduler：调度器根据容量、队列等限制条件（如每个队列分配一定的资源，最多执行一定数量的作业等），将系统中的资源分配给各个正在运行的应用程序
• Applications Manager：应用程序管理器负责管理整个系统中所有应用程序，包括应用程序提交、与调度器协商资源以启动ApplicationMaster、监控ApplicationMaster运行状态并在失败时重新启动它等

NodeManager

NM 是每个节点上的资源和任务管理器。

• 定时地向RM 汇报本节点上的资源使用情况和各个Container 的运行状态
• 接收并处理来自AM 的Container启动/ 停止等各种请求

ApplicationMaster

用户提交的每个应用程序均包含一个AM，主要功能包括：

• 与RM 调度器协商以获取资源（用 Container 表示）
• 将得到的任务进一步分配给内部的任务
• 与 NM 通信以启动 / 停止任务
• 监控所有任务运行状态，并在任务运行失败时重新为任务申请资源以重启任务

Container

Container 是YARN 中的资源抽象， 它封装了某个节点上的多维度资源， 如内存、CPU、磁盘、网络等，当AM 向RM 申请资源时，RM 为AM 返回的资源便是用Container表示的

工作流程

1. 用户向YARN 中提交应用程序， 其中包括ApplicationMaster 程序、启动ApplicationMaster 的命令、用户程序等。
2. ResourceManager 为该应用程序分配第一个Container，并与对应的Node-Manager 通信，要求它在这个Container中启动应用程序的ApplicationMaster。
3. ApplicationMaster 首先向ResourceManager 注册，这样用户可以直接通过ResourceManage 查看应用程序的运行状态，然后它将为各个任务申请资源，并监控它的运行状态，直到运行结束，即重复步骤4~7。
4. ApplicationMaster 采用轮询的方式通过RPC 协议向ResourceManager 申请和领取资源。
5. 一旦ApplicationMaster 申请到资源后，便与对应的NodeManager 通信，要求它启动任务。
6. NodeManager 为任务设置好运行环境（包括环境变量、JAR 包、二进制程序等）后，将任务启动命令写到一个脚本中，并通过运行该脚本启动任务。
7. 各个任务通过某个RPC 协议向ApplicationMaster 汇报自己的状态和进度，以让ApplicationMaster 随时掌握各个任务的运行状态，从而可以在任务失败时重新启动任务。在应用程序运行过程中，用户可随时通过RPC向ApplicationMaster 查询应用程序的当前运行状态。
8. 应用程序运行完成后，ApplicationMaster 向ResourceManager 注销并关闭自己。

资源调度算法

FIFO

FIFO 调度算法用于最早的 Hadoop 系统中，Hadoop 面向的是单用户提交的大规模数据处理作业。在 FIFO 调度算法中只有一个用户，所有作业按照优先级提交至具有不同优先级的队列中，然后由调度器（Scheduler）先按照作业提交的时间顺序选择待执行的作业。FIFO 的队列设置了 5 个优先等级，分别为：Very Low、Low、Normal、High 及 Very High。每个等级对应一个队列，按照队列的优先级从高到低选取队列，在同级队列中，按照提交作业的时间先后顺序提取并执行。其调度大体流程如图所示。

Capacity 调度算法

• 队列中单个任务使用的资源不会超过队列的容量。
• 如果队列满，且集群有空闲的资源，调度器可以把资源分配给此队列（可配置），弹性队列。
• 正常情况下，容量调度器不会抢占容器，因此如果一个队列随着使用，资源不够时，只能等待其他队列释放资源。
• 容量调度器也可以执行work-preserving preemption，RM会请求应用返回容器。

Capacity 调度算法是由 Yahoo！开发的多用户调度策略，它以队列为单位划分资源，每个队列可设定一定比例的资源最低保证和使用上限，同时每个用户也可设定一定的资源使用上限以防止资源滥用。而当一个队列的资源有剩余时，可暂时将剩余资源共享给其他队列。Capacity Scheduler 支持多个队列，每个队列可分配一定的资源量，队列中资源的调度策略可以为 FIFO 或 DRF (Dominant Resource Fairness)，多用户下，为防止同一个用户提交的作业独占队列的所有资源，Capacity Scheduler 对每个用户可提交的作业可分配的资源量进行了限制。

应用程序提交后，ResourceManager 会向 CapacityScheduler 发送一个事件，CapacityScheduler 收到后，将为应用程序创建一个对象跟踪和维护其运行时的信息，同时，将它提交到对应的叶子队列中，队列会对应用程序进行合法性检查。通过检查，应用程序才算提交成功。提交成功后，它的ApplicationMaster会为它申请资源，CapacityScheduler收到资源申请后，暂时将这些请求存放到一个数据结构中，以等待为其分配合适的资源。

NodeManager 发送的心跳信息有两类需要 CapacityScheduler 处理：一类是最新启动的 Container；另一类是运行完成的 Container。CapacityScheduler 将回收它使用的资源进行再分配。CapacityScheduler 采用三级资源分配策略(即将双层调度机制中的第一层分为选择队列与选择应用程序两级)，当一个节点上有空闲资源时，它会依次选择队列、应用程序和 Container (请求)使用该资源，接下来介绍三级资源分配策略。

第一级：选择队列。CapacityScheduler 采用基于优先级的深度优先遍历算法选择队列：从根队列开始，按照资源使用率由小到大遍历子队列。如果子队列是叶子队列，则按照第二、三级的方法在队列中选择一个 Container，否则以该队列为根队列，重复以上过程，直到找到合适的 Container 并退出。

第二级：选择应用程序。选中一个叶子队列后，CapacityScheduler 按照ApplicationID 对叶子队列中的应用程序进行排序，依次遍历排序后的应用程序，找到合适的 Container。

第三级：选择 Container。选中一个应用程序后，先满足优先级高的Container。同一优先级，先满足本地化的 Container，依次选择节点本地化、机架本地化和非本地化的 Container。

Fair 调度算法

• 每个队列有权重元素，用于fair share的计算。
• 默认队列和动态创建的队列，权重为1（默认队列的可配置）。
• 调度器会使用最小资源数量来进行资源分配进行优先排序。如果两个队列的资源都低于fair share额度，那么远低于最小资源数量的队列，会被有限分配资源。

Fair Scheduler 是 Facebook 开发的多用户调度器，同 Capacity Scheduler 相似，都以队列为单位划分资源，且每个队列可设定一定比例的资源最低保证和使用上限。Facebook 设计 Fair Scheduler 算法的初衷是让 Hadoop 平台可以更高效的处理不同类型的作业，最大化的保证了系统中各作业能够分配到的系统资源 。如果当前集群中只有一个作业，则该作业会独占整个集群中全部系统资源。当有新的作业被提交至系统时，一些任务会在完成后将资源分配给新提交的作业，Fair Scheduler 会尽量保证各作业间可以获得基本相同的系统资源，从而保证短作业具有较短的响应时间。

与CapacityScheduler不同的是，FairScheduler 提供了更多样化的调度策略，调度策略在队列间和队列内部可单独设置。当前有三种策略可选，分别是先来先服务(FIFO)、公平调度(Fair)和主资源公平调度(Dominant ResourceFairness，DRF)。

1. 先来先服务：按优先级高低调度，优先级相同，则按提交时间先后顺序调度；提交时间相同，则按名称大小调度。
2. 公平调度：按内存资源使用比率大小调度。
3. 主资源公平调度：按主资源公平调度算法进行调度，所需份额最大的资源称为主资源，把最大最小公平算法应用于主资源上，将多维资源调度问题转化为单资源调度问题。

DRF算法伪代码：

1
2
3
4
5
6
7
8
9
10
11
12

R = <r1, ··· , rm> //m种资源对应容量
C = <c1, ··· , cm> //已经使用资源量，初始为0
si (i = 1…n) //用户i的主资源所需份额，初始为0
Ui = <ui,1, ··· , ui,m> (i = 1…n) //分配给用户i的资源量，初始为0
挑选出所需主资源si最小的用户i；
Di ← 用户i下一个任务所需的资源量
if C + Di <= R then
C = C + Di //更新C
Ui = Ui + Di //更新U
else
return //资源已经用完
end if

饥饿和抢占

FairShare的计算会被用于判断饥饿以及是否进行抢占。在计算FairShare时，有两种：

• Steady FairShare，按照配置文件中所有queue的weight，计算出的。
• Instantaneous FairShare，，按照配置文件中所有queue的weight，仅对包含活动应用程序的queue计算出的。
  在配置yarn.scheduler.fair.preemption和yarn.scheduler.fair.preemption.cluster-utilization-threshold后，抢占会启用。

饥饿有两种：

1. FairShare Starvation
   要注意的是，在同一个队列里面，如果存在多个应用程序，它们会平均的分摊Instantaneous FairShare。因此可能存在队列整体不是饥饿状态，但是每个应用程序是。
   判定条件为：
   1. 未获得所要求的资源。
   2. 应用程序资源使用低于Instantaneous FairShare。
   3. 应用程序的资源使用低于fairSharePreemptionThreshold，并持续fairSharePreemptionTimeout。
2. MinShare Starvation
   判定条件为：
   1. 未获得所要求的资源。
   2. 应用程序资源使用低于MinShare。
   3. 应用程序的资源使用低于MinShare，并持续MinSharePreemptionTimeout。

决定需要进行抢占的时候，可能在多个队列中都有可抢占的container，决定container是否可以被抢占，需要满足：

1. 所在队列是可抢占的。
2. 杀死container以后不会导致应用程序的资源低于Instantaneous FairShare。

启用抢占并不能保证队列或应用程序能够获得所有的Instantaneous FairShare。只能最终保证脱离饥饿的状态，即获得fairSharePreemptionThreshold份额的资源。

FairShare Starvation、MinShare Starvation以及抢占的关系如下：