Berkeley DB 的桶操作

Posted by zhangxiaojian on August 8, 2014

从去年开始,学习Berkeley DB 也有一段时间,因为没有找到比较好的中文书籍,一直断断续续看官方的英文文档,开着有道词典,不认识的单词就划词去查。开始速度很慢,后来熟了一些就能快一点。这两个礼拜正式投入使用,学习实验室INM数据库存储模块,完成了物化视图实例的存储接口。期间也对Berkeley DB的桶操作有了更深入一些的了解。

1.BDB简单存取

BDB是键值对存取,一个键值对叫做一个record,键和值使用相同的数据结构,C++ API中定义为Dbt,用数据的指针和数据的长度初始化Dbt对象。假设key值为“luffy”,value值为“op”。

char *pkey = "luffy";
char *pvalue = "op";
Dbt key(pkey,strlen(pkey)+1);
Dbt value(pvalue,strlen(pvalue)+1);

这样就准备好了要存储的record,当然,数据可以是任何复杂的类型,也可以是序列化之后的数据块。存储还需要Db类型的句柄,它与一个物理文件关联,一般在使用数据库的时候打开。

Db db(NULL,0);
db.open(NULL,            // Transaction pointer
        "my_db.db",      // Database file name
        NULL,            // Optional logical database name
        DB_BTREE,        // Database access method
        oFlags,          // Open flags
        0);              // File mode

第二个参数是关联的文件,第四个参数是数据库的组织方式,这里使用的是最为广泛的BTree类型。剩下的参数详细使用方式可以参考这里。接下来存到数据库中:

db.put(NULL,&key,&value,0);

函数返回0表示操作正确,返回其他非0数或者抛出异常都代表操作失败。

与数据库取的时候操作类似,要打开数据库,定义key值。不同的是不需要定义value,我们需要根据key来找到value的值。

char *pkey = "luffy";
Dbt key(pkey,strlen(pkey)+1);
Dbt data;

db.get(NULL,&key,&data,0);
char *value = (char*)data.get_data();

此时value为”op”,完成了一次简单的存取。实际上的使用较为复杂,涉及多种配置,下面将要介绍的桶操作就是其中一种。

2.一个桶操作的例子

从上面的例子可以看到,我们每插入一条数据,就需要调用一次put函数,如果数据库配置支持事务,锁等复杂的功能时,BDB之中的处理会有较大开销,当数据比较多的时候,就会降低系统性能。BDB为此提供了批量存取、删除的API,可以一次性对多条record操作。示例如下:

#define BULK_SIZE 8*1024           //定义桶大小,必须为1024的偶数倍。

void *memory = malloc(BULK_SIZE);  //分配空间
Dbt key;             
key.set_flags(DB_DBT_USERMEM);     //告诉系统,使用自己的内存空间
key.set_data(memory);
key.set_ulen(BULK_SIZE);           //和上一节的size参数不同。

//假设要存的数据在vector中
vector< pair<string,string> >::iterator iter = data.begin(); 
while(iter != data.end())
{
    DbMultipleKeyDataBuilder builder(key);   
    do{
        size_t key_len = iter->first.size() + 1;
        size_t data_len = iter->second.size() + 1;
        void *key_str,*data_str;
        if(builder.reserve(key_str,key_len,data_str,data_len)
                == false) //预分配空间,并初始化指针参数
        {
            db.put(NULL,&key,NULL,DB_MUTIPLE_KEY);
            break;
        }else{
            //将数据放到预分配空间里
            strcpy((char*)key_str,iter->first.c_str());  
            strcpy((char*)data_str,iter->second.c_str());
        }
        ++iter;
    }while(iter != data.end());
    if(iter == data.end())
    {
        db.put(NULL,&key,NULL,DB_MUTIPLE_KEY);  //最终的批量操作
        break;
    }	
} 

如上述代码所示,不是将key-value值一次次放入数据库中,而是全部放入预先分配的空间中,然后再批量的交给BDB处理。这样在数据量较大,操作频繁的情况下,速度可以提升数倍。但是显然也需要付出预先分配一定空间的代价。

3.发现问题

我们将数据放到预先分配的memory中,然后每次存放新的数据要预先向memory申请空间,那么memory用光了怎么办?难道需要存入8M数据后再分配8M的pure memory给新的数据用吗?如果这样,插入10G数据,不是需要10G内存,不断申请分配,得不偿失了。

