Skip to content
LLD Learn/Distributed & Large-Scale Modeling
Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Message Queues & Graph-Shaped Data

5 min read

You'll learn to

  • -Back a message queue with a table that counts attempts, schedules retries and has a dead-letter path
  • -Store a weighted graph as nodes and edges, and see why a recursive query needs a cycle guard
  • -Know where a relational graph stops being the right tool

This chapter covers two schema shapes that appear constantly in distributed systems: a durable message queue stored in a table, and a graph stored relationally. They are quite different problems from anything else in this module.

A Schema-Backed Message Queue

A message queue holds jobs waiting to be processed. An in-memory queue loses everything if the process crashes, so a durable queue lives in a table. Think of a post office. Letters wait in a tray. If delivery fails, the clerk tries again later. After enough failed tries, the letter goes into an undeliverable pile for a person to look at, so one bad letter does not block the whole office.

That is exactly the design: track each message's status and how many attempts have been made, and move a message that keeps failing to a dead-letter table for manual investigation. A message that fails 50 times in a row should not retry forever. This protects the system from a poison message, one that can never succeed.

A durable queue with retry tracking and a dead-letter path
CREATE TABLE message_queue (
    id INTEGER PRIMARY KEY,
    payload TEXT NOT NULL,
    status TEXT NOT NULL DEFAULT 'pending'
        CHECK (status IN ('pending', 'processing', 'completed', 'failed')),
    attempt_count INTEGER NOT NULL DEFAULT 0,
    max_attempts INTEGER NOT NULL DEFAULT 5,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    next_retry_at TIMESTAMP
);

CREATE TABLE dead_letter_queue (        -- messages that exhausted all retries
    id INTEGER PRIMARY KEY,
    original_message_id INTEGER NOT NULL,
    payload TEXT NOT NULL,
    failure_reason TEXT NOT NULL,
    moved_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);
-- application logic: on failure, increment attempt_count; if it now
-- exceeds max_attempts, move the row into dead_letter_queue instead of retrying again

The next_retry_at column supports exponential backoff, where each failure schedules the next retry further away, avoiding hammering a downstream system that is already struggling. The demo plays out the worst case. One poison message always fails. The limit is 5 attempts and the delays are 1, 2, 4 and 8 seconds.

Press Run: five attempts at t = 0, 1, 3, 7 and 15 seconds, then the dead-letter table

Graph-Shaped Data: Nodes and Edges

Think of a subway map: stations are nodes and the tracks between them are edges, each with a cost. A network of waypoints joined by routes that cost fuel is the same thing, and it maps onto two simple tables, the same shape as the self-referencing friend graph from the Intermediate Modeling module, with a weight added to each edge.

A weighted graph as nodes and edges
CREATE TABLE waypoints (id INTEGER PRIMARY KEY, name TEXT NOT NULL);

CREATE TABLE wormhole_routes (           -- edges, with a weight
    from_waypoint_id INTEGER NOT NULL REFERENCES waypoints(id),
    to_waypoint_id INTEGER NOT NULL REFERENCES waypoints(id),
    fuel_cost DECIMAL(8, 2) NOT NULL,
    PRIMARY KEY (from_waypoint_id, to_waypoint_id)
);

When a Recursive Query Is (and Is Not) the Right Tool

"Is there any path from A to B?" and "list every waypoint reachable within 3 hops" are questions a recursive query can answer directly. A recursive CTE (common table expression) is a query that refers to itself; this is the technique from the hierarchical-data chapter, now applied to a general graph, where a node can connect to many others, instead of a tree, where each node has one parent.

A recursive query finding all reachable waypoints, guarded against cycles
WITH RECURSIVE reachable AS (
    SELECT to_waypoint_id AS waypoint_id, fuel_cost AS total_cost,
           '/' || from_waypoint_id || '/' || to_waypoint_id || '/' AS visited_path
    FROM wormhole_routes WHERE from_waypoint_id = :start_id
    UNION ALL
    SELECT r.to_waypoint_id, reachable.total_cost + r.fuel_cost,
           reachable.visited_path || r.to_waypoint_id || '/'
    FROM wormhole_routes r
    JOIN reachable ON r.from_waypoint_id = reachable.waypoint_id
    WHERE reachable.visited_path NOT LIKE '%/' || r.to_waypoint_id || '/%'  -- stop before re-entering a visited waypoint
)
SELECT DISTINCT waypoint_id, MIN(total_cost) FROM reachable GROUP BY waypoint_id;

The visited_path column is not decoration. A tree has no cycles, but a route network can have one: A to B to C to A. Without a guard that refuses to re-enter a waypoint already on the current path, this query never ends, because UNION ALL does not remove duplicates, so each lap around the cycle adds new rows with an ever-larger cost.

The demo mirrors the query in Python. Routes cost 5, 3 and 2 around a loop A to B to C to A, with a side route from C to D costing 4. With the guard, the search ends and finds B at 5, C at 8 and D at 12. Without it, each extra lap adds 10, so the cost of reaching B would be 5, 15, 25, 35 and so on.

Press Run: the guard ends the search, and without it the cost would grow forever

One honest caveat: even with the guard, the minimum cost here covers only the paths the query explored, and is not a proven shortest path the way Dijkstra's algorithm guarantees. For true shortest paths on large or dense graphs, a recursive SQL query becomes impractical, and a graph database or an in-memory algorithm run outside the database is the better tool. A relational graph suits moderate sizes and reachability questions.

Naming that boundary shows the honest-scoping habit from the Phase 1 case studies: "a cycle-guarded recursive CTE handles reachability and simple path queries well; true shortest paths at scale would push me toward Dijkstra or a dedicated graph database."

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

Design the TARS Message Protocol and Wormhole Navigation schemas in the LLD Lab's Interstellar act.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!