Scaling Strategies §

Key takeaways of this section:

1. Measure before scaling: profile a request’s wall-clock time and find the phase with the largest fraction — that phase is the bottleneck, and only speeding it up increases throughput.
2. IO-bound → faster storage (NVMe), more bandwidth, or Asynchrony to multiplex I/O on one thread; caching reduces I/O altogether.
3. Compute-bound → more cores (vertical), more machines (horizontal), or a lower-complexity algorithm — the highest-leverage fix.
4. Real workloads mix both, and in a multitier architecture each tier has its own bottleneck, so each tier is scaled independently.

Use profiling tools (perf, strace, APM tracing) to decompose a request’s wall-clock time. If 80% of request time is spent waiting on a database query, the system is IO-bound on the database. If 80% is spent in a CPU-intensive computation (e.g., image encoding), it is compute-bound. The bottleneck is the single resource that, if made faster, would increase overall throughput.

Solutions: faster storage (NVMe over SATA), more network bandwidth, or Asynchrony to multiplex many I/O operations on a single thread (event loop). A single event-loop thread can handle 100K concurrent connections because it is never blocked waiting for I/O. Caching (below) reduces I/O by serving repeated reads from memory.

A $O(n^2)$ algorithm on 1M items takes 10,000× longer than on 10K items; an $O(n \log n)$ algorithm takes only ~150× longer. Reducing algorithmic complexity is the highest-leverage optimization for compute-bound workloads. See Parallelism for how to partition compute-bound work across cores or machines.

When to scale up: the workload fits on one machine; the bottleneck is a single resource (e.g., CPU). A database with 100 GB of data and 10K QPS can run on a 64-core, 256 GB RAM machine.

When to scale out: the workload exceeds the maximum single-machine capacity; the bottleneck is distributed (e.g., network, disk I/O). A web server with 1M requests/second needs multiple machines.

Vertical scaling is linear in cost (a 2× machine costs 2×). The cost per request decreases with utilization: a half-loaded 64-core machine costs the same as a fully loaded one, so right-sizing (choosing the smallest instance that meets SLOs) directly reduces cost per request.

Cloud pricing: each additional instance is billed independently (per-second or per-hour). A 2× cluster costs exactly 2× in per-instance pricing. However, spot/preemptible instances (AWS Spot, GCP Preemptible) offer 60–90% discounts in exchange for possible interruption, making them suitable for stateless, horizontally-scaled workloads that can tolerate node loss.

On-premises: shared infrastructure (network switches, storage arrays, power, cooling) is amortized across nodes, so horizontal scaling can be sub-linear in cost. A 10-node cluster may cost less than 10× a single node because the switch and power budget are shared.

Right-sizing: monitor utilization and downscale when average utilization drops below ~40%. Over-provisioned instances waste budget without improving SLOs. Autoscaling (below) automates this.

Key takeaways of this section:

1. Amdahl’s law caps scale-out: the serial fraction $1 - P$ (single-writer database, global lock) bounds throughput no matter how many machines you add — find and remove serial components first.
2. Multitier architecture separates stateless tiers (web, app), which scale out trivially, from the stateful database tier, which needs sharding or replication.
3. Traffic distribution (load balancer, reverse proxy) spreads requests across machines.
4. Data distribution (caching, CDN, sharding) spreads state so the data tier does not become the new serial bottleneck.

Round-robin: cycle through servers in order. Simple but ignores current load.

Least connections: send to the server with the fewest active connections. Better for variable request durations.

Consistent hashing: hash the request key (e.g., user ID) to a position on a circular ring; each server owns the arc from its position to the next server’s position. A key is routed to the server that owns its position. When a server is added or removed, only the keys in the affected arc (approximately $1/N$ of the total) need to be remapped. In practice, each physical server is represented by many virtual nodes (e.g., 100–200) on the ring to ensure even distribution despite the randomness of the hash. Without virtual nodes, a small number of servers can produce highly uneven arc sizes.

Common implementations: Nginx, HAProxy, Envoy. The reverse proxy sits at the edge of the service and can: terminate TLS (offloading CPU from app servers), apply rate limiting (see Queueing and Latency for backpressure mechanisms), route by path or header, and buffer slow clients. See Networks for the underlying transport protocols.

Cache-aside: the application checks the cache; on a miss, it reads from the database and populates the cache. Simple, but a thundering herd (many simultaneous misses for the same key) can overwhelm the database.

Write-through: the application writes to the cache and the database simultaneously. The cache is always consistent but writes are slower.

Write-behind (write-back): the application writes to the cache; the cache asynchronously flushes to the database. Fast writes, but data can be lost on cache failure.

