How does Rendezvous Hashing help me avoid email delays?

In the morning, as soon as I arrived at the company and greeted the beautiful receptionist, I walked energetically to my workplace, only to be immediately notified of an incident. Some customers reported that their emails, sent since yesterday, have yet to be delivered. Today would be a day to stay at home. After investigating the issue, it was discovered that one particular customer had sent nearly a million emails that were still pending, causing a delay for other customers. In essence, the email system was functioning as follows.

In the system, there is a queue to line up email-sending requests. Typically, the number of sending requests is low, and they are processed sequentially, so they get cleared out. However, in this case, that customer sent excessive emails. If he had sent them alone, it wouldn’t have been an issue, but other customers who sent just one or two emails have been waiting endlessly without receiving any response. They have been calling our customer support team, causing them to break out in a sweat (it’s currently 8 degrees outside). I always felt sorry for these beautiful colleagues, so I had to take action.

There is only one congested queue, so we need to increase the queue. At this point, the system will look like this.

I thought everything was fine, but it turned out it wasn’t. Scaling up didn’t improve the performance because the producer sent messages to the queue using round-robin distribution. This means that each new email received was sequentially pushed into those queues. As a result, the customers with nearly a million emails were evenly distributed across multiple queues, with each queue having less than 100,000 emails, still causing congestion for other customers. I was a bit annoyed at this point, so I put that particular customer in a separate queue to mitigate the impact. However, the challenge was identifying emails from that customer, placing them in the designated queue, and ensuring that future customers from different companies would also be directed to their respective dedicated queues, avoiding the situation where one company ends up in multiple queues and affects others. Of course, there may be cases where unfortunate customers still end up in the same queue as the customer above, but it would be less frequent and cause fewer complaints.

The simplest solution is to use modulo division. For example, if there are five servers, we can divide the customer’s ID by 5. If the remainder is 0, the customer goes to queue 1. If the remainder is 1, the customer goes to queue 2, and so on. This method ensures that each customer is assigned to exactly one queue. However, what happens if I need to add or remove queues? In that case, all messages will be shuffled, leading to potential chaos in the consumer systems’ caches. Additionally, we need to consider the issue of equal distribution. What if there are some customers whose IDs all result in a remainder of 0 when divided by 5?

Now, we need an algorithm to handle this issue so that adding or removing nodes doesn’t disrupt the message and queue system. Consistent hashing and Rendezvous Hashing are two commonly used approaches for this. These methods are often employed for server partitioning in load balancing, similar to the queue scenario. The crucial aspect is ensuring even distribution. Consistent hashing is a bit complex, but since I’m lazy, I’ll look for Rendezvous Hashing to handle this. Unfortunately, I couldn’t find any libraries, so I had to code it myself. I’ve placed the source code here. At this point, the model will look like this.

PS: Below is a description of the even distribution of the Rendezvous Hashing algorithm!

Let’s assume we have five nodes and 10,000 different companies with the following C# code snippet:

using Rendezvous;

namespace Demo
{
    internal class Program
    {
        static void Main(string[] args)
        {

            List<Node> nodes = new List<Node>();
            for (int i = 0; i < 5; i++)
                {
                    nodes.Add(new Node("node" + i, 1));
                }
            Rendezvous.RendezvousHash rendezvous = new Rendezvous.RendezvousHash(nodes);

            Dictionary<string, int> countItemInNode = new Dictionary<string, int>();

            for (int i = 0; i < 10000; i++)
            {
                var item = Guid.NewGuid().ToString();
                var nodeName=rendezvous.GetNode(item).Name;
                if (countItemInNode.ContainsKey(nodeName))
                {
                    countItemInNode[nodeName]++;
                }
                else
                {
                    countItemInNode[nodeName] = 1;
                }
            }

            foreach (var item in countItemInNode)
            {
                Console.WriteLine(item.Key + ":" + item.Value);
            }
        }
    }
}

Below are the results of node distribution using this algorithm. As you can see, it is very even with minimal deviation. Each queue receives approximately 2000 messages.

If you find it helpful, please upvote and share to motivate me to continue writing more!