问一道大数据量面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道大数据量面试题

问一道大数据量面试题# JobHunting - 待字闺中

h*22013-04-02 07:04

1 楼

有两台机器，每台10T数据，数据中都是url，每行一个url，他们只有万分之一的
diff，要查找有这两台机器的url的差集，需要一个准确的结果（不能用boolfilter)。
类似的一题是：也是两台各10T数据，一开始两边数据相同，后来可能两边有更改，如
果能够提供一个接口，快速的比较两边数据是否有diff，如果有，diff的是哪些url。

s*12013-04-02 07:04

2 楼

我的思路是先对两台机器各自进行 external sort
然后用两个pointer, 指向各自的起始位置，一行一行比

c*r2013-04-02 07:04

3 楼

感觉不需要排序就能做了，类似找重复数字的原理，只不过10T数据显然不能放进一个
大数组里。分成若干个文件，读到了一个url就去文件堆里找，有的话就消掉，没的话
就加上，最后文件堆里剩下的就是2个机器的差异.

s*12013-04-02 07:04

4 楼

恩，你说的有道理，可以根据hash值分成若干个文件比对。

p*22013-04-02 07:04

5 楼

mapreduce行吗？

b*a2013-04-02 07:04

6 楼

嗯就是这样做的

【在 c********r 的大作中提到】

: 感觉不需要排序就能做了，类似找重复数字的原理，只不过10T数据显然不能放进一个
: 大数组里。分成若干个文件，读到了一个url就去文件堆里找，有的话就消掉，没的话
: 就加上，最后文件堆里剩下的就是2个机器的差异.

b*a2013-04-02 07:04

7 楼

可以的。其实原理和hash到小文件一样吧。

【在 p*****2 的大作中提到】

: mapreduce行吗？

d*x2013-04-02 07:04

8 楼

map to hash，label with data set name at the end, then merge compare when
reduce.

boolfilter)。

【在 h******2 的大作中提到】

: 有两台机器，每台10T数据，数据中都是url，每行一个url，他们只有万分之一的
: diff，要查找有这两台机器的url的差集，需要一个准确的结果（不能用boolfilter)。
: 类似的一题是：也是两台各10T数据，一开始两边数据相同，后来可能两边有更改，如
: 果能够提供一个接口，快速的比较两边数据是否有diff，如果有，diff的是哪些url。

d*x2013-04-02 07:04

9 楼

我在单机搭了个hadoop，以后这类东西可以自己验证了

【在 p*****2 的大作中提到】

: mapreduce行吗？

b*l2013-04-02 07:04

10 楼

恩，有道理。去文件堆里查找一个URL有什么可以优化的吗？

【在 c********r 的大作中提到】

j*x2013-04-02 07:04

11 楼

大文件分成10万组，每组排序之后计算security hash，然后比较hash值，按照原文所
谓的万分之一的区别，理想情况下只需要比较十分之一的数据。能节省一点带宽
===
我幼稚了，万分之一不等于只有一万个文件

boolfilter)。

【在 h******2 的大作中提到】

p*22013-04-02 07:04

12 楼

牛。好搭吗？

【在 d**********x 的大作中提到】

: 我在单机搭了个hadoop，以后这类东西可以自己验证了

d*x2013-04-02 07:04

13 楼

也就一下午，你可以试试

【在 p*****2 的大作中提到】

:
: 牛。好搭吗？

p*22013-04-02 07:04

14 楼

什么机器都能setup吗？

【在 d**********x 的大作中提到】

: 也就一下午，你可以试试

d*x2013-04-02 07:04

15 楼

ubuntu就行

【在 p*****2 的大作中提到】

:
: 什么机器都能setup吗？

p*22013-04-02 07:04

16 楼

还真没有。郁闷了。

【在 d**********x 的大作中提到】

: ubuntu就行

r*h2013-04-02 07:04

17 楼

我也正准备弄一个玩玩:)
不知道在虚拟机里面搭能不能使用全部feature

【在 d**********x 的大作中提到】

: 我在单机搭了个hadoop，以后这类东西可以自己验证了

p*22013-04-02 07:04

18 楼

你先试试。回来汇报一下？

【在 r**h 的大作中提到】

: 我也正准备弄一个玩玩:)
: 不知道在虚拟机里面搭能不能使用全部feature

i*12013-04-02 07:04

19 楼

请问一下，这个hash到文件如何hash?
能详细讲讲吗？
譬如第二个10T数据分成多个文件，然后从第一个10T数据里一条一条的拿url，来遍历
第二个10T数据的文件，这个过程哪里用到hash?

【在 b*****a 的大作中提到】

: 可以的。其实原理和hash到小文件一样吧。

i*c2013-04-02 07:04

20 楼

theoryfrom diff/sync tools, e.g.
http://en.m.wikipedia.org/wiki/Remote_Differential_Compression#

【在 h******2 的大作中提到】

i*12013-04-02 07:04

21 楼

还是这个牛逼，写的很详细。

【在 i****c 的大作中提到】

: theoryfrom diff/sync tools, e.g.
: http://en.m.wikipedia.org/wiki/Remote_Differential_Compression#

a*s2013-04-02 07:04

22 楼

只有两台机器，如果不让用cluster的话，每台机器对自己的每个url做hash，得到一个
10TB数据的url 的hash范围[a,b]，第二台机器得到另外一个范围[c,d],假设两个集合
的交际是[c,b],然后开始如下通信：
machine 1 收集[a,c]数据并存为结果的一部分；
machine 1把[(b-c)/2,c]的数据以（url,1）的（key，value）对的发给machine2；
machine 1把从machine 2 发来的[c,(b-c)/2]的数据，连同自己disk上属于该区间的数
据，对于相同的url key，把他们的value相加，然后吧所有做完后value是1的数据存储
为结果的一部分。
machine 2做类似machine1的工作，只是数据范围是[(b-c)/2,b],并把所有数据(b,d]的
url直接存为结果。
以上可能没有考虑两个节点的load balancing，可以通过popularity检测来决定两台
machine 工作区间的划分，使其达到balancing。