Predis sharding (consistent hashing)

Question

Predis claim to have Client-side sharding (support for consistent hashing of keys). http://github.com/nrk/predis

I can do sharding using connect to an array of profiles (nodes) but it isn't consistent hashing. When I add another node to the pool, some of the keys can't be found. Anyone has any experience on this?

Using php 5.2 (and redis's php 5.2 version).

Answer 1

The official Redis site says "Redis supports client-side sharding via consistent hashing. Currently there is no support for fail tolerance nor to add or remove clusters at run time."

From what I understand at the moment this kind of sharing is not fault tolerant, and all keys stored on a failed node will be lost. Equally if you add a new node, some portion of the key space will now be lost (as the keys will be stored on the wrong node). Normally in a consistent hashing system, when a new node joins it copies all the keys which now map to it from its neighbours. There is no support in the Redis server to do this.

So the consistent hashing works fine if you are using Redis as a cache, where the actually data is stored behind Redis, but for the moment don't expect your data to not go missing.

UPDATE: It is possible to implement real sharding via a consistent hashing library called ketama.

Answer 2

The solution is to use virtual sharding. I don't know Predis framework works but I predict that it uses some kind of array - you probably fill it with information about each shard at start-up.

Assume that you will have maximum of 10 shards (this number should be unlikely to be reached). Then, create sharding array that points to only 3 real servers. In the future when you will add new nodes, you will migrate related data to new shard and change mapping. This approach preserves form changing hash function.

Initial mapping:

0 => 0 //node #0
1 => 0
2 => 0
3 => 1 //node #1
4 => 1
5 => 1
6 => 2 //node #2
7 => 2
8 => 2
9 => 2

When you adds new node you only change mapping:

0 => 0
1 => 0
2 => 3 // new node #3
3 => 1
4 => 1
5 => 3 // new node #3
7 => 2
8 => 2
9 => 3 // new node #3

so you have to move data with h(x) = 9 or 5 or 2 to node #3.