2012年11月27日星期二

文件系统缓存控制小工具vmtouch

文件系统缓存的一个作用是加快文件读取速度,vmtouch可用于管理文件系统缓存,是个有意思的小工具。vmtouch有以下功能:
  1. 查询文件/目录有多少被载入缓存
  2. 将文件/目录载入缓存
  3. 将文件/目录从缓存中清除
  4. 锁定缓存

以下为vmtouch使用示例:

















最开始 a.txt 文件被载入到缓存中,占用84个page,共336K;使用vmtouch -e 将文件从缓存中清除;使用tail命令读取 a.txt 部分内容,再使用vmtouch进行查看,a.txt 部分内容被载入缓存,占用10个page,40K。

下面是vmtouch的具体实现:

递归查找文件:因为我们向vmtouch传入的可以是目录,最终是要操作该目录下的所有文件,而目录下可能包含目录,因而需要用到递归。vmtouch中vmtouch_crawl函数是个递归函数,若其参数path指示一个目录,则不断递归,是否是目录通过stat结构的st_mode字段判断,vmtouch_crawl函数中用到stat、opendir、readdir系统调用。

打开/映射文件:目录下每个文件最终会跳出递归调用,vmtouch_file函数被vmtouch_crawl调用,用于文件处理。vmtouch_file先判断文件类型,对链接以及过大的文件(500*1024*1024)不进行处理,调用open、mmap完成文件打开和虚拟内存映射。

查询:vmtouch_file调用mincore查询某个文件的缓存占用情况,传入系统调用mincore的第一个参数是mmap的返回值,第二个参数是文件长度值,第三个参数是指向一块pages_in_file大小的内存指针。根据mincore的查询结果,如果一个页面在内存中,则增加pages_in_core等统计值。

载入内存:要将一个文件载入缓存,对其进行读取即可,vmtouch_file中通过对mem的访问操作达到载入文件缓存的目的:







清除缓存:在linux下,清除一个文件相应的缓存可调用posix_fadvise完成,posix_fadvise函数原型如为:int posix_fadvise(int fd, off_t offset, off_t len, int advice); 传入相应文件描述符、文件大小和 POSIX_FADV_DONTNEED 标志即可完成缓存清除。

内存锁:有时候我们系统一些数据长驻内存,不被交换出去,这时我们可通过mlock调用实现,mlock第一个参数为mem,第二个参数为文件长度。

vmtouch可用于“预热”文件系统缓存,有意识地换出冷数据、控制热数据常驻内存,从而减少page fault,增加缓存命中率。

Have fun!

2012年11月22日星期四

rtags——node.js+redis实现的标签管理模块

引言
在我们游览网页时,随处可见标签的身影:
  • 进入个人微博主页,可以看到自己/他人的标签,微博系统会推送与你有相同标签的人
  • 游览博文,大多数博文有标签标记,以说明文章主旨,方便搜索和查阅
  • 网上购物,我们经常使用标签进行商品搜索,如点选 “冬装” +  “男士” + “外套” 进行衣物过滤
rtags就是一个用于标签管理的node.js模块,其使用redis的set数据结构,存放标签和相关信息。

API
rtags提供以下接口:
  1. 添加物件及其标签  Tag#add(tags, id[, fn])
  2. 查询物件的标签  Tag#queryID(id, fn)
  3. 查询两个物件共有的标签  Tag#queryID(id1, id2, fn)
  4. 查询具有特定标签的物件  Tag#queryTag(tags, fn)
  5. 删除物件的标签  Tag#delTag(tags, id[, fn])
  6. 删除物件  Tag#remove(id[, fn])
示例
首先调用 Tag#createTag 生成一个 Tag 实例,传入一个字符串指示物件的类别,比如 ‘blogs’ 指示博文,‘clothes’ 指示衣服:
 var tag = rtags.createTag('blogs');

然后添加该类别的物件和对应的标签,Tag#add 接收两个参数,第一个是物件的标签,有多个标签可用逗号隔开;第二个参数是物件的 id,以下代码中以 strs 下标为 id:

var strs = [];
strs.push('travel,photography,food,music,shopping');
strs.push('music,party,food,girl');
strs.push('mac,computer,cpu,memory,disk');
strs.push('linux,kernel,linus,1991');
strs.push('kernel,process,lock,time,linux');

