SSTable(Sorted-String Table) 是排序字符串表的简称，也就是说 SSTable 内部的数据都是有序排列的。当 MemTable 中的数据大小超过某个阈值之后，会通过 Minor Compaction 写入到 SSTable 中。除了 Minor Compaction 会写入 SSTable，在 Major Compaction 的时候也会将多个 SSTable 文件合并生成新的 SSTable。这篇文章只关注 SSTable 的格式，所以不会展示 Compaction 的细节。 SSTable 文件格式 根据 LevelDB 的文档，可以知道 SSTable 的格式如下所示： 123456789101112<beginning_of_file>[data block 1][data block 2]...[data block N][meta block 1]...[meta block K][metaindex block][index block][Footer] (fixed size; starts at file_size ...

顺着 log 的使用，其实可以找到 LSM-Tree 的主线：根据写 WAL 可以找到 MemTable 的写流程，根据写 MANIFEST 可以顺出 Compaction 的流程。这篇文章主要关注 MemTable。 Arean Arean 是 LevelDB 自己实现的内容管理，其主要是与 SkipList 绑定（实际上也是唯一的用途），而 SkipList 又是与 MemTable 进行绑定的。MemTable 内部是使用引用计数法来管理的，每当使用 MemTable 时引用会加一，结束使用时，引用会减一。当 MemTable 变为 Immutable MemTable 写入 SSTable 时引用会减为 0，这时就会销毁 MemTable，同时也会销毁内部的 SkipList 和 Arean classDiagram class Arena{ - char* alloc_ptr_ - size_t alloc_bytes_remaining_ - vector~char*~ blocks_ - atomic~size_t~ memory_u ...

log 在 LevelDB 中发挥着重要的作用，它主要有两个使用场景 wal，在写 key/value 之前，先向 wal 中写入，用于 crash 后恢复内存数据 manifest，记录 lsm 的一些元信息，包括层级信息等，用于重启后恢复 db 的一些重要信息 LevelDB 将对 Log 的读写操作分别封装为了 Writer, Reader 两个类，分别在 log_writer.cc 和 log_reader.cc 中。这两个类并不知道数据长什么样子(可能是单 key 写入，也可能是 WriteBatch批量写入，也可能存储的 VersionEdit)，只是单纯地将数据当做字节数组来处理。对于上层调用者来说，他们不需要知道数据底层是怎么存储的(比如一条数据可能跨 block 读取)，只需要调用 log 的方法每次写入或者读取一条数据即可。 Log 结构 log 是由一个一个 block 组成的，根据一次写入的数据在 block 的位置，可以将数据分为三种类型： 数据完整地放在一个 block 中，可以标记为 kFullType 数据跨越多个 block。为了完整地读取出一条 ...

编码 LevelDB 提供了两种编码方式：定长编码和变长编码 定长编码，编码时，将数据以字节为单位放入字符数组中。解码时，每次读取一个字节的数据，放入字符数组中 varint 变长编码，不显示地存储数据地长度，它在每个字节的 8 bit 中留出 1 位用来表示数据是否结束。 如果该位为 1，表示数据还没有读取完，需要继续读取； 如果为 0，表示这是数据的最后一个字节。比如数据 1234 的存储格式为 0000 0100 1101 0010 varint 变长编码的实现如下： 123456789101112131415161718192021222324252627282930313233343536373839404142434445char* EncodeVarint32(char* dst, uint32_t v) { // Operate on characters as unsigneds uint8_t* ptr = reinterpret_cast<uint8_t*>(dst); static const int B = 128; // ...

tmux 是一款优秀的终端复用软用工具，可以实现分屏、会话共享等功能 会话(session): 建立一个 tmux 工作区会话，回话可以长期主流，重新链接服务器不会丢失 窗口(window): 窗格(pane): 工作的最小单位 一个 tmux session 可以包含多个 Windows，一个 window 可以包含多个 pane Session 操作 tmux new -s name: Start a new named session tmux attach: Attach to the most recently used session tmux a(ttach-session) -t name: 进入到名称为 name 的会话 tmux detach/Ctrl-b d: 断开当前回话，会话在后台运行 tmux kill -session -t name: 关闭会话 tmux ls/Ctrl-b s: 查看所有会话 快捷指令 tmux 的所有指令都有一个前缀，默认 Ctrl-b 系统指令 Ctrl-b ?: 显示帮助文档 Ctrl-b d: Detach fro ...

vim cheatsheet https://vim.rtorr.com/ Mode vim 有四种模式 normal，普通模式，按下 esc， ctrl + [ 可以进入 normal mode insert，插入模式 i, a, o, insert, append, open a line below command-line，使用 : 可以进入 command-line mode，可以进行很多操作 visual，块状选择，v 以字符为单位选择，V 选中行，ctrl + v 选择每一行相同位置的连续字符 插入模式下的 Move Arount j, k, h, l gj, gk(折行文本) 单词操作 w/W 移动到下个单词开头/单词含标点 e/E 移动到下个单词结尾/单词含标点 b/B 移动到上个单词开头/单词含标点 ge/gE 移动到上个单词结尾/单词含标点 dw/W 删除一个单词/单词含标 点，可搭配数字使用 dt{char} delete until d$/0 删除到行尾/首 r, c, s, replace, change（c(a)w 删除一 ...

声明：以下内容都是我 xjb 写的，不保证其正确性 引言 不知道是谁说的，程序就是状态机。所谓状态机，就是一种数学计算模型。对于给定的输入，状态机会从一种状态变为另一种状态。同时，在任意时刻，状态机只能处于有限状态中的一种。 下面我们将从状态机的视角重新解释事务的 ACID。 以下内容纯属我 xjb 乱想的，不要太当真 ACID ACID 是事务的四种特性，其解释如下： Atomicity 原子性：一组操作要么全部完成，要么全部失败。不存在部分成功部分失败的情况 Consistency 一致性：如果事务开始前，DB 的状态是一致的，那么事务结束后，DB 同样是一致的 Isolation 隔离性：不同事物之间应该相互隔离，不应该互相影响 Durability 持久性：事务对数据做出的修改因该能够持久化都非易失性存储设备上 原子性 首先我们从状态机的视角理解原子性，其状态变化图大概如下图所示 在上图中，数据库处于状态 S，当事务 T1 使用 Begin 表示开启一个事务时，数据库从状态 S 转变为状态 A1，在事务中，没执行一个命令，都会让数据库的状态发生改变，假设其状态改变 ...

引言 不论是网络传输，还是将数据写入到存储设备中，都需要将内存中的数据进行序列化，并且需要在使用时将其反序列化为原来的数据。因此，如何设计序列化方法让我们能够编码和解码数据就是我们要思考的问题。 如果数据涉及安全问题，我们可以使用各种加密算法对数据进行加密，但是如果数据没有加密的必要性，我们并不需要花费额外的开销在加密和解密上。 不管是什么类型的数据，读取的时候都是以字节流的形式读取的，所以我们并不能区分数据的界限。所以自定义编码格式是很有必要的。如果我们知道了数据的开头，该如何找到数据的结尾呢？最简单的方式是存储数据的长度，根据数据的长度，我们就可以找到数据的结尾。 这个想法很好，但是问题来了，我们怎么知道 length 需要花费多少字节存储呢？一个简单的想法是使用固定长度来存储，比如一个字节能够表示 255 字节的数据，对于比较小的数据来说已经足够了。但是如果有的数据非常大怎么办呢？使用 int 32 位来表示长度，这样我们就能存储 4G 的数据了。一般来说这是足够的，但是如果我们存储的数据可能更多地是小数据，这就会造成浪费。 那么有没有一种方法让我们既能够安全地存取数据，又能够 ...

引言 LevelDB 是个基于 LSM 结构的 KV 数据库，其写入涉及到 Memtable、SSTable、Log 等多个组件。本文将会简要介绍一下 LevelDB 写入一个 Key/Value 的流程。 WriteBatch 无论是 PUT 操作还是 DEL 操作，底层都会调用方法向 WriteBatch 中写入，WriteBatch 可以批量向数据库中写入数据。 1234567TEST(WriteBatchTest, Multiple) { WriteBatch batch; batch.Put(Slice("foo"), Slice("bar")); batch.Delete(Slice("box")); batch.Put(Slice("baz"), Slice("boo")); WriteBatchInternal::SetSequence(&batch, 100);} 随后批量写入数据库 123456789101112131415161 ...

概述 布隆过滤器（Bloom Filter）是 1970 年由布隆提出来的，它可以用于判断一个 key 是否在某一个集合中。 原理 Bloom Filter 实际上是一个 bitmap，每一位是一个二进制位，0 表示 key 不在集合中，1 表示 key 在集合中。当插入一个 key 时，通过 hash 函数计算出一个 hash 值，然后向 bitmap 中对应的位置 1。当查找一个 key 时，如果对应为为 0，则表示集合中没有该 key。但是当对应位位 1 时，我们并不能断定集合中存在该 key，因为 hash 冲突可能造成 Bloom Filter 假阳性。因此，如何选择 hash 函数就成为提高 Bloom Filter 性能的因素之一了。 最简单的想法是使用一个 Hash 函数会造成冲突过大，那么我们就使用多个 Hash 函数，将多个 bit 位置为 1。查找时我们需要判断多个 bit 位，只有当这些 bit 位全为 1 时，才到集合中去查找，否则就可能判断该 key 不存在于集合中了。 但是这样又会将一个问题放大：就是如果数组太小了，插入若干个 key 后可能将整个 bi ...