返回 登录
0

网易视频云:优雅的Bitcask/BeansDB

阅读1118

网易视频云是网易倾力打造的一款基于云计算的分布式多媒体处理集群和专业音视频技术,为客户提供稳定流畅、低时延、高并发的视频直播、录制、存储、转码及点播等音视频的PASS服务。在线教育、远程医疗、娱乐秀场、在线金融等各行业及企业用户只需经过简单的开发即可打造在线音视频平台。现在,网易视频云与大家分享一下优雅的Bitcask/BeansDB.

概述
Bitcask是由Riak提出的海量小文件存储场景下的解决方案,着眼解决以下问题:
• 读写低延迟
• 随机写请求的磁盘高吞吐量
• 故障时的快速恢复且不丢数据
• 使用简单
Bitcask论文中主要定义了文件存储格式以及相关API,感兴趣可见参考资料。
BeansDB是Douban参考Bitcask论文开发的适用于Douban使用场景的小文件存储系统。作者Davies通过匠心独具的设计和深厚的技术水平将这一复杂的问题解决的比较优雅,值得仔细品味一番。
近期阅读了Bitcask论文和部分BeansDB源码,在此基础上分析BeansDB的设计和实现上的一些关键技术,包括数据文件组织、内存hash tree索引等,拿出来与大家交流探讨。

数据存储

总体架构
整体上看,一个BeansDB进程将其管理的存储空间(可以是一块磁盘或者磁盘上某个目录,代码中被抽象为hstore)组织成树状结构(树深度可配置)。每个hstore包含多级目录,而每个Bitcask实例管理一个最底层子目录,数据文件被存储在底层目录下,下面是测试环境中一个典型存储配置:
图片描述
其中有256个子目录(配置的树深度为2)可以存储实际文件数据,也即hstore包含了256个Bitcask实例。
文件格式
在每个Bitcask实例内部,BeansDB采取了Bitcask论文定义的文件存储格式,如下:
图片描述
bitcask文件存储特征如下:
• 每个目录下只有一个活跃文件(当前可写入),称为active data file,其他文件称为older data file,只读不写;
• 每个文件作为记录被追加写入active data file;
• 文件的删除也被作为一条record追加至active data file后面。

元数据存储
Bitcask设计初衷意在解决小文件存储的效率低下问题,而小文件存储效率低下的原因除了文件随机IO较多外,还容易由于数量的暴涨而导致元数据(dentry/inode)开销的增大,直接影响读写效率。
为了解决该问题,文件被以日志方式追加至大文件中,大大减少文件系统元数据开销。同时Bitcask管理自身文件索引:维护文件key至在磁盘文件位置及文件内偏移。BeansDB中定义的文件元数据格式为:
图片描述
为了效率考虑,Bitcask会将所有文件元数据缓存在内存中,这样在读文件时只需要一次IO即可。
为了能将如此众多的文件元数据全部缓存在内存中,我们必须得尽量压缩每个文件的元数据字节数,BeansDB在这方面可谓苦心孤诣,BeansDB文件元数据格式定义如下:
图片描述
这样单个Bitcask实例内便可以最多存储256个bucket。高24位便用来存储bucket内偏移。每个bucket大小一般定义为2GB,因此单个Bitcask实例最大支持的存储空间为512GB,妥妥的!
根据上面的定义我们大致可以计算出每个文件元数据占据的总存储空间size = 4B + 4B + 2B + 1B + size(key) = 11B + size(key),可以说已经很小了,按照20B/perfile计算,100MB个文件也只占用约2GB内存。

Hash tree
BeansDB使用了hash tree在内存中维护Bitcask的元数据。实现上使用了数组作为底层实现的16叉hash tree:
图片描述
而之所以使用hash tree的主要原因有二:
• 类似于普通的哈希字典, 保存 key 以及它在磁盘中的位置, 方面快速访问;
• 可快速比较两个存储节点中的内容是否一致, 将所有 key 按照其哈希组织成树, 同时节点的哈希是子节点的哈希的哈希, 这样可以快速比较并找出差异。
Hash tree除在内存中存储外,还会定期被dump至磁盘上,主要是为了加速系统启动速度。当一个active data file写满时,关闭该data file的同时会在后台将该data file对应的hash tree 写入磁盘,称之为hint file。

