那谁的技术博客

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

tokyocabinet1.4.19阅读笔记(一)hash数据库概述

开始正式的研究key-value形式的持久化存储方案了,第一个阅读的项目是tokyo cabinet,版本号是1.4.19.

tokyo cabinet支持几种数据库形式,包括hash数据库,B+树数据库,fix-length数据库,table数据库。目前我仅看了第一种hash数据库的实现。之所以选择这个,是因为第一这种类型的数据库似乎是TC中使用的最多的一种,其次它的算法比之B+树又更简单一些而效率上的表现也丝毫不差。

看看TC中代码的组织。关于上面几个分类的数据库实现,实际上在TC项目的代码组织中各自以单个文件的形式出现,比如hash数据库的代码全都集中在 tchdb.c/h中,也只不过4000多行罢了。除去这几种数据库的实现文件,其余的代码文件功能可以大体上分为两类,一类是辅助性质的代码,给项目中各个部分使用上的,另一部分就是单独的管理数据库的CLI程序的代码,比如tchmgr.c/h就是用于管理HASH数据库的CLI程序的代码。之所以要交代一下项目中代码的组织,无非是为了说明,其实如果将问题集中在HASH数据库或者其他形式的数据库实现上,起码在TC中,所要关注的代码是不多的。

首先来看数据库文件是如何组织的。

从图中可以看到,hash数据库文件大致分为四个部分:数据库文件头,bucket 数组,free pool数组,最后的是真正存放record的部分。下面对这几部分做一个说明。

1)数据库文件头
数据库文件头部分存放的是关于该数据库的一些总体信息,包括这些内容:
name offset length feature
magic number 0 32 identification of the database. Begins with "ToKyO CaBiNeT"
database type 32 1 hash (0x01) / B+ tree (0x02) / fixed-length (0x03) / table (0x04)
additional flags 33 1 logical union of open (1<<0) and fatal (1<<1)
alignment power 34 1 the alignment size, by power of 2
free block pool power 35 1 the number of elements in the free block pool, by power of 2
options 36 1 logical union of large (1<<0), Deflate (1<<1), BZIP2 (1<<2), TCBS (1<<3), extra codec (1<<4)
bucket number 40 8 the number of elements of the bucket array
record number 48 8 the number of records in the database
file size 56 8 the file size of the database
first record 64 8 the offset of the first record
opaque region 128 128 users can use this region arbitrarily

需要说明的是,上面这个表格来自tokyocabinet的官方文档说明,在这里。同时,数据库文件中需要存放数据的地方,使用的都是小端方式存放的,以下就不再就这点做说明了。从上面的表格可以看出,数据库文件头的尺寸为256 bytes。
在操作hash数据库的所有API中,都会用到一个对象类型为TCHDB的指针,该结构体中存放的信息就包括了所有数据库文件头的内容,所以每次在打开或者创建一个hash数据库的时候,都会将数据库文件头信息读入到这个指针中(函数tchdbloadmeta)。

2)bucket 数组
bucket array中的每个元素都是一个整数,按照使用的是32位还是64位系统,存放的也就是32位或者64位的整数。这个数组存放的这个整数值,就是每次对 key 进行hash之后得到的hash值所对应的第一个元素在数据库文件中的偏移量。

3)free pool数组
free pool数组中的每个元素定义结构体如下:
typedef struct {                         // type of structure for a free block
  uint64_t off;                          // offset of the block
  uint32_t rsiz;                         // size of the block
} HDBFB; 

很明显,仅有两个成员,一个存放的是在数据库文件中的偏移量,一个则是该free block的尺寸。free pool数组用于保存那些被删除的记录信息,以便于回收利用这些数据区,后续会针对free pool相关的操作,API做一个详细的分析。

4)record数据区
每个record数据区的结构如下表:
name offset length feature
magic number 0 1 identification of record block. always 0xC8
hash value 1 1 the hash value to decide the path of the hash chain
left chain 2 4 the alignment quotient of the destination of the left chain
right chain 6 4 the alignment quotient of the destination of the right chain
padding size 10 2 the size of the padding
key size 12 vary the size of the key
value size vary vary the size of the value
key vary vary the data of the key
value vary vary the data of the value
padding vary vary useless data

当然,上面这个结构只是该record被使用时的结构图,当某一项record被删除时,它的结构就变为:
name offset length feature
magic number 0 1 identification of record block. always 0xB0
block size 1 4 size of the block
   
对比两种情况,首先是最开始的magic number是不同的,当magic number是0XB0也就是该record是已经被删除的free record时,那么紧跟着的4个字节存放的就是这个free record的尺寸,而record后面的部分可以忽略不计了。

分析完了hash数据库文件的几个组成部分,从最开始的数据库文件示意图中还看到,从文件头到bucket array这一部分将通过mmap映射到系统的共享内存中,当然,可以映射的内容可能不止到这里,但是,数据库文件头+bucket array这两部分是一定要映射到共享内存中的,也就是说,hash数据库中映射到共享内存中的内容上限没有限制,但是下限是文件头+bucket array部分。

同时,free pool也会通过malloc分配一个堆上的内存,存放到TCHDB的fbpool指针中。

这几部分(除了record zone),通过不同的方式都分别的读取到内存中,目的就是为了加快查找的速度,后面会详细的进行说明。


 

posted on 2010-01-10 10:22 那谁 阅读(6927) 评论(5)  编辑 收藏 引用 所属分类: linux kernel

评论

# re: tokyocabinet1.4.19阅读笔记(一)hash数据库概述  回复  更多评论   

我最近也在阅读源码,希望与你一起学习!
2010-01-10 17:54 | 阿福

# re: tokyocabinet1.4.19阅读笔记(一)hash数据库概述  回复  更多评论   

@阿福
巧了,我也去过你blog看过,说起来,还是国内研究TC的人,或者说阅读TC代码的人太少了点儿。
2010-01-10 19:16 | 那谁

# re: tokyocabinet1.4.19阅读笔记(一)hash数据库概述  回复  更多评论   

请教一下为什么选择tc而不是bdb?
2010-01-20 16:24 | guest

# re: tokyocabinet1.4.19阅读笔记(一)hash数据库概述[未登录]  回复  更多评论   

@guest
因为tc相对而言较简单,对我入门阅读数据库实现比较方便
2010-01-20 16:26 | 那谁

# re: tokyocabinet1.4.19阅读笔记(一)hash数据库概述  回复  更多评论   

不错!最近正巧也在关注 Key-Value 数据库。

目前 NoSQL 方案越来越被重视,感觉类似 bdb 的东西将更火~~

TC代码中命名方式相当不喜欢 :( TC 的作者相当喜欢搞一个很长的 .c 文件。。。
2010-02-01 23:10 | hightman

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