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。 |
