前言

本文一切基于MySql InnoDB

概念

1. 分区：把一张表的数据分成多个区块，在逻辑上看最终只是一张表，但底层是由多个物理区块组成的

2. 分表：把一张表按一定的规则分解成多个具有独立存储空间的实体表。系统读写时需要根据定义好的规则得到对应的子表名，然后操作它。

3. 分库：把一个库拆成多个库，突破库级别的数据库操作I/O瓶颈。

在mysql中，schema和库(database)是一个概念

数据库架构演变

一开始，我们只用单机数据库就足够满足业务需要了，但随着业务的拓展，带来越来越多的请求，我们将数据库的写操作和读操作进行分离，使用多个从库副本（Slaver Replication）负责读，使用主库（Master）负责写。从库从主库同步更新数据，保持数据一致。架构上的数据库主从同步，使得从库可以水平扩展，所以更多的读请求不成问题。

但是当用户量级上来后，写请求越来越多，该怎么办？加一个Master是不能解决问题的， 因为数据要保存一致性，写操作需要2个master之间同步，相当于是重复了，而且更加复杂。

这时就需要用到分库分表，对写操作进行切分。

什么情况下要分库分表

任何问题都是太大或者太小的问题，我们这主要面对的是数据量太大的问题。

1. 用户请求量太大

   • 瓶颈：单服务器的TPS，内存，IO都是有限的。
   • 解决方法：分散请求到多个服务器上； 其实用户请求和执行一个sql查询是本质是一样的，都是请求一个资源，只是用户请求还会经过网关，路由，http服务器等。

2. 单表数据量太大

   • 瓶颈：索引膨胀，查询耗时长，影响正常CRUD。
   • 解决方法：切分成多个数据集更小的表。

3. 单库数据量太大

   • 瓶颈：单个数据库处理能力有限，单库所在服务器上磁盘空间不足，I/O有限；
   • 解决方法：切分成更多更小的库

1 分区

首先，我们要明白分区的区是指什么！

我们在《【InnoDB详解二】MySQL文件系统和InnoDB存储结构》一文中提到过，MySQL的物理数据，存储在表空间文件（.ibdata1和.ibd）中，这里讲的分区的意思是指将同一表中不同行的记录分配到不同的物理文件中，几个分区就有几个.idb文件。

MySQL在5.1时添加了对水平分区的支持。分区是将一个表或索引分解成多个更小，更可管理的部分。每个区都是独立的，可以独立处理，也可以作为一个更大对象的一部分进行处理。这个是MySQL支持的功能，业务代码无需改动。

可以通过使用SHOW VARIABLES命令来确定MySQL是否支持分区，如：

1
2
3
4
5
6
7
8

mysql> SHOW VARIABLES LIKE '%partition%';
 
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| have_partition_engine | YES   |
+-----------------------+-------+
1 row in set (0.00 sec)

在如上列出的一个正确的SHOW VARIABLES 命令所产生的输出中，如果没有看到变量have_partition_engine的值为YES，那么MySQL的版本就不支持分区。

MySQL是面向OLTP的数据库，对于分区的使用应该更加小心，如果不清楚如何使用分区可能会对性能产生负面的影响。

1.1 MySQL分区类型

目前MySQL支持一下几种类型的分区：

1. RANGE分区：基于一个给定区间边界，得到若干个连续区间范围，按照分区键的落点，把数据分配到不同的分区；
2. LIST分区：类似RANGE分区，区别在于LIST分区是基于枚举出的值列表分区，RANGE是基于给定连续区间范围分区；
3. HASH分区：基于用户自定义的表达式的返回值，对其根据分区数来取模，从而进行记录在分区间的分配的模式。这个用户自定义的表达式，就是MySQL希望用户填入的哈希函数。
4. KEY分区：类似于按HASH分区，区别在于KEY分区只支持计算一列或多列，且使用MySQL 服务器提供的自身的哈希函数。

如果表存在主键或者唯一索引时，分区列必须是唯一索引的一个组成部分。

在实战中，十有八九都是用RANGE分区。

1.1.1 RANGE分区

RANGE分区是实战最常用的一种分区类型，行数据基于属于一个给定的连续区间的列值被放入分区。

但是记住，当插入的数据不在一个分区中定义的值的时候，会抛异常。

RANGE分区主要用于日期列的分区，比如交易表啊，销售表啊等。可以根据年月来存放数据。

如果你分区走的唯一索引中date类型的数据，那么注意了，优化器只能对YEAR(),TO_DAYS(),TO_SECONDS(),UNIX_TIMESTAMP()这类函数进行优化选择。

实战中可以用int类型的字段来存时间戳做分区列，那么只用存yyyyMM就好了，也不用关心函数了。

MySQL使用PARTITION命令来做分区，sql语句如下：

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

CREATE TABLE
    `Order` (
        `id`
        INT NOT NULL AUTO_INCREMENT,
        `partition_key`
        INT NOT NULL,
        `amt`
        DECIMAL(5) NULL) PARTITION BY RANGE(partition_key)
PARTITIONS 5(
    PARTITION part0 VALUES LESS THAN(201901),
    PARTITION part1 VALUES LESS THAN(201902),
    PARTITION part2 VALUES LESS THAN(201903),
    PARTITION part3 VALUES LESS THAN(201904),
    PARTITION part4 VALUES LESS THAN(201905),
    PARTITION part4 VALUES LESS THAN MAXVALUE;

RANGE分区通过使用PARTITION BY RANGE(expr)实现，其中“expr” 可以是某个列值，如id，no，partition_key等。或一个基于某个列值并返回一个整数值的表达式，如YEAR(date)。不过值得注意的是，expr的返回值，不可以为NULL。

其中，MAXVALUE 表示最大的可能的整数值。如果没有设置MAXVALUE这个分区，那么此时如果insert一个partition_key大于201905的记录，MySQL就会抛出异常，插入失败。

VALUES LESS THAN的排列必须从小到大顺序列出，这样MySQL才能识别一个一个的区间段。

这时候我们先插入一些数据：

1
2
3

INSERT INTO `Order` (`id`, `partition_key`, `amt`) VALUES ('1', '201901', '1000');
INSERT INTO `Order` (`id`, `partition_key`, `amt`) VALUES ('2', '201902', '800');
INSERT INTO `Order` (`id`, `partition_key`, `amt`) VALUES ('3', '201903', '1200');

现在我们查询一下，通过EXPLAIN PARTITION命令发现SQL优化器只需搜对应的区，不会搜索所有分区:

因为partition_key是分区键。当然，我们也可以直接指定搜索哪个分区:

SELECT * FROM Order PARTITION (part0,part1) WHERE status amt > 1000

注意，如果sql语句不指定分区，则会走所有分区，性能反而会不升反降。所以分区表后，select语句必须走分区键。

涉及聚合函数SUM()、COUNT()的查询时，如果不指定分区，那么会在每个分区上并行处理。例如执行这条语句SELECT COUNT(1) FROM Order，则会在每个分区上都同时运行查询；

一个例子不够，我们再举一个例子，来看看expr是个函数表达式的场景，假如现在有如下雇员表：

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

CREATE TABLE employees (
    id INT NOT NULL,
    fname VARCHAR(30),
    lname VARCHAR(30),
    hired DATE NOT NULL DEFAULT '1970-01-01',
    separated DATE NOT NULL DEFAULT '9999-12-31',
    job_code INT,
    store_id INT
)
PARTITION BY RANGE (YEAR(separated)) (
    PARTITION p0 VALUES LESS THAN (1991),
    PARTITION p1 VALUES LESS THAN (1996),
    PARTITION p2 VALUES LESS THAN (2001),
    PARTITION p3 VALUES LESS THAN MAXVALUE
);

在这个方案中，在1991年前离职的所有雇员的记录保存在分区p0中，1991年到1995年期间离职的所有雇员的记录保存在分区p1中， 1996年到2000年期间离职的所有雇员的记录保存在分区p2中，2000年后离职的所有工人的信息保存在p3中。

当需要删除“旧的”数据时，使用分区会有意想不到的效果。

假如我们想删除所有在1991年前就已经离职的雇员的记录，你只需简单地使用ALTER TABLE employees DROP PARTITION p0;

对于有大量行的表，这比运行DELETE FROM employees WHERE YEAR(separated) <= 1990要有效得多。

1.1.2 LIST分区

MySQL中的LIST分区在很多方面类似于RANGE分区。和RANGE分区一样，LIST分区的每个分区必须明确定义。它们的主要区别在于，LIST分区是基于枚举出的值列表分区，RANGE是基于给定连续区间范围分区；

LIST分区通过使用PARTITION BY LIST(expr)来实现，我们假定有20个音像店，分布在4个有经销权的地区，如下表所示：

要按照属于同一个地区商店的记录保存在同一个分区的原则来分割表，可以使用下面的CREATE TABLE语句：

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

CREATE TABLE employees (
    id INT NOT NULL,
    fname VARCHAR(30),
    lname VARCHAR(30),
    hired DATE NOT NULL DEFAULT '1970-01-01',
    separated DATE NOT NULL DEFAULT '9999-12-31',
    job_code INT,
    store_id INT
)
PARTITION BY LIST(store_id)
    PARTITION pNorth VALUES IN (3,5,6,9,17),
    PARTITION pEast VALUES IN (1,2,10,11,19,20),
    PARTITION pWest VALUES IN (4,12,13,14,18),
    PARTITION pCentral VALUES IN (7,8,15,16)
);

可以看到，和RANGE分区相比，LIST分区的VALUES IN后面接的是枚举值列表，不像RANGE是用VALUES LESS THAN来定义区间边界。

如果试图插入字段值（或分区表达式的返回值）不在分区值列表中的任何一行时，那么“INSERT”查询将失败并报错。例如，假定LIST分区的采用上面的方案，那么下面的查询将失败：INSERT INTO employees VALUES (224, 'Linus', 'Torvalds', '2002-05-01', '2004-10-12', 42, 21);。因为“store_id”字段值21不能在用于定义分区pNorth, pEast, pWest,或pCentral的值列表中找到。

要重点注意的是，LIST分区没有类似如“VALUES LESS THAN MAXVALUE”这样的包含其他值在内的定义。所以将要匹配的任何值都必须在值列表中能够找到。

1.1.3 HASH分区

HASH分区主要用来确保数据在预先确定数目的分区中平均分布。在RANGE和LIST分区中，我们必须明确指定一个给定的区间或列值集合，来指定哪些记录进入哪些分区；而在HASH分区中，MySQL自动完成分配记录到区间的工作，你所要做的只是确定一个用来做哈希的字段或者表达式，以及指定被分区的表将要被分割成的分区数量。

要使用HASH分区来分割一个表，要在CREATE TABLE 语句上添加一个PARTITION BY HASH (expr)子句，其中“expr”同样可以是一个返回一个整数的表达式，或者仅仅是字段类型为整型的某个字段。

此外，你很可能需要在后面再添加一个“PARTITIONS num”子句，其中num 是一个非负的整数，它表示表将要被分割成分区的数量。

例如，下面的语句创建了一个使用基于“store_id”列进行哈希处理的表，该表被分成了4个分区：

1
2
3
4
5
6
7
8
9
10
11

CREATE TABLE employees (
    id INT NOT NULL,
    fname VARCHAR(30),
    lname VARCHAR(30),
    hired DATE NOT NULL DEFAULT '1970-01-01',
    separated DATE NOT NULL DEFAULT '9999-12-31',
    job_code INT,
    store_id INT
)
PARTITION BY HASH(store_id)
PARTITIONS 4；

如果没有包括一个PARTITIONS子句，那么分区的数量将默认为1。

注意，expr不应该设置的过于复杂，因为每当插入或更新（或者可能删除）一行时，这个表达式都要计算一次；这意味着非常复杂的表达式可能会引起性能问题，尤其是在执行同时影响大量行的运算（例如批量插入）的时候。

最有效率的哈希函数是只对单个表列进行计算，并且它的结果值随字段值进行一致地增大或减小，因为这考虑了在分区范围上的“修剪”。也就是说，表达式值和它所基于的列的值变化越接近，MySQL就可以越有效地使用该表达式来进行HASH分区。

当使用了“PARTITION BY HASH”时，MySQL将基于用户提供的函数结果的模数来确定使用哪个编号的分区。换句话，对于一个表达式“expr”，将要保存记录的分区编号为N ，其中“N = MOD(expr, num)”。

1.1.4 KEY分区

按照KEY进行分区类似于按照HASH分区，除了HASH分区使用的用户定义的表达式，而KEY分区的哈希函数是由MySQL 服务器提供。

MySQLCluster使用函数MD5()来实现KEY分区；对于使用其他存储引擎的表，服务器使用其自己内部的 哈希函数，这些函数是基于与PASSWORD()一样的运算法则。

“CREATE TABLE … PARTITION BY KEY”的语法规则类似于创建一个通过HASH分区的表的规则。它们唯一的区别在于使用的关键字是KEY而不是HASH，并且KEY分区只采用一个或多个列名的一个列表。

1
2
3
4
5
6
7

CREATE TABLE tk (
    col1 INT NOT NULL,
    col2 CHAR(5),
    col3 DATE
)
PARTITION BY LINEAR KEY (col1)
PARTITIONS 3;

1.1.5 子分区

子分区是分区表中每个分区的再次分割。例如，考虑下面的CREATE TABLE 语句：

1
2
3
4
5
6
7
8
9

CREATE TABLE ts (id INT, purchased DATE)
    PARTITION BY RANGE(YEAR(purchased))
    SUBPARTITION BY HASH(TO_DAYS(purchased))
    SUBPARTITIONS 2
    (
        PARTITION p0 VALUES LESS THAN (1990),
        PARTITION p1 VALUES LESS THAN (2000),
        PARTITION p2 VALUES LESS THAN MAXVALUE
    );

表ts有3个RANGE分区。这3个分区（p0, p1, 和 p2）中的每一个分区又被进一步分成了2个子分区。实际上，整个表被分成了3 * 2 = 6个分区。但是，由于PARTITION BY RANGE子句的作用，p0分区的子分区里，只会保存“purchased”列中值小于1990的那些记录。

在MySQL 5.1中，对于已经通过RANGE或LIST分区了的表再进行子分区是可能的。子分区既可以使用HASH希分区，也可以使用KEY分区。这也被称为复合分区（composite partitioning）。

为了对个别的子分区指定选项，使用SUBPARTITION 子句来明确定义子分区也是可能的。例如，创建在前面例子中给出的同一个表的、一个更加详细的方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

CREATE TABLE ts (id INT, purchased DATE)
    PARTITION BY RANGE(YEAR(purchased))
    SUBPARTITION BY HASH(TO_DAYS(purchased))
    (
        PARTITION p0 VALUES LESS THAN (1990)
        (
            SUBPARTITION s0,
            SUBPARTITION s1
        ),
        PARTITION p1 VALUES LESS THAN (2000)
        (
            SUBPARTITION s2,
            SUBPARTITION s3
        ),
        PARTITION p2 VALUES LESS THAN MAXVALUE
        (
            SUBPARTITION s4,
            SUBPARTITION s5
        )
    );

不过有几点要注意的语法项：

1. 每个分区必须有相同数量的子分区。
2. 如果在一个分区表上的某个分区上使用SUBPARTITION来明确定义子分区，那么就必须定义其他所有分区的子分区。

子分区可以用于特别大的表，在多个磁盘间分配数据和索引。假设有6个磁盘，分别为/disk0， /disk1， /disk2等。现在考虑下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

CREATE TABLE ts (id INT, purchased DATE)
    PARTITION BY RANGE(YEAR(purchased))
    SUBPARTITION BY HASH(TO_DAYS(purchased))
    (
        PARTITION p0 VALUES LESS THAN (1990)
        (
            SUBPARTITION s0a
                DATA DIRECTORY = '/disk0'
                INDEX DIRECTORY = '/disk1',
            SUBPARTITION s0b
                DATA DIRECTORY = '/disk2' 
                INDEX DIRECTORY = '/disk3'
        ),
        PARTITION p1 VALUES LESS THAN (2000)
        (
            SUBPARTITION s1a
                DATA DIRECTORY = '/disk4/data' 
                INDEX DIRECTORY = '/disk4/idx',
            SUBPARTITION s1b
                DATA DIRECTORY = '/disk5/data' 
                INDEX DIRECTORY = '/disk5/idx'
        ),
        PARTITION p2 VALUES LESS THAN MAXVALUE
        (
            SUBPARTITION s2a,
            SUBPARTITION s2b
        )
    );

• DATA DIRECTORY表示数据的物理文件的存放目录
• INDEX DIRECTORY表示索引的物理文件的存放目录

在这个例子中，每个RANGE分区的数据和索引都使用一个单独的磁盘。存储的分配如下：

1. 购买日期在1990年前的记录占了大量的存储空间，所以把它分为了四个部分进行存储，组成p0分区的两个子分区（s0a 和s0b）的数据和索引都分别用一个单独的磁盘进行存储。换句话说：
   • 子分区s0a 的数据保存在磁盘/disk0中。
   • 子分区s0a 的索引保存在磁盘/disk1中。
   • 子分区s0b 的数据保存在磁盘/disk2中。
   • 子分区s0b 的索引保存在磁盘/disk3中。
2. 保存购买日期从1990年到1999年间的记录（分区p1）不需要保存购买日期在1990年之前的记录那么大的存储空间。这些记录分在2个磁盘（/disk4和/disk5）上保存，而不是4个磁盘：
   • 属于分区p1的第一个子分区（s1a）的数据和索引保存在磁盘/disk4上 — 其中数据保存在路径/disk4/data下，索引保存在/disk4/idx下。
   • 属于分区p1的第二个子分区（s1b）的数据和索引保存在磁盘/disk5上 — 其中数据保存在路径/disk5/data下，索引保存在/disk5/idx下。
3. 保存购买日期从2000年到现在的记录（分区p2）不需要前面两个RANGE分区那么大的空间。当前，在默认的位置能够足够保存所有这些记录。

1.2 分区维护

MySQL提供了许多修改分区表的方式。添加、删除、重新定义、合并或拆分已经存在的分区是可能的。所有这些操作都可以通过使用ALTER TABLE命令的分区扩展来实现。

下面我们来总结一下所有分区维护的命令，为简便计，我们定义几种partitions_exprs来替代如下子命令：

• RANGE分区，range_partitions_exprs(n)即为：

  1 2	PARTITION p VALUES LESS THAN (xxx) ...(n个PARTITION子句)

• LIST分区，list_partitions_exprs即为：

  1 2	PARTITION p VALUES IN (xxx,yyy,...), ...(n个PARTITION子句)

1.2.1 添加分区

1. 为已创建的未分区表创建分区：
   • RANGE：ALTER TABLE tb PARTITION BY RANGE (expr) ( range_partitions_exprs(n>0) );
   • LIST：ALTER TABLE tb PARTITION BY LIST (expr) ( list_partitions_exprs(n>0) );
   • HASH：ALTER TABLE tb PARTITION BY HASH(expr) PARTITIONS 2;
   • KEY：ALTER TABLE tb PARTITION BY KEY(expr) PARTITIONS 2;
2. 为分区表添加n个分区：
   • RANGE：ALTER TABLE tb ADD PARTITION ( range_partitions_exprs(n>0) );
   • LIST：ALTER TABLE tb ADD PARTITION ( list_partitions_exprs(n>0) );
   • HASH & KEY：ALTER TABLE tb ADD PARTITION PARTITIONS n;

对于通过RANGE分区的表，只可以使用ADD PARTITION添加新的分区到分区列表的尾端。设法通过这种方式在现有分区的前面或之间增加一个新的分区，将会导致报错。此时建议使用下文的拆分操作，REORGANIZE命令可以运行expr重叠。

不能添加这样一个新的LIST分区，该分区包含有已经包含在现有分区值列表中的任意值。如果试图这样做，将会导致错误。此时建议使用下文的拆分操作，REORGANIZE命令可以运行expr重叠。

