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的初始化进行分析。
-
- TCADB *tcadbnew(void){
- TCADB *adb;
- TCMALLOC(adb, sizeof(*adb));
- adb->omode = ADBOVOID;
- adb->mdb = NULL;
- adb->ndb = NULL;
- adb->hdb = NULL;
- adb->bdb = NULL;
- adb->fdb = NULL;
- adb->tdb = NULL;
- adb->capnum = -1;
- adb->capsiz = -1;
- adb->capcnt = 0;
- adb->cur = NULL;
- adb->skel = NULL;
- return adb;
- }
其中,根据初始化传入参数不同,建立不同类型数据库。
2.2TCADB数据库打开操作
通过tcadbopen打开数据库,并对于TCADB结构体指针进行初始化。
由于是实现hash database,对于TCMDB结构体进行初始化。
-
- bool tcadbopen(TCADB *adb, const char *name){
- assert(adb && name);
-
- if(adb->omode != ADBOVOID) return false;
-
- TCLIST *elems = tcstrsplit(name, "#");
-
- char *path = tclistshift2(elems);
- if(!path){
- tclistdel(elems);
- return false;
- }
-
-
- else if(!tcstricmp(path, "*")){
- adb->mdb = bnum > 0 ? tcmdbnew2(bnum) : tcmdbnew();
- adb->capnum = capnum;
- adb->capsiz = capsiz;
- adb->capcnt = 0;
- adb->omode = ADBOMDB;
2.2.1 TCMDB结构
TCMDB结构是on-memory hash database。
-
- typedef struct {
- void **mmtxs;
- void *imtx;
- TCMAP **maps;
- int iter;
- } TCMDB;
其中TCMAP结构是MAP数组。
-
- typedef struct {
- TCMAPREC **buckets;
- TCMAPREC *first;
- TCMAPREC *last;
- TCMAPREC *cur;
- uint32_t bnum;
- uint64_t rnum;
- uint64_t msiz;
- } 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.
-
-
- TCMDB *tcmdbnew2(uint32_t bnum){
- TCMDB *mdb;
-
- if(bnum < 1) bnum = TCMDBDEFBNUM;
-
- bnum = bnum / TCMDBMNUM + 17;
- TCMALLOC(mdb, sizeof(*mdb));
-
- TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);
- TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));
- TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);
- if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");
- for(int i = 0; i < TCMDBMNUM; i++){
- if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)
- tcmyfatal("rwlock error");
-
- mdb->maps[i] = tcmapnew2(bnum);
- }
- mdb->iter = -1;
-
- return mdb;
- }
然后通过tcmapnew2对于TCMAP进行初始化。
-
-
- TCMAP *tcmapnew2(uint32_t bnum){
- if(bnum < 1) bnum = 1;
- TCMAP *map;
- TCMALLOC(map, sizeof(*map));
- TCMAPREC **buckets;
-
-
- if(bnum >= TCMAPZMMINSIZ / sizeof(*buckets)){
- buckets = tczeromap(bnum * sizeof(*buckets));
- } else {
- TCCALLOC(buckets, bnum, sizeof(*buckets));
- }
- map->buckets = buckets;
- map->first = NULL;
- map->last = NULL;
- map->cur = NULL;
- map->bnum = bnum;
- map->rnum = 0;
- map->msiz = 0;
- return map;
- }
TCMAPREC结构为:
TCMAPREC存储了key和value内容。
----------------------------------------
|TCMAPREC结构|keybuf'/0'|valuebuf'/0'|
-------------------------------------
其中的指针left,right为二叉树结构,prev和next将该bucket桶上的record全部
连起来,方面进行遍历。
-
- typedef struct _TCMAPREC {
- int32_t ksiz;
- int32_t vsiz;
- struct _TCMAPREC *left;
- struct _TCMAPREC *right;
- struct _TCMAPREC *prev;
- struct _TCMAPREC *next;
- } TC
2.3数据记录的写入
在前面的2节对于内存hash memory的基本数据结构进行了分析。通过tcmdbput将key,value结构写入到内存中。
-
-
-
-
- void tcmdbput(TCMDB *mdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
- assert(mdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
- unsigned int mi;
- TCMDBHASH(mi, kbuf, ksiz);
- if(pthread_rwlock_wrlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return;
- tcmapput(mdb->maps[mi], kbuf, ksiz, vbuf, vsiz);
- pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
- }
2.3.1 Hash算法映射
先通过hash算法,映射到maps数据的元素上。
-
-
- void tcmapput(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
- assert(map && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
- if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
- uint32_t hash;
-
- TCMAPHASH1(hash, kbuf, ksiz);
- int bidx = hash % map->bnum;
- TCMAPREC *rec = map->buckets[bidx];
-
- TCMAPREC **entp = map->buckets + bidx;
-
- TCMAPHASH2(hash, kbuf, ksiz);
- hash &= ~TCMAPKMAXSIZ;
-
再通过hash算法,映射到特定maps元素的buckets数组中。即:先找个MAP,再找buckets。
2.3.2记录初次插入二叉树
我们先讨论初次加入二叉树结构的方法。
-
-
-
-
-
-
- TCMALLOC(rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
- char *dbuf = (char *)rec + sizeof(*rec);
-
- memcpy(dbuf, kbuf, ksiz);
-
- dbuf[ksiz] = '/0';
- rec->ksiz = ksiz | hash;
-
- memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
- dbuf[ksiz+psiz+vsiz] = '/0';
-
- rec->vsiz = vsiz;
- rec->left = NULL;
- rec->right = NULL;
-
-
-
- rec->prev = map->last;
- rec->next = NULL;
-
- *entp = rec;
-
- if(!map->first) map->first = rec;
-
-
- if(map->last) map->last->next = rec;
- map->last = rec;
-
- map->rnum++;
2.3.3记录插入二叉树
在已有二叉树结构中增加记录。循环遍历二叉树结构,插入节点。
-
-
-
- while(rec){
- uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
- uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
-
- if(hash > rhash){
- entp = &(rec->left);
- rec = rec->left;
- } else if(hash < rhash){
- entp = &(rec->right);
- rec = rec->right;
- } else {
-
-
- char *dbuf = (char *)rec + sizeof(*rec);
- int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
- if(kcmp < 0){
- entp = &(rec->left);
- rec = rec->left;
- } else if(kcmp > 0){
- entp = &(rec->right);
- rec = rec->right;
- } else {
-
- map->msiz += vsiz - rec->vsiz;
- int psiz = TCALIGNPAD(ksiz);
- if(vsiz > rec->vsiz){
- TCMAPREC *old = rec;
- TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
- if(rec != old){
- if(map->first == old) map->first = rec;
- if(map->last == old) map->last = rec;
- if(map->cur == old) map->cur = rec;
- *entp = rec;
- if(rec->prev) rec->prev->next = rec;
- if(rec->next) rec->next->prev = rec;
- dbuf = (char *)rec + sizeof(*rec);
- }
- }
- memcpy(dbuf + ksiz + psiz, vbuf, vsiz);
- dbuf[ksiz+psiz+vsiz] = '/0';
- rec->vsiz = vsiz;
- return;
- }
- }
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数组进行访问。
- 通过tcmdbget进行查找
-
- void *tcmdbget(TCMDB *mdb, const void *kbuf, int ksiz, int *sp){
- assert(mdb && kbuf && ksiz >= 0 && sp);
- unsigned int mi;
-
- TCMDBHASH(mi, kbuf, ksiz);
-
- if(pthread_rwlock_rdlock((pthread_rwlock_t *)mdb->mmtxs + mi) != 0) return NULL;
- int vsiz;
- const char *vbuf = tcmapget(mdb->maps[mi], kbuf, ksiz, &vsiz);
- char *rv;
- if(vbuf){
- TCMEMDUP(rv, vbuf, vsiz);
- *sp = vsiz;
- } else {
- rv = NULL;
- }
- pthread_rwlock_unlock((pthread_rwlock_t *)mdb->mmtxs + mi);
- return rv;
- }
2.4.2 hash buckets二叉树查找
查找二叉树结构,获得value对象,返回的是分配好的内存地址,所以查找使用以后,
需要进行释放。
-
-
- const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp){
- assert(map && kbuf && ksiz >= 0 && sp);
- if(ksiz > TCMAPKMAXSIZ) ksiz = TCMAPKMAXSIZ;
- uint32_t hash;
- TCMAPHASH1(hash, kbuf, ksiz);
-
- TCMAPREC *rec = map->buckets[hash%map->bnum];
- TCMAPHASH2(hash, kbuf, ksiz);
- hash &= ~TCMAPKMAXSIZ;
-
-
-
- while(rec){
- uint32_t rhash = rec->ksiz & ~TCMAPKMAXSIZ;
- uint32_t rksiz = rec->ksiz & TCMAPKMAXSIZ;
- if(hash > rhash){
- rec = rec->left;
- } else if(hash < rhash){
- rec = rec->right;
- } else {
-
-
-
- char *dbuf = (char *)rec + sizeof(*rec);
- int kcmp = TCKEYCMP(kbuf, ksiz, dbuf, rksiz);
- if(kcmp < 0){
- rec = rec->left;
- } else if(kcmp > 0){
- rec = rec->right;
- } else {
- *sp = rec->vsiz;
-
-
-
- return dbuf + rksiz + TCALIGNPAD(rksiz);
- }
- }
- }
注: hashmap中使用了2插树的方式来加速查询时间. 每个桶和桶中元素的连接是通过2插数的形式进行的