天天看點

9種分布式ID生成算法一、為什麼要用分布式ID?二、 分布式ID都有哪些生成方式?總結

目錄

一、為什麼要用分布式ID?

1、什麼是分布式ID?

2、那麼分布式ID需要滿足那些條件?

二、 分布式ID都有哪些生成方式?

1、基于UUID(不推薦)

2、基于資料庫自增ID(不推薦)

3、基于資料庫叢集模式(不推薦)

4、基于資料庫的号段模式

5、基于Redis模式

6、基于雪花算法(Snowflake)模式

7、百度(uid-generator)

8、美團(Leaf)

号段模式

snowflake模式

9、滴滴(Tinyid)

Http方式接入

Java用戶端方式接入

總結

以下文章來源于公衆号:程式員内點事 ,作者程式員内點事

一、為什麼要用分布式ID?

在說分布式ID的具體實作之前,我們來簡單分析一下為什麼用分布式ID?分布式ID應該滿足哪些特征?

1、什麼是分布式ID?

拿MySQL資料庫舉個栗子:

在我們業務資料量不大的時候,單庫單表完全可以支撐現有業務,資料再大一點搞個MySQL主從同步讀寫分離也能對付。

但随着資料日漸增長,主從同步也扛不住了,就需要對資料庫進行分庫分表,但分庫分表後需要有一個唯一ID來辨別一條資料,資料庫的自增ID顯然不能滿足需求;特别一點的如訂單、優惠券也都需要有

唯一ID

做辨別。此時一個能夠生成

全局唯一ID

的系統是非常必要的。那麼這個

全局唯一ID

就叫

分布式ID

2、那麼分布式ID需要滿足那些條件?

  • 全局唯一:必須保證ID是全局性唯一的,基本要求
  • 高性能:高可用低延時,ID生成響應要塊,否則反倒會成為業務瓶頸
  • 高可用:100%的可用性是騙人的,但是也要無限接近于100%的可用性
  • 好接入:要秉着拿來即用的設計原則,在系統設計和實作上要盡可能的簡單
  • 趨勢遞增:最好趨勢遞增,這個要求就得看具體業務場景了,一般不嚴格要求

二、 分布式ID都有哪些生成方式?

今天主要分析一下以下9種,分布式ID生成器方式以及優缺點:

  • UUID
  • 資料庫自增ID
  • 資料庫多主模式
  • 号段模式
  • Redis
  • 雪花算法(SnowFlake)
  • 滴滴出品(TinyID)
  • 百度 (Uidgenerator)
  • 美團(Leaf)

那麼它們都是如何實作?以及各自有什麼優缺點?我們往下看

9種分布式ID生成算法一、為什麼要用分布式ID?二、 分布式ID都有哪些生成方式?總結

1、基于UUID(不推薦)

在Java的世界裡,想要得到一個具有唯一性的ID,首先被想到可能就是

UUID

,畢竟它有着全球唯一的特性。那麼

UUID

可以做

分布式ID

嗎?答案是可以的,但是并不推薦!

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

UUID

的生成簡單到隻有一行代碼,輸出結果 

c2b8c2b9e46c47e3b30dca3b0d447718
           

但UUID卻并不适用于實際的業務需求。像用作訂單号

UUID

這樣的字元串沒有絲毫的意義,看不出和訂單相關的有用資訊;而對于資料庫來說用作業務

主鍵ID

,它不僅是太長還是字元串,存儲性能差查詢也很耗時,是以不推薦用作

分布式ID

優點:

  • 生成足夠簡單,本地生成無網絡消耗,具有唯一性

缺點:

  • 無序的字元串,不具備趨勢自增特性
  • 沒有具體的業務含義
  • 長度過長16 位元組128位,36位長度的字元串,存儲以及查詢對MySQL的性能消耗較大,MySQL官方明确建議主鍵要盡量越短越好,作為資料庫主鍵 

    UUID

     的無序性會導緻資料位置頻繁變動,嚴重影響性能。

2、基于資料庫自增ID(不推薦)

基于資料庫的

auto_increment

自增ID完全可以充當

分布式ID

,具體實作:需要一個單獨的MySQL執行個體用來生成ID,建表結構如下:

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');
           

當我們需要一個ID的時候,向表中插入一條記錄傳回

主鍵ID

,但這種方式有一個比較緻命的缺點,通路量激增時MySQL本身就是系統的瓶頸,用它來實作分布式服務風險比較大,不推薦!

優點:

  • 實作簡單,ID單調自增,數值類型查詢速度快

缺點:

  • DB單點存在當機風險,無法扛住高并發場景

3、基于資料庫叢集模式(不推薦)

