手机上的 AI - 在 Android/iOS 上运行 Caffe 深度学习框架

目前在云端基于各种深度学习框架的 AI 服务已经非常成熟,但最近的一些案例展示了在移动设备上直接运行深度神经网络模型能够带来很大的处理速度优势。比如 Facebook 在官方博客上发布的可在移动设备上进行实时视频风格转换的应用案例 “Delivering real-time AI in the palm of your hand”。其中提到 Caffe2go 框架加上优化后的网络模型,可以在 iPhone6S 上支持 20FPS 的视频风格转换。Google Tensorflow 也提供了 iOS 和 Android 的 example

Caffe 是一个知名的开源深度学习框架,在图像处理上有着非常广泛的应用。Caffe 本身基于 C++ 实现,有着非常简洁的代码结构,所以也有着很好的可移植性。早年也已经有了几个 github 项目实现了 Caffe 到 iOS/Android 平台的移植。但从我的角度来看,这些项目的编译依赖和编译过程都过于复杂,代码也不再更新,而且最终产出的产品包过大。caffe-compact 最接近我的思路,但是在两年前未完工就已经不更新了。

从我个人在 APP 产品上的经验来看,移植深度学习框架到 APP 中,不仅仅是能不能跑,跑不跑得快,还有个很重要的因素是包大小问题。因为一般用深度学习模型只是实现一个产品功能,不是整个产品。一个产品功能如果对 APP 包大小影响太大,很多 APP 产品都无法集成进去。我希望依赖库能尽量地精简,这样打包进 APP 的内容能尽量地少。所以我在春节期间在 github 上启动了一个 Caffe-Mobile 项目,将 Caffe 移植到 Android/iOS 上,并实现了以下目标:

NO_BACKWARD:手机的电量和计算能力都不允许进行模型训练,所以不如干脆移除所有的后向传播依赖代码,这样生成的库会更小,编译也更快。

最小的依赖。原始的 Caffe 依赖很多第三方库:protobuf, cblas, cuda, cudnn, gflags, glog, lmdb, leveldb, boost, opencv 等。但事实上很多依赖都是没必要的:cuda/cudnn 仅支持 GPU, gflags 仅为了支持命令行工具,lmdb/leveldb 是为了在训练时更高效地读写数据,opencv 是为了处理输入图片,很多 boost 库都可以用 c++0x 库来替换。经过精简和修改部分代码,Caffe-Mobile 的第三方库依赖缩减到两个:protobuf 和 cblas。其中在 iOS 平台上,cblas 用 Accelerate Framework 中的 vecLib 实现;在 Android 平台上, cblas 用交叉编译的 OpenBLAS 实现。

相同的代码基,相同的编译方式。两个平台都采取先用 cmake 编译 Caffe 库(.a or .so),然后再用对应平台的 IDE 集成到 app 中。编译脚本使用同一个 CMakeList.txt,无需将库的编译也放到复杂的 IDE 环境中去完成。

可随 Caffe 代码更新。为了保证开发者能追随最新 Caffe 代码更新,我在修改代码时使用了预编译宏进行分支控制。这样进行 diff/patch 时,如果 Caffe 源码改动较大,merge 时开发者可以清楚地看到哪些地方被修改,是如何改的,更方便 merge 最新更新。

除了 Caffe 库外,在 Caffe-Mobile 项目中还提供了 Android/iOS 两个平台上的最简单的 APP 实现示例 CaffeSimple,展示了在手机上使用 Caffe example 里的 MNIST 示例(深度学习领域的 Hello World)训练出来的 LeNet 模型预测一个手写字符 “8” 图片的过程和结果。 Caffe-Mobile 项目的地址在:https://github.com/solrex/caffe-mobile 欢迎体验,感兴趣的同学们也可以帮忙 Star 下 :)

消息队列

整理浏览器书签时候发现以前对 Message Queue 产生过一些兴趣,以后说不定还会仔细做一下调研。在这里先简单记录一下,也好精简书签数量。

1. MemcacheQ

使用 memcache 协议的消息队列,存储看是使用的 Berkeley DB。受限于 Berkeley DB,对消息大小有一些限制——不超过 64K,但简单易用,缺点还包括缺乏复杂的消息队列特性。

2. ØMQ (ZeroMQ)

专门的消息队列实现,支持多种语言,支持较多的高级特性,也可用于进程内通信。类似于 TCP,不假设消息格式,需要用户自己处理消息封包、解包。文档很清楚,看起来很酷的样子,未调研是否支持分布式扩展。

WP Super Cache插件带来的500错误

今天博客服务器(Hostmonster 主机)全站从中午开始出现 500 错误,然后我登陆进 CPanel 各种查看日志、进程、数据库、PHP 状态,均未发现异常。后来又清理 php.ini、.htaccess,重启 PHP,也没有任何改善。只好给客服投了个 Ticket,准备等待客服解决。

后来灵机一动,发现同一主机 host 的其它 WordPress,有的活得很好,有的也是挂掉了。于是用排除法清理 wp-config.php,最终确定是 wp-config.php 中的 WP_CACHE 配置项有问题,删掉之后访问就恢复正常。

define('WP_CACHE', true); //Added by WP-Cache Manager

但由于 WP_CACHE 配置项是 WP Super Cache 自动增加的,一旦登陆进后台,WP Super Cache 就会自动把它再加上,后台页面又会出现 500 错误。于是乎我只好将整个 WP Super Cache 插件干掉(包括 wp-content 下的 php 脚本),终于一切恢复了正常。印象里删掉的 WP Super Cache 的版本是 0.9.9.*。

rm advanced-cache.php backup-*  cache/  wp-cache-config.php plugins/wp-super-cache/ -rf

考虑到 WP Super Cache 还是对性能有一定改善,又看了一下最新版的 WP Super Cache 是 1.0 版,我怀疑是 WP Super Cache 版本较旧造成的问题。虽然该版本已经使用了很长时间,不明白为什么今天才会爆出来 500 错误(也许 Hostmonster 主机程序进行了升级?),我还是装上了最新版本 WP Super Cache 插件。期望它不要再出现类似问题,否则只能弃用了。

既然我的博客不是同一主机上的个例,我想可能在 Hostmonster 上的其它主机也可能会遇到此类问题,特记录下来供参考。

64位Ubuntu上使用Network Connect

Network Connect 是 Juniper 公司出品的配合其安全硬件 VPN 解决方案的软件包,很多公司使用这个 VPN 解决方案,一般需要使用 RSA Token 动态密码登录。Network Connect 支持 Windows 和 Linux 操作系统,但很遗憾的是,它只支持 32 位 Linux。下面以 Ubuntu 为例,介绍如何

在 64 位 Linux 上安装并使用 Juniper Network Connect

1. 安装浏览器 Java 插件(64位);

$ sudo apt-get install icedtea-plugin

虽然看起来只安装了一个软件包,但实际上可能会下载依赖的 OpenJDK 的一系列软件包。这是为了在 Firefox 下能够正确启动 Network Connect 的安装过程。

2. 修改 root 密码;

$ sudo passwd

由于 Ubuntu 默认不使用 root 用户,下面自动安装 Network Connect 软件时候又必须提供 root 密码,所以这里必须先初始化 root 的密码。

3. 打开 Firefox,访问 VPN 网站。

像在 Windows 下那样,先登录进入 VPN 页面,再点击 start,启动 Network Connect 的自动安装过程。过程中会弹出一个很丑的终端,安装时需要输入 root 密码,但是最终必定是无法弹出 Network Connect 小图标,也连接不上。

4. 下载脚本 junipernc[1],并且安装到执行目录 /usr/bin 中;

