更新時(shí)間：2012-04-20
多版本并發(fā)控制技術(shù)已經(jīng)成為未來數(shù)據(jù)庫的發(fā)展趨勢。目前，多版本并發(fā)控制被很多數(shù)據(jù)庫或存儲(chǔ)引擎采用，如Oracle，MS SQL Server 2005+, PostgreSQL, Firebird, InnoDB, Falcon, PBXT, Maria等等。新的數(shù)據(jù)庫存儲(chǔ)引擎，幾乎毫無例外的使用多版本而不是單版本加鎖的方法實(shí)現(xiàn)并發(fā)控制。
雖然都是多版本，但不同的數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)卻有很大不同。在開源數(shù)據(jù)庫領(lǐng)域最負(fù)盛名的兩個(gè)系統(tǒng)PostgreSQL和InnoDB的多版本實(shí)現(xiàn)就可謂有天壤之別。
一、PostgreSQL的多版本實(shí)現(xiàn)(基于8.4.1版本)
PostgreSQL采用堆+B+樹索引（忽視R樹、哈希、GiST等不常用的索引）的存儲(chǔ)結(jié)構(gòu)，堆與索引的存儲(chǔ)模式不同。
堆中記錄包含版本化信息，PostgreSQL不區(qū)分記錄的最新版本或老版本，都存儲(chǔ)在堆中。簡單的說，堆中每條記錄頭上記錄t_xmin和t_xmax兩個(gè)屬性，分別表示創(chuàng)建與刪除這一版本的事務(wù)ID，另外記錄t_ctid屬性，表示該記錄下一個(gè)更新的版本的RID，即記錄的多個(gè)版本構(gòu)成從最老到最新的單向鏈表（見HeapTupleHeaderData結(jié)構(gòu)）。DELETE一條記錄時(shí)，設(shè)置t_xmax，并不將記錄真正刪除；UPDATE一條記錄時(shí)，也不直接更新，而是插入一個(gè)新版本，對原來被更新的版本，將其t_xmax設(shè)為當(dāng)前事務(wù)ID，設(shè)置其t_ctid指向新版本。
有了這些信息還不夠，為了判斷版本的可見性，還需要兩個(gè)東西，一是事務(wù)提交日志，二是事務(wù)快照。事務(wù)提交日志對每個(gè)事務(wù)使用兩個(gè)bit，記錄事務(wù)是活躍、已提交還是已回滾。事務(wù)快照在事務(wù)開始時(shí)分配，其中最重要的信息是當(dāng)時(shí)活躍事務(wù)的列表（見SnapshotData結(jié)構(gòu)）。
有了這些東西，系統(tǒng)可以判斷一個(gè)版本是否可見。判斷過程比較復(fù)雜，不過從簡單的原理上說，系統(tǒng)先通過判斷t_xmin是否在全局活躍事務(wù)列表中、是否在事務(wù)快照活躍事務(wù)列表中、根據(jù)事務(wù)提交日志判斷事務(wù)是提交還是回滾了等來判斷t_xmin事務(wù)是否在事務(wù)開始時(shí)已經(jīng)提交；然后用類似的方法判斷t_xmax是否在事務(wù)開始時(shí)已經(jīng)提交。如果t_xmin在事務(wù)開始時(shí)沒有提交則不可見；如果t_xmin在事務(wù)開始時(shí)已經(jīng)提交而t_xmax沒有，則可見；如果t_xmin和t_xmax在事務(wù)開始時(shí)都已經(jīng)提交了則不可見。（詳細(xì)過程見HeapTupleSatisfiesMVCC、TransactionIdDidCommit、XidInMVCCSnapshot等函數(shù)）。
索引中則不包含版本信息。一般情況下，記錄的所有版本都在索引中存在對應(yīng)的索引項(xiàng)。舉個(gè)例子，如果一個(gè)表有三個(gè)索引，更新一條記錄時(shí)，不但在堆中會(huì)插入一個(gè)新版本，新版本對應(yīng)的索引項(xiàng)也要插入到三個(gè)索引中，即使這次更新可能沒有更新某些索引的屬性（見ExecUpdate函數(shù)）。在PostgreSQL 8.3中引入了HOT（Heap-Only-Tuple）技術(shù)，如果新老版本在同一頁面，并且UPDATE沒有更新任何索引屬性，則不插入新版本對應(yīng)的索引項(xiàng)。
由于索引沒有版本信息，進(jìn)行索引掃描時(shí)，即使查詢所需所有屬性在索引中都存在，也需要從堆中取出對應(yīng)的記錄判斷是否可見（見index_getnext函數(shù)）。
事務(wù)提交或回滾時(shí)操作簡單，除事務(wù)提交時(shí)要寫出事務(wù)外，只需要更新事務(wù)提交日志中對應(yīng)的事務(wù)狀態(tài)。也就是說回滾時(shí)并不需要將事務(wù)所作的操作從物理上清理掉，只要將事務(wù)狀態(tài)設(shè)為已經(jīng)回滾，則該事務(wù)產(chǎn)生的版本對其它事務(wù)自然就不可見了。
老舊的不再需要的版本，即不會(huì)被將來的任何事務(wù)見到的版本的清理是通過VACUUM實(shí)現(xiàn)的。由于新老版本混雜在一起，進(jìn)行VACUUM時(shí)本質(zhì)上是需要掃描所有數(shù)據(jù)。8.4版中引入了Visibility Map技術(shù)，用來在VACUUM時(shí)跳過那些肯定不包含老舊版本的頁面，但如果系統(tǒng)更新頻繁且離散，這一技術(shù)就派不上大用場。在線的VACUUM只能清理頁面中的老舊版本，但不能縮減表占用的空間，其實(shí)是產(chǎn)生碎片。要縮減表空間時(shí)的VACUUM會(huì)鎖住表導(dǎo)致期間表不能被更新。
二、InnoDB的多版本實(shí)現(xiàn)（基于MySQL 5.1.33版本帶的InnoDB）
InnoDB采用索引組織表的存儲(chǔ)結(jié)構(gòu)，沒有堆，記錄存儲(chǔ)在主鍵索引中，其它索引稱為二級索引，其中每個(gè)索引項(xiàng)都包含所對應(yīng)記錄的主鍵。主鍵索引與二級索引的存儲(chǔ)格式也不同。
主鍵索引擁有版本化信息，但與PostgreSQL不同，一般情況下InnoDB的主鍵索引中只存儲(chǔ)記錄的最新版本，舊版本的信息則集中存儲(chǔ)在回滾段中，只有主鍵被更新時(shí)才需要同時(shí)存儲(chǔ)多個(gè)版本在主鍵索引中。主鍵索引記錄的頭上包含有6字節(jié)的事務(wù)ID與7字節(jié)指向回滾段中舊版本的指針（見MySQL手冊）。DELETE時(shí)只是標(biāo)記而不真正刪除。UPDATE時(shí)進(jìn)行本地更新，并將前像寫到回滾段中。
存在與PostgreSQL中事務(wù)快照類似讀視圖，也記錄了事務(wù)開始時(shí)的活躍事務(wù)列表（見read_view_struct結(jié)構(gòu)），但不需要PostgreSQL中的事務(wù)提交日志。根據(jù)讀視圖和記錄頭上的事務(wù)ID，可以判斷出一個(gè)版本在事務(wù)開始時(shí)是否已經(jīng)提交，即是否可見。如果存儲(chǔ)在主鍵索引中的記錄不可見，則根據(jù)指向回滾段中舊版本的指針找到舊版本信息，構(gòu)造出舊的記錄�；貪L段采用的是append-only的日志型存儲(chǔ)，記錄的舊版本信息并不是一條完整的記錄，而只是被更新的屬性的前像�；貪L段中的舊版本信息中也包含更舊的版本的位置，即版本鏈表是從新到舊的。
由于沒有事務(wù)日志表示事務(wù)是否回滾，在事務(wù)回滾時(shí)必須清理該事務(wù)所進(jìn)行的修改，插入的記錄要?jiǎng)h除，更新的記錄要更新回來（見row_undo函數(shù)）。事務(wù)提交時(shí)則無需處理。
二級索引中的每個(gè)索引項(xiàng)并沒有版本化信息。但在頁面頭記錄了對該頁面操作的事務(wù)的ID的最大值，通過這一值可以判斷頁面中是否可能包含不可見的數(shù)據(jù)，如果是，則需要訪問主鍵索引判斷可見性。否則，可以直接從索引中獲取查詢所需屬性。二級索引中可能存儲(chǔ)一條記錄的多個(gè)版本對應(yīng)的索引項(xiàng)，如果UPDATE操作更新了某個(gè)索引的屬性，則類似于PostgreSQL，插入新索引項(xiàng)到二級索引中，老索引項(xiàng)并不刪除。但沒有被UPDATE操作更新的索引則不需要插入新索引項(xiàng)。
系統(tǒng)使用一個(gè)后臺(tái)線程不時(shí)處理回滾段，在需要時(shí)清理由于DELETE、二級索引或主鍵索引中由于主鍵被更新而產(chǎn)生的老舊版本，這一過程稱這purge。如果UPDATE沒有更新索引，則不會(huì)帶來purge開銷。
三、評價(jià)與總結(jié)
PostgreSQL與InnoDB的多版本實(shí)現(xiàn)最大的區(qū)別在于最新版本和歷史版本是否分離存儲(chǔ)，PostgreSQL不分，InnoDB分。
PostgreSQL的這種設(shè)計(jì)被其最初的設(shè)計(jì)者M(jìn)ike Stonebraker稱為no-overwrite的設(shè)計(jì)，在設(shè)計(jì)了PostgreSQL幾年之后他的一篇回顧性論文《The Implementation of Postgres》 （PostgreSQL早期叫Postgres）中，Stonebraker指出當(dāng)初這樣設(shè)計(jì)的主要原因是尋求與當(dāng)時(shí)已經(jīng)廣泛使用的WAL模式不同的存儲(chǔ)機(jī)制，有點(diǎn)為了創(chuàng)新而創(chuàng)新的意思。這一設(shè)計(jì)有兩大好處：一是事務(wù)回滾時(shí)無需復(fù)雜處理，非常快；二是可以查詢以前的歷史數(shù)據(jù)。還有一個(gè)可能的好處是可以實(shí)現(xiàn)數(shù)據(jù)即日志，即更新時(shí)只要更新數(shù)據(jù)就行了，不需要再寫日志來描述做了什么更新。但要使這個(gè)好處實(shí)現(xiàn)，需要有一種持久的，并且隨機(jī)寫具有與順序?qū)戭愃菩阅艿拇鎯?chǔ)介質(zhì)才行，因?yàn)闉榱吮ＷC事務(wù)提交后的持久性，需要寫出被事務(wù)更新的數(shù)據(jù)，而這些數(shù)據(jù)可能是離散的。WAL系統(tǒng)則不同，事務(wù)提交時(shí)只需要寫日志就行了，而日志是順序?qū)懭氲摹．?dāng)前的硬件環(huán)境并不是這樣，因此PostgreSQL中仍然還要寫日志，只不過不需要寫UNDO日志，只要REDO日志就行了。
最新的PostgreSQL與當(dāng)初Stonebraker的設(shè)計(jì)已經(jīng)有了很大改進(jìn)，比如HOT技術(shù)減少了索引中的版本數(shù)，Visibility Map技術(shù)加快了VACUUM，記錄頭部結(jié)構(gòu)也更緊湊。但no-overwrite的設(shè)計(jì)原則仍然沒變。
相對于InnoDB，PostgreSQL的優(yōu)勢似乎主要的只有一條：事務(wù)回滾可以立即完成，無論事務(wù)進(jìn)行了多少操作。查詢以前的歷史數(shù)據(jù)的功能并不常用，在目前的PostgreSQL中也并不實(shí)用。
PostgreSQL的主要劣勢在于：
1、最新版本和歷史版本不分離存儲(chǔ)，導(dǎo)致清理老舊版本需要作更多的掃描，代價(jià)更大；
2、UPDATE不是本地更新，會(huì)產(chǎn)生老舊版本需要清理。與之相對的是InnoDB只有在事務(wù)回滾時(shí)才需要清理老的記錄數(shù)據(jù)。而事務(wù)回滾是罕見的；
3、只要有一個(gè)索引屬性被更新，或者新版本的記錄與原版本不在同一頁面，就要插入所有索引的新版本索引項(xiàng)；
4、堆占用的空間不能通過在線的VACUUM回收，在線VACUUM會(huì)產(chǎn)生很多碎片（這也是由于使用了堆而不是索引組織表導(dǎo)致的）；
5、由于索引中完全沒有版本信息，不能實(shí)現(xiàn)Coverage index scan，即查詢只掃描索引，直接從索引中返回所需的屬性。與之相對的是InnoDB中二級索引頁頭記錄的最近修改該頁的事務(wù)ID信息可以在大部分情況下實(shí)現(xiàn)Coverage index scan。Coverage index scan是應(yīng)用中經(jīng)常使用的優(yōu)化技巧，PostgreSQL不支持這個(gè)對提升系統(tǒng)性能帶來很大限制，因?yàn)樗饕龗呙枋琼樞蛟L問，去訪問堆則很可能變成亂序訪問，性能可能相差百倍；
6、判斷版本可見性更復(fù)雜，開銷更大。PostgreSQL比InnoDB在判斷可見性時(shí)，需要增加訪問事務(wù)提交日志的操作，事務(wù)提交日志每個(gè)事務(wù)需要分配兩個(gè)bit，對高更新負(fù)載的系統(tǒng)會(huì)占用較大空間，這時(shí)要么事務(wù)提交日志回占用大量內(nèi)存，要么判斷可見性時(shí)就可能產(chǎn)生額外的IO。對比PostgreSQL中判斷可見性的函數(shù)HeapTupleSatisfiesMVCC和InnoDB中判斷可見性的函數(shù)read_view_sees_trx_id，可以容易看出這兩者的復(fù)雜度不可同日而語。
InnoDB的主要劣勢在于事務(wù)回滾時(shí)需要清理事務(wù)所作的所有修改，因此使用InnoDB時(shí)要避免使用超大型事務(wù)，否則回滾可能超慢無比。
