2011年10月16日星期日

浏览器窗口标题栏闪烁通知

对于WebIM 对话或其它各种Comet应用场景,当收到新消息时,希望能够及时提醒用户。


但是用户
可能将窗口切换到计算机上其它窗口上了,比如看其它网页、聊一下QQ、收发一下邮件等各种其它事情,此时web窗口就不在用户焦点上了,收到的新消息时很可能看不到。而javascript控制的web窗口并不能很好融入到OS级别的窗口系统中。比较普遍的一种做法就是让浏览器标题栏不断闪烁,应用程序的标题闪烁是很容易被注意到的,不管是浏览器和其它各种程序之间,还是浏览器多tab或windows之间。这算是最接近OS级别窗口的提示方式了。


实现的目标:
  • 当对话窗口失去焦点(切换到其它程序或其它浏览器窗口),并且收到新消息时,标题栏闪烁。
  • 没有失去焦点时不闪烁提示。焦点重新回到窗口时,标题栏恢复正常不再闪烁。


一、标题栏的闪烁
要实现标题栏闪烁的效果很简单,只要让 title 的内容来回变化就可以。
比如每500ms,
document.title=“【您有新的消息】”
下次
document.title=“【      】”
这样来回变化就实现了闪烁效果。



二、浏览器窗口焦点的判断
根据目标的要求,首先要知道当前窗口激活状态。

注册window.onblur和window.onfocus函数来记录焦点变化,但是IE上的行为有差异,不能直接用,而应该用document.onfocusin和document.onfocusout。
关于window或Dom元素的focus焦点这方面的行为,各浏览器行为有差异,尤其IE的行为有很多bug。

//当前浏览器窗口是否处于焦点
var isWindowFocus = true;
function focusin() { isWindowFocus=true;}
function focusout() { isWindowFocus=false;}
//注册焦点变化监听器
if ("onfocusin" in document){//for IE 
    document.onfocusin = focusin;
    document.onfocusout = focusout;
} else {
    window.onblur = focusout;
    window.onfocus= focusin;
}



三、具体实现
使用方式:每当收到新消息时就调用 doFlashTitle 方法实现闪烁,调用者不做任何判断。
要求:
1.如果当前窗口失去焦点一直执行title闪烁,如果当前处于窗口焦点则什么也不做。
2.当窗口重新获得焦点时,停止闪烁(退出闪烁循环)。
3.多次调用,闪烁循环本身只应执行一次。也就是说闪烁函数只同时运行一个,否则多个同样的调用一起执行的话会导致标题闪动异常(快),消耗资源。

//实现标题闪动效果

var flashStep=0;  //交替变量
var flashTitleRun = false; //是否正在执行
var normalTitle = "正常显示的标题"; 
function flashTitle()  
{  
 //仅窗口不在焦点时闪烁title,回到焦点时停止闪烁并将title恢复正常
 if(isWindowFocus){//当前处于焦点
  document.title=normalTitle;
  flashTitleRun = false;
  return;//退出循环
 }
 
 flashTitleRun = true;
 flashStep++;  
 if (flashStep==3) {flashStep=1;}  
 if (flashStep==1) {document.title="【您有新的消息】";}  
 if (flashStep==2) {document.title="【      】";}  
 setTimeout("flashTitle()",500);  //循环
} 
//调用这个执行标题闪烁,而不是直接调用flashTitle,保证多次调用只会执行一次。
function doFlashTitle(){
 if(!flashTitleRun)//没有执行时,才执行
      flashTitle();
}


四、小结
title闪烁并不难,但跨浏览器的焦点判断的问题比较多,IE非常诡异。参考资料都是焦点判断方面的。
只能判断出窗口焦点是否激活,没有办法判断窗口对人是不是可见的。

在js中调用window.focus()方法,窗口到底会不会被激活是完全不可靠的。而在IE上执行此方法,不管窗口是否激活了,都会导致focus事件的触发,使得上述的判断方法认为已经获得焦点了,但其实没有。所以最好就不要再使用window或dom的focus方法,以免干扰判断。而非IE浏览器正常,只有窗口确实被激活了才触发focus事件。