前邊說了單點資料庫方式不可取,那對上邊的方式做一些高可用優化,換成主從模式叢集。害怕一個主節點挂掉沒法用,那就做雙主模式叢集,也就是兩個Mysql執行個體都能單獨的生産自增ID。

那這樣還會有個問題,兩個MySQL執行個體的自增ID都從1開始,會生成重複的ID怎麼辦?

解決方案:設定

起始值

自增步長

MySQL_1 配置:

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長
           

MySQL_2 配置:

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長
           

這樣兩個MySQL執行個體的自增ID分别就是:

1、3、5、7、9 

2、4、6、8、10

那如果叢集後的性能還是扛不住高并發咋辦?就要進行MySQL擴容增加節點,這是一個比較麻煩的事。

9種分布式ID生成算法一、為什麼要用分布式ID?二、 分布式ID都有哪些生成方式?總結

從上圖可以看出,水準擴充的資料庫叢集,有利于解決資料庫單點壓力的問題,同時為了ID生成特性,将自增步長按照機器數量來設定。

增加第三台

MySQL

執行個體需要人工修改一、二兩台

MySQL執行個體

的起始值和步長,把

第三台機器的ID

起始生成位置設定在比現有

最大自增ID

的位置遠一些,但必須在一、二兩台

MySQL執行個體

ID還沒有增長到

第三台MySQL執行個體

起始ID

值的時候,否則

自增ID

就要出現重複了,必要時可能還需要停機修改。

優點:

  • 解決DB單點問題

缺點:

  • 不利于後續擴容,而且實際上單個資料庫自身壓力還是大,依舊無法滿足高并發場景。

4、基于資料庫的号段模式

号段模式是當下分布式ID生成器的主流實作方式之一,号段模式可以了解為從資料庫批量的擷取自增ID,每次從資料庫取出一個号段範圍,例如 (1,1000] 代表1000個ID,具體的業務服務将本号段,生成1~1000的自增ID并加載到記憶體。表結構如下:

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '目前最大id',
  step int(20) NOT NULL COMMENT '号段的布長',
  biz_type    int(20) NOT NULL COMMENT '業務類型',
  version int(20) NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)
) 
           

biz_type :代表不同業務類型

max_id :目前最大的可用id

step :代表号段的長度

version :是一個樂觀鎖,每次都更新version,保證并發時資料的正确性

id biz_type max_id step version
1 101 1000 2000

等這批号段ID用完,再次向資料庫申請新号段,對

max_id

字段做一次

update

操作,

update max_id= max_id + step

,update成功則說明新号段擷取成功,新的号段範圍是

(max_id ,max_id +step]

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

由于多業務端可能同時操作,是以采用版本号

version

樂觀鎖方式更新,這種

分布式ID

生成方式不強依賴于資料庫,不會頻繁的通路資料庫,對資料庫的壓力小很多。

5、基于Redis模式

Redis

也同樣可以實作,原理就是利用

redis

的 

incr

指令實作ID的原子性自增。

127.0.0.1:6379> set seq_id 1     // 初始化自增ID為1
OK
127.0.0.1:6379> incr seq_id      // 增加1,并傳回遞增後的數值
(integer) 2
           

redis

實作需要注意一點,要考慮到redis持久化的問題。

redis

有兩種持久化方式

RDB

AOF

  • RDB

    會定時打一個快照進行持久化,假如連續自增但

    redis

    沒及時持久化,而這會Redis挂掉了,重新開機Redis後會出現ID重複的情況。
  • AOF

    會對每條寫指令進行持久化,即使

    Redis

    挂掉了也不會出現ID重複的情況,但由于incr指令的特殊性,會導緻

    Redis

    重新開機恢複的資料時間過長。

6、基于雪花算法(Snowflake)模式

雪花算法(Snowflake)是twitter公司内部分布式項目采用的ID生成算法,開源後廣受國内大廠的好評,在該算法影響下各大公司相繼開發出各具特色的分布式生成器。

9種分布式ID生成算法一、為什麼要用分布式ID?二、 分布式ID都有哪些生成方式?總結

Snowflake

生成的是Long類型的ID,一個Long類型占8個位元組,每個位元組占8比特,也就是說一個Long類型占64個比特。

Snowflake ID組成結構:

正數位

(占1比特)+ 

時間戳

(占41比特)+ 

機器ID

(占5比特)+ 

資料中心

(占5比特)+ 

自增值

