跳转至

本篇文章来自 OceanBase 内部论文分享

本篇文章分享的论文是《High-Performance Concurrency Control Mechanisms for Main-Memory Databases》,该论文介绍了微软SQL Server内存数据库Hekaton所使用的并发控制算法原型,提出了一种无锁的乐观并发控制以及一种无锁的悲观并发控制方法,最终Hekaton采用的是其中的乐观并发控制方法,其也是第一个在生产中将OCC落地的数据库。欢迎感兴趣的同学一起交流学习~

Background

本篇论文讨论内存数据库(Main-Memory Database)中MVCC的设计。

Main-Memory Database

产生背景: - 服务器内存大小不断增加(TB级) - 服务器处理器核数不断增加 - 内存价格持续下降

特点: - 表数据完全存在内存中,无需从磁盘读取 - 进行针对性优化,如无锁结构、无锁并发控制方法等 - 性能优异

SQL Server Hekaton

集成在SQL Server中针对内存数据以及OLTP负载进行优化的数据库引擎。 优化点: - 优化内存索引 - 无锁结构 - 解释执行

Hekaton Concurrency Control Mechanism

论文介绍了Hekaton高性能事务并发控制算法的原型方法,基于事务不阻塞的原则以及MVCC技术,介绍了一种无锁的多版本悲观并发控制(PCC)以及一种无锁的多版本乐观并发控制(OCC)策略,并实现了面向内存优化的单版本加锁基线方案,在不同场景对这三种方法进行了测试与比较。

这里的事务不阻塞不是说永远不等待,是说不等锁。 不阻塞的好处是会有更少的上下文切换。

MVCC Storage Engine

存储和索引

设计原则

避免等待,设计为lock-free

论文以 lock-free hashtable index为例,介绍并发控制策略,也可用于trees以及skip list等顺序索引结构中。

memory storage engine prototype

Record

  • 包含Name、Amount两列
  • 包含Begin、End字段,存储时间戳或事务id,代表该版本有效时间范围
  • 相同hash bucket版本通过指针相连,从旧到新
  • 与原型基本结构相同
  • 增加将相同key的version连接的指针
  • 增加了一个无锁B-tree(Bw-tree)用于范围查询,叶子节点指向第一个版本
  • 可同时存在多个hash index(见附录)

hekaton storage engine

事务执行

  1. Active:事务创建,获取开启时间戳
  2. Normal processsing phase:事务执行。
  3. Preparation phase:若commit,则将新version以及delete版本相关信息写redo log并等待日志持久化
  4. Postprocessing phase:commit成功则替换新旧版本中事务ID为事务end时间戳;abort则将事务ID替换为infinity
  5. Transaction terminated:旧版本通过garbage colloctor

事务状态图

版本可见性

RT为事务T读取时间,

场景一、Begin与End都为时间戳

TBegin <= RT < TEnd则可读

场景二、Begin为 TB 事务ID

TB状态 TB的结束时间戳 事务T检查版本V的记录是否可见
Active 未设置 只有TBeigin=T并且V的结束时间戳是infinity才可见
Preparing TS V的开始时间戳是TS但是V还没有提交。使用TS作为V的开始时间戳来检测可见性
Committed TS V的开始时间戳就是TS
Aborted 不相关 忽略,这是一个垃圾版本
Terminated
或没找到
不相关 重新读取V的Begin字段

场景三、End 为 TE 事务ID

TE状态 TE的结束时间戳 事务T检查版本V的记录是否可见
Active 未设置 TE=T就可见
Preparing TS V的结束时间戳会在提交时变成TS。如果TS>RT,就可见
Committed TS 使用TS做可见性判断
Aborted 不相关 V可见
Terminated
或没找到
不相关 重新读取V的结束时间戳字段

版本更新

事务只允许更新最新版本V: - V的结束时间戳字段End是infinity - V End 字段=TE事务,事务TE Aborted - V End 字段=TE事务,事务TE是Active或Preparing,产生写写冲突,采用first-write-win策略,事务终止

Commit 依赖

如果T1必须在T2提交后才能提交,那就认为T1依赖T2: - 提前读 - 提前忽略

每个事务增加: - CommitDepCounter:commit依赖事务数 - AbortNow:是否需要abort - CommitDepSet:依赖于本事务commit的事务ID

如果事务T2提交成功,就将T1 的 CommitDepCounter 减1并唤醒它。 如果事务T2 Abort,那就将 T1 的AbortNow置为1。

Commit依赖将所有的等待步骤都推迟到了Commit阶段。 事务在commit之前很可能不需要等待,因为很可能它依赖的事务也都提交了。 也免去了死锁问题,总是年轻事务等待年老事务。

