---
title: "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"
description: "Consistent Hashing and Random Trees asks how a distributed cache can absorb membership changes and flash crowds without throwing away nearly every placement decision. Read it to see how stable item and cache positions localize reassignment, how monotonicity limits movement, and how a different random cache tree for each page spreads hot demand."
canonical_url: "https://fanout.sh/daily/2026-09-05-consistent-hashing-random-trees"
md_url: "https://fanout.sh/daily/2026-09-05-consistent-hashing-random-trees.md"
last_updated: "2026-09-05"
access: "public"
---

# Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web

Consistent Hashing and Random Trees asks how a distributed cache can absorb membership changes and flash crowds without throwing away nearly every placement decision. Read it to see how stable item and cache positions localize reassignment, how monotonicity limits movement, and how a different random cache tree for each page spreads hot demand.

## Paper details

- Authors: David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy

- Venue: STOC 1997

- Track: Systems

- Difficulty: Easy

- Reading time: 35 min

- Original paper: https://doi.org/10.1145/258533.258660

## What you will learn

- Why a conventional hash whose range depends on the cache count can remap almost every object when one cache joins or leaves.

- How the paper maps items and replicated cache points to a fixed unit interval, then uses monotonicity to prevent movement between two old caches.

- How balance, spread, load, random cache trees, and explicit model assumptions qualify the paper's theoretical hot-spot guarantees.

## Continue exploring

[Explore consistent hashing in Fanout](https://fanout.sh/system/archive/consistent-hashing): Connect the original closest-point construction to Fanout's practical hash-ring guide, including virtual nodes, membership convergence, warmup, and hot-key limits.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md