今天打算写点小东西来练练手，看了知乎一些老司机的建议，决定从爬虫开始练起。

网络爬虫的介绍

之前刚注册好博客，访客数量巨多，我有点兴奋，唉我是不是太火了咋啥都没写就这么多访客？某人一脸淡然回答：搜索引擎的爬虫啦。什么是爬虫？你写的程序就像一只轻盈的蜘蛛，在internet这个巨大的网上飞快的爬行，获取你需要的信息。这些被广泛用于互联网搜索引擎。

“它们可以自动采集所有其能够访问到的页面内容，以供搜索引擎做进一步处理（分检整理下载的页面），而使得用户能更快的检索到他们需要的信息。”——wiki

种子的介绍

首先先介绍下种子，可能和主题关系不太紧密，不过宝宝可是连种子的定义都不知道的人啊！【捂脸】

• BitTorrent is a communications protocol of peer-to-peer file sharing which is used to distribute data over the Internet.——wiki
• 种子就是个文本文件，种子文件内容=Tracker信息+文件信息。
  • Tracker信息：用种子下载的时候先解析这个信息得到Tracker地址，然后连接Traker服务器，提供其他下载的人的IP,然后你就找他们要文件的信息。
  • 文件信息：种子下载最大的好处就是把文件虚拟分成大小相等的block，不过块大小必须是2k的整数次方，然后把每个块的检索信息和Hash验证码写入种子文件中。
• 所以你就知道，种子下载就是找好多下载过这个资源的人一小块一小块的要，用P2P协议传输，最后用好快的速度下到想要的资源~（正在用种子蹭学校网下电影）
• 现在还有用DHT网络技术实现种子下载，可以不用Tracker直接下载，这样连Tracker服务器都不要了嘛，用户可以更快的通过哈希表寻址储存，找到前人开始下载 
• 

网络爬虫的工作原理

终于进入正题了！网络爬虫的工作流程大致如下：

1. 选取一部分精心挑选的种子的URL
2. 把这些种子URL放在待处理的队列中，作为将来要爬取得入口
3. 从待处理的URL队列中取出URLs,解析DNS，得到主机IP，然后将网页下载，放在已下载的网页库中，同时，将这些URL放在已抓取的URL队列。
4. 从已抓取的URL队列中，分析存在URL，从而探索更多的URL，将它们放在待处理队列中，这里就进入了步骤2的循环。

从爬虫角度对互联网进行划分

1. 已下载未过期网页
2. 已下载已过期网页，这些网页有了更新
3. 可知网页，还有抓取下来，也没有在我们的待处理URL队列中，但是可以通过已抓取页面或者待分析URL获取到的URL，认为是可知网页
4. 待下载网页，在待处理URL中的那些网页
5. 不可知网页，爬虫无法直接抓取下载的网页

搜索策略

不明白的朋友去看数据结构：）

1. 广度优先搜索，一层一层搜索（用队列和树实现）
2. 深度优先搜索，一条路走到黑，再回头换条路再走到黑（现实生活中用得少）
3. 最佳搜索，是一种改进型，使用设计好的网页分析算法，预测待抓取URL与目标网页内容的相关度，从中选择较优的进行搜索。缺点是会自动舍弃它认为“不合适”的URL，它的判断可能会出错噢。这是一种局部最优算法。
   • Partial PageRank策略：有一个Rank值，对已下载和URL队列中的URL形成网页集合，计算PageRank，按照大小进行排序，并按照顺序抓取
   • OPIC策略策略：“该算法实际上也是对页面进行一个重要性打分。在算法开始前，给所有页面一个相同的初始现金（cash）。当下载了某个页面P之后，将P的现金分摊给所有从P中分析出的链接，并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。”
   • 大站优先策略：对待分析URL中网站进行分类，对待下载页面多的网站进行优先下载

更新策略

1. 历史参考策略，根据页面以往的更新数据，判断未来何时会发生变化（泊松过程进行建模）
2. 用户体验策略，我们通常只会看谷歌出来的前几页的资料啦，一样的道理，优先更新查询结果前几页的的网页，“用户体验策略保留网页的多个历史版本，并且根据过去每次内容变化对搜索质量的影响，得出一个平均值，用这个值作为决定何时重新抓取的依据。”
3. 聚类抽样策略，将目标网页分成一个个cluster，对每个cluster进行抽样，确定更新周期，作为整个类别的更新周期。（在Reference3的博客中有详细的图片说明哦）

分布式抓取系统结构

对于这一部分我是蛮感兴趣的。依旧是wawlian博客中的图说的非常清楚，我在这里也引用一下： 

每个数据中心有多台服务器，你写的程序让不同的服务器协同工作，抓取需要的页面，那么他们怎么能一起好好工作呢？现在主要有三种方法：

1. 主从式，一个主人，一群奴隶。奴隶们负责抓取网页，主人负责待处理URL队列，分发工作，以及统治好奴隶们。主从式最大的瓶颈就是这个主人，要是他很蠢或者生病了，全部玩完。
2. 对等式，是个平等的社会，大家地位都一样，都是屁儿（peer）,每个URL有对应的hash值，假设有n个服务器，每个都有自己的编号，那么通过hash值mod3就可以得出是谁来处理各自URL。对等式的缺陷就是，要是一个服务器坏了，那么n就会减一，所有hashmod的结果都会变噢，是不是又得重来？拓展性不好。
3. 哈希法，对等式的改进，“一致性哈希将URL的主域名进行哈希运算，映射为一个范围在0-232之间的某个数。而将这个范围平均的分配给m台服务器，根据URL主域名哈希运算的值所处的范围判断是哪台服务器来进行抓取。如果某一台服务器出现问题，那么本该由该服务器负责的网页则按照顺时针顺延，由下一台服务器进行抓取。这样的话，及时某台服务器出现问题，也不会影响其他的工作。”

Reference:

1. https://en.wikipedia.org/wiki/BitTorrent
2. http://www.laitaolun.com/243.html
3. http://www.cnblogs.com/wawlian/archive/2012/06/18/2553061.html