1.2.2 重调整分区

1. 数据不丢失的前提下，将m个分区合并为n个分区（m>n），即减量重新组织分区
   • RANGE：ALTER TABLE tb REORGANIZE PARTITION s0,s1,... INTO ( range_partitions_exprs(n) )
   • LIST：ALTER TABLE tb REORGANIZE PARTITION s0,s1,... INTO ( list_partitions_exprs(n) )
   • HASH & KEY：ALTER TABLE clients COALESCE PARTITION n; (n小于原有分区数)
2. 数据不丢失的前提下，将分区表的m个分区拆分为n个分区（m<n），即增量重新组织分区
   • RANGE：ALTER TABLE tb REORGANIZE PARTITION p0,p1,... INTO ( range_partitions_exprs(n) )
   • LIST：ALTER TABLE tb REORGANIZE PARTITION p0,p1,... INTO ( list_partitions_exprs(n) )

不能使用REORGANIZE PARTITION来改变表的分区类型；也就是说，例如，不能把RANGE分区变为HASH分区，反之亦然。也不能使用该命令来改变分区表达式或列。

3. 重建分区，即先删除分区中的所有记录，然后重新插入。可用于整理分区碎片。
   • ALTER TABLE tb REBUILD PARTITION p0, p1;
4. 优化分区，整理分区碎片
   • ALTER TABLE tb OPTIMIZE PARTITION p0, p1;

如从分区中删除了大量的行，或者对一个带有可变长度字段（VARCHAR、BLOB、TEXT类型）的行作了许多修改，可以使用优化分区来收回没有使用的空间，并整理分区数据文件的碎片。
5. 修复分区，修补被破坏的分区。
- ALTER TABLE tb REPAIR PARTITION p0,p1;
6. 检查分区，这个命令可以告诉你分区中的数据或索引是否已经被破坏，如果被破坏，请使用修复分区来修补
- ALTER TABLE tb CHECK PARTITION p1;

1.2.3 删除分区

1. 删除一个分区，以及分区内的所有数据：
   • ALTER TABLE tb DROP PARTITION p2;
2. 删除一个分区，但保留分区内的所有数据(MySQL 5.5引入)：
   • ALTER TABLE tb TRUNCATE PARTITION p2;

1.2.4 查询分区数据

1. 查看某个schema下某个表的分区信息
   • SELECT * FROM INFORMATION_SCHEMA.PARTITIONS WHERE TABLE_SCHEMA = 'xxx' AND TABLE_NAME LIKE 'xxxx';
2. 分析某个分区,主要看行数和名称以及状态
   • ALTER TABLE tb ANALYZE PARTITION p3;

2 分表

分表顾名思义，就是把一张超大的数据表，拆分为多个较小的表，使得一些超大表的痼疾，得到有效的缓解。

超大表会带来如下的影响：

1. 单表数据量太大，会被频繁读写，加锁操作密集，导致性能降低。
2. 单表数据量太大，对应的索引也会很大，查询效率降低，增删操作的性能也会降低。

分表和分区看起来十分类似，确实，分区已经能够在磁盘层面将一张表拆分成多个文件了，理论上前面提到的大表的问题都能得到有效解决。因为分区就是分表的数据库实现版本。

在MySQL 5.1分区功能出现以前，要想解决超大表问题，只能采用分表操作，因为这类问题十分常见，MySQL才自带了一个分区功能，以达到相同的效果。

所以你可以直接说分区就是分表的替代，分表是分区出现以前的做法。不过这不代表我们就没有必要学习分表了，相反，水平分表的功能或许可以用更加便捷的分区来替代，但是垂直分表的功能，分区却无法替代。

分表只能通过程序代码来实现，目前市面上有许多分表的框架。

2.1 分表和分区的区别

1. 分区只是一张表中的数据和索引的存储位置发生改变，分表则是将一张表分成多张表，是真实的有多套表的配套文件
2. 分区没法突破数据库层面，不论怎么分区，这些分区都要在一个数据库下。而分表可以将子表分配在同一个库中，也可以分配在不同库中，突破数据库性能的限制。
3. 分区只能替代水平分表的功能，无法取代垂直分表的功能。

2.2 分表的类型

分表分为水平分表和垂直分表。

2.2.1 水平分表

水平分表和分区很像，或者说分区就是水平分表的数据库实现版本，它们分的都是行记录，就像用一把刀，水平的将一个表切成多张表一样。

针对数据量巨大的单张表（比如订单表），我们按照某种规则，切分到多张表里面去。

但是需要注意，如果这些表还是在同一个库中，所以库级别的数据库操作还是有IO瓶颈。分表可以将单张表的数据切分到多个服务器上去，每个服务器具有相应的库与子表，这是分区所不能有的优势。

水平分表的切分规则一般有如下几种：

1. 范围切分
   • 可以根据某个字段的范围做划分，比如订单号字段，从0到10000一个表，10001到20000一个表。
2. HASH取模
   • 可以根据某个字段的HASH取模做划分，比如将一个用户表分成10个子表，可以取用户id，然后hash后取10的模，从而分配到不同的数据库上。不过这种划分一旦确定后，就无法改变子表数量了。
3. 地理/国籍/类型等
   • 比如按照华东，华南，华北这样来区分业务表，或者安卓用户，IOS用户等来区分用户表。
4. 时间
   • 按照时间切分，比如将6个月前，甚至一年前的数据切出去放到另外的一张表，因为随着时间流逝，这些表的数据被查询的概率变小，所以没必要和“热数据”放在一起，这个也是“冷热数据分离”。

2.2.2 垂直分表

水平分表分的是行记录，而垂直分表，分的是列字段，它就像用一把刀，垂直的将一个表切成多张表一样。

垂直分表是基于列字段进行的。一般是表中的字段较多，或者有数据较大长度较长（比如text，blob，varchar(1000)以上的字段）的字段时，我们将不常用的，或者数据量大的字段拆分到“扩展表”上。这样避免查询时，数据量太大造成的“跨页”问题。

垂直分表的切分规则很好理解，一般是“不常用”或者“字段数据量大”这两点来做切割，我们不多赘述。

3 分库

分库同样是为了应对超大数据带来的巨大的IO需求，如果不拆库，那么单库所能支持的吞吐能力和磁盘空间，就会成为制衡业务发展的瓶颈。分库的主要目的是为突破单节点数据库服务器的I/O能力限制，解决数据库水平扩展性问题。

3.1 分区分表之外的分库作用

也许你会问，我们有了分区和分表技术，还需要分库来解决大数据量的问题吗？对的，需要。

分区和分表可以把单表分到不同的硬盘上，但不能分配到不同服务器上。一台机器的性能是有限制的，用分库可以解决单台服务器性能不够，或者成本过高问题。

将一个库分成多个库，并在多个服务器上部署，就可以突破单服务器的性能瓶颈，这是分库必要性的最主要原因。

3.2 分库的类型

分库同样分为水平分库和垂直分库。

1. 水平分库
   • 水平分库和水平分表相似，并且关系紧密，水平分库就是将单个库中的表作水平分表，然后将子表分别置于不同的子库当中，独立部署。
   • 因为库中内容的主要载体是表，所以水平分库和水平分表基本上如影随形。
   • 例如用户表，我们可以使用注册时间的范围来分表，将2020年注册的用户表usrtb2020部署在usrdata20中，2021年注册的用户表usrtb2021部署在usrdata21中。
2. 垂直分库
   • 同样的，垂直分库和垂直分表也十分类似，不过垂直分表拆分的是字段，而垂直分库，拆分的是表。
   • 垂直分库是将一个库下的表作不同维度的分类，然后将其分配给不同子库的策略。
   • 例如，我们可以将用户相关的表都放置在usrdata这个库中，将订单相关的表都放置在odrdata中，以此类推。
   • 垂直分库的分类维度有很多，可以按照业务模块划分（用户/订单…），按照技术模块分（日志类库/图片类库…），或者空间，时间等等。

4 分库分表存在的问题

1. 事务问题。
   • 问题描述：在执行分库分表之后，由于数据存储到了不同的库上，数据库事务管理出现了困难。如果依赖数据库本身的分布式事务管理功能去执行事务，将付出高昂的性能代价；如果由应用程序去协助控制，形成程序逻辑上的事务，又会造成编程方面的负担。
   • 解决方法：利用分布式事务，协调不同库之间的数据原子性，一致性。

2. 跨库跨表的join问题。

   • 问题描述：在执行了分库分表之后，难以避免会将原本逻辑关联性很强的数据划分到不同的表、不同的库上，这时，表的关联操作将受到限制，我们无法join位于不同分库的表，也无法join分表粒度不同的表，结果原本一次查询能够完成的业务，可能需要多次查询才能完成。
   • 解决方法：tddl、MyCAT等都支持跨分片join。但是我们应该尽力避免跨库join，如果一定要整合数据，那么请在代码中多次查询完成。

3. 额外的数据管理负担和数据运算压力。

   • 问题描述：额外的数据管理负担，最显而易见的就是数据的定位问题和数据的增删改查的重复执行问题，这些都可以通过应用程序解决，但必然引起额外的逻辑运算，例如，对于一个记录用户成绩的用户数据表userTable，业务要求查出成绩最好的100位，在进行分表之前，只需一个order by语句就可以搞定，但是在进行分表之后，将需要n个order by语句，分别查出每一个分表的前100名用户数据，然后再对这些数据进行合并计算，才能得出结果。
   • 解决方法：无解，这是水平拓展的代价。

5 分库分表方案产品

目前市面上的分库分表中间件相对较多，其中基于代理方式的有MySQL Proxy和Amoeba；基于Hibernate框架的是Hibernate Shards；基于jdbc的有当当sharding-jdbc；基于mybatis的类似maven插件式的有蘑菇街的蘑菇街TSharding；通过重写spring的ibatis template类的Cobar Client。

还有一些大公司的开源产品：

1 动态规划的概念

1.1 定义

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

决策过程是什么呢？在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。各个阶段决策的选取依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。

在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

1.2 概念和术语

关于动态规划，我们要了解如下概念和术语，我们以0-1背包问题为例：

0-1背包问题:我们有n种物品，物品j的重量为wj，价格为pj，背包的总重量是W，如果限定每种物品只能选择0个或1个，那么如何选取物品，使背包内物品的总价值最大。

1. 阶段：
   • 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同
   • 0-1背包问题中，我们每一次选取一个新的物品放入背包的这个过程，就是一个阶段。
2. 状态：
   • 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。
   • 0-1背包问题中，我们每一次选取一个新的物品后，（已选取物品，已选取的物品总价值），这二者的值就是一个阶段的状态。
3. 决策
   • 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。
   • 0-1背包问题中，每次我们选取哪个物品放入，这就是一个决策，
4. 策略：
   • 由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。
   • 一次连续阶段的多个决策序列就是策略，比如策略A可以是：放入钢笔——放入水壶——放入睡袋。策略B是放入钢笔——放入睡袋——放入头盔。以此类推
5. 多阶段决策问题：
   • 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题
   • 0-1背包问题就是一个典型的多阶段决策问题。

1.3 核心思路

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

不过与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。在动态规划中，我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

动态规划的核心除了分阶段决策外，还有上面所说的避免重复计算。这个如何理解呢？

比如0-1背包问题，我们现在有1，2，3三个物品，xj=1表示j物品放入背包，xj=0则表示j物品没放入。同时策略C(x1x2x3)=001，表示x1和x2都没有放入背包，x3放入了背包。

现在假如通过穷举得到了如下的5种可行策略：

那么由图我们可以知道，C2=011和C3=010这两种策略，都要经过01这个策略，如果在计算011的时候我们计算一遍01，在计算010的时候我们又计算一遍01，那么就重复计算了，我们为什么不把01这个策略的状态（已选取物品，已选取的物品总价值）保存下来呢？这样在计算010的时候，直接就可以把01的结果拿出来用了。

动态规划算法可以理解为是分治法和穷举法的结合：

1. 它用分治法的思想将一个问题分为多个决策阶段，既将问题复杂性减小，也为后续的局部结果复用提供前提。
2. 它搜索解的方式还是穷举法那一套，只不过因为可以局部复用，所以它的复杂性会大大降低。

其关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间

1.4 适用场景

动态规划算法通常用于求解具有某种最优性质的多阶段决策问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和状态无后效性：

1. 最优化原理（最优子结构性质）
   • 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。
   • 在0-1背包问题中，我们假设策略C=011是最优解，也就是说背包存放x2和x3，才能使价值最高，那么它的子策略，01x和x11，也同样都是最优解。最优化原理通俗的讲就是：011是最优解，那么01x肯定也是最优解，01x表示x3先不论，x1肯定不能选，x2肯定要选，否则就不是最优解。
2. 状态无后效性：
   • 状态无后效性指的是每个阶段的状态都是过去阶段的一个完整总结，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策。这就是无后向性，又称为无后效性。
   • 在0-1背包问题中，我们的状态是（已选取物品，已选取的物品总价值），我们之所以选择这样的两个值作为状态，就是因为它都是对过去阶段的完整总结。这使得从这个状态基础上进行的新的决策，可以不用去关心之前的状态，因为之前的状态被总结了。之所以要使状态无后效性，就是为了便于存储和复用阶段的结果，避免重复计算。
   • 试想一下，如果状态不是无后效性的，比如我们选择的状态是（本次选取的物品），那么我们保存这个状态的值，根本对后面的复用没有帮助，后面要想知道背包还剩多少空间，还是要把之前经历过的阶段的解都计算一遍。

1.5 解题技巧

前文我们提到过，动态规划是分治法和穷举法的结合，同时，在动态规划中，我们可以用一个表来记录所有已穷举出的已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。具体的动态规划算法多种多样，但它们具有相同的填表格式。

那么，如何将上述的经验整理成解题技巧呢？还是用0-1背包问题为例，来看下所谓的填表格式到底是什么：

假设你是个小偷，背着一个可装4磅东西的背包。你可盗窃的商品有如下3件。为了让盗窃的商品价值最高，你该选择哪些商品？

每个动态规划算法都从一个填表的网格开始，背包问题的网格如下：

• 网格的各行为商品，各列为不同容量（1～4磅）的背包。单元格内填入当前情况下的最大背包价值。
• 第一行表示只能选吉他，第二行表示可以选吉他+音响，以此类推。
• 虽然我们题目的背包是4磅，但我们仍然需要1到3磅的前三列，因为它们将帮助我们在计算剩余空间时发挥作用。
• 网格最初是空的。我们将填充其中的每个单元格，网格填满后，就找到了问题的答案！

【填充第一行】

第一个单元格表示背包的容量为1磅。吉他的重量也是1磅，这意味着它能装入背包！因此这个单元格包含吉他，价值为1500美元。

由于这是第一行，只有吉他可供你选择，于是不管背包多大，单元格内的值都是1500美元，所以第一行的值都是1500。

【填充第二行】

我们现在处于第二行，可偷的商品有吉他和音响。我们先来看第一个单元格，它表示容量为1磅的背包。在此之前，可装入1磅背包的商品的最大价值为1500美元，由于容量1磅的背包装不下音响，因此最大价值依然是1500美元。接下来的两个单元格的情况与此相同。在这些单元格中，背包的容量分别为2磅和3磅，而以前的最大价值为1500美元。由于这些背包装不下音响，因此最大价值保持不变。

但如果背包的容量为4磅，那就能够装下音响！原来的最大价值为1500美元，但如果在背包中装入音响而不是吉他，价值将为3000美元！你更新了最大价值！在这个网格中，你逐步地更新最大价值。

于是我们得到了第二行：

【填充第三行】

笔记本电脑重3磅，没法将其装入容量为1磅或2磅的背包，因此前两个单元格的最大价值还是1500美元。

对于容量为3磅的背包，原来的最大价值为1500美元，但现在你可选择盗窃价值2000美元的笔记本电脑而不是吉他，这样新的最大价值将为2000美元！

对于容量为4磅的背包，当前的最大价值为3000美元，你可不偷音响，而偷笔记本电脑，但它只值2000美元。价值没有原来高。但笔记本电脑的重量只有3磅，背包还有1磅的容量没用！

在1磅的容量中，可装入的商品的最大价值是多少呢？根据之前计算的最大价值可知（第一列中最大的值），在1磅的容量中可装入吉他，价值1500美元。

注意，此时我们就用到了背包容量为1的那一列，所以我们之所以要算出与4磅无关的容量为1,2,3磅的结果，就是为了这一刻。

笔记本电脑和吉他的总价值为3500美元，因此偷它们是更好的选择。最终的网格类似于下面这样。

【总结】

经过上面的分析，我们可以发现，题目所要的答案，其实只是网格最右下角的那一个单元格。那我们为什么要算出其他的单元格呢？

因为下一个单元格的值，需要用到之前单元格的值来计算，比如最后的答案3500美元，就用到了背包容量为1的那一列的数据来计算剩余1磅空间的时候选择哪个物品最合算。

我们记录下之前单元格的值，就是为了计算新单元格的时候不用重复计算，就像这道题，我们最后想知道背包容量为1时应该如何选取物品，如果没有保存下结果，那我们要重新算一遍第一列的场景，那效率就很低了。

记忆化搜索，即用一个二维数组保存已经计算好的子问题的解，下次再计算相同子问题时，就不用重复求解了。

每一个新的单元格的值，都需要复用到之前单元格的数据来算出，如果我们能归纳出一个通用的以旧单元格值推导出新单元格值的公式，那就相当于找到了一条可得到最优解的方法。这个公式，我们称为状态转移方程。

我们前文提到过，状态是每一个阶段的总结，动态规划是多阶段决策的过程，我们在多个阶段间行进，状态也在一直转移。状态转移方程，顾名思义，就是状态变化的方程，比如说我们可以归纳出该题的状态转移方程如下图：

于是我们知道了：

1. 填表法是动态规划的固定套路，它能帮助我们理解状态转移的过程，并且记录和复用之前的结果。
2. 网格的每一个单元格，都可以理解为是一个阶段，阶段变量有两个，可选取物品类型和背包重量，也就是网格的横纵轴。
3. 每个阶段的策略，就是我们的状态转移方程，即我们用现有的状态，决策出了当前阶段的状态。
4. 动态规划的核心就在于：
   • 将题目划分为多个子问题，对应多个阶段
   • 确定哪些变量属于状态
   • 归纳出状态转移方程

2 经典题型

2.1 0-1背包问题

2.1.1 题目

【描述】：有 n 个物品和一个大小为 bagSize 的背包. 给定数组 itemSizes 表示每个物品的大小和数组 itemValues 表示每个物品的价值。问最多能装入背包的总价值是多大?

• itemSizes[i], itemValues[i], n, bagSize 均为整数
• 你不能将物品进行切分
• 你所挑选的要装入背包的物品的总大小不能超过 bagSize
• 每个物品只能取一次

【样例 1】:

• 输入: bagSize = 10, itemSizes = [2, 3, 5, 7], itemValues = [1, 5, 2, 4]
• 输出: 9
• 解释: 装入 itemSizes[1] 和 itemSizes[3] 可以得到最大价值, itemValues[1] + itemValues[3] = 9

【样例 2】:

• 输入: bagSize = 10, itemSizes = [2, 3, 8], itemValues = [2, 5, 8]
• 输出: 10
• 解释: 装入 itemSizes[0] 和 itemSizes[2] 可以得到最大价值, itemValues[0] + itemValues[2] = 10

2.1.2 题解

前文已叙述，不再赘述。

