4. Message Delivery and Processing

distributedsystem/books/think-distributed-systems

Idempotency

1. Core Concepts & Definitions

• System Model: A partially synchronous system with unreliable components communicating over an unreliable network.
  • Components can crash and recover, losing volatile memory but retaining durable memory.
  • Networks can reorder, drop, or duplicate messages.
  • Byzantine failures are excluded (components do not behave maliciously or deviate intentionally from their algorithms).
• Side Effect: A state change local to a specific concurrent component.
• Sender vs. Receiver: In a request-response dialogue, the sender submits the request, and the receiver processes it, performs a side effect, and returns a response.
• Delivery vs. Processing:
  • Message Delivery: The transfer of a message across the network and its presentation to the application layer.
  • Message Processing: The execution of application logic (which triggers side effects) and the generation of a response.

Delivery and Processing Categories

Category	Message Delivery (Receiver Side)	Message Processing (Receiver Side)
At-most-once	The network delivers the message 0 or 1 times.	The receiver processes the message 0 or 1 times.
At-least-once	The network delivers the message 1 or more times.	The receiver processes the message 1 or more times.
Exactly-once	The network delivers the message exactly 1 time.	The receiver processes the message exactly 1 time.

2. The Uncertainty Principle of Distributed Systems

A component has a limited local view (it only knows its own state and its channel to the network). This limited view forces a transition from certainty to uncertainty:

1. Before sending: The sender is certain that no work has occurred.
2. After sending, before response: The sender enters a state of uncertainty. If a timeout occurs, the sender cannot distinguish between:
   • The request being lost in transit.
   • The receiver crashing before processing the message.
   • The receiver crashing after processing the message
   • The response being lost in transit.
   • The network or the receiver being slow.
3. After receiving response: The sender is again certain of success or failure.

Why TCP Cannot Guarantee Application-Level Safety

While TCP is a reliable transport protocol using acknowledgments and retransmissions, it does not solve application-level message loss.

• TCP lives in the OS kernel and acknowledges receipt of data to its network buffer before passing it to the application layer.
• If the system crashes after the kernel acknowledges the message but before the application processes it, the message is permanently lost.
• Thus, TCP’s underlying at-least-once delivery transitions to an at-most-once guarantee at the application layer.

3. The Impossibility of “Exactly-Once” Processing

In an unreliable network with crash-recovery nodes, exactly-once message delivery or processing is physically impossible. The sender only has two real choices when a failure or delay occurs: move on (resulting in at-most-once semantics) or retry (resulting in at-least-once semantics).

Analysis of Common Implementation Failures

Attempting to track state naively on the receiver side to achieve exactly-once processing always fails:

Attempt A: Track Before Processing (Leads to At-Most-Once)

on message request do
    if request in received then return
    received := received + request   <-- Crash here loses the request forever
    process(request)
end

• Failure Scenario: If the receiver crashes after tracking the request but before executing process(request), the request is marked as processed but was never actually executed. A subsequent sender retry will be rejected.

Attempt B: Process Before Tracking (Leads to At-Least-Once)

on message request do
    if request in received then return response
    process(request)                 <-- Crash here processes again on retry
    received := received + request
end

• Failure Scenario: If the receiver crashes after executing process(request) but before tracking it in received, a retry will bypass the duplicate check and process the request a second time.

4. Exactly-Once Processing Semantics

Because physically processing a message exactly once is impossible due to retries, distributed systems aim for exactly-once processing semantics.

This means the system behaves as if the message was processed exactly once. Formally, this is defined by equivalence ($\equiv$) rather than strict equality ($=$):
$P(m)\equiv P(m)\cdot P(m)\cdot \cdots \cdot P(m)$

• Equivalence is application-specific: For example, duplicate entries in a debug log are technically unequal to a single entry, but from an application standpoint, they are equivalent. “Equivalence is in the eye of the beholder.”
• End-to-End Requirement: Achieving this requires at-least-once delivery (sender retries until acknowledged) combined with receiver-side deduplication.

5. Idempotence & Implementation Patterns

Idempotence is the mathematical property where applying an operation multiple times yields the same result as applying it once:
$f(f(x))=f(x)$

In distributed systems, if message processing is idempotent, at-least-once delivery guarantees exactly-once processing semantics.

Inherently Idempotent vs. Non-Idempotent Operations

• Inherently Idempotent: A write-once register starting at NULL. Setting it to X locks the value forever. Duplicate requests do not change the state.
• Non-Idempotent: Charging a credit card. Duplicate requests result in duplicate charges.

Key Implementation Patterns

1. Idempotency Keys (UUIDs)

The sender generates a universally unique identifier (UUID) for a request and attaches it to the initial call and all subsequent retries. The receiver deduplicates incoming requests using this key.

2. Transactional Deduplication (The “Outbox” or Receipt Table Pattern)

To safely track keys, the receiver must write the tracking state and the application side effects within the same atomic database transaction:

on message request do
    if request in received then
        return response
    end
    
    begin transaction
        process(request)                // Perform side effect (e.g., charge balance)
        received = received + request   // Record the idempotency key
    commit transaction                  // Atomically commit both or roll back both
    
    return response
end

Case Study Insight: Stripe vs. Airline App (UX Trade-offs)

• Stripe: Saves the HTTP status code and response body of the first request matching an idempotency key. Subsequent retries return that cached response, even if the first attempt returned an error.
• Airline Mobile App Failure: An airline app crashed repeatedly at checkout. The user retried 5 times, resulting in 5 pending credit card holds. While the airline engineers argued that only 1 charge would ultimately settle (satisfying their technical definition of exactly-once equivalence), this created a terrible user experience (UX) because the user observed multiple pending charges.
• Takeaway: When designing exactly-once processing semantics, consider both the technical state equivalence and the emotional state of the human user.