多版本并发控制:PostgreSQL vs InnoDB

数据库   2009-11-07 22:15   阅读400   评论2  
字号:    
多版本并发控制技术被很多数据库或存储引擎采用,如Oracle,MS SQL Server 2005+, PostgreSQL, Firebird, InnoDB, Falcon, PBXT, Maria等等。新的数据库存储引擎,几乎毫无例外的使用多版本而不是单版本加锁的方法实现并发控制,可以说多版本已经成为未来的发展趋势。

虽然都是多版本,但不同的系统的实现却有很大不同。在开源数据库领域最负盛名的两个系统PostgreSQL和InnoDB的多版本实现就可谓有天壤之别。

一、PostgreSQL的多版本实现(基于8.4.1版本)
PostgreSQL采用堆+B+树索引(忽视R树、哈希、GiST等不常用的索引)的存储结构,堆与索引的存储模式不同。

堆中记录包含版本化信息,PostgreSQL不区分记录的最新版本或老版本,都存储在堆中。简单的说,堆中每条记录头上记录t_xmin和t_xmax两个属性,分别表示创建与删除这一版本的事务ID,另外记录t_ctid属性,表示该记录下一个更新的版本的RID,即记录的多个版本构成从最老到最新的单向链表(见HeapTupleHeaderData结构)。DELETE一条记录时,设置t_xmax,并不将记录真正删除;UPDATE一条记录时,也不直接更新,而是插入一个新版本,对原来被更新的版本,将其t_xmax设为当前事务ID,设置其t_ctid指向新版本。

有了这些信息还不够,为了判断版本的可见性,还需要两个东西,一是事务提交日志,二是事务快照。事务提交日志对每个事务使用两个bit,记录事务是活跃、已提交还是已回滚。事务快照在事务开始时分配,其中最重要的信息是当时活跃事务的列表(见SnapshotData结构)。

有了这些东西,系统可以判断一个版本是否可见。判断过程比较复杂,不过从简单的原理上说,系统先通过判断t_xmin是否在全局活跃事务列表中、是否在事务快照活跃事务列表中、根据事务提交日志判断事务是提交还是回滚了等来判断t_xmin事务是否在事务开始时已经提交;然后用类似的方法判断t_xmax是否在事务开始时已经提交。如果t_xmin在事务开始时没有提交则不可见;如果t_xmin在事务开始时已经提交而t_xmax没有,则可见;如果t_xmin和t_xmax在事务开始时都已经提交了则不可见。(详细过程见HeapTupleSatisfiesMVCC、TransactionIdDidCommit、XidInMVCCSnapshot等函数)。

索引中则不包含版本信息。一般情况下,记录的所有版本都在索引中存在对应的索引项。举个例子,如果一个表有三个索引,更新一条记录时,不但在堆中会插入一个新版本,新版本对应的索引项也要插入到三个索引中,即使这次更新可能没有更新某些索引的属性(见ExecUpdate函数)。在PostgreSQL 8.3中引入了HOT(Heap-Only-Tuple)技术,如果新老版本在同一页面,并且UPDATE没有更新任何索引属性,则不插入新版本对应的索引项。

由于索引没有版本信息,进行索引扫描时,即使查询所需所有属性在索引中都存在,也需要从堆中取出对应的记录判断是否可见(见index_getnext函数)。

事务提交或回滚时操作简单,除事务提交时要写出事务外,只需要更新事务提交日志中对应的事务状态。也就是说回滚时并不需要将事务所作的操作从物理上清理掉,只要将事务状态设为已经回滚,则该事务产生的版本对其它事务自然就不可见了。

老旧的不再需要的版本,即不会被将来的任何事务见到的版本的清理是通过VACUUM实现的。由于新老版本混杂在一起,进行VACUUM时本质上是需要扫描所有数据。8.4版中引入了Visibility Map技术,用来在VACUUM时跳过那些肯定不包含老旧版本的页面,但如果系统更新频繁且离散,这一技术就派不上大用场。在线的VACUUM只能清理页面中的老旧版本,但不能缩减表占用的空间,其实是产生碎片。要缩减表空间时的VACUUM会锁住表导致期间表不能被更新。

二、InnoDB的多版本实现(基于MySQL 5.1.33版本带的InnoDB)
InnoDB采用索引组织表的存储结构,没有堆,记录存储在主键索引中,其它索引称为二级索引,其中每个索引项都包含所对应记录的主键。主键索引与二级索引的存储格式也不同。

主键索引拥有版本化信息,但与PostgreSQL不同,一般情况下InnoDB的主键索引中只存储记录的最新版本,旧版本的信息则集中存储在回滚段中,只有主键被更新时才需要同时存储多个版本在主键索引中。主键索引记录的头上包含有6字节的事务ID与7字节指向回滚段中旧版本的指针(见MySQL手册)。DELETE时只是标记而不真正删除。UPDATE时进行本地更新,并将前像写到回滚段中。

