Date: 2026-06-05
Time: 13:21
chat-system/chat_system.pyThis file is a single-server, in-memory chat system implementing the core concepts you'd discuss in a "Design a Chat System" interview. It owns all messaging state — connections, conversations, message routing, presence, read receipts, and group management — in one ChatServer class. It's a pedagogical implementation: no network layer, no persistence, no sharding — just the domain logic that a real system like WhatsApp or Slack would distribute across many services.
Message — The central data unit. Carries both content and ordering metadata:
sequence_number: per-conversation monotonic counter for total order within a conversationlamport_timestamp: global logical clock for cross-conversation causal orderingedited / deleted: soft-state flags — deleted messages replace content with "[deleted]" rather than being removed from the listConversation — Container for an ordered message list plus participant set. The nextsequence counter is the source of truth for sequence number assignment. Serves both DMs and groups (distinguished by isgroup).
GroupInfo — Group metadata separated from the conversation itself. Tracks members, admins, creator_id. The membership set here is the authoritative one for permission checks; Conversation.participants mirrors it.
UserConnection — Per-user connection state with two queues: inbox (for online/away users) and offline_queue (buffered until reconnect). This models the fan-out delivery pattern where the server decides routing based on presence.
ChatServerThe monolith. Key index structures:
| Field | Type | Purpose |
|-------|------|---------|
| messages | dict[str, Message] | Global message lookup by ID — enables edit/delete/mark-read by ID |
| conversations | dict[str, Conversation] | All conversations keyed by computed or generated ID |
| readcursors | dict[tuple, int] | (userid, convid) → lastread_sequence — sequence-based, not message-ID-based |
| user_conversations | dict[str, set] | Reverse index: user → their conversation IDs |
| contacts | dict[str, set] | Bidirectional contact graph, built implicitly by messaging |
| lamport_clock | int | Single global Lamport counter incremented on every message send |
sendmessage — The DM path. Creates the conversation lazily on first message, assigns sequence + Lamport timestamps, delivers via deliver, auto-marks the sender's own message as read, and builds up the contact graph and conversation index as side effects.
sendgroupmessage — The group path. Validates sender membership, then fans out to all group members except the sender via _deliver.
deliver — The routing decision point. Online/away users get messages in their inbox; offline users get them in offlinequeue. This is the write-path analog of push vs. pull.
connect / disconnect — Manage presence transitions and flush the offline queue to inbox on reconnect. Both generate SYSTEM messages to the user's contacts — this is presence notification fan-out.
gethistory — Cursor-based pagination using bisect for O(log n) cursor lookup. Supports both forward and backward traversal. Returns (page, nextcursor) where next_cursor is None when exhausted.
Conversation ID as canonical key for DMs: dmconversation_id sorts the two user IDs lexicographically and produces "dm:{u1}:{u2}". This guarantees exactly one conversation per pair regardless of who messages first — a classic deduplication technique.
Lamport clocks for causal ordering: Every sendmessage and sendgroupmessage increments a global lamportclock. This gives a total order across all conversations on this server. In a distributed version, each server would maintain its own clock and merge on receipt.
Sequence numbers for per-conversation ordering: Independent from Lamport timestamps. Sequence numbers are scoped to a conversation and used for read cursors and pagination. This separation is deliberate — you want local dense ordering for pagination but global logical ordering for consistency.
Lazy resource creation: Conversations, connections, contacts, and conversation indices are all created on first use. There's no explicit "create DM" step — send_message handles it.
Soft deletes: delete_message sets deleted=True and overwrites content with "[deleted]" but keeps the message in the list. This preserves sequence number continuity and avoids holes in pagination.
Dual-queue delivery: The inbox / offline_queue split models the real-world pattern where a chat server buffers messages for disconnected clients and flushes them on reconnect, rather than requiring the client to poll.
Imports: All stdlib — uuid for message/group IDs, bisect for pagination cursor lookup, dataclasses for data models, enum for status/type enums, typing for Optional.
Imported by: testchatsystem.py — the test suite. No other modules depend on this; it's a self-contained implementation.
A typical message lifecycle:
1. Sender calls send_message → conversation created if needed → Lamport clock incremented → sequence number assigned → Message constructed and appended to conversation
2. deliver called for recipient → checks recipient's UserStatus → routes to inbox (online/away) or offlinequeue (offline)
3. Recipient reconnects (connect) → offline_queue flushed to inbox → presence notification sent to contacts
4. Recipient reads messages → calls markread with a message ID → server resolves to sequence number → updates readcursors
5. Unread count queried → getunreadcount computes lastseq - lastread — O(1)
For groups, step 2 fans out to all members except sender.
next_sequence counter.dmconversationid("alice", "bob") == dmconversationid("bob", "alice").markread has a msg.sequencenumber > current guard preventing regression.sendgroupmessage raises ValueError if the sender isn't a member.add_member enforces this limit.gettypingusers prunes stale entries.send_message adds both directions.Minimal and deliberate:
sendgroupmessage: raises ValueError if sender is not a group memberadd_member: raises ValueError if group has 500+ memberseditmessage / deletemessage: raise PermissionError if userid != senderidself.messages, self.groups, self.conversations: will raise KeyError — no defensive checks. The caller is expected to pass valid IDs.chat-system/testchatsystem.py — See what scenarios the tests cover: edge cases in pagination, offline delivery, group membership transitionschat-system/plan.md — Understand the design rationale and what tradeoffs were considered before implementationchat-system/chatsystem.py:gethistory — The cursor-based pagination logic has subtle edge cases around forward vs backward traversal and cursor position resolutionmessage-ordering-distributed — How this single-server Lamport clock approach would change with multiple servers (vector clocks, hybrid logical clocks, or server-assigned timestamps with tie-breaking)fan-out-on-write-vs-read — This implementation does fan-out-on-write (pushing to each member's queue); explore when fan-out-on-read (pull model) is preferable, especially for large groupschat-dm-conversation-dedup — DM conversations use a deterministic sorted-pair ID (dm:{min}:{max}) guaranteeing exactly one conversation per user pairchat-dual-ordering-scheme — Messages carry both per-conversation sequence numbers (for pagination/read-cursors) and global Lamport timestamps (for causal ordering), serving different purposeschat-offline-queue-flush-on-connect — When a user connects, their offline_queue is drained into inbox in FIFO order, preserving message arrival orderingchat-read-cursors-monotonic — mark_read only advances the read cursor; it silently ignores attempts to set a lower sequence numberchat-soft-delete-preserves-sequence — Deleted messages remain in the conversation list with deleted=True and content replaced, preserving sequence number continuity for pagination