(占12比特),總共64比特組成的一個Long類型。

  • 第一個bit位(1bit):Java中long的最高位是符号位代表正負,正數是0,負數是1,一般生成ID都為正數,是以預設為0。
  • 時間戳部分(41bit):毫秒級的時間,不建議存目前時間戳,而是用(目前時間戳 - 固定開始時間戳)的內插補點,可以使産生的ID從更小的值開始;41位的時間戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
  • 工作機器id(10bit):也被叫做

    workId

    ,這個可以靈活配置,機房或者機器号組合都可以。
  • 序列号部分(12bit),自增值支援同一毫秒内同一個節點可以生成4096個ID

根據這個算法的邏輯,隻需要将這個算法用Java語言實作出來,封裝為一個工具方法,那麼各個業務應用可以直接使用該工具方法來擷取分布式ID,隻需保證每個業務應用有自己的工作機器id即可,而不需要單獨去搭建一個擷取分布式ID的應用。

Java版本的

Snowflake

算法實作:

/**
 * Twitter的SnowFlake算法,使用SnowFlake算法生成一個整數,然後轉化為62進制變成一個短位址URL
 *
 * https://github.com/beyondfengyu/SnowFlake
 */
public class SnowFlakeShortUrl {

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

    /**
     * 每一部分占用的位數
     */
    private final static long SEQUENCE_BIT = 12;   //序列号占用的位數
    private final static long MACHINE_BIT = 5;     //機器辨別占用的位數
    private final static long DATA_CENTER_BIT = 5; //資料中心占用的位數

    /**
     * 每一部分的最大值
     */
    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;  //資料中心
    private long machineId;     //機器辨別
    private long sequence = 0L; //序列号
    private long lastTimeStamp = -1L;  //上一次時間戳

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

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

