Motivation

In SQS, FIFO queues behave very differently from standard queues when receiving messages. A feature we haven't implemented at all were message group IDs. While we were able to send and track them, we didn't actually do anything with them. But they greatly affect how receiving of messages work. Here's the gist from the FIFO delivery logic.

When receiving messages from a FIFO queue with multiple message group IDs, Amazon SQS first attempts to return as many messages with the same message group ID as possible. This allows other consumers to process messages with a different message group ID. When you receive a message with a message group ID, no more messages for the same message group ID are returned unless you delete the message or it becomes visible.

The issue was first raised in #6766, and requested by several Pro users.

Turns out that this was a non-trivial change to make because of a) the way our SqsProvider communicates with the SqsQueue, and b) how messages are organized in the FifoQueue.

Changes

Here's a summary of changes and their respective commits to make it easier to review:

• f8e87a2 Added a bunch of tests to validate the behavior of AWS
• 16821e5 Refactor the communication between the SqsProvider and SqsQueue.
  The problem was that abstracting over a get method that only returns a single message was blocking a way to retrieve multiple messages from the queue atomically, which is exactly what the FIFO behavior requires. So I replaced the SqsQueue.get method with a receive method that much more closely resembles what ReceiveMessage is doing, and allows you to get multiple messages at once. Now the access to the underlying datastructure holding the messages is hidden behind receive.
• 8f1d70e Implement the actual message group logic (significant changes in the FifoQueue - completely new receive logic).
  Instead of storing individual messages in the queue, we now have a queue that orders MessageGroup objects that in turn contain a priority queue of messages. The implication is that we need more memory to store the messages. The worst case if each message has its own unique message group. The trade off is a simplified implementation of making sure that only one consumer receives a message group when there's a race for the queue. We first dequeue the message group (making it inaccessible to other consumers), and then get the messages from the group. Because we know that only one thread will access the messages in the group, it also vastly simplifies concurrent access. The visible queue is therefore now a construct that has moved completely into the StandardQueue
• f08d4ac Adapt SQS developer endpoints to the changes

Future work

Expired receipt handles

I added a currently xfailed test that shows that you cannot delete a message with an expired receipt handle in FIFO queues. I was too lazy to implement this right now, since the PR is already quite large, and it needs some additional tinkering with the receipt handle encoder.

Message group ordering

It's not clear exactly how message groups themselves are ordered in the queue. There seems to be some sort of priority in AWS given to groups when they expire, but it behaved differently depending on whether messages were removed or expired. I couldn't figure out how AWS does it exactly, and it's not documented. The only mention I could find is a vague statement I interpret as "there is no particular guarantee in which order message groups will be received".

FIFO queue logic applies only per message group ID. Each message group ID represents a distinct ordered message group within an Amazon SQS queue. For each message group ID, all messages are sent and received in strict order. However, messages with different message group ID values might be sent and received out of order.

For this reason, I had to currently allow different orderings of message groups (note that the order within a group is guaranteed)

More tests

There are a bunch more tests one could write. Including concurrent access, ordering behavior of groups with more groups to see how they are ordered after deletion etc.

Code duplication

There is a bit of code duplication especially in the receive implementations. It seems hard to generalize, and maybe not worth it at all, given that we are not going to introduce other queue types. Maybe one could extract some util methods that do some of the work (e.g. collect messages from a queue or queue-like interface).

Performance

There is a lot of locking going on in FIFO queues. Basically all access to message groups is currently completely linearized across consumers. This will affect performance mostly when there are many parallel consumers. But more systematic benchmarks are necessary, that can maybe be preformed as part of #7342

Fixes

• bug: SQS receive_message returns duplicates of same message when --visibility-timeout=0 #7397 fixed as a convenient side effect from the refactoring of the delivery logic.
• bug: concurrent requests made to a FIFO queue return messages from the same MessageGroupId #6766
• bug: Lambda should correctly process FIFO queue event sources #7036 (potentially - need to write a specific test)