$ wget http://mad-scientist.net/junipernc -O junipernc 
$ chmod 755 junipernc
$ sudo mv junipernc /usr/bin

5. 安装 Network Connect 二进制程序依赖的 32 位动态链接库;

NC 具体的可执行程序是 ~/.juniper_networks/network_connect/ncsv ,是 32 位的可执行程序。如果不安装它依赖的 32 位动态链接库[2],该程序是执行不了的。

$ sudo apt-get install libc6-i386 lib32z1 lib32nss-mdns

6. 执行 junipernc 脚本,会跳出各种对话框,对应填入各种参数;

$ junipernc --nojava

URL 就填入 VPN 网站的域名,USER 就是自己的用户名,REALM 比较麻烦,需要自己查看 VPN 网站登录页面的源代码,看对应 REALM 域实际表单提交的 value 是什么,填进去即可。

--nojava 的意思是,只执行 VPN 连接,不启动 Network Connect 小锁图标的 Java 程序。因为该 Java 程序要求 32 位 Java 环境。

连接失败会有提示;连接成功后,junipernc 会一直停在那里,终止连接可以使用 Ctrl-C 命令行,或者 sudo killall -9 ncsv。

6-1. 修改 junipernc 配置;

junipernc 有两个配置文件,一个是 ~/.vpn.default.cfg,保存着用户手工输入的配置;一个是 ~/.vpn.default.crt,这个是从网站上下载下来的证书。

这样,一般的 VPN 连接功能就实现了。如果希望启动 Network Connect 小锁图标并监控 VPN 的流量信息,就需要

在 64 位 Ubuntu 上安装 32 位 Java 环境[3]

如果不是特别需要,不建议折腾下面这套东西。

a. 到 Oracle 网站上下载 32位 Java 的 tar 包;

到这个地址:http://www.oracle.com/technetwork/java/javase/downloads/index-jsp-138363.html#javasejdk下载例如 jre-7u3-linux-i586.tar.gz 的 Linux JRE 包。重要的特征是那个 i586。

b. 解压并安装到 jvm 目录,调整默认 java 的链接到 32位 JRE。

$ tar xzvf jre-7u3-linux-i586.tar.gz
$ sudo mv jre1.7.0_03 /usr/lib/jvm
$ sudo update-alternatives --install /usr/bin/java java /usr/lib/jvm/jre1.7.0_03/bin/
java 73
$ sudo update-alternatives --config java

最后一个命令会给出一个 Java 的列表,如下所示,选择 jre1.7.0_03 对应的编号即可。

There are 2 choices for the alternative java (providing /usr/bin/java).

  Selection    Path                                      Priority   Status
------------------------------------------------------------
  0            /usr/lib/jvm/java-6-openjdk/jre/bin/java   1061      auto mode
  1            /usr/lib/jvm/java-6-openjdk/jre/bin/java   1061      manual mode
* 2            /usr/lib/jvm/jre1.7.0_03/bin/java          73        manual mode

Press enter to keep the current choice[*], or type selection number: 2

c. 验证 java 可以执行且版本正确(其实依赖上面的第 5 步);

$ java -version
java version "1.7.0_03"
Java(TM) SE Runtime Environment (build 1.7.0_03-b04)
Java HotSpot(TM) Server VM (build 22.1-b02, mixed mode)

d. 安装 32位 JRE 可能依赖的 32位动态链接库。

$ sudo apt-get install ia32-libs

这个包会依赖非常多的 32位链接库,安装过程会比较漫长。

参考文章:

[1] Using Juniper Network Connect on Ubuntu
[2] Debian6(64位)搞掂Juniper VPN
[3] Installing 32 bit java now that ia32-sun-java6-bin is not available

修改exvim目录过滤逻辑为匹配拒绝

exVim 是一个非常优秀的 Vim 环境,通过它能够省去很多 Vim 插件的配置工作。自从使用上 exVim 后,我基本没有再自定义 Vim 插件,完全依赖 exVim 打包的辅助功能。

最近让我略有不爽的使用问题是:exVim 默认的 file filter 和 dir filter 都是匹配通过的,即“匹配 filter 过滤条件的目录和文件被通过,列入项目目录、文件列表中”。

exVim 的 dir filter

对于文件来说,设置匹配通过毫无问题。因为我也想要项目中仅包含 “.cpp,.c,.h,.py” 这样的源代码文件,选出来匹配这些模式的文件就是我希望的结果。

但是对于目录来说,设置匹配通过就与我通常的需求相悖了。一般情况下,项目目录下的所有目录都是程序需要的。但是一些专门存放测试程序、测试框架、输出文件的目录,我其实不希望显示在我的项目中。而且 exVim 中的目录过滤貌似仅限在项目顶层目录中,过滤的意义不大。

所以我修改了一下 exVim 的代码,将默认的 dir filter 含义修改为匹配拒绝,即:“匹配 dir filter 的目录被拒绝(被过滤掉),无论它在哪一级。"例如,我将 dir filter 设置为 “test,output”,那么我项目目录下所有叫做 test 或者 output 的子目录都不会显示到项目目录列表中,而不妨碍其它名称目录的通过。

可以想见两个 filter 采用不同的通过逻辑并不是 exVim 开发者希望看到的,所以我想这个修改也没必要提交给开发者。不过我仍然觉得这是很有用的一个修改,所以拿出来分享一下。修改的补丁文件见:http://share.solrex.org/ibuild/exvim-dir_filter-8.05_b2.patch

PS: patch 文件中还有一个改动是将 quick_gen_project_PROJECT_autogen.sh 文件从项目目录下,移动到项目目录下的 .vimfiles.PROJECT/ 目录中,原因是看起来碍眼 :)

代码行统计工具-CLOC

在工作中有时会有需要统计代码的行数,一般会用 wc 给出一个大致的结果。只不过在源代码文件分布比较分散,且存在多种不同类型语言的源代码时,wc 就不是特别适合了。

在公司内部也见过一些同事实现类似功能的脚本,但我想这应该是一个通用的需求,于是就找到了这个工具 - CLOC。其实就是一个 perl 脚本,很好用,统计报告也很清晰。在这里推荐一下。下面是一个统计 leveldb 源代码行数的例子。

$ cloc .
     128 text files.
     123 unique files.                                          
     353 files ignored.

http://cloc.sourceforge.net v 1.55  T=0.5 s (238.0 files/s, 46718.0 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C++                             60           2012           1258          13124
C/C++ Header                    52            968           1458           2690
HTML                             3             84              0           1094
C                                1             33              7            255
make                             1             43             17            153
CSS                              1             10              1             78
Bourne Shell                     1              9             19             46
-------------------------------------------------------------------------------
SUM:                           119           3159           2760          17440
-------------------------------------------------------------------------------

epoll 事件之 EPOLLRDHUP

在对系统问题进行排查时,我发现了一个奇怪的现象:明明是对方断开请求,系统却报告一个查询失败的错误,但从用户角度来看请求的结果正常返回,没有任何问题。

对这个现象深入分析后发现,这是一个基于 epoll 的连接池实现上的问题,或者说是特性 :)

首先解释一下导致这个现象的原因。

在使用 epoll 时,对端正常断开连接(调用 close()),在服务器端会触发一个 epoll 事件。在低于 2.6.17 版本的内核中,这个 epoll 事件一般是 EPOLLIN,即 0x1,代表连接可读。

连接池检测到某个连接发生 EPOLLIN 事件且没有错误后,会认为有请求到来,将连接交给上层进行处理。这样一来,上层尝试在对端已经 close() 的连接上读取请求,只能读到 EOF,会认为发生异常,报告一个错误。

