那谁的技术博客

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

tokyocabinet1.4.19阅读笔记(四)hash数据库freepool的组织与管理

这一节关注freepool的组织,freepool顾名思义,就是负责存放被删除,空闲出来的空间,以便于后面回收利用.
在第一节中已经提到,这一个部分,在初始化的时候会全部读入采用malloc从堆中分配的内存中,所以对它的大部分操作都是直接在内存中进行的---除了要同步到数据库文件中时.

所有的freepool,以数组形式组织在一起,每个freepool元素结构体的定义是:
typedef struct {                         // type of structure for a free block
  uint64_t off;                          // offset of the block
  uint32_t rsiz;                         // size of the block
} HDBFB;
可见,每个freepool关注的仅有两个因素:所保存block在数据库文件中的offset,以及这块block的尺寸.

当需要插入新的记录时,需要在当前的freepool中进行查询,看有没有适合的freepool可以回收利用,因此需要根据尺寸进行查询,所以为了提高查询速率,freepool数组中的元素是根据每个freepool的尺寸进行排序的,这样根据尺寸进行查找时就可以采用二分查找提高效率了,但是要注意到可能出现的找到的尺寸不符合要求,过大了(大于所需尺寸的一倍以上),这个时候会将这块freepool进行拆分,一部分给予使用,剩余的回收到freepool中.另外,如果在freepool中查找所需尺寸出现了很多次失败的情况(一旦失败表示没有符合要求的freepool可以回收利用,这时就需要增加数据库文件大小以加入新的记录了),就需要对freepool进行一次合并操作,将相邻的freepool合并起来形成尽可能大的freepool,而判断是否相邻的依据就是根据在数据库文件中的offset,此时又会将所有的freepool根据offset进行一次排序,然后再进行前面的合并操作.

以上就是freepool数组的大体组织情况,因为它保存在内存里面的,而且会经常有更新,那么就会出现当前的freepool与数据库文件中保存的freepool情况不一致的可能,所以在关闭/拷贝数据库的时候还要将内存中的freepool信息一次性的同步到数据库文件中,但是我注意到,在数据库运行期间是没有这个同步操作的,所以,一旦数据库被非法关闭,那么数据库文件中里面的freepool信息将完全的错乱,我想这也是TC不够安全的一个佐证吧.

下面简单的介绍TC hash数据库中与freepool相关的API:
1)static bool tchdbsavefbp(TCHDB *hdb)
将当前内存中freepool数组信息同步到数据库文件中,仅当关闭/拷贝数据库时被调用.

2) static bool tchdbloadfbp(TCHDB *hdb)
加载数据库文件中的freepool信息到内存中,与tchdbsavefbp 是两个互逆的过程.

3) static void tcfbpsortbyoff(HDBFB *fbpool, int fbpnum)
根据offset对freepool数组进行排序

4) static void tcfbpsortbyrsiz(HDBFB *fbpool, int fbpnum)
根据size对freepool数组进行排序

5) static void tchdbfbpmerge(TCHDB *hdb)
将地址相邻的freepool进行合并,内部实现中首先会调用tcfbpsortbyoff 对freepool根据offset进行排序,这样才方便合并操作.

6) static void tchdbfbpinsert(TCHDB *hdb, uint64_t off, uint32_t rsiz)
将一块block插入到合适的freepool中,插入之前和插入之后freepool数组都是根据size排序好的.

7) static bool tchdbfbpsearch(TCHDB *hdb, TCHREC *rec)
根据rec所要求的尺寸,查找一块合适的freepool回收利用,如果找到的freepool过大(大于所要求的一倍),那么就分为两份,一份负责插入rec,一份重新插入到合适的freepool中.

8) static bool tchdbfbpsplice(TCHDB *hdb, TCHREC *rec, uint32_t nsiz)
查看紧跟着rec的数据库文件空间是否是空闲的,如果是就合并进来,也就是加大rec的尺寸,以满足nsiz大小的要求.

9) static bool tchdbwritefb(TCHDB *hdb, uint64_t off, uint32_t rsiz)
将一块block置位空闲的(就是写它的magic number为0xb0)

总体来看,freepool是TC hash数据库中操作很频繁的一块数据区,在删除一条记录时需要将这条记录放到合适的freepool中,而新增记录时还需要从当前的freepool中查找合适的block,但是由于freepool是保存在内存中的,而且又进行过排序因此可以使用二分查找算法,所以对它进行的管理操作还是较为高效的.




posted on 2010-01-22 22:38 那谁 阅读(6533) 评论(1)  编辑 收藏 引用 所属分类: tokyo cabinet

评论

# re: tokyocabinet1.4.19阅读笔记(四)hash数据库freepool的组织与管理  回复  更多评论   

TC的HDB的碎片整理如果只考虑相邻空闲块进行merge的话,效果有限。另外,对机器和进程异常的处理正如你所说,还不够安全。
2010-01-24 15:56 | davidripple

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