bitcask存储
Bitcask的存储介绍
对于大多数存储系统中，其中读的性能一般都会成为瓶颈，以数据库为例，关系型数据库的底层存储为了解决快速查找的问题，一般采用BTree等，这种支持顺序扫描，当然为了快速查找也可以使用hash的方式快速定为到对应的节点，但是hash不支持顺序扫描；在面对这些问题的时候，Bitcask的存储模型产生了，能将随机写入转化为顺序写入，这样有的好处是：提高随机写入的吞吐量和很好的利用类似ssd这种顺序存储的硬件，因此bitcask有一下特点：
(1)所有的key都存储于内存中，所有的value都存储于磁盘中；
(2)以追加的方式写入磁盘，即写操作是有序的，这样可以减少磁盘的寻道时间，是一种高吞吐量的写入方案，在更新数据是，也是把新数据追加道文件的后面，然后更新一下数据的文件指针即可；
(3)读取数据时，通过数据的指针以及偏移量即可，时间复杂度O(1)，因为所有的key都是存储于内存，查找数据时，直接访问内存索引，这样减少了随机读数据的时间，同时又能让内存不会爆增；
(4)bitcask有一个合并的时间窗口，当旧数据占到一定比列时，会触发合并的动作，即将多个data文件合并减少磁盘文件个数和搜索时间(由于更新写入可能存在多个value，但是只有最新的一条数据是有效的)；
Bitcask的存储结构
Bitcask的分为3中文件，包括数据文件，索引文件和hint file。数据文件存储原始的kv数据，索引文件存储各个数据的索引位置，在启动时加载到内存中，hint file为了提高构建索引文件的速度使用的文件，存储结构图如下：
说明：
1:加载到内存的文件；
2:存储在磁盘上的文件；
3:存储在磁盘文件上的格式；
4:hint的文件格式；
data文件的存储格式：
crc32(4byte)|timeStamp(4byte)|ksz(4byte)|valueSz(4byte)|key|value
在bitcask重启后，直接扫描data文件建立索引可能会非常耗时(当kv存储非常多的时候)，那么有hint file就可以加快访问的速度，其存储格式：
timeStamp(4byte)|ksz(4byte)|valuesz(4byte)|valuePos(8byte)|key
这样就可以直接跳过value的扫描，通过valuePos直接找到对应的文件内容。
具体代码实现：(python版本)
import os
import shutil
import cPickle as pickle
class Bitcask(Object):
def __init__(self, threshold = 10000, path = './'):
self.table_ = {}
self.threshold_ = threshold
self.path_ = path
self.curr_active_ = # 最新使用的文件
if os.path.exists(path) == False:
# 创建文件夹
def get(self, key):
record = self.__get_record(key)
if record != None:
return record[5] # 第六个值是value
return None
def put(self, key, value):
key_size = len(key)
value_size = 0 if value is None else len(value)
ts = datetime.now()
crc = crc32('{0}{1}{2}{3}{4}'.format(ts, key_size, value_size, key, size))
info = self.__io_write(crc, ts, key_size, value_size, key, value)
self.table_[key] = info
return True
def delete(self, key):
''' 删除数据，将对应的key添加为一条None '''
return self.put(key, None)
def update(self, key, value):
''' 更新数据，将对应的key添加为一条value '''
return self.put(key, value)
def load_data(self, path):
''' 加载目录下的数据 '''
if path is not None:
self.path_ = path
if os.path.exists(path) == False:
# 创建文件夹
for filename in #所有的文件
self.load_file(filename)
def load_file(self, filename):
f = open(filename)
data = f.read()
list_items = data.split("t.")
start = 0
length = 0
for item in list_items[:-1]:
s = item + "t."
record = pickle.load(s) # 加载文件
length = len(item) + 2
if self.table_.has_key(record[4]) is True:
ts1 = record[1] # 获取时间戳
ts2 = self.__get_record(record[4])[1]
if ts1 > ts2: # 对比时间戳
self.table_[record[4]] = (filename, start, length)
else:
self.table_[record[4]] = (filename, start, length)
start += length
f.close()
def __get_record(self, key):
''' 根据key读取完整的记录 '''
info = self.table_[key] # 先获取对应的记录信息
if not info:
return None;
pickled_data = self.__io_read(*info)
data = pickle.loads(pickled_data)
def __io_read(self, filename, start, length):
with open(filename, 'rb') as f:
f.seek(start)
return f.read(length)
def __io_write(self, crc, ts, key_size, value_size, key, value):
active_filename = '%s%s.sst'%(self.path_, self.curr_active_)
try:
if os.path.getsize(active_filename) >= self.threshold_:
self.curr_active_ += 1
active_filename = '%s%s.sst'%(self.path_, self.curr_active_)
except:
pass
# 保存数据到文件
with open(active_filename, 'a') as f:
data = pickle.dumps(crc, ts, key_size, value_size, key, value)
start = f.tell()
length = len(data)
f.write(data)
return active_filename, start, length
def merge(self, dst_path):
''' 合并多个文件，基本操作就是读取self.table_中所有的key，
然后将key的数据写入到对应的合并文件中，代码可以自行添加 '''
def load_file_with_hint(self, hint_filename):
''' 使用hint文件加快key的load，将ts,key_size,value_size,value_pos,key这些数据写入到
磁盘文件，然后通过load_file_with_hint加载出来，代码可以自行添加 '''
if __name__ == '__main__':
s = Bitcask()
# 加载数据，然后进行一系列操作
扩展：
(1)完整的基于bitcask的kv存储具体的可以参考豆瓣的BeansDB开源代码；
(2)leveldb也采用类似bitcask的存储方案，其中网上有对比性能(http://erlang.blog.51cto.com/2072079/1001968)；