mufassall

Data & storage / 6 / 11

Consistent hashing

A profile API keeps hot data in three cache servers. Adding a fourth one should help, but with `hash % N` it empties almost the whole cache. How a hash ring moves only a quarter of the keys, and why it needs virtual nodes.

  • 12 min
  • Intermediate
  • 9 steps
Cache hit rate
95 %
DB reads
250 /s
Keys moved
0 %
Open in Lab
20%
  • request
  • reply
  • redelivery
  • duplicate
  • lost

Numbers are a model scenario, not measurements

The real request

Profile API → Cache B

Request

GET user:u_4212

Response

"plan=pro;lang=uz"
  1. GET — hash("user:u_42") = 2718281827, and 2718281827 % 3 = 1, so the key lives on cache B.
  2. u_42 — The user id inside the key. Every API server computes the same cache for it, with no lookup table.
Course: 42 lessons
  1. 01 Foundations

    1. The life of a request
    2. Latency and throughput
    3. Napkin math
  2. 02 Scaling

    1. Scaling up vs scaling out
    2. Load balancing
    3. Stateless servers
    4. Caching
    5. CDN and edge caching
  3. 03 Data & storage

    1. SQL and NoSQL
    2. Database indexes
    3. Storage engines: B-tree and LSM
    4. Database replication
    5. Sharding
    6. Consistent hashing
    7. Unique IDs
    8. CAP: when the link breaks
    9. Consensus and leader election
    10. Transactions
    11. File uploads
  4. 04 Communication

    1. API styles
    2. Message queues
    3. Pub/sub and event logs
    4. Real-time updates
    5. Reliable callbacks
  5. 05 Reliability

    1. Redundancy and failover
    2. Rate limiting
    3. Timeouts and retries
    4. Observability
  6. 06 Architecture

    1. Microservices
    2. Service discovery
    3. Sagas and the outbox
    4. Batch vs stream
  7. 07 Security

    1. Authentication
    2. Authorization
    3. Encryption and secrets
  8. 08 Shipping

    1. Testing
    2. CI/CD: from commit to production
  9. 09 Whole systems

    1. From requirements to design
    2. Design a URL shortener
    3. Design a news feed
    4. Design a chat
  10. 10 Business processes

    1. Payment gateway