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函数中主要进行了以下工作：
- 如果以daemon模式运行，则调用ttdaemonize函数，建立可运行的子子进程，父进程和子进程都退出
- tcadbopen函数，根据数据库文件，为TCADB对象赋值，对于hash类型的db而言，会将数据库文件mmap到共享内存中
- 调用ttservaddtimedhandler函数，建立一个tserv的timer对象，其handler是do_slave
- 如果有外部脚本相关的，则再调用ttservaddtimedhandler函数，建立N个timer对象，其handler是do_extpc
- 调用ttservsettaskhandler函数，将tserv的do_task赋值为do_task函数
- 调用ttservsettermhandler函数，将tserv的do_term赋值为do_term函数，处理退出
- do{ ttservstart(); }while(g_restart); 之类的g_restart值可以有signal改变，从而使ttserver可以再次执行ttservstart，以达到重启、reload的效果
- 在ttservstart函数中，是真正的业务逻辑
以下简单看看ttservstart函数：
- 根据host和port，建立socket，可以是unix原始套接口，也可以是TCP套接口
- 新建timer个数个线程，等待执行timer->do_timer函数
- 新建thnum个worker线程，以空的reqs初始化，等待执行timer->do_task函数
- epoll_wait：
- 如果是请求建立连接，则accept连接，并将accept的socket端口加入到epoll的监听队列里
- 如果是其他请求，则请求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个问题：
- 复制数据库文件，与tcrmgr copy的区别；后者对锁的使用情况
- B+tree数据文件格式，为什么异常退出会导致数据丢失？
- 尝试用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里的数据难道不存在于数据文件中吗？