2.1.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public int backPack(int bagSize, int[] itemSizes, int[] itemValues) {
    int itemsNum = itemSizes.length;
    // 创建一个数组，存放已计算过的结果，填表法。
    int[][] values = new int[itemsNum][bagSize];
    // 开始填表，itemSizes数组中，0-itemIdx区间内的物品，为当前可选物品
    for (int itemIdx = 0;itemIdx < itemsNum;itemIdx++){
        for (int bagIdx = 0;bagIdx < bagSize;bagIdx++){
            int thisBagSize = bagIdx+1;// 因为下标为0开始，但背包size从1开始。
            // 从已计算的结果中获取【当前背包size下，如果当前物品不可取时，背包可存放的最大价值】。
            int maxValueWithoutThisItem = getCachedValue(itemIdx-1,bagIdx,values);
            // 计算【当前背包size下，如果当前物品可取时，背包可存放的最大价值】
            // 计算方法为：如果当前物品可以被当前背包size容纳
            //      那么尝试优先存放该物品，并从之前的不包含当前物品的结果中
            //          寻找【可以填满剩余空间的最大价值】，二者相加即为结果。
            int maxValueIncludeThisItem = itemSizes[itemIdx] <= thisBagSize ?
                    itemValues[itemIdx] + getCachedValue(itemIdx-1,thisBagSize-itemSizes[itemIdx]-1,values): maxValueWithoutThisItem;
            // 比较【当前背包size下，如果当前物品不可取时，背包可存放的最大价值】和【当前背包size下，如果当前物品可取时，背包可存放的最大价值】
            // 哪个大就选择哪个值作为当前阶段的解。
            values[itemIdx][bagIdx] = Math.max(maxValueWithoutThisItem,maxValueIncludeThisItem);
        }
    }
    return values[itemsNum-1][bagSize-1];
}
private int getCachedValue(int i,int j,int[][] values){
    if (i < 0 || j < 0){
        return 0;
    }

    return values[i][j];
}

2.2 最长公共子串

2.2.1 题目

【描述】：给出两个字符串，找到最长公共子串，并返回其长度。

• 子串的字符应该连续的出现在原字符串中，这与子序列有所不同。

【样例 1】:

• 输入: “hish” and “fish”
• 输出: 3
• 解释: 最长公共子串是 “ish”

【样例 2】:

• 输入: “hish” and “vista”
• 输出: 2
• 解释: 最长公共子串是 ‘is’

2.2.2 题解

将两个单词的字母分列为横纵轴，如下图所示。

因为公共子串有顺序和连续的要求（如is和si就不是一个公共子串，ios和is不是一个共同子串，只有is和is才是。），所以在矩阵当中，两个相邻的对角线的单元格都为1的时候，才是公共子串出现的时候。

那我们把两个相邻的成对角线的单元格都赋值1可以吗？不行，还记得我们动态规划状态的定义吗？状态是过去阶段的总结！

所以，我们应该用右下角的单元格来存储目前已出现的这个公共子串的长度，而不是单纯的赋值1。

对于前面的背包问题，最终答案总是在最后的单元格中。但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。

2.2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/** 最长公共子串
 * @param Str1: Str1 string
 * @param str2: str2 string
 * @return: the length of the longest common substring
 */
public int longestCommonSubstring(String str1, String str2) {
    int result = 0;
    if (str1.isEmpty()|| str2.isEmpty()){
        return result;
    }
    // 创建一个数组，存放已计算过的结果，填表法。
    int[][] values = new int[str1.length()][str2.length()];
    for (int i = 0;i<str1.length();i++){
        for (int j = 0;j<str2.length();j++){
            // 状态转移方程为：当两个字母相等时，当前值取左上角的单元格的值+1
            if (str1.charAt(i) == str2.charAt(j)){
                values[i][j] = getCachedValue(i-1,j-1,values)+1;
            }
            result = Math.max(result,values[i][j]);
        }
    }
    return result;
}
private int getCachedValue(int i,int j,int[][] values){
    if (i < 0 || j < 0 || i >= values.length || j >=values[0].length){
        return 0;
    }
    return values[i][j];
}

2.3 最长公共子串

2.3.1 题目

【描述】：给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

最长公共子序列的定义：

• 最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。

【样例 1】:

• 输入: “fosh” and “fort”
• 输出: 2
• 解释: 最长公共子序列是 “f”,”o”

【样例 2】:

• 输入: “fosh” and “fish”
• 输出: 3
• 解释: 最长公共子序列是 “f”,”s”,”h”

2.3.2 题解

将两个单词的字母分列为横纵轴，如下图所示。

因为公共子序列有顺序的要求，但是没有连续的要求（如is和si就不是一个公共子序列，但ios和is中的is是公共子序列），所以在矩阵当中，某个字母相等的单元格的左上部分存在另一个字母相等的单元格，才是公共子序列出现的时候。

但因为公共子序列没有连续的要求，故而两个1，可能离得有点远，没法像最长公共子串那一题一样直接根据左上相邻单元格来判断，所以在该题状态转移方程中，我们要注意将1一直传递下去。

所以我们得到状态转移方程：

2.3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/** 最长公共子序列
 * @param Str1: Str1 string
 * @param str2: Str1 string
 * @return: The length of longest common subsequence of Str1 and str2
 */
public int longestCommonSubsequence(String Str1, String str2) {
    int result = 0;
    if (Str1.isEmpty()|| str2.isEmpty()){
        return result;
    }
    // 创建一个数组，存放已计算过的结果，填表法。
    int[][] values = new int[Str1.length()][str2.length()];
    for (int i = 0;i<Str1.length();i++){
        for (int j = 0;j<str2.length();j++){
            // 状态转移方程为：
            // 1. 当两个字母相等时，当前值取左上角的单元格的值+1
            // 2. 当两个字母不等时，当前值取左方和上方两个单元格中最大的值
            if (Str1.charAt(i) == str2.charAt(j)){
                values[i][j] = getCachedValue(i-1,j-1,values)+1;
            }else {
                values[i][j] = Math.max(getCachedValue(i,j-1,values),getCachedValue(i-1,j,values));
            }
            result = Math.max(result,values[i][j]);
        }
    }
    return result;
}
private int getCachedValue(int i,int j,int[][] values){
    if (i < 0 || j < 0){
        return 0;
    }
    return values[i][j];
}

前言

排序算法可以分为两大类：

1. 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
2. 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

其中这些算法的复杂度如下表格：

稳定性：如果a原本在b前面，而a=b，排序之后a仍然在b的前面，则表示该算法是稳定的排序算法。

1 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，每一次比较两个元素，如果它们的顺序错误就把它们交换过来。

遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

冒泡排序的算法步骤如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，直到排序完成。

1.2 动图演示

1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public void bubbleSort() {
	int[] arr = new int[]{-12, 3, 2, 34, 5, 8, 1};
	// 冒泡排序，外层循环确定“冒泡”的次数，一共要进行n次冒泡
	// 每次冒泡完成，都会将当前数列的最大值推到数列尾端
	for (int i = 0; i < arr.length - 1; i++) {
		// 这一层循环是控制单次“冒泡”的，每次“冒泡”的遍历范围是未排序的部分数列
		// 所以j值小于arr.length-1-i，因为第i轮“冒泡”，数列的尾端就有i位已经排好序了。
		for (int j = 0; j < arr.length - 1 - i; j++) {
			// 随着j的增大，泡沫逐渐上浮，如果相邻的两项顺序不是我们希望的，那么要交换顺序
			if (arr[j] > arr[j + 1]) {
				// 交换顺序
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

由代码可见，冒泡排序的时间复杂度是O(n^2)，不过值得注意的是，在最好的情况下（即当前数列已经是我们想要的顺序了），它的时间复杂度是O(n)。要想得到线性的时间复杂度，我们需要改造一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public void bubbleSort() {
	int[] arr = {1,3,2,45,65,33,12};
	// 添加一个变量来标记是否进行了交换操作
	boolean didSwap = false;
	// 冒泡排序，外层循环确定“冒泡”的次数，一共要进行n次冒泡
	// 每次冒泡完成，都会将当前数列的最大值推到数列尾端
	for (int i = 0; i < arr.length - 1; i++) {
		// 这一层循环是控制单次“冒泡”的，每次“冒泡”的遍历范围是未排序的部分数列
		// 所以j值小于arr.length-1-i，因为第i轮“冒泡”，数列的尾端就有i位已经排好序了。
		for (int j = 0; j < arr.length - 1 - i; j++) {
			// 随着j的增大，泡沫逐渐上浮，如果相邻的两项顺序不是我们希望的，那么要交换顺序
			if (arr[j] > arr[j + 1]) {
				// 交换顺序
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				didSwap = true;
			}
		}
		// 如果一次冒泡过程中，一次交换操作都没执行，那说明数列已经有序了，直接返回
		if(didSwap == false) {
			return;
		}
	}
}

2 选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1,n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1,i-1]和R(i,n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1,i]和R[i+1,n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟选择，排序完成。

2.2 动图演示

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void selectionSort() {
	int[] arr = {1,3,2,45,65,33,12};
	// 做第i趟选择排序，[0,i)是有序区
	for(int i = 0; i < arr.length - 1; i++) {
		int minValIdx = i;
		// 遍历无序区[i,n]
		for(int j = minValIdx + 1; j < arr.length; j++){
			if(arr[j] < arr[minValIdx]){
				//记下目前找到的最小值所在的位置
				minValIdx = j;
			}
		}
		//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
		if(i != minValIdx){
			//交换a[i]和a[minValIdx]
			int temp = arr[i];
			arr[i] = arr[minValIdx];
			arr[minValIdx] = temp;
		}
	}
}

2.4 算法总结

选择排序是表现最稳定的排序算法之一，因为无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。

同时值得注意的是，它还是不稳定的，如何理解选择排序是不稳定的呢？

举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

唯一的好处可能就是不占用额外的内存空间。选择排序也是一般人想到的最多的排序方法，它的排序思路非常的常规。

3 插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的有序区间中从后向前扫描；
3. 如果当前被扫描的元素（已排序）大于新元素，将该元素移到下一位置，即将它的空间让出来；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置；
6. 重复步骤2~5。

3.2 动图演示

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public void insertionSort(){
	int[] arr = {1,3,2,45,65,33,12};
	// i控制有序区[0,i),i从1开始，说明arr[0]一开始默认有序
	// 同时arr[i]即为这一趟排序，要被用来插入的值
	for(int i=1; i<arr.length; i++){
		int val = arr[i];
		// j是在有序区[0,i)之间从前向后遍历的指针
		for(int j=i-1; j>0; j--){
			// 如果j的值比val大，那么j向后挪一个位置
			if(arr[j] > val){
				arr[j+1] = arr[j];
			} else {// 否则，说明找到了val应该在的位置
				arr[j+1] = val;
			}
		}
	}
}

3.4 算法总结

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

值得注意的是，插入排序最好情况（数列本身已经有序）的时间复杂度是O(n)，也就是说，每一趟的插入操作，都是第一步就找到了插入的位置，这样的时间复杂度是线性的。

4 快速排序（Quick Sort）

快速排序是采用分治法的思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

4.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；一般都采用当前数列的第一个元素作为pivot。
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列，重复步骤1-2进行递归排序，直到所有子数列都有序为止。

4.2 动图演示

4.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * @param arr        待排序列
 * @param start  待排序列起始位置
 * @param end 待排序列结束位置
 */
private static void quickSort(int[] arr, int start, int end) {
	if (start >= end) {
		return;
	}
	int left = start;
	int right = end;
	//待排序的第一个元素作为基准值
	int pivot = arr[left];

	//从左右两边交替扫描，直到left = right
	while (left < right) {
		while (right > left && arr[right] >= pivot) {
			//从右往左扫描，找到第一个比基准值小的元素
			right--;
		}

		//找到这种元素将arr[right]放入arr[left]中
		arr[left] = arr[right];

		while (left < right && arr[left] <= pivot) {
			//从左往右扫描，找到第一个比基准值大的元素
			left++;
		}

		//找到这种元素将arr[left]放入arr[right]中
		arr[right] = arr[left];
	}
	//基准值归位
	arr[left] = pivot;
	//对基准值左边的元素进行递归排序
	quickSort(arr, start, left - 1);
	//对基准值右边的元素进行递归排序。
	quickSort(arr, right + 1, end);
}

4.4 算法总结

快速排序顾名思义，它的性能可以达到比较类排序算法最高的O(nlogn)级别。不过由于分治法主要采用递归实现，所以它也是有额外的递归造成的栈空间的使用。因为一般情况下，快排会递归logn次，所以他的空间复杂度是O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

快排的最坏情况，是每次分隔，生成的两个subList都有一个是空集合，也就是每次选取的pivot是当前数列的最小值或者最大值，无法达到二分的效果。这种情况下，它的时间复杂度是O(n^2)，空间复杂度是O(n)。

5 希尔排序（Shell’s Sort）

希尔排序(Shell’s Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本，它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序是非稳定排序算法，也是第一个突破O(n2)的排序算法。

该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2. 因为插入排序每次遍历一遍完整数组，只能将一个元素移动到已排序区间的正确位置。当n值很大时，为了找到移动一个元素到正确位置的时间太长了，所以插入排序一般来说是低效的算法。

基于插入排序上述的这两点性质，希尔排序通过分组，达到了如下三个目的：

1. 通过分组，使得每个子序列的长度减少，使得每一次遍历，能较快的将一个元素确定位置。虽然这时确定的只是改元素在分组内的位置，可能并非整个序列的正确位置，但此时已经接近于它们排序后的最终位置了。
2. 通过分组，使得只要完整遍历一次整个序列的时间，就可以使每个分组内都有一个元素确定大概的位置，相比于插入排序的一次完整遍历只能确定一个元素的正确位置，性能提升非常明显。
3. 通过分组进行插入排序，使得希尔排序在进行最后一次全序列的插入排序时，基本上每个元素所在的位置已经接近于它排序后正确的位置了，面对这样的情况，插入排序的性能可以达到接近线性时间，即O(n)。

5.1 算法描述

先将整个待排序的序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量gap，一般默认初始为length/2。
2. 确定了gap后，则可以得到如下gap个分组，每个分组最多有length/gap个元素，如gap=length/2时分组如：{arr[0],arr[gap]}，{arr[1],arr[gap+1]}.....{arr[gap-1],arr[length-1]}
3. 对每个分组，执行插入排序。
4. 再确定一个新的gap，一般为再缩小一倍，gap=gap/2
5. 重复步骤2、3、4，直到gap=1为止，这时不存在其他分组了，最后执行一次对整个序列的插入排序，算法结束。

5.2 动图演示

5.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

private static void shellSort(int[] arr, int start, int end) {
    int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
    //希尔排序
    int gap = array.length;
    while (true) {
        gap /= 2;   //增量每次减半
        for (int i = 0; i < gap; i++) {// i控制分组，
            for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
                int k = j - gap;// k是组内元素的index
                while (k >= 0 && array[k] > array[k+gap]) {
                    int temp = array[k];
                    array[k] = array[k+gap];
                    array[k + gap] = temp;
                    k -= gap;
                }
            }
        }
        if (gap == 1)
            break;
    }
}

5.4 算法总结

希尔排序的时间的平均时间复杂度为O(n^1.3)，希尔排序时间复杂度最快的是O(nlog(2n))，没有快速排序算法O(n(logn))快，因此希尔排序在中等大小规模时表现良好，但对规模非常大的数据排序不是最优选择。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，一般来说，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。

6 归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列

6.1 算法描述

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序，再进行对半分，一直分到子序列的长度为1为止。
3. 将两个排序好的子序列合并，递归回溯，最后归并成一个最终的排序序列。

6.2 动图演示

6.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public static void main(String[] args) {
    int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10,7,21,15,9,7,42 };
    int[] newNums = new int[nums.length];
    mergeSort(nums,newNums, 0, nums.length - 1);
    for (int x : newNums) {
        System.out.println(x);
    }
}

public static void mergeSort(int[] nums,int[] newNums, int left, int right) {
    if (left == right)
        return;
    // 归并排序就是不断的在nums和newNums之间相互倒腾数据，每次递归都发生两次倒腾。
    int mid = left + (right - left) / 2;
    int leftArrIdx = left, rightArrIdx = mid + 1;
    mergeSort(nums,newNums, leftArrIdx, mid); //左有序数组
    mergeSort(nums,newNums, rightArrIdx, right); //右有序数组

    int newArrIdx = leftArrIdx;
    // 此时，leftArr = nums的[leftArrIdx,mid]区间，rightArr = nums的[rightArrIdx,right]区间
    // leftArr和rightArr都有序了，接下来进行第一次倒腾。
    // 三个指针控制，在把leftArr和rightArr的数组搬运到newNums对应位置的期间顺便进行合并（再排序）
    // 每次循环，leftArr和rightArr中，两个被指针指向的元素，较小的那个才会加入newNums
    while (leftArrIdx <= mid && rightArrIdx <= right) {
        newNums[newArrIdx++] = nums[leftArrIdx] < nums[rightArrIdx] ? nums[leftArrIdx++] : nums[rightArrIdx++];
    }
    // 如果rightArr都加入newNum了，leftArr还有剩余，则把leftArr一股脑加进去
    while (leftArrIdx <= mid)
        newNums[newArrIdx++] = nums[leftArrIdx++];
    // 如果leftArr都加入newNum了，rightArr还有剩余，则把rightArr一股脑加进去
    while (rightArrIdx <= right)
        newNums[newArrIdx++] = nums[rightArrIdx++];

    // 到这里为止，newNums的[letf,right]已经是有序的了。
    // 但nums的[letf,right]区间还是无序的，还是分成了[left,mid]和[mid+1,right]这两个有序区间
    // 这时用newNums的顺序覆盖nums，这一步不是多余的，因为递归出栈后，逻辑是从nums里面拿排序好的数据
    // 所以进行第二次倒腾，第二次倒腾是为了递归出栈后的第一次倒腾有意义。
    for(int i=left;i <= right;i++){
        nums[i] = newNums[i];
    }
}

6.4 算法总结

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

7 堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7.1 算法描述

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
4. 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 动图演示

7.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public static void main(String[] args) {
    int[] arr = {1, 4, 6, 8, 2, 5, 3, 7, 9};
    heapSort(arr);
}


public static void heapSort(int[] arr) {

    // 首先我们要明确下，用数组表示堆/二叉树的时候，有如下公式：
    // 1. arr[0]到arr[length/2],都是非叶子节点
    // 2. 对于某个节点arr[i]，则可知它的左子结点是arr[2i+1]，右子结点是arr[2i+2]

    // 循环建立初始堆，大顶堆
    // parentIdx从后往前遍历，说明进行上滤操作，调整是从下而上的
    // 创建初始堆之所以要从下而上，是因为现在整个堆都是无序的
    for (int parentIdx = arr.length / 2; parentIdx >= 0; parentIdx--) {
        heapAdjust(arr, parentIdx, arr.length);
    }

    // lastUnsorted，指向未排序区间的最后一个元素
    for (int lastUnsorted = arr.length - 1; lastUnsorted > 0; lastUnsorted--) {
        // 将 堆顶元素 和 未排序区间的最后一个元素 进行交换
        int temp = arr[lastUnsorted];
        arr[lastUnsorted] = arr[0];
        arr[0] = temp;

        // 重新调整堆，此时要从上而下调整，进行下滤操作，
        // 因为此时除了堆顶，其他节点都有序了，这种情况下滤操作更快
        heapAdjust(arr, 0, lastUnsorted);
    }
}

public static void heapAdjust(int[] arr, int parent, int length) {
    int left = 2 * parent + 1; // 左孩子
    int right = 2 * parent + 2; // 右孩子

    // 如果左子结点大于父节点，交换
    if (left < length && arr[left] > arr[parent]) {
        swap(arr,parent,left);
        heapAdjust(arr, left,length);
    }

    // 如果右子结点大于父节点，交换
    if (right < length && arr[right] > arr[parent]) {
        swap(arr,parent,right);
        heapAdjust(arr, right,length);
    }

}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

7.4 算法总结

堆排序是一种不稳定的选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。

所以堆排序时间复杂度一般认为就是O(nlogn)级。时间复杂度很稳定，都是O(nlogn)。

8 计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

1. 找出待排序的数组A中最大元素值max和最小元素值min，并创建一个长度为max-min的数组C。
2. 统计数组A中每个值为i的元素出现的次数，存入数组C的第i-min项；
3. 数组C从小到大填充原数组A，数组C从第0项开始，每一项i输出C[i]次，输出的值是i+min。

8.2 动图演示

8.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void countingSort(int[] arr) {
    int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
    for (int val : arr){
        max = Math.max(max, val);
        min = Math.min(min, val);
    }
    int[] bucket = new int[max-min+1];


    for (int val : arr) {
        bucket[val-min]++;
    }

    int sortedIndex=0;
    for (int i = 0;i < bucket.length;i++) {
        while(bucket[i] > 0) {
            arr[sortedIndex++] = i+min;
            bucket[i]--;
        }
    }
}

8.4 算法总结

计数排序是一个稳定的排序算法。当输入的元素是 n 个范围差为k的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

9 桶排序（Bucket Sort）

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（一般使用快排），最后把每个桶里排好序的数据拼接起来。

算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中；可应用于数据量分布比较均匀，或比较侧重于区间数量时。

桶排序利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

我们用k表示桶的个数，那假设数据是均匀分布的，则每个桶的元素平均个数为n/k，那么桶排序的时间复杂度是O(n+nlog(n/k))=O(n+nlogn-nlogk)。

故而我们可以很明显的看出，O(n+nlogn-nlogk)，为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量，即k越大越好。当然，做到这一点很不容易，数据量巨大的情况下，映射函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中，使得每个桶内的排序性能接近。（试想一下极端情况，所有元素都在一个桶内，那时间复杂度就是快排的O(nlogn)了）

9.1 算法描述

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

9.2 动图演示

9.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public static void bucketSort(int[] arr,int bucketNum){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    //桶数
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }

    //将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int idx = (arr[i]-min)/(((max-min)/bucketNum)+1);
        bucketArr.get(idx).add(arr[i]);
    }
    System.out.printf(new Gson().toJson(bucketArr));
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }

    //将桶内数据填回原数组
    int i = 0;
    for (ArrayList<Integer> bucket : bucketArr){
        if (bucket.isEmpty()){
            continue;
        }
        for (int val : bucket){
            arr[i++] = val;
        }

    }
}

