Multiversion concurrency control 多版本并发控制

并发访问（读或者写）数据库时，对正在事务内处理的数据做多版本的管理，用来避免由于写操作的堵塞，而引发读操作失败的并发问题。

引言

先看一个案例：

1.查看数据的事务隔离级别

对事务隔离级别不熟悉的同学可以参考文章 【MySQL （三） | 五分钟搞清楚MySQL事务隔离级别】

1

SELECT @@tx_isolation;

可见 数据库隔离级别使用的是MySQL默认的RR级别。

REPEATABLE READ 意味着：

• 同一个事务中多次执行同一个select,读取到的数据没有发生改变；
• 此时：允许幻读，但不允许不可重复读和脏读，所以RR隔离级别要求解决不可重复读；

2.在不同会话中执行以下SQL

补充一下建表语句：

1
2
3
4
5
6
7
8

create table `test_zq` (
	`id` int (11),
	`test_id` int (11)
); 
insert into `test_zq` (`id`, `test_id`) values('1','18');
insert into `test_zq` (`id`, `test_id`) values('4','8');
insert into `test_zq` (`id`, `test_id`) values('7','4');
insert into `test_zq` (`id`, `test_id`) values('10','1234');

用户1：

1
2
3

begin;
-- 更新 id 为 1 的数据
UPDATE test_zq SET test_id = 20 WHERE id = 1;

用户2:

1
2
3

begin;
--查询 id 为 1 的数据
SELECT * FROM test_zq WHERE id = 1;

执行结果大致如下：

根据事务隔离级别来看，我们理论上对获得 X 锁（关于锁的概念可以参考 【MySQL （四） | 五分钟搞清楚InnoDB锁机制】）的数据行是不能再被获取读锁而访问的，但是事实上我们依然访问到了这个数据！

通过结果说明：我们可以在一个事务未进行 commit/rollback操作之前，另一个事务仍然可以读取到数据库中的数据，只不过是读取到的是其他事务未改变之前的数据。此处是利用了MVCC多数据做了多版本处理，读取的数据来源于快照。

3.同理，在不同会话中执行以下SQL

用户1：

1
2

begin;
SELECT * FROM test_zq WHERE id = 1;

用户2：

1
2

begin;
update test_zq set test_id = 22 where id = 1;

执行完之后再回到用户1进行一次数据查询

1

SELECT * FROM test_zq WHERE id = 1;

执行结果：

执行结果和上一步的执行结果一样，只不过区别在于2步骤中是先 update 后 select , 3 步骤是先 select 后 update.

虽然两者执行结果是一致的，但是我们要思考两个问题：

• 他们的底层实现是一样的吗？
• 他们的实现和MVCC有什么关系呢？

接下来我们便开始了解一下 MVCC 机制

什么是MVCC

MVCC，Multi-Version Concurrency Control，多版本并发控制。MVCC 是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问；在编程语言中实现事务内存。

如果有人从数据库中读数据的同时，有另外的人写入数据，有可能读数据的人会看到『半写』或者不一致的数据。有很多种方法来解决这个问题，叫做并发控制方法。最简单的方法，通过加锁，让所有的读者等待写者工作完成，但是这样效率会很差。MVCC 使用了一种不同的手段，每个连接到数据库的读者，在某个瞬间看到的是数据库的一个快照，写者写操作造成的变化在写操作完成之前（或者数据库事务提交之前）对于其他的读者来说是不可见的。

当一个 MVCC 数据库需要更一个一条数据记录的时候，它不会直接用新数据覆盖旧数据，而是将旧数据标记为过时（obsolete）并在别处增加新版本的数据。这样就会有存储多个版本的数据，但是只有一个是最新的。这种方式允许读者读取在他读之前已经存在的数据，即使这些在读的过程中半路被别人修改、删除了，也对先前正在读的用户没有影响。这种多版本的方式避免了填充删除操作在内存和磁盘存储结构造成的空洞的开销，但是需要系统周期性整理（sweep through）以真实删除老的、过时的数据。对于面向文档的数据库（Document-oriented database，也即半结构化数据库）来说，这种方式允许系统将整个文档写到磁盘的一块连续区域上，当需要更新的时候，直接重写一个版本，而不是对文档的某些比特位、分片切除，或者维护一个链式的、非连续的数据库结构。

MVCC 提供了时点（point in time）一致性视图。MVCC 并发控制下的读事务一般使用时间戳或者事务 ID去标记当前读的数据库的状态（版本），读取这个版本的数据。读、写事务相互隔离，不需要加锁。读写并存的时候，写操作会根据目前数据库的状态，创建一个新版本，并发的读则依旧访问旧版本的数据。

一句话总结就是：

MVCC(Multiversion concurrency control) 就是 同一份数据临时保留多版本的一种方式，进而实现并发控制

哪么此处需要注意的点就是：

• 在读写并发的过程中如何实现多版本？
• 在读写并发之后，如何实现旧版本的删除（毕竟很多时候只需要一份最新版的数据就够了）？

下面介绍一下MySQL中对于 MVCC 的逻辑实现

MVCC逻辑流程-插入

在MySQL中建表时，每个表都会有三列隐藏记录，其中和MVCC有关系的有两列

• 数据行的版本号 （DB_TRX_ID）
• 删除版本号 (DB_ROLL_PT)

在插入数据的时候，假设系统的全局事务ID从1开始，以下SQL语句执行分析参考注释信息：

1
2
3
4

begin;-- 获取到全局事务ID
insert into `test_zq` (`id`, `test_id`) values('5','68');
insert into `test_zq` (`id`, `test_id`) values('6','78');
commit;-- 提交事务

当执行完以上SQL语句之后，表格中的内容会变成：

可以看到，插入的过程中会把全局事务ID记录到列 DB_TRX_ID 中去

MVCC逻辑流程-删除

对上述表格做删除逻辑，执行以下SQL语句（假设获取到的事务逻辑ID为 3）

1
2
3

begin；--获得全局事务ID = 3
delete test_zq where id = 6;
commit;

执行完上述SQL之后数据并没有被真正删除，而是对删除版本号做改变，如下所示：

MVCC逻辑流程-修改

修改逻辑和删除逻辑有点相似，修改数据的时候 会先复制一条当前记录行数据，同事标记这条数据的数据行版本号为当前是事务版本号，最后把原来的数据行的删除版本号标记为当前是事务。

执行以下SQL语句：

1
2
3

begin;-- 获取全局系统事务ID 假设为 10
update test_zq set test_id = 22 where id = 5;
commit;

执行后表格实际数据应该是：

MVCC逻辑流程-查询

此时，数据查询规则如下：

• 查找数据行版本号早于当前事务版本号的数据行记录

  也就是说，数据行的版本号要小于或等于当前是事务的系统版本号，这样也就确保了读取到的数据是当前事务开始前已经存在的数据，或者是自身事务改变过的数据

