上午去面试了腾讯,然后问到了爬虫的问题,结果很多都想不起来了。所以写个帖子总结有关爬虫的种种问题,顺便也方便些其他找实习的同学,第一次笔试没想到会拿到面试,已经很好运了,再攒攒人品。
A 假设,要写一个爬虫,抓取新浪网的数据,那么需要怎样设计?
B 新浪网本身肯定是防爬虫的,那么常见防爬虫的方式有哪些?
C 如果使用 hash 来保证不会出现重复爬取的 url ,如果出现了 hash 碰撞的情况怎么办?
- 针对问题B,常见网站防止爬虫的基本思路就是爬虫在某些方面比人强,某些方面比人差,因此,如果某些访问请求访问的频率大于某个阈值时,我就可以使用验证码来判断请求发起者是不是人,这一点我用 ss 翻墙的时候经常遇见 google 这么干,当然有的简单验证码是可以通过 python 一个光学识别的包来通过的,北邮教务处登录的验证码就属于这种比较弱的验证码,这种方法最直接的想法是降低请求频率。
针对问题A,首先估测新浪网的数据量,假设每天产生 1000 条新闻,那么单是新闻就是 1000365 条的量,打开新浪可以看到光是分站就是 60 个,整个新浪的 url 量就是 1000365 (天)60 (个分站)15 (年)=4.38*10^8 ,这里我忘了我是什么时候用的新浪,姑且从 2000 年开始计算,认为是 16 年,为方便计算认为是 15 年。新浪的数据只会比它多,而不会比它多,而不会比它少。为此直接的想法时使用多线程爬虫,多个爬虫同时爬取,除了使用多线程还可以使用分布式的大型爬虫,只有这个样子才可能爬完这么多( orz ),然而新浪必然有自己的频率反爬虫机制,因此我们的爬虫还得使用代理(也得限制频率),随着一段时间更换一个代理,降低爬虫被封的危险。 现在又有另外一个问题,我今天爬了一次新浪,存了数据,过了几天接着爬,还要再重新爬取一遍么? http 协议里我记得有个字段是 If-Modified-Since ,同样可以利用这已经缓存过的 url 网址是否改变过,改变了我们再从新爬去,没改变就不用从新爬取了。 会有这种问题,不同平台的爬虫可能会爬取同一个链解,造成资源的浪费,怎么办。这点我想的是某个爬虫必须自己保存已经访问过的 url 网址,同时还得有一个总的索引来保存所有已经访问过 url 网址,这点我直接想到的答案有点类似 dns 轮询了, master 爬虫靠 slave 爬虫爬取不同分站的 url ,当遇到其他分站的 url 时,不去访问,遇到同一个分站的时候先问 master 哪个主机可能存储了这个信息, master 给出另一台 slave 地址,然后我直接去问你访问了没?同时为了节省空间,每个爬虫直接存储 url 的 hash 值,而不是 url 网址。当然这个东西直接引出了问题 C
针对问题C,不同爬虫保存 hash 值,可能会遇见 hash 碰撞的情况,怎样应对这种情况呢?直接想法是在增加存储的信息,考虑的是我如果把 url 和 hash 值存到一起,那我不如直接存 url 呢,所以这个问题我没想到特别好的答案,个人比较觉得中意的想法类似给 url 每个字母在不同位置算加权,构成一个 hash 链,但是也觉得不是很好,这个确实没想到好的答案。期待大神的回复
发现面试还是有点喜欢问你在数据量大的思想下解决问题的能力,所以平时写程序时还是要跳开来看问题,不要被局限。
1
hxndg OP 为什么有的 markdown 不能标记,好奇怪
|
2
loading 2016-04-18 16:13:04 +08:00
所以,腾讯都是爬虫爬过来的数据。
|
3
hxndg OP 我本身考虑过,先让爬虫把链接分析并整理,然后直接段时间切换代理抓取的方式,但和这个类似。所以就没写
|
5
mornlight 2016-04-18 16:26:58 +08:00
A B 问题主要靠经验。
我一直有 C 的疑惑,如果是简单的 url hash ,数据多了之后很容易会碰撞,怎么设计能支撑更多数据的 hash 规则? |
6
feather12315 2016-04-18 16:29:50 +08:00 via Android 1
最后一个是不是在考布隆过滤器?
|
7
hxndg OP @mornlight 确实,前两个问题经验可以解决,可是上午昏昏欲睡地。。。。。
对于问题 c 我也想不明白,打算去看看分布式爬虫么? |
8
Yc1992 2016-04-18 16:30:57 +08:00
hash 这个问题很有意思,我是直接把头部字段中的所有信息都提取出来用 hash.update 了一下来去重的。
|
9
hxndg OP @feather12315 orz ,确实,布隆过滤器看了下百科发现确实很有效
|
10
qqmishi 2016-04-18 16:39:08 +08:00
有的网站只要不发送验证码就不验证了 23333333 (比如学校的
新浪的直接用 cookie 登录就可以绕过验证码了。 hash 那个可以尝试加个盐?具体的防止方法没怎么考虑过,毕竟个人的小爬虫数据量不是很大。 |
11
murmur 2016-04-18 16:46:04 +08:00
@mornlight 碰撞就碰撞呗,那又怎么样,又不是搜索引擎有漏掉必须手动补上的情况,新浪微博产生的数据在日千万级别,还是我上学刚开始的数据,现在早都日亿了,比起 bloomfilter ,你没爬到的数据能有多少能估计到么。。
|
12
murmur 2016-04-18 16:47:19 +08:00
B 新浪网本身肯定是防爬虫的,那么常见防爬虫的方式有哪些?
这个问题,新浪微博是冻结账号,必须手机解封,而且一个手机每天只能解封 5 个账号,这也是我读研的时候爬微博碰到的问题 验证码什么都弱爆了,真的 |
13
peter999 2016-04-18 16:48:04 +08:00
也是 py 交易(ಡωಡ)
|
15
murmur 2016-04-18 16:54:51 +08:00
另外补充一下,新浪新闻那个不适合作为考点,这种新闻网站他是希望你去爬的,只要别过分,因为有竞争,所以收录的越多越全越好,如果这个问题放到 3 年前答,爬新闻类网站首选他的 RSS ,可惜现在 RSS 用的越来越少,死链一是多二是更新不及时
一声叹息 但是新浪微博不一样,这个东西压根就没想让你爬,他自己有自己的搜索引擎,我们以前做监控的时候,就是用他的站内搜索,新浪微博和新闻不一样,没有固定的信息源,也就是说你不知道一个重要的东西是啥时候冒出来的,所以只能监控重要关键词 新浪微博还一个很恶心一点就是移动端(官方客户端)的乱序时间线,他会随机打乱时间,把以前很老的数据挖出来当新的,貌似 pc 端还是正常的,这个真的没法理解为什么要这么做 以前可以爬微博的移动端,还有一部分人选择盗用 weico 什么的 key 来用,比爬页面容易很多,但是现在第三方微博客户端越来越少,能盗用的 key 也不多了,何况现在应该没什么客户端直接把 key 加密在 app 里吧,应该都是服务端中转一次 |
16
mikezhang0515 2016-04-18 17:02:52 +08:00
这是啥岗位啊?
|
17
hxndg OP @mikezhang0515 后端 c++
|
18
sean10 2016-04-18 17:27:52 +08:00 via iPhone
前排收藏学长面经
|
19
hxndg OP @sean10 噗,面经的话等过段时间 byr 论坛上写一点好了,毕竟腾讯是我投的第一家。。。。才一个的面经太少了。。。。
|
21
feather12315 2016-04-18 21:12:41 +08:00 via Android
@murmur 我不知道为什么, github 上找到一 Sina 爬虫代码,已经运行了 3 天了,速度没降,没有收到任何跳转提示。(使用固定不变的 cookie , 12h 重新登录一次。没这样做以前会出现跳转。)
|
22
SlipStupig 2016-04-18 21:42:59 +08:00
我就不明白现在的人动不动就说 MD5,sha 容易发生碰撞, md5 和 sha 的碰撞率几乎正常情况下有生之年是遇不到,到底有没了解过 MD5 这类算法
@mornlight |
23
murmur 2016-04-18 21:46:47 +08:00
@SlipStupig 问题 bloomfilter 是 hash 到位点上的。。撞起来不要太容易
|
24
SlipStupig 2016-04-18 21:54:40 +08:00
@murmur 我说 md5 你跟我说 bloom
|
25
murmur 2016-04-18 22:01:42 +08:00
@SlipStupig 这页我就没看到 md5 和 sha
|
26
firefox12 2016-04-18 22:36:51 +08:00
md5 的问题 不是碰撞 是存储 md5 值的空间太大
|
27
decaywood 2016-04-18 22:45:09 +08:00
分布式爬虫对于重复 url 我觉得可以这样:单独弄一个 url 收集服务器或进程称 A ,当各 slave 准备爬取某网页时都先调用 A 的 API 确认一下是否有重复,如果没有, A 将次 url 建立索引返回成功响应,否则失败。这样就省去了每个爬虫 hash 都存一份,且由于是网络 IO 密集型,对爬取速度影响不大。同时减少了同步负担。至于 url 的索引,直接内存数据库解决就行了,简单粗暴。
|
28
leoguo1314 2016-04-18 22:52:17 +08:00 via Android
可以马克吗?我是一个马克
|
29
binux 2016-04-18 23:07:42 +08:00
布隆过滤器不能解决碰撞,遇到 hash 碰撞,碰撞就碰撞了呗。有得是其他原因会导致你一个页面抓取失败的,不差碰撞这一个。
|
30
sicklife 2016-04-18 23:44:56 +08:00
同意 @binux
redis 有针对碰撞的解决方案, http://www.lai18.com/content/1400608.html , 所以,比较简单的方法,就是使用 redis ,不要自己造轮子。 |
31
5qwang 2016-04-19 07:46:20 +08:00
@feather12315 有具体 github 的网址吗?谢谢
|
32
feather12315 2016-04-19 08:03:22 +08:00 via Android
|
34
ytmsdy 2016-04-19 10:23:44 +08:00
对 HASH 的问题比较有疑惑,碰到这样的问题,直接鸵鸟就好了。按照 HASH 的算法,碰撞的概率也是很小很小的。就算真的碰到了,直接忽略掉就好了。比如说在 1 亿条数据里面,万一碰到个十条八条的碰撞,这样的差错概率也是可以忍受的。
|