Week 6 — Consistent Hashing & Search

The Problem with Modulo Hashing

Standard approach: server = hash(key) % N

Add or remove a server (N changes) → almost all keys remap to different servers → massive cache miss storm.

Consistent Hashing

Map both keys and servers onto a hash ring (0 to 2³²-1). A key is served by the first server clockwise from its position.

         Server A (12 o'clock)
        /
Ring → Key X → Server A
        \
         Key Y → Server B (3 o'clock)
                  \
                   Server C (6 o'clock)

Adding a server: Only keys between the new server and its predecessor move — ~1/N of all keys.

Removing a server: Only that server’s keys move to its successor.

Virtual Nodes

Assign each physical server multiple positions on the ring. Prevents uneven distribution when servers have different capacities.

Server A → positions 12, 4, 8 o'clock
Server B → positions 2, 6, 10 o'clock

Used by: Redis Cluster, Cassandra, DynamoDB.

Search Systems

Why SQL Full-Text Search Falls Short

SELECT * FROM products WHERE name LIKE '%laptop%';
-- Can't use B-tree index → full table scan
-- No ranking (relevant results first)
-- No typo tolerance
-- No stemming (search "run" → finds "running", "ran")

Inverted Index

Core data structure behind all search engines:

"laptop"  → [doc_3, doc_7, doc_15]
"gaming"  → [doc_3, doc_9]
"cheap"   → [doc_7, doc_22]

At query time, intersect the lists.

Relevance: TF-IDF / BM25

• TF (Term Frequency): how often does the term appear in this document?
• IDF (Inverse Document Frequency): how rare is this term across all documents?
• Score = TF × IDF — common words (“the”, “a”) score low; rare specific words score high

BM25 is the modern improvement on TF-IDF. Used by Elasticsearch and PostgreSQL full-text search.

PostgreSQL Full-Text vs Elasticsearch

	PostgreSQL FTS	Elasticsearch
Setup	Already there	Separate cluster
Scale	Moderate (millions of docs)	Billions of docs
Features	Basic	Fuzzy, facets, geo, aggregations
Consistency	Strong (same DB)	Eventual

Key principle: PostgreSQL is the source of truth. Elasticsearch is a derived read model — it can always be rebuilt from PostgreSQL.

Write → PostgreSQL → (async sync) → Elasticsearch index
Read  → Elasticsearch (fast, ranked)

Practice

Design search for a product catalogue:

• 5M products, updated hourly
• Need: typo tolerance, filter by category/price, relevance ranking
• 10K searches/sec at peak

Self-check

• Why does consistent hashing still have uneven distribution without virtual nodes?
• If Elasticsearch goes down, what happens to your users? What happens to your data?
• What’s the difference between a search index and a database index?