Consistent Hashing in .NET


Consistent hashing is a powerful tool for spreading a load across a distributed system. A popular library is Ketama, writen in C. I implemented the same idea in C# using the MD5 hash function, just as Ketama does. Unfortunately it ran at roughly 40MB/s. I don’t think we need a true cryptographic hash function. Instead, I think we only need uniformity, which spreads the inputs evenly across the range of output values. I tried using this C# implementation of the Murmer 2 hash function. It ran at around 600MB/s, about 15 times faster than the MD5 version. I doubt Ketama is the bottleneck in any real system, but there’s no reason to use a more expensive hash function. The code is below.

class ConsistentHashing<T>
    {
        struct Point
        {
            public readonly UInt32 key;
            public readonly T bucket;

            public Point(UInt32 k, T v)
            {
                key = k;
                bucket = v;
            }
        }

        MurmurHash2UInt32Hack hash = new MurmurHash2UInt32Hack();
        //private MD5Wrap hash = new MD5Wrap();
        private Point[] circle;

        public T GetBucket(byte[] input)
        {
            UInt32 top = (UInt32)circle.Length;
            UInt32 high = top;
            UInt32 low = 0;
            var val = hash.Hash(input);

            while(true)
            {
                UInt32 mid = (high - low)/2 + low;
                var pt = circle[mid];
                if (val > pt.key)
                    low = mid;
                else if (val < pt.key)
                    high = mid;
                if (mid == top)
                    return circle[0].bucket;
                else if (high - low <= 1)
                    return circle[mid].bucket;
            }
        }

        public ConsistentHashing(IEnumerable<T> buckets)
        {
            var lst = new SortedList<UInt32,Point>();
            var encoder = Encoding.ASCII;
            foreach (var bucket in buckets)
            {
                for (var i=0; i < 160; i++)
                {
                    var name = bucket.ToString() + i;
                    byte[] input = encoder.GetBytes(name);
                    var key = hash.Hash(input);
                    lst.Add(key, new Point(key, bucket));
                }
            }

            circle = lst.Values.ToArray();
        }
    }
Advertisements

2 comments

  1. socorroco

    That is very good. But can you explain how to implement the line: MurmurHash2UInt32Hack hash = new MurmurHash2UInt32Hack();

    … what does need to be imported in the .cs file?

    • Pinku

      It’s the link under the text “this C# implementaton”. He’s got several different implmentations on that page.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s