集群高并發(fā)情況下如何保證分布式唯一全局Id生成

為什么需要分布式全局唯一Id,以及分布式Id的業(yè)務需求

在復雜分布式系統(tǒng)中,往往需要對大量的數據和消息進行唯一標識

如在美團點評的金融鸟蜡、支付、餐飲、酒店;

貓眼電影等產品的系統(tǒng)中數據日漸增長,對數據分庫分表后需要有一個唯一Id來標識一條數據或消息;

特別一點的如訂單先鱼、騎手枕赵、優(yōu)惠券也都需要有唯一Id坐標是.

此時一個能夠生成全局唯一Id的系統(tǒng)是非常必要的

Id生成規(guī)則部分硬性要求

1. 全局唯一

2. 趨勢遞增

在Mysql的InnoDB引擎中使用的是聚集索引,由于多數RDBMS使用Btree的數據結構來存儲索引數據,在主鍵的選擇上面我們應該盡量使用有序的主鍵來保證寫入性能

3. 單調遞增

盡量保證下一個Id一定大于上一個Id,例如事務版本號剿吻、IM增量消息譬猫、排序等特殊需求

4. 信息安全

如果Id是連續(xù)的,惡意用戶的扒取工作就非常容易做了,直接按照順序下載指定URL即可;如果是訂單號就更危險了,競對可以直接知道我們一天的單量.所以在一些應用場景下,需要Id無規(guī)則不規(guī)則,讓競爭對手不好猜

5. 含時間戳

這樣就能夠在開發(fā)中快速了解這個分布式Id的生成時間

Id號生成系統(tǒng)的可用性要求

• 高可用

發(fā)一個獲取分布式Id的請求,服務器就要保證99.999%的情況下給我創(chuàng)建一個唯一分布式Id

• 低延遲

發(fā)一個獲取分布式Id的請求,服務器要快,極速

• 高QPS

例如并發(fā)一口氣10萬個創(chuàng)建分布式Id請求同時殺過來,服務器要頂得住且一下子成功創(chuàng)建10萬個分布式Id

一般通用方案

• UUID

是什么: UUID(Univesally Unique Identifler)的標準型包含32個16進制數字,以連字號分為五段,形式為8-4-4-4-12的36個字符

性能非常高: 本地生成,沒有網絡消耗

如果只是考慮唯一性:OK,關鍵是他無序,入數據庫性能比較差

為什么無序的UUID會導致入庫性能變差呢?

1. 無序,無法預測他的生成順序,不能生成遞增有序的數字.首先分布式Id一般都會作為主鍵,但是按照mysql官方推薦的主鍵盡量越短越好,UUID每一個都很長,所以不是很推薦
2. 主鍵,ID作為主鍵時在特定的環(huán)境會存在一些問題.比如做DB主鍵的場景下,UUID就非常不適用MySQL官方有明確的建議主鍵盡量越短越好36個字符長度的UUID不符合要求
3. 索引,B+樹索引的分裂.既然分布式Id是主鍵,然后主鍵是包含索引的,然后mysql的索引是通過B+樹來實現(xiàn)的,每一次新的UUID數據的插入,為了查詢的優(yōu)化,都會對索引底層的B+樹進行修改,因為UUID是無序的,所以每一次UUID數據的插入都會對主鍵地城的B+樹進行很大的修改,這一點很不好.插入完全無序,不但會導致一些中間節(jié)點產生分裂,也會白白創(chuàng)造出很多不飽和的節(jié)點,這樣大大降低了數據庫插入的性能

• 數據庫自增主鍵(小公司)

在分布式里面,數據庫的自增Id機制的主要原理是:數據庫自增Id和mysql數據庫的replace into實現(xiàn)的

這里的replace into跟insert功能類似

不同點在于: replace into首先嘗試插入數據列表中,如果發(fā)現(xiàn)表中已經有此行數據(根據主鍵或唯一索引判斷)則先刪除,再插入,否則直接插入新數據.

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

例: REPLACE INTO 表 (列..) values ('value'..)

那數據庫自增ID機制適合做分布式ID嗎?答案是不太合適

1. 系統(tǒng)水平擴展比較困難,比如定義好了步長和機器臺數之后,如果要添加機器該怎么做?假設現(xiàn)在只有一臺機器發(fā)號是1.2.3.4.5(步長是1),這個時候需要擴容機器一臺.可以這樣做;把第二臺機器的初始值設置的比第一臺超過很多,貌似還好,現(xiàn)在想象一下如果我們線上有100臺機器,這個時候要擴容該怎么做?簡直是噩夢.所以系統(tǒng)水平擴展方案復雜難以實現(xiàn)
2. 數據庫壓力還是很大,每次獲取ID都得讀寫一次數據庫,非常影響性能,不符合分布式ID里面的延遲低和高QPS的規(guī)則(在高并發(fā)下,如果都去數據庫里面獲取ID,那是非常影響性能的)

• Reids生成全局Id策略(部署麻煩)

因為Redis是單線的天生保證原子性,可以使用原子操作INCR和INCRBY來實現(xiàn)

注意: 在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把存儲系統(tǒng)從Mysql遷移到Cassandra(由Facebook開發(fā)一套開源分布式NoSQL數據庫系統(tǒng))因為Cassandra沒有順序ID生成機制,所以開發(fā)了一套全局唯一ID生成服務

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

1. twitter的SnowFlake生成ID能夠按照時間有序生成
2. SnowFlake算法生成id的結果是一個64bit大小的整數,為一個Long型(轉換成字符串后長度為19)
3. 分布式系統(tǒng)內不會產生ID碰撞(由datacenter和workerId作區(qū)分)并且效率較高

雪花算法組成

xuehua.png

號段解析

• 1bit: 不用,因為二進制中最高位是符號位,1表示負數,0表示正數,生成的id一般都是用整數,所以最高位固定為0.
• 41bit-時間戳: 用來記錄時間戳,毫秒級.41位可以表示2^{(41)-1個數字;如果只用來表示正整數(計算機中正數包含0),可以表示的數值范圍是:0至2}(41)-1,減1是因為可表示的數值范圍是從0開始算的,而不是1'也就是說41位可以表示2^{(41)-1個毫秒的值,轉化成單位年則是2}(41)-1/(1000606024365)=69年(夠用到2039-09-07)
• 10bit-工作機器id: 用來記錄工作機器的id.可以部署在2^{(10)=1024個節(jié)點,包括5位datacenterId和5位workerId;5位(bit)可以表示的最大正整數是2}(5)-1=31,即可以用0,1,2,3,...31這32個數字,來表示不同的datacenterId和workerId
• 12bit-序列號: 用來記錄同一毫秒內產生的不同id.12位(bit)可以表示最大正整數是2^{12}-1=4095,即可以用0,1,2,3...4094這4095個數字,來表示同一時間戳內產生的4095個ID序號

SnowFlake可以保證: 所有聲稱的id按時間趨勢遞增,整個分布式系統(tǒng)內不會產生重復id(因為有datacenterId和workerId來區(qū)分)

源碼

目前雪花算法已經開源了,除非自己想手動配置機器碼和唯一識別碼等,不用刻意去了解底層機制,感興趣的可以去github翻閱源碼
gitHub

使用

Hutool工具包 官網

有一定經驗的同學應該都用過,非常爽,例如官網的說法比如要計算MD5為例:

[以前] 打開搜索引擎->搜"java MD5加密"->打開某篇博客->復制粘貼->改改好用

[現(xiàn)在] 引入Hutool-> SecureUtil.md5()

SpringBoot項目的同學,可以參考我整理的封裝工具類,拿去用就好了

package com.mac.zimu.util;

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

import javax.annotation.PostConstruct;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.stream.Stream;

/**
 * @PROJECT_NAME: 杭州品茗信息技術有限公司
 * @DESCRIPTION: 獲取雪花算法Id
 * @author: 徐子木
 * @DATE: 2020/12/15 8:29 下午
 */
@Slf4j
public class SnowFlakeUtil {

    private static long workerId = 0;
    private static long dataCenterId = 1;
    private static Snowflake snowflake = IdUtil.createSnowflake(workerId,dataCenterId);

    @PostConstruct
    public void init() {
        try {
            workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
            log.info("當前機器的workId: {}", workerId);
        } catch (Exception e) {
            e.printStackTrace();
            log.error("當前機器的workId獲取失敗", e);
            workerId = NetUtil.getLocalhostStr().hashCode();
        }
    }

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

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

    public static void main(String[] args) {
        ExecutorService executorService = Executors.newFixedThreadPool(5);
        Stream.iterate(0,x->x+1).
                limit(20).
                forEach(x->{
                    executorService.submit(()->{
                        long id = SnowFlakeUtil.snowflakeId();
                        System.out.println(id);
                    });
                });
        executorService.shutdown();
    }


}

優(yōu)缺點

• 優(yōu)點:
  毫秒數在高位,自增序列在低位,整個ID都是趨勢遞增的.不依賴數據庫等第三方系統(tǒng),以服務的方式部署,穩(wěn)定性更高,生成的Id的性能也是非常高的.可以根據自身業(yè)務特性分配bit位,非常靈活.

• 缺點:
  依賴機器時鐘,如果機器時鐘回撥,會導致重復ID生成.在單機上是遞增的,但是由于設計到分布式環(huán)境,每臺機器上的時鐘不可能完全同步,有時候會出現(xiàn)不是全局遞增的情況(此缺點可以認為無所謂,一般分布式id只要求趨勢遞增,而不會嚴格要求遞增,90%的需求都只要求趨勢遞增)!