How are distributed queues architectured?

Question

What are architectural patterns/solutions that make distributed queues tick?

Please share for both ordered and non-ordered types.

Answer 1

You can think of the backend of a queue as a replicated database. (I am assuming the queues you are talking about consider themselves as durable: when they accept a message, they guarantee at least once delivery.)

As a replicated database, the message queue backend uses a replication protocol to make sure the message is on at least N hosts before acknowledging receipt to the sender. Common replication protocols are 2PC, 3PC, and consensus protocols like Raft, Multi-Paxos, and Chain Replication.

To send a message to a receiver, you have to do almost the same replication with a message lease. The queue server reserves the message for a certain period of time; it sends the message to the receiver, and if/when the receiver ackowledges receipt of the message the server deletes the message. Otherwise, the servers will resend the message to the next available receiver.

Some message queues stop there, others add lots of bells and whistles. SQS is one queue implementation that doesn't add many bells and whistles so that it can scale more. It allows them, for example, to shard the queue so that one SQS queue is actually made of many—even thousands—of these queues as described above. As an aside, I once heard one SQS developer ask another "What does 'ordering' mean when you are accepting millions of messages per second?"

That being said, some queues do provide strong ordering guarantees. (I have implemented a couple of these types of systems.) The cost of this is less ability to scale. To maintain ordering the queue's complexity goes way up. The queue has to maintain an ordered log of all the messages, and have the same ordering replicated across its servers. This is much much harder than unordered replication. Ordered queue systems typically elect a master to maintain the ordering and all messages are routed to the master. They also tend to use the more complex protocols for replication.