原文鏈接

一框仔、為什么要用分布式ID？

在說(shuō)分布式ID的具體實(shí)現(xiàn)之前，我們來(lái)簡(jiǎn)單分析一下為什么用分布式ID主巍？分布式ID應(yīng)該滿足哪些特征？

1、什么是分布式ID？

拿MySQL數(shù)據(jù)庫(kù)舉個(gè)栗子：

在我們業(yè)務(wù)數(shù)據(jù)量不大的時(shí)候瓶珊，單庫(kù)單表完全可以支撐現(xiàn)有業(yè)務(wù)，數(shù)據(jù)再大一點(diǎn)搞個(gè)MySQL主從同步讀寫(xiě)分離也能對(duì)付耸彪。

但隨著數(shù)據(jù)日漸增長(zhǎng)伞芹，主從同步也扛不住了，就需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行分庫(kù)分表蝉娜，但分庫(kù)分表后需要有一個(gè)唯一ID來(lái)標(biāo)識(shí)一條數(shù)據(jù)丑瞧，數(shù)據(jù)庫(kù)的自增ID顯然不能滿足需求柑土；特別一點(diǎn)的如訂單、優(yōu)惠券也都需要有唯一ID做標(biāo)識(shí)绊汹。此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的稽屏。那么這個(gè)全局唯一ID就叫分布式ID。

2西乖、那么分布式ID需要滿足哪些條件狐榔？

• 全局唯一：必須保證ID是全局性唯一的，基本要求
• 高性能：高可用低延時(shí)获雕，ID生成響應(yīng)要快薄腻，否則反倒會(huì)成為業(yè)務(wù)瓶頸
• 高可用：100%的可用性是騙人的，但是也要無(wú)限接近于100%的可用性
• 好接入：要秉著拿來(lái)即用的設(shè)計(jì)原則届案，在系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)上要盡可能的簡(jiǎn)單
• 趨勢(shì)遞增：最好趨勢(shì)遞增庵楷，這個(gè)要求就得看具體業(yè)務(wù)場(chǎng)景了，一般不嚴(yán)格要求

二楣颠、 分布式ID都有哪些生成方式尽纽？

今天主要分析一下以下9種，分布式ID生成器方式以及優(yōu)缺點(diǎn)：

• UUID
• 數(shù)據(jù)庫(kù)自增ID
• 數(shù)據(jù)庫(kù)多主模式
• 號(hào)段模式
• Redis
• 雪花算法（SnowFlake）

那么它們都是如何實(shí)現(xiàn)童漩？以及各自有什么優(yōu)缺點(diǎn)弄贿？我們往下看

1、基于UUID

在Java的世界里矫膨，想要得到一個(gè)具有唯一性的ID差凹，首先被想到可能就是UUID，畢竟它有著全球唯一的特性侧馅。那么UUID可以做分布式ID嗎危尿？答案是可以的，但是并不推薦馁痴！

public static void main(String[] args) { 
       String uuid = UUID.randomUUID().toString().replaceAll("-","");
       System.out.println(uuid);
 }

UUID的生成簡(jiǎn)單到只有一行代碼脚线，輸出結(jié)果 c2b8c2b9e46c47e3b30dca3b0d447718，但UUID卻并不適用于實(shí)際的業(yè)務(wù)需求弥搞。像用作訂單號(hào)UUID這樣的字符串沒(méi)有絲毫的意義，看不出和訂單相關(guān)的有用信息渠旁；而對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)用作業(yè)務(wù)主鍵ID攀例，它不僅是太長(zhǎng)還是字符串，存儲(chǔ)性能差查詢也很耗時(shí)顾腊，所以不推薦用作分布式ID粤铭。

優(yōu)點(diǎn)：

• 生成足夠簡(jiǎn)單坞靶，本地生成無(wú)網(wǎng)絡(luò)消耗默伍，具有唯一性

缺點(diǎn)：

• 無(wú)序的字符串吉殃，不具備趨勢(shì)自增特性
• 沒(méi)有具體的業(yè)務(wù)含義
• 長(zhǎng)度過(guò)長(zhǎng)16 字節(jié)128位劫樟，36位長(zhǎng)度的字符串，存儲(chǔ)以及查詢對(duì)MySQL的性能消耗較大垛吗，MySQL官方明確建議主鍵要盡量越短越好凹髓，作為數(shù)據(jù)庫(kù)主鍵 UUID 的無(wú)序性會(huì)導(dǎo)致數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能怯屉。

