Rocksdb

参考： https://github.com/facebook/r...https://github.com/facebook/r...https://blog.csdn.net/Z_Stand...https://www.jianshu.com/p/f57...https://book.tidb.io/session3...https://www.iggiewang.cn/2021...IntroductionRocksDB的Iterator在通过高度封装后，能够像C++ stl库为每一个容器结构的迭代器的iterator一样被应用，它能够定位到某个key，并能够从这个key开始进行scan，它也能够被用来进行反向scan。 如果在创立迭代器时，ReadOptions.snapshot被给定，迭代器将返回该snapshot的数据，如果传入的为nullptr，隐性视图将被创立，隐性视图不能转为显性。 用户对Iterator的应用NewIterator 创立一个迭代器，须要传入ReadOptionsSeek 查找一个keySeekToFirst 迭代器挪动到db的第一个key地位，个别用于程序遍历整个db的所有keySeekToLast 迭代器挪动到db的最初一个key地位， 个别用于反向遍历整个db的所有keySeekForPrev挪动到以后key的上一个地位，个别用于遍历(limit, start]之间的keyNext 迭代器挪动到下一个keyPrev迭代器挪动到上一个keyIterator::status()能够返回以后迭代器的error。error蕴含IO error，checksum不匹配，外部谬误等... 如果没有谬误，状态为Status::OK()。如果Iterator::Valid()是true，status必定为OK。而如果Iterator::Valid()为false，可能是因为此时迭代器走到了数据的开端，这种状况status是OK；也有可能是呈现了谬误，这种状况status不是OK。 5.13.x或更早的版本中，这两个API会有不同，须要再查阅文档。 各Iterator DBIterImplementation: db/db_iter.ccInterface: IteratorDBIter是对InternalIterator的封装，它的工作次要是将Internal key解析成user key，并展现进去 Example底层的InternalIterator中 InternalKey(user_key="Key1", seqno=10, Type=Put) | Value = "KEY1_VAL2"InternalKey(user_key="Key1", seqno=9, Type=Put) | Value = "KEY1_VAL1"InternalKey(user_key="Key2", seqno=16, Type=Put) | Value = "KEY2_VAL2"InternalKey(user_key="Key2", seqno=15, Type=Delete) | Value = "KEY2_VAL1"InternalKey(user_key="Key3", seqno=7, Type=Delete) | Value = "KEY3_VAL1"InternalKey(user_key="Key4", seqno=5, Type=Put) | Value = "KEY4_VAL1"DBIter将Internal Key解析为User Key，并裸露接口给用户 Key="Key1" | Value = "KEY1_VAL2"Key="Key2" | Value = "KEY2_VAL2"Key="Key4" | Value = "KEY4_VAL1"MergingIteratorImplementation: table/merging_iterator.ccInterface: InternalIteratorMergingIterator由很多Children Iterator组成 ...

参考： https://www.jianshu.com/p/9b5...https://zhuanlan.zhihu.com/p/...SST File Format之前在LSM-Tree局部有提过，但过后理解的比拟浅 <beginning_of_file>[data block 1][data block 2]...[data block N][meta block 1: filter block] [meta block 2: index block][meta block 3: compression dictionary block] [meta block 4: range deletion block] [meta block 5: stats block] ...[meta block K: future extended block] (More meta blocks may be added in the future)[metaindex block][Footer] (fixed size; starts at file_size - sizeof(Footer))<end_of_file>与BlockBasedTableBuilder相干的类有以下几个 BlockBasedTable, 该类封装了用于读取磁盘BlockBasedTable类型的SST表的逻辑。BlockBasedTableBuilder, 该类用于在磁盘上构建一个BlockBasedTable类型的SST表。BlockBasedTableFactory, 该类是BlockBasedTable工厂办法的实现，用于创立BlockBasedTable/BlockBasedTableBuilder。Write Block的程序：Write meta blocks, metaindex block and footer in the following order. ...

