Scaling Fundamentals and Concepts Questions

Core concepts required to reason about scaling decisions and to communicate clear approaches. Topics include the difference between vertical and horizontal scaling and their trade offs; stateless versus stateful service design and why statelessness enables horizontal scaling; basic load balancing and request distribution strategies; when and how to apply caching replication and partitioning; simple autoscaling concepts and common metrics used to trigger scaling; how to identify common bottlenecks and apply pragmatic mitigations; and fundamental trade offs between latency throughput cost and complexity. This topic tests conceptual clarity and the ability to map requirements to simple scaling approaches.

MediumTechnical

60 practiced

Implement an LRU cache in Python with two methods: get(key) -> value or -1 if missing, and put(key, value). The cache should have a fixed capacity and guarantee O(1) get and put. Include a brief explanation of the data structures you used and why they achieve O(1).

Sample Answer

To implement an LRU cache with O(1) get and put, use a doubly linked list to track usage order (most recent at head, least at tail) and a hashmap (dict) to map keys to their nodes for O(1) access and updates. Moving a node to head or removing tail is O(1) with a doubly linked list.

python

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}  # key -> Node
        # dummy head/tail to simplify edge ops
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # unlink node
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _add_to_head(self, node):
        # insert right after head (most recent)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if not node:
            return -1
        # mark as recently used
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_to_head(node)
        else:
            if len(self.map) >= self.cap:
                # evict least recently used (tail.prev)
                lru = self.tail.prev
                self._remove(lru)
                del self.map[lru.key]
            new_node = Node(key, value)
            self.map[key] = new_node
            self._add_to_head(new_node)

Key points:- Hashmap gives O(1) lookup to node by key.- Doubly linked list allows O(1) insert/remove for moving nodes and evicting tail.Time Complexity: get O(1), put O(1). Space: O(capacity).Edge cases: capacity <= 0 (could raise), updating existing key, handling single-element cache.

Alternative: Python's collections.OrderedDict provides similar behavior with move_to_end for a shorter implementation.

EasyTechnical

68 practiced

Explain synchronous versus asynchronous replication for copies of data. Describe trade-offs in write latency, durability, and availability. Give two scenarios where synchronous replication is preferred and two where asynchronous replication is more practical.

MediumTechnical

65 practiced

Implement a token-bucket rate limiter in Java or Python with method allow_request(client_id) that returns true if the request is allowed. The limiter should support per-client limits and be safe for single-process use. Briefly explain how you'd extend it for a distributed environment.

Sample Answer

Approach: Use a token-bucket per client. Each bucket tracks capacity, refill rate (tokens per second), current tokens, and last refill timestamp. On allow_request, refill tokens based on elapsed time (capped at capacity) under a lock, then consume one token if available.

python

import time
import threading
from collections import defaultdict

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity            # max tokens
        self.refill_rate = refill_rate      # tokens per second
        self.tokens = capacity
        self.last = time.monotonic()
        self.lock = threading.Lock()

    def allow(self):
        with self.lock:
            now = time.monotonic()
            elapsed = now - self.last
            # add tokens, cap at capacity
            self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
            self.last = now
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

class RateLimiter:
    def __init__(self, default_capacity, default_refill_rate):
        self.default_capacity = default_capacity
        self.default_refill_rate = default_refill_rate
        self.buckets = defaultdict(lambda: TokenBucket(default_capacity, default_refill_rate))
        self.global_lock = threading.Lock()  # protects buckets dict

    def allow_request(self, client_id):
        # get or create bucket safely
        with self.global_lock:
            bucket = self.buckets[client_id]
        return bucket.allow()

