> 本文是《从零实现 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,这样一是可以满足多样需求,二是可以让用户无缝切换到我的存储项目中
> 注:以上是我个人能够想到的一些东西,但在实际场景中,可能问的问题会更多,大家如果有相关的经验,可以在这里留言分享!
有疑问加站长微信联系(非本文作者))
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)