Consistent hashing без магии

Consistent hashing минимизирует изменение key placement при изменении множества buckets/nodes. Он не предоставляет replication, durability, membership consensus, failure detection или perfect balance. Эти слои проектируются отдельно.

Две математики

Для uniform integer hash при переходе hash mod 4 → hash mod 5 совпадает примерно 1/5 assignments, поэтому перемещается примерно 4/5 = 80% keys.

В equal-capacity consistent-hash design добавление пятого node к четырём должно отдать ему в expectation около 1/(4+1)=20% keyspace. Это не 1/N со старым N и не deterministic exact balance: finite samples и случайные token intervals дают variance.

Сценарии

Modulo live-node-count прост, но membership change массово remaps keys. Его можно стабилизировать fixed slots/directory, но тогда это уже другой placement layer.

Joining node сначала получает token ranges, streams data и доказывает readiness. Ownership epoch публикуется после transfer; иначе router отправит запросы к пустому owner.

Multiple tokens/vnodes уменьшают imbalance и позволяют capacity weights. Больше tokens означает больше peers/ranges/repair tasks и комбинаций failure exposure. Текущее Cassandra guidance предлагает выбирать token count под elasticity, availability и cluster size; универсального «256 всегда» нет.

При RF=1 отказ owner означает unavailability. Replication policy выбирает distinct physical nodes/failure domains, consistency policy выбирает required responses, repair восстанавливает RF. Ring сам этого не делает.

Redis Cluster — важный контрпример

Redis официально пишет, что Cluster не использует consistent hashing. Он применяет CRC16(key) mod 16384 и явно назначает fixed slots masters. Scale operation двигает slots между nodes. Это снижает массовый remap, но это slot directory, не Karger ring.

Operations checklist

• token/slot map versioned и atomically published;
• weights основаны на tested capacity;
• replicas distinct by physical failure domain;
• bootstrap/repair resumable и checksummed;
• stale router получает redirect/epoch error;
• decommission ждёт transfer и drain;
• hot key обрабатывается отдельно от average balance.

Связанные темы

[CONCEPT]replication

[CONCEPT]hot-key-mitigation

Первичные источники

• Karger et al. paper: https://people.csail.mit.edu/karger/Papers/web.pdf
• ACM record: https://doi.org/10.1145/258533.258660
• Cassandra Dynamo architecture: https://cassandra.apache.org/doc/latest/cassandra/architecture/dynamo.html
• Cassandra production tokens: https://cassandra.apache.org/doc/latest/cassandra/getting-started/production.html
• Redis scaling: https://redis.io/docs/latest/operate/oss_and_stack/management/scaling/