Secure Distributed Storage, Messaging, and Consistency

What's being tested

Candidates must show practical mastery of designing scalable, durable, and consistent distributed storage and messaging systems: partitioning, replication/consensus, durability vs latency tradeoffs, client-facing APIs, and multi-tenant operational concerns. Interviewers probe whether you can frame correctness constraints (ordering, delivery semantics, isolation), pick appropriate algorithms (consensus, MVCC, CAS), and justify tradeoffs for availability, performance, and cost in realistic failure modes. They also expect concrete engineering choices — data models, garbage collection, metadata placement, and how to observe and recover systems.

Core knowledge

• Partitioning (sharding): split data by key to scale throughput; choose consistent hashing or range partitioning depending on hot-key risk; each partition should be independently replicated and rebalanced.

• Replication & consensus: use leader-follower (e.g., Kafka) for high-throughput append logs or quorum consensus (RAFT, Paxos) for strong consistency; quorum = $\lfloor n/2\rfloor+1$ for n replicas.

• Durability & storage tiers: persist writes to WAL/append-only segments on local SSD, then tier cold objects to object stores (S3); segment sizes commonly 100MB–1GB for efficient compaction and recovery.

• Delivery semantics: clearly separate at-least-once, at-most-once, exactly-once; exactly-once typically requires idempotency + transactional writes (two-phase commit or idempotent producer with sequence numbers).

• Ordering & offsets: order guarantees usually per-partition; store consumer offsets in a durable, low-latency store (etcd/Zookeeper/internal offsets topic); allow manual/automatic offset management for replay.

• Deduplication & content-addressable storage: map content to hash-based IDs (e.g., SHA-256) for dedup; use reference counts or reachability GC; avoid counting race conditions with atomic CAS or distributed transactions.

• Large-payload handling: keep metadata in the log/queue and store large blobs in object store; pass pointers in messages to avoid broker memory spikes.

• Retention & compaction: support time/size-based retention and log compaction for latest-key semantics; compaction is CPU and IO heavy — plan background compaction windows and backpressure.

• Transactions & isolation: distributed transactions use coordinated commit (2PC) or transactional log with multi-writer epochs; prefer application-level idempotency or single-partition transactions to avoid cross-partition 2PC complexity.

• Authentication, authorization, encryption: require mutual TLS (mTLS) at the transport, RBAC for tenant isolation, and encryption-at-rest for sensitive blobs; keep token lifetimes short and log access-control decisions for audit.

• Monitoring & SLOs: instrument p99/p95 latency, throughput, tail-recovery time, replication lag, and GC pauses; SLOs drive choices: e.g., synchronous replication increases p99 but improves durability.

• Failure & recovery playbooks: design for fast leader failover, replica catch-up, and safe truncation; ensure metadata (topic list, partition assignment) is itself replicated and versioned.

Worked example — Design distributed message queue service

First 30s framing: ask about expected throughput, latency SLOs, message size distribution, ordering guarantees (global vs per-topic-partition), retention semantics, multi-tenancy, and exactly-once needs. Declare assumptions: per-partition ordering is OK, message sizes small (<1MB), throughput 100k msgs/sec per topic.

Skeleton pillars to present:

1. API model: Publish(topic, key, payload) and Subscribe(topic, partition) with consumer-group semantics and offset commit API.
2. Partitioning & routing: consistent hashing on key → partition to provide per-key ordering and balance.
3. Durability & persistence: append-only segmented logs on local disks, immediate fsync for durability when required, async replication.
4. Replication & failover: leader-follower per partition with RAFT-style majority for critical topics and configurable replication factor for others.
5. Consumer offset & delivery semantics: offsets stored durably; support at-least-once by default, exactly-once via idempotent producers + transactional commit for consumer offsets.

One concrete tradeoff: synchronous replication guarantees durability but increases end-to-end latency; offer topic-level policy to choose sync vs async replication. For large payloads, use pointers to external object store to prevent broker memory/IO explosion.

How to close: summarize SLOs and deployment assumptions, mention operational concerns (compaction windows, monitoring), and say "if I had more time I'd design the metadata service, simulate leader failover scenarios, and sketch client retry/backoff and quota enforcement."

A second angle — Design distributed transactions protocol

The same fundamentals (consensus, durable logs, coordination) apply but constraints shift: cross-shard atomicity demands a coordination protocol. For small-scale, prefer single-partition transactions to avoid distributed commit. For cross-partition, present coordinator-based 2PC built on a replicated log plus leader election; reduce blocking using optimistic concurrency control or cohort-prepared leasing and use timeouts and idempotent commit records to recover. Call out costly failure modes: coordinator crash leaves prepared state requiring careful GC. Tradeoffs: 2PC gives atomicity but sacrifices availability; consider sagas for looser consistency with compensating actions.

Common pitfalls

Pitfall: Designing for global total ordering by default. Total ordering across all keys kills scalability; prefer per-partition ordering and explain why the app actually needs global order.

Pitfall: Ignoring metadata scalability. Storing topic/partition metadata in a single node becomes a bottleneck; design metadata as a small replicated service and quantify limits (metadata ops/sec, number of partitions).

Pitfall: Over-promising exactly-once without implementation detail. Saying "we support exactly-once" without explaining idempotent producers, sequence numbers, and atomic offset commits will lose credibility; show the mechanism (transactional writes + offset commit).

Connections

Interviewers may pivot to adjacent topics like stream processing (stateful processing and time semantics), object storage design (cold-storage lifecycle and GC), or multi-region replication (geo-consistency models and conflict resolution). Be ready to discuss monitoring/playbooks and cost tradeoffs (e.g., hot-spot mitigation vs replication cost).

Further reading

• [Designing Data-Intensive Applications, Martin Kleppmann] — deep treatment of logs, replication, consensus, and transactions.

• The Kafka Papers & Confluent Blog — practical patterns for log-based messaging, partitioning, and storage tradeoffs.