首頁  >  文章  >  資料庫  >  RocksDB上鎖定機制的實例詳解

RocksDB上鎖定機制的實例詳解

零下一度
零下一度原創
2017-07-03 09:31:442446瀏覽

      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_map778caf43aec31ff36e12de3aca6abf8d)則存在於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<std::string, LockInfo> 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, 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.行锁空间代价
    由于锁信息是常驻内存,我们简单分析下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).當傳回的二級索引不符合條件時,則結束

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将新加入的等待关系解除,并报死锁错误。

相关的数据结构:

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; //是否检测死锁
int64_t deadlock_detect_depth = 50; //死锁检测的深度
int64_t lock_timeout = -1; //等待锁时间,线上一般设置为5s
int64_t expiration = -1; //持有锁时间,
}




以上是RocksDB上鎖定機制的實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn