文件描述符传递方式的开销

以前提到过用文件描述符传递方式解决多进程惊群问题。最近实际测试了一下这种实现，发现实际效果不佳。较多进程无锁方式（nginx的实现减少进程锁）差得多，仔细思考了下，理论上应该这样解释这个原因：

1. 进程间文件描述符传递方式在接收一次连接时，整个系统会有 accept, sendmsg, recvmsg, epoll_ctl四次系统调用

2. 多进程无锁方式尽管有惊群效应，但接收一次连接时，最多N进程 × 1（accept）次系统调用，而且sendmsg调用开销远较一次accept为大。

3，文件描述符传递方式还存在进程间切换，以及发送接收数据的时间开销

综上，Nginx的实现方式尽管复杂，却是最高效的方式。

一种HTTP模拟全双工Socket通信的实现

最近几天把很早之前构思过的一种HTTP模拟全双工Socket通信的方法在Snova/GSnova C4上实现了，效果不错，这里简单介绍一下实现方法。若有其他对此感兴趣的朋友，可以一起研究讨论。
Snova C4利用双HTTP连接 + Chunked transfer encoding 模拟实现一个全双工通信的TCP Socket。具体HTTP代理实现流程文字描述如下：

• 浏览器发送HTTP请求到本地C4；
• 本地C4创建两个HTTP连接到远端C4，其中一个携带加密后的HTTP请求内容，另一个则只携带读请求；
• (重要)远端C4收到第一个HTTP连接后，将HTTP请求解开，创建到目的Site的连接，发送具体HTTP请求，之后到本地C4连接马上返回；
• 远端C4收到第二个HTTP连接后，阻塞在第一个HTTP连接中创建的Socket读上，每读取一段内容，则将内容加密通过HTTP应答消息体返回给本地C4；注意这里的应答内容必须通过Chunked transfer encoding 方式发送；
• 本地C4收到第二个HTTP连接的应答后，不断读应答消息体，将解开的内容写回到浏览器。至此整个Proxy过程大致结束。

若是HTTPS代理的情况，稍有不同：

• 浏览器发送Connect请求到本地C4；
• 本地C4创建两个HTTP连接到远端C4，其中一个携带加密后的Connect请求内容，另一个则只携带读请求；
• (重要)远端C4收到第一个HTTP连接后，将Connect请求解开，创建到目的Site的连接，发送具体HTTP请求，之后到本地C4连接马上返回，携带“200 Established”应答内容；
• 远端C4收到第二个HTTP连接后，阻塞在第一个HTTP连接中创建的Socket读上，每读取一段内容，则将内容加密通过HTTP应答消息体返回给本地C4；注意这里的应答内容必须通过Chunked transfer encoding 方式发送；
• 本地C4收到第二个HTTP连接的应答后，不断读应答消息体，将解开的内容写回到浏览器；
• 同时本地C4不断读取浏览器连接Socket，将读取的内容通过第一个HTTP连接发送到远端C4；远端C4收到后，则不断写到socket中。
• 以上两步同时循环执行。

若是其他非HTTP协议的TCP代理，过程类似HTTPS的情况。

其实，Chunked transfer encoding默认在HTTP协议中是请求/应答都可以携带的，若在HTTP请求中也采用类似上述应答的方式，效果应当更好。不过在目前的几个PaaS平台中，几乎都不支持HTTP请求带Tansfer-Encoding。
最终的实现的效果相当不错，相比之前的心跳ping机制（也可以模拟全双工Socket通信），实时性大大提高，甚至访问视频网站这种对socket通信连接稳定性要求较高的场景也表现良好。
题外的话：大部分PaaS限制了一个HTTP请求的最大时长，一般是30s。所以在C4的实现中是用一点小技巧绕过这个限制，需要实现类似机制的朋友可以提前注意一下。

分裂的神经

技术：
继续在X项目花费零碎时间。这几天一直纠结于一个问题，抽象成计算机语言描述就是：
一个二级int hashmap(key为int)，即hashmap的value是另一个int hashmap， 如何按照规则A输出其中指定起始位置，指定个数的元素，元素在第二级hashmap的value中。
规则A：按照元素所属的hashmap间隔排列，即一级hashmap含10个二级hahsmap，若输出10个元素，则10个元素分属10个hashmap；
直觉的实现应该是全部将元素输出到数组，按照上述规则排序并输出。这种方法效率非常低，增加了一倍的空间存储临时元素，并耗费大量CPU排序，当元素个数巨大时，这样的算法对系统的影响是非常大的。
今天专门抽出时间仔细思考了这个问题，用了一种方法简洁的实现这个需求：用vector代替第二级hashmap，这样输出元素时，记录每次的输出的vector下标，即可近似的用二维数组的输出规则输出元素。这样的实现只用了20行左右代码，效率也相当高，算法复杂度等同于顺序迭代访问每个元素。这里的要点在于用vector代替原先hashmap。
有时，针对某些问题，用另外一种思维方式会取得意想不到的效果。

胡思：
重又将20余年前的历史在wiki上回顾了一次。每次看都有不同的感受，不同的思考，特别是在读过《1984》，《俄国人》之后。李贺诗言”临岐击剑如铜吼“，大概就是目前这种感受。
村上春树也在《1Q84》中描绘了一个初始以社会主义为目的后逐渐演变为类邪教的组织。大约持统一思想论的组织，无论高尚与否，大都最后都会异变。
“没人要和你玩平等的游戏 每个人都想要你心爱的玩具”——《亚细亚的孤儿》

Linux下传送文件描述符的几个问题

这两日仍抽空忙于项目的设计开发，遇到了两个关于Linux下传送文件描述符的问题，记录如下：

1. Linux不支持类似SystemV的流管道传递文件描述符（即非FIFO/tcp socket等），只支持通过UnixSocket方式。目前只有类似Solaris的系统支持前者。

   不得已，修改了arch中相关代码，单独打开了一对UnixSocket专用于文件描述符传送。

2. 64位系统下，接受文件描述符侧进程在recvmsg调用返回后结构struct msghdr变量中msg_controllen大小较结构struct cmsghdr变量中cmsg_len大4个字节；在32位系统下两者相等。

    在64位系统只传送1个文件描述符的情况下，前者大小为24字节而后者20字节。若按照APUE中代码的判断规则则是失败的，按照UNP中则可以通过。（Ubuntu 64/32）

尤其是后一问题，折腾了许久才发现32位与64位的不同，目前参考UNP修改了判断语句以规避此问题，后续有时间的话还需要对原因进一步探讨。

仰视皇天白日速

最近从零开始写一个创业项目的后台代码，十余天的功夫竟已吭哧吭哧写了上万行代码，可谓“高产”了。同时遇到的并纠结的实际技术问题还是不少，例如mysql无异步C API，NFS存放图片，HTTP服务，protobuf，缓存，关键词搜索等问题，都需要时间一一解决。 不过好在尚有“先见之明”，前年底就开始独力写了一个已用到生产项目中的arch框架，为此次项目省事不少。
这段时间也随手总结加强了几条在后台C/C++开发上的经验/教训：
1. 尽量用进程协作方式，而非多线程
2. 设计实现中，考虑对栈对象友好的方式而非堆对象
3. 异步协议，而非同步协议
4. 尽量避免对象池的应用，用优化的malloc实现代替，如tcmalloc，jemalloc等。（Boost的对象池在大量小对象（10w级）性能糟糕）
5. 通用的功能考虑拆分到独立进程中实现，其它组件通过协议/进程间调用来访问。
6. std::list的size方法不是常量时间，随list长度增加（这倒是以前没想到过的）
7. 默认的G++编译器4.0之后已经提供了部分tr1实现，如hashmap->unordered_map等。
凑足七条，算作“呜呼七歌兮悄终曲”吧。

后记：
1. 这两天读了几篇李商隐和杜诗，愈读愈发觉得积聚了不少沉郁之气。
2. 联想到当下及数月之后，竟隐有“筵席渐散”之感。

一种代替dynamic_cast的模版RTTI实现

在arch框架中，存在这样一种场景：一个IO Channel上顺序注册了一组handler，分别处理不同类型的事件消息，则当某个事件消息到达时，需要依次判断handler是否能处理该类型的消息。（参考自Jboss-Netty的设计）。这类操作是在网络服务是进行，执行次数最多，因此需要考虑一个高效的实现。
最初的实现是模仿Netty中Java的实现，用dynamic_cast判断（Java中是InstanceOf判断），但用dynamic_cast总觉得不太优雅，性能可能也存在问题（参考附注）。
最近有些空闲时间，重新思考了下这个问题，用了另外一种方法代替dynamic_cast实现
1. 注册handler接口方法用模版方法代替，将该携带类型信息的handler注册到一个和该类型相关的模版类中，如红色框部分。当然，在handler析构时需要去注册   

2. 和该类型相关的模版类用静态set保存注册信息；

3. 判断事件类型与handler相关联信息，则可调用该模版类的静态方法。时间复杂度为set的实现决定。这里用tr1::unordered_set保存指针，时间复杂度为O(1)。 从理论上应当比用dynamic_cast快的多。(测试发现新方案较dynamic_cast实现快60%以上)
附注：
1. Google的编程规范强烈建议不要在产品代码中使用dynamic_cast。
2. 据一份评测报告显示，一次dynamic_cast可能消耗数十微秒，这个评测待验证。数十微秒显然太慢了。

