Partial ordering of events in distributed system in practice

We are using Symfony Messenger with Amazon SQS as message queue. We have no guarantee that events will be processed in same order as they was dispatched.

Example

We have Payment:

class Payment {
    public static function create(): void;
    public function setAsCharged(): void;
    public function setAsFailed(): void;
}

We receive set of actions that happened on Payment in one batch and dispatch them to queue:

$actions = [
    ['initialization', '2023-01-01 00:00:00'],
    ['charge', '2023-01-01 00:00:10']
];
foreach ($actions as $action) {
    $messenger->dispatch(new PaymentEvent($action)));
}

Current implementation

Events are dispatched to message queue in order, but as SQS works, charge event can be processed before initialization event.
We are throwing exception because Payment does not already exists. Message is then retried by retry mechanism. Meanwhile initialization event is processed on different worker. charge is retried, Payment already exists. Everything is good. Payment is in correct state.

Problem

This is not recommended behavior. Exception should not be used to control application.
Moreover we can not distinguish between events that really failed and events that failed because of Payment creating takes too long.

Observed solutions but very complex

I have studied some algorithms for achieving partial ordering in distributed systems such as: Lamport timestamp, Paxos, Raft

If I understand them correctly, workers must somehow communicate between each other. Should we use Redis, MySQL or any other persistent storage, that can be accessed by all of the workers?

We are using PHP and I didn't find any examples or libraries with implementation to use. It looks like it is very complex problem and it is not worth it. Especially if we can use retry mechanism.

We do not want to use FIFO queue because of lower performance.

Another solution we are trying

We are currently trying to use process managers to address that problem. With them we can save event to something like buffer and when expected message is received and processed we go to processing another event in buffer.

It starting to come very complex and must be tailored to every domain we modeling.

Question

1. Do you think retry mechanism is good enough?
2. Is there any less complex solution that can be used in general?
3. Is there any of algorithm mentioned above suitable for our technological stack?

Two thoughts:

• If you only need a partial (vs. a total) ordering, then it's likely you can have as many FIFO queues as needed (up to the number of partitions of possible events such that no two events in different partitions have an ordering requirement) and direct events to the appropriate queue based on the ordering requirements of that event.
• Alternatively, you might be able to exploit some aspect of your domain to represent the not-yet-seen event. For instance, a charge event for a given payment if seen before the initialization event, can result in a state that's basically "this payment hasn't been initialized but has been charged".