分散式系統中,有一些需要使用全局唯一ID的場景,這種時候為了防止ID衝突可以使用36位的UUID,但是UUID有一些缺點,首先他相對比較長,另外UUID一般是無序的。有些時候我們希望能使用一種簡單一些的ID,並且希望ID能夠按照時間有序生成。而twitter的snowflake解決了這種需求,最初T... ...
演算法概述
分散式系統中,有一些需要使用全局唯一ID的場景,這種時候為了防止ID衝突可以使用36位的UUID,但是UUID有一些缺點,首先他相對比較長,另外UUID一般是無序的。有些時候我們希望能使用一種簡單一些的ID,並且希望ID能夠按照時間有序生成。而twitter的snowflake解決了這種需求,最初Twitter把存儲系統從MySQL遷移到Cassandra,因為Cassandra沒有順序ID生成機制,所以開發了這樣一套全局唯一ID生成服務。
該項目地址(Scala實現):https://github.com/twitter/snowflake
python版項目地址:https://github.com/erans/pysnowflake
ID結構
Snowflake生成的是Long類型的ID,一個Long類型占8個位元組,每個位元組占8比特,也就是說一個Long類型占64個比特。
snowflake的結構如下(每部分用-分開):
註:上圖的工作機器id(10比特)=數據中心(占左5比特)+ 機器ID(占右5比特)
Snowflake ID組成結構:正數位(占1比特)+ 時間戳(占41比特)+ 數據中心(占5比特)+ 機器ID(占5比特)+ 自增值(占12比特)
第一位為未使用,接下來的41位為毫秒級時間(41位的長度可以使用69年),然後是5位datacenterId和5位workerId(10位的長度最多支持部署1024個節點) ,最後12位是毫秒內的計數(12位的計數順序號支持每個節點每毫秒產生4096個ID序號)一共加起來剛好64位,為一個Long型(轉換成字元串長度為18)。
1bit:不使用。
- 因為二進位中最高位是符號位,1表示負數,0表示正數。生成的id一般都是用整數,所以最高位固定為0。
41bit-時間戳:用來記錄時間戳,毫秒級。
- 41位可以表示個毫秒的值。
- 轉化成單位年則是年。
10bit-工作機器id:用來記錄工作機器id。
- 可以部署在個節點,包含5位datacenterId和5位workerId
- 5位(bit)可以表示的最大正整數是,即可以用0、1、2、3、....31這32個數字,來表示不同的datecenterId或workerId
12bit-序列號:序列號,用來記錄同毫秒內產生的不同id。
- 12位(bit)可以表示的最大正整數是,即可以用0、1、2、3、....4094這4095個數字,來表示同一機器同一時間截(毫秒)內產生的4095個ID序號。
演算法特性
SnowFlake可以保證:
- 所有生成的id按時間趨勢遞增
- 整個分散式系統內不會產生重覆id(因為有datacenterId和workerId來做區分)
據說:snowflake每秒能夠產生26萬個ID。
演算法代碼(C#)
網上雪花演算法的C#實現代碼一大把,但大多是複製的同一份代碼。而且,網上的C#版實現有很多錯誤。
這裡要提一下雪花演算法(Snowflake)C#版本 壓測Id重覆嚴重,為這位博主默哀一下...
這裡的演算法實現代碼是我參考原版(Scala實現)、Java版的代碼用C#實現的,經測試未發現問題,可放心使用。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Runtime.Remoting.Contexts;
using System.Runtime.CompilerServices;
namespace SnowflakeDemo
{
public sealed class IdWorker
{
/// <summary>
/// 起始的時間戳:唯一時間,這是一個避免重覆的隨機量,自行設定不要大於當前時間戳。
/// 一個計時周期表示一百納秒,即一千萬分之一秒。 1 毫秒內有 10,000 個計時周期,即 1 秒內有 1,000 萬個計時周期。
/// </summary>
private static long StartTimeStamp = new DateTime(2020,7,1).Ticks/10000;
/*
* 每一部分占用的位數
* 對於移位運算符 << 和 >>,右側操作數的類型必須為 int,或具有預定義隱式數值轉換 為 int 的類型。
*/
private const int SequenceBit = 12; //序列號占用的位數
private const int MachingBit = 5; //機器標識占用的位數
private const int DataCenterBit = 5; //數據中心占用的位數
/*
* 每一部分的最大值
*/
private static long MaxSequence = -1L ^ (-1L << SequenceBit);
private static long MaxMachingNum = -1L ^ (-1L << MachingBit);
private static long MaxDataCenterNum = -1L ^ (-1L << DataCenterBit);
/*
* 每一部分向左的位移
*/
private const int MachingLeft = SequenceBit;
private const int DataCenterLeft = SequenceBit + MachingBit;
private const int TimeStampLeft = DataCenterLeft + DataCenterBit;
private long dataCenterId; //數據中心
private long machineId; //機器標識
private long sequence; //序列號
private long lastTimeStamp = -1; //上一次時間戳
private long GetNextMill()
{
long mill = getNewTimeStamp();
while (mill <= lastTimeStamp)
{
mill = getNewTimeStamp();
}
return mill;
}
private long getNewTimeStamp()
{
return DateTime.Now.Ticks/10000;
}
/// <summary>
/// 根據指定的數據中心ID和機器標誌ID生成指定的序列號
/// </summary>
/// <param name="dataCenterId">數據中心ID</param>
/// <param name="machineId">機器標誌ID</param>
public IdWorker(long dataCenterId, long machineId)
{
if (dataCenterId > MaxDataCenterNum || dataCenterId < 0)
{
throw new ArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0!");
}
if (machineId > MaxMachingNum || machineId < 0)
{
throw new ArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0!");
}
this.dataCenterId = dataCenterId;
this.machineId = machineId;
}
/// <summary>
/// 產生下一個ID
/// </summary>
/// <returns></returns>
[MethodImplAttribute(MethodImplOptions.Synchronized)]
public long NextId()
{
long currTimeStamp = getNewTimeStamp();
if (currTimeStamp < lastTimeStamp)
{
//如果當前時間戳比上一次生成ID時時間戳還小,拋出異常,因為不能保證現在生成的ID之前沒有生成過
throw new Exception("Clock moved backwards. Refusing to generate id");
}
if (currTimeStamp == lastTimeStamp)
{
//相同毫秒內,序列號自增
sequence = (sequence + 1) & MaxSequence;
//同一毫秒的序列數已經達到最大
if (sequence == 0L)
{
currTimeStamp = GetNextMill();
}
}
else
{
//不同毫秒內,序列號置為0
sequence = 0L;
}
lastTimeStamp = currTimeStamp;
return (currTimeStamp - StartTimeStamp) << TimeStampLeft //時間戳部分
| dataCenterId << DataCenterLeft //數據中心部分
| machineId << MachingLeft //機器標識部分
| sequence; //序列號部分
}
}
}
演算法測試
測試代碼:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
namespace SnowflakeDemo
{
class Program
{
static void Main(string[] args)
{
IdWorker idworker = new IdWorker(1, 1);
Console.WriteLine("開始單線程測試:");
Stopwatch sw1 = new Stopwatch();
sw1.Start();
for (int i = 0; i < 260000; i++)
{
idworker.NextId();
}
sw1.Stop();
TimeSpan ts = sw1.Elapsed;
Console.WriteLine("產生26萬個ID需要{0}毫秒",ts.TotalMilliseconds);
Console.WriteLine();
Console.WriteLine("開始多線程測試:");
int threadNum = 10;//測試線程數
int idNum = 100000;//每個線程產生的id數
long[,] idAllAry = new long[threadNum,idNum];
bool[] completeAry = new bool[threadNum];
double[] workTimeAry = new double[threadNum];
Thread[] thAry = new Thread[threadNum];
for (int i = 0; i < thAry.Length; i++)
{
thAry[i] = new Thread(new ParameterizedThreadStart(obj =>
{
int index = (int)obj;
Stopwatch sw2 = new Stopwatch();
sw2.Start();
for (int j = 0; j < idNum; j++)
{
idAllAry[index,j]=idworker.NextId();
}
completeAry[index] = true;
sw2.Stop();
workTimeAry[index] = sw2.Elapsed.TotalMilliseconds;
}));
}
for (int i = 0; i < thAry.Length; i++)
{
thAry[i].Start(i);
}
Console.WriteLine(string.Format("運行{0}個線程,每個線程產生{1}個ID",threadNum,idNum));
while (completeAry.Where(c => !c).ToList().Count != 0)
{
Console.WriteLine("等待執行結果...");
Thread.Sleep(1000);
}
Console.WriteLine(string.Format("單個線程產生ID耗時的最小為{0}毫秒,最大為{1}毫秒", workTimeAry.Min(), workTimeAry.Max()));
List<long> idList = new List<long>();
for (int i = 0; i < threadNum; i++)
{
for (int j = 0; j < idNum; j++)
{
idList.Add(idAllAry[i, j]);
}
}
var qrepeatId = idList.GroupBy(x => x).Where(x => x.Count() > 1).ToList();
Console.WriteLine(string.Format("ID總數為{0},ID重覆個數{1}", idList.Count, qrepeatId.Count));
foreach (var item in qrepeatId)
{
Console.WriteLine(item.Key);
}
Console.ReadLine();
}
}
}
測試結果:
開始單線程測試:
產生26萬個ID需要972.9153毫秒
開始多線程測試:
運行10個線程,每個線程產生100000個ID等待執行結果…
待執行結果...
待執行結果...
待執行結果...
待執行結果...
單個線程產生ID耗時的最小為1895.3256毫秒,最大為3828.659毫秒
ID總數為1000000,ID重覆個數0
參考文章:
Twitter的分散式自增ID演算法snowflake(雪花演算法) - C#版——博客園
一口氣說出9種分散式ID生成方式,阿裡面試官都懵了——知乎
雪花演算法(SnowFlake)Java實現——簡書
理解分散式id生成演算法SnowFlake——segmentfault——講解的較為細緻