[转]Kyoto Cabinet 使用及原理

小咪咪 2022-08-22 12:26 322阅读 0赞

### Kyoto Cabinet 基本规格书   ###

如果你知道 Tokyo Cabinet ，那么就应该知道 Kyoto Cabinet，因为他们都是同一个作者（平林幹雄）开发出来的 Key-Value 数据库。

**Kyoto Cabinet**：a straightforward implementation of DBM，主页： [http://fallabs.com/kyotocabinet/][http_fallabs.com_kyotocabinet] ，演示文稿： [http://www.slideshare.net/estraier/kyotoproducts-5886452][http_www.slideshare.net_estraier_kyotoproducts-5886452] 。

**Tokyo Cabinet**：a modern implementation of DBM，主页：  [http://fallabs.com/tokyocabinet/][http_fallabs.com_tokyocabinet]

以下Tokyo Cabinet简称为TC， Kyoto Cabinet简称为KC，本文主要对KC做介绍。

KC是TC的后继者或兄弟项目，因为KC在各方面都超过了，所以作者在TC的首页上的开头向所有人推荐使用KC（我也是这个推荐才开始关注KC的）。TC为C实现，为了更好的可维护性，KC采用C++实现。

以下内容的英文原文来自： [http://fallabs.com/kyotocabinet/spex.html][http_fallabs.com_kyotocabinet_spex.html]

**一、介绍**

KC是一个数据库管理的 lib。数据库是一个简单的包含记录的数据文件，每个记录是一个键值对（key/value），key和value都是变长的字节序列。key和value既可以是二进制的，也可以是文本字符串。数据库中的key必须唯一。数据库既没有表的概念，也不存在数据类型。所有的记录被组织为hash表或B+树。

在数据库中，可以储存key-value记录，也可以根据key来获取和删除记录。还可以遍历访问所有的key。这些方法类似于UNIX标准中的DBM库（及后来的NDBM和GDBM）。因为KC的高性能，可以作为DBM的替代品。

**Hash 数据库** 的每个操作的时间复杂度是 O(1)，因此理论上，性能是常量而与数据库的规模无关。在实践中，性能由内存或存储设备的速度决定。如果数据库的大小小于内存大小，性能表现为内存的速度，比STL中的std::map要快。当然数据库大小可以大于内存大小，最大上限是8EB（1024×1024×1024GB）。即使在这样的情况下，每个操作也只需要一两个存储设备的seek操作。

**B+ tree 数据库**的每个操作的时间复杂度是 O(log N)。因此理论上，性能是数据库规模的对数。尽管B+ tree 数据库的随机访问性能要慢于 hash数据库，但B+ tree数据库支持对 key 顺序的连续访问，这可以实现对字符串的前向匹配查找和整数的范围查找。连续访问的性能远快于随机访问。

API是基于面向对象设计的，hash数据库和B+ tree数据库都有从同一个超类继承而来的同样的方法。除了他们，还有7种数据库也继承了同样的超类。 **prototype hash** 数据库采用标准容器 std::unordered\_map 实现， **prototype tree** 数据库采用标准容器 std::map 实现， **stash**数据库是采用naive hash map的原始实现来节省内存， **cache hash** 数据库是采用 LRU删除算法的双向链接 hash map 原始实现。 **cache tree** 数据库是基于cache hash 数据库并提供B+ tree的机制。 **directory hash** 数据库是采用文件系统的目录机制实现，每个记录存储为一个目录下的文件。 **directory tree** 数据库基于directory hash数据库并提供B+ tree的机制。所有的数据库都有相关的事物（transaction）和游标（cursor）的实用方法。软件也包含了命令行接口的程序。

KC的运行速度非常快。例如，保存一百万记录到hash数据库中只需要0.9秒，保存到B+ tree数据库只需要1.1秒。而且数据库本身还非常小。例如，hash数据库的每个记录头只有16字节，B+ tree数据库是4字节。更进一步，KC的伸缩性非常大，数据库大小可以增长到8EB（9.22e18 bytes）。

KC是C++语言编写的，并提供C++、C、Java、Python、Ruby、Perl 和 Lua 的API。KC可以用在所有符合 C++03标准并带TR1库扩展的平台。KC是GNU General Public License的自由软件。FOSS License例外也提供用来适应其它免费和开源的licenses。另一方面也提供商业license。如果你在专有软件中使用KC，那么你需要商业license。

**二、特性**

下面描述KC的特性。

**起源**

最初的DBM是由 Kenneth Thompson 开发，作为最初AT&T UNIX的一部分。后来，很多跟随者开发了和 DBM 类似的NDBM、SDBM、GDBM、TDB 和 BerkeleyDB。在2003年，出于性能原因，我（作者）开发了QDBM代替GDBM。

在2007年，TC出于以下目的被开发来作为QDBM的后继者。这些目标都实现了，TC可以替代传统的DBM产品。

*  改进的**空间效率**：更小的数据库文件
 *  改进的**时间效率**：更快的处理速度
 *  改进的**并行性**：多线程环境下的高性能
 *  改进的**可用性**：简单的API
 *  改进的**健壮性**：即使在灾难情况下数据库文件也不会损坏
 *  支持**64位架构**：巨大的内存空间和数据库文件可用

在2009年，KC作为另一个QDBM后继者被开发出来。和兄弟产品（TC）相比较，追加了下面这些优势。然而，至少在单线程操作环境下，TC的性能要高于KC。

*  改进的**空间效率**：更小的数据库文件
 *  改进的**并行性**：多线程环境下的高性能
 *  改进的**可移植性**：对底层的抽象来支持 非POSIX系统
 *  改进的**可用性**：简单的API，面向对象的设计
 *  改进的**健壮性**：即使在灾难情况下数据库文件也不会损坏

我（作者）将同时维护TC和KC，因为他们的价值不同。

**高效的Hash数据库实现**

KC使用hash算法获取记录。如果 bucket array 拥有足够的元素数量，那么获取的时间复杂度是O(1)。这样获取记录的时间是常量，而和数据库规模无关。存储和删除记录也一样。hash值的碰撞是通过分离链接（separate chaining）管理的。每个链（chain）的数据结构是二分查找树。即使 bucket array 极度缺乏元素，获取的时间复杂度也只是O(log n)。

KC的高性能获取是通过将整个 bucket array 加载到内存中。如果 bucket array 在内存中，那么访问目标记录的区域可能仅需要一组如 lseek、read、write这样的文件操作即可。如果 bucket array 保存在文件中，不会使用 read 调用读到内存中而是通过 mmap 调用直接映射到内存中。这样，连接到数据库的准备时间非常短，二个或更多的进程能够共享同样的内存映射。

在哈希表中使用的哈希函数是 MurMurHash 2.0 。如果 bucket array 的元素数量为数据库记录数的一半，尽管取决于输入的特性，哈希值碰撞的概率大概是55.3%（一样的话是35.5%，二倍的话是20.4%，4倍是11.0%，8倍是5.7%）。如果是这样，获取一个记录大概需要2个或更少的一组文件操作。如果作为一个性能指标，为了处理有一百万记录的数据库，需要一个拥有一半元素数量的 bucket array 。每个元素是6字节。这样只需要用3M内存，就可以处理一个拥有一百万记录的数据库。

如果用一个更大长度的值覆盖记录现有的值，那么必须移动区域到文件的另一个位置。因为这个操作的时间复杂度取决于一个记录的区域大小，所以连续地扩展值是低效的。然而，KC通过对齐（alignment）处理这个问题。如果增加的数据可以放置在记录尾部的填充区域（padding region），就不必移动记录的区域了。

一般而言，在连续更新的同时，可用区域会出现碎片，并且数据库的大小会快速增长。KC通过空闲块池（free block pool）和自动的碎片整理机制处理这个问题。如果一个记录被删除或被移到另一个位置，那个区域将被作为一个空闲块处理。空闲块池管理着空闲块并重用最合适的区域给一个新的记录。自动碎片整理会分别移动记录和空闲块。连续的空闲块会被合并成一个。

**有用的B+ Tree数据库**

尽管B+ tree数据库比hash数据库慢，但它的特点在于顺序访问每个记录。顺序可以由用户指定。B+ tree数据库中的记录被存储和安排到逻辑页中（logical pages）。被组织在B树这种多路平衡树中的稀疏索引，用来维护每个页。这样获取等操作的时间复杂度是O(log n)。通过游标（Cursor）可以按顺序访问每个记录。游标可以跳到指定key的位置，并能够从当前位置向前或向后移动。因为每个页被组织为双向链表，所以游标步进的时间复杂度是O(1)。

B+ tree数据库的实现是基于上面的hash数据库。因为B+ tree数据库的每个页是作为hash数据库中的一个记录保存的，所以B+ tree数据库继承了hash数据库的存储管理效率。因为每个记录的头更小并且每个页的对齐是根据这个页的大小来调整的，大部分情况下，数据库文件大小比对应的hash数据库小一半。

虽然许多页操作需要更新B+ tree数据库，但KC通过页缓存（page cache）加快了这一过程并减少了文件操作。页缓存是用双层的 LRU 列表实现的，这使得频繁访问的页被缓存在“hot”列表中，最近访问的页被缓存在“warm”LRU列表中。如果页缓存能够有效地工作并且整个稀疏索引被缓存在内存中，那么获取一个记录可能只需要一个或更少的一组文件操作。

B+ tree数据库的每个页可以被压缩存储。默认的压缩方法是ZLIB的"Deflate"方法。因为一个页中的记录有相似的模式，由于Lempel-Ziv算法预计会有较高的压缩率。对于处理文本数据的情况，数据库的大小可能被减小到50%或更小。如果数据库的规模很大并且磁盘IO成为瓶颈，使用压缩方法会使处理速度有巨大地提高。此外，可以指定外部的LZO和LZMA压缩算法。

**实用的功能**

KC具有事物机制特征。可以在一个事物的开始和结束之间一次性提交一组操作，或者终止事物并回滚到事物之前的状态。支持两种隔离级别："serializable" 和 "read uncommitted"。持久性是通过预写日志（write ahead logging）和影式分页（shadow paging）保证的。

还提供自动事物和自动恢复的机制。如果在打开数据库的时候指定了自动事物选项，那么每一个更新操作都受隐式提交事务的保护。因此不需要显式的事物操作就可以保证持久性。事务外的数据库崩溃后，自动恢复机制开始工作。在打开数据库的时候如果发现数据库不一致，所有的区域会被按照“fsck”的方式扫描，并且隐式地将完好的记录重建。

KC提供两种模式连接到数据库：“读”和“写”。读只能获取记录但不能保存和删除。写可以执行所有方法。通过文件锁定方式连接数据库时，可以排斥多进程的控制。当一个写连接到一个数据库后，既不允许读也不允许写连接。当一个读连接到数据库后，其它的读可以连接，但是写不能。根据这种机制，保证了多任务环境中同时连接的数据一致性。

API函数是可重入的，可以用在多线程环境中。不同的数据库对象可以完全并行地操作。对于同时操作同一个数据库对象，读写锁被用来排斥控制。就是说，一个写线程正在操作一个对象，其它的读线程和写线程将被阻塞。锁定粒度取决于数据结构。hash数据库使用记录锁定，而B+ tree数据库使用页锁定。

为了改进性能和并发性，KC使用内建于主流CPU的原子操作，如原子递增和CAS(compare-and-swap)。如POSIX线程包提供的原生环境的锁原语被使用CAS的原语所替换。

**简单而灵活的接口**

KC通过基于面向对象设计的简单API。数据库的每个操作被封装发布为易懂的方法，如open、close、set、remove、get 等等。hash数据库和B+ tree数据库的类都衍生自公共的抽象类，它定义了接口。很容易将应用从一个数据库移植到另一个。此外，多态数据库API在运行时被赋予一个数据库。

KC支持 visitor 模式。你可以通过回调函数的方式定义任意的数据库操作。visitor类封装了回调函数和他们的状态数据。database类有个 accept 方法，可以接受一个visitor类的实例并用一个记录数据为参数调用它的函数。回调函数的返回值反映了一个记录的新状态。

另外，提供了许多有用的工具方法，如前缀查询（prefix search）、正则查询（regex search）、日志（logging）、热备份（hot backup）、伪快照（pseudo-snapshot） 和 合并（merging）。还提供了一个MapReduce框架。尽管它不是分布式和并发的，对于较少CPU负载和较少内存使用的聚合计算还是有用的。

给C++提供的核心API的同时，绑定了其它语言，如C、Java、Python、Ruby、Perl 和 Lua 。每个API也提供了相关的命令行接口。他们对于原型、测试和调试很有用。

**三、安装**

支持Linux、FreeBSD、Solaris、Mac OS X、Windows等，需要 gcc 4.2 和 ZLIB库。具体安装说明详见： [http://fallabs.com/kyotocabinet/spex.html\#installation][http_fallabs.com_kyotocabinet_spex.html_installation]

**四、向导**

稍后考虑翻译，请先看原文： [http://fallabs.com/kyotocabinet/spex.html\#tutorial][http_fallabs.com_kyotocabinet_spex.html_tutorial]

**五、提示和技巧**

这一节描述KC的提示和技巧。

调优 Stash 数据库

stash数据库（StashDB）是省内存的内存数据库。可以使用如下优化方法。

*  **tune\_buckets**：设置hash数据库的 bucket 数量

默认的bucket数量大约是1百万。如果你想存更多的记录，调用 **tune\_buckets**设置bucket数量。建议的bucket数量的比率是和记录总数量相同，可以是从80%到400% 。如果比率低于100%，因为碰撞链是线性链接表，所以时间效率会快速下降。

调优 Cache Hash 数据库

cache hash数据库（CacheDB）是一个带LRU删除特性的内存数据库。 可以使用如下优化方法。

*  **tune\_options**：设置可选特性（optional features）
 *  **tune\_buckets**：设置hash数据库的 bucket 数量
 *  **tune\_compressor**：设置数据压缩方法
 *  **cap\_count**：设置记录数的容量
 *  **cap\_size**：设置内存使用的容量

**tune\_options **特性以牺牲时间效率为代价来减少内存的使用。如果指定为 CacheDB::TCOMPRESS，每个记录的key和value在存储到文件时会被隐式压缩处理。如果value大于1KB或更多，压缩是很有效的。

默认的 bucket 数量是大约1百万。如果你想存储更多的记录，调整  **tune\_buckets ** 来设置bucket数量。建议bucket数量的比率是和记录数量一样，可以是记录数量的50%到400% 。如果这个比率小于100%，时间效率会逐渐下降，因为碰撞链是二分查找树。

**CacheDB::TCOMPRESS **选项的默认压缩算法是由ZLIB 实现的 "Deflate"算法。如果你想用别算法，调用  **tune\_compressor ** 来设置一个压缩与解压的函数是实现。

默认cache hash数据库在内存中维护所有的记录，并且没有记录会过期。如果想让老的记录过期来保持内存使用为常量，调用  **cap\_count **和/或** ** **cap\_size** 来限制容量。

如果你想缓存一千万记录，并且保持内存使用小于8GB，建议按下面示例这样设置。

db.tune_buckets(10LL * 1000 * 1000); db.cap_count(10LL * 1000 * 1000); db.cap_size(8LL << 30); db.open(...);

所有的调优方法必须在数据库打开前设置。

**调优 Cache Tree 数据库**

cache tree数据库（GrassDB）是B+ tree的内存数据库。因为B+ tree中的每个node被序列化为一个page buffer，并被作为cache hash数据库中的一个记录看待，所以cache hash数据库中的所有配置项（除了容量限制外）都可以用在cache tree数据库中。此外，还有下面这些优化方法。

*  **tune\_page**：设置每个页大小
 *  **tune\_page\_cache**：设置页缓存（page cache）容量大小
 *  **tune\_comparator**：设置记录比较器

通过tune\_page 调整的页大小，大部分情况下不用修改。默认是8192，这是主流环境中典型页大小的两倍。如果每个节点的大小超过了这个值，节点被分为两个。

页缓存的默认大小是64MB。如果你想减少内存使用，调整  **tune\_page\_cache **可以把大部分的页转换为平的字节数组（flat byte arrays），这是为了改进空间效率做的序列化或压缩。

默认的记录比较器是词汇顺序（lexical ordering）函数。这样B+ tree数据库中的记录按照key的词汇顺序放置。如果你想使用其它顺序，调整  **tune\_comparator **来设置一个实现排序功能的函数。

如果你想缓存一千万记录，并让内存使用尽可能小， 建议按下面示例这样设置。

db.tune_options(GrassDB::TCCOMPESS); db.tune_buckets(500LL * 1000); db.tune_page(32768); db.tune_page_cache(1LL << 20); db.open(...);

所有的调优方法必须在数据库打开前设置。

调优 File Hash 数据库

file hash数据库（HashDB）是哈希表的文件数据库。提供下面这些调整参数设置。

*  **tune\_alignment**：设置记录的对齐幂数
 *  **tune\_fbp**：设置空闲块池的容量幂数
 *  **tune\_options**：设置可选特性
 *  **tune\_buckets**：设置哈希表的bucket数量
 *  **tune\_map**：设置内部内存映射区域的大小
 *  **tune\_defrag**：设置自动碎片整理的单位步数
 *  **tune\_compressor**：设置数据压缩器

默认对其值幂数是3，就是说每个记录的地址被分配为8个字节(1<<3)的倍数。如果你确信数据库被创建之后很少更新，可以设置 **tune\_alignment**为0，这样对齐就是1个字节(1<<0)。如果每个记录的典型大小预期超过1KB，把对齐调到8或更大。

大部分情况下空闲块池的大小 **tune\_fbp**不用调整。参数默认是10，这就是说空闲块池的大小是1024（1<<10）。

可选特性 **tune\_options**可以减少数据库文件大小，以损失伸缩性或时间效率为代价。如果设置为 HashDB::TSMALL ，记录的地址宽度将从6字节减小到4字节。这样导致每个记录占用（footprint）从16字节减小到12字节。然而，它限制了数据库文件的最大大小为16GB（2GB乘以对齐）。如果设置为 HashDB::TLINEAR ，哈希表的碰撞链的数据结构将从二叉树改为线性链表。这种情况下，每个记录的占用从16字节减少到10字节，然而时间效率变得与hash bucket的数量敏感了。如果设置为 HashDB::TCOMPRESS ，每个记录在存储到文件时被隐式压缩。如果value大于1KB或更多，压缩会很有效。

默认bucket数量是大约1百万。 如果你想存储更多的记录，调整  **tune\_buckets **来设置bucket数量。建议的bucket数量的比率是记录数量的2倍，也可以是100%到400%。如果比率低于100%，时间效率会逐渐降低。 如果你设置了bucket数量，建议设置 **HashDB::TLINEAR **选项来改进时间和空间效率。

默认内部内存映射区域的大小是64MB。如果数据库大小预期大于64MB，通过 **tune\_map**设置映射的大小大于预期的数据库大小。尽管机器的内存容量限制了映射的大小，但是增加映射大小可以有效改进性能。

默认自动碎片整理是禁用的。如果数据库中现存的记录被修改（删除或者用不同的大小修改），可用区域的碎片会逐渐发生。这种情况下，设置 tune\_defrag 来启用自动碎片整理并设置 单位步数（unit step number）。建议的单位步数是8，意味着每8个更新操作执行一组碎片整理操作。更大的数，空间效率会变高但时间效率会变低。

HashDB::TCOMPRESS 选项默认压缩算法是由ZLIB 实现的 "Deflate"算法。如果你想用别算法，调用 **tune\_compressor **来设置一个压缩与解压的函数是实现。

如果你想存储1万个记录，并尽可能减小数据库大小， 建议按下面示例这样设置。

db.tune_alignment(0); db.tune_options(HashDB::TSMALL | HashDB::TLINEAR); db.tune_buckets(10LL * 1000); db.tune_defrag(8); db.open(...);

如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率， 建议按下面示例这样设置。

db.tune_options(HashDB::TLINEAR); db.tune_buckets(20LL * 1000 * 1000 * 1000); db.tune_map(300LL << 30); db.open(...);

所有的调优方法必须在数据库打开前设置。因为 tune\_alignment, tune\_fbp, tune\_options, 和 tune\_buckets设置项是作为数据库的元数据存储的，这些方法必须在数据库被创建的前调用，并且之后不能修改。因为其它的调优参数不是保存在数据库中的，所以他们可以在每次打开数据库时设置。

调优 File Tree 数据库

file tree数据库（TreeDB）是B+ tree的文件数据库。 因为B+ tree中的每个node被序列化为一个page buffer，并被存储为 file hash数据库中的一个记录，所以file hash数据库中的所有配置项都可以用在file tree数据库中。此外，还有下面这些优化方法。

*  **tune\_page**：设置每个页大小
 *  **tune\_page\_cache**：设置页缓存（page cache）容量大小
 *  **tune\_comparator**：设置记录比较器

通过**tune\_page **调整的页大小，大部分情况下不用修改。默认是8192，这是主流环境中典型页大小的两倍。如果每个节点的大小超过了这个值，节点被分为两个。

页缓存的默认大小是64MB。如果你的机器有大量的内存，设置  **tune\_page\_cache **加载所有的节点到页缓存中。如果内存不富裕，最好保持默认的页缓存大小，并通过  **tune\_map **来对内部内存映射区域分配内存。

file tree数据库的默认对齐是256（1<<8）。默认的bucket数量大概是65536。其它的默认参数和file hash数据库一样。注意bucket的数量应该按照页的数量计算。建议 bucket数量的比率大约是记录数量的10% 。如果压缩选项被指定，每个页的所有记录被立刻压缩。因此，压缩对于 file tree数据库更有效，而不是file hash数据库。

如果你想存储1万个记录，并尽可能减小数据库大小， 建议按下面示例这样设置。

db.tune_options(TreeDB::TLINEAR | TreeDB::TCCOMPESS); db.tune_buckets(1LL * 1000); db.tune_defrag(8); db.tune_page(32768); db.open(...);

如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率，建议按下面示例这样设置。

db.tune_options(TreeDB::TLINEAR); db.tune_buckets(1LL * 1000 * 1000 * 1000); db.tune_map(300LL << 30); db.tune_page_cache(8LL << 30); db.open(...);

所有的调优方法必须在数据库打开前设置。因为  **tune\_page **设置项是作为数据库的元数据存储的，这些方法必须在数据库被创建的前调用，并且之后不能修改。因为其它的调优参数不是保存在数据库中的，所以他们可以在每次打开数据库时设置。

调优 Directory Hash 数据库

directory hash 数据库（DirDB）是由文件系统的目录机制驱动的，每个记录对应于目录中的一个文件。 提供下面这些调整参数设置。

*  **tune\_options**：设置可选特性

可选特性**tune\_options**可以减少数据库文件大小 ，以损失伸缩性或时间效率为代价。如果设置为 DirDB::TCOMPRESS ， 每个记录的key和value在存储到文件时会被隐式压缩处理。如果value大于1KB或更多，压缩是很有效的。

directory hash 数据库的性能严重依赖于文件系统的实现和设置。像EXT2这样的文件系统并不善于在一个目录中存储很多文件。但是这种情况下，其它文件系统如 EXT3 和 ReiserFS 是相对有效的。一般而言，具有B tree特性的文件系统及其变体比线形搜索算法更适合。

所有的调优方法必须在数据库打开前设置。 因为  **tune\_options **设置项是作为数据库的元数据存储的，这些方法必须在数据库被创建的前调用，并且之后不能修改。

调优 Directory Tree  数据库

directory tree 数据库（ForestDB）是B+ tree的目录数据库。正如 file tree 数据库是基于 file hash 数据库一样， directory tree 数据库是基于  directory hash 数据库。 所以  directory hash  数据库中的所有配置项都可以用在  directory tree  数据库中。其它调优方法与 file tree 数据库相同。

directory tree 数据库的性能特征类似于  directory hash 数据库。然而，因为记录被组织在页中，所以在许多情况下，I/O操作的频率要少些、性能更好些。

选择合适的数据库

为了针对你的应用选择合适的数据库，清晰的需求规格书非常重要。如果不需要记录持久保存，建议使用内存数据库。有 prototype hash数据库（ProtoHashDB），prototype tree 数据库（ProtoTreeDB），stash 数据库（StashDB），cache hash数据库（CacheDB），和cache tree数据库（GrassDB）。如果对你应用逻辑而言，key的顺序非常重要，那么cache tree数据库比较合适。如果不是，stash数据库比较合适。cache tree数据库的内存占用要小于其它的。cache hash数据库能够隐式删除老的记录并保持内存占用为常量。prototype 数据库在少数情况下有用。

*  时间效率：CacheDB > StashDB > ProtoHashDB > ProtoTreeDB > GrassDB
 *  空间效率：GrassDB > StashDB > CacheDB > ProtoHashDB > ProtoTreeDB

如果你的应用需要持久化保存记录，建议使用持久数据库。有 file hash 数据库（HashDB），file tree 数据库（TreeDB）， directory hash 数据库（DirDB）和  directory tree 数据库（ForestDB）。 如果对你应用逻辑而言，key的顺序非常重要，那么  file tree 数据库比较合适。如果不是，  file hash 数据库比较合适。在大部分情况下，  file hash 数据库的性能和并发性要好于其它的。如果每个记录的大小很大， directory hash 数据库比较合适。

包括 KC 和 TC 在内的大部分DBM实现是对存储小记录而优化的。既然如此，如果你想处理非常大的记录，直接使用文件系统是更好的解决方案，而不是DBM。如果你存储和获取大记录，那么 read 和 write 系统调用的处理时间是主要的，而不是 open 和 lseek 系统调用。尽管典型的DBM会减小每个记录的定位时间的工作量，但是他们会增加每个记录数据 读写 的工作量。如果你处理大记录但不想直接使用文件系统，那么使用  directory hash 数据库。它仅仅是对文件系统的目录机制的包装。如果你想按照key的顺序处理大记录，应该使用  directory tree 数据库。   directory tree 数据库是可扩展性的最后武器。

*  时间效率：HashDB > TreeDB > DirDB > ForestDB
 *  空间效率：TreeDB > HashDB > ForestDB > DirDB

如果你想使用产品代码做性能测试来决定数据库的类型，那么使用多态(polymorphic)数据库。它可以在打开数据库的时候动态指定数据库类型。事实上，多态数据库被建议在大部分场景下使用，尽管它会在运行时带来一点点的性能损失。这就是为什么官方的脚本语言绑定只支持多态数据库。

事物性

如果打开数据库的应用进程没有关闭数据库，它会带来数据丢失和数据库损坏的风险。默认，正确地关闭数据库时持久性是稳定的，对于每个更新操作是不稳定的。KC处理这个问题是基于WAL（write ahead logging）的事物机制。事物由应用显示的开始和提交。在事物期间的每个更新操作的持久性是稳定的。事物可以由应用取消。这种情况下，所有事物期间的更新操作将被废弃，数据库的内容会被回滚。像这样尽管事物是非常有用的，但是 由于增加了写WAL数据， 更新操作的吞吐率会下降到默认方式的大约50%。

db.begin_transaction(); db.set("japan", "tokyo"); db.set("korea", "seoul"); db.end_transaction();

如果你对显示地开始和提交事务感到烦恼，那么可以使用自动事物机制，在打开数据库的时候指定 BasicDB::AUTOTRAN 选项。这样自动事物对每个更新操作隐式地开始和提交。自动事物的额外负担要轻于显示地事物。

db.open("casket.kch", HashDB::OWRITER | HashDB::OCREATE | HashDB::OAUTOTRAN); db.set("japan", "tokyo"); db.set("china", "beijing");

毕竟，根据你的应用的需求选择使用方式是非常重要的。

默认

进程崩溃的风险：一些记录可能丢失

系统崩溃的风险： 一些记录可能丢失

性能损失：无

注意：崩溃后的自动恢复花的时间与数据库大小成比例

事物

隐式使用：open(..., BasicDB::OAUTOTRAN);

显示使用：begin\_transaction(false); ...; end\_transaction(true);

进程崩溃的风险： 无

系统崩溃的风险：一些记录可能丢失

性能损失：吞吐率将下降到大约30%或更低

事物+同步

隐式使用：open(..., BasicDB::OAUTOTRAN | BasicDB::OAUTOSYNC);

显示使用：begin\_transaction(true); ...; end\_transaction(true);

进程崩溃的风险：无

系统崩溃的风险： 无

性能损失： 吞吐率将下降到大约1%或更低

备份

任何硬件设备都可能突然发生故障。尤其是存储设备，如HDD和SSD是脆弱的。因此，定期备份你的数据库文件是很重要的，即使你使用事物。当数据库不被另一个进程更新的时候，你可以使用如 cp 、 tar 这样的命令复制数据库文件。

如果应用使用了多线程，你想安全地做数据库的备份文件，使用 BasicDB::copy 方法，它会同步数据库状态和数据库文件并生成一个复制文件。在数据复制期间，应该保证数据库文件不被更新。

db.copy("backup.kch");

你可能想要“热备份”，意味着在一个线程创建备份文件的同时，其它线程不被阻塞。这种情况，使用File::synchronize 方法，它将同步数据库文件并调用一个任意定义的函数。回调函数能执行一个操作系统提供的"snapshot"命令。

class BackupImpl : public FileProcessor {   bool process(const std::string& path, int64_t size, int64_t count) {     char cmd[1024];     sprintf(cmd, "snapshot.sh %s", path.c_str());     return system(cmd) == 0;   } } proc; db.synchronize(&proc);

伪快照（Pseudo-snapshot）

主要为 cache hash数据库和 cache tree数据库提供伪快照机制。BasicDB::dump\_snapshot 方法 dump 所有记录到一个流或一个文件中。BasicDB::load\_snapshot 方法从一个流或一个文件中加载记录。尽管操作是原子执行的，但是它不会立刻完成，需要花数据库大小比例时间并阻塞其它线程。因为伪快照数据的格式是在所有数据库类通用的，所以适合合并彼此记录。

db.dump_snapshot("backup.kcss"); db.load_snapshot("backup.kcss");

如果你不想要其它线程被阻塞，自己使用游标机制来保存/加载记录。

加密数据库

file tree 等的数据库的 **tune\_compressor** 方法可以设置任意的数据压缩功能。事实上，功能不仅可以执行时间压缩，也可以执行数据加密。**ArcfourCompressor** 类实现了基于Arcfour (aka. RC4)的轻量加密算法。它可以用来临时改进你数据库的安全性而不会增加高负载。

ArcfourCompressor comp; comp.set_key("foobarbaz", 9); TreeDB db; db.tune_options(kc::TreeDB::TCOMPRESS); db.tune_compressor(&comp); db.open(...); comp.begin_cycle((uint64_t)getpid() << 32 + (uint64_t)time());

如果你使用多态数据库，很容易启用加密。zcomp 选择指定压缩算法，zkey 指定密钥。

PolyDB db; db.open("casket.kct#zcomp=arc#zkey=foobarbaz", ...);

zcomp支持用 zlib 对于ZLIB的原始格式， def对于 Deflate格式， gz对于gzip格式，arc对于 Arcfour加密，arcz对于ZLIB的 Arcfour加密压缩。

注意哈希数据库类型（CacheDB，HashDB，DirDB）只压缩每个记录的value。这样，每个记录的key不会被压缩。然而，树型数据库（GrassDB，TreeDB，ForestDB）压缩数据库中的所有数据。所以，如果你想要通过压缩来加密，请选择一种树型数据库。

内存数据库的空间效率

stash 数据库（StashDB），cache hash 数据库（CacheDB），和 cache tree 数据库（GrassDB）可以节省字符串形式的关联数组的内存使用。他们可以替代 C++中的std::map，Java中的java.util.Map，和许多脚本语言内建的关联数组机制。stash数据库和cache hash数据库可以改进空间效率，由于将每个记录的key和value序列化到一个字节数组中。cache tree 数据库改进了空间效率，由于将每个页中记录序列化到了一个字节数组。

例如，如果你存储一千万记录并且每个key和value都是8字节，\`std::map<std::string, std::string>' (ProtoTreeDB) 使用大约 1.2GB内存。同样的情况下，stash 数据库使用 465MB 内存；cache hash数据库使用 618MB 内存；cache tree数据库使用 318MB 内存。在这种情况下，cache tree数据库提供了最佳的空间效率。然而，关于时间效率， stash 数据库和 cache 数据库 优于 cache tree数据库，由于哈希表和B+ tree的不同。注意B+ tree是非常适合顺序访问，但不适合随机访问的。要改进B+ tree的时间效率，设置 页大小为1024或更小。

如果你想要极端减小内存使用，使用带压缩选项的 cache tree数据库。此外，设置bucket数量为记录数量的5%，设置页大小为32768或更大，设置页缓存容量小于总记录大小的5% 。例如，上面的一千万记录的情况，bucket数量应该是50万，页大小应该是32768，页缓存应该是8MB。对于多态数据库，这些表达为"%\#opts=c\#bnum=500k\#psiz=32768\#pccap=8m"。因此，一千万记录只占用 60MB 内存。

多进程共享一个数据库

多进程不能同时访问一个数据库文件。当一个进程连接到它时，数据库文件受读写锁的锁定。注意 BasicDB::ONOLOCK 选项不应该被用来跳过文件锁定机制。这个选项是用来绕过一些如NFS这样的文件系统的，它不支持文件锁定机制。

如果你想要多进程共享一个数据库，使用  [Kyoto Tycoon][]  替代。它是作为 KC 网络接口的轻型数据库server。

六、License

要使用KC，你可以选择GNU GPL 或 商业许可。如果你选择GPL，应用程序的源码要兼容GPL的许可。如果你选择商业许可，你将免除GPL的责任。

### GNU General Public License ###

Kyoto Cabinet is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or any later version.

Kyoto Cabinet is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see \``http://www.gnu.org/licenses/`'.

### FOSS License Exception ###

The FOSS License Exception is also provided in order to accommodate products under other free and open source licenses. See [the body text][] for details.

### Commercial License ###

If you use Kyoto Cabinet within a proprietary software, a commercial license is required.

The commercial license allows you to utilize Kyoto Cabinet by including it in your applications for purpose of developing and producing your applications and to utilize Kyoto Cabinet in order to transfer, sale, rent, lease, distribute or sublicense your applications to any third parties. See [the license guide][] for details.

### Author ###

Kyoto Cabinet was written and is maintained by [FAL Labs][]. You can contact the author by e-mail to \``info@fallabs.com`'.

来源：http://han.guokai.blog.163.com/blog/static/13671827120112279177670/

[Kyoto Cabinet 实现原理][Kyoto Cabinet]

由于最近在做分布式存储系统，需要一个小、性能好、靠谱的存储引擎，我们瞄准了Kyoto Cabinet，希望通过分析源码能对它进行改造成我们需要的引擎，这一工作落在我身上，于是我花了一星期时间彻底地分析了Kyoto Cabinet源码，下面将分享下由Kyoto Cabinet源码分析出的实现原理。

下面主要分析hashdb和treedb这两种存储结构，其他的要么简单，要么类似，就不分析了。

一、hashdb

hashdb，顾名思义就是哈希表，只是哈希表存放在文件系统而不是内存，复杂度比存在内存大多了，冲突采用链表或二叉树解决。

大家对哈希表应该都比较熟悉，它由三要素组成：哈希函数，哈希表和冲突解决方法。在无冲突情况下，查找、插入和更新复杂度为O（1）；有冲突情况下的复杂度就视冲突情况来定复杂度了。增加哈希表的桶数，可以减少冲突，但会牺牲空间，所以具体应用时，需要权衡冲突和空间。

下面分别对上面介绍的三要素是如何hashdb实现的。

（1）哈希函数

hashdb的哈希函数是采用MurMur[算法][Link 1]。具体可以看维基百科的介绍：[http://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C][http_zh.wikipedia.org_wiki_Murmur_E5_93_88_E5_B8_8C]，实现函数是hashmurmur，这里就不贴代码了。

（2）哈希表

hashdb的哈希表是文件系统里一个文件，它的结构由下面图所示：

![Image 1][]

图1 哈希表结构

![Image 1][]

图2 bucket section内部结构

![Image 1][]

图3 record section内部结构

![Image 1][]

图4  record 内部结构

由图1－图4可知哈希表是如何在文件系统里实现了，其中图1的meta data是哈希表的属性，图4的right address只有冲突方法是二叉树时才有，链表方式不需要。

（3）冲突解决方法

hashdb有两种冲突方案：链表和二叉树，是可选的。冲突较少时用链表好，多时用二叉树。

下面分析下hashdb里较难理解或需注意的技术细节。

（1）碎片整理

a.  首然找到一个free block  
        b.   然后将后面的记录的padding缩小，然后将记录紧凑地前移，在有限步下完成后，会空出一大块空间块

c.   最后将该大块空间加入free block pool

（2）文件恢复

触发条件：没有调用close而非正常关闭db。

恢复思想：遍历旧hashdb文件里的record，然后将合法的record插入新hashdb，最后替换旧文件。

（3）非法close[数据库][Link 2]，可能产生数据丢失或数据被认为合法但不正确

a. 写padding size的时，成功写入第一个字节，写入第二字节失败，可能引起不可回收的文件碎片，或认为该记录不合法；  
         b. 写key size或value size写一半，可能引起该记录的边界到了第二个记录上，这就为什么恢复DB时，需要顺利正确能读出两个记录的第一个记录才认为是合法的；

c.  写data写一半，只会引起数据不正确；  
         d. 写Address写一半，可通过自动恢复dB恢复，而且数据没有丢失或不正确。

（4）Free block pool大小超过最大值时，会有free block无法放入Free block pool，导致该free block无法利用，直到碎片整理到它。

（5）事务

hashdb是采用预写日志方式来实现事务的，它的事务隔离级别是可序列化的，事务的最高隔离级别，粒度最大。

日志文件格式如下图所示：

![Image 1][]

图5 日志格式

（6）hashdb的锁粒度是record级别，但又不完全是，它是分配一定数量的锁放到内存级哈希表，通过哈希的方式去获取锁。

二、treedb

treedb的[数据结构][Link 1]是采用最小B+树，B+持久化到磁盘方式是采用hashdb，我感觉该持久化方式是比较偷懒的，性能没有直接将B+树保持到磁盘好，因为通过hashdb会产生较多的磁盘IO，但作者为弥补这一点，treedb内部实现了一级lru的index page node cache和二级lru的leaf page node cache来减少读写磁盘。

treedb主要内部数据结构由下图所示：

![Image 1][]

图6  Index node结构

![Image 1][]

图7 Link node结构

![Image 1][]

图8 Leaf node结构

![Image 1][]

图9 recode结构

上面说了，treedb持久化方式是采用hashdb，上图的index node和leaf node对应hashdb的value，key是node id。

另外，如果不设autsyn，treedb不会该更新立即写入磁盘，而是写在cache里，后面某个时间再刷到磁盘上。

treedb的锁粒度是node，即page。

treedb里的lru cache是采用一般的实现方式：哈希表+双向链表。

来源：http://blog.csdn.net/whycold/article/details/21868353

[http_fallabs.com_kyotocabinet]: http://fallabs.com/kyotocabinet/
[http_www.slideshare.net_estraier_kyotoproducts-5886452]: http://www.slideshare.net/estraier/kyotoproducts-5886452
[http_fallabs.com_tokyocabinet]: http://fallabs.com/tokyocabinet/
[http_fallabs.com_kyotocabinet_spex.html]: http://fallabs.com/kyotocabinet/spex.html
[http_fallabs.com_kyotocabinet_spex.html_installation]: http://fallabs.com/kyotocabinet/spex.html#installation
[http_fallabs.com_kyotocabinet_spex.html_tutorial]: http://fallabs.com/kyotocabinet/spex.html#tutorial
[Kyoto Tycoon]: http://fallabs.com/kyototycoon/
[the body text]: http://fallabs.com/license/fossexception.txt
[the license guide]: http://fallabs.com/license/
[FAL Labs]: http://fallabs.com/
[Kyoto Cabinet]: http://blog.csdn.net/whycold/article/details/21868353
[Link 1]: http://lib.csdn.net/base/31
[http_zh.wikipedia.org_wiki_Murmur_E5_93_88_E5_B8_8C]: http://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C
[Image 1]: 
[Link 2]: http://lib.csdn.net/base/14