Kyoto Cabinet 基本规格书

转载： 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，建议按下面示例这样设置。
所有的调优方法必须在数据库打开前设置。
调优 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 来设置一个实现排序功能的函数。
如果你想缓存一千万记录，并让内存使用尽可能小，建议按下面示例这样设置。
所有的调优方法必须在数据库打开前设置。
调优 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万个记录，并尽可能减小数据库大小，建议按下面示例这样设置。
如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率，建议按下面示例这样设置。
所有的调优方法必须在数据库打开前设置。因为 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万个记录，并尽可能减小数据库大小，建议按下面示例这样设置。
如果你有巨兽般的512GB内存的机器，想存储百亿个记录，并想尽可能改进时间效率，建议按下面示例这样设置。
所有的调优方法必须在数据库打开前设置。因为 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%。
如果你对显示地开始和提交事务感到烦恼，那么可以使用自动事物机制，在打开数据库的时候指定 BasicDB::AUTOTRAN 选项。这样自动事物对每个更新操作隐式地开始和提交。自动事物的额外负担要轻于显示地事物。
毕竟，根据你的应用的需求选择使用方式是非常重要的。
默认
进程崩溃的风险：一些记录可能丢失
系统崩溃的风险：一些记录可能丢失
性能损失：无
注意：崩溃后的自动恢复花的时间与数据库大小成比例
事物
隐式使用：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 方法，它会同步数据库状态和数据库文件并生成一个复制文件。在数据复制期间，应该保证数据库文件不被更新。
你可能想要“热备份”，意味着在一个线程创建备份文件的同时，其它线程不被阻塞。这种情况，使用 File::synchronize 方法，它将同步数据库文件并调用一个任意定义的函数。回调函数能执行一个操作系统提供的”snapshot”命令。
伪快照（Pseudo-snapshot）
主要为 cache hash数据库和 cache tree数据库提供伪快照机制。BasicDB::dump_snapshot 方法 dump 所有记录到一个流或一个文件中。BasicDB::load_snapshot 方法从一个流或一个文件中加载记录。尽管操作是原子执行的，但是它不会立刻完成，需要花数据库大小比例时间并阻塞其它线程。因为伪快照数据的格式是在所有数据库类通用的，所以适合合并彼此记录。
如果你不想要其它线程被阻塞，自己使用游标机制来保存/加载记录。
加密数据库
file tree 等的数据库的 tune_compressor 方法可以设置任意的数据压缩功能。事实上，功能不仅可以执行时间压缩，也可以执行数据加密。ArcfourCompressor 类实现了基于Arcfour (aka. RC4)的轻量加密算法。它可以用来临时改进你数据库的安全性而不会增加高负载。
如果你使用多态数据库，很容易启用加密。zcomp 选择指定压缩算法，zkey 指定密钥。
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‘.

关于sqlite的事务的使用

缘起

sqlite写入500条不大的记录居然要花费20多秒的时间，太慢了！！！

分析

sqlite是一个非常优秀的嵌入式数据库，读取性能非常好，写入性能就比较差一些，为什么写入性能差呢？下面做了一个测试。

下面是对500+条记录些操作的系统调用的观察，发现时间基本花费在了fdatasync系统调用上，调用2064次；write系统调用虽然8049次，但是write并不保证逻辑，所以速度很快。

 

查资料

http://www.cnblogs.com/KimSky/archive/2011/05/31/2064028.html

发现： 如果使用事务的方式批量插入数据，效果会有明显改善，因为默认情况下每次写入操作都会落地才返回的（更加安全靠谱），如果使用事务，则批量数据一次性落地。

修改代码，分析系统调用如下：（发现fdatasync调用12次）

 

结论：

1. 借用事务采用批量写入的方式来加速写操作

2. 如果业务上不能批量操作呢？似乎有一个nosync的sqlite版本（不知道为什么不是一个配置选项）

参考资料： http://www.sqlite.org/speed.html

3. 如果数据量太大，可以分多批提交事务，因为事务是需要内存的。（不过，sqlite一般不会存放N个G的数据的，几百MB已经算是比较大的了，这样的数据量内存还是吃的消的）

 

参考资料：

http://www.phpchina.com/archives/view-33876-1.html

 