因此在使用 2.6.17 之前版本内核的系统中,我们无法依赖封装 epoll 的底层连接库来实现对对端关闭连接事件的检测,只能通过上层读取数据时进行区分处理。

不过,2.6.17 版本内核中增加了 EPOLLRDHUP 事件,代表对端断开连接,关于添加这个事件的理由可以参见 “[Patch][RFC] epoll and half closed TCP connections”。

在使用 2.6.17 之后版本内核的服务器系统中,对端连接断开触发的 epoll 事件会包含 EPOLLIN | EPOLLRDHUP,即 0x2001。有了这个事件,对端断开连接的异常就可以在底层进行处理了,不用再移交到上层。

重现这个现象的方法很简单,首先 telnet 到 server,然后什么都不做直接退出,查看在不同系统中触发的事件码。

注意,在使用 2.6.17 之前版本内核的系统中,sys/epoll.h 的 EPOLL_EVENTS 枚举类型中是没有 EPOLLRDHUP 事件的,所以带 EPOLLRDHUP 的程序无法编译通过。

Shell Tips: Unix 时间到字面

我的工作需要天天跟报表数据打交道,在交换的文件中,一般时间的字段内容都是 Unix 时间。为了检查数据的正确性,不可避免地需要转换 Unix 时间到人类可读的字面时间。

下面想分享的是一个在 Shell 下转换 Unix 时间到字面的小方法。与前面几篇一样,这个小 shell 函数仍然可以放在 ~/.bashrc 中方便快捷使用。

# 转换 Unix 时间到本地时间字符串
function ctime()
{   
    date -d "UTC 1970-01-01 $1 secs"
}

使用方法很简单:

$ ctime 1234567890
Sat Feb 14 07:31:30 CST 2009

对 date 命令熟悉的同学会说,date 不是已经有直接转 Unix 时间的参数了吗?

$ date -d @1234567890
Sat Feb 14 07:31:30     2009

但是不好意思的是,小弟有时候用的 date 程序好老,不支持 @ 符号。

$ date --version
date (coreutils) 5.2.1
Written by David MacKenzie.

Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

PS: 写完这篇博文,我又想到了一个有趣的事情,既然很多 Linux 64 位版本的 time_t 已经是 long long 格式了,那么 date 命令有没有 year 2038 问题呢?

下面是 date (coreutils) 5.2.1 在 64 位服务器上的尝试结果:

$ date +%s -d "Tue Jan 19 11:14:07 CST 2038"
2147483647
$ date +%s -d "Tue Jan 19 11:14:08 CST 2038"
2147483648
$ date +%s -d "Tue Jan 19 11:14:09 CST 2999"
32473710849
$ ctime 2147483647
Tue Jan 19 11:14:07 CST 2038
$ ctime 2147483648
Sat Dec 14 04:51:44 LMT 1901
$ ctime 32473710849
Mon Mar 28 07:33:53 LMT 1910

看来字面时间和 Unix 时间之间互转存在着问题啊!但是用 Ubuntu 11.04 的 date (GNU coreutils) 8.5 尝试就不存在这个问题了。

SHELL TIPS: rsync 和 crontab 变量

本周我遭遇了一个惨痛事件,远程开发机有两块硬盘同时损坏,整个分区数据完全丢失。这直接导致我在开发机上 home 目录中所有文件人间蒸发了,真是一觉回到解放前!

值得庆幸的是这件事发生在端午假期中间,放假前我把大部分源代码都提交到了库里,辛苦劳动的损失倒不大。但是之前种种努力搭建的开发环境全丢失了,这一点让人很郁闷。为了不再遭受这样的损失,我痛下决心学习了一下 rsync,用来同步和备份数据。

不得不说 rsync 也是一个神器啊,man rsync 发现有各种灵活用法,最有用的我觉得还是通过 ssh 来备份的方法。发现了这个秘密后,我觉得用来备份自己的网站数据也不错。下面是我使用的参数:

rsync -avzuptS --delete --max-delete=100 -e "ssh" username@solrex.org:~/ ~/backup

如果懒得输入 ssh 密码,可以使用 ssh 公钥认证

一旦配置了公钥认证,这个备份命令就可以定制为 cron 任务定时执行了。这时候我发现一个有趣的问题:如果镜像了整个 home 目录的话,无法记录命令执行日志。 因为无论日志写入到 home 目录下哪个地方,都会因为远端没有这个文件被 rsync 删除掉。无奈之下只好使用笨方法,让 cron 把同步日志发邮件给自己。

$ crontab -l
SHELL=/bin/bash
HOME=/home/work
MAILTO="someone@somesite.com"
PATH=/home/work/local/bin:/usr/local/bin:/bin:/usr/bin:/usr/X11R6/bin
00 21 * * * mirror_site

把 SHELL 配成 /bin/bash 的原因是 /bin/sh 可能会导致一些不常见的诡异问题,例如这个。同样,在 crontab 中声明 PATH 环境变量可以避免某些命令找不到的问题,特别是自己写的放在 home 目录的脚本。

Poderosa 项目复活了

Poderosa截图,图片来自官网
Poderosa 截图

四年之前我就开始关注 Poderosa 这个项目,因为我认为它是我能找到的最好的 Cygwin 终端客户端——没有之一。当然,如果你把它当做 ssh 客户端去跟其它软件比,你就输了。

由于它在 2006 年 11 月以后再也没有更新过新版本,两年前,我曾经因为它有了一个“同人” 2009 特别版 而激动不已。

前两天,我偶尔去逛论坛,居然发现这个项目复活了!作者在开放讨论区里面声明发布了 4.3.0b,真是太让人兴奋了!

令人奇怪的是,xjzhang1979 君虽然提供了 N 个 Poderosa 特别版升级版本,但从来没有释出过源代码,看起来也没有打算这样做。作者 kzmi这里也提到:

5.7.x has more new features, but their source code has not been disclosed.

4.3.x are developed on the Poderosa project and you can get their source code.
Some features from 5.7.x were added to 4.3.x.
...
I believe that the terminal emulation of 4.3.x would be better than 5.7.x's.

由于 5.7.x 不开放的源代码,相比 4.3.x 而言用户肯定对其安全性有一定怀疑。现在有了更好选择,恐怕特别版的拥护者会越来越少了。这真的让人很遗憾!

更新 JabRef 2.7 中文版

JabRef 的中文版是我翻译的。但是好久没有关注邮件列表,偶然瞄到才发现又有新增的部分需要翻译。于是今天就花了些时间更新了一下中文翻译,将会集成到 JabRef 的 2.7 版本中。“抢先版”请看这里 ^_^

另外,在我 Windows 平台下的 JabRef 2.6 以后版本中,列表页中文文献名都显示为方框,由于下方细节中有正确显示,我也就没管它。但是 Linux 下却显示正常,这点让我比较好奇。今天才发现 Windows 平台下需要设置列表页字体为中文字体才能正确显示。这样看原来的显示正常到方框,大概与 Java 不同版本的默认字体设置有关系。

再另外,sourceforge 的 svn checkout 速度可是真慢啊!不知道是不是帝国的网络条件导致的。

Shell Tips: 用GNU Screen实现发送交互到所有会话

服务器冗余和分拆是互联网服务中经常用来缓解访问压力的手段,那么检查或者管理多台同构服务器也是互联网行业工程师们绕不开的操作。经常面临的问题是:如何高效地在多台服务器上执行相同的命令,进行批量系统操作或问题检查。

Windows 下的 ssh 客户端 XShellSecureCRT 都提供了类似的功能,当每个标签页都连接到一个服务器时,可以在命令窗口中发送交互到所有的标签页以实现同时操作多台服务器的目的。这招我还是从 OP 那里学来的,的确大大提高了生产力。

