Data structure to use for a consumable message queue where it's safe for messages to overwrite one another
Sorry, you have to tell us more.  We can't tell you what you should do in case of a failure; that will depend upon the application semantics and the type of a failure.

In general, in the event of a failure of an attempted operation, there are several options:


Retry the operation later.
Treat the failure as permanent.


If you decide you want to retry it later, then the implications of this for other operations depends on the dependencies between operations and the desired semantics.  If operations A and B commute (performing A first then B has the same effect as B then A), and if you try A and it fails, then often you can perform B immediately and then retry A.  If operations A and B don't commute, and you try A first and it fails, then performing B immediately and then retrying A will have different semantics, which might or might not be acceptable depending upon what guarantees you are trying to provide.

Related topics: ACID, database transactions.



Example: Suppose you have a one-level filesystem (with no directories), and the intended semantics are that operations on one file can be performed in an arbitrary order compared to operations on another file (but operations on a single file are performed in the order they were requested).

Then operations A and B commute if they are performed on different files, and they don't commute if they're performed on the same file.  Thus, conceptually you can maintain one queue per file.  When you receive a request to perform operation $O$ on file $F$, append $O$ to the queue for $F$.  Whenever you are free to perform an operation, pick an arbitrary file whose queue is non-empty and try the operation at the head of the queue.  If the operation succeeds, then you can pop it from the queue.  If it fails and you want to retry it later, then you have to leave it at the head of the queue to be retried later.

Such a data structure can be implemented with a hash table of queues. The hash table is keyed on the filename; it yields a queue.  It's easy to implement all the necessary behaviors using this data structure.



I am assuming that there are only two possible outcomes of an attempted operation: success (the operation is performed in full), or failure (and there is no effect: this is the same as a no-op).  If it is possible that an operation can fail partway through without rolling back its effects, so it has a partial effect, then you've got much bigger problems.