关于sqlite的系列分析文章（可以看看）

http://www.cnblogs.com/hustcat/archive/2009/02/12/1389448.html

 

SQLite的原子提交原理

http://www.cnblogs.com/vagerent/archive/2008/11/05/1327247.html

 

PHP实现的一维关联数组序列化

下面是一个典型的k-v存储格式的PHP实现：

 

注意：

1. pack(“n”,…) 使得key、value长度都限制在65535以内

IE6下经典的请求abort问题

摘自：http://www.cnblogs.com/shihao/archive/2012/06/22/2559042.html

 

IE6 a标签的请求被abort的原因

最近项目中掉进IE6 a标签abort两次坑，第一次是a标签绑定一个事件，href='javascript:;'这样a标签触发了事件，切换验证码图片，结果验证码图片总是显示不出来，通过抓包显示状态为abort。其实这个的原因可以从IE6中a标签执行顺序说起，IE6中a标签执行onclick在执行默认事件（即href跳转）之前，当触发了绑定的事件之后，那么处理完事件之后，如果不return false或者阻止默认事件，则会继续执行href跳转，IE6会认为页面跳转到其他页面或者页面重新刷新，则abort之前onclick事件中的请求。

所以当onclick时，做出的获取最新验证码图片的请求，会因为下一步href的触发而abort。同时，如果你在a绑定的事件中做ajax请求，那么也会被无情的abort。

IE6 a标签的请求被abort的解决方案

解决的方法就是在onclick或者绑定事件中return false来阻止a标签跳转的默认事件。
例如下面的代码：

或者你也可以给a标签的href写成“#”，即当前页面的锚点，这样页面就不会跳转，自然不会abort请求。

最好的方式还是两种都用，保险！

 

其他参考资料：

http://www.web92.net/758.html

http://www.cnblogs.com/Ren_Lei/archive/2010/09/26/1836130.html

面试题

 

编写算法，从10亿个浮点数当中，选出其中最大的10000个。

1、读入的头10000个数，直接创建二叉排序树。O(1)
2、对以后每个读入的数，比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
3、如果大，查找二叉排序树，找到应当插入的位置。
4、删除当前最小的结点。
5、重复步骤2，直到10亿个数全都读完。
6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
基本上算法的时间复杂度是O(N)次比较
算法的空间复杂度是10000(常数)

Bloom Filter算法及应用

1. 引言
问题：有1000瓶药，但是其中有一瓶是有毒的，小白鼠吃了24小时后就会死掉，请问，在24小时找出有毒的药物，最少需要多少只小白鼠？
答案是：10只，一只小白鼠可以表示2种状态，2^10可以表示1024种状态
分析可参考：http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态，Bloom Filter(BF)算法也是利用这个思想，其本质是上是一个很长的二进制向量和一系列随机映射函数

2. 概述
问题：快速判断一个元素是否在一个集合中
解决方法：一般来说，我们会用HASH表来存储集合中的数据，好处是快速准确，缺点是存储效率低，在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题，而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合，来判断一个元素是否属于这个集合
优点是：快速查找，并具有非常高的存储效率
缺点是：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合

3. 算法描述
BF包含：
1)一个m位的二进位数组，每一位初始化时置为0
2)k个相互独立的hash函数
算法：
针对一个n个元素的集合，通过k个hash函数，将集合中的每个元素都映射到二进位数组中，映射到的位置置为1
例如：对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时，通过对P应用k次hash函数，判断其对应所有的位置都是1，如果是则认为P是集合中的元素，否则不是。

4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，如何根据输入元素个数n，确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明（可参考相关文档），可以得到：
1）当hash函数个数k=(ln2)*(m/n)时错误率最小
2）在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍

5. 应用
有10亿个url，如何判断一个新的url是否在这个url的集合中？
一个url平均长度为52，如果用Hash表解决的话，由于Hash表的存储效率一般只有50%，因此10个url大概需要100G内存，一般服务器无法存储。
使用BF，要求错误率小于万分之一。
此时，输入元素n=10亿，最大错误率E=0.0001
可计算出：m=nlg(1/E)*1.44=57.6亿，大概需要7.2亿（57.6亿/8）个字节，即720M内存。
Hash函数个数：k=(ln2)*(m/n)  大概4个Hash函数

