OceanBase内存事务引擎

OceanBase 是一个分布式可扩展的关系数据库,采用基线静态数据与动态增量 数据分离存储的架构设计。其内存事务引擎提供了动态数据的存储、写入和查询服务,用户写入的数据被存储在内存中称为memtable的数据结构中。memtable及其周边的事务管理结构共同组成了内存数据库引擎,来实现事务的ACID特性。在事务引擎中,通过多版本的并发控制技术实现读写相互不阻塞,实现只读事务满足“快照隔离”级别;通过经典的行锁方式实现多个写之间的并发控制,实现最高满足“已提交读”的事务隔离级别。

1. 概述

1.1 整体结构

整体结构

  • TableMgr:管理memtable(冻结的,活跃的)
  • SessionMgr:维护事务上下文
  • LockMgr:行锁管理
  • TransExecutor:事务流程执行器

事务执行流程

事务执行流程

  1. 预提交
    进行预处理,包括加锁,进行逻辑判断(比如insert/update/delte能否进 行),where条件的判断,数据读取等,并且将更新数据写入事务上下文

  2. 提交
    收到提交请求后(commit / autocommmit),由事务线程进行提交,包括申请事务版本号,提交对数据的修改,释放行锁等

  3. 发布
    单线程发布,同步redo log,原子性地发布当前事务

发布阶段完成后,事务对数据的修改才可以被后续开始的其他事务读取到

P.s. 应该只有autocommit可以提前释放锁?

memtable内存结构

数据以行为单位存储在memtable中,通过基于行的btree索引和hash单行索引提供查询功能,包括btree的范围索引和hash的单行索引。memtable与SessionMgr配合实现多版本并发控制,与锁管理器配合实现两阶段锁控制,后续将详细说明。

1.2 内存存储格式

RowCompaction

OB中存储的是对数据的修改记录,如上图所示,每次对行数据的更新记录都保存在一个变长的内存块里;读取时,需要将数据修改记录应用到基线数据上。随着链表变长,需要将多个块合并成一个块(RowCompaction),以减少读取时遍历链表的合并代价。

活跃memtable冻结之后,会和基线数据合并,其内存也可以被释放,因此这里采用了一种简单的内存管理策略,即只申请不释放;在活跃memtable被释放的时候,一次性释放内存。

为了节省内存使用,在上述变长内存块中,多列数据会压缩存储。

1.3 并发索引结构

内存引擎提供了针对行主键的单行和范围查询,实现了B+ Tree和Hash两个主键索引设计。

B+ Tree

B+ Tree结构

  1. 加锁

    • 从根节点开始遍历查询待插入位置,并在遍历过程中对路径上的节点加共享锁
    • 将叶子节点的共享锁升级为互斥锁,并拷贝当前的叶子节点,将新节点插入到拷贝出的节点中,如果节点不分裂,则原子的修改其父节点指针即可
    • 如果节点要分裂,那么其父节点的共享锁升级为互斥锁,拷贝父节点,然后将分裂后的节点插入拷贝出的父节点,如果父节点还需要分裂,则递归执行此操作
    • 需要注意的是,共享锁的获取方式是自顶向下,而互斥锁的获取方式是随着分裂自底向上,为了避免出现死锁,获取共享锁的方式为try_lock:共享锁加锁失败的情况下,将路径上已经加上的锁释放掉,然后重试。
  2. copy-on-write

    • 在修改B+ tree节点的过程中,除了原子的替换子节点的指针外,对节点的修改都需要先拷贝,然后在拷贝出的副本上操作;而在这个过程中,原节点可能还会被访问到,因此原节点不能立即删除,而是需要暂时保存直到确认不会被读取时再删除
    • P.s. 这里引入了多版本的概念,后续再写一篇文章介绍

