System Design Cases
Consistent Hashing
Consistent hashing concept page: hash ring with 4 nodes (A/B/C/D) with 256 vnodes each, demonstrating naive modulo disaster vs consistent hashing add/remove, vnode balance properties, and node failure rebalance via clockwise next-on-ring.
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.
Связанные темы
Первичные источники
- 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/