但这种方法也存在一些问题:

  1. 只适用于特定的 ssh 客户端。例如对 Linux 来说就有些不适用,不过据说 Konsole 也提供了类似功能,未验证。
  2. 每个标签页中,还是得一台一台地登陆上服务器,很难自动化。据说有的客户端支持编写脚本实现,但还要学习对应脚本语言,且灵活性有限。
  3. 无法一直保持持续的连接。特别是对有开发机的工程师,本来开发机是一直在线的,但由于客户端的限制,只能在本地电脑连接多服务器。当本地网络断开后,自然多服务器的连接也断开了。

为了解决这些问题,小弟想到了神器 GNU Screen。Screen 也是终端,难道无法做这件事吗?您还别说,在我费心劳力一上午之后,总算摸索出了用 Screen 解决上述问题的方法。下面两个可以放到 ~/.bashrc 中的函数,就是我心血的“结晶” :)

function screenssh ()
{
    local username=YOUR_USERNAME
    local password=YOUR_PASSWORD
    local server=''
    local timeout=3
    for server in $@; do
        screen -S $STY -X screen ssh $username@$server
    done
    sleep $timeout
    local cmd="screen -S $STY -X at ssh# stuff $'$password\n'"
    eval $cmd
}

function lets ()
{
    local cmd="screen -S $STY -X at ssh# stuff $'$1\n'"
    eval $cmd
}

Screen 的用法和技巧,在我之前的文章中也有提及,此处不再赘述。这里主要介绍一下上面两个函数的作用和用法:

screenssh 是在 screen 中自动登陆多台服务器的命令。这个 bash 函数接受服务器列表作为输入,执行后会在当前 screen 中为每个服务器打开一个 window,并使用提供的用户名和密码登陆这些服务器。这样当前 screen 中就会多出 N 个 window,分别对应登陆到 N 个服务器。在使用前,你要修改用户名、密码变量值为你需要的内容,而且该命令必须在 screen 中执行,在 screen 外执行是无效的。

执行完 screenssh 后,就可以祭出 lets 命令来在多个 window 中同时执行操作命令了。lets 接受一个字符串作为输入,执行后该字符串会作为命令发送到 N 个服务器对应的 N 个 windows 中执行。

看完以后令人困惑的地方可能是,我到底应该在哪里执行 screenssh 和 lets 这两个命令呢?下面用一个例子来更直白地阐述一下这两个命令的使用方法。

假设你需要在 3 台服务器:s1.solrex.org, s2.solrex.org, s3.solrex.org 上执行 grep FATAL ~/error_log 查看错误日志。那么你应当:

1. $ screen -S admin
# 首先创建一个 screen,这时候你有了 0 号 window;
2. $ screenssh s1.solrex.org s2.solrex.org s3.solrex.org
# 在 0 号 window 中执行 screenssh 命令,自动打开 3 个 window,连接到三个不同的服务器;
3. $ lets "grep FATAL ~/error_log"
# 在 0 号 window 中执行 lets,将命令自动分发到 3 台服务器上执行;
4. ctrl-a N 切换到不同的 window 查看命令的执行情况;
5. ctrl-a 0 切换到 0 号 window 执行下一条批量命令;

下面我们再回顾一下上文中提到的 3 个问题是否解决了:1. GNU Screen Linux 一般均自带,不存在专用客户端问题;2. screenssh 解决了自动化登陆多台服务器问题,且服务器列表作为参数,非常灵活且易定制;3. 开发机上运行的 screen 保证了客户端离线连接不断。

Shell Tips: cppath、scppath、mybackup

分享几个觉得有用的小 shell 函数。

1. scppath

在进行一些跨机器的操作时,每次 scp 总要手动去拼那个路径,首先从 PS1 拷贝粘贴用户名和主机名,然后再 pwd 拷贝粘贴当前目录,然后再 ls 拷贝粘贴要 scp 的文件名。好烦啊,所以就写了下面这个小函数来生成 scp 的文件路径,放到 ~/.bashrc 里。

function scppath()
{
    local _IFS=$IFS
    IFS=$(echo -en "\n\b")
    local _file
    for _file in $@; do
        echo "\"$USER@$HOSTNAME:$PWD/$_file\""
    done
    IFS=$_IFS
}

2. cppath

同样可以有 cppath。

function cppath()
{
    local _IFS=$IFS
    IFS=$(echo -en "\n\b")
    local _file
    for _file in $@; do
        echo "\"$PWD/$_file\""
    done
    IFS=$_IFS
}

3. mybackup

这个函数是偷懒备份用的。当写代码写到一半,不想或者不能 check in,但又想备份一下时,就用这个命令对文件或者目录进行自动的备份。

function mybackup()
{
    local _bak_dir=~/history
    local _path=''
    mkdir -p $_bak_dir
    local _IFS=$IFS
    IFS=$(echo -en "\n\b")
    for _path in $@; do
        if [ -f $_path ]; then
            cp $_path $_bak_dir/"$_path".`date +%Y-%m-%d.%H-%M-%S`
        elif [ -d $_path ]; then
            _path=`basename $_path`
            tar -cvf $_bak_dir/$_path.`date +%Y-%m-%d.%H-%M-%S`.tar $_path
        fi 
        echo "Backuped $_path to $_bak_dir."
    done
    IFS=$_IFS
}

Infobright 数据仓库

最近有部分工作涉及到了 Infobright 数据仓库,就浏览了一些相关的资料,感觉很受启发。下面写一些感想,如有谬误,还请指正。

简单的来讲,Infobright 主要有下面的一些优点:

1. TB 级的数据存储和高效查询。大数据量存储主要依赖自己提供的高速数据加载工具(百G/小时)和高数据压缩比(>10:1),高效查询主要依赖特殊设计的存储结构对查询的优化,但这里优化的效果还取决于数据库结构和查询语句的设计。

2. 高数据压缩比,号称一般能够达到 10:1 以上的数据压缩率。高数据压缩比主要依赖列式存储和 patent-pending 的灵活压缩算法。

3. 与主要 BI 分析工具的兼容性。兼容性这点主要依赖与 MySQL 的集成,作为 MySQL 的存储引擎自然地能够保证与 BI 分析工具的兼容。

除了上面的优点外,它也有一些限制:

1. 不支持数据更新。这使对数据的修改变得很困难,这样就限制了它作为实时数据服务的数据仓库来使用。用户要么忍受数据的非实时或非精确,这样对最(较)新数据的分析准确性就降低了许多;要么将它作为历史库来使用,带来的问题是实时库用什么?很多用户选择数据仓库系统,不是因为存储空间不够,而是数据加载性能和查询性能无法满足要求。

2. 不支持高并发。虽然单库 10 多个并发对一般的应用来说也足够了,但较低的机器利用率对投资者来说总是一件不爽的事情,特别是在并发小请求较多的情况下。

3. 没有提供主从备份和横向扩展的功能。如果没有主从备份,想做备份的话,也可以主从同时加载数据,但只能校验最终的数据一致性,这会使得从机在数据加载时停服务的时间较长;横向扩展方面,倒不是 Infobright 的错,它本身就不是分布式的存储系统,但如果把它搞成一个分布式的系统,应该是一件比较好玩的事情。

在架构方面,Infobright 给我展示了不少新想法,算是受益颇多吧。首先是按列存储,然后把列数据切成小块(Data Pack),进行压缩和统计(DPN, Data Pack Node),然后再对多块数据之间进行知识关联(Knowledge Node),最后对整个表形成知识网格(Knowledge Grid)。虽然说 Infobright 没有提供索引结构,但它 Knowledge Grid 中的 Numerical Histogram、Character Map 和 Pack-to-Pack 结构,怎么看都和 bitmap 索引脱不了关系。只是它的组织形式不像传统数据库中的索引罢了。

其实我们在设计类似的分布式表格系统时,也可以实现类似于 Knowledge Grid 的结构。这个结构未必跟 Infobright 的一样,但是如果在压缩的基础上,基于系统查询模式(分布式系统的查询模式一般相对简单,复杂的也做不来),存储一些辅助的块统计信息以及块之间的关联信息,对于减少查询的资源消耗,提高查询效率会非常有帮助,这也正好是针对分布式表格系统很难建立索引这一缺点的弥补。

参考链接:

这篇文章对 Infobright 及其安装方法进行了基本介绍,最后的一个查询速度对比有些夸张(105:1),我觉得这可能跟查询条件正好能匹配上 Knowledge Grid 中的信息所致;这个博客很有趣,从 2010 年 3 月 8 日到 5 月 8 日之间的文章全是 Infobright 相关的,写的还是挺详细的;Brighthouse: An Analytic DataWarehouse for Ad-hoc Queries 是一篇相关的 08 年 VLDB paper;此外官网上的白皮书不能直接下载,但在搜索引擎中能搜到一些。

在 shell 脚本里打日志

今天小弟在重构代码中的一个脚本模块,其中涉及到日志功能。上午花了点儿时间想出了个在 shell 打日志的技巧,觉得值得写一下。

希望要实现的效果是:实现一个 write_log 命令,给一条出错消息作为输入,write_log 记录日志时自动加上 时间戳、脚本文件名和行号。形如:

2010-12-17 19:13:44 [work.sh:24] FATAL: mkdir -p /x.

时间戳、脚本文件名都好获得,但是行号就没那么容易实现了。shell 中的 $LINENO 变量只能展开成当前行的行号,如果把 write_log 实现成函数的话,势必在函数中无法使用 $LINENO。

开始我想了好大一会儿,觉得 eval 能干这个事情。但是如果用 eval 的话,还不如直接把 $LINENO 传给 write_log 函数呢,与我的初衷不是太相符。我拉来同事讨论了一把,也没解决问题。正当我准备放弃了,计划每次传 $LINENO 参数时,忽然想起来,怎么把 alias 给忘了呢?

于是,write_log 的实现就是这个样子了:

function _write_log()
{
  if [ $# -eq 2 ]; then
    if [ -z $LOGFILE ]; then
      echo "$(date "+%Y-%m-%d %H:%M:%S") [$0:$1] $2"
    else
      echo "$(date "+%Y-%m-%d %H:%M:%S") [$0:$1] $2" >> $LOGFILE
    fi
  elif [ $# -eq 1 ]; then
    if [ -z $LOGFILE ]; then
      echo "$(date "+%Y-%m-%d %H:%M:%S") [$0] $1"
    else
      echo "$(date "+%Y-%m-%d %H:%M:%S") [$0] $1" >> $LOGFILE
    fi
  else
    return 1
  fi
}
alias write_log='_write_log $LINENO' # 这里必须使用单引号

存在的问题是:上面这段代码在 bash 里是不工作的,但是用 sh 可以——即使 sh 也是链接到 bash 的。问题出在 alias 上,可以把问题简化成这样,有一个脚本 a.sh:

$ cat a.sh
alias lss='ls -l'
lss /tmp

这个脚本用 /bin/sh 执行是这样的:

$ sh a.sh 
total 8
drwx------ 2 gdm gdm 4096 2010-12-17 19:34 orbit-gdm
drwx------ 2 gdm gdm 4096 2010-12-17 11:04 pulse-PKdhtXMmr18n

用 /bin/bash 执行是这样的:

$ bash a.sh 
a.sh: line 2: lss: command not found

把 bash 随便 link 成一个叫 sh 的链接文件,再执行是类似这样的:

$ ln -s /bin/bash ~/sh
$ ~/sh a.sh 
total 8
drwx------ 2 gdm gdm 4096 2010-12-17 19:34 orbit-gdm
drwx------ 2 gdm gdm 4096 2010-12-17 11:04 pulse-PKdhtXMmr18n

这个问题肯定是有原因的,我不愿意去翻 bash 源代码,也不知道哪里去找答案,所以我放弃了,直接在文件头加上

#!/bin/sh

如果哪位兄台知道这种“奇怪”现象的原因所在,请不吝赐教 :)

Linux screen窗口中文乱码问题

环境:Linux Dist: CentOS 4.3,locale: en_US.UTF-8, .vimrc: set fencs=gbk

目标:终端使用 less/more/grep 等命令正确显示 GBK 编码文件内容,vim 正确显示 GBK 编码文件汉字

症状:

1. 系统自带 gnome-terminal 在设置终端编码为 GBK 后,能达到目标。

2. 使用 xshell 在 windows 平台上设置终端编码为 default 时,ssh 登录到 CentOS,能达到目标。

3. 在 screen 命令窗口内,无论终端还是 vim, 中文均显示为乱码,无法达到目标。

解决办法:在 ~/.screenrc 中,添加下面两句:

defencoding GBK
encoding UTF-8 GBK

我的猜测是 xshell、gnome-terminal 等终端能够将自身编码传给系统,因此系统能够对输出自动进行转码。而 screen 属于终端中的终端,它自身的编码不是 GBK,导致传给系统以后没有对输出进行转码。设置 screen 的编码和转换规则后,就 OK 了。

WordPress博客评论合并工具

上篇,这里共享我写的一个用来合并 WordPress 博客评论的小工具。该工具可以将两个镜像 WordPress 博客上对同一篇文章的评论合并起来。

下面先介绍合并的步骤:

1. 首先到这里下载我修改的 WordPress 导入插件,并按照安装一般 WordPress 插件的方式,安装并启用该插件。

2. 然后在 WP 管理后台选择“工具->导入->WordPress”,然后上传从镜像 WP 博客导出的 xml 文件。

3. 在下一步选择“Only Merge Comments” 很重要!!!

Wordpress博客评论合并工具

4. submit,稍等片刻即可。

其实我没有重新制造轮子,只是修改了一下 WordPress 默认的博客导入工具 WordPress Importer,给它加了点儿功能。只要选中“Only Merge Comments”,使用这个工具是很安全的,它只会将 xml 中与当前博客中存在的文章对应的评论添加上去,而不处理任何不存在的文章,也不会重复添加已有的评论,而且会过滤某些垃圾评论。用这个选项,你可以重复导入很多次 :)

可能的缺陷有:这个工具判断文章是否存在的唯一标准是文章标题,因此如果有多篇文章标题一样,可能会存在问题(未测试)。本人不保证它是充分测试的,因此在应用之前最好还是在本地的镜像测试后进行;如果没有进行测试,请一定在合并之前对博客进行备份

下面是我修改的 patch:

--- wordpress-importer/wordpress-importer.php    2010-06-02 00:38:23.000000000 +0800
+++ ../../www/blog/wp-content/plugins/wordpress-importer/wordpress-importer.php    2010-09-29 19:33:57.953790929 +0800
@@ -49,2 +49,3 @@
     var $fetch_attachments = false;
+    var $only_merge_comments = false;
     var $url_remap = array ();
@@ -258,2 +259,7 @@

+<h2><?php _e('Only Merge Comments', 'wordpress-importer'); ?></h2>
+<p>
+    <input type="checkbox" value="1" name="comments" id="merge-comments" />
+    <label for="merge-comments"><?php _e('Only merge comments, ignore post, tags...', 'wordpress-importer') ?></label>
+</p>
<?php
@@ -483,3 +489,7 @@

