epoll机制在搜索引擎spider中的应用

本文将介绍epoll的概念,原理, 优点,及使用接口,同时结合作者在搜索引擎spider开发中epoll使用方式的代码向大家具体介绍epoll的使用方式。
P.S. 笔者08年曾有使用epoll编写未考虑压力控制的crawler,将国内著名票务网站(艺龙)压垮并在boss的带领下登门道歉的经历:) 足见epoll的强悍!
epoll是什么
按照man帮助中的说明,epoll是为了高性能处理处理文件句柄而改进的poll机制, 和其类似的功能是select调用。epoll提供相对简单的接口, 即能实现高效的数量巨大的文件句柄的操作和控制。 是select和poll的升级替代品。
select也可以管理调度数量众多的文件句柄,但一般select能够管理的文件句柄数为2048(受FD_SETSIZE定义大小的限制), 虽然可以通过修改linux内核代码调整,但因为其实现为轮询机制,所以在当文件句柄较多,而有事件的句柄较少的情况下select的性能会较低(当然,我个人觉得最大的问题,还是文件句柄数的限制), 当然,很多早期的搜索引擎spider,很多都是直接使用select,调度网络句柄,性能也还不错,比如larbin
而在操作系统实现中,epoll是通过callback回调函数来操作active的文件句柄,所以该调用不用像select或是poll一样需要线性扫描,所以epoll效率较高(当然,如果操作的文件句柄都是活跃的,那select/poll的性能类似),而且epoll能够管理的文件句柄数非常多,一般是系统能够管理的文件句柄的上限,况且epoll通过epoll_create,epoll_ctl,epoll_wait即能完成文件句柄的管理, 所以很多时候epoll系列的接口会成为管理大量文件句柄的机制的首选。
epoll的优点
其实上文已经提到了很多,综合起来,主要是以下两方面有点:
  1. 高效: 在大量文件句柄管理中,如果active的文件句柄较少,则效率较select/poll高
  2. 量大: 理论上能够管理操作系统最大文件句柄数的句柄
当然,在实际中,在一些benchmark中,如果绝大部分文件句柄/socket都active,则epoll的效率相较select/poll并没有什么优势,相反, 如果过多使用epoll_ctl,效率相比还有稍微的下降。但是一旦使用idle connections模拟WAN环境,epoll的效率就远在select/poll之上
另外,能够管理的文件句柄数也不可能达到最大句柄上限,在1GB内存的机器上大约是10万左右,具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。
epoll的使用
首先要介绍epoll相关的数据结构。
epoll用到的有函数都是在头文件sys/epoll.h中声明:
typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ };
结构体epoll_event 被用于注册所感兴趣的事件和回传所发生待处理的事件,其中epoll_data 联合体用来保存触发事件的某个文件描述符相关的数据,例如一个client连接到服务器,服务器通过调用accept函数可以得到于这个client对应的socket文件描述符,可以把这文件描述符赋给epoll_data的fd字段以便后面的读写操作在这个文件描述符上进行。epoll_event 结构体的events字段是表示感兴趣的事件和被触发的事件可能的取值为:
EPOLLIN :表示对应的文件描述符可以读; EPOLLOUT:表示对应的文件描述符可以写; EPOLLPRI:表示对应的文件描述符有紧急的数据可读; EPOLLERR:表示对应的文件描述符发生错误; EPOLLHUP:表示对应的文件描述符被挂断; EPOLLET:表示对应的文件描述符有事件发生;
函数接口如下:
函数声明:int epoll_create(int size)
该函数生成一个epoll专用的文件描述符,其中的参数是指定生成描述符的最大范围 2、epoll_ctl函数
函数声明:int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
该函数用于控制某个文件描述符上的事件,可以注册事件,修改事件,删除事件。
参数: epfd:由 epoll_create 生成的epoll专用的文件描述符;
op:要进行的操作例如注册事件,可能的取值:
                EPOLL_CTL_ADD 注册、EPOLL_CTL_MOD 修改、EPOLL_CTL_DEL 删除