    /**
     * 根據指定的資料中心ID和機器标志ID生成指定的序列号
     *
     * @param dataCenterId 資料中心ID
     * @param machineId    機器标志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;
    }

    /**
     * 産生下一個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) {
            //相同毫秒内,序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列數已經達到最大
            if (sequence == 0L) {
                currTimeStamp = getNextMill();
            }
        } else {
            //不同毫秒内,序列号置為0
            sequence = 0L;
        }

        lastTimeStamp = currTimeStamp;

        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //時間戳部分
                | dataCenterId << DATA_CENTER_LEFT       //資料中心部分
                | machineId << MACHINE_LEFT             //機器辨別部分
                | sequence;                             //序列号部分
    }

    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);

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

7、百度(uid-generator)

uid-generator

是由百度技術部開發,項目GitHub位址

https://github.com/baidu/uid-generator

uid-generator

是基于

Snowflake

算法實作的,與原始的

snowflake

算法不同在于,

uid-generator

支援自

定義時間戳

工作機器ID

和 

序列号

 等各部分的位數,而且

uid-generator

中采用使用者自定義

workId

的生成政策。

uid-generator

需要與資料庫配合使用,需要新增一個

WORKER_NODE

表。當應用啟動時會向資料庫表中去插入一條資料,插入成功後傳回的自增ID就是該機器的

workId

資料由host,port組成。

對于

uid-generator

 ID組成結構:

workId

,占用了22個bit位,時間占用了28個bit位,序列化占用了13個bit位,需要注意的是,和原始的

snowflake

不太一樣,時間的機關是秒,而不是毫秒,

workId

也不一樣,而且同一應用每次重新開機就會消費一個

workId

參考文獻

https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

8、美團(Leaf)

Leaf

由美團開發,github位址:

https://github.com/Meituan-Dianping/Leaf

Leaf

同時支援号段模式和

snowflake

算法模式,可以切換使用。

号段模式

先導入源碼 https://github.com/Meituan-Dianping/Leaf ,在建一張表

leaf_alloc

DROP TABLE IF EXISTS `leaf_alloc`;

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '業務key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '目前已經配置設定了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步長,也是動态調整的最小步長',
  `description` varchar(256)  DEFAULT NULL COMMENT '業務key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '資料庫維護的更新時間',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
           

然後在項目中開啟

号段模式

,配置對應的資料庫資訊,并關閉

snowflake

模式

leaf.name=com.sankuai.leaf.opensource.test
leaf.segment.enable=true
leaf.jdbc.url=jdbc:mysql://localhost:3306/leaf_test?useUnicode=true&characterEncoding=utf8&characterSetResults=utf8
leaf.jdbc.username=root
leaf.jdbc.password=root

leaf.snowflake.enable=false
#leaf.snowflake.zk.address=
#leaf.snowflake.port=
           

啟動

leaf-server

 子產品的 

LeafServerApplication

項目就跑起來了

号段模式擷取分布式自增ID的測試url :

http://localhost:8080/api/segment/get/leaf-segment-test

監控号段模式:

http://localhost:8080/cache

snowflake模式

Leaf

的snowflake模式依賴于

ZooKeeper

,不同于

原始snowflake

算法也主要是在

workId

的生成上,

Leaf

workId

是基于

ZooKeeper

的順序Id來生成的,每個應用在使用

Leaf-snowflake

時,啟動時都會都在

Zookeeper

中生成一個順序Id,相當于一台機器對應一個順序節點,也就是一個

workId

leaf.snowflake.enable=true
leaf.snowflake.zk.address=127.0.0.1
leaf.snowflake.port=2181
           

snowflake模式擷取分布式自增ID的測試url:

http://localhost:8080/api/snowflake/get/test
傳送門:美團(Leaf)分布式ID算法(實戰)

9、滴滴(Tinyid)

Tinyid

由滴滴開發,Github位址:

https://github.com/didi/tinyid

Tinyid

是基于号段模式原理實作的與

Leaf

如出一轍,每個服務擷取一個号段(1000,2000]、(2000,3000]、(3000,4000]

9種分布式ID生成算法一、為什麼要用分布式ID?二、 分布式ID都有哪些生成方式?總結

Tinyid

提供

http

tinyid-client

兩種方式接入

Http方式接入

(1)導入Tinyid源碼:

git clone https://github.com/didi/tinyid.git

(2)建立資料表:

CREATE TABLE `tiny_id_info` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主鍵',
  `biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '業務類型,唯一',
  `begin_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '開始id,僅記錄初始值,無其他含義。初始化時begin_id和max_id應相同',
  `max_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '目前最大id',
  `step` int(11) DEFAULT '0' COMMENT '步長',
  `delta` int(11) NOT NULL DEFAULT '1' COMMENT '每次id增量',
  `remainder` int(11) NOT NULL DEFAULT '0' COMMENT '餘數',
  `create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '建立時間',
  `update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新時間',
  `version` bigint(20) NOT NULL DEFAULT '0' COMMENT '版本号',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_biz_type` (`biz_type`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'id資訊表';
           
CREATE TABLE `tiny_id_token` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
  `token` varchar(255) NOT NULL DEFAULT '' COMMENT 'token',
  `biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '此token可通路的業務類型辨別',
  `remark` varchar(255) NOT NULL DEFAULT '' COMMENT '備注',
  `create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '建立時間',
  `update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'token資訊表';
           
INSERT INTO `tiny_id_info` 
(`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`)
VALUES
    (1, 'test', 1, 1, 100000, 1, 0, '2018-07-21 23:52:58', '2018-07-22 23:19:27', 1);

INSERT INTO `tiny_id_info` 
(`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`)
VALUES
    (2, 'test_odd', 1, 1, 100000, 2, 1, '2018-07-21 23:52:58', '2018-07-23 00:39:24', 3);


INSERT INTO `tiny_id_token` 
(`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`)
VALUES
    (1, '0f673adf80504e2eaa552f5d791b644c', 'test', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');

INSERT INTO `tiny_id_token` 
(`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`)
VALUES
    (2, '0f673adf80504e2eaa552f5d791b644c', 'test_odd', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');
           

 (3)配置資料庫:

datasource.tinyid.names=primary
datasource.tinyid.primary.driver-class-name=com.mysql.jdbc.Driver
datasource.tinyid.primary.url=jdbc:mysql://ip:port/databaseName?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8
datasource.tinyid.primary.username=root
datasource.tinyid.primary.password=123456
           

(4)啟動

tinyid-server

後測試

擷取分布式自增ID: http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c'
傳回結果: 3
           
批量擷取分布式自增ID:
http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c&batchSize=10'
傳回結果:  4,5,6,7,8,9,10,11,12,13
           

Java用戶端方式接入

重複Http方式的(2)(3)操作

引入依賴

       <dependency>
            <groupId>com.xiaoju.uemc.tinyid</groupId>
            <artifactId>tinyid-client</artifactId>
            <version>${tinyid.version}</version>
        </dependency>
           

配置檔案

tinyid.server =localhost:9999
tinyid.token =0f673adf80504e2eaa552f5d791b644c
           

test

 、

tinyid.token

是在資料庫表中預先插入的資料,

test

 是具體業務類型,

tinyid.token

表示可通路的業務類型

// 擷取單個分布式自增ID
Long id =  TinyId . nextId( " test " );

// 按需批量分布式自增ID
List< Long > ids =  TinyId . nextId( " test " , 10 );
           
 傳送門:滴滴(Tinyid)分布式ID算法(實戰)

總結

本文隻是簡單介紹一下每種分布式ID生成器,旨在給大家一個詳細學習的方向,每種生成方式都有它自己的優缺點,具體如何使用還要看具體的業務需求。