如何判断RocksDB中的文件是否过期

发布网友发布时间：2022-05-02 02:34

共2个回答

懂视网时间：2022-05-02 06:55

1.行锁数据结构
RocksDB锁粒度最小是行，对于KV存储而言，锁对象就是key，每一个key对应一个LockInfo结构。所有key通过hash表管理，查找锁时，直接通过hash表定位即可确定这个key是否已经被上锁。但如果全局只有一个hash表，会导致这个访问这个hash表的冲突很多，影响并发性能。RocksDB首先按Columnfamily进行拆分，每个Columnfamily中的锁通过一个LockMap管理，而每个LockMap再拆分成若干个分片，每个分片通过LockMapStripe管理，而hash表(std::unordered_map<std::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<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; //持有锁时间，
}

参考文档
https://github.com/mdcallag/mytools/wiki/Cursor-Isolation
https://www.postgresql.org/docs/9.4/static/transaction-iso.html
https://github.com/facebook/mysql-5.6/issues/340
http://www.cnblogs.com/digdeep/p/4947694.html
http://www.cnblogs.com/digdeep/archive/2015/11/16/4968453.html

RocksDB上锁机制

标签：结构 odi 深度优先空间 hang 范围数据结构 isolation shared

热心网友时间：2022-05-02 04:03

RocksDB底层存储结构是LSM，有很多Level的sst文件，sst文件需要定期compaction。那么，当一些文件参与compaction，生成新文件之后，旧文件会占用一定的存储空间，那么旧文件何时物理退场是一个问题，毕竟这些部分旧文件可能还在被使用。比较粗暴的方法就是这些文件保留特定时间之后，再进行物理退场。不过这种解决方法也存在一个问题，即若特定时间内积累的这些旧文件过多，会占用大量的存储空间。不过这种解决方案虽然存在问题，但是没有其他太多的副作用，实现起来也比较简单。那么RocksDB是如何管理这些旧文件的呢？
对于RocksDB，底层基于LSM结构，由一系列sst文件组成。在每次compaction之后，新生成的文件会注册到数据库中，而参与过compaction的旧文件也需要物理删除。然而，这些旧文件不能被立即删除，因为旧文件中的部分文件可能因为RocksDB中操作被占用，直到这些文件被占用结束。
sst文件列表存储在version数据结构中。每次compaction之后或者内存数据刷新落盘后，就会产生一个新version。同一时间，只有一个“当前”版本。它表示LSM树中最新的文件。任何新的操作或迭代器在整个读过程或者生命周期中都会使用最新版本对应的文件。而所有被占用的版本对应的文件都要被保留。而所有那些没有在version中的文件就应该被删除了。如下举一个例子：
v1={f1,f2,f3} (当前版本对应的文件列表)

存储在磁盘上的文件：f1, f2, f3
这个时候创建了一个新的迭代器1，会使用v1版本
此时，存储在磁盘上的文件依旧是f1, f2, f3
这个时候，发生一次刷新落盘,新增文件f4，此时会创建一个新version：
v2={f1,f2,f3,f4}(当前版本)
v1={f1,f2,f3}（该版本被迭代器1使用）

此时，存储在磁盘上的文件是f1, f2, f3, f4
又发生一次compaction,将f2,f3,f4合并成f5，形成一个新版本v3：
v3={f1,f5}(当前版本)
v2={f1,f2,f3,f4}
v1={f1,f2,f3}(该版本被迭代器1使用)

此时，存储在磁盘上的文件是f1, f2, f3, f4, f5
然而，此时v2既不是最新版本，也没有被任何操作、迭代器使用，那么这个版本理应被删除，包括f4。而v1依旧不能被删除，因为它仍然被迭代器1使用。此时，版本状态如下：
v3={f1,f5}(当前版本)
v1={f1, f2, f3}(该版本被迭代器1使用)
此时，存储在磁盘上的文件为：f1, f2, f3, f5
当迭代器1销毁后，
v3={f1,f5}(当前版本)
v1={f1,f2,f3}
此时，存储在磁盘上的文件为：f1, f2, f3, f5
现在，v1既不是最新版本，也没有被占用，v1理应被删除，包括文件f2,f3。
此时，有效版本如下：

v3={f1,f5}(当前版本)

此时，存储在磁盘上的文件为：f1, f5
可以通过引用技术实现以上逻辑。每一个sst文件以及每一个版本都有引用技术。
sst引用计数变化：
1.当我们创建一个新版本时，我们会对所有文件增加引用计数。
2.当一个版本没有被占用时，这个版本对应的所有文件引用计数都要减1。
3.当一个文件的引用技术降至0时，该文件就可以被物理删除了。
版本引用计数变化：
1.当创建一个版本时，它是最新的版本，此时该版本引用计数为1
2.当一个版本不再是最新的版本时，此时该版本引用计数减1
3.任何人使用某版本时，该版本引用计数加1，使用结束，该版本引用计数减1
4.当一个版本引用计数为0时，该版本应该被删除

5.当一个版本为最新版本或者被使用时，此时该版本引用计数不为0，因为需要保留
有时，对版本的引用计数会直接维护，比如对文件做compaction时。然而，更多情况下，是通过super version数据结构来间接维护引用计数，super version维护内存表以及版本的引用计数。每次阅读过程只需要增加以及减少一次引用计数，而super version会维护版本的引用技术。这种机制能够避免引用技术被锁住较长时间。
RocksDB将所有版本信息维护在VersionSet数据结构中，同时记录“最新”版本。因为每个column family都有各自的LSM，它们有自己的版本列表，有对应的最新版本。但是在整个数据库中，只有一个VersionSet维护所有column failies的版本信息。