分布式全局id

前言

假设有两台服务器做集群，当同一时间分别有一个请求访问两台服务器执行下订单操作，那么可能会产生订单号重复的问题。

这时就需要引入分布式全局id的概念，在分布式情况下生成全局id，确保唯一性。

高并发情况下分布式全局id生成有多种方法，本文主要讲以下四种

1.利用全球唯一的UUID生成订单号

2.基于数据库自增或者序列生成订单号

3.基于redis生成

4.snowflake算法

一般像订单id，就需要用到分布式全局id的概念。

生成分布式全局id策略：

1.全局唯一性。

2.安全性，不能很容易的被人猜到。

3.趋势递增性。

订单号的命名规则比如：“业务编码+时间戳+机器编号【前四位】+随机4位数+毫秒数”。

UUID生成订单号

UUID是指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的。

UUID组成部分：当前日期和时间+时钟序列+随机数+全局唯一的IEEE机器识别号。

全局唯一的IEEE机器识别号：如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。

优点：

简单，代码方便。
生成ID性能非常好，基本不会有性能问题。
全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更等情况下，可以从容应对。
不占宽带。

缺点：

没有排序，无法保证趋势递增。
UUID往往是使用字符串存储，查询的效率比较低。
存储空间比较大，如果是海量数据，就需要考虑存储量的问题。
传输数据量大。

使用场景：数据库主键或者token。

数据库主键如果是用数字递增的话，当数据库集群，分表分库等情况下可能会导致重复问题。

数据库自增

利用数据库自增（mysql）或者序列号（oracle）方式实现订单号。

注意：在数据库集群环境下，默认自增方式存在问题，因为都是从1开始自增，可能会存在重复，应该设置每台不同数据库自增的间隔方式不同。

由此就引申出一个问题，数据库集群的话，如何解决自增id幂等性问题？

答：设置自增的步长。例如有两台mysql的情况下，设置步长为2，一台起始值为0，一台起始值为1，这样子设置的话一台id为偶数，一台为奇数。当有三台的时候，可以设置步长为3；那么当一开始用的是两台，之后想扩展成三台的时候，由于之前的数据id已经根据原先的步长生成了，就很难去扩展，这就是缺点，需要事先定好集群数量，设置好步长，之后就不能再扩展。

优点：

简单，代码方便，性能可以接受。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

不同数据库语法和实现不同,数据库迁移的时候或多数据库版本支持的时候需要处理。
在性能达不到要求的情况下，比较难于扩展。
在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成，有单点故障的风险。
分表分库的时候会有麻烦。
占用宽带，因为需要连接数据库。

查询自增的步长

SHOW VARIABLES LIKE 'auto_inc%'

修改自增的步长

SET @@auto_increment_increment=10;

修改起始值

SET @@auto_increment_offset=5;

Redis

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

优点：

不依赖于数据库,灵活方便，且性能优于数据库。
数字id天然排序，对分页或者需要排序的结果很有帮助。

缺点：

如果系统中没有redis，还需要引入新的组件，增加系统复杂度。
需要编码和配置的工作量比较大。
占宽带，因为需要连接redis。

注意：在redis集群情况下，同样和数据库一样需要设置不同的增长步长，用时key一定要设置有效期。

订单号可以设置成当前日期+5位自增id

例如2019100309150101+00001

日期可以精确到毫秒，自增id不足5位数可以补0，+号是用来区分，实际上是没有+号的。

这样子设置，只要在同一毫秒，订单数不超过99999，就不会有问题。

也可以把日期设置成精确到秒，同一秒，订单数不超过99999，也不会有问题。

在并发数超级大的情况下，由于redis是单线程的，可能会导致阻塞，解决的办法是，提前生成好订单号存起来，需要用到的时候直接取出来，这样子是不会阻塞的。

实践

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.mayikt</groupId>
    <artifactId>order-days-105</artifactId>
    <version>0.0.1-SNAPSHOT</version>

    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.0.1.RELEASE</version>
    </parent>
    <dependencies>
        <!-- SpringBoot整合Web组件 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <!-- SpringBoot对Redis支持 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
        </dependency>

    </dependencies>