strs.forEach(function(str, i){ tag.add(str, i); });

经过上面调用,redis 数据库中就有了博文标签数据,我们就可以进行相关查询了。查询某物件具有哪些标签,我们可以调用 Tag#queryID,该函数接收物件 id 和一个回调函数作为参数,查询结果作为数组存放在 ids 中:

tag
  .queryID(id = '3')
  .end(function(err, ids){
    if (err) throw err;
    console.log('Tags for "%s":', id);
    var tags = ids.join(' ');
    console.log('  - %s', tags);
  });

以上代码用于查询 id 为 ‘3’ 的博文的标签,执行该段代码,输出为:

Tags for "3":
  - kernel linux linus 1991

要查询两个物件具有哪些相同标签,同样调用 Tag#queryID,这时传入的参数应为两个物件的 id 和一个回调函数:

tag
  .queryID(id1 = '3', id2 = '4')
  .end(function(err, ids){
    if (err) throw err;
    console.log('Tags for "%s" and "%s" both have:', id1, id2);
    var tags = ids.join(' ');
    console.log('  - %s', tags);
  });

以上代码用于查询 id 为 ‘3’ 和 ‘4’ 的博文共有的标签,查询结果为:

Tags for "3" and "4" both have:
  - kernel linux

rtags 还提供根据标签搜索物件的功能,调用 Tag#queryTag,传入标签和一个回调函数,若有多个标签,可用逗号隔开:

tag
  .queryTag(tags = 'music,food')
  .end(function(err, ids){
    if (err) throw err;
    console.log('The objects own the "%s" tags:', tags);
    var id = ids.join(' ');
    console.log('  - %s', id);
    process.exit();
  });

以上代码查询同时具有 ‘music’ 和 ‘food’ 标签的博文,其输出为:

The objects own the "music,food" tags:
  - 0 1

安装
rtags通过以下命令安装,该命令会一同安装rtags依赖的redis模块:
$ npm install rtags

亦可以通过以下命令从 github 获取 rtags 源码:
$ git clone git@github.com:bangerlee/rtags.git

拉起 redis-server,安装 should 模块后,我们可以执行 rtags 源码目录下的例子:
$ cd rtags/test
$ node index.js

github地址: https://github.com/bangerlee/rtags.git
欢迎 git pull/fork/clone。

Have fun!

2012年11月16日星期五

使用libqrencode生成二维码

libqrencode用于生成QR code格式的二维码,其用C编写。相比ZXing支持一维、二维和多种编码格式,libqrencode功能更简单,只针对最常见的QR code,只能用于编码。

libqrencode提供的接口在源码qrencode.h文件中有详细说明,除了编程接口,libqrencode还提供了一个现成的程序用于生成二维码。安装libqrencode后,源码目录下生成qrencode,其用法如下:
./qrencode -s 5 -o bangerlee.png bangerlee.blogspot.com

以上命令将字符串 "bangerlee.blogspot.com" 编码为QR code二维码,其中 -s 指示二维码上黑白小块的大小(单位为像素),-o 指示生成的二维码图像文件名称。

libqrencode支持对中文进行编码。












Have fun!

2012年11月13日星期二

Node.js+MongoDB实现短域名功能——开源项目short

MongoDB是一个分布式的文档存储数据库,数据用二进制的JSON格式BSON存储。

设计一个存储博文的数据库表,如果使用关系型数据库,博文本身用一个表存储,评论用另一个单独的表存储,而使用MongoDB,评论可嵌入博文表,一篇完整的博文,其相关信息只需存放在一个表中:




















下面来看如何使用Node.js和MongoDB实现短域名功能,主要用到Node.js的Mongoose模块。

首先设计短域名在MongoDB中的保存结构,除原URL、短域名这两个字段要存储外,还可以存储生成时间、访问者等与短域名相关的信息,表结构如下:












以上URL表示缩短前的域名,hash表示短域名。

其次考虑接口,接口很简单,一个接口generate用于接收URL,返回短域名;另一个接口retrieve接收短域名,返回原URL。

最后需要设计一个hash函数实现URL与短域名关联,hash函数供generate函数调用。

generate函数:













以上用到mongoose的save接口,往mongoDB服务器保存短域名数据。

retrieve函数:










findByHash函数中,调用mongoose的findeOne接口,findeOne根据传入的hash值,在mongoDB服务器中查找相应的短域名条目。完成查找后,findByHash再调用mongoose的update接口更新短域名条目中的hits等字段。

hash函数:


hash函数很简单,一个URL通过hasher对应到一个长度为6的 [0-9a-zA-Z]字符串。

调用以上generate接口,完成 URL为 http://nodejs.org/,以及URL为 http://bangerlee.blogspot.com/ 的短域名生成后,使用mongo进行数据查询,我们可以看到:





















有了以上短域名功能,我们可以进一步搭建一个提供短域名跳转的服务器,其核心是根据hash,调用retrieve函数,从MongoDB服务器上获取相应的URL,完成域名跳转:


































执行以上服务器程序,然后在地址栏输入 http://localhost:8080/GHJwvl ,回车之后就会跳转到 http://bangerlee.blogspot.com/ 。

Have fun!

2012年11月8日星期四

Redis+node.js使用实例——英文搜索引擎Reds

Redis不仅能像memcached一样用作缓存层,其还可以作以下用途:
  • 持久化:aof 或 rdb
  • 消息队列:使用Redis的list数据结构,也可以使用score set做带权重的消息队列
  • 日志收集器:多个端点将日志信息写入Redis,单独一个线程将所有日志写到磁盘
  • 记录社交关系:将每个人的好友存放在一个set中,求两个人的共同好友时,只需求出两个集合的交集
适合Redis的应用场景远不止上面列的这些,只有想不到,没有用不到。下面看一个使用Redis+node.js实现的英文搜索引擎——Reds,学习Redis的用法。

Reds用到node.js的Redis模块,以及处理英文自然语言的natural模块,其实现以下功能:
调用Reds的search.index接口将英文语句加到Redis服务器,如以下语句:
  • 'Tobi wants 4 dollars'
  • 'Loki is a ferret'
  • 'Tobi is also a ferret'
  • 'Jane is a bitchy ferret'
  • 'Tobi is employed by LearnBoost'
调用单词搜索接口search.query、search.type和search.end搜索符合条件的单词。针对以上语句,若查询同时包含 'jane' 和 'bitchy' 的语句,则Reds返回 'Jane is a bitchy ferret' 这条语句作为结果;若查询包含 'jane' 或 'dollars' 的语句,则Reds返回 'Jane is a bitchy ferret' 和 'Tobi wants 4 dollars' 作为结果。

具体接口调用如下:







reds.createSearch调用创建一个search对象,传入'misc'作为该search对象的标识,后续在该search下进行语句插入和单词查询,均需匹配该标识。

search.index处理语句,进行分词,最后存放到redis服务器score set结构中,第一个参数为要保存的语句,第二个参数为语句的id,第三个参数为插入语句时执行的函数,为可选参数。search.index函数原型如下:
















  • key为search对象的标识,即 'misc'
  • db为redis.createClient()调用所创建的redis客户端对象
  • 对于要插入的str语句,words调用确保str是[a-zA-Z0-9]范围内的有效字符,stripStopWords调用过滤掉str中的stop words(对于英文语句,a/the/to等词就属于stop words),之后再由stem调用得到语句中剩余词的词干(比如 cats/catty/catlike 的词干都是 cat),原语句 'Tobi wants 4 dollars' 经过该步处理后变成一个数组: {'toni',  'want',  'dollar'}
  • countWords计算以上数组元素个数
  • metaphoneMap函数也与自然语言处理相关,其底层调用natural模块的metaphone函数,生成单词对应的发音词(如对 'tobi',返回 'TB'),metaphoneMap最后返回包含如下内容的对象:







以上都是reds自然语言处理相关的代码,下面才真正用到Redis,Redis zadd命令的格式为:
zadd key score member [score] [member]
key为键值,score表示权重,member为内容,score和member可选。

再看上面的代码,对于语句中的每个单词,调用zadd添加两条记录,对于 'tobi',有:
zadd misc:word:TB 1 1
zadd misc:object:1 1 TB

整条语句保存后,有:







以上为分词插入Redis score sets过程,可以看到对于每个单词,插入了两条记录,一条以单词发音缩写为key,单词出现次数为score,句子id为内容;另一条以句子id为key,单词出现次数为score,单词发音缩写为内容。

下面来看单词查询过程,查询主要由end函数完成:




















以上查询代码,也是先求出所要查询单词的词干,然后由metaphoneKeys返回之前插入单词时的key格式,对于 'tobi',metaphoneKeys返回 'misc:word:TB'。

db.multi括起来的代码指示对Redis加权集合进行并集或交集操作,type由search.type接口指定,默认为 'and',即进行交集操作,对应的Redis命令为 zinterstore,zinterstore格式如下:

zinterstore destination numkeys key [key …]

可理解为创立一个名为 'destination' 的集合,key对应的member相同,则满足交集条件,这样的member属于 'destination' 中的一个元素。

对应于本文开头的查询示例,查询既有 'tobi' 单词,又包含 'dollar' 单词,有:







可以看到zrevrange返回id 1,对应于本文开头使用search.index插入的语句。

对于求并集,需由调用search..type('or'),对应的Redis命令为zunionstore

Have fun!

2012年11月3日星期六

Redis源码走读

同为内存K-V数据库,Redis具有数据持久化等功能,比memcached强大。下面通过走读Redis代码,了解Redis大体框架。

首先从Redis服务器端的main函数开始,main调用initServerConfig对redisServer结构类型的server全局变量进行默认初始化,填充默认端口(6379)、DB数量(16)等字段。initServerConfig接着调用populateCommandTable对全局变量redisCommandTable保存的Redis命令进行分类,分类后的命令由全局变量commandTable存放,lookupCommand函数用于命令查找。

之后main函数调用loadServerConfig,使用redis.conf中的配置重新填充server中的字段。接着main调用initServer,大部分服务器初始化工作由该函数完成。initServer进行以下函数调用:


  • 调用listCreate创建存放不同状态的客户端的链表,填充server中clients、clients_to_close、slaves、monitors等字段
  • 调用createShareObjects创建共享对象,服务器内部实现用到的特定字符串、整数,Redis将其包装成共享对象,存放在share全局变量中,以供其他数据结构共用。如封装了换行符 '\r\n' 的字符串对象,响应消息、出错消息均要使用;strings、sets、lists等结构均要使用整数对象作ID、引用计数等
  • 调用aeCreateEventLoop,该函数调用aeApiCreate,aeApiCreate调用epoll_create,创建epoll实例
  • 调用zmalloc给DB分配内存,之后分别对各个DB分配dict
  • 调用anetTcpServer,其底层调用socket、setsockopt、bind、listen等系统接口,完成端口监听
  • 调用aeCreateTimeEvent,将serverCron加到时间事件队列,serverCron为Redis服务器完成断连超时客户端等定时任务
  • 调用aeCreateFileEvent,将acceptTcpHandler加入IO事件队列,acceptTcpHandler调用anetTcpAccept,anetTcpAccept 调用anetGenericAccept,anetGenericAccept 执行while(1)循环调用系统接口accept,等待客户端的连接


回到main函数,main调用aeMain,aeMain首先调用beforesleep,如果配置了AOF,beforesleep调用flushAppendOnlyFile将内存数据刷入磁盘,接着aeMain调用aeProcessEvents处理事件事件和IO事件。

以上为Redis服务器启动过程的代码实现,下面我们来看Redis服务器处理指令的代码实现。

在服务器初始化initServer函数中,注册了acceptTcpHandler IO事件函数,并循环调用accept等待客户端接入。当有客户端接入时,acceptTcpHandler下的acceptCommonHandler函数被调用,acceptCommonHandler调用createClient,createClient创建一个redisClient对象c,选定一个DB,将accept返回的文件描述符记录到c的fd字段,并将c加到server.client链表,调用aeCreateFileEvent将readQueryFromClient添加到IO事件队列,该函数用于接受客户端指令。

当客户端向服务器发送指令,readQueryFromClient函数被调用,其调用processInputBuffer对指令进行解析,processInputBuffer调用processCommand对指令作有效性检查,最后processCommand调用cmd->proc对执行进行处理,相对与set指令,cmd->proc指示的就是setCommand函数。

Have fun!