对雪花算法的初识到热恋

分库分表常见主键id生产策略讲解

引入什么技术都是会存在一定的风险，分库分表也不会是例外。在不同的数据节点生成一个唯一主键是一个难题，一张逻辑表x_order会被拆分成多个真实表x_order_n，然后这些表又被分散到不同的库中db_0、db1、db2各个表自增键由于没有办法相互的感应会产生重复的主键，这就没有办法满足分库分表对主键的全局唯一的要求了。

尽管可以使用分片表的自增主键初始值和步长来解决，但是这样会导致运维成本提高，可扩展性差，这种方式不太可取。

业界常用ID解决方案

UUID： 性能非常高，没有网络消耗。缺点就是无序的字符串，不具备有趋势自增的特性，UUID太长也不便于存储，浪费存储空间，所以很多的场景是不使用的

Redsi发号器： 利用Redis的INCR和INCRBY来实现，原子操作，线程安全，性能比Mysql强劲。缺点就是需要占用网络资源，增加系统复杂度。

Snowflake雪花算法： 它是twitter开源式的分布式ID生成算法，代码实现简单，而且不占用宽带，数据的迁移不会受到影响，生成的id里包含有时间戳，所以生成的id按照时间进行递增，部署多台服务器的话，需要保证系统时间是一样的。缺点就是依赖系统时钟。

UUID

进入UUID的主键生成实现类，发现它只有一个规则，那就是UUID.randomUUID()，可以看出是多么的牛啊。UUID虽然可以做到全局的唯一性，但还是不推荐作为主键，因为我们知道，在实际业务中主键一般为整型，而UUID是生成32位的字符串。它对MYSQL的性能消耗会比较大，而且MYSQL也建议主键要尽量的短，UUID主键的无序性还会导致数据位置的频繁变动，严重的影响了性能。

public final class UUIDShardingKeyGenerator implements ShardingKeyGenerator {

    private Properties properties = new Properties();


    public UUIDShardingKeyGenerator() {

    }


    public String getType() {

        return "UUID";

    }


    public synchronized Comparable<?> generateKey() {

        return UUID.randomUUID().toString().replaceAll("-", "");

    }


    public Properties getProperties() {

        return this.properties;

    }


    public void setProperties(Properties properties) {

        this.properties = properties;

    }

}

Snowflake（雪花算法）

雪花算法是默认使用主键生成方案，生成一个64bit的长整型数据。sharding-jdbc中雪花算法生成的主键主要是由四个部分组成，1bit符号位、41bit时间戳位、10bit机器id，12bit序列号。

符号位（1bit）

在Java当中，Long型最高的位是符号位，也就是正数是0，负数是1，一般id生成都为正数，所以的话默认是0。

时间戳位（41bit）

41位的时间戳占41个bit，毫秒数是2的41次幂，而一年的总毫秒数就为1000L * 60 * 60 * 24 * 365，为服务上线的时间毫秒级时间戳（当前时间-服务第一次上线的时间）。

工作机器id(10bit)

表示一个唯一的工作进程，它的默认值是0，可以通过key-generator.props.worker.id来进行设置

序列号位（12bit）

可以允许同一毫秒生成2^12=4096个id，理论上一秒就可以生成400万个id。

时钟回拨

了解了雪花算法主键的组成后可以发现，这是一种严重的依赖服务器的时间算法，这时候依赖服务器时间就会遇到一个棘手的问题就是-时钟回拨。

为啥会出现时钟回拨这种现象

据我们所知，在互联网中有一种网络的时间协议叫ntp，专门是用来进行同步或者是用来校准网络计算机的时间。这就是手机现在不用手动校对时间的原因。

当硬件因为某一些原因导致时间快或者是慢了，这个时候就需要使用ntp服务来对时间进行校准，在做校准的时候就有可能发生服务器时钟的跳跃或者是回拨这些问题。

雪花算法怎么样解决时钟回拨问题

上面提到服务器时钟回拨问题可能会导致重复的id产生，所以在SNOWFLAKE方案对雪花算法进行了改进，添加了一个最大的容忍时钟回拨毫秒数。

当时钟回拨的时间超过最大容忍毫秒数的阀值的话，就直接程序报错。如果在可以容忍的范围内的话，就默认使用了分布式的主键生成器，等待时钟同步到最后一次生成主键时间后才继续开始工作。

最大容忍的时钟回拨毫秒数默认是0，max.tolerate.time.difference.milliseconds来设置。

public final class SnowflakeShardingKeyGenerator implements ShardingKeyGenerator{

    @Getter

    @Setter

    private Properties properties = new Properties();

    

    public String getType() {

        return "SNOWFLAKE";

    }

    

