[gunnarmorling]

> A more performant variation of this approach is the "hi/low" algorithm

I am discussing this approach, just not under that name:

> Gaps in the sequence are fine, hence it is possible to increment the persistent state of the sequence or counter in larger steps, and dispense the actual values from an in-memory copy.

In that model, a database sequence (e.g. fetched in 100 increments) represents the hi value, and local increments to the fetched sequence value are the low value.

However, unlike the log-based approach, this does not ensure monotonicity across multiple concurrent requests.

[AdieuToLogic]

> However, unlike the log-based approach, this does not ensure monotonicity across multiple concurrent requests.

Is this a functional requirement when a system is multi-process? Specifically, a single multi-threaded process could provide monotonic guarantees across all messages processed.

Once 2+ processes are introduced, it is impossible to guarantee monotonicity globally unless a SPoT (a.k.a. "queue") is used for delivery due to variations in message delivery times, performance of machines running each process, etc. An additional implication is there is no provable way to determine if a message received by process "A" logically precedes a message received by process "B" without authoritative information in the messages.

In short, an answer which generalizes the question:

  Can we get the space efficiency for consumers when using 
  monotonically increasing idempotency keys, without 
  hampering performance of multi-threaded producers?

Is to use the "hi/low" algorithm for both a single process multi-threaded solution, by only needing the process to allocate the "hi" value periodically and provide verifiable monotonic values, and also for multi-process (potentially multi-threaded as well) solutions, which ensures each process does not produce duplicate keys while providing a per-process partial ordering guarantee.