分布式主键 详解

雪花算法结合分库分表的问题

问题出现

使用ShardingSphere框架自带的雪花算法生成分布式主键，如果和分片算法结合使用不当就很有可能造成数据分布不均匀的情况

如下所示，我使用分布式主键生成策略是SNOWFLAKE，分表策略是常见的取模运算

	rules:
      sharding:
        # 分片键生成策略
        key-generators:
          # 雪花算法
          alg_snowflake:
            type: SNOWFLAKE
            props:
              worker:
                id: 1
        sharding-algorithms:
          # 定义分库策略
          db_alg:
            type: MOD
            props:
              sharding-count: 2
          # 分表策略
          sys_user_tab_alg:
            type: INLINE
            props:
              algorithm-expression: sys_user$->{((uid+1)%4).intdiv(2)+1}

进行新增操作后，这里并没有均匀的分布在四个数据表中，只存在两个数据表中

原因分析

造成这个问题的原因是，ShardingSPhere自带的雪花算法的序列号位是一个单位时间内自增，如果不是一个单位时间内那么就重置为0重新自增。

// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithm

@Override
public synchronized Long generateKey() {
    long currentMilliseconds = timeService.getCurrentMillis();
    // 处理雪花算法41bit时间戳位 时钟回拨 
    if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
        currentMilliseconds = timeService.getCurrentMillis();
    }
    // 处理12bit序列号位
    if (lastMilliseconds == currentMilliseconds) {
        // 单位时间内  sequence序列号位每次都是自增
        if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
            currentMilliseconds = waitUntilNextTime(currentMilliseconds);
        }
    } else {
        // 如果不是一个单位时间内，序列号位就又重置
        vibrateSequenceOffset();
        sequence = sequenceOffset;
    }
    lastMilliseconds = currentMilliseconds;
      //  时间戳位 | 工作进程位 | 序列号位
  return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}

进一步编写测试类验证

取出插入数据库中的uid值，进行位& 运算，最终就可以发现序列号位基本上都是 0 或者是1 那么这样我们就进行简单的 %2 %4 运算所以就导致了上方的数据分布不均匀问题

public void testSequence(List<Long> uidList) {
    int mask = (1 << 3) - 1;
    for (Long uid : uidList) {
        log.info("uid:{} 的后3位的结果为 {}", uid, uid & mask);
    }
}

uid:1027514136331812864 的后3位的结果为 0
uid:1027514137086787584 的后3位的结果为 0
uid:1027514137128730624 的后3位的结果为 0
uid:1027514137166479360 的后3位的结果为 0
uid:1027514137204228096 的后3位的结果为 0
uid:1027514137057427457 的后3位的结果为 1
uid:1027514137107759105 的后3位的结果为 1
uid:1027514137149702145 的后3位的结果为 1
uid:1027514137183256577 的后3位的结果为 1
uid:1027514137216811009 的后3位的结果为 1

解决思路

修改现有的雪花算法，让序列号位不要每次都重置。这种方式的确能解决当前业务功能。

@Override
public synchronized Long generateKey() {
    long currentMilliseconds = timeService.getCurrentMillis();
    if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
        currentMilliseconds = timeService.getCurrentMillis();
    }
    if (lastMilliseconds == currentMilliseconds) {
//      if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
        currentMilliseconds = waitUntilNextTime(currentMilliseconds);
//      }
    } else {
        vibrateSequenceOffset();
//      sequence = sequenceOffset;
        // SEQUENCE_MASK = (1 << 12L) - 1
        sequence = sequence >= SEQUENCE_MASK ? 0:sequence+1;
    }
    lastMilliseconds = currentMilliseconds;
    return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}

但是带来的问题是分布式场景下，雪花算法的序列号位相当于没用了。因为雪花算法的初始目标就是分布式主键生成不冲突，它是靠 时间戳位+工作进程位+序列号位保证的。

如果在单位时间内，并且没有设置工作进程位，多台服务器中的序列号位相同了，那么也就导致了后续生成的id都可能出现重复的情况。

分布式主键要考虑的问题

1. 主键除了要标识数据的唯一性之外，还通常会要求主键与业务不直接相关。因为这样不管业务如何变化，都不会影响主键来控制数据的生命周期
2. 但是，另外一个方面，我们通常又会要求主键包含一部分的业务属性，这样可以加速对数据的检索。
3. 主键也需要考虑安全性，让别人无法通过规律猜出主键来。

所以，对于主键，一方面，要求他与业务不直接相关。这就要求分配主键的服务要足够稳定，足够快速。不能说我辛辛苦苦把业务给弄完了，然后等着分配主键的时候，还要等半天，甚至等不到。另一方面，要求他能够包含某一些业务特性。这就要求分配主键的服务能够进行一定程度的扩展。

主键生成策略

数据库策略

业务层面不设置主键，直接使用数据库的自增长。这种方式实现简单，但是分库分表场景下就会造成主键冲突。当然也可以通过为各个数据库设置自增长步长来解决。但是又不能满足分库分表扩缩容的场景。