9.4 算法总结

桶排序在最优情况下（数组内的元素均匀分布，可以使得分桶后，每个桶内的元素数量差异不大），可以达到接近线性的时间复杂度，因为它不是比较排序算法，所以可以突破O(nlogn)的极限。

桶排序最坏的时间复杂度是O(nlogn)，也就是所有元素都在同一个桶内，这样相当于对整个列表使用了快排。

不过桶排序是稳定的排序算法。

10 基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照次低位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

比如一系列两位数数字组成的序列，他们比大小，十位上的数字肯定优先级更高，个位上的数字优先级较低。我们先按照个位上的数字排序，再按照十位上的数字排序，那么就可以得到十位>个位标准下的有序。

换句话说，如果对于数字大小的评价标准是个位>十位，那基数排序先判断十位再判断个位即可。

在十进制数中，基数r就等于10，即表示最大有10种可能，最多需要10个桶来映射数组元素。

10.1 算法描述

1. 取得数组中的最大数，并取得位数，这就确定了我们最多要判断多少位。
2. 将待排元素按照个位进行分桶；然后将这些桶中的元素按桶的编号重新串接起来，得到以个位排序完成的序列。
3. 再对序列按照十位进行分桶，然后将这些桶中的元素按桶的编号重新串接起来，得到以十位排序完成的序列。
4. 以此类推，一直到最高位进行分桶并且重新串接，最后得到完整排序的序列。

10.2 动图演示

10.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

private static void radixsSort(int[] array) {
    // 找到最大数
    int max = 0;
    for (int i : array) {
        max = Math.max(max,i);
    }
    // 判断位数
    int d = 0;
    while (max > 0) {
        max = max / 10;
        d++;
    }
    // 数字的基数都是10，所以建立十个队列
    List<ArrayList> bucket = new ArrayList<ArrayList>();
    for (int i = 0; i < 10; i++)
    {
        ArrayList queue = new ArrayList();
        bucket.add(queue);
    }
    // 进行times次分配和收集
    for (int i = 0; i < d; i++) {
        // 分配
        for (int j = 0; j < array.length; j++) {
            int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            ArrayList queue = bucket.get(x);
            queue.add(array[j]);
            bucket.set(x, queue);
        }
        // 收集
        int count = 0;
        for (int j = 0; j < 10; j++) {
            while (bucket.get(j).size() > 0) {
                ArrayList<Integer> queue = bucket.get(j);
                array[count] = queue.get(0);
                queue.remove(0);
                count++;
            }
        }
    }
}

10.4 算法总结

假设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r。那么每处理一位数，就需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历一遍桶+遍历一遍数组，最多元素数为n，则处理一位数的时间复杂度为O(n+r)。处理d位数的总的时间复杂度为O(d*(n+r))。

基数排序的空间复杂度为O(n+r)，n表示n个指针，用来给桶内的元素做后驱指向，r则是开辟了长度为r的队列，用来当做r个桶。

基数排序基于分别排序，分别收集，所以是稳定的。

基数排序算法适用于位数不多，待排序列最大位数不是特别大，每一位数的范围不大的情况下（当然对于数字排序，每一位的范围都是[0,9]）。

前言

二叉树的遍历是指不重复地访问二叉树中所有结点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历主要包括前序遍历、中序遍历、后序遍历。

一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树，则二叉树的遍历方式有 6 种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以默认都是先左后右，故而只讨论三种方式：

• DLR–前序遍历（根在前，从左往右，首先访问根结点，然后遍历左子树，最后遍历右子树，根->左->右）
  • 
• LDR–中序遍历（根在中，从左往右，首先遍历左子树，然后访问根节点，最后遍历右子树，左->根->右）
  • 
• LRD–后序遍历（根在后，从左往右，首先遍历左子树，然后遍历右子树，最后访问根节点，左->右->根）
  • 
• 层序遍历（除此之外，还有一种层序遍历，层序遍历嘛，就是按层，从上到下，从左到右遍历，这个没啥好说的）
  • 

所以前中后序遍历的前/中/后，指的是根节点在前/中/后输出的意思，因此这三种遍历也称为先根遍历，中根遍历，后根遍历。

本文就不掉书袋再复述前序/中序/后序遍历的教科书方法了。我们这里介绍一种易记的方法。

1 先序遍历

先序遍历可以想象成，小人从树根开始绕着整棵树的外围转一圈，经过结点的顺序就是先序遍历的顺序

先序遍历结果：ABDHIEJCFKG

2 中序遍历

中序遍历可以想象成，按树画好的左右位置投影下来就可以了

中序遍历结果：HDIBEJAFKCG

3 后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。还记得我们先序遍历绕圈的路线么？就是围着树的外围绕一圈，如果发现一剪刀就能剪下的一颗葡萄（注意必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。

后序遍历结果：HIDJEBKFGCA

4 层序遍历

层序遍历太简单了，就是按照一层一层的顺序，从左到右写下来就行了。

后序遍历结果：ABCDEFGHIJK

前言

我们在日常的开发和维护工作中，免不了需要对JAVA程序进行监控、调优以及问题排查。

给一个系统定位问题的时候，知识、经验是关键基础，数据是依据，工具是运用知识处理数据的手段。这里说的数据包括∶运行日志、异常堆栈、GC日志、线程快照（thread dump/java core文件）、堆转储快照（heap dump/hprof文件）等。

经常使用适当的监控和分析工具可以加快我们分析数据、定位解决问题的速度，但在学习工具前，也应当意识到工具永远都是知识技能的一层包装，没有什么工具是”秘密武器”，不可能学会了就能包治百病。

进程id的获取

许多工具或者命令需要用到java进程的进程id，有必要回顾一下。

1. 查看当前运行的所有的java进程：ps -ef|grep java；
2. 准确获取定位到tomcat下正在运行的java进程的PID命令：ps -ef|grep java | grep catalina | awk '{print $2}'
3. 准确定位到tomcat下正在运行的java进程相关信息：ps -ef|grep java | grep catalina.

jinfo/jmap访问受限的解决

一般情况下，我们使用jinfo命令，可能会遇到如下的报错：

这是因为新版的Linux系统加入了 ptrace-scope 机制,该机制的目的是防止用户访问正在执行的进程的内存，但是如jinfo,jmap这些调试类工具本身就是利用ptrace来获取执行进程的内存等信息。

解决：

1. 临时解决，该方法在下次重启前有效：echo 0 | sudo tee /proc/sys/kernel/yama/ptrace_scope
2. 永久解决，直接修改内核参数：sudo vi /etc/sysctl.d/10-ptrace.conf
   • 编辑这行: kernel.yama.ptrace_scope = 1
   • 修改为: kernel.yama.ptrace_scope = 0
   • 重启系统，使修改生效。

参数名：kernel.yama.ptrace_scope（值为１：表示禁止用户访问正在执行的进程的内存；０表示可以访问）

1 jps 显示JVM进程信息

jps (Java Virtual Machine Process Status Tool)，是java提供的一个显示当前所有JAVA进程pid的命令，适合在linux/unix平台上简单察看当前java进程的一些简单情况。

我们常常会用到unix系统里的ps命令，这个命令主要是用来显示当前系统的进程情况，有哪些进程以及进程id。

jps就是java程序版本的ps命令，它的作用是显示当前系统的java进程情况及进程id。

格式：jps [-命令选项]

1.1 jps的选项

jps默认只会打印进程id和java类名，如果要更具体的信息，则要借助更多的选项：

1. jps -q

   • 只显示pid，不显示class名称,jar文件名和传递给main方法的参数
   • 

2. jps -m

   • 输出传递给main方法的参数，在嵌入式jvm上可能是null
   • 

3. jps -l

   • 输出应用程序main class的完整package名或者应用程序的jar文件完整路径名
   • 

4. jps -v

   • 输出传递给JVM的参数
   • 

5. jps -V

   • 隐藏输出传递给JVM的参数

2 jinfo 显示JVM配置信息

jinfo 是 JDK 自带的命令，可以用来查看正在运行的 java 应用程序的扩展参数，包括Java System属性和JVM命令行参数；也可以动态的修改正在运行的JVM一些参数。当系统崩溃时，jinfo也可以从core文件里面知道崩溃的Java应用程序的配置信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Usage:
    jinfo [option] <pid>
        (to connect to running process)
    jinfo [option] <executable <core>
        (to connect to a core file)
    jinfo [option] [server_id@]<remote server IP or hostname>
        (to connect to remote debug server)

where <option> is one of:
    -flag <name>         to print the value of the named VM flag
    -flag [+|-]<name>    to enable or disable the named VM flag
    -flag <name>=<value> to set the named VM flag to the given value
    -flags               to print VM flags
    -sysprops            to print Java system properties
    <no option>          to print both of the above
    -h | -help           to print this help message

格式：jinfo [-命令选项] <pid> 或 jinfo [-命令选项] <executable core> 或 jinfo [-命令选项] [server_id@] <remote ip or hostname>

• pid：对应jvm的进程id
• executable core：产生core dump文件
• remote server IP or hostname：远程调试服务的ip或者hostname
• server-id：唯一id,假如一台主机上多个远程debug服务;

Javacore，也可以称为“threaddump”或是“javadump”，它是 Java 提供的一种诊断特性，能够提供一份可读的当前运行的 JVM 中线程使用情况的快照。即在某个特定时刻，JVM 中有哪些线程在运行，每个线程执行到哪一个类，哪一个方法。
应用程序如果出现不可恢复的错误或是内存泄露，就会自动触发 Javacore 的生成。

jinfo工具特别强大，有众多的可选命令选项，比如：

2.1 输出JVM进程的参数和属性

jinfo <pid>

不带任何选项的情况下，输出当前 jvm 进程的全部参数和系统属性

2.2 打印JVM特定参数的值

jinfo -flag <name> <pid>

用于打印虚拟机标记参数的值，name表示虚拟机标记参数的名称。

2.3 开启或关闭JVM特定参数

jinfo -flag [+|-]<name> <pid>

用于开启或关闭虚拟机标记参数。+表示开启，-表示关闭。

2.4 设置JVM特定参数的值

jinfo -flag <name>=<value> <pid>

用于设置虚拟机标记参数，但并不是每个参数都可以被动态修改的。

2.5 打印所有JVM参数

jinfo -flags <pid>

打印虚拟机参数。什么是虚拟机参数呢？如-XX:NewSize,-XX:OldSize等就是虚拟机参数。

2.6 打印所有系统参数

jinfo -sysprops <pid>

打印所有系统参数

3 jmap 生成内存快照文件

jmap命令是一个可以输出所有内存中对象的工具，甚至可以将VM 中的heap，以二进制输出成文本。打印出某个java进程（使用pid）内存内的，所有‘对象’的情况（如：产生那些对象，及其数量）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Usage:
    jmap [option] <pid>
        (to connect to running process)
    jmap [option] <executable <core>
        (to connect to a core file)
    jmap [option] [server_id@]<remote server IP or hostname>
        (to connect to remote debug server)

where <option> is one of:
    <none>               to print same info as Solaris pmap
    -heap                to print java heap summary
    -histo[:live]        to print histogram of java object heap; if the "live"
                         suboption is specified, only count live objects
    -clstats             to print class loader statistics
    -finalizerinfo       to print information on objects awaiting finalization
    -dump:<dump-options> to dump java heap in hprof binary format
                         dump-options:
                           live         dump only live objects; if not specified,
                                        all objects in the heap are dumped.
                           format=b     binary format
                           file=<file>  dump heap to <file>
                         Example: jmap -dump:live,format=b,file=heap.bin <pid>
    -F                   force. Use with -dump:<dump-options> <pid> or -histo
                         to force a heap dump or histogram when <pid> does not
                         respond. The "live" suboption is not supported
                         in this mode.
    -h | -help           to print this help message
    -J<flag>             to pass <flag> directly to the runtime system

64位机上使用需要使用如下方式：jmap -J-d64 -heap pid

格式：jmap [option] <pid> 或 jmap [option] <executable <core> 或 jmap [option] [server_id@]<remote server IP or hostname>

• pid：对应jvm的进程id
• executable core：产生core dump文件
• remote server IP or hostname：远程调试服务的ip或者hostname
• server-id：唯一id,假如一台主机上多个远程debug服务;

jinfo工具特别强大，有众多的可选命令选项，比如：

3.1 输出hprof二进制格式的heap文件

jmap -dump:live,format=b,file=myjmapfile.txt <pid>
或
jmap -dump:file=myjmapfile.hprof,format=b <pid>

使用hprof二进制形式,输出jvm的heap内容到文件，file=可以指定文件存放的目录。live子选项是可选的，假如指定live选项，那么只输出活的对象到文件。

3.2 打印正等候回收的对象的信息

jmap -finalizerinfo <pid>

打印正等候回收的对象的信息。

Number of objects pending for finalization: 0 表示等候回收的对象为0个

3.3 打印heap的概要信息

jmap -heap <pid>

打印heap的概要信息，GC使用的算法，heap（堆）的配置及JVM堆内存的使用情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Attaching to process ID 2805, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 25.181-b13

using thread-local object allocation.
Parallel GC with 4 thread(s)   ##GC 方式

Heap Configuration:  ##堆配置情况，也就是JVM参数配置的结果[平常说的tomcat配置JVM参数，就是在配置这些]
   MinHeapFreeRatio         = 0  ##最小堆使用比例
   MaxHeapFreeRatio         = 100  ##最大堆可用比例
   MaxHeapSize              = 734003200 (700.0MB)  ##最大堆空间大小
   NewSize                  = 21495808 (20.5MB)  ##新生代分配大小
   MaxNewSize               = 244318208 (233.0MB)  ##最大可新生代分配大小
   OldSize                  = 43515904 (41.5MB)  ##老年代大小
   NewRatio                 = 2  ##新生代比例
   SurvivorRatio            = 8  ##新生代与suvivor的比例
   MetaspaceSize            = 21807104 (20.796875MB)  ## 元数据空间大小
   CompressedClassSpaceSize = 1073741824 (1024.0MB)  ## 压缩空间大小
   MaxMetaspaceSize         = 17592186044415 MB  ## 最大元数据空间大小
   G1HeapRegionSize         = 0 (0.0MB)  ## G1的对region空间大小

Heap Usage:  ##堆使用情况【堆内存实际的使用情况】
PS Young Generation  ##新生代（伊甸区Eden区 + 幸存区survior(1+2)空间）
Eden Space:   ##伊甸区
   capacity = 32505856 (31.0MB)
   used     = 0 (0.0MB)
   free     = 32505856 (31.0MB)
   0.0% used
From Space:  ##survior1区
   capacity = 2621440 (2.5MB)
   used     = 0 (0.0MB)
   free     = 2621440 (2.5MB)
   0.0% used
To Space:  ##survior2 区
   capacity = 4194304 (4.0MB)
   used     = 0 (0.0MB)
   free     = 4194304 (4.0MB)
   0.0% used
PS Old Generation  ##老年代使用情况
   capacity = 21495808 (20.5MB)
   used     = 3738528 (3.565338134765625MB)
   free     = 17757280 (16.934661865234375MB)
   17.391893340320124% used

4524 interned Strings occupying 360168 bytes.

3.4 打印每个class的实例信息

jmap -histo:live <pid>
或
jmap -histo: <pid>

打印每个class的实例数目，内存占用,类全名信息，VM的内部类名字开头会加上前缀”*”。如果live子参数加上后，只统计活的对象数量

采用jmap -histo pid>a.log日志将其保存，在一段时间后，使用文本对比工具，可以对比出GC回收了哪些对象。

jmap -dump:format=b,file=outfile 3024可以将3024进程的内存heap输出出来到outfile文件里，再配合MAT（内存分析工具）。

3.5 打印类加载器的数据

jmap -clstats <pid>

-clstats是-permstat的替代方案，在JDK8之前，-permstat用来打印类加载器的数据。打印Java堆内存的永久保存区域的类加载器的智能统计信息。

对于每个类加载器而言，它的名称、活跃度、地址、父类加载器、它所加载的类的数量和大小都会被打印。此外，包含的字符串数量和大小也会被打印。

3.6 指定传递给运行jmap的JVM的参数

jmap -J<flag> <pid>

指定传递给运行jmap的JVM的参数

如jmap -J-d64 -heap pid表示在64位机上使用jmap -heap

4 jstack 输出线程堆栈快照

jstack用于打印出给定的java进程ID或core file或远程调试服务的Java堆栈信息（也就是线程），如果是在64位机器上，需要指定选项”-J-d64”，Windows的jstack使用方式只支持以下的这种方式：jstack [-l] pid

如果java程序崩溃生成core文件，jstack工具可以用来获得core文件的java stack和native stack的信息，从而可以轻松地知道java程序是如何崩溃和在程序何处发生问题。

另外，jstack工具还可以附属到正在运行的java程序中，看到当时运行的java程序的java stack和native stack的信息，如果现在运行的java程序呈现hung的状态，jstack是非常有用的。

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

Usage:
    jstack [-l] <pid>
        (to connect to running process)
    jstack -F [-m] [-l] <pid>
        (to connect to a hung process)
    jstack [-m] [-l] <executable> <core>
        (to connect to a core file)
    jstack [-m] [-l] [server_id@]<remote server IP or hostname>
        (to connect to a remote debug server)

Options:
    -F  to force a thread dump. Use when jstack <pid> does not respond (process is hung)
    -m  to print both java and native frames (mixed mode)
    -l  long listing. Prints additional information about locks
    -h or -help to print this help message

格式：jstack [option] <pid> 或 jstack [option] <executable <core> 或 jstack [option] [server_id@]<remote server IP or hostname>

• pid：对应jvm的进程id
• executable core：产生core dump文件
• remote server IP or hostname：远程调试服务的ip或者hostname
• server-id：唯一id,假如一台主机上多个远程debug服务;

