ensures the consistent hash cycle unchanged when collide

Bug #1308077 reported by Jianjun Zheng on 2014-04-15
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
libmemcached
Undecided
Unassigned

Bug Description

When the virtual node A and virtual node B collides, the order of A and B on the consistent hash cycle is undetermined.
Because of different implementation of sort functions in various languages or unstable sort algorithm like quick sort,
the order of A and B may be different in different clients(e.g. Client X, Client Y).

It could cause such a serious problem:
Client X : set foo hello
Client Y : get foo
with a small probability:
the client X's key(foo) point to node A, while the client Y's key point to node B.

Thus, all the keys that point to node B in Client Y will fail when doing Get commands.

It will be better if the flag of use_sort_hosts gets set, which makes the comparing of index(in the patch) meaningful even when servers order in the configure rearranged.

Jianjun Zheng (codeeply) wrote :
Jianjun Zheng (codeeply) on 2014-04-15
description: updated
description: updated
Jianjun Zheng (codeeply) on 2014-04-15
tags: added: consistent hash
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Patches