Consistent hash exchange - keeping track of a timeline
But before we look under the hood, lets familiarize with the concept of consistent hashing and when to use it.
Messages sent to a queue are generally sent in order, first message in - first message out. And, when we say out, we often mean; "to be handled by a consumer". One queue with one consumer would then automatically mean that messages are sent and handled in order. But, brokers can consist of several queues with several consumers connected. When systems scale, message ordering per key are kept by adding a consistent hash exchange to route messages to queues, based on value or id (which keeps ordering for each key, but not between different keys).
The idea is simple; if we as an example want colorful marbles to pass through a funnel and land in buckets, a consistent hash exchange would ensure that all marbles of same color would end up in the same bucket.
But in what scenarios is consistent hashing useful?
To put it into context: the company Prosa addresses the scenario in this use case. Their business model involves doing narrative analysis of texts as they are being written, then alerting the writer of potential inconsistencies or narrative issues in real time. The idea is built on information entering the system in a strict timeline, eg., in the order the author wrote them - newest information needs to be the truth, and updates need to be presented in a sequential order; otherwise, it would not make sense. All updates from a specific user then need to be handled by the same consumer.
Read the full Prosa case study
How the actual hashing plays out depends on the underlying algorithms of the exchange, and as with everything else, there are often more than one option.
AMQP broker LavinMQ recently introduced using the jump instead of the ring algorithm, and therefore, it's reasonable to explain the difference between them.
Ring Consistent Hash algorithm
To explain the concept simply: Ring Consistent Hash distributes messages by spreading a queue across many vnodes (virtual nodes) in a circle, like numbers on a clock face. Messages carry a hash value based on their routing key. It could be a user ID, order ID, or any other value that identifies what the message is about.
In a scenario with 3 queues, each with 10 vnodes, the ring would carry 30 vnodes pointing to 3 different queues.
The number of vnodes per queue is specified as the queue weight. The higher the number, the more vnodes in the ring.
When a message arrives, the exchange calculates its hash value and then searches through the ring's vnodes to find the "next highest number." This means that a message with #20 is sent to the first vnode at 21 or higher.
Jump Consistent Hash
Jump Consistent Hash does not distribute queues around a circle using virtual nodes. Instead, it just lines your queues up in a row and gives them strict sequential numbers (e.g., Queue 1, Queue 2, Queue 3).
Messages still carry a hash value based on their routing key. However, instead of "finding" a place for the message, the algorithm relies on a fast probability formula - only using the message's hash value, and the total number of queues to determine where it should go.
In analogy terms, if queues were compared to tables at a party, jump consistent hashing would ensure that when more guests (messages) arrive and new tables (queues) need to be added, only the minimal amount of guests needs to move to spread the guests evenly. Most guests get to stay exactly where they are.
The formula uses the hash value to seed a random number generator. Then it calculates a fraction that tells it exactly how many tables it can safely "jump" over.
The loop keeps jumping forward until the next jump would push the message past the total number of available tables (
num_buckets
). When it stops, the very last table it landed on (
b
) is where the message is sent.
Comparison ring vs. jump
With a consistent hash exchange, the entire goal is to spread the processing work evenly across all your queues while maintaining message ordering. While both algorithms do this, they use fundamentally different approaches.
In a setup where the ring algorithm is used, the weight of the queue dictates how many nodes point to each queue on the ring. This is worth keeping an eye on, since setting the weight too low might create gaps and uneven workloads, while setting it too high requires more server memory to store the nodes and extra CPU cycles to search them. You also have to consider that if multiple routing keys hash to the exact same number, they form a single block of data that the algorithm cannot divide.
In that same setup, the Jump algorithm calculates the destination using a probability formula based solely on the message key and the total number of queues. This allows it to route messages instantly with almost zero overhead since it never stores a map of the system in memory.
The algorithms also handle server failures differently. Because the Jump algorithm relies on a continuous mathematical sequence of queues, a lost queue must be explicitly replaced. Systems typically solve this using a logical mapping approach, in which a new queue is brought up to replace the failed one, keeping the mathematical sequence intact.
When the Ring algorithm faces a server failure, the exchange simply removes the nodes belonging to the crashed queue from the ring. When the next message arrives, the algorithm scans clockwise, bypasses the missing queue, and deposits the message at the next available marker to naturally adjust the traffic flow.
Good to know about consistent hashing
Consistent hashing with strict message ordering can face difficulties, and the best way to avoid them is to be aware that they exist.
In this scenario, even distribution might be disrupted; In unlikely cases, a single entity might generate a large, disproportionate amount of traffic compared to everyone else. In system design, this is called a heavy hitter or noisy neighbor. But because of the promise of message ordering, this entity will always be directed to the same queue, leading to potentially creating uneven load between the queues. To avoid this, make sure to monitor your queue lengths.
Broken ordering might also occur in scenarios where the consumer fails and no one steps in to replace. Normally, consumers failure are not really an issue. If you have a single active consumer with queues on standby, the risk of losing messages is minimal. But in a scenario where a consumer stops or dies and no replacement is ready to step in, messages from one entity will be piled up in the queue until you hit x-max-length. Messages piled up in one queue will maintain message ordering, but once
x-max-length
is reached, messages will start being dropped instead of piling up further, and that is when the ordering guarantee breaks. To avoid this, ensure you have backups ready for queues where you cannot afford to lose message ordering.
When Systems Scale: why prefer jump?
As announced, the Jump algorithm will be the new default in LavinMQ 3.0, but users have been able to opt in since version 2.7. This conscious choice was made based on the easy scaling and fast performance that the jump algorithm brings. In software like LavinMQ, performance and production trust are crucial. It simply aligns with the mission of the software.
Do you have experience with consistent hash exchange and would like to discuss it? Or maybe have questions about how to configure your setup to avoid the vulnerabilities better. We would love to hear about your experiences and how we can help.
Reach out to us; contact@cloudamqp.com
