Bitcask通过日志结构化的设计,实现了一个简单、高效的键值存储系统,可以达到低延迟、高吞吐量、崩溃安全、易备份等设计目标。

实现

花了几个小时写了一个最小的能跑的版本，没想到 bitcask 这么简单。可以直接参考论文 Bitcask A Log-Structured Hash Table for Fast Key/Value Data ，读完论文后就能写了。首先研究数据在磁盘上是如何组织的，然后研究如何写入，写入后如何查询，启动时如何恢复旧数据，按照这个顺序就能够实现啦。

数据要分为两类，一类是在内存中，一类是在磁盘中。磁盘中的数据数据分为头部和数据部分两类，其中头部为时间戳，key 长度，value 长度，共 12 字节，然后数据部分就是 key 和 value 。论文中还有 crc ，此处先忽略，算在头部也很简单。key 和 value 写入时会先计算长度，生成头部字段的元信息，随后加上数据部分，这样一条数据就构造完成了。

内存中的数据可以用哈希表来存，后续可以改造成 B+ 树或其他结构。其中数据的 key 作为哈希表的 key ，而 value 可以设置为时间戳，文件偏移值，文件总长度三个属性。这样读取数据的时候根据 key 可以直接获取数据在文件中的 offset ，进而获取数据。

写入数据是计算当前数据的长度，然后累加到 offset 上，然后建立映射。因为一个文件写不下，所以在内存中还要加上一层文件的识别。几根据 key 获取元数据，从元数据中获取文件名和偏移值，二者组合直接访问对应的数据，再根据 value size 获取对应长度的数据。

程序启动时会先读取文件中的所有数据从而建立哈希表，可以理解为建立索引的过程，有了索引以后才能查询。

如何实现删除？

删除采用的时逻辑删除，可以简单粗暴的在内存中把 key 对应的 value 抹掉，这样无法从磁盘中查数据了。但是磁盘中依旧有需要被删除的数据该怎么办？接下来是合并操作，通常称为 compaction ，在 LSM Tree 中也有这个东西。首先从头开始读取磁盘文件，根据拿到的数据去哈希表中查找，判断是否被逻辑删除，若被删了则跳过，若没有则创建一张新的哈希表建立新的索引，并把数据写入新的文件中。这样把所有的旧数据都遍历一遍，该删的数据就都删干净了。

优劣

文件以追加的方式写入磁盘中所以写入速度非常快，所有键都在内存中所以读取速度也很快。缺点也很明显，键越多占用内存越多，需要定期合并来处理旧的，被删除的数据。

总的来说，Bitcask 是一个简单高效的键值存储解决方案，特别适合读取速度要求高和写入密集型的工作负载。然而，其内存使用和文件合并的特性可能会限制其在某些场景下的适用性。

优化

1. 添加 CRC 支持，从而确保数据的完整性。

在 encode 是使用对 data 部分生成 crc 校验码。然后 decode 读取 crc 并对 data 重新生成 crc 比较二者是否一致从而判断数据是否完整。还需要修改一些其他部分，因为数据的固定部分发生了改变 CRC 长度固定 4 字节。

2. 支持删除逻辑

删除分为两部分，即内存中和磁盘上。在内存中直接将 key 对应的 value 删除即可，现在直接调用的内置的 map 故可直接使用删除的函数。然后上磁盘上，如何删除磁盘上的数据？这也分为逻辑删除和 Compact 两部分，对于逻辑删除可以使用墓碑的方式，在删除内存数据之前找到位于磁盘上的数据，然后标记一下表示数据已经被删除了。对于 Compact ，需要后续启动时读取磁盘数据文件重新建立索引，若发现删除标记则跳过。什么时候 Compact 也有讲究，可以为文件设置写入上限，超过上限后触发 Compact 机制，也可以在后半夜执行，因为 Compact 重建索引的过程对系统资源消耗过大可能会影响正常业务的运行。

3. 添加范型支持

目前 go 已经支持范型了， 改造一下即可。

4. 参考 leveldb 的 log 模块重构 wal 。

leveldb 再次基础上引入了更多的概念，。首先是 record ，在 leveldb 中设计了个更多的结构。目前仅实现了 record ，内部的布局如下。其中 timestamp、keysize 、valuesize、crc 固定长度，均是 4B，而 key 和 value 是变长。

┌───────────┐
│ timestamp │
├───────────┤
│ key_size  │
├───────────┤
│ value_size│
├───────────┤
│ key       │
├───────────┤
│ value     │
├───────────┤
│ crc       │
└───────────┘

Log File:

+------------------------+
|       Block 1          |
+------------------------+
| Record 1               |
| Record 2               |
+------------------------+

+------------------------+
|       Block 2          |
+------------------------+
| Record 3               |
| Record 4               |
+------------------------+

+------------------------+
|       Block 3          |
+------------------------+
| Record 5               |
+------------------------+

其中：

• Block 1 包括 Record 1 和 Record 2。
• Block 2 包括 Record 3 的开始部分。
• Block 3 包括 Record 3 的剩余部分和 Record 5。

每个 Block 的大小是固定的，所以如果一个记录太大，无法完全适应当前块，它将被拆分，其余部分将存储在下一个块中。同样地，如果一个块的剩余空间足以容纳一个新的记录的一部分或全部，那么这个记录将存储在那个块中。

这种组织方式有几个优点：

• 容错性: 如果一个块损坏，只需丢弃那个块，而不会影响其它块。
• 可扩展性: 可以通过调整块大小来平衡存储效率和容错能力。
• 灵活性: 允许记录横跨多个块，因此不限制单个记录的大小。

这种设计使得 LevelDB 在处理大量小记录或少量大记录时都能保持高效和灵活。

5. 使用 B+ 树作为索引

参考 boltdb 的 B+ 树模块。

此前是用 go 写的，时隔一年，这次用现代 C++ 重写了一遍，并发还不完善 ：https://github.com/jieway/abysskv