参考资料:

hotmail前端优化

前两天(2011-7-1),有一篇hotmail前端优化的文章,使用户响应比以前快10倍,自己简单小结一下。原文地址:这里 。不过,只能说hotmail以前优化做得太少了,这些gmail老早就做了。(遗憾的是国内用户最近访问hotmail也不太顺畅)


现代浏览器越来越强大,可以把更多的工作从server端交给浏览器去做。更一般地说,C/S模型中,如果C越强大,就可以考虑把更多S的工作放到C中去完成。


缓存、预加载、异步操作。
优化的关键是找到平衡点。


缓存:
已加载的数据缓存住,不要每次都重新加载。
即使今天的美国,网络依然是瓶颈。所以数据离浏览器越近就越快。
如果数据不在浏览器,应该使用更加有效的方式获取。
浏览器中可以直接用DOM对象缓存,需要的时候直接切换过去。


缓存的平衡:
缓存何时需要更新,比如有新邮件时?server通知浏览器,然后浏览器获取数据。也就是,服务器推送通知。
退出hotmail时清掉缓存,保证隐私安全。当然,如果没有安全方面的问题,可以考虑缓存更长时间。


预加载:
如果内容已经有了,响应自然就是即时的。
预加载的数据类型:可以是数据,也可以是代码。

什么时候预加载什么?
原则上说应该预加载最有效的、命中率高的内容。而这要基于用户的行为特征,也就是通过用户(各阶段的)行为分析来决定。
比如:
  • 用户一上来一般会查看列表中新邮件标题,然后会选择查看他们,利用用户这个停顿的时机来预加载新邮件的内容。
  • 用户看这封邮件的内容很可能也会看挨着的下一封或上一封邮件的内容,所以可以预加载下一封邮件内容。
  • 用户看这封邮件的时候,下一步的行为可能是删除或回复,所以可以预加载好删除和回复的代码和数据(发送时需要有地址簿的数据)。

时机的技巧:利用人在操作的间歇预加载。人不是机器,人的行为是由一系列的动作组成,中间会有或长或短的间歇时间,就算对人而言是很短的间歇,对机器而言也是很长的间隔时间了。

为了效果更好,设计上也应该需要调整。

加载技巧:可以将下载的内容分成小块,并按一定的优先顺序下载,用户最需要的应该尽快可用。而不是一次加载太多的数据,那样可能造成不能及时响应。

考虑到巨大的用户量,前端应要防止server过载,保持服务有效 。另外,后台还要努力提升存储系统的吞吐率。

我顺便补充一下懒加载:
预加载和懒加载是两个相反的行为,但都是性能优化的手段,改善用户体验,具体看怎么用了。
预加载那些用户下一步马上需要的,如初次加载就包含,或在初次加载之后,利用用户的下一步行为的间歇时间提前加载。
而懒加载是先不加载那些用户不会马上用到的,或不常用到的部分,这样减少了加载内容。


异步操作:
没啥说的,界面立刻响应,任务在后台执行,而不是等待。

最后,性能是特性,优化无止境。

Macbook Pro 使用小记

本周(2011年5月)到手Macbook Pro,很激动。刚刚使用了几天,简单记下自己的感受。

Macbook Pro的硬件配置和做工真没得说,非常完美。
触控板很强大、很好用,鼠标可以基本不用了,但要稍微学习一下。
主要说说软件系统的差异。

鼠标右键功能使用较少,大部分功能设计使用单键就可以搞定。


Dock:
很多程序关闭按钮的行为不是退出,而是类似于最小化到dock中,需要Command+Q或菜单来退出。

Finder相当于资源浏览器,但是没有地址栏不太习惯。
命令行终端和linux差不多,特权命令也需要sudo执行。


widget小工具集也不错。


键盘与菜单:
快捷键不一样,大多需要Command键组合,很多组合习惯也不一样。
程序中“关于”菜单,是最左边的菜单中的第一项,而windows一般是最右边菜单的最后一项。
程序的菜单不是在应用程序上,而是统一在桌面顶部,切换程序菜单就跟着变。

