Message ordering guarantees in HLD - System Design Exercise

Design: Message Ordering Guarantee System

Design focuses on the messaging system's ordering guarantees and core architecture. It excludes detailed security, user interface, and persistence backup strategies.

Functional Requirements

FR1: Ensure messages sent between distributed components are received in the correct order.

FR2: Support multiple ordering guarantees: no ordering, per-producer ordering, global ordering.

FR3: Handle message loss and retries without breaking ordering guarantees.

FR4: Allow scalable message throughput with low latency.

FR5: Provide APIs for producers to send messages and consumers to receive messages in order.

Non-Functional Requirements

NFR1: System must handle up to 100,000 messages per second.

NFR2: End-to-end message delivery latency should be under 200ms for 99th percentile.

NFR3: Availability target of 99.9% uptime.

NFR4: Support horizontal scaling of producers and consumers.

NFR5: Ordering guarantees must be maintained even under failures and retries.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Message producers

Message brokers or queues

Partitions or shards for scaling

Message consumers

Ordering metadata (sequence numbers, timestamps)

Retry and dead-letter handling

Design Patterns

Partitioned queues with per-partition ordering

Sequence numbers for ordering enforcement

Idempotent message processing

Leader election for global ordering

Exactly-once or at-least-once delivery semantics

Reference Architecture

 +-------------+       +----------------+       +--------------+       +--------------+
 |  Producers  | ----> | Message Broker | ----> | Partitions   | ----> | Consumers    |
 +-------------+       +----------------+       +--------------+       +--------------+
                           |                        |                      |
                           |                        |                      |
                           +----> Ordering Metadata (sequence numbers) <----+

Notes:
- Producers send messages with sequence numbers per partition.
- Broker routes messages to partitions to maintain order.
- Consumers read from partitions in order.
- Retry and duplicate handling ensure ordering is preserved.

Components

Producers

Any client application or service

Send messages with ordering metadata (e.g., sequence numbers) to the broker.

Message Broker

Kafka, RabbitMQ, or custom queue system

Receive messages, assign them to partitions, and maintain order per partition.

Partitions

Logical or physical queues

Divide message stream to enable parallelism while preserving order within each partition.

Consumers

Client applications or services

Consume messages from partitions in order, process them reliably.

Ordering Metadata

Sequence numbers or timestamps

Track message order per producer or globally to enforce ordering guarantees.

Request Flow

1. Producer assigns a sequence number to each message per partition and sends it to the broker.

2. Broker receives messages and routes them to the correct partition based on key or producer ID.

3. Within each partition, messages are stored in the order received.

4. Consumers subscribe to partitions and receive messages in the exact order they were stored.

5. If a message fails processing, consumer retries or dead-letter handling ensures order is not broken.

6. Ordering metadata is used to detect missing or out-of-order messages and handle them appropriately.

Database Schema

Entities: - Message: {message_id (PK), partition_id, producer_id, sequence_number, payload, timestamp, status} - Partition: {partition_id (PK), broker_id} - Producer: {producer_id (PK), metadata} Relationships: - Each Message belongs to one Partition. - Each Message is produced by one Producer. - Sequence_number is unique per (producer_id, partition_id) pair to maintain order.

Scaling Discussion

Bottlenecks

Single partition can become a throughput bottleneck limiting parallelism.

Global ordering requires coordination, which can increase latency and reduce availability.

Message broker storage and network bandwidth can be overwhelmed at high message rates.

Consumer processing speed can limit end-to-end latency.

Solutions

Increase number of partitions to allow parallel processing and higher throughput.

Use partition keys to shard messages so ordering is guaranteed per partition, not globally.

Implement leader election and consensus protocols only when global ordering is strictly required.

Use efficient storage and replication strategies in the broker to handle load.

Scale consumers horizontally and implement backpressure to handle bursts.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Clarify types of ordering guarantees and their impact on design.

Explain partitioning strategy to balance ordering and scalability.

Describe how sequence numbers or metadata enforce order.

Discuss failure handling to maintain ordering guarantees.

Highlight trade-offs between global ordering and system performance.

Practice

1. Which message ordering guarantee ensures messages from the same sender arrive in the order they were sent?

easy

A. Random ordering

B. Total ordering

C. No ordering guarantee

D. FIFO (First In, First Out) ordering

Solution

1. Step 1: Understand FIFO ordering

   FIFO means messages from one sender arrive in the exact order they were sent.

2. Step 2: Compare with other options

   Total ordering orders all messages globally, not just per sender. No ordering or random ordering do not guarantee order.

3. Final Answer:

   FIFO (First In, First Out) ordering -> Option D

4. Quick Check:

   Per-sender order = FIFO [OK]

Hint: FIFO orders per sender, total orders globally [OK]

Common Mistakes:

• Confusing total ordering with per-sender ordering
• Thinking no ordering guarantees any order
• Assuming random ordering preserves send order

2. Which of the following is the correct way to describe total ordering in message systems?

easy

A. All messages from all senders are delivered in the same global order.

B. Messages from each sender arrive in order, but different senders' messages may be unordered.

C. Messages can arrive in any order without restrictions.

D. Messages are delivered in reverse order of sending.

Solution

1. Step 1: Define total ordering

   Total ordering means all messages, regardless of sender, are delivered in one global sequence.

2. Step 2: Eliminate incorrect options

   Messages from each sender arrive in order, but different senders' messages may be unordered. describes FIFO, C means no ordering, D is reverse order which is not standard.

3. Final Answer:

   All messages from all senders are delivered in the same global order. -> Option A

4. Quick Check:

   Total ordering = global sequence [OK]

Hint: Total ordering means one global message sequence [OK]

Common Mistakes:

• Mixing FIFO with total ordering
• Assuming messages can be unordered in total ordering
• Confusing reverse order with total order

3. Consider a messaging system where two senders, S1 and S2, send messages as follows:
S1: M1, M2
S2: N1, N2
If the system guarantees FIFO ordering only, which of the following sequences is possible at the receiver?

medium

A. [M2, M1, N1, N2]

B. [N1, M2, M1, N2]

C. [M1, N1, M2, N2]

D. [N2, N1, M1, M2]

Solution

1. Step 1: Understand FIFO per sender

   Messages from each sender must arrive in order: S1's M1 before M2, S2's N1 before N2.

2. Step 2: Check sequences for FIFO compliance

   [M1, N1, M2, N2] respects order for both senders. Options A, B, D break order for at least one sender.

3. Final Answer:

   [M1, N1, M2, N2] -> Option C

4. Quick Check:

   Sender order preserved = FIFO [OK]

Hint: Check each sender's message order only for FIFO [OK]

Common Mistakes:

• Mixing messages from different senders' order
• Assuming total order with FIFO guarantee
• Ignoring sender-specific order

4. A system claims to provide total ordering but sometimes delivers messages out of order. Which of the following is the most likely cause?

medium

A. Using FIFO queues per sender without global coordination

B. Messages are duplicated at the receiver

C. Messages are sent in parallel but processed sequentially

D. Network delays causing message reordering without coordination

Solution

1. Step 1: Understand total ordering requirements

   Total ordering requires global coordination to maintain one sequence for all messages.

2. Step 2: Identify cause of out-of-order delivery

   Using only FIFO per sender (no global coordination) can cause messages from different senders to arrive unordered, violating total order.

3. Final Answer:

   Using FIFO queues per sender without global coordination -> Option A

4. Quick Check:

   Total order needs global coordination [OK]

Hint: Total order needs global coordination, FIFO alone is insufficient [OK]

Common Mistakes:

• Blaming network delays without considering coordination
• Confusing message duplication with ordering
• Assuming parallel sending guarantees order

5. You are designing a chat application where message order is critical only per user, but global order is not required. Which message ordering guarantee should you choose to optimize for performance?

hard

A. Total ordering to ensure all messages are globally ordered

B. FIFO ordering per sender to maintain each user's message order

C. No ordering guarantee to maximize throughput

D. Random ordering to balance load

Solution

1. Step 1: Analyze application requirements

   Chat needs messages from each user in order, but no need for global order across users.

2. Step 2: Choose ordering guarantee for performance

   FIFO per sender meets the requirement and is more efficient than total ordering, which is costly.

3. Final Answer:

   FIFO ordering per sender to maintain each user's message order -> Option B

4. Quick Check:

   Per-user order only = FIFO [OK]

Hint: Choose FIFO if only per-sender order matters [OK]

Common Mistakes:

• Choosing total order unnecessarily, hurting performance
• Ignoring ordering needs and picking no guarantee
• Confusing random order with any guarantee