fd:关联的文件描述符;
event:指向epoll_event的指针;
如果调用成功返回0,不成功返回-1
函数声明:epoll_wait
epoll的工作模式
epoll有两种工作模式,ET模式与LT模式。
LT是缺省的工作方式,并且同时支持block和no-block socket;在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表。 ET是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知。 ET(Edge Triggered)与LT(Level Triggered)的主要区别可以从下面的例子看出:
例子:1. 标示管道读者的文件句柄注册到epoll中;2. 管道写者向管道中写入2KB的数据;3. 调用epoll_wait可以获得管道读者为已就绪的文件句柄;4. 管道读者读取1KB的数据5. 一次epoll_wait调用完成
如果是ET模式,管道中剩余的1KB被挂起,再次调用epoll_wait,得不到管道读者的文件句柄,除非有新的数据写入管道。如果是LT模式,只要管道中有数据可读,每次调用epoll_wait都会触发。 另一点区别就是设为ET模式的文件句柄必须是非阻塞的。
搜索引擎spider中的使用示例
功能描述
此处的spider,是一个具体而微的应用,或者更应该定义为crawler,即定向快速抓取指定网站,例如我们已经获取到1KW个URL,需要再1天内江1KW的URL对应的网站,使用单机抓取下来。
更具体地,笔者当时的应用场景,是快速地检查指定URL list对应的网站是否能连通, 所以具体操作的时候,仅抓取网页的头部信息, 并返回其中的return status即可, 因为一开始没有spider设计的经验, 所以该crawler一开始没有考虑同一网站的压力控制, 而epoll过去强悍,导致QA线下测试该crawler时,就将国内著名票务网站压垮(据票务网站的同事说, 他们的服务器CPU过热自动重启,而刚完成重启,就。。。又挂了: ),也算是工作后的一个奇遇了。  当然, 这样的CASE在如今,能够很容易被检查出来是一场攻击而被直接封IP。
架构
因为是一个简化的spider,所以架构图和下图类似(精确的架构图涉及泄密不再贴出来):
性能考虑
假设20个线程,每个线程最多管理50个socket, 假设抓取超时时间为10秒(一般会比这个时间长),假设不考虑压力控制,则该crawler每天能够抓取 20 * 50 * 86400 / 10 = 8640,000个网页,单机。如需要更强悍的抓取能力, 考虑使用多机。
代码示例
因为代码较多,此处仅贴出涉及到epoll工作原理的代码部分。
 图: epoll_create,创建epoll的fd,其中_max_sock_num指定最大管理的socket数量
图: 将socket加入epoll机制: 创建非阻塞fd,并将非阻塞fd加入epoll管理(初始的fd不响应读消息)
图: 使用epoll_ctl设置fd的状态,请参见上图设置读消息机制理解
图: epoll_wait调用方式: 如果active的socket数量不为0,则分出错,断开,读,写状态进行对应处理。
更多实现参见该文附件代码: contm_connector.cpp, 该代码在实际项目中应用,因用到了自行开发的日志库等外部lib,故不能直接编译,但逻辑经过测试,所以参考性较强。
具体代码参见: http://pan.baidu.com/share/link?shareid=2373459832&uk=1493671608
更多内容参见:
epoll 使用说明: http://www.xmailserver.org/linux-patches/nio-improve.html
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

特定场景的Cralwer

有时也叫Crawler。
今天整理电脑文档的时候发现很早09年初自己写的一个crawler的设计文档, 打开这个50多页的文档,里边N多的逻辑图及规范定义的数据结构, 才觉得真的好久没有见过写得那么规范的文档了(也许有点自夸, 或者码农都觉得自己的就是规范: )
将其中的总体设计图分享给大家参考,确切的说,并不是一个完整的crawler,而是一个连通性检查模块,所以当中更增加了很多定制化的逻辑。
该设计中严格地区分了数据流及过程,也算是设计图中的一种创新了。
设计时参考了Ming the Web: Discovering Knowledge from Hypertext Data》中的Crawler, 其中完整架构如下:
此处也向大家推荐这本书《Ming the Web: Discovering Knowledge from Hypertext Data》,里边对于从spider 索引建立,ranking,检索过程等搜索引擎相关的技术都有深入浅出的介绍, 特别适合从事互联网,特别是搜索的同学。
参考文档:
Ming the Web: Discovering Knowledge from Hypertext Data
也可关注微博: weibo.com/dustinsea
或者直接访问http://semocean.com

