dazuiniu's blog

大嘴牛觉得有两家数据库值得关注，一家是Akiban公司，

主要提供的是对于数据库上做join的一种优化方式，公司在Boston，起家方式也就是一哥们想到了一个idea，然后开始搞，貌似是个印度人。

另外一家是RethinkDB公司：

这个说起来来头稍微大那么一点点，成立公司的老大是那个写defmacro的哥们，对于函数式编程语言应该有很深的造诣。成立的初衷是觉得在数据库界，随着SSD技术的出现，数据库迟早也要发生翻天覆地的变化，因为之前所有的数据库算法的考量都是基于内存快而磁盘很慢这个特点做出的，而SSD则不然，他将成为未来填补内存和磁盘的重要桥梁，甚至磁盘被完全替代也有可能。老大很有信心，而专门在 O’Reilly大会上讲“为什么我们要在2010年开一家数据库公司”，这确实有点匪夷所思，当今社会，大家似乎都对Web2.0的概念情有独钟，而对于底层技术比较冷淡。当然，现在的火热的云计算也算是对于体系架构的一种小小的颠覆。

没啥重点，随便写点东西。谢谢！

在上面的一篇文章中，大嘴牛讲到了山寨Tokyo Cabinet数据库的问题，这里，大嘴牛为了增加人品，放出源代码，现在只有四个文件，没有一个实例的用法，在以后会补上。源代码在此：

https://github.com/dazuiniu/kvdb

[1]. http://www.dazuiniu.com/blog/2010/08/21/hand-craft-your-own-tokyo-cabinet.html

项目需要使用一个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 的大小合适的时候，基本所有的操作都在内存中了。

很多计算本质上只是一个“添加”操作。数据库中的日志就只允许添加，一旦数据库中有任何的操作，就会生成新的日志，也就是说所有的数据库的历史操作都是保存在日志中，那么再反过来说就是数据库只是日志的一个子集（所有已完成的事务中对记录的最新更新的集合）。这个看法是大嘴牛第一次接触到的，提供了一种全新的看待问题的角度。

The database is a cache of a subset of the log (the subset that represents the latest updates to all the records by the transactions that happened to commit).

[1]. http://blogs.msdn.com/b/pathelland/archive/2007/06/14/accountants-don-t-use-erasers.aspx