RocksDB 잠금 메커니즘의 예에 대한 자세한 설명

RocksDB는 오픈 소스 스토리지 엔진으로서 트랜잭션의 ACID 특성을 지원합니다. ACID에서 I(격리)를 지원하려면 동시성 제어가 필수적입니다. 이 기사에서는 주로 RocksDB의 잠금 메커니즘 구현에 대해 설명합니다. 이 글을 통해 독자들이 RocksDB 동시성 제어의 원리를 심도 있게 이해할 수 있기를 바랍니다. 이 기사는 주로 다음 네 가지 측면에서 시작됩니다. 먼저 RocksDB 잠금의 기본 구조를 소개하고 RocksDB 행 잠금 데이터 구조의 잠금 공간 오버헤드를 소개합니다. 그런 다음 몇 가지 일반적인 잠금 프로세스를 소개합니다. 마지막으로 메커니즘의 필수 교착 상태 감지 메커니즘을 소개하겠습니다.

1. 행 잠금 데이터 구조
RocksDB의 최소 잠금 단위는 행입니다. KV 저장소의 경우 잠금 개체가 키이고 각 키는 LockInfo 구조에 해당합니다. 모든 키는 해시 테이블을 통해 관리되며, 잠금을 찾을 때 해시 테이블을 통해 직접 찾아 키가 잠겨 있는지 확인할 수 있습니다. 그러나 전역적으로 해시 테이블이 하나만 있는 경우 이 해시 테이블에 액세스할 때 많은 충돌이 발생하여 동시성 성능에 영향을 미칩니다. RocksDB는 먼저 Columnfamily로 분할됩니다. 각 Columnfamily의 잠금은 LockMap으로 관리되며 각 LockMap은 LockMapStripe로 분할되고 해시 테이블(std::unordered_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). 1로 점프하여 기본 키가 조건을 충족하지 않을 때까지 계속 실행한 후 종료됩니다.

3.3. 보조 인덱스 기반 업데이트
이 시나리오는 보조 인덱스에서 기본 키를 찾는 프로세스에 한 단계가 더 있다는 점을 제외하면 3.2와 유사합니다.
1) 스냅샷을 생성하고 반복자를 기반으로 보조 인덱스를 스캔합니다.
2) 보조 인덱스에 따라 기본 키를 반대로 찾습니다. 실제로 이 프로세스도 호출됩니다. 키
3 ) 보조 인덱스에 따라 계속해서 다음 기본 키를 탐색하고 잠금을 시도합니다.
4) 반환된 보조 인덱스가 조건을 충족하지 않으면 종료됩니다

3.4 InnoDB 잠금 사이
RocksDB와 InnoDB의 차이점에 대해 말하자면, 업데이트 시나리오의 경우 RocksDB는 여전히 스냅샷을 읽는 반면 InnoDB는 현재 버전을 읽으므로 동작에 차이가 있습니다. 예를 들어 RC 격리 수준의 범위 업데이트 시나리오에서 트랜잭션은 1,000개의 레코드를 업데이트해야 하므로 잠금이 검색되고 잠겨 있으므로 999번째 레코드를 검색하면 이 키의 시퀀스를 찾을 수 있습니다. 스캔된 스냅샷(다른 트랜잭션에 의해 업데이트된 이 키)보다 크면 이번에는 스냅샷 다시 획득이 트리거되고 이 스냅샷을 기반으로 최신 키 값을 가져옵니다. InnoDB에는 이러한 문제가 없습니다. 현재 읽기 및 스캔 프로세스를 통해 999번째 레코드가 업데이트되면 InnoDB는 최신 레코드를 직접 볼 수 있습니다. 이 경우 RocksDB와 InnoDB에서 본 결과는 동일합니다. 또 다른 경우에는 새로 삽입된 키도 스캔 범위에 있다고 가정하면 이 키의 시퀀스는 의심할 여지없이 스캔된 스냅샷보다 크므로 이 키는 스캔 프로세스 중에 필터링되어 존재하지 않습니다. 충돌 감지라고 불리는 이 키는 발견되지 않습니다. 업데이트 과정에서 ID가 1과 900인 두 개의 레코드가 삽입되었습니다. 마지막으로 900번째 레코드가 보이지 않아 업데이트할 수 없었습니다. InnoDB의 경우 현재 읽고 있기 때문에 새로 삽입된 ID 900의 레코드를 보고 업데이트할 수 있다는 점이 InnoDB와의 차이점이다.
업데이트가 스냅샷을 기반으로 한다는 점 외에도 RocksDB는 잠금이 더 간결합니다. 특히 업데이트 프로세스 중에 열 업데이트에 고유 제약 조건이 포함되면 기본 키만 잠깁니다. , 잠금이 필요합니다. 일반 보조 인덱스는 잠글 필요가 없습니다. 이 목적은 고유 제약 조건 충돌을 방지하는 것입니다. 여기서 고유 제약 조건(기본 키 또는 고유 인덱스)이 업데이트되면 잠금이 필요합니다. InnoDB는 각 인덱스를 잠가야 합니다. 예를 들어 업데이트가 보조 인덱스를 기반으로 배치되면 보조 인덱스도 잠가야 합니다. 이러한 차이가 발생하는 이유는 InnoDB가 RR 격리 수준을 구현하기 때문입니다. 여기서 격리 수준에 대해 조금 이야기해 보겠습니다. 실제로 MySQL에서 정의하는 RR 격리 수준은 SQL 표준에서 정의하는 격리 수준과 다소 다릅니다. SQL 표준은 반복 불가능한 읽기 문제를 해결하기 위해 RR 격리 수준을 정의하고 팬텀 읽기 문제를 해결하기 위해 직렬화 가능 격리 수준을 정의합니다. 반복 불가능 읽기는 동일한 레코드의 값이 수정되지 않는다는 점을 강조하는 반면, 팬텀 읽기는 두 번의 읽기에 의해 반환되는 레코드 수가 고정되어 있으며 레코드 수를 늘리거나 줄이지 않는다는 점을 강조합니다. MySQL은 반복 불가능한 읽기 및 팬텀 읽기 문제를 해결하기 위해 RR 격리 수준을 정의하는 반면, InnoDB의 RR 격리 수준 구현은 GAP 잠금에 의존합니다. RocksDB는 스냅샷 기반 메커니즘이 새로 삽입된 레코드를 효과적으로 필터링할 수 있기 때문에 GAP 잠금을 지원하지 않습니다(고유한 제약 조건 검사만 지원하고 존재하지 않는 키는 잠급니다). 반면 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!