硬核项目手写 KV 存储—轻松拿捏面试官！

> 本文是《从零实现 KV 存储》课程的面试要点总结，相当于只要你学习了课程，以下提到的内容都是你自己完成的。对课程感兴趣的同学可以进这个链接查看详情：[https://w02agegxg3.feishu.cn/docx/Ktp3dBGl9oHdbOxbjUWcGdSnn3g](https://link.zhihu.com/?target=https%3A//w02agegxg3.feishu.cn/docx/Ktp3dBGl9oHdbOxbjUWcGdSnn3g) ## **在简历上如何写这个项目？** **项目概述** 基于 Bitcask 模型，兼容 Redis 数据结构和协议的高性能 KV 存储引擎 **设计细节** - 采用 Key/Value 的数据模型，实现数据存储和检索的快速、稳定、高效 - 存储模型：采用 Bitcask 存储模型，具备高吞吐量和低读写放大的特征 - 持久化：实现了数据的持久化，确保数据的可靠性和可恢复性 - 索引：多种内存索引结构，高效、快速数据访问 - 并发控制：使用锁机制，确保数据的一致性和并发访问的正确性 - 编程语言：采用 Go/Rust（根据实际情况写 Go 或者 Rust） 编写，兼顾高性能以及编码简洁性 **结果** - 性能方面：相较于其他同类型的存储引擎，读写性能稳定快速，相较于 redis，能够基本在一个数量级，但是节省了大量的内存空间 - 例如 leveldb、bolt、badger、sled 等等，做个简单的对比 - 可靠性：依赖数据文件的持久化特性，确保了数据的可靠存储和恢复，降低数据丢失的风险 - 简洁直观的用户 API，支持内嵌式的基础 Put/Get/Delete 等接口，也可以通过 HTTP 接口进行数据访问，也可以通过 redis client 进行直接访问 ## **可能的面试问题&回答** ### **你做的这个项目能简单介绍一下吗** 我开发的项目是一个基于 Bitcask 存储模型的 KV 数据库。bitcask 是一种高性能的持久化存储引擎，其基本原理是采用了预写日志的数据存储方式，每一条数据在写入时首先会追加写入到数据文件中，然后更新内存索引，内存索引存储了 Key 和 Value 在磁盘上的位置，读取数据时，会先从内存中根据 key 找到对应 Value 的位置，然后再从磁盘中取出实际的 Value。 基于这种模型，其读写性能都非常高效快速，因为每次写入实际上都是一次顺序 IO 操作，然后更新内存，每次读取也是直接从内存中找到对应数据在磁盘上的位置。 ### **为什么会做这个项目** 这个问题的答案因人而异，可以根据自己的情况来回答，例如： > 对数据库存储系统实现的好奇心，看到了对应的 Bitcask 的论文，想要自己去实现 > 弥补 redis 的缺陷，因为 redis 是一种基于内存的数据库，在数据量较大的情况下，对内存的压力会非常大，而 Bitcask 可以规避这个缺点，显著降低内存使用量 > 参加数据库比赛，针对性的设计了一种存储引擎 > 现有的存储引擎例如基于 B+ 树，读性能稳定，但是写数据是随机 IO，性能较差，LSM Tree 写性能优秀，但是读性能不稳定，读放大、写放大、空间放大问题严重；而 Bitcask 存储模型的读写性能则非常的稳定快速。 ### **有哪些适用场景** **缓存系统** KV 数据库可用作缓存系统的后端存储，以提供快速的数据访问和响应能力。由于 Bitcask 存储模型具有高性能和低读写放大的特性，它适合存储频繁访问的热数据，提供快速的缓存读取操作。 **日志存储** KV 数据库可以作为日志存储系统使用，将日志数据持久化到磁盘上的日志文件中。Bitcask 存储模型的追加写入方式使得日志的写入操作非常高效，确保了日志的可靠存储和后续分析。 **Key 小 Value 大的 KV 数据存储** Bitcask 将 key 和对应的索引都维护在了内存当中，这样如果 key 较小的话，那么内存当中能够维护的数据量就更多，并且 Value 是在磁盘上存储的，因此可利用磁盘更大的空间来存储 Value。 ### **优缺点是什么** **优点** - **读写低延迟** 这是由于 Bitcask 存储模型文件的追加写入特性，充分利用顺序 IO 的优势。 - **高吞吐量，即使数据完全无序** 写入的数据不需要在磁盘上排序，Bitcask 的日志结构文件设计在写入过程中减少了磁盘磁头的移动。 - **能够处理大于内存的数据集，性能稳定** 数据访问涉及对内存中的索引数据结构进行直接查找，这使得即使数据集非常大，查找数据也非常高效。 - **一次磁盘 IO 可以获取任意键值对** 内存索引数据结构直接指向数据所在的磁盘位置，不需要多次磁盘寻址来读取一个值，有时甚至不需要寻址，这归功于操作系统的文件系统缓存以及 WAL 的 block 缓存。 - **性能快速稳定** 写入操作最多需要一次对当前打开文件的尾部的寻址，然后进行追加写入，写入后会更新内存。这个流程不会受到数据库数据量大小的影响，因此性能稳定。 - **备份简单** 在大多数系统中，备份可能非常复杂。Bitcask 通过其只追加写入一次的磁盘格式简化了此过程。任何按磁盘块顺序存档或复制文件的工具都将正确备份或复制 Bitcask 数据库。 - **批处理操作可以保证原子性、一致性和持久性** 支持批处理操作，这些操作是原子、一致和持久的。批处理中的新写入操作在提交之前被缓存在内存中。如果批处理成功提交，批处理中的所有写入操作将持久保存到磁盘。如果批处理失败，批处理中的所有写入操作将被丢弃。 即一个批处理操作中的所有写入操作要么全部成功，要么全部失败。 **缺点** - **所有的 key 必须在内存中维护** 始终将所有 key 保留在内存中，这意味着您的系统必须具有足够的内存来容纳所有的 key。 - **启动速度受数据量的影响** 数据库启动时，会加载所有的数据，并且会重放所有的操作，以此来构建内存索引，如果数据量较大，这个过程可能会非常漫长 ### **磁盘上产生了无效的数据，如何清理** 实现了 Bitcask 论文中提到的 Merge 方案，Merge 实际上就是对磁盘数据空间进行清理的操作，其基本执行流程是遍历所有的数据，并将有效的数据进行重写，然后使用新的文件替换旧的文件，以此达到回收空间的效果。 **追问：** - **Merge 的过程会阻塞读写操作吗** - 不会，Merge 实际上是在新的目录打开了新的 Bitcask 进程实例，这个实例和原目录上运行的实例互不冲突，Merge 的时候，只会读取原 Bitcask 实例的索引数据结构，判断数据是否有效，并不会对原来的实例产生任何影响，并且原实例的写入会写到新的文件中，不会参与到 Merge 过程中，所以对写入也没有影响。 - **Merge 过程万一很漫长，中途挂了怎么办** - 在具体实现中，会在 Merge 结束之后，在磁盘文件中写入一个 Merge 完成的标识，只有当有这个标识的时候，我们才认为一次 Merge 是完整的，否则 Merge 都是不完整的，直接删除掉 Merge 的数据目录即可。 ### **写操作是如何保证原子性的** 采用了预写日志的方式，和其他大多数系统一样，WAL 通常是保证事务原子性和持久性的关键，在 Bitcask 存储模型中，比较特殊的是 WAL 文件本身就是数据文件，所以天然可以保证原子性，我们在写入的时候加上了一个完成的标识，并且给每一批次的数据都附了一个全局递增的 id，只有全部提交完成了，这个批次的数据才算完成，否则都不会进行加载。 ### **和 LevelDB、BoltDB、Redis 的区别** LevelDB 是经典的 LSM Tree 存储模型，其基本架构大致分为了 WAL、memtable、SSTable，数据写入首先会到 wal 中保证持久化，然后更新到内存的 memtable 中，如果 memtable 满了，则 flush 到磁盘的 sstable 中。 读数据会从 memtable 查找，如果没找到，则从磁盘上的多级 sstable 中查找，读性能不稳定。 BoltDB 是 B+ 树存储模型，读性能稳定，但是写入是随机 IO，性能较差。 Redis 是一种纯内存的数据结构服务，也可以持久化到磁盘中，但其实际上是一种面向内存的 KV 存储，数据量受到内存容量的影响。 而 Bitcask 存储模型，写性能和 LSM 模型相当，读性能也很稳定，读写都是一次磁盘 IO 操作即完成，并且相较于 Redis，Value 是不会存储到内存中，节省了内存空间，并且性能能够和 Redis 维持在一个数量级。 ### **做了哪些改进** - **内存索引限制** - 前面说到，Bitcask 的一大缺点就是所有的 key 都必须在内存中维护，这样数据库中能存储的数据量就受到了内存容量的限制，而我的项目中，创造性的使用了持久化的 B+ 树来作为索引数据结构，这样就可以将索引存储到磁盘上，突破了内存容量的限制。但是这样带来的一个副作用便是读性能会下降，因为原来是直接从内存中就能到获取到 Value 的位置，但是使用 B+ 树存储索引的话，还需要从磁盘 B+ 树中获取索引，然后再到磁盘中获取 Value，相当于多了几次磁盘 IO 操作 - **内存索引锁粒度优化** - 在我的最初的项目中，内存索引是单个数据结构，并且为了保证并发安全，这个结构的读写都需要加锁，如果在大数据量下，所有的数据都会竞争这把锁，所以我将索引进行了分区，并通过哈希函数将 key 映射到不同的索引结构当中，大大减少了并发冲突 - **启动速度优化** - 为了避免在重启的时候全量加载所有的数据来构建内存索引，我的项目中实现了 Bitcask 论文中提到的 Hint 文件，Hint 文件实际上就是一个 key+索引的文件，它不存储 Value，相较于原始文件容量会小很多，这样重启加载的时候，直接加载这个 Hint 文件 - 追问 1：Hint 文件是在什么时候生成的呢 - Merge 的时候生成的，Merge 时实际上所有的数据都是有效的，这个时候只需要依次存储对应的 key 和索引数据 - 追问 2：Hint 文件的格式是什么 - 和数据文件是一样的，都采用了日志追加的方式 - **持久化策略优化** - 在最开始的设计中，默认的刷盘策略是交给了操作系统来调度，这样的好处是性能很好，但是存在丢失数据的风险，在实际环境中，我们可以再提供另一个选项，用户可以设置积累到多少个字节之后，再进行一次持久化。这相当于提供了一个折中的方案，相较于之前的要么每条都持久化，要么完全交给操作系统，这样能够让用户自己灵活配置。 - **数据文件布局优化** - 我还参考了 LevelDB 和 RocksDB 的 WAL 文件的格式，将数据文件的组织形式改为 block（32KB） 的方式，加速数据读写的效率。 - **兼容 HTTP 协议** - 单纯的 KV 接口大多只能在嵌入式的场景中使用，但无法作为远程调用服务使用，所以我在存储引擎的基础之上，加上了 HTTP 的访问接口，这样便可以将存储引擎作为 HTTP 服务使用 - **兼容 Redis 数据结构和协议** - 原生的 KV 接口能够满足的需求比较有限，而 Redis 支持了多种数据结构，比如 String、List、Hash、Set、ZSet，满足了多样化的需求。于是我在 KV 的接口之上，兼容了 Redis 的数据结构，并且兼容了 Redis 的通信协议 RESP，这样一是可以满足多样需求，二是可以让用户无缝切换到我的存储项目中 > 注：以上是我个人能够想到的一些东西，但在实际场景中，可能问的问题会更多，大家如果有相关的经验，可以在这里留言分享！