参考： https://github.com/facebook/r...https://zhuanlan.zhihu.com/p/...Remote Compaction机制使近程地Compaction成为可能，它能够是一个不同的过程，甚至是在近程的主机上。通过将Compaction服务迁徙到近程的主机上，不会有后盾的Compaction服务去影响read和write申请，进步了性能和稳定性。而专用于Compaction的近程主机能够只对Compaction做优化，并用来给不同的DB做Compaction。 Schedule第一步是数据库触发Compaction，它不会在本地进行Compaction，而是在CompactionService中发送 Compaction信息。用户须要实现CompactionService::Start()，来发送Compaction信息给远端过程，从而调度Compaction Compactremote的Compaction Worker须要运行应用发来的Compaction信息运行DB::OpenAndCompact()。Worker会在只读模式下进行Compact，它不能批改LSM Tree，而是将Compact的后果放在一个临时的地位。 Return Result当Compaction完结后，须要向原先的那台db返回后果，蕴含Compact的SST的元数据和一些internal的信息，与调度环节中相似的，此处两台机器的通信须要被实现。 Install & Purge原db通过CompactionService::WaitForComplete()期待后果返回，后果应该传入该函数并返回。在这之后，如果临时工作区和db不在同一个文件系统上，须要先把临时工作区的文件copy过来，而后再做重命名。

Compaction是RocksDB中很重要的机制，而RocksDB默认采纳Leveled Compaction策略。因而先着重剖析Leveled Compaction 文件构造 在磁盘上的文件分为多个level，其中，level 0是非凡的，它蕴含了刚刚被flush的Memtable，因而存在level 0中的数据会比其余level更新。此外，Level 0的各文件之间并不是有序的，而其余Level中的各个sstfile间是有序的，如下图这意味着除Level 0之外的其余Level都能够通过二分搜寻来精确地定位key的地位，而Level 0则不行。因为这个起因，Level 0的文件数目须要被严格控制。除Level 0之外的其余Level都有指标大小，这些指标大小个别呈指数级别增长 当L0层的文件数据达到level0_file_num_compaction_trigger，compaction会被触发，L0层的文件将会merge到L1层。因为L0层的SST文件之间是无序的，可能有重叠的局部，所以在做compaction时，失常会将L0层的所有文件全副merge sort后写到L1层。 在这次Compaction后，L1层的文件大小可能会超过指标大小，这种状况下，L1中的至多一个文件会被merge到L2中 须要留神的是，L1及以下Level的Compaction是并行的。而默认状况下，L0到L1压缩不是并行的。在某些状况下，它可能成为限度Compaction速度的瓶颈。RocksDB仅反对L0到L1的基于子压缩的并行化。要启用它，能够将max_subcompactions设置为大于1。而后，RocksDB将尝试对范畴进行分区，并应用多个线程来执行它： Compaction筛选当多个Level触发Compaction机制时，RocksDB须要决定先对哪个Level做Compaction。为了辨别优先级，对每个Level计算相应的Score 对于非L0层的层，score的计算形式为，level中所有sstfile的大小除以该level对应的指标大小（如果须要Compaction的文件已被选中，它将不蕴含在level总大小中）对于L0，score为（l0文件的总数量除以level0_file_num_compaction_trigger）和（总大小减去max_bytes_for_level_base）的最大值。 须要留神的是，如果文件数量小于level0_file_num_compaction_trigger，即便score再高，也不会从L0触发compaction

B+ Tree的毛病B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会缓缓决裂，逻辑上间断的叶子节点在物理上往往不间断，甚至拆散的很远，但做范畴查问时，会产生大量随机读IO。对于大量的随机写也一样，新插入的数据在磁盘上的地位可能相隔很远，会产生大量的随机写IO。 相比B+ Tree，LSM-Tree可能会损失一部分读性能，但换来了微小的写性能的晋升。 LSM-Tree原理 Memtable当一个Memtable被写满时，它将变为immutable的，前面进来的数据将写入一个新的Memtable。而后盾线程将会将Immutable Memtable flush进一个SST文件，并在flush好后将该Memtable销毁 数据结构可抉择的数据结构 SkipList (Default)HashLinkListHashSkipListVectorMemtable默认采纳跳表实现而哈希跳表我之前没有接触过，后果搜寻后发现是先对哈希值取模放入对应的桶中，再在每个哈希桶中保护跳表构造。这样的话应该会晋升随机单个查问的速度，而范畴查问应该会变慢一点。 此外，依据官网文档，只有SkipList反对并发插入。 Flush三种状况下会触发flush操作 当某一个Memtable的大小超出了ColumnFamilyOptions::write_buffer_size当所有列族的Memtable的总大小超出了DBOptions::db_write_buffer_size，或者DBOptions::write_buffer_manager收回了flush的信号。这种状况下size最大的那个Memtable将被flushWAL的大小超过了DBOptions::max_total_wal_size。这种状况下最老的Memtable将被flush，以便清空它相应的WAL中的局部。Write Ahead LogRocksDB的每次更新都会写入两个地位：内存中的memtable（稍后将flush到SST文件）和磁盘上的预写日志（WAL）。而当Memtable中的数据flush后，WAL中对应的数据将被删除 WAL被用作故障后复原数据，它默认是开启的。也能够通过配置敞开它。

