RocksDB上鎖機制

 RocksDB作為一個開源的存儲引擎支持事務的ACID特性，而要支持ACID中的I(Isolation),并發控制這塊是少不了的，本文主要討論RocksDB的鎖機制實現，細節會涉及到源碼分析，希望通過本文讀者可以深入了解RocksDB并發控制原理。文章主要從以下4方面展開，首先會介紹RocksDB鎖的基本結構，然后我會介紹RocksDB行鎖數據結構設計下，鎖空間開銷，接著我會介紹幾種典型場景的上鎖流程，最后會介紹鎖機制中必不可少的死鎖檢測機制。

1.行鎖數據結構
    RocksDB鎖粒度最小是行，對于KV存儲而言，鎖對象就是key，每一個key對應一個LockInfo結構。所有key通過hash表管理，查找鎖時，直接通過hash表定位即可確定這個key是否已經被上鎖。但如果全局只有一個hash表，會導致這個訪問這個hash表的沖突很多，影響并發性能。RocksDB首先按Columnfamily進行拆分，每個Columnfamily中的鎖通過一個LockMap管理，而每個LockMap再拆分成若干個分片，每個分片通過LockMapStripe管理，而hash表(std::unordered_map<std::string, LockInfo>)則存在于Stripe結構中，Stripe結構中還包含一個mutex和condition_variable，這個主要作用是，互斥訪問hash表，當出現鎖沖突時，將線程掛起，解鎖后，喚醒掛起的線程。這種設計很簡單但也帶來一個顯而易見的問題，就是多個不相關的鎖公用一個condition_variable，導致鎖釋放時，不必要的喚醒一批線程，而這些線程重試后，發現仍然需要等待，造成了無效的上下文切換。對比我們之前討論的InnoDB鎖機制，我們發現InnoDB是一個page里面的記錄復用一把鎖，而且復用是有條件的，同一個事務對一個page的若干條記錄加鎖才能復用；而且鎖等待隊列是精確等待，精確到記錄級別，不會導致的無效的喚醒。雖然RocksDB鎖設計比較粗糙，但也做了一定的優化，比如在管理LockMaps時，通過在每個線程本地緩存一份拷貝lock_maps_cache_，通過全局鏈表將每個線程的cache鏈起來，當LockMaps變更時(刪除columnfamily)，則全局將每個線程的copy清空，由于columnfamily改動很少，所以大部分訪問LockMaps操作都是不需要加鎖的，提高了并發效率。
相關數據結構如下：

2.行鎖空間代價
    由于鎖信息是常駐內存，我們簡單分析下RocksDB鎖占用的內存。每個鎖實際上是unordered_map中的一個元素，則鎖占用的內存為key_length+8+8+1，假設key為bigint，占8個字節，則100w行記錄，需要消耗大約22M內存。但是由于內存與key_length正相關，導致RocksDB的內存消耗不可控。我們可以簡單算算RocksDB作為MySQL存儲引擎時，key_length的范圍。對于單列索引，最大值為2048個字節，具體可以參考max_supported_key_part_length實現；對于復合索引，索引最大長度為3072個字節，具體可以參考max_supported_key_length實現。假設最壞的情況，key_length=3072，則100w行記錄，需要消耗3G內存，如果是鎖1億行記錄，則需要消耗300G內存，這種情況下內存會有撐爆的風險。因此RocksDB提供參數配置max_row_locks，確保內存可控，默認RDB_MAX_ROW_LOCKS設置為1G，對于大部分key為bigint場景，極端情況下，也需要消耗22G內存。而在這方面，InnoDB則比較友好，hash表的key是(space_id, page_no)，所以無論key有多大，key部分的內存消耗都是恒定的。前面我也提到了InnoDB在一個事務需要鎖大量記錄場景下是有優化的，多個記錄可以公用一把鎖，這樣也間接可以減少內存。

3.上鎖流程分析
    前面簡單了解了RocksDB鎖數據結構的設計以及鎖對內存資源的消耗。這節主要介紹幾種典型場景下，RocksDB是如何加鎖的。與InnoDB一樣，RocksDB也支持MVCC，讀不上鎖，為了方便，下面的討論基于RocksDB作為MySQL的一個引擎來展開，主要包括三類，基于主鍵的更新，基于二級索引的更新，基于主鍵的范圍更新等。在展開討論之前，有一點需要說明的是，RocksDB與InnoDB不同，RocksDB的更新也是基于快照的，而InnoDB的更新基于當前讀，這種差異也使得在實際應用中，相同隔離級別下，表現有所不一樣。對于RocksDB而言，在RC隔離級別下，每個語句開始都會重新獲取一次快照；在RR隔離級別下，整個事務中只在第一個語句開始時獲取一次快照，所有語句共用這個快照，直到事務結束。

3.1.基于主鍵的更新
這里主要接口是TransactionBaseImpl::GetForUpdate
1).嘗試對key加鎖，如果鎖被其它事務持有，則需要等待
2).創建snapshot
3).調用ValidateSnapshot，Get key,通過比較Sequence判斷key是否被更新過
4).由于是加鎖后，再獲取snapshot，所以檢查一定成功。
5).執行更新操作
這里有一個延遲獲取快照的機制，實際上在語句開始時，需要調用acquire_snapshot獲取快照，但為了避免沖突導致的重試，在對key加鎖后，再獲取snapshot，這就保證了在基于主鍵更新的場景下，不會存在ValidateSnapshot失敗的場景。

堆棧如下：

3.2.基于主鍵的范圍更新
1).創建Snapshot，基于迭代器掃描主鍵
2).通過get_row_by_rowid，嘗試對key加鎖
3).調用ValidateSnapshot，Get key,通過比較Sequence判斷key是否被更新過
4).如果key被其它事務更新過(key對應的SequenceNumber比Snapshot要新)，觸發重試
5).重試情況下，會釋放老的快照并釋放鎖，通過tx->acquire_snapshot(false)，延遲獲取快照(加鎖后，再拿snapshot)
5).再次調用get_for_update，由于此時key已經被加鎖，重試一定可以成功。
6).執行更新操作
7).跳轉到1，繼續執行，直到主鍵不符合條件時，則結束。

3.3.基于二級索引的更新
這種場景與3.2類似，只不過多一步從二級索引定位主鍵過程。
1).創建Snapshot，基于迭代器掃描二級索引
2).根據二級索引反向找到主鍵，實際上也是調用get_row_by_rowid，這個過程就會嘗試對key加鎖
3).繼續根據二級索引遍歷下一個主鍵，嘗試加鎖
4).當返回的二級索引不符合條件時，則結束

3.4 與InnoDB加鎖的區別
      前面我們說到了RocksDB與InnoDB的一點區別是，對于更新場景，RocksDB仍然是快照讀，而InnoDB是當前讀，導致行為上的差異。比如在RC隔離級別下的范圍更新場景，比如一個事務要更新1000條記錄，由于是邊掃描邊加鎖，可能在掃描到第999條記錄時，發現這個key的Sequence大于掃描的快照(這個key被其它事務更新了)，這個時候會觸發重新獲取快照，然后基于這個快照拿到最新的key值。InnoDB則沒有這個問題，通過當前讀，掃描過程中，如果第999條記錄被更新了，InnoDB可以直接看到最新的記錄。這種情況下，RocksDB和InnoDB看到的結果是一樣的。在另外一種情況下，假設也是掃描的范圍中，新插入了key，這key的Sequence毫無疑問會比掃描的Snapshot要大，因此在Scan過程中這個key會被過濾掉，也就不存在所謂的沖突檢測了，這個key不會被找到。更新過程中，插入了id為1和900的兩條記錄，最后第900條記錄由于不可見，所以更新不到。而對于InnoDB而言，由于是當前讀，新插入的id為900的記錄可以被看到并更新，所以這里是與InnoDB有區別的地方。
      除了更新基于快照這個區別以外，RocksDB在加鎖上也更簡潔，所有加鎖只涉及唯一索引，具體而言，在更新過程中，只對主鍵加鎖；更新列涉及唯一約束時，需要加鎖；而普通二級索引，則不用加鎖，這個目的是為了避免唯一約束沖突。這里面，如果更新了唯一約束(主鍵，或者唯一索引)，都需要加鎖。而InnoDB則是需要對每個索引加鎖，比如基于二級索引定位更新，則二級索引也需要加鎖。之所以有這個區別是，是因為InnoDB為了實現RR隔離級別。這里稍微講下隔離級別，實際上MySQL中定義的RR隔離級別與SQL標準定義的隔離級別有點不一樣。SQL標準定義RR隔離級別解決不可重復讀的問題，Serializable隔離級別解決幻讀問題。不可重復讀側重講同一條記錄值不會修改；而幻讀則側重講兩次讀返回的記錄條數是固定的，不會增加或減少記錄數目。MySQL定義RR隔離級別同時解決了不可重復讀和幻讀問題，而InnoDB中RR隔離級別的實現就是依賴于GAP鎖。而RocksDB不支持GAP鎖(僅僅支持唯一約束檢查，對不存在的key加鎖)，因為基于快照的機制可以有效過濾掉新插入的記錄，而InnoDB由于當前讀，導致需要通過間隙鎖禁止其它插入，所以二級索引也需要加鎖，主要是為了鎖間隙，否則兩次當前讀的結果可能不一樣。當然，對RC割裂級別，InnoDB普通二級索引也是沒有必要加鎖的。

4.死鎖檢測算法
      死鎖檢測采用DFS((Depth First Search,深度優先算法)，基本思路根據加入等待關系，繼續查找被等待者的等待關系，如果發現成環，則認為發生了死鎖，當然在大并發系統下，鎖等待關系非常復雜，為了將死鎖檢測帶來的資源消耗控制在一定范圍，可以通過設置deadlock_detect_depth來控制死鎖檢測搜索的深度，或者在特定業務場景下，認為一定不會發生死鎖，則關閉死鎖檢測，這樣在一定程度上有利于系統并發的提升。需要說明的是，如果關閉死鎖，最好配套將鎖等待超時時間設置較小，避免系統真發生死鎖時，事務長時間hang住。死鎖檢測基本流程如下：
1.定位到具體某個分片，獲取mutex
2.調用AcquireLocked嘗試加鎖
3.若上鎖失敗，則觸發進行死鎖檢測
4.調用IncrementWaiters增加一個等待者
5.如果等待者不在被等待者map里面，則肯定不會存在死鎖，返回
6.對于被等待者，沿著wait_txn_map_向下檢查等待關系，看看是否成環
7.若發現成環，則將調用DecrementWaitersImpl將新加入的等待關系解除，并報死鎖錯誤。

相關的數據結構：