Distributed Systems: Idempotency, Delivery Semantics và Gossip

At-Most-Once:
  Gửi 1 lần, không retry
  "Fire and forget"
  Có thể mất messages
  Use case: metrics, logs (mất 1 điểm không quan trọng)

At-Least-Once:
  Retry cho đến khi có ACK
  Có thể duplicate messages
  Consumer PHẢI idempotent!
  Use case: hầu hết messaging systems (Kafka default)

Exactly-Once:
  Mỗi message được xử lý đúng 1 lần
  Khó nhất để implement
  Use case: payments, inventory (không thể duplicate!)

Natural idempotency:
  PUT /users/1 { name: "Alice" }   ← idempotent (set to value)
  DELETE /users/1                   ← idempotent (already deleted → 404 ok)
  GET /users/1                      ← idempotent (read-only)

NOT naturally idempotent:
  POST /orders                      ← tạo order mới mỗi lần
  POST /payments                    ← charge mỗi lần
  PATCH /account { balance: +100 }  ← relative update

Making non-idempotent operations idempotent:

Approach 1 — Idempotency Key:
  Client generate UUID trước khi call
  POST /payments
  Idempotency-Key: 550e8400-e29b-41d4-a716-446655440000
  { amount: 100 }

  Server: check key exists → return cached response
  → Safe to retry!

Approach 2 — Conditional Requests:
  GET /orders/1 → ETag: "abc123"
  PUT /orders/1
  If-Match: "abc123"   ← chỉ update nếu vẫn là version này
  → 412 Precondition Failed nếu đã thay đổi

Approach 3 — Natural deduplication:
  "Set status='shipped'" idempotent
  "Increment shipment count" NOT idempotent → avoid

Database Schema:
  CREATE TABLE idempotency_keys (
    key           UUID PRIMARY KEY,
    request_hash  VARCHAR(64),    -- hash của request body
    status        ENUM('PROCESSING', 'COMPLETED', 'FAILED'),
    response_code INT,
    response_body TEXT,
    created_at    TIMESTAMP,
    expires_at    TIMESTAMP,      -- TTL: sau 24h có thể delete
    locked_at     TIMESTAMP       -- để detect stale PROCESSING
  );

Request flow:

  1. Extract Idempotency-Key từ header
     Validate format (UUID v4)
     Generate request_hash = SHA256(method + path + body)

  2. BEGIN TRANSACTION
     SELECT ... FROM idempotency_keys WHERE key=? FOR UPDATE
     (FOR UPDATE = pessimistic lock, ngăn concurrent same key)

  3. Nếu found:
     a. Status=COMPLETED: ROLLBACK, return cached response
     b. Status=FAILED: ROLLBACK, return cached error
     c. Status=PROCESSING + locked_at cũ (stale):
        → Update locked_at, COMMIT, retry operation
     d. Status=PROCESSING + locked_at mới:
        → ROLLBACK, return 409 Conflict "please retry later"

  4. Nếu not found:
     INSERT (key, hash, status=PROCESSING, locked_at=now)
     COMMIT (release lock trên table level)

  5. Execute business logic (ngoài transaction)
     (long-running operation không nên trong transaction)

  6. BEGIN TRANSACTION
     UPDATE status=COMPLETED, response_code=200, response_body=...
     COMMIT

  7. Return response

Mismatch detection:
  Nếu request_hash khác với stored:
  → Same key nhưng different request → 422 Unprocessable
  → Prevent accidental key reuse

Kafka Producer Idempotency:
  Producer config: enable.idempotence=true

  Producer ID (PID) + Sequence Number:
    Broker track (PID, sequence_number) per partition
    Duplicate = same PID + same sequence → discard

  Scope: single partition, single producer session
  (PID changes on restart → new "session")