Hash

  • 每个哈希桶一个bit的锁标记,1表示互斥占用
  • 为了实现简单,使用一整段连续内存(可能长达10G)
  • 每64KB块为一个初始化单位,使用一个byte来标记初始化标记和并发锁标记
  • 延迟初始化,当查询或插入涉及到某个64KB块的时候,再对这块内存调用memset,调用的时候要使用上述bit锁标记
  • P.s. 并发还是以哈希桶为单位,延迟初始化

2. 并发事务

OB使用MVCC技术实现只读事务与读写事务相互不阻塞,每次对行列数据的修改并非在数据的存储位置上就地修改,而是保存了一份以事务版本号标记的修改记录,在不考虑每日合并机制的情况下,可以认为在内存表中保存了每一次事务的修改历史,并且可以读取每一行的任意历史快照,但是实际上由于内存的限制,不可能一直保存数据的修改历史。因此,在每次每日合并时,截至每日合并之前的所有修改历史将被合并。

每日合并

2.1 事务隔离级别

OB的默认事务隔离级别为READ COMMITED,并且提供只读事务的SNAPSHOT READ。

  • READ COMMITED(简称RC)行为与Oracle一致
  • Oracle Statement-Level Read Consistency
  • Transaction Set Consistency: 并发更新同一行的情况,使用最新版本重试,避免lost update;重试若干次都失败的话,则返回执行失败

P.s. 另开一篇讨论隔离级别

2.2 多版本并发控制

事务版本号的分配

如之前所述,OB在内存里为每次事务修改保留了一份历史记录,这个记录有一个全局唯一的事务版本号,而MVCC提供的快照读特性需要保证读到任意一个有效历史时刻上的数据。

有些数据库在事务开始即分配了事务版本号,在事务执行过程中,写入的数据以这个版本号进行标记,这种情况基本可以保证事务版本号的递增,但是需要处理较早开始的事务分配了一个较小版本号却较晚提交的情况,例如:

  • 初始状态,A=1, B=1
  • start T1, set A = 2, 版本号1
  • start T2, set B = 3, 版本号2
  • commit T2
  • start T3, read A, 使用版本号2

对于上述情况,虽然T3读取时,A的版本号为1,比2更小,但需要过滤T1未提交的数据。这种版本号分配方式比较简单(MySQL使用了类似的分配方法),但是快照读取逻辑变得复杂,并且由于事务版本号顺序没有严格反映提交顺序,为备机与主机一致的事务性回放增加了处理难度。

因此OB的内存事务引擎采用在事务提交时分配版本号的方式,使事务版本号严格的按照提交顺序分配。这意味着需要在事务提交时,将分配的事务版本号写回到本次事务修改的所有数据上去。对比Oracle的实现,它需要考虑到向回滚块(undo block)写回事务版本号,可能需要将回滚块从磁盘加载回内存,并且当事务修改的行过多时,也会使得写回操作耗时过长,因此Oracle并没有在提交事务的时候立即将事务版本号写回所有的回滚块,而是维护了一个全局事务槽,在事务修改数据的过程中,将事务槽的地址保存在数据块中。在事务提交时,将事务版本号保存在事务槽中,然后采用延迟的方式将事务版本号写回数据块。

对于OB来说,由于所有的修改数据都在内存里,因此不存在写回和加载等问题,并且针对互联网应用的特点,暂时不支持长事务,所以并没有采用Oracle延迟写回的方法,而是在提交时遍历所有被修改的数据,在内存中将事务版本号写回。

多版本数据的存储

数据存储

  • 一次事务对一行数据的修改被保存为一个链表节点(数据块)
  • 行头结构保存了data list head/tail,以及undo list head
  • data list head/tail指向最近一次RowCompaction之后的数据块链表
  • undo list head指向了最近一次RowCompaction之前的数据块链表

如上图所示,版本5及以后的快照读,可以从data list head开始遍历;而对于之前的版本,则需要遍历undo list,找到对应的版本号。

事务提交与回滚

