haproxy consistent hashing in csharp

haproxychash.cs

// defined in haproxy/src/hash.c as hash_djb2()
static uint HashDJB2(byte[] input)
{
	var key = input;
    int i = 0;
	uint hash = 5381;

	/* the hash unrolled eight times */
    var len = input.Length;
	for (; len >= 8; len -= 8) {
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
		hash = ((hash << 5) + hash) + key[i++];
	}

	switch (len) {
		case 7: goto left7;
		case 6: goto left6;
		case 5: goto left5;
		case 4: goto left4;
		case 3: goto left3;
		case 2: goto left2;
		case 1: goto left1;
		default: goto left0;
	}

    left7:
    hash = ((hash << 5) + hash) + key[i++];
    left6:
    hash = ((hash << 5) + hash) + key[i++];
    left5:
    hash = ((hash << 5) + hash) + key[i++];
    left4:
    hash = ((hash << 5) + hash) + key[i++];
    left3:
    hash = ((hash << 5) + hash) + key[i++];
    left2:
    hash = ((hash << 5) + hash) + key[i++];
    left1:
    hash = ((hash << 5) + hash) + key[i++];
    left0:
	return hash;
}

// defined in haproxy/src/hash.c as hash_wt6()
static uint HashWT6(byte[] input)
{
	var key = input;
	uint h0 = 0xa53c965aU;
	uint h1 = 0x5ca6953aU;
	uint step0 = 6;
	uint step1 = 18;

    int i = 0;
	for (var len = input.Length; len > 0; len--) {
		uint t;

		t = key[i++];

		h0 = ~(h0 ^ t);
		h1 = ~(h1 + t);

		t  = (h1 << (int)step0) | (h1 >> (32-(int)step0));
		h1 = (h0 << (int)step1) | (h0 >> (32-(int)step1));
		h0 = t;

		t = ((h0 >> 16) ^ h1) & 0xffff;
		step0 = t & 0x1F;
		step1 = t >> 11;
	}
	return h0 ^ h1;
}

// defined in haproxy/src/hash.c as hash_sdbm()
static uint HashSDBM(byte[] input)
{
	var key = input;
	uint hash = 0;
	uint c;
    int i = 0;
    var len = input.Length;
	while (len-- != 0) {
		c = key[i++];
		hash = c + (hash << 6) + (hash << 16) - hash;
	}

	return hash;
}

// defined in haproxy/src/tools.c as __full_hash()
static uint HashAvalanche(uint a)
{
	/* This function is one of Bob Jenkins' full avalanche hashing
	 * functions, which when provides quite a good distribution for little
	 * input variations. The result is quite suited to fit over a 32-bit
	 * space with enough variations so that a randomly picked number falls
	 * equally before any server position.
	 * Check http://burtleburtle.net/bob/hash/integer.html for more info.
	 */
	a = (a+0x7ed55d16) + (a<<12);
	a = (a^0xc761c23c) ^ (a>>19);
	a = (a+0x165667b1) + (a<<5);
	a = (a+0xd3a2646c) ^ (a<<9);
	a = (a+0xfd7046c5) + (a<<3);
	a = (a^0xb55a4f09) ^ (a>>16);

	/* ensure values are better spread all around the tree by multiplying
	 * by a large prime close to 3/4 of the tree.
	 */
	return a * 3221225473U;
}

// defined in haproxy/src/lb_chash.c as chash_init_server_tree()
static ServerNode[] PopulateHashRing(Server[] servers, int weightScale = 16, int weightRange = 256)
{
    var totalWeights = servers.Sum(s => s.Weight * weightScale);
    var hashRing = new ServerNode[totalWeights];
    int idx = 0;
    foreach (var server in servers)
    {
        // if server weight = 1, it will have 1 * 16 (scale) = 16 nodes in the hash ring
        // if server weight = 10, it will has 10 * 16 (scale) = 160 nodes in the hash ring
        for (int i = 0; i < server.Weight * weightScale; ++i)
        {
            var hashInput = (uint)(server.Id * weightRange * weightScale + i);
            var hash = HashAvalanche(hashInput);
            var node = new ServerNode() { Server = server, Key = hash };
            hashRing[idx++] = node;
        }
    }
    return hashRing.OrderBy(n => n.Key).ToArray();
}

// logic can be finded in haproxy/src/backend.c in get_server_hh()
static uint GetRequestHash(string userId, Func<byte[], uint> hasher, bool avalanche = false)
{
    var bytes = Encoding.ASCII.GetBytes(userId.ToCharArray());
    var hash = hasher(bytes);
    if (avalanche)
    {
        hash = HashAvalanche(hash);
    }
    return hash;
}

// defined in haproxy/src/lb_chash.c as chash_get_server_hash()
static Server ConsistentGetServer(ServerNode[] ring, uint requestHash)
{
    // brute-force sequential search... and horribly written, but works
    // in reality should build a tree or do binary search
    if (requestHash <= ring[0].Key)
    {
        return ring[0].Server;
    }
    else if (requestHash >= ring[ring.Length - 1].Key)
    {
        return ring[ring.Length - 1].Server;
    }

    int i = 1;
    for (; i < ring.Length; ++i)
    {
        if (requestHash <= ring[i].Key)
        {
            break;
        }
    }

    var dp = requestHash - ring[i - 1].Key;
    var dn = ring[i].Key - requestHash;
    if (dp <= dn)
    {
        return ring[i - 1].Server;
    }
    else
    {
        return ring[i].Server;
    }
}

static void Main_TestConsistentHash()
{
    var servers = new Server[]
    {
        new Server() { Id = 2130732033, Name = "datacache1", Weight = 16 },
        new Server() { Id = 2130732034, Name = "datacache2", Weight = 16 },
        new Server() { Id = 2130732035, Name = "datacache3", Weight = 16 },
        new Server() { Id = 2130732036, Name = "datacache4", Weight = 16 },
        new Server() { Id = 2130732037, Name = "datacache5", Weight = 16 },
        new Server() { Id = 2130732038, Name = "datacache6", Weight = 16 },
        new Server() { Id = 2130732039, Name = "datacache7", Weight = 16 },
        new Server() { Id = 2130732040, Name = "datacache8", Weight = 16 },
    };

    var ring = PopulateHashRing(servers);
    var userIds = new string[]
    {
        "14f904fd-c18d-126e-68a5-b01e46a33577",
        "9676282e-17b2-da60-1d33-83091aaa7d70",
        "ccdc0674-3978-515a-24f4-df3b6083285a",
        "76cfef99-a0e8-7507-eefd-15b67f8bdc83",
        "c01d4090-b86c-92a5-ebf5-89224bc4982d",
        "e6396344-3544-9c99-b901-c324db52858d",
        "6d871165-877b-8c34-6f55-b5c2db4c812d",
        "6ad9fb7d-7173-246e-ad20-721362adc63b",
        "46bef82f-a3d3-3c73-e3d8-24e2a1f09f42",
        "c7e72eb4-1be0-38f6-dac6-fa9c36dc341e"
    };

    foreach (var userId in userIds)
    {
        var hasher = HashDJB2;
        // var hasher = HashSDBM;
        // var hasher = HashWT6;

        var requestHash = GetRequestHash(userId, hasher, avalanche: false);

        var server = ConsistentGetServer(ring, requestHash);
        Console.WriteLine("UserId {0} matched server {1}", userId, server.Name);
    }
}

Main_TestConsistentHash();

class Server {
    public int Id { get; set; }
    public string Name { get; set; }
    public int Weight { get; set; }
}

class ServerNode {
    public Server Server { get; set; }
    public uint Key { get; set; }
}