tinyhttpd源码剖析

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

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

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

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

Read More

Webbench源码剖析

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

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

1
2
3
4
5
6
7
8
9
10
11
#模拟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.

Read More

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为例吧。

Read More

一致性哈希算法

一致性hash算法在分布式系统里面使用比较广,我也只是听说过这个概念,今天看到一个一致性hash开源库,随手写篇文章,记录下吧。

假如我们使用普通的哈希方式来处理负载均衡,到目标机器的映射使用的算法为:

hash(o) mod n (n表示机器的总数)

如果需要增加或减少一台机器的时候,算法就变为 hash(o) mod (n + 1) / hash(o) mod (n - 1)

不仅需要重新编写代码,当服务器做了大量变更,大量的o会重定向不同的服务器而导致了缓冲不被命中,所以此时,就提出了一致性hash算法。

一致性哈希算法:

简单的说,哈希函数将o映射到 0 ~ 2^32 - 1的值区间,将这些数字头尾相连,然后将它们组织成一个闭合的圆环。如图一所示:

要实现一致性哈希算法,思路就是下面2个步骤:

Read More

写了一个简单的CGI Server

之前看过一些开源程序的源码,也略微知道些Apache的CGI处理程序架构,于是用了一段时间,用C写了一个简单的CGI Server,代码算上头文件,一共1200行左右,难度中等偏上。麻雀虽小,五脏俱全。如果把程序里所涉及的HTTP协议,Linux下POSIX编程等等搞清楚,我想找工作中肯定是有足够的竞争力的,当然我也只是皮毛而已,不再班门弄斧了,下面简单的说下程序流程吧。

再说程序流程之前,我先简单说下CGI吧,CGI这个东西比较老了,N年之前,没有PHP JSP等等动态脚本之前,这个是非常火的。只要能支持输入输出的程序,都可以编写CGI脚本,比如Apache就集成了CGI服务器功能,你可以使用Python编写简单的CGI脚本,可以参照前几天我发的文章,点击此处,现在CGI 脚本基本上使用的比较少了,但是在一些对效率要求比较高的设计里还是可以看到一些身影,比如腾讯的QQ相册,QQ空间里就可以看到(你可以打开QQ空间,查看源码-查找CGI),他们的脚本应该是C/C++编写的,效率,你懂的,如果你想更多的了解CGI脚本相关,可以点击此处,推荐了解一些,但是不值得深入学习,那个精力不如学习PHP/Python了。。。

其实说白了,CGI 扮演的就是在服务器和特定解释器之间输入输出协议的角色,每个来自用户的请求,Web服务器都会唤起特定语言解释器的命令行,执行CGI脚本。

现在来介绍下此CGI Server,我不想长篇大论了,一幅图来描述其执行过程(字比较丑,凑合看吧),具体看代码吧:

Read More

Redis里dict源码剖析

Redis全名叫做Remote Dictionary Server,从全称就可以看出dict是Redis里重要的数据结构,看了下dict.c里的源码,简单分析下。

dict.c主要是实现了哈希功能,实际上实现哈希(字典)常见的方法有几种:

<1>比如我们数据结构课上学的数组和链表法,但是这种方法适用于元素个数不多的情况下

<2>使用复杂的平衡树(B-等等),性能比较不错,比如MySQL里的索引就使用了这种方法

<3>哈希表,兼顾了高效和简单性,Redis选择了这种方法。

我们就解读下dict.c里源码里的数据结构吧,我们知道hash表的性能由hash表的大小和解决冲突的方法决定。Redis里使用了两个哈希表(ht[0])和哈希表(ht[1]),hash[0]是字典主要使用的hash表,而hash[1]主要对0号哈希表进行rehash时才使用。读者可能不明白这个地方啥意思?其实就是,程序每次申请几个字节(默认为4字节),当key/value数量达到规定时,程序申请的4字节就翻一倍(这里使用了慢迁移),那什么时候rehash呢?我们知道size == used(根据下面的dictht结构体)时,达到最理想状态,所以当used/size > 1时,就进行rehash。我们先看看dict.h里定义的几个结构体吧:

Read More

Letter Combinations of a Phone Number

由于这个月还没写博客,找道题应付下吧,主要原因是自己现在太忙了,得准备找工作啊,唉,弱的惨不忍睹。好吧,不抱怨了,进入正题,LeetCode上面的一道题,题目描述为:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

**Input:**Digit string "23"
**Output:** ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
**
Note:**
Although the above answer is in lexicographical order, your answer could be in any order you want.

其实就是组合问题,如下图所示:

如图所示,遍历完 1,2,3,就把a,d (g,h,i)遍历完了,之后回溯到e,就是个DFS搞定。

Read More