Optimistic Concurrency Control

事务维系数据集合

串行化级别: - ReadSet: 所读版本 - ScanSet: 重复scan操作所需要的信息 - WriteSet: 新旧版本指针

Normal Processing Phase

包含Index Scan定位对应版本以及读/写。 可串行化级别下,使用事务开始时间作为读操作TS。

事务流程图

  1. Start Scan: 执行scan操作,记录scan信息
  2. Check Predicate: 谓词检查
  3. Check visibility: 可见性判断,同时添加commit依赖
  4. Read Version: 读数据,记录指针到ReadSet
  5. Check Updatability: 确定版本可以更新;可提前更新,前提是该版本的事务已经完成normal processing
  6. Update Version: 执行更新,插入新版本,旧版本end修改为事务ID(失败就abort),写入WriteSet
  7. Delete Version: 修改旧版本end字段为事务ID,记录其指针到WriteSet

事务流程图2

PreCommit

  • 获取事务end ts(commit ts)
  • 设置事务状态为Preparing
  • 进入Preparation phase

Preparation Phase

  1. Read validation:
  2. 可重复读检查。重新扫描ReadSet,确认版本仍然可见
  3. 幻读检查: 重新执行ScanSet中的扫描,检查是否有新版本

  4. Wait for commit dependencies

  5. 等待所有依赖事务提交, CommitDepCounter=0
  6. 未通过或者AbortNow=1,就abort,进入 postprocessing phase

  7. Logging

  8. 将创建的新版本、删除版本的信息写入日志

设置事务状态:aborted/committed

Postprocessing Phase

成功commit就把TS写到旧版本end字段和新版本的begin字段。 如果abort就把WriteSet中的新版本end字段设置为infinity,新版本start字段设置为infinity。 这里的abort动作不会阻塞其它事务。

Low Level Isolation

Repeatable read

不需要做幻读检查。读操作使用事务开始时间。

Snapshot Isolation

不做可重复读检查与幻读检查,使用事务开始时间作为读操作时间戳。

Read Committed

不做可重复读检查与幻读检查。读操作使用当前时间。

Read-only Transaction

SI 或者 RC隔离级别性能更好

Pessimistic Concurrency Control

事务维系数据集合

串行化级别: - ReadSet: 事务读到的版本数据 - BucketSet: 访问上锁的bucket集合 - WriteSet: 新旧版本指针

Lock Types

Record Lock

  • 保证可重复读
  • 只对最新版本加锁
  • 使用Record End 字段实现(64 bits)

记录锁

Bucket Lock(Range Locks)

  • 避免幻读
  • 存储于hash bucket中,扫描的时候上锁

数据结构:

LockCount: 上锁的数目
LockList: 加锁的事务

Eager update & Wait-For Dependencies

可串行化场景下,传统的多版本加锁方法更新/删除某一行,下面的场景会导致阻塞: - 行已经加了read lock - Bucket 已经加锁

Eager Update

允许对有read lock和bucket lock的bucket进行update。

但是锁释放之前不允许precommit 进入preparing阶段。 还需要添加wait-for依赖。

Wait-For Denpendencies

一个事务有以下结构:

WaitForCounter: 事务依赖的的个数
NoMoreWaitFors: 不允许再添加wait-for依赖
WaitingTxnList: 依赖当前事务结束的事务集合

Wait-For类型: - Read Lock Denpendency - Bucket Lock Denpendency

Read Lock Denpendencies

一个事务TU想要对版本V更新或删除,但是V已经有了read lock: - 将TU的事务ID写入V的 WriteLock 字段 - ReadLockCounter > 0,TU WaitForCounter加1

事务TR对V加读锁: - NoMoreReadLocks=true 或 ReadLockCount=max_value,TR abort - ReadLockCounter > 0,将其加1 - 若已存在事务TU添加的write lock,且TR为第一个读锁,检查TU NoMoreWaitFor,若true,abort,否则强制TU等待TR(添加wait-for依赖)

事务 TR 对版本 V 释放read lock - 不存在write lock,直接将ReadLockCounter减1 - 存在write lock 且 ReadLockCounter > 1,同上 - 存在write lock 且 ReadLockCounter = 1, ReadLockCounter置为0,并将其NoMoreReadLocks置为1,TU WaitForCounter减1避免后续read lock进一步阻塞TU commit

Bucket Lock Denpendencies

允许Bucket提前插入,但需要上锁事务完成,才能进行precommit,通过添加wait-for依赖实现。