Key points:- Per-client O(1) operations.- Thread-safe for single-process using locks.- Time complexity: O(1). Space: O(#clients).Edge cases:- Clock skew: use monotonic time (used).- Unbounded clients: consider eviction/LRU to avoid memory growth.- Burst behavior controlled by capacity.

Distributed extension (brief):- Use a central store like Redis with an atomic Lua script implementing token logic (read tokens, compute refill, consume, write back) to preserve atomicity across nodes.- Alternatively, shard clients across instances (consistent hashing) and run local buckets plus a fallback central quota. For high accuracy use Redis tokens; for eventual consistency and latency optimization use local buckets with periodic reconciliation.

EasyTechnical

61 practiced

Explain the difference between vertical (scale-up) and horizontal (scale-out) scaling. For each approach list the main benefits and trade-offs across capacity, fault-domain isolation, cost, operational complexity, and deployment downtime. Give concrete examples of when you would choose vertical scaling versus horizontal scaling for a web service.

Sample Answer

Vertical (scale-up) means increasing the capacity of a single machine (CPU, RAM, disk, faster NIC). Horizontal (scale-out) means adding more machines/instances behind a load balancer and distributing load.

Vertical scaling — benefits and trade-offs:- Capacity: Simple way to get more single-node throughput (e.g., bigger DB instance). Benefit: fewer distributed concerns. Trade-off: finite headroom and expensive at high-end.- Fault-domain isolation: Low — single node is single point of failure unless replicated.- Cost: Upfront/instance-cost rises non-linearly for high-end hardware or larger cloud instance types.- Operational complexity: Lower — fewer nodes to manage, simpler deployment and debugging.- Deployment downtime: Can require downtime for resize/reboot (though some clouds support live resize).

Horizontal scaling — benefits and trade-offs:- Capacity: Near-linear aggregate capacity by adding nodes; good for stateless web tiers and partitionable workloads.- Fault-domain isolation: High — node failures affect a subset only; easier to achieve high availability.- Cost: Can be more cost-efficient using many small instances; adds networking and coordination overhead.- Operational complexity: Higher — needs load balancing, service discovery, session management, data sharding/replication, consistency handling.- Deployment downtime: Lower — rolling updates enable zero-downtime deploys.

When to choose which:- Vertical: Single-node databases that are hard to partition (e.g., legacy monolith or an OLAP DB) or when simplicity and low operational overhead matter and expected scale fits one big machine.- Horizontal: Web frontend, stateless APIs, microservices, read replicas, and any workload needing high availability and elastic autoscaling (e.g., handling variable traffic spikes).

Concrete example: For a Node.js REST API that is stateless, choose horizontal scale-out behind an autoscaling group + LB. For a legacy PostgreSQL with complex JOINs and low write scale, start by scaling up (bigger instance) then add read replicas or sharding as needed.

MediumTechnical

74 practiced

You operate a caching tier that occasionally experiences 'hot key' spikes which overwhelm specific cache nodes. Propose at least five practical mitigations for hot keys including both short-term and long-term measures such as key hashing changes, request coalescing, pre-warming, and rate limiting.

Sample Answer

Here are practical mitigations (short- and long-term) for hot-key spikes, with rationale, implementation notes, and trade-offs:

1) Key partitioning / change hashing (long-term)- Use consistent hashing with virtual nodes or shard-by-key-prefix to spread one hot logical key across multiple cache slots (e.g., user:12345 -> user:12345:shardN where N = hash(timestamp)%k).- Trade-off: client/server must agree on partitioning; increases complexity for reads/writes and requires aggregation.

2) Request coalescing / single-flight (short-term)- On a cache miss, deduplicate concurrent backend fetches: first request triggers DB/API call, others wait for result cached.- Implementation: in-memory map of inflight keys with promise/futures. Reduces backend overload and thundering herd.

3) Local in-process cache + TTL jitter (short-term)- Add per-instance LRU cache with short TTL and randomized expiry to absorb spikes and avoid synchronized refreshes.- Trade-off: cache staleness window and memory per process.

4) Pre-warming and proactive refresh (medium-term)- Detect trending keys (analytics) and pre-populate cache before spikes (scheduled refresh or on change).- Use push to cache on writes to keep hot entries fresh.

5) Rate limiting and backpressure (short-term)- Apply per-key QPS limits at edge/load balancer; return degraded response or stale data when limit exceeded.- Combine with a “graceful degradation” policy (serve stale or lightweight fallback).

6) Tiered caching and adaptive TTLs (medium-term)- Promote very hot keys to a dedicated fast tier (in-memory on multiple nodes) or increase replication.- Reduce write amplification by using longer TTLs for stable hot objects; adapt TTL by observed access patterns.

7) Monitoring, autoscaling, and routing (operational)- Alert on per-key QPS and cache miss spikes; auto-scale cache nodes or route hot-key traffic to dedicated nodes.- Trade-off: cost and state migration complexity.

Example single-flight pseudo (concept):- inflight = map[key -> promise]- on request: if inflight[key] exists await promise else create promise, fetch backend, resolve promise, cache result, delete inflight[key].

Choosing a combination depends on RPO/RTO, staleness tolerance, and operational cost. Start with request coalescing + local cache + rate limits for immediate relief; plan partitioning/pre-warm and tiered caching for robust long-term fixes.

Unlock Full Question Bank

Get access to hundreds of Scaling Fundamentals and Concepts interview questions and detailed answers.

Join thousands of developers preparing for their dream job.