Chinaunix首页 | 论坛 | 博客

michael

首页　| 　博文目录　| 　关于我

bjpiao

  • 博客访问： 1003912
  • 博文数量： 96
  • 博客积分： 1553
  • 博客等级： 上尉
  • 技术积分： 1871
  • 用 户 组： 普通用户
  • 注册时间： 2011-12-25 14:50
个人简介

专注点，细心点，耐心点 知行合一

文章分类

全部博文（96）

文章存档

2018年（1）

2014年（4）

2013年（31）

2012年（56）

2011年（4）

我的朋友
最近访客
推荐博文
相关博文
Tokyo Cabinet 代码分析

分类： Mysql/postgreSQL

2012-01-15 16:41:54



1.基本介绍

tokyo cabinet是key value数据库(官方主页为：)，由日本人开发应用比较广泛，作者本人是在日本的一个社交网站工作（貌似是日本国内最大的）。张宴的blog对其在金山公司的应用有相应的阐述。

toky cabinet数据库主要的实现有:（1）HASH 结构；（2）B+树结构；（3）Fixed-Length结构；（4）Abstract 结构。

由于key value数据库本身的实现涉及到数据结构、内存组织、文件读写等多个方面，对于其中的实现细节能够有了解，对于数据结构、程序设计功底有较高的提升。所以打算对于tokyo cabinet的源代码进行一个分析。先主要对于abstract类型数据库进行一个分析。

2. Abstract database

 Abstract数据库主要是通过内存实现Hash 数据库,B+树数据库等。主要对于Hash结构进行分析。

2.1 Abastrat数据库主要数据结构

 先对于TCADB的初始化进行分析。

[c-sharp] view plaincopy
  1. /* Create an abstract database object. */  
  2. TCADB *tcadbnew(void){  
  3.   TCADB *adb;  
  4.   TCMALLOC(adb, sizeof(*adb));  
  5.   adb->omode = ADBOVOID;  
  6.   adb->mdb = NULL;  
  7.   adb->ndb = NULL;  
  8.   adb->hdb = NULL;  
  9.   adb->bdb = NULL;  
  10.   adb->fdb = NULL;  
  11.   adb->tdb = NULL;  
  12.   adb->capnum = -1;  
  13.   adb->capsiz = -1;  
  14.   adb->capcnt = 0;  
  15.   adb->cur = NULL;  
  16.   adb->skel = NULL;  
  17.   return adb;  
  18. }  

 其中，根据初始化传入参数不同，建立不同类型数据库。

2.2TCADB数据库打开操作

   通过tcadbopen打开数据库，并对于TCADB结构体指针进行初始化。

   由于是实现hash database，对于TCMDB结构体进行初始化。

  

[c-sharp] view plaincopy
  1. /* Open an abstract database. */  
  2. bool tcadbopen(TCADB *adb, const char *name){  
  3.   assert(adb && name);  
  4.   /*根据配置进行相应的打开操作*/  
  5.   if(adb->omode != ADBOVOID) return false;     
  6.   /*应该是可以配置数据库相关参数，然后通过#进行分割*/  
  7.   TCLIST *elems = tcstrsplit(name, "#");  
  8.   /*获得实际的路径，如果是*,则为内存数据库*/  
  9.   char *path = tclistshift2(elems);  
  10.   if(!path){  
  11.     tclistdel(elems);  
  12.     return false;  
  13.   }  
  14.     /* 此时设置为on-memory hash database， 
  15.    * 对于mdb进行内存分配*/  
  16.    else if(!tcstricmp(path, "*")){  
  17.     adb->mdb = bnum > 0 ? tcmdbnew2(bnum) :    tcmdbnew();  
  18.     adb->capnum = capnum;  
  19.     adb->capsiz = capsiz;  
  20.     adb->capcnt = 0;  
  21.     adb->omode = ADBOMDB;  

 2.2.1 TCMDB结构

  TCMDB结构是on-memory hash database。

[c-sharp] view plaincopy
  1.  /*HASH数据库结构*/  
  2.  typedef struct {                         /* type of structure for a on-memory hash database */  
  3.   void **mmtxs;                          /* mutexes for method */  
  4.   void *imtx;                            /* mutex for iterator */  
  5.   TCMAP **maps;                          /* internal map objects */  
  6.   int iter;                              /* index of maps for the iterator */  
  7. } TCMDB;  

其中TCMAP结构是MAP数组。

[c-sharp] view plaincopy
  1. /*TCPMAP数据结构*/  
  2. typedef struct {                         /* type of structure for a map */  
  3.   TCMAPREC **buckets;                    /* bucket array */  
  4.   TCMAPREC *first;                       /* pointer to the first element */  
  5.   TCMAPREC *last;                        /* pointer to the last element */  
  6.   TCMAPREC *cur;                         /* pointer to the current element */  
  7.   uint32_t bnum;                         /* number of buckets */  
  8.   uint64_t rnum;                         /* number of records */  
  9.   uint64_t msiz;                         /* total size of records */  
  10. } TCMAP;  

MAP结构中含有Hash buckets数组。

2.2.2 TCMDB结构初始化

     在TCMDB结构中，含有TCMAP结构数组，然后各TCMAP结构在含有hash buckets数组。即：在操作过程中先在hash到TCMAP数组中的某个元素上。然后再次hash，定位到TCMAP元素的hash buckets数组元素中。不是单一的采用hash buckets数组直接进行hash映射。

    通过tcmdbnew2对于TCMDB结构进行了初始化，先分配TCMAP数组，然后对于TCMAP结构再分配hash buckets.

[c-sharp] view plaincopy
  1. /*分配方法为tcmdbnew*/  
  2. /* Create an on-memory hash database with specifying the number of the buckets. */  
  3. TCMDB *tcmdbnew2(uint32_t bnum){  
  4.   TCMDB *mdb;  
  5.   /* 默认hash桶的个数为65536*/  
  6.   if(bnum < 1) bnum = TCMDBDEFBNUM;  
  7.   /* 对于bucket number又进行了处理，应该使得hash更为均匀*/  
  8.   bnum = bnum / TCMDBMNUM + 17;  
  9.   TCMALLOC(mdb, sizeof(*mdb));  
  10.   /*对于每个MAP分配读写锁*/  
  11.   TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);  
  12.   TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));  
  13.   TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);  
  14.   if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");  
  15.   for(int i = 0; i < TCMDBMNUM; i++){  
  16.     if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)  
  17.       tcmyfatal("rwlock error");  
  18.     /*对于MAP进行分配，先有MAP，然后基于MAP，分配多个bucket */  
  19.     mdb->maps[i] = tcmapnew2(bnum);  
  20.   }  
  21.   mdb->iter = -1;  
  22.    
  23.   return mdb;  
  24. }  

然后通过tcmapnew2对于TCMAP进行初始化。

[c-sharp] view plaincopy
  1. /*分配MAP的方法*/  
  2. /* Create a map object with specifying the number of the buckets. */  
  3. TCMAP *tcmapnew2(uint32_t bnum){  
  4.   if(bnum < 1) bnum = 1;  
  5.   TCMAP *map;  
  6.   TCMALLOC(map, sizeof(*map));  
  7.   TCMAPREC **buckets;  
  8.   /*如果bnum过大，才用了mmap方式进行了映射。 
  9.    *否则直接在内存中分配*/  
  10.   if(bnum >= TCMAPZMMINSIZ / sizeof(*buckets)){  
  11.     buckets = tczeromap(bnum * sizeof(*buckets));  
  12.   } else {  
  13.     TCCALLOC(buckets, bnum, sizeof(*buckets));  
  14.   }  
  15.   map->buckets = buckets;  //真正使用的hash buckets桶数组  
  16.   map->first = NULL;  //指向头一个record记录  
  17.   map->last = NULL;   //指向最后一个record记录   
  18.   map->cur = NULL;    //通过first和last将所有的节点串联起来   
  19.   map->bnum = bnum;  
  20.   map->rnum = 0;  
  21.   map->msiz = 0;  
  22.   return map;  
  23. }  

TCMAPREC结构为：

TCMAPREC存储了key和value内容。

 ----------------------------------------
|TCMAPREC结构|keybuf'/0'|valuebuf'/0'|
 -------------------------------------

其中的指针left,right为二叉树结构，prev和next将该bucket桶上的record全部

连起来，方面进行遍历。

[c-sharp] view plaincopy
  1. /*数据记录结构*/  
  2. typedef struct _TCMAPREC {               /* type of structure for an element of a map */  
  3.   int32_t ksiz;                          /* size of the region of the key */  
  4.   int32_t vsiz;                          /* size of the region of the value */  
  5.   struct _TCMAPREC *left;                /* pointer to the left child */  
  6.   struct _TCMAPREC *right;               /* pointer to the right child */  
  7.   struct _TCMAPREC *prev;                /* pointer to the previous element */  
  8.   struct _TCMAPREC *next;                /* pointer to the next element */  
  9. } TC

2.3数据记录的写入

   在前面的2节对于内存hash memory的基本数据结构进行了分析。通过tcmdbput将key，value结构写入到内存中。

[c-sharp] view plaincopy
  1. /*通过tcmdbput进行存储 
  2.  *先通过key映射到某个map上面 
  3.  *然后在map上面进行bucket的操作*/  
  4. /* Store a record into an on-memory hash database. */  
  5. void tcmdbput(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){  
  6.   assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);  
  7.   unsigned int mi;  
  8.   TCMDBHASH(mi, kbuf, ksiz);  
  9.   if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;  
  10.   tcmapput(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);  
  11.   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);  
  12. }  

2.3.1 Hash算法映射

先通过hash算法，映射到maps数据的元素上。

 

[c-sharp] view plaincopy
  1. /*将一个对象存储在map object中*/  
  2. /* Store a record into a map object. */  
  3. void tcmapput(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){  
  4.  assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);  
  5.   if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;  
  6.   uint32_t hash;  
  7.   /*第一次HASH映射到map数组上*/  
  8.   TCMAPHASH1(hash, kbuf, ksiz);  
  9.   int bidx = hash % map->bnum;  
  10.   TCMAPREC *rec = map->buckets[bidx];  
  11.   /*entp保存父节点地址*/  
  12.   TCMAPREC **entp = map->buckets + bidx;  
  13.   /*第二次HASH映射到特定map的bucket上*/  
  14.   TCMAPHASH2(hash, kbuf, ksiz);  
  15.   hash &= ~TCMAPKMAXSIZ;  
  16.     

再通过hash算法，映射到特定maps元素的buckets数组中。即：先找个MAP，再找buckets。

2.3.2记录初次插入二叉树

我们先讨论初次加入二叉树结构的方法。

