4 ms·

Is guaranteed at-most-once delivery impossible?

by aaa667 12y ago

antirez 12y ago
Exctly-once is impossible. Example, you build all the system to be totally consistent and transactional (a CP system basically). Then you deliver the message to the client, and it dies without to report you if the message was acknowledged or not. You have two options: 1. Re-issue the message. If you do that, it is possible that the now crashed client already processed it, and you end with multiple delivery. 2. Drop the message. If you do that, the client maybe did not processed the message, and you end with no delivery.
- deleted 12y ago
  [deleted]
- avar 12y ago
  Exactly-once is possible in practice if you effectively bring the client under the umbrella of your transactions. E.g. you can (ab)use MySQL and other RDBMs to do something like: 1. Have a table where each row is a "job" or "message" and has a status which when enqueued is status = "unclaimed". You can also have a `last_changed` column. 2. Have workers consuming that table that GET_LOCK() a row and set status = "processing" and hold the lock for the duration of the processing. 3. When they're finished with the task they update status = "finished" and unlock the row (or equivalently, disconnect). This requires much tighter coupling between the queue and the queue consumer (each client must maintain a lock / connection for the duration of processing items). But it means that: * Nothing will ever pick up the item more than once due to the GET_LOCK(). * If the consumer dies the item is either just unlocked, or the status is "processing". You can as a matter of policy re-pick up "processing" with a `last_changed` in the distant past, alert on those items and manually inspect them. * If the consumer processes the item successfully it'll set the status to "finished" and nothing will process the item again. Now obviously this requires a lot more overhead & maintenance than what you have in mind, in particular it makes some of the failure cases be "the item is delayed due to a consumer dying and won't be processed until a human looks at whether it was actually finished". But this is the sort of pattern that you might use e.g. if you have a queue for sending out invoices. At work we use MySQL + https://metacpan.org/pod/Data::Consumer::MySQL https://metacpan.org/pod/Data::Consumer::MySQL to do this.
  - antirez 12y ago
    Even considering the client to be part of the distributed system in an "active" way, cooperating for the single delivery goal, the part I don't believe is reasonable is: "In particular it makes some of the failure cases be "the item is delayed due to a consumer dying and won't be processed until a human looks at whether it was actually finished". Moreover, what you describe here is more like: at most once delivery with delivered messages log so that non acknowledged entires can be inspected. I don't see how this really qualifies as exactly once. I guess exactly once must be , eventually, honored automatically even in the face of failures to qualify. Isn't it just better to use an at-least-once queue, (trans)actions-unique-IDs, and a CP store as the source of truth for the current state? So you turn all the sensible operations into idempotent ones.
    - avar 12y ago
      Right, you don't have to implement it like that, but the point is that the job is guaranteed to be in one of these states: * Hasn't been picked up yet * Has been picked up, and currently has something processing it (because the lock is still there) * Has been picked up, but whatever picked it up has gone away * It's finished Handling the jobs that haven't been picked up yet or are finished is easy. But what do you do about the jobs where the processor has simply gone away? Well, if they still hold the lock you can give them some more time, and if they don't hold the lock presumably they died. At that point you can decide how you want to handle that, do you just have something re-queue those jobs after some set amount of time has passed, or does someone manually look at the jobs and decide what to do? As an example of something we use this for: You might have some transactional E-Mails to be sent out, each recipient is a row in the queue table, you have to generate an E-Mail and pipe it to sendmail, just before you shell out to sendmail you mark the item as "processing", then you depending on the sendmail return value you either mark the item as processed in the queue or re-queue it. There's obviously a race condition here where sendmail might have returned OK to you but the DB server you're talking to blows up (so you can't set the status as "finished"). No amount of having unique IDs in external systems is going to help you because that'll just create the same problem. I.e. you have some state outside of your system that needs to be manipulated exactly once, and once that's done you'd like to mark the job as done. In practice once you get the things that can fail between "processing" and "finished" down to some trivial logic this sort of thing is really reliable as an "exactly once" queue. To the extent that it fails once in a blue moon you can usually just manually repair it, i.e. in this case see what your mail logs say about what mails you sent out. Redis obviously doesn't have the same strong storage guarantees as a disk-backed RDMBs, but we also have a version of exactly this logic that runs on top of Redis sentinel: https://metacpan.org/pod/Queue::Q::ReliableFIFO::Redis https://metacpan.org/pod/Queue::Q::ReliableFIFO::Redis It has the same queued/in-progress/finished queues using Redis lists, things are moved between the lists atomically and processed by workers, but of course if a worker crashes and burns at the wrong time you're stuck with some items in in-progress state and have to somehow figure out what to do with them. I.e. either you blindly re-queue them (at least once) or manually see whether they finished their work and re-queue them as appropriate (exactly once).
- lucian1900 12y ago
  That's not entirely true, since what you describe isn't a CP system. The client is a part of the system! It is possible to have the client be part of the consensus algorithm and guarantee exactly once delivery, but the latency gets quite high.
  - antirez 12y ago
    Are you assuming the client will eventually recover here? Or that clients are in general able to "lock" the resource before doing some work? Because otherwise, imagine a client may crash and will never recover again, and you have clients sending a beam of electrons in some device, without feedbacks about the beam output. Each client is a device that can send the beam. If the client will never restart again, even with all the cooperation and consensus, there is no way to know if the beam of electrons was generated or not.
tlrobinson 12y ago
"> /dev/null" is technically very bad "at most once"

