2012年12月19日星期三

查找中国防火墙设备ip地址

前两天看到一个用于查找GFC(Great Firewall of China)设备ip的python脚本mongol.py,觉得挺有意思,拿来研究了一下。

这个脚本基于 Internet Censorship in China: Where Does the Filtering Occur? 这篇论文,mongol.py基本就是该论文4.3节Algorithm的实现。除了防火墙设备ip查找算法,论文还阐述了以下内容:

  • 从现有实验结果看,有状态的连接(即已完成三次握手的连接)+ 敏感词 才会触发审查
  • 对访问外国的流量审查严格,国内主要还是靠social control(如人工审查)
  • 国内两大ISP,电信的审查设备主要设置在省区城域网,网通的主要设置在骨干网,因在省区也有审查设备,GFC其实也具备国内流量审查的能力
  • 审查起作用后,链路被阻塞的状态会维持一段时间,这段时间内,即使后续的报文不包含敏感词,也会被阻塞


mongol.py接受一个ip参数,其完成以下工作:

首先新建socket与指定ip 80端口进行连接,发送一条GET消息:
GET / HTTP/1.1      \r\n
Host: ip    \r\n
\r\n

在connect调用返回前,三次握手已经完成。之后拿到response,判断响应状态码,如果是200 OK 或 302 Redirect 或 401 Unauthorized,则表明可与目的ip 80端口建立有效连接。

然后对于有效连接,利用scapy进行ackattack(相当于traceroute),并记录本机到目的ip的中间router设备ip,注意所记录的router中可能有一个就是GFC设备,此时由于还没有发送敏感词,并未触发审查

再之后重新新建一个socket进行目的ip连接,此时发送一条包含敏感词的GET消息:
GET /tibetalk  \r\n
Host: ip  \r\n
\r\n

如果发送后出现socket error,则说明GFC设备在该链路上向本机发送了RST报文(也会向目的ip发送),审查机制被触发

最后再次进行ackattack,因为本机收到RST后,本机到目的ip的链路还会阻塞一段时间,这时即使是不包含敏感词的一个ack报文都会被阻塞,trace到的最后一个ip地址就是GFC设备的ip地址


貌似直接traceroute实现不是基于tcp三次握手的,否则直接traceroute Facebook就可以找到防火墙服务器ip;另对于是否stateful的连接才会触发审查,还可以用netcat工具进行验证。

以上提到的论文作者为查找全中国范围内的GFC设备,提到的一个方法也很有趣,利用中国政府网-部门地方链接以及各种导航网站获取到全国各个地方的网站,以此作为检测工具的目的ip地址参数。

Have fun!

2012年12月15日星期六

微信公众平台开放接口

微信公众平台,是为有更多话语权的人设置的一个功能,这部分人或许是明星,或许是地产大佬,或许是某行业中知道更多内幕、小道消息的人。公众平台的推广口号虽说是每个人都有自己的品牌,但在这本已信息过载的时代,谁会专门设置一个通道,关注某个普通人生活中鸡毛蒜皮的那点事。

本着折腾的精神看了下公众平台的开放接口,目前提供的接口就2个:

  • 网址接入公众平台合法性校验功能
  • 普通微信用户消息回复功能

使用前先需要填一些信息,包括token、URL等:















对于以上第二个功能,普通微信用户向公众平台发送消息时,公众平台再以POST的方式向以上配置的URL发送信息,包含以下一些数据:

  • 文本消息:包括文本消息内容、接受/发送方微信号等
  • 地理位置消息:包括地理位置经纬度等信息
  • 图片消息:包括图片链接等信息
我们部署在指定URL上的应用可以以POST方式回应文本、图文信息。

或许可以利用公众平台开放接口实现文本信息查询、基于地理位置的应用。

Have fun!

2012年12月14日星期五

新浪微博开放平台应用之登录授权

在前文《新浪微博开放平台应用之数据抓取》中,我们学会了如何使用 trends/statuses 接口抓取话题数据,相比 trends/statuses 接口,有些抓取数据的接口需要登录授权后才能调用,比如获取评论的接口 2/comments/show。下面我们就来看如何进行登录授权。