分类模型在关键词推荐系统中的应用

以下内容均基于百度关键词推荐系统进行讨论
本文内容主要集中在使用机器学习方法判断两个短文本的相关性为基础构建商业关键词推荐系统。 为方便读者理解, 会先介绍该技术的具体应用背景及场景。
广告主在百度或google上进行广告投放时, 需要选择关键词, 以向搜索引擎表述自己想要覆盖的有商业价值的网民搜索流量。 在选择关键词后, 还需要设定具体的关键词匹配模式, 以告诉搜索引擎选择的关键词以何种方式去匹配网民的搜索。 举个例子: 网民在百度上搜索 ‘鲜花快送’, 假设商家A是卖花的, 搞鲜花速递业务的, 则A可以在百度凤巢系统中选择‘鲜花快送’这个关键词,同时设定匹配模式为精确匹配(即网民搜索和A在凤巢系统中选择的关键词完全一致时才出A的广告, 更多细节参见:http://yingxiao.baidu.com/), 假设B在凤巢中未选择‘鲜花快递’, 但选择了‘鲜花速递’, 假设B选择了广泛匹配(语义近似即匹配,具体参见http://yingxiao.baidu.com/), 则B的广告也会被触发(具体是否会展现, 还和出价, 质量度等诸多因素有关)
此时会面临一个问题: 广告主在凤巢系统中选择关键词时, 仅凭自己去想, 很难完全想到所有符合自己需求的关键词(网民的搜索query千奇百怪), 故需要提供工具, 帮助凤巢客户快速找到和自己推广意图一致或相近的关键词,即: 关键词推荐工具。
从交互上来看,可以将关键词工具看成一个搜索引擎,凤巢客户输入一个种子词(种子query),返回一个和种子query意图相近的推荐词list。
当然作为推荐系统, 其中还会包括属性披露, 推荐理由, 关键词行业分类, 关键词自动分组等支持, 这些内容会在接下来的其他博文进行介绍。
整个推荐流程大致如下
整个推荐流程, 大致分为5步:
  1. 基础日志,数据清洗即预处理
  2. 候选词触发: 根据输入种子query触发得到系统性能支持的最大关键词候选(供后续流程进行筛选过滤及排序),当然为保证性能, 该过程中会保留触发关键词的各种基础属性,例如PV, 行业, 主题等; 一般业界的检索,推荐系统会有较多触发逻辑逻辑,故触发出的关键词会比较多
  3. 相关性过滤:因为触发出的推荐关键词较多,故需要判断推荐关键词与种子query的相关性;既要保证召回,又需要保证准确性。
  4. ranking
  5. 使用业务,商业规则对最终结果进行排序调整及过滤(最经典的, 黄赌毒必须过滤删除)
对于相关性过滤,很早以前我们也是使用规则进行过滤,但随着规则数量的急剧增加,一方面导致系统架构性能下降,另外一方面也使系统策略越难约维护,故最终决定使用机器学习方法进行相关性过滤。
涉及到机器学习方法解决问题, 就会涉及到3方面的问题: 用哪些数据,准备哪些数据,如何处理数据? 使用哪些特征? 选用何种model ?
数据
一般来说,如果数据选择有问题, 那基本可以说后边无论再做多少努力, 这些努力都会付诸东流, 公司里这样的机器学习相关的项目也不少见: 几个人全情投入几个月或是1年多,效果总提不上去,回过头来发现数据就有问题,哭都没有眼泪。
所以一开始我们选择数据就比较慎重,还好关键词推荐工具隐性和显性反馈数据都还算比较丰富(推荐系统中都需要有这些信息, 将整个数据流形成完整的迭代闭环): 我们可以认为用户输入一个query并选择了这个query返回的某个候选推荐词的pair,就是一个正例(即模型是判断是否相关,相关为正例,不相关为),而输入一个query后,用户将返回的某个词放入垃圾箱(关键词工具交互上支持该操作),则query及被放入垃圾箱的关键词组成的pair,即为负例。
获得数据后, 很快就发现一个问题: 客户操作得到的正例, 就是毫无疑问的正例;但用户的负反馈(用户使用种子query搜索得到返回结果后,被扔入垃圾箱的的case)很多时候并不一定和query不相关, 甚至是很相关,只是因为用户个性化的原因导致客户认为这个case 不适合自己。
比如: 一个客户主要卖各种花茶, 像菊花茶, 桂花茶等,但他不卖茉莉花茶,此时如果用户输入花茶, 从相关性来说, 推荐‘菊花茶’,‘茉莉花茶’, ‘桂花茶’其实都是OK的,但用户将‘茉莉花茶’放入垃圾箱,因为他不卖该产品。其实并不能说明花茶和茉莉花茶不相关。
为了消除因个性化带来的负例不准的情况,我们人工标注了1.5W非个性化的负例。 并进行随机sampling, 使正负例数量基本相当。
最终使用1/10数据作为测试样本,9/10作为训练样本。
特征
数据准备就绪后,下一步就是如何选择合适的特征了。 因为整个关键词推荐系统所能触发的关键词各式各样, 各种类型千奇百怪, 所以如果直接使用各种地位特征(例如字面,或是ID类)的话,会导致特征空间较大而数据比较稀疏,导致完成分类基本上变成不可能完成的任务; 所以我们不能直接使用字面, ID作为特征进行分类,而是要使用更加泛化,高维的特征。
在特征选择过程中,我们也充分贯彻了站在巨人的肩膀上远眺的方式,充分利用手头的资源,例如短串核心判断,同意变化扩展等基础工具进行特征设计。更详细的特征此处不便于列出,仅列出两个有代表性的特征供大家参考。
  1. 推荐词与种子query经过切词后的相同term的长度之和与种子query经过切词后的term的长度之和的比值;类型为double类型。
  2. 推荐词基本切词后切词顺序包含 query, 特征值为1,默认值为0;类型为double类型。
  3. 推荐词,种子query的topic向量相似度。
  4. 。。。。更多高维特征。。。。。
利用多个类似的高维特征,就能很好地覆盖推荐词与种子query; 当然特征的设计会直接影响关键词推荐中相关性的定义,例如如果字面(重合)相关特征较多, 则推荐主要表现为字面相关,如特征主要为语义特征, 则推荐结果反映为语义相关。如果特征中有用户的历史行为信息特征(例如用户已经选择的关键词),则可以认为相关性模型就已经实现了个性化处理。
 模型
很多项目因为周期比较赶, 所以小步快跑的起步阶段并没有太多时间去做模型和参数的双向搜索,所以综合效率和时间的代价,选择了部分模型及在经验参数下的效果,进行模型的初选。
最终综合考虑性能,准确性和召回诸多因素下,选择了adaboost,在adaboost ratio 和 弱分类器数量上进行了参数实验。 准确性/召回 效果如下:
具体adaboost算法参见: adaboost介绍
WLRatio 300 500 1000 1500
0 0.87/0.89 0.87/0.91 0.87/0.9 0.86/0.91
-0.1 0.81/0.95 0.79/0.96 0.8/0.96 0.8/0.97
-0.2 0.74/0.98 0.73/0.98 0.73/0.98 0.73/0.98
-0.3 0.66/0.99 0.64/1 0.65/1 0.64/1
评估
以上内容均属于线下模型优化部分,所有的指标均可以线下获得, 但最终需要用线上的效果说话, 最后说服力的, 还是线上A/B Test, 因为是后台策略的升级, 故这样的实验在成熟的A/B test框架下比较容易做; 线上实验的最终效果也比较符合预期, 保证准确性的情况下召回大为提升(此处就不贴具体数值)
后文:后来将adaboost直接替换为Random Forest,在未改变模型的基础上效果立刻提升非常多,可见模型选择也较为重要。
参考文献:
百度凤巢关键词工具: www2.baidu.com
Data.Mining.Concepts.and.Techniques.2nd.Ed
也可关注微博: weibo.com
或是直接访问: http://semocean.com

Google experiment infrastructure 阅读心得

背景

Google 的文化就是数据驱动:不停实验,不断得到实验结果进行分析并进行改进,这样就会导致所有R&D(Researcher&Developer)都会有不断实验的冲动和需求。这就对实验框架提出了文中重点描述的三个需求:
1.        More: 更多能够同时进行的实验
2.        Better:不合法的实验不能在框架中实验, 而合法的实验, 但如果效果不佳, 则应该能够被及时发现并下线
3.        Faster:实验应该能快速建立并启动
和google search engine面临的问题一样,推荐系统也存在大量实验,故文中的思想可以在后续关键词推荐的设计中借鉴。
原有相关工作
一般来说,进行实验的目的有以下两个:
1.        测试新的features
2.        在已有features上,测试各种参数的最优值及组合
而原有框架却有较多限制。例如google在2007年以前使用single Layer模式,该方式实现较为简单, 却有很多限制, 包括:
1.        每个请求最多只能做一个实验,可能导致很多实验流量不足
2.        添加条件进行分流时会使框架变得复杂
3.        上游模块做了较多流量划分后,下游模块可能出现stravation的状况
另一种方式:Mutil-factorialdesign,让每个参数都相对独立地做实验,最多能同时做N个实验,其中N为参数个数。缺点是不容易调整,且很多参数是不独立的,文中给的例子是UI显示文字,背景的颜色不能相同。

Overlapping Experiment Infrastucture

主要思想:
1.        将待实验参数划分为独立的N组subsets。例如,不同的binary功能不一样,则可以认为他们的parameters不相交,可划分到不同的subsets中
2.        定义domain, layer,experiment后,对流量进行划分及条件判断,其中:
l  Domain: 流量的划分,domain之间流量是不能有交集的
l  Layer:每组相关的subset参数组成一个实验layer
l  Experiment:具体实验,在一个subset中,测试0个及多个测试参数
3.        Domain, layer, experiment可以嵌套
如下图所示:
其中(a)为single layer,(b)为带有非覆盖domain的简单示例,(c)中包含两个launchlayer(d)中则存在更多嵌套
具体的参数设置, 既可以通过代码修改来实现, 也可以通过更新数据来制定(对应文中的binarypush 和data push,一般情况下data push 能够更快地进行更新)。
对于domain流量的划分,在searchengine 中一般是通过cookie来划分(不能通过request等非机器/用户属性进行划分,否则用户看到的效果可能出现跳动),而在Overlapping Experiment Infrastucture中,流量划分有以下原则:
1.        Domain 流量不能有交集,一旦流量划分到某个domain,则流量不能再其他平级的domain中被使用,所以一般domain的划分可以使用。一般使用cookie,或是cookie-day,userid取模来进行划分。
2.        Layer可以考虑使用不同的功能模块binary来进行划分参数。在各layers中,分流可使用mod =f(cookie, layer)进行流量划分
3.        在具体实验中,需要考虑condition(具体实验条件是否成立)
具体实验逻辑参见下图:
同时文中提到会使用配套数据校验工具校验数据格式正确性(其实这个是上线的必须具有的工具,并无新意),另外线上会时时关注重要指标,例如CTR,如果CTR等重要KPI超过异常边界,则新实验直接下线。这样的检测固然能保证避免异常,但是否会限制实验的上线速度需要思考,毕竟线上多个实验同时进行的话, CTR类似的KPI发生异常时,不能很快确认是哪个实验导致。
和传统方式一样, 实验框架提供的是实验流量的定位,但具体实验中,某次请求究竟是走了实验组逻辑,还是走了控制组逻辑,则仍需要从日志中分析。
其他
文中提到的以下内容也非常值得借鉴:
1.        文中提到了canary code的概念,表明google会在线上开实验,小流量测试代码正确性。也是正式,让google公司中RD/QA的比例很高(中国主要的search engine公司中,代码正确性更多是在线下验证,这就要求更多测试工程师)
2.        所有和实验框架的代码均被抽离成shared library的形式编译到各binary中,这样就让实验代码实现高度统一。但这里有一个问题:很多复杂系统中数据流是通过很多层binary后,才能得到最后的结果,如何控制各层之间的数据流向,设计时需要重点考虑。
需思考的问题
1.        涉及到多层次模块的架构中,如何控制各实验在各层之间的数据传输(如使用binary push的方式,则同一层的binary可能不一样,除非统一binary,而由data push控制)
2.        如何记录实验结果:文中使用logging的方式仍然会导致线下需要较多的logging事后分析的工作
也可关注我的微博:  weibo.com/dustinsea
或直接访问 semocean.com