jstack工具特别强大，有众多的可选命令选项和适用场景，比如：

4.1 程序没有响应时强制打印线程

jstack -F <pid>

当pid对应的程序没有响应时，强制打印线程堆栈信息。

4.2 打印完整的堆栈信息

jstack -l <pid>

长列表，打印关于锁的附加信息，例如属于java.util.concurrent的ownable synchronizers列表。

4.3 打印java/native框架的所有堆栈

jstack -m <pid>

打印java和native c/c++框架的所有栈信息。

4.4 jstack统计线程数

jstack -l 28367 | grep 'java.lang.Thread.State' | wc -l

4.5 jstack检测死锁

我们先写个死锁代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class DeathLock {

    private static Lock lock1 = new ReentrantLock();
    private static Lock lock2 = new ReentrantLock();

    public static void deathLock() {
        Thread t1 = new Thread() {
            @Override
            public void run() {
                try {
                    lock1.lock();
                    TimeUnit.SECONDS.sleep(1);
                    lock2.lock();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        };
        Thread t2 = new Thread() {
            @Override
            public void run() {
                try {
                    lock2.lock();
                    TimeUnit.SECONDS.sleep(1);
                    lock1.lock();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        };

        t1.setName("mythread1");
        t2.setName("mythread2");
        t1.start();
        t2.start();
    }

    public static void main(String[] args) {
        deathLock();
    }
}

这个死锁会输出如下日志

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

"mythread2" #12 prio=5 os_prio=0 tid=0x0000000058ef7800 nid=0x1ab4 waiting on condition [0x0000000059f8f000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000000d602d610> (a java.util.concurrent.lock
s.ReentrantLock$NonfairSync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInt
errupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(A
bstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Abstrac
tQueuedSynchronizer.java:1199)
        at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLo
ck.java:209)
        at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:285)

        at DeathLock$2.run(DeathLock.java:34)

   Locked ownable synchronizers:
        - <0x00000000d602d640> (a java.util.concurrent.locks.ReentrantLock$Nonfa
irSync)

"mythread1" #11 prio=5 os_prio=0 tid=0x0000000058ef7000 nid=0x3e68 waiting on condition [0x000000005947f000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000000d602d640> (a java.util.concurrent.lock
s.ReentrantLock$NonfairSync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInt
errupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(A
bstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Abstrac
tQueuedSynchronizer.java:1199)
        at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLo
ck.java:209)
        at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:285)

        at DeathLock$1.run(DeathLock.java:22)

   Locked ownable synchronizers:
        - <0x00000000d602d610> (a java.util.concurrent.locks.ReentrantLock$Nonfa
irSync)


Found one Java-level deadlock:
=============================
"mythread2":
  waiting for ownable synchronizer 0x00000000d602d610, (a java.util.concurrent.l
ocks.ReentrantLock$NonfairSync),
  which is held by "mythread1"
"mythread1":
  waiting for ownable synchronizer 0x00000000d602d640, (a java.util.concurrent.l
ocks.ReentrantLock$NonfairSync),
  which is held by "mythread2"

Java stack information for the threads listed above:
===================================================
"mythread2":
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000000d602d610> (a java.util.concurrent.lock
s.ReentrantLock$NonfairSync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInt
errupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(A
bstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Abstrac
tQueuedSynchronizer.java:1199)
        at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLo
ck.java:209)
        at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:285)

        at DeathLock$2.run(DeathLock.java:34)
"mythread1":
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000000d602d640> (a java.util.concurrent.lock
s.ReentrantLock$NonfairSync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInt
errupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(A
bstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Abstrac
tQueuedSynchronizer.java:1199)
        at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLo
ck.java:209)
        at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:285)

        at DeathLock$1.run(DeathLock.java:22)

Found 1 deadlock.

4.6 jstack检测cpu高

步骤一：查看cpu占用高进程

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

> top

Mem:  16333644k total,  9472968k used,  6860676k free,   165616k buffers
Swap:        0k total,        0k used,        0k free,  6665292k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
17850 root      20   0 7588m 112m  11m S 100.7  0.7  47:53.80 java
 1552 root      20   0  121m  13m 8524 S  0.7  0.1  14:37.75 AliYunDun
 3581 root      20   0 9750m 2.0g  13m S  0.7 12.9 298:30.20 java
    1 root      20   0 19360 1612 1308 S  0.0  0.0   0:00.81 init
    2 root      20   0     0    0    0 S  0.0  0.0   0:00.00 kthreadd
    3 root      RT   0     0    0    0 S  0.0  0.0   0:00.14 migration/0

步骤二：查看cpu占用高线程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

> top -H -p 17850

top - 17:43:15 up 5 days,  7:31,  1 user,  load average: 0.99, 0.97, 0.91
Tasks:  32 total,   1 running,  31 sleeping,   0 stopped,   0 zombie
Cpu(s):  3.7%us,  8.9%sy,  0.0%ni, 87.4%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:  16333644k total,  9592504k used,  6741140k free,   165700k buffers
Swap:        0k total,        0k used,        0k free,  6781620k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
17880 root      20   0 7588m 112m  11m R 99.9  0.7  50:47.43 java
17856 root      20   0 7588m 112m  11m S  0.3  0.7   0:02.08 java
17850 root      20   0 7588m 112m  11m S  0.0  0.7   0:00.00 java
17851 root      20   0 7588m 112m  11m S  0.0  0.7   0:00.23 java
17852 root      20   0 7588m 112m  11m S  0.0  0.7   0:02.09 java
17853 root      20   0 7588m 112m  11m S  0.0  0.7   0:02.12 java
17854 root      20   0 7588m 112m  11m S  0.0  0.7   0:02.07 java

步骤三：转换线程ID

1
2

> printf "%x\n" 17880
45d8

步骤四：定位cpu占用线程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

jstack 17850|grep 45d8 -A 30
"pool-1-thread-11" #20 prio=5 os_prio=0 tid=0x00007fc860352800 nid=0x45d8 runnable [0x00007fc8417d2000]
   java.lang.Thread.State: RUNNABLE
        at java.io.FileOutputStream.writeBytes(Native Method)
        at java.io.FileOutputStream.write(FileOutputStream.java:326)
        at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
        at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
        - locked <0x00000006c6c2e708> (a java.io.BufferedOutputStream)
        at java.io.PrintStream.write(PrintStream.java:482)
        - locked <0x00000006c6c10178> (a java.io.PrintStream)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        - locked <0x00000006c6c26620> (a java.io.OutputStreamWriter)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        - eliminated <0x00000006c6c10178> (a java.io.PrintStream)
        at java.io.PrintStream.print(PrintStream.java:597)
        at java.io.PrintStream.println(PrintStream.java:736)
        - locked <0x00000006c6c10178> (a java.io.PrintStream)
        at com.demo.guava.HardTask.call(HardTask.java:18)
        at com.demo.guava.HardTask.call(HardTask.java:9)
        at java.util.concurrent.FutureTask.run(FutureTask.java:266)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
        at java.lang.Thread.run(Thread.java:745)

"pool-1-thread-10" #19 prio=5 os_prio=0 tid=0x00007fc860345000 nid=0x45d7 waiting on condition [0x00007fc8418d3000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000006c6c14178> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)

5 jstat 收集JVM运行数据

Jstat是JDK自带的一个轻量级小工具。全称“Java Virtual Machine statistics monitoring tool”，它位于java的bin目录下，主要利用JVM内建的指令对Java应用程序的资源和性能进行实时的命令行的监控，包括了堆内存各部分的使用量，以及加载类的数量，还有垃圾回收状况的监控。

可见，Jstat是轻量级的、专门针对JVM的工具。

格式：jstat [-命令选项] <pid>

jstat工具特别强大，有众多的可选项，详细查看堆内各个部分的使用量，以及加载类的数量。使用时，需加上查看进程的进程id，和所选参数。参考格式如下：

5.1 类加载统计

jstat –class <pid>

显示加载class的数量，及所占空间等信息。

5.2 编译统计

jstat -compiler <pid>

显示VM实时编译的数量等信息。

5.3 垃圾回收统计

jstat -gc <pid>

显示gc的信息，查看gc的次数，及时间。

5.4 堆内存统计

jstat -gccapacity <pid>

显示VM内存中三代（young，old，perm）对象的使用和占用大小

5.5 新生代垃圾回收统计

jstat -gcnew <pid>

统计年轻代对象的信息

5.6 新生代内存统计

jstat -gcnewcapacity <pid>

统计年轻代对象的信息及其占用量。

5.7 老年代垃圾回收统计

jstat -gcold <pid>

统计老年代对象的信息

5.8 老年代内存统计

jstat -gcoldcapacity <pid>

统计老年代对象的信息及其占用量

5.9 元数据空间统计

jstat -gcmetacapacity <pid>

统计元数据空间容量

5.10 总结垃圾回收统计

jstat -gcutil <pid>

统计gc容量占比信息

5.11 JVM编译方法统计

jstat -printcompilation <pid>

统计 JVM编译方法的信息

6 jhat 堆快照文件可视化工具

jhat（Java Virtual Machine Heap Analysis Tool）虚拟机堆转储快照分析工具，也是jdk内置的工具之一，是个用来分析java堆内存的命令，它会建立一个HTTP/HTML服务器，让用户可以在浏览器上查看分析结果，包括对象的数量，大小等等，并支持对象查询语言（OQL）。

jhat的作用对象是堆快照文件，也就是dump文件或者hprof文件，文件生成后，我们再使用jaht进行分析。

1. 使用jmap命令获取java程序堆快照（生成dump文件）

2. 使用jconsole选项通过HotSpotDiagnosticMXBean从运行时获得堆快照（生成dump文件）

3. 虚拟机启动时如果指定了-XX:+HeapDumpOnOutOfMemoryError选项, 则在抛出OutOfMemoryError时, 会自动执行堆快照（生成dump文件）

4. 使用 hprof 命令获得hprof文件（生成hprof文件）

用法：jhat [ options ] heap-dump-file，如jhat -J-Xmx512M app.dump

option具体选项及作用如下：

1. -J< flag > 因为 jhat 命令实际上会启动一个JVM来执行, 通过 -J 可以在启动JVM时传入一些启动参数. 例如, -J-Xmx512m 则指定运行 jhat 的Java虚拟机使用的最大堆内存为 512 MB. 如果需要使用多个JVM启动参数,则传入多个 -Jxxxxxx
2. -stack false|true 关闭跟踪对象分配调用堆栈。如果分配位置信息在堆转储中不可用. 则必须将此标志设置为 false. 默认值为 true.
3. -refs false|true 关闭对象引用跟踪。默认情况下, 返回的指针是指向其他特定对象的对象,如反向链接或输入引用(referrers or incoming references), 会统计/计算堆中的所有对象。
4. -port port-number 设置 jhat HTTP server 的端口号. 默认值 7000。
5. -exclude exclude-file 指定对象查询时需要排除的数据成员列表文件。 例如, 如果文件列出了 java.lang.String.value , 那么当从某个特定对象 Object o 计算可达的对象列表时, 引用路径涉及 java.lang.String.value 的都会被排除。
6. -baseline exclude-file 指定一个基准堆转储(baseline heap dump)。 在两个 heap dumps 中有相同 object ID 的对象会被标记为不是新的(marked as not being new). 其他对象被标记为新的(new). 在比较两个不同的堆转储时很有用。
7. -debug int 设置 debug 级别. 0 表示不输出调试信息。 值越大则表示输出更详细的 debug 信息。
8. -version 启动后只显示版本信息就退出。

有时dump出来的堆很大，在启动时会报堆空间不足的错误，可加参数：jhat -J-Xmx512m <heap dump file>。这个内存大小可根据自己电脑进行设置。

不过实事求是地说，在实际工作中，除非真的没有别的工具可用，否则一般不会去直接使用jhat命令来分析demp文件，主要原因有二：

• 一是一般不会在部署应用程序的服务器上直接分析dump文件，即使可以这样做，也会尽量将dump文件拷贝到其他机器上进行分析，因为分析工作是一个耗时且消耗硬件资源的过程，既然都要在其他机器上进行，就没必要受到命令行工具的限制了；
• 另外一个原因是jhat的分析功能相对来说很简陋，VisualVM以及专门分析dump文件的Eclipse Memory Analyzer、IBM HeapAnalyzer等工具，都能实现比jhat更强大更专业的分析功能。

6.1 jhat工具的开启

1. 使用jps获取java应用的pid

1
2
3
4

$ jps
> 17904 -- process information unavailable
> 40836 Jps
> 43228 -- process information unavailable

2. 使用jmap获取dump文件

   1 2 3

   $ jmap -dump:file=test.dump,format=b 43228 > Dumping heap to D:\projects\i-lupro-app\test.dump ... > Heap dump file created

3. 使用jhat分析dump文件

   1 2 3 4 5 6 7 8 9 10

   $ jhat -J-Xmx512M test.dump > Reading from test.dump... > Dump file created Wed Nov 25 18:48:51 CST 2020 > Snapshot read, resolving... > Resolving 197329 objects... > Chasing references, expect 39 dots....................................... > Eliminating duplicate references....................................... > Snapshot resolved. > Started HTTP server on port 7000 > Server is ready.

4. 在浏览器打开http://localhost:7000/开启可视化工具

6.2 jhat工具的功能

6.2.1 显示出堆中所包含的所有的类

6.2.2 从根集能引用到的对象

6.2.3 显示平台包括的所有类的实例数量

6.2.4 堆实例的分布表

6.2.5 执行对象查询语句（OQL）

其输入内容如：

1
2

# 查询长度大于100的字符串
select s from java.lang.String s where s.count > 100

详细的OQL可点击上图的“OQL help”

7 jconsole 可视化监控控制台

Jconsole（Java Monitoring and Management Console），一种基于JMX的可视化监视、管理工具。

7.1 启动JConsole

• 点击JDK/bin 目录下面的jconsole.exe 即可启动
• 然后会自动自动搜索本机运行的所有虚拟机进程。
• 选择其中一个进程可开始进行监控

7.2 JConsole介绍

JConsole 基本包括以下基本功能：概述、内存、线程、类、VM概要、MBean

7.2.1 概览

7.2.2 内存监控

内存页签相对于可视化的jstat 命令，用于监视受收集器管理的虚拟机内存。

jconsole可监控的内存有许多，如下图

我们以堆内存为例：

除了方法区，Java虚拟机可能需要进行内部处理或优化，这也属于非堆内存的内存。 例如，实时（JIT）编译器需要内存用于存储从Java虚拟机的高性能的代码翻译的机器码。

7.2.3 线程监控

如果上面的“内存”页签相当于可视化的jstat命令的话，“线程”页签的功能相当于可视化的jstack命令，遇到线程停顿时可以使用这个页签进行监控分析。

在左下角的“线程”列表列出了所有的活动线程。 如果你输入一个“filter”字段中的字符串，线程列表将只显示其名称中包含你输入字符串线程。 点击一个线程在线程列表的名称，显示该线程的信息的权利，包括线程的名称，状态、阻塞和等待的次数、堆栈跟踪。

如果要检查您的应用程序已经陷入死锁的线程，可以通过点击“检测死锁”按钮检测。线程长时间停顿的主要原因主要有：等待外部资源（数据库连接、网络资源、设备资源等）、死循环、锁等待（活锁和死锁）

我们写个死锁代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

package com.jvm;
/**
 * 线程死锁验证
 */
public class JConsoleThreadLock {
    /**
     * 线程死锁等待演示
     */
    static class SynAddRunalbe implements Runnable {
        int a, b;
        public SynAddRunalbe(int a, int b) {
            this.a = a;
            this.b = b;
        }
        @Override
        public void run() {
            synchronized (Integer.valueOf(a)) {
                synchronized (Integer.valueOf(b)) {
                    System.out.println(a + b);
                }
            }
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            new Thread(new SynAddRunalbe(1, 2)).start();
            new Thread(new SynAddRunalbe(2, 1)).start();
        }
    }
}

这段代码开了200个线程去分别计算1+2以及2+1的值，其实for循环是可省略的，两个线程也可能会导致死锁，不过那样概率太小，需要尝试运行很多次才能看到效果。一般的话，带for循环的版本最多运行2～3次就会遇到线程死锁，程序无法结束。

造成死锁的原因是Integer.valueOf（）方法基于减少对象创建次数和节省内存的考虑，[-128，127]之间的数字会被缓存，当valueOf（）方法传入参数在这个范围之内，将直接返回缓存中的对象。也就是说，代码中调用了200次Integer.valueOf（）方法一共就只返回了两个不同的对象。假如在某个线程的两个synchronized块之间发生了一次线程切换，那就会出现线程A等着被线程B持有的Integer.valueOf（1），线程B又等着被线程A持有的Integer.valueOf（2），结果出现大家都
跑不下去的情景。

如果检测到任何死锁的线程，这些都显示在一个新的标签，旁边出现的“死锁”标签， 在图所示。

结果描述：显示了线程Thread-53在等待一个被线程Thread-66持有Integer对象，而点击线程Thread-66则显示它也在等待一个Integer对象，被线程Thread-53持有，这样两个线程就互相卡住，都不存在等到锁释放的希望了

7.2.4 类加载信息监控

类”标签显示关于类加载的信息。

• 红线表示加载的类的总数（包括后来卸载的）
• 蓝线是当前的类加载数

在选项卡底部的详细信息部分显示类的加载，因为Java虚拟机开始的总数，当前加载和卸载的数量。** 跟踪**类加载详细的输出，您可以勾选在顶部的右上角复选框。

7.2.5 VM概要监控

在此选项卡中提供的信息包括以下内容。

• 摘要
  • 运行时间 ：开始以来，Java虚拟机的时间总额。
  • 进程的CPU时间 ：Java VM的开始，因为它消耗的CPU时间总量。
  • 编译总时间 ：累计时间花费在JIT编译。
• 主题
  • 活动线程 ：目前现场守护线程，加上非守护线程数量。
  • 峰值 ：活动线程的最高数目，因为Java虚拟机开始。
  • 守护线程 ：当前的活动守护线程数量。
  • 总线程 ：开始自Java虚拟机启动的线程总数，包括非守护进程，守护进程和终止的线程。
• 类
  • 当前类装载 ：目前加载到内存中的类数目。
  • 总类加载 ：从Java VM开始加载到内存中的类总和，包括那些后来被卸载的类。
  • 已卸载类总数 ：从Java虚拟机开始从内存中卸载的类的数目。
• 内存
  • 当前的堆大小 ：目前所占用的堆的千字节数。
  • 分配的内存 ：堆分配的内存总量。
  • 最大堆最大值 ：堆所占用的千字节的最大数目。
  • 待最后确定的对象：待最后确定的对象的数量。
  • 花在执行GC的垃圾收集器 ：包括垃圾收集，垃圾收集器的名称，进行藏品的数量和总时间的信息。
• 操作系统
  • 总物理内存
  • 空闲物理内存
  • 分配的虚拟内存
  • 其他信息
• VM参数 ：输入参数的应用程序通过Java虚拟机，不包括的主要方法的参数。
  • 类路径是由系统类加载器用于搜索类文件的类路径。
  • 库路径 ：加载库时要搜索的路径列表。
  • 引导类路径 ：引导类路径是由引导类加载器用于搜索类文件。

8 jvisualvm

jvisualvm是Netbeans的profile子项目，从JDK6.0 update 7 版本开始自带。jvisualvm同jconsole一样，都是一个基于图形化界面的、可以查看本地及远程的JAVA GUI监控工具，jvisualvm是一个综合性的分析工具，其整合了jstack、jmap、jinfo等众多调试工具的功能，可以认为jvisualvm是jconsole的升级版。

8.1 启动jvisualvm

在JDK_HOME/bin下双击jvisualvm.exe，或者直接在命令行中输入jvisualvm 都可

我们可以看到侧边框：

• 本地：如果你本地有java进程启动了，那么在本地这个栏目就会显示。
• 远程：监控的远程主机
• 快照：装载dump文件或者hprof文件，进行分析

