分布式ID

雪花算法（时间戳41+机器编号10+自增序列号10）

作用：希望ID按照时间进行有序生成

原理：

即一台带有编号的服务器在毫秒级时间戳内生成带有自增序号的ID,这个ID保证了自增性和唯一性

雪花算法根据结构的生成ID个数的上线时，每毫秒最多能生成2^12次方个ID即4096个

总共64个Bit位，第一个位置不用，使用41个比特位作为时间戳（可以使用69年，单位时毫秒级别）、使用10个bit为作为机器ID(机器编号），最后使用12个比特位作为自增ID

特点：

1、按照时间递增

2、因为分布式ID采用了机器编号组成，因此，就算进行分布式部署，由于机器编号不同，最后生成的ID也不同，做到了不重复

3、1毫秒产生4096个id，那么1秒内就能产生400万左右个的ID

实现方式：

now:生成id的时间戳

workId:机器编号id

n:序列号

大概生成伪代码

now=System.now();//获取当前时间戳
if(now==last){last //为前一个生成id的时间戳
    n++;
  if(n>4069){//判断序列号是否超过每毫秒内的最大值   
    now=nextTime();
      n=0;;
    

}
}else{
  n=0;
}

long id=(now<<22)|(workId<<12)|n; //去或运算

实现方式：可以使用Redis来完成

@Component
public class RedisIdWorker {
    /**
     * 开始时间戳
     */
    private static final long BEGIN_TIMESTAMP = 1640995200L;
    /**
     * 序列号的位数
     */
    private static final int COUNT_BITS = 22;
    private static final int work_id = 452;//机器id

    private StringRedisTemplate stringRedisTemplate;

    public RedisIdWorker(StringRedisTemplate stringRedisTemplate) {
        this.stringRedisTemplate = stringRedisTemplate;
    }

    public long nextId(String keyPrefix) {
        // 1.生成时间戳
        LocalDateTime now = LocalDateTime.now();//需要获得毫秒级的时间戳
        long nowSecond = now.toEpochSecond(ZoneOffset.UTC);
        long timestamp = nowSecond - BEGIN_TIMESTAMP;//得到毫秒

        // 2.生成序列号
        // 2.1.获取当前日期，精确到天
        String date = now.format(DateTimeFormatter.ofPattern("yyyy:MM:dd"));
        // 2.2.自增长
        long count = stringRedisTemplate.opsForValue().increment("icr:" + keyPrefix + ":" + date);

        // 3.拼接并返回
        return timestamp << COUNT_BITS | work_id<<12|count;
        //时间戳左移22位，机器id左移12位，序列号
    }
}

Redis实现全局唯一Id（时间戳+自增序号）

为了增加ID的安全性，我们可以不直接使用Redis自增的数值，而是拼接一些其它信息：

时间戳：31bit，以秒为单位，可以使用69年

序列号：32bit，秒内的计数器，支持每秒产生2^32个不同ID

将时间戳转化为日期格式，然后作为key好处

• 1、首先就是通过redis的key不能重复来进行计算，每秒内进行自增
• 2、便于统计每天、每月的一个id生成量

分布式ID生成方式

• 1、UUID
• 2、数据库自增ID
• 3、Redis
• 4、雪花算法

UUID:

缺点：

• 生成不是自增的，会导致插入数据库的效率较慢
• 2、生成所需要的空间较大

数据库自增

数据库自增ID:分库分表情况下会重复

解决方式：单独使用一张表（主要字段，id,其他字段）来生成分布式ID

表结构如下:

create table order_id(
 id bigint(20) unsigned not null auto_increment,
  stub char(1) not null default '',
  primary key (id),
  unique key sub(stub)
  )
  

begin;
replace into order_id stub values('b');//如果数据库中有字段b的值那么会先将原来字段删除，再进行插入，否则直接插入
select Last_insert_id();//通过这个查询拿到最后一个ID
commit;

缺点：

在高并发、数据量大的情况下性能比较差

对于高并发方面：比如每秒几十万的生成，那么需要同时去数据库执行这个生成ID，数据库扛不住

第二个就是，每次生成ID都需要去访问数据库，性能肯定不会太好，就算id表的数据很少基本就是用1条，但需要和数据库交互性能本就会受影响

当然解决上面方法痛点可以采用集群模式

比如可以将请求负载均衡到多个数据库，数据库A自增比如只生成奇数1，3，5，数据库只生成偶数比如2，4，6

这种方式的问题：

• 1、不是绝对的ID递增
• 2、对于高并发情况：如果要使用数据库方式，那么就只有一直加机器，让其负载均衡

• • 如果一开始并发量不大，我们就使用两台机器来做分布式自增id，但是后面并发量变大了，两台并发量扛不住，那只有加机器，那么我们可以先拿到此时库中最大的id（比如10000），然后将所有数据库的自增起始值设置为大于这个值比如（10w)的，然后再设置对应的步长，但是这个方式设置，需要对数据库进行重启（所以说这种方式在高并发情况下并不合适）

雪花算法

public class SnowflakeIdWorker{
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1288834974657L;
 