TU在Bucket B插入/删除新版本: - B不存在Bucket lock,直接上锁事务维系结构 - B存在Bucket lock - TU NoMoreWaitFors=true,TU abort - TU NoMoreWaitFors=false,对B LockList事务添加wait-for依赖

这时是TU给自己加了一个依赖(Wait-For Denpendency)。

事务TS scan Bucket B,发现满足查询条件但不可见版本V,且更新其事务TU为Active,为避免幻读,需添加wait-for依赖: - TU NoMoreWaitFors=true,TS abort - TU NoMoreWaitFors=false:TU添加到自身WaitingTxnList;将TU WaitForCounter加1

这时是TS给TU添加依赖。

Normal Processing Phase

阶段/控制策略 OCC PCC
Start Scan 记录Scan信息到ScanSet(Serializable) 对Scan的Bucket加锁,放入BUcketLockSet(Serializable)
Check Predicate 条件检查 条件检查
Check Visibility 可见性判断,commit 依赖条件添加 与OCC相同,但是需要添加Wait-For依赖(Serializable)
Read Version 读版本指针存入ReadSet(Serializable、RR) 添加read lock(Serializable、RR)
Check Updatability 可更新检查,commit依赖添加 与OCC相同
Update Version 更新,加入WriteSet 更新,添加wait-for依赖
Delete Version 删除,加入WriteSet 删除,添加wait-for依赖
Process End Precommit wait-for等待,precommit,释放read/bucket lock

Preparation Phase

不需要做Read Validation。 直接等待commit denpendencies。 然后记录日志。

Postprocessing Phase

与乐观并发控制一致,通过修改版本的begin、end字段,隐式释放写锁。

Experimental Results

实验环境

  • 2-socket CPU,共12核24线程,NUMA架构,访问remote memory比local memory慢30%
  • Log异步刷盘,组提交避免IO带宽成为瓶颈
  • 测试0 - 24线程,24线程CPU利用率最高,加线程吞吐下降

实现面向内存优化的单版本加锁(1V)方案作为基线,测试不同场景1V、OCC(MV/O)以及PCC(MV/L)的表现。

同构负载-RC

低竞争: - 多版本管理以及垃圾回收开销,吞吐不如1V - MV/L 比 MV/O慢30%,依赖追踪以及锁的额外写导致内存流量增加

高竞争: - 热点数据访问cache同步导致核间流量大 - MV/O表现最好

Higher Isolation Level

固定24线程,改变隔离级别: - 加锁方式,RR级别损失很小<2%;MV/O 可重复读检查,损失8% - Serializable:1V > MV/L > MV/O - MV/O需要承担更多隔离级别造成的性能损失

异构负载—短只读事务影响

低竞争: - 只读比例增加,gap减小——多版本以及垃圾回收代价减小 - 绝大多数只读,MV比1V好,纯只读MV相同,1V略差

高竞争: 80%是只读,MV比1V高73%以及63%——MV只读不影响写

异构负载—长只读事务影响

存在长事务时更新吞吐: - 存在1个长事务,1V下降75%,MV下降5%,MV为1V两倍 - 50%长事务,MV为1V 80倍

存在长事务时读吞吐: MV优于1V

Conclusion

  • 可在获取锁不成为瓶颈的情况下有效的实现1V-Lock方式
  • 1V-Lock方式在短事务、低竞争下表现好,但不同场景适应性很差
  • 高竞争以及存在长事务时MVCC优于1V-Lock
  • MVCC-O表现比MVCC-P好

悲观并发控制:访问数据时加锁,有可能需要等待锁释放 乐观并发控制:假设数据一般不会造成冲突,只在事务提交时进行冲突检测

最终Hekaton所采用为其中的乐观并发控制(OCC)方法。而基于磁盘的数据库通常采用悲观并发控制(PCC)方法,其解释原因如下: - 在对数据update时进行冲突检测(写写冲突) - 假设前提不同: - 基于磁盘的PCC事务tx1 等到tx2 回滚时才能继续,tx2 commit产生conflict error(假设tx2会提交失败) - 基于内存的PCC事务tx1 直接产生conflict Error(假设tx2会提交成功)

Main-Memory Database Concurrency Control Mechanisms

Main-Memory 数据库 并发控制方法 支持隔离级别
Microsoft Hekaton MVCC-O(lock-free) Serializable, RR, SI, RC(single stmt)
Oracle TimesTen Single-version + multiple-lock Serializable, RC
SAP HANA MVCC-P(lock) Serializable, SI, RC
IBM SolidDB Single-version + multiple-lock RR, RC
VoltDB Deterministic Concurrency Control Serializable

References

附录

Bw树