h******2 发帖数: 13 | 1 有两台机器,每台10T数据, 数据中都是url,每行一个url, 他们只有万分之一的
diff, 要查找有这两台机器的url的差集, 需要一个准确的结果(不能用boolfilter)。
类似的一题是:也是两台各10T数据,一开始两边数据相同,后来可能两边有更改,如
果能够提供一个接口,快速的比较两边数据是否有diff, 如果有,diff的是哪些url。 |
s*****1 发帖数: 134 | 2 我的思路是先对两台机器各自进行 external sort
然后用两个pointer, 指向各自的起始位置,一行一行比 |
c********r 发帖数: 4 | 3 感觉不需要排序就能做了,类似找重复数字的原理,只不过10T数据显然不能放进一个
大数组里。分成若干个文件,读到了一个url就去文件堆里找,有的话就消掉,没的话
就加上,最后文件堆里剩下的就是2个机器的差异. |
s*****1 发帖数: 134 | 4 恩,你说的有道理,可以根据hash值分成若干个文件比对。 |
p*****2 发帖数: 21240 | |
b*****a 发帖数: 7 | 6 嗯 就是这样做的
【在 c********r 的大作中提到】 : 感觉不需要排序就能做了,类似找重复数字的原理,只不过10T数据显然不能放进一个 : 大数组里。分成若干个文件,读到了一个url就去文件堆里找,有的话就消掉,没的话 : 就加上,最后文件堆里剩下的就是2个机器的差异.
|
b*****a 发帖数: 7 | 7 可以的。其实原理和hash到小文件一样吧。
【在 p*****2 的大作中提到】 : mapreduce行吗?
|
d**********x 发帖数: 4083 | 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**********x 发帖数: 4083 | 9 我在单机搭了个hadoop,以后这类东西可以自己验证了
【在 p*****2 的大作中提到】 : mapreduce行吗?
|
b*******l 发帖数: 590 | 10 恩,有道理。去文件堆里查找一个URL有什么可以优化的吗?
【在 c********r 的大作中提到】 : 感觉不需要排序就能做了,类似找重复数字的原理,只不过10T数据显然不能放进一个 : 大数组里。分成若干个文件,读到了一个url就去文件堆里找,有的话就消掉,没的话 : 就加上,最后文件堆里剩下的就是2个机器的差异.
|
|
|
j********x 发帖数: 2330 | 11 大文件分成10万组,每组排序之后计算security hash,然后比较hash值,按照原文所
谓的万分之一的区别,理想情况下只需要比较十分之一的数据。能节省一点带宽
===
我幼稚了,万分之一不等于只有一万个文件
boolfilter)。
【在 h******2 的大作中提到】 : 有两台机器,每台10T数据, 数据中都是url,每行一个url, 他们只有万分之一的 : diff, 要查找有这两台机器的url的差集, 需要一个准确的结果(不能用boolfilter)。 : 类似的一题是:也是两台各10T数据,一开始两边数据相同,后来可能两边有更改,如 : 果能够提供一个接口,快速的比较两边数据是否有diff, 如果有,diff的是哪些url。
|
p*****2 发帖数: 21240 | 12
牛。好搭吗?
【在 d**********x 的大作中提到】 : 我在单机搭了个hadoop,以后这类东西可以自己验证了
|
d**********x 发帖数: 4083 | 13 也就一下午,你可以试试
【在 p*****2 的大作中提到】 : : 牛。好搭吗?
|
p*****2 发帖数: 21240 | 14
什么机器都能setup吗?
【在 d**********x 的大作中提到】 : 也就一下午,你可以试试
|
d**********x 发帖数: 4083 | 15 ubuntu就行
【在 p*****2 的大作中提到】 : : 什么机器都能setup吗?
|
p*****2 发帖数: 21240 | 16
还真没有。郁闷了。
【在 d**********x 的大作中提到】 : ubuntu就行
|
r**h 发帖数: 1288 | 17 我也正准备弄一个玩玩:)
不知道在虚拟机里面搭能不能使用全部feature
【在 d**********x 的大作中提到】 : 我在单机搭了个hadoop,以后这类东西可以自己验证了
|
p*****2 发帖数: 21240 | 18
你先试试。回来汇报一下?
【在 r**h 的大作中提到】 : 我也正准备弄一个玩玩:) : 不知道在虚拟机里面搭能不能使用全部feature
|
i****1 发帖数: 445 | 19 请问一下,这个hash到文件如何hash?
能详细讲讲吗?
譬如第二个10T数据分成多个文件,然后从第一个10T数据里一条一条的拿url,来遍历
第二个10T数据的文件,这个过程哪里用到hash?
【在 b*****a 的大作中提到】 : 可以的。其实原理和hash到小文件一样吧。
|
i****c 发帖数: 102 | 20 theoryfrom diff/sync tools, e.g.
http://en.m.wikipedia.org/wiki/Remote_Differential_Compression#
【在 h******2 的大作中提到】 : 有两台机器,每台10T数据, 数据中都是url,每行一个url, 他们只有万分之一的 : diff, 要查找有这两台机器的url的差集, 需要一个准确的结果(不能用boolfilter)。 : 类似的一题是:也是两台各10T数据,一开始两边数据相同,后来可能两边有更改,如 : 果能够提供一个接口,快速的比较两边数据是否有diff, 如果有,diff的是哪些url。
|
i****1 发帖数: 445 | 21 还是这个牛逼,写的很详细。
【在 i****c 的大作中提到】 : theoryfrom diff/sync tools, e.g. : http://en.m.wikipedia.org/wiki/Remote_Differential_Compression#
|
a*****s 发帖数: 1121 | 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。 |