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

原因:為什麼需要雪花算法

為什麼需要分布式全局唯一ID以及分布式ID的業務需求？叢集高并發情況下如何保證分布式唯一全局Id生成？

在複雜分布式系統中，往往需嬰對大量的資料和消息進行唯一辨別，如在美團點評的金融、支付、餐飲、酒店，貓眼電影等産品的系統中資料日漸增長，對資料分庫分表後需要有一個唯一ID來辨別一條資料或消息。特别一點的如訂單、騎手、優惠券也都雷要有唯一ID做辨別。此時一個能夠生成全局唯一ID的系統是非常必要的。

ID生成規則部分硬性要求

全局唯一：不能出現重複的ID号，既然是唯一-辨別，這是最基本的要求
趨勢遞增：在MySQL的InnoDB引擎中使用的是聚集索引，由于多數RDBMS使用Btree的資料結構來存儲索引資料，在主鍵的選擇上面我們應該盡量使用有序的主鍵保證寫入性能。
單調遞增：保證下一個ID一定大于上一個ID，例如事務版本号、IM增量消息、排序等特殊需求
資訊安全：如果ID是連續的，惡意使用者的扒取工作就非常容易做了，直接按照順序下載下傳指定URL即可。如果是訂單号就更危險了，競對可以直接知道我們一天的單量。是以在一些應用場景下，需要ID無規則不規則，讓競争對手否好猜。
含時間戳：這樣就能夠在開發中快速了解這個分布式id的生成時間。

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

高可用：發一個擷取分布式ID的請求，伺服器就要保證99.999%的情況下給我建立一個唯一分布式ID。
低延遲：發一個擷取分布式ID的請求，伺服器就要快，極速。
高QPS：假如并發一口氣10萬個建立分布式ID請求同時殺過來，伺服器要頂的住且一下子成功建立10萬個分布式ID。

一般通用方案

UUID

UUID(Universally Unique ldentifer)的标準型式包含32個16進制數字，以連了号分為五段，形式為8-4-4-4-12的36個字元，示例：550e8400-e29b-41d4-a716-446655440000

性能非常高：本地生成，沒有網絡消耗

如果隻是考慮唯一性，那就選用它吧

但是，入資料庫性能差

為什麼無序的UUID會導緻入庫性能變差呢？

無序，無法預測他的生成順序，不能生成遞增有序的數字。首先分布式ID一般都會作為主鍵，但是安裝MySQL官方推薦主鍵要盡量越短越好，UUID每一個都很長，是以不是很推薦。
主鍵，ID作為主鍵時在特定的環境會存在一些問題。比如做DB主鍵的場景下，UUID就非常不适用MySQL官方有明确的建議主鍵要盡量越短越好36個字元長度的UUID不符合要求。
索引，既然分布式ID是主鍵，然後主鍵是包含索引的，然後MySQL的索引是通過B+樹來實作的，每一次新的UUID資料的插入，為了查詢的優化，都會對索引底層的B+樹進行修改，因為UUID資料是無序的，是以每一次UUID資料的插入都會對主鍵地械的B+樹進行很大的修改，這一點很不好。插入完全無序，不但會導緻一-些中間節點産生分裂，也會白白創造出很多不飽和的節點，這樣大大降低了資料庫插入的性能。

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.

If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.

link

資料庫自增主鍵

單機

在單機裡面，資料庫的自增ID機制的主要原理是：資料庫自增ID和MySQL資料庫的replace into實作的。

REPLACE INTO的含義是插入一條記錄，如果表中唯一索引的值遇到沖突，則替換老資料。

這裡的replace into跟inset功能類似，不同點在于：replace into首先嘗試插入資料清單中，如果發現表中已經有此行資料（根據主鍵或唯一索引判斷）則先删除，再插入。否則直接插入新資料。

CREATE TABLE t_test(
    id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    stub CHAR(1) NOT NULL DEFAULT '',
    UNIQUE KEY stub(stub)
)

SELECT * FROMt_ test;

REPLACE INTO t_test (stub) VALUES('b');

SELECT LAST_INSERT_ID();

叢集分布式

那資料庫自增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

來源

Twitter的分布式自增ID算法snowflake

概述

Twitter的snowflake解決了這種需求，最初Twitter把存儲系統從MySQL遷移到Cassandra（由Facebook開發一套開源分布式NoSQL資料庫系統）。因為Cassandra沒有順序ID生成機制，是以開發了這樣一套全局唯一生成服務。

