TiKV 顺序扫数据流程详解

TiKV （字节开源数据库的Key-Value 存储引擎）采用顺序扫（Forward Scan）来读取数据。顺序扫的核心目标是在给定的时间戳范围内，找到所有符合条件的数据版本。这一机制对于确保事务一致性至关重要，特别是在高并发场景下。

以下是顺序扫的实现流程：

数据格式

在事务写入完成后，RocksDB 中的数据分布如下：

CF 类别	Key Format	Value Format
Lock	Lock 的 Key 和 Timestamp	Lock 的类型、主键、锁持续时间等信息
Default	Key + `commit_ts`	行键的值
Write	Key + `commit_ts`	beginTransaction的类型和开始时间

Key 的编码处理：

User Key：经过 Memory Comparable Encoding，使其与 Timestamp 的组合 Key 保持顺序。

Timestamp：存储取反形式，确保 newer data（较大 Timestamp）排列在前面。

顺序扫流程

顺序扫的代码位于，主要定义为：

def scan(self, scan_ts: Timestamp, lower_bound: Key, upper_bound: Key) -> Result

步骤 1：初始化 Cursor

首次迭代时，将 Lock 和 Write Cursor 同时初始至 lower_bound。

if !self.is_started {    if self.cfg.lower_bound.is_some() {        self.write_cursor.seek(&self.cfg.lower_bound)?;        self.lock_cursor.seek(&self.cfg.lower_bound)?;    } else {        self.write_cursor.seek_to_first()?;        self.lock_cursor.seek_to_first()?;    }    self.is_started = true;}

步骤 2：比较 Cursor 的结果

Lock Cursor 和 Write Cursor 同时移动，找出第一个遇到的 User Key。

let w_key = if self.write_cursor.valid()? { Some(self.write_cursor.key()) } else { None };let l_key = if self.lock_cursor.valid()? { Some(self.lock_cursor.key()) } else { None };match (w_key, l_key) {    // ... Skipping detailed match logic ...}

步骤 3：处理各类情况

双 Cursor 同时为空：没有数据，结束扫描。

Write Cursor 有数据，Lock Cursor 无数据：处理 Write 的当前版本。

Write Cursor 无数据，Lock Cursor 有数据：处理对应的 Lock。

双 Cursor 同时有数据：比较 User Key，优先处理较低的 Key。

步骤 4：处理 Write 的数据

如果 User Key 来自 Write Cursor：

寻找符合 scan_ts 的最大版本：

next() 多次尝试，若找到直接取用。

seek() 若未找到，直接寻找目标 Key。

获取 Value：根据 Write Info，读取 Default CF 中的 Value。

移动 Cursor 跳过当前 Key 的其余版本，准备处理下一个 Key。

步骤 5：重复 ScanUntilDone

若没有找到数据，回到步骤 2，若有找到，则根据需要决定是否继续扫描。

样例解释

以事务 #1 和 #2 为例，结合 RockDB 中的数据，展示了顺序扫如何在给定 scan_ts 下高效读取相关 Key-Value 对。通过样例，清晰地展示了处理锁冲突和版本选择的逻辑，直观地体现了 MVCC 在高并发环境中的优势。

实现总结

并行 Cursor 操作：Lock和Write Cursor 并行处理，类似归并排序，确保最佳性能。

时间戳优化：通过取反和编码，保持数据存储的顺序，提升读取效率。

锁冲突处理：灵活处理锁状态，避免阻塞，确保事务一致性。

TiKV 的顺序扫机制不仅实现了高效的数据读取，还通过智能 Cursor 调度和版本管理，确保在复杂事务环境下的稳定性和一致性。这一设计为MVCC事务存储提供了坚实的基础，支持大规模实时应用。

转载地址：http://dfkoz.baihongyu.com/

你可能感兴趣的文章