2蔚舀、基于數(shù)據(jù)庫(kù)自增ID

基于數(shù)據(jù)庫(kù)的auto_increment自增ID完全可以充當(dāng)分布式ID，具體實(shí)現(xiàn)：需要一個(gè)單獨(dú)的MySQL實(shí)例用來(lái)生成ID锨络，建表結(jié)構(gòu)如下：

CREATE DATABASE `SEQ_ID`;
CREATE TABLE SEQID.SEQUENCE_ID (
    id bigint(20) unsigned NOT NULL auto_increment, 
    value char(10) NOT NULL default '',
    PRIMARY KEY (id),
) ENGINE=MyISAM;

insert into SEQUENCE_ID(value) VALUES ('values');

當(dāng)我們需要一個(gè)ID的時(shí)候赌躺，向表中插入一條記錄返回主鍵ID，但這種方式有一個(gè)比較致命的缺點(diǎn)羡儿，訪問(wèn)量激增時(shí)MySQL本身就是系統(tǒng)的瓶頸礼患，用它來(lái)實(shí)現(xiàn)分布式服務(wù)風(fēng)險(xiǎn)比較大，不推薦掠归！

優(yōu)點(diǎn)：

• 實(shí)現(xiàn)簡(jiǎn)單缅叠，ID單調(diào)自增，數(shù)值類型查詢速度快

缺點(diǎn)：

• DB單點(diǎn)存在宕機(jī)風(fēng)險(xiǎn)拂到，無(wú)法扛住高并發(fā)場(chǎng)景

3痪署、基于數(shù)據(jù)庫(kù)集群模式

前邊說(shuō)了單點(diǎn)數(shù)據(jù)庫(kù)方式不可取，那對(duì)上邊的方式做一些高可用優(yōu)化兄旬，換成主從模式集群狼犯。害怕一個(gè)主節(jié)點(diǎn)掛掉沒(méi)法用，那就做雙主模式集群领铐，也就是兩個(gè)Mysql實(shí)例都能單獨(dú)的生產(chǎn)自增ID悯森。

那這樣還會(huì)有個(gè)問(wèn)題，兩個(gè)MySQL實(shí)例的自增ID都從1開(kāi)始绪撵，會(huì)生成重復(fù)的ID怎么辦瓢姻？

解決方案：設(shè)置起始值和自增步長(zhǎng)

MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長(zhǎng)

MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長(zhǎng)

這樣兩個(gè)MySQL實(shí)例的自增ID分別就是：

1、3音诈、5幻碱、7、9
2细溅、4褥傍、6、8喇聊、10

那如果集群后的性能還是扛不住高并發(fā)咋辦恍风？就要進(jìn)行MySQL擴(kuò)容增加節(jié)點(diǎn)，這是一個(gè)比較麻煩的事。

從上圖可以看出朋贬，水平擴(kuò)展的數(shù)據(jù)庫(kù)集群凯楔，有利于解決數(shù)據(jù)庫(kù)單點(diǎn)壓力的問(wèn)題，同時(shí)為了ID生成特性锦募，將自增步長(zhǎng)按照機(jī)器數(shù)量來(lái)設(shè)置摆屯。

增加第三臺(tái)MySQL實(shí)例需要人工修改一、二兩臺(tái)MySQL實(shí)例的起始值和步長(zhǎng)御滩，把第三臺(tái)機(jī)器的ID起始生成位置設(shè)定在比現(xiàn)有最大自增ID的位置遠(yuǎn)一些鸥拧，但必須在一、二兩臺(tái)MySQL實(shí)例ID還沒(méi)有增長(zhǎng)到第三臺(tái)MySQL實(shí)例的起始ID值的時(shí)候削解，否則自增ID就要出現(xiàn)重復(fù)了富弦，必要時(shí)可能還需要停機(jī)修改。

優(yōu)點(diǎn)：

• 解決DB單點(diǎn)問(wèn)題

缺點(diǎn)：

• 不利于后續(xù)擴(kuò)容氛驮，而且實(shí)際上單個(gè)數(shù)據(jù)庫(kù)自身壓力還是大腕柜，依舊無(wú)法滿足高并發(fā)場(chǎng)景。