[c-sharp] view plaincopy
  1. /*如果为首次加入，则直接放入到buckets中*/  
  2. /*计算需要pad的字节大小*? 
  3.   int psiz = TCALIGNPAD(ksiz); 
  4. map->msiz += ksiz + vsiz; 
  5. /*分配key，value，pad大小，末尾'/0' 
  6.  *rec表示了左右子树，父节点*/  
  7. TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);  
  8. char *dbuf = (char *)rec + sizeof(*rec);  
  9. /*在TCMAPREC结构体之后，存放key的内容*/  
  10. memcpy(dbuf, kbuf, ksiz);  
  11. /*key值通过在末尾增加'/0'分割*/  
  12. dbuf[ksiz] = '/0';  
  13. rec->ksiz = ksiz | hash;  
  14. /*value值的拷贝*/  
  15. memcpy(dbuf + ksiz + psiz, vbuf, vsiz);  
  16. dbuf[ksiz+psiz+vsiz] = '/0';  
  17. /*修改rec记录的大小*/  
  18. rec->vsiz = vsiz;  
  19. rec->left = NULL;  
  20. rec->right = NULL;  
  21. /*record的prev节点指向原先的最后一个节点 
  22.  *构成双向链表结构，并通过Map的first和last 
  23.  *节点进行连接*/  
  24. rec->prev = map->last;  
  25. rec->next = NULL;  
  26. /*加入到树中*/  
  27. *entp = rec;  
  28. /*如果该buckets数组为初次插入节点，则first头节点指向该记录*/  
  29. if(!map->first) map->first = rec;  
  30. /*如果last节点不为空，（已经有插入节点），则将原先节点的next节点 
  31.  *指向该记录，然后last节点指向新的记录，即：将原先的节点都连接起来*/  
  32. if(map->last) map->last->next = rec;  
  33. map->last = rec;  
  34. /*record记录数增加*/  
  35. map->rnum++;  

 2.3.3记录插入二叉树

   在已有二叉树结构中增加记录。循环遍历二叉树结构，插入节点。

[c-sharp] view plaincopy
  1. /*二叉树遍历过程，先比较hash，找到相应的节点， 
  2.  *再比较相应的key值，如果key值不相同，同样作为 
  3.  *二叉树进行比较插入*/  
  4. while(rec){  
  5.     uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;  
  6.     uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;  
  7.     /*如果hash值大，则选择左子树，entp存放父节点*/  
  8.     if(hash > rhash){  
  9.       entp = &(rec->left);  
  10.       rec = rec->left;  
  11.     } else if(hash < rhash){  
  12.       entp = &(rec->right);  
  13.       rec = rec->right;  
  14.     } else {  
  15.     /*如果相同，则比较key是否相同，如果不相同继续遍历 
  16.      *二叉树*/  
  17.       char *dbuf = (char *)rec + sizeof(*rec);  
  18.       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);  
  19.       if(kcmp < 0){  
  20.         entp = &(rec->left);  
  21.         rec = rec->left;  
  22.       } else if(kcmp > 0){  
  23.         entp = &(rec->right);  
  24.         rec = rec->right;  
  25.       } else {  
  26.       /*如果key值相同，则对于原先的rec进行更新*/  
  27.         map->msiz += vsiz - rec->vsiz;  
  28.         int psiz = TCALIGNPAD(ksiz);  
  29.         if(vsiz > rec->vsiz){  
  30.           TCMAPREC *old = rec;  
  31.           TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);  
  32.           if(rec != old){  
  33.             if(map->first == old) map->first = rec;  
  34.             if(map->last == old) map->last = rec;  
  35.             if(map->cur == old) map->cur = rec;  
  36.             *entp = rec;  
  37.             if(rec->prev) rec->prev->next = rec;  
  38.             if(rec->next) rec->next->prev = rec;  
  39.             dbuf = (char *)rec + sizeof(*rec);  
  40.           }  
  41.         }  
  42.         memcpy(dbuf + ksiz + psiz, vbuf, vsiz);  
  43.         dbuf[ksiz+psiz+vsiz] = '/0';  
  44.         rec->vsiz = vsiz;  
  45.         return;  
  46.       }  
  47.     }  

2.3.4 memory hash database 结构层次图

memory Hash MAP 结构图：
默认TCMAP数组8个元素，先映射到不同TCMAP元素之上。
 --------------------------------
|TCMAP1 | TCMAP2 | .....| TCMAP8 |
 --------------------------------
    |
    V再次映射到buckets数组中的元素
  --------------------------------------------------------------
 |rec_buckets数组|rec_first|rec_last|rec_cur|bucket数目|rec数目|
  -------------------------------------------------------------
    |
    VREC被映射到具体的bucket元素，然后按照二叉树的结构进行存储
 -------------------------------------------------
 | ksiz|vsiz|left_rec|right_rec|prev_rec|next_rec|
 -------------------------------------------------
