Hashing in the Wild

Git: Content-Addressable Storage

Git stores every version of every file as a blob — an object identified by the SHA-1 hash of its contents. The file path is irrelevant to storage. The content determines the address.

This creates content-addressable storage (CAS). In a content-addressable store, the key is derived from the value, not assigned independently.

import hashlib

def git_blob_hash(content: bytes) -> str:
    """
    Compute the Git blob SHA-1 for file content.
    Git prepends 'blob <size>\0' before hashing.
    """
    header = f"blob {len(content)}\0".encode()
    sha1 = hashlib.sha1(header + content)
    return sha1.hexdigest()

# The same content always produces the same address
content = b"def hello():\n    return 'world'\n"
address = git_blob_hash(content)
# address is always "9b0d5e6a..." regardless of filename or location

The architectural consequence is profound. If you modify one file in a 10,000-file repository, only one blob changes. All other blobs are shared. Git does not copy unchanged files across commits — it references the same blobs. A branch is not a copy of the repository; it is a new commit object that points to the same tree of blobs. Creating a branch is O(1) regardless of repository size.

The hash function’s determinism enables deduplication. The hash function’s collision resistance enables trust — you can verify that a file you fetched matches the file that was committed, without trusting the network or the server.

Load Balancers: Consistent Hashing

A load balancer must distribute requests across N servers. The naive approach: server = servers[hash(request_key) % N]. This works until a server is added or removed. At that point, N changes, and hash(key) % N changes for almost every key. Every session that was pinned to server 3 is now pinned to a different server. Sessions break.

Consistent hashing solves this. Both keys and servers are mapped to the same circular ring using the same hash function. A key is served by the first server clockwise from the key’s position on the ring.

import hashlib
import bisect

class ConsistentHashRing:
    """
    Consistent hash ring: only O(K/N) keys migrate when a
    node is added or removed, where K is the total number of
    keys and N is the number of nodes.
    """
    def __init__(self):
        self._ring: dict[int, str] = {}   # hash position -> node name
        self._sorted_keys: list[int] = []

    def _hash(self, key: str) -> int:
        return int(hashlib.sha256(key.encode()).hexdigest(), 16)

    def add_node(self, node: str) -> None:
        h = self._hash(node)
        self._ring[h] = node
        bisect.insort(self._sorted_keys, h)

    def remove_node(self, node: str) -> None:
        h = self._hash(node)
        self._ring.pop(h, None)
        self._sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        if not self._ring:
            raise ValueError("Ring is empty")
        h = self._hash(key)
        # Find the first node clockwise from key's position
        idx = (bisect.bisect_right(self._sorted_keys, h)
               % len(self._sorted_keys))
        return self._ring[self._sorted_keys[idx]]

When a server is added or removed, only the keys between the new/removed node and its predecessor on the ring migrate. On average, K/N keys migrate when one of N nodes changes — compared to nearly all K keys with modular hashing.

Virtual Nodes: Fixing Uneven Distribution

A three-node ring with one hash position per node produces uneven distribution. With three positions on a 360-degree ring, the spacing between them is random — one arc might cover 180 degrees, another 10 degrees, another 170 degrees. The server on the large arc handles far more traffic.

The fix is virtual nodes: each physical server is mapped to multiple positions on the ring (100–200 is typical). The positions for “server-A” are derived by hashing “server-A-1”, “server-A-2”, …, “server-A-200”.

class VirtualNodeRing(ConsistentHashRing):
    """
    Consistent hash ring with virtual nodes for even distribution.
    More virtual nodes per server = more even load distribution.
    """
    def __init__(self, virtual_nodes: int = 150):
        super().__init__()
        self._virtual_nodes = virtual_nodes

    def add_node(self, node: str) -> None:
        for i in range(self._virtual_nodes):
            virtual_key = f"{node}-vnode-{i}"
            h = self._hash(virtual_key)
            self._ring[h] = node
            bisect.insort(self._sorted_keys, h)

    def remove_node(self, node: str) -> None:
        for i in range(self._virtual_nodes):
            virtual_key = f"{node}-vnode-{i}"
            h = self._hash(virtual_key)
            self._ring.pop(h, None)
            if h in self._sorted_keys:
                self._sorted_keys.remove(h)

With 150 virtual nodes per server, the load deviation across servers drops to within a few percent, regardless of the number of physical servers.

Virtual nodes smooth load distribution; removing N2 affects only its arc.

Distributed Caches: Sharding by Key

A distributed cache (Redis Cluster, Memcached) must decide which cache node holds a given key. The key-to-node mapping must be consistent — the same key must always go to the same node — and must survive node additions and removals without invalidating most cached data.

This is exactly the load-balancer problem. Redis Cluster uses a variant: it divides the key space into 16,384 fixed hash slots (slot = crc16(key) % 16384). Each node owns a contiguous range of slots. When a node is added or removed, only the affected slots migrate.

