Partitioning & Sharding • Hash-based PartitioningMedium⏱️ ~3 min
Failure Modes: Rehash Storms, Skew, and Cross Language Consistency
Rehash storms occur when the partition count N changes in a naive hash(key) mod N scheme, causing nearly all keys to remap to different partitions. This triggers catastrophic cache invalidation and massive data migration simultaneously. For example, a 100 node cache cluster using modulo hashing loses 99 percent of cached data when adding one node (changing from mod 100 to mod 101), causing a thundering herd of cache misses to hit the backing database. The database experiences a sudden 100x traffic spike, potentially cascading into full outage. Production systems must use consistent hashing, rendezvous hashing, or maintain a stable logical bucket space separate from physical nodes. With consistent hashing, adding one node to a 100 node cluster moves only 1 percent of keys. With a fixed bucket space of 10,000 logical buckets mapped to nodes, adding a node requires only remapping some buckets (not rehashing keys), and keys within unmapped buckets stay on the same node.
Hash function choice and implementation consistency across languages create subtle but severe bugs. Different hash functions (MD5, SHA, Murmur3, xxHash) produce completely different outputs, so changing hash algorithms remaps all keys. Even the same algorithm can differ across languages due to byte ordering (endianness), string encoding (UTF8 versus UTF16), or integer width (32 bit versus 64 bit). For example, Java's built in hashCode() returns a 32 bit signed integer, while Go's hash/fnv returns a 64 bit unsigned integer. If Java clients and Go services compute partition assignments independently, they will disagree on key placement, causing split brain routing where writes go to one partition and reads check another. Production systems must standardize on one hash function with a published specification, define canonical serialization (field order, encoding, normalization), use 64 bit hash output to minimize collisions, and publish reference implementations in all supported languages with cross language test suites.
Poor hash quality or insufficient bucket counts cause uneven distribution even without hotkeys. Weak hash functions can have correlation with input patterns, clustering keys non uniformly. Using too few buckets relative to nodes amplifies variance: with only 10 buckets and 8 nodes, some nodes will own 2 buckets while others own 1, creating 2x load imbalance. Production guidance is to use 100 to 1,000 logical buckets per physical node (so an 8 node cluster uses 800 to 8,000 buckets), fast non cryptographic hash functions like Murmur3 or xxHash with 64 bit output, and to monitor per node load variance continuously. When heterogeneous nodes exist (different CPU, memory, or disk), assign buckets proportionally to capacity: a node with 2x capacity should own 2x buckets. Update bucket assignments dynamically based on observed load, not just static capacity, to handle workload shifts over time.
💡 Key Takeaways
•Rehash storm from naive modulo causes 99 percent cache miss rate: Adding one node to 100 node cluster with hash(key) mod N changes almost all key mappings, invalidating cached data and spiking backend load 100x. Use consistent hashing to limit movement to 1 percent of keys.
•Fixed logical bucket space decouples keys from nodes: Maintain 10,000 buckets mapped to nodes. Adding node remaps only some bucket to node assignments. Keys within unchanged buckets stay put, avoiding full rehash.
•Cross language hash inconsistency causes split brain routing: Java hashCode returns 32 bit signed int. Go FNV returns 64 bit unsigned. Same key hashes to different partitions. Writes and reads target different nodes, causing data loss and inconsistency.
•Canonical serialization prevents hash drift: Define field order, encoding (UTF8), and normalization before hashing. Version the hashing scheme. Java and Python clients must produce bitwise identical hash input for the same logical key.
•Weak hash functions cluster keys non uniformly: Poor hash quality causes correlation with input patterns. Use Murmur3 or xxHash with 64 bit output. Avoid simple XOR or addition based hashes susceptible to pattern bias.
•Insufficient bucket count amplifies variance: 10 buckets across 8 nodes means some nodes own 2 buckets, others 1 (2x imbalance). Use 100 to 1,000 buckets per node (800 to 8,000 for 8 node cluster) to smooth distribution via law of large numbers.
📌 Examples
Rehash storm incident: Memcache cluster of 100 nodes uses hash(key) mod 100. Operator adds 1 node without switching to consistent hashing, changing formula to mod 101. 99 out of 100 keys remap. Cache hit rate drops from 95 percent to 1 percent instantly. Database receives 50x traffic spike and times out, causing site wide outage.
Cross language hash bug: Java microservice computes partition = hash(user_id).intValue() mod 16. Python analytics service computes partition = hash(user_id) mod 16 using built in hash(). Python's hash output differs from Java Murmur3. Analytics reads wrong partitions, reporting zero activity for 80 percent of users. Fix: standardize on Murmur3 with published byte serialization for user_id.
Insufficient bucket count: Distributed cache with 50 nodes uses 100 buckets (2 buckets per node average). Random assignment gives some nodes 4 buckets, others 0. Coefficient of variation is 0.6. Increase to 5,000 buckets (100 per node). CV drops to 0.08. Load variance reduces from 4x to 1.2x max.
Heterogeneous node weighting: Cluster has 10 standard nodes (8 CPU cores each) and 2 large nodes (64 cores each). Assign 100 buckets to each standard node, 800 buckets to each large node. Total 2,600 buckets. Large nodes handle 8x load proportional to capacity, preventing small nodes from bottlenecking cluster throughput.