API
虽然Bitcask对外定义了一系列API,但我在这里并不打算一一枚举,只以有代码可参考的BeansDB为例大致描述其API的内部流程。
Put
1. 根据key定位该发往哪个存储目录(Bitcask instance);
2. 在Bitcask的hash tree中查找该key对应的Item是否存在,如果存在,说明是update,记录下原始版本号(oldv);
3. 根据原始版本号以及更新类型决定新版本号;
4. 为要写入的数据计算hash:uint16_t hash = gen_hash(value, vlen);
5. 如果步骤2得到的item不为null并且当前写入数据和已经存在数据是一样的,那其实什么也不用做,直接返回即可;
6. 分配新的DataRecord并初始化,以容纳要写入的新数据;
7. 将6的DataRecord写入Bitcask的缓存buffer,等待后续定期sync到日志文件(bucket);
8. 将元数据记录添加至bitcask的hash tree中并返回成功
说明:
• 在beansdb的实现中,每个Bitcask实例有两个hash tree,全局的hash tree和当前正在写入bucket的hash tree。这么做的原因是为了加快生成hint file的速度(相比之下,当前NEFS在生成hint file时必须从磁盘上读取一次日志文件头,代价较大)。可参考bc_rotate的代码。因此,在8的插入hash tree时候需要分别插入这两棵树。
• 上面的写过程都是在Bitcask的写锁保护之下完成的pthread_mutex_lock(&bc->write_lock)
会不会成为性能瓶颈?应该不至于,因为全是内存操作!
• 步骤7中可能写入Bitcask实例的内存缓冲区可能就返回了,潜在风险!
Get
1. 根据key定位该发往哪个存储目录(Bitcask instance);
2. 在Bitcask的hash tree中查找该key对应的记录是否存在,不存在则返回null
3. 判断item中记录的bucket id(pos & 0xff)是否是当前正在写入的bucket,如果是先判断要读取的数据是否在内存缓冲区;
4. 否则根据pos & 0xffffff00从相应的bucket中读出数据,并返回。
Delete
delete的流程与put一致,只是其version设置为-1。标记为删除,与正常的put区别在于:
1. value值为“ ”;
2. 新的DataRecord的版本为-oldversion – 1,为负值;
说明
• delete的时候并没有将记录的元数据(Item)从hash tree中删除;而是有个后台线程会做定期压缩(将version<0的的元数据记录删掉)。这样设计的主要理由我想可能是避免在删除的时候对hash tree作调整吧。后台压缩可参考bc_optimize。
一些关键问题
关于内存使用
这个我们在前面大致估算过,2GB的内存可大约存储100M个文件,与BeansDB作者的设计目标差不多,比Bitcask内存利用效率高。
关于异常恢复
为解决BeansDB设计在进程异常退出时每个Bitcak实例都需要从磁盘恢复内存文件映射表(key->元数据)而不得不读取大量数据的问题。Bitcask会为每个大文件(bucket)生成一个hint file,其实是该bucket内所有文件元数据的一份磁盘dump。
前面我们看到在写入Bitcask实例时除了写入Bitcask全局的hash tree外还写入了一棵current hash tree,这便是当前活跃bucket的元数据树,在bucket写满关闭时在后台由内存dump至磁盘中。想法非常自然,实现非常优雅。
即便如此,由于每个Bitcask实例中hint file可能也比较多(假如按照每个bitcask管理256GB磁盘空间,而每个文件平均大小为128KB计算,每个bitcask总的文件数量约为2M,而每个文件元数据量约为20B,则每个bitcask实例的元数据总量约为40MB,即每个bitcask的元数据恢复时间也比较快,去决定于元数据读取IO速度),即使有多个bitcask实例,我们也可以采取并行恢复(每个Bitcask实例并行地读出元数据,构建hash tree)的策略来提升恢复效率。
关于数据可靠性以及由此引出的一致性讨论
本篇主要讨论Beasdb如何优雅实现了Bitcask定义的存储格式。我们并没有讨论文件数据的可靠性以及采用多副本策略保证可靠性时的一致性问题。作者代码中也没相关内容。
大概猜测:
• 首先上层设置proxy,将写请求转发至多副本,多副本全部写入才算成功;
• 如果发生写异常,直接通过同步hash tree来做数据同步即可,可参考前面说的hash tree特性来理解。
beansDB存储应用
根据作者的博客透露,beansDB目前在douban主要有两套存储集群:一套存储诸如图片、日记等极小文件,而另外一套存储诸如音乐、视频等较大文件,我倒是很好奇对于一些超大文件(如超过最大bucket的限制),beansDB如何处理?
可能丢数据
由于beansDB在写入时只是写缓冲区即返回,因此,客户端即使得到写成功的结果也不一定保险。据社区有人反映,确实丢数据了。
数据merge
由于Beansdb的删除仅是逻辑删除,其实际物理数据依然存在,因此,需要后台任务定期对垃圾数据较多的bucket作空间回收:merge。
BeansDB中的merge也比较简单:顺序遍历每个bucket,扫描其hash tree的每个记录,查找其在全局hash tree中是否依然有效,如果无效,该记录空间即可被回收。
merge 的时候, 对当前merge的bucket会生产一个小的hash tree, 对应新生产的数据文件。一个数据文件 merge 完成后, 会锁住写, 并这个小的hash tree的内容更新到主体 hash tree 中, 这个过程是MlgN 复杂度的内存操作, N是一个bucket 的记录数, M 是当前数据文件的记录数, M一般在1M以内, 更新应该能在 1s 左右的时间内完成。

评论