Mac笔记本上的按键比标准键盘少很多。
F1-F12功能不一样,直接按就可以,不需要Fn,而一般笔记本相反,都需要Fn来使用功能。
键盘没有Home、End、PageUp、PageDown,需要 Fn+4个方向键 替代。
光标移到行首或行尾:command+左箭头或右箭头。
标准键盘右两个删除键:backspace(向左删)和Del(向右删),而Mac上只有一个delete键,作用和backspace键一样,如果想向右删需要用Fn+delete。
剪切、复制、粘贴、撤消:不是用Ctrl,而是Command组合。


窗口的关闭、最小化、最大化:
这三个按钮在窗口左上角,而windows是右上角。
关闭按钮也是反的,在三个按钮的最左边,而不是最右边。
最大化按钮很不一样,不是真的最大化,而是根据窗口内容的最合适大小(一般比最大化小很多),只能自己拖到更大的大小。小提示:chrome浏览器用 “shift+最大化” 可以真的最大化。

Cmd+X只能操作文本,不能操作文件或文件夹。必须用拖拽的方式实现:
拖动到其它目录就是剪切,或者Command+拖拽强制剪切到外部存储设备;
Option+拖拽是复制;Cmd+Option+拖拽是创建快捷方式。

windows上弹出的提示窗口一般出现在桌面右下角,而Mac是右上角。

文件系统方面:Mac可以读写Fat格式文件。注意:mac可以读ntfs格式的数据,但不能写ntfs(修改、删除、新建),比如使用ntfs格式的移动硬盘。

软件:Mac上有自己的App Store,没事可以进去看看,很多常用软件都有,但不是很全。

安装软件:安装包一般是一个dmg格式的文件,其实就是一个镜像。常见有两种安装方法:
  1. 带安装向导的,一路点下去即可。一般也提供了卸载程序。
  2. 直接将程序拖动到应用程序文件夹。删除也是从应用程序中拖到回收站。

Mac上自带了大量应用软件和实用工具,不介绍了,挺好玩的。
默认就有Java、Python、Ruby等语言支持,这对开发人员非常友好。
Mac自带的中文输入法不太好用,可以自己安装FIT输入法(和SunPinyin合作了),搜狗和QQ输入法也出了Mac版了。
MPlayerX播放器不错,可以播rmvb这种国内经常使用的格式。

我常用的软件:
  • 浏览器:Chrome、Firefox、Safari
  • 输入法:FIT输入法(SunPinyin)、搜狗输入法、QQ输入法
  • BT下载工具:Vuze
  • MPlayerX播放器
  • 编辑器:TextWrangler、jEdit、Bluefish、MacVim
  • Twitter for mac
  • 虚拟机:VirtualBox
  • Dropbox
  • The Unarchiver(7zip、rar解压)
  • QQ、MSN都有官方的Mac版,自带iChat就支持Gtalk
  • http://www.microsoft.com/mac/ 除了MSN,还有Mac版的远程桌面,方便访问Windows
  • chnroutes vpn路由


开发工具:

  • XCode,包括了unix常用工具gcc等,开发人员必备。已经免费了,自带系统光盘中有,也可以从App Store中下载。
  • Eclipse
  • 自带终端(Terminal),多种风格、保存书签等功能都有
  • 安装各种Linux开源软件的工具,MacPorts、Homebrew 和fink,推荐Homebrew
  • Mysql官方有Mac版,App Store有免费的Navicat for mysql Lite


文件名关联办法:右键-显示简介-打开方式(调整为希望的默认程序)-全部更改
注意:右键-打开方式-其它-总是以此方式打开,只对当前文件有效,不是都改。
技术上是和叫做Launch Service的系统服务有关。


Mac自带终端(Terminal),因为没有PageUp、PageDonw,查看man、less等命令时无法翻页,使用Fn或Command组合也不成。解决方法是用传统Unix的空格/b或ctrl+f和ctrl+b

2011年3月29日星期二

【原创】Kyoto Cabinet 基本规格书

如果你知道 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,建议按下面示例这样设置。
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 来对内部内存映射区域分配内存。

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

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' (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'.