大量短连接的Server中的惊群问题

最近继续完善自己的多进程非阻塞网络服务框架arch，对于所谓的惊群（Thundering herd）的问题，查看了在这个问题上nginx源码以及其它一些非开源代码，公司内部代码中的处理方式，有以下的思考：

惊群问题（Thundering herd problem），wiki上的解释简单说是“大量处理进程/CPU阻塞在一个调用上，由于某个触发条件导致都被唤醒，但只有一个进程能继续处理，其它均失败”。惊群现象会浪费较多的CPU。这种现象可以出现在很多场景中，以下讨论的具体场景为处理大量短连接的Server中的惊群。

这种场景以Web Server为典型，一般有多个进程/线程同时监听80端口（poll非阻塞IO方式），则当有一个客户端连接上来时，所有的等待者均被唤醒，继而都调用accept处理，但只有一个能成功，其它均失败。

目前较多的实现是基本不考虑惊群问题，如检查的第一个公司内部实现代码，lighthttpd。Redis因为是单进程单线程的实现，故没有考虑此问题。

Nginx是用进程锁的方式解决该问题，即确保在某一个时刻，只有一个进程监听端口处理接收的连接；后续通过比较复杂的手段在多个进程间切换监听工作达到负载均衡的效果，仍然用到进程锁。

 

Nginx的实现对于我来说过复杂了。我在arch中用了一个较为简单方式解决这个问题。

arch是一个多进程的框架实现，故这里先讨论多进程模型下的一种较简单的解决方法：

1. 一个主控进程（Manager）监听指定端口，将FD加入到非阻塞IO集合中，用类poll方式监听（select/poll/epoll）

2. 启动N（N=CPU个数）个工作IO进程（Worker），建立Worker和Manager之间的通信连接（Linux下只能用UnixDomainSocket， 某些Unix可用Stream管道）

3. 以上是进程初始化时的工作，当一个连接发生时，Manager接受此链接，马上将该连接的文件描述符发送到一个Worker进程（同时关闭文件描述符），马上返回到自己的等待状态等待处理下一个连接；（这里的选择Worker进程即是复杂均衡的判断逻辑，一般来说轮询选择就可以达到较好的平衡状态）

4. Worker进程接收到文件描述符后，加入到自己的非阻塞IO集合，读取数据处理业务逻辑

同Nginx的实现一样，arch也避免了惊群现象，不同之处在于arch用到了进程间文件描述符传送，避免了复杂的锁实现；而Nginx用了进程锁，避免了文件描述符传送的系统调用；后续会比较一下两者性能区别。

 

多线程模型下较为简单，只需要采用类似Nginx的锁方式，结合arch的manager+worker模型：

1. 启动Manager线程，监听定端口，将其加入到非阻塞IO集合中，用类poll方式监听（select/poll/epoll）

2. 启动N（N=CPU个数）个工作IO线程（Worker）

3. 当一个连接发生时，Manager接受此链接，马上将该连接的文件描述符交给一个Worker线程马上返回到自己的等待状态处理下一个连接；（这里的选择Worker进程即是复杂均衡的判断逻辑，一般来说轮询选择就可以达到较好的平衡状态）

4. Worker线程接收到文件描述符后，加入到自己的非阻塞IO集合，读取数据处理业务逻辑。

不过，对于编写C/C++的Server程序来说，多线程应当是尽量避免的。这倒是题外话了。

Snova的C4在几个免费PaaS平台上的部署（Openshift， CloundFoundry， Heroku， Jelastic）

C4主要是从snova-heroku部分移植，修复了一些bug，性能大大增强，实用性大为增强，不再只是玩具试验性质的东东了。

Openshift

• 注册帐号

          到这个链接注册https://openshift.redhat.com

• 安装工具

          安装命令行工具rhc，安装依赖ruby以及gem， https://openshift.redhat.com/app/express#quickstart

          注意， gem安装rhc可能被防火墙中断，可能需要设置代理，代理可以用snova设置，如

                   gem install --http-proxy http://127.0.0.1:48100 rhc

• 部署

           将snova-c4-server-[version].war 放到一个创建的空目录下，然后在命令行下进入该目录，逐个执行下面的命令:

      rhc-create-domain -n <domainName> -l <yourId> -p <yourPassword>  创建主域名， 部署新应用是这一步可不执行
      rhc-create-app -a <appName> -t jbossas-7.0 -p <yourPassword> 创建app
      cd <appName>   进入上一步创建的目录
      mv ../snova-c4-server-[version].war <appName>/deployments/ROOT.war
      git rm -r src pom.xml
      git commit –m “delete”
      git push                         以上三步重新部署同一个app时可不执行
      git init 
      git add .
      git commit –m “deploy”
      git push

