网站建设运营法律风险防范,wordpress站点路径,网站建设公司郴州,亚马逊做网站文章目录1、RocksDB 摘要1.1、RocksDB 特点1.2、基本接口1.3、编译2、LSM - Tree2.1、Memtable2.2、WAL2.3、SST2.4、BlockCache3、读写流程3.1、读取流程3.2、写入流程4、LSM-Tree 放大问题4.1、放大问题4.2、compactionRocksDB 是 Facebook 针对高性能磁盘开发开源的嵌入式持…
文章目录1、RocksDB 摘要1.1、RocksDB 特点1.2、基本接口1.3、编译2、LSM - Tree2.1、Memtable2.2、WAL2.3、SST2.4、BlockCache3、读写流程3.1、读取流程3.2、写入流程4、LSM-Tree 放大问题4.1、放大问题4.2、compactionRocksDB 是 Facebook 针对高性能磁盘开发开源的嵌入式持久化存储系统采用了 WAL 机制和 LSM Tree 结构。RocksDB 所有类型的数据都是采用追加写没有更新文件的操作。比较适合使用基于 Append Only 的高性能分布式文件系统。1、RocksDB 摘要
1.1、RocksDB 特点
基于 LevelDB嵌入式 KV 存储引擎针对写密集型场景而提出的解决方案。例日志系统、海量数据存储、海量数据分析紧凑型存储。相同的数据量更少的空间占用。基于 LSM-Tree 的存储结构。 内存MemTable磁盘SST | WAL
1.2、基本接口
OpenGet获取 keyPut存放 keyDelete删除 key具体在 compaction 中删除SingleDelete针对从未修改过的 key比 delete 删除快Merge合并新写入的数据。带来大量的读数据请求提前获取 Merge 的增量数据然后进行合并。Iterator通过给定的 key 批量获取符合条件的 KV 记录。
1.3、编译
# 1、RocksDB
git clone https://github.com/facebook/rocksdb.git
cd rocksdb
# 编译成调试模式
make
# 编译成发布模式
make static_lib # 压缩库 Ubuntu
# gflags
sudo apt-get install libgflags-dev
# snappy
sudo apt-get install libsnappy-dev
# zlib
sudo apt-get install zlib1g-dev
# bzip2
sudo apt-get install libbz2-dev
# lz4
sudo apt-get install liblz4-dev
# zstandard
sudo apt-get install libzstd-dev2、LSM - Tree
RocksDB 架构基于 LSM-Tree, log structured merge tree 存储结构其核心就是利用顺序写来提升写性能。
LSM-Tree 组成
内存可写的 MemTable 只读的 Immutable Memtable磁盘WAL 多层级 SST
LSM-Tree VS B Tree
LSM-Tree顺序写追加更新。问题数据冗余需要后台线程 compactionB Tree随机写就地更新。问题磁盘随机 IO 磁盘顺序 IO且锁粒度大
接下来从整体上先介绍 RocksDB 架构图如图所示
用户的数据需要同时写到内存中的 Memtable 数据结构和磁盘 WAL 日志。可写的 Memtable 用于快速索引查询的缓存数据并采用了跳表数据提升查找数据的速度。定时转换成只读的 Immutable Memtable保存到 SST 文件中flush 磁盘操作。在此期间若出现服务故障重启系统会从 WAL 中将数据通过 Redo 的方式回复到 Memtable。
为了定期 compact 合并压缩数据将 Immutable Memtable 分为多个层次。Level 0 层允许数据重复文件间无序文件内部有序Level 1 ~ Level N 没有数据重复跨层可能有重复文件间是有序的。数据逐层愈冷压缩程度愈高。SST 文件为每一层的主要存储方式。
读取数据时先读内存 Memtable若没有再读磁盘 SST 文件。
参考论文Chen G J, Wiener J L, Lyer S, et al. Realtime data processing at facebook[C]. Proceedings of the 2016 International Conference on Management of Data. 2016: 1087-1098.2.1、Memtable
Memtable 内存数据结构其中的数据总是最新的。同时服务于读和写写操作先插入 Memtable读数据先查询 Memtable。当 Memtable 写满修改为只读的 Immutable Memtable并被新的 Memtable 替换。后台线程会该 Immutable Memtable 异步落盘flush到一个 SST 文件落盘后销毁 Memtable。
Memtable 基于跳表实现。跳表是多层级有序链表其特点是
从最高层次开始跳跃查找并记录跳跃路径查询时间O(logn)找到待插入位置后插入节点并随机层高根据跳跃路径构建层级链表关系
跳表应用场景
范围查询快速有序地列出所有的节点并发粒度非常低。相较红黑树加锁整棵树只将相邻的结点操作加锁
重要参数
# 一个 memtable 的大小
write_buffer_size
# 管理 memtable 使用的总内存数
db_write_buffer_size
# 刷盘到 SST 文件的最大 memtable 数
max_write_buffer_number复习其他常见的层级数据结构
跳表多层级有序链表B 树叶子节点包含所有的数据非叶子节点只包含索引 key 信息时间轮按照定时任务到期时间轻重缓急进行分层
2.2、WAL
WAL, Write Ahead Log。RocksDB 中的 DML 操作同时写入内存 Memtable 和磁盘 WAL 日志文件。当系统崩溃时WAL 日志可以完整恢复 Memtable 中的数据以保 WAL中的数据通过 redo 的方式恢复到 Memtable。
重要参数
# WAL 文件的最大大小
DBOptions::max_total_wal_size
# WAL 文件的删除时间
DBOptions::WAL_ttl_seconds2.3、SST
SST, Sorted String Table有序键值对集合是 LSM - Tree 在磁盘中的数据结构。与 B Tree 就地更新不同找到元数据所在页并修改值LSM-Tree 直接 append 写到磁盘再同通过合并的方式取出冗余数据。
为了加快 key 的查询速度
建立索引布隆过滤器Bloom Filter判断某个字符串一定不在该集合若该字符串存在可能有误差。 原理位图 N 个哈希算法。key 经过 N 个哈希后若对应的位图是 0则 key 不存在场景限制不支持删除 key而 SST 本身不会被修改所以可以使用。
SST 文件格式
Footer程序启动位置存储 IndexBlock 和 MetaIndexBlock 的位置IndexBlock存储 DataBlock 的位置MetaIndexBlock存储了过滤元数据、属性信息、压缩字典索引的位置DataBlock存储有序的数据记录
引用论文Cho M, Choi W, Park S H. A Study on WAF reduction and SST file size on RocksDB[C]. Proceedings of the Korea Information Processing Society Conference. Korea Information Processing Society, 2017: 709-7122.4、BlockCache
背景内核 page cache 不可定制。因此用户可以在内存中指定 RocksDB 缓存块传一个 Cache 对象给 RocksDB 实例。一个缓存对象可以在同一个进程的多个 RocksDB 实例之间共享。块缓存存储未压缩过的块也可以设置块缓存去存储压缩后的块。
RocksDB 两种类型的缓存都通过分片来减轻锁冲突容量被平均分配到每个分片分片间不共享空间。默认情况下每个缓存会被分成 64 个分片每个分片至少 512 B。
默认情况下索引和过滤块都在 BlockCache 外面存储用户可以选择将它们缓存在 BlockCache 中
LRUCache基于 LRU 算法lru 列表 哈希表。ClockCache基于 Clock 算法clock 指针 环形列表 哈希表。
与 LRU 缓存比较Clock 缓存有更好的锁粒度。LRU 缓存读取数据时需要对所有分片加互斥锁因为需要更新的 LRU 列表而在 Clock 缓存上读取数据时不需要申请该分片的互斥锁只需要搜索并行的哈希表。只有在插入的时候需要每个分片的锁锁粒度更小。因此一定环境下Clock 缓存性能更好。
3、读写流程
3.1、读取流程
先读内存 memtable若不存在读磁盘 SST
SST 查找流程
FindFiles。从 SST 文件中查找如果在 L0那么每个文件都得读因为 L0 不保证 key 不重叠如果在更深的层key 保证不重叠每层只需要读一个 SST 文件即可。L1 开始每层可以在内存中维护一个 SST 的有序区间索引在索引上二分查找即可。LoadIB FB。IB, index block是 SST block 的索引FB, filter block 是一个布隆过滤器可以快速排除 key 不在的情况因此优先加载。SearchIB。二分查找 index block找到对应的 blockSearchFB。用布隆过滤器过滤如果没有则返回LoadDB。加载 block 到内存SearchDB。block 中继续二分查找ReadValue。找到 key 后读数据。若考虑 WiscKey KV 分离的情况还需要去 vLog 中读取
3.2、写入流程
写入磁盘 WAL 文件写入内存 memtablememtable 大小达到阈值后冻结成 immutable memtable。后续的写入交给新的 memtable 和 WAL后台 compaction 线程将 immutable memtable 落盘成 level 0 的 SST持久化后释放对应的 WAL若插入新的 SST 后当前层 Li 的总文件大小超出阈值会从 level i 挑出一个文件和 level i 1 层的重叠文件合并直到所有层的大小都小于阈值。合并过程中保证 level 1 以后各 SST 的 key 不重叠
4、LSM-Tree 放大问题
4.1、放大问题
读放大描述物理读取的字节数相较于返回的字节数之比。RocksDB 读取操作需要分层依次查找直到找到对应数据该过程可能涉及多次 IO写放大描述磁盘上存储的数据字节数相较于数据库包含的逻辑字节数之比。所有的写入操作都是顺序写而不是就地更新无效数据不会马上被清理掉。空间放大描述实际写入磁盘的数据大小和程序要求写入的数据大小之比。为了减小读放大和空间放大RocksDB 采用后台线程合并数据的方式来解决但会造成对同一条数据多次写入磁盘
4.2、compaction
rocksdb 默认采用 leveled compactionleveled tiered合并算法。compaction 操作会造成写放大但会减少读放大空间放大。
除 L0 外其他层级不会出现重复数据。
leveled每一层只有一个文件且每一层文件大小是上一层的 10 倍tiered将文件分成拆分成大小相同的部分
将相邻层的重复数据进行合并。同时也可以并行 compaction