• 查找删除版本号要么为NULL，要么大于当前事务版本号的记录

  这样确保查询出来的数据行记录在事务开启之前没有被删除

根据上述规则，我们继续以上张表格为例，对此做查询操作

1
2
3

begin;-- 假设拿到的系统事务ID为 12
select * from test_zq;
commit;

执行结果应该是：

本文整理自

【MySQL（5）| 五分钟搞清楚 MVCC 机制】

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

字符函数

CONCAT() 字符连接

1
2

SELECT CONCAT('a','-','b');
--结果为: a-b

CONCAT_WS() 使用指定的分隔符进行字符连接

1
2

SELECT CONCAT_WS('|','A','B','C'); 
--结果为： A|B|C

FORMAT() 数字格式化

对数字四舍五入,返回字符串,包括逗号’,’

1
2
3
4

SELECT FORMAT(12560.7,2); 
--结果：12,560.70
SELECT FORMAT(12560.78,1); 
--结果：12,560.8

LOWER() 转换成小写字母

UPPER() 转换成大写字母

LEFT() 截取左侧字符

1
2

SELECT LEFT('mysql',2);  
--结果：my

RIGHT() 截取右侧字符

LENGTH() 获取字符串长度

长度包含空格

LTRIM() 删除前导空格

等同于LEFT TRIM()

RTRIM() 删除后续空格

TRIM() 删除前后两边的指定字符(默认空格)

删除指定的前导和后续的字符,但不能删除中间的字符,如

1
2
3
4
5
6

SELECT TRIM(LEADING'?','??MYSQL????');  
--leading前导,结果：MYSQL????
SELECT TRIM(TRAILING'?','??MYSQL????');  
--trailing后序,结果：??MYSQL
SELECT TRIM(BOTH'?','??MYSQL???'); 
--结果：MYSQL

REPLACE() 替换字符

如将’?’替换为’-‘

1
2

SELECT REPLACE('??MYSQL???','?','-');  
--结果：--MYSQL---

SUBSTRING(string，offset，length) 截取字符串

1
2

SELECT SUBSTRING('MYSQL',2,3);  
--结果：SQL

[NOT] LIKE 模糊匹配

ESCAPE可指定转义字符

• % 代表任意个字符，0个或多个
• _ 代表任意一个字符，只有一个

1
2
3
4

SELECT name FROM test WHERE name LIKE'%o%'; 
--结果：输入name 中带‘o’的name
SELECT name FROM test WHERE name LIKE'%1%%' ESCAPE '1';
--找到中间带% 的匹配name

数值运算

CEIL(数值) 向上取整

1
2

SELECT CEIL(3.01);
--结果是4

FLOOR(数值) 向下取整

1
2

SELECT FLOOR(3.99);
--结果是3;

DIV 除法,保留整数

如果使用’’,如’3/4’结果为’0.75’

1
2

SELECT 3 DIV 4; 
--结果是0；因为3除以4，整数位为0

MOD 取模

相当于’%’取余运算符，可以用%号代替；

1
2
3
4

SELECT 4 MOD 3; 
--结果为1；
SELECT 5.3 MOD 3; 
--结果为2.3

POWER(数值,数值) 幂运算

1
2

SELECT POWER(3,3); 
--结果为27

ROUND(数值,小数的位数) 四舍五入

TRUNCATE(数值,截取位数)

和ROUND()类似,不四舍五入,直接截断,截取位数可以是负数，

1
2

SELECT TRUNCATE(125.68,-1); 
--结果为120

比较运算

[NOT] BETWEEN ... AND ...

1
2
3
4

SELECT 15 BETWEEND 1 AND 20 
-- 15在1到20之间 ,返回值是1
SELECT 15 NOT BETWEEND 1 AND 20 
--15在1到20之间,条件不成立 返回值是0

[NOT] IN()

判断值是否在给定的集合中,如果在返回1,不在返回0,或者相反

1
2
3
4

SELECT 10 IN(5,10,15) 
-- 返回1 
SELECT 10 NOT(5,10,15) 
-- 返回0

IS [NOT] NULL

是否为NULL,成立返回1,不成立返回0

1
2
3
4

SELECT NULL IS NULL 
-- 返回1 
SELECT '' IS NULL
-- 返回0 , 除了NULL其它都是非空 返回都是1

聚合函数

聚合函数只有一个返回值

AVG()平均值

1
2

SELECT ROUND(AVG(goods_price),2) AS avg_price 
FROM tdb_goods;

COUNT()计数

1
2

SELECT COUNT(goods_id) AS counts 
FROM tdb_goods;

MAX()最大值

1
2

SELECT MAX(goods_price) AS max 
FROM tdb_goods;

MIN()最小值

SUM()求和

1
2

SELECT SUM(goods_price) AS sum 
FROM tdb_goods;

加密函数

MD5() 摘要算法

1

SELECT MD5('admin');

PASSWORD() 密码算法

通过PASSWORD()修改MySQL当前用户和其他用户的密码

1
2

-- 把密码修改成dimitar。
SET PASSWORD=PASSWORD(‘dimitar’);

日期时间函数

NOW() 当前日期,时间

CURDATE() 当前日期

CURTIME() 当前时间

DATE_ADD() 时间增减

1
2
3
4
5

INTERVAL`可以为负值
单位 `YEAR, MONTH, WEEK, DAY
SELECT DATE_ADD('2014-3-12',INTERVAL 365 DAY); 
-- 返回2015-3-12
-- 在原有给定的时间上增加365天

DATEDIFF() 日期差值

单位为日,前面时间减去后面时间

1
2

SELECT DATEDIFF('2014-1-1','2015-1-1') 
-- 返回365

DATEDIFF() 日期格式化

1
2

SELECT DATE_FORMAT('2014-3-2','%m/%d/%Y');
-- 返回03/02/2014

内置信息函数

VERSION() MySQL版本信息

SELECT DATABASE() 当前数据库

USER() 当前用户

1

SELECT USER();

CONNECTION_ID() 当前用户的连接ID

1

SELECT CONNECTION_ID();

LAST_INSERT_ID() 最后插入的记录的 ID 号

ID为主键,必须自动编号AUTO_INCREMENT,可以不叫’ID’.
如果一次INSERT插入的是多条记录，得到的是多条记录中的第一条（而不是最后一条！）

本文遵循CC 4.0 BY-SA版权协议.

锁

锁是用于管理不同事务对共享资源的并发访问

表锁和行锁的区别：

在加锁效率、锁定粒度以及冲突概率上，表锁肯定是大于行锁的

但是在并发性能上，表锁远低于行锁。

表锁是锁定了整个表，在加锁期间，无论读写，这个表的数据都是锁定的，相反行锁只是锁定了这个表中的一条数据，其他数据仍然可以操作，这就可很好的提高了数据库的并发性能。

Mysql Innodb 锁类型

• 共享锁 Shared Locks （简称 S 锁，属于行锁）
• 排他锁 Exclusive Locks（简称 X 锁，属于行锁）
• 意向共享锁 Intention Shared Locks （简称 IS 锁，属于表锁）
• 意向排他锁 Intention Exclusive Locks （简称 IX 锁，属于表锁）
• 自增锁 AUTO-INC Locks

共享锁（S）与排它锁 （X）

共享锁

又称之为 读锁，简称 s 锁，顾名思义，共享锁就是多个事务对于同一数据可以共享一把锁，都能访问到数据库，但是只能读不能修改；

加锁方式：

select * from users where id = 1 lock in share mode;

释放方式：

rollback/commit;

举例：

当手动为select语句加上共享锁之后，在右边的会话中我们对该条数据执行update 操作 ，会发现一直卡住，这就是说，加了共享锁的数据，只能被其他事务读取，但是不能被修改

当我们 commit/rollback结束掉左边会话框的事务时，会发现右边会话框的update操作可以正常进行了

但是我们要注意一点，哪就是共享锁是不影响其他事物读取数据的，如下举例：

排它锁

又称为写锁，简称 X 锁，排它锁不能与其他锁并存，如一个事务获取了一个数据行的排它锁，其他事务就不能再获取改行的锁（包括共享锁和排它锁），只有当前获取了排它锁的事务可以对数据进行读取和修改（此时其他事务要读取数据可从快照获取）

加锁方式：

delete update insert 默认加排他锁

select * from users where id = 1 for update;

释放方式：

rollback/commit;

举例：

另一事务获取共享锁,排他锁,都会锁住

InnoDB 行锁到底锁的是什么？

我们首先来看如下一个例子：

发现在事务1中对id=1的数据行做了更新操作，但是事务未提交之前，事务2去再去更新这条数据会卡住，也就是被锁住了。

接下来我们在事务1 未做任何改变，保持事务未提交状态的情况下去更新id = 2 的数据行

结果显而易见，更新数据成功了。

综上所述：

InnoDB的行锁是通过给索引上的索引项加锁来实现的，只有通过索引条件进行数据检索，Innodb才使用行级锁。否则，将使用表锁（锁住索引的所有记录）。

借此我们是不是能联想到，如果我们的删除/修改语句是没有命中索引的，哪么，则会锁住整个表，这在性能上的影响还是挺大的。

意向共享锁(IS)和意向排他锁(IX)

意向共享锁

表示事务准备给数据行加入共享锁，也就是说一个数据行在加共享锁之前必须先取得该表的IS锁。

意向排他锁

表示事务准备给数据行加入排它锁，也就是说一个数据行加排它锁之前必须先取得该表的IX锁。

• 意向锁是InnoDB数据操作之前自动加的，不需要用户干预

• 意向锁是表级锁

关于这两个锁的实际演示例子本文鉴于篇幅便不再赘述，感兴趣的可以根据上边描述的共享锁和排他锁演示过程自己体验一遍.

这两个意向锁存在的意义是：

当事务想去进行锁表时，可以先判断意向锁是否存在，存在时则可快速的返回，告知该表不能启用表锁（也就是会锁住对应会话），提高了加锁的效率。??

自增锁 （AUTO -INC Locks）

针对自增列自增长的一个特殊的表级别锁

可以使用如下语句查看 ：

1
2

-- 默认取值1 代表连续 事务未提交则id永久丢失
SHOW VARIABLES LIKE 'innodb_autoinc_lock_mode';

实际演示效果如下：

执行结果如下：

行锁的算法

简介

行锁锁的是索引上的索引项

只有通过索引条件进行数据检索，Innodb才使用行级锁。否则，将使用表锁（锁住索引的所有记录）

行锁的算法:

• 临键锁 Next-Key locks

  当sql执行按照索引进行数据的检索时，查询条件为范围查找（between and < > 等等）并有数据命中，则测试SQL语句加上的锁为Next-Key locks,锁住索引的记录区间加下一个记录区间，这个区间是左开右闭的

• 间隙锁 Gap

  查询条件为范围查找（between and < > 等等）且当记录不存在时，临键锁退化成Gap. 在上述检索条件下，如果没有命中记录，则退化成Gap锁，锁住数据不存在的区间（左开右开）

• 记录锁 Record Lock

  唯一性索引 条件为精准匹配，退化成Record锁. 当SQL执行按照唯一性（Primary Key,Unique Key）索引进行数据的检索时，查询条件等值匹配且查询的数据存在，这时SQL语句上加的锁即为记录锁Record locks,锁住具体的索引项。

举例

临键锁

Next-Key locks 也是 InnoDB 引擎默认的行锁算法.

如图：我们假设一张表中的数据行的id 是 1 4 7 10

则innodb会把这个表的数据划分成如图五个区间(因为有四个记录)，然后我们执行图中的SQL语句之后，会发现有两个区间被锁住了，一个是（4,7] ， 一个是 (7,10]

为了验证这个结论，我做了如下实验：

验证区间是否左开右闭：

验证当前记录行是否被锁定：

验证是否锁定下一区间：

以下两种锁只给出结论，演示过程省略，感兴趣可自行验证哈！都是同样的方法，就不赘述了

间隙锁

记录锁

总结

MySQL 的 Innodb引擎正是通过上述不同类型的锁，完成了事务隔离：

• 加 X 锁 避免了数据的脏读
• 加 S 锁 避免了数据的不可重复读
• 加上 Next Key 避免了数据的幻读

补充

Innodb中行级锁作用于索引之上，如果没有索引，则只能够锁表。

一次封锁法

为了预防死锁，一般应用中推荐一次封锁法。也就是在方法的开始阶段，已经预先知道会用到哪些数据，然后全部锁住，在方法运行完成之后，再进行解锁。

一次封锁法能够预防死锁，但从该方法的定义中可以看到，每次操作都锁住全部数据，如果这样数据的执行只能是串行化的，性能不高。

两阶段锁协议

数据库遵循的是两段锁协议，将事务分解成加锁和解锁两个阶段

加锁阶段

该阶段可以进行加锁操作，在对任何数据进行读操作之前要申请并获得S锁(Shared Lock，其它事务可以继续加S锁，但不能加Exclusive Lock，即排他锁)；而在进行写操作之前，需要申请X锁(Exclusive Lock，其它事务不能再获得任何锁)。加锁不成功则进入等待状态，而不能再加其它锁。

从这个定义可以看出，加锁阶段定义了事务之间的协调规则，能够有效提高多个事务之间的执行性能，但同时也带来了死锁的风险，之后会举例介绍死锁的成因。

解锁阶段

事务进入解锁阶段将释放其持有的锁，该阶段只能进行解锁操作，而不能再加其它锁。

Innodb中的各种锁

Shared Lock And Exclusive Locks

这是两个行级锁，包括 Shared Lock(S 共享锁) 和 Exclusive Lock(X 排他锁):

1. 共享锁 允许持有锁的事务去读取一行数据，可以有多个事务同时持有共享锁，但当数据被加上共享锁时，不能再被加排他锁。
2. 排他锁 允许持有锁的事务去更新或则删除一行数据，同时只能有一个事务持有排他锁，当数据被加上排他锁时，不能再加共享锁。

Record Locks

记录锁是作用在索引上，比如这么一条语句：

1

SELECT c1 FROM t WHERE c1=10 FOR UPDATE

这条语句将会在c1值为10这条记录的索引加锁，阻止其它事务的插入，更新和删除操作。 即使c1不存在索引，Innodb也会创建一个隐藏的clustered index，并用其作为锁的依据。

Next-key Locks

Next-key锁是记录锁和Gap锁的结合，锁住了记录和记录之前的一段Gap区间。 比如索引包含了10，11，13和20，那么Next-key分出的区间如下：

1
2
3
4
5

(negative infinity, 10]
(10, 11]
(11, 13]
(13, 20]
(20, positive infinity)

Intention Locks

Intention Locks(意向锁)是MySQL为了支持不同粒度的锁而设计的一种 表级别锁(但不是通常认为的表锁) ，它表示了表之后将被加上哪种行级锁。意向锁的分类如下：

1. Intention Shared Lock，意向共享锁(IS) ，表示事务将要在表上加共享锁，规则是在表中申请某些行的共享锁之前，必须先申请IS锁。
2. Intention Exclusive Lock，意向排他锁(IX) ，表示事务将要在标上加排他锁，规则是在表中申请某些行的排他锁之前，必须先申请IX锁。

1

SELECT ... LOCK IN SHARE MODE

该语句将会在表上加IS锁，同时在对应的记录上加上S锁。

1

SELECT ... FOR UPDATE

该语句将会在标上加上IX锁，同时在对应的记录上加上X锁。

表级锁的兼容性矩阵：

总结:意向锁(IX,IS)之间不会产生冲突, 其他情况可将IX锁当做X锁, IS锁当做S锁

事实上意向锁不会和行级的S和X锁产生冲突，只会和表级的S和X锁产生冲突.

GAP Locks

Gap锁是一种范围锁，Gap锁作用范围是Record锁之间，或者Record锁之前与Record锁之后的范围。

如图所示，首先当前该记录存在索引，id为5和30的记录将整个分为了 <=5 ，>5&<=30 和 >30 三个区间，如果要更新30的数据，那么 >5 的所有区间都会被锁住。

Insert Intention Locks

Insert Intention Locks也就是插入意向锁，但它其实是一种GAP锁，在行数据被插入之前，设定的一种锁，如果两个事务要插入同一个GAP中的不同行记录，它们都会获取这个GAP的插入意向锁，但相互之间不会冲突。

AUTO-INC Locks

AUTO-INC锁是一种特殊的表级别锁，主要处理表中带有自增列的情况。实际上是为了保证自增的正确性，所以有了这种锁。

本文整理自

【MySQL （四） | 五分钟搞清楚InnoDB锁机制】

Innodb 锁类型详解

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

B树

B树是一种多路自平衡搜索树，它类似普通的二叉树，但是B书允许每个节点有更多的子节点。B树示意图如下：

B树的特点：
（1）所有键值分布在整个树中
（2）任何关键字出现且只出现在一个节点中
（3）搜索有可能在非叶子节点结束
（4）在关键字全集内做一次查找，性能逼近二分查找算法

B+树

B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：

从图中也可以看到，B+树与B树的不同在于：
（1）所有关键字存储在叶子节点，非叶子节点不存储真正的data
（2）为所有叶子节点增加了一个链指针

为什么用B/B+树来实现索引

红黑树等结构也可以用来实现索引，但是文件系统及数据库系统普遍使用B/B+树结构来实现索引。mysql是基于磁盘的数据库，索引是以索引文件的形式存在于磁盘中的，索引的查找过程就会涉及到磁盘IO消耗，磁盘IO的消耗相比较于内存IO的消耗要高好几个数量级，所以索引的组织结构要设计得在查找关键字时要尽量减少磁盘IO的次数。为什么要使用B/B+树，跟磁盘的存储原理有关。

局部性原理与磁盘预读

为了提升效率，要尽量减少磁盘IO的次数。实际过程中，磁盘并不是每次严格按需读取，而是每次都会预读。磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中，这样做的理论依据是计算机科学中注明的局部性原理：

1
2

当一个数据被用到时，其附近的数据也通常会马上被使用
程序运行期间所需要的数据通常比较集中

（1）由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，
因此对于具有局部性的程序来说，预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。
（2）MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改)。linux 默认页大小为4K。

B-Tree利用了磁盘预读的机制

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个结点只需一次I/O。
假设 B-Tree 的高度为 h,B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3，也即索引的B+树层次一般不超过三层，所以查找效率很高）。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

B+树的优势

为什么InnoDB的索引使用B+树而不是B树:
（1）B+树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储data，所以一个节点可以存储更多的内节点，每个节点能索引的范围更大更精确。也就是说使用B+树单次磁盘IO的信息量相比较B树更大，IO效率更高。
（2）mysql是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链表指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而B树每个节点的key和data在一起，无法进行区间查找。

附:B树严格定义

3：所有叶子节点都出现在同一层，且叶子节点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)
4：每个非叶子节点包含有n个关键字信息(n，P0，K1，P1，K2，P2，……，Kn，Pn)，其中：
a) Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

比如，我们通过上面那张btree结构来查找29这个元素，查找过程为：
（1）根据根节点找到文件目录的跟磁盘块1，将其中的信息装入到内存中【磁盘IO操作第1次】
（2）此时内存中有两个文件名17,35和三个存储其他磁盘页面地址的数据（指针），根据算法我们发现17 < 29 <35，因此我们找到指针p2
（3）根据指针p2我们找到磁盘块3，并将其中信息装入到内存中【磁盘IO操作第2次】
（4）此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据（指针），根据算法我们发现26 <29<30，因为我们找到指针p2
（5）根据指针p2我们定位到磁盘块8，并将其中信息装入内存【磁盘IO操作第3次】
（6）此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。

本文整理自

以B tree和B+ tree的区别来分析mysql索引实现
由 B-/B+树看 MySQL索引结构
BTree和B+Tree详解
MySQL B+树索引和哈希索引的区别

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

区别

1. InnoDB 支持事务，MyISAM 不支持事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

2. InnoDB 支持外键，而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败；

3. InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。

4. InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；

5. InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

   

如何选择：

1. 是否要支持事务，如果要请选择 InnoDB，如果不需要可以考虑 MyISAM；

2. 如果表中绝大多数都只是读查询，可以考虑 MyISAM，如果既有读写也挺频繁，请使用InnoDB。

3. 系统奔溃后，MyISAM恢复起来更困难，能否接受，不能接受就选 InnoDB；

4. MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的。如果你不知道用什么存储引擎，那就用InnoDB，至少不会差。

本文整理自

Mysql 中 MyISAM 和 InnoDB 的区别有哪些？

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

mutex一般用于为一段代码加锁，以保证这段代码的原子性（atomic）操作，即：要么不执行这段代码，要么将这段代码全部执行完毕。

例如，最简单的并发冲突问题就是一个变量自增1：

1

balance = balance + 1;

表面看这是一条语句，可是在背后的汇编中我们可以看到，指令集操作过程中会引入中间变量来保存右边的值，进而这个操作至少会被扩充为：

1
2

int tmp = balance + 1;
balance = tmp;

这就需要一把互斥锁（mutual exclusive, mutex）将这段代码给锁住，使其达到任何一个线程“要么全部执行上述代码，要么不执行这段代码”的效果。这个用法可以表示为：

1
2
3
4
5

lock_t mutex;
...
lock(&mutex)
    balance = balance + 1;
unlock(&mutex);

那么，一个自然的问题便是，我如何实现上面的这个lock()函数呢？

乍一看这个问题是非常复杂的，特别是考虑到它能够被适用于各种代码的各种情况。但经过各种简化，这个lock()实现，可以通过几个test和set的组合得以实现。

例如，

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

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
    // 0: lock is available
    // 1: lock is held
    mutex->flag = 0;
}

void lock(lock_t *mutex) {
    while (mutex->flag == 1) {  // Test the flag.
        ;    // Wait the lock
    mutex->flag = 1;  // Set the lock, i.e. start to hold lock
}

void unlock(lock_t *mutex) {
    mutex->flag = 0;
}

我第一次看到这个算法的时候非常惊讶，一个本来极其复杂的问题就这么优雅地被解决了。它仅仅涉及到对条件的检验和变量的复制，然后整个问题就这么轻而易举地被攻破了。

当然，我并没能看到上述代码的“坑”，也即是必须依靠指令集级别的支持才能真正做到atomic。这同样说明了并发程序的困难，稍微不注意便会调入一个万劫不复的坑里，并且你还不知道哪里出错了。

上述极端优雅的代码，有一个隐藏的坑，那便是在lock()函数的实现里，while循环那一段其实是可以被乱入的。

假设thread A是第一个运行到此的线程，那么它得到的mutex->flag就肯定是0，于是它继续跳出循环往下运行，希望通过下面的mutex->flag = 1来持有锁，使得其它线程在检测while循环时为真，进而进入循环的等待状态。

可如果在A执行到这个赋值为1的语句之前，又有另外一个thread B运行到了这个while循环部分，由于mutex->flag还未被赋值为1，B同样可以跳出while，从而跟A一样拿到这把锁！这就出现了冲突。

那怎么办呢？仔细后可以发现，其实关键问题就在于：

• 对mutex->flag的检测
• 对mutex->flag的赋值

这两个操作必须是不被干扰的，也就是它必须是atomic的，要么这两段代码不被执行，要么这两段代码被不中断地完整执行。

这就需要借助CPU指令集的帮助，来保证上述两条语句的atomic操作，也即是著名的TestAndSet()操作。

1
2
3
4
5

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

CPU的指令集，并不需要支持繁复的各种atomic操作。仅仅支持上面这个函数，各种互斥加锁的情形，便都能够被涵盖。

此时，在回到我们最开始的那个优雅的lock()实现，就可以将其改造为：

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

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *lock) {
    // 0: lock is available
    // 1: lock is held
    mutex->flag = 0;
}