-        $post_exists = post_exists($post_title, '', $post_date);
+        if ($this->only_merge_comments) {
+            $post_exists = post_exists($post_title, '', '');
+        } else {
+            $post_exists = post_exists($post_title, '', $post_date);
+        }

@@ -489,4 +499,7 @@
             $comment_post_ID = $post_id = $post_exists;
-        } else {
-
+        } else if ( $this->only_merge_comments) {
+            echo '<li>';
+            printf(__('Post <em>%s</em> not found, comments not updated.', 'wordpress-importer'), stripslashes($post_title));
+            $comment_post_ID = $post_id = $post_exists;
+        } else {
             // If it has parent, process parent first.
@@ -605,3 +618,11 @@
                 // if this is a new post we can skip the comment_exists() check
-                if ( !$post_exists || !comment_exists($comment['comment_author'], $comment['comment_date']) ) {
+                if ($this->only_merge_comments) {
+                    if ( $post_exists && !comment_exists($comment['comment_author'], $comment['comment_date']) && $comment['comment_author'] != 'Unknown') {
+                        if (isset($inserted_comments[$comment['comment_parent']]))
+                            $comment['comment_parent'] = $inserted_comments[$comment['comment_parent']];
+                        $comment = wp_filter_comment($comment);
+                        $inserted_comments[$key] = wp_insert_comment($comment);
+                        $num_comments++;
+                    }
+                } else if ( !$post_exists || !comment_exists($comment['comment_author'], $comment['comment_date']) ) {
                     if (isset($inserted_comments[$comment['comment_parent']]))
@@ -847,5 +868,7 @@
         $this->get_entries();
-        $this->process_categories();
-        $this->process_tags();
-        $this->process_terms();
+        if ($this->only_merge_comments) {
+            $this->process_categories();
+            $this->process_tags();
+            $this->process_terms();
+        }
         $result = $this->process_posts();
@@ -891,2 +914,4 @@
                 $fetch_attachments = ! empty( $_POST['attachments'] );
+                $only_merge_comments = ! empty( $_POST['comments'] );
+                $this->only_merge_comments = (bool) $only_merge_comments;
                 $result = $this->import( $_GET['id'], $fetch_attachments);

Fastbit中的bitmap索引算法

摘要:bitmap 索引是一种典型的数据库索引方案,本文基于 Fastbit 软件包,使用实际用例对一些常用的 bitmap 索引算法进行了一个较为系统的介绍。

一、Fastbit是什么?

引用 Fastbit 的官方网站上的介绍:Fastbit是一个追随 NoSQL(Not Only SQL) 运动精神的开源的数据处理程序库,它提供了一系列的用压缩的 bitmap 索引支持的查询函数。在这里,我们关注的关键词是“bitmap 索引”。Fastbit 使用的是按列存储方式,其 bitmap 索引也是在按列存储的数据上建立起来的。

二、Fastbit 中的 bitmap 索引算法

Fastbit 的源代码有着非常清晰的结构。在 Fastbit 的源代码中,每个索引算法都用一个 C++ 类来实现,所有的索引算法类都是基类 index 的派生,并且在 fastbit 源代码中保存为以 i 开头的源文件。

下面是 Fastbit 中的索引类的派生关系图,从美观考虑,直接使用 xmind 思维导图而不是 UML 来展现了:

fastbit 索引算法派生关系图

下面我们将对其中部分算法进行简单的介绍。我们将这些索引算法分为几大类:基础算法、扩展算法、多层算法和多成分算法。

三、基础 bitmap 索引算法

基础的 bitmap 索引算法是最简单的 bitmap 索引算法,给出了 bitmap 索引的基本原理。

3.1 relic

relic (定义在 irelic.h 中,实现在 irelic.cpp ) 是最原始的 equality-encoded 算法,这个单词代表“遗迹”的意思。它可谓是最简单直观的 bitmap 索引算法。relic 为需要索引的每个值都建立一个 bitvector,在该 bitvector 中,只有等于该值的列才会被置 1,其它位都被置 0,如下表所示:

数据 索引(bitmap)
a b d e g
a 1 0 0 0 0
g 0 0 0 0 1
d 0 0 1 0 0
e 0 0 0 1 0
b 0 1 0 0 0
d 0 0 1 0 0
g 0 0 0 0 1
e 0 0 0 1 0
3.2 bin

bin (定义于 ibin.h,实现在 ibin.cpp)是 binned equality-encoded 算法,这里它代表“桶”的意思。它可以视为是 relic 的一种变形,它将值域分为几个不相交的区间,将原本是相等才置一的规则转变为值落在该区间内就置一,如下表所示。当然,relic 也可以视为 bin 的一个特例(将区间定义为 [a, a+ε)。bin 每个区间的范围由程序遵从某些规则设定,这些规则由命令行通过参数传入。

数据 索引(bitmap)
(…,b) [b,e) [e,…)
a 1 0 0
g 0 0 1
d 0 1 0
e 0 0 1
b 0 1 0
d 0 1 0
g 0 0 1
e 0 0 1
3.3 bin->range

range (定义于 ibin.h,实现于 irange.cpp)是 range-encoded 算法,这里它代表“范围”的意思。正如它字面所表达的意思,range 的每个 bitvector 标记着小于某边界值的值,如下表所示。因此,它可以视为是 bin 的一个累积表示,这也是 fastbit 软件包中所做的:首先构造 bin,然后累加转换成 range。值得注意的是,一般最后一列代表着小于无穷大,因此该 bitvector 全为 1,会被略去不写。

数据 索引(bitmap)
(…,b) (…,e) (…,g)
a 1 1 1
g 0 0 0
d 0 1 1
e 0 0 1
b 0 1 1
d 0 1 1
g 0 0 0
e 0 0 1
3.4 bin->mesa

mesa (定义于 ibin.h,实现于 imesa.cpp)是 interval-encoded 算法[1],它与 bin 类似,只不过它的区间之间有重叠部分。与 range 相同,在 fastbit 软件包中,它也是通过 bin 构造起来的。

数据 索引(bitmap)
(…,d) [a,e) [b,g) [d,…)
a 1 1 0 0
g 0 0 0 1
d 0 1 1 1
e 0 0 1 1
b 1 1 1 0
d 0 1 1 1
g 0 0 0 1
e 0 0 1 1

四、扩展 bitmap 索引算法

4.1 direkte

direkte (定义于 idirekte.h,实现于 idirekte.cpp)是丹麦语中的 direct,它与 relic 几乎是一样的,不同点只是它为小于最大值的所有值都建立了一个 bitvector(即使该值并不存在于列中)。

数据 索引(bitmap)
a b c d e f g
a 1 0 0 0 0 0 0
g 0 0 0 0 0 0 1
d 0 0 0 1 0 0 0
e 0 0 0 0 1 0 0
b 0 1 0 0 0 0 0
d 0 0 0 1 0 0 0
g 0 0 0 0 0 0 1
e 0 0 0 0 1 0 0
4.2 relic->slice

slice(定义于 irelic.h,实现于 islice.cpp)实现了 O'Neil'97 [2] 提出的 bit-slice 算法。它的基本思想就是首先将原始数据用二进制进行编码,bitmap 就是所有值的二进制编码表示的集合,bitvector 的个数由最大值的二进制表示决定,如下表所示:

数据 编码 索引(bitmap)
a 0 0 0 0
g 4 1 0 0
d 2 0 1 0
e 3 0 1 1
b 1 0 0 1
d 2 0 1 0
g 4 1 0 0
e 3 0 1 1
4.3 bin->bak

bak (定义于 ibin.h,实现于 idbak.cpp)是丹麦语中的 bin,因此它是 bin 的变形。它使用减精度来表示 bin 区间的中心,即它的每一个区间都是用一个更低精度的数来表示,具体来说就是四舍五入啦。下面是一个对 1-100 的数据列建立 bak 索引的输出,其中第一列表示区间的中心,第二三列代表区间最小最大值,第四列代表该区间内数据的个数:

index (equality encoding on reduced precision values) for data.a contains 19 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  14  5
20  15  24  10
30  25  34  10
40  35  44  10
50  45  54  10
60  55  65  11
70  66  74  9
80  75  84  10
90  85  94  10
100 95  100 6
4.4 bin->bak2

bak2 (定义于 ibin.h,实现于 idbak2.cpp)是 bak 的变形,也是以减精度来表示区间。但与 bak 不同的是,它将 bak 的每个区间区分为两个区间:小于减精度数的区间,和大于等于减精度数的区间。虽然注释中这样说,但实现时 bak2 是将 bak 的区间分为了三个:小于、等于和大于。下面是一个对 1-100 的数据列建立 bak2 索引的输出,每列的含义与 bak 中示例相同:

index (equality encoding on reduced precision values) for data.a contains 37 bitvectors for 100 objects
1   1   1   1
2   2   2   1
3   3   3   1
4   4   4   1
5   5   5   1
6   6   6   1
7   7   7   1
8   8   8   1
9   9   9   1
10  10  10  1   
10  11  14  4   
15  15  19  5
20  20  20  1
20  21  24  4
25  25  29  5
30  30  30  1
30  31  34  4
35  35  39  5
40  40  40  1
40  41  44  4
45  45  49  5
50  50  50  1
50  51  54  4
55  55  59  5
60  60  60  1
60  61  65  5
66  66  69  4
70  70  70  1
70  71  74  4
75  75  79  5
80  80  80  1
80  81  84  4
85  85  89  5
90  90  90  1
90  91  94  4
95  95  99  5
100 100 100 1

除了上面几个算法之外,扩展的算法还有 roster 和 keywords,这两种算法比较复杂,这里就不示例讲解了。

五、多层 bitmap 索引算法

有了几个基础的 bitmap 索引算法,我们就可以考虑将这些算法组合成一个层次的结构,构造出多层的 bitmap 索引算法。下面的几个算法,即是由前面的基础 bitmap 索引算法构造出来的二(多)层 bitmap 索引算法。

5.1 bin->ambit

ambit(定义于 ibin.h,实现于 ixambit.cpp)是 multilevel-range based算法,在这个算法中索引分为多层,每层索引都是基于 range 的索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 ambit。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则由一简单算法确定,确定分组个数的算法为(第一个桶不参与分组):

ixambit.cpp:
33     // the default number of coarse bins is determined based on a set
34     // of simplified assumptions about expected sizes of range encoded
35     // bitmaps and word size being 32 bits.
36     const uint32_t defaultJ = static_cast
37         (nbins < 100 ? sqrt((double)nbins) :
38          0.5*(31.0 + sqrt(31.0*(31 + 4.0*nbins))));

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 ambit:

ambit 索引

5.2 bin->pale

pale(定义于 ibin.h,实现于 ixpale.cpp)是 two-level binned equality-range算法,它的索引分为两层,第一层为 binned equality(bin) 索引,第二层为 range 索引。在具体实现时,pale 首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 pale。与 ambit 相同,分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当 bin 桶数大于31时,默认第一层为16个组:

ixpale.cpp:
45     else { // default -- 16 coarse bins
46         if (nbins > 31) {
47         j = 16;
48         }
49         else {
50         j = nbins;
51         }
52     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pale:

pale 索引

5.3 bin->pack

pack(定义于 ibin.h,实现于 ixpack.cpp)是 two-level binned range-equality 算法。它的索引分两层,与 pale 相反,第一层为 range 索引,第二层为 binned equality(bin) 索引。具体实现时,fastbit 首先构造 bin,然后对桶进行分组(调用bin::divideBitmaps),然后构造 pack。分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于63时,默认第一层为31个组:

ixpack.cpp:
44     else { // default -- 31 coarse bins
45         if (nbins > 63) {
46         j = 31;
47         }
48         else {
49         j = nbins;
50         }
51     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 pack:

pack 索引

5.4 bin->zone

zone(定义于 ibin.h,实现于 ixzone.cpp)是 two-level binned equality-equality 算法,它的索引分两层,两层均为 binned equality(bin) 索引。它的实现方式也是首先构造 bin,然后对桶进行分组(调用 bin::divideBitmaps),然后构造 zone。其分组粒度可以由命令行传入参数 ncoarse=x 和/或 nrefine=n 指定,否则当bin桶数大于31时,默认第一层为14个组:

ixpack.cpp:
46     else { // default -- 14 coarse bins
47         if (nbins > 31) {
48         j = 14;
49         }
50         else {
51         j = nbins;
52         }
53     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 zone:

zone 索引

5.5 bin->fuge

fuge(定义于 ibin.h,实现于 ixfuge.cpp)是 two-level binned interval-equality 算法,fuge 为德语中 interstice 的表述。fuge 的索引分两层,第一层为 interval(mesa) 索引,第二层为 binned equality(bin) 索引,它也是采用首先构造 bin,然后基于 bin 构造 fuge 的方式。其分组粒度由 ncoarse=x 指定,否则默认的分组个数由下面算法确定:

ixfuge.cpp:
887     // default size based on the size of fine level index sf: sf(w-1)/N/sqrt(2)
...
899     if (ncoarse < 5U && offset32.back() >
900     offset32[0]+static_cast(nrows/31)) {
901     ncoarse = sizeof(ibis::bitvector::word_t);
...
913     else {
914         ncoarse = ncmax;
915     }
916     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 bin,右侧是基于该 bin 构造的 fuge:

fuge 索引

5.6 relic->bylt

bylt(定义于 irelic.h,实现于 ixrelic.cpp)是 two-level unbinned range-equality 算法,bylt 是丹麦语的 pack(binned 版本算法)。bylt 索引分两层,第一层为 range 索引,第二层为 unbinned equality(relic) 索引。在实现时首先构造 relic,然后对桶进行分组(调用bin::divideBitmaps),然后构造 bylt。分组粒度可以由 ncoarse=x 指定,bylt 保证每组中桶数是大致均匀的,否则由下面算法决定分组的个数:

ixbylt.cpp:
182     // default size based on the size of fine level index sf:
183     // (w-1) * sqrt(sf*(sf-N/(w-1))) / (2N)
184     if (ncoarse < 5U && offset64.back() > offset64[0]+(int32_t)(nrows/31U)) { 
185     ncoarse = sizeof(ibis::bitvector::word_t);
     const int wm1 = ncoarse*8-1;
...
199         ncoarse = ncmax;
200     }
201     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 bylt:

bylt 索引

5.7 relic->fuzz

fuzz(定义于 irelic.h,实现于 ixfuzz.cpp)是two-level unbinned interval-equality 算法,即 fuge 的 unbinned 版本,名字起源于 fuzzy 聚类/分类。fuzz 索引分两层,第一层为 interval(mesa) 索引,第二层为 unbinned equality(relic) 索引,具体实现时 fastbit 也是采用首先构造 relic,然后构造 fuzz 的方式。其分组粒度可以由 ncoarse=x 指定,否则默认分组个数由下面算法确定:

ixfuzz.cpp:
168     // default size based on the size of fine level index sf: sf(w-1)/N/        sqrt(2) 
169     if (ncoarse < 5U && offset64.back() > offset64[0]+nrows/31U) {
170     ncoarse = sizeof(ibis::bitvector::word_t);
...
182     else {
183         ncoarse = ncmax;
184     }
185     }

下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 fuzz:

fuzz 索引

5.8 relic->zona

zona(定义于 irelic.h,实现于 ixzona.cpp)是 two-level unbinned equality-equality 算法,zona 是丹麦语的zone(binned 版本算法),其索引分两层,两层均为 unbinned equality(relic) 索引。首先构造 relic,然后对桶进行分组构造zona,分组个数默认为11个。下面看一个实际的例子,左侧是对 1-100 的数据列构造的 relic,右侧是基于该 relic 构造的 zona:

zona 索引

六、多成分 bitmap 索引

多成分(multi-component)bitmap 索引[3]是使用一组基数将数据值分解成多个部分,分别对每个部分进行 bitmap 索引的方案。原理描述如下:给定 n-1 个基数 { bn-1, bn-2, ..., b1},那么一个值 v 可以通过下式分解为 {vn, vn-1, ..., v1}:

数据值的分解

这和数的表示法类似,如果令 bi 都是 10,那么 vi 就是十进制表示法中第 i 位的值(大于等于0,小于10)。更准确的表述可以参考[3]。下面我们来看 fastbit 中的几个实现。

6.1 relic->fade

fade(定义于 irelic.h,实现于 ifade.cpp)是 multicomponent range-encoded 算法,即在每个部分中,是使用的 range 索引。下面来看一个 range-encoded 的例子:

fade 索引

在(b)图中,选择的基数是 9,那么索引就变成了一个单成分的 range 索引算法;在(c)图中,选择的基数是 <3, 3> 这样一个双成分编码,对分解出来的每个成分(大于等于0,小于3)生成 range 索引,就得出了 (c) 图中的结果。

6.2 relic->fade->sapid

sapid(定义于 irelic.h,实现于 isapid.cpp)是 multicomponent equality-encoded 算法,即在每个部分中是使用的 equality(relic) 索引。下面来看一个 equality-encoded 的例子:

sapid 索引

在(b)图中,选择的基数是 <3, 4> 这样一个双成分编码,对分解出来的每个成分生成 relic 索引,就得到了 (b) 图中的索引结果。

除了这两个索引算法之外,还有 sbiad(multicomponent interval-encoded),egale(multicomponent equality code on bins), entre(multicomponent interval code on bins), moins(multicomponent range code on bins)这几个索引算法。从括号中我们可以大致猜出这些索引的实现方式,但是由于我们现在没有一个很好的示例展现方式,用实际用例来展现这些索引算法的效果将会留给以后的文章进行。

七、总结

这篇文章基于 fastbit 软件包,加以实际的用例对常用的 bitmap 索引算法进行了一个较为系统的介绍。不过生成 bitmap 索引仅仅是第一步,bitmap 索引在存储时会有很大的开销,在不损害(较少损害)查询效率的情况下,对 bitmap 索引进行有效的压缩是一个非常有挑战性的课题。除了 bitmap 索引的生成和存储之外,在不同类型的 bitmap 索引上实现高效的各种类型的查询,也是一个值得进一步探讨的问题。我们很高兴地看到 fastbit 软件包实现了很多这些相关领域的算法,为我们提供了非常宝贵的资料。

参考文献

[1] C-Y. Chan and Y. E. Ioannidis, An efficient bitmap encoding scheme for selection queries, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1999.
[2] P. O’Neil and DalIan Quass, Improved Query Performance with Variant Indexes, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1997.
[3] C-Y. Chan and Y. E. Ioannidis, Bitmap Index Design and Evaluation, in Proceedings of the ACM international conference on Management of data (SIGMOD), 1998.

Shell Tips: GNU Screen 的一些小技巧

由于工作环境的问题,最近越来越感觉到 screen 命令的可贵,下面总结一点使用 screen 命令的小技巧。

最常用的参数组合:

screen -ls // 列出已有的 screen
screen -D -R // 进入指定的 screen 名,如果没有,则以该名称创建 screen

由于很常用,我把这两个命令取了个 alias:

alias sl='screen -ls'
alias sr='screen -D -R'

除了命令之外,还有快捷键 Ctrl+ac 创建 screen;Ctrl+aa 在两个 screen 之间相互切换;Ctrl+ad 从 screen 中 detach;Ctrl+a数字,跳转到数字指代的 screen。

在 screen 最下方显示状态栏,状态栏包括已经打开的 screen 标签列表,当前的 screen 和时间。其中在 screen 标签处显示该 screen 所处的目录名。显示 screen 所处的目录名这一点实现起来要困难一些,首先得修改 .bashrc,加入 screen term 对应的信息

case $TERM in
    screen*)
        # This is the escape sequence ESC k \w ESC
        # Use current dir as the title
        SCREENTITLE='\[\ek\W\e\\\]'
        PS1="${SCREENTITLE}${PS1}"
        ;;
    *)
        ;;
esac

然后 . 或者 source 一下,再修改 screen 的配置文件,添加状态栏,在 .screenrc 中添加:

caption always '%{=b cw}%-w%{=rb db}%>%n %t%{-}%+w%{-b}%< %{= kG}%-=%D %c%{-}'
shelltitle '$ |bash'

最终效果为:

GNU Screen 多标签状态栏

删除 MBR 引发的诡异问题

我要跟女友交换一下笔记本电脑,她不常用 Linux,而我的 Ubuntu 分区占了好几十 G 空间,因此我想还是删了再给她吧。

我的电脑有两个系统:Windows Server 2008 和 Ubuntu 10.04。按照惯常的思维,删除 Ubuntu 只需要先格式化 MBR,然后删除 Ubuntu 分区即可。因为手头没有 DOS 启动盘,我想到一键恢复的硬盘版是带 DOS 工具的,就在 Windows 下装了个一键恢复硬盘版,然后进 DOS 命令行 “fdisk /mbr”。

可谁知道做完这些之后,MBR 是清掉了,但系统无法启动了,提示消息是这样的:

Windows 未能将启动原因可能是最近更改了硬件或软件
文件:\Windows\system32\winload.exe
状态:0xc000000e
信息:无法加载所选项,因为应用程序丢失或损坏。
...

然后我就傻眼了,从来没有遇到过这种情况呀!搜索了一番之后,才明白了这是什么意思。

Windows Vista 之后的系统,不再使用 boot.ini 保存启动菜单,而是使用一种叫做 BCD(Boot Configuration Data)机制来管理启动菜单,其默认的配置文件是活动分区(一般是 C:\)的 \Boot\BCD。简单的来说,可以将 \Boot\BCD 文件看成是 GRUB 的 menu.lst(grub.conf)文件,里面储存着系统装载程序的路径和参数等。

在我这里,出现上面问题的原因是 BCD 每项记录中的 device 选项被“一键恢复硬盘版”改成了 unknown,这样启动程序不知道到哪里去找系统的装载程序,自然也就无法启动了。使用 bcdedit /store C:\Boot\BCD 可以查看系统的 BCD 每项记录。(较为诡异的是,在没有删除 MBR 之前,我是如何进入到启动项里的?)

我用的解决方法是把所有默认启动项中的 unknown 改成了 boot。还得依靠工具,使用 WinPE U 盘(DOS 启动盘未尝试)启动,进入 C:\Windows\System32\,执行 bcdedit 命令:

bcdedit /store C:\Boot\BCD /set {default} osdevice boot
bcdedit /store C:\Boot\BCD /set {default} device boot
bcdedit /store C:\Boot\BCD /set {default} detecthal 1

然后就可以启动进入 Windows 了。