4矫废、基于數(shù)據(jù)庫(kù)的號(hào)段模式

號(hào)段模式是當(dāng)下分布式ID生成器的主流實(shí)現(xiàn)方式之一盏缤，號(hào)段模式可以理解為從數(shù)據(jù)庫(kù)批量的獲取自增ID，每次從數(shù)據(jù)庫(kù)取出一個(gè)號(hào)段范圍蓖扑，例如 (0,1000] 代表1000個(gè)ID唉铜，具體的業(yè)務(wù)服務(wù)將本號(hào)段，生成1~1000的自增ID并加載到內(nèi)存律杠。表結(jié)構(gòu)如下：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '當(dāng)前最大id',
  step int(20) NOT NULL COMMENT '號(hào)段的布長(zhǎng)',
  biz_type    int(20) NOT NULL COMMENT '業(yè)務(wù)類型',
  version int(20) NOT NULL COMMENT '版本號(hào)',
  PRIMARY KEY (`id`)
) 

biz_type ：代表不同業(yè)務(wù)類型

max_id ：當(dāng)前最大的可用id

step ：代表號(hào)段的長(zhǎng)度

version ：是一個(gè)樂(lè)觀鎖潭流，每次都更新version，保證并發(fā)時(shí)數(shù)據(jù)的正確性

等這批號(hào)段ID用完柜去，再次向數(shù)據(jù)庫(kù)申請(qǐng)新號(hào)段灰嫉，對(duì)max_id字段做一次update操作，update max_id= max_id + step嗓奢，update成功則說(shuō)明新號(hào)段獲取成功讼撒，新的號(hào)段范圍是(max_id ,max_id +step]。

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

由于多業(yè)務(wù)端可能同時(shí)操作股耽，所以采用版本號(hào)version樂(lè)觀鎖方式更新根盒，這種分布式ID生成方式不強(qiáng)依賴于數(shù)據(jù)庫(kù)，不會(huì)頻繁的訪問(wèn)數(shù)據(jù)庫(kù)物蝙，對(duì)數(shù)據(jù)庫(kù)的壓力小很多炎滞。

5、基于Redis模式

Redis也同樣可以實(shí)現(xiàn)茬末，原理就是利用redis的 incr命令實(shí)現(xiàn)ID的原子性自增。

127.0.0.1:6379> set seq_id 1     // 初始化自增ID為1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回遞增后的數(shù)值
(integer) 2

用redis實(shí)現(xiàn)需要注意一點(diǎn)丽惭，要考慮到redis持久化的問(wèn)題击奶。redis有兩種持久化方式RDB和AOF

• RDB會(huì)定時(shí)打一個(gè)快照進(jìn)行持久化，假如連續(xù)自增但redis沒(méi)及時(shí)持久化责掏，而這會(huì)Redis掛掉了柜砾，重啟Redis后會(huì)出現(xiàn)ID重復(fù)的情況。
• AOF會(huì)對(duì)每條寫(xiě)命令進(jìn)行持久化换衬，即使Redis掛掉了也不會(huì)出現(xiàn)ID重復(fù)的情況痰驱，但由于incr命令的特殊性，會(huì)導(dǎo)致Redis重啟恢復(fù)的數(shù)據(jù)時(shí)間過(guò)長(zhǎng)瞳浦。

6担映、基于雪花算法（Snowflake）模式

雪花算法（Snowflake）是twitter公司內(nèi)部分布式項(xiàng)目采用的ID生成算法，開(kāi)源后廣受國(guó)內(nèi)大廠的好評(píng)叫潦，在該算法影響下各大公司相繼開(kāi)發(fā)出各具特色的分布式生成器蝇完。

Snowflake生成的是Long類型的ID，一個(gè)Long類型占8個(gè)字節(jié)矗蕊，每個(gè)字節(jié)占8比特短蜕，也就是說(shuō)一個(gè)Long類型占64個(gè)比特。

Snowflake ID組成結(jié)構(gòu)：正數(shù)位（占1比特）+ 時(shí)間戳（占41比特）+ 機(jī)器ID（占5比特）+ 數(shù)據(jù)中心（占5比特）+ 自增值（占12比特）傻咖，總共64比特組成的一個(gè)Long類型朋魔。

• 第一個(gè)bit位（1bit）：Java中l(wèi)ong的最高位是符號(hào)位代表正負(fù)，正數(shù)是0卿操，負(fù)數(shù)是1警检，一般生成ID都為正數(shù)，所以默認(rèn)為0硬纤。
• 時(shí)間戳部分（41bit）：毫秒級(jí)的時(shí)間解滓，不建議存當(dāng)前時(shí)間戳，而是用（當(dāng)前時(shí)間戳 - 固定開(kāi)始時(shí)間戳）的差值筝家，可以使產(chǎn)生的ID從更小的值開(kāi)始洼裤；41位的時(shí)間戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年
• 工作機(jī)器id（10bit）：也被叫做workId溪王，這個(gè)可以靈活配置腮鞍，機(jī)房或者機(jī)器號(hào)組合都可以。
• 序列號(hào)部分（12bit）莹菱，自增值支持同一毫秒內(nèi)同一個(gè)節(jié)點(diǎn)可以生成4096個(gè)ID

根據(jù)這個(gè)算法的邏輯移国，只需要將這個(gè)算法用Java語(yǔ)言實(shí)現(xiàn)出來(lái)，封裝為一個(gè)工具方法道伟，那么各個(gè)業(yè)務(wù)應(yīng)用可以直接使用該工具方法來(lái)獲取分布式ID迹缀，只需保證每個(gè)業(yè)務(wù)應(yīng)用有自己的工作機(jī)器id即可使碾，而不需要單獨(dú)去搭建一個(gè)獲取分布式ID的應(yīng)用。

Java版本的Snowflake算法實(shí)現(xiàn)：

/**
 * Twitter的SnowFlake算法,使用SnowFlake算法生成一個(gè)整數(shù)祝懂，然后轉(zhuǎn)化為62進(jìn)制變成一個(gè)短地址URL
 *
 * https://github.com/beyondfengyu/SnowFlake
 */
public class SnowFlakeShortUrl {

    /**
     * 起始的時(shí)間戳
     */
    private final static long START_TIMESTAMP = 1480166465631L;

    /**
     * 每一部分占用的位數(shù)
     */
    private final static long SEQUENCE_BIT = 12;   //序列號(hào)占用的位數(shù)
    private final static long MACHINE_BIT = 5;     //機(jī)器標(biāo)識(shí)占用的位數(shù)
    private final static long DATA_CENTER_BIT = 5; //數(shù)據(jù)中心占用的位數(shù)

    /**
     * 每一部分的最大值
     */
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    private long dataCenterId;  //數(shù)據(jù)中心
    private long machineId;     //機(jī)器標(biāo)識(shí)
    private long sequence = 0L; //序列號(hào)
    private long lastTimeStamp = -1L;  //上一次時(shí)間戳

    private long getNextMill() {
        long mill = getNewTimeStamp();
        while (mill <= lastTimeStamp) {
            mill = getNewTimeStamp();
        }
        return mill;
    }

    private long getNewTimeStamp() {
        return System.currentTimeMillis();
    }

    /**
     * 根據(jù)指定的數(shù)據(jù)中心ID和機(jī)器標(biāo)志ID生成指定的序列號(hào)
     *
     * @param dataCenterId 數(shù)據(jù)中心ID
     * @param machineId    機(jī)器標(biāo)志ID
     */
    public SnowFlakeShortUrl(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0票摇！");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0！");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }

    /**
     * 產(chǎn)生下一個(gè)ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currTimeStamp = getNewTimeStamp();
        if (currTimeStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currTimeStamp == lastTimeStamp) {
            //相同毫秒內(nèi)砚蓬，序列號(hào)自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
            if (sequence == 0L) {
                currTimeStamp = getNextMill();
            }
        } else {
            //不同毫秒內(nèi)矢门，序列號(hào)置為0
            sequence = 0L;
        }

        lastTimeStamp = currTimeStamp;

        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //時(shí)間戳部分
                | dataCenterId << DATA_CENTER_LEFT       //數(shù)據(jù)中心部分
                | machineId << MACHINE_LEFT             //機(jī)器標(biāo)識(shí)部分
                | sequence;                             //序列號(hào)部分
    }
    
    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);

        for (int i = 0; i < (1 << 4); i++) {
            //10進(jìn)制
            System.out.println(snowFlake.nextId());
        }
    }
}

End

家中一縷霞光