分布式全局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解決方案