HBase 事務和并發控制機制原理

來自： http://www.codeceo.com/article/hbase-transaction.html

作為一款優秀的非內存數據庫，HBase和傳統數據庫一樣提供了事務的概念，只是HBase的事務是行級事務，可以保證行級數據的原子性、一致性、隔離性以及持久性，即通常所說的ACID特性。為了實現事務特性，HBase采用了各種并發控制策略，包括各種鎖機制、MVCC機制等。本文首先介紹HBase的兩種基于鎖實現的同步機制，再分別詳細介紹行鎖的實現以及各種讀寫鎖的應用場景，最后重點介紹MVCC機制的實現策略。

HBase同步機制

HBase提供了兩種同步機制，一種是基于CountDownLatch實現的互斥鎖，常見的使用場景是行數據更新時所持的行鎖。另一種是基于ReentrantReadWriteLock實現的讀寫鎖，該鎖可以給臨界資源加上read-lock或者write-lock。其中read-lock允許并發的讀取操作，而write-lock是完全的互斥操作。

CountDownLatch

Java中，CountDownLatch是一個同步輔助類，在完成一組其他線程執行的操作之前，它允許一個或多個線程阻塞等待。CountDownLatch使用給定的計數初始化，核心的兩個方法是countDown()和await()，前者可以實現給定計數倒數一次，后者是等待計數倒數到0，如果沒有到達0，就一直阻塞等待。結合線程安全的map容器，基于test-and-set機制，CountDownLatch可以實現基本的互斥鎖，原理如下：

1. 初始化：CountDownLatch初始化計數為1

2. test過程：線程首先將臨界資源作為key，latch作為value嘗試插入線程安全的map中。如果返回失敗，表示其他線程已經持有了該鎖，調用await方法阻塞到該latch上，等待其他線程釋放鎖；

3. set過程：如果返回成功，就表示已經持有該鎖，其他線程必然插入失敗。持有該鎖之后執行各種操作，執行完成之后釋放鎖，釋放鎖首先將map中對應的KeyValue移除，再調用latch的countDown方法，該方法會將計數減1，變為0之后就會喚醒其他阻塞線程。

ReentrantReadWriteLock

讀寫鎖分為讀鎖、寫鎖，和互斥鎖相比可以提供更高的并行性。讀鎖允許多個線程同時以讀模式占有鎖資源，而寫鎖只能由一個線程以寫模式占有。如果讀寫鎖是寫加鎖狀態，在鎖釋放之前，所有試圖對該鎖占有的線程都會被阻塞；如果是讀加鎖狀態，所有其他對該鎖的讀請求都會并行執行，但是寫請求會被阻塞。顯而易見，讀寫鎖適合于讀多寫少的場景，也因為讀鎖可以共享，寫鎖只能某個線程獨占，讀寫鎖也被稱為共享－獨占鎖，即經常見到的S鎖和X鎖。

Java中，ReentrantReadWriteLock是讀寫鎖的實現類，該類中有兩個方法readLock()和writeLock()分別用來獲取讀鎖和寫鎖。

HBase中行鎖的具體實現

HBase采用行鎖實現更新的原子性，要么全部更新成功，要么失敗。所有對HBase行級數據的更新操作，都需要首先獲取該行的行鎖，并且在更新完成之后釋放，等待其他線程獲取。因此，HBase中對同一行數據的更新操作都是串行操作。

行鎖相關數據結構

如上圖所示，HBase中行鎖相關的主要結構有RowLock和RowLockContext兩個類，其中RowLockContext類存儲行鎖相關上下文信息，包括持鎖線程、被鎖對象以及可以實現互斥鎖的CountDownLatch對象等等，RowLockContext是RowLock的一個屬性，除此之外，RowLock還包含表征行鎖是否已經釋放的release字段。具體字段如下圖所示：

更新加鎖流程

1. 首先使用rowkey以及自身線程對象生成行鎖上下文RowLockContext對象