为了实现RC级别事务,满足ACID特性,主要需要以下几个特性:

  • 事务原子提交
  • 事务级别回滚
  • 语句级别回滚
  • 读取事务内未提交数据

为此,每个事务维护一个事务上下文,保存事务执行过程中未提交的数据、锁信息等。OB为每条语句产生一个执行计划,包括了必要的基线数据,操作类型(insert/update/delete/select/select for update)、待写入的数据、判断条件等。内存引擎执行这个计划的主要过程包括:

  • 查询活跃表中的动态数据,并对行加锁
  • 如果行不存在,则写入一个空的行头,然后加锁
  • 将修改数据写入链表节点
  • 事务提交时,回填事务版本号

事务上下文

针对此事务上下文结构,对应的操作过程如下:

  • 事务提交,获取事务版本号,提交,并更新全局事务版本号
  • 事务回滚,将事务上下文里结构整体释放掉
  • 语句级别的回滚,事务内单条语句执行失败需要保证事务状态回到语句开始之前,因此在事务上下文中要记录语句开始之前的状态,语句回滚时回滚到语句开始之前
  • 读取事务内未提交数据,除了遍历data list,还要遍历事务上下文中未提交的数据(需要将未提交数据的指针附在data list tail后)

2.3 两阶段锁与冲突调度

两阶段锁

OB使用经典的两阶段锁来处理并发的更新事务,即在事务过程中,加锁和解锁是两个互不重叠的阶段。事务中的DML语句在执行过程中,涉及到的行都将被加上互斥行锁。目前OB只支持RC隔离级别,不支持范围锁或者谓词锁。每行的行头使用4byte保存锁标志,最高位标记锁状态,其余31位标志持有锁的事务描述符(即锁的拥有者)。

锁冲突调度

与传统数据库的实现不同,OB内存引擎执行事务都是在内存中进行,没有IO操作,所以启动的线程数量一般不会超过CPU的数量。线程资源宝贵,因此不能出现线程阻塞,来等待某些事情发生或条件满足的情况。事务执行过程中可能会遇到锁冲突,为了避免线程陷入锁等待,将尝试加锁失败的请求回滚,放回任务队列等待重新执行,线程则继续处理后面的请求。

3. 事务持久化、恢复

3.1 批处理与提交

事务提交时,一般需要先写日志再提交。如果每次完成一个事务就写一次日志,而日志需要同步到磁盘,性能会比较差。所以,一般会将批量连续的一批事务日志一次刷到磁盘。常见的数据库一般通过日志缓冲区,加上一个定时工作的刷日志线程来完成这一功能。OB采用了另外一种方法,日志缓冲区如下图所示:

日志缓冲区

目前OB不支持大于2MB的事务,所以一个事务的所有操作日志可以在一个缓冲区内存储。写事务日志一般需要如下步骤:

  • 在事务缓冲区占位
  • 事务线程将事务操作数据序列化写到日志缓冲区
  • 由缓冲区最后一个完成写操作日志的事务线程负责将缓冲区发起写硬盘和同步备机的操作

此外,事务线程在填充完日志后,会判断当前的负载情况,如果负载较低,那么不管缓冲区是否已满,都会立即将缓冲区提交,以降低事务延迟。

在日志缓冲区的占位通过一个128位的组合起来的数字来确定:

struct  
{
  int64_t block_id;  // 缓冲区块编号,递增,循环使用
  int32_t offset; // 事务日志偏移量
  int32_t id; // 缓冲区块内部编号
}

使用这样的操作,在日志缓冲区的占位操作就可以使用一次CAS指令完成。在使用CAS之前要先判断当前的缓冲块空间是否足够存储要写入的日志:如果够,可以直接写该offset和id;如果不够,那么使用下一个缓冲区块,block_id加1,offset重置为0,id重置为1。然后用新的三元组原子替换之前的三元组,如果替换成功,则占位成功,如果替换失败,则重复之前的流程。

