2015年终总结

再过几个小时就2016年了,对2015年做个小的总结吧。2015年,结束了20年的学业生涯,我完成了从学生到职场人士的转变。2015年4月上旬我离开了北邮,5.1后,正式入职,目前已有着接近8个月的工作经验。20年的学生时光有着太多太多的故事,不打算长篇大论,这里就简单总结下我研究生期间做的让自己记忆深刻的事情以及这几个月在阿里所做的事情吧。

研究生时光

  • 研究生期间很认真的补计算机基础,由于太努力以及自己不怎么锻炼,导致后期脊椎出了点小问题,并且后期身体免疫力下降,大病了一场,持续了大半年之久,入职时都没好利索。
  • 前期努力没有白费,校招时候没怎么努力就拿到想要的工作Offer。
  • 研究方向从信息安全转向到做搜索引擎相关工作研发,并且希望今后自己能在搜索相关方向有所建树。
  • 校招目标公司从微软(由于微软裁员)转到阿里杭州(研二暑假七月份转变的),并在2014年9月份顺利拿到校招Offer,早早结束了校招。
  • 在原神马搜索商搜的负责人张栋的帮助下,校招转岗到阿里巴巴移动事业群-神马搜索-核心引擎部门,这里感谢张栋老师。
  • 在校期间不满导师人品,要求辞退换导师,没被批准,被中心记过一次,但导师对我反而最好,毕业了也经常与导师保持联系,我多次建议他对学生好些。
  • 要求导师给实验室提高补助,新的补助策略是我定的,基本工资500一月,加班费另算(记得是100一天),最后导师通过了提案,实验室师弟师妹每月收到的补助提高了一倍多,而此时我早已离开实验室,并且我在校实验室期间没有一个月补助超过300元。
  • 挂了一门课,并且挂了三年,是我们实验室导师的课,差一点不能毕业答辩。而我在大三时候说,如果我读研,一定要多挂几门科,算是履行当年的戏言吧。
  • 毕业论文被抽到盲审,但顺利通过。
  • 毕业答辩未通过,很大部分原因是答辩导师与我导师关系不好,幸运的是论文修改后竟然通过答辩了。
  • 结识了很多北邮以及其他高校技术大牛。
  • 简单指导了下好友从国企跳槽来互联网,学的PHP,努力了三个月就拿到了很多Offer,目测是个潜力股。
  • 顺利毕业。

工作情况

  • 引擎部门牛人很多,我全方位被碾压,即使在阿里,比我们部门厉害多的部门也非常多,感受到很大的压力。
  • 由于之前大病了一场,记忆力有点变弱,并且由于一些原因在入职前长时间没有学习,所以入职很长一段时间的表现我自己都不太满意。
  • Mentor很厉害,那种差距让我差点崩溃,也特别严厉,早期我有打算离职换工作的打算,后来发现很多应届生第一份工作都是需要一段时间适应期的。Mentor指点了我2个月,现在与别的同事结对或看别人写代码,有时候会认为其效率太低而替他着急。
  • 目前算是适应了工作,开始做一些能提高自己的事情了。
  • 讨厌加班,喜欢那种能给自己时间读书和造轮子,但最好是Linux C/C++相关的搜索工作,其实大部分时间能7点前下班就行,但目前很辛苦,不是那么喜欢。
  • 从入职到现在8个月里,除去调研以及杂活以外,做了几个项目:
    • 新人项目做了个日志收集预警系统,用来及早通知线上问题以及查找线上问题原因,本是一个P7的新人项目,但是那人没来,老大扔我做了,做了2个多月才上线,目前广泛使用。
    • 做了2个多月引擎优化,对于一个搜索门外汉来说,对团队并没有太多的贡献,好在性能QPS提高了3.5%左右,内存也稍微省了一点,但最大的收获是对搜索引擎有了个大概和全面的认识。
    • 做了个集群调度系统,这个项目团队成员较多,我负责了监控模块、负载均衡、配置下载以及集成测试等功能,集成测试对我帮助最大,通过集成测试了解了调度的一些功能,比如如何调度,滚动升级,挂载服务,资源限制等等。
    • 负责了一个月的全网线上支持,每天帮其他团队同学回答和解决线上问题,很虐心。
  • 阿里不同部门的差异可能比不同公司之间的差异还要大,甚至同一大部门下的不同小组实力差别都是天壤之别,线上支持一个月我更确信了这一点。
  • 感受到了互联网的浮躁,特别是创业公司。
  • 自己实力有些进步,所以能够更容易分辨出一些微博大V的真实实力。
  • 做技术的话,杭州是一个性价比特别高的城市,不算贵的房价,较好的互联网技术氛围,但是空气没想象中好,堵车目测比北京还要严重,在西湖区支付宝附近,也会饱受噪音(附近有个军用机场)的骚扰,这让人很不爽。
  • 熟悉Emacs后发现比Vim要好用,但是看代码的话,使用了Eclipse后效率比以前高了很多。

展望2016

  • 谈个恋爱应该是个重要话题
  • 造轮子
  • 更多精力关注搜索和分布式方面的开发

几种Hash算法的实现

哈希被广泛使用在很多领域,如数据存储,加密,计算机视觉(几何哈希),此处就简单整理下几个常见的Hash函数的实现,有空陆续补充吧。

BKDR Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名
// 是一种简单快捷的hash算法。
// 也是Java目前采用的字符串的Hash算法(累乘因子为31)。
// 此哈希函数用的最多
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
// 可将乘法分解为位运算及加减法可以提高效率
// 如将上式表达为:hash = hash << 7 + hash << 1 + hash + ch;
}
return hash;
}

其中累乘因子也可以为131、1313、13131,比如下述代码就使用了33。

1
2
3
4
5
6
7
unsigned int times33(char *str)
{
unsigned int val = 0;
while (*str)
val = (val << 5) + val + (*str++);
return val;
}

此算法也会有如下变种,如:

1
2
3
4
5
6
7
unsigned int timesnum(char *str, int num)
{
unsigned int val = 0;
while (*str)
val = val * num + (*str++);
return val;
}

SDBM Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 本算法是由于在开源项目SDBM(一种简单的数据库引擎)中被应用而得名
// 它与BKDRHash思想一致,只是种子不同而已。
template<class T>
size_t SDBMHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}

AP Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Arash Partow发明的一种hash算法
// 比较优秀的一种哈希算法
unsigned int APhash(char *str)
{
unsigned int val = 0;
int i = 0;
for (i = 0; *str; i++)
if ((i & 1) == 0)
val ^= ((val << 7)^(*str++)^(val>>3));
else
val ^= (~((val << 11)^(*str++)^(val>>5)));
return (val & 0x7FFFFFFF);
}

FNV Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Unix system系统中使用的一种著名hash算法,后来微软也在其hash_map中实现。
template<class T>
size_t FNVHash(const T* str)
{
if(!*str)
return 0;
register size_t hash = 2166136261;
while (size_t ch = (size_t)*str++)
{
hash *= 16777619;
hash ^= ch;
}
return hash;
}

其实关于为什么要用异或,我搜索了下原因,见Why is XOR the default way to combine hashes?

MySQL中出现的字符串哈希函数

1
2
3
4
5
6
7
8
9
unsigned int MySQLhash(char *str)
{
register unsigned int nr = 1, nr2 = 4;
while(*str) {
nr ^= (((nr & 63) + nr2)*((unsigned int)*str++)) + (nr << 8);
nr2 += 3;
}
return (unsigned int)nr;
}

参考链接:
spiderq
各种哈希函数冲突率分析

写了一个Chrome插件 - 百度无损音乐下载插件

1、之前是从http://music.baidu.com/ 入手的,现在发现从此处入手已经找不到方法了。由于我又不是太懂JS语法,于是用了几十分钟,没分析到地址放弃。

2、灵光一闪,从http://fm.baidu.com/ 入手,在Chrome下抓包,细心分析后,果然发现蜘丝马迹,如下图所示:

见左图那个灰色的链接,我们打开链接看下,嘿,发现了许多歌曲信息哦,如下图所示:

由于是FM,所以songIDs有一大串,咱们试试构造下,以黑蝙蝠中队为例,其有三种音乐格式,第一种是可以直接下载的,第二三种是收费的:

我们构造下不同格式的音乐试试看,以无损音乐flac格式和921kbps为例:

构造的链接为:http://music.baidu.com/data/music/fmlink?songIds=966991&type=flac&rate=921


将songLink后的地址格式化为正常网页地址,如下所示:
http://yinyueshiting.baidu.com/data2/music/33809115/966991111600921.flac?xcode=a6ed00d30421e9bebbbef0f52f4938299d0fba1db032ff5f
下载下,发现可以正常下载,28.8M,flac格式的无损音乐。

所以,超高/无损音乐下载方法就是:
将此链接的:
http://music.baidu.com/data/music/fmlink?songIds=966991&type=flac&rate=921
songIds、type、rate改完你想下载的音乐就可以了。

如果只想下载无损音乐flac格式的(前提条件是百度下载里包含无损格式),这样就可以了,只需要更改歌曲songIds。
http://music.baidu.com/data/music/fmlink?songIds=966991&type=flac

用了2-3天时间,学了下前端开发方面的基础知识,没怎么看教程,就是想实现某些功能或者遇到问题就去搜索解决,遇到了一些坑,但是收获也挺大的,于是随手写了个Chrome插件,可用来下载百度无损音乐的,比较简单,原理如上。

程序地址

点击下载插件

使用方法