# Redis Cluster slot assignment (simplified)
def redis_slot(key: str) -> int:
    """Returns the hash slot for a key (0–16383)."""
    import binascii
    # If key contains braces, only hash the content inside {}
    # This enables co-location: {user:123}:profile and {user:123}:settings
    # will always land on the same slot
    start = key.find('{')
    end = key.find('}', start)
    if start != -1 and end != -1 and end > start + 1:
        key = key[start + 1:end]
    return binascii.crc_hqx(key.encode(), 0) % 16384

The hash tag {} mechanism is a pragmatic escape hatch: if two keys must be on the same node (for atomic operations), wrap the shared identifier in braces. The hash function then only hashes the content inside the braces, guaranteeing co-location.

Rolling Hashes: Hashing a Sliding Window in O(1)

rsync copies only the changed bytes of a multi-gigabyte file by scanning the destination file for blocks that match the source’s block hashes — at every byte offset, not just aligned block boundaries. git diff --find-renames detects a file that moved from src/a.py to lib/a.py by hashing overlapping windows of both files and looking for matches. Content-defined chunking in Restic and BorgBackup finds “natural” chunk boundaries in a binary file by scanning for byte windows whose hash ends in a specific pattern, so that a single-byte insertion re-chunks only the surrounding region rather than shifting every downstream chunk.

All three do the same thing: they compute the hash of every length-W substring of a length-N stream. Naively, that is O(N·W) — recompute a hash for every window. Rolling hashes make it O(N).

A rolling hash is a hash function with a special algebraic property: given the hash of window [i, i+W), you can compute the hash of window [i+1, i+W+1) in O(1) by removing the outgoing byte and adding the incoming byte. Karp-Rabin’s polynomial hash is the canonical example. Treat the window as a base-B number modulo a prime P:

H(s[i..i+W]) = (s[i]·B^(W-1) + s[i+1]·B^(W-2) + ... + s[i+W-1]) mod P

Sliding one byte to the right subtracts s[i]·B^(W-1), multiplies the remainder by B, and adds s[i+W] — three arithmetic operations, no dependence on W.

BASE = 257
MOD  = (1 << 61) - 1        # Mersenne prime; fast reduction, low collision rate

def rabin_karp(text: bytes, pattern: bytes) -> list:
    """
    Return all offsets where pattern occurs in text.
    O(N + M) expected time; collisions verified by direct byte comparison.
    """
    n, m = len(text), len(pattern)
    if m > n or m == 0:
        return []

    top = pow(BASE, m - 1, MOD)         # B^(m-1) mod P, for the drop step
    ph = th = 0
    for i in range(m):                  # seed both hashes from first window
        ph = (ph * BASE + pattern[i]) % MOD
        th = (th * BASE + text[i])    % MOD

    hits = []
    for i in range(n - m + 1):
        if th == ph and text[i:i + m] == pattern:   # verify to rule out collision
            hits.append(i)
        if i + m < n:
            # Roll: drop text[i], add text[i+m].
            th = ((th - text[i] * top) * BASE + text[i + m]) % MOD
    return hits

The rolling step is the whole point. Without it, you would recompute an m-byte hash at every position — Θ(N·M). With it, hashing is Θ(N) and only positions where the hashes match pay the O(M) verification cost. On random data, false positive rate is ≈ 1/P; with a 61-bit prime, that is roughly one wasted comparison every 2×10^18 positions — effectively never on any real workload.

Rabin-Karp’s real value is not single-pattern search — for that, KMP or Aho-Corasick are simpler and have no collision handling. It shines when you need multi-pattern search: hash k patterns into a set, then scan the text once, checking each window’s hash against the set in O(1). This is how content-defined chunking works, how plagiarism detectors compare a document against a corpus, and how Rsync’s algorithm finds source blocks in the destination file.

Level 1 — Understand

1. What property of a hash function makes Git’s content-addressable storage work? What would break if two different files could produce the same hash?

2. Explain the difference between modular hashing (hash(key) % N) and consistent hashing. In which scenario does modular hashing break, and what is the consequence?

3. What problem do virtual nodes solve in a consistent hash ring? What is the cost of using more virtual nodes?

Level 2 — Apply

A consistent hash ring has three nodes: A, B, C. Their positions on the ring (0–99) are: A=10, B=45, C=72.

1. Which node handles keys that hash to: 5, 30, 60, 80?

2. Node B is removed. Which keys migrate, and to which node?

3. Node D is added at position 55. Which keys migrate, and to which node?

Level 3 — Design

You are designing the routing layer for a distributed session store. The session store has 10 nodes. Sessions must be sticky — a user’s session must always be routed to the same node for the duration of the session. The node pool changes: nodes fail ~2 times per month and are replaced; capacity scales up by adding 2–3 nodes per quarter.

1. Design the routing strategy. Choose between modular hashing and consistent hashing. Name the tradeoff explicitly.

2. How many virtual nodes per physical node would you configure? What determines this number?

3. When a node fails mid-session, some sessions are lost. Propose a strategy to reduce session loss on node failure without breaking the consistent hashing model. Name every tradeoff you introduce.

A complete answer will: define the chosen approach, quantify its cost or complexity, and identify what breaks first as scale or load increases.