目錄
- 演算法概述
- ID結構
- 演算法特性
- 演算法代碼（C#）
- 演算法測驗
演算法概述
分布式系統中，有一些需要使用全域唯一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——講解的較為細致
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/3507.html
標籤：C#