请教一道 Python 多线程爬虫的面试题

[yhf]

从一个 url 出发，打印出所有链接出去的 url ，所有 url 只打印一次。

首先是单线程版本的，用 BFS ，同时用一个 set 记录访问过的 url 就可以了.

start = "http://google.com"
queue = [start]
visited = {start}

while queue:
    url = queue.pop(0)
    print url

    for next_url in extract_urls(url):
        if next_url not in visited:
            queue.append(next_url)
            visited.add(next_url)

然后要求把这个改成多线程，我是这样写的，不知道对不对：

class ThreadUrl(threading.Thread):

    def __init__(self, queue, visited):
        super(ThreadUrl, self).__init__()
        self.queue = queue
        self.visited = visited

    def run(self):
        while True:
            url = self.queue.get()
            print "%s: %s" % (self.name, url)
            for next_url in extract_urls(url):
                if next_url not in self.visited:
                    self.queue.put(next_url)
                    self.visited.add(next_url)
            self.queue.task_done()


queue = Queue()
visited = set()
visited.add("http://google.com")

for i in range(5):
    t = ThreadUrl(queue, visited)
    t.setDaemon(True)
    t.start()

queue.put(start_url)
queue.join()

没有学过操作系统，有些不确定。我的理解是， python 的Queue是 thread safe 的，set不是 thread safe 的。每次从 queue 里获取头部，这个是 thread safe 的，而我的if next_url not in self.visited这条语句写在queue.get()和queue.task_done()之间，所以可以保证操作visited也是 thread safe 的？因此我没有对visited进行 synchronization...

如果我的思路是错的，那么我还需要 synchronization 。这种情况下是应该用 lock 吗？我这种 lock 的方法对吗？

class ThreadUrl(threading.Thread):

    def __init__(self, queue, visited, lock):
        super(ThreadUrl, self).__init__()
        self.queue = queue
        self.visited = visited
        self.lock = lock

    def run(self):
        while True:
            url = self.queue.get()
            print "%s: %s" % (self.name, url)
            for next_url in extract_urls(url):
                self.lock.acquire()
                if next_url not in self.visited:
                    self.queue.put(next_url)
                    self.visited.add(next_url)
                self.lock.release()
            self.queue.task_done()

最后，这题是一道比较开放式的题目，对于多线程的版本，是否有更优的解法，或者有哪些注意点值得跟面试官讨论呢？

[binux]

queue 是线程安全的，不代表 queue.get() 和 queue.task_done()之间是安全的， 它又不是锁。
set 可能是线程安全的，因为它是原生对象 + GIL 。
但是 __contain__ 和 add 操作是需要加锁的。
你这么加锁，逻辑上对了，但是获取释放次数太多了，慢。

多线程设计注重任务的分解，什么地方可以并行，什么地方并行能带来收益。
比如此例， add 操作是不可并行，但是由于 GIL ，只有页面抓取能带来收益，所以 merge 部分不适合放到线程中。

针对这个例子，更好的解法是 io 异步。

[yhf]

@binux 多谢！

为了减少加锁的次数，我在 extract_urls()获得所有 urls 后再一次性判断是否在 set 中，这样一个线程中只加一次锁，这样性能会有较大提升吗？

<script src="https://gist.github.com/yhfyhf/39e4b3ec3d36a3e73f54.js"></script>

后面的我还不是太理解，你提到的只将抓取放在线程中， merge 部分不放到线程中。可是抓取过程中会产生新的 url ，我需要判断这个 url 是否在 set 中，所以判断语句我还是需要放在线程中呀？还请 binux 大大再解释一下，非常感谢！

[binux]

@yhf 如果你能保证 next_urls 没有重复的 url ，这样是对的，如果有，需要先对 next_urls 去重

merge 部分可以推回主线程做啊，下载线程不需要等到 merge 完成就能开始下一个抓取。
但是由于它们时间过于悬殊，在这个例子中其实没什么意义。

[Andiry]

每个线程维护自己的 visited ，最后做一次 merge 不就可以了

[sherlocktheplant]

@Andiry 那么会有重复访问的问题

[DuckJK]

@binux 请问大大， python 里面的异步 io 模块选择哪个顺手？我查了下资料有这么几个 Twisted 、 Tornado 和 gevent 。 python3 里面有 asyncio 模块，我看了这篇文章 http://www.keakon.net/2015/09/07/%E5%88%9D%E6%8E%A2Python3%E7%9A%84%E5%BC%82%E6%AD%A5IO%E7%BC%96%E7%A8%8B

下面有 评论说 libuv 的 Python 接口 pyuv 也非常不错，我现在倾向 Tornado 和 pyuv 。请问下大大的意见，谢谢。

[Damnever]

我只说我看到的问题。。。
锁住的临界资源应该尽可能小，检查 /操作 set 的时候你把 queue 操作也锁了一次

[Damnever]

@Damnever queue 是线程安全的你也说过。。。

[asj]

直接放 set 里不就是你要的结果嘛，还弄个 queue 干啥？

[reorx]

这里如果用多线程写法的话，我觉得应该是造一个 thread pool ，这个 pool 里的线程用于网络请求、解析返回页面里的 URL ，然后把结果扔到一个 Queue 中，主线程只做一件事就是不停地从这个 Queue 里取结果，去重后 print ，然后把新的未爬过的 URL spawn 出新的线程去处理

当然最有效率的办法还是如 @binux 所说，使用异步 io 库，这样可以保证单核效能最大化，且所有网络请求等待的时间都不会浪费（线程池方案就算线程多也不一定可以保证），推荐用 gevent 和 tornado ， twisted 比较重更适合解决 CS 结构双向通讯的网络需求

[yhf]

@Damnever 谢谢！那把 queue.put()操作放在锁外面应该怎么写呢？

[yhf]

@reorx 谢谢！我试试。

[lxy]

如果是我，那么多线程只做一个工作，就是网络请求。好像跟 10 楼差不多。其实就是一个生产者、消费者问题。线程之间的任务要尽量独立、互不影响。

[binux]

@DuckJK Twisted 、 Tornado 和 gevent 都是对事件库的封装， tornado 可以让你用 python3 的风格写异步过程， gevent 可以让你什么都不改就能异步，但是有时候会卡死。其他的没用过。

[reorx]

就楼主的题目写了一些简单的练习代码，对比了几种不同的 Gevent 实现方案。 threading 应该是大同小异的。有兴趣的可以阅读： https://github.com/reorx/learn_spider

有段时间没写网络异步的东西了，而且也一直没写过爬虫应用，感觉必须不时练习一下才能有自我提升
(๑•̀ㅂ•́)و✧

[mikezhang0515]

我觉得没问题啊，你们难道遇到过 Python 下多线程不安全的 bug ？反正我就一直这么写，就用 set ， queue ，还有爬虫耗时在 io ，不要瞎听别人忽悠