System Design Interview: Design a Service Discovery System

Problem and Scope

Design an internal service discovery system for 2,000 logical services and 100,000 dynamic instances across 3 regions. Container rescheduling, autoscaling, and rolling deployments continuously change addresses. One large deployment may replace 10,000 endpoints in 2 minutes. Callers use several languages, so every team cannot be expected to maintain a sophisticated discovery SDK.

The problem separates two deadlines. After the control plane observes an instance's deliberate transition out of service, p99 from that observation to stopping new traffic is at most 3 seconds. If a process or node disappears without notice, hard-failure detection p99 is at most 15 seconds. Existing calls should continue from last-known endpoints during a 10-minute discovery control-plane outage. That does not imply that new instances become visible or cached instances remain alive during the outage.

The service count, instance count, region count, deployment size, and SLOs are interview assumptions. Scope includes registration, leases, health state, endpoint queries and incremental delivery, caching, draining, multi-region behavior, and verification. Request balancing is covered only where discovery needs it; business APIs, a complete service-mesh data plane, and public DNS are out of scope. This is system-design because the core task spans a control plane, proxies, health signals, and end-to-end traffic behavior.

What Interviewers Evaluate

The first signal is separating registration, discovery, health decisions, and routing. A registry records who claims to run where. Health logic decides whether an instance should receive traffic now. Discovery delivers candidates to the calling side. A proxy or client selects one candidate. Drawing all four as one database misses propagation latency and failure boundaries.

The second signal is control-plane and data-plane separation. If every business request synchronously queries the registry, a registry slowdown becomes a site-wide outage. A strong design keeps versioned snapshots in proxies and receives changes in the background. During a control-plane failure, the data plane uses its last-known set and handles stale endpoints with short connection timeouts, bounded retries, and passive local ejection.

The third signal is acknowledging that discovery information can always be stale. DNS TTLs, proxy caches, watch delay, failure detection, and rolling shutdown create windows. A strong answer defines which event starts each clock, assigns separate SLOs to deliberate withdrawal and hard failure, and budgets probe cadence, threshold, and propagation. “Strong consistency prevents calls to dead instances” ignores partitions and an instance failing immediately after a read.

Finally, the interviewer is looking for scale and operational judgment. If 100,000 instances renew a lease directly every 10 seconds, the registry receives 10,000 renewals per second before rollout changes and watch fanout. The design must contain write amplification, reconnect storms, full snapshots, regional failure domains, and bad health checks instead of merely naming Consul, etcd, or Kubernetes.

Questions to Clarify Before Answering

• What is the source of registration truth? If an orchestrator owns Pod lifecycle, a controller should produce registrations. A local agent with workload identity can register VMs or external processes. Allowing unauthenticated self-registration pollutes the catalog.
• When does the 3-second clock begin? Here it starts when the control plane accepts READY to DRAINING or not-ready. If an application freezes before reporting, hard-failure detection owns it.
• How many false removals can the 15-second target tolerate? Three consecutive failures reduce transient packet-loss errors, but a 5-second interval plus timeouts consumes nearly the whole budget. Passive error rates, regional spare capacity, and confirmation windows change the choice.
• Do callers need instance addresses or a stable service address? DNS plus platform load balancing is simplest for a stable VIP. A proxy or client discovery is more suitable when callers need version, region, or shard metadata.
• Does a control-plane outage fail open or closed? Ordinary internal services can continue from a last-known snapshot. Security revocation and hard isolation cannot depend on a stale discovery cache; an independent identity and authorization layer should deny them.
• Is automatic cross-region failover allowed? Stateless reads may fail over by policy. Data residency, single-writer state, or high cross-region cost must explicitly restrict the target set.

30-Second Answer

“I would build a regional control plane and local data plane. An orchestrator or authenticated agent writes instances to a sharded catalog with STARTING, READY, DRAINING, UNHEALTHY, and EXPIRED states. Only READY is routable. Graceful shutdown enters DRAINING before connections drain. A regional leader orders changes with monotonic revisions. A distribution tier pushes deltas to 5,000 node proxies, and a proxy fetches a full snapshot when it detects a revision gap.

