1.隔離級別
(1)讀不提交(Read Uncommited，RU)
這種隔離級別下，事務間完全不隔離，會產生臟讀，可以讀取未提交的記錄，實際情況下不會使用。
(2)讀提交(Read commited，RC)
僅能讀取到已提交的記錄，這種隔離級別下，會存在幻讀現象，所謂幻讀是指在同一個事務中，多次執行同一個查詢，返回的記錄不完全相同的現象。幻讀產生的根本原因是，在RC隔離級別下，每條語句都會讀取已提交事務的更新，若兩次查詢之間有其他事務提交，則會導致兩次查詢結果不一致。雖然如此，讀提交隔離級別在生產環境中使用很廣泛。
(3)可重復讀(Repeatable Read, RR)
可重復讀隔離級別解決了不可重復讀的問題，但依然沒有解決幻讀的問題。那么不可重復讀與幻讀有什么區別呢？不可重復讀重點在修改，即讀取過的數據，兩次讀的值不一樣；而幻讀則側重于記錄數目變化【插入和刪除】。一般教科書上告訴我們只有到串行化隔離級別才解決幻讀問題，但mysql的innodb比較特殊，RR即解決了幻讀問題，主要通過GAP鎖實現。另外，不是所有的數據庫都實現了該隔離級別，后面會簡單介紹下mysql是如何實現可重復讀隔離級別的。
(4)串行化(Serializable)
在串行化隔離模式下，消除了臟讀，幻象，但事務并發度急劇下降，事務的隔離級別與事務的并發度成反比，隔離級別越高，事務的并發度越低。實際生產環境下，dba會在并發和滿足業務需求之間作權衡，選擇合適的隔離級別。
2.并發調度方式
與隔離級別緊密聯系的另外一個東西是并發調度，通過并發調度實現隔離級別。對于并發調度，不同的數據庫廠商有不同的實現機制，但基本原理類似，都是通過加鎖來保護數據對象不同時被多個事務修改。多版本的并發控制(MVCC)相對于傳統的基于鎖的并發控制主要特點是讀不上鎖，這種特性對于讀多寫少的場景，大大提高了系統的并發度，因此大部分關系型數據庫都實現了MVCC。
3.兩階段鎖協議
兩階段鎖協議的含義是，事務分為兩個階段，第一個階段是獲得封鎖，第二個階段是釋放封鎖。兩階段封鎖保證并發調度的正確性。兩階段封鎖相對于一階段封鎖（一次性獲得事務需要的所有鎖），提高了并發度，但同時也帶來了死鎖的可能。
4.死鎖
所謂死鎖是指兩個或多個事務，各自占有對方的期望獲得的資源，形成的循環等待，彼此無法繼續執行的一種狀態。
5.鎖類型
根據鎖的類型分，可以分為共享鎖，排他鎖，意向共享鎖和意向排他鎖。根據鎖的粒度分，又可以分為行鎖，表鎖。對于mysql而言，事務機制更多是靠底層的存儲引擎來實現，因此，mysql層面只有表鎖，而支持事務的innodb存儲引擎則實現了行鎖(記錄鎖)，gap鎖，next-key鎖。Mysql的記錄鎖實質是索引記錄的鎖，因為innodb是索引組織表；gap鎖是索引記錄間隙的鎖，這種鎖只在RR隔離級別下有效；next-key鎖是記錄鎖加上記錄之前gap鎖的組合。mysql通過gap鎖和next-key鎖實現RR隔離級別。
說明：
對于更新操作(讀不上鎖)，只有走索引才可能上行鎖；否則會對聚簇索引的每一行上寫鎖，實際等同于對表上寫鎖。
若多個物理記錄對應同一個索引，若同時訪問，也會出現鎖沖突；
當表有多個索引時，不同事務可以用不同的索引鎖住不同的行，另外innodb會同時用行鎖對數據記錄(聚簇索引)加鎖。
MVCC并發控制機制下，任何操作都不會阻塞讀操作，讀操作也不會阻塞任何操作，只因為讀不上鎖。
? ? ?
?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<: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操作都是不需要加鎖的，提高了并發效率。
相關數據結構如下：
struct?LockInfo?{ bool?exclusive;?//排它鎖或是共享鎖 autovector<transactionid>?txn_ids;?//事務列表，對于共享鎖而言，同一個key可以對應多個事務 //?Transaction?locks?are?not?valid?after?this?time?in?us uint64_t?expiration_time; } struct?LockMapStripe?{? //?Mutex?must?be?held?before?modifying?keys?map std::shared_ptr<transactiondbmutex>?stripe_mutex; //?Condition?Variable?per?stripe?for?waiting?on?a?lock std::shared_ptr<transactiondbcondvar>?stripe_cv; //?Locked?keys?mapped?to?the?info?about?the?transactions?that?locked?them. std::unordered_map<:string>?keys; } struct?LockMap?{ const?size_t?num_stripes_;?//分片個數 std::atomic<int64_t>?lock_cnt{0};?//鎖數目 std::vector<lockmapstripe>?lock_map_stripes_;?//鎖分片 } class?TransactionLockMgr?{ using?LockMaps?=?std::unordered_map<uint32_t>>; LockMaps?lock_maps_; //?Thread-local?cache?of?entries?in?lock_maps_.?This?is?an?optimization //?to?avoid?acquiring?a?mutex?in?order?to?look?up?a?LockMap std::unique_ptr<threadlocalptr>?lock_maps_cache_; }</threadlocalptr></uint32_t></lockmapstripe></int64_t></:string></transactiondbcondvar></transactiondbmutex></transactionid>
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失敗的場景。
堆棧如下：
1-myrocks::ha_rocksdb::get_row_by_rowid 2-myrocks::ha_rocksdb::get_for_update 3-myrocks::Rdb_transaction_impl::get_for_update 4-rocksdb::TransactionBaseImpl::GetForUpdate { //加鎖 5-rocksdb::TransactionImpl::TryLock ??6-rocksdb::TransactionDBImpl::TryLock ????7-rocksdb::TransactionLockMgr::TryLock? ?//延遲獲取快照，與acquire_snapshot配合使用 ?6-SetSnapshotIfNeeded() ?//檢查key對應快照是否過期 ?6-ValidateSnapshot ??7-rocksdb::TransactionUtil::CheckKeyForConflict ????8-rocksdb::TransactionUtil::CheckKey ??????9-rocksdb::DBImpl::GetLatestSequenceForKey?//第一次讀取 //讀取key 5-rocksdb::TransactionBaseImpl::Get ??6-rocksdb::WriteBatchWithIndex::GetFromBatchAndDB ????7-rocksdb::DB::Get ??????8-rocksdb::DBImpl::Get ????????9-rocksdb::DBImpl::GetImpl?//第二次讀取 }
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).當返回的二級索引不符合條件時，則結束
4.死鎖檢測算法
? ? ? 死鎖檢測采用DFS((Depth First Search,深度優先算法)，基本思路根據加入等待關系，繼續查找被等待者的等待關系，如果發現成環，則認為發生了死鎖，當然在大并發系統下，鎖等待關系非常復雜，為了將死鎖檢測帶來的資源消耗控制在一定范圍，可以通過設置deadlock_detect_depth來控制死鎖檢測搜索的深度，或者在特定業務場景下，認為一定不會發生死鎖，則關閉死鎖檢測，這樣在一定程度上有利于系統并發的提升。需要說明的是，如果關閉死鎖，最好配套將鎖等待超時時間設置較小，避免系統真發生死鎖時，事務長時間hang住。死鎖檢測基本流程如下：
1.定位到具體某個分片，獲取mutex
2.調用AcquireLocked嘗試加鎖
3.若上鎖失敗，則觸發進行死鎖檢測
4.調用IncrementWaiters增加一個等待者
5.如果等待者不在被等待者map里面，則肯定不會存在死鎖，返回
6.對于被等待者，沿著wait_txn_map_向下檢查等待關系，看看是否成環
7.若發現成環，則將調用DecrementWaitersImpl將新加入的等待關系解除，并報死鎖錯誤。
相關的數據結構：
class?TransactionLockMgr?{ //?Must?be?held?when?modifying?wait_txn_map_?and?rev_wait_txn_map_. std::mutex?wait_txn_map_mutex_; //?Maps?from?waitee?->?number?of?waiters. HashMap<transactionid>?rev_wait_txn_map_; //?Maps?from?waiter?->?waitee. HashMap<transactionid>>?wait_txn_map_; DecrementWaiters?// IncrementWaiters?// } struct?TransactionOptions?{ bool?deadlock_detect?=?false;?//是否檢測死鎖 int64_t?deadlock_detect_depth?=?50;?//死鎖檢測的深度 int64_t?lock_timeout?=?-1;?//等待鎖時間，線上一般設置為5s int64_t?expiration?=?-1;?//持有鎖時間， }</transactionid></transactionid>
