RocksDBのロック機構の例を詳しく解説

RocksDB は、オープンソースのストレージ エンジンとして、トランザクションの ACID 特性をサポートします。ACID の I (Isolation) をサポートするには、同時実行制御が不可欠です。この記事では主に、RocksDB のロック メカニズムの実装について説明します。この記事を通じて、読者が RocksDB 同時実行制御の原則を深く理解できることを願っています。この記事は主に次の 4 つの側面から始まります。まず、RocksDB のロックの基本構造を紹介します。次に、RocksDB の行ロック データ構造の設計におけるロック スペースのオーバーヘッドを紹介します。次に、いくつかの代表的なロック プロセスを紹介します。最後に、メカニズムの中で重要なデッドロック検出メカニズムを紹介します。

1. 行ロックのデータ構造
RocksDB の最小ロック粒度は行であり、KV ストレージの場合、ロック オブジェクトはキーであり、各キーは LockInfo 構造に対応します。すべてのキーはハッシュ テーブルを通じて管理され、ロックを検索する場合は、ハッシュ テーブルを通じてキーを直接見つけて、キーがロックされているかどうかを判断できます。しかし、グローバルにハッシュ テーブルが 1 つしかない場合、このハッシュ テーブルにアクセスする際に多くの競合が発生し、同時実行パフォーマンスに影響します。 RocksDB はまず Columnfamily によって分割され、各 Columnfamily のロックは LockMap によって管理され、各 LockMap は LockMapStripe とハッシュ テーブル (std::unowned_map
関連するデータ構造は次のとおりです:

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) スナップショットを作成し、イテレータに基づいて主キーをスキャンします
2) get_row_by_rowid を介してキーをロックしてみます
3)。キーを渡し、シーケンスを比較してキーが更新されたかどうかを判断します
4) キーが他のトランザクションによって更新されている場合 (キーに対応する SequenceNumber がスナップショットより新しい場合)、再試行がトリガーされます
。 5) 再試行の場合、古いスナップショットが解放されてロックが解除されます。tx->acquire_snapshot(false) を使用してスナップショットの取得を遅らせます (ロック後にスナップショットを取得します)
5)。この時点ではキーがロックされているため、再度 get_for_update を実行してください。
6). 更新操作
7) を実行し、主キーが条件を満たさなくなるまで実行を続けます。

3.3. セカンダリ インデックスに基づいて更新
このシナリオは 3.2 と似ていますが、セカンダリ インデックスから主キーを見つけるプロセスが 1 つ増えています。
1) スナップショットを作成し、イテレーターに基づいてセカンダリ インデックスをスキャンします。実際には、get_row_by_rowid も呼び出されます。キー
3)。セカンダリインデックスに従って次の主キーをトラバースし続け、ロックを試みます
4) 返されたセカンダリインデックスが条件を満たさない場合、終了します
3.4 違いInnoDB でのロックの間

私たちはここにいました RocksDB と InnoDB の違いについて言えば、更新シナリオでは、RocksDB は引き続きスナップショットを読み取りますが、InnoDB は現在の読み取りを行うため、動作に違いが生じます。たとえば、RC 分離レベルでの範囲更新シナリオでは、トランザクションで 1,000 件のレコードを更新する必要があるため、999 番目のレコードをスキャンすると、このキーのシーケンスが検出される可能性があります。スキャンされたスナップショット (他のトランザクションによって更新されたこのキー) より大きい場合、今度はスナップショットの再取得がトリガーされ、このスナップショットに基づいて最新のキー値が取得されます。 InnoDB にはこの問題はありません。現在の読み取りおよびスキャン プロセスを通じて、999 番目のレコードが更新された場合、InnoDB は最新のレコードを直接確認できます。この場合、RocksDB と InnoDB で表示される結果は同じです。別のケースでは、新しく挿入されたキーもスキャン範囲内にあると仮定すると、このキーのシーケンスは間違いなくスキャンされたスナップショットよりも大きいため、このキーはスキャン プロセス中に除外され、存在しなくなります。競合検出と呼ばれる場合、このキーは見つかりません。更新プロセス中に、ID 1 と 900 の 2 つのレコードが挿入されました。最終的に、900 番目のレコードは非表示のため更新できませんでした。 InnoDB の場合は現在読み取り中なので、新しく挿入された ID 900 のレコードを参照して更新できるので、この点が InnoDB との違いです。
更新がスナップショットに基づいているという違いに加えて、RocksDB はロックにおいてもより簡潔です。具体的には、更新プロセス中に一意の制約が含まれる場合、主キーのみがロックされます。 , ロックが必要ですが、通常のセカンダリ インデックスをロックする必要はありません。これは、一意制約の競合を回避するためです。ここで、一意制約（主キーまたは一意インデックス）を更新する場合は、ロックが必要です。たとえば、InnoDB は各インデックスをロックする必要があります。たとえば、更新がセカンダリ インデックスに基づいて配置される場合、セカンダリ インデックスもロックする必要があります。この違いの理由は、InnoDB が RR 分離レベルを実装しているためです。ここで分離レベルについて少し説明しましょう。実際、MySQL で定義されている RR 分離レベルは、SQL 標準で定義されている分離レベルとは多少異なります。 SQL 標準では、反復不可能な読み取りの問題を解決するための RR 分離レベルと、ファントム読み取りの問題を解決するためのシリアル化可能な分離レベルが定義されています。非反復読み取りは、同じレコードの値が変更されないことを強調します。一方、ファントム読み取りは、2 回の読み取りによって返されるレコードの数が固定されており、レコード数が増減しないことを強調します。 MySQL は、反復不能読み取りとファントム読み取りの問題を解決するために RR 分離レベルを定義しますが、InnoDB での RR 分離レベルの実装は GAP ロックに依存しています。 RocksDB は GAP ロックをサポートしません (一意の制約チェックと存在しないキーのロックのみをサポートします)。これは、スナップショット ベースのメカニズムが新しく挿入されたレコードを効果的に除外できるためです。一方、InnoDB は現在の読み取りのためにギャップ ロックを介した他の挿入を禁止する必要があるためです。主にロック ギャップのためにセカンダリ インデックスもロックする必要があります。そうしないと、現在の 2 つの読み取りの結果が異なる可能性があります。もちろん、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 中国語 Web サイトの他の関連記事を参照してください。