手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜Qcloud , 注册 | 登陆

yhustc:Twisted+AC自动机构建高效的过滤服务器

首页 > python >

这是yhustc帮烂桔搞定AC自动机的过程。上次在PHPX上看到也有人用PHP实现了一个,但我估计在大并发的时候,效率也不会高到哪里去。PHP纯处理字符串效率毕竟还是不咋地。。如果用perl呢?没试过。。。。还是看一下yhustc怎么实现在的吧。
yhustc的网址是:http://www.yhustc.com ,yhustc在文中还提到了twisted,我没用过这个玩意,后来google了一下,发现还是很迷糊。
原文内容如下:

橘子有个网站,访问量大约每天500万PV,为了怕被屏蔽,需要对一系列敏感词进行过滤(超过1200个词),然后才输出内容给用户。

替 换给定关键词的功能,每种编程语言都有,PHP的最强大。基于正则匹配替换的大家都有,就不提了。基于精确匹配的字符串替换,PHP的 str_replace函数可以根据给定的数组,一次函数调用对多关键词进行匹配。自然橘子用的也是这个咯(如果使用的是for i < 1200 顺序的循环,基本系统效率可以无视了)。可是现在问题出现了:系统负载非常高,而且是持续的高,晚上10点的高峰期CPU一直100%的满负荷运行。

要优化性能,就需要一步步的分析瓶颈在什么地方:

1、 由于橘子说有些关键词以后没准会解封,所以不想把原始内容就保存为带上一堆****这样子。因此原始内容都保存的好好的,那么给用户输出的,是每次过滤过 后的结果。那么这里自然有个问题,就是相同的内容,针对每个用户都被过滤了一次,这不明摆着的CPU浪费嘛。我说你可以考虑空间换时间, 加硬盘后上缓存,一定时间内都只过滤一次,其他用户都读缓存即可,这样计算开销几乎全部省下来了。但是橘子哭穷啊,SSD的硬盘两千多一块。IDE的插上 去就得给机器断点,现在百度正在考验自己的站点,这个电断不得(如果IDC够好的话,夜里换其实没啥问题,偏偏他的IDC技术不照)。那行,看来还是只能每次都过滤了,你爱折腾我也没办法。

2、分析一下PHP的str_replace,他既然支持多关键词的数组输入,说明内部肯定是一个AC自动机。 什么是AC自动机,大家请自行google并学习,我就不长篇大论了。本来多关键字替换的应用,AC自动机是最好的选择,但是为啥他的服务器负责就是居高 不下呢?这与PHP的实现机制有关,PHP的生命周期是一个WEB请求,那么每个用户请求页面时,调用一次str_replace。即使输入的数组是一摸 一样的,也必须重新构建一个AC自动机的搜索树,这个搜索树初始化的计算开销以及内存开销乘以并发数,严重降低了系统性能。(也不全是PHP生命周期引发 的,主要是因为AC自动机是封装在str_replace内部实现的,即使是串行的调用,相同输入仍然会每次都初始化自己的搜索树)

那么我们现在的问题就很明确了:实现一个全局的AC自动机,用他来处理所有的请求即可。这个任务PHP是没法执行了,加之要找AC自动机的相关模块才能自己二次开发,选定了python来干这个事情。https://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/  这里是python的AC自动机的模块,非常的简单易用,看看就会。 

读 取关键词列表,添加关键词,构建搜索树,OK!测试一下关键词的搜索效果,windows平台下10000次的循环搜索,python的程序比直接用 PHP的str_replace执行时间缩短了200倍,当时震惊的一塌糊涂!!(不过这跟PHP在windows平台执行效率低也有关系,linux上 面明显要快非常多)

话不多说,把python的程序封装到一个Socket TCP Server里面,这样便于WEB的PHP程序通过套接口请求服务,把原文发过来,过滤后又发回去,这样就实现了一次过滤。 

高高兴兴的把程序发给橘子,结果一上服务器,反而比先前的PHP str_replace效率还差。

3、这时候才想到一个问题,我做的测试是串行执行的,只能算运行总时间。如果要上web上面应用,需要考虑并发问题。也就是需要ab测试。ab -c 500 -n 500测试了一把,果不其然,效率忒低。继续分析,我觉得是高并发情况下,python那个简单封装的TCPServer不够用。线程开销和阻塞式的服务 模式拖低了系统效率。为什么会有这种问题,请问自己“你写的http server能跟apache比不?”这里面的性能优化太高深,搞不明白,怎么办呢?我们需要站在巨人的肩膀上才行。于是想到可以用Twisted库来构建自己的TCP Server。什么是Twisted?也请自行google,并且学习一下。

 

把TCP的服务器用Twisted改写了之后,AB测试了一把,大大的有惊喜:

PHP的str_replace版本

ab -c 500 -n 500 str_version.php
Requests per second:    165.86 [#/sec] (mean)
Time per request:       3014.552 [ms] (mean)
Time per request:       6.029 [ms] (mean, across all concurrent requests)

PHP + python的旧版本的tcp server + AC自动机

ab -c 500 -n 500 old_ac_filter.php
Requests per second:    165.06 [#/sec] (mean)
Time per request:       3029.286 [ms] (mean)
Time per request:       6.059 [ms] (mean, across all concurrent requests)

PHP + python的twisted版本的tcp server + AC自动机

ab -c 500 -n 500 twisted_ac_filter.php
Requests per second:    620.93 [#/sec] (mean)
Time per request:       805.246 [ms] (mean)
Time per request:       1.610 [ms] (mean, across all concurrent requests) 

高并发的情况下,每秒处理的请求数提升了4倍,效果那不是盖的。

晚上十点,又迎来了一个访问量的高峰,情况非常稳定,橘子回报:

“之前这个点都是满负载跑-,-  -v-而且还是关闭了在线统计功能的情况下”

“现在我把在线统计打开了,cpu也就50%左右”

反正是够用了,就优化到此为止吧。

其实这个需求,还有进一步优化的余地,空间换时间+全局的AC自动机,可以把系统性能提高若干数量级。 

大 致思路是:在内容刚刚产生的时候PHP通过UDP消息把需要处理的东西发送给python程序,python实现一个两个线程的生产消费者模式的工作进 程。消费线程每次取出消息槽里面一个需要处理的请求,使用一个全局的AC自动机对内容进行处理,然后存放起来,继续处理下一个请求,当没有请求的时候就阻 塞住。生产线程是一个UDP的server,收到数据后就给消息槽添加一个请求数据,并且给消费线程发送信号激活它工作。如此往复即可。

--EOF--
小知识:
Twisted是一个事件驱动的网络框架,它由Python写成,基于MIT授 权协议。Twisted支持各种各样的底层协议,比如:TCP,UDP,SSL/TLS,多地址传输,Unix socket等,以及HTTP,NNTP,IMAP,SSH,IRC,FTP等其他高级协议。有了这些支持相当于有了一个强有力的基础,你可以用它来开发 诸如web server,Mail server,即时通讯软件 等等。

这里还有一个简单的教程(繁体字)

http://ez2learn.com/index.php/python-tutorials/twisted-tutorials




本站采用创作共享版权协议, 要求署名、非商业和保持一致. 本站欢迎任何非商业应用的转载, 但须注明出自"膘叔", 保留原始链接, 此外还必须标注原文标题和链接.

Tags: twisted, ac自动机, python, yhustc

« 上一篇 | 下一篇 »

只显示10条记录相关文章

jQuery简单开发 (浏览: 14106, 评论: 2)
YY博鼎力之作:ThinkPHP 2008年离线资料包下载 (浏览: 13105, 评论: 0)
让PY在android上飞起来 (浏览: 12983, 评论: 0)
Python 3.0 一个巨大的改变 (浏览: 12835, 评论: 0)
PHP分词索引 (浏览: 12492, 评论: 1)
又拍网架构-又一个用到python的网站 (浏览: 11961, 评论: 0)
心碎:pyscripter。。。 (浏览: 11055, 评论: 2)
初学python (浏览: 9932, 评论: 0)
Python学习资源 (浏览: 9642, 评论: 1)
php2python (浏览: 9027, 评论: 0)

2条记录访客评论

先谢过膘叔。。

Post by liuw on 2012, May 28, 10:41 PM 引用此文发表评论 #1

膘叔,能share这个的源码吗?懒人非常想拿来主义。
----
已经将你的要求和邮箱发给了yhustc。

Post by liuw on 2012, May 28, 10:18 PM 引用此文发表评论 #2


发表评论

评论内容 (必填):