tokyo cabinet与tyrant一起,组成了一个可用的NoSQL数据库,cabinet是lib,tyrant是server。其性能和应用性毋庸置疑,希望可以学习,同时也对其稳定性持怀疑态度,希望可以看看是我用的不对,还是其源码有可改进的地方。

从tyrant/ttserver.c的main函数入手:

main(){
    ……
    g_serv = ttservnew();
    int rv = proc(dbname, host, port, thnum, tout, dmn, pidpath, kl, logpath,
                  ulogpath, ulim, uas, sid, mhost, mport, rtspath, ropts,
                  skelpath, mulnum, extpath, extpcs, mask);
    ttservdel(g_serv);
    if(extpcs) tclistdel(extpcs);
    return rv;
  }
}

省略的部分是命令行参数处理,ttservnew函数对TTSERV进行初始化,其中初始化了4个锁:
ttservnew(){
    ……
    if(pthread_mutex_init(&serv->qmtx, NULL) != 0) tcmyfatal("pthread_mutex_init failed");
    if(pthread_cond_init(&serv->qcnd, NULL) != 0) tcmyfatal("pthread_cond_init failed");
    if(pthread_mutex_init(&serv->tmtx, NULL) != 0) tcmyfatal("pthread_mutex_init failed");
    if(pthread_cond_init(&serv->tcnd, NULL) != 0) tcmyfatal("pthread_cond_init failed");
    ……
}

typedef struct _TTSERV {
    ……
    pthread_mutex_t qmtx;                  /* mutex for the queue */
    pthread_cond_t qcnd;                   /* condition variable for the queue */
    pthread_mutex_t tmtx;                  /* mutex for the timer */
    pthread_cond_t tcnd;                   /* condition variable for the timer */
    ……
}

这里就牵涉到两个重要的概念,timer线程和worker线程,稍候会介绍。qmtx和qcnd主要是供主线程和worker线程使用,tmtx和tcnd主要供主线程和timer线程使用。

可以看出,真正的处理逻辑是在proc函数里。这个函数里进行了大量的稳定、log、容错等处理,先都忽略(但是这些才保证了一份好代码的存在!)。

proc函数中主要进行了以下工作:

  1. 如果以daemon模式运行,则调用ttdaemonize函数,建立可运行的子子进程,父进程和子进程都退出
  2. tcadbopen函数,根据数据库文件,为TCADB对象赋值,对于hash类型的db而言,会将数据库文件mmap到共享内存中
  3. 调用ttservaddtimedhandler函数,建立一个tserv的timer对象,其handler是do_slave
  4. 如果有外部脚本相关的,则再调用ttservaddtimedhandler函数,建立N个timer对象,其handler是do_extpc
  5. 调用ttservsettaskhandler函数,将tserv的do_task赋值为do_task函数
  6. 调用ttservsettermhandler函数,将tserv的do_term赋值为do_term函数,处理退出
  7. do{ ttservstart(); }while(g_restart); 之类的g_restart值可以有signal改变,从而使ttserver可以再次执行ttservstart,以达到重启、reload的效果
  8. 在ttservstart函数中,是真正的业务逻辑

以下简单看看ttservstart函数:

  1. 根据host和port,建立socket,可以是unix原始套接口,也可以是TCP套接口
  2. 新建timer个数个线程,等待执行timer->do_timer函数
  3. 新建thnum个worker线程,以空的reqs初始化,等待执行timer->do_task函数
  4. epoll_wait:
    1. 如果是请求建立连接,则accept连接,并将accept的socket端口加入到epoll的监听队列里
    2. 如果是其他请求,则请求qmtx锁,将该端口push到serv->queue里,释放qmtx锁,并发送qcnd信号,触发worker线程

worker线程的主体就是do_task函数,其读取socket中的数据,如果以magic word打头,则是二进制格式的命令;否则就是memcached兼容的命令格式。根据请求内容,再分别调用如do_put、do_get等函数进行处理。

以do_get函数为例,主要是调用tcadbget函数,读取到内容,再通过socket返回给客户端。这里的tcadbget函数,会根据数据库的类型,调用其get函数进行读取,比如hash database,就使用tchdbget方法。tchdbget中,首先请求HDBLOCKMETHOD 的read lock(允许其他读,但是不允许写),对整个db加锁,然后调用tchdbbidx函数计算出key对应在hash数组中的位置,和二次hash的key(为了解决hash碰撞,对于第一次hash key相同的元素,使用tree再进行存储)。调用tchdbgetimpl函数,进行真正的获取数据。

tchdbgetimpl函数中:由于hash database使用了on-memory hash database作为缓存,所以,如果cache不为空,则先会执行tcmdbget在cache中查找,如果找到则返回,否则继续在真正的hash database里查找。首先找到bucket的偏移位置,对于hash database来说,一部分数据会被map到共享内存,如果bucket属于这部分数据,则从map中读取;否则从数据文件读取(可能存在bucket的一部分数据在map,另一部分在数据文件的情况)。

