if you're using a queue like SQS and expect it to be ordered and exactly-once, you're in for a lot of surprise. If you need ordering, use a stream/log like Kinesis or Kafka.
Exactly-once is not a requirement but ordering is. I had Kafka and Kinesis in mind when writing this question but just in case you haven't seen it, there is a way to get ordering guarantees using SNS and SQS:
Does that really guarantee in-order processing, or just that messages can be picked up in order. If you have multiple consumers on your queue and consumer A picks up message x from the head of the queue then consumer B picks up message y next, it is possible for y to get processed before x. Maybe consumer A is slow (gc pause?) for some reason, and now we are processing out of order, even though the queuing infrastructure does not see it. If you truly need to guarantee strict processing order (x must complete before you start processing y) I think you may need to build that into your app. Or, I misread, which is very possible.