三种常见的哈希分片
- 节点取余
- 一致性哈希
- 虚拟槽哈希
节点取余
主要采取的手段就是:hash(key) % N
|--------------|
| 1~100 |
|--------------|
hash(key)%3
|--------------| |--------------| |--------------|
| 3,6,9...99 | | 1,4,7...100 | | 2,5,8...98 |
|--------------| |--------------| |--------------|
|--------------|
| 1~100 |
|--------------|
hash(key)%4
|--------------| |--------------| |--------------| |--------------|
| 4,8,...100 | | 1,5...97 | | 2,6...98 | | 3,7...99 |
|--------------| |--------------| |--------------| |--------------|
节点取余存在的问题
数据迁移量较大,例如: 1~10
, 3
个节点:
- 第0个节点: 3, 6, 9
- 第1个节点: 1, 4, 7, 10
- 第2个节点: 2, 5, 8
如果这时候我们把节点进行扩展,扩展到 4 个节点数据存储如下:
- 第0个节点: 4, 8
- 第1个节点: 1, 5, 9
- 第2个节点: 2, 6, 10
- 第3个节点: 3, 7
节点取余推荐扩容方式
翻倍扩容, 例如: 1~10
, 3
个节点:
- 第0个节点: 3, 6, 9
- 第1个节点: 1, 4, 7, 10
- 第2个节点: 2, 5, 8
然后我们基于上一次的节点数量进行翻一倍,目前就是 6 个节点了:
- 第0个节点: 6
- 第1个节点: 1 7
- 第2个节点: 2 8
- 第3个节点: 3 9
- 第4个节点: 4 10
- 第5个节点: 5