log-structured-database

4th September 2020 at 4:38pm
Diagram

Log Structure Unordered 数据库文件中纪录无序 Ordered 数据库文件中纪录有序 Ordered 数据库文件中纪录有序 Index In-Memory Hash Map 纪录 每个 key 对应其在数据库 文件中的纪录的位置 <= 同左 Log-Structured Merge-Tree
 使用平衡树或者红黑树实现的, 查询快,索引 key 有序 Query 通过索引找到数据所在文件位置 <= 同左
 假如索引 miss,因为数据有 序, 从数据文件中查找更快了 可以二分查找,不用遍历。 <= 同左
 由于索引中的 key 有序,且数 据库文件中纪录有序,因此 不需 要把全部 key 落索引中 Write 更新索引、
 追加写最后一个文件分片 <= 同左
 虽然数据库文件中纪录有序,但 是不需要保证它一直是有序的。 在数据写入时去实时重新排序数 据文件中的纪录会很耗 I/O。 序写一个新纪录的文件,再定期 做压缩合并是更合理的做法。 更新索引、
 写 WAL 防 crash Compaction 追加写导致一个 key 可能出现在 多个文件分片。需要做压缩。背 景线程对现有数据进行压缩合 并,合并完后使用新的分片文件 及索引,旧文件和索引丢弃。 除了未压缩过的文件,其他文件 都是有序的,因此压缩合并时可 以使用类似合并排序的做法。 能更高、内存消耗更少。 压缩合并时, 新增的数据不再存 在文件中,而是直接在索引中 取。 而且索引中已经排好序,这 会使合并性能更好。 Pros and Cons + 实现简单 - Hash map 不适合存磁盘。如 果 key 太多,内存可能不够用 - 无法做范围查询 对比左边方案:
 + 压缩性能更好
 + 可以做范围查询
 - Hash map key 过多时内存可 能不够用 对比左边方案:
 + 压缩性能更好
 + 不需要全量数据进索引