雪花算法snowflake分布式id生成原理詳解，以及對解決時鐘回撥問題幾種方案讨論

文章目錄

- 一、前言
- 二、雪花算法snowflake
- - 1、基本定義
  - 2、snowflake的優缺點
- 三、Java代碼實作snowflake
- - 1、組裝生成id
  - 2、計算最大值的幾種方式
  - 3、反解析ID
  - 4、ID生成器使用方式
- 四、時鐘回撥問題和解決方案讨論
- - 1、時間戳自增徹底解決時鐘回撥問題
  - 2、緩存曆史序列号緩解時鐘回撥問題
  - 3、等待時鐘校正
- 五、要點總結

一、前言

在日趨複雜的分布式系統中，資料量越來越大，資料庫分庫分表是一貫的垂直水準做法，但是需要一個全局唯一ID辨別一條資料或者MQ消息，資料庫id自增就顯然不能滿足要求了。因為場景不同，分布式ID需要滿足以下幾個條件：

全局唯一性，不能出現重複的ID。
趨勢遞增，在 MySQL InnoDB 引擎中使用的是聚集索引，由于多數 RDBMS 使用 B-tree 的資料結構來存儲索引資料，在主鍵的選擇上應該盡量使用有序的主鍵保證寫入性能。
單調遞增，保證下一個ID一定大于上一個ID。例如分布式事務版本号、IM增量消息、排序等特殊需求。
資訊安全，對于特殊業務，如訂單等，分布式ID生成應該是無規則的，不能從ID上反解析出流量等敏感資訊。

市面上對分布式ID生成大緻有幾種算法（一些開源項目都是圍着這幾種算法進行實作和優化）：

UUID：因為是本地生成，性能極高，但是生成的ID太長，16位元組128位，通常需要字元串類型存儲，且無序，是以很多場景不适用，也不适用于作為MySQL資料庫的主鍵和索引（MySql官方建議，主鍵越短越好；對于 InnoDB 引擎，索引的無序性可能會引起資料位置頻繁變動，嚴重影響性能）。
資料庫自增ID：每次擷取ID都需要DB的IO操作，DB壓力大，性能低。資料庫當機對外依賴服務就是毀滅性打擊，不過可以部署資料庫叢集保證高可用。
資料庫号段算法：對資料庫自增ID的優化，每次擷取一個号段的值。用完之後再去資料庫擷取新的号段，可以大大減輕資料庫的壓力。号段越長，性能越高，同時如果資料庫當機，号段沒有用完，短時間還可以對外提供服務。（美團的Leaf、滴滴的TinyId）
雪花算法：Twitter開源的snowflake，以時間戳+機器+遞增序列組成，基本趨勢遞增，且性能很高，因為強依賴機器時鐘，是以需要考慮時鐘回撥問題，即機器上的時間可能因為校正出現倒退，導緻生成的ID重複。（百度的uid-generator、美團的Leaf）

雪花算法和資料庫号段算法用的最多，本篇主要對雪花算法原理剖析和解決時鐘回撥問題讨論。

二、雪花算法snowflake

1、基本定義

雪花算法snowflake分布式id生成原理詳解，以及對解決時鐘回撥問題幾種方案讨論

snowflake原理其實很簡單，生成一個

64bit（long）

的全局唯一ID，标準元素以1bit無用符号位+41bit時間戳+10bit機器ID+12bit序列化組成，其中除1bit符号位不可調整外，其他三個辨別的bit都可以根據實際情況調整：

41bit-時間可以表示（1L<<41）/(1000L360024*365)=69年的時間。
10bit-機器可以表示1024台機器。如果對IDC劃分有需求，還可以将10-bit分5-bit給IDC，分5-bit給工作機器。這樣就可以表示32個IDC，每個IDC下可以有32台機器。
12個自增序列号可以表示2^12個ID，理論上snowflake方案的QPS約為409.6w/s。

注：都是從0開始計數。

2、snowflake的優缺點

優點：

毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。
可以不依賴資料庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也非常高。
可以根據自身業務特性配置設定bit位，非常靈活。

缺點：

強依賴機器時鐘，如果機器上時鐘回撥，會導緻發号重複或者服務處于不可用狀态。

三、Java代碼實作snowflake

如下示例，41bit給時間戳，5bit給IDC，5bit給工作機器，12bit給序列号，代碼中是寫死的，如果某些bit需要動态調整，可在成員屬性定義。計算過程需要一些位運算基礎。

public class SnowflakeIdGenerator {

    public static final int TOTAL_BITS = 1 << 6;

    private static final long SIGN_BITS = 1;

    private static final long TIME_STAMP_BITS = 41L;

    private static final long DATA_CENTER_ID_BITS = 5L;

    private static final long WORKER_ID_BITS = 5L;

    private static final long SEQUENCE_BITS = 12L;

    /**
     * 時間向左位移位數 22位
     */
    private static final long TIMESTAMP_LEFT_SHIFT = WORKER_ID_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS;

    /**
     * IDC向左位移位數 17位
     */
    private static final long DATA_CENTER_ID_SHIFT = WORKER_ID_BITS + SEQUENCE_BITS;

    /**
     * 機器ID 向左位移位數 12位
     */
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;

    /**
     * 序列掩碼，用于限定序列最大值為4095
     */
    private static final long SEQUENCE_MASK =  -1L ^ (-1L << SEQUENCE_BITS);

    /**
     * 最大支援機器節點數0~31，一共32個
     */
    private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
    /**
     * 最大支援資料中心節點數0~31，一共32個
     */
    private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

    /**
     * 最大時間戳 2199023255551
     */
    private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);

    /**
     * Customer epoch
     */
    private final long twepoch;

    private final long workerId;

    private final long dataCenterId;

    private long sequence = 0L;

    private long lastTimestamp = -1L;

    /**
     *
     * @param workerId 機器ID
     * @param dataCenterId  IDC ID
     */
    public SnowflakeIdGenerator(long workerId, long dataCenterId) {
        this(workerId, dataCenterId, null);
    }

    /**
     *
     * @param workerId  機器ID
     * @param dataCenterId IDC ID
     * @param epochDate 初始化時間起點
     */
    public SnowflakeIdGenerator(long workerId, long dataCenterId, Date epochDate) {
        if (workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException("worker Id can't be greater than "+ MAX_WORKER_ID + " or less than 0");
        }
        if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
            throw new IllegalArgumentException("datacenter Id can't be greater than {" + MAX_DATA_CENTER_ID + "} or less than 0");
        }

        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
        if (epochDate != null) {
            this.twepoch = epochDate.getTime();
        } else {
            //2010-10-11
            this.twepoch = 1286726400000L;
        }

    }

    public long genID() throws Exception {
        try {
            return nextId();
        } catch (Exception e) {
            throw e;
        }
    }

    public long getLastTimestamp() {
        return lastTimestamp;
    }

    /**
     * 通過移位解析出sequence，sequence有效位為[0,12]
     * 是以先向左移64-12，然後再像右移64-12，通過兩次移位就可以把無效位移除了
     * @param id
     * @return
     */
    public long getSequence2(long id) {
        return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
    }

    /**
     * 通過移位解析出workerId，workerId有效位為[13,17], 左右兩邊都有無效位
     * 先向左移 41+5+1，移除掉41bit-時間，5bit-IDC、1bit-sign，
     * 然後右移回去41+5+1+12，進而移除掉12bit-序列号
     * @param id
     * @return
     */
    public long getWorkerId2(long id) {
        return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
    }
    /**
     * 通過移位解析出IDC_ID，dataCenterId有效位為[18,23]，左邊兩邊都有無效位
     * 先左移41+1，移除掉41bit-時間和1bit-sign
     * 然後右移回去41+1+5+12，移除掉右邊的5bit-workerId和12bit-序列号
     * @param id
     * @return
     */
    public long getDataCenterId2(long id) {
        return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
    }
    /**
     * 41bit-時間，左邊1bit-sign為0，可以忽略，不用左移，是以隻需要右移，并加上起始時間twepoch即可。
     * @param id
     * @return
     */
    public long getGenerateDateTime2(long id) {
        return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
    }

    public long getSequence(long id) {
        return id & ~(-1L << SEQUENCE_BITS);
    }

    public long getWorkerId(long id) {
        return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
    }

    public long getDataCenterId(long id) {
        return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
    }

    public long getGenerateDateTime(long id) {
        return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
    }

    private synchronized long nextId() throws Exception {
        long timestamp = timeGen();
        // 1、出現時鐘回撥問題，直接抛異常
        if (timestamp < lastTimestamp) {
            long refusedTimes = lastTimestamp - timestamp;
            // 可自定義異常類
            throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", refusedTimes));
        }
        // 2、時間等于lastTimestamp，取目前的sequence + 1
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            // Exceed the max sequence, we wait the next second to generate id
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
            this.sequence = 0L;
        }
        lastTimestamp = timestamp;

        return allocate(timestamp - this.twepoch);
    }

    private long allocate(long deltaSeconds) {
        return (deltaSeconds << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;
    }

    private long timeGen() {
        long currentTimestamp = System.currentTimeMillis();
        // 時間戳超出最大值
        if (currentTimestamp - twepoch > MAX_DELTA_TIMESTAMP) {
            throw new UnsupportedOperationException("Timestamp bits is exhausted. Refusing ID generate. Now: " + currentTimestamp);
        }
        return currentTimestamp;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 測試
     * @param args
     */
    public static void main(String[] args) throws Exception {
        SnowflakeIdGenerator snowflakeIdGenerator = new SnowflakeIdGenerator(1,2);
        long id = snowflakeIdGenerator.genID();

        System.out.println("ID=" + id + ", lastTimestamp=" + snowflakeIdGenerator.getLastTimestamp());
        System.out.println("ID二進制：" + Long.toBinaryString(id));
        System.out.println("解析ID:");
        System.out.println("Sequence=" + snowflakeIdGenerator.getSequence(id));
        System.out.println("WorkerId=" + snowflakeIdGenerator.getWorkerId(id));
        System.out.println("DataCenterId=" + snowflakeIdGenerator.getDataCenterId(id));
        System.out.println("GenerateDateTime=" + snowflakeIdGenerator.getGenerateDateTime(id));

        System.out.println("Sequence2=" + snowflakeIdGenerator.getSequence2(id));
        System.out.println("WorkerId2=" + snowflakeIdGenerator.getWorkerId2(id));
        System.out.println("DataCenterId2=" + snowflakeIdGenerator.getDataCenterId2(id));
        System.out.println("GenerateDateTime2=" + snowflakeIdGenerator.getGenerateDateTime2(id));
    }

}

雪花算法snowflake分布式id生成原理詳解，以及對解決時鐘回撥問題幾種方案讨論

1、組裝生成id

生成id的過程，就是把每一種辨別（時間、機器、序列号）移到對應位置，然後相加。

long id = (deltaTime << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;

deltaTime 向左移22位（IDC-bit+機器bit+序列号bit）。
dataCenterId 向左移17位（機器bit+序列号bit）。
workerId 向左移12位（序列号bit）。
sequence 不用移。
中間的 | 以運算規律就相當于 + 求和（1 | 1 = 1，1 | 0 = 1，0 | 1 = 1，0 | 0 = 0）。

2、計算最大值的幾種方式

（1）注意到代碼中分别對每個辨別的最大值做了計算：

//序列掩碼，用于限定序列最大值為4095 ((2^12)-1) ，從0開始算就有4096個序列
private static final long SEQUENCE_MASK =  -1L ^ (-1L << SEQUENCE_BITS);

//最大支援機器節點數0~31，一共32個  (2^5)-1
private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);

//最大支援資料中心節點數0~31，一共32個   (2^5)-1
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

//最大時間戳 2199023255551   (2^41)-1
private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);

如上方式計算最大值并不好了解，就是利用二進制的運算邏輯，如果不了解根本看不懂。拿

-1L ^ (-1L << SEQUENCE_BITS)

舉例：

先看看從哪個方向開始計算：

-1L ^ (-1L << 12)

，

-1L

和

(-1L <<12)

做

按位異或運算（

1 ^ 1 = 0，1 ^ 0 = 1，0 ^ 1 = 1，0 ^ 0 = 0

）。

-1L 的二進制為64個1： 1111111111111111111111111111111111111111111111111111111111111111 。
-1L 左移12位得到： 1111111111111111111111111111111111111111111111111111 000000 000000 。
最後 1111111111111111111111111111111111111111111111111111111111111111 和 1111111111111111111111111111111111111111111111111111 000000 000000 做 ^ 運算得到 0000000000000000000000000000000000000000000000000000 111111 111111 （前面有52個0），這就得到序列号的最大值（4095）了，也可以說是掩碼。

雪花算法snowflake分布式id生成原理詳解，以及對解決時鐘回撥問題幾種方案讨論

（2）其實有一種更容易了解的計算最大值的方式，比如計算12bit-序列号的最大值，那就是

(2^12 -1)

呀，但是位運算性能更高，用位運算的方式就是

((1 << 12) -1)

。1左移12位得到

1 0000 0000 0000

，減1也是可以得到

1111 1111 1111

，即4095。

（3）還看到一種計算最大值的方式，繼續拿12bit-序列号舉例，

~(-1L << 12)

，

不知道怎麼計算那就傻了：

-1L先向左移12位得到

1111111111111111111111111111111111111111111111111111 000000 000000

，然後進行

按位非運算（

~ 1 = -2，~ 0 = -1 ，~n = - ( n+1 )

），也可以了解為反轉，1轉為0,0轉為1，然後也可以得到

0000000000000000000000000000000000000000000000000000 111111 111111

。

3、反解析ID

（1）通過已經生成的ID解析出時間、機器和序列号：

public long getSequence(long id) {
    return id & ~(-1L << SEQUENCE_BITS);
}

public long getWorkerId(long id) {
    return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}

public long getDataCenterId(long id) {
    return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}

public long getGenerateDateTime(long id) {
    return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
}

因為

sequence

本身就在低位，是以不需要移動，其他機器和時間都是需要将id向右移動，使得自己的有效位置在低位，至于和自己的最大值做

運算，是為了讓不屬于自己bit的位置無效，即都轉為0。

例如：生成的id為1414362783486840832，轉為二進制

1001110100000110100110111010100111101010001000001000000000000

，想解析出

workerId

，

workerId

有效位為[13, 17]，那就将id向右移12位，移到低位得到

0000000000001001110100000110100110111010100111101010001000001

，

workerId

有5-bit，那麼除了低位5-bit，其他位置都是無效bit，轉為0。

0000000000001001110100000110100110111010100111101010001000001

和

做

運算得到1（左邊都是0可以省掉）。

（2）不過還有一種解析的思路更易于了解，就是運用兩次移位運算，把無效位置移除：

1bit-sign + 41bit-time + 5bit-IDC + 5bit-workerId + 12bit-sequence

/**
 * 通過移位解析出sequence，sequence有效位為[0,12]
 * 是以先向左移64-12，然後再像右移64-12，通過兩次移位就可以把無效位移除了
 * @param id
 * @return
 */
public long getSequence2(long id) {
    return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
}
/**
 * 通過移位解析出workerId，workerId有效位為[13,17], 左右兩邊都有無效位
 * 先向左移 41+5+1，移除掉41bit-時間，5bit-IDC、1bit-sign，
 * 然後右移回去41+5+1+12，進而移除掉12bit-序列号
 * @param id
 * @return
 */