Business requests use the local proxy or a stable VIP and never query the registry synchronously. During an outage, proxies retain the last snapshot and temporarily eject bad endpoints using connection timeouts, bounded retries, and passive errors. Health separates startup, readiness, liveness, and passive signals. Five-second active probes with three failures target roughly 15-second crash detection. I finish with fault injection for rollouts, partitions, broken watches, reconnect storms, and bad probes, measuring removal latency, stale requests, and convergence.”

Step-by-Step Deep Dive

Step 1: Define the data model and state machine

The catalog key includes at least namespace, service name, and port name so environments and protocols do not collide. An endpoint contains a stable instance ID, address, region, zone, version, weight, capability labels, state, lease expiry, and revision. Only predefined label dimensions are allowed; arbitrary high-cardinality data does not belong in the discovery plane.

A state machine carries more meaning than one healthy Boolean. STARTING receives no traffic. READY accepts new traffic. DRAINING stops new requests while existing connections finish. UNHEALTHY reflects an active or passive failure decision. EXPIRED means a lease was not renewed. Each transition records its reason, source, and monotonic revision so out-of-order updates are auditable.

Updates for one endpoint are deduplicated by instance ID and start generation. A delayed lease from an old process cannot resurrect an address already replaced. If the orchestrator is authoritative, a controller watches desired lifecycle and actual readiness. With self-registration, the writer authenticates as a workload and can modify only its own service and instance record.

Step 2: Choose a discovery pattern without copying complexity to every language

DNS plus a stable VIP works when callers only need a service name and the platform already handles endpoints and health. Returning instance addresses directly through DNS is simple, but TTL creates a tradeoff between query load and stale time. Clients that ignore a short TTL widen the risk.

Client-side discovery can select by version, zone, and load, but every language must implement watch handling, caching, balancing, retries, and safe upgrades. Because the problem has polyglot callers, prefer server-side discovery through a node-local or existing platform proxy. The application calls a stable local address, and the proxy owns the endpoint set and backend choice. One extra local hop buys uniform semantics and rapid upgrades.

If every workload already runs on Kubernetes, Service, DNS, and EndpointSlice usually cover basic discovery. Building another registry would duplicate the platform. Introduce a separate control plane only for a real cross-VM, cross-cluster, advanced routing, or policy requirement, and prefer consuming orchestrator endpoint truth.

Step 3: Order writes while allowing stale reads

Deploy 3 or 5 catalog replicas per region, using a consensus leader for registrations and state transitions. Shard by service key or tenant so one global leader does not own all 100,000 instances. Do not synchronously replicate every write across regions; a remote partition should not block healthy regions. The global layer synchronizes service policy and allowed failover destinations.

A successful write means the regional catalog accepted a revision. It does not mean every proxy has seen it. The distributor pushes ordered deltas. A proxy persists its last complete snapshot and revision. It applies a contiguous revision, but fetches a full snapshot for that service if it detects a gap, fails validation, or reconnects after delta retention has expired. Snapshot replacement is atomic so old and new halves never mix.

The read path exchanges bounded staleness for availability. A proxy records snapshot age, last control-plane contact, and watch lag. It alerts beyond the normal age budget but still uses the last set during the stated 10-minute outage. If every known endpoint fails, it returns an explicit no-backend result rather than silently bypassing policy into any region.

Step 4: Separate deliberate withdrawal from hard-failure detection

For graceful shutdown, the application first withdraws readiness. The catalog enters DRAINING, and proxies stop choosing that endpoint after propagation. The process waits through a maximum connection-drain period before exiting. The application also stops accepting new work because discovery propagation is not instantaneous; old proxies or long-lived connections can still hold its address.

A hard failure sends no signal. With active probes every 5 seconds and removal after 3 consecutive failures, a failure just after a successful probe may consume almost 15 seconds in sampling alone, before probe timeout and propagation. Meeting 15-second p99 requires budgeting timeout, scheduler jitter, and delivery together or shortening the interval. A proxy can temporarily eject an endpoint after connection refusal, timeout, or a high local error rate, but one caller's network problem must not globally deregister it.

