知识图谱的很重要的原始数据来源还是来自于网站抓取的数据，网站抓取器就是我们常说的Spider。

在互联网上爬来爬去，发现链接，抓取网页，这就是Spider整天做的事情。听起来很简单，但是实际上是困难重重的。

Spider有两个核心任务：选链调度 和 网页抓取。

Spider面临的主要问题有：

• 压力计算、控制、流量分配：
  • 如何提升对外抓取友好度，减少被封禁。如何评估网站可承受的压力。如何在多用户之间，多种不同的抓取需求之间进行流量分配。
• 抓取流量有限，需要根据预测合理调度，使收益最大化：
  • 链接发现：需要预测优先CHK哪些页面可能发现更多更好的新链接。
  • 待抓分级：需要在抓取之前预测哪些待抓链接对应的网页质量更高，从而优先抓取。
  • 页面更新：需要预测哪些网页更可能发生了变化（或失效），哪些网页的变化更重要，从而优先CHK。
  • 这些预测通常需要基于对现有数据的挖掘统计，由已抓反馈待抓，由历史调度推测未来调度。在这个过程中会用到大规模数据挖掘，机器学习等方法。
• 收录控制：互联网上有大量各种重复、垃圾信息，如果不加限制，我们的系统将很快被垃圾占领。需要判断网页的质量，挖掘网页的重复规律，在尽可能早的地方把垃圾和重复控制住。

1、抓取器(Crawler)

最简单的抓取器就是一个实现了HTTP协议的客户端：接收一系列URL，向网站发起抓取，输出一系列网页。但是在实际中，简单的HTTP抓取不能完全满足抓取需求。除了高性能、高并发外，还有如下需求：

• 多抓取协议支持：目前主要是HTTP和HTTPS。
• 多种资源类型：多文档、图片、视频。
• 页面拼接：对内嵌frame页进行抓取拼接。
• 页面跳转：跳转可以通过HTTP头、HTML meta标签静态实现，也可以通过javascript动态实现。前者容易识别，后者依赖javascript解析，很难精确做到。
• 页面渲染：像浏览器一样执行javascript代码和css渲染，使输出网页看起来像在浏览器里看到的一样。

页面渲染功能的实现方案一把是基于chrome或者firefox内核实现，但有得必有失，这样会导致性能远差于简单的网页抓取器，并非所有网页都有这么复杂的渲染需求，可以让用户自己根据需要来选择。

另外，在这之前，还要能够保证不被网站封禁，比如控制抓取的频率、验证码破解、登录验证等。这些都是令人头疼的难题。

2、新链拓展

有了抓取器，给定一批链接，可以把网页抓回来。但从哪得到源源不断的链接以持续抓取呢？这就是新链拓展做的事情。

互联网拓朴是一个广泛连接的图，从一个小的核心网页集合出发（例如新浪，hao123），沿着链接可以找到互联网上绝大部分网页。新链拓展模块就是负责从网页上提取出新的链接。新提出的链接合并到老链接集合（原始链接称之为种子）中，从而使抓取可以持续，使爬虫的触角逐渐伸向全网，源源不断地得到新出现的网页链接。

通常情况下，链接是通过解析HTML树中的 <a> 标签得到的。但还有一些其它的提链方式：

• 链接可能直接以纯文本的形式出现。需要抽取器从文本中正确地截取链接部分。
• 链接可能由javascript脚本动态生成，甚至需要用户点击操作才能触发生成。这时候需要借助有页面渲染能力的抓取器来解决提链问题了。

另外，对于特定领域的抓取器，比如我们知识图谱，对于某个种子URL，拓展出来的新链是有要求的。例如从网易新闻的频道首页开始抓取，递归抓取（发现/拓展）新闻详情页。这一般通过正则表达式来描述新链拓展的规则。以上面的例子为例：

频道首页的URL格式为：http://news.163.com/domestic/，http://news.163.com/shehui/。所以其对应的正则表达式为：http://news.163.com/[a-z]*/。

新闻详情页的URL格式为：http://news.163.com/15/0630/16/ATCCTD9A00011229.html，http://news.163.com/15/0630/14/ATC89L110001124J.html。所以其对应的正则表达式为：http://news.163.com/[0-9] /[0-9] /[0-9] /. .html。

综上，如果我们想要创建一个全站抓取任务，从频道首页发现新闻详情页，则链接发现规则可以这样配：

入口页面正则：http://news.163.com/[a-z]*/

此入口页面允许的新链正则：http://news.163.com/[0-9] /[0-9] /[0-9] /. .html

那么解析器在分析频道首页时，发现的新链当中，符合新闻详情正则的链接都会被选取，放到种子库当中，供下轮调度使用。

页面解析器（抽取器）也只能针对某些pattern的URL进行页面抽取（通用的页面解析器，如新闻类型的一般准确率不高，很难满足抽取需求）。