由于本地和远程展示的监控界面都是相同的，接下来我们直接介绍远程。

8.2 添加远程监控

注意，一个主机如果希望支持远程监控，需要在启动时添加以下参数：

1
2
3
4

-Dcom.sun.management.jmxremote.port=1099
-Dcom.sun.management.jmxremote.authenticate=false
-Dcom.sun.management.jmxremote.ssl=false

右击”远程”–>”添加远程主机”，出现界面：

在连接后面添加一个1099，这是远程主机jmx监听的端口号，点击确定，侧边栏变为：

点击红色框中的jmx连接，出现以下界面：

8.3 jvisualvm介绍

jvisualvm分为四个选项卡：概述、监视、线程、抽样器，下面我们一一介绍：

8.3.1 概述页

默认显示的就是概述选项卡，其中的信息相当于我们调用了jinfo命令获得，其还包含了两个子选项卡：

• jvm参数栏：相当于我们调用jinfo -flags <pid>获得
• 系统属性栏：相当于我们调用jinfo -sysprops <pid>获得

8.3.2 监视页

主要显示了cpu、内存使用、类加载信息、线程信息等，这只是一个概要性的介绍，如下图：

点击右上角的”堆dump”会在远程主机上，dump一个内存映射文件，之所以不直接dump到本地，主要是因为这个文件通常比较大，直接dump到本地会很慢。

dump完成之后，可以手工下载这个文件，通过”文件”->”装入”来进行分析。

8.3.3 线程页

线程选项卡列出了所有线程的信息，并使用了不同的颜色标记，右下角的颜色表示了不同的状态。

右上角的线程dump会直接把线程信息dump到本地，相当于调用了jstack命令，如：

8.3.4 抽样器页

主要有”cpu”和”内存”两个按钮，功能类似，只不过一个是抽样线程占用cpu的情况，一个是抽样jvm对象内存的情况。

1. 通过设置可以对CPU的采样来源以及内存的刷新时间进行设置；
2. 点击CPU或者Memory即可开始监控，点击Stop则停止采样；

我们以分析cpu波动为例，看下如何使用cpu采样器：

8.3.4.1 分析CPU波动问题

进入抽样器页（Sampler），在CPU波动的时候点击CPU对CPU进行抽样。

注意线上环境千万不要使用Sampler右边的Profiler

抽样进行一段时间后(建议3分钟左右就行了,时间越长生成的snapshot越大)，点击”stop”，然后点击”snapshot”生成快照

生成快照后按照”Total Time(CPU)”排序，找到那些线程最耗费CPU，从下图中我们看到基本上都是DubboServerHandler，熟悉Dubbo框架的知道这都是我们的业务线程。

那么我们对这些线程进行分析(多分析几个线程，双击指定线程就可以看这个线程的调用栈以及耗时情况)，看看这些线程在哪里比较耗费CPU。

通过分析发现，在Dubbo远程调用的时候验证参数的时间比我们处理业务的时间都长(见下图红色方框框起来的方法)。结合Dubbo官方文档得知，Dubbo的参数验证这个特性是比较耗费性能的，而我们的接口参数使用了javax.validation注解来验证参数。所以我们在调用的时候使用validation=”false”禁止使用参数验证这个特性就好了CPU就回归正常了。

除此之外，我们也可以动态的观察线程的变化，功能有点类似JProfiler的“Mark Current Values”。我们点击线程CPU时间这个tab。查看每个线程占用cpu时间的增量数据。

8.3.4.2 内存采样

和cpu采样一样的，样进行一段时间后(建议3分钟左右就行了,时间越长生成的snapshot越大)，点击”stop”，然后点击”snapshot”生成快照

点击增量同样可以监控内存的变动情况：

点击“执行GC”，则可以手动触发GC；
点击“堆Dump”，则可以手动触发dump文件生成；

1 堆和树的区别

堆是一类特殊的树，就类似一堆东西一样（金字塔结构），按照由大到小（或由小到大）“堆”起来。

其中容易混淆的是二叉堆和二叉树。

二叉堆的特点是双亲结点的值必然小于等于（最小堆）或者大于等于（最大堆）子结点的值，而两个子结点的关键字没有次序规定。

而二叉树中，每个双亲结点的值均大于左子树结点的值，均小于右子树结点的值，也就是说，每个双亲结点的左右子结点的值有次序关系。

从上面各自的结构上的分析可得：二叉树是用来做查找的，而二叉堆是用来做排序的。

2 优先级队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。而在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。

优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现，因为和其他线性结构相比，用堆实现优先级队列的性能最优：

一般在优先队列里面说“堆”这个词，指的都是二叉堆这种数据结构实现。

可以看到，使用堆来实现优先级队列，它的入队和出队操作性能都比较优秀且平衡。

由于二叉堆具有很明显的规律，所以我们可以用一个数组而不需要用链表来表示。我们设计一个数组来表示上图的“二叉堆”。

根据二叉堆的性质，我们可以得到这样的数组来表示一个堆：数组第0位放弃，从第一位开始放入堆的元素。我们看到，在堆中描述的父子结构（颜色标记），在数组中依然得以保留，不过保留的方式变成了：第i个位置上的元素，他的左子结点总是在第2i位置上，右子结点在2i+1的位置上。

2.1 入队操作(add)

就像为了保证二叉树的查询效率，我们要时刻维持二叉树的平衡一样。我们每次对堆进行插入操作，都需要保证满足堆的堆序特性。所以很多时候我们在插入之后，不得不调整整个堆的顺序来维持堆的数据结构。

这个在插入时能保证堆继续“平衡”的操作叫做上滤（Sift up），下面以一个最小堆为例：

1. 为将一个元素X插入到堆中，我们在下一个可用位置（前序遍历找下一个可用结点）创建一个空穴。
2. 如果X可以放在该空穴中而不破坏堆的序（父结点小于等于子结点），那么可以插入完成。否则，将空穴和父结点交换位置。这个操作叫做上滤。

3. 以此类推，直到空穴无法再上滤为止（此时的父结点已经小于等于插入的值），插入完成。
   

这个操作我们可以通过递归来实现，平均的时间复杂度是O(logn)。

2.2 出队操作(poll)

根据堆序特性，找到最先元素很简单，就是堆的根节点，但是删除它却不容易，删除根节点，必然会破坏树的结构。所以在删除时，我们也要特定操作，来保证堆序继续正确。

这个在删除时能保证堆继续“平衡”的操作叫做下滤（Sift down），下面还是以一个最小堆为例：

1. 删除一个元素，我们可以很快找到，根节点元素就是最小的元素。此时根节点变成了空穴。删掉了一个结点，肯定要找一个结点补回来，为了维持完全二叉的特性，我们找堆的最后一个结点（前序遍历）赋值给空穴。也就是下图中标红的31。
   
2. 此时，31成为了根结点是不满足堆序的，所以肯定需要在左右结点中找一个子结点来和根结点做交互，选择哪个呢？根据堆序，肯定选择子结点中较小的那个结点，和空穴交换位置。
   
3. 重复上述操作，直到空穴下沉到最底层为止。下滤操作完成。
   

这个操作我们可以通过递归来实现，平均的时间复杂度是O(logn)。

2.3 构建堆(heapify)

将一个任意数组整理成堆，这个操作叫做heapify，构建一个n个元素的最大/最小堆，我们直接执行n次insert方法即可， 因为在设计insert方法时，就已将考虑到将插入到值放到堆的合适位置。输入n项，即可自动生成n大小的堆。此时算法的时间复杂度是O(nlogn)。

2.4 替换堆中堆顶元素(replace)

用一个新的元素，替换堆中优先级最高的元素，可以直接用新元素覆盖堆顶元素，然后执行一次sift down操作即可，时间复杂度为O(logn)。

3 JAVA中PriorityQueue实现

PriorityQueue在jdk的java.util包下，其本质是一个Object数组，也就是我们前文提到的，使用数组来存放堆的模式：

1
2
3
4
5
6
7
8
9

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

3.1 构造方法

优先级队列，java的实现默认是小顶堆的实现，默认调用Object的compareTo方法。

1

PriorityQueue queue = new PriorityQueue();

我们可以使用它的另一个构造方法，手动传入指定的comparator：

1
2
3
4
5
6
7

Comparator comparator = new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
		...
	}
};
PriorityQueue queue = new PriorityQueue(capacity,comparator);

3.2 添加元素

add()和offer()都是用来做入队操作的方法，add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同。

add()在插入失败时抛出异常，offer()则会返回false。对于PriorityQueue，这两个方法其实没什么差别。新加入的元素可能会破坏堆的堆序性质，因此需要进行必要的调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public boolean offer(E var1) {
	if (var1 == null) {//不允许放入null元素
		throw new NullPointerException();
	} else {
		++this.modCount;
		int var2 = this.size;
		if (var2 >= this.queue.length) {
			this.grow(var2 + 1);//自动扩容
		}

		this.size = var2 + 1;
		if (var2 == 0) {//队列原来为空，这是插入的第一个元素
			this.queue[0] = var1;
		} else {
			this.siftUp(var2, var1);//调整
		}

		return true;
	}
}

上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法用于插入元素x并维持堆的特性。

1
2
3
4
5
6
7
8

private void siftUp(int var1, E var2) {
	if (this.comparator != null) {
		this.siftUpUsingComparator(var1, var2);// 元素类型是无法直接比较，要借用比较器的场景
	} else {
		this.siftUpComparable(var1, var2);// 元素类型是可以直接比较，不需要借用比较器的场景
	}

}

这两者代码大同小异，我们看其中一个：

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

private void siftUpUsingComparator(int var1, E var2) {// var1是size
	while(true) {
		if (var1 > 0) {
			int var3 = var1 - 1 >>> 1;// val3是parent的下标，parentNo = (nodeNo-1)/2
			Object var4 = this.queue[var3]; // val4是parent元素
			if (this.comparator.compare(var2, var4) < 0) {
				this.queue[var1] = var4;// 如果var2优先级较高，和parent交换下标
				var1 = var3;
				continue;
			}
		}
		this.queue[var1] = var2;// 交换完下标，最后赋值，var2赋值到它应该去的地方。
		return;
	}
}

3.3 获取队首元素

element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值优先级最高的那个元素。

二者唯一的区别是当方法失败时element()抛出异常，peek()返回null。

由于堆用数组表示，根据下标关系，0下标处的那个元素就是堆顶元素。所以直接返回数组0下标处的那个元素即可。

1
2
3

public E peek() {
	return (size == 0) ? null : (E) queue[0];
}

3.4 删除队首元素

remove()和poll()的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时remove()抛出异常，poll()返回null。由于删除操作会改变队列的结构，为维护堆的堆序性质，需要进行必要的调整。

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

public E poll() {
	if (size == 0)
		return null;
	int s = --size;//size减小
	modCount++;
	E result = (E) queue[0];//0下标处的那个元素就是堆顶元素
	E x = (E) queue[s];
	queue[s] = null;
	if (s != 0)
		siftDown(0, x);//调整
	return result;
}

上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）

重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。

1
2
3
4
5
6

private void siftDown(int k, E x) {
	if (comparator != null)
		siftDownUsingComparator(k, x);// 元素类型是无法直接比较，要借用比较器的场景
	else
		siftDownComparable(k, x);// 元素类型是可以直接比较，不需要借用比较器的场景
}

这两者代码大同小异，我们看其中一个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

private void siftDownUsingComparator(int k, E x) {
	int half = size >>> 1;
	while (k < half) {
		// 首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
		int child = (k << 1) + 1;//leftNo = parentNo*2+1
		Object c = queue[child];
		int right = child + 1;
		if (right < size &&
			comparator.compare((E) c, (E) queue[right]) > 0)
			c = queue[child = right];
		if (comparator.compare(x, (E) c) <= 0)
			break;// 如果parent已经比子结点小了，跳出循环
		queue[k] = c;// 否则，用较小的子结点替换parent，继续循环
		k = child;
	}
	queue[k] = x;最后将x赋值在他适合的位置
}

3.5 删除特定元素

remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。

具体来说，remove(Object o)可以分为2种情况：

1. 删除的是最后一个元素。直接删除即可，不需要调整。
2. 2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。

1
2
3
4
5
6
7
8
9

public boolean remove(Object o) {
	int i = indexOf(o); //通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
	if (i == -1)
		return false;// 找不到下标，就返回
	else {
		removeAt(i);// 调用removeAt
		return true;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

private E removeAt(int i) {
	// assert i >= 0 && i < size;
	modCount++;
	int s = --size;
	if (s == i) // removed last element
		queue[i] = null;// //情况1，也就是要删的地方是堆的最后一个，则直接删除
	else {
		E moved = (E) queue[s];// 将堆最后一个元素赋给moved
		queue[s] = null;
		siftDown(i, moved);// 情况2，则用moved来替换被删除的位置，接着执行siftDown方法，
		if (queue[i] == moved) {// 如果调用完siftDown，但moved还在原位没有下沉，那么可能说明moved应该上滤
			siftUp(i, moved);// 调用siftUp，尝试让moved上滤
			if (queue[i] != moved)// moved终于不在原地了
				return moved;
		}
	}
	return null;
}

4 应用

4.1 在n个元素中找到前k项

维护一个size=k的优先级队列，优先级的逻辑为题目中要求的逻辑，如题目要是找出最小的k项，那实现就是值越大的项优先级越高。

遍历一次n个元素，每次遍历中，都将当前元素入队，同时出队一个元素，保证队列的长度为k。

这样一次完整的遍历后，队列中的元素即为结果，时间复杂度为n*(logk+logk)，即O(nlogk)。

不过该题使用不完整快排（即快排到前k项即可，其他的操作都不用做）会更快，可以达到O(n)。

1 分布式事务的概念

事务在分布式计算领域也得到了广泛的应用。在单机数据库中，我们很容易能够实现一套满足ACID特性的事务处理系统，但是在分布式数据库中，数据分散在各台不同的机器上，如何对这些数据进行分布式事务处理具有非常大的挑战。

分布式事务的分布式，是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于分布式系统的不同节点之上。通常一个分布式事务会涉及对多个数据源或业务系统的操作。

一个最典型的分布式事务场景是跨行的转账操作。该操作涉及调用两个异地的银行服务。其中一个是本地银行提供的取款服务，另一个是目标银行提供的存款服务，这两个服务本身是无状态且相互独立的，共同构成了一个完整的分布式事务。取款和存款两个步骤要么都执行，要么都不执行。否则，如果从本地银行取款成功，但是因为某种原因存款服务失败了，那么必须回滚到取款之前的状态，否则就会导致数据不一致。

从上面的例子可以看出，一个分布式事务可以看作是由多个分布式操作序列组成的，例如上面例子中的取款服务和存款服务，通常可以把这一系列分布式的操作序列称为子事务。由于分布式事务中，各个子事务的执行是分布式的，因此要实现一种能够保证ACID特性的分布式事务处理系统就显得格外复杂。

分布式事务=分布式+事务，这是分布式事务本身最直观，也最重要的标签。我们要想理解分布式事务的理论基础，就要首先从这两个角度来解读：

1.1 分布式事务是个事务

首先，分布式事务是个事务，既然是事务，那么我们会希望它能够满足传统事务的ACID四个特性：

1.1.1 传统事务要拥有ACID特性

• Atomic（原子性）

  • 事务的原子性是指事务必须是一个原子的操作序列单元。事务中包含的各项操作在一次执行过程中，要么全部执行，要么全部不执行。
  • 任何一项操作失败都将导致整个事务失败，同时其他已经被执行的操作都将被撤销并回滚。只有所有的操作全部成功，整个事务才算是成功完成。

• Consistency（一致性）

  • 事务的一致性是指事务的执行不能破坏数据库数据的完整性和一致性，一个事务在执行前后，数据库都必须处于一致性状态。换句话说，事务的执行结果必须是使数据库从一个一致性状态转变到另一个一致性状态。
  • 假设银行的转账操作就是一个事务。假设A和B原来账户都有100元。此时A转账给B50元，转账结束后，应该是A账户减去50元变成50元，B账户增加50元变成150元。A、B的账户总和还是200元。转账前后，数据库就是从一个一致性状态（A100元，B100元，A、B共200元）转变到另一个一致性状态（A50元，B150元，A、B共200元）。假设转账结束后只扣了A账户，没有增加B账户，这时数据库就处于不一致的状态。

• Isolation（隔离性）

  • 事务的隔离性是指在并发环境中，并发的事务是相互隔离的，事务之间互不干扰。

  • 在标准的SQL规范中，定义的4个事务隔离级别，不同隔离级别对事务的处理不同。4个隔离级别分别是：读未提交、读已提交、可重复读和串行化。

    

  • 事务隔离级别越高，就越能保证数据的完整性和一致性，但同时对并发性能的影响也越大。

  • 通常，对于绝大多数的应用来说，可以优先考虑将数据库系统的隔离级别设置为授权读取，这能够在避免脏读的同时保证较好的并发性能。尽管这种事务隔离级别会导致不可重复读、幻读和第二类丢失更新等并发问题，但较为科学的做法是在可能出现这类问题的个别场合中，由应用程序主动采用悲观锁或乐观锁来进行事务控制。

• Durability（持久性）

  • 事务的持久性又称为永久性，是指一个事务一旦提交，对数据库中对应数据的状态变更就应该是永久性的。即使发生系统崩溃或机器宕机等故障，只要数据库能够重新启动，那么一定能够将其恢复到事务成功结束时的状态。

1.2 分布式事务是分布式的

其次，分布式事务是分布式的，既然是分布式的系统，那么它必然无可避免的要收到CAP理论的约束：

1.2.1 分布式系统要受CAP理论约束

CAP理论：一个分布式系统不可能同时满足一致性（C:Consistency）、可用性（A:Availability）和分区容错性（P:Partition tolerance）这三个基本要求，最多只能满足其中的两项。

• 一致性
  • 在分布式环境中，一致性是指数据在多个副本之间是否能够保持一致的特性（这点跟ACID中的一致性含义不同）。
  • 对于一个将数据副本分布在不同节点上的分布式系统来说，如果对第一个节点的数据进行了更新操作并且更新成功后，却没有使得第二个节点上的数据得到相应的更新，于是在对第二个节点的数据进行读取操作时，获取的依然是更新前的数据（称为脏数据），这就是典型的分布式数据不一致情况。
  • 在分布式系统中，如果能够做到针对一个数据项的更新操作执行成功后，所有的用户都能读取到最新的值，那么这样的系统就被认为具有强一致性（或严格的一致性）。
• 可用性
  • 可用性是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果，如果超过了这个时间范围，那么系统就被认为是不可用的。
  • 『有限的时间内』是一个在系统设计之初就设定好的运行指标，不同的系统会有很大的差别。比如对于一个在线搜索引擎来说，通常在0.5秒内需要给出用户搜索关键词对应的检索结果。而对应Hive来说，一次正常的查询时间可能在20秒到30秒之间。
  • 『返回结果』是可用性的另一个非常重要的指标，它要求系统在完成对用户请求的处理后，返回一个正常的响应结果。正常的响应结果通常能够明确地反映出对请求的处理结果，及成功或失败，而不是一个让用户感到困惑的返回结果。
  • 让我们再来看看上面提到的在线搜索引擎的例子，如果用户输入指定的搜索关键词后，返回的结果是一个系统错误，比如”OutOfMemoryErroe”或”System Has Crashed”等提示语，那么我们认为此时系统是不可用的。
• 分区容错性
  • 分区容错性要求一个分布式系统需要具备如下特性：分布式系统在遇到任何网络分区故障的时候，仍然能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。
  • 网络分区是指在分布式系统中，不同的节点分布在不同的子网络（机房或异地网络等）中，由于一些特殊的原因导致这些子网络之间出现网络不连通的状况，但各个子网络的内部网络是正常的，从而导致整个系统的网络环境被切分成了若干个孤立的区域。

需要明确的一点是：对于一个分布式系统而言，分区容错性可以说是一个最基本的要求。因为既然是一个分布式系统，那么分布式系统中的组件必然需要被部署到不同的节点，否则也就无所谓的分布式系统了，因此必然出现子网络。

而对于分布式系统而言，网络问题又是一个必定会出现的异常情况，因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构师往往需要把精力花在如何根据业务特点在C（一致性）和A（可用性）之间寻求平衡。

比如Cassandra、Dynamo等中间件，他们的实现默认优先选择AP，弱化C；

而HBase、MongoDB等中间件，他们的实现默认优先选择CP，弱化A。

1.2.2 一致性和可用性权衡的总结——BASE理论

BASE是Basically Available(基本可用）、Soft state(软状态）和Eventually consistent(最终一致性）三个短语的简写，由eBay架构师Dan Pritchett提出的，是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网分布式系统实践的总结，是基于CAP定律逐步演化而来。

BASE理论核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。

• 基本可用
  • 基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性——但请注意，这绝不等价于系统不可用。比如
    • 响应时间上的损失：正常情况下，一个在线搜索引擎需要在0.5秒之内返回给用户相应的查询结果，但由于出现故障（比如系统部分机房发生断电或断网故障），查询结果的响应时间增加到了1~2秒。
    • 功能上的损失：正常情况下，在一个电子商务网站（比如淘宝）上购物，消费者几乎能够顺利地完成每一笔订单。但在一些节日大促购物高峰的时候（比如双十一、双十二），由于消费者的购物行为激增，为了保护系统的稳定性（或者保证一致性），部分消费者可能会被引导到一个降级页面
• 弱状态
  • 弱状态是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同的数据副本之间进行数据同步的过程存在延时。
• 最终一致性
  • 最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。
  • 最终一致性是一种特殊的弱一致性：系统能够保证在没有其他新的更新操作的情况下，数据最终一定能够达到一致的状态，因此所有客户端对系统的数据访问都能够获取到最新的值。同时，在没有发生故障的前提下，数据到达一致状态的时间延迟，取决于网络延迟、系统负载和数据复制方案设计等因素。
  • 在实际工程实践中，最终一致性存在以下五类主要的变种：
    • 因果一致性(Causal consistency)
      • 如果进程A通知进程B它已更新了一个数据项，那么进程B的后续访问将返回更新后的值，且一次写入将保证取代前一次写入。与进程A无因果关系的进程C的访问遵守一般的最终一致性规则。
    • 读己之所写(Read your writes)
      • 当进程A自己更新一个数据项之后，它总是访问到更新过的值，绝不会看到旧值。这是因果一致性模型的一个特例。
    • 会话一致性(Session consistency)
      • 这是上一个模型的实用版本，它把访问存储系统的进程放到会话的上下文中。只要会话还存在，系统就保证“读己之所写”一致性。如果由于某些失败情形令会话终止，就要建立新的会话，而且系统的保证不会延续到新的会话。
    • 单调读一致性(Monotonic read consistency)
      • 如果某个进程已经看到过数据对象的某个值，那么该进程任何后续访问都不会返回在那个值之前的值。
    • 单调写一致性(Monotonic write consistency)
      • 系统保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性，就非常难以编程了。

        以上就是最终一致性的五种常见的变种，在实际系统实践中，可以将其中的若干个变种互相结合起来，以构建一个具有最终一致性特性的分布式系统。
        事实上，最终一致性并不是只有那些大型分布式系统才涉及的特性，许多现代的关系型数据库都采用了最终一致性模型。在现代关系型数据库中（比如MySQL和PostgreSQL），大多都会采用同步或异步方式来实现主备数据复制技术。在同步方式中，数据的复制过程通常是更新事务的一部分，因此在事务完成后，主备数据库的数据就会达到一致。而在异步方式中，备库的更新往往会存在延时，这取决于事务日志在主备数据库之间传输的时间长短。如果传输时间过长或者甚至在日志传输过程中出现异常导致无法及时将事务应用到备库上，那么很显然，从备库中读取的数据将是旧的，因此就出现了数据不一致的情况。
        当然，无论是采用多次重试还是人为数据订正，关系型数据库还是能够保证最终数据达到一致，这就是系统提供最终一致性保证的经典案例。

1.3 ACID和CAP妥协下的柔性事务

可以看到，ACID特性和CAP理论，在关于一致性问题上都有论述，只不过

• ACID中的C论述的是：一个事务在执行前后，数据库的数据都必须处于一致性状态，如转账过程，金钱总量应该保持不变。
• CAP中的C论述的是：同一个数据在多个分布式副本之间是否能够保持一致，如某个用户的余额，在各个副本之间值应该一致。

我们需要注意到他们论述的点其实是不同的。

同时，我们还要注意到，虽然分布式系统受限于CAP理论而时常要在A和C中做取舍，但对于分布式事务系统来说，C的重要性是高于A的，故而市面上成熟的分布式事务解决方案，都是在努力事务ACID特性的基础上，尽量在分布式的情况下（也就是满足分区容错性的情况下）达到较好的数据一致性。

我们一般来说，根据数据一致性的实效，以及ACID/CAP取舍的类型，可将事务分为：

1. 刚性事务：遵循ACID原则，强一致性。本地事务，基本都是刚性事务。
2. 柔性事务：遵循BASE理论，最终一致性；与刚性事务不同，柔性事务允许一定时间内，不同节点的数据不一致，但要求最终一致。

受限于分布式的局限，分布式事务的实现目前都是柔性事务，换句话说，我们还无法实现完全满足ACID强一致性的分布式事务。

2 分布式事务的解决方案

经过上文的论述，我们有了一定的理论基础，明确了我们希望的分布式事务应该是什么样的。我们往往为了可用性和分区容错性，忍痛放弃强一致支持的刚性事务，转而追求最终一致性的柔性事务。

那么如何实现能够基本满足ACID特性和CAP理论的分布式事务呢？我们接下来介绍几种成熟的柔性事务实现。

1. XA协议：更偏向于在数据库层面解决数据库之间的分布式事务
   • 1.1 2PC（两段式提交）
   • 1.2 3PC（三段式提交）
2. TCC两阶段补偿型事务：更偏向于在应用层面解决分布式系统中的补偿形分布式事务
3. 最大努力通知：最简单的一种柔性事务，适用于一些最终一致性时间敏感度低，且被动方处理结果不影响主动方的处理结果的业务。
4. 本地消息表：将分布式事务拆分成本地事务进行处理的一种思路
5. 事务消息机制：借助RocketMQ支持分布式事务消息的特性实现发送端的业务逻辑和消息发送的事务绑定，其本质可以看做是本地消息表的RocketMQ实现。注意，消费端的原子性和回滚则要自己保证，综合来看，更类似最大努力通知模型。
6. Saga事务模型：让所有事件按照顺序推进，则一定可以达到一致性，如果发生异常，则逆序依次调用反向的补偿逻辑做回滚。

2.1 XA协议

在分布式系统中，每个节点都能明确知道自身事务操作结果，但无法直接获取到其他分布式节点的操作结果。所以当一个事务要横跨多个节点时，为了保证事务处理的ACID特性而引入了协调者组件来统一调度所有分布式节点（参与者）的执行逻辑，协调者调度参与者的行为并最终决定是否把参与者的事务进行真正的提交。

XA协议是体现和贯彻协调者角色的一种很经典分布式事务协议，由Tuxedo提出，XA的目的是保证分布式事务的ACID特性，就像本地事务一样。

XA大致分为两部分：事务管理器（协调者角色）和本地资源管理器。其中本地资源管理器往往由数据库实现，比如Oracle、DB2这些商业数据库都实现了XA接口，而事务管理器作为全局的调度者，负责各个本地资源的提交和回滚。

XA协议为了保证分布式事务能够在保持ACID特性的同时保证分布式系统之间的数据一致性，提供了两种分布式事务的实现：2PC和3PC协议。

2.1.1 2PC

2.1.1.1 简介

• 2PC（Two-Phase Commit 两阶段提交）：完成参与者的协调，统一决定事务的提交或回滚，使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和数据一致性。
• 目前绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的。

2.1.1.2 协议内容

1. 投票，尝试让协调者们提交事务

   • 事务询问：协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作，等待响应
   • 执行事务：参与者节点执行事务操作，并记录Undo和Redo信息到事务日志
   • 参与者响应：若参与者成功执行事务，则向协调者反馈Yes响应，否则反馈No响应

2. 根据协调者反馈决定事务执行结果

   21. 如果所有参与者的反馈都是Yes响应，那么执行事务提交
       • 发送提交请求：协调者向所有参与者发送Commit请求
       • 事务提交：参与者接受到Commit请求后执行事务提交操作并释放占用的事务资源
       • 反馈事务提交结果：参与者完成事务提交后向协调者发送Ack消息
       • 完成事务：协调者收到所有参与者的Ack响应后，完成事务提交
   • 
   22. 如果任何一个参与者返回了N响应或者协调者等待超时后就会中断事务
       • 发送回滚请求：协调者向所有参与者发送Rollback请求
       • 事务回滚：参与者受到请求后通过Undo信息执行事务回滚操作并释放占用的事务资源
       • 反馈事务回滚结果：参与者回滚事务后向协调者发送Ack消息
       • 中断事务：协调者接收到所有参与者的Ack响应后，完成事务中断
   • 

   ---

   2.1.1.3 优缺点

• 优点
  • 原理简单，实现方便，有许多现成的实现框架
• 缺点
  • 同步阻塞：在阶段二事务提交过程中，所有参与者的操作逻辑都处于阻塞状态，等待其他参与者响应，协调者请求
  • 单点问题：一旦协调者出现问题，阶段二提交流程无法运转，并且参与者会一直处于锁定事务资源的状态，无法继续事务操作
  • 太过保守：任何一个参与节点的失败使得协调者无法获取所有参与者的响应信息都会导致整个事务的失败

    2.1.2 3PC

    2.1.2.1 简介

• 3PC（Three-Phase Commit 三阶段提交）将二阶段提交的提交事务请求过程一分为二，形成CanCommit、PreCommit、doCommit三个阶段
• 

  2.1.2.2 内容

1. CanCommit

   • 事务询问：协调者向所有参与者发送包含事务内容的CanCommit请求，询问是否可以执行事务提交操作，等待响应
   • 参与者响应：参与者接收到CanCommit请求后判断自身能够顺利执行事务，能则返回Yes响应并进入预备状态，否则返回No响应

2. PreCommit

   21. 如果所有参与者反馈都为Yes响应，则执行事务预提交
       • 发送预提交请求：协调者向所有参与者节点发出PreCommit请求，并进入Prepared阶段
       • 事务预提交：参与者接收到PreCommit请求后预执行事务操作（还未提交），并记录Undo和Redo信息到事务日志中
       • 参与者响应事务执行结果：若参与者成功执行事务后则返回Ack响应给协调者，等待最终命令，提交（commit）或者中断（abort）
   22. 如果任何一个参与者反馈了No响应或者协调者等待所有协调者的响应超时则中断事务
       • 发送中断请求：协调者向所有参与者节点发出Abort请求
       • 中断事务：无论收到Abort请求或者等待协调者请求超时，参与者都会中断事务

3. DoCommit

   31. 执行提交
       • 发送提交请求：当协调者收到所有参与者反馈的Ack响应，向所有参与者发送DoCommit请求，从预提交状态转到提交状态
       • 事务提交：参与者接收到DoCommit请求后，正式执行事务提交操作，并释放占用的事务资源
       • 反馈事务提交结果：参与者完成事务提交后向协调者发送Ack消息
       • 完成事务：协调者接受到所有参与者反馈的Ack响应后，完成事务
   32. 中断事务
       • 发送中断请求：协调者向所有参与者节点发出Abort请求
       • 事务回滚：参与者接收到Abort请求后，利用Undo信息执行事务回滚操作，并释放占用的事务资源
       • 反馈事务回滚结果：参与者完成事务回滚后向协调者发送Ack消息
       • 中断事务：协调者接收到所有参与者反馈的Ack响应后，中断事务

         ps1.需要注意的是，在这一阶段，可能发生两种故障，协调者工作异常，或者协调者与参与者之间网络异常。无论出现何种情况，都会导致参与者无法及时接收到协调者发送的doCommit或者Abort请求，针对这样的异常，参与者在等待超时后，继续进行事务提交。

2.1.2.3 优缺点

• 优点
  • 降低参与者的阻塞范围，能够在出现单点故障后继续达成一致
• 缺点
  • 接受者接收到PreCommit消息后，如果出现网络分区导致协调者和参与者无法正常通信，这时参与者仍会进行事务提交，造成数据的不一致

2.1.3 2PC和3PC的区别总结

• 2PC图示

  • 提交成功
    
  • 中断事务
    

• 3PC 图示
  

• 与两阶段提交不同的是，三阶段提交有如下改动点。

  • 引入超时机制。同时在协调者和参与者中都引入超时机制。
  • 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。
  • 3PC的第三阶段，参与者等待协调者反馈超时时，会默认执行。

• 总结

  • 相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
  • 默认执行其实是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。

2.2 TCC两阶段补偿型事务

2.2.1 简介

TCC方案是可能是目前最火的一种柔性事务方案了。关于TCC（Try-Confirm-Cancel）的概念，最早是由Pat Helland于2007年发表的一篇名为《Life beyond Distributed Transactions:an Apostate’s Opinion》的论文提出。在该论文中，TCC还是以Tentative-Confirmation-Cancellation命名。正式以Try-Confirm-Cancel作为名称的是Atomikos公司，其注册了TCC商标。

国内最早关于TCC的报道，应该是InfoQ上对阿里程立博士的一篇采访。经过程博士的这一次传道之后，TCC在国内逐渐被大家广为了解并接受。

Atomikos公司在商业版本事务管理器ExtremeTransactions中提供了TCC方案的实现，但是由于其是收费的，因此相应的很多的开源实现方案也就涌现出来，如：TCC-transaction、ByteTCC、spring-cloud-rest-tcc、ByteTCC、Himly。

2.2.2 内容

TCC是三个英文单词的首字母缩写而来。没错，TCC分别对应Try、Confirm和Cancel三种操作，这三种操作的业务含义如下：

1. Try：预留业务资源
2. Confirm：确认执行业务操作
3. Cancel：取消执行业务操作

我们以一个经典电商系统下的支付订单场景为例：

那对一个订单支付之后，我们需要做下面的步骤：

1. 更改订单的状态为“已支付”
2. 扣减商品库存
3. 给会员增加积分
4. 创建销售出库单通知仓库发货

上述这几个步骤，要么一起成功，要么一起失败，必须是一个整体性的事务。

那么TCC如何实现呢？

2.2.2.1 Try

Try操作的核心是预留业务资源，比如

1. 别直接把订单状态修改为已支付，可以先把订单状态修改为 UPDATING，也就是修改中的意思。
2. 库存服务也别直接扣减库存啊，而改为冻结掉库存。你可以把可销售的库存：100-2=98，设置为98没问题，然后在一个单独的冻结库存的字段里，设置一个2，也就是说，有2个库存是给冻结了。
3. 同理，别直接给用户增加会员积分，可以先在积分表里的一个预增加积分字段加入积分。
4. 销售出库单可以创建，但是也设置一个中间状态“UNKNOWN”表示未确认。

2.2.2.2 Confirm

完成了Try操作后，接下来就分成两种情况了，第一种情况是比较理想的，那就是各个服务执行自己的Try操作都成功了，那么紧接着进入Confirm阶段。

订单，库存，积分，出库四个模块都感知到了try操作的成功，这时confirm操作执行：

1. 正式把订单的状态设置为“已支付”。
2. 冻结库存字段的2个库存扣掉变为0。
3. 将预增加字段的10个积分扣掉，然后加入实际的会员积分字段中。
4. 将销售出库单的状态正式修改为“已创建”，可以供仓储管理人员查看和使用，而不是停留在之前的中间状态“UNKNOWN”了。

这里简单提一句，如果你要玩TCC分布式事务，必须引入一款TCC分布式事务框架，比如国内开源的 ByteTCC、Himly、TCC-transaction。否则的话，感知各个阶段的执行情况以及推进执行下一个阶段的这些事情，不太可能自己手写实现，太复杂了。

2.2.2.3 Cancel

Confirm是try都成功后的操作，那么cancel就是try操作异常后才会进入的阶段。如积分服务吧，它执行出错了，订单服务内的TCC事务框架是可以感知到的，然后它会决定对整个TCC分布式事务进行回滚。

1. 将订单的状态设置为“CANCELED”，也就是这个订单的状态是已取消。
2. 将冻结库存扣减掉2，加回到可销售库存里去，98 + 2 = 100。
3. 将预增加积分字段的10个积分扣减掉。
4. 将销售出库单的状态修改为“CANCELED”，即已取消。

2.2.3 TCC是补偿形事务

TCC中的两阶段提交（try+confirm或者try+cancel）并没有对开发者完全屏蔽，也就是说从代码层面，开发者是可以感受到两阶段提交的存在。如上述案例：在第一阶段，相关模块需要提供try接口，为积分库存等预留字段分配资源。在第二阶段，各模块需要提供confirm/cancel接口(确认/取消预留)。开发者明显的感知到了两阶段提交过程的存在。try、confirm/cancel在执行过程中，一般都会开启各自的本地事务，来保证方法内部业务逻辑的ACID特性。其中：

1. try过程的本地事务，是保证资源预留的业务逻辑的正确性。

2. confirm/cancel执行的本地事务逻辑确认/取消预留资源，以保证最终一致性，也就是所谓的补偿型事务(Compensation-Based Transactions)。

由于是多个独立的本地事务，因此不会对资源一直加锁。

另外，这里提到confirm/cancel执行的本地事务是补偿性事务，关于什么是补偿性事务，atomikos官网上有以下描述：

红色框中的内容，是对补偿性事务的解释。大致含义是，”补偿是一个独立的支持ACID特性的本地事务，用于在逻辑上取消服务提供者上一个ACID事务造成的影响，对于一个长事务(long-running transaction)，与其实现一个巨大的分布式ACID事务，不如使用基于补偿性的方案，把每一次服务调用当做一个较短的本地ACID事务来处理，执行完就立即提交”。

在这里，笔者理解为confirm和cancel就是补偿事务，用于取消try阶段本地事务造成的影响。因为第一阶段try只是预留资源，之后必须要明确的告诉服务提供者，这个资源你到底要不要，对应第二阶段的confirm/cancel。

现在应该明白为什么把TCC叫做两阶段补偿性事务了，提交过程分为2个阶段，第二阶段的confirm/cancel执行的事务属于补偿事务。

2.2.4 优缺点

• 优点
  • 解决了跨应用业务操作的原子性问题，在诸如组合支付、账务拆分场景非常实用。
  • TCC实际上把数据库层的二阶段提交上提到了应用层来实现，对于数据库来说是一阶段提交，规避了数据库层的2PC性能低下问题。
• 缺点
  • TCC的Try、Confirm和Cancel操作功能需业务提供，开发成本高。

2.3 最大努力通知

2.3.1 简介

最大努力通知型( Best-effort delivery)是最简单的一种柔性事务，适用于一些最终一致性时间敏感度低的业务，且被动方处理结果不影响主动方的处理结果。典型的使用场景如银行通知、商户通知等。

最大努力通知型的实现方案，一般符合以下特点：

1. 不可靠消息：业务活动执行方，在完成业务处理之后，向业务活动的触发方发送消息，直到通知N次后不再通知，允许消息丢失(不可靠消息)。
2. 定期校对：业务活动的触发方，根据定时策略，向业务活动执行方查询(执行方提供查询接口)，恢复丢失的业务消息。

2.3.2 内容

举例来说：设计一个短信发送平台，背景是公司内部有多个业务都有发送短信的需求，如果每个业务独立实现短信发送功能，存在功能实现上的重复。因此专门做了一个短信平台项目，所有的业务方都接入这个短信平台，来实现发送短信的功能。简化后的架构如下所示：

短信发送流程如下：

1. 业务方将短信发送请求提交给短信平台
2. 短信平台接收到要发送的短信，记录到数据库中，并标记其状态为”已接收”
3. 短信平台调用外部短信发送供应商的接口，发送短信。外部供应商的接口也是异步将短信发送到用户手机上，因此这个接口调用后，立即返回，进入第4步。
4. 更新短信发送状态为”已发送”
5. 短信发送供应商异步通知短信平台短信发送结果。而通知可能失败，因此最多只会通知N次。
6. 短信平台接收到短信发送结果后，更新短信发送状态，可能是成功，也可能失败(如手机欠费)。到底是成功还是失败并不重要，重要的是我们知道了这调短信发送的最终结果
7. 如果最多只通知N次，如果都失败了的话，那么短信平台将不知道短信到底有没有成功发送。因此短信发送供应商需要提供一个查询接口，以方便短信平台驱动的去查询，进行定期校对。

在这个案例中，短信发送供应商通知短信平台短信发送结果的过程中，就是最典型的最大努力通知型方案，尽最大的努力通知了N次就不再通知。通过提供一个短信结果查询接口，让短信平台可以进行定期的校对。而由于短信发送业务的时间敏感度并不高，比较适合采用这个方案。

需要注意的是，定期校对的步骤很重要，短信结果查询接口很重要，必须要进行定期校对。因为后期要进行对账，比如一个月的短信发送总量在高峰期可以达到1亿条左右，即使一条短信只要5分钱，一个月就有500W。

2.3.3 优缺点

• 优点
  • 原理简单，实现方便，目前也有现成的实现框架
• 缺点
  • 即便柔性事务都只能保证数据的最终一致性，最大努力通知模型的最终时间也可能是最长的，因为消息发送的不确定性，可能会导致通知迟迟无法被消费，只适用于最终一致性时间敏感度低的业务。
  • 回滚逻辑需要业务编写补偿逻辑来实现，比较费力。

2.4 本地消息表

在描述本地消息表之前，我们要先了解一个概念：

消息发送一致性：是指产生消息的业务动作与消息发送的一致，本地业务逻辑执行与消息发送是原子性的。也就是说，如果业务操作成功，那么由这个业务操作所产生的消息一定要成功投递出去(一般是发送到kafka、rocketmq、rabbitmq等消息中间件中)，否则就丢消息。

以购物场景为例，张三购买物品，账户扣款100元的同时，需要保证在下游的会员服务中给该账户增加100积分。如果扣款100元的业务逻辑执行失败了，但是通知增加积分的消息却没有回滚，而是发送出去了，那就会导致积分无故增加。同样的，如果扣款成功了，但是消息通知失败了，扣款却没有回滚的话，也会导致该增加的积分没有增加。

2.4.1 简介

本地消息表这种实现方式应该是业界使用最多的，这种实现方式的思路，其实是源于 ebay，后来通过支付宝等公司的布道，在业内广泛使用。其基本的设计思想是将远程分布式事务拆分成一系列的本地事务。如果不考虑性能及设计优雅，借助关系型数据库中的表即可实现。

2.4.2 内容

我们可以从下面的流程图中看出其中的一些细节：

举例说明：下单购买商品

1. 支付服务器：前提是有个本地消息表A

   • 1.1 当你支付的时候，你需要把你支付的金额扣减，并且把消息落到本地消息表A，这两个操作要放入同一个事务(依靠数据库本地事务保证一致性）。
   • 1.2 消息落表后，发送MQ通知到商品库存服务器，发送成功后，更新表A中的状态。
   • 1.3 除此之外，支付服务器还有一个定时任务去轮询这个本地事务表A，把没有发送的消息，重试发送给商品库存服务器。

2. 商品库存服务器：前提是有个本地消息表B

   • 2.1 MQ到达商品服务器之后，将接收的消息写入这个服务器的本地消息表B，然后进行扣减库存这两个操作要放入同一个事务(依靠数据库本地事务保证一致性）。扣减成功后，更新事务表B中的状态。
   • 2.2 发送反馈消息给支付服务器，如果执行成功了，就反馈成功消息。如果执行失败，则反馈失败消息。
   • 2.3 除此之外，商品库存服务器还有一个定时任务去轮询这个本地事务表B，把没有发送的消息，重试发送给支付服务器。

如果支付服务器接收到成功的回馈，那么事务成功。如果接收到失败的反馈，则执行回滚操作，即调用补偿接口进行反向操作。

本地消息表模型，通过将业务和消息落表的操作放入同一个本地事务，利用本地事务的ACID特性，来确保发送方/接收方的自身业务逻辑的连贯性和紧密型。

换句话说，只有发送方的业务逻辑执行成功，发送方才会将消息落表，以及发出通知，因为这些步骤在一个本地事务里面，要么都失败，要么都成功。

同理，接收方的业务逻辑执行，接收消息的落表，以及消息表状态的翻转，也都在一个本地事务里面，所以如果接收方发出了通知，那证明接收方的业务逻辑肯定已经执行了。

当两端自身的逻辑都具有连贯性和紧密型，那剩下的只要确保消息可靠就行了。mq的重试机制，以及两方的定时校验机制，都是这种可靠性的保障。

2.4.3 优缺点

• 优点
  • 一种非常经典的实现，将整个分布式事务分割成多个端的本地事务，利用本地事务的可靠性来保证分布式事务在各个端的可靠性，从而使我们的精力只要集中要消息通知和校检上。
• 缺点
  • 消息表会耦合到业务系统中，如果没有封装好的解决方案，会有很多杂活需要处理。
  • 回滚逻辑需要业务编写补偿逻辑来实现，比较费力。

2.5 事务消息机制

2.5.1 简介

前文讨论本地消息表的时候，我们提到了消息发送一致性，使用本地消息表，将业务逻辑和本地消息表的读写用本地事务来保证，这确实是一个办法。但这种办法需要额外建消息表，还需要手动编写落表逻辑和业务逻辑绑定的代码，耦合较重。有什么更优雅的，但同样能保证消息发送一致性的实现吗？答案就是本章讨论的事务消息机制。

从Apache RocketMQ发布的4.3版本开始，RocketMQ开源了社区最为关心的分布式事务消息，而且实现了对外部组件的零依赖。

RocketMQ事务消息设计则主要是为了解决Producer端的消息发送与本地事务执行的原子性问题，RocketMQ的设计中broker与producer端的双向通信能力，使得broker天生可以作为一个事务协调者存在；而RocketMQ本身提供的存储机制，则为事务消息提供了持久化能力；RocketMQ的高可用机制以及可靠消息设计，则为事务消息在系统在发生异常时，依然能够保证事务的最终一致性达成。

2.5.2 内容

事务消息的逻辑，是由发送端Producer进行保证(消费端无需考虑)

1. 首先，发送一个事务消息，这个时候，RocketMQ将消息状态标记为Prepared，注意此时这条消息消费者是无法消费到的。
2. 接着，执行业务代码逻辑，可能是一个本地数据库事务操作
3. 最后，确认发送消息，根据本地业务执行结果返回commit或者是rollback。
   • 3.1 如果本地业务执行成功，消息是commit，这个时候，RocketMQ将消息状态标记为可消费，这个时候消费者，才能真正的保证消费到这条数据。
   • 3.2 如果消息是rollback，RocketMQ将删除该prepare消息不进行下发。

如果发送端发送的确认消息发送失败了怎么办？RocketMQ会定期扫描消息集群中的事务消息，如果发现了Prepared消息，它会向消息发送端(生产者)确认。RocketMQ会根据发送端设置的策略来决定是回滚还是继续发送确认消息。这样就保证了消息发送与本地事务同时成功或同时失败。

消费端的消费成功机制由RocketMQ保证。如果发送的消息消费超时了就一直重试。

但值得注意的是，如果消费端接到通知，然后执行消费端业务逻辑失败了的话，阿里提供给我们的解决方法是：人工解决。也就是说，两端之间的原子性，需要人工做补偿逻辑，该机制无法保证。

2.5.3 优缺点

• 优点
  • 依靠成熟的消息中间件的事务消息机制，不用耦合太多其他逻辑在业务逻辑中，就可以保证消息发送一致性，实现简单。
• 缺点
  • 发送端和消费端之间的原子性无法保证，如果发送回滚，需要人工介入。

2.6 Saga事务模型

2.6.1 简介

Saga事务模型又叫做长时间运行的事务（Long-running-transaction）, 它是由普林斯顿大学的H.Garcia-Molina等人于1987年提出，是一种异步的分布式事务解决方案，其理论基础在于，其假设所有事件按照顺序推进，总能达到系统的最终一致性，因此saga需要服务分别定义提交接口以及补偿接口，当某个事务分支失败时，调用其它的分支的补偿接口来进行回滚。

2.6.2 内容

saga的具体实现分为两种：Choreography以及Orchestration：

Choreography：更接近Saga模型的初衷的一种实现：所有事件按照顺序推进，总能达到系统的最终一致性

这种模式下不存在协调器的概念，每个节点均对自己的上下游负责，在监听处理上游节点事件的同时，对下游节点发布事件。

Orchestration：存在中心节点的模式

该中心节点，即协调器知道整个事务的分布状态，相比于无中心节点方式，该方式有着许多优点：

1. 能够避免事务之间的循环依赖关系，由协调器来管理整个事务链条。
2. 参与者只需要执行命令/回复(其实回复消息也是一种事件消息)，无需关心和维护自己的上下游是谁，降低参与者的复杂性。
3. 开发测试门槛低。
4. 扩展性好，在添加新步骤时，事务复杂性保持线性，回滚更容易管理。

基于上述优势，因此大多数saga模型实现均采用了这种思路。

2.6.3 优缺点

• 优点
  • 降低了事务粒度，使得事务扩展更加容易，同时采用了异步化方式提升性能。
• 缺点
  • 很多时候很难定义补偿接口，回滚代价高，而且由于在执行过程中采用了先提交后补偿的思路进行操作，所以单个子事务在并发提交时的隔离性很难保证。

3 分布式事务解决方案总结

3.1 XA协议和TCC的区别

作为最热门的两种解决方案，XA协议和TCC的区别我们需要重点知晓。

TCC与XA两阶段提交有着异曲同工之妙，下图列出了二者之间的对比：

1. 在阶段1：

   • 在XA中，各个RM准备提交各自的事务分支，事实上就是准备提交资源的更新操作(insert、delete、update等)；而在TCC中，是主业务活动请求(try)各个从业务服务预留资源。

2. 在阶段2：

   • XA根据第一阶段每个RM是否都prepare成功，判断是要提交还是回滚。如果都prepare成功，那么就commit每个事务分支，反之则rollback每个事务分支。

TCC中，如果在第一阶段所有业务资源都预留成功，那么confirm各个从业务服务，否则取消(cancel)所有从业务服务的资源预留请求。

TCC两阶段提交与XA两阶段提交的区别是：

1. XA是资源层面的分布式事务，强一致性，在两阶段提交的整个过程中，一直会持有资源的锁。
   • XA事务中的两阶段提交内部过程是对开发者屏蔽的，回顾我们之前讲解JTA规范时，通过UserTransaction的commit方法来提交全局事务，这只是一次方法调用，其内部会委派给TransactionManager进行真正的两阶段提交，因此开发者从代码层面是感知不到这个过程的。
   • 而事务管理器在两阶段提交过程中，从prepare到commit/rollback过程中，资源实际上一直都是被加锁的。如果有其他人需要更新这两条记录，那么就必须等待锁释放。

2. TCC是业务层面的分布式事务，最终一致性，在TCC整个过程中，不会一直持有资源的锁。
   • TCC中的两阶段提交并没有对开发者完全屏蔽，也就是说从代码层面，开发者是可以感受到两阶段提交的存在。如上述航班预定案例：在第一阶段，航空公司需要提供try接口(机票资源预留)。
   • 在第二阶段，航空公司提需要提供confirm/cancel接口(确认购买机票/取消预留)。开发者明显的感知到了两阶段提交过程的存在。try、confirm/cancel在执行过程中，一般都会开启各自的本地事务，来保证方法内部业务逻辑的ACID特性。其中：
     1. try过程的本地事务，是保证资源预留的业务逻辑的正确性。
     2. confirm/cancel执行的本地事务逻辑确认/取消预留资源，以保证最终一致性，也就是所谓的补偿型事务(Compensation-Based Transactions)。

3.2 最大努力通知和本地消息表的区别

虽然都是利用mq，但是本地消息表利用本地事务来绑定业务逻辑和消息发送，使得mq两端的操作（发送前和接收后）是绝对可靠的，原子的。保证了消息发送一致性。

而最大努力通知模型，业务逻辑和发送消息之间没有这种紧密的可靠性保证，一切只能在业务上自己去实现代码来保证可靠。

前言

在JAVA开发中，我们经常需要操作数组和集合，其中数组和链表的排序是重中之重。

Arrays.sort方法用来对数组排序。Collections.sort()方法用来对链表排序，而Collections.sort()的底层，其实使用的也是Arrays.sort方法。

所以JAVA内置排序的核心类，都在于Arrays工具类，接下来我们也重点剖析该类。

1. Arrays工具类

我们先来看下Arrays工具类对外暴露的sort方法列表。

A：从排序范围角度划分，sort方法分为了

1. 针对数组的整体做排序的方法，如
   • sort(int[] a)
   • sort(Object[] a)
   • sort(T[] a, Comparator<? super T> c)
2. 针对数组的局部做排序的方法，如
   • sort(int[] a, int fromIndex, int toIndex)
   • sort(Object[] a , int fromIndex, int toIndex)
   • sort(T[] a, int fromIndex, int toIndex,Comparator<? super T> c)

B：从排序类型角度划分，sort方法分为了

1. 对数组按照默认升序的方式进行排序的方法，如
   • sort(int[] a)
   • sort(Object[] a)
   • sort(int[] a, int fromIndex, int toIndex)
   • sort(Object[] a , int fromIndex, int toIndex)
2. 对数组按照自定义排序类型进行排序的方法，如
   • sort(T[] a, Comparator<? super T> c)
   • sort(T[] a, int fromIndex, int toIndex,Comparator<? super T> c)

C：从操作对象角度划分，sort方法分为了

1. 对基本类型（byte，int，char等）数组操作的方法
   • sort(int[] a)
   • sort(int[] a, int fromIndex, int toIndex)
2. 对对象类型（object）数组操作的方法
   • sort(Object[] a)
   • sort(Object[] a , int fromIndex, int toIndex)
   • sort(T[] a, Comparator<? super T> c)
   • sort(T[] a, int fromIndex, int toIndex,Comparator<? super T> c)

这里最重要的划分是C：从操作对象角度划分，因为JAVA对不同类型的数组，定义了不同的实现方法（以常用的JDK 1.8版本为例），我们先来开门见山的总结一下：

2. 基本类型数组的排序

对于基本数据类型的数组，假设数组长度为length：

1. 如果length<47，那么采用插入排序算法。
2. 如果47<=length<286，或者286<=length，但数组不具备特定结构，那么使用快速排序的一种优化形式：双轴快排算法。
3. 如果286<=length，并且数组具备特定结构，那么使用归并排序算法。

2.1 数组是否具备特定结构

在判断是否使用归并排序前，要先判断数组是否具备特定结构，这是一个什么意思呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Check if the array is nearly sorted
    for (int k = left; k < right; run[count] = k) {        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {                if (--m == 0) {
                    sort(a, left, right, true);                    return;
                }
            }
        }        /*
         * The array is not highly structured,
         * use Quicksort instead of merge sort.
         */
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);            return;
        }
    }

这里主要作用是看他数组具不具备结构：实际逻辑是分组排序，每个降序序列为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后再从最后的8开始继续往后面找。

每遇到这样一个降序组，++count，当count大于MAX_RUN_COUNT（67），被判断为这个数组不具备结构，也就是说这数据时而升时而降，波峰波谷太多，排列太过陡峭，说明不适合采用归并排序，还是使用快速排序为宜。

如果count少于MAX_RUN_COUNT（67）的，说明这个数组还有点结构，就继续往下走下面的归并排序。

2.2 双轴快排

双轴快排（DualPivotQuickSort）是快排的一种优化版本。双轴快速排序，顾名思义，取两个中心点pivot1，pivot2，且pivot≤pivot2，可将序列分成三段：x<pivot1、pivot1≤x≤pivot2，x<pivot2，然后分别对三段进行递归。基本过程如下图：

具体详细内容可见博客单轴快排（SinglePivotQuickSort）和双轴快排（DualPivotQuickSort）及其JAVA实现

3. 对象类型数组的排序

对于对象类型的数组，假设数组长度为length：

• 1. 如果length<32，那么采用不包含合并操作的mini-TimSort算法。
• 2. 如果32<=length，那么采用完整TimSort排序算法（一种结合了归并排序和插入排序的算法）。

3.1 TimSort

TimSort算法是一种起源于归并排序和插入排序的混合排序算法，设计初衷是为了在真实世界中的各种数据中可以有较好的性能。

基本工作过程是：

1. 扫描数组，确定其中的单调上升段和严格单调下降段，将严格下降段反转。我们将这样的段称之为run。
2. 定义最小run长度，短于此的run通过插入排序合并为长度高于最小run长度；
3. 反复归并一些相邻run，过程中需要避免归并长度相差很大的run，直至整个排序完成；
4. 如何避免归并长度相差很大run呢， 依次将run压入栈中，若栈顶run X，run Y，run Z 的长度违反了X>Y+Z 或 Y>Z 则Y run与较小长度的run合并，并再次放入栈中。 依据这个法则，能够尽量使得大小相同的run合并，以提高性能。注意Timsort是稳定排序故只有相邻的run才能归并。
5. Merge操作还可以辅之以galloping，具体细节可以自行研究。

总之，timsort是工业级算法，其混用插入排序与归并排序，二分搜索等算法，亮点是充分利用待排序数据可能部分有序的事实，并且依据待排序数据内容动态改变排序策略——选择性进行归并以及galloping。

具体内容我们不展开，可详见Collections.sort()源码分析(基于JAVA8)

4. 为什么要采用不同的算法？

对于长度较小的数组使用插入排序这很好理解，虽然插入排序的时间复杂度为O(n^2)，但在n较小的情况下，插入排序性能要高于快速排序。

其次我们要知道，在n的数量较大时，归并排序和快速排序，都是性能最优的排序算法，他们的时间复杂度平均都在O(nlogn)左右，只不过区别在于归并排序是稳定的，快速排序是不稳定的。

稳定是指相等的数据在排序之后仍然按照排序之前的前后顺序排列。

对于基本数据类型，稳定性没有意义，所以它可以使用不稳定的快排（当然它也使用了归并排序）

而对于对象类型，稳定性是比较重要的，因为对象相等的判断比较复杂，我们无法寄希望于每个程序员都会重写准确的equal方法，故而稳妥起见，最好相等对象尽量保持排序前的顺序，故而我们使用都是稳定算法的归并排序和插入排序结合而成的TimSort算法。

另外一个原因是归并排序的比较次数比快排少，移动（对象引用的移动）次数比快排多，而对于对象来说，比较是相对耗时的操作，所以它不适合使用快排。

而对于基本数据类型来说，比较和移动都不怎么耗时，所以它用归并或者快排都可以

总结：

1. 基本数据类型数组使用快排+归并是因为：

   • 基本数据类型无所谓稳定性，可以采用非稳定的快排。
   • 对于基本数据类型来说，比较和移动都不怎么耗时，所以它用归并或者快排都可以。

2. 对象数据类型数组使用TimSort排序是因为（或者换句话说，对象数据类型不使用快排是因为）：

   • 对象数据类型要求稳定性，需要采用稳定的归并+插入。
   • 对于对象来说，比较操作相对耗时，所以用比较操作较少的归并排序可以扬长避短。