i********r 发帖数: 12113 | 1 有7台server,存在哪台server,用hash value %7,现在需要扩展到14台,算法如何改
变,要求还可以访问到原来在
server的数据。如果扩展到任意多台,如何改进。 |
H*M 发帖数: 1268 | 2 how about save the old hash functions and iterate until you find the data?
I don't think you can use a diff new hash function while make the old remain
in the machines hashed by old functions.
【在 i********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有7台server,存在哪台server,用hash value %7,现在需要扩展到14台,算法如何改 : 变,要求还可以访问到原来在 : server的数据。如果扩展到任意多台,如何改进。
|
H*M 发帖数: 1268 | 3 当server数很大的时候,就不行了
可以考虑用linear hashing,或者extendable hashing
每次加新机器的时候只split一台机器上的,而且hashing functions也有规律.这样 am
ortized的complexytiy还是O(1)
remain
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how about save the old hash functions and iterate until you find the data? : I don't think you can use a diff new hash function while make the old remain : in the machines hashed by old functions.
|
g*******y 发帖数: 1930 | 4 将原来7台机子上存的keys拿来rehashing一次,按照新的hash值移动到新的server。
考虑到data比较大,移动会有很大cost,可以在新server相应的储存该key的地方,设一个forward的标签,把fetch data的request forward到旧server上 |
H*M 发帖数: 1268 | 5 第一个方案肯定不行的,如果hash function没规律的话,移动data复杂度太大,最坏的
N太机器全要移动。
forward idea不错。不过可能会要forward好多层。每变一次hashfunction就要forward
。
设一个forward的标签,把fetch data的request forward到旧server上
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 将原来7台机子上存的keys拿来rehashing一次,按照新的hash值移动到新的server。 : 考虑到data比较大,移动会有很大cost,可以在新server相应的储存该key的地方,设一个forward的标签,把fetch data的request forward到旧server上
|