dbm之sdbm

sdbm是 http://amisha.pragmaticdata.com/~schadow/dbm-java/ 上一个dbm的实现。sdbm主要由dir和page组成。它和w3c-dbm(见dbm之w3c-dbm)有所不同，w3c-dbm由dir和block组成。w3c-dbm的element保存时是区分索引和kv_content的，并且 kv_content 可以跨block w3c-dbm_block的，所以对kv的大小没限制。sdbm_page有点像hashmap的bucket，处理hash冲突时采用拉链法。因为sdbm_page是定长的，并且kv不能跨page，所以对于kv的大小限制受page大小影响。另一个区别是两者对dir的组织也不一样。w3c-dbm对dir的处理更像普通的hashmap，bucket数组，满时double dir。sdbm把dir作为一棵binary tree处理。此外，w3c-dbm使用一个文件来保存dir和kv的信息，sdbm则使用两个文件，一个保存dir信息，dir_file，另一个保存page，page_file。

 

sdbm之page：

 

page_file被划分一个个page，对应project的class Page。 Page 有3个属性：1.pag:bytes array;2.pageSize:size of pag;3.bno:page num，唯一，通过bno可以确定对应的page在page_file的偏移量。off(page)=page.bno*PAGE_SIZE。Page 还支持put_kv,get_kv,reove_kv 和 split_page等操作。

 

page在page_file的格式：

 

    *     +--------------------------------+

    * ino  | n | keyoff | datoff | keyoff |

    *     +------------+--------+--------+

    *        | datoff | - - - ---->   |

    *     +--------+----------------------+

    *        |    F R E E A R E A        |

    *     +--------------+----------------+

    *        |  <---- - - - | data          |

    *     +--------+-----+----+----------+

    *        |  key   | data     | key      |

    *     +--------+----------+-----------+

 

在page头的page_n(n)，keyoff，datoff都是占2byes的short value。尾部的key，data则是kv的content。z中间则是可用空间。当插入一个新kv时，根据图示的两个箭头方向收缩可用空间。

ino：两个函数，getIno(int i)，setIno(int i,new_ino)。主要是get/set page头第i个short value；

page_n:keyoff+datoff的个数，也就是kv_num*2。当page_n=0，free_area_begin=2，free_area_end=PAGE_SIZE；当page_n不等于0，getIno(page_n)就是最后一个kv的dataoff的值，该值就是free_area_end；

keyoff:所对应的key的偏移量；

datoff:所对应的data的偏移量；

1 kv所占的kv_space=2*2（short_len）+ k_len+v_len。

page的几个操作：

1.get_kv:只能遍历page的key；

2.put_kv：伪代码如下：

    int n=get_ino(0);
    int kv_off= n==0?page_size:get_ino(n);

   kv_off -= k_len;
   copy key to page[kv_off,kv_off+k_len];
   set_ino(n+1,kv_off);

   kv_off -= v_len;
   copy value to page[kv_off,kv_off+v_len];
   set_ino(n+2,kv_off);

   set_ino(0,n+2);

 

3.remove_kv：删除kv可能会出现free_area的空洞（当该kv不是last put kv），这时需要移动kv去覆盖空洞，并且更新受影响的keyoff 和datoff。最后set_ino(0,get_ino(0)-2)；

4.split_page：接受2个参数new_page 和maskbit。split cur_page伪代码如下：

    Page temp_page;
    copy cur_page to temp_page;
    clear cur_page;
    clear new_page;

    for kv in temp_page{
        if hash(kv_k)&maskbit !=0 put kv to new_page;
        else put kv to cur_page;
    }

maskbit的作用在dir的分析中会解释。

sdbm之dir：

sdbm使用binary tree来 组件dir。所有的leaf node 对应1个page。

每个 binary tree node有1个状态位：是否有子节点。该信息保存在dir_file里，占1bit，dir_file的内容作为1个 bit array，每个bit对应二叉树的一个节点。对该状态的操作通过getdbit和setdbit来操作。

简单描述一下dir是如何工作的：

1.当只有1个page时，不需要使用目录树来定位page；

2.给出一个hash_value 定位page，假设当前目录树的结构如下：

|0|

|1| |2|

|3| |4|

 

从root(node0)开始，hash_value的每个bit(从低到高)如果是0则前进到左子节点，否则到 右子节点。直到没有子节点而停下，所到达的leaf node就是该hash_value对应的page,并且该page的bno为到达该节点的轨迹。例 如0x**01,定位到node2，page_2_bno=0x01. 0x**10定位到node4，page_4_bno=0x10.

3.split，假如在上文的树中，node2需要split,第2bit为1的移到新的page_6.

|0|

|1| |2|

|3| |4| |5| |6|

split后,page_2变为page_5，但是hash_value-->page的映射不变。

因为page_5_bno=0x01=page_2_bno.page_6_bno=0x11.

总结：

w3c-dbm和sdbm都是非常简单的kv store的两个实现，不支持事务，也不保证数据的可靠。但是通过分析这两个project，对hash如何结合disk来使用有一定的认识，这和in-memory的hash还是有一定的区别的。下一篇文章会分析jdbm的实现，它通过WAL（write-ahead-log）实现事务。并且对kv的组织和w3c-dbm，sdbm也不一样。