Common in-memory caches: Redis, Memcached. A cache hit reduces a 10 ms database read to a 0.1 ms memory read, a 100× latency improvement for the cached portion.

Providers: Cloudflare, Akamai, Fastly. A CDN caches images, CSS, JS, and sometimes API responses at edge locations (PoPs) near the user. This reduces round-trip latency (a request from Sydney to a US origin is ~200 ms; to a Sydney PoP is ~5 ms) and reduces origin load. CDNs also provide DDoS mitigation and TLS termination at the edge.

The shard key determines which node holds a given record. The goal is even load distribution: each shard should receive approximately $1/N$ of the total requests. Common shard keys: user ID (range or hash), geographic region, tenant ID.

Range sharding: assign contiguous key ranges to shards. Simple, but hot keys (e.g., a viral user) can overload one shard.

Hash sharding: hash the key and assign to shard $h(key) \mod N$. Even distribution, but adding a shard requires rehashing all keys (mitigated by consistent hashing with virtual nodes).

Database scaling before sharding: the database is usually the first bottleneck that horizontal app-server scaling cannot resolve, because it is a shared serial resource (see Amdahl’s law above). Before sharding, try the cheaper database-specific options: read replicas (replicate the database and split reads from writes — read/write splitting at the application or proxy layer — for read-heavy workloads), connection pooling (a small pool of database connections shared by all app servers, since each connection is expensive on the database side), and vertical scaling of the database node. See Fault Tolerance for replication, and Consensus and Consistency for how sharding interacts with consistency guarantees.

Kubernetes HPA (Horizontal Pod Autoscaler): monitors a metric (CPU, memory, or a custom metric like requests/second) and adjusts the number of replicas to keep the metric at a target value. For example, target CPU at 60%: if average CPU across pods reaches 80%, HPA scales out; if it drops to 30%, HPA scales in.

AWS Auto Scaling groups: maintain a desired number of EC2 instances within a defined range. Scaling policies: target tracking (keep a metric at a target, analogous to HPA), step scaling (add N instances when the metric crosses a threshold), predictive scaling (use historical patterns to pre-scale before a known traffic spike).

Scale-in / scale-out thresholds and cooldowns: to prevent oscillation (scale out, then immediately scale in), a cooldown period (e.g., 300 s) is enforced after each scaling action. During the cooldown, no further scaling occurs. The scale-out threshold is typically set at 70–80% utilization (before saturation, per the queueing-theory argument in Queueing and Latency); the scale-in threshold is lower (e.g., 30%) to avoid flapping.

Vertical autoscaling (Kubernetes VPA): adjusts the CPU/memory requests and limits of pods rather than the number of replicas. Useful when the workload is not easily parallelizable.

Challenges: cold-start latency (a new instance needs time to warm up: JIT compilation, cache population, connection pool establishment), cost (over-provisioning during scale-out), and the serial bottleneck (if the database is a single instance, scaling app servers beyond a point does not help—see Amdahl’s law above).

Before: 1 server, $\lambda = 1000$ req/s, $W = 50$ ms. By Little’s law, $L = \lambda W = 1000 \times 0.05 = 50$ concurrent requests. For an M/M/1 model, the service rate is $\mu = \lambda + 1/W = 1000 + 20 = 1020$ req/s, giving utilization $\rho = \lambda / \mu = 1000 / 1020 \approx 0.98$. The server is near saturation.

After: 2 servers, round-robin. Each server handles $\lambda' = 500$ req/s. If the response time is independent of load (no queueing, e.g., fixed I/O latency), each server still takes 50 ms. Maximum sustainable throughput doubles to 2000 req/s ($2\mu = 2040$ req/s); the completed throughput at the current arrival rate is still 1000 req/s, with each server handling 500 req/s. Average response time: $\approx 51$ ms (50 ms service + 1 ms load balancer overhead).

With queueing: model each server as M/M/1 with $\mu = 1020$ req/s. At $\lambda' = 500$: $\rho' = 500 / 1020 \approx 0.49$. Average time in system: $W' = 1 / (\mu - \lambda') = 1 / 520 \approx 1.9$ ms. The queueing delay drops dramatically from the original $W = 1/(1020 - 1000) = 50$ ms to $\approx 1.9$ ms.

Limitation: this model assumes each server is an independent M/M/1 with the same $\mu = 1020$. In practice, the 50 ms response time is dominated by shared I/O (database, network), so the two servers contend on the same backend. The effective service rate per server is lower than 1020 because database connections, disk I/O, and network bandwidth are shared. To truly remove the shared bottleneck, the database must be sharded or replicated so that each app server has its own dedicated I/O path. See Fault Tolerance for how replication and sharding eliminate shared-resource contention.