Is guaranteed at-most-once delivery impossible?

by aaa667 12y ago

Is guaranteed at-most-once delivery impossible?

Exctly-once is impossible. Example, you build all the system to be totally consistent and transactional (a CP system basically). Then you deliver the message to the client, and it dies without to report you if the message was acknowledged or not. You have two options: 1. Re-issue the message. If you do that, it is possible that the now crashed client already processed it, and you end with multiple delivery. 2. Drop the message. If you do that, the client maybe did not processed the message, and you end with no delivery.

deleted 12y ago
[deleted]
avar 12y ago
Exactly-once is possible in practice if you effectively bring the client under the umbrella of your transactions. E.g. you can (ab)use MySQL and other RDBMs to do something like: 1. Have a table where each row is a "job" or "message" and has a status which when enqueued is status = "unclaimed". You can also have a `last_changed` column. 2. Have workers consuming that table that GET_LOCK() a row and set status = "processing" and hold the lock for the duration of the processing. 3. When they're finished with the task they update status = "finished" and unlock the row (or equivalently, disconnect). This requires much tighter coupling between the queue and the queue consumer (each client must maintain a lock / connection for the duration of processing items). But it means that: * Nothing will ever pick up the item more than once due to the GET_LOCK(). * If the consumer dies the item is either just unlocked, or the status is "processing". You can as a matter of policy re-pick up "processing" with a `last_changed` in the distant past, alert on those items and manually inspect them. * If the consumer processes the item successfully it'll set the status to "finished" and nothing will process the item again. Now obviously this requires a lot more overhead & maintenance than what you have in mind, in particular it makes some of the failure cases be "the item is delayed due to a consumer dying and won't be processed until a human looks at whether it was actually finished". But this is the sort of pattern that you might use e.g. if you have a queue for sending out invoices. At work we use MySQL + https://metacpan.org/pod/Data::Consumer::MySQL https://metacpan.org/pod/Data::Consumer::MySQL to do this.
- antirez 12y ago
  Even considering the client to be part of the distributed system in an "active" way, cooperating for the single delivery goal, the part I don't believe is reasonable is: "In particular it makes some of the failure cases be "the item is delayed due to a consumer dying and won't be processed until a human looks at whether it was actually finished". Moreover, what you describe here is more like: at most once delivery with delivered messages log so that non acknowledged entires can be inspected. I don't see how this really qualifies as exactly once. I guess exactly once must be , eventually, honored automatically even in the face of failures to qualify. Isn't it just better to use an at-least-once queue, (trans)actions-unique-IDs, and a CP store as the source of truth for the current state? So you turn all the sensible operations into idempotent ones.
  - avar 12y ago
    Right, you don't have to implement it like that, but the point is that the job is guaranteed to be in one of these states: * Hasn't been picked up yet * Has been picked up, and currently has something processing it (because the lock is still there) * Has been picked up, but whatever picked it up has gone away * It's finished Handling the jobs that haven't been picked up yet or are finished is easy. But what do you do about the jobs where the processor has simply gone away? Well, if they still hold the lock you can give them some more time, and if they don't hold the lock presumably they died. At that point you can decide how you want to handle that, do you just have something re-queue those jobs after some set amount of time has passed, or does someone manually look at the jobs and decide what to do? As an example of something we use this for: You might have some transactional E-Mails to be sent out, each recipient is a row in the queue table, you have to generate an E-Mail and pipe it to sendmail, just before you shell out to sendmail you mark the item as "processing", then you depending on the sendmail return value you either mark the item as processed in the queue or re-queue it. There's obviously a race condition here where sendmail might have returned OK to you but the DB server you're talking to blows up (so you can't set the status as "finished"). No amount of having unique IDs in external systems is going to help you because that'll just create the same problem. I.e. you have some state outside of your system that needs to be manipulated exactly once, and once that's done you'd like to mark the job as done. In practice once you get the things that can fail between "processing" and "finished" down to some trivial logic this sort of thing is really reliable as an "exactly once" queue. To the extent that it fails once in a blue moon you can usually just manually repair it, i.e. in this case see what your mail logs say about what mails you sent out. Redis obviously doesn't have the same strong storage guarantees as a disk-backed RDMBs, but we also have a version of exactly this logic that runs on top of Redis sentinel: https://metacpan.org/pod/Queue::Q::ReliableFIFO::Redis https://metacpan.org/pod/Queue::Q::ReliableFIFO::Redis It has the same queued/in-progress/finished queues using Redis lists, things are moved between the lists atomically and processed by workers, but of course if a worker crashes and burns at the wrong time you're stuck with some items in in-progress state and have to somehow figure out what to do with them. I.e. either you blindly re-queue them (at least once) or manually see whether they finished their work and re-queue them as appropriate (exactly once).
lucian1900 12y ago
That's not entirely true, since what you describe isn't a CP system. The client is a part of the system! It is possible to have the client be part of the consensus algorithm and guarantee exactly once delivery, but the latency gets quite high.
- antirez 12y ago
  Are you assuming the client will eventually recover here? Or that clients are in general able to "lock" the resource before doing some work? Because otherwise, imagine a client may crash and will never recover again, and you have clients sending a beam of electrons in some device, without feedbacks about the beam output. Each client is a device that can send the beam. If the client will never restart again, even with all the cooperation and consensus, there is no way to know if the beam of electrons was generated or not.

tlrobinson 12y ago

"> /dev/null" is technically very bad "at most once"