Startup, readiness, and liveness are also distinct. Startup protects a slow initialization. Readiness failure stops traffic. Liveness failure triggers a restart. Putting a shared database in every instance's liveness test can restart the whole service during a database outage and amplify pressure. Critical dependencies may affect readiness, but checks need short timeouts, jitter, and capacity protection to avoid a probe storm.

Step 5: Calculate write, change, and fanout load

If 100,000 instances renew directly every 10 seconds, steady state is 10,000 renewals per second. Prefer an orchestrator watch over per-instance heartbeats, or aggregate renewals through node agents with randomized jitter. Lease expiry remains a safety net for abandoned records, not the normal withdrawal path.

Replacing 10,000 endpoints in 2 minutes averages about 83 additions and 83 removals per second, or roughly 167 membership changes. Sending every change independently to all 5,000 node proxies would create as many as about 835,000 deliveries per second. Real subscriptions filter to services each proxy needs, coalesce same-service changes over short windows, and use hierarchical distribution. Coalescing must not turn the 3-second withdrawal SLO into a one-minute batch.

Full snapshots need a budget too. At an illustrative serialized size of 256 bytes per endpoint, a global 100,000-endpoint snapshot is about 24.4 MiB. A normal proxy fetches only subscribed services, not the global catalog. Reconnect uses exponential backoff with jitter, and distributors retain a short delta log so 5,000 proxies do not request full snapshots simultaneously after recovery.

Step 6: Define region and security boundaries

An instance registers in its local region by default, and calls prefer READY endpoints in the same region and zone. If a regional catalog loses quorum, it rejects new writes while local proxies keep reading their caches. Another region must not mark those endpoints healthy or overwrite local truth based on a remote probe.

Service policy declares whether cross-region routing is allowed, read-only or writable behavior, target order, capacity limits, and data boundaries. Explicit policy triggers global failover. Stateless reads can switch quickly; a proxy for a single-writer database must first establish ownership transfer. Discovery returns candidate addresses and cannot replace a business consistency protocol.

Registration, deregistration, and watches require workload identity and least privilege, with catalog changes in an audit log. Proxies authenticate the control plane, and sensitive services can combine discovery with mutual TLS. Endpoint labels are not trusted authorization claims; callers still validate service identity and permission at connection or request time.

Step 7: Verify with timelines and fault injection

First test a rolling replacement. The old instance withdraws readiness. Record when the catalog accepts the revision, the proxy applies it, the last new request arrives, and the process exits. The new instance enters the set only after startup and readiness. Assert active-withdrawal propagation p99 below 3 seconds, completion of in-flight work, and zero traffic to not-ready instances.

Then kill a process without deregistration and verify that the 5-second probe, failure threshold, and distribution together meet 15-second p99. Inject one proxy network fault, a whole-node failure, lagging catalog followers, leader change, regional quorum loss, a delta gap, a corrupted snapshot, and a 10-minute control-plane outage. Recovery reconnects with jitter and causes no full-snapshot stampede.

Production metrics include registration and renewal rates, catalog write latency, READY count per service, health flapping, probe latency, watch lag, snapshot age, revision gaps, full-snapshot fallbacks, proxy reconnects, new requests to removed endpoints, stale-endpoint connection failures, and no-backend results. A traffic timeline proves propagation; a green control-plane dashboard alone does not.

Strong Sample Answer

“I separate registration truth, health decisions, discovery delivery, and request routing. A regional consensus group accepts authenticated instance changes. Each record has a service key, instance ID, start generation, address, region, version, state, lease, and revision. Only READY enters the routable set. Shutdown moves to DRAINING, stops new traffic, drains, then exits. Hard failures use probes and lease expiry. Passive errors eject locally and do not immediately become global truth.

Because callers are polyglot, I would not have every process watch the registry. Five thousand node proxies subscribe only to needed services, persist a full snapshot and monotonic revision, apply contiguous deltas, and refetch one service on a gap. Requests use the local proxy and never synchronously query the control plane. During a 10-minute outage, proxies use last-known endpoints with short connection timeouts, bounded retries, and local ejection. New instances are invisible and old addresses may be stale, so those costs are explicit metrics.