void lock(lock_t *mutex) {
    while (TestAndSet(&lock_t->flag, 1) == 1) {
        ;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

上述代码极其精巧。乍一看在lock()实现里不是还缺少一行mutex->flag = 1;么？可其实呢，它已经被整合到了TestAndSet()函数中。

这样的支持TestAndSet()的实现，便是最简单的spin lock，弹簧锁。之所以叫弹簧锁，那是因为在各类锁当中，弹簧锁就是最初的被投入工业使用的最简单的实现技术。

本文整理自

互斥锁mutex的简单实现

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

JDBC介绍

​ jdbc是java数据库连接(java DataBase Connectivity)技术的简称，由一组使用java语言编写的类与接口组成，可以为多种关系数据库提供统一访问

• 实现步骤

1. 1. 使用JDBC编程需要连接数据库，注册驱动和数据库信息
   2. 操作Connection，打开 Statement 对象 。
   3. 通过Statement执行SQL， 返回结果到ResultSet对象。
   4. 使用ResultSet读取数据，然后通过代码转化为具体的POJO对象。
   5. 关闭数据库的相关资源。

• 优点

​ 直接底层操作，提供了很简单、便捷的访问数据库的方法，跨平台性比较强。灵活性比较强。可以写很复杂的SQL语句。

• 缺点

​ 工作量相对较大。我们需要先连接，然后处理JDBC底层事务，处理数据类型。我们还需要操作Connection对象、Statement对象和ResultSet对象去拿到数据，并准确的关闭它们。

我们要对JDBC编程可能产生的异常进行捕捉处理并正确关闭资源。

ORM介绍

​ 由于JDBC存在的缺陷，所以我们在实际工作中很少使用JDBC进行操作数据库的编程。于是我们就提出了对象关系映射（Object Relational Mapping）简称 ORM，或者O/RM，或者 O/R mapping。

• 介绍

1. ORM模型就是数据库的表和简单Java对象（Plain Ordinary Java Object，简称POJO）的映射关系模型。
2. 它主要解决数据库数据和POJO对象的相互映射。我们通过这层映射就可以简单的把数据库表的数据转化为POJO。以便程序员更加容易的理解和应用Java程序.而且程序员一般只需要了解Java应用而无需对数据库进行深入的了解。此外，ORM模型提供了统一的规则使得数据库的数据通过配置便可轻易的映射到POJO上。

• 常用的ORM框架

1. Java系列：

​ Hibernate全自动需要写hql语句

​ Mybatis半自动自己写sql语句,可操作性强,小巧（前身iBatis）

​ Apache OJB

​ TopLink 是位居第一的Java对象关系可持续性体系结构 （待研究）

​ Jaxor ：是一个简单但功能强大的创建到关系映像层对象的工具。它允许开发者轻松地 在表中插入、更新、删除行，但也可被扩展为创建一个可扩展的映像层，这个层可创建一 个完全的域模型，透明地映射到数据库表

2. .Net系列：EF6与EFCore、Dapper

• 优点

目前我们接触（用）到比较多的是Hibernate和MyBatis。

MyBatis优点：

1. 易于上手和掌握。
2. sql写在xml里，便于统一管理和优化。
3. 解除sql与程序代码的耦合。
4. 提供映射标签，支持对象与数据库的orm字段关系映射
5. 提供对象关系映射标签，支持对象关系组建维护
6. 提供xml标签，支持编写动态sql。

Hibernate优点：

1. 消除了代码的映射规则，它全部被分离到XML或者注解里面去配置。
2. 无需再管理数据库连接，它也配置到XML里面。
3. 一个会话中，不要操作多个对象，只要操作Sesison即可。
4. 关闭资源只需要关闭一个Session即可。

• 缺点

MyBatis缺点：

1. sql工作量很大，尤其是字段多、关联表多时，更是如此。
2. sql依赖于数据库，导致数据库移植性差。
3. 由于xml里标签id必须唯一，导致DAO中方法不支持方法重载。
4. 字段映射标签和对象关系映射标签仅仅是对映射关系的描述，具体实现仍然依赖于sql。（比如配置了一对多Collection标签，如果sql里没有join子表或查询子表的话，查询后返回的对象是不具备对象关系的，即Collection的对象为null）
5. DAO层过于简单，对象组装的工作量较大。
6. 不支持级联更新、级联删除。
7. 编写动态sql时,不方便调试，尤其逻辑复杂时。
8. 提供的写动态sql的xml标签功能简单（连struts都比不上），编写动态sql仍然受限，且可读性低。
9. 若不查询主键字段，容易造成查询出的对象有“覆盖”现象。
10. 参数的数据类型支持不完善。（如参数为Date类型时，容易报没有get、set方法，需在参数上加@param）
11. 多参数时，使用不方便，功能不够强大。（目前支持的方法有map、对象、注解@param以及默认采用012索引位的方式）
12. 缓存使用不当，容易产生脏数据。

Hibernate缺点：

1. 全表映射带来的不便，比如更新时需要发送所有的字段。
2. 无法根据不同的条件组装不同的SQL。　
3. 对多表关联和复杂的SQL查询支持较差。需要自己写SQL，返回后，需要自己将数据组装到POJO中。
4. 不能有效支持存储过程。
5. 虽然有HQL，但是性能较差，大型互联网往往需要优化SQL，而Hibernate做不到。

• 框架选择

​ Hibernate作为Java ORM框架，它确实编程简易，需要我们提供映射的规则，完全可以通过IDE生成。同时无需编写SQL确实开发效率优于MyBatis。而且，它也提供了缓存、日志、级联、等强大的功能，但是Hibernate的缺陷也是十分的明显的。就是在多表关联复杂的SQL时，数据系统权限限制时，根据条件变化的SQL时。存储过程等使用场景。Hibernate十分不便。而性能又难以通过SQL来优化。所以Hibernate一般只适用于场景不太复杂的、性能要求不太苛刻的时候使用。

​ MyBatis 是一个灵活的、可以动态生成映射关系的框架，它几物可以替代JDBC。拥有动态列、动态表名，存储过程都支持。同时提供了简易的缓存（如(默认)一级缓存，还有二级缓存）、日志、级联。但是它的缺陷是需要你提供映射规则和SQL，所以它的开发工作量一般要比Hibernate略大一些。

​ 总结。你需要根据你的项目的实际情况去选择框架。MyBatis具有高度灵活、可优化、易维护等特点,所以目前还是myBatis比较合适我们。

JDBC,Mybatis性能比较（无事务）

• 测试向本机的数据库插入数据

JDBC：批量操作

MyBatis：

1. 批量处理（SQL拼接）代码如下

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

     Map<String,Object> param = Maps.newHashMap();
        param.put("recordList", recordList);
        recordDao.insertList(param);复制代码
<insert id="insertList" parameterType="java.util.Map">
        insert into test
        (aa,bb,cc,dd,ee,ff,gg,hh,ii)
        values
        <foreach collection="recordList" item="recordList" open="" close=""
                 separator=",">
            (
            null,
            #{recordList.aa,jdbcType=VARCHAR},
            #{recordList.bb,jdbcType=VARCHAR},
            #{recordList.cc,jdbcType=VARCHAR},
            #{recordList.dd,jdbcType=VARCHAR},
            #{recordList.ee,jdbcType=VARCHAR},
            #{recordList.ff,jdbcType=VARCHAR},
            #{recordList.gg,jdbcType=VARCHAR},
            #{recordList.hh,jdbcType=VARCHAR},
            #{recordList.ii,jdbcType=VARCHAR},
            )
        </foreach>
        ;
    </insert>

2. for 循环插入，一条条的执行插入

本文整理自

传统JDBC与ORM框架之间的性能比较

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

HTTP状态码分类

HTTP状态码由三个十进制数字组成，第一个十进制数字定义了状态码的类型，后两个数字没有分类的作用。HTTP状态码共分为5种类型：

HTTP状态码列表:

详细说明

众所周知，每一个HTTP响应都会带有一个状态码，不过对于很多开发者来说，平时使用最多的几个状态码无外乎就是200、400、404、500等。

那其他众多状态码该应用在何种场景中，什么时候应该使用哪些状态码就成为一个值得我们深入思考的问题了。即便在Facebook这样的公司中，那些聪明的开发者所构建的API也可能只返回200。对于目前的绝大部分服务端接口层设计都会遵循REST规范，而REST规范中推荐选用标准的HTTP 状态码作为返回值。

在笔者的来自微软的接口设计指南与来自于PayPal的RESTful API标准这两篇来自于PayPal与Microsoft的REST设计规范中都建议了部分合适的返回值，而在本文这部分主要是对于通用的HTTP状态码选择进行一些讨论。

目前HTTP状态码主要分为如下几类:

• 1xx:信息响应类，表示接收到请求并且继续处理
• 2xx:处理成功响应类，表示动作被成功接收、理解和接受
• 3xx:重定向响应类，为了完成指定的动作，必须接受进一步处理
• 4xx:客户端错误，客户请求包含语法错误或者是不能正确执行
• 5xx:服务端错误，服务器不能正确执行一个正确的请求

1xx

2XX/3XX

4XX

5XX

本文整理自

HTTP 状态码详解与选用

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

锁优化思路

最好的方式不加锁，如果必须加锁，可以从如下几个方面入手进行锁优化：

1
2
3
4
5

1. 减少锁持有时间
2. 减小锁粒度
3. 读写锁替代独占锁
4. 锁分离
5. 锁粗化

减少锁的持有时间

减少锁的持有时间，即减少锁内代码执行时间，可以通过减少锁内代码量实现，例如避免给整个方法加锁、将不需要加锁的代码移出去，例如：

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

public synchronized void doSomething() { 
    System.out.println("before");
    needLockCode(); 
    System.out.println("after");
}

//改为：

public void doSomething() { 
    System.out.println("before");
    synchronized(this){ 
        needLockCode(); 
    } 
    System.out.println("after");
}

或：

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

public void doSomething() { 
    synchronized(this){ 
        System.out.println("before");
        needLockCode(); 
        System.out.println("after");
    } 
}

//改为：

 public void doSomething() { 
    System.out.println("before");
    synchronized(this){ 
        needLockCode(); 
    } 
    System.out.println("after");
}

减小锁的粒度

减小锁的粒度，这个偏向于减小被锁住代码涉及的影响范围的减小，降低锁竞争的几率，例如jdk5的ConcurrentHashMap，ConcurrentHashMap不会为整个hash表加锁，而是将Hash表划分为多个分段，对每个段加锁，这样减小了锁粒度，提升了并发处理效果。

再如假设有对象object，如果加锁后，不允许对object操作，此时锁粒度相当于object对象，如果实际上object只有一个名为needLock字段可能会出现并发问题，此时将锁加在这个字段上即可。

读写锁替代独占锁

ReentrantLock和synchronized使用的是独占锁，无论是读或写都保证同时只有一个线程执行被锁代码。但是单纯的读实际上不会引起并发问题。尤其是对于读多写少的场景，可以将读和写的锁分离开来，可以有效提升系统的并发能力。

读写锁在同一时刻可以允许多个线程访问，但是在写线程访问时，所有的读线程和其他写线程都会被阻塞。读写锁维护了一对锁：读锁和写锁。一般情况下，读写锁的性能都会比排它锁好，因为大多数场景读是多于写的。

当执行读操作的时候，需要获取读锁，在并发访问的时候，读锁不会被阻塞；在执行写操作时线程必须要获取写锁，当已经有线程持有写锁的情况下，所有的线程都会被阻塞。读锁和写锁关系：

• 读锁与读锁可以共享
• 读锁与写锁互斥
• 写锁与写锁互斥

ReentrantReadWriteLock是提供了读锁和写锁：

1
2
3
4
5
6
7
8
9

public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable {
    ...
    /** Inner class providing readlock */
    private final ReentrantReadWriteLock.ReadLock readerLock;

    /** Inner class providing writelock */
    private final ReentrantReadWriteLock.WriteLock writerLock;
    ...
}

锁分离

在读写锁的思想上做进一步的延伸，如果对两个上下文互相不依赖、互相不影响的操作使用了同一把锁，这时候可以把锁进行拆分，根据不同的功能拆分不同的锁, 进行有效的锁分离。

一个典型的示例便是LinkedBlockingQueue，在它内部，take()和put()分别实现了从队列中取得数据和往队列中增加数据的功能，虽然两个方法都对当前队列进行了修改操作，但由于当前队列为链表实现，两个操作分别作用于队列的前端和尾端，从理论上说，两者并不冲突。

如果使用独占锁，那么同一时间两个操作不能同时进行，会因为等待锁资源而阻塞。但是两个操作实际上是不冲突的，这时候可以使take()和put()各自使用一把锁，提高并发效率。LinkedBlockingQueue中为两个操作分别准备了takeLock和putLock：

1
2
3
4
5
6
7
8
9
10
11

 1     /** Lock held by take, poll, etc */
 2     private final ReentrantLock takeLock = new ReentrantLock();
 3 
 4     /** Wait queue for waiting takes */
 5     private final Condition notEmpty = takeLock.newCondition();
 6 
 7     /** Lock held by put, offer, etc */
 8     private final ReentrantLock putLock = new ReentrantLock();
 9 
10     /** Wait queue for waiting puts */
11     private final Condition notFull = putLock.newCondition();

锁粗化

必要的时候，将被锁住的代码量变多、锁持有时间更长也是锁优化的方式，但优化结果一定要使整体的执行效率变的更好，例如：

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

for(int i = 0; i < 100; i++) {
    synchronized(lock) {
        needLockCode();             
    }
}

//改为：

synchronized(lock) {
    for(int i = 0; i < 100; i++) {
        needLockCode();
    }
}

改造后，尽管每个线程每次持有锁的时间变长了，但减少了每个线程请求和释放锁的次数，而请求和释放锁也是要消耗资源的。

虚拟机的锁优化

自旋锁与自适应自旋

由于挂起线程和恢复线程都需要转入内核态完成，给系统带来很大压力，同时，共享数据的锁定状态只会持续很短的一段时间，因此去挂起和恢复线程很不值得。因此，可以使线程执行一个自我循环，因为对于执行时间短的代码这一会可能就会释放锁，而线程就不需要进行一次阻塞与唤醒。

自旋等待不能代替阻塞，自旋本身虽然避免了线程切换的开销，但是会占用处理器时间，如果锁被占用时间短，自旋等待效果好；反之，自旋的线程只会白白浪费处理器资源；因此，要限制自旋等待时间，自旋次数默认值是10次，超过次数仍然没有成功获取锁，就挂起线程，进入同步阻塞状态。

自适应自旋更智能一些，它根据前一次在同一个锁上的自旋时间以及锁的拥有者的状态来决定自旋次数，如果对于某个锁的自旋很少有成功获得过锁，就不自旋了，避免浪费CPU资源。如果自旋等待刚刚成功获得过锁，并且持有锁的线程在运行，则认为此次自旋很有可能成功，就允许自旋更多的次数。

锁消除

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

有时候锁是开发者无意中涉及到的，例如对于下面代码：

1
2
3

public static String getStr(String s1, String s2) {
    return s1 + s2;
}

只进行了字符串的拼接，但其中的s1 + s2可能被虚拟机优化为：

1
2
3
4

StringBuffer sb = new StringBuffer();
sb.append(s1);
sb.append(s2);
return sb.toString();

而append()涉及了synchronized:

1
2
3
4
5
6

@Override
public synchronized StringBuffer append(String str) {
    toStringCache = null;
    super.append(str);
    return this;
}

append()中的锁就是sb对象，如果该对象在方法中new的话，sb对象就不会逃逸到方法以外，jvm认为此时不必要加锁，此处的锁就被安全的消除了。

锁粗化

原则上，我们在编写代码的时候，总是推荐将同步块的作用范围限制得尽量小——只在共享数据的实际作用域中才进行同步，这样是为了使需要同步的操作数量尽可能变小，如果存在锁竞争，那等待锁的线程也能尽快拿到锁。

但如果一系列操作频繁对同一个对象加锁解锁，或者加锁操作再循环体内，会耗费性能，这时虚拟机会扩大加锁范围来减少获取锁、释放锁的操作。具体可以看上文示例。

轻量级锁

轻量级锁是JDK6之中加入的新型锁机制，它名字中的“轻量级”是相对于使用操作系统互斥量来实现的传统锁而言的，因此传统的锁机制就称为“重量级”锁。首先需要强调一点的是，轻量级锁并不是用来代替重量级锁的，它的本意是在没有多线程竞争的前提下减少传统的重量级锁使用操作系统互斥量产生的性能消耗。

在代码进入同步块的时候，如果同步对象没有被锁定，虚拟机首先将在当前线程的栈帧中建立一个名为锁记录( Lock Record)的空间，用于存储锁对象目前的Mark Word的拷贝，虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针。如果这个更新动作成功了，那么这个线程就拥有了该对象的锁，并且对象 Mark Word的锁标志位(Mark Word的最后2bit)将转变为“00”，即表示此又对象处于轻量级锁定状态。

如果这个更新操作失败了，虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧，如果是说明当前线程已经拥有了这个对象的锁，那就可以直接进入同步块继续执行，否则说明这个锁对象已经被其他线程抢占了，如果有两条以上的线程争用同一个锁，那轻量级锁就不再有效，自旋失败后要膨胀为重量级锁，Mark Word中存储的就是指向重量级锁的指针，后面等待锁的线程也要进入阻塞状态。

轻量级锁能提升程序同步性能的依据是“对于绝大部分的锁，在整个同步周期内都是不存在竞争”，这是一个经验数据。如果没有竞争，轻量级锁使用CAS操作避免了使用互斥量的开销，但如果存在锁竞争，除了互斥量的开销外，还额外发生了CAS操作，因此在有竞争的情况下，轻量级锁会比传统的重量级锁更慢。

偏向锁

大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。如果说轻量级锁是在无竞争的情况下使用CAS操作去消除同步使用的互斥量，那偏向锁就是在无竞争的情况下把整个同步都消除掉，连CAS操作都不做了。

当锁对象第一次被线程获取的时候，虚拟机将会把对象头中的标志位设为“01”，即偏向模式。同时使用CAS操作把获取到这个锁的线程的ID记录在对象的Mark Word之中，如果CAS操作成功，持有偏向锁的线程以后每次进入这个锁相关的同步块时，虚拟机都可以不再进行任何同步操作（例如Locking、Unlocking及对Mark Word的Update等）。当有另外一个线程去尝试获取这个锁时，偏向模式就宣告结束。

也就是说，偏向锁会偏向第一个获得它的线程，只有当其它线程尝试竞争偏向锁时，偏向模式才会失效。偏向锁是为了避免某个线程反复执行获取、释放同一把锁时的性能消耗，即如果仍是同个线程去获得这个锁，偏向锁模式会直接进入同步块，不需要再次获得锁。

锁的作用效果

偏向锁是为了避免某个线程反复执行获取、释放同一把锁时的性能消耗，而轻量级锁和自旋锁是为了避免重量级锁，因为重量级锁属于操作系统层面的互斥操作，挂起和唤醒线程涉及到上下文切换,是非常消耗资源的操作。

锁获取过程

最终，锁的获取过程会是，首先会尝试轻量级锁，轻量级锁会使用CAS操作来获得锁，如果轻量级锁获得失败，说明存在多线程对锁资源的竞争。此时会会尝试自旋锁，如果自旋失败，最终只能膨胀为重量级锁。

除重量级锁外，以上锁均为乐观锁。

本文整理自

JAVA锁优化

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

hashCode简介

hashCode是 jdk 根据对象的值和状态算出来的一个 int 型数字，即对象的哈希码值，代表了该对象在内存中的存储位置。

顶级父类 Object 提供获取 hashcode 的方法，调用的是本地的方法；

1

public native int hashCode();

Java 中的 hash 值主要用来干什么的？

hash 值主要是用来在散列存储结构（HashMap、HashTable、HashSet 等等）中确定对象的存储地址的，提高对象的查询效率，

常见类的hashcode

string

阅读 String 源码来分析：

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

    public int hashCode() {
        int h = hash;// 主要是 String 对象是不可变的，可以使用一个变量存储起来，方便以后使用。
        if (h == 0 && value.length > 0) {
            char val[] = value;
// 计算每个字符的 ascii 参与到 hashcode 计算中，将前面计算的结果乘以 31 。
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

为什么要以 31 为权来计算 hashCode？

1. 因为 31 是素数，素数跟其他数相乘，更容易产生唯一性，所以 hash 冲突会小；

2. 相乘的时候，数字越大，结果也越大，很容易超出 int 值上限，31是一个大小适中的素数.

3. 为什么不是 17 ,23等等，参考StackOverflow上最高票的答案参考答案

   The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

   解释说，因为乘31可以方便地优化为移位和减法，实际计算的是(i << 5) - i。

Long

查看 Long.java 的 hashCode() 方法，

1
2
3

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

因为 Long 类型有 64 位，比 hash 的长度多了一倍，利用前 32 位 和后 32 位异或，尽可能的让更多的位置参与计算 hash 来保证唯一性。

重写 hashcode 和 equals

为什么要同时重写

首先了解默认情况下的 hashcode 和 equals 方法是什么样：

• hashcode 根据内存地址换算出来一个值(jdk5以前)；
• equals 判断对象的内存地址是否一样；

但是大多数情况下，我们是需要判断它们的值是否是相等的情况。

Object.hashCode的通用约定（摘自《Effective Java》第45页）

1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回 同一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。
2. 如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任一个对象的hashCode方法必须产生同样的整数结果。
3. 如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。

如果只重写了equals方法而没有重写hashCode方法的话，则可能会违反第二条：相等的对象必须具有相等的散列码（hashCode）。

比如我们用一个可变的对象作为 hashMap 的键，并且重写了 hashcode 和 equals 方法，当我把一对键值（可变对象为键）装进 hashMap 后，又去改变了键对象的某个属性（这个属性参与了 hashcode 的计算），然后就不能再用这个可变对象去操作已经插入到 hashMap 中的键值对了。

自定义hashCode

参考 IDEA 根据字段自动生成的 hashCode 和 equals 方法：

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

public class ObjectDemo {
    private String value1;
    private String value2;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true; 
        if (o == null || getClass() != o.getClass()) return false;

        ObjectDemo that = (ObjectDemo) o;

        if (value1 != null ? !value1.equals(that.value1) : that.value1 != null) return false; 
        return value2 != null ? value2.equals(that.value2) : that.value2 == null;
    }

    @Override
    public int hashCode() {
        int result = value1 != null ? value1.hashCode() : 0;
        result = 31 * result + (value2 != null ? value2.hashCode() : 0);
        return result;
    }
}

本文整理自

• Why does Java’s hashCode() in String use 31 as a multiplier?
• java为什么要重写hashCode和equals方法

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!