网页爬虫及其用到的算法和数据结构
import requests #用来爬取网页
from bs4 import BeautifulSoup #用来解析网页
seds = ["http://www.hao123.com", #我们的种子
"http://www.csdn.net",
"http://www.cricode.com"]
sum = 0 #我们设定终止条件为：爬取到100000个页面时，就不玩了
while sum < 10000 :
if sum < len(seds):
r = requests.get(seds[sum])
sum = sum + 1
do_save_action(r)
soup = BeautifulSoup(r.content)
urls = soup.find_all("href",.....) //解析网页
for url in urls:
seds.append(url)
else:
break
1）我们的任务是爬取1万个网页，按上面这个程序，一个人在默默的爬取，假设爬起一个网页3秒钟，那么，爬一万个网页需要3万秒钟。MGD，我们应当考虑开启多个线程(池)去一起爬取，或者用分布式架构去并发的爬取网页。
2）种子URL和后续解析到的URL都放在一个列表里，我们应该设计一个更合理的数据结构来存放这些待爬取的URL才是，比如队列或者优先队列。
3）对各个网站的url，我们一视同仁，事实上，我们应当区别对待。大站好站优先原则应当予以考虑。
4）每次发起请求，我们都是根据url发起请求，而这个过程中会牵涉到DNS解析，将url转换成ip地址。一个网站通常由成千上万的URL，因此，我们可以考虑将这些网站域名的IP地址进行缓存，避免每次都发起DNS请求，费时费力。
5）解析到网页中的urls后，我们没有做任何去重处理，全部放入待爬取的列表中。事实上，可能有很多链接是重复的，我们做了很多重复劳动。
1）并行爬起问题
我们可以有多重方法去实现并行。
多线程或者线程池方式，一个爬虫程序内部开启多个线程。同一台机器开启多个爬虫程序，如此，我们就有N多爬取线程在同时工作。能大大减少时间。
此外，当我们要爬取的任务特别多时，一台机器、一个网点肯定是不够的，我们必须考虑分布式爬虫。常见的分布式架构有：主从（Master——Slave）架构、点对点（Peer to Peer）架构，混合架构等。
说道分布式架构，那我们需要考虑的问题就有很多，我们需要分派任务，各个爬虫之间需要通信合作，共同完成任务，不要重复爬取相同的网页。分派任务我们要做到公平公正，就需要考虑如何进行负载均衡。负载均衡，我们第一个想到的就是Hash，比如根据网站域名进行hash。
负载均衡分派完任务之后，千万不要以为万事大吉了，万一哪台机器挂了呢？原先指派给挂掉的哪台机器的任务指派给谁？又或者哪天要增加几台机器，任务有该如何进行重新分配呢？
一个比较好的解决方案是用一致性Hash算法。
2）待爬取网页队列
如何对待待抓取队列，跟操作系统如何调度进程是类似的场景。
不同网站，重要程度不同，因此，可以设计一个优先级队列来存放待爬起的网页链接。如此一来，每次抓取时，我们都优先爬取重要的网页。
当然，你也可以效仿操作系统的进程调度策略之多级反馈队列调度算法。
3）DNS缓存
为了避免每次都发起DNS查询，我们可以将DNS进行缓存。DNS缓存当然是设计一个hash表来存储已有的域名及其IP。
4）网页去重
说到网页去重，第一个想到的是垃圾邮件过滤。垃圾邮件过滤一个经典的解决方案是Bloom Filter（布隆过滤器）。布隆过滤器原理简单来说就是：建立一个大的位数组，然后用多个Hash函数对同一个url进行hash得到多个数字，然后将位数组中这些数字对应的位置为1。下次再来一个url时，同样是用多个Hash函数进行hash，得到多个数字，我们只需要判断位数组中这些数字对应的为是全为1，如果全为1，那么说明这个url已经出现过。如此，便完成了url去重的问题。当然，这种方法会有误差，只要误差在我们的容忍范围之类，比如1万个网页，我只爬取到了9999个，剩下那一个网页，who cares！
5）数据存储的问题
数据存储同样是个很有技术含量的问题。用关系数据库存取还是用NoSQL，抑或是自己设计特定的文件格式进行存储，都大有文章可做。
6）进程间通信
分布式爬虫，就必然离不开进程间的通信。我们可以以规定的数据格式进行数据交互，完成进程间通信。
