Appearance
Distributed Algorithms
42. What is consistent hashing, and where is it used?
The short answer
Consistent hashing spreads keys across servers so that adding or removing a server moves only a small share of the keys. With plain hash(key) % N, changing N from 3 to 4 moves about three quarters of all keys, which empties every cache at once. Consistent hashing places both servers and keys on a ring of hash values; each key belongs to the next server clockwise. Adding a server only takes keys from its neighbours, about 1/N of the total. Virtual nodes, many points per server, even out the load. It is used in cache clusters, DynamoDB, Cassandra, and load balancers with sticky routing.
ts
import { createHash } from 'node:crypto'
const h32 = (s: string) => createHash('md5').update(s).digest().readUInt32BE(0) // (1)
export class HashRing {
private ring: { point: number; node: string }[] = []
private vnodes: number
constructor(nodes: string[], vnodes = 100) {
this.vnodes = vnodes
nodes.forEach((n) => this.add(n))
}
add(node: string) {
for (let i = 0; i < this.vnodes; i++) this.ring.push({ point: h32(`${node}#${i}`), node }) // (2)
this.ring.sort((a, b) => a.point - b.point)
}
get(key: string): string {
const p = h32(key)
let lo = 0, hi = this.ring.length
while (lo < hi) { // (3)
const mid = (lo + hi) >> 1
if (this.ring[mid].point < p) lo = mid + 1; else hi = mid
}
return this.ring[lo % this.ring.length].node // (4)
}
}- A hash to a 32-bit number, so every key and node has a position on the ring. MD5 is fine here; it is used for spreading, not security.
- 100 virtual nodes per server, scattered around the ring, so each server owns many small arcs and load evens out.
- Binary search for the first ring point at or after the key's position.
- Wrap around to the first point if the key is past the last one.
The real result. With 10,000 keys on servers cache-a, cache-b and cache-c, adding cache-d moved 2,664 keys, about 27%, close to the ideal 25%. Using hash % 3 then hash % 4 instead moved 7,391 keys, about 74%.
43. What is a Bloom filter, and when can it be useful?
The short answer
A Bloom filter is a tiny, fast data structure that answers "have I possibly seen this item?" It can say "definitely not" or "probably yes": it never gives a false negative, but it can give a false positive at a rate you choose. It is a bit array plus several hash functions; adding an item sets a few bits, and checking an item tests those bits. It uses far less memory than storing the items. It is used to skip pointless expensive lookups: "is this username taken?" before querying the database, "is this URL already crawled?", and inside databases such as Cassandra to avoid reading files that cannot contain a key.
ts
import { createHash } from 'node:crypto'
export class BloomFilter {
private bits: Uint8Array
private m: number
private k: number
constructor(m: number, k: number) {
this.m = m // number of bits
this.k = k // number of hash functions
this.bits = new Uint8Array(Math.ceil(m / 8))
}
private positions(item: string): number[] {
const d = createHash('sha256').update(item).digest()
const a = d.readUInt32BE(0), b = d.readUInt32BE(4)
return Array.from({ length: this.k }, (_, i) => (a + i * b) % this.m) // (1)
}
add(item: string) {
for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7) // (2)
}
mightContain(item: string): boolean {
return this.positions(item).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0) // (3)
}
}- k bit positions from two hashes, a standard trick that behaves like k independent hash functions.
- Adding sets k bits.
p >> 3picks the byte andp & 7the bit inside it. - Checking needs all k bits set. Any zero bit means the item was definitely never added.
The real result. Sized for 100,000 items at a 1% false-positive rate, the filter needs about 958,506 bits and 7 hash functions, which is 117 KB. After adding 100,000 taken usernames, every one of them returned "probably yes", and checking 100,000 usernames that were never added gave 999 false positives, 0.999%. Storing the 100,000 names themselves would take megabytes.
Sizing, in words. For n items and a false-positive rate p, the number of bits is m = −n × ln(p) ÷ (ln 2)², and the best number of hash functions is k = (m ÷ n) × ln 2. For n = 100,000 and p = 0.01, that gives m ≈ 958,506 and k ≈ 7.
Limits: you cannot remove an item from a plain Bloom filter, because its bits may be shared with other items; a counting Bloom filter can. And it cannot list what it contains.
44. What are Snowflake-style distributed IDs?
The short answer
A Snowflake ID, a scheme Twitter introduced, is a 64-bit integer that many servers can generate independently, without coordination, that is still unique and roughly time-ordered. Its bits hold a timestamp in milliseconds since a custom epoch, 41 bits; a worker ID, 10 bits, unique per generator; and a sequence number, 12 bits, for IDs made in the same millisecond. That allows 4,096 IDs per millisecond per worker, sorting by ID roughly sorts by creation time, and the IDs fit in a database bigint. UUIDv7 follows the same idea in 128 bits.
ts
const EPOCH = 1735689600000n // 2025-01-01T00:00:00Z
export class Snowflake {
private seq = 0n
private last = -1n
private worker: bigint
constructor(worker: bigint) { this.worker = worker } // (1)
next(now = BigInt(Date.now())): bigint {
if (now === this.last) {
this.seq = (this.seq + 1n) & 4095n // (2)
if (this.seq === 0n) { while (BigInt(Date.now()) <= this.last) {} now = BigInt(Date.now()) } // (3)
} else {
this.seq = 0n
}
this.last = now
return ((now - EPOCH) << 22n) | (this.worker << 12n) | this.seq // (4)
}
}- Each generator gets a unique worker ID, from 0 to 1,023, from configuration or a coordination service.
- Same millisecond: increment the sequence, wrapping at 4,096.
- Sequence exhausted: wait for the next millisecond.
- Pack the three parts with bit shifts.
BigIntis needed because JavaScript numbers lose precision above 2 to the power 53.
The real result. Worker 7 generating two IDs at 2026-10-27T10:00:00Z produced 240776537702428672 and 240776537702428673. Decoding them gives the same timestamp and worker, with sequence 0 and 1.
Two traps. Send these IDs to browsers as strings, because JSON.parse turns large integers into imprecise numbers. And if a server's clock jumps backwards, a generator must refuse or wait, or it may repeat IDs.
45. What is leader election in a distributed system?
The short answer
Leader election is how a group of nodes agrees that exactly one of them is in charge of a job, such as running the nightly billing, being the database primary, or owning a Kafka partition, and quickly picks a new one if the leader dies. Nodes compete for a lease, a lock with an expiry, held in a strongly consistent store such as etcd, ZooKeeper, Consul or the Kubernetes API, and the holder keeps renewing it. If renewals stop, the lease expires and another node takes over. The danger is two nodes both believing they lead, which fencing tokens prevent (question 47).
Leader election with a Kubernetes Lease, the idea:
- Every replica tries to create or update the
Leaseobject namedbilling-leaderwith its own name and a renew time. - The Kubernetes API accepts only one update for each version of the object, so only one replica succeeds.
- The winner renews the lease every few seconds and runs the job.
- If the winner stops renewing, crashes or is cut off, others see the lease expire after, say, 15 seconds, and one of them takes over.
| Use | Leader does |
|---|---|
| Scheduled jobs across replicas | Runs the cron job once, not once per replica |
| Database clusters | Accepts writes as primary |
| Kafka and Raft groups | Coordinates replication for a partition |
| Controllers in Kubernetes | Acts on resources while the others stand by |
A simpler alternative for scheduled jobs: a database advisory lock, SELECT pg_try_advisory_lock(42), taken at the start of each run. Only one replica gets it.
46. What are consensus algorithms such as Raft and Paxos used for?
The short answer
Consensus algorithms let a group of nodes agree on a single sequence of decisions, such as the order of writes to a log, even when some nodes crash or messages are delayed, as long as a majority is working. Paxos, from Leslie Lamport, is the original and is famously hard to understand. Raft was designed to be easier: it elects a leader, the leader appends entries to its log and replicates them, and an entry counts as committed once a majority stores it. They power etcd, the store behind Kubernetes, ZooKeeper, Consul, CockroachDB, and Kafka's KRaft mode.
Why clusters have an odd number of nodes:
| Nodes | Majority needed | Failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
A fourth node adds cost and network traffic but tolerates no more failures than three. Five is the usual size for critical clusters.
You will rarely implement Raft. You will use systems built on it, so what matters in an interview is knowing that they need a majority, that a minority partition stops accepting writes, which is a CP choice (CAP), and that writes are slower than to a single node.
47. What are distributed locks, and what failure cases must be considered?
The short answer
A distributed lock lets processes on different machines agree that only one of them does something at a time, such as processing one customer's payout. The simple version is Redis SET lock:payout:42 <random-token> NX PX 30000: set the key only if absent, with a 30-second expiry. Failure cases are the real topic. The holder can pause, from garbage collection or a slow network, past the expiry while another process takes the lock; the lock store can fail over and forget the lock; and clocks drift. So keep the protected work short, release the lock only if you still own it, and use fencing tokens so the resource itself rejects a stale holder.
ts
import { randomUUID } from 'node:crypto'
export async function withLock<T>(name: string, ttlMs: number, work: () => Promise<T>): Promise<T | null> {
const token = randomUUID()
const ok = await redis.set(`lock:${name}`, token, { NX: true, PX: ttlMs }) // (1)
if (!ok) return null // (2)
try {
return await work()
} finally {
await redis.eval( // (3)
"if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end",
{ keys: [`lock:${name}`], arguments: [token] })
}
}- Take the lock only if nobody has it, with an automatic expiry so a crashed holder does not block forever.
- Someone else holds it: skip, or retry later.
- Release only your own lock. Without the check, a slow holder whose lock already expired would delete the next holder's lock. The Lua script makes check and delete atomic.
| Failure | Defence |
|---|---|
| Holder crashes | Expiry releases the lock |
| Holder pauses past the expiry | Fencing tokens checked by the resource; keep work short |
| Deleting another holder's lock | Release with a check of your own token |
| Lock store fails over and loses the key | A consensus-based store such as etcd for correctness-critical locks |
| Work longer than the expiry | Renew the lock while working, or redesign |
Ask whether you need a lock at all. A database row lock, SELECT … FOR UPDATE, a unique constraint, or an idempotent operation often does the job more safely (pessimistic locking).
48. How would you design a distributed rate limiter?
The short answer
Keep counters in a shared fast store, usually Redis, so every API instance counts against the same limit. Pick an algorithm: fixed window counters, simplest; sliding window, smoother; or token bucket, which allows short bursts at a steady average rate. Update atomically, with INCR and an expiry or a Lua script, so concurrent requests cannot both slip through. Key the limit by API key, user or IP, return 429 with Retry-After, put a coarse limit at the edge, and decide what happens if Redis is down, usually allowing traffic with a local fallback limit.
A token bucket in one atomic Lua script:
ts
const TOKEN_BUCKET = `
local tokens = tonumber(redis.call('HGET', KEYS[1], 't') or ARGV[1])
local last = tonumber(redis.call('HGET', KEYS[1], 'ts') or ARGV[3])
local refill = (tonumber(ARGV[3]) - last) / 1000 * tonumber(ARGV[2])
tokens = math.min(tonumber(ARGV[1]), tokens + refill)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call('HSET', KEYS[1], 't', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return allowed and 1 or 0`
export async function allow(apiKey: string, capacity = 20, perSecond = 5) {
const ok = await redis.eval(TOKEN_BUCKET, {
keys: [`rl:${apiKey}`],
arguments: [String(capacity), String(perSecond), String(Date.now())], // (1)
})
return ok === 1 // (2)
}- Capacity 20, refilling at 5 tokens a second. A client can burst 20 requests, then sustain 5 per second. The script refills based on the time since the last request, then spends one token.
- The whole read-refill-spend runs atomically inside Redis, so two instances can never spend the same token.
| Algorithm | Allows bursts | Precision | Storage per key |
|---|---|---|---|
| Fixed window | Up to double at the window boundary | Low | One counter |
| Sliding window log | No | Exact | One entry per request |
| Sliding window counter | Little | Good | Two counters |
| Token bucket | Yes, up to capacity | Good | Two numbers |
The single-service version, with express-rate-limit and a Redis store, is in the rate limiting question.
49. What trade-offs arise when choosing consistency and availability?
The short answer
Strong consistency means every read sees the latest write, which requires coordination: waiting for replicas, a majority, or a single leader. That costs latency on every write, and during a network partition some requests must fail. Choosing availability means always answering, from whichever copy is reachable, at the cost of stale reads and conflicting writes that must be merged later. The right answer is per operation, not per system: payments, stock and bookings need consistency; feeds, likes, carts and recommendations can be available and eventually consistent.
| Operation | Choose | Why |
|---|---|---|
| Charge a card, move money | Consistency | Doing it twice or wrongly is costly |
| Book the last seat | Consistency | Two people cannot both get it |
| Username uniqueness | Consistency | Must be decided once |
| Shopping cart contents | Availability | Merge two devices' carts later |
| Likes and view counts | Availability | Slightly wrong for a moment is fine |
| Product page | Availability | Serve a cached copy rather than an error |
Tools on each side:
| For consistency | For availability |
|---|---|
| Single-leader database, synchronous replication | Multi-region replicas, eventual reads |
| Transactions and row locks | Caches and stale-while-revalidate |
| Consensus stores such as etcd | Queues that accept writes and apply them later |
| Quorum reads and writes | Conflict resolution: last write wins, merge, or CRDTs |
CRDTs in one sentence. Conflict-free replicated data types are data structures, such as counters and sets, designed so that copies updated separately can always be merged into the same result, which is how collaborative editors and offline-first apps stay available (CAP).