bucket的header数据结构为:

magic word | hash | left child off | right child off | padding size | size of key | size of value |

buckey里的数据是以树存储的,用上面计算出的二次hash的key,与bucket key比较,若二次key较小,则向左子树找;若较大则向右子树找;否则相等时,比较关键字,若相等,则找到结果,返回;如果虽然二次hash的值相等,但是比较关键字不等,则需要解决二次 hash的碰撞。

二次hash碰撞的解决方法,是沿着当前节点的左子树或者右子树下行直至找到二次hash值等、关键字也等的节点,或者找不到匹配的节点,则返回失败。

———————————- 小分割 ——————————————

2012-1-19

今天想解决3个问题:

  1. 复制数据库文件,与tcrmgr copy的区别;后者对锁的使用情况
  2. B+tree数据文件格式,为什么异常退出会导致数据丢失?
  3. 尝试用c代码读取ulog和数据文件的内容
tcrmgr copy的奥秘

tcrmgr copy的响应函数是proccopy,首先tcrdbnew数据库,并init了一个mutex锁,继而调用tcrdbcopy函数,先请求这个mutex锁,再进行具体的copy操作。

这里请求mutex锁的tcrdblockmethod函数,在多处被调用,比如get、put等等。这里是简单的CLI模式,每次数据库都是new的,mutex锁也是新建的,但是可以猜想,在多线程模式下,线程间的读写操作都是互斥的。(这里存疑,为什么用互斥锁,而非条件变量呢?)

tcrdbcopyimpl组装socket的copy包,通过tcrdbsend发送给ttserver。并通过ttsockgetc获取返回值。

可以看出,copy的奥秘不在tcrmgr这里,而是在ttserver怎样处理copy请求里。

ttserver.c的do_copy函数具体处理copy请求,针对B+tree,其实际处理函数为tcbdbcopy。

首先对数据库加写锁,排除一切的读写操作,从cache里读取叶节点和非叶节点,分别存储到lids和nids里。解锁。由于cache里的数据还未写入到数据文件里,所以针对每个节点,调用对应的save函数,写入到数据文件中(写入每个节点的前后加写锁、解锁)。

调用tcbdbtranbegin启动事务,加读锁,调用tchdbcopy函数(据说B+tree的底层存储其实是hash格式)将数据写到目的文件中,解锁。

实际执行复制操作的是tchdbcopyimpl,这里封装了两种操作,一种是直接调用tccopyfile进行复制,另一种是当目的文件以@开头,则执行命令。仅关注前者,很简单,就是将数据库文件中的内容读取出来,写入到目标文件。

那么tcrmgr copy和直接copy有哪些区别呢?

  • tcrmgr copy会先将cache中的数据写回到文件中;而直接copy不会,所以cache中的数据就丢失了
  • tcrmgr copy写备份文件的时候,会加读锁,排斥写,保证备份文件的数据格式是正确的;而直接copy时没有锁,如果正好遇到cache中的数据同步到数据库文件,则备份文件的格式可能是损坏的
B+tree数据库异常情况分析

从上面的copy过程,猜想,异常退出导致文件格式损坏的原因可能有:

  • 数据写在cache里,没有存入文件,cache里的新数据丢失
  • 存入文件过程中,异常退出,导致文件格式损坏,可能很多数据甚至整个文件都会丢失

具体需要看tcbdbputimpl函数。在该函数中,首先从history里查找key对应的叶节点的pid,如果找不到则从根节点开始二分查找,直至找到或者新建了一个leaf节点的pid(细节没看)。然后将新内容作为rec写入pid对应的leaf位置。之后如果需要,会对整个树进行调整

如果该节点所在的recs数目超过了启动ttserver时的预设值lmemb,或者该节点的的size超过了lsmax,则调整。调整的具体过程忽略,可以参考算法中的B+ tree部分。

否则,如果该节点的recs数目<1,则说明put失败,需要调用tcbdbleafkill函数切断该leaf节点与树的联系(疑问,这个leaf里应该还有其他旧数据,岂不是也丢失了?)。

如果不在事务里,则将数据写入cache。如果页节点的cache数目大于设定值lcnum,则需要将叶节点的cache内容写入到数据文件(又调用了hash的put函数,不清楚那边是否也有cache缓存),并清除叶节点cache的内容。同样处理非叶节点。那么,如果非正常退出,cache中的数据就有可能会丢失。

在将数据写入数据文件的过程中,注意到其rbuf的大小是BDBPAGEBUFSIZ,即32768,这就意味着,一个leaf的最大字节数是32768(数据部分应该是比这个要小)。

留个问题,cache里的数据难道不存在于数据文件中吗?

Leave a Reply