bitcask简介

在软件系统中, 数据通常存储于内存或磁盘,

完全将数据存储于内存的系统, 比如redis,

面向磁盘的存储系统, 比如数据库mysql, 存储ceph等系统,

数据存储于内存的系统速度更快, 适合作为缓存,

面向磁盘的存储系统则可以存储比内存大得多的数据, 适合大容量存储,

面向磁盘的存储系统需要一个存储引擎管理存储于磁盘中的数据,

存储引擎的实现主要基于两种算法, B+树或lsm,

在数据结构及算法相关课程中我们可能了解过B+树,

知道树一类算法在检索上效率比较高,

基于B+树进行搜索, 在读取数据上速度更快,

适合读多写少的系统,

bitcask是一种类似lsm实现的算法

bitcask简化了lsm的实现逻辑, 简化了代码实现

bitcask相对于B+树一类算法也能做到更高地写入效率

那么bitcask是如何做到快速写入呢

内部数据结构

首先我们需要了解bitcask算法的整体架构,

内存中数据结构

内存中数据结构为keydir, 采用哈希表实现,

每个key指向日志文件id,

磁盘文件

磁盘文件由一个active file和多个older file组成,

active file为当前写入的活动中的日志文件,

older file为不再修改的日志文件

数据元组

数据元组是存储在磁盘日志中的基本单元,

如何能快速写入

bitcask的写入非常简单也很高效, 采用直接追加写入日志的方式,

其他基本操作:读取 删除操作

读取操作也很简单, bitcask先在内存中从keydir根据key得到value的file id和value位置,

然后再到对应的磁盘中文件位置读取value值

删除操作也非常快速, 先从内存中keydir删除对应key, 然后在日志中追加一个数据删除的标志,

如何解决日志数据冗余

bitcask无论是插入数据, 还是删除数据, 都是采用追加日志的方法,

这样虽然很高效, 但是问题是会在日志中有很多冗余数据,

这时就需要一个定期的日志压缩算法, 将冗余的日志数据合并

遍历全部的older file, 如果数据元组中的key在keydir存在, 并且其时间戳与keydir中相同,

说明是最新的数据, 写入merged data file, 同时将:时间戳 key长度 value长度 value位置 key写入一个hint file

额外的好处

使用日志记录操作数据的方式, 还有一种额外的好处,

就是当系统崩溃/重启后, 只需读取hint file即可重新构建出keydir,

将数据信息快速恢复出来.