完成登录需要用到 oauth2/authorize 接口,其接收以下参数:
  • client_id: 所申请的app_key
  • response_type: 返回数据类型,值可为code或state,code用于后续获取access_token
  • display: 授权页面的终端类型,default指示游览器
  • redirect_uri: 授权回调地址,需与开放平台中设置的回调地址一致

参数既可以以POST方式传送,也可以以GET方式发送,如下例子:
https://api.weibo.com/oauth2/authorize?redirect_uri=http://liuxiaofang.sinaapp.com/callback?url=/init-comments&ids=3522096338448283&response_type=code&client_id=622387540&display=default

以上url以人为可读的方式显示,向应用服务器发送前还得经过编码(如使用python中的urllib.quote)。

这里所说的回调地址,通过 应用页面 -> 接口管理 -> 授权设置 进行配置。














正确发送URL后,将进入以下登录界面:













成功登录后,将跳转到我们之前设定的 redirect_uri,并返回 code 值:
http://liuxiaofang.sinaapp.com/callback?url=/init-comments&ids=3522096338448283&code=123456

有了code,我们就可以请求获取access_token,获取 access_token 的接口为 oauth2/access_token,其接收以下参数:
  • grant_type: 请求类型,对应与调用 authorize 获得的code,这里值应为 authorization_code
  • code: 以上获得的 code 值
  • client_id: 所申请的 app_key
  • client_secret: 所申请的 app_secret
  • redirect_uri: 回调地址,需与开放平台中设置的回调地址一致
向 oauth2/access_token 传送参数,需用POST方式,如:
https://api.weibo.com/oauth2/access_token
grant_typeauthorization_code
client_id622387540
client_secret = 123456
redirect_urihttp://liuxiaofang.sinaapp.com/callback?
code = 123456

正确发送URL后,将跳转到类似以下授权页面:















完成授权后,将跳转到之前设定的回调地址,并且从 response 中,我们可以获取到 access_token 和 expires_in 超时值。

有了 access_token,我们终于可以使用 2/comments/show 这类需要事先登录授权的接口了。下面通过GET方式获取指定微博id的评论,获取到的 access_token 放置在请求头中:

https://api.weibo.com/2/comments/show?id=3522885349661782
Authorization: OAuth2 123456

之后新浪服务器将返回评论id、评论文本、评论创建时间、评论作者等信息。

欢迎访问我的一个基于sae和新浪开放平台的网站 带上猫咪去旅行

Have fun!

2012年12月11日星期二

python web框架bottle

bottle是一个python WSGI框架,简单的一个py文件,集成了router、redirect、template,request/response获取与设定等功能,下面介绍其基本使用方法。

先import相关方法,并声明Bottle对象:

from bottle import Bottle, jinja2_template as template, static_file, redirect, request, response, run
app = Bottle()

Router
利用python的decorator方法,可以声明多个URL对应一个处理函数:

@app.get('/')
@app.get('/index')
def index():
  return 'Hello bottle!'

template
template用于将后台代码与前端代码分离,增加后台代码重用:

@app.get('/login')
def login():
   return template("login.html", handler=get_site_info())

@app.post('/login')
def login_post():
   return UserService.login()

redirect
bottle提供了redirect方法用于页面跳转,如登出后跳转到登录页面:

@app.get('/log-out')
 def log_out():
   UserService.log_out()
   redirect('/login', 302)

request/response
bottle提供了request和response对象,通过这两个对象,可方便地操作请求与响应数据:

@app.get('/admin')
 def admin():
   _status = request.query.get('status', None)
   response.set_cookie('status', _status)

static_file
网页包含html、js、图片等静态内容,处理这些静态内容的请求,我们不需要编写专门的router处理,只需要将静态内容放到一个文件夹下,利用如下一段代码,即可处理所有static文件请求:

@app.get('/static/<filename:re:.*')
 def server_static_file(filename):
   return static_file(filename, root='./static/')