问题形容编译环境MacOSM1 Progcc/opt/homebrew/Cellar/gcc/10.2.0_4/lib/gcc/10/gcc/aarch64-apple-darwin20/10.2.1/include/arm_acle.h: In function 'int __rndr(uint64_t*)':/opt/homebrew/Cellar/gcc/10.2.0_4/lib/gcc/10/gcc/aarch64-apple-darwin20/10.2.1/include/arm_acle.h:201:34: error: invalid conversion from 'uint64_t*' {aka 'long long unsigned int*'} to 'long unsigned int*' [-fpermissive] 201 | return __builtin_aarch64_rndr (__res); | ^~~~~ | | | uint64_t* {aka long long unsigned int*}<built-in>: note: initializing argument 1 of 'int __builtin_aarch64_rndr(long unsigned int*)'/opt/homebrew/Cellar/gcc/10.2.0_4/lib/gcc/10/gcc/aarch64-apple-darwin20/10.2.1/include/arm_acle.h: In function 'int __rndrrs(uint64_t*)':/opt/homebrew/Cellar/gcc/10.2.0_4/lib/gcc/10/gcc/aarch64-apple-darwin20/10.2.1/include/arm_acle.h:207:36: error: invalid conversion from 'uint64_t*' {aka 'long long unsigned int*'} to 'long unsigned int*' [-fpermissive] 207 | return __builtin_aarch64_rndrrs (__res); | ^~~~~ | | | uint64_t* {aka long long unsigned int*}<built-in>: note: initializing argument 1 of 'int __builtin_aarch64_rndrrs(long unsigned int*)'解决问题百思不得其解 最初终于在google搜到了和我一样问题的老哥https://githubmemory.com/repo... ...

相干材料The History of RocksDB: http://rocksdb.blogspot.com/2... RocksDB的诞生起因2011年中时，Dhruba Borthakur曾经在HBase/HDFS方面做了五年的开发工作，他十分青睐Hadoop优良的生态，但同时他想挑战一些新的货色：晋升HBase/HDFS的查问服务工作负载。 事实证明他在这方面做得很胜利，在对HBase/HDFS进行了多轮加强后，他曾经可能使HBase/HDFS的提早速度仅为MySQL服务器的两倍，并且HBase/HDFS在雷同硬件雷同工作负载下应用的IOPs仅为MySQL的三倍。 但这时，闪存存储成为了事实，数据集从旋转磁盘迁徙到闪存。而他通过测试后发现，2012年的HDFS/HBase存在一些软件瓶颈，因而无奈无效地应用闪存。如果数据存储在闪存中，那么就须要一个新的存储引擎，以便可能无效地为数据上的随机工作负载提供服务。 为什么RocksDB是嵌入式的？假如说，旋转磁盘上的读取或写入大概须要10毫秒，闪存的读取或写入大概须要100微秒。两台机器之间的网络提早放弃在50微秒。那么在CS架构中，通过网络拜访旋转磁盘上的数据会导致10.05毫秒的提早，网络施加的开销仅为0.5%。而假如用闪存驱动器代替磁盘，对于本地连接的闪存，数据拜访工夫为100微秒，通过网络拜访雷同数据的工夫为150微秒。这种状况下，网络数据拜访的开销比本地数据拜访高50%。简而言之，当闪存提供了极高的IO速度时，网络成为了性能的瓶颈。 为什么不应用现有的嵌入式数据库？过后现有的数据库曾经有很多了：BerkeleyDB, KyotoDB, SQLite3, leveldb。在这些数据库的开源基准测试中，leveldb仿佛是最快的那一个。但并非所有这些数据库都适宜在闪存上存储数据。因为闪存的写持久性无限，对闪存上数据块的更新通常会引入写入放大（write-amplification）。当对leveldb进行测试时，他发现它不适宜现实的服务器工作负载。开源基准测试后果乍一看十分棒，但只是针对一个大小小于测试机器的RAM的数据库。当在一个至多比main memory大5倍的数据库上执行雷同的基准测试时，性能后果令人丧气。 此外，leveldb的单线程压缩，频繁的写暂停导致99%的提早十分大。leveldb并不能生产闪存带来的io量。在闪存的倒退下，须要一个可能在读放大、写放大和空间放大之间进行优雅衡量的数据库。所以，RocksDB诞生了。 RocksDB的愿景带有点查找和范畴扫描的嵌入式键值存储针对疾速存储进行优化，例如闪存和RAM提供全面生产反对的服务器端数据库随CPU内核数和存储IOPs线性扩大须要留神的是，RocksDB不是分布式数据库。它没有内置容错或复制性能。它对数据分片无所不知。目前比拟多的计划应该是Raft+RocksDB。

