tokyocabinet源码分析.doc

码农70%时间看别人的代码，30%的时间自己写代码。本人也是这样由于手头上的项目，花几天的时间把Tokyocabinet看了一下。Tokyocabinet 是一个DBM的实现，这里的数据库由一系列key-value对的记录构成。Key和value都可以是任意长度的字节序列。Tokyocabinet的源码结构md5.c myconf.c tcadb.c tcamgr.c tcatest.c tcawmgr.c tcbdb.c tcbmgr.c tcbmttest.c tcbtest.c tcfdb.c tcfmgr.c tcfmttest.c tcftest.c tchdb.c tchmgr.c tchmttest.c tchtest.c tctdb.c tctmgr.c tctmttest.c tcttest.c tcucodec.c tcumttest.c tcutest.c tcutil.c其中,tca*.c是抽象出来的数据库的代码，这个的库可以是hashtable,fix-length array database,b+ tree database 中的任何一种。tcb*.c是b+ tree数据库的相关代码,tcf*.c是fix-length array 数据库的相关代码,tch*.c是hashtable型数据库相关代码,tct*.c是table database相关的代码。理解了这些数据存储类型的区别,才能理解后来tokyotyrant的一些参数设置.在下一节就专门讲述这些; tcu*.c是工具类的杂项函数集。 基本上所有的数据库类型都有*test和*mttest,*mgr三个二进制程序。比如fix-length-array database有tcftest.c,tcftest.c,tcfmttest.c都有是main函数的。Tokyocabinet的存储类型n 如果DB名字为“*” 内存中的Hash存储n 如果DB名字为“+” 内存中的B+存储n 如果DB名字为“.tch” 硬盘上的HASH存储n 如果DB名字为“.tch” 硬盘上的B+存储n 如果DB名字为“.tcf” 像数组一样的连续数字对应定长值的存储n 如果DB名字为“.tct” 一个key值下面对应很多个name-value的形式Tokyocabinet的关键参数 bnum : 指定bucket array的数量。推荐设置为存储总记录的0.5 4倍，使key的哈希分布更均匀，减少在bucket内二分查找的时间复杂度。 xmsiz: 指定TCHDB的扩展MMAP内存大小。 rcnum: 缓存内存的记录条数 dbgfd : 设置为1，调试信息下面是硬盘上HASH存储的源码分析文件结构 图1 tch文件格式 如上图，文件大概分为3个部分1 256个字节的头，见下表；2 bnum个bucket数组，每个bucket保存offset, bucket 下第一个数据的绝对偏移量（文件）；3 数据部分 表1 头的结构magic number032identification of the database. Begins with ToKyO CaBiNeTdatabase type321hash (0x01) / B+ tree (0x02) / fixed-length (0x03) / table (0x04)additional flags331logical union of open (10) and fatal (11)alignment power341the alignment size, by power of 2free block pool power351the number of elements in the free block pool, by power of 2options361logical union of large (10), Deflate (11), BZIP2 (12), TCBS (13), extra codec (14)bucket number408the number of elements of the bucket arrayrecord number488the number of records in the databasefile size568the file size of the databasefirst record648the offset of the first recordopaque region128128users can use this region arbitrarilyOn-memory hash结构 图2 这是On-memory hash结构图 1 最上层是maps数组，长度固定为8，对key的访问先hash到其中一个map; 2 每个map由buckets数组组成（bnum/8）。Key经过第二次hash到其中一个bucket; 3 hash到同一bucket的recor