应用单独生成

数据库生成的主键不靠谱，那么就应用层面自己来生成。比较常见的算法就是：UUID、NANOID、SnowFlaks雪花算法

优点：简单使用。比如UUID使用JDK自带的工具类即可、SnowFlaks按照它定义的规则自行组合。比较容易扩展，可以随意组合生成主键。

缺点：

• 算法不能太复杂，会消耗cpu计算资源与内存空间
• 要考虑多线程并发安全问题，不能主键冲突。
• 考虑数据库产品结合因素，比如mysql的InnoDB存储引擎，B+树索引，需要使用趋势递增的主键来避免B+树的分裂。UUID这类无序字符串主键就不能满足

第三方服务统一生成

借助第三方服务来生成主键，比如redis、zookeeper、MongoDB

redis：通过incr指令，配合lua脚本比较容易防并发

zookeeper：使用它的序列号节点；或者是在apache提供的Zookeeper客户端Curator中，提供了DistributedAtomicInteger，DistributedAtomicLong等工具，可以用来生成分布式递增的ID。

MongoDB：使用MongoDB的ObjectID。

缺点：

• 这些原生的方式大都不是为了分布式主键场景而设计的，所以，如果要保证高效以及稳定，在使用这些工具时，还是需要非常谨慎。
• 每一次生成主键都需要调用第三方服务，效率问题也需要考虑

与第三方结合的segment策略

还是从第三方获取主键，只不过是一次获取一批主键，缓存在本地，当使用完后再去申请一批。

比如我们设计下面这种数据表

biz_tag表示具体的某一业务标识，用户或订单他们都对应的一整个集群服务。max_id表示当前已经分配的最大id，step表示每次分配的步长。max_id会随着每一次分配id而增加。

这种方式的缺点是应用向第三方申请id有网络消耗，这段时间内应用会出现无主键可用的情况。

与第三方结合的多segment策略

双Buffer写入，向第三方服务申请两个segment放入本地缓存。避免出现应用在向第三方申请主键这段期间没有主键可用的情况

扩展点：

• 比较依赖DB，上方max_id 和step这两个字段都是保存在数据库的。我们可以保存在其他存储方式
• 第三方应用宕机，在我服务中双buffer中的id使用完之前重新提供服务，这样问题都不大。所以我服务中保存的buffer个数可以多一些，进而提高容错性

雪花算法详解

雪花算法使用8字节的二进制序列来生成一个主键

• 41bit的时间戳为主体，时间戳位保证趋势递增，放在最高位；

• 10bit的工作进程位标识服务器中运行的进程，而不是标识机器，需要应用自行扩展；

• 12bit序列号位是用来区分单位时间内 单机器内的自增序列。

而在具体实现时，雪花算法实际上只是提供了一个思路，并没有提供现成的框架。比如ShardingSphere中的雪花算法就是这样生成的。

时间戳位问题

41bit的时间戳为主体，时间戳位保证趋势递增，放在最高位；

时间戳位存在时钟回拨的问题。

一台服务器上，获取时钟只能依赖于内核的电信号维护，而电信号很难保持稳定。在高并发场景下获取高精度的时间戳有时会往前跳，有时会往回拨。

一旦时钟回拨就有可能产生重复的id。

各个框架的雪花算法都有对时钟回拨的问题做相应的处理，基本思路就是记录上一次生成主键的时间lastMilliseconds，和当前时间进行比较，如果lastMilliseconds大于当前时间就表示出现了时钟回拨，处理方式要么sleep()一段时间，要么直接抛异常。就比如ShardingSPhere的SnowFlake雪花算法就是sleep()，而cosID_SnowFlake就是抛异常

// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithm
@SneakyThrows(InterruptedException.class)
private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {
    //  上一次生成主键的时间 和 当前时间进行比较
    if (lastMilliseconds <= currentMilliseconds) {
        return false;
    }
    long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;
    Preconditions.checkState(...);
    // 解决时钟回拨的方式采用sleep()
    Thread.sleep(timeDifferenceMilliseconds);
    return true;
}

// 全类名 me.ahoo.cosid.snowflake.AbstractSnowflakeId
public synchronized long generate() {
    long currentTimestamp = this.getCurrentTime();
    // 时钟回拨
    if (currentTimestamp < this.lastTimestamp) {
        // 抛异常
        throw new ClockBackwardsException(this.lastTimestamp, currentTimestamp);
    } else {
        // 序列号处理 不是同一个单位时间点&&值>2^12 就重置0
        if (currentTimestamp > this.lastTimestamp && this.sequence >= this.sequenceResetThreshold) {
            this.sequence = 0L;
        }
		// 序列号位自增
        this.sequence = this.sequence + 1L & this.maxSequence;
        if (this.sequence == 0L) {
            currentTimestamp = this.nextTime();
        }

        this.lastTimestamp = currentTimestamp;
        long diffTimestamp = currentTimestamp - this.epoch;
        if (diffTimestamp > this.maxTimestamp) {
            throw new TimestampOverflowException(this.epoch, diffTimestamp, this.maxTimestamp);
        } else {
            // 时间戳 | 进程号 | 序列位
            return diffTimestamp << (int)this.timestampLeft | this.machineId << (int)this.machineLeft | this.sequence;
        }
    }
}

