UUID的弊端以及雪花算法

一、问题

为什么需要分布式全局唯一ID以及分布式ID的业务需求

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识

• 如在美团点评的金融、支付、餐饮、酒店;
• 猫眼电影等产品的系统中数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息;
• 特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。

此时一个能够生成全局唯一ID的系统是非常必要的

ID生成规则部分硬性要求

①全局唯一

即不能出现重复ID号

②趋势递增

在Mysql的InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用的是BTree的数据结构作为存储索引数据，在主键的选择上我们应该尽量使用有序的主键保证写入性能

③单调递增

保证下一个ID一定大于上一个ID，如事务版本号、排序等特殊要求

④信息安全

如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可:如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，需要ID无规则不规则，让竞争对手不好猜

⑤含时间戳

在开发中能快速了解这个分布式id生成的时间

ID号生成系统的可用性要求

①高可用

发一个获取分布式ID的请求，服务器要保证99.999%的情况下能给我返回一个分布式ID

②低延迟

返回的速度要快

③高QPS（抵抗高访问）

比如一秒内10万个，需要服务器能抵抗住并且生成10万个分布式ID

二、一般通用方案

（一）UUID

jdk自带，生成36位字符，形式为8-4-4-4-12，包含4个连号－，对于单体式仅需满足唯一的话可以使用

• 好处：性能高，本地生成，无网络消耗
• 坏处：无序且字符串长，存入数据库会增大数据库压力，入数据库性能差。mysql官方推荐主键越短越好

索引， B+树索引的分裂

既然分布式id是主键，然后主键是包含索引的，然后mysql的索引是通过b+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b+树进行修改，因为UUID数据是无序的。

所以每一次UUID数据的插入都会对主键地的b+树进行很大的修改，这一点很不好。插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能

（二）数据库自增主键

数据库自增主键实现原理：数据库自增id和replace into实现的

REPLACE INTO的含义是插入一条记录，如果表中唯一索引的值遇到冲突，则替换老数据

那数据库自增ID机制适合作分布式ID吗? 答案是不太适合

1. 系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做? 假设现在只有一台机器发号是1,2.3.4.5(步长是1)，这个时候需要扩容机器一台。可以这样做，把第二台机器的初始值设置得比第一台超过很多，貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做? 简直是噩梦。所以系统水平扩展方案复杂难以实现。
2. 数据库压力还是很大，每次获取ID都得读写一次数据库，非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则(在高并发下，如果都去数据库里面获取id，那是非常影响性能的)

（三）Redis生成全局id策略

因为Redis是单线的天生保证原子性，可以使用原子操作INCR和INCRBY来实现

注意:在Redis集群情况下，同样和MySQL一样需要设置不同的增长步长，同时key一定要设置有效期

可以使用Redis集群来获取更高的吞吐量。

假如一个集群中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5，然后步长都是5。

各个Redis生成的ID为:

• A: 1,6,11,16,21
• B: 2,7,12,17,22
• C: 3,8,13,18,23
• D: 4,9,14,19,24
• E: 5,10,15,20,25

三、snowflake

（一）概述

官网：

https://github.com/twitter-archive/snowflake

Twitter的分布式自增ID算法

特点：

① 能够按照时间有序生成

②Snowflake算法生成id的结果是一个64bit大小的整数，为一个Long型，转化为字符串最多19位

③分布式系统内不会产生ID碰撞(由datacenter和workerld作区分) 并且效率较高。

（二）结构

bit表示 -，id一般为正，所以固定为0

时间戳位范围为0-2^41次方，大概是可以使用69年（从1970算起）

工作进程位最多为2^10，即1024个节点，包括5位datacenter和5位workerld作区分

12bit-序列号，序列号，用来记录同毫秒内产生的不同id。12位(bit) 可以表示的最大正整数是2^12-1=4059

（三）代码

/**
 * Twitter_Snowflake

 * SnowFlake的结构如下(每部分用-分开):

 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 

 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0

 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69

 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId

 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

 * 加起来刚好64位，为一个Long型。

 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {
    // ==============================Fields===========================================
    /** 开始时间截 (2020-08-28) */
    private final long twepoch = 1598598185157L;
 
    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;
 
    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;
 
    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
    /** 支持的最大数据标识id，结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 
    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;
 
    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;
 
    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;
 
    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 
    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    /** 工作机器ID(0~31) */
    private long workerId;
 
    /** 数据中心ID(0~31) */
    private long datacenterId;
 
    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;
 
    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;
 
    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31) 此方法是判断传入的机房号和机器号是否超过了最大值，即31，或者小于0
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
 
    // ==============================Methods==========================================
    /*
     * 核心方法
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        //1.获取当前的系统时间
        long timestamp = timeGen();
 
        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
 
        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            // sequence 要增1, 但要预防sequence超过 最大值4095，所以要 与 SEQUENCE_MASK 按位求与 
            // 即如果此时sequence等于4095，加1后为4096，再和4095按位与后，结果为0
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }
 
        //上次生成ID的时间截
        //把当前时间赋值给 lastTime, 以便下一次判断是否处在同一个毫秒内
        lastTimestamp = timestamp;
 
        //移位并通过或运算拼到一起组成64位的ID
         long id = ((timestamp - twepoch) << timestampLeftShift) // 时间戳减去默认时间 再左移22位 与运算
                | (datacenterId << datacenterIdShift) // 机房号 左移17位 与运算
                | (workerId << workerIdShift) // 机器号 左移12位 与运算
                | sequence; // 序列号无需左移 直接进行与运算
        return id;
    }
 
    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

（四）优缺点

优点:

毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。可以根据自身业务特性分配bit位，非常灵活。

缺点:

依赖机器时钟，如果机器时钟回拨，会导致重复ID生成在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况(此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会亚格要求递增，90%的需求都只要求趋势递增)

缺点的解决方案

可以参照以下两个来进行机器时钟的同步

• 百度开源的分布式唯一ID生成器UidGenerator
• Leaf--美团点评分布式ID生成系统