SD12.2 · LESSON 2 OF 6

A chat service

Produce an end-to-end design whose data paths, capacities and failure behavior satisfy explicit requirements.

THE IDEA

A chat service

"Sent" hides four different facts: the message was accepted, durably recorded, delivered to a device and read. Acknowledge the sender only after the durable write, give each message a sequence number per conversation so ordering is defined, and let a reconnecting client ask for everything after the last sequence it saw. Writing a frame to a socket proves none of the later states.

1. accepted2. durably recorded3. delivered4. read

client has seen up to sequence3

conversation log: seq 1…5 reconnect after 3: the server replays 2 message(s) (4, 5)

server writes to the durable log, THEN acknowledges: a crash cannot lose an acknowledged message ordering is defined per conversation by the sequence number; delivered and read are later, separate facts

Reconnect after different points; acknowledge too early.

Predict first. Does sending a network frame prove the recipient read the message?

Chapter context

A case study integrates choices into one coherent system. Start with a small requirement set, trace the important operations, calculate the dominant costs and stress the design with a failure before adding components.

TRY IT YOURSELF

Part 1. Do it hands-on

Count states and replays by hand, then build a conversation log with a state machine and replay.

1. accepted2. durably recorded3. delivered4. read

client has seen up to sequence3

conversation log: seq 1…5 reconnect after 3: the server replays 2 message(s) (4, 5)

message states messages replayed after seeing 3 of 5 messages lost by acking early a sent frame proves it was read? (yes/no)

To do: A chat message passes through accepted → durably recorded → delivered → read. How many distinct states is that?
To do: A conversation has messages with sequence numbers 1–5. A client reconnects having seen up to 3. Messages the server replays?
To do: The server tells the sender "accepted" BEFORE writing to durable storage and then crashes. Messages lost that the sender believes were accepted (one in flight)?
To do: Does sending a network frame prove the recipient read the message? Type yes or no

Part 2. Do it in code

STATES = ["accepted", "recorded", "delivered", "read"] (PROVIDED).
class Conversation: self.log is a list of messages {"seq", "text", "state"}. send(text): record the message DURABLY first (append to the log with the next seq starting at 1 and state "recorded"), and only then return the seq (the acknowledgement). ack_before_record(text) is the unsafe version: it returns a seq but appends nothing (simulating a crash before the write).
advance(seq): move the message one step along STATES (recorded → delivered → read); ValueError if it is already read or unknown. A message cannot skip a state.
since(last_seq): the messages with seq greater than last_seq, in order (a reconnecting client's replay).
state_of(seq): the current state.
unread_count(): messages whose state is not "read".

STATES = ["accepted", "recorded", "delivered", "read"]

class Conversation:
    def __init__(self):
        self.log = []

    def send(self, text):
        pass

    def ack_before_record(self, text):
        pass

    def advance(self, seq):
        pass

    def since(self, last_seq):
        pass

    def state_of(self, seq):
        pass

    def unread_count(self):
        pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does sending a network frame prove the recipient read the message?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For first-completion XP, define a unique logical event key such as (user_id, lesson_id, reward_version). Under a fixed reward r, $XP=r\times$ count(distinct eligible event keys). The deduplication record and awarded effect must share an atomic durable boundary in a real implementation.

Worked example

One hundred learners complete the same lesson, and every completion request is retried once. There are 200 deliveries but only 100 distinct learner-lesson events. At 20 XP per first completion, the correct total is 2000 XP, not 4000. The Python example models the invariant without pretending to implement distributed persistence.

Reference code

The following example uses the Python standard library and does not call a remote service.

deliveries=[]
for user in range(100):
    deliveries.extend([(user,'lesson-1','reward-v1')]*2)
unique=set(deliveries)
assert len(deliveries) == 200
assert len(unique) == 100
assert 20*len(unique) == 2000
assert 20*len(deliveries) == 4000

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A keyspace count does not prove collision freedom. Delivery and reading are different product events. Deduplication must cover both durable event identity and the actual effect.