看图了解RocksDB

简介: 它是一个高性能的Key-Value数据库。设计了完善的持久化机制,同时保证性能和安全性。能够良好的支持范围查询,因为K-V记录就是按照Key来排序的。 下图为写入的流程: 可以看到主要的三个组成部分,内存结构memtable,类似事务日志角色的WAL文件,持久化的SST文件。

它是一个高性能的Key-Value数据库。设计了完善的持久化机制,同时保证性能和安全性。能够良好的支持范围查询,因为K-V记录就是按照Key来排序的。


下图为写入的流程:

b06ff0742ae3821223fb29274aef0b3e653c2f67

可以看到主要的三个组成部分,内存结构memtable,类似事务日志角色的WAL文件,持久化的SST文件。

数据会放到内存结构memtable,一定条件下触发写到到SST文件。写入WAL文件是可选的,用来恢复未写入到磁盘的memtable

memtable如其名为一种内存的数据结构。通过设置memtable的大小、总大小来控制何时flushSST文件。大部分格式的memtable不支持并发写入,并发调用依然会依次写入。

WAL全称wirte ahead log。打开dbflush列族(一种逻辑分片机制)都会创建WAL文件,所包含的数据全部从memtable写入SST文件后WAL文件会被归档。通过设置WAL上限也会触发flush


下图展示了读取的层次:

be279f90e727321873d47cbbdc97706d46ee9f37


memtableSST文件组成数据的全集。之上是缓存层,缓存为提升查询性能做了分片,底层都采用hash查询,不同缓存结构的区别在于热点数据的替换逻辑。访问数据库时,都是访问的打开时间点的view(我猜测一个key有不同时间戳的多条记录)。除了直接查询db,还提供了查询快照的机制。直接访问db时,会持有文件句柄,这样多个SST文件合并时,已经被合并但被访问的文件就不能被删除。而快照机制保证了访问过程中文件能被删除(我并未想明白如何做到的),不过打开期间被删除的key的记录还会在新合并的文件里存在。


memtable的结构有几种可选,本质都是排序的结构(为了支持范围查询)

9ec7aa51eae012d152f677869b6b2746486b8fab

其中之一是上图的跳跃表,不了解跳跃表机制的读者可以简单理解为有序支持近似二分查找的时间复杂度为log2(N)的结构

f4e36ab8af1e045174ff6875f4992e32a532ec79

另外一种是hash结合跳跃表,是按照key的前缀做hash,单独访问一个key时性能更好,范围查询性能会差些


WAL文件结构如下图,按照写入的顺序来存储变长的K-V,按照固定长度来分组存储(可能一个K-V跨多个分组)的目的是便于读取

770db51ff074cfede56f2dd0dd65d7380b5d632e


支持几种SST文件结构

08b51387b3ac49e9d4973cc416c94deb0aad52f1

上图为按照多块来存储的结构。每块的K-V都是有序的,而多块也是有序的。文件中包含元数据相关的信息,包括数据压缩字典、过滤器等。会按照数据块所属的K-V范围来创建索引,为提升查询性能会给索引分片。

56765ff825d19c49ee00045b25e890ac93aeedc5

另外一种结构是每个K-V来存储。它的索引比较特殊,由hash结构和二进制查找缓存两部分组成。依然按照key的前缀做hash,如果桶对应的K-V记录很少,则直接指向第一个key(有多个key属于该桶)的记录位置。如果属于桶的K-V记录多于16条,或者包含多于一个前缀的记录,则先指向二进制查找缓存(先二分查找),而后指向第一个key的记录位置。


随着K-V的写入,会生成很多的SST文件。这部分文件需要被合并到一起,从而降低打开文件数量,并且移除已经不存在的记录。

介绍合并之前先了解sorted runs的概念。一个sorted run可以理解为一个时间段的所有数据,不同sorted run会覆盖不同时间段。通常会给sorted run编号,并称作levelX,时间范围越早的sorted run编号越高(level0的数据最新,也是memtable,严格意义上说不属于sorted run,因为不一定有序)。

rocksdb主要提供了两类方式,通用合并(有时亦称作tiered)与leveled合并(rocksdb的默认方式)。它们的最主要区别在于频度,后者会更积极的合并小的sorted run到大的,而前者更倾向于等到两者大小相当后再合并。

04366fb186369a1deec6397dbf60a08f27f640fa

上图为通用合并过程

我把通用合并简单理解为更简单粗暴的合并,可以尽量降低磁盘的写入,但会增大读取,需要更大的临时空间(极端时需要两倍数据容量的磁盘空间)。遵循的一个规则是“合并结果放到可能最高的level”。是否触发合并是依据设置的空间比例参数。
size amplification ratio =
(size(R1) + size(R2) + ... size(Rn-1)) / size(Rn)

5648b0f7ca826251097d4a1e0a27434f2be180fa

上图为level合并过程

每个level有相应的目标大小,超出后会触发本level与下一level的文件合并到一起。合并是可以并发执行的(L0L1比较特殊需要先分片后才能并行)。


总结下rocksdb做了哪些设计来满足预期的使用场景。所有记录在业务上是有序的,对key的查询其实会执行类似二分查找。持久化是通过写入有序文件来实现的。高性能的写入是通过先写入内存结构来保证的(写满的内存结构刷到持久化文件)。提供了level机制对数据做分层,优先查询最新写入的level从而提升查询性能。针对查询有常见的缓存、索引机制,也有压缩、编码机制来节省存储空间。


目录
相关文章
|
1月前
|
存储 SQL 缓存
|
1月前
|
存储 NoSQL 关系型数据库
RocksDB 事务实现和应用场景
RocksDB 事务实现和应用场景
|
8月前
|
存储 SQL 缓存
第7章_InnoDB数据存储结构
第7章_InnoDB数据存储结构
167 0
|
存储 算法 关系型数据库
InnoDB数据存储结构
InnoDB数据存储结构整理
103 0
|
存储 SQL NoSQL
KV型数据存储引擎LevelDB/BerkeleyDB/lmdb/comdb/rocksdb/UnQLite
KV型数据存储引擎LevelDB/BerkeleyDB/lmdb/comdb/rocksdb/UnQLite
710 0
|
Web App开发
RocksDB 写入流程详解
最初的写入流程,继承自 leveldb,多个 写线程组成一个 group, leader 负责 group 的 WAL 及 memtable 的提交,提交完后唤醒所有的 follwer,向上层返回。 支持 allow_concurrent_memtable_write 选项,在1的基础上,leader 提交完 WAL 后,group 里所有线程并发写 memtable。
|
Java 关系型数据库 MySQL
RocksDB TransactionDB事务实现分析
## 基本概念 #### 1. LSN (log sequence number) RocksDB中的每一条记录(KeyValue)都有一个LogSequenceNumber(后面统称lsn),从最初的0开始,每次写入加1。该值为逻辑量,区别于InnoDB的lsn为redo log物理写入字节量。 这个lsn在RocksDB内部的memtable中是`单调递增`的,在WriteA
4205 0
|
关系型数据库 Java MySQL
RocksDB事务实现TransactionDB分析
本文主要对RocksDB中事务实现TransactionDB做分析,设计事务并发、隔离级别、MVCC等实现细节
9205 0