单机存储引擎的基础方法

发表于 更新于 分类于

这是一篇关于单机存储引擎基本思路的总结和分析。

看了 Facebook Haystack 的论文 [1] 后，对于其单机对象存储引擎的设计感觉十分简洁，进而对其他单机引擎的设计产生了一些兴趣。

看了 [2] 之后，对单机存储引擎有了一个非常粗略的了解。首先，需要处理的内容分为两类：数据及其索引。此时有两种方案：

  1. 数据和索引放到一起（聚簇索引，Clustered Index），例如 Berkeley DB，InnoDB，LevelDB

  2. 数据和索引分别存放，例如 MyISAM，Facebook Haystack

对于索引，只考虑精确索引，有以下分类：

  • 平坦结构

    • 哈希表，例如 Bitcask

  • 树结构

    • B 树族，例如 Berkeley DB，InnoDB，MyISAM

    • LSM 树，例如 LevelDB

    • 分形树，例如 PerconaFT

    • R 树，例如 PostGIS

    • T 树（纯内存结构)，例如 EXtremeDB

方案比较（个人看法）

数据和索引放在一起存储的方案，其优点在于：

  1. 索引到 Key 之后无需再进行一次 IO 操作即可直接取出 Value

  2. 索引和数据的一致性高

  3. 如果索引是有序的，则数据也是有序存放的，进行扫描时效率高

数据和索引不放在一起存储的方案，其优点在于：

  1. 数据和索引可以以不同的方式进行组织

  2. 索引的大小显著减少

如果索引能够全放入内存，则不应该使用聚簇索引。写请求较多的情况下，最好不要使用聚簇索引。需要支持扫描请求的话，并且数据存储于 HDD 的情况下，应该考虑聚簇索引。如果在意启动时间，应该使用聚簇索引。具体解释见 Update 1

对于索引方案，可以看到很少有使用哈希表做索引的存储引擎。个人认为这是因为哈希表必须全部装入内存，并且很难进行增量持久化。这对于传统数据库场景和文件系统场景都是不可接受的，因为占用了太多内存。B 树和 LSM 树比较受欢迎也是因为索引可以部分装入内存，这样热点索引载入内存，其他留在磁盘上，剩下的内存就可以做其他事情了，最差也可以做热点数据的缓存用。

LSM 树是近几年新兴的索引结构，其比较 B 树的优点是读写性能更高。这是得益于其分裂、合并的操作可以在后台进行。LSM 树的缺点是写放大，这在论文 [3] 中有所改进。LSM 的另一个问题是在写请求较多时，后台合并的速度不够快以至于很难完成分裂、合并等操作，以至于整体性能的持续下降。

几乎所有的存储引擎没有采用 Facebook Haystack 的方案，使用异步写入 Index File 的方式增量持久化内存索引信息。这是因为大部分存储引擎是为了小 Value 设计的。对于 Facebook Haystack 的场景，平均个 Value 大约有 80KB 左右的大小，一个 100GB 的数据库也只能存储约 1.3 million 个对象，其索引大小应不会超过 10MB。常见的数据库使用场景应该不是这样的，但是我没有统计数据。但是个人认为，对于纯 Key-Value Store 的场景（无需在节点上进行 join 之类的计算），可以接受比较大的索引大小，比如说 10GB 的索引。在这样的情况下，Facebook Haystack 的设计方案还是很有吸引力的，相当于一次同步的顺序写入操作即可完成写请求。如果比较在意索引占用内存的话，也可以使用 LSM 树进行索引，但是将索引和数据分离仍然能够受益，见论文 [4]。

Update 1

个人非常同意评论区 @CatKang 的看法：选择数据和索引分离还是在一起这个问题得考虑三个维度：索引特性，对象大小，请求特征。

由于已经有两位知友就我对于如何选择聚簇索引的看法提出一些问题，我希望把这一段讨论进一步展开一些，给出我提出这一建议的具体原因。

如果索引能够全放入内存，则不应该使用聚簇索引

使用聚簇索引很可能就不能将索引全部载入内存中，在这种情况下有点得不偿失。全内存索引性能高，索引结构上受到的限制极少。如有可能，应该尽量使用全内存索引。

写请求较多的情况下，最好不要使用聚簇索引

并非不要使用聚簇索引，而是建议考虑非聚簇索引。不使用聚簇索引，可以更自由的组织写入数据的存放方式，进而获得更高的写入性能，比如说像 Haystack 那样顺序写单文件，又比如说并行写 SSD 上不同 cell 的多个文件。使用聚簇索引可以避免使用非聚簇索引带来的一些问题，例如扫描性能可能下降，删除场景浪费空间，索引和数据的 Crash 一致性问题，等等。但是不可避免的，数据的写入受限于索引的组织方式。使用 B 树，随机写带来性能下降。使用 LSM 树进行索引，（个人看法）也不过是将随机写延迟到后台线程进行，随机写转化为顺序写的代价就是写放大，并且在持续高写入场景下，还会有 compact 和写入请求争用写入带宽的问题。

需要支持扫描请求的话，并且数据存储于 HDD 的情况下，应该考虑聚簇索引

扫描请求最好是数据有序排放，一次扫描正好访问一个连续空间，性能高。此时如果索引本身是有序的，再采用聚簇索引，对扫描请求的支持效率是最高的。

如果在意启动时间，应该使用聚簇索引

非聚簇索引的索引和数据有 Crash 一致性问题。在 Crash-Recover 的场景下，需要从数据恢复索引的最新状态，带来启动时间的增加。

References

  • [1] Beaver, D., Kumar, S., Li, H. C., Sobel, J., Vajgel, P., & Facebook, I. (2010). Finding a Needle in Haystack: Facebook’s Photo Storage. In Proc. USENIX Symp. Operating Systems Design and Implementations (OSDI’10) (pp. 1–14).

  • [2] Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems (1st ed.). O’Reilly Media, Inc.

  • [3] Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles - SOSP ’17, 497–514. DOI:https://doi.org/10.1145/3132747.3132765

  • [4] Thanumalayan Sankaranarayana Pillai Lanyue Lu and Remzi H. Arpaci-Dusseau Andrea C. Arpaci-Dusseau. 2016. WiscKey: Separating Keys from Values in SSD-Conscious Storage. Fast ’16 13, 1 (2016), 1–28. DOI:https://doi.org/10.1145/3033273