一、背景

普通hash取模弊端明显，扩容需要对所有数据重新hash，数据迁移量很大。

二、原理

创建1<<32个节点，形成hash环，hash值对1<<32取模后，顺时针映射到真实节点。

三、优缺点

3.1 优点：

可以动态扩容，增加一个真实节点，只对顺时针下一个真实节点产生影响，迁移率小。

3.2 缺点：

• hash倾斜，导致数据分布不均。
• 真实节点很多的话，扩容要计算hash环上迁移虚拟节点的工作量增大。

四、对缺点的补充

分库与分表的算法分开，独立扩容。

• m为库的数量，hash%(1<<32) / ((1<<32)/m)，作为分库算法，表数量不变去成倍的扩容库，只需迁移整张表，不需要重新hash。
• n为表的数量，hash % n，作为分表算法，扩容库并不需要重新hash，成倍的扩容表，只需要在本库迁移，不需要换库。

五、部分代码

5.1 分库分表算法：

        long hash = Hashing.murmur3_128().hashString(orderNo, StandardCharsets.UTF_8).asLong();
        if(hash<=0) hash = hash & Long.MAX_VALUE;
        long value = hash % 4294967296L;

        // 分库,64库
        long databaseIndex = value / (4294967296L/32);

        // 分表,每库分32张表
        long tableIndex = hash % 32;
        System.out.println(value + "  " + databaseIndex + "-" + tableIndex);

5.2 数据测试

• 扩容库，左图32库32表，右图64库32表

  
  
  image.png

• 扩容表，左图32库32表，右图32库64表

  
  
  image.png