分布式ID生成之雪花算法
分布式ID生成方案
唯一ID可以標(biāo)識(shí)數(shù)據(jù)的唯一性颂暇，在分布式系統(tǒng)中生成唯一ID的方案有很多搪柑，常見的方式大概有以下幾種方式：
UUID 隨機(jī)數(shù)
數(shù)據(jù)庫特性
Redis 生成 ID
snowflake 雪花算法
關(guān)于雪花算法
有這樣一種說法，自然界中并不存在兩片完全一樣的雪花(世界上沒有兩片相同的樹葉)并徘，每一片雪花都擁有自己漂亮獨(dú)特的形狀且是獨(dú)一無二。
雪花算法也表示生成的 ID 如雪花般獨(dú)一無二，SnowFlake 算法昼榛，是 Twitter 開源的分布式 ID 生成算法。
雪花算法概述
雪花算法生成的 ID 是純數(shù)字且具有時(shí)間順序的剔难。其原始版本是 scala 版胆屿，后面出現(xiàn)了許多其他語言的版本如Java、C++等偶宫。
組成結(jié)構(gòu)
雪花算法-組成結(jié)構(gòu)
大致是由：首位無效符非迹、時(shí)間戳差值，機(jī)器(進(jìn)程)編碼纯趋，序列號(hào)四部分組成憎兽。
1 bit：首位無效，為啥呢吵冒？
因?yàn)槎M(jìn)制里第一個(gè) bit 為如果是 1唇兑，那么都是負(fù)數(shù)，但是我們生成的 id 都是正數(shù)桦锄，所以第一個(gè) bit 統(tǒng)一都是 0扎附。
41 bit：表示的是時(shí)間戳，單位是毫秒
41 bit 可以表示的數(shù)字多達(dá) 2^41 - 1结耀，也就是可以標(biāo)識(shí) 2 ^ 41 - 1 個(gè)毫秒值留夜，換算成年就是表示 69 年的時(shí)間。
10 bit：記錄工作機(jī)器 id图甜，代表的是這個(gè)服務(wù)最多可以部署在 2^10 臺(tái)機(jī)器上碍粥，也就是 1024 臺(tái)機(jī)器
10 bit 里 5 個(gè) bit 代表機(jī)房 id，5 個(gè) bit 代表機(jī)器 id黑毅。意思就是最多代表 2 ^ 5 個(gè)機(jī)房（32 個(gè)機(jī)房）嚼摩，每個(gè)機(jī)房里可以代表 2 ^ 5 個(gè)機(jī)器（32 臺(tái)機(jī)器），也可以根據(jù)自己公司的實(shí)際情況確定。
12 bit：這個(gè)是用來記錄同一個(gè)毫秒內(nèi)產(chǎn)生的不同 id
12 bit 可以代表的最大正整數(shù)是 2 ^ 12 - 1 = 4096枕面，也就是說可以用這個(gè) 12 bit 代表的數(shù)字來區(qū)分同一個(gè)毫秒內(nèi)的 4096 個(gè)不同的 id愿卒。
雪花算法優(yōu)點(diǎn)
自增、有序潮秘、適合分布式場(chǎng)景琼开，生成時(shí)不依賴于數(shù)據(jù)庫，完全在內(nèi)存中生成枕荞，每秒能生成數(shù)百萬的自增 ID柜候，存入數(shù)據(jù)庫中，索引效率高躏精。
時(shí)間位：可以根據(jù)時(shí)間進(jìn)行排序渣刷，有助于提高查詢速度。
機(jī)器 ID 位：適用于分布式環(huán)境下對(duì)多節(jié)點(diǎn)的各個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)矗烛，可以具體根據(jù)節(jié)點(diǎn)數(shù)和部署情況設(shè)計(jì)劃分機(jī)器位 10 位長(zhǎng)度飞主，如劃分5位表示進(jìn)程位等。
序列號(hào)位：是一系列的自增id高诺，可以支持同一節(jié)點(diǎn)同一毫秒生成多個(gè) ID 序號(hào)，12 位的計(jì)數(shù)序列號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生 4096 個(gè) ID 序號(hào)
snowflake 算法可以根據(jù)項(xiàng)目情況以及自身需要進(jìn)行一定的修改碾篡。
基于 Snowflake 算法的其他開源方案 百度 uid-generator 虱而、滴滴 Tinyid 、美團(tuán)leaf
Java實(shí)現(xiàn)雪花雪花系統(tǒng)
使用Java語言實(shí)現(xiàn)雪花算法的ID生成器开泽，可以參考以下代碼牡拇。這個(gè)實(shí)現(xiàn)同樣遵循了雪花算法的基本結(jié)構(gòu)，包括1位符號(hào)位穆律、41位時(shí)間戳惠呼、10位機(jī)器標(biāo)識(shí)（5位數(shù)據(jù)中心ID和5位工作機(jī)器ID）以及12位序列號(hào)。我們將這些位數(shù)放在了配置文件中峦耘，家人們可以根據(jù)實(shí)際情況進(jìn)行調(diào)整剔蹋。在這個(gè)代碼中，我們提供了單id生成接口和批量id生成接口辅髓。代碼如下：
配置信息 application.yml
server:
? port: 8000
snowflake:
? #數(shù)據(jù)中心id位數(shù)
? datacenterBits: 5
? # 機(jī)器id位數(shù)
? workerBits: 5
? # 序列id所占位數(shù)
? sequenceBits: 12
? # 數(shù)據(jù)中心id,范圍0-2^5-1
? datacenterId: 1
? # 機(jī)器id,范圍0-2^5-1
? workerId: 1
? # 時(shí)間戳起始點(diǎn)（2024-01-01 00::00:00 的毫秒數(shù)）
? twepoch: 1704038400000
? #單次批量生成id的最大數(shù)量? 默認(rèn)10萬
? maxBatchCount: 100000
SnowflakeProperties
import lombok.Data;
import org.springframework.boot.context.properties.ConfigurationProperties;
import org.springframework.stereotype.Component;
@Component
@ConfigurationProperties(prefix ="snowflake")
@Data
public class SnowflakeProperties {
? ? //數(shù)據(jù)中心id
? ? private Long datacenterId;
? ? //數(shù)據(jù)中心id位數(shù)
? ? private Long datacenterBits;
? ? //機(jī)器id
? ? private Long workerId;
? ? //機(jī)器id位數(shù)
? ? private Long workerBits;
? ? //序列id所占位數(shù)
? ? private Long sequenceBits;
? ? // 時(shí)間戳起始點(diǎn)（毫秒）
? ? private? Long twepoch;
? ? //單次批量生成id的最大數(shù)量
? ? private Integer maxBatchCount;
}
SnowflakeIdGenerator
package cn.xj.snowflake.generator;
import cn.xj.snowflake.config.SnowflakeProperties;
import org.springframework.stereotype.Component;
import java.util.ArrayList;
import java.util.List;
@Component
public class SnowflakeIdGenerator {
? ? //數(shù)據(jù)中心id
? ? private final long datacenterId;
? ? //數(shù)據(jù)中心id位數(shù)
? ? private final long datacenterBits;
? ? //機(jī)器id
? ? private final long workerId;
? ? //機(jī)器id位數(shù)
? ? private final long workerBits;
? ? //序列id所占位數(shù)
? ? private final? long sequenceBits;
? ? // 時(shí)間戳起始點(diǎn)（毫秒）
? ? private final long twepoch;
? ? //數(shù)據(jù)中心最大id
? ? private final long maxDatacenterId;
? ? //機(jī)器最大id
? ? private final long maxWorkerId;
? ? //最大序列號(hào)
? ? private final long maxSequence;
? ? //機(jī)器id左移位數(shù)
? ? private final long workerIdShift;
? ? //數(shù)據(jù)中心id左移位數(shù)
? ? private final long datacenterIdShift;
? ? //毫秒數(shù)左移位數(shù)
? ? private final long timestampLeftShift;
? ? //單次批量生成id的最大數(shù)量
? ? private final int maxBatchCount;
? ? // 序列號(hào)
? ? private long sequence = 0L;
? ? // 上一次時(shí)間戳
? ? private long lastTimestamp = -1L;
? ? public SnowflakeIdGenerator(SnowflakeProperties properties) {
? ? ? ? //數(shù)據(jù)中心id
? ? ? ? this.datacenterId = properties.getDatacenterId();
? ? ? ? //數(shù)據(jù)中心id位數(shù)
? ? ? ? this.datacenterBits = properties.getDatacenterBits();
? ? ? ? //機(jī)器id
? ? ? ? this.workerId = properties.getWorkerId();
? ? ? ? //機(jī)器id位數(shù)
? ? ? ? this.workerBits = properties.getWorkerBits();
? ? ? ? //序列id所占位數(shù)
? ? ? ? this.sequenceBits = properties.getSequenceBits();
? ? ? ? // 時(shí)間戳起始點(diǎn)（毫秒）
? ? ? ? this.twepoch = properties.getTwepoch();
? ? ? ? //數(shù)據(jù)中心最大id
? ? ? ? this.maxDatacenterId = -1L ^ (-1L << properties.getDatacenterBits());
? ? ? ? //機(jī)器最大id
? ? ? ? this.maxWorkerId = -1L ^ (-1L << properties.getWorkerBits());
? ? ? ? //最大序列號(hào)
? ? ? ? this.maxSequence = -1L ^ (-1L << properties.getSequenceBits());
? ? ? ? this.workerIdShift = properties.getSequenceBits();
? ? ? ? //數(shù)據(jù)中心id左移位數(shù)
? ? ? ? this.datacenterIdShift = properties.getSequenceBits() + properties.getWorkerBits();
? ? ? ? //毫秒數(shù)左移位數(shù)
? ? ? ? this.timestampLeftShift = properties.getSequenceBits() + properties.getWorkerBits() + properties.getSequenceBits();
? ? ? ? //單次批量生成id的最大數(shù)量
? ? ? ? this.maxBatchCount = properties.getMaxBatchCount();
? ? ? ? // 校驗(yàn)datacenterId和workerId是否超出最大值
? ? ? ? if (datacenterId > maxDatacenterId || datacenterId < 0) {
? ? ? ? ? ? throw new IllegalArgumentException(String.format("數(shù)據(jù)中心Id不能大于%d或小于0", maxDatacenterId));
? ? ? ? }
? ? ? ? if (workerId > maxWorkerId || workerId < 0) {
? ? ? ? ? ? throw new IllegalArgumentException(String.format("機(jī)器Id不能大于%d或小于0", maxWorkerId));
? ? ? ? }
? ? }
? ? /**
? ? * id生成方法(單個(gè))
? ? * @return
? ? */
? ? public synchronized long nextId() {
? ? ? ? //獲取當(dāng)前時(shí)間的毫秒數(shù)
? ? ? ? long timestamp = currentTime();
? ? ? ? //判斷時(shí)鐘是否回?fù)?/p>
? ? ? ? if (timestamp < lastTimestamp) {
? ? ? ? ? ? throw new RuntimeException(String.format("時(shí)鐘回?fù)芷溃負(fù)芎撩霐?shù)：%d", lastTimestamp - timestamp));
? ? ? ? }
? ? ? ? //設(shè)置序列號(hào)
? ? ? ? if (lastTimestamp == timestamp) {
? ? ? ? ? ? //設(shè)置序列號(hào)遞增，如果當(dāng)前毫秒內(nèi)序列號(hào)已經(jīng)達(dá)到最大值洛口，則直到下一毫秒在重新從0開始計(jì)算序列號(hào)
? ? ? ? ? ? sequence = (sequence + 1) & maxSequence;
? ? ? ? ? ? if (sequence == 0) {
? ? ? ? ? ? ? ? timestamp = tilNextMillis(lastTimestamp);
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? sequence = 0L;
? ? ? ? }
? ? ? ? lastTimestamp = timestamp;
? ? ? ? //計(jì)算id
? ? ? ? return ((timestamp - twepoch) << timestampLeftShift) |
? ? ? ? ? ? ? ? (datacenterId << datacenterIdShift) |
? ? ? ? ? ? ? ? (workerId << workerIdShift) |
? ? ? ? ? ? ? ? sequence;
? ? }
? ? /**
? ? * id生成方法(批量)
? ? * @return
? ? */
? ? public synchronized List<Long> nextIds(int count) {
? ? ? ? if (count > maxBatchCount || count < 0) {
? ? ? ? ? ? throw new IllegalArgumentException(String.format("批量生成id的數(shù)量不能大于%d或小于0", maxBatchCount));
? ? ? ? }
? ? ? ? List<Long> ids = new ArrayList<>(count);
? ? ? ? for (int i = 0; i < count; i++) {
? ? ? ? ? ? ids.add(nextId());
? ? ? ? }
? ? ? ? return ids;
? ? }
? ? /**
? ? * 循環(huán)等待直至獲取到新的毫秒時(shí)間戳
? ? * 確保生成的時(shí)間戳總是向前移動(dòng)的矫付，即使在相同的毫秒內(nèi)請(qǐng)求多個(gè)ID時(shí)也能保持唯一性。
? ? */
? ? private long tilNextMillis(long lastTimestamp) {
? ? ? ? long timestamp = currentTime();
? ? ? ? // 循環(huán)等待直至獲取到新的毫秒時(shí)間戳
? ? ? ? while (timestamp <= lastTimestamp) {
? ? ? ? ? ? timestamp = currentTime();
? ? ? ? }
? ? ? ? return timestamp;
? ? }
? ? /**
? ? * 獲取當(dāng)前時(shí)間的毫秒數(shù)
? ? */
? ? private long currentTime() {
? ? ? ? return System.currentTimeMillis();
? ? }
}
這個(gè)Java類SnowflakeIdWorker封裝了雪花算法的核心邏輯第焰。它允許通過構(gòu)造函數(shù)指定數(shù)據(jù)中心ID和機(jī)器ID买优，并提供了nextId()和nextIds()方法用于生成唯一的ID。該方法通過同步關(guān)鍵字synchronized保證了線程安全。
SnowflakeApi
import cn.xj.snowflake.generator.SnowflakeIdGenerator;
import jakarta.annotation.Resource;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RestController;
import java.util.List;
@RestController
public class SnowflakeApi {
? ? @Resource
? ? private SnowflakeIdGenerator snowflakeIdGenerator;
? ? @PostMapping("/snowflake/api/nextId")
? ? public Long nextId(){
? ? ? ? return snowflakeIdGenerator.nextId();
? ? }
? ? @PostMapping("/snowflake/api/nextIds")
? ? public List<Long> nextIds(@RequestBody int count){
? ? ? ? return snowflakeIdGenerator.nextIds(count);
? ? }
}
接口調(diào)用詳情
單個(gè)id生成接口nextId:
批量id生成接口nextIds:我們此處生成了10萬條id,響應(yīng)時(shí)長(zhǎng)不到1s
雪花算法的開源代碼或者優(yōu)秀代碼示例有很多杀赢，但思想基本是一樣的烘跺。
雪花算法的缺點(diǎn)
雪花算法在單機(jī)系統(tǒng)上 ID 是遞增的，但強(qiáng)依賴與系統(tǒng)時(shí)間的一致性葵陵，如果系統(tǒng)時(shí)間被回?fù)芑蛘吒淖円狠赡軙?huì)造成 ID 沖突或者重復(fù)。在分布式系統(tǒng)多節(jié)點(diǎn)的情況下脱篙，所有節(jié)點(diǎn)的時(shí)鐘并不能保證不完全同步娇钱，所以有可能會(huì)出現(xiàn)不是全局遞增的情況。
總結(jié)
分布式唯一 ID 的方案有很多绊困，本文主要討論了雪花算法文搂，組成結(jié)構(gòu)大致分為了無效位泼舱、時(shí)間位识埋、機(jī)器位和序列號(hào)位操漠。其特點(diǎn)是自增毯焕、有序逗栽、純數(shù)字組成查詢效率高且不依賴于數(shù)據(jù)庫糠惫。