2. 再將rowkey作為key，RowLockContext對象作為value調用putIfAbsert方法寫入全局map中。key的唯一性，保證map中最多只有一個RowLockContext。putIfAbsent方法會返回一個existingContext對象，該對象表示key插入前map中對應該key的value值，根據existingContext是否為null、是否是自身線程創建，可以分為如下三種情況：

（1）existingContext對象為null，表示該行鎖沒有被其他線程持有，可以根據創建的上下文對象持有該鎖
（2）existingContext是自身線程創建，表示自身線程已經再創建RowLockContext對象，直接使用存在的RowLockContext對象持有該鎖。這種情況會出現在批量更新線程中，一次批量更新可能前前后后對某一行數據更新多次，需要多次持有該行數據的行鎖，在HBase中是被允許的。
（3）existingContext是其他線程創建，則該線程會阻塞在此上下文所持鎖上，直至所持行鎖被釋放或者阻塞超時。如果所持行鎖釋放，該線程會重新競爭寫全局map，一旦競爭成功就持有該行鎖，否則繼續阻塞。而如果阻塞超時，就會拋出異常，不會再去競爭該鎖。

釋放流程

在線程更新完成操作之后，必須在finnally方法中執行行鎖釋放操作，即調用rowLock.release()方法，該方法主要執行如下兩個操作：

1. 從lockedRows這個全局map中將該row對應的RowLockContext移除

2. 調用latch.countDown()方法，喚醒其他阻塞在await上等待該行鎖的線程

HBase中讀寫鎖的使用

HBase中除了使用互斥鎖實現行級數據的一致性之外，也使用讀寫鎖實現store級別操作以及region級別操作的并發控制。比如：

1. Region更新讀寫鎖：HBase在執行數據更新操作之前都會加一把Region級別的讀鎖（共享鎖），所有更新操作線程之間不會相互阻塞；然而，HBase在將memstore數據落盤時會加一把Region級別的寫鎖（獨占鎖）。因此，在memstore數據落盤時，數據更新操作線程（Put操作、Append操作、Delete操作）都會阻塞等待至該寫鎖釋放。

2. Region Close保護鎖：HBase在執行close操作以及split操作時會首先加一把Region級別的寫鎖（獨占鎖），阻塞對region的其他操作，比如compact操作、flush操作以及其他更新操作，這些操作都會持有一把讀鎖（共享鎖）

3. Store snapshot保護鎖：HBase在執行flush memstore的過程中首先會基于memstore做snapshot，這個階段會加一把store級別的寫鎖（獨占鎖），用以阻塞其他線程對該memstore的各種更新操作；清除snapshot時也相同，會加一把寫鎖阻塞其他對該memstore的更新操作。

HBase中MVCC機制的實現

如上文所述，HBase分別提供了行鎖和讀寫鎖來實現行級數據、Store級別以及Region級別的并發控制。除此之外，HBase還提供了MVCC機制實現數據的讀寫并發控制。MVCC，即多版本并發控制技術，它使得事務引擎不再單純地使用行鎖實現數據讀寫的并發控制，取而代之的是，把行鎖與行的多個版本結合起來，經過簡單的算法就可以實現非鎖定讀，進而大大的提高系統的并發性能。HBase正是使用行鎖 ＋ MVCC保證高效的并發讀寫以及讀寫數據一致性。

MVCC機制簡介

在了解HBase如何實現MVCC之前，我們首先需要了解當前僅基于行鎖實現的更新操作對于讀請求有什么影響。下圖為HBase基于行鎖實現的數據更新時序示意圖：

上圖中簡單地表述了數據更新流程（后續文章會對HBase數據寫入進行深入的介紹），簡單來說，數據更新可以分為如下幾個階段：獲取行鎖、更新WAL、數據寫入本地緩存memstore、釋放行鎖。

