James Gray或JimGray,Jim是James的昵称

Transaction发明人,图灵奖

Gray进入数据库领域时,关系数据库基本理论已成熟,但各大厂RDBMS遇到一系列技术问题,数据库规模,数据库结构复杂,更多用户共享数据库情况下,如何保障完整性(Integrity)、安全性(Security)、并行性 (Concurrency),及故障后恢复 (Recovery)

主要手段

  • DB操作分为事务原子单位
  • 操作请求时,不同程度数据元素(字段、记录或文件)“加锁”(locking);操作完成后再“解锁 ”(unlocking)
  • 更新分两阶段提交。 WAL

隔离性目标是使并发事务执行效果与串行一致

但具体技术实现需在并发能力和串行化效果间进行平衡,很难两者兼顾

平衡结果会出现违反串行效果的异常现象(Phenomenon)

通常隔离级别提升伴随并发能力下降,两者负相关


ANSI SQL-92提出基于异常现象定义隔离级别的方法,没有将隔离级别与具体实现机制绑定

脏读,T1修改的数据项尚未提交即可被T2读到,而T1 Rollback,T2刚读取到的数据并没有实际存在

不可重复读,T1读取数据项,T2对其中的数据修改或删除且Commit成功。T1再次读取,得到T2修改后的数据或发现数据已删除。T1一个事务两次同样条件读取,结果集内容变更或结果集数量减少

幻读,T1查询条件获得结果集,T2插入符合条件的新数据,commit 成功后,T1再次执行同样查询,结果集增大


Jim Gray 等人论文“A Critique of ANSI SQL Isolation Levels”

Critique Isolation Levels

Critique提出了ANSI SQL-92两个问题

自然语言方式界定的异常现象并不严格,导致一些同质化的异常现象被遗漏

一些典型的异常现象并没有被涵盖进去,导致隔离级别存在明显缺失


Lost Update

create table account (balance int,name varchar(20)) ;

insert into account values(50,'Tom');
T1T2
begin;begin;
select balance into @bal from account where name=‘Tom’
select balance into @bal from account where name=‘Tom’
update account set balance = @bal -40 where name = ‘Tom’;
commit;
update account set balance = @bal - 1 where name = ‘Tom’;
commit;

T1、T2串行效果是两次扣减,分别为40和1,最终值为9,但并行的最终值为49,T2修改被丢失

Lost update实质是T1读数据,后该数据被T2修改并提交,T1基于已经过期数据进行再次修改,造成T2修改被覆盖

Read Skew

读偏序是RC会遇到的问题

如果数据项x与y存在一致性约束,T1先对读x,而后T2修改x和y后commit,T1再读y。T1得到的x与y不满足原有的一致性约束

MySQL默认RR,手工设置为RC并初始化数据

insert into account values(70,'Tom');
insert into account values(30,'Kevin');
T1T2
set session transaction isolation level read committed;
begin;
set session transaction isolation level read committed;
begin;
select * from account where name=’Tom’;
———————balance name70 Tom
select * from account where name=’Tom’;
———————balance name70 Tom
update account set balance = balance - 30 where name=‘Tom’;
update account set balance = balance + 30 where name=’Kevin’;
commit;
select * from account where name=‘Kevin’;
———————balance name60 Kevin
commit;

初始数据Tom与Kevin合计为100,T1两次读取得到账户合计为130,不符合之前的一致性约束

Critique给出新矩阵,比ANSI更完善也更贴合真实数据库产品

主流数据库考虑到串行化效果与并发性能的平衡,一般默认隔离级别都介于RC与RR之间,部分提供了Serializable

无论ASNI SQL-92还是Critique隔离级别都不能确保直接映射到实际数据库的同名隔离级别

SI&MVCC

快照隔离(SI,Snapshot Isolation)

Oracle、MySQL InnoDB、PostgreSQL普遍使用

MVCC通过记录数据项历史版本提升多事务访问并发处理能力

MVCC和锁都是SI的重要实现手段,也存在无锁的SI实现

Critique描述的 SI运作过程

