Chapter 3: System Design & Distributed Systems Architecture Internals

1. Concept Introduction

The Transition from Monolith to Distributed Systems

As digital applications scaled from thousands to hundreds of millions of concurrent users, single-node hardware ceiling limits (vertical scaling / scale-up) were breached. While a single server can be upgraded with 128+ CPU cores and terabytes of RAM, hardware costs scale non-linearly, and physical constraints (memory bus bandwidth, socket limits, thermal throttling) create hard ceilings. Furthermore, single-node systems represent single points of failure (SPOFs).

+-------------------------------------------------------------------------+
|                       HORIZONTAL SCALING (SCALE-OUT)                    |
|  +--------------+   +--------------+   +--------------+   +-----------+ |
|  | Worker Node 1|   | Worker Node 2|   | Worker Node 3|   | Node N... | |
|  +--------------+   +--------------+   +--------------+   +-----------+ |
|        │                   │                  │                 │       |
|  ========= Inter-Node Network Mesh (Unreliable, Asynchronous) ========= |
+-------------------------------------------------------------------------+

Core Fundamental Theorems

1. CAP Theorem (Brewer’s Theorem)

In any asynchronous network subject to partitions, a distributed datastore can simultaneously guarantee at most two of the following three properties:

• Consistency (C): Every read receives the most recent write or an error (Linearizability).
• Availability (A): Every non-failing node returns a non-error response for every request.
• Partition Tolerance (P): The system continues operating despite arbitrary message drops or network delays.

2. PACELC Theorem (Abadi’s Extension)

2. Theory & Low-Level Internals

A. Consistent Hashing Ring Mechanics

                      CONSISTENT HASHING RING (32-bit Space)

                             Node_A (Hash: 0x1000)
                                  0 / 2^32
                                  . . .
                          .                   .
                      .                           .
           Node_D (Hash: 0xC000)                Key_1 (Hash: 0x3000)
                .                                    .
               .                                      .  --> Maps Clockwise
              .                                        .     to Node_B
               .                                      .
           Key_2 (Hash: 0x8000)                 Node_B (Hash: 0x5000)
                      .                           .
                          .                   .
                                  . . .
                             Node_C (Hash: 0x9000)

B. Storage Engines: B-Trees vs. LSM-Trees

3. Real Production Architecture Example

Global Multi-Region Low-Latency Rate Limiter serving 2,000,000 requests/sec across 3 geographic regions (US-East, EU-West, AP-South) with sub-10ms evaluation latency.

                                GLOBAL EDGE LAYER
                          +----------------------------+
                          |   Anycast DNS / Cloudflare |
                          +----------------------------+
                                        │
             ┌──────────────────────────┼──────────────────────────┐
             ▼                          ▼                          ▼
+-------------------------+  +-------------------------+  +-------------------------+
|   REGION: US-EAST       |  |   REGION: EU-WEST       |  |   REGION: AP-SOUTH      |
|  +-------------------+  |  |  +-------------------+  |  |  +-------------------+  |
|  | API Gateway Proxy |  |  |  | API Gateway Proxy |  |  |  | API Gateway Proxy |  |
|  +-------------------+  |  |  +-------------------+  |  |  +-------------------+  |
|            │            |  |            │            |  |            │            |
|            ▼            |  |            ▼            |  |            ▼            |
|  +-------------------+  |  |  +-------------------+  |  |  +-------------------+  |
|  | Local Redis Cluster| |  |  | Local Redis Cluster| |  |  | Local Redis Cluster| |  |
|  | (Sliding Window)  |  |  |  | (Sliding Window)  |  |  |  | (Sliding Window)  |  |
|  +-------------------+  |  |  +-------------------+  |  |  +-------------------+  |
+-------------------------+  +-------------------------+  +-------------------------+

4. Code Examples

A. Consistent Hashing Ring with Virtual Nodes (VNodes) in Java

package com.interviewkit.systemdesign.hashing;

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Collection;
import java.util.SortedMap;
import java.util.ConcurrentSkipListMap;

/**
 * PRODUCTION PRACTICE: Consistent Hash Ring with Virtual Nodes.
 * Solves non-uniform key distribution and hotspotting.
 */
public class ConsistentHashRing<T> {

    private final int numberOfReplicas; // VNodes per Physical Server
    private final SortedMap<Long, T> circle = new ConcurrentSkipListMap<>();

    public ConsistentHashRing(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String vNodeKey = node.toString() + "-VNODE-" + i;
            long hash = computeHash(vNodeKey);
            circle.put(hash, node);
        }
    }

    public T get(String key) {
        if (circle.isEmpty()) return null;
        long hash = computeHash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    private long computeHash(String key) {
        try {
            MessageDigest md5 = MessageDigest.getInstance("MD5");
            byte[] digest = md5.digest(key.getBytes(StandardCharsets.UTF_8));
            long hash = ((long) (digest[3] & 0xFF) << 24) |
                         ((long) (digest[2] & 0xFF) << 16) |
                         ((long) (digest[1] & 0xFF) << 8) |
                         ((long) (digest[0] & 0xFF));
            return hash & 0xffffffffL;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException("MD5 missing", e);
        }
    }
}

B. Distributed Sliding Window Rate Limiter Lua Script for Redis

-- SLIDING WINDOW RATE LIMITER LUA SCRIPT
local rateLimitKey = KEYS[1]
local now = tonumber(ARGV[1])
local windowSize = tonumber(ARGV[2])
local maxRequests = tonumber(ARGV[3])
local requestId = ARGV[4]

local clearBefore = now - windowSize

-- 1. Remove expired timestamps
redis.call('ZREMRANGEBYSCORE', rateLimitKey, 0, clearBefore)

-- 2. Count active requests in sliding window
local currentRequestCount = redis.call('ZCARD', rateLimitKey)

if currentRequestCount < maxRequests then
    redis.call('ZADD', rateLimitKey, now, requestId)
    redis.call('PEXPIRE', rateLimitKey, windowSize)
    return 1 -- PERMITTED
else
    return 0 -- RATE LIMITED (HTTP 429)
end

5. Tiered Interview Questions

6. Production Debugging Scenario