</project>

配置文件application.yml

spring:
  redis:
    database: 1
    host: localhost
    port: 6379
    password: 123456
    jedis:
      pool:
        max-active: 8
        max-wait: -1
        max-idle: 8
        min-idle: 0
    timeout: 10000

新建controller类

package com.example.distributedglobalid;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.support.atomic.RedisAtomicLong;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.TimeUnit;

@RestController
public class OrderController {
    @Autowired
    private RedisTemplate redisTemplate;

    @RequestMapping("/order")
    public String order(String key){
        RedisAtomicLong redisAtomicLong = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        //-------这里的设置是需要在redis设置的，否则在这里设置的话，每次执行都设置了
        //设置过期时间，24小时；过期之后会从新累计
        redisAtomicLong.expire(24,TimeUnit.HOURS);
        //设置起始值
        //redisAtomicLong.set(2);      
        //设置步长+10
        redisAtomicLong.addAndGet(9);
        long incrementAndGet = redisAtomicLong.incrementAndGet();
        //不足5位数补0
        String id = String.format("%1$05d", incrementAndGet);
        return addPrefix(id);
    }

    /**
     * 拼接日期前缀
     * @param id
     * @return
     */
    public static String addPrefix(String id){
        return new SimpleDateFormat("yyyyMMddHHmmss").format(new Date())+id;
    }

}

启动项目

打开浏览器访问http://localhost:8080/order?key=asdaa

可以一直刷新浏览器页面看效果。

snowflake(雪花)算法

推特开源的id生成算法，结果是一个long类型的id，其核心算法是：

高位随机+毫秒数+机器码(数据中心+机器id)+10位的流水号码。

snowflake生产的id是一个18位数的long型数字。每毫秒最多生成4096个id，每秒可达4096000个。

测试类

package com.example.distributedglobalid;

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 -
 * 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。
 * 41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，
 * SnowFlake每秒能够产生26万ID左右。
 */
public class Snowflake {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 机器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)
     */
    public Snowflake(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() {
        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 = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        // 上次生成ID的时间截
        lastTimestamp = timestamp;

        // 移位并通过或运算拼到一起组成64位的ID
        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();
    }

    // ==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        Snowflake idWorker = new Snowflake(0, 0);
        for (int i = 0; i < 100; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

一般生成分布式全局id，推荐使用雪花算法，效率高，不需要连接数据库等，不占宽带。

分布式全局id

前言

UUID生成订单号

数据库自增

Redis

snowflake(雪花)算法

继续阅读

分布式Id生成方案

Java 分布式主键生成方案雪花算法（snowflake）

(SpringBoot)Hibernate主键生成策略-雪花算法

生成分布式ID算法 -- 雪花算法

MyBatis Plus 源码 | 主键ASSIGN_ID生成方式的雪花改进版算法分析MyBatis Plus中主键生成方式ASSIGN_ID的算法分析

分布式唯一ID一什么是分布式唯一ID，有些什么需求二有哪些分布式唯一主键生成方案，各自优缺点三雪花算法如何解决时钟回拨问题

高并发情况下，如何生成分布式全局id

压倒90%程序员的面试题：分库分表有哪些弊端？表的数据太大的时候都会习惯性的去分库分表，分库分表会带来哪些弊端你了解过吗

关于生成订单号规则的一些思考

JPA中使用 @GenericGenerator 自定义方式生成主键 ID

高并发情况下分布式全局ID高并发情况下分布式全局ID

高并发情况下分布式全局Id生成

雪花算法源码分析

雪花算法（SnowFlake）的升级版可靠实现，解决时钟回拨抛出异常导致业务中断的问题传统算法的缺点解决方法不足代码

雪花算法snowflake分布式id生成原理详解，以及对解决时钟回拨问题几种方案讨论

分布式中id解决方案（含雪花算法）分布式id解决方案