Section 7: The Same Millisecond - Deep Dive (Candidate-Driven)

Executive Summary: The interviewer hands you the wheel, and where you steer is scored. We go deep on three walls: the double-like race, where two people swiping at the same instant must produce exactly one match; the seen-set, where a 10.8 KB Bloom filter per user replaces 1.4 million point reads a second; and what happens after "It's a Match", where the hard part is authorization, not volume. Each dive lands as mechanism, number, trade-off.

The interviewer caps the marker: "Where would you like to go deeper?" Answer with a plan, not a wander:

"The deck gets its own pass next, so first three walls on the swipe path. The race, because our correctness invariant is exactly one match per mutually-liking pair and concurrency is where that breaks. The seen-set, because keeping swiped faces out of the deck is a requirement that would otherwise cost a point read per candidate. And the match fan-out, because that's where a block has to win within a second."

Dive One: The Double-Like Race

Section 6 walked the easy case: Marco liked Priya on Thursday, so when Priya swipes right on Sunday at 8:40 p.m., the check finds his like. Now the interviewer twists it: "What if Marco swipes right on her at the same millisecond?"

The naive design is check-then-write: read "did they like me?", find nothing, write my like. Run it for both at once. Each check finds nothing, because neither write has happened yet. Both write and both get match: null. Two people who like each other get zero matches, forever, and nothing in a naive design ever notices.

The fix is to flip the order: write-then-check (D2). Write my like at LOCAL_QUORUM and wait for the acknowledgement. Only then read the reverse like at LOCAL_QUORUM.

# Every *_quorum call is LOCAL_QUORUM: 2 of the 3 replicas
# in the region that owns the partition.
def like(swiper, target):
    # 0. Replay, conflict, or new?
    existing = read_quorum(swipes[swiper][target])
    if existing == PASS and not lapsed(existing):   # lapsed = older than 60 days
        return 409                                  # a recent pass can't flip
    if existing != LIKE:                            # new row: only these count
        if not like_cap.try_increment(swiper):
            return 429
    # existing == LIKE is a replay: rewrite (idempotent), rerun the check.

    # 1. Write first: both rows in one logged batch.
    try:
        write_quorum_logged_batch([
            swipes[swiper][target]         = LIKE,
            likes_received[target][swiper] = now,
        ], ttl=90d)                         # a timeout raises; the phone retries
    finally:
        # Published even if the batch timed out: the reconciler's input.
        kafka.publish("likes", key=pair_key(swiper, target))

    # 2. Only after the ack: did target already like swiper?
    if read_quorum(likes_received[swiper][target]) is None:
        return {"match": None}

    # 3. Same pair, same id. Create only if no row exists, active or
    #    unmatched, so a replay can never resurrect an unmatch.
    m = hash(min(swiper, target), max(swiper, target))
    row = read_quorum(matches[m])
    if row is None:
        upsert_quorum(matches[m] = {user_lo, user_hi, created_at})  # never writes unmatched_at
        upsert_quorum(matches_by_user, both users)
        kafka.publish("match-created", key=m)
    elif row.unmatched_at is not None:
        return {"match": None}
    return {"match": m}

Step 0 makes retries safe: a replay reruns the check without spending the cap again. The batch is acknowledged only after both rows reach quorum, so the overlap argument below applies to likes_received, the row the other side reads.

Here's the argument, and it's worth saying precisely. With RF 3, a LOCAL_QUORUM write lands on 2 of the owning region's 3 replicas, and a LOCAL_QUORUM read asks 2 of those same 3. Since 2 + 2 > 3, the two sets share at least one replica. So a quorum read that begins after a quorum write was acknowledged will see that write. That is the only guarantee we use. It says nothing about a write still in flight while the read runs. That read may or may not see it.

Now suppose both checks missed. Priya's read missed Marco's write, so her read must have started before his write was acknowledged. Marco's read missed hers, so the same holds the other way. Each side also waited for its own ack before reading. Chain those four facts in real time:

ack(W_Priya) < start(R_Priya) < ack(W_Marco) < start(R_Marco) < ack(W_Priya)

That's a cycle, which is impossible. So at least one side detects the match.

likes_received[X] is always written and read in X's home region. For a cross-region pair (Passport), the like's likes_received write goes to the target's home region: the cross-region round trip Section 11 prices.

Interviewer: "So Cassandra is linearizable here?"

You: "No, and I don't need it to be. QUORUM in Cassandra isn't linearizable. Concurrent operations can see each other in either order, and a write that times out can still land on one replica. All I rely on is the overlap guarantee for writes acknowledged before the read began, and the argument only ever uses that case."

Both sides can detect it, which is the reason for the deterministic match_id. If both find no matches row, both upserts write the same key, so they collapse into one row. Both match-created events carry the same id, and the notification service dedupes on it. The invariant holds both ways: never zero, never two.

The timed-out write is the gap the argument doesn't cover. Say Priya's write lands on one replica and the ack never comes back. Marco's read can miss it. The first backstop is the phone: a like that never got its answer stays queued and is retried with the same idempotent PUT, rerunning write-then-check. The async reconciler covers phones that never come back, which is why the like event goes to Kafka, keyed by pair, either way, so one consumer sees both likes of a pair in order. It re-reads both directions at quorum after a short delay, and again after the hinted-handoff window, because a single-replica write can stay invisible to quorum reads until repair. It creates any missing match using the same id, and only if no matches row exists, so racing the online path is harmless.

Flip trigger: a store that can't guarantee quorum overlap (eventually consistent reads only). Then use a single pair row updated atomically in a strongly consistent store, such as a DynamoDB conditional update or a Lua script in a durable Redis.

Critical Insight: The proof needs nothing stronger than "a read that starts after an ack sees it." Saying exactly that, and no more, is the Staff signal. Claiming linearizability is the trap.

Quick check before moving on: