Chat and Presence: Sequencing, Fan-Out, and Deep Dives

This lesson covers sections 4 to 6 of Chapter 11 and continues Chat and Presence: Framing, Scale Math, and Architecture.

4. Message Sequencing, The Three-Tick ACK Protocol & Production Schemas

To provide an intuitive, reliable user experience across unreliable mobile networks, the platform implements Monotonic Per-Conversation Sequencing and the Three-Tick Acknowledgment Protocol:

Figure 11.2: The Three-Tick Bidirectional ACK Protocol & Monotonic Sequencing

The Three-Tick Delivery State Machine

Every message transitions through three explicit acknowledgment barriers:

THE PROTOCOL SEQUENCE FLOW:

1. User A -> Server (Send): Client A sends { client_msg_id: "m-109", conv_id: 102, body: "Hello" } over WebSocket.
2. Server Commit & Tick 1: The Message Service commits the row to ScyllaDB, assigns seq_id = 402, and returns an immediate response: { client_msg_id: "m-109", seq_id: 402, status: "COMMITTED" }. Client A renders a Single Gray Tick.
3. Server -> User B (Dispatch): Server locates User B on Gateway 88 and streams the message down User B's socket.
4. User B -> Server (Delivery ACK & Tick 2): User B's device writes the record to its local SQLite database and automatically transmits an ACK: { conv_id: 102, delivered_seq_id: 402 }. Server relays this ACK to Gateway 142, and Client A renders a Double Gray Tick.
5. User B Opens Chat (Read ACK & Tick 3): User B taps the notification and views the chat. Client B transmits { conv_id: 102, read_up_to_seq: 402 }. Server relays the read receipt to Client A, rendering the Double Blue Tick.

Monotonic Conversation Sequencing & Gap Detection

Why do we sequence per conversation rather than globally?

A global sequencer across 50,000,000 users requires a single central coordinator, capping throughput to ~50,000 writes/sec and creating a single point of failure.

In reality, User A does not care if their message to User B was assigned an ID before or after a message sent between two strangers in Tokyo. Ordering is only meaningful within a single conversation.

ATOMIC PER-CONVERSATION SEQUENCE ASSIGNMENT:

Each conversation maintains a dedicated atomic counter in Redis:

seq_id = redis.call("INCR", "seq:conv:" .. conv_id)

(Backed up by Cassandra Lightweight Transactions / ScyllaDB Paxos for recovery).

CLIENT-SIDE GAP DETECTION:

Because cellular UDP/TCP packets can arrive out of order during network handoffs:

1. Recipient receives seq_id = 401.
2. Next packet arrives with seq_id = 403!
3. The Recipient client detects a gap (402 is missing).
4. The client holds message 403 in a temporary memory buffer without rendering it to the screen.
5. Client issues an immediate sync query: GET /messages?conv_id=102&after=401&before=403.
6. Upon receiving 402, the client renders 401 -> 402 -> 403 in perfect conversational order, completely eliminating transcript inversion!

Production Database Schemas (ScyllaDB CQL & PostgreSQL DDL)

1. SCYLLADB / CASSANDRA WIDE-COLUMN MESSAGE STORE (CQL)

CREATE KEYSPACE chat_cluster WITH replication = {
  'class': 'NetworkTopologyStrategy',
  'us-east': 3,
  'eu-west': 3
};

CREATE TABLE chat_cluster.messages (
  conversation_id uuid,
  bucket_month text,       -- Format: 'YYYY-MM' (Prevents unbounded partition bloat)
  sequence_id bigint,
  message_id uuid,
  sender_id uuid,
  payload_ciphertext blob, -- E2E encrypted ciphertext
  encryption_header blob,  -- Ephemeral public keys and IV
  created_at timestamp,
  PRIMARY KEY ((conversation_id, bucket_month), sequence_id)
) WITH CLUSTERING ORDER BY (sequence_id ASC)
  AND compaction = {
    'class': 'TimeWindowCompactionStrategy',
    'compaction_window_unit': 'DAYS',
    'compaction_window_size': 1
  };

2. POSTGRESQL RELATIONAL METADATA STORE (USERS & GROUPS)

CREATE TABLE conversations (
  conversation_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  conversation_type VARCHAR(16) NOT NULL DEFAULT 'DIRECT', -- 'DIRECT', 'GROUP', 'CHANNEL'
  title VARCHAR(128),
  created_by UUID NOT NULL,
  current_sequence_id BIGINT NOT NULL DEFAULT 0,
  created_at TIMESTAMP WITH TIME ZONE DEFAULT NOW()
);