本插件支持Chrome浏览器和UC桌面浏览器,其他Webkit内核的浏览器应该也支持,但是我没做测试。

Linux系统下安装方法

Linux下直接下载此插件,之后解压后,在BDMusicDownloader文件夹下发现一个src.crx文件,将其拖入到Chrome浏览器-设置-扩展程序界面即可,当打开如以 http://music.baidu.com/song/ 开头的链接时,即下载音乐地址,会自动弹出插件,点击下载即可。如图所示:

Windows下安装方法

从程序地址里下载安装插件,解压文件夹,注意,因为Chrome在Win下的安全限制,所以此文件夹不能删除,之后同上所示,但不是拖入src.crx文件,而是选中开发者模式-加载正在开发的插件-BDMusicDownloader,之后选中src文件,打开即可。如图以UC桌面浏览器为例:

说句题外话,UC桌面浏览器真的还蛮好用的,支持Chrome插件(废话,使用的都是同一个内核),但是自带科学上网,打开Github速度就挺快的,推荐使用。

需要改进的地方

因为我前端经验太少,所以一些小细节没处理好,比如当音乐名字太长时,样式就比较难看了。因我忙着在回家前要把孙钟秀的《操作系统教程》读完,并且之前部门给我的入职前作业我还没完成,所以不打算再做太多修改了,感兴趣的东西可以帮忙修改下。

源码地址

https://github.com/armsword/BDMusicDownloader

代码已注释,有时间和感兴趣的同学,可以帮忙优化下界面。

jwSMTP源码剖析

前段时间事情太多了,忙着写毕业论文,考试,然后又被抽到了盲审,不过好在有惊无险,最后也在学院提交三月中旬申请答辩成功,如果盲审顺利的话,4月份就可以毕业了。不过这段时间总算可以看代码、看书了,感觉自己操作系统方面有些不扎实,索性买了本孙钟秀的《操作系统教程》看,之后顺便阅读和分析了jwSMTP源码,这里写篇文章记录下。本文不想对代码细节作太多分析,因为代码比较好读,并且文章末尾我会放出我注释过的源码链接,所以此文多介绍下原理吧。

jwSMTP

jwSMTP是一个由C++编写的发送邮件的库,支持Linux、Windows等平台。可使用HTML或纯文本方式发送邮件。也可添加附件,支持多个收件人。并且支持LOGIN和PLAIN两种服务器验证方式。

两种调用方式

第一种方式

1
2
3
4
5
6
7
mailer mail(“myfriend@friend.com”, // who the mail is too
“someone@somewhere.net”, // who the mail is from
“There is always room for FooBar”, // subject for the email
“Foo\nBar”, // content of the message
“ns.somewhere.net”); // the nameserver to contact
// to query for an MX record
mail.send( );

第二种方式

1
2
3
4
5
6
7
8
mailer mail(“myfriend@friend.com”, // who the mail is too
“someone@somewhere.net”, // who the mail is from
“There is always room for FooBar”, // subject for the email
vec, // content of the message
“mail.somewhere.net”, // the smtp server to mail to
mailer::SMTP_PORT, // default smtp port (25)
false); // do not query MX records,
// mail directly to mail.somewhere.net

主要区别是一个查询MX record,一个不查询MX record,直接发送给SMTP Server。

base64编码

Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一,设计此种编码是为了使二进制数据可以通过非纯8bit的传输层传输,Base64编码可用于在HTTP环境下传递较长的标识信息,另一方面,采用Base64编码具有不可读性,即所编码的数据不会被人用肉眼所直接看到。
电子邮件的主题,MIME都会用到base64编码。我们现在说下其原理:

Base64编码方法:

  • base64的编码都是按字符串长度,以每3个8bit的字符为一组,然后针对每组,首先获取每个字符的ASCII编码,然后将ASCII编码转换成8bit的二进制,得到一组3*8=24bit的字节,然后再将这24bit划分为4个6bit的字节,并在每个6bit的字节前面都填两个高位0,得到4个8bit的字节,然后将这4个8bit的字节转换成10进制,对照Base64编码表,得到对应编码后的字符。
  • 不是3的整数倍的,需要补齐而出现的0,转化成十进制的时候就不能按常规用base64编码表来对应,可以理解成为一种特殊的“异常”,编码应该对应“=”。
    代码base64.cpp/base64.h是对Base64编码的实现,更多原理请参考下参考链接关于base64编码的原理与实现一文。打开一封Email,查看其原始信息,一般为如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Date: Thu, 25 Dec 2014 06:33:07 +0800
