当前位置:  软件>C/C++软件

简单的KeyValue存储系统原型 HashDB

    来源:    发布时间:2015-01-28

    本文导语:  1、HashDB是什么?HashDB是一个简单的KeyValue存储系统原型,提供基本的二元组的数据存储与读取功能,亦即当前被广为推崇的NoSQL存储系统。最初想到设计这个小系统,完全是出于偶然。本人维护着一个轻量级的开源重复数据删...

1、HashDB是什么?
HashDB是一个简单的KeyValue存储系统原型,提供基本的二元组的数据存储与读取功能,亦即当前被广为推崇的NoSQL存储系统。最初想到设计这个小系统,完全是出于偶然。本人维护着一个轻量级的开源重复数据删除小工具deduputil,它基于块级对文件目录进行数据去重并进行打包,支持定长和变长数据分块算法,并支持数据块压缩。deduputil使用hash数据指纹来区分和识别重复数据块,数据块指纹采用hashtable进行存储和查找,并完全置于内存中。假设,数据块平均大小为4KB,数据块对象属性描述约需40字节,则存储8TB数据的指纹大约需要80GB内存,如此庞大的内存需求使得deduputil很难工作于普通的PC或服务器。因此决定对deduputil进行重构,支持在内存有限的环境下进行大数据量的去重和打包,思想是让指纹数据在内存与磁盘之间进行交换。最初想直接采用类似Tokyo Cabinet的NoSQL系统,后来发现这些系统远远比deduputil复杂,使用它们真是大材小用,而且使得deduputil对第三方软件产生了依赖。于是产生了设计一个简单的KeyValue存储系统的念头,经过几个晚上的奋战,HashDB原型系统完成并成功应用于deduputil上,代码量不到1000行,非常非常轻量级。HashDB以较小的内存消耗达到支持超大hashtable,数据持久化存储于文件中,并在内存与文件之间进行交换。HashDB主要采用了hashtable, bloom filter, set-assocaite cache, file layout, btree等数据结构与算法,初步性能测试结果表明HashDB的性能基本还算不错,已经比较接近Tokyo Cabinet的性能。HashDB源码包含在deduputil中,可以从http://sourceforge.net/projects/deduputil/获得。 

2、基本原理

HashDB采用哈稀表数据结构组织数据,以文件形式对数据进行持久化存储,文件数据布局如下图所示,由header, bloom filter, bucket array, hash entries四个部分组成。Header记录HashDB的一些全局信息,比如总的记录数、hash桶数、缓存记录数以及它们在文件中的偏移位置。Header持久化存储在HashDB文件头部,加载时需要首先读取它,然后据此加载其他组成部分数据。Bloom filter是一个空间效率很高的数据结构,它由一个位数组和一组hash映射函数组成。Bloom filter可以用于检索一个元素是否在一个集合中,它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。这里主要利用bloom filter来快速判断给定Key是否存在于HashDB中,如果不存在则直接返回,存在则再进行文件I/O读写和Key精确查找,从而节省大量的I/O和检索开销。bloom filter长度由最大支持记录数决定,在创建HashDB时指定并保存在header中,一旦创建不可修改,下次启动时从header中读取并加载。

简单的KeyValue存储系统原型 HashDB[图片]


HashDB以hashtable方式组织数据,桶数组长度在创建时指定,同样以后不可修改。bucket array会远远小于记录总数,一般平均桶长在10以上。通常情况下,桶中以链表方式组织产生冲突的记录,查找时遍历链表,当桶较长时顺序查找效率较低。HashDB桶中的记录采用btree结合二次hash方法来组织,这点参考了Tokyo Cabinet。Btree实现简单,查找时间复杂度为log(h),但可能会发生二叉树极度为平衡的情况,而平衡树(如RB, B*, B-, B+树)实现则较为复杂。二次hash方法,先比较hash值再比较关键字key,从而获得较为平衡的btree。实践表明,btree结合二次hash的方法非常有效,可以大大提高检索效率。Bucket array中记录中对应桶的btree根结点偏移,以它为Root可以遍历搜索整个hash桶。

