那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程

这一节关注TC中的hash数据库如何根据一个key查找到该key所在的record,因为后续的删除,插入记录都是以查找为基础的,所以首先描述这部分内容.

从上一节的概述中,可以看到record结构体中有两个成员left,right:
typedef struct {                         // type of structure for a record
  uint64_t off;                          // offset of the record
  uint32_t rsiz;                         // size of the whole record
  uint8_t magic;                         // magic number
  uint8_t hash;                          // second hash value
  uint64_t left;                         // offset of the left child record
  uint64_t right;                        // offset of the right child record
  uint32_t ksiz;                         // size of the key
  uint32_t vsiz;                         // size of the value
  uint16_t psiz;                         // size of the padding
  const char *kbuf;                      // pointer to the key
  const char *vbuf;                      // pointer to the value
  uint64_t boff;                         // offset of the body
  char *bbuf;                            // buffer of the body
} TCHREC;
说明,每个record是存放在一个类二叉树的结构中的.

实际上,TC会首先根据一个record的key去算出该key所在的bucket index以及hash index,代码如下:
/* Get the bucket index of a record.
   `hdb' specifies the hash database object.
   `kbuf' specifies the pointer to the region of the key.
   `ksiz' specifies the size of the region of the key.
   `hp' specifies the pointer to the variable into which the second hash value is assigned.
   The return value is the bucket index. 
*/
static uint64_t tchdbbidx(TCHDB *hdb, const char *kbuf, int ksiz, uint8_t *hp){
  assert(hdb 
&& kbuf && ksiz >= 0 && hp);
  uint64_t idx 
= 19780211;
  uint32_t hash 
= 751;
  
const char *rp = kbuf + ksiz;
  
while(ksiz--){
    idx 
= idx * 37 + *(uint8_t *)kbuf++;
    hash 
= (hash * 31^ *(uint8_t *)--rp;
  }
  
*hp = hash;
  
return idx % hdb->bnum;
}
需要特别提醒的一点是,上面的算法中,根据key算出所在的bucket index,是经过模TCHDB->bnum之后的结果,也就是说,这个值是有限制的---最大不能超过TCHDB初始化时得到的bucket最大数量;而算出的二级hash值,我是没有看出来有数值上的限制的,为什么?看了后面的内容就明白了.

因此,所有根据记录的key算出bucket index相同的记录全都以二叉树的形式组织起来,而每个bucket array元素存放的整型值就是该bucket树根所在记录的offset.

到此,相关的结构体联系都清楚了,下面的流程图给出了查找一个key的记录是否存在的流程:


简单的解释一下,这个查找的流程就是首先根据查找的key算出所在的bucket,然后在这个bucket的二叉树中按照条件遍历的过程.

前面提到过,bucket array是整个被mmap映射到共享内存中去的.我们来做一个估计,假设存放bucket array的内存使用了1G,而真正存放record的文件长度有16G,也就是,bucket array的元素与记录大概是1:16的关系,假设所选的hash算法足够的好,以至于每个记录的key可以较为平均的分布在不同的bucket index上,也就是每个bucket array的元素组成的二叉树上平均有16个元素,那么也就最多需要O(4)次读取文件I/O(每次去读取记录的数据都是一次读磁盘操作) + O(1)次内存读操作(因为需要在bucket array中得到树根元素的offset).

但是等等,上面还有一些细节没有交待清楚.

首先,上面的二叉树不是类似AVL,红黑树这样的平衡二叉查找树,也就是说,很可能在极端的情况下演变成一个链表---树的一边没有元素,另一边有全部的元素.
其次,上面的流程图中还有一点就是每次比较首先比较的是hash值,这个值的奥秘就在于解决上面提到的那个问题.既然只是一个普通的二叉树,无法保证平衡,那么就通过算出这个二级的hash值来保证平衡---当然,前提依然是所选择的hash算法足够的好,可以保证key平均的分布.

前面提到过,非平衡的二叉树只会在极端的情况下才会演变为一个极端不平衡的二叉树--链表,而诸如AVL,红黑树之类的平衡二叉树,算法编码都相对复杂,调试起来也麻烦,出错了要跟进更麻烦,另外还别忘了,这些平衡二叉树之所以能保持平衡,在删除/增加元素时做的让树重新平衡的操作,比如旋转等,都是要涉及到读写树结点的,而这些,目前都是存放在磁盘上的---也就是这是相对较费时的操作,所以问题在于:是不是值得为这一个极端的情况去优化?另外,引入二级hash就是为了部分解决这个极端不平衡问题,它的思路简单也容易实现,但是引入的另外一个问题就是每次查找时根据key去算bucket index的时候,还要耗费时间去算hash index了.

平衡点,还是平衡点.时间还是空间,这是一个问题.

所以,经过对TC的hash数据库查找key流程的分析,最大的感受是:它没有使用复杂的算法与数据结构,而是通过一些巧妙的优化如二级hash的引入,达到了系统效率和编码调试复杂度之间一个较好的平衡.学会"平衡"各种因素,是做项目做事情,都要掌握的一个技能,而这个,只有多经历多想才能慢慢积累了.

好了,简单的回顾整个查找key的关键点:
1) 所有的record是以二叉树的形式组织在同一个bucket上面的.
2) 这个二叉树不是平衡的二叉树
3) 为了解决问题二造成的极端不平衡问题,TC引入了二级hash,以保证这个二叉树尽可能的平衡.

