Function to shard/distribute (consistent hashing)?

I have thought a bit about making a somewhat lightweight consistent-hashing-like PHP function to shard uploaded files between different servers.

Obviously, rand() would work to distribute the files among the servers somewhat evenly, but when requesting the files, no one will know which file lies on what server...

I know that there's some extensive libraries out there to create consistent-hashing, but I wonder how these works and how I can do t开发者_开发问答o roll out my own, very lightweight one?

Note: I do not take into account that servers will be removed, but instead more ones added to the pool further on.

Update:

Here's a quick line of psuedocode:

$config['shards'] = array('192.168.1.1, 192.168.1.2');

function shard ($filename) {

    $servers = $config['shards'];

    // do lookup in some magic way to decide which server to return.

    return $appropriateserver;
}


echo shard('filename.jpg'); // returns the appropriate server to distribute the file.

---

Well, one thing you could do would be to use crc32...

$crc = crc32($mykey);
$serverNo = $crc % count($servers);

It should be fairly consistent (meaning evenly balanced), and 100% reproducible...

---

I recommend using MurmurHash3: it is much faster than cryptographic hash functions, while preserves similar randomness. MurmurHash speed is close to CRC32 or even better. There is PHP implementation.

---

an eventual solution would be:

CRC32(key) % 4 when you only have 4 servers

and when you want to rebalance you can use 2 different hash functions while migration

ex:

$server_hash1 = crc32($key) % 4
$result = $db->search($server_hash1, $key);

if ($result == false)
{
    $server_hash2 = crc32($key) % 8
    $result = $db->search($server_hash2, $key);
}

• You have to do the same for insert/update (with a move function from config1 to config2)
• You can do the move async (batched way)