CloundFoundry

• 注册帐号

          注册， https://my.cloudfoundry.com/signup， 注意，注册不是马上成功，似乎是第二天才会收到注册成功的邮件

• 安装工具

          安装命令行工具vmc，安装依赖ruby以及gem，和openshift的工具rhc安装过程类似

          http://start.cloudfoundry.com/tools/vmc/installing-vmc.html

• 部署

          将snova-c4-server-[version].war放到任意的空目录下，然后在命令行下进入该目录，逐个执行下面的命令

      vmc target api.cloudfoundry.com
      vmc login
      vmc push <appname>  —— 此处appname为任意名称，为域名一部分，此命令执行后有后面的交互，参照下面的输入Y/N
       Would you like to deploy from the current directory? [Yn]: Y
       Application Deployed URL [<appname>.cloudfoundry.com]: <回车>
       Detected a Java Web Application, is this correct? [Yn]: Y
       Memory Reservation (64M, 128M, 256M, 512M, 1G, 2G) [512M]:   <回车>
       Creating Application: OK
       Would you like to bind any services to 'snova4'? [yN]: n
       Uploading Application:
        Checking for available resources: OK
        Processing resources: OK
        Packing application: OK
        Uploading (843K): OK
       Push Status: OK
       Staging Application: OK
       Starting Application: OK

Heroku

参考snova中heroku的wiki即可

Jelastic

• 注册帐号

          http://jelastic.com

• 部署

          完全图形化的操作，无需安装工具，按照说明将war上传并deploy到ROOT下即可

          http://jelastic.com/docs/upload-deploy-application

后记：

这几个所谓的PaaS平台中，粗略观察下，纯以平台IO性能而言，似乎Openshift较差，CloundFoundry最好，已接近或超过AppEngine；部署上，Jelastic部署最为简单，完全界面上操作，其它几个则相对复杂，需要安装各种复杂的命令行工具部署，简直到了”非程序员不能为也的地步”了。

字符串匹配算法

今日，研究了一天的字符串匹配算法，小有所得。主要是从这个链接学习， http://www-igm.univ-mlv.fr/~lecroq/string/

理论上，这里算法都比glibc中strstr的算法复杂度小，但在实际场景中，特别是和目前的开发的产品中关键字匹配场景下，无论是Boyer-Moore还是Knuth-Morris-Pratt等这些经典的算法实现都比strstr慢得多，而strstr的默认算法仅是一种高度优化过的Brute Force实现（Linux下C的测试结果证明如此，java下根据默认string.IndexOf算法看来，可能另有差别，需要进一步证明）。

目前得到一点结论是，这些经典的算法中都有预处理阶段，而Brute Force实现并无此阶段，当是预处理阶段耗时较多造成的差别。

（从200字节中查找20字节字符串1000000次， strstr:0ms, 其它最优的实现是250ms+）

关于snova-heroku的一二三

 

大约圣诞节前一天，发现了heroku这个PaaS平台，看了一下wiki以及heroku.com上的介绍，觉得有些意思；后来正好工作上没多少事情，花了半天仔细看了一下这个平台相关技术架构，虽然不甚了了之处仍有不少，不过大致上已经了解到从技术角度而言对于heroku，可以用来做些什么以及不可以做些什么。

heroku本质上是一个分布式环境，但对于开始的免费账户只提供一个dyno（heroku的特有概念，类似Instance），CPU大约是750h/month，带宽没有限制。支持的语言较多，主要是ruby，另外python/java目前也支持。Runtime上限制远比Google的AppEngine为少，以Java为例，从语言角度来看几乎没有任何限制，目前观察到的唯一“限制”就是App的input只能是HTTP请求，当然这是基于Web的PaaS的必要条件，也谈不上限制了。

后来的一天，着手写了一些代码，初步验证开始的想法正确；由于之前一段时间写了一个基于GoogleAppEngine的proxy，而这个proxy有不少Appnegine平台的限制，正好heroku没有这些限制，于是开始着手实现基于heroku的proxy。

实现的过程总体上是顺利的，除了当中偶发奇想用一些P2P技术代替HTTP请求耽搁了几天，最后大约2011.12.30完成所有实现。之后两天主要修改项目上的wiki以及snova项目的其它子项目，在2012到来的第一天正式release。

注：1. 用一些P2P技术代替HTTP请求从原理上任然是可行的，不过相对目前的实现几乎没有任何性能优势；2. 目前的实现通过异步IO+定期轮询绕过了较多的技术限制，但这种技巧在分布式环境中算是一种错误方法，只不过由于免费环境只有一个dyno才得以利用。

 

http://code.google.com/p/snova/wiki/HerokuInstallation

2012.01.02 小恙中记