上方只能处理单台服务器上的时钟回拨，如果是多台服务器一个集群，就无法保证时间戳的统一了。

可以为每个应用配置一个工作进程位来防止不同服务器之间的主键冲突。但是万一应用没有配置嘞？大部分应用不会为了一个雪花算法去单独考虑如何分配工作进程位。

也可以使用ntpd这样的时间同步服务来把多个服务器的时间同步一下。但同样的不会有人仅仅为了雪花算法去这么做

第三种方案是将时间戳从本地扔到第三方服务上去，比如zookeeper，这样多个服务就可以根据共同的时间戳往前推进，省了服务器之间同步时间的麻烦。美团的leaf就是这么做的。缺点是：给雪花算法添加强绑定；降低了效率，因为多了一个访问第三方的步骤。

这有变为了方案取舍、实现优化的头疼环节。就像整个分布式主键一样。

工作进程位问题

10bit的工作进程位标识服务器中运行的进程，而不是标识机器，需要应用自行扩展；它是分布式场景下，保证id不重复很重要的字段。

因为一台服务器上面可以运行多个进程实例，所以这个标识是工作进程的，而不能简单理解为标识机器。工作进程是需要各个应用自己设定值，所以这里就分为了手动指定和自动获取两种方式。

对于一些小集群，就可以简单使用手动指定的方式在配置文件中为当前应用指定一个工作进程。但如果是大型集群，上百个微服务肯定就不能手动指定了。

现在就有一个思路，把MachineId(比如ip+端口)当做一个短的并发不是很高的分布式主键来处理，用其他分布式主键生成的方式生成工作进程位。我们现在需要依赖于一个工作进程位来生成分布式唯一主键，然后现在又要依赖于一个分布式唯一主键生成策略来生成工作进程位，完美闭环！鸡生蛋 蛋生鸡问题。

首先工作进程位是不需要考虑高并发问题，通常工作进程位只需要在一个应用启动时分配一个就可以了，应用的运行过程中不需要什么变化。所以工程进程位每次单步推进，申请一次，分配一个就行

其次工程进程位有一个天然的就带有唯一性的因素，比如使用ip地址，如果服务器运行多个应用那么也可以使用ip+端口区分。所以工作进程位天生就有很多唯一性因素，不需要像雪花算法那样去设计复杂的结构。

最后工作进程位的分配需要保持稳定。工作进程要与一个应用建立绑定关系。给一个应用分配工作进程号位之后如果应用崩溃了，重启服务之后所生成的雪花算法还是需要保持一个稳定的区分度。所以可以使用一个本地缓存保存这个应用的工作进程位，应用重启后，还需要保持，那么这个缓存可以持久化到本地文件中。

其实把这几个方面想明白了，Cosid当中的工作进程位分配机制也就大致成型了。

序列号位问题

序列号位就是一个连续性问题。就比如上文中的结合分库分表的问题。

如果不是一个单位时间内，那么就将序列为重置为0，进而导致了我们使用取模分片策略使得数据分配不均匀。

根据雪花算法扩展基因分片法

业务场景，对User用户表进行分库分表，最简单的处理就是根据userId作为分片键，之后每次查询都根据userId这个分片键来进行查询。但用户登录这个场景嘞？此时只有一个用户名，你甚至都不知道这个用户名是否存在，难道就只能全路由查询？这肯定是不能接受的。

此时就可以使用基因法的分片算法来解决这个问题。它的基础思想是再给用户分配userId时，就把用户名当中的某种序列信息插入到userId当中。从而保证userId和用户名可以按照某一种对应规则分到同一个分片上。这样就可以根据用户名确定对应的用户信息在哪一个分片上

具体在实现时，可以参照雪花算法的实现。

@Test
public void testGene() {
    // 初始值
    Long userId = 1257458L;
    String userName = "testroy";
    // 基因序列位数
    int dataSize = 3;

    //掩码，二进制表述为全部是1.  111
    int mask = ((1 << dataSize) - 1);
    // 只取 datasize 个bit位
    long userGene = userName.hashCode() & mask;
    // 给ID添加用户名的基因片段后的新ID，保持了原id的一致性
    long newUserId = (userId << dataSize) | userGene;

    // 对新用户id对8取模进行数据分片
    long actualNode = newUserId % 8;
    System.out.println("用户信息实际保存的分片：" + actualNode);
    long userNode = (userName.hashCode() & mask) % 8;
    System.out.println("根据用户名判断，用户信息可能的分片：" + userNode);
}

用户信息实际保存的分片：2
根据用户名判断，用户信息可能的分片：2