前言
在應(yīng)用程序中地来，唯一ID是一個(gè)系統(tǒng)必備的功能。體現(xiàn)在：
- 單體應(yīng)用：?jiǎn)误w應(yīng)用用于唯一標(biāo)識(shí)用戶熙掺、訂單等的唯一標(biāo)識(shí)需要保證應(yīng)用內(nèi)唯一未斑。
- 半分布式系統(tǒng)：分區(qū)分服的游戲應(yīng)用，在合服時(shí)為了避免數(shù)據(jù)沖突需要保證所有的ID全局唯一币绩。
- 全分布式系統(tǒng)：大型的電商蜡秽、外賣、金融系統(tǒng)等的訂單ID缆镣、用戶ID等需要全局唯一芽突。
單體應(yīng)用的唯一ID可以簡(jiǎn)單使用數(shù)據(jù)庫(kù)的自增ID來(lái)實(shí)現(xiàn)即可，在這里我們不予以討論董瞻。我們討論的是在半分布式和全分布式系統(tǒng)中的唯一ID生成的方案寞蚌。
ID生成系統(tǒng)的需求
- 全局唯一性：不能出現(xiàn)重復(fù)的ID，這是最基本的要求钠糊。
- 趨勢(shì)遞增：MySQL InnoDB引擎使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)索引數(shù)據(jù)煞聪，在主鍵的選擇上面我們應(yīng)盡量使用有序的主鍵保證寫(xiě)入性能昔脯。
- 單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID云稚。幾乎所有的關(guān)系性數(shù)據(jù)庫(kù)都使用B+Tree來(lái)進(jìn)行數(shù)據(jù)在硬盤(pán)上的存儲(chǔ)静陈，為了避免葉分裂拐格，需要保證新的ID總是大于之前所有的ID刑赶。
- 信息安全：如果ID是連續(xù)遞增的撞叨，惡意用戶就可以很容易的窺見(jiàn)訂單號(hào)的規(guī)則牵敷，從而猜出下一個(gè)訂單號(hào)枷餐，如果是競(jìng)爭(zhēng)對(duì)手尖淘，就可以直接知道我們一天的訂單量村生。所以在某些場(chǎng)景下趁桃，需要ID無(wú)規(guī)則卫病。
技術(shù)方案
1. UUID
UUID是指在一臺(tái)機(jī)器在同一時(shí)間中生成的數(shù)字在所有機(jī)器中都是唯一的蟀苛。按照開(kāi)放軟件基金會(huì)(OSF)制定的標(biāo)準(zhǔn)計(jì)算帜平，用到了以太網(wǎng)卡地址裆甩、納秒級(jí)時(shí)間嗤栓、芯片ID碼和許多可能的數(shù)字箍邮。
UUID由以下幾部分的組成：
（1）當(dāng)前日期和時(shí)間。
（2）時(shí)鐘序列摔敛。
（3）全局唯一的IEEE機(jī)器識(shí)別號(hào)马昙，如果有網(wǎng)卡行楞，從網(wǎng)卡MAC地址獲得子房，沒(méi)有網(wǎng)卡以其他方式獲得证杭。
標(biāo)準(zhǔn)的UUID格式為：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)解愤，以連字號(hào)分為五段形式的36個(gè)字符乎莉，示例：550e8400-e29b-41d4-a716-446655440000
很多語(yǔ)言中都提供了原生的生成UUID的方法惋啃。比如：
C#
new GUID()
JAVA
UUID.randomUUID()
優(yōu)點(diǎn)
- 性能非常高：本地生成边灭，沒(méi)有網(wǎng)絡(luò)消耗绒瘦。
缺點(diǎn)
- 不易存儲(chǔ)：UUID太長(zhǎng)椭坚，16字節(jié)128位善茎，通常以36長(zhǎng)度的字符串表示。
- 信息不安全：基于MAC地址生成UUID的算法可能會(huì)造成MAC地址泄露航邢，這個(gè)漏洞曾被用于尋找梅麗莎病毒的制作者位置膳殷。
- ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問(wèn)題赚窃，比如做DB主鍵的場(chǎng)景下勒极，效率太低辱匿。
2. MongoDB
MongoDB的ObjectId 采用12字節(jié)的存儲(chǔ)空間炫彩，每個(gè)字節(jié)兩位16進(jìn)制數(shù)字江兢，是一個(gè)24位的字符串划址。
生成規(guī)則如下：
[0,1,2,3] [4,5,6] [7,8] [9,10,11]
時(shí)間戳 |機(jī)器碼 |PID |計(jì)數(shù)器
- 前四字節(jié)是時(shí)間戳夺颤，可以提供秒級(jí)別的唯一性世澜。
- 接下來(lái)三字節(jié)是所在主機(jī)的唯一標(biāo)識(shí)符寥裂，通常是機(jī)器主機(jī)名的散列值封恰。
- 接下來(lái)兩字節(jié)是產(chǎn)生ObjectId的PID诺舔，確保同一臺(tái)機(jī)器上并發(fā)產(chǎn)生的ObjectId是唯一的低飒。
前九字節(jié)保證了同一秒鐘不同機(jī)器的不同進(jìn)程產(chǎn)生的ObjectId時(shí)唯一的褥赊。 - 最后三字節(jié)是自增計(jì)數(shù)器拌喉，確保相同進(jìn)程同一秒鐘產(chǎn)生的ObjectId是唯一的。
優(yōu)點(diǎn)
缺點(diǎn)
- 不易存儲(chǔ)：ObjectId 太長(zhǎng)琅坡，12字節(jié)96位榆俺，通常以24長(zhǎng)度的字符串表示茴晋。
- ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問(wèn)題诺擅，比如做DB主鍵的場(chǎng)景下啡直，效率太低酒觅。
- ID作為索引時(shí)舷丹，導(dǎo)致索引的數(shù)據(jù)量太大颜凯，浪費(fèi)磁盤(pán)空間症概。
3. 數(shù)據(jù)庫(kù)
使用數(shù)據(jù)庫(kù)的ID自增策略彼城，如 MySQL 的 auto_increment逼友。
優(yōu)點(diǎn)
- 數(shù)據(jù)庫(kù)生成的ID絕對(duì)有序
缺點(diǎn)
- 需要獨(dú)立部署數(shù)據(jù)庫(kù)實(shí)例
- 有網(wǎng)絡(luò)請(qǐng)求帜乞，速度慢
- 有單點(diǎn)故障的風(fēng)險(xiǎn)黎烈。要解決這個(gè)問(wèn)題照棋，就得引入集群烈炭，進(jìn)一步增加系統(tǒng)的復(fù)雜度符隙。
4. Redis
Redis的所有命令操作都是單線程的霹疫，本身提供像 incr 和 increby 這樣的自增原子命令丽蝎，所以能保證生成的 ID 肯定是唯一有序的屠阻。
優(yōu)點(diǎn)
- 不依賴于數(shù)據(jù)庫(kù)国觉，靈活方便蛉加，且性能優(yōu)于數(shù)據(jù)庫(kù)
缺點(diǎn)
- 如果系統(tǒng)中沒(méi)有Redis，還需要引入新的組件厂抽，增加系統(tǒng)復(fù)雜度筷凤。
- 有單點(diǎn)故障的風(fēng)險(xiǎn)。要解決這個(gè)問(wèn)題挪丢，就得引入集群乾蓬，進(jìn)一步增加系統(tǒng)的復(fù)雜度任内。
5. 百度UidGenerator
UidGenerator是百度開(kāi)源的分布式ID生成器，基于于Snowflake算法的實(shí)現(xiàn)趋距。
具體可以參考官網(wǎng)：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
6. 美團(tuán)Leaf
Leaf 是美團(tuán)開(kāi)源的分布式ID生成器节腐，能保證全局唯一性铜跑、趨勢(shì)遞增锅纺、單調(diào)遞增囤锉、信息安全官地，但也需要依賴關(guān)系數(shù)據(jù)庫(kù)驱入、Zookeeper等中間件亏较。
具體可以參考官網(wǎng)：https://tech.meituan.com/2017/04/21/mt-leaf.html
7. Snowflake
Twitter 實(shí)現(xiàn)了一個(gè)全局ID生成的服務(wù) Snowflake：https://github.com/twitter-archive/snowflake
SnowflakeID生成規(guī)則
如上圖的所示，Twitter 的 Snowflake 算法由下面幾部分組成：
- 1位符號(hào)位：
最高位為 0巡通，表示正數(shù)；因?yàn)樗械腎D都是正數(shù)誊锭。 - 41位時(shí)間戳（毫秒級(jí)）：
需要注意的是此處的 41 位時(shí)間戳并非存儲(chǔ)當(dāng)前時(shí)間的時(shí)間戳，而是存儲(chǔ)時(shí)間戳的差值（當(dāng)前時(shí)間戳 - 起始時(shí)間戳）窘行，這里的起始時(shí)間戳由程序來(lái)指定图仓，所以41位毫秒時(shí)間戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年救崔。 - 10位數(shù)據(jù)機(jī)器位：
包括5位數(shù)據(jù)標(biāo)識(shí)位和5位機(jī)器標(biāo)識(shí)位纬黎，這10位決定了分布式系統(tǒng)中最多可以部署 1 << 10 = 1024 個(gè)節(jié)點(diǎn)劫窒。超過(guò)這個(gè)數(shù)量主巍，生成的ID就有可能會(huì)沖突孕索。 - 12位毫秒內(nèi)的序列：
這 12 位計(jì)數(shù)支持每個(gè)節(jié)點(diǎn)每毫秒（同一臺(tái)機(jī)器，同一時(shí)刻）最多生成 1 << 12 = 4096個(gè)ID。
加起來(lái)剛好64位镇眷，為一個(gè)Int64型的整數(shù)偏灿。
優(yōu)點(diǎn)
- 簡(jiǎn)單高效翁垂，沒(méi)有網(wǎng)絡(luò)請(qǐng)求沿猜，生成速度快啼肩。
- 時(shí)間戳在高位，自增序列在低位衙伶，整個(gè)ID是趨勢(shì)遞增的祈坠，按照時(shí)間有序遞增。
- 靈活度高矢劲，可以根據(jù)業(yè)務(wù)需求赦拘，調(diào)整bit位的劃分，滿足不同的需求芬沉。
- 生成的是一個(gè)Int64的整形躺同，作為數(shù)據(jù)庫(kù)的索引，效率非常高丸逸。
缺點(diǎn)
- 依賴機(jī)器的時(shí)鐘，如果服務(wù)器時(shí)鐘回?fù)埽瑫?huì)導(dǎo)致重復(fù)ID生成。
- 在分布式環(huán)境上，每個(gè)服務(wù)器的時(shí)鐘不可能完全同步，有時(shí)會(huì)出現(xiàn)不是全局遞增的情況致板。
在大多數(shù)情況下萝挤，Snowflake算法能夠滿足應(yīng)用需求。以下是我使用Go和C#實(shí)現(xiàn)的可以靈活配置各個(gè)部分所占位數(shù)的Snowflake算法。
Go
/*
用于生成唯一的、遞增的Id。生成的規(guī)則如下：
1、生成的Id包含一個(gè)固定前綴值
2、為了生成盡可能多的不重復(fù)數(shù)字，所以使用int64來(lái)表示一個(gè)數(shù)字，其中：
0 000000000000000 0000000000000000000000000000 00000000000000000000
第一部分：1位，固定為0
第二部分：共PrefixBitCount位，表示固定前綴值。范圍為[0, math.Pow(2, PrefixBitCount))
第三部分：共TimeBitCount位，表示當(dāng)前時(shí)間距離基礎(chǔ)時(shí)間的秒數(shù)船侧。范圍為[0, math.Pow(2, TimeBitCount))讯检，以2019-1-1 00:00:00為基準(zhǔn)則可以持續(xù)到2025-07-01 00:00:00
第四部分：共SeedBitCount位投放，表示自增種子烙样。范圍為[0, math.Pow(2, SeedBitCount))
3批狱、總體而言卦停，此規(guī)則支持每秒生成math.Pow(2, SeedBitCount)個(gè)不同的數(shù)字小槐，并且在math.Pow(2, TimeBitCount)/60/60/24/365年的時(shí)間范圍內(nèi)有效
*/
package idUtil
import (
"fmt"
"math"
"sync"
"time"
)
// Id生成器
type IdGenerator struct {
prefixBitCount uint // 前綴所占的位數(shù)
minPrefix int64 // 最小的前綴值
maxPrefix int64 // 最大的前綴值
timeBitCount uint // 時(shí)間戳所占的位數(shù)
baseTimeUnix int64 // 基礎(chǔ)時(shí)間
maxTimeDuration int64 // 最大的時(shí)間范圍
seedBitCount uint // 自增種子所占的位數(shù)
currSeed int64 // 當(dāng)前種子值
minSeed int64 // 最小的種子值
maxSeed int64 // 最大的種子值
mutex sync.Mutex // 鎖對(duì)象
}
func (this *IdGenerator) getTimeStamp() int64 {
return time.Now().Unix() - this.baseTimeUnix
}
func (this *IdGenerator) generateSeed() int64 {
this.mutex.Lock()
defer this.mutex.Unlock()
if this.currSeed >= this.maxSeed {
this.currSeed = this.minSeed
} else {
this.currSeed = this.currSeed + 1
}
return this.currSeed
}
// 生成新的Id
// prefix：Id的前綴值疆栏。取值范圍必須可以用創(chuàng)建對(duì)象時(shí)指定的前綴值的位數(shù)來(lái)表示若专，否則會(huì)返回參數(shù)超出范圍的錯(cuò)誤
// 返回值：
// 新的Id
// 錯(cuò)誤對(duì)象
func (this *IdGenerator) GenerateNewId(prefix int64) (int64, error) {
if prefix < this.minPrefix || prefix > this.maxPrefix {
return 0, fmt.Errorf("前綴值溢出米酬，有效范圍為【%d,%d】", this.minPrefix, this.maxPrefix)
}
stamp := this.getTimeStamp()
seed := this.generateSeed()
id := prefix<<(this.timeBitCount+this.seedBitCount) | stamp<<this.seedBitCount | seed
return id, nil
}
// 創(chuàng)建新的Id生成器對(duì)象（為了保證Id的唯一，需要保證生成的對(duì)象全局唯一）
// prefixBitCount + timeBitCount + seedBitCount <= 63
// prefixBitCount:表示id前綴的位數(shù)
// timeBitCount:表示時(shí)間的位數(shù)
// seedBitCount:表示自增種子的位數(shù)
// 返回值：
// 新的Id生成器對(duì)象
// 錯(cuò)誤對(duì)象
func New(prefixBitCount, timeBitCount, seedBitCount uint) (*IdGenerator, error) {
// 之所以使用63位而不是64，是為了保證值為正數(shù)
if prefixBitCount+timeBitCount+seedBitCount > 63 {
return nil, fmt.Errorf("總位數(shù)%d超過(guò)63位丧慈，請(qǐng)調(diào)整所有值的合理范圍。", prefixBitCount+timeBitCount+seedBitCount)
}
obj := &IdGenerator{
prefixBitCount: prefixBitCount,
timeBitCount: timeBitCount,
seedBitCount: seedBitCount,
}
obj.minPrefix = 0
obj.maxPrefix = int64(math.Pow(2, float64(prefixBitCount))) - 1
obj.baseTimeUnix = time.Date(2019, time.January, 1, 0, 0, 0, 0, time.Local).Unix()
obj.maxTimeDuration = (int64(math.Pow(2, float64(timeBitCount))) - 1) / 86400 / 365
obj.currSeed = 0
obj.minSeed = 0
obj.maxSeed = int64(math.Pow(2, float64(seedBitCount))) - 1
fmt.Printf("Prefix:[%d, %d], Time:%d Year, Seed:[%d, %d]\n", obj.minPrefix, obj.maxPrefix, obj.maxTimeDuration, obj.minSeed, obj.maxSeed)
return obj, nil
}
C#
/*
用于生成唯一的虐沥、遞增的Id天试。生成的規(guī)則如下：
1刚照、生成的Id包含一個(gè)固定前綴值
2郭变、為了生成盡可能多的不重復(fù)數(shù)字横辆，所以使用int64來(lái)表示一個(gè)數(shù)字靖避，其中：
0 000000000000000 0000000000000000000000000000 00000000000000000000
第一部分：1位榛臼，固定為0
第二部分：共PrefixBitCount位，表示固定前綴值。范圍為[0, math.Pow(2, PrefixBitCount))
第三部分：共TimeBitCount位尿扯，表示當(dāng)前時(shí)間距離基礎(chǔ)時(shí)間的秒數(shù)。范圍為[0, math.Pow(2, TimeBitCount))容客，以2019-1-1 00:00:00為基準(zhǔn)則可以持續(xù)到2025-07-01 00:00:00
第四部分：共SeedBitCount位调煎，表示自增種子。范圍為[0, math.Pow(2, SeedBitCount))
3挎挖、總體而言，此規(guī)則支持每秒生成math.Pow(2, SeedBitCount)個(gè)不同的數(shù)字汛闸，并且在math.Pow(2, TimeBitCount)/60/60/24/365年的時(shí)間范圍內(nèi)有效
*/
using System;
namespace Util
{
/// <summary>
/// Id生成助手類
/// </summary>
public class IdUtil
{
/// <summary>
/// 前綴所占的位數(shù)
/// </summary>
public Int32 PrefixBitCount { get; set; }
/// <summary>
/// 最小的前綴值
/// </summary>
private Int64 MinPrefix { get; set; }
/// <summary>
/// 最大的前綴值
/// </summary>
private Int64 MaxPrefix { get; set; }
/// <summary>
/// 時(shí)間戳所占的位數(shù)
/// </summary>
public Int32 TimeBitCount { get; set; }
/// <summary>
/// 自增種子所占的位數(shù)
/// </summary>
public Int32 SeedBitCount { get; set; }
/// <summary>
/// 當(dāng)前種子值
/// </summary>
private Int64 CurrSeed { get; set; }
/// <summary>
/// 最小的種子值
/// </summary>
private Int64 MinSeed { get; set; }
/// <summary>
/// 最大的種子值
/// </summary>
private Int64 MaxSeed { get; set; }
/// <summary>
/// 鎖對(duì)象
/// </summary>
private Object LockObj { get; set; }
/// <summary>
/// 創(chuàng)建Id助手類對(duì)象（為了保證Id的唯一大咱，需要保證生成的對(duì)象全局唯一）
/// prefixBitCount + timeBitCount + seedBitCount <= 63
/// </summary>
/// <param name="prefixBitCount">表示id前綴的位數(shù)</param>
/// <param name="timeBitCount">表示時(shí)間的位數(shù)</param>
/// <param name="seedBitCount">表示自增種子的位數(shù)</param>
public IdUtil(Int32 prefixBitCount, Int32 timeBitCount, Int32 seedBitCount)
{
// 之所以使用63位而不是64劳跃，是為了保證值為正數(shù)
if (prefixBitCount + timeBitCount + seedBitCount > 63)
{
throw new ArgumentOutOfRangeException(String.Format("總位數(shù){0}超過(guò)63位，請(qǐng)調(diào)整所有值的合理范圍浙垫。", (prefixBitCount + timeBitCount + seedBitCount).ToString()));
}
this.PrefixBitCount = prefixBitCount;
this.TimeBitCount = timeBitCount;
this.SeedBitCount = seedBitCount;
this.MinPrefix = 0;
this.MaxPrefix = (Int64)System.Math.Pow(2, this.PrefixBitCount) - 1;
this.CurrSeed = 0;
this.MinSeed = 0;
this.MaxSeed = (Int64)System.Math.Pow(2, this.SeedBitCount) - 1;
Console.WriteLine(String.Format("Prefix:[{0},{1}], Time:{2} Year, Seed:[{3},{4}]", this.MinPrefix, this.MaxPrefix, (Int64)(System.Math.Pow(2, this.TimeBitCount) / 60 / 60 / 24 / 365), this.MinSeed, this.MaxSeed));
this.LockObj = new Object();
}
private Int64 GetTimeStamp()
{
DateTime startTime = new DateTime(2019, 1, 1);
DateTime currTime = DateTime.Now;
return (Int64)System.Math.Round((currTime - startTime).TotalSeconds, MidpointRounding.AwayFromZero);
}
private Int64 GenerateNewSeed()
{
lock (this.LockObj)
{
if (this.CurrSeed >= this.MaxSeed)
{
this.CurrSeed = this.MinSeed;
}
else
{
this.CurrSeed += 1;
}
return this.CurrSeed;
}
}
/// <summary>
/// 生成新的Id
/// </summary>
/// <param name="prefix">Id的前綴值刨仑。取值范圍必須可以用初始化時(shí)指定的前綴值的位數(shù)來(lái)表示，否則會(huì)拋出ArgumentOutOfRangeException</param>
/// <returns>新的Id</returns>
public Int64 GenerateNewId(Int64 prefix)
{
if (prefix < this.MinPrefix || prefix > this.MaxPrefix)
{
throw new ArgumentOutOfRangeException(String.Format("前綴的值溢出夹姥，有效范圍為【{0},{1}】", this.MinPrefix.ToString(), this.MaxPrefix.ToString()));
}
Int64 stamp = this.GetTimeStamp();
Int64 seed = this.GenerateNewSeed();
return (prefix << (this.TimeBitCount + this.SeedBitCount)) | (stamp << this.SeedBitCount) | seed;
}
}
}