如上圖所示，前后分別有兩次對同一行數據的更新操作。假如第二次更新過程在將列簇cf1更新為t2_cf1之后中有一次讀請求進來，此時讀到的第一列數據將是第二次更新后的數據t2_cf1，然而第二列數據卻是第一次更新后的數據t1_cf2，很顯然，只針對更行操作加行鎖會產生讀取數據不一致的情況。最簡單的數據不一致解決方案是讀寫線程公用一把行鎖，這樣可以保證讀寫之間互斥，但是讀寫線程同時搶占行鎖必然會極大地影響性能。

為此，HBase采用MVCC解決方案避免讀線程去獲取行鎖。MVCC解決方案對上述數據更新操作時序和讀操作都進行了一定的修正，主要新增了一個寫序號和讀序號，其實就是數據的版本號。修正后的更新操作時序示意圖為：

如上圖所示，修正后的更新操作主要新增了‘獲取寫序號’和’結束寫序號’兩個步驟，并且每個cell數據寫memstore操作都會攜帶該寫序號。那讀請求需要經過什么樣的修正呢？HBase的做法如下：

（1）每個讀操作開始時都會分配一個讀序號，稱為讀取點
（2）讀取點的值是所有的寫操作完成序號中的最大整數
（3）一次讀操作的結果就是讀取點對應的所有cell值的集合

如下圖所示，第一次更新獲取的寫序號為1，第二次更新獲取的寫序號為2。讀請求進來時寫操作完成序號中的最大整數為wn ＝ 1，因此對應的讀取點為wn ＝ 1，讀取的結果為wn ＝ 1所對應的所有cell值集合，即為t1_cf1和t1_cf2，這樣就可以實現以無鎖的方式讀取到一致的數據。

HBase中MVCC實現

HBase中，MVCC的具體實現類為MultiVersionConsistencyControl，該類維護了兩個long型的變量、一個WriteEntry對象和一個writeQueue隊列：

1. long memstoreRead：記錄當前全局的讀取點，讀請求進來之后首先會獲取該讀取點

2. long memstoreWrite：記錄當前全局的寫序號，根據它為下一個更新線程分配新的寫序號

3. writeEntry：記錄更新操作的寫序號對象，主要包含兩個變量，一個是writeNumber，表示寫序號；一個是布爾類型的completed，表示該次更新是否完成

4. writeQueue：當前所有更新操作的寫序號對象集合

獲取寫序號

根據上文中更新數據時序圖可知，更新線程獲取行鎖之后就需要獲取寫序號，對應的方法為beginMemstoreInsert，該方法將memstoreWrite加1，生成writeEntry對象并插入到隊列writeQueue，返回writeEntry對象。Note：生成的writeEntry對象中包含寫序號writeNumber，更新線程會將該writeNumber設置為cell數據的一個屬性。

結束寫序號

數據更新完成之后，釋放行鎖之前，更新線程會調用completeMemstoreInsert方法更新writeEntry對象以及memstoreRead變量，具體分為如下兩步：

1. 首先將該writeEntry對象標記為’已完成’，再將全局讀取點memstoreRead盡可能多地往前移。前移算法為遍歷隊列writeQueue中所有的writeEntry對象，移除掉已經標記為’已完成’的writeEntry直至遇到未完成的writeEntry，最后將memstoreRead變量更新為最新已完成的writeNumber。

2. 注意上述memstoreRead變量有可能并不等于當前更新線程的writeNumber，這種情況下該更新線程對數據的更新操作對用戶并不可見。為了實現更新完成之后更新結果即對用戶可見，需要等待memstoreRead變量前移到當前更新線程的witeNumber。因此它會阻塞當前線程，等待其他線程對應的writeEntry對象標記為’已完成’，直至memstoreRead等于當前線程的writeNumber。

總結

HBase提供了各種鎖機制和MVCC機制來保證數據的原子性、一致性等特性，其中使用互斥鎖實現的行鎖保證了行級數據的原子性，使用JDK提供的讀寫鎖實現了Store級別、Region級別的數據一致性，同時使用行鎖+MVCC機制實現了在高性能非鎖定讀場景下的數據一致性。