Hashing in the Wild

Introduction

In 2012, GitHub added a feature: every file in every repository has a permanent address — the SHA-1 hash of its contents. Not a path. Not a filename. The hash. Change one byte in the file and the address changes. The file at the old address remains permanently available and permanently unchanged.

This is not a convenience feature. It is an architectural decision with a specific algorithmic basis. The hash function makes storage immutable. Immutable storage makes branching cheap. Cheap branching makes version control distributed. Every Git operation you have ever run — clone, branch, merge, push — depends on the properties of a hash function.

You built hash tables in Book 1, Chapter 22. You saw modular arithmetic on a ring in Chapter 39. Now those structures appear inside three systems you use daily. The shape is identical. The scale and the consequences are different.

Thread Activation

In Book 1, Ch 22, you built a hash table: a hash function maps keys to bucket indices; collisions are resolved by chaining or probing. In Ch 39, you saw modular arithmetic applied to a ring — the basis of consistent hashing.

This chapter traces Thread 1 (Hashing) into three production systems. Each system uses the same mathematical properties — uniform distribution, determinism, and (in the case of SHA-1) collision resistance — but applies them to different engineering problems. The thread continues in Book 3, Chapters 4–5, where consistent hashing becomes the foundation of distributed database sharding.

The Concept

A hash function takes an input of arbitrary length and produces a fixed-length output (the hash, digest, or fingerprint). Two properties make hash functions useful in engineering:

1. Determinism: the same input always produces the same output. Given the same content, the hash is always the same value.
2. Uniform distribution: outputs are distributed uniformly across the output space. This prevents hotspotting — no single output bucket is disproportionately likely.

Cryptographic hash functions add a third property:

3. Collision resistance: it is computationally infeasible to find two different inputs that produce the same output. This enables trust: if two files have the same SHA-256 hash, you can be confident (but not certain) they have identical content.

The engineering applications of hash functions vary, but each one exploits one or more of these three properties.

How It Works

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

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]]

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)

# 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

Tradeoffs

AT3 — Simplicity vs. Flexibility

Naive modular hashing (hash(key) % N) is simple: O(1), one line of code, easy to understand. Consistent hashing is more complex: a ring data structure, O(log N) lookup via binary search, virtual nodes to correct uneven distribution. The cost of flexibility is complexity.

The decision point is: does your server pool change? If N is fixed forever, modular hashing is correct. If N changes — due to failures, autoscaling, planned capacity changes — the cost of modular hashing is session breakage on every cluster change. For any system that operates at scale, the server pool changes. Consistent hashing is the standard choice.

AT9 — Correctness vs. Performance

SHA-1 (used by Git) is cryptographic: collision-resistant but slow (~200 MB/s on modern hardware). MurmurHash and xxHash are non-cryptographic: not collision-resistant but extremely fast (5–10 GB/s). For a load balancer routing decision, collision resistance is irrelevant — you do not need a security guarantee, you need speed. For Git, where the hash is a trust anchor, collision resistance matters. Use SHA-2 or SHA-3 for security; use MurmurHash or xxHash for performance.

Where It Fails

FM6 — Hotspotting

Without virtual nodes, consistent hashing produces uneven distribution. A three-node ring will, by the random placement of three points on a circle, almost certainly have one arc that is substantially larger than the others. The node responsible for the large arc handles more traffic. Virtual nodes fix this by creating many more points, averaging out the distribution.

The failure mode is silent: the system works correctly, but one node is overloaded. Monitor per-node request rates and connection counts. If one node consistently handles 40% of traffic in a three-node pool, you have hotspotting.

FM9 — Silent Data Corruption

Git’s use of SHA-1 has a known weakness: SHA-1 is theoretically broken for collision resistance (demonstrated by the SHAttered attack in 2017). An attacker who can construct two different files with the same SHA-1 hash can substitute one for the other in a repository. Git has migrated to SHA-256 for new repositories for this reason. The failure mode (two different objects with the same address) would corrupt the DAG silently.

Real Systems

DynamoDB uses consistent hashing to distribute data across nodes. Each item’s partition key is hashed using a consistent hash function; the hash determines which partition the item lives on. When DynamoDB adds capacity, only the partitions adjacent to the new nodes need to migrate data.

Cassandra uses a consistent hash ring with virtual nodes (called “vnodes” in Cassandra documentation). Each node is assigned multiple token ranges on the ring. The token range assignment is configurable; nodes with more capacity receive more tokens.

CDNs (Akamai, Fastly, CloudFlare) use consistent hashing to route requests to edge nodes. A request for a given URL is always routed to the same edge node (or a small set of edge nodes), maximising cache hit rates. When edge nodes are added (during a traffic spike), consistent hashing ensures most cached content remains at the same nodes.

Exercises