V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
hxndg
V2EX  ›  Python

一面结束,总结爬虫的一些小问题,抛砖引玉

  •  1
     
  •   hxndg · 2016-04-18 15:59:51 +08:00 · 2459 次点击
    这是一个创建于 3142 天前的主题,其中的信息可能已经有所发展或是发生改变。

    上午去面试了腾讯,然后问到了爬虫的问题,结果很多都想不起来了。所以写个帖子总结有关爬虫的种种问题,顺便也方便些其他找实习的同学,第一次笔试没想到会拿到面试,已经很好运了,再攒攒人品。

    A 假设,要写一个爬虫,抓取新浪网的数据,那么需要怎样设计?

    B 新浪网本身肯定是防爬虫的,那么常见防爬虫的方式有哪些?

    C 如果使用 hash 来保证不会出现重复爬取的 url ,如果出现了 hash 碰撞的情况怎么办?

    • 针对问题B,常见网站防止爬虫的基本思路就是爬虫在某些方面比人强,某些方面比人差,因此,如果某些访问请求访问的频率大于某个阈值时,我就可以使用验证码来判断请求发起者是不是人,这一点我用 ss 翻墙的时候经常遇见 google 这么干,当然有的简单验证码是可以通过 python 一个光学识别的包来通过的,北邮教务处登录的验证码就属于这种比较弱的验证码,这种方法最直接的想法是降低请求频率。
    • 还有一部分网站利用爬虫不能解析 js 的功能来动态生成页面,从而防爬虫,这一点主要是抓北邮人论坛,和微拍热门的时候遇到过,破解方法是找到那个 js 访问的网址,然后获得 json 数据就成了,记得 chrome 里是按 F12 浏览 network 即可。
    • 还有一些简单爬虫根本没法解决的问题,比方说页面动态变化,还有就是如果某个“人”访问了除了探测根本看不到的网站,那他就是爬虫,封他没问题,亦或某些很独特的验证码比方说什么“写出来质能方程”,这种真的我不知道怎么针对了。

    针对问题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 条附言  ·  2016-04-18 16:37:27 +08:00
    6 楼针对 hash 给出了一个很赞的解决方案 orz ,虽然我想的不同位置字母加权也算 hash (逗),不过还是布隆过滤器更有效哈,万分感谢。
    第 2 条附言  ·  2016-04-18 19:57:43 +08:00
    不出所料的面试跪了,还是很郁闷。。。。
    我就不信了,不看剑指 offer 和面试宝典就是不成。
    我就不性经典书籍不必这些好?!
    35 条回复    2016-04-19 16:56:56 +08:00
    hxndg
        1
    hxndg  
    OP
       2016-04-18 16:09:03 +08:00
    为什么有的 markdown 不能标记,好奇怪
    loading
        2
    loading  
       2016-04-18 16:13:04 +08:00
    所以,腾讯都是爬虫爬过来的数据。
    hxndg
        3
    hxndg  
    OP
       2016-04-18 16:13:21 +08:00
    我本身考虑过,先让爬虫把链接分析并整理,然后直接段时间切换代理抓取的方式,但和这个类似。所以就没写
    hxndg
        4
    hxndg  
    OP
       2016-04-18 16:13:57 +08:00
    @loading e.....我表示我只是简历上写了爬虫,怪我。。。。。
    mornlight
        5
    mornlight  
       2016-04-18 16:26:58 +08:00
    A B 问题主要靠经验。
    我一直有 C 的疑惑,如果是简单的 url hash ,数据多了之后很容易会碰撞,怎么设计能支撑更多数据的 hash 规则?
    feather12315
        6
    feather12315  
       2016-04-18 16:29:50 +08:00 via Android   ❤️ 1
    最后一个是不是在考布隆过滤器?
    hxndg
        7
    hxndg  
    OP
       2016-04-18 16:30:31 +08:00
    @mornlight 确实,前两个问题经验可以解决,可是上午昏昏欲睡地。。。。。
    对于问题 c 我也想不明白,打算去看看分布式爬虫么?
    Yc1992
        8
    Yc1992  
       2016-04-18 16:30:57 +08:00
    hash 这个问题很有意思,我是直接把头部字段中的所有信息都提取出来用 hash.update 了一下来去重的。
    hxndg
        9
    hxndg  
    OP
       2016-04-18 16:35:43 +08:00
    @feather12315 orz ,确实,布隆过滤器看了下百科发现确实很有效
    qqmishi
        10
    qqmishi  
       2016-04-18 16:39:08 +08:00
    有的网站只要不发送验证码就不验证了 23333333 (比如学校的
    新浪的直接用 cookie 登录就可以绕过验证码了。
    hash 那个可以尝试加个盐?具体的防止方法没怎么考虑过,毕竟个人的小爬虫数据量不是很大。
    murmur
        11
    murmur  
       2016-04-18 16:46:04 +08:00
    @mornlight 碰撞就碰撞呗,那又怎么样,又不是搜索引擎有漏掉必须手动补上的情况,新浪微博产生的数据在日千万级别,还是我上学刚开始的数据,现在早都日亿了,比起 bloomfilter ,你没爬到的数据能有多少能估计到么。。
    murmur
        12
    murmur  
       2016-04-18 16:47:19 +08:00
    B 新浪网本身肯定是防爬虫的,那么常见防爬虫的方式有哪些?
    这个问题,新浪微博是冻结账号,必须手机解封,而且一个手机每天只能解封 5 个账号,这也是我读研的时候爬微博碰到的问题
    验证码什么都弱爆了,真的
    peter999
        13
    peter999  
       2016-04-18 16:48:04 +08:00
    也是 py 交易(ಡωಡ)
    hxndg
        14
    hxndg  
    OP
       2016-04-18 16:50:49 +08:00
    @murmur 额,我倒是不知道每个手机解封的数量有限制。。。。验证码弱爆了,这我很赞同。
    murmur
        15
    murmur  
       2016-04-18 16:54:51 +08:00
    另外补充一下,新浪新闻那个不适合作为考点,这种新闻网站他是希望你去爬的,只要别过分,因为有竞争,所以收录的越多越全越好,如果这个问题放到 3 年前答,爬新闻类网站首选他的 RSS ,可惜现在 RSS 用的越来越少,死链一是多二是更新不及时
    一声叹息
    但是新浪微博不一样,这个东西压根就没想让你爬,他自己有自己的搜索引擎,我们以前做监控的时候,就是用他的站内搜索,新浪微博和新闻不一样,没有固定的信息源,也就是说你不知道一个重要的东西是啥时候冒出来的,所以只能监控重要关键词
    新浪微博还一个很恶心一点就是移动端(官方客户端)的乱序时间线,他会随机打乱时间,把以前很老的数据挖出来当新的,貌似 pc 端还是正常的,这个真的没法理解为什么要这么做
    以前可以爬微博的移动端,还有一部分人选择盗用 weico 什么的 key 来用,比爬页面容易很多,但是现在第三方微博客户端越来越少,能盗用的 key 也不多了,何况现在应该没什么客户端直接把 key 加密在 app 里吧,应该都是服务端中转一次
    mikezhang0515
        16
    mikezhang0515  
       2016-04-18 17:02:52 +08:00
    这是啥岗位啊?
    hxndg
        17
    hxndg  
    OP
       2016-04-18 17:12:56 +08:00
    @mikezhang0515 后端 c++
    sean10
        18
    sean10  
       2016-04-18 17:27:52 +08:00 via iPhone
    前排收藏学长面经
    hxndg
        19
    hxndg  
    OP
       2016-04-18 18:13:53 +08:00
    @sean10 噗,面经的话等过段时间 byr 论坛上写一点好了,毕竟腾讯是我投的第一家。。。。才一个的面经太少了。。。。
    sean10
        20
    sean10  
       2016-04-18 18:32:38 +08:00 via iPad
    @hxndg 好~
    feather12315
        21
    feather12315  
       2016-04-18 21:12:41 +08:00 via Android
    @murmur 我不知道为什么, github 上找到一 Sina 爬虫代码,已经运行了 3 天了,速度没降,没有收到任何跳转提示。(使用固定不变的 cookie , 12h 重新登录一次。没这样做以前会出现跳转。)
    SlipStupig
        22
    SlipStupig  
       2016-04-18 21:42:59 +08:00
    我就不明白现在的人动不动就说 MD5,sha 容易发生碰撞, md5 和 sha 的碰撞率几乎正常情况下有生之年是遇不到,到底有没了解过 MD5 这类算法
    @mornlight
    murmur
        23
    murmur  
       2016-04-18 21:46:47 +08:00
    @SlipStupig 问题 bloomfilter 是 hash 到位点上的。。撞起来不要太容易
    SlipStupig
        24
    SlipStupig  
       2016-04-18 21:54:40 +08:00
    @murmur 我说 md5 你跟我说 bloom
    murmur
        25
    murmur  
       2016-04-18 22:01:42 +08:00
    @SlipStupig 这页我就没看到 md5 和 sha
    firefox12
        26
    firefox12  
       2016-04-18 22:36:51 +08:00
    md5 的问题 不是碰撞 是存储 md5 值的空间太大
    decaywood
        27
    decaywood  
       2016-04-18 22:45:09 +08:00
    分布式爬虫对于重复 url 我觉得可以这样:单独弄一个 url 收集服务器或进程称 A ,当各 slave 准备爬取某网页时都先调用 A 的 API 确认一下是否有重复,如果没有, A 将次 url 建立索引返回成功响应,否则失败。这样就省去了每个爬虫 hash 都存一份,且由于是网络 IO 密集型,对爬取速度影响不大。同时减少了同步负担。至于 url 的索引,直接内存数据库解决就行了,简单粗暴。
    leoguo1314
        28
    leoguo1314  
       2016-04-18 22:52:17 +08:00 via Android
    可以马克吗?我是一个马克
    binux
        29
    binux  
       2016-04-18 23:07:42 +08:00
    布隆过滤器不能解决碰撞,遇到 hash 碰撞,碰撞就碰撞了呗。有得是其他原因会导致你一个页面抓取失败的,不差碰撞这一个。
    sicklife
        30
    sicklife  
       2016-04-18 23:44:56 +08:00
    同意 @binux
    redis 有针对碰撞的解决方案, http://www.lai18.com/content/1400608.html , 所以,比较简单的方法,就是使用 redis ,不要自己造轮子。
    5qwang
        31
    5qwang  
       2016-04-19 07:46:20 +08:00
    @feather12315 有具体 github 的网址吗?谢谢
    feather12315
        32
    feather12315  
       2016-04-19 08:03:22 +08:00 via Android
    est
        33
    est  
       2016-04-19 09:05:53 +08:00
    @binux 然后 B 大你去腾讯面,一样会跪。
    ytmsdy
        34
    ytmsdy  
       2016-04-19 10:23:44 +08:00
    对 HASH 的问题比较有疑惑,碰到这样的问题,直接鸵鸟就好了。按照 HASH 的算法,碰撞的概率也是很小很小的。就算真的碰到了,直接忽略掉就好了。比如说在 1 亿条数据里面,万一碰到个十条八条的碰撞,这样的差错概率也是可以忍受的。
    binux
        35
    binux  
       2016-04-19 16:56:56 +08:00
    @est 腾讯爬虫并不一定比我有经验。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2759 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 81ms · UTC 08:26 · PVG 16:26 · LAX 00:26 · JFK 03:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.