T1开始获取Start Timestamp(ST),DB所有数据项的每个历史版本都记录着对应的时间戳Commit Timestamp(CT)

T1读的快照由所有数据项CT<ST且最近的历史版本构成,这些数据只是历史版本,不会再次被写锁定,不会发生读写冲突,快照内的读操作永远不会被阻塞

其他事务在ST后的修改,T1不可见

T1 commit瞬间获得一个CT,并保证大于此刻数据库中已存在的任意时间戳(ST或CT),持久化时会将这个CT将作为数据项的版本时间戳

T1写操作也体现在T1的快照中,可被T1内读操作再次读取。T1 commit后,修改会对那些持有ST大于T1 CT的事务可见

如果存在其他事务(T2),其CT在T1的运行间隔【ST,CT】之间,与T1对同样的数据项进行写操作,则T1 abort,T2 commit成功,这特性称First-committer-wins,可保证不出现Lost update

部分数据库会将其调整为First-write-wins,将冲突判断提前到write操作时,减少冲突的代价


不同DB对SI实现差别很大

PG将历史版本和当前版本一起保存通过时间戳区分,MySQL和Oracle都在回滚段中保存历史版本

MySQL的RC与RR均用了SI,如果当前事务(T1)读操作的数据被其他事务的写操作加锁,T1转向回滚段读取快照数据,避免读操作被阻塞

但是RC的快照定义与以上描述不同,也包括了T1执行过程中其他事务提交的最新版本

时间戳是生成SI的关键要素。单机系统中唯一时间戳比较容易实现,分布式系统在跨节点、跨数据中心甚至跨城市部署的情况下如何建立一个唯一时钟就成为一个非常复杂的问题

Serializable VS SSI

SI如此有效,甚至TPC-C benchmark中也没有出现任何异常现象,但事实上SI不能保证完整的串行化效果

Critique中指出,SI还无法处理A5B(Write Skew,写偏序)

Write Skew

写偏序也是一致性约束下的异常现象,两个并行事务都基于自己读到的数据集去覆盖另一部分数据集,在串行化情况下两个事务无论何种先后顺序,最终将达到一致状态,但SI隔离级别下无法实现

“黑白球”常常被用来说明写偏序问题

真正的串行化效果

早期数据库通过严格两阶段锁协议(S2PL,Strict Two-Phase Locking)实现了完全的串行化隔离(Serializable Isolation)

即正在进行读操作的数据阻塞对应写操作,写操作阻塞所有操作(包括读操作和写操作)

如阻塞造成循环将构成死锁,则需要进行rollback操作

S2PL的问题显而易见,在竞争激烈场景下,阻塞和死锁会造成数据库吞吐量下降和响应时间的增加,所以这种串行化无法应用于实际生产环境

直到SSI的出现,人们终于找到具有实际价值的串行化隔离方案

串行化快照隔离(SSI, Serializable Snapshot Isolation,也会被翻译为序列化快照)是基于SI改进达到Serializable级别的隔离性

SSI由Michael James Cahill在他的论文”Serializable Isolation for Snapshot Databases”中提出(

SSI保留了SI的很多优点,特别是读不阻塞任何操作,写不会阻塞读。事务依然在快照中运行,但增加了对事务间读写冲突的监控用于识别事务图(transaction graph)中的危险结构

当一组并发事务可能产生异常现象(anomaly),系统将通过回滚其中某些事务进行干预以消除anomaly发生的可能。这个过程虽然会导致某些事务的错误回滚(不会导致anomaly的事务被误杀),但可以确保消除anomaly

从理论模型看,SSI性能接近SI,远远好于S2PL

PostgreSQL在9.1版本中实现了SSI,首个支持SSI的商业数据库,验证了SSI的实现效果

CockroachDB也从Cahill的论文获得灵感,实现SSI并将其作为其默认隔离级别

SI/SSI已经成为主流数据库的隔离技术,尤其是后者的出现,无需开发人员在代码通过显式锁来避免异常,降低了人为错误的概率

ref

https://mp.weixin.qq.com/s/pweyiJdqgsnZDUkZu73Mbw