Preventing Double‑Spend: Idempotency, Internal IDs, and the Discipline of State Before Side‑Effects

A challenge when building RESTful services is trusting the data sent from the client, especially if the service uses that data to make processing decisions.

The approach described in this article is to retain all such decision data at the server and only accept from the client an opaque and globally unique name that is not used directly in the service.

This is discussed with a payment service that is to transfer $1 million dollars. Due to time-outs, the client may retry its call. The requirement for the service is that when called many times for the same named transfer, the service must only send the funds a maximum of once. It is acceptable for the funds to not be sent, but the service must never double-spend.

A design that leads to a double-spend

Consider this RESTful service sketched in Python that would double-spend:

def payment(payload: PaymentPayload, request: Request):
    money_sent(payload.destination, payload.amount)

and the client:

def post_item():
    endpoint = "http://127.0.0.1:8000/payment"

    # send $1 million dollars to destination
    payload = {'amount': 10000000, 'destination': '00000000'}

    try:
        with httpx.Client(timeout=4.0) as client:
            response = client.post(endpoint, json=payload)
            response.raise_for_status()
            return response.json()
    except httpx.HTTPStatusError as exc:
        # Server returned 4xx or 5xx
    except httpx.RequestError as exc:
        # Network / timeout / connection error

The client calls client.post and if there are no issues, post returns with no error, no local exceptions are raised and the service has correctly sent the money to payload.destination.

But, in a distributed system, there are a number of factors outside the control of the code on both sides that might cause client.post to be called more than once.

The first call to client.post may timeout. As written, the client is prepared to wait four seconds before abandoning the call.

If the machine the service is running on is overloaded, the service will take longer to complete the call to payment and respond to the client. The four seconds might pass, the client times out, abandons the call to the service, and raises a local RequestError exception.

Even though the service is running slowly, it is operating perfectly well. The service could have called money_sent before the client abandoned the call.

The client cannot tell with 100% certainty how much of /payment was executed before the call was abandoned.

If client.post is called again, a double-spend can occur.

Idempotency

An idempotent operation is one that, when repeated, produces the same final state as if it were done once.

Marking an email as read is an idempotent operation. If the email is unread, marking it as read changes the state to read. If the email is marked as read, setting it to read does not alter the state so the same final state is produced.

By contrast, pressing "volume up" is not idempotent. Each press of the "volume up" button increases the volume; repeating the action changes the final state each time.

Not only are distributed systems characterised by partial failure, they are also characterised by partial information.

When a client receives a time-out, it cannot reliably tell if the remote operation was successfully applied or not. The only information available to the client is the timeout which is information about the invocation, not the state within the service.

If the client's strategy is to retry, it is possible the service is erroneously called twice for the same logical operation.

An idempotent design

To design a service that exhibits idempotent behaviour we must consider what the service should do so that the client repeating the request does not change the final state at the service.

We can view invoking a service a maximum of once as a state-machine-based logical invocation. Any retries as physical calls that advance the state of the logical call towards a maximum of one successful invocation.

To distinguish the logical call from the multiple physical calls the invocation should be named.

This design uses a version 4 UUID. The reason for this is that a version 4 UUID is generated at random (easy to do in a distributed system, no message exchange is required) and the chance of two UUIDs being the same is so small it can effectively be treated as zero. For the detail on this, read the What's in a name section.

The code

This is the implementation of the idempotent service and there are a number of points to note, plus one bug:

@app.post("/payment",  response_model = PaymentResponse)
async def payment(payload: PaymentPayload, request: Request):
    uuid = payload.uuid

    if uuid not in db:
        db[uuid] = f'{get_globally_unique_machine_id()}: \
                     {get_monotonically_increasing_value()}'

    st_key = db[uuid]

    exc_p = 0.1

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 1")

    if st_key in ps:
        if ps[st_key] == 'applied':
            return {'state': 'applied'}

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 2")

    success = money_sent(payload.amount)

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 3")

    if success:
        ps[st_key] = 'applied'
        return {'state': 'applied'}
    else:
        return {'state': 'failed'}

Points to note.

UUID not used directly in the service

The UUID provided from the client via the payload is not used as part of the idempotency logic. This is because the value is from the client and that data is not trusted.