6.总结
BF通过牺牲一定的错误率来保证时间和空间（鱼与熊掌，不可兼得），目前被广泛应用于海量数据处理及数据库系统中。
例如，在Big table和Cassandra中，都使用BF作为索引结构。
P.S 针对BF的错误识别问题，可以通过建立白名单的方式解决。

参考文献：
paper：Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500

 

迅雷面试题

1.给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
2.一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。最后就做出这一道题目，时间复杂度为O(n!), 空间复杂度为O(n)。

算法题：
1.连接两个单向链表，返回排序后的结果。
2.一个保存有10000个URL的文本文件，删除其中相同的URL。
3.将9个石子放在9×9的方格中，要求同行、同列、45度上无两个石子。

智力题：
1.一笔画四条直线穿过3×3的9个点。
2.国王给三个囚犯每人戴了一顶帽子，帽子不是黑色就是白色，并且告诉囚犯们谁看到其它两个人都是白帽子或者知道自己戴的是黑帽子，谁就能被释放。囚犯们能看到其它的人帽子颜色，但是看不到自己的帽子颜色。过了一段时间，三个囚犯都没有说话，其中一个聪明的囚犯立刻肯定自己戴的是黑帽子，你知道为什么吗？
3.有16个硬币，A和B轮流拿，每次拿的个数只能是1，2，4之一，谁最后拿谁就输。问可以保证赢吗？?

文件的打开方式

用法：

1. 不存在则创建之，存在则直接用之

因为w/w+ 会清空文件，故不用

2. 打开文件后可以随意改写和读取文件的任何部分

因为 a/a+ 不能随意seek到文件的任意位置，故不用

 

 

fopen() 中 mode 的可能值列表
mode 说明
‘r’ 只读方式打开，将文件指针指向文件头。
‘r+’ 读写方式打开，将文件指针指向文件头。
‘w’ 写入方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘w+’ 读写方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘a’ 写入方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘a+’ 读写方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘x’ 创建并以写入方式打开，将文件指针指向文件头。如果文件已存在，则 fopen() 调用失败并返回 FALSE，并生成一条 E_WARNING级别的错误信息。如果文件不存在则尝试创建之。这和给 底层的 open(2) 系统调用指定 O_EXCL|O_CREAT 标记是等价的。
‘x+’ 创建并以读写方式打开，其他的行为和 ‘x’ 一样。

 

注意：

1. w+ 方式总是会把原文件清空的

2. a+ 方式是不能来回fseek的

所以，或许你需要的是 r+ 方式，自己先判断一下文件是否存在，不存在则创建之即可

关于文件的最后修改时间

有这么一个现象，明明看着日志文件的最后修改时间不断地变化，但是日志内容却没有增长，看了一下是磁盘空间满了；

这里说明一个逻辑，对于已存在的文件，即使磁盘空间满了，更新文件的时候虽更新失败，依然会导致文件的最后修改时间发生变化；推测：更新文件内容时，应该是先更新文件的最后修改时间，然后再更新内容的；如果更新最后修改时间在后，似乎程序员不会让更新内容失败的情况下依然去更新最后修改时间的

fgets的第二个参数

缘起

string fgets ( resource $handle [, int $length ] );

第二个参数指定可以读取的最大长度，但是比较有意思的是，如果最终没有读取到换行，则返回的不是$length个字节，而是 $length -1 个字节，文档是这么写的，事实也是这样子的，那么为什么制造这么一个小插曲呢？说多少就是多少不是很好嘛，为什么还要少一个字节呢？

分析

因为PHP是用c写的，这可能也不是PHP故意如此的，或许C就是这样的，于是：

man fgets

…

fgets() reads in at most one less than size characters from stream and stores them into the buffer pointed to by
s. Reading stops after an EOF or a newline. If a newline is read, it is stored into the buffer. A ‘\0’ is
stored after the last character in the buffer.

…

看来这和字符串buffer的长度是有关系的，字符串总是要以”\0″（是零不是欧）结尾的，所以真正得到的长度比指定的长度是小1的。

如果一行是3个字符（带上换行），这时候，指定fgets的最大长度为3，则读不出来换行，只能读到2个字符，写一次才能读到换行