From: A<A@yeah.net>
To: "B"<b@126.com>
Subject:
X-mailer: Foxmail 5.0 beta2 [cn]
Mime-Version: 1.0
Content-Type: text/plain;
charset="gb2312"
Content-Transfer-Encoding: base64
xOO6w6OsU25haVgNCg0KoaGhodXiysfSu7j2QmFzZTY0tcSy4srU08q8/qOhDQoNCkJlc3QgV2lz
aGVzIQ0KIAkJCQkNCqGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaEgICAgICAgICAgICAgICBl
U1g/IQ0KoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoSAgICAgICAgICAgICAgIHNuYWl4QHll
YWgubmV0DQqhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhoaGhICAgICAgICAgMjAwMy0x
Mi0yNQ0K

程序流程

程序一般为先设置发件人信息,之后设置收件人信息,对应的函数为setsender()和addrecipient()函数,此处没什么可说的。之后是setmessage/setmessageHTML函数,两者的主要区别是不是需要base64编码,方法前面已说,此处主要说下checkRFCcompat()函数,此函数主要功能是:将消息结尾改为CRLF(\r\n)形式,之后注意此处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if(message.size() == 1) {
if(*(message.begin()) == '.')
message.push_back('.');
}
else if(message.size() == 2) {
if(*(message.begin()) == '.') {
it = message.begin();
it = message.insert(it, '.');
}
}
else {
if(*(message.begin()) == '.') {
it = message.begin();
it = message.insert(it, '.');
}
for(it = message.begin()+2; it != message.end(); ++it) {
// follow the rfc. Add '.' if the first character on a line is '.'
if(*it == '\n') {
if( ((it + 1) != message.end()) && (*(it +1) == '.') ) {
it = message.insert(it + 1, '.');
++it; // step past
}
}
}
}

此处是根据RFC2821(SMTP协议)的4.5.2 Transparency编写的,内容为下:

  1. Before sending a line of mail text, the SMTP client checks the first character of the line. If it is a period, one additional period is inserted at the beginning of the line.

  2. When a line of mail text is received by the SMTP server, it checks the line. If the line is composed of a single period, it is treated as the end of mail indicator. If the first character is a period and there are other characters on the line, the first character is deleted.

然后就是每一行消息不能超过1000个字符,见RFC2821的text line小节。

之后的一些setsubject、setserver、addrecipent等等函数,都不做解释了,都是用来添加/删除主机、设置服务器、增加/删除收件人列表相关的,很好明白。我们重点说下邮件发送函数send()里的operator()()函数,如果lookupMXRecord为真,就调用gethostaddresses()函数,用来查询MX记录,这涉及到DNS协议相关知识,请查DNS小节。如果为fasle,则直接连接SMTP server,operator()()和makesmtpmessage()函数主要是完成了如下流程(并不完全一致,仅参考):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
C: telnet smtp.163.com 25 (连接到163的SMTP服务器,协议规定SMTP服务器的端口号为25)
S: Trying 202.108.5.83...
Connected to smtp.163.split.netease.com.
Escape character is '^]'.
220 163.com Anti-spam GT for Coremail System (163com[071018]) (220 表示连接成功)
C: HELO smtp.163.com (协议规定的握手过程,格式为HELO + 服务器名称)
S: 250 OK (250 表示握手成功)
C: AUTH LOGIN (AUTH LOGIN 是用户登录命令)
S: 334 dXNlcm5hbWU6 (334表示服务器接受)
C: tommy_mail (输入明文用户名)
S: 535 Error: authentication failed (服务器拒绝,因为SMTP要求用户名和密码都通过64位编码后再发送)
C: AUTH LOGIN (重新要求SMTP登录)
S: 334 dXNlcm5hbWU6
C: dG9tb*****FpbA== (用编码后的内容发送)
S: 334 UGFzc3dvcmQ6 (334表示接受)
C: ********aXZldXA= (编码后的密码)
S: 235 Authentication successful (235 登录成功)
C: MAIL FROM:<A@163.com> (MAIL FROM:<>格式,用来记录发送者)
S: 250 Mail OK (250 系统常用确认信息)
C: RCPT TO:<B@126.com> (接收者邮箱,可多次使用以实现发送给多个人)
S: 250 Mail OK
C: DATA (DATA明令表示以下为邮件正文)
S: 354 End data with <CR><LF>.<CR><LF>
C: TO:11@11 (发送给谁,这里可自由撰写,也是伪造邮件的一个入口,欺骗一般人可以,但会读源码的人欺骗不了)
FROM:22@22 (发送者是谁,可串改)
SUBJECT:TEST MAIL SMTP (邮件主题)
hello world (空一行写邮件正文)
. (正文以.结束)
S: 250 Mail OK queued as smtp3,DdGowLBLAjqD6_JIg1hfBA==.63235S2 1223879684 (服务器接受)
C: noop (空操作,延迟退出时间)
S: 250 OK
C: quit (退出SMTP服务器连接)
S: 221 Bye

DNS协议

调用gethostaddresses()函数,用来查询MX记录,这涉及到DNS协议相关知识,本函数可以使用nslookup命令模拟,我本地模拟如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
imlinuxer@imlinuxer:~$ nslookup
> set type=mx
> mail.qq.com
Server: 127.0.1.1
Address: 127.0.1.1#53
Non-authoritative answer:
*** Can't find mail.qq.com: No answer
Authoritative answers can be found from:
mail.qq.com
origin = qq.com
mail addr = webmaster.qq.com
serial = 1186990741
refresh = 300
retry = 600
expire = 86400
minimum = 86400

DNS查询的过程一般是:客户向DNS服务器的53端口发送UDP报文,DNS服务器收到后进行处理,并把结果记录仍以UDP报文的形式返回过来。除了报文头是固定的12字节外,其他每一部分的长度均为不定字节数。我们只关心的是报文头、问题、回答这三个部分
DNS的协议为rfc1035,但是枯燥难懂,可以查看参考链接的DNS消息格式,比较容易理解。

1
unsigned char dns[512] = {1,1, 1,0, 0,1, 0,0, 0,0, 0,0};

比如此处即为DNS Header消息头部信息。
之后几段代码是请求部分格式,代码里我已详细注释,之后发送请求,解析应答即可。

SMTP验证方式

比较简单,原理见此:SMTP验证方式种类(LOGIN、PLAIN、CRAM-MD5)
jwSMTP代码只实现了两种验证方式:LOGIN和PLAIN。

说的有点多了,感觉很多原理都解释了,逻辑稍微有一点混乱,主要是自己不是那么擅长组织语言,如果读者有兴趣,可以多了解下原理,知道SMTP和DNS原理,基本上代码就不需要多看了。

最后扔出我的中文源码剖析代码,在Github上:

https://github.com/armsword/Source/tree/master/jwSMTP

参考链接

关于base64编码的原理与实现
POP3 SMTP协议分析学习笔记
DNS消息格式

tinyhttpd源码剖析

喊了几天学习Web开发,为了毕业论文,今晚上计划也是看看CSS呢,但是实在是没忍住,读了下经典的tinyhttp的源代码,这款代码还是颇有名气的,网上这么评论的:

tinyhttpd是一个超轻量型Http Server,使用C语言开发,全部代码只有500、600行,附带一个简单的Client,可以通过阅读这段代码理解一个Http Server的本质。

其实,代码颇简单,适合刚学习Web Server的童鞋学习,因为我之前写过CGI Server,所以,我还是认为此代码写的一般,并且我在Ubuntu下编译遇到了不少错误,我都懒得写详细分析了,所以随便写下吧,后面的Github地址里有详细的分析。

源码下载地址:http://sourceforge.net/projects/tinyhttpd/

make编译后会有不少错误和警告,我这里说下怎么改正错误:

  1. Makefile文件里的:gcc -W -Wall -lsocket -lpthread -o httpd httpd.c ,修改为:
    gcc -W -Wall -o httpd httpd.c -lpthread

  2. 481行的 int client_name_len 改为 socklen_t client_name_len

  3. 436行 改动与上面相似,改为socklen_t类型即可。

  4. 34行改为void accept_request(void ); 所以下面的实现也要修改下:

1
2
3
4
5
6
7
8
9
void *accept_request(void* client1)
{
int client = *(int *)client1;
char buf[1024];
// 省略
// 同时注意此函数77 和129行改为return NULL;
// 497行改为
if (pthread_create(&newthread , NULL, accept_request, (void*)client_sock) != 0)

之后再make,程序就OK了。

简单说下程序的逻辑吧:

一个无限循环,一个请求,创建一个线程,之后线程处理函数处理每个请求,然后解析HTTP请求,然后做一些判断处理,之后判断文件是否可执行,不可执行,打开文件,输出给客户端(浏览器)呗,可执行就创建管道,父子进程通信。

整个流程就这么简单,程序主要处理2种HTTP请求方式:GET和POST,懒得说了,上传两张图片,自己分析吧,图片原始出处不清楚,电脑里存了好久了,。

GET:

POST:

其实这个源码里有一个地方比较难懂,就是那个解析HTTP每一行的那个get_line函数里的recv的MSG_PEEK参数,详细解释可以参考此链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 读取socket,判断换行,CRLF标志,之后以"\n"换行,并在字符串后添加'\0'
int get_line(int sock, char *buf, int size)
{
int i = 0;
char c = '\0';
int n;
while ((i < size - 1) && (c != '\n'))
{
// 一个字符一个字符的读取
n = recv(sock, &c, 1, 0);
/* DEBUG printf("%02X\n", c); */
if (n > 0)
{
if (c == '\r')
{
/*
* 注意MSG_PEEK参数,表示TCP Buffer不删除之前队列数据,从队列里接收数据
*/
n = recv(sock, &c, 1, MSG_PEEK);
/* DEBUG printf("%02X\n", c); */
if ((n > 0) && (c == '\n'))
recv(sock, &c, 1, 0);
else
c = '\n';
}
buf[i] = c;
i++;
}
else
c = '\n';
}
buf[i] = '\0';
return(i);
}

这代码,没啥写头,很多功能都没实现,请求只实现了GET和POST,Header里只用了第一行,CGI里全局变量只定义了几个,并且我验证程序,发现CGI功能好像是有些问题的,但是因为我CGI水平比较水,懒得检测原因了,总体来说,程序比我之前的那个CGI Server要简单些,功能要稍微弱些吧。

下面放出我Github里的详细中文注释,欢迎指正,谢谢:

https://github.com/armsword/Source/tree/master/tinyhttpd

Webbench源码剖析

我们知道知名的Web网站压力测试工具有Webbench、ab、http_load、siege等等,这种工具的源码都不是太长,所以,我用了一下午和晚上时间仔细了分析了Webbench的源码,并且写下这篇博客记录下。

我们先看下一般Webbench是怎么做压力测试的吧,方法很简单,如下所示:

1
2
3
4
5
6
7
8
9
10
#模拟200次请求,持续时间5秒的压力测试 -c 后为并发数, -t 后为持续时间
[imlinuxer@imlinuxer webbench-1.5]# webbench -c 200 -t 5 http://localhost/index.php
Webbench - Simple Web Benchmark 1.5
Copyright (c) Radim Kolar 1997-2004, GPL Open Source Software.
Benchmarking: GET http://localhost/index.php
200 clients, running 5 sec.
Speed=156804 pages/min, 128496336 bytes/sec.
Requests: 13067 susceed, 0 failed.

那Webbench的原理是怎么样的?其实也是很简单的,就是根据提供的参数构造HTTP请求Header,然后使用fork,创建指定大小(webbench提供的参数-c 后的数字,上文为200)个子进程,每个子进程利用socket创建TCP连接到URL,然后通过管道向父进程发送数据,父进程通过管道读取子进程的数据,并作累计,输出即可。其简单流程图如下图所示:


下面简单说下源码吧,源码很短,不到600行,两个文件,分别为socket.c和webbench.c。先说下socket.c,代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int Socket(const char *host, int clientPort)
{
int sock;
unsigned long inaddr;
struct sockaddr_in ad;
struct hostent *hp;
memset(&ad, 0, sizeof(ad));
ad.sin_family = AF_INET;
// 将字符串转换为32位二进制网络字节序的IPv4地址
inaddr = inet_addr(host);
if (inaddr != INADDR_NONE)
memcpy(&ad.sin_addr, &inaddr, sizeof(inaddr));
else
{
// 使用域名或主机名获取ip地址
hp = gethostbyname(host);
if (hp == NULL)
return -1;
memcpy(&ad.sin_addr, hp->h_addr, hp->h_length);
}
ad.sin_port = htons(clientPort);
sock = socket(AF_INET, SOCK_STREAM, 0);
if (sock < 0)
return sock;
if (connect(sock, (struct sockaddr *)&ad, sizeof(ad)) < 0)
return -1;
return sock;
}

自己封装了个socket模块,只需要注意的就是URL可能不是域名,也可能是IP地址。

然后就是webbench.c文件,咱们从main函数说起,因为需要对命令行做处理,所以使用了getopt_long函数,没使用这个函数的同学可以man getopt_long或者查看在线文件man 。注意下此结构体为getopt_long的参数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 长选项,getopt_long的参数
static const struct option long_options[]=
{
{"force",no_argument,&force,1},
{"reload",no_argument,&force_reload,1},
{"time",required_argument,NULL,'t'},
{"help",no_argument,NULL,'?'},
{"http09",no_argument,NULL,'9'},
{"http10",no_argument,NULL,'1'},
{"http11",no_argument,NULL,'2'},
{"get",no_argument,&method,METHOD_GET},
{"head",no_argument,&method,METHOD_HEAD},
{"options",no_argument,&method,METHOD_OPTIONS},
{"trace",no_argument,&method,METHOD_TRACE},
{"version",no_argument,NULL,'V'},
{"proxy",required_argument,NULL,'p'},
{"clients",required_argument,NULL,'c'},
{NULL,0,NULL,0}
};

之后是buildr_equest()函数,主要功能是构造HTTP头请求,构造成下面类似情况,具体可以参考代码:

1
2
3
4
GET / HTTP/1.1
Host: www.baidu.com
Cache-Control: max-age=0
Pragma: no-cache

之后便是打印压力测试的一些信息,没啥可说的,很容易读懂,之后到了return bench()处,bench函数是压力测试的核心代码。
bench里根据并发数,使用fork()创建子进程,子进程调用benchcore()函数,此函数里使用alarm和sigaction信号控制定时时间,alarm函数设置了多少时间之后产生SIGALRM信号,一旦产生此信号,运行alarm_handler函数,使得timerexpired等于1,这样可以通过判断timerexpired值来退出程序。然后子进程将数据写入管道。同时父进程读取管道数据,将数据进行累加,当全部读取完子进程后,父进程输出信息退出。

总体来说,Webbench代码还是很好读懂的,当然此代码也存在一些问题,比如不支持POST请求方式,只能模拟单个IP测试等等。
宿舍马上要熄灯了,写的比较着急,可能逻辑混乱些。我Github里对此源码做了非常详细的源码剖析。感兴趣的同学请查看详细的源码剖析吧。

链接地址:
https://github.com/armsword/Source/tree/master/webbench-1.5

Redis AE事件库源码剖析

很久之前就看过AE库了,不过这东西好久不看,也忘得差不多了,正好要找工作了,简历上写了之前的项目用过这个AE事件库,索性我就又把AE库看了一遍,本来表达能力就差,复习下吧。

先上张图,下图左侧是ae.c文件里所有的函数,一目了然。

AE事件库包含文件事件和时间事件,其包含2个源文件ae.c和ae.h,当然还有四个不同的多用复用封装的文件:ae_epoll.c、ae_select.c、ae_evport.c、ae_kqueue.c。一般常用的是ae_select.c(跨平台用),linux下多用ae_epoll.c。我们就以ae_epoll.c为例吧。

我们先说说文中用到的几个结构体:

aeEventLoop 核心数据结构,每个aeEventLoop对应一个event loop。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* State of an event based program */
typedef struct aeEventLoop {
int maxfd; /* 现在注册的最大文件描述符 */
int setsize; /* 跟踪文件描述符的最大数量 */
long long timeEventNextId; //下一个timer的id
time_t lastTime; /* 用来诊断系统时间偏差 */
aeFileEvent *events; /* 用于保存epoll需要关注的文件事件的fd、触发条件、注册函数 */
aeFiredEvent *fired; /* poll_wait之后获得可读或者可写的fd数组,通过aeFiredEvent->fd再定位到events*/
aeTimeEvent *timeEventHead; //以链表形式保存多个时间事件,每隔一段时间机会触发注册的函数
int stop; //停止运行的标志
void *apidata; /* This is used for polling API specific data */
aeBeforeSleepProc *beforesleep; //阻塞地等待下一个事件发生之前要执行的函数
} aeEventLoop;

aeFileEvent是文件事件结构体,mask是要捕获的事件的掩码(读|写),rfileProc和wfileProc分别指处理文件读和写事件的函数,clientData是函数用的参数。

1
2
3
4
5
6
7
/* File event structure */
typedef struct aeFileEvent {
int mask; /* one of AE_(READABLE|WRITABLE) */
aeFileProc *rfileProc;
aeFileProc *wfileProc;
void *clientData;
} aeFileEvent;

aeFiredEvent指的已准备好的文件事件的结构体,包括fd(文件描述符)和mask(掩码):

1
2
3
4
5
/* A fired event */
typedef struct aeFiredEvent {
int fd;
int mask;
} aeFiredEvent;

aeTimeEvent 是时间事件用到的结构体,id是指的这个定时器的id,when_sec、when_ms分别指的秒和毫秒,timeproc是时间处理函数,finalizerProc是定时器被删除的时候的回调函数,next指的下一个结点,定时器事件是一个链表形式存储的各个时间事件,无序的。

1
2
3
4
5
6
7
8
9
10
/* Time event structure */
typedef struct aeTimeEvent {
long long id; /* time event identifier. */
long when_sec; /* seconds */
long when_ms; /* milliseconds */
aeTimeProc *timeProc;
aeEventFinalizerProc *finalizerProc;
void *clientData;
struct aeTimeEvent *next;
} aeTimeEvent;

下面这个结构体用在epoll创建,aeCreateApi()里使用:

1
2
3
4
typedef struct aeApiState {
int epfd;
struct epoll_event *events;
} aeApiState;

下面来说说程序流程吧,再说aeMain()函数之前,我先说下一些准备动作吧,分别为aeCreateEventLoop()、aeCreateTimeEvent()、aeCreateFileEvent()和aeSetBeforeSleepProc()。 aeCreateEventLoop()创建一个aeEventLoop结构体,做些初始化,之后调用函数aeApiCreate(),如上述结构体,epfd由epoll_create创建,*events 保存epoll_wait返回的事件组。 aeCreateFileEvent()为fd注册一个文件事件,使用epoll_ctl加入到全局的epoll fd 进行监控,之后再指定事件可读写处理函数。 aeCreateTimeEvent()注册一个时间事件,使用aeAddMillisecondsToNow()加入时间事件。 beforesleep 就是个回调函数,sleep之前调用的函数,有些事情是每次循环必须做的,并非文件和时间事件。

1
2
3
void aeSetBeforeSleepProc(aeEventLoop *eventLoop, aeBeforeSleepProc *beforesleep) {
eventLoop->beforesleep = beforesleep;
}

下面说说核心循环函数aeMain()吧:

1
2
3
4
5
6
7
8
void aeMain(aeEventLoop *eventLoop) {
eventLoop->stop = 0;
while (!eventLoop->stop) {
if (eventLoop->beforesleep != NULL)
eventLoop->beforesleep(eventLoop);
aeProcessEvents(eventLoop, AE_ALL_EVENTS);
}
}

由stop来决定是否停止,beforesleep可以决定它是否停止,但redis里beforesleep就是一个实现,做的工作只是保证aeProcessEvents要用到的fd都准备好。aeProcessEvents一般会阻塞的(有例外)等待事件(时间和文件事件)的发生,然后做一些处理,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
* The function returns the number of events processed. */
int aeProcessEvents(aeEventLoop *eventLoop, int flags)
{
int processed = 0, numevents;
/* Nothing to do? return ASAP */
if (!(flags & AE_TIME_EVENTS) && !(flags & AE_FILE_EVENTS)) return 0;
/* Note that we want call select() even if there are no
* file events to process as long as we want to process time
* events, in order to sleep until the next time event is ready
* to fire. */
if (eventLoop->maxfd != -1 ||
((flags & AE_TIME_EVENTS) && !(flags & AE_DONT_WAIT))) {
int j;
aeTimeEvent *shortest = NULL;
struct timeval tv, *tvp;
if (flags & AE_TIME_EVENTS && !(flags & AE_DONT_WAIT))
shortest = aeSearchNearestTimer(eventLoop);
if (shortest) {
long now_sec, now_ms;
/* Calculate the time missing for the nearest
* timer to fire. */
aeGetTime(&now_sec, &now_ms);
tvp = &tv;
tvp->tv_sec = shortest->when_sec - now_sec;
if (shortest->when_ms < now_ms) {
tvp->tv_usec = ((shortest->when_ms+1000) - now_ms)*1000;
tvp->tv_sec --;
} else {
tvp->tv_usec = (shortest->when_ms - now_ms)*1000;
}
if (tvp->tv_sec < 0) tvp->tv_sec = 0;
if (tvp->tv_usec < 0) tvp->tv_usec = 0;
} else {
/* If we have to check for events but need to return
* ASAP because of AE_DONT_WAIT we need to set the timeout
* to zero */
if (flags & AE_DONT_WAIT) {
tv.tv_sec = tv.tv_usec = 0;
tvp = &tv;
} else {
/* Otherwise we can block */
tvp = NULL; /* wait forever */
}
}
numevents = aeApiPoll(eventLoop, tvp);
for (j = 0; j < numevents; j++) {
aeFileEvent *fe = &eventLoop->events[eventLoop->fired[j].fd];
int mask = eventLoop->fired[j].mask;
int fd = eventLoop->fired[j].fd;
int rfired = 0;
/* note the fe->mask & mask & ... code: maybe an already processed
* event removed an element that fired and we still didn't
* processed, so we check if the event is still valid. */
if (fe->mask & mask & AE_READABLE) {
rfired = 1;
fe->rfileProc(eventLoop,fd,fe->clientData,mask);
}
if (fe->mask & mask & AE_WRITABLE) {
if (!rfired || fe->wfileProc != fe->rfileProc)
fe->wfileProc(eventLoop,fd,fe->clientData,mask);
}
processed++;
}
}
/* Check time events */
if (flags & AE_TIME_EVENTS)
processed += processTimeEvents(eventLoop);
return processed; /* return the number of processed file/time events */
}

注意参数flags,当为AE_DONT_WAIT时就表示是不阻塞的检查关注的事件是否发生了,如果没发生则直接返回0。
aeProcessEvents处理过程如下:
首先通过调用aeSearchNearestTimer找到离现在最近的定时器是什么时候,这个地方其实做的不好,不如libevent的定时器,需要O(N)得到最短时间,可以改为最小堆保存时间,然后将得到的时间作为参数传给aeApiPoll,作为其timeout参数,来返回命中的文件事件数目,查看eventLoop->fired,可以取出命中事件的详细信息,然后调用rfileProc或wfileProc做事件读写处理,最后再调用processTimeEvents处理已经触发了的定时器事件,然后返回所有已处理的事件(文件和时间)总和。
最后,参考链接里的那个Redis执行流程图还是挺有借鉴意义的,图片太大,我就不转过来了,参考链接在最下方。

PS:边看边写,写到此处竟然又晚上两点多了,现在作息时间越来越乱,等拿到offer后,需要调整下生物钟了。

参考链接:http://my.oschina.net/qichang/blog/32469