map中的last和first指针，将所有的rec结构进行串联，从而方便遍历。

2.4数据记录的查找

   在前面的部分对于记录的插入进行了阐述。本节对通过key查找value方法进行了分析。

2.4.1TCMAP数组查找

  先映射到MAP数组的一个元素，然后基于该元素对于hash buckets数组进行访问。

[c-sharp] view plaincopy
  1. 通过tcmdbget进行查找  
  2.     /* Retrieve a record in an on-memory hash database. */  
  3. void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){  
  4.   assert(mdb && kbuf && ksiz >= 0 && sp);  
  5.   unsigned int mi;  
  6.   /*将key映射到map数组的一个元素上*/  
  7.   TCMDBHASH(mi, kbuf, ksiz);  
  8.   /*通过mutex锁唯一访问*/  
  9.   if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;  
  10.   int vsiz;  
  11.   const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);  
  12.   char *rv;  
  13.   if(vbuf){  
  14.     TCMEMDUP(rv, vbuf, vsiz);  
  15.     *sp = vsiz;  
  16.   } else {  
  17.     rv = NULL;  
  18.   }  
  19.   pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);  
  20.   return rv;  
  21. }  

2.4.2 hash buckets二叉树查找

  查找二叉树结构，获得value对象，返回的是分配好的内存地址，所以查找使用以后，

需要进行释放。

[c-sharp] view plaincopy
  1. /*通过tcmapget遍历二叉搜索树，查找value*/  
  2. /* Retrieve a record in a map object. */  
  3. const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){  
  4.   assert(map && kbuf && ksiz >= 0 && sp);  
  5.   if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;  
  6.   uint32_t hash;  
  7.   TCMAPHASH1(hash, kbuf, ksiz);  
  8.   /*先定位到bucket一个元素上*/  
  9.   TCMAPREC *rec = map->buckets[hash%map->bnum];  
  10.   TCMAPHASH2(hash, kbuf, ksiz);  
  11.   hash &= ~TCMAPKMAXSIZ;  
  12.   /*遍历二叉树 
  13.    *hash值相同，然后比较key值 
  14.    */  
  15.   while(rec){  
  16.     uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;  
  17.     uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;  
  18.     if(hash > rhash){  
  19.       rec = rec->left;  
  20.     } else if(hash < rhash){  
  21.       rec = rec->right;  
  22.     } else {  
  23.     /*dbuf的结构是rec结构体之后存放了key 
  24.      *TCKEYCMP先比较了两个的keybuffer的大小， 
  25.      *然后再比较值*/  
  26.       char *dbuf = (char *)rec + sizeof(*rec);  
  27.       int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);  
  28.       if(kcmp < 0){  
  29.         rec = rec->left;  
  30.       } else if(kcmp > 0){  
  31.         rec = rec->right;  
  32.       } else {  
  33.         *sp = rec->vsiz;  
  34.         /*找到之后，翻译value所在buffer的地址 
  35.          *通过TCMEMDUP复制内存, 
  36.          *所在在使用完了Value以后，应该释放*/  
  37.         return dbuf + rksiz + TCALIGNPAD(rksiz);  
  38.       }  
  39.     }  
  40.   }  

 注: hashmap中使用了2插树的方式来加速查询时间. 每个桶和桶中元素的连接是通过2插数的形式进行的

阅读(3578) | 评论(2) | 转发(3) |
0

上一篇：NoSQL数据库探讨之一 － 为什么要用非关系数据库？

下一篇：数据可视化是怎样创造出来的

给主人留下些什么吧！~~

bjpiao2012-01-28 22:09:01

☆彼岸★花开: 是哈希表与二叉树的结合体吧？~.....
是的, hash之后, 使用了二叉树, 查找快些

回复 | 举报

☆彼岸★花开2012-01-16 22:14:48

是哈希表与二叉树的结合体吧？~

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6