CREATE TABLE conversation_participants (
  conversation_id UUID NOT NULL,
  user_id UUID NOT NULL,
  role VARCHAR(16) NOT NULL DEFAULT 'MEMBER', -- 'ADMIN', 'MEMBER'
  last_read_sequence_id BIGINT NOT NULL DEFAULT 0,
  joined_at TIMESTAMP WITH TIME ZONE DEFAULT NOW(),
  PRIMARY KEY (conversation_id, user_id)
);

5. Hybrid Group Fan-Out & Scoped Presence Engine

Group communication and presence updates represent the two primary sources of exponential traffic amplification in chat infrastructure:

Figure 11.3: Hybrid Group Fan-Out Threshold & The Scoped Presence Engine

The 256-Member Hybrid Fan-Out Threshold

The architecture selects between Fan-out on Write and Fan-out on Read based on group membership size:

1. SMALL GROUPS (< 256 MEMBERS - FAN-OUT ON WRITE):

When User A sends a message to a 5-person family group, the server writes 5 lightweight pointer rows into each participant's private inbox partition.

Why this wins: When a user opens their app, the client reads a single sequential partition (WHERE user_id = :me). Unread badge counts and conversation lists are computed instantly in O(1) time.

2. LARGE CHANNELS (> 256 MEMBERS - FAN-OUT ON READ):

In a 50,000-member community channel, writing 50,000 database rows per message is architectural suicide.

• The Strategy: The message is written exactly once to the channel's shared timeline partition (messages_by_channel).
• Gateway-Side Optimization: The dispatch router sends a single gRPC payload to each gateway node holding members of that channel. The gateway node fans out the payload in RAM directly across local socket descriptors, slashing inter-service network bandwidth by over 90%!

The Scoped Presence Architecture (Eliminating the 10-Billion Event Storm)

To prevent the catastrophic O(N * M) presence broadcast storm, Staff engineers divide presence into two distinct access models:

TIER 1: THE CONTACT SIDEBAR (LAZY PULL)

When User A opens their app, they see a list of 200 friends.

• The Rule: The server never broadcasts status changes to this list. Instead, the mobile client executes an asynchronous batch read from Redis: MGET presence:user_1 presence:user_2 ... presence:user_200
• Evaluated once on app launch in a single network roundtrip (<3ms in Redis).
• Status is rendered as static indicators (Green = Online, Gray = Offline).

TIER 2: ACTIVE 1-TO-1 CHAT SCREEN (SCOPED REAL-TIME PUB/SUB)

When User A actually taps on User B's name and enters the active chat screen:

• Client A subscribes to an ephemeral, short-lived Redis Pub/Sub channel: SUBSCRIBE presence:chat:conv_102
• User B's gateway publishes real-time typing indicators and online heartbeats strictly to presence:chat:conv_102.
• When User A navigates away from the screen, the client immediately sends UNSUBSCRIBE.
• Result: Network presence traffic drops from 10,000,000,000 events/sec down to under 20,000,000 events/sec—a 99.8% traffic reduction that keeps the entire platform stable!

6. Deep Dives

Deep Dive 1: Epoll Socket Memory Optimization & Kernel TCP Buffer Tuning

Hosting 100,000 persistent WebSockets per server requires tuning Linux kernel networking subsystems to bypass default memory limits.

THE KERNEL TCP TUNING PROFILE (/ETC/SYSCTL.CONF):

# Maximum open file descriptors across the OS
fs.file-max = 2097152

# Increase maximum network socket listen backlog
net.core.somaxconn = 65535

# Restrict default TCP read/write buffer allocations (Min, Default, Max)
# Allocates 4 KB default read buffer and 4 KB default write buffer
net.ipv4.tcp_rmem = 4096 4096 16384
net.ipv4.tcp_wmem = 4096 4096 16384

# Enable rapid reuse of TIME_WAIT sockets for outgoing connections
net.ipv4.tcp_tw_reuse = 1

# Reduce TCP keep-alive interval to detect broken cellular connections
net.ipv4.tcp_keepalive_time = 60
net.ipv4.tcp_keepalive_intvl = 10
net.ipv4.tcp_keepalive_probes = 3

The Go / Netpoll Runtime Advantage: Traditional Java frameworks allocate one operating system thread per connection, capping concurrency at ~10,000 threads. By leveraging non-blocking Epoll runtimes (Go Goroutines or Java Netty NIO), 100,000 idle sockets consume less than 250 active OS worker threads, maintaining near-zero CPU idle thrashing.

Deep Dive 2: End-to-End Encryption (E2E) Architecture & The Five Product Sacrifices

Implementing End-to-End Encryption using the Signal Protocol (Double Ratchet Algorithm) creates mathematical privacy guarantees while permanently eliminating five major server-side product capabilities.

HOW THE DOUBLE RATCHET PROTOCOL WORKS:

1. Pre-Key Bundles: Each user generates and publishes a collection of cryptographic public keys to the server: an Identity Key, a Signed Pre-Key, and 100 One-Time Pre-Keys.
2. Session Initialization (X3DH): When User A initiates a chat with User B, A fetches B's Pre-Key bundle from the server, performs an Extended Triple Diffie-Hellman (X3DH) exchange, and derives a shared master secret.
3. The Double Ratchet: For every single message transmitted:
   • The sending client ratchets its symmetric encryption key forward using an ephemeral Diffie-Hellman key exchange.
   • Even if an attacker steals a user's phone and extracts the current encryption key, they cannot decrypt historical messages (Forward Secrecy), nor can they decrypt future messages once the user sends a new message (Post-Compromise Security).

THE FIVE CAPABILITIES PERMANENTLY ELIMINATED BY E2E:

1. Server-Side Full-Text Search: The server stores opaque binary ciphertext blobs. It cannot build an inverted index. Search must run entirely on-device using SQLite FTS5.
2. Spam & Abuse Proactive Detection: The server cannot scan message text for phishing links or hate speech before delivery. Abuse detection must rely on user-initiated reporting.
3. Automated Content Moderation: CSAM and illegal content scanning cannot run in server pipelines.
4. Seamless Multi-Device History Sync: A new phone does not possess the historical ratchet keys. Decrypting old messages requires device-to-device local Wi-Fi transfer or user-held encrypted cloud backup keys.
5. Lossless Cloud Backup: If a user forgets their master recovery passphrase, their chat history is permanently, mathematically unrecoverable.

Deep Dive 3: Offline Message Storage & Reconnection Delta Protocol

Mobile devices spend hours in subway tunnels, flight mode, or areas with poor cellular coverage. The system must guarantee reliable recovery upon reconnection.

THE RECONNECTION PROTOCOL:

1. User B's device reconnects to a WebSocket gateway after 4 hours offline.

2. The Sync Handshake: Instead of asking the server for "all new messages", the client transmits a lightweight sync vector:

   {
     "action": "SYNC_CONVERSATIONS",
     "cursor_map": {
       "conv_102": 401,
       "conv_105": 8812,
       "conv_109": 32
     }
   }

3. The ScyllaDB Delta Slice Query: The server executes a fast slice query against ScyllaDB's clustering keys:

   SELECT * FROM messages
   WHERE conversation_id = :conv_id AND bucket_month = :month AND sequence_id > :last_seen
   LIMIT 100;

4. The server streams all missed messages back in a single compressed batch.

5. The client writes them to local storage, increments its sequence counter, and emits Delivery ACKs in a single bulk packet.

Deep Dive 4: Media Upload Pipeline & Ephemeral Presigned S3 Encrypted Uploads

Sending images, voice notes, and 4K videos directly over stateful WebSocket connections is an anti-pattern: a 50 MB video upload blocks the socket buffer and monopolizes gateway RAM.

THE OPTIMIZED MEDIA UPLOAD FLOW:

1. Client-Side Encryption: The sender compresses the video, generates a random 256-bit AES-GCM key, and encrypts the video locally on the device.
2. Presigned URL Request: Sender makes a lightweight REST call: POST /media/upload-ticket. The server returns an Amazon S3 presigned URL.
3. Direct-to-S3 Upload: The mobile client uploads the encrypted binary blob directly to S3 via HTTP PUT, bypassing chat gateway servers entirely.
4. Thumbnail Metadata Dispatch: Once S3 confirms upload, the sender transmits a standard 200-byte chat message over the WebSocket containing:
   • S3 Object URL.
   • SHA-256 Hash of ciphertext (for integrity).
   • Encrypted AES media key (encrypted via the Signal Ratchet).
   • Micro-thumbnail (a 16x16 blurred Base64 image rendered instantly in the chat bubble).
5. The recipient downloads the encrypted blob directly from S3 CDN and decrypts it locally in RAM.

Deep Dive 5: Ephemeral Typing Indicators, Debouncing & Disconnection Grace Windows

Typing indicators ("Alice is typing...") generate massive write volume with zero durability requirements. Storing typing events in a database is pure architectural waste.

