b******7
发帖数: 79 | 1 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
，结果今天吃亏了。
一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
但是如果放到新的上，那怎么改hash?
肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了，而且给你一个hash,
旧的文件属于新的还是就得server没法得到。
希望牛人指点！！！非常感谢！ |
S*********N
发帖数: 6151 | 2
new hash-function offset by 7 with % 14 ?
【在 b******7 的大作中提到】
: 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
: 究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
: ，结果今天吃亏了。
: 一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
: 一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
: 以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
: 可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
: write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
: 但是如果放到新的上，那怎么改hash?
: 肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
|
b******7
发帖数: 79 | 3 这样肯定不对。注意一定要保证旧的文件仍旧能被访问。给你一个hash,你怎么知道这
个hash对应的文件在旧的server中。 |
l***i
发帖数: 1309 | 4 不知道这么做行不行。The old servers are 1 to 7, the new servers are 8 to 14.
Now given a request, compute hash%7+1. And then search for the file in both
old(hash%7+1) and new(hash%7+8), if you found it in old, then do nothing. If
you do not find in both old and new, then store a copy of that file in one
of the new servers(hash%7+8). |
b******7
发帖数: 79 | 5 我题的方法和你说的其实一样，就是hash 后再hash 0/1, 这样搜索两个对应的server.
这样不高效，不行。还有一个方法，我想到的就是对旧server文件建map,存已经在旧
server上文件的hash，但是这样明显也很浪费资源。
14.
both
If
one
【在 l***i 的大作中提到】
: 不知道这么做行不行。The old servers are 1 to 7, the new servers are 8 to 14.
: Now given a request, compute hash%7+1. And then search for the file in both
: old(hash%7+1) and new(hash%7+8), if you found it in old, then do nothing. If
: you do not find in both old and new, then store a copy of that file in one
: of the new servers(hash%7+8).
|
g*******y
发帖数: 1930 | 6 用一个hashset来存旧server的所有文件的MD5，这个hashset的size肯定很小，相对于原来存文件本身来说
新文件就%7以后存到server上，query的时候，先在hashset上查，然后确定在旧server还是新server上
server.
【在 b******7 的大作中提到】
: 我题的方法和你说的其实一样，就是hash 后再hash 0/1, 这样搜索两个对应的server.
: 这样不高效，不行。还有一个方法，我想到的就是对旧server文件建map,存已经在旧
: server上文件的hash，但是这样明显也很浪费资源。
:
: 14.
: both
: If
: one
|
N*D
发帖数: 3641 | 7 正确的做法是backfill，其他解法都是hack
我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
，结果今天吃亏了。
一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
但是如果放到新的上，那怎么改hash?
肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
为0的去旧server,1的去新server,但是这个缺点是旧的已经满了，而且给你一个hash,
旧的文件属于新的还是就得server没法得
【在 b******7 的大作中提到】
: 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
: 究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
: ，结果今天吃亏了。
: 一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
: 一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
: 以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
: 可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
: write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
: 但是如果放到新的上，那怎么改hash?
: 肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
|
m******9
发帖数: 968 | 8 难题，我在本版上也看到过，也没有仔细想过
有谁能具体解答一下呀，同谢谢 |
k**u
发帖数: 698 | 9 大牛能否详细说说？
【在 N*D 的大作中提到】
: 正确的做法是backfill，其他解法都是hack
:
: 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
: 究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
: ，结果今天吃亏了。
: 一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
: 一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
: 以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
: 可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
: write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
|
a****s
发帖数: 559 | 10 问题没明白。7个server里，每个server有多少文件。如果很多的话，hash%7只是算一
个文件该去那个server. 具体到了一个server上还要其它方式组织。那么就按lanti说
的1-7对应8-14，没什么不高效啊？最坏情况不过是搜索时间加倍，但时间复杂度不变
。 |
|
|
N*D
发帖数: 3641 | 11 俺胡诌的，呵呵。俺脚的工业界正确的做法是吧7个server上的文件按照新的hash，重新
分布到14个server上去。
【在 k**u 的大作中提到】
: 大牛能否详细说说？
|
S*********N
发帖数: 6151 | 12
重新
我觉得工业界可以用双工，
每个server加个挂兜，哈哈。
【在 N*D 的大作中提到】
: 俺胡诌的，呵呵。俺脚的工业界正确的做法是吧7个server上的文件按照新的hash，重新
: 分布到14个server上去。
|
N*D
发帖数: 3641 | 13 现在流行的做法是放到云里面去，scalable storage，server不会run out of space，
不会有这个user case。
【在 S*********N 的大作中提到】
:
: 重新
: 我觉得工业界可以用双工，
: 每个server加个挂兜，哈哈。
|
S*********N
发帖数: 6151 | 14
scalable storage,
that is what I am talking.
there are different ways to implement.
cluster->cloud?
【在 N*D 的大作中提到】
: 现在流行的做法是放到云里面去，scalable storage，server不会run out of space，
: 不会有这个user case。
|
N*D
发帖数: 3641 | 15 cloud是指scalable computing；scalable storage的example比如Amazon S3
【在 S*********N 的大作中提到】
:
: scalable storage,
: that is what I am talking.
: there are different ways to implement.
: cluster->cloud?
|
H*M
发帖数: 1268 | 16 为什么不能挪动原来server文件?原体是这样说的吗?严格不能挪动还是说挪动是const的
complexity?
【在 b******7 的大作中提到】
: 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
: 究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
: ，结果今天吃亏了。
: 一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
: 一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
: 以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
: 可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
: write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
: 但是如果放到新的上，那怎么改hash?
: 肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
|
k**s
发帖数: 53 | 17 分两种情况：
1. 新数据插入: hash%7 + 8 到新server上
2. 数据查询：同时送到hash%7 和 hash%7 + 8两台server, 有数据的那台server最终
回答。
【在 b******7 的大作中提到】
: 我刚刚面试amazon被问得，首先，这是一道老题，后悔当时看到这道题的时候没仔细研
: 究。以前我在版内看过这道题，但是没有人提出正确解，我也就大概想了想，没仔细想
: ，结果今天吃亏了。
: 一个分布式文件系统，7个server, 原来的文件用MD5 hash后分布到这7个server中的某
: 一个(比如hash%7)，现在这些server快满了，就增加了7个server, 这样新文件来了可
: 以放到这些新的server上面。问题是，我们不能挪动原有server的文件，旧的文件仍旧
: 可以被访问。那么我们怎么改这个hash系统以至于新，旧文件都可以被正常read,
: write。举例，如果新文件来了，我们如果还是hash%7，那么就会放到旧的server上，
: 但是如果放到新的上，那怎么改hash?
: 肯定要用hierarchical 的hash,比如，如果hash%7==1, 这些hahs被再次hash为0，1，
|
k**s
发帖数: 53 | 18 我这个是假设前端拿到请求后就已经知道是insert还是query. 这个假设一般应该是成
立的。
【在 k**s 的大作中提到】
: 分两种情况：
: 1. 新数据插入: hash%7 + 8 到新server上
: 2. 数据查询：同时送到hash%7 和 hash%7 + 8两台server, 有数据的那台server最终
: 回答。
|
a*****i
发帖数: 268 | 19 是以前所有的文件都不能挪动，还是可以少量挪动以前的文件？
如果是后者，可以用consistent hashing。 |
