I’m reminded of classical LRU cache implementation - double linked list and a hash map that points to the list elements.

It is a queue if we squint really hard, but it allows random access and reordering. Do we have durable structures of this kind?

I can’t imagine how to shoehorn this into Kafka or SQS.