最后,使用run方法让我们后台服务跑起来:
run(app, host='localhost', port=8080)

Have fun!

2012年12月10日星期一

社会化评论系统 ”多说“

多说 是一个评论系统,其整合了新浪微博、豆瓣、人人等多个社交网站评论插件,原先孤立的站点文章、博文可以通过 多说 与社交网站关联起来,利用社交人气活跃站点。

多说 是个开源的评论系统,使用起来也非常简单,先在多说官网进行注册,注册完成后将获得一段代码,将该段代码粘贴到网页代码<body></body>间任意位置,就可以使用多说评论系统。效果如下:













Have fun!

2012年12月9日星期日

新浪微博开放平台应用之数据抓取

新浪微博开放平台为开发者提供了很多API,用于访问或修改各种数据,如微博、评论、话题、收藏、用户标签等。下面展示如何使用“话题”的API,对特定数据进行访问。

新浪微博中的话题,由##括起来,要访问话题数据,需用到 trends/statuses 接口,其接受以下参数:
  • source : 所申请的app_key
  • trend_name : 要抓取的话题
  • count : 抓取条目的数量

通过GET方式(或直接通过游览器),访问以下URL:
http://api.t.sina.com.cn/trends/statuses.json?count=40&source=31641035&trend_name=带上猫咪去旅行

该URL指示获取最多40条,话题包含“带上猫咪去旅行”关键字的微博数据,访问该URL后,可获得以下形式的数据:

[{
"created_at":"Fri Dec 07 23:01:47 +0800 2012",
"id":3520736712709956,
"text":"#带上猫咪去旅行图站#低调内测上线 http://t.cn/zjJypQ5",
"source":"<a href=\"http://weibo.com\" rel=\"nofollow\">新浪微博</a>",
"thumbnail_pic":"http://ww4.sinaimg.cn/thumbnail/66f77025gw1dzlk18f7r3j.jpg",
"bmiddle_pic":"http://ww4.sinaimg.cn/bmiddle/66f77025gw1dzlk18f7r3j.jpg",
"original_pic":"http://ww4.sinaimg.cn/large/66f77025gw1dzlk18f7r3j.jpg",
"user":
{"id":1727492133,
"screen_name":"bangerlee",
"name":"bangerlee",
"province":"44",
"city":"1",
"location":"广东 广州",
"gender":"m",
"created_at":"Fri Apr 09 15:12:15 +0800 2010",
}]

可以看到返回的微博数据包含了我们想要搜索的关键词#带上猫咪去旅行#,另还有微博文字内容、微博图片ip、微博用户名等信息。

通过一个python小程序,我们可以实现数据抓取:




























运行以上程序有:
linux # python get_data.py  
bangerlee
#带上猫咪去旅行图站#低调内测上线 http://t.cn/zjJypQ5
http://ww4.sinaimg.cn/thumbnail/66f77025gw1dzlk18f7r3j.jpg

Have fun!

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!

2012年10月31日星期三

libevent源码走读

libevent响应事件(文件描述符可读/可写、超时、信号),调用特定函数进行处理,libevent中主要有以下几个概念:

  1. 事件多路分发机制(event demultiplexer),即epoll、kqueue、select等
  2. 事件源,在指定的文件描述符上注册关心的事件,如I/O读写、定时、信号事件
  3. 事件处理器(event handler),事件触发时被调用
  4. 反应器(reactor),事件管理接口,注册事件后进入循环,事件就绪时调用事件处理函数


libevent中主要的几个接口:

  • event_init:初始化libevent库,生成event_base实例
  • event_set:初始化事件event,设置回调函数和关注的事件
  • event_base_set:设置event从属的event_base,即指明event要注册到哪个event_base上
  • event_add:正式添加事件
  • event_base_dispatch:程序进入无限循环,等待就绪事件


以下是上面各个函数的具体实现(基于libevent-2.0.20-stable版本)。

event_init函数:调用event_base_new_with_config,该函数进行事件多路分发机制选择。epoll、kqueue、select等多种事件多路分发机制被存放在eventops数组中,从该数组下标0开始选择,将选好的事件多路分发机制存放在evsel字段中。之后调用evsel->init,该接口函数最终调用对应事件多路分发机制的初始化函数,如epoll对应的是epoll_create。

event_set函数:调用event_assign,event_assign函数中,填充event结构中的文件描述符、事件类型、事件处理函数等字段。

event_base_set函数:简单地设定event结构中的ev_base字段为指定值。

event_add函数:调用event_add_internal,该函数中,根据不同的事件类型,调用不同函数处理,对于I/O,调用evmap_io_add;对于signal,调用evmap_signal_add。之后调用event_queue_insert,将事件加入激活事件队列。

在evmap_io_add和evmap_signal_add中,均会调用evsel->add,其作用就是调用某个具体事件多路分发机制的接口函数,完成事件添加。例如对应于epoll的add函数就是epoll_nochangelist_add,该函数调用epoll_apply_one_change,epoll_apply_one_change调用epoll_ctl进行事件注册。

event_base_dispatch函数:调用event_base_loop,该函数调用evsel->dispatch,即事件多路分发机制注册的dispatch函数,对应于epoll就是epoll_dispatch,epoll_dispatch调用epoll_wait,调用event_set函数时设定了监听的文件描述符,epoll_wait在此文件描述符上等待I/O事件发生。

Have fun!

2012年10月30日星期二

memcached客户端一致性哈希算法实现——libketama

对于memcached,K-V存储到哪个memcached服务器,由memcached客户端决定。下面我们分析一种memcached客户端一致性哈希算法(consistent hashing algo)实现库——libketama。

使用方法
libketama提供了一个memcached服务器配置文件,我们需先将服务器ip、memory填入该文件:








之后我们编码调用libketama接口,输入K-V中的key值,libketama为我们返回该K-V将要被存放到的memcached服务器ip。




















以上代码简单展示了libketama的用法,用到libketama提供的ketama_roll、ketama_hashi、ketama_get_server、ketama_smoke几个接口。

一致性哈希模型构建
构建一致性哈希模型,需要模拟两个对象,一个是圆,另一个是圆上的虚拟节点。libketama分别通过continuum、mcs两个结构模拟圆和虚拟节点:









以上numpoints记录圆上虚拟节点的数目,modtime记录memcached服务器配置文件的修改时间,array为圆上虚拟节点mcs数组。








以上point记录虚拟节点在圆上的位置。

模型构建过程
ketama_roll接口用于一致性哈希模型构建,其调用ketama_create_continuum,ketama_create_continuum函数先调用read_server_definition函数读取memcached服务器配置文件,将信息保存在以下结构中:







之后构建虚拟节点,根据所配置的服务器个数,一共构建numservers*160个虚拟节点:



























以上代码中,首先对每个物理服务器节点计算权重pct,再由权重得出为每个物理服务器设立的虚拟节点个数ks*4。

之后调用ketama_md5_digest计算“ip-i”(比如“10.0.1.1:11211-0”)对应的md5值,并由该md5值得出虚拟节点的具体位置,即mcs结构中的point值。

确定所有虚拟节点point值之后,最终对所有point值排序,并将虚拟节点总个数、mcs数组放入共享内存中。至此完成一致性哈希模型的构建。

由Key获取ip
一个K-V应该放入哪个memcached?首先我们可以调用ketama_hashi接口计算出key的md5散列值kh,其计算方法与计算虚拟节点point值的方法相同。

之后调用ketama_get_server,构建虚拟节点时虚拟节点已根据point值完成排序,ketama_get_server中采用二分查找法,若能找到第一个大于kh的point值,则返回相应的mcs结构;若未找到,则返回虚拟节点数组的第一个mcs结构。

Have fun!

2012年10月29日星期一

memcached中的内存管理

memcached,分布式K-V内存缓存服务,其核心为内存管理,下面我们就来了解memcached管理内存的方式、解读这部分代码,本文基于memcached 1.4.15版本。

memcached以类似Linux内核中的slab内存分配机制进行内存管理:













一块连续的1M大小的page被分成多个等大的chunk,slab class管理特定大小的chunk。一对K-V组成一个item,一个item被放置到一块chunk中。

除了以上结构外,memcached使用名为slots的链表,管理空闲的chunk:

memcached对内存的管理主要是对slabclass和slots链表的维护。slabclass_t结构如下:

下面从memcached初始化内存管理结构、add/delete操作分析相应的memcached代码。

初始化内存管理结构

main函数中,调用slabs_init进行内存管理相关的初始化工作。slabs_init函数中,初始化数组长度为MAX_NUMBER_OF_SLAB_CLASSES的slabclass数组,对每个slab class,填入size和per slab值。size值为sizeof(item) + settings.chunk_size,即最小为96,默认factor为1.25,size若不足8的倍数则补齐。

初始化过程很简单,初始化完成后memcached也并没有真正从操作系统获取物理内存。

add操作

拉起memcached服务后,memcached即对端口进行监听,等待请求的到来。在memcached客户端执行add操作后,函数调用过程如下:

event_handler -> drive_machine -> try_read_command -> process_command -> process_update_command -> item_alloc -> do_item_alloc -> slabs_alloc ->  do_slabs_alloc

在do_item_alloc函数中,调用slabs_clsid函数,slabs_clsid根据添加的key的长度计算所要放置到的slabclass的下标,计算方法为遍历slabclass数组,将key长度与slabclass->size进行比较。

在do_slabs_alloc函数中,首先判断是否有空闲的chunk,即sl_curr值是否为零。如果sl_curr非零,则从slots中取chunk;否则调用do_slabs_newslab完成page申请。
do_slabs_newslab -> split_slab_page_into_freelist -> do_slabs_free

do_slabs_newslab调用memory_allocate从系统申请1M大小的内存,之后调用split_slab_page_into_freelist将1M内存分成等大的chunk,split_slab_page_into_freelist 对每块chunk调用do_slabs_free,将这些新生成的空闲chunk加入slots链表。完成以上动作,do_slabs_newslab函数中,将新申请的page加入slab_list数组。

完成空闲chunk申请后,在do_item_alloc函数中,将key、key长度、value等值填到chunk中:
delete操作

对应delete操作,函数调用过程如下:
event_handler -> drive_machine -> try_read_command -> process_command -> process_delete_command -> item_get -> do_item_get -> item_remove -> do_item_remove -> item_free -> slabs_free -> do_slabs_free

在do_slabs_free中,内存并不是真正归还系统,而是放到相应slab class的slots链表头部:

Have fun!



2012年10月28日星期日

在vim中使用cscope快速查看代码

使用vim+cscope,我们可以很方便地跟踪和查看代码。

安装cscope后,执行以下命令:

# cd /usr/src/linux
# find . -name '*.h' -o -name '*.c' > cscope.files
# cscope -b -k -q
# ctags -R
# echo 'cs add .' >> /etc/vimrc

此后进入/usr/src/linux,使用vim就支持代码跟踪了。

执行 :cs help 可以显示cscope帮助信息:

cscope commands:
add  : Add a new database             (Usage: add file|dir [pre-path] [flags])
find : Query for a pattern            (Usage: find c|d|e|f|g|i|s|t name)
       c: Find functions calling this function
       d: Find functions called by this function
       e: Find this egrep pattern
       f: Find this file
       g: Find this definition
       i: Find files #including this file
       s: Find this C symbol
       t: Find assignments to
help : Show this message              (Usage: help)
kill : Kill a connection              (Usage: kill #)
reset: Reinit all connections         (Usage: reset)
show : Show connections               (Usage: show)


常用命令:
:cs find g hash    #查找hash函数或变量的定义
:cs find e hash    #查找包含hash字段的代码行

常用快捷键:
:ctrl + ]       #跳转到光标所在符号的定义位置
:ctrl +T       #回到上一次的位置

Have fun!