Message delivery guarantees in HLD - System Design Exercise

Design: Message Delivery Guarantee System

Design the core message delivery system focusing on delivery guarantees and reliability. Out of scope: client UI, advanced analytics, and message content processing.

Functional Requirements

FR1: Support three delivery guarantees: at-most-once, at-least-once, exactly-once

FR2: Allow clients to send and receive messages reliably

FR3: Handle message loss, duplication, and ordering issues

FR4: Provide APIs for sending and receiving messages

FR5: Support message persistence to avoid data loss

FR6: Allow scaling to handle 100,000 messages per second

FR7: Ensure p99 latency for message delivery under 200ms

Non-Functional Requirements

NFR1: System must be highly available with 99.9% uptime

NFR2: Support horizontal scaling for throughput

NFR3: Use standard protocols (e.g., REST, gRPC) for client communication

NFR4: Message storage must be durable and consistent

NFR5: Latency target: p99 < 200ms for message delivery

NFR6: Handle network failures gracefully

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Message broker or queue

Persistent storage for messages

Delivery tracking and acknowledgment system

Client API gateway

Retry and dead-letter queue mechanisms

Monitoring and alerting

Design Patterns

At-most-once, at-least-once, exactly-once delivery patterns

Idempotent message processing

Message deduplication

Two-phase commit or distributed transactions for exactly-once

Retry with exponential backoff

Event sourcing for message state

Reference Architecture

Client API Gateway
      |
      v
+------------------+       +---------------------+
|  Message Broker  |<----->| Persistent Storage  |
+------------------+       +---------------------+
      |                          |
      v                          v
+------------------+       +---------------------+
| Delivery Tracker |       | Dead-letter Queue   |
+------------------+       +---------------------+

Components

Client API Gateway

REST/gRPC server

Receives client requests to send and receive messages

Message Broker

Kafka/RabbitMQ or custom queue

Handles message queuing and delivery with support for delivery guarantees

Persistent Storage

Distributed database (e.g., Cassandra, PostgreSQL)

Stores messages durably to prevent data loss

Delivery Tracker

In-memory store with persistence (e.g., Redis + DB)

Tracks message delivery status and acknowledgments

Dead-letter Queue

Separate queue system

Stores messages that failed delivery after retries

Request Flow

1. Client sends message to API Gateway.

2. API Gateway validates and forwards message to Message Broker.

3. Message Broker stores message in Persistent Storage for durability.

4. Message Broker delivers message to consumer clients.

5. Consumer acknowledges message receipt to Delivery Tracker.

6. Delivery Tracker updates message status to prevent duplicates.

7. If delivery fails repeatedly, message moves to Dead-letter Queue.

8. For exactly-once, system uses idempotency keys and transactional updates.

Database Schema

Entities: - Message: id (PK), content, timestamp, status, delivery_attempts, idempotency_key - DeliveryStatus: message_id (FK), consumer_id, acknowledged (bool), timestamp - DeadLetter: message_id (FK), reason, timestamp Relationships: - One Message can have multiple DeliveryStatus entries (one per consumer) - DeadLetter references Message for failed deliveries

Scaling Discussion

Bottlenecks

Message Broker throughput limits under high load

Persistent Storage write/read latency

Delivery Tracker state size and update frequency

Network bandwidth for message delivery

Handling large numbers of consumer acknowledgments

Solutions

Partition Message Broker topics/queues to distribute load

Use scalable distributed databases with write optimization

Cache delivery status and batch updates to storage

Use compression and efficient protocols for network communication

Shard Delivery Tracker by consumer groups and use asynchronous processing

Interview Tips

Time: 10 minutes for requirements and clarifications, 15 minutes for architecture and data flow, 10 minutes for scaling discussion, 10 minutes for Q&A

Clarify delivery guarantee definitions and client expectations

Explain trade-offs between at-most-once, at-least-once, and exactly-once

Describe components and their roles clearly

Discuss how persistence and acknowledgments ensure reliability

Address scaling challenges and solutions thoughtfully

Mention failure handling and monitoring importance

Practice

1. Which message delivery guarantee ensures that a message is never delivered more than once, but some messages might be lost?

easy

A. Exactly once

B. At most once

C. At least once

D. None of the above

Solution

1. Step 1: Understand 'At most once' guarantee

   This guarantee means messages can be lost but never duplicated.

2. Step 2: Compare with other guarantees

   'At least once' may duplicate messages, 'Exactly once' avoids loss and duplication but is complex.

3. Final Answer:

   At most once -> Option B

4. Quick Check:

   At most once = no duplicates, possible loss [OK]

Hint: No duplicates but possible loss means 'At most once' [OK]

Common Mistakes:

• Confusing 'At most once' with 'At least once'
• Thinking 'Exactly once' is simple
• Assuming 'At most once' never loses messages

2. Which of the following is the correct description of the 'Exactly once' message delivery guarantee?

easy

A. Messages are delivered once without loss or duplication

B. Messages may be lost but never duplicated

C. Messages may be duplicated but never lost

D. Messages are delivered at least once, possibly duplicated

Solution

1. Step 1: Define 'Exactly once' guarantee

   This guarantee ensures each message is delivered once, no loss, no duplication.

2. Step 2: Eliminate other options

   'Messages may be lost but never duplicated' is 'At most once', 'Messages may be duplicated but never lost' and 'delivered at least once, possibly duplicated' describe 'At least once'.

3. Final Answer:

   Messages are delivered once without loss or duplication -> Option A

4. Quick Check:

   Exactly once = no loss, no duplicates [OK]

Hint: Exactly once means no loss and no duplicates [OK]

Common Mistakes:

• Mixing 'Exactly once' with 'At least once'
• Believing 'Exactly once' allows duplicates
• Confusing 'At most once' with 'Exactly once'

3. Consider a message queue system that uses 'At least once' delivery. If a message is sent and the receiver crashes before acknowledging, what is the likely outcome?

medium

A. The message is lost and never delivered

B. The message is delivered once without duplication

C. The message is delivered at most once

D. The message may be delivered multiple times

Solution

1. Step 1: Understand 'At least once' behavior on receiver crash

   If receiver crashes before ack, sender retries, causing possible duplicates.

2. Step 2: Analyze options

   The message is not lost but sender retries on no ack, so may be delivered multiple times to ensure at least once.

3. Final Answer:

   The message may be delivered multiple times -> Option D

4. Quick Check:

   At least once = possible duplicates [OK]

Hint: Receiver crash before ack causes duplicates in 'At least once' [OK]

Common Mistakes:

• Assuming message is lost on crash
• Confusing 'At least once' with 'At most once'
• Ignoring possibility of duplicates

4. A system claims to provide 'Exactly once' delivery but sometimes messages are duplicated. What is the most likely cause?

medium

A. The system uses 'At least once' delivery without deduplication

B. The system uses 'At most once' delivery internally

C. The system does not handle acknowledgments properly

D. The system drops messages on network failure

Solution

1. Step 1: Identify cause of duplicates in 'Exactly once'

   Duplicates usually happen if 'At least once' is used without deduplication.

2. Step 2: Evaluate other options

   'At most once' causes losses not duplicates, improper ack handling or dropping messages cause losses or retries but exactly once needs deduplication atop at least once.

3. Final Answer:

   The system uses 'At least once' delivery without deduplication -> Option A

4. Quick Check:

   Duplicates mean missing deduplication in 'At least once' [OK]

Hint: Duplicates in 'Exactly once' mean missing deduplication [OK]

Common Mistakes:

• Assuming 'At most once' causes duplicates
• Ignoring deduplication step
• Confusing message loss with duplication

5. You are designing a payment processing system that must never lose or duplicate transactions. Which message delivery guarantee should you choose and why?

hard

A. At most once, because it avoids duplicates

B. At least once, because it ensures no message loss

C. Exactly once, because it guarantees no loss and no duplicates

D. None, because message delivery guarantees are not relevant

Solution

1. Step 1: Identify system requirements

   Payment processing must avoid losing or duplicating transactions.

2. Step 2: Match guarantee to requirements

   'Exactly once' ensures messages are delivered once without loss or duplication, fitting the need.

3. Final Answer:

   Exactly once, because it guarantees no loss and no duplicates -> Option C

4. Quick Check:

   Payment systems need exactly once delivery [OK]

Hint: No loss or duplicates means choose 'Exactly once' [OK]

Common Mistakes:

• Choosing 'At most once' and risking loss
• Choosing 'At least once' and risking duplicates
• Ignoring delivery guarantees in critical systems