Bitcask论文阅读笔记

简介

Bitcask是Riak分布式数据库使用的日志型存储模型,主要有以下几点特性:

  • 读写低延迟
  • 高吞吐量,尤其是随机写
  • 能处理大量的数据集而不降低性能
  • 故障时快速恢复且不丢失数据
  • 易于备份和恢复
  • 易于理解的代码结构和数据格式

结构

硬盘结构

在给定的一段时间内,只有一个active data file能提供append(写入)功能,当该文件大小达到指定阈值时,则会创建一个新的active data file。每一个写入到file的entry结构如下:

Entry结构

包括以下内容:

  • crc:校验值
  • tstamp:记录写入该数据的时间
  • ksz:key_size
  • value_sz:value_size
  • key:key
  • value:value

内存结构

在写入之后,一个被称为keydir(hash table)的内存结构将被更新,每一个键映射到固定大小的结构中,包括了以下内容:

  • file_id:去哪个文件查询
  • value_size:读取value多长的字节
  • value_position:value在文件中的位置

每一次写操作发生,keydir都会进行原子性的更新。

操作

read

读取value的过程:

  1. 查找keydir中的key,并读取file_idpositionsize
  2. 通过file_id找到对应的data file,再通过positionsize字段找到entry中的value。

merge

由于删除操作并不会真正删除掉entry,只是将删除操作封装成entry写入文件,因此需要merge操作将所有的非active文件中entry遍历,并重组为一个新文件。同时生成一个hint file,用于存储data file的位置和大小。

Q:hint file的作用是什么?

A:每次进程重启时需要重建keydir,需要扫描所有的数据文件,因此使用hint file加速构建keydir的速度。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!