A server local_machine_id:int identity is used which addresses a number of correctness, reliability, and security hazards.

1. Client‑input isolation

   A client‑generated UUID is untrusted input. If it was used directly as the key in ps, you allow the client to:

   • influence the storage layout
   • influence shard distribution
   • create hot partitions by skewing the UUID content
   • create denial‑of‑service patterns
   • reuse UUIDs that break idempotency

   By mapping the incoming UUID to local_machine_id:int, all internal state is isolated from client control.

2. Replay protection

   A mobile client might reuse a UUID accidentally when:

   • a payment is sent via the service
   • the mobile signal is dropped
   • the mobile operating system suspends the network stack
   • the mobile payment application resends the same request
   • the UUID is reused because the application did not generate a new one

   In the Python implementation above, a reused UUID always resolves to the same internal ID, and the state machine protects against double-spending.

3. Temporal ordering guarantees

   A UUIDv4 has no notion of ordering. It is just a series of random bits. The integer in local_machine_id:int does have ordering.

   Ordering gives:

   • monotonic progress (assuming the state the int is based on is not rewound)
   • safe "what happened around this time?" queries based on the monotonicity
   • safe recovery
   • safe replay
   • safe audit trails

   Using the UUID directly denies such ordering.

4. Shard‑safe distribution

   UUIDs are uniformly random. Random values do not work well with:

   • range‑based sharding
   • compaction
   • TTL sweeps
   • cold‑storage migration
   • locality‑aware caching

   As the int in local_machine_id:int is monotonically increasing, the combined value is ideal to achieve all of these.

5. Operational introspection

   Using local_machine_id:int supports these kinds of log inspections:

   • "Show me the last 10 000 operations on machine 7."
   • "What was happening around ID 8 400 000?"
   • "Which machine processed this payment?"

   UUIDs cannot answer any of these as they are just a series of random bits.

6. No client influence over internal state machine

   The code's internal state machine (ps) must be:

   • deterministic
   • monotonic
   • crash‑safe
   • replay‑safe

   If the client controls the key, they can:

   • force collisions
   • force pathological patterns
   • force replays
   • force state regressions

   Mapping the UUID prevents all of this.

   This is why it is generally a good idea to not trust any data from a client.

Simulated failure

For illustration, the code uses simulated failure:

    exc_p = 0.1

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 1")

The exception raised in the service is returned to the client as HTTP 500. The likelihood of the error occurring can be changed with exc_p.

The state-transition

Without the simulated failure, the service code is:

@app.post("/payment",  response_model = PaymentResponse)
async def payment(payload: PaymentPayload, request: Request):
    uuid = payload.uuid

    if uuid not in db:
        db[uuid] = f'{get_globally_unique_machine_id()}: \
                     {get_monotonically_increasing_value()}'

    st_key = db[uuid]

    exc_p = 0.1

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 1")

    if st_key in ps:
        if ps[st_key] == 'applied':
            return {'state': 'applied'}

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 2")

    success = money_sent(payload.amount)

    if random.random() < exc_p:
        raise HTTPException(status_code=500, detail="Simulated failure 3")

    if success:
        return {'state': 'applied'}
    else:
        return {'state': 'failed'}

In a production solution both db and ps must be backed by persistent storage and that storage must provide atomic update.

This is because, in a real system, there would be multiple /payment processes running. To provide the idempotency guarantee, updates to db and ps must be atomic so that all payment processes observe only a clean, before and after state, not an intermediate, partially updated value. Without atomicity, multiple /payment processes could not provide an idempotent service guarantee, as checks of db and ps may miss an update due to a lack of safe inspection of the persistent state.

Once ps[st_key] = 'applied' has completed, all processes --- including the current one --- have an atomically updated ps dictionary. Should the same UUID be presented to any /payments process, the check of st_key in ps will be successful, it will match 'applied' and idempotency will be guaranteed.

The client submitted UUID is extracted from the payload and discovered in db.

The local_machine_id:int value is set in db, and this value becomes the state key (st_key).

If that key is in the persistent store (ps), the value in the store is checked. If that value is 'applied', the service returns that value.

Note, this check is before the call to money_sent.

This check provides the idempotency guarantee. Given this design, for a given UUID, money_sent can only be called once.

If the call to money_sent was successful, the state transition is set to 'applied', and the service returns this value to the client so it knows a successful invocation has happened.

In the above implementation, the only state of interest is 'applied'. The state transition value can track other states but the one that enforces idempotency is 'applied'. Tracking others would be useful operationally but they are not required for correctness.

The bug

The money_sent logic is:

    success = money_sent(payload.amount, payload.destination)

    if success:
        ps[st_key] = 'applied'
        return {'state': 'applied'}
    else:
        return {'state': 'false'}

It is possible for the service to crash after successfully sending the money but before noting that with ps[st_key] = 'applied'

If this were to happen, the money has been sent but any retry, due to the service crash, would cause the money to be sent again as st_key would not be in ps. This would break idempotency.

This implication of this technical failure is that the payment processor would have to settle the over-payment for $1 million which might adversely affect the organization's reputation.

The solution

This prevents the double-spend in this case:

    ps[st_key] = 'applied'
    success = money_sent(payload.amount, payload.destination)

    if success:
        return {'state': 'applied'}
    else:
        return {'state': 'false'}

ps is updated before money_sent is called.

If money_sent is successful, this ordering is acceptable.

If the st_key is set to 'applied' and the service crashes before the money is sent, all other retries with the same UUID will not send any money.

This means no money would be sent. This is inconvenient for the person or organization making the payment but safe for the company offering the payment service.

This is the case where an invocation to an idempotent service is at most once. In this case, the call has not worked, and no subsequent retry will make it work.

Here the payment processor is erring on the side of caution, preferring to not pay (in case it was a mistake) on the understanding that this approach will be inconvenient and will require manual intervention to resolve.

This is a good engineering tradeoff as this situation only arises when the process crashes in a particular place, relative to ps being updated. Such a crash is likely to be rare.

If the process crashes before st_key is set to applied, no state has been updated and a retry will be required to make payment progress.

If the process crashes after the money has been sent but before the new state has been communicated back to the client, a retry from the client will have 'applied' returned after the check of ps reveals its st_key state is 'applied'.

If the service process crashed in this way on the final client retry, the client code would not know 'applied' had been reached and the money sent. In this case, a manual inspection of operational logs would be required.

The client code

The client code to try a maximum of six times is:

def post_item():
    url = "http://127.0.0.1:8000/payment"
    payload = {'uuid': str(uuid.uuid4()),
               'amount': 10000000,
               'destination': 00000000}

    for attempt in range(6):
        try:
            with httpx.Client(timeout=10.0) as client:
                response = client.post(url, json=payload)
                response.raise_for_status()

                if response.json()['state'] == 'failed':
                    print(f"Attempt {attempt + 1}: failed")
                else:
                    return response.json()

        except httpx.HTTPStatusError as exc:
            # Server returned 4xx or 5xx
            print(f"Attempt {attempt + 1}: "
                  f"HTTP error {exc.response.status_code} "
                  f"{response.json()['detail']}")
            if exc.response.status_code < 500:
                # 4xx error, client is wrong,m retry will not work
                raise
            # if error is 5xx, retry MAY work so go to next attempt

        except httpx.RequestError as exc:
            # Network / timeout / connection error
            print(f"Attempt {attempt + 1}: Request error {exc}")

    raise RuntimeError("All retries failed")

Note, after all six retries, post_item may fail to send the money. This is communicated by raising a RuntimeError.

If client.post does not have an issue, post_item will return response.json().

The type of response.json() is whatever is returned by the service. In this case, the Python type will be a dictionary (the service returns {'state': 'applied'}).

Therefore, the Python type returned by post_item is dict | RuntimeError.

If client.post executes correctly, the logic of the client can rely on the service having sent the money.

On a sixth retry, if the service marks the st_key as applied, and then crashes, the money will not have been sent and a manual intervention will be required. However, this case is likely to be rare relative to the number of successful money transfers.

The four possible outcomes

It can be helpful to consider what the number of outcome combinations there are when combining the client's point of view with what happens at the server.

Case 1 is the happy path, everything works.

Case 2 is the money has been sent, the service state is 'applied' but the client believes there has been a failure so a retry is initiated.

Case 3: the money has not been sent (money_sent returned False, the services state is not 'applied') and the HTTP succeeded but the response payload indicated an application-level money_sent failure. The client retries.

Case 4: the money has not been sent as in case 3, and the client detects a failure such as the underlying communication fails. The client retries.

Only Case 1, the happy path, does not lead to a retry. The logic in the service must correctly handle the other three combinations.

How long to retain the UUID in db?

The idempotency guarantee comes from having the UUIDs retained in db.

The values cannot be retained indefinitely as the memory requirement of the service would be unbounded. Its memory footprint would need to grow and grow to retain UUIDs that might need to be checked at some arbitrary future point.

When a failure occurs and the client retries, it is tempting to say that the UUIDs in db only need to be retained for a short amount of time, such as hours which is more than long enough to provide the necessary guarantees for client retries which would happen in a short amount of time, measured in tens of seconds.

However, for a payment processor, failed payments may be batched up, and resubmitted to the system on a schedule that far exceeds a short retry window. Resubmission may be days later.

In the subsection below on sizing the idempotent service, a peak rate of 200,000 payments per second is required to support the 9.6 billion payments made in 24 hours by Alibaba during its Singles Day in 2023.

For seven days of retention, this would require a persistent system with up to 2TB of storage with a UUID submission rate of 200,000 per second. This is an over-specification as the peak lasted only for 24 hours and 2 terabytes assumes the rate of 200,000 per second is sustained for a full seven days. More storage would be required for ps.

Two terabytes of cloud storage would cost approximately $600 per month.

If the rate remained the same but retention for 30 days was required, the cost would be $2,500.

Neither value is large enough to prohibit retaining that much data.

Conclusion

The lessons to be learned from this work are:

• An idempotent service requires server‑side naming and server‑side state
• Client UUIDs must never be used to drive service logic
• Using an internal ID isolates the service from client behaviour
• Atomic, persistent storage for both identity and state is mandatory
• Updating state before performing side effects ensures safety
• Retaining UUIDs is essential for replay protection and is operationally affordable
• UUIDv4 provides effectively unique names without coordination

What's in a name

To track a single logical invocation across multiple physical calls, a client must send a name to associate any retries with the same logical invocation.

This name is retained in the memory of the service and must be backed by persistent storage to protect against crash failure.

To ensure that a double-spend cannot occur via the payment service, each name presented must always be retained by the service.

Deleting a name at the service opens up the possibility that a client re-presenting that name at any point in the future could lead to a double-spend.

However, retaining every name at the service will eventually require massive amounts of storage. There are more efficient methods --- such as a Bloom Filter --- but such a lookup is probabilistic. If wrong, a double-spend might occur.

Another approach is to bound the number of names retained at the service.

Assume that the service will retain all names within the current calendar month. If the name presented by the client is prepended with the current month at the service, this would lead to a name guaranteed to be unique during a year. If a client presented the same name in the same month a year later, a double-spend could occur.

To prevent this, the client name should be prepended with day-month-year in the service, not just the month.

This guarantees a unique name within the service. This means the service does not need to retain any.

However, this design assumes that the date is never rolled back or reset.

State‑derived names are not globally unique, stable, and reproducible

The naming requirement is to start an arbitrary process and have it access a name from a stream of names where each one is unique to that process at that time, and that this name will not be available to any other process started at any point in the future within the same distributed system.

This requirement is an ideal. The stream would provide a distributed system-wide name to an arbitrary process without the need for any coordination or announcement about the use of that process. Such a stream would be convenient: a process is started, it accesses a system-wide name, and that name is guaranteed unique, with no chance of a clash, now and into the future. No other process will ever see that name.

If a name is based on state that can be reset, that name may be repeated.

Even the Trusted Platform Module can have its state reset when such a module is virtualized.

UUID version 1

Rather than the ideal, a universally unique identifier is a candidate for providing a name to be used with a service providing idempotent money transfers.

A version 1 UUID is based on state:

• 60 bits of timestamp (in 100-ns intervals since 1582)
• 4 bits for the UUID version (always 0001 for version 1)
• 14 bits of clock sequence
• 48 bits of node ID (usually based on the computer's MAC address)

The timestamps of version 1 of UUID have a 100-nanosecond resolution. If two UUIDs are generated within the same 100-ns interval, the timestamp is identical.

If the timestamp repeats or the clock goes backwards (based on a comparison with the last timestamp generated), or the node ID changes, the clock sequence is incremented. As the clock sequence is 2¹⁴ which is 16,384 different possibilities, if more than 16,384 version 1 UUIDs are generated within a 100-nanosecond window, a UUID collision becomes possible.

Therefore, uniqueness in UUID version 1 is bounded by the clock-sequence space.

For version 1 of UUID, rewinding the time breaks uniqueness.

Its uniqueness can also be broken by:

• Machine cloning
• Node-ID duplication

Cloning

Cloning breaks timestamp history, clock-sequence history and the node ID depending on what is cloned.

When a VM is cloned, the following is also cloned:

• the last timestamp used
• the last clock sequence
• the MAC address (unless a cloud platform randomises it)
• any virtual Trusted Platform Model state (if present)

Two VMs will now start with identical state and both will generate identical version 1 UUIDs due to cloned state.

Node-ID duplication

Node duplication means two machines share the same node ID. UUIDv1 assumes the node ID is globally unique. In practice, it is not.

MAC addresses can be reused by vendors or they can be duplicated in virtual network interface cards (NICs). Cloud providers (AWS, Azure, GCP) generate MAC addresses from predictable ranges. Two machines provided by different providers can have the same MAC. Docker-bridge-networks can assign identical MACs to containers across hosts.

Version 4 of UUID

Version 4 of UUID is a random-based, 128-bit identifier. It provides uniqueness guarantees without relying on state that might be repeated as in version 1.

In version 4, 4 bits are used to store the version (fixed to the binary 0100) and 2 to 3 bits are used to store a version variant field: the exact number of bits depends on the variant.

The remaining 121 or 122 bits are random.

In this naming scheme, there is no guarantee of uniqueness across processes. However, the chance of two processes generating the same UUIDv4 is 1 in 2 to the power of the random bit space, so 2¹²¹ or 2¹²².

2¹²¹ is approximately 2.66 x 10³⁶.

When drawing random values from a space of size \(N\), the probability of at least one collision reaches 50% when approximately \(\sqrt{N}\) have been drawn. This is known as the Birthday Paradox.

The square root of 2.66 x 10³⁶ is approximately 2.71 x 10¹⁸.

So a collision is likely 50% of the time when 2.71 x 10¹⁸ values have been drawn from the UUID version 4 space.

At 1 billion UUIDv4 values generated per second, it would take approximately 2.71 x 10¹⁸ / 10⁹ seconds for a 50% chance of a clash which is approximately 86 years. For a 1 in 10 chance, that figure is 39 years.

This assumes a system using UUIDv4 at a rate of 1 billion per second which is not realistic as it implies that many payments per second. This is an assumption that helps make a point about the size of the space.

A more realistic, real-world rate is up to approximately 10⁶ (1 million) for typical application code. Well-optimised service code might get to 10⁷ (fast random number generation, tight loops). Beyond that would require an architecture specially built for UUIDv4 generation: data vectorization based on Single Instruction, Multiple Data, and pre-allocated buffers with zero branching and zero system calls.

Why UUIDv4 is a good solution

Our ideal naming requirement was:

The requirement is to start an arbitrary process and have it access a name from a stream of names where each one is unique to that process at that time, and that this name will not be available to any other process started at any point in the future within the same distributed system.

The main reason UUIDv4 is a good solution is that an arbitrary process can access a name where each name is effectively unique.

There is a chance of a clash but it is so theoretically small, it can safely be treated as equivalent to zero. Therefore, each name is unique for all practical purposes.

UUIDv4 can be generated in isolation with no message exchange required. This makes it cheap to run in terms of computation and cheap in terms of infrastructure required: no message exchange is required.

The desire to have the name unique through all of time is an abstract, ideal requirement that does not require a practical implementation within an actual distributed system.

What happens in payments if there is a name clash?

Our idempotent payment service satisfies this invariant:

An idempotent operation is one that, when repeated, produces the same final state as if it were done once.

If two clients did generate the same UUIDv4 value, the first one to be processed in the payment system would be paid. The second one would go unpaid.

Even though in this case the two payments are two legitimately separate payments, the second one received by the payment service appears to be a retry of the first.

This assumes that the UUID is retained by the payment system for long enough that the duplicate from the second client can be detected. This requires retention of the UUIDs. This is discussed below.

If the second payment is denied, the payer is inconvenienced, but the denial of that transfer is safe for the organization handling the payment, and that organization would have to take manual steps to recover the situation to the satisfaction of their client.

How likely is such a repeat UUID?

Assume that the lifetime of the RESTful payment service is 30 years and that there are 100 processes generating UUIDv4 values at a rate of 10⁷ per process.

The space size for 121 bits is:

N = 2¹²¹ ≈ 2.66 x 10³⁶

The total rate of UUIDv4 generation is 10⁹ (100 * 10⁷).

The 30 year lifetime of the service in seconds is 9.46 × 10⁸.

At the above generation rate, in 30 years, the total number of UUIDs generated is:

n = 10⁹ × 9.46 × 10⁸ ≈ 9.46 × 10¹⁷

From the Birthday Paradox, the approximate probability of at least one collision is given by:

p ≈ 1 − 𝑒 ^{− \(\frac{n^{2}}{2N}\)}

Based on \(n\) and \(N\), calculating the exponent:

\(\displaystyle \frac{n^{2}}{2N}\) ≈ \(\displaystyle \frac{(9.46 \times 10^{17})^{2}}{2 \times 2.66 \times 10^{36}}\) ≈ \(\displaystyle \frac{8.95 \times 10^{35}}{5.32 \times 10^{36}}\) ≈ 0.168

\(\displaystyle p ≈ 1 - e^{0.168} ≈ 1 - 0.845 ≈ 0.155\)

With a UUIDv4 random space of 2¹²¹, over 30 years at 10⁹ UUID/s across 100 processes, the probability of at least one collision is roughly:

𝑝 ≈ 15.5%

A realistic payment rate

On an average day globally, Amazon Inc. customers place 15.25 million orders. This is 176 payments per second.

Taobao, Alibaba's 'instant commerce' portal reported passing 40 million daily orders within a month of launching.

Using 40 million per day as a minimum, across the whole of Alibaba which includes Taobao and other marketplaces, an estimate of the average daily number of orders is in the range 50 to 100 million.

Taking 100 million per day, this is 1,157 per second.

Alibaba’s marketplaces, including both Taobao and Tmall, have approximately 1 billion active consumers. During Alibaba's peak trading event, Singles Day in 2023, these marketplaces took 9.6 billion orders in a 24 hour period with 5% refunds. This is a once-per-year spike and, including refunds, is over 116,000 payments per second.

Sizing the idempotent service

Assuming an idempotent payment service that would persistently retain all version 4 UUIDs for seven days at a rate of 200,000 payments and UUIDs per second, the amount of storage required for the UUIDs is calculated as:

Total UUIDs \(= 200,000 \times 86,400 \times 7\)
Total UUIDs \(= 120,960,000,000\)

A UUID is 16 bytes in length so the total storage requirement, in bytes, is:

Total storage \(= 120,960,000,000 \times 16\)
Total storage \(= 1,935,360,000,000\) bytes

This is ≈ 1.9353 TB.

If we apply 3 times redundancy for this storage we require 5.8060 TB.

At US pricing of $0.1 per GB‑month, 1 TB‑month is $100 so 5.8060 TB is $580 per month.

This is the price for the storage required for a fully replicated, 7-day idempotency key store assuming a rate of 200,000 payments per second.

If retention was 30 days, the monthly cost would be no more than $2,500 per month.

These financial costs are not significant enough to affect the architecture and are quite within the budget of a payment processor capable of handling up to 200,000 payments per second. This price does not take into account what else would be necessary, such as the networking infrastructure.

Read next: An introduction to residual design
A residual design focuses on the present in a way that does not curtail the future.

Related Articles

• Retry Windows and the Limits of Idempotency
• The Myth of Complete Specifications
• Latency Is Architectural
• Agents Cannot Maintain Systems: The Additive‑Transformative Gap in LLM Software Delivery
• Vibe Coding Is Not Engineering