基于Bitcask的KV Store
Bitcask
Bitcask 是一种高效的键值存储模型，最初由 Riak 数据库系统的开发团队 Basho Technologies 引入。它以其极高的读写性能和简洁的设计而著称，特别适合某些类型的工作负载，如读多写少、数据较小、需要高吞吐量的场景。
Bitcask 的基本原理
- 基于日志的写入：
- 所有的写操作都被追加（append）到一个日志文件中，而不会修改已经存在的数据。这种基于日志的写入机制保证了数据的持久性，并且由于是顺序写入，磁盘 I/O 操作非常高效。
- 键的内存索引：
- Bitcask 使用内存中的哈希表来保存每个键对应的数据的文件偏移量。每次读取操作都通过内存中的索引直接定位到存储在磁盘上的数据位置，然后读取数据。这使得读取操作非常快速。
- 只追加的文件：
- 数据只会追加到日志文件的末尾，旧的数据会保留在日志中。为了防止磁盘空间被这些旧数据占用，Bitcask 会定期进行压缩和合并（compaction），将活跃的数据重新写入新的日志文件中，释放无用的空间。
- 写入操作的高效性：
- 由于写入操作是顺序追加的，不涉及对现有数据的修改，Bitcask 的写入操作非常高效。这种模型特别适合 SSD 等顺序写入性能良好的存储设备。
- 数据恢复和启动速度：
- 当数据库启动时，Bitcask 会将磁盘上的数据文件逐一加载，并重建内存中的索引。由于索引只包含键和文件偏移量，这种恢复过程相对快速，特别是在数据量较大的情况下。
优点
- 高写入性能：由于数据是顺序追加的，写入操作非常快，并且对磁盘的磨损较小。
- 高读取性能：内存中的键索引使得读取操作能够快速定位数据，减少了磁盘 I/O 的开销。
- 崩溃恢复：基于日志的写入机制保证了在系统崩溃时不会丢失数据。
缺点
- 内存占用：由于 Bitcask 将所有的键索引保存在内存中，对于键数量非常大的数据集，内存使用可能成为瓶颈。
- 磁盘碎片：由于采用日志追加的方式，磁盘上的数据会随着时间的推移变得分散，因此需要定期进行压缩和合并操作。
使用场景
- 小规模键值对：特别适合处理大量的小键值对数据，如元数据存储。
- 读多写少：在读多写少的工作负载中，Bitcask 的性能表现尤其优异。
- 高吞吐量需求：需要快速写入和读取大量数据的场景，如缓存系统或日志存储。
实现
数据文件存储格式
当数据落盘时，每条数据会被存储为
crc 校验值：用于检测数据是否为修改
type 类型：数据的类型 (Normal/Deleted)
key/val 的大小 : 这里用变长存储 ，最大设置成 5bytes, 2^40 大小足够了
key/val 实际的数据
这里没有用到论文中的提到的timestamp：表示数据插入的时间
主要编码解码相关代码在data/log_record.go
KeyDirectory
主要是一个索引层，记录 key 和 datafile 中数据的映射(这里只需要记录 fileid, datafile 里对应的 record 大小，和 record 在 datafile 里的 offset)
record 在索引中的记录格式：
整体视图
DB 操作
Get
先根据 key 通过 KeyDirectory 索引获得到对应的在文件中的 record 相关信息
没找到的到直接返回，再通过 file_id 和 offset 读取 data，解析 data（会通过 CRC 判断数据是否被篡改），再通过 type 判断是否被删除，再获得对应的 value
Put
会向对应的 activefile 向入相应的 data，再更新索引。
Delete
删除也是一种 put，只不过 type 为 Deleted，通过 indexer 获得对应的 record，如果没有则直接返回，因为 indexer 中记录了所有 data，然后向 activefile 加入新 data,删除索引。
Merge & Compaction
Hint File
在 Bitcask 中，Hint File 是一种优化机制，用于加速数据库的启动和恢复过程。它是一个辅助文件，存储了 KeyDirectory 中的 value。构建 KeyDirectory 时先从 Hint File 加载，避免大量的扫描加载旧文件。
Hint File 非常适合在数据量大且重启频繁的场景中使用，它能够有效减少数据库的重启时间，提升系统的整体可用性。
这里暴露一个 Merge 方法，让用户去按需生成 Hint File merge.go
这里会创建一个新的 Database 在一个新的 merge 目录进行，将所有 data file 按最新到旧的顺序，即先处理最新的文件，来生成 Hint File。
这里 Merge 时打开一个新的 Database 主要是为了不影响原先的 database 后续操作，比如 Merge 时还会有其它操作同时进行。同时 Merge 时可能会被中断，这里存储个文件来标示 Merge 是否完成。
这里也会标示在 Merge 时未操作的 Data File ID，后续 Recory 时还需要加载后续的文件
Recory
DB 在打开时，需要构建 KeyDirectory，加载 Merge 原数据获得未 merge 的 Data File ID,是否完成，
如果完成了，则可以删除原 Database 中的 old data file，将 merge 目录中的 data file 移到数据目录下。
再从 non merge data file id 加载构建索引，也需要处理带有事务 ID 的 record。
Transaction
提供一个方法创建带有事务提交的 DB，执行 Commit 时，会让所有 data record 会带有当前事务 ID，存储到 Data file 中，完成后再写入一个标识 record(type 为 TxnFinished)，更新索引。
Res
https://riak.com/assets/bitcask-intro.pdf