RocksDB上鎖機(jī)制的案例詳細(xì)說(shuō)明

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

struct LockInfo {
bool exclusive; //排它鎖或是共享鎖
autovector<TransactionID> txn_ids; //事務(wù)列表，對(duì)于共享鎖而言，同一個(gè)key可以對(duì)應(yīng)多個(gè)事務(wù)

// 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<std::string, LockInfo> keys;
}

struct LockMap {
const size_t num_stripes_; //分片個(gè)數(shù)
std::atomic<int64_t> lock_cnt{0}; //鎖數(shù)目
std::vector<LockMapStripe*> lock_map_stripes_; //鎖分片
}

class TransactionLockMgr {
using LockMaps = std::unordered_map<uint32_t, std::shared_ptr<LockMap>>;
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_;
}

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

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

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

堆棧如下：

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對(duì)應(yīng)快照是否過(guò)期
 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).創(chuàng)建Snapshot，基于迭代器掃描主鍵
2).通過(guò)get_row_by_rowid，嘗試對(duì)key加鎖
3).調(diào)用ValidateSnapshot，Get key,通過(guò)比較Sequence判斷key是否被更新過(guò)
4).如果key被其它事務(wù)更新過(guò)(key對(duì)應(yīng)的SequenceNumber比Snapshot要新)，觸發(fā)重試
5).重試情況下，會(huì)釋放老的快照并釋放鎖，通過(guò)tx->acquire_snapshot(false)，延遲獲取快照(加鎖后，再拿snapshot)
5).再次調(diào)用get_for_update，由于此時(shí)key已經(jīng)被加鎖，重試一定可以成功。
6).執(zhí)行更新操作
7).跳轉(zhuǎn)到1，繼續(xù)執(zhí)行，直到主鍵不符合條件時(shí)，則結(jié)束。

3.3.基于二級(jí)索引的更新
這種場(chǎng)景與3.2類(lèi)似，只不過(guò)多一步從二級(jí)索引定位主鍵過(guò)程。
1).創(chuàng)建Snapshot，基于迭代器掃描二級(jí)索引
2).根據(jù)二級(jí)索引反向找到主鍵，實(shí)際上也是調(diào)用get_row_by_rowid，這個(gè)過(guò)程就會(huì)嘗試對(duì)key加鎖
3).繼續(xù)根據(jù)二級(jí)索引遍歷下一個(gè)主鍵，嘗試加鎖
4).當(dāng)返回的二級(jí)索引不符合條件時(shí)，則結(jié)束

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

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

相關(guān)的數(shù)據(jù)結(jié)構(gòu)：

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, int> rev_wait_txn_map_;

// Maps from waiter -> waitee.
HashMap<TransactionID, autovector<TransactionID>> wait_txn_map_;

DecrementWaiters //

IncrementWaiters //
}

struct TransactionOptions {
bool deadlock_detect = false; //是否檢測(cè)死鎖
int64_t deadlock_detect_depth = 50; //死鎖檢測(cè)的深度
int64_t lock_timeout = -1; //等待鎖時(shí)間，線上一般設(shè)置為5s
int64_t expiration = -1; //持有鎖時(shí)間，
}

以上就是RocksDB上鎖機(jī)制的實(shí)例詳解的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！