dazuiniu's blog

多线程的开发与调试总是很困难的。因为他的不确定性，比如你的一个变量，在线程A的函数中可以使用，也可以同时在线程B的函数中被修改，由于两者的调用时机完全无法确定，因此增加了多线程的程序的维护与开发的难度。

大嘴牛采用了 active object 与 message passing 两种方式相结合的方式来从某种程度上缓解多线程编写的难度。

对于需要修改的类，可以封装成一个单独的线程，所有对于类下面数据的修改都通过消息方式进行传递，因此，其他线程想要进行修改，必须发送消息来进行。

问题还是存在的。比如你的读数据。如果你可以忍受读出脏的数据，那么没问题，这种模式比较合适你。否则还是乖乖的使用锁进行数据保护吧。

前面讲到了 TC 数据库的文件结构，这里大嘴牛又想到了一种方法，适用的场景是当 key 是一个64位的整数。那么最关键的是如何从一个 key 找到 value 所存放的位置，这里大嘴牛使用了一种类似于 Linux 中的页表机制。

所谓 Linux 页表机制，也就说对于一个 32位长的虚拟地址，我们会把他分成10，10，12三个部门，其中第一个10位用以寻址1024个页目录表，而第二个10位用以寻址另外的1024个页项。

那么在这里同样类似，我们可以把64位整数分成8个8位，每个8位用以寻址256个下个表的偏移，最后一个的表上的偏移用以说明 value 在数据文件中的位置。

对于上面的情况：

1. 对于读取操作而言，我们需要读取8次页表，然后读取真正的 value 值。
2. 对于写入操作而言，一种情况是 key 之前已经被寻址过，那么和读取操作一样，先读取8次页表，最后写入真正的value内容。而对于之前 key 没有被寻址过，那么就需要建立key的映射表，只有建立了这个映射表之后，才可以写入内容。
3. 对于删除操作而言，前面的操作类似与读取，但是对于一个具体的记录，我们会把其中的一个标志位置上，用以表明该记录已被删除。
4. 对于遍历操作，我们只需要不断读取数据文件，如果发现某个记录的删除标志位没有被置上，那么就把该记录读取出来。

最后的实测发现，和 Linux 的 page fault 所需要的代价比较大一样，这里的建立映射这个过程是一个比较慢的过程，但是当这个映射建立之后，实际的读取操作还是十分快的。

另外，这个方法只能对于数据不太的情况，可以想像，如果量很大，那么我们的这个 index 文件就会超过预期，64位的寻址可是可以达到 2^64 哦。

项目需要使用一个Key Value的数据库，于是便考虑使用 Tokyo Cabinet 这个鬼子开发的数据库，据说实测效果很不错。如果你不需要 TC 的多线程支持，你还可以在编译的时候指定 –withou-pthread 这样就不会对数据库加锁，当然也只能使用在单线程之中。

但是用在自己的项目中需要引入一个链接库，自己的代码不是特别的清晰，于是考虑自己来山寨一个类似的数据库，一个体现了程序员普遍存在的造轮子的性格，当然也算是锻炼一下编码能力吧，别拍我。

既然要山寨，那么首先要了解这个 TC 数据库大致是如何实现的。其实对于数据库而言，比较重要的就是你的文件格式是什么样子，基本上你的文件布局定了，你的数据结构也定了，整个数据库的架构也定了。TC 的数据库只有一个文件，有人说这不是废话吗，不是这样的，有时候为了实现的方便，我们可以使用两个文件来表示一个数据库，其中一个文件是 index 文件，而另外一个文件才是真正的 data 文件，使用这样方法的有 MySQL 的 myiasm 引擎，也有 git 的 pack 数据文件，既然是一个文件，你对于各个部分的合理布局就必须考虑周到，TC 的这个布局也还是比较自然的，基本上和 APUE 2nd 中的那个数据库结构类似，也就是其中：

1. 文件头部分
2. hash 桶部分
3. 空洞管理部分
4. 真正的记录存放部分

既然是自己山寨，自己考虑独特的使用场景，同时为了实现简单，在自己的数据库中不使用空洞管理部分，这样带来的后果是自己的数据库会不断增长，文件中的碎片会变多，但是在结束的时候可以重新开一个数据库，将原来的数据倒到新的数据库中，也算是一个解决方法，但这种方法只有当这个操作不是在性能关键部分的时候才可以使用。

需要注意的是对于在内存中的数据管理，我们只需要存放指针就可以了，但是对于一个文件而言，我们只能存放对于该文件的偏移地址。

对于 hash 出来的值是一致的情况，我们一般而言会把它挂到一个链表上，但是 TC 不是这样，TC 对于相同的 hash 值，会把他们挂到一个二叉树上，但是我们知道对于二叉树，他可能退化，为了防止这样情况的发生，TC 对于 key 进行第二次 hash （hash 的方法与第一次不同），而是利用这个新的 hash 值作为二叉树的 key，这样就会尽可能的较少了退化的概率，任何事情都不是绝对的，我们要妥协，要忍耐。

对于 TC 和大嘴牛的这个山寨数据库，mmap的使用也是必须的，因为对于文件一直做 seek 并读取其中一部门的数据实在是性能的第一大杀手，而通过内存映射文件，我们可以有效的减少 seek 的次数，加快了速度，后来的实测也的确证实了这点。

最后大嘴牛的实现大概全部加起来也就 500+ 行代码左右，性能还不错，对于自己使用已经可以了，因为对于大嘴牛而言，总共的数量也就在10万左右，不会很大，而当 mmap 的大小合适的时候，基本所有的操作都在内存中了。

C++ 0x 虽然还没有完全普及开来，但是对于尝鲜的同学会遇到一个问题，怎么编译具有这些新特性的程序呢？利用 G++ 的同学们可以在后面加上这个选项就可以了。

-std=c++0x

正好看到有文章介绍 rethinkdb 的产品使用的是 lock-free 的算法。文件见下面的连接[1]，其中对于这两个的名字解释如下：

In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls.

By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation. Wait-free algorithms have stronger guarantees than lock-free algorithms, and ensure a high thorughput without sacrificing latency of a particular transaction.

《The art of multiprocessor programming》书中说到：

A concurrent object implementation is wait-free if each method call finishes in a finite number of steps.  A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

大嘴牛个人的理解是这里的 lock-free 并不是说没有用于保护的锁的意思，而是指对于整个系统而言没有出现比如死锁的状况，而 wait-free 则表示根本不需要等待锁的时间。wait-free 比 lock-free 更加难实现，要求更加高，比如使用在嵌入式实时系统中等等。

[1]. http://www.rethinkdb.com/blog/2010/06/lock-free-vs-wait-free-concurrency/

画的不太好。