Kafka Transactional Producer (Exactly-Once):
  Atomic write across multiple partitions:
    producer.beginTransaction()
    producer.send(topic1, record1)
    producer.send(topic2, record2)
    producer.commitTransaction()
    → All-or-nothing across partitions

  Consumer reads only committed messages:
    isolation.level = read_committed

Kafka Streams Exactly-Once:
  read-process-write loop:
    Read from input partition (track offset)
    Process (stateful)
    Write to output partition + commit offset
  → Transactional: atomic commit của (output write + offset commit)
  → "Effectively exactly-once" end-to-end

Giải pháp naive không work:

  Producer gửi message M
  Broker nhận M, process, nhưng ACK bị mất
  Producer timeout → retry → gửi M lần 2
  Broker nhận M lần 2 → duplicate!

  Giải pháp: deduplication at broker
  Broker nhớ message IDs đã xử lý → nếu duplicate → discard

  Nhưng: broker state không unlimited
  Phải có TTL → nếu retry sau TTL → không dedup được

Layers của exactly-once:
  Producer → Broker:     Idempotent producer (sequence numbers)
  Broker → Broker:       Replication (Raft/Paxos)
  Broker → Consumer:     Consumer track offset, manual commit
  Consumer → DB:         Idempotent writes (upsert, conditional update)
  End-to-end:            Transactional produce + consume

Single DB (easy case):
  Transaction = exactly-once built-in
  ACID guarantees: commit hoặc rollback, không partially applied

Distributed exactly-once:
  Saga + Idempotency:
    Mỗi step check idempotency key trước khi execute
    Saga orchestrator có thể retry safely
    
  Outbox + Idempotent consumers:
    Producer: write to outbox trong transaction (at-least-once publish)
    Consumer: idempotent processing → effectively exactly-once

  Trong thực tế: "exactly-once" often means:
    At-least-once delivery + Idempotent processing
    = Effectively exactly-once observable behavior

Cảm hứng từ rumor spreading trong xã hội:
  Mỗi node định kỳ chọn random neighbor
  Exchange information về cluster state
  → Thông tin lan rộng theo cấp số nhân

  Round 1: 1 node biết → 2 nodes biết
  Round 2: 2 nodes → 4 nodes
  Round 3: 4 nodes → 8 nodes
  Round k: 2^k nodes biết
  → Convergence trong O(log N) rounds

Cassandra — Gossip cho cluster membership:
  Mỗi node gossip mỗi 1 second với 1-3 random nodes
  Exchange: HeartbeatState (generation + version counter)
  Phát hiện failure: nếu không nhận update từ node X đủ lâu
    → Đánh dấu X là suspected dead
    → Dùng Phi Accrual Failure Detector (xác suất, không binary)

  Generation: tăng mỗi khi node restart (phân biệt restart vs slow)
  Version: tăng mỗi khi gossip state update

Amazon DynamoDB — Ring membership
Redis Cluster — Cluster bus (gossip port)
Consul — Memberlist library (SWIM protocol)

SWIM (Scalable Weakly-consistent Infection-style Membership):
  Cải tiến gossip với:
    Direct + indirect failure detection (tránh false positives)
    Piggybacking membership updates lên failure detection messages
    → Efficient: O(1) messages per node per detection period

Gossip:
  Eventual consistency (không guarantee khi converge)
  Không có global agreement
  Scalable: O(log N) convergence, O(1) per-node overhead
  Use case: cluster membership, failure detection, anti-entropy

Consensus (Raft/Paxos):
  Strong consistency (linearizable)
  Global agreement on value
  O(N) messages per proposal (broadcast)
  Use case: leader election, distributed locks, replicated state machine

Hybrid (nhiều systems):
  Gossip cho membership/discovery (scalable)
  Consensus cho critical decisions (correct)

  Cassandra: Gossip cho ring membership + Paxos cho lightweight transactions
  etcd: Raft cho everything (small clusters, consistency first)
  Kafka: ZooKeeper/KRaft cho controller, Gossip-like cho partition metadata