    /** 机器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;
 
    /**
     * 构造函数
     *
     * @param workerId
     *            工作ID (0~31)
     * @param datacenterId
     *            数据中心ID (0~31)
     */
    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;
    }
 
    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
 
        // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        //这里是处理时间回波的方案：为什么会有：因为我们的ID是对当前时间具有比较高的依赖性
        //所以一半会采取将生成分布式ID的服务器的时间和时间服务器的时间进行同步，
        //如果发现本地生成ID的这台服务器的时间走快了，那么再去时间的时候就会有时间回退到之前
        //比如现在系统是12：30：05，然后准确时间是20：30：00
        // 那么时间就会回退到30：00那么如果不额外处理就会造成ID重复的问题
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format(
                            "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                            (lastTimestamp - timestamp)));
        }
 
        // 如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            //mask:4095即二进制12个1（即如果序列号小于4095时候就是本身，
            //如果超过了4096了比如4096那么后面12位就是0，那么做与运算之后序列号就变为0
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                //超过了4096，那么就等下一秒
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }
 
        // 上次生成ID的时间截
        lastTimestamp = timestamp;
 
        // 移位并通过或运算拼到一起组成64位的ID
        //timestamp - twepoch（twepoch一般设置为服务启动的一个初始时间，因为雪花算法最多69年
        //减去之后时间就可以长一点，比如初始时间2024年的，那么就可以用用到2024+69
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
 
    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @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();
    }
 
    //测试方法
    public static void main(String[] args) {
 
        // 假设我们有一个工作机器ID为1，数据中心ID为1的环境
        long workerId = 1L;
        long datacenterId = 1L;
        
        // 创建一个SnowflakeIdWorker实例
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(workerId, datacenterId);
        
        // 生成并打印10个ID作为示例
        for (int i = 0; i < 10; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
 
}

时间回拨：

• 如果回波时间很短比如（<=100ms)

• • 比较短可以考虑直接sleep一段时间（等时间大于原来的时间后继续生成ID)

• 如果回拨时间适中比如（100ms<s<=1s)

• • 我们可以采用缓存机制，即缓存下每一毫秒生成的最大id，可以使用hashmap等结构
  • 然后出现时间回波后就只需要拿到最后那一毫秒的最大ID,然后再此基础上进行自增
  • 时间太长不太适合：比较占内存

• 如果时间比较长，比如（1s<s<=5s)

• • 这台机器上出现时间回波，那我就让客户端进行重试策略，去另一个分布式ID服务上去拿ID

• 当时间回拨非常长比如（5<s):

• • 就可以考虑将这个服务进行下线，然后将这台机器时间不同好之后又重新上线

美团Leaf分布式ID生成方案（号段模式）

提供了两种方式：

Leaf 提供了 号段模式 和 Snowflake(雪花算法) 这两种模式来生成分布式 ID。并且，它支持双号段，还解决了雪花 ID 系统时钟回拨问题。不过，时钟问题的解决需要弱依赖于 Zookeeper（使用 Zookeeper 作为注册中心，通过在特定路径下读取和创建子节点来管理 workId） 。

Leaf 的诞生主要是为了解决美团各个业务线生成分布式 ID 的方法多种多样以及不可靠的问题。

Leaf 对原有的号段模式进行改进，比如它这里增加了双号段避免获取 DB 在获取号段的时候阻塞请求获取 ID 的线程。简单来说，就是我一个号段还没用完之前，我自己就主动提前去获取下一个号段（图片来自于美团官方文章：《Leaf——美团点评分布式 ID 生成系统》）。

号段模式

核心：数据库中一次自增一段的ID,然后本地程序拿到这一段ID之后，使用程序进行自己维护自增ID,比如一次访问数据库拿到数据范围是1000~2000，那么我们程序就在这个范围进行自增

优点：

• 支撑高并发：
• leaf服务可以很方便的进行线性扩展，性能完全能支撑大多数业务场景
• ID号码是趋势递增的8byte的64位数字。满足上述数据库存储的主键要求
• 3、容灾性高：Leaf服务内部有号段缓存，几十DB宕机了，短时间内Leaf服务任然能正常对外提供服务（因为每次leaf服务从DB中拿的是一段ID)
• 4:灵活性强，比如这里max_id,步长step等可以自定义，直接修改
• 5、如果后面并发量非常大，那么我们就直接分表就完事了，让每个业务类型使用一张表，一个服务器，即一个表一个业务

缺点：

• 1、id是有规律的，别人可以根据id可以分析出每天的订单量大概在多少，可能会造成数据泄露
• 2、数据波动比较大（即在去和数据库进行交互去获取一段的ID的那个时刻，由于各个服务都去拿取这个数据，由于每次获取id后需要进行一个数据的更行操作，所以数据库会有一个行锁，虽然也比较快，但是在高并发情况下，就会导致在取id这一时刻，用户的响应时间会增加）
• 3、DB宕机，还是

优化段号模式（双段号模式）：

上面这个方案的优化：美团Leaf方式---缓存双Buffer

• 当leaf服务器原来的ID用了10%的时候那就取访问数据库取下一段，重复这个操作，这样处理就比较好的处理

当让也可以使用Redis来完成自增设计，和上面这个设计方式其实也类似

这两种方式都有一个共同的问题：就是自增ID需要依赖于第三方库，比如Mysql,Redis等

大厂基本就是基于雪花算法来进行封装对应的方法的

时钟回波的解决方案：默认的雪花算法时钟回波问题时就抛一个异常，但是对于每个公司来说处理方式是不同的，大多数公司是另外的处理方式，

雪花算法模式

还解决了雪花 ID 系统时钟回拨问题。不过，时钟问题的解决需要弱依赖于 Zookeeper（使用 Zookeeper 作为注册中心，通过在特定路径下读取和创建子节点来管理 workId） 。