事实证明,每次使用的memory不需要是刚刚分配好的pure memory,不论它里面在使用前有什么数据,都不影响。会从起始地址开始,新的数据覆盖之前的数据。

那么,不妨假设在我们使用memory的时候,它已经存了值,也许是这样:

/img/uploads/2014/08/DYTQEN0D3CWEKL4V4UD.jpg)

在内存中是以c风格字符串存储,把末尾的/0也加上了,忽略大端小端,和内存中的模样相同。

现在我们需要存入一个新的key-value,而且恰好长度和memory中现有的首个key-value相同。执行完上一小节的函数,memory的值现在变成了这样:

/img/uploads/2014/08/1.jpg

其中只有luffy-op是我们需要插入的数据,后面的是memory中的“脏”数据。于是 为BDB异常纠结,在接收到这样一个批量操作的内存时,该如何正确的取出第一个,而不会将后面的数据错误的存入?

4.步步跟进

首先测试一下,BDB的确能够精明的躲过脏数据,而得到正确的存储结果,但是它是怎么做到的呢?其中必然有某些隐情! debug一步步跟进,终于经过层层调用,定位到一个“神奇”的函数:

/img/uploads/2014/08/UDMX2AD_1YJHSS@PY8VJ0.jpgbulk_ptr是刚刚被另一个“神奇”的函数初始化的指针,key还是我们熟悉的带有批量存储数据的key,tkey和data是临时Dbt类型数据,执行完这个函数之后,他们就会变成包含luffy-op的key-value值,存入到数据库中。

说这是一个“神奇”的函数,是因为在gdb中无法单步执行进入,为此郁闷不已,就像突然发现快追到手的暗恋多年的妹子,原来是一个汉子。不过经过斗争,加上暴力搜索,还是找到了它。化神奇为腐朽。才发现其实它是一个宏定义!下面是初始化bulk_ptr指针的宏定义:

#define	DB_MULTIPLE_INIT(pointer, dbt)					
(pointer = (u_int8_t *)(dbt)->data +				
(dbt)->ulen - sizeof(u_int32_t))

dbt就是熟悉的key,这个函数是使pointer指向我们所申请的memory的最后四个字节。似乎初见端倪。再来看看它是怎么用的:

#define	DB_MULTIPLE_KEY_NEXT(pointer, dbt, retkey, retklen, retdata, retdlen) 
do {								
    u_int32_t *__p = (u_int32_t *)(pointer);		
    if (*__p == (u_int32_t)-1) {				
        retdata = NULL;					
        retkey = NULL;					
        pointer = NULL;					
        break;						
    }							
    retkey = (u_int8_t *)(dbt)->data + *__p--;		
    retklen = *__p--;					
    retdata = (u_int8_t *)(dbt)->data + *__p--;		
    retdlen = *__p--;					
    pointer = __p;						
} while (0)

原来是将要存入的key-value值得长度放在了memory的最末端!怪不得可以正确的取出想要的数据。它将最末端的四位标记为-1,对于u_int类型,其实就是0xFFFFFFFF,这个数字足够大,不会和其它的数据混淆。当存入luffy-op的时候,就将最末端修改为这样:

/img/uploads/2014/08/11.jpg

哈哈,所要的数据都在这里了,从后往前看,一位代表偏移,一位代表字段长度,偏移第一位是0,后面的是前两个字段的和。

这些长度是在哪里不知不觉加上的呢?就在reserve函数中,它做了两件事,一个是把要插入的位置的指针初始化,一个是把数据的长度加在了后面。如果两头在中间相遇,就返回false,分配失败。根据上述程序,失败之后将已经存入的值写入数据库,然后跳出循环,重新build一个key,用的还是原来的memory,但是这时可以重头再来了!

5.总结

批量存取节省的并不是插入BDB数据库的时间,因为在内部,还是一条一条取出来用游标插进去,节省的是BDB内部复杂的函数调用,以及事务等校验的开销。空间换取时间的做法,桶大小选取尤为重要,但是在计算的时候,别忘了,在末端是存有长度信息的,所以别指望申请多大的空间就能存多大空间的数据,存入一个record需要占用record长度+16字节。还有坑爹的宏定义函数,在调用处展开,也是空间换取时间的做法,可见数据库系统对时间要求是比较高。但是很不利于调试…..