前文提到，所有进入RocksDB的数据，会先进入内存，再flush进disk。本文，我们会学习到，RocksDB 如果管理和存储内存中的数据。 图1 RocksDB 架构图(source:https://www.slideshare.net/me... RocksDB有三种基本文件格式是 Memtable/SST file/Log file。Memtable 是一种内存文件数据系统，新写数据会被写进 Memtable，部分请求内容会被写进 Log file。Log file 是一种有利于顺序写的文件系统。Memtable 的内存空间被填满之后，会有一部分老数据被转移到 SST file 里面，这些数据对应的 Log file 里的 log 就会被安全删除。SST file 中的内容是有序的。 MemTable MemTable是一个内存数据结构，他保存了落盘到SST文件前的数据。他同时服务于读和写——新的写入总是将数据插入到memtable，读取在查询SST文件前总是要查询memtable，因为memtable里面的数据总是更新的。一旦一个memtable被写满，他会变成不可修改的，并被一个新的memtable替换。一个后台线程会把这个memtable的内容落盘到一个SST文件，然后这个memtable就可以被销毁了。并且在flush的过程中，会完成数据的压缩 RocksDB默认实现方式是SkipList，适用于范围查询和插入，但是如果是其他场景，RocksDB也提供了另外两种实现方式。具体区别可参考https://github.com/facebook/rocksdb/wiki/MemTable a vector memtable:适用于批量载入过程，每次新增元素都会追加到之前的元素后，当MemTable的数据被刷入L0时，数据会按之前的顺利刷入SST filea prefix-hash memtable:适用于带有指定前缀的查询，插入和scanImmutable Memtable 所有的写操作都是在memtable进行，当memtable空间不足时，会创建一块新的memtable来继续接收写操作，原先的内存将被标识为只读模式，等待被刷入sst。在任何时候，一个CF中，只存在一块active memtable和0+块immutable memtable。刷入时机有以下三个条件来确定： write_buffer_size 设置一块memtable的容量,一旦写满，就标记为只读，然后创建一块新的。max_write_buffer_number 设置memtable的最大存在数(active 和 immutable 共享)，一旦active memtable被写满了，并且memtable的数量大于max_write_buffer_number,此时会阻塞写操作。当flush操作比写入慢的时候，会发生这种情况min_write_buffer_number_to_merge 设置刷入sst之前，最小可合并的memtable数，例如，如果设置2，只有当 immutable memtable数量达到2的时候，会被刷入sst，数量为1的时候，则永远不会被刷入。由于每次Get()都需要线性查询每个memtable,所以，如果这个值太高，会影响写的性能 例如： write\_buffer\_size = 512MB;max\_write\_buffer\_number = 5;min\_write\_buffer\_number\_to\_merge = 2;当写入速达到 16MB/s，每32s会创建一块新的memtable,每64s会有2块memtable合并，并刷入sst 。Depending on the working set size,每一刷在512MB 到 1GB之间。为了防止刷入操作影响写性能，内存使用上限是5*512MB = 2.5GB。到达上限后，所有的写请求将会被阻塞。 ...