以上,就是TC对记录,bucket的组织情况,以及整个查找算法的流程.可以看到,算法,结构体定义等等都不复杂,但是由于巧妙的构思,既可以使用尽可能简单的算法/数据结构,又能规避可能出现的一些隐患,同时还能保证查找的高效率.

查找是key-value形式存储的核心流程,能够将这个流程优化,对整个系统的性能也有很大的影响.



posted on 2010-01-12 19:25 那谁 阅读(6464) 评论(6)  编辑 收藏 引用 所属分类: tokyo cabinet

评论

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

找到工作了吗?呵呵
2010-01-12 19:26 | code

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

@code
汗,你这个回复也太快了吧.
呵呵,周四去面试.
2010-01-12 19:29 | 那谁

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

汗啊,发现TC的设计和我之前用于分词的XDB词典,以前最近所思考的以crc32值计算后先做比较而期待是否能得到近似平横的二叉树,很接近!

实际测试后(用连续的1,2,3...作key或随机生成的字符串做key分别测试)
用crc32大体能保持相对于根结点的左右子树元素平横,树的高度也能平横,但树的高度却是平横树的2倍左右。。。

也就是说 2万个元素就会达到 32 左右的树高,这样感觉价值不大所以立即放弃,看上去还是要用B+树才比较好。
2010-02-01 23:16 | hightman

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

由此看出来其实tc的设计还有好多地方可以改进的,包括它的hash计算(好多的乘法运算。。。完全没必要以自己的生日作初始值,可以试着参考经典高效的hash算法嘛),据某文章说该作者还比较自恋的,曾经在sourceforge的主页上设置随机的<title>,每句都是“最xxx,顶级xxx。。。”类似的含义。


对了还有一次疑或bucket array的长度是否在创建数据库时就确定下来了的?
2010-02-01 23:22 | hightman

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

你看的是tc哪个版本?
我看的是tokyocabinet-1.4.45,tcutil.c中hash链的实现,作者使用的是平衡树啊,splay-tree伸展树
2011-03-15 17:43 | wtommy

# re: tokyocabinet1.4.19阅读笔记(二)hash数据库查找key流程  回复  更多评论   

您这个就是说,在 key 1 有重复值。这个需要您进去数据库把之前的记录给删除,要不就在新的记录改一下 key 1。<a href=http://www.mbtshoe-sales.com/>mbt outlet</a>
2011-03-29 13:37 | key 1

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理