Twitter的分布式雪花算法SnowFlake ，經測試snowflake 每秒能夠産生26萬個自增可排序的ID

Twitter的SnowFlake生成ID能夠按照時間有序生成。
SnowFlake算法生成ID的結果是一個64bit大小的整數，為一個Long型（轉換成字元串後長度最多19）。
分布式系統内不會産生ID碰撞（由datacenter和workerld作區分）并且效率較高。

分布式系統中，有一些需要使用全局唯一ID的場景，生成ID的基本要求：

在分布式的環境下必須全局且唯一。

一般都需要單調遞增，因為一般唯一ID都會存到資料庫，而Innodb的特性就是将内容存儲在主鍵索引樹上的葉子節點而且是從左往右，遞增的，是以考

慮到資料庫性能，一般生成的ID也最好是單調遞增。為了防止ID沖突可以使用36位的UUID，但是UUID有一些缺點，首先他相對比較長，另外UUID一般是無序的。

可能還會需要無規則，因為如果使用唯一ID作為訂單号這種，為了不然别人知道一天的訂單量是多少，就需要這個規則。

結構

雪花算法的幾個核心組成部分：

SnowFlake可以保證：

所有生成的ID按時間趨勢遞增。
整個分布式系統内不會産生重複id（因為有DataCenterId和Workerld來做區分)

源碼

以下代碼僅供學習：

/**
 * Twitter_Snowflake
 * SnowFlake的結構如下(每部分用-分開):
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
 * 1位辨別，由于long基本類型在Java中是帶符号的，最高位是符号位，正數是0，負數是1，是以id一般是正數，最高位是0
 * 41位時間戳(毫秒級)，注意，41位時間戳不是存儲目前時間的時間戳，而是存儲時間戳的內插補點（目前時間戳 - 開始時間戳)
 * 得到的值），這裡的的開始時間戳，一般是我們的id生成器開始使用的時間，由我們程式來指定的（如下面程式SnowflakeIdWorker類的startTime屬性）。41位的時間戳，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
 * 10位的資料機器位，可以部署在1024個節點，包括5位datacenterId和5位workerId
 * 12位序列，毫秒内的計數，12位的計數順序号支援每個節點每毫秒(同一機器，同一時間戳)産生4096個ID序号
 * 加起來剛好64位，為一個Long型。
 */
public class SnowflakeIdWorker {
    /** 開始時間戳 (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 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() {
        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();
    }

    /** 測試 */
    public static void main(String[] args) {
        System.out.println("開始："+System.currentTimeMillis());
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 50; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
//            System.out.println(Long.toBinaryString(id));
        }
        System.out.println("結束："+System.currentTimeMillis());
    }
}

工程落地經驗

Hutool的Snowflake文檔

添加依賴

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-captcha</artifactId>
    <version>4.6.8</version>
</dependency>

示例程式：

import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil; 
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Component;

import javax.annotation.PostConstruct;

@Slf4j
@Component
public class IdGeneratorSnowflake{
    private long workerId = 0;
    private long datacenterId = 1;
    private Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);

    public synchronized long snowflakeId(){
        return snowflake.nextId();
    }

    public synchronized long snowflakeId(long workerId, long datacenterId){
        Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
        return snowflake.nextId();
    }

    public static void main(String[] args){
        IdGeneratorSnowflake idGenerator = new IdGeneratorSnowflake();
        System.out.println(idGenerator.snowflakeId());

        ExecutorService threadPool = Executors.newFixedThreadPool(5);
        for (int i = 1; i <= 20; i++){
            threadPool.submit(() -> {
                System.out.print1n(idGenerator.snowflakeId());
            });
        }

        threadPool.shutdown();

    }
}

優缺點

優點：

毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。

不依賴資料庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的。

可以根據自身業務特性配置設定bit位，非常靈活。

缺點：

依賴機器時鐘，如果機器時鐘回撥，會導緻重複ID生成。

在單機上是遞增的，但是由于設計到分布式環境，每台機器上的時鐘不可能完全同步，有時候會出現不是全局遞增的情況。

（此缺點可以認為無所謂，一般分布式ID隻要求趨勢遞增，并不會嚴格要求遞增，90%的需求都隻要求趨勢遞增）

其他補充

百度開源的分布式唯一ID生成器UidGenerator

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

繼續閱讀

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

詳解STM32單片機的堆棧

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述