One hundred thousand instances renewing every 10 seconds would generate 10,000 writes per second, so I prefer the orchestrator watch or node aggregation. Replacing 10,000 endpoints in 2 minutes creates about 167 add and remove changes per second. Filter by subscription, coalesce briefly, and fan out hierarchically without consuming the 3-second withdrawal budget. Probing every 5 seconds and requiring 3 failures already approaches 15 seconds, so timeout and propagation are part of the budget.

I verify through the traffic timeline: no new requests within 3 seconds of an accepted withdrawal, and a hard-crashed endpoint leaves the candidate set within 15 seconds. Existing traffic continues during leader changes, a regional partition, and a 10-minute control-plane stop. Finally, 5,000 proxies reconnect with jitter, fill revision gaps, and converge without overwhelming the catalog.”

Common Mistakes

• Querying the registry before every request → control-plane delay or failure enters the business path → cache versioned endpoints locally and receive changes in the background.
• Using one healthy Boolean → startup, traffic admission, draining, and restart semantics collapse together → use an explicit state machine with transition sources.
• Restarting on readiness failure → a downstream outage can restart an entire service fleet → readiness removes traffic; liveness covers only unrecoverable local failure.
• Assuming a short DNS TTL eliminates stale data → client caches, propagation, and detection still create a window while query load rises → measure the TTL tradeoff and retain data-plane resilience.
• Allowing unauthenticated self-registration → mistaken or hostile endpoints can receive internal traffic → use orchestrator truth or constrained workload identity.
• Having every proxy subscribe to the global catalog → deployments and reconnects create fanout and snapshot storms → filter by service, distribute hierarchically, version deltas, and jitter reconnects.
• Strongly replicating every heartbeat across regions → remote latency or partition blocks healthy regions → order writes regionally and synchronize only policy and allowed failover metadata.
• Treating discovery success as request success → an endpoint can fail immediately after lookup → the call protocol still needs connection timeouts, bounded retries, circuit breaking, and idempotency.
• Checking every dependency for health → one shared outage removes all instances at once → check only critical traffic-admission conditions with short timeouts and jitter.

Follow-up Questions and Answers

Follow-up 1: Why not let all 100,000 instances use client-side discovery directly?

Client-side discovery removes a hop and enables detailed routing, but it copies watches, caches, revision repair, balancing, ejection, and upgrades into every language and process. With polyglot teams, node proxies reduce 100,000 client connections to about 5,000 data-plane instances. A single mature runtime with an extremely tight latency budget may justify a mandatory SDK, but it still needs protocol conformance tests and enforced upgrades.

Follow-up 2: Why is it safe to use old endpoints during a control-plane outage?

The last snapshot lets surviving instances continue, at the cost of missing additions, withdrawals, and failover changes. Proxies expose snapshot age, use short timeouts and passive errors to reduce calls to dead addresses, and cap retries. Security revocation must not wait for discovery-cache propagation; an independent identity and authorization layer fails closed. Once a service-specific maximum snapshot age expires, its policy can degrade or reject rather than applying one global rule.

Follow-up 3: Do 5-second probes and 3 failures really meet 15 seconds?

Not necessarily. A failure immediately after a successful check may use almost 15 seconds for three failed samples, and timeout, scheduling jitter, and endpoint propagation add more. To meet p99, shorten the interval, keep timeout below the interval, and use connection refusal or other passive signals for faster local ejection. Fault injection must measure the distribution from the last successful request to the last new route; multiplying configuration values is not proof.

Follow-up 4: Why does a rolling deployment need DRAINING instead of immediate deletion?

Deletion only stops callers that have seen the new list. It does not handle old caches, keep-alive, long RPCs, or queued work. DRAINING removes the endpoint from new-request candidates while the process remains for a bounded drain period. The application also stops accepting new work, and call timeouts fit within the platform termination grace. Verification tracks last new request, in-flight completion, and forced termination.

Follow-up 5: Should another region accept registrations when one region loses quorum?

It should not automatically take ownership of that region's instance truth. A cross-region view can mistake a partition for total instance failure, and two control planes may accept conflicting state. The region without quorum stops catalog writes while proxies read cache. The global layer routes new calls only according to declared service failover policy. On recovery, revisions and start generations reconcile state so an expired lease cannot overwrite a newer instance.