public long getWorkerId2(long id) {
    return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
 * 通過移位解析出IDC_ID，dataCenterId有效位為[18,23]，左邊兩邊都有無效位
 * 先左移41+1，移除掉41bit-時間和1bit-sign
 * 然後右移回去41+1+5+12，移除掉右邊的5bit-workerId和12bit-序列号
 * @param id
 * @return
 */
public long getDataCenterId2(long id) {
    return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
 * 41bit-時間，左邊1bit-sign為0，可以忽略，不用左移，是以隻需要右移，并加上起始時間twepoch即可。
 * @param id
 * @return
 */
public long getGenerateDateTime2(long id) {
    return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
}

4、ID生成器使用方式

主要有兩種方式，一種是發号器，一種是本地生成：

發号器，就是把雪花算法ID生成封裝成一個服務，部署在多台機器上，由外界請求發号器服務擷取ID。這樣做的好處，是機器不需要那麼多，1024台完全足夠了，相對ID的時間戳和序列号的bit就可以調大一些。但是因為需要遠端請求擷取ID，是以會受到網絡波動的影響，性能上肯定是沒有直接從本地生成擷取高的，同時發号器一旦挂了，很多服務就不能對外提供服務了，是以發号器服務需要高可用，多執行個體，異地部署和容災，發号器在發号的時候，也可以釋出一段時間的ID，服務本地緩存起來，這樣不僅提高性能，不需要每次都去請求發号器，也在一定程度上緩解了發号器故障帶來的影響。
本地生成ID，沒有網絡延遲，性能極高。隻能通過機器id來保證生成的ID唯一性，是以需要提供足夠多的機器id，每台機器可能部署多個服務，每個服務可能部署在多台機器，都需要配置設定不同的機器id，并且服務重新開機了也需要重新配置設定機器id。這樣機器id就有了用後即毀的特點。需要足夠多的機器id，就必須縮減時間bit和序列号bit。

可以利用

MySql

或者

zk

進行機器id的配置設定和管理。

四、時鐘回撥問題和解決方案讨論

首先看看時鐘為什麼會發生回撥？機器本地時鐘可能會因為各種原因發生不準的情況，網絡中提供了NTP服務來做時間校準，做校準的時候就會發生時鐘的跳躍或者回撥的問題。

因為雪花算法強依賴機器時鐘，是以難以避免受到時鐘回撥的影響，有可能産生ID重複。原标準實作代碼中是直接抛異常，短暫停止對外服務，這樣在實際生産中是無法忍受的。是以要盡量避免時鐘回撥帶來的影響，解決思路有兩個：

不依賴機器時鐘驅動，就沒時鐘回撥的事兒了。即定義一個初始時間戳，在初始時間戳上自增，不跟随機器時鐘增加。時間戳何時自增？當序列号增加到最大時，此時時間戳+1，這樣完全不會浪費序列号，适合流量較大的場景，如果流量較小，可能出現時間斷層滞後。
依然依賴機器時鐘，如果時鐘回撥範圍較小，如幾十毫秒，可以等到時間回到正常；如果流量不大，前幾百毫秒或者幾秒的序列号肯定有剩餘，可以将前幾百毫秒或者幾秒的序列号緩存起來，如果發生時鐘回撥，就從緩存中擷取序列号自增。

（時鐘回撥問題，可通過手動調整電腦上的時鐘進行模拟測試。）

1、時間戳自增徹底解決時鐘回撥問題

private long sequence = -1L;
private long startTimestamp = 1623947387000L;
private synchronized  long nextId2() {
    long sequenceTmp = sequence;
    sequence = (sequence + 1) & SEQUENCE_MASK;
    // sequence =0 有可能是初始+1=0，也可能是超過了最大值等于0
    // 是以把 初始+1=0排除掉
    if (sequence == 0 && sequenceTmp >= 0) {
        // sequence自增到最大了，時間戳自增1
        startTimestamp += 1;
    }
    // 生成id
    return allocate(startTimestamp - twepoch);
}

起始時間可以構造器裡指定，也可以用預設的，而

sequence

初始為-1，是為了不想浪費

sequence+1=0

這一序列号。

sequence = 0

排除掉初始

sequence=-1 +1 = 0

的情況就是

sequence

超過最大值了，此時時間戳

startTimestamp

自增。

代碼和思路都很簡單，就是完全脫離機器時鐘，徹底解決了時鐘回撥問題。顯而易見的優點，每一毫秒4096個序列号（

[0,4095]

）沒有浪費，同時因為時間自增由程式自己掌控，是以可以利用未來時間，預先生成一些ID放在緩存裡，外界從緩存中直接擷取ID，快消費完了再生産，這樣就形成了永動的生産-消費者模式，擷取ID省去了生成的過程，性能也會大大提升。

但是時間戳完全自控，也有很明顯的缺點，ID生成的時間，并不是真實的時間，如果流量較小，時間可能會滞後很多。如果對從ID解析出來的時間戳沒有什麼利用意義，這個缺點也不需要關心。

2、緩存曆史序列号緩解時鐘回撥問題

// 記錄近2S的毫秒數的sequence的緩存
private int LENGTH = 2000;
// sequence緩存
private long[] sequenceCycle = new long[LENGTH];

private synchronized long nextId() throws Exception {
    long timestamp = timeGen();
    int index = (int)(timestamp % LENGTH);
    // 1、出現時鐘回撥問題，擷取曆史序列号自增
    if (timestamp < lastTimestamp) {
        long sequence = 0;
        do {
           if ((lastTimestamp - timestamp) > LENGTH) {
               // 可自定義異常、告警等，短暫不能對外提供，故障轉移，将請求轉發到正常機器。
               throw new UnsupportedOperationException("The timeback range is too large and exceeds 2000ms caches");
            }
            long preSequence = sequenceCycle[index];
            sequence = (preSequence + 1) & SEQUENCE_MASK;
            if (sequence == 0) {
                // 如果取出的曆史序列号+1後已經達到超過最大值，
                // 則重新擷取timestamp,重新拿其他位置的緩存
                timestamp = tilNextMillis(lastTimestamp);
                index = (int)(timestamp % LENGTH);
            } else {
            	// 更新緩存
                sequenceCycle[index] = this.sequence;            
                return allocate((timestamp - this.twepoch), sequence);
            }
        } while (timestamp < lastTimestamp);
        // 如果在擷取緩存的過程中timestamp恢複正常了，就走正常流程
    }
    // 2、時間等于lastTimestamp，取目前的sequence + 1
    if (timestamp == lastTimestamp) {
        sequence = (sequence + 1) & SEQUENCE_MASK;
        // Exceed the max sequence, we wait the next second to generate id
        if (sequence == 0) {
            timestamp = tilNextMillis(lastTimestamp);
            index = (int)(timestamp % LENGTH);
        }
    } else {
        // 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
        this.sequence = 0L;
    }
    // 緩存sequence + 更新lastTimestamp
    sequenceCycle[index] = this.sequence;
    lastTimestamp = timestamp;
    // 生成id
    return allocate(timestamp - this.twepoch);
}

這裡緩存了2000ms的序列号，如果發生時鐘回撥，且回撥範圍在2000ms内，就從緩存中取序列号自增，超過2000ms回撥，就抛異常，故障轉移，将請求配置設定到正常機器。

若擷取的曆史 sequence+1 之後超過了最大值，則重新擷取時間戳，重新擷取緩存 sequence 。
極端情況下，擷取很多次緩存 sequence+1 都超過了最大值，就會一直循環擷取，這樣可能會影響性能，是以實際生産中可以限定重新擷取次數。
在這個重新擷取的過程中，時鐘可能恢複正常了，則此時也要退出循環，走正常流程。

3、等待時鐘校正

private synchronized  long nextId3() {
    long timestamp = timeGen();
    // 1、出現時鐘回撥問題，如果回撥幅度不大，等待時鐘自己校正
    if (timestamp < lastTimestamp) {
        int sleepCntMax = 2;
        int sleepCnt = 0;
        do {
            long sleepTime = lastTimestamp - timestamp;
            if (sleepCnt > sleepCntMax) {
                // 可自定義異常類
                throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", sleepTime));
            }
            if (sleepTime <= 500) {
                try {
                    Thread.sleep(sleepTime);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    sleepCnt++;
                    timestamp = tilNextMillis(lastTimestamp);
                }
            } else {
                // 可自定義異常類
                throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", sleepTime));
            }
        } while (timestamp < lastTimestamp);
    }
    // 2、時間等于lastTimestamp，取目前的sequence + 1
    if (timestamp == lastTimestamp) {
        sequence = (sequence + 1) & SEQUENCE_MASK;
        // Exceed the max sequence, we wait the next second to generate id
        if (sequence == 0) {
            timestamp = tilNextMillis(lastTimestamp);
        }
    } else {
        // 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
        this.sequence = 0L;
    }
    lastTimestamp = timestamp;
    // 生成id
    return allocate(timestamp - this.twepoch);
}

等待時鐘自己校正來解決時鐘回撥問題，适用于回撥幅度小的場景。比如回撥時長小于500ms，那就睡眠500ms，等時間恢複到正常，如果這個過程中又發生了時鐘回撥，不可能一直等它校正，實際生産中可限定校正的次數，超過最大校正次數，那就抛異常吧，這屬于極端情況。

解決時鐘回撥問題的方法還有很多，無非就是避免和緩解。每種方式有各自的特點和适用場景，可以兩兩結合使用，比如時鐘回撥幅度小，就休眠校正，回撥幅度大或者出現多次回撥，也不抛異常，擷取緩存

sequence

對外提供服務。也可以當發生時鐘回撥時，用備用機器id生成ID等。

五、要點總結

生成全局唯一的分布式ID的方式有很多，常用的有資料庫号段算法和雪花算法，這兩個算法的實踐，大廠也有開源的項目，如百度的uid-generator、美團的Leaf、滴滴的TinyId等。
雪花算法的原理很簡單，主要由時間戳+機器id+序列号生成64bit的ID，整體趨勢遞增，且全局唯一，性能也不錯。每種組成辨別的bit都可以自定義，靈活性很高，如果需要更高的QPS，可以相對的把序列号bit調大一些。
因為雪花算法強依賴機器時鐘，就難以避免時鐘回撥問題，解決的方式很多，無非從避免和緩解兩個角度出發，常用的方式有，時間戳自增脫離機器時鐘依賴，利用緩存序列号，或者等待時鐘校正等，各有各的特點，正确利用其優點，才能最大提高性能。
雪花算法ID生成器的使用方式有兩種，一種是遠端發号器，需要做到高可用。另一種就是直接本地生成ID，省去了遠端請求過程，性能自然也是比遠端發号器高的，但是機器id用後即毀，需要配置設定足夠多的機器id。機器id的管理和配置設定可以利用 MySql 或者 ZK 。

參考：

Leaf——美團點評分布式ID生成系統
http://www.cnblogs.com/relucent/p/4955340.html
https://segmentfault.com/a/1190000011282426
https://www.yuque.com/simonalong/butterfly/tul824

如若文章有錯誤了解，歡迎批評指正，同時非常期待你的評論、點贊和收藏。

雪花算法snowflake分布式id生成原理詳解，以及對解決時鐘回撥問題幾種方案讨論

文章目錄

一、前言

二、雪花算法snowflake

1、基本定義

2、snowflake的優缺點

三、Java代碼實作snowflake

1、組裝生成id

2、計算最大值的幾種方式

3、反解析ID

4、ID生成器使用方式

四、時鐘回撥問題和解決方案讨論

1、時間戳自增徹底解決時鐘回撥問題

2、緩存曆史序列号緩解時鐘回撥問題

3、等待時鐘校正

五、要點總結

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]