事务线程仅发起工作,将缓冲区块交给写盘的线程,发起异步网络请求;后续确认日志数据是否写完,是在写盘和网络操作的回调函数中处理。

3.2 并发事务回放

OB的主机以并行方式执行多个事务,备机通过回放操作日志追赶主机,经常会面临性能问题。为了保证事务完成的顺序性,回放很难做成并行的方式。OB的同步模式加上MVCC实现了备机的并发日志回放,保证主机即使以最大并发工作时,备机也可以追赶上主机。

并发日志回放

如图所示,读日志线程读取日志,解析成单独的事务,然后将每个事务打包成回放任务,交给回放线程。回放线程以消费者工作模式,只要拿到回放任务就进行回放操作,将操作日志中的信息写到内存表中。

回放线程操作memtable时,需要给回放的行加行锁,但不用两阶段锁策略,这样可以让操作同一行的事务并行回放。

由于使用MVCC机制,并发回放的顺序可以不同于事务提交的顺序。不过在memtable内部,保证链表内的数据是按照事务的版本有序的,即保证备机和主机是同样的memtable。

4. 性能优化

事务两阶段锁,在事务执行过程中加锁,事务回滚或者提交redo log后才释放锁,对于修改不同行的并发事务不存在冲突,这些并发的事务提交的redo log有机会组成一个group,一次IO写到磁盘。但是类似于秒杀减库存这种操作,可能有几十万人同时在线对一件商品下单,会产生同一行的严重的锁冲突。此时,热点行的更新操作退化成IO的串行化执行,只有提交redo log才释放锁。为此,OB进行了两点优化:

提前释放锁

对于autocommit事务,在日志缓冲区占位后,就可以立即释放行锁,使后续获取相同行锁的事务可以获取到锁开始预处理。这样修改同一行的并发事务虽然在预处理阶段仍然是串行的,但是在耗时最多的写redo log阶段有机会组成一个组一次提交,增加引擎的吞吐能力。

尽管释放了行锁,但是因为事务还没有提交,在没有提交redo log之前,是不会给客户端应答的。后续读取同一行的只读事务不会读取到未提交的的数据;而后续对相同行的修改则需要读取到未提交的数据,以保证在前一个事务修改的基础上进行操作,比如判断并扣减库存要在上一次扣减结果的基础上进行。

对于redo log提交失败的情况,和失败事务修改了同一行的事务也要被回滚。而只读事务因为不能读到修改,所以不受影响。对于select for update语句,要等待释放锁的的事务提交后才能读取,否则可能出现读取到的未提交数据,因为提交redo log失败而被回滚的风险。

热点行请求调度

提前释放锁解决了并发事务提交redo log的冲突,但是预处理阶段在并发压力大的情况下,处理锁冲突调度的代价仍然比较大。因此考虑到事务预处理既然要通过加锁达到串行化的目的,那么可以直接将修改同一行的事务请求调度到相同的线程排队处理,避免一次锁冲突调度的而开销。

此外,OB为一些经常使用到的全局对象,比如SchemaMgr,MemtableMgr等,做了一些优化。这些对象在平时只读,比较少的情况下会修改。使用CAS实现读写锁和引用计数,在CPU核心数量不多时性能比较好,但是随着CPU数量的增加,原子操作对全局共享变量的读写代价变得明显。

因此针对全局对象多读多写少的特性,OB实现了并发读写锁和引用计数,通过减小读锁代价,增加写锁代价来优化性能。即读锁的加锁解锁,引用计数的增加和减少,都只操作线程局部变量;要获取写锁时,则需要遍历所有的线程,对每个线程局部的读写锁都加上写锁;引用计数同理,要尝试释放对象时,要遍历所有线程局部的引用计数,确认都没有引用的情况下才释放对象,否则在每个线程局部打上标记,等减引用计数时再尝试释放对象。

Paper:
OceanBase内存事务引擎

flacro

Read more posts by this author.