4,110
9月 152013
9月 152013
转载： http://www.360doc.com/content/11/0401/17/28217_106451082.shtml
如果你知道 Tokyo Cabinet ，那么就应该知道 Kyoto Cabinet，因为他们都是同一个作者（平林幹雄）开发出来的 Key-Value 数据库。
Kyoto Cabinet：a straightforward implementation of DBM，主页：http://fallabs.com/kyotocabinet/ ，演示文稿：http://www.slideshare.net/estraier/kyotoproducts-5886452 。
Tokyo Cabinet：a modern implementation of DBM，主页： 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
一、介绍
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#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，建议按下面示例这样设置。
|
1 |
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 来设置一个实现排序功能的函数。
如果你想缓存一千万记录，并让内存使用尽可能小，建议按下面示例这样设置。
|
1 |
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万个记录，并尽可能减小数据库大小，建议按下面示例这样设置。
|
1 |
db.tune_alignment(0); db.tune_options(HashDB::TSMALL | HashDB::TLINEAR); db.tune_buckets(10LL * 1000); db.tune_defrag(8); db.open(...); |
如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率，建议按下面示例这样设置。
|
1 |
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 来对内部内存映射区域分配内存。
默认的记录比较器是词汇顺序（lexical ordering）函数。这样B+ tree数据库中的记录按照key的词汇顺序放置。如果你想使用其它顺序，调整 tune_comparator 来设置一个实现排序功能的函数。
file tree数据库的默认对齐是256（1<<8）。默认的bucket数量大概是65536。其它的默认参数和file hash数据库一样。注意bucket的数量应该按照页的数量计算。建议 bucket数量的比率大约是记录数量的10% 。如果压缩选项被指定，每个页的所有记录被立刻压缩。因此，压缩对于 file tree数据库更有效，而不是file hash数据库。
如果你想存储1万个记录，并尽可能减小数据库大小，建议按下面示例这样设置。
|
1 |
db.tune_options(TreeDB::TLINEAR | TreeDB::TCCOMPESS); db.tune_buckets(1LL * 1000); db.tune_defrag(8); db.tune_page(32768); db.open(...); |
如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率，建议按下面示例这样设置。
|
1 |
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%。
|
1 |
db.begin_transaction(); db.set("japan", "tokyo"); db.set("korea", "seoul"); db.end_transaction(); |
如果你对显示地开始和提交事务感到烦恼，那么可以使用自动事物机制，在打开数据库的时候指定 BasicDB::AUTOTRAN 选项。这样自动事物对每个更新操作隐式地开始和提交。自动事物的额外负担要轻于显示地事物。
|
1 |
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 方法，它会同步数据库状态和数据库文件并生成一个复制文件。在数据复制期间，应该保证数据库文件不被更新。
|
1 |
db.copy("backup.kch"); |
你可能想要“热备份”，意味着在一个线程创建备份文件的同时，其它线程不被阻塞。这种情况，使用 File::synchronize 方法，它将同步数据库文件并调用一个任意定义的函数。回调函数能执行一个操作系统提供的”snapshot”命令。
|
1 |
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 方法从一个流或一个文件中加载记录。尽管操作是原子执行的，但是它不会立刻完成，需要花数据库大小比例时间并阻塞其它线程。因为伪快照数据的格式是在所有数据库类通用的，所以适合合并彼此记录。
|
1 |
db.dump_snapshot("backup.kcss"); db.load_snapshot("backup.kcss"); |
如果你不想要其它线程被阻塞，自己使用游标机制来保存/加载记录。
加密数据库
file tree 等的数据库的 tune_compressor 方法可以设置任意的数据压缩功能。事实上，功能不仅可以执行时间压缩，也可以执行数据加密。ArcfourCompressor 类实现了基于Arcfour (aka. RC4)的轻量加密算法。它可以用来临时改进你数据库的安全性而不会增加高负载。
|
1 |
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 指定密钥。
|
1 |
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‘.
10月 072012
在Tokyotyrant中有支持根据前缀来查询的方式，命令行如下：
tcrmgr list [-port num] [-sep chr] [-m num] [-pv] [-px] [-fm str] host
参数中的-fm 就是要指定的key的前缀，试想：不同的存储方式中，这种操作是怎么实现的呢？
1. 对于hash存储，遍历所有的key，然后和提供的前缀来比较，显然效率是很低的，所以如果有这种需求，就不要使用hash存储
2. 对于tree的存储方式，比hash方式查找要比较的少一些
3. B+tree， 这个就比较快一下，这个是比较适合的存储方式
8月 272012
缘起：
tokyotyrant自有的master<->master， master->slave 模式已经不能满足业务的需要，现在期望可以随意复制，选择性复制。
办法：
1. 我们可以直接分析ulog来实现
2. 我们可以参考tokyotyrant的复制协议，通过socket来复制，或者使用C来实现，或者使用自己熟悉的语言实现
3. tokyotyrant提供了一个tcrmgr的工具，其中的repl子命令可以帮助我们通过socket复制数据，我们就可以使用自己熟悉的语言，将输出的信息解析后处理，同步到自己想同步到的地方去
PHP代码：
这里仅仅实现了两个命令的解析。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
<?php define("PUT", "10"); define("OUT", "20"); while(!feof(STDIN)) { $str = trim(fgets(STDIN)); if (!$str) continue; $arr = explode("\t", $str); parse_record($arr[3]); } exit; function parse_record($str) { $str = str_replace(" ", "", $str); if (strlen($str) < 4) return false; $magic = substr($str, 0, 2); $cmd = substr($str, 2, 2); if ($magic != "C8") return false; switch($cmd) { case OUT: $ksiz = hexdec(substr($str, 4, 8)) * 2; $key = pack("H*", substr($str, 12, $ksiz)); echo "out\t", $key ,"\n"; break; case PUT: $ksiz = hexdec(substr($str, 4, 8)) * 2; $key = pack("H*", substr($str, 20, $ksiz)); $vsiz = hexdec(substr($str, $ksiz + 18, 8)) * 2; $val = pack("H*", substr($str, $ksiz + 20, $vsiz)); echo "put\t", $key , "\t", $val, "\n"; break; default: } return true; } |
使用方法：
tcrmgr repl -port 4242 -ts 1345999492000000 -sid 1234 -ph 10.71.6.28|php repl.php
记录格式：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
struct record{ int magic; // 0xc8 int cmd; // put: 0x10; delete 0x20; ... ... } struct put_record{ int magic; // 0x80 int cmd; // 0x10 int32 ksiz; char *key; int32 vsiz; char *val; } struct delete_record{ int magic; // 0x80 int cmd; // 0x20 int32 ksiz; char *key; } |
6月 182012
使用Tokyotrant有相当一段时间了，确实有几次莫名的退出，今天再次出现，查了一下系统日志，报错如下：
$grep ttserver /var/log/messages
Jun 18 22:00:42 localhost kernel: [2463228.773583] ttserver[32282] general protection rip:2b6557922dcb rsp:4a0b2c08 error:0
又出现一次；
Jul 18 07:00:21 localhost kernel: [11461817.641400] ttserver[612]: segfault at 000000001ffc2000 rip 0000003f5407c08f rsp 000000004732ec08 error 4
2月 012012
下面的8001端口进程使用的是默认的malloc内存分配器， 8002端口是使用了tcmalloc内存分配器，线上数据运行了1个月的时间，发现tcmalloc使用的内存更多一些。
12月 222011
1. 同样在一组磁盘上的两个TT端口，其读写操作是根据均匀的hash方式来分配的，但是，其中一个3001端口同步数据就很慢，而3002端口同步数据就很快，重启3001端口依然很慢； 把3002端口停掉之后，3001端口依然很慢。
2. 通过tcpdump抓包发现：
3001端口的master 2001端口，数据流表现为：
2001 ——–很多数据给—–》 3001
3001 ——–因为吃不消，所以act 一个win(0) 给 —-》 2001
2001 ——–不断询问 ———-》3001
2001 ——–不断询问 ———-》3001
2001 ——–不断询问 ———-》3001
3001 ——–响应，说在给点儿吧 ——-》 2001
2001 ——–很多数据给 ———…..
使用netstat也可以发现，对于3001的同步连接中的接受队列总是会阻塞很多数据，看来是执行的太慢
3. 观察 3001端口的执行情况，下面是使用strace跟踪的这个繁忙的ttserver进程的系统调用情况：
为什么futex耗费的时间如此惊人？
12月 222011
1. TokyoTrant（后面简称TT）在备份的时候不能提供写服务也不能提供读服务2. 备份的速度取决于磁盘的好坏
下面有一个TT备份的参考：
date; tcrmgr copy -port 3004 10.xx.x.xx @/data1/tokyotyrant/bin/ttbackup.sh; date
Thu Dec 22 23:22:59 CST 2011
Thu Dec 22 23:25:30 CST 2011
这里备份了12G的数据，用了2.5分钟；
磁盘性能：
5块 146G的磁盘做了逻辑卷的， 备份到同一个目录下， 如果按照300MB/s 的写速度， 300MB/s 的读速度，则每秒钟复制150MB的数据，则大约100s可以复制15G的数据；
而这里12G的数据复制了2.5分钟，看来我的计算是有些偏差的
另外一台机器的备份情况，备份数据量： 9.4G
关于复制时的一点注意事项：
当我们将复制好的从库启动之后，可能会发现延迟越来越大，可能是因为，数据都在磁盘上，虽然配置了很大的内存，现在还没能用上，磁盘的随机读写操作可能比较严重，过一段时间之后，随着磁盘数据越来越多地载入内存，这时候的读写操作都会很快了，延迟自然就越来越小了。
9月 012011
不同的情景适合不同的参数，我们的场景是读写比例2:1， 写操作高峰时间为 6000/s ；资源为 2台8核16G内存机器。每台机器 6 * 149G的磁盘做了raid10。
每台机器2个端口，每个端口数据文件为5G； 存储方式为 .tch ; 没有任何调谐参数时， 每个端口处理写操作量为：
200~400/s ； 添加调谐参数 #xmsiz=5242880000 后， 每个端口处理写操作量为：
1000~2000/s ； 速度整整提高了原来的4倍。
关于负载的比较（只取了部分时间点来比较）：
调整参数前：
sar -f /var/log/sa/sa05
调整参数后：
sar -f /var/log/sa/sa06
关于磁盘的读写数据的变化，因为没有sar没有收集，这里就不能给出了
关于页面的换入换出的比较：
调整参数前：
sar -B -f /var/log/sa/sa05
调整参数后：
sar -B -f /var/log/sa/sa06
可以看到，页面的换入换出明显减少了大约一半， 或许你发现了fault变多了，这也是使用了mmap的缘故，具体需要了解一下mmap了。
关于mmap：
因为tc是从文件的开始固定地map文件的一段区域的，所以，如果map的那段区域如果慢慢变冷的话，这样的map也就变的没有意义了；或者文件太大，能map到内存的也不过1/10或者更少，则map的意义也是很小的，故要根据实际情况来选择之。
如果tc能聪明地选择map热数据的话，自然是件好事，但是目前确实还没有这么做，而且其升级版kc也没有这么做，至少到1.2.70版本是没有这么做的。
8月 312011
最近由于使用TokyoTyrant的全内存存储方式导致内存吃紧，于是突然想到TokyoTyrant支持压缩存储，抱着试一试的态度，看看内存存储是不是也能压缩；测试了一下发现似乎没有压缩，看了一下代码，如下图：
不解释了，意思就是说内存型的不支持压缩，其实也可以理解