存在与PostgreSQL中事务快照类似读视图,也记录了事务开始时的活跃事务列表(见read_view_struct结构),但不需要PostgreSQL中的事务提交日志。根据读视图和记录头上的事务ID,可以判断出一个版本在事务开始时是否已经提交,即是否可见。如果存储在主键索引中的记录不可见,则根据指向回滚段中旧版本的指针找到旧版本信息,构造出旧的记录。回滚段采用的是append-only的日志型存储,记录的旧版本信息并不是一条完整的记录,而只是被更新的属性的前像。回滚段中的旧版本信息中也包含更旧的版本的位置,即版本链表是从新到旧的。

由于没有事务日志表示事务是否回滚,在事务回滚时必须清理该事务所进行的修改,插入的记录要删除,更新的记录要更新回来(见row_undo函数)。事务提交时则无需处理。

二级索引中的每个索引项并没有版本化信息。但在页面头记录了对该页面操作的事务的ID的最大值,通过这一值可以判断页面中是否可能包含不可见的数据,如果是,则需要访问主键索引判断可见性。否则,可以直接从索引中获取查询所需属性。二级索引中可能存储一条记录的多个版本对应的索引项,如果UPDATE操作更新了某个索引的属性,则类似于PostgreSQL,插入新索引项到二级索引中,老索引项并不删除。但没有被UPDATE操作更新的索引则不需要插入新索引项。

系统使用一个后台线程不时处理回滚段,在需要时清理由于DELETE、二级索引或主键索引中由于主键被更新而产生的老旧版本,这一过程称这purge。如果UPDATE没有更新索引,则不会带来purge开销。

三、我的评价
PostgreSQL与InnoDB的多版本实现最大的区别在于最新版本和历史版本是否分离存储,PostgreSQL不分,InnoDB分。

PostgreSQL的这种设计被其最初的设计者Mike Stonebraker称为no-overwrite的设计,在设计了PostgreSQL几年之后他的一篇回顾性论文《The Implementation of Postgres》 (PostgreSQL早期叫Postgres)中,Stonebraker指出当初这样设计的主要原因是寻求与当时已经广泛使用的WAL模式不同的存储机制,有点为了创新而创新的意思。这一设计有两大好处:一是事务回滚时无需复杂处理,非常快;二是可以查询以前的历史数据。还有一个可能的好处是可以实现数据即日志,即更新时只要更新数据就行了,不需要再写日志来描述做了什么更新。但要使这个好处实现,需要有一种持久的,并且随机写具有与顺序写类似性能的存储介质才行,因为为了保证事务提交后的持久性,需要写出被事务更新的数据,而这些数据可能是离散的。WAL系统则不同,事务提交时只需要写日志就行了,而日志是顺序写入的。当前的硬件环境并不是这样,因此PostgreSQL中仍然还要写日志,只不过不需要写UNDO日志,只要REDO日志就行了。

最新的PostgreSQL与当初Stonebraker的设计已经有了很大改进,比如HOT技术减少了索引中的版本数,Visibility Map技术加快了VACUUM,记录头部结构也更紧凑。但no-overwrite的设计原则仍然没变。

相对于InnoDB,PostgreSQL的优势似乎主要的只有一条:事务回滚可以立即完成,无论事务进行了多少操作。查询以前的历史数据的功能并不常用,在目前的PostgreSQL中也并不实用。

PostgreSQL的主要劣势在于
1、最新版本和历史版本不分离存储,导致清理老旧版本需要作更多的扫描,代价更大;
2、UPDATE不是本地更新,会产生老旧版本需要清理。与之相对的是InnoDB只有在事务回滚时才需要清理老的记录数据。而事务回滚是罕见的;
3、只要有一个索引属性被更新,或者新版本的记录与原版本不在同一页面,就要插入所有索引的新版本索引项;
4、堆占用的空间不能通过在线的VACUUM回收,在线VACUUM会产生很多碎片(这也是由于使用了堆而不是索引组织表导致的);
5、由于索引中完全没有版本信息,不能实现Coverage index scan,即查询只扫描索引,直接从索引中返回所需的属性。与之相对的是InnoDB中二级索引页头记录的最近修改该页的事务ID信息可以在大部分情况下实现Coverage index scan。Coverage index scan是应用中经常使用的优化技巧,PostgreSQL不支持这个对提升系统性能带来很大限制,因为索引扫描是顺序访问,去访问堆则很可能变成乱序访问,性能可能相差百倍;
6、判断版本可见性更复杂,开销更大。PostgreSQL比InnoDB在判断可见性时,需要增加访问事务提交日志的操作,事务提交日志每个事务需要分配两个bit,对高更新负载的系统会占用较大空间,这时要么事务提交日志回占用大量内存,要么判断可见性时就可能产生额外的IO。对比PostgreSQL中判断可见性的函数HeapTupleSatisfiesMVCC和InnoDB中判断可见性的函数read_view_sees_trx_id,可以容易看出这两者的复杂度不可同日而语。

InnoDB的主要劣势在于事务回滚时需要清理事务所作的所有修改,因此使用InnoDB时要避免使用超大型事务,否则回滚可能超慢无比。

评论(2)
阅读(400)