Hash entries区域部分存储了所有的KeyValue记录,出于简化设计实现考虑,每个记录的大小固定,Key和Value都有最大长度限制,记录以Append方式增加,支持修改Key对应的Value值,目前没有支持删除操作。同一个桶中的记录以btree方式组织,入口地址保存在bucket array中对应桶节点中。HashDB设计了Cache系统来提升性能,缓存的记录数量通常约为总记录数的10%,这也是采纳了热点数据的常见比率。Cache管理算法采用类似计算机高速Cache的组相联(Set-associative)算法,以hash为基础进行记录的换入和换出,即同一个桶中的记录会被cache到相同的cache项中。

HashDB中,header, bloom filter, bucket array, hash entries四个部分持久化存储于文件中,运行时header, bloom filter, bucket array完全缓存在内存中,cache则仅在运行时存在,这部分内存空间消耗是可以估算的。假设,总记录数tnum=1000万,hash桶数bnum=100万,缓存记录数量cnum=100万,每条记录固定大小为1KB,则内存消耗=1000万/8 + 100万*8 + 100万*1KB = 1.25MB + 8MB + 1GB。HashDB加载时,header, bloom filter, bucket array将从文件中读取并载入内存,并读取每个hash桶的第一个记录对cache进行预热。HashDB关闭时,内存中的所有脏数据将被写回文件,记录数庞大时,这个过程会比较耗时。

HashDB目前还是一个很简单的原型系统,没有提供锁机制,只能应用于单进程/线程模式。HashDB也没有提供常驻系统服务(Daemon),仅提供如下几个API进行访问。详细信息请参考hashdb.h & hashdb.c,简单描述如下:
HASHDB *hashdb_new(uint64_t tnum, uint32_t bnum, uint32_t cnum, hashfunc_t hash_func1, hashfunc_t hash_func2);
创建一个新的HashDB对象,参数分别为总记录数、hash桶数、缓存记录数、两个hash函数。

int hashdb_open(HASHDB *db, const char *path);
使用HashDB对象打开文件,路径由path指定。如果HashDB文件已经存在,则将header, bloom filter, bucket array载入内存,然后预读记录进行cache预热;如果是新建HashDB,则根据hashdb_new输入参数计算header结构各项参数值,然后在文件中为header, bloom filter, bucket array预分配空间。 

int hashdb_close(HASHDB *db, int flash);
关闭HashDB,将缓存数据中的所有脏数据与加文件,并释放内存空间。

int hashdb_set(HASHDB *db, char *key, void *value, int vsize);
设置(写入或更新)KeyValue记录,参数分别为关键字、值以及value长度。pos = hash_func1(key) % cnum,计算出key对应的cache位置,如果该位置已经缓存记录但不是当前记录,则将该记录换出内存(缓存状态设置为未缓存);如果没有缓存并bloom filter判断记录存在,则查找记录并换入内存。然后,设置缓存记录结构各项数据,对于新记录需要设置bloom filter位状态和缓存状态。

int hashdb_get(HASHDB *db, char *key, void *value, int *vsize);
读取KeyValue记录,参数分别为关键字、值缓冲区和值长度。pos = hash_func1(key) % cnum,计算出key对应的cache位置,如果bloom filter判断该记录不存在,则直接返回。如果该位置缓存记录但不是当前记录,则将该记录换出内存;如果没有缓存,则查找记录并换入内存,然后复制key对应的记录值和值长度。


    
 
 

您可能感兴趣的文章:

 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • java命名空间javax.xml.crypto.dsig.keyinfo接口keyvalue的类成员方法: rsa_type定义及介绍
  • mysql实现本地keyvalue数据库缓存示例
  • java命名空间javax.xml.crypto.dsig.keyinfo接口keyvalue的类成员方法: dsa_type定义及介绍


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    php开源软件 iis7站长之家