背景 图片来自于SmartKeyerror 此图为 SSTable 的总览图，如图所示主要由下面几个模块构成 Data Block ： 具体的数据块，存储 (key value)，并在存储时通过前缀压缩等方法进行优化 Meta Block ： 为了方便查询所建立的过滤块，leveldb中使用的是布隆过滤器，该过滤块可以快速判断 key 是否存在 Metaindex Block ： 对 Meta Block 块的索引块，默认 Meta Block 为 4K 大小 Index Block ：对 Data Block 块的索引块 Footer ：存储 Metaindex Block 与 Index Block 的偏移地址 分析触发 Compaction接下来我们将从 leveldb 的源码部分看看一个 SSTable 究竟是如何产生的 首先是一个大致的调用逻辑: leveldb 会在对外接口 open 中去调用 MaybeScheduleCompaction 函数，从名字中得知，此函数应该是调度触发压缩(Compaction)，为什么是Maybe呢？ 12345678910111 ...

背景一般来说，哈希表的实现是通过两个部分实现的 12hash = hashfunc(key)index = hash % table_size 使用求模来减少存储空间，所以必然会导致不同的数据离散到相同的索引下标处，此时就发生了哈希冲突。 解决方案主要分为两大类 链式法 （Separate Chaining） 开放地址法（Open Addressing） 链接技术将采用额外的数据节点来处理冲突。当冲突发生时，在冲突位置建立链表，通过链表串联起离散到相同下标的节点。在最坏的状况下，会退化为单链表，性能损失严重，哈希攻击便是采用这种形式。 开放地址就是开放哈希表中的所有地址，不使用额外的空间。如果遇到冲突，寻找其他位置存储。 开放地址法线性探测如果哈希到索引为 x 处，如果此处有元素，则查看 x + 1 处，如果没有则放在这里，如果有，则以此类推查看 x + 2，x + 3, … 二次探查这是线性探测的改进，每次的步长变为平方倍数。 Double hashing另一种改进的开放寻址法称为重哈希(Double hashing)或者叫二度哈希（Rehashing） 而在 LevelD ...

背景Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组表示一个集合，并能判断一个元素是否属于这个集合。 Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。 leveldb 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中，若过滤器表示不存在，则该 key 一定不存在，由此加快了查找的效率。 优劣相对于其他表示数据集的数据结构，如平衡二叉搜索树、Trie 树、哈希表，甚至更简单的数组或者链表。大都需要对数据项本身存储。但是 Bloom Filter 并不存储数据项本身，而是用高效紧凑的位数组来存。 如此设计，使得 Bloom Filter 的大小与数据项本身大小（如字符串的长短）无关。可以理解为在哈希表基础上，忽略了冲突处理，从而省下了额外开销。 对于 Bloom Filter ，其误判率应该和以下参数有关： 哈希函数的个数 k 底层位数组的长度 m 数据集大小 n 当 k = ln2 * (m/n) ...

背景LRU （Last Recent Used）是一个重要的缓存替换算法，常用于缓存场景,一般的实现是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。 内部实现LevelDB的LRUCache设计有4个数据结构，是依次递进的关系，分别是： LRUHandle HandleTable LRUCache ShardedLRUCache LRUHandle 是 LRUCache 中的数据节点，HandleTable 是 LRUCache 为了实现可扩展哈希性而自定义的哈希桶，LRUCache 便是核心类，内部维护了一条冷数据双向链表，一条热数据双向链表，以及 HandleTable来索引节点，此时LRU的缓存管理数据结构已经实现。而 ShardedLRUCache 是为了在多线程访问时提升效率，内部有16个LRUCache，查找key的时候，先计算属于哪一个LRUCache，然后在相应的LRUCache中上锁查找。 模块分析首先是 LevelDB 的导出接口 Cache 123456789101112131415161718192 ...

多重指针的理解简介其实这本不是一个很难理解的内容： 指针就是指向一个数据的地址 而所谓的多重指针就是指向指针的指针，反复的嵌套。 指针的值存储着对应类型的地址 背景在实现一个节点数据的移动代码时，仿佛对这个问题有了更新的理解 所有特此记录一下： 1234567891011121314 LRUNode **new_list = new LRUNode *[new_length]; memset(new_list, 0, sizeof(new_list[0]) * new_length); for (uint32_t i = 0; i < length_; i++) { LRUNode *h = list_[i]; // h 指向list连续地址中偏移i个单位的地址 while (h != nullptr) { LRUNode *next = h->next_hash; // next 获取h的下一个节点 uint32_t hash = h->hash; LRUNode **ptr = &new_list[h ...

gdb调试CMU15445-P3简介在小型的项目中，代码流程都很清楚，并没有涉及到复杂的函数调用与层层封装，然而在一个比较完整的项目中，层与层之间的高度封装，函数流的调用，让我们想理解某一块的代码实现增加了许多困难。 为此，使用 gdb 调试代码可以很好的显示中间过程以及调用流，以方便我们更好的理解某一块代码的实现。 本文并不涉及到 gdb 相关的基础语法 基础语法可以参考 GDB调试 准备工作由于在 CMU15445 的 P3 中需要实现几个执行器与优化算子，所以必须要理解此处的代码流程是什么。 当我们运行它所要求的 SQL 语句之后 报错是由于 SeqScanExecutor 没有实现 所以现在应该找到该类所对应的文件 那么该项目是如何执行到这个位置呢？传入参数的含义分别是什么呢？ 此时我们就可以通过 gdb 来定位执行流程 如上图， 在使用 gdb 启动项目之后，我们在需要定位的地方打上断点，之后就可以开始调试。 定位流程输入对应的语句 12CREATE TABLE t1(v1 INT, v2 VARCHAR(100));SELECT * FROM t1; 我们发现 ...

理解直接初始化与复制初始化的区别简介当用于类类型对象时，初始化的复制形式和直接形式有所不同： 直接初始化直接调用与实参匹配的构造函数。 复制初始化则是首先使用指定构造函数创建一个临时对象，然后用复制构造函数将那个临时对象复制到正在创建的对象。 很多时候编译器会默认给我们进行优化，省去创建临时对象这一步，以此来节省创建临时对象的损耗。 对比下面的源代码来自于c++拷贝初始化和直接初始化的底层区别 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <cstring>#include <iostream>using namespace std;class ClassTest { public: ClassTest() { c[0] = '\0'; cout << "ClassTest()" << endl;
...

智能指针简介有关内存的分配与释放。我们往往会遇到以下的问题。 由于疏忽忘记释放 new 出来的堆空间。 由于代码逻辑的原因，在 if 判断, try-catch 异常中直接退出函数块，导致并没有执行函数末尾的 delete 逻辑。 智能指针的解决方案 ：分配的动态内存都交由有生命周期的对象来处理，那么在对象过期时，让它的析构函数删除指向的内存。 c++11 提供了 unique_ptr、shared_ptr 和 weak_ptr 方便我们去管理内存。 auto_ptr在这里先说一下 c++98 提供的 auto_ptr ： 与 unique_ptr 类似，都是对资源的独占性。 但是在 C++11 后 auto_ptr 已经被“抛弃”，具体的原因有以下几点 ： 复制或者赋值都会改变资源的所有权 12345678910auto_ptr<string> p1(new string("Hello"));auto_ptr<string> p2(new string("World"));cout << &quo ...

c++ 中左右值与 std::move 的解析简介在 c++ 中,对于拷贝我们经常会遇到以下的问题： 十分影响性能的场景： 程序中存在大量的无用拷贝。 创建许多临时值，先将临时值进行拷贝，之后再将临时值释放。 存在一些对象不能拷贝 ： unique_ptr 所以如果存在一种移动逻辑，将一个对象的所有权移动到另一个管理对象，这样就可以避免许多无用的拷贝以及无法拷贝，从而提升性能。 左/右值对移动的探讨，首先需要理解两个概念：左值、右值。 从代码逻辑上判断：左值就是 = 左边的值，即可以取地址，右值就是 = 右边的值，无法取地址。 12int a = 5; // a是左值,5是右值B b = B(); // b是左值,B()是右值 左/右值引用从名字上看左右值引用无非就是对应类型变量的别名，c++引入引用这种语法，本身是想降低对指针的使用难度，因为引用本身是通过指针来实现的，都是为了避免拷贝，直接访问对象。 左值引用左值引用就是对左值的引用，给左值取别名。主要作用是避免对象拷贝。 123int a = 5;int &ref_a = a; // 左 ...

std::tuple简介std::tuple 是类似 pair 的模板。相对于 pair 只含有两个成员，每一个 tuple 实例都可以有不同的成员数目。 tuple 的创建与初始化12std::tuple<T1, T2, TN> t1; //创建一个空的tuple对象（使用默认构造），它对应的元素分别是T1和T2...Tn类型。std::tuple<T1, T2, TN> t2(v1, v2, ... TN); //创建一个tuple对象，它的两个元素分别是T1和T2 ...Tn类型。 这些方式属于直接构造 tuple 对象。同时也可以通过下面的方式创建 tuple 对象。 12345678910auto t3 = std::tie(T1, T2, T3); //返回左值引用的元组auto t4 = std::make_tuple(T1,T2,T3); //创建一个拷贝对象std::get<2>(t3); // 假定 T3 初始为 1T3++;std::get<2>(t3); // T3 变为 2std::get<2> ...