3、链接库与网页库

可以持续抓取网页后，我们让这个系统自动跑下去。但是很快我们会发现链接和网页的数量迅速膨胀，简单的文件存储越来越慢，我们需要更高效的存储方式。怎么设计链接库和网页库的存储呢？

链接库的需求：

• schema支持(定长、变长字段都有）
• 批量读需求(选取链接）
• 批量写需求（把新链接合并回链接库）
• 随机读需求（小量）
• 记录长度较小，差异不大(平均几百Byte，最大1KB以内)
• 有大量read-modify-write需求(链接状态的改变需要参考上次的链接状态）

网页库的需求：

• schema支持(定长、变长字段都有）
• 批量读需求（建索引库）
• 批量写需求（spider抓回来的网页入网页库）
• 随机读需求（小量）
• 记录长度较大，差异较大(平均几十KB，最大达到几MB级)

网页库数据量比较大，基本都是离线批量的读写应用（偏向于OLAP），所以业界通用做法是存放在HBase中。而对于链接库，则需要比较大量的随机大写，偏向于OLTP，所以DB（需要sharding）或者NoSQL（如ES）比较合适。

4、选链调度

经过源源不断的 网页抓取=>新链扩展 周期循环之后，链接库里面的种子会非常多，但是抓取器每天能够抓取的链接是有限的，这就产生了一个问题：这么多链接究竟应该选哪些来抓取呢？这就是spider调度策略做的事情。

TIPS商业搜索引擎，spider的链接库里会有几千亿链接，但是每天发起抓取的链接量仅能够有几十亿。

调度策略模型

1、广度有限

spider最原始、最基础的调度策略是广度优先。即：优先调度浅层链接。这里的深度并不是指URL的目录深度，而是链接从首页开始的follow深度(即常见的link_depth字段)。 这是符合一般人对网站的浏览习惯的。一般人从首页开始，通过导航链接，层层找到需要的内容。站长也会把一些重点推荐的内容或新内容放在首页或浅层栏目页上。而需要点击N多次才能发现的页面，一般用户很难找到，价值也不高。

2、链接分级

这个也是比较通用的做法，就是为每个种子分配权重（调度优先级），类似于操作系统的进程调度算法。

为了区分不同链接之间的优先级，spider选取时会对链接进行分级：

• 先根据链接属性计算出权重
• 再根据权重映射到级别
• 选取时从高级别向低级别选取
• 低级别有低保，保证不会被饿死
• 同级别内随机选取

TIPS五种流量划分

我们希望每个站点上的链接可以按某种优先级排序。排好序后链接选取工作就极简单了，只要按顺序从高到低选即可。但我们发现并不是所有链接之间的优先级都是可比的。链接可以分成一些group，group内可比，group间不可比。

根据链接调度的需求，把链接分成五种流量类型：

• 覆盖率CHK
• 覆盖率GET
• 时效性CHK
• 时效性GET
• 更新率CHK

这五种流量类型内部的链接优先级可直接比较，流量类型之间则不可比。流量类型之间的调度通过配比动态计算得到。

3、站点隔离选取

除了对链接根据流量类型进行group，为了体现站点之间的巨大差别，还可以考虑引入站点隔离选取机制。

在站点隔离选取机制下，linkbase按URL字典序(站点部分倒转)排列，相同站点的链接存储在一起。各个站点之间完全独立选取，方便各个站点进行独立的策略控制，避免了相互影响。

调度依赖的属性

链接调度模型定下后，关键是如何更好更快地获取、计算链接相关各种属性，以及尽快地把这些属性生效到线上，影响调度。

待抓链接可以拿到的属性

• URL长相：有很多文章可以做。
  • 各种聚类：聚类后已抓链接的各种属性统计后都可以反馈到待抓
    • domain
    • stat-pattern
    • keyman-pattern
    • domain+anchor聚类
  • 首页/dir_depth，链接长度
  • 从URL上提取时间
• 反链/anchor/fresh-pp/page_rank/微博转发
  • anchor-mine：根据anchor挖掘，对linkbase进行操作，对链接进行提权或降权。
• 前链/link_depth/hub_depth
• sobar访问
• 推送链接的meta信息

已抓链接可以拿到的属性

• 所有待抓链接的属性
• 抓取反馈
  • 抓取状态：成功/失败，返回码
• 单页面级特征
  • 页面价值：质量(有效性、丰富度、整洁度)，受众
  • 页面类型：索引页/内容页，语义分类：新闻/小说/视频/博客...
  • 页面提取信息：正文、标题、链接、页面发布时间、结构化数据
• 多页面特征
  • 页面价值：稀缺(重复度)
  • 贡献新链接能力
• 时间维度特征
  • 抓取历史记录
  • 易变性/易死性
• 建库反馈
  • 建库级别：vip/se/大度/时效性...
• 线上反馈
  • 点击、展现

spider调度的目标就是根据这些属性，安排出最优的调度顺序，使用最少的流量，获取最大的收益。

以前数据挖掘模块往往把最终调权的数据直接生成好，灌入link库。但这里面有很多拍脑袋的阈值和人工决策树。机器学习引入调度排序后，会越来越倾向于数据挖掘只产出基础属性，把基础属性回灌到link库中。基础属性怎么用，由机器学习来决定。

一些重要的调度策略

1、待抓链接调度

• 思路：使用机器学习的方法，根据待抓链接的属性，学习抓取后的页面价值。
• 难点：
  • 已抓反馈待抓，选择合适的粒度
    • 不要太粗：区分度不够
    • 不要太细：样本数太少
    • 高内聚：对于待预测目标属性，聚类产生的粒度要高内聚。即：聚在一起的链接的目标属性应该接近。
    • 低耦合：不同的聚类之间，目标属性应该有区分度。
  • 提升各种属性的反馈速度
    • 反链、anchor、page_rank等需要反转和迭代的比较难做。架构需要考虑如何更好地支持。

2、索引页调度

索引页的价值在于发现新链接。那么它的价值就要按follow出来的后链进行评价，可以用"母凭子贵"来概括。具体如何评价呢？

• 人无我有
  • 别人follow不出来的链接，我能follow出来。
• 人有我精
  • 别人follow出来的链接质量平平，我follow出来的都是优质链接。
• 人精我快
  • 大家都能follow出来的链接，我比别人抢先一步。

索引页分级主要由index-check模块完成。index-check模块根据link-pair产出的链接对信息，对索引页发现链接的能力进行评估，生成链接贡献度和强度谱数据。产出的索引页分级数据使用modlink回标到linkbase生效。

hubdig模块根据链接贡献度和强度谱数据进一步挖掘出hub页(高质量易变索引页)及hub页分级，以时效性CHK方式进行高频调度。

除此之外，通过pattern之间指向关系挖掘，也可以对索引页的分级产生影响。负责这项工作的模块叫link_uniq。 具体做法如下：

对于资源patternB，考察patternA对patternB的指向关系：patternA => patternB。定义四个衡量标准：

• uniq度：指向关系中patternB链接集合uniq后数量 / 指向关系对总量
  • 衡量指向关系的重复程度。如果重复度高，意味着调度patternA的链接follow出patternB的链接大部分都是老链接。
• 覆盖度：指向关系中patternB链接集合uniq后数量 / patternB收录链接总量
  • 衡量通过对patternA中链接的调度，可以发现patternB中多大比例的链接。
• 贡献度：指向关系中patternB链接集合uniq后数量 / 指向关系中patternA链接集合uniq后数量
  • 衡量对patternA中链接的调度能否起到"四两拨千斤“的效果。
• 有效度：指向关系中patternA链接集合uniq后数量 / patternA收录链接总量
  • 衡量此挖掘结果对于patternA是否具有统计意义。如果patternA中仅有少量链接follow出patternB，那反馈到全体patternA链接就是错误的。 link-uniq产出低价值指向数据，作用于effect，对中级别索引页进行降权。提升中级别索引页CHK有效性。

同时link-uniq还产出边框数据，作用于EC。用于辅助索引页识别(索引页识别主要看链接块面积，很重要的一点就是去除边框链接块的影响）。 边框的特点：

• 同功能页面上，边框处于相同位置。边框对应的后链往往重复度很高，即uniq度很低。可以通过这种方式挖掘出每种pattern上的边框块。 但link-uniq挖掘非常耗时，历史上挖掘次数很少，因此产生的效果也不大。如何降低这种大型数据挖掘的成本，使之常态化运行，也是架构方需要考虑的重要问题。

3、更新率调度

有大量存量的内容页，更新哪些呢？主要取决于两点：

• 变化的概率：变好 | 变差 | 变化
  • 网页特性本身的易变性：不同网页易变性不同。商品信息页，BBS页
  • 已CHK反馈待CHK：同类链接大量变化，可能意味着该链接也有变化
• 更新的收益：
  • 是否在索引库，在哪个库中？
  • 是否有点击、展现等
  • 如果不在索引中，或者没有点击展现，那么即使不更新，影响也较小

具体排序策略：

• 更新概率模型
  • 网页自身属性
  • 集合反馈属性
    • 定期pattern聚类挖掘网页变化情况
  • 机器学习：由以上属性计算出网页变化概率
• 更新收益计算
  • 建库反馈网页在什么索引库中
  • 检索端点击、展现反馈
  • 不同收益给予不同权重
• 综合计算CHK收益
  • 用(更新概率 * 更新收益)衡量CHK某链接的优先级

选链调度是整个spider最复杂的模块，有很多深度挖掘、机器学习的东东在里面。