    public synchronized Comparable<?> generateKey() {

     /**

      * 当前系统时间毫秒数 

      */ 

        long currentMilliseconds = timeService.getCurrentMillis();

        /**

         * 判断是否需要等待容忍时间差，如果需要，则等待时间差过去，然后再获取当前系统时间 

         */ 

        if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {

            currentMilliseconds = timeService.getCurrentMillis();

        }

        /**

         * 如果最后一次毫秒与 当前系统时间毫秒相同，即还在同一毫秒内 

         */

        if (lastMilliseconds == currentMilliseconds) {

         /**

          * &位与运算符：两个数都转为二进制，如果相对应位都是1，则结果为1，否则为0

          * 当序列为4095时，4095+1后的新序列与掩码进行位与运算结果是0

          * 当序列为其他值时，位与运算结果都不会是0

          * 即本毫秒的序列已经用到最大值4096，此时要取下一个毫秒时间值

          */

            if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {

                currentMilliseconds = waitUntilNextTime(currentMilliseconds);

            }

        } else {

         /**

          * 上一毫秒已经过去，把序列值重置为1 

          */

            vibrateSequenceOffset();

            sequence = sequenceOffset;

        }

        lastMilliseconds = currentMilliseconds;

        

        /**

         * XX......XX XX000000 00000000 00000000 时间差 XX

         *    XXXXXX XXXX0000 00000000 机器ID XX

         *               XXXX XXXXXXXX 序列号 XX

         *  三部分进行|位或运算：如果相对应位都是0，则结果为0，否则为1

         */

        return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;

    }

    

    /**

     * 判断是否需要等待容忍时间差

     */

    @SneakyThrows

    private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {

     /**

      * 如果获取ID时的最后一次时间毫秒数小于等于当前系统时间毫秒数，属于正常情况，则不需要等待 

      */

        if (lastMilliseconds <= currentMilliseconds) {

            return false;

        }

        /**

         * ===>时钟回拨的情况（生成序列的时间大于当前系统的时间），需要等待时间差 

         */

        /**

         * 获取ID时的最后一次毫秒数减去当前系统时间毫秒数的时间差 

         */

        long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;

        /**

         * 时间差小于最大容忍时间差，即当前还在时钟回拨的时间差之内 

         */

        Preconditions.checkState(timeDifferenceMilliseconds < getMaxTolerateTimeDifferenceMilliseconds(), 

                "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastMilliseconds, currentMilliseconds);

        /**

         * 线程休眠时间差 

         */

        Thread.sleep(timeDifferenceMilliseconds);

        return true;

    }

    

    // 配置的机器ID

    private long getWorkerId() {

        long result = Long.valueOf(properties.getProperty("worker.id", String.valueOf(WORKER_ID)));

        Preconditions.checkArgument(result >= 0L && result < WORKER_ID_MAX_VALUE);

        return result;

    }

    

    private int getMaxTolerateTimeDifferenceMilliseconds() {

        return Integer.valueOf(properties.getProperty("max.tolerate.time.difference.milliseconds", String.valueOf(MAX_TOLERATE_TIME_DIFFERENCE_MILLISECONDS)));

    }

    

    private long waitUntilNextTime(final long lastTime) {

        long result = timeService.getCurrentMillis();

        while (result <= lastTime) {

            result = timeService.getCurrentMillis();

        }

        return result;

    }

}

可以看出最后的主键生成时间（lastMilliseconds）与当前（currentMilliseconds）做比较，如果生成的时间大于当前时间的话，这就说明了时钟回调了。那么这时会接着判断两个时间的差，看下是否在设置在最大的容忍时间范围内，在范围内就睡眠差值的时间，大于差值那就直接报异常。

百度UidGenerator

UidGenerator算法是对雪花算法的改进版。UidGenerator组成是由：sign(1bit)+delta seconds(28bits)+worker node id(22bits)+sequence(13bits)。

UidGenerator可以保证指定的机器同一时间某一并发序列是唯一的，并由此生成一个64bits的唯一id。

UidGenerator跟雪花算法不一样，它可以自定义时间戳，工作机器id与序列号各部位的位数，用于不同的场景。

1.sign：固定的符号标识，生成的UID为正数。

2.delta seconds：当前的时间

3.worker id：机器id，内置实现是在启动的时候由数据库分配，默认分配策略为：用后就弃掉。

4.sequence：每秒下的并发序列，13bits可以支持每一秒8192个并发。

UidGenerator两种方式

DefaultUidGenerator： 通过DefaultUidGenerator来实现的，对于时钟回拨问题比较的简单，根据业务情况来调整字段占用的位数。

CachedUidGenerator： CachedUidGenerator是在DefaultUidGenerator进行改进的，利用了RingBuffer，它的本质是一个数组，数组里的每一个项都叫slot。而CachedUidGenerator是设计两个RingBuffer，一个是用于保存唯一id，一个保存flag。

CachedUidGenerator主要是通过以下的集中方式规避了时钟的问题和增强了唯一性

1、自增列：在每一次重启的时候workerid都会初始化，且它就是数据库自增的id，这样完美的实现每一个实例获取到的workerid都不一样，不会造成冲突

2、RingBuffer：不需要在每次取得ID都要计算分布式ID，而是利用RingBuffer数据结构预先生成若干个分布式ID来保存

3、时间递增：像雪花算法都是通过currentTimeMillis来获取时间，并比较，这样的话是很依赖服务器的时间，但是CachedUidGenerator的时间类型是AtomicLong，通过incrementAndGet方法来获取下一次的时间，这样就避免了对服务器时间的依赖，也就是时钟回拨的问题可以得到解决。

CachedUidGenerator通过缓存的这种方式来预先生成唯一ID列表，这种可以解决唯一ID所消耗的时间，但是也有不好的点就是，需要耗费内存来缓存这一部分ID的数据，如果访问量不是很大的情况下，提前生成的UID的时间戳可能是很早以前的。