THE EPHEMERAL PIPELINE:

1. Client-Side Debounce: When a user types, their mobile app captures keystrokes but enforces a 3-second debounce window. It emits at most one typing_started event every 3 seconds.
2. In-Memory Pub/Sub Relay: The gateway publishes the event to the active chat's Redis channel: presence:chat:<conv_id>.
3. Ephemeral In-Memory TTL: Typing events carry an automatic 5-second TTL. If the typing user stops or their app crashes, the recipient's UI automatically clears the typing indicator after 5 seconds without requiring an explicit typing_stopped packet.
4. Disconnection Grace Window: When a WebSocket TCP connection drops (e.g., cell tower handoff), the server does not immediately mark the user offline. It sets a 15-second reconnection grace timer in Redis. If the client reconnects within 15 seconds, user presence remains continuously "Online" to external observers, filtering out annoying presence flickering.

Deep Dive 6: Multi-Device Sync & Per-Device Encrypted Message Queues

In modern messaging, a single user account is bound to multiple active cryptographic endpoints (e.g., Primary Phone, Desktop App, Web Browser).

THE FAN-OUT PER DEVICE TOPOLOGY:

In an E2E encrypted system, a message cannot be encrypted once for a user; it must be encrypted separately for each of the user's active devices.

If User B has 3 registered devices:

1. Sender A fetches Pre-Key bundles for Device B1, B2, and B3.
2. Sender A produces three distinct encrypted ciphertext payloads: CB1, CB2, CB3, plus one for Sender A's own laptop CA2.
3. The server receives the envelope containing the multi-device ciphertexts and places them into individual Per-Device Outbox Queues.
4. Each device fetches its specific ciphertext, decrypts it with its unique local device key, and commits its local sequence pointer independently.

Deep Dive 7: Distributed Full-Text Search in E2E vs Plaintext Architectures

Search is one of the most heavily used features in chat applications. The underlying security model completely dictates the search architecture:

Deep Dive 8: Spam, Abuse & Content Moderation under E2E Zero-Knowledge Constraints

If a platform's servers cannot read message text, how does it detect spammers, scammers, and abusive content?

THE STAFF DEFENSE ARCHITECTURE:

1. Metadata Behavioral Profiling: While message content is hidden, metadata is visible: connection IP, registration velocity, account age, and outbound invitation velocity. If a newly registered account opens 500 new conversations with strangers in 10 minutes, the account is automatically flagged for rate limiting.
2. Client-Side Perceptual Hashing: For known malicious images (CSAM / virus signatures), the client app evaluates a cryptographic perceptual hash (PDQ / PhotoDNA) locally on the device against an encrypted on-device bloom filter before sending.
3. User-Initiated Decryption Reporting: When a user clicks "Report Spam" on a message:
   • The reporting user's client decrypts the last 5 messages in the conversation and submits the plaintext along with Apple/Google HMAC cryptographic verification signatures directly to the human trust-and-safety review queue.
   • This provides undeniable legal proof that the reported user emitted those specific words without breaking global end-to-end encryption!

Deep Dive 9: Distributed Read-Receipt Fan-Out & Monotonic Watermark Pointers

In a 150-member group chat, tracking read receipts naively is a catastrophic database bottleneck:

If each message contains an array of read_by_user_ids, every time any of the 149 members opens the app, the system executes an update mutation on that message row. For 100 messages read by 149 members, that generates 14,900 concurrent database updates on a single row!

THE STAFF WATERMARK ARCHITECTURE:

Rather than tracking read status per message, we track a Monotonic Watermark Pointer per Participant:

1. Each record in conversation_participants holds a single 64-bit integer: last_read_sequence_id.

2. When User B opens the group chat and reads up to sequence 402, the client sends a single lightweight payload:

   {
     "conversation_id": "conv_102",
     "last_read_sequence_id": 402
   }

3. The server executes a single O(1) update:

   UPDATE conversation_participants
   SET last_read_sequence_id = 402
   WHERE conversation_id = :conv_id AND user_id = :uid
   AND last_read_sequence_id < 402;

4. Instant Unread Count Derivation:

   Unread Messages = conversation.current_sequence_id - participant.last_read_sequence_id

5. Group Read Attribution ("Seen by Alice, Bob, and 12 others"): The client renders the "Seen By" list by querying:

   SELECT user_id FROM conversation_participants
   WHERE conversation_id = :conv_id AND last_read_sequence_id >= :target_seq_id;

6. This converts an intractable O(N * M) write-amplification nightmare into a clean, predictable O(1) scalar watermark update!