仙草奶綠的程式筆記本

這裡會分享製作的程式與一些心得。

2018-06-04

0029. SnowFlake 分散式雪花演算法 (高併發、產生唯一ID數值演算法)

C#學習筆記

 

環境

 Visual Studio 2015  C#  
目的：

 SnowFlake演算法 C#的實作，可以應用於高併發下產生具64 bit 自增式唯一碼的流水號
應用：  DB Insert每筆資料時，產生的流水號
Github:

https://github.com/gotoa1234/SnowFlakeAlo
本篇分為四部分：
一、  SnowFlake原理
二、  C# 程式碼架構
三、  實作程式碼說明
四、  參考文獻

 

一、 SnowFlake原理

Step 1：以下是SnowFlake原理圖 使用了63bit 其中

Step 2: 關鍵點：每次為了取得唯一值，需要搭配 TimeStamp (微秒) + MacAddress   (自增序號為高併發時，最大可容納數)

12 bit 允許範圍： 0~4095

二、C#程式碼架構

Step 1：主程式

Step 2： SnowFlake主程式 : SnowFlakeAlg

               SnowFlake產生ID的Mathod： SnowFlakeAlg.Method

三、實作程式碼說明

Step 1：Form.cs 主程式-執行100次

private void Form1_Load(object sender, EventArgs e)
{      
            for (int i = 0; i < 100; i++)
            {
                Console.WriteLine(SnowFlakeAlg.GetGuid());
            }

}

Step 2：  SnowFlakeAlg.cs  

主程式： 用一個Lock 確保產生的Id 是遞增的，如果在相同微秒下，已經用完了4095個序號，則會強制換下一微秒

/// <summary>
/// 分布式自增演算法 - 產生唯一ID
/// </summary>
public static partial class SnowFlakeAlg
{
    /// <summary>
    /// 鎖住的資源對象
    /// </summary>
    private static object lockItem = new object();

    /// <summary>
    /// 上一個時間戳- 進行比較用
    /// </summary>
    private static long lastDateTimeStamp = 0L;

    /// <summary>
    /// Sequence 序列號 允許0~4095
    /// </summary>
    private static long sequence = 0L;

    public static long GetGuid()
    {
        //非同步情況下，使用Lock 確保產生唯一ID
        lock(lockItem)
        {
            long result = 0L;
            //1. 41bit
            long timelong = SnowFlakeAlg.GetTimeSpan.GetTimeSpanReturnLong();
            //2. 10bit
            long macSn = SnowFlakeAlg.GetMacAddress.GetTenBitMacAddress();
            //3. 12bit
            sequence++;

            //seq == 0 表示 同一秒內已經被排了4095次，Seq 已經用盡，切換至下一秒
            if (timelong == lastDateTimeStamp)
            {
                if (true == SnowFlakeAlg.GetSequence.checkSeq(sequence))
                {
                    //取得下一微秒的Long值
                    timelong = SnowFlakeAlg.GetTimeSpan.GetTimeSpanReturnNextSecondLong();
                }
            }
            else//不同微秒下
            {
                sequence = 0;//歸0
            }
            //紀錄本次的TimeStamp
            lastDateTimeStamp = timelong;
            
            //41bit 
            result =((timelong) << 22) | macSn << 12 | sequence;

            return result;
        }
       
    }
}

Step 3：  SnowFlakeAlg.Method

以下共三種Class組合，分別：

1. GetMacAddress : 取得Mac 位址的方法 ， 並且取得 XX-XX-XX-XX-XX-XX   取得後面兩個Byte (Mac 必定為6Byte 組成 ，我們需要10bit 可自由從裡面挑出兩個Byte)

2. GetTimeSpan： 取得微秒轉成Long 的大小，這是核心，唯有時間才會符合 自增 + 不重複 這個條件

3. GetSequence： 判斷是否同一微秒下，4095個號碼是否用盡。

#region Method

#region Mac Function 10bit


private static class GetMacAddress
{
    /// <summary>
    /// Ascii對應表
    /// </summary>
    private static Dictionary<char, int> dicAscii = new Dictionary<char, int>()
    {
        {'0' , 0},{ '1' ,1} , {'2' , 2},{ '3' ,3} , {'4' , 4},{ '5' ,5} , {'6' , 6},{ '7' ,7} , {'8' , 8},{ '9' ,9} , {'A' , 10},{ 'B' ,11} , {'C' , 12},{ 'D' ,13} , { 'E' ,14} ,{'F' , 15}
    };

    /// <summary>
    /// 取得10位元的網路卡位址
    /// </summary>
    /// <returns></returns>
    public static long GetTenBitMacAddress()
    {
        //取得網卡Libary - 取得本機器所有網路卡
        NetworkInterface[] macs = NetworkInterface.GetAllNetworkInterfaces();

        //取得電腦上的 Ethernet 的 MAC Address ，第一個抓到的實體網卡
        var result = macs.Where(o => o.NetworkInterfaceType == NetworkInterfaceType.Ethernet).FirstOrDefault();

        //沒有網卡
        if (null == result)
        {
            return 0;
        }   //return 0L;
        else//有網卡則進行計算
        {
            //※邏輯 ： SnowFlake 演算法取10bit ，實體網卡為 12Byte EX: E0-3F-49-4D-01-1C
            //          取最後兩個Byte(2 * 8) 進行6bit位移，取10Bit 

            //String -> ASCII 
            byte[] macDecByte = System.Text.Encoding.ASCII.GetBytes(result.GetPhysicalAddress().ToString());

            //左邊
            int left = AscIIToInt((char)Convert.ToInt32(macDecByte[8])) * 16 + AscIIToInt((char)Convert.ToInt32(macDecByte[9])) * 1 << 8;//=>x的位元   x x x x x x x x o o o o o o o o
            int right = AscIIToInt((char)Convert.ToInt32(macDecByte[10])) * 16 + AscIIToInt((char)Convert.ToInt32(macDecByte[11])) * 1;//=> x的位元       o o o o o o o o x x x x x x x x
            int total = left + right;//相加

            //保留 10 bit =>  (最大整數4095 如右邊x的部分)=> o o o o o o x x x x x x x x x x   
            total = total >> 6;//

            return total;
        }
    }

    /// <summary>
    /// 將AscII碼 轉為 Int
    /// </summary>
    /// <returns></returns>
    private static int AscIIToInt(char item)
    {
        int resultValue = 0;
        //取得對應 Char -> Value
        dicAscii.TryGetValue(item, out resultValue);
        //返回16進位數值 
        return resultValue;
    }
}
#endregion

#region TimeSpan Milliseconds 41bit
/// <summary>
/// 取得時間戳 
/// </summary>
private static class GetTimeSpan
{
   
    /// <summary>
    /// 回傳當前時間微秒 Long型態
    /// </summary>
    /// <returns></returns>
    public static long GetTimeSpanReturnLong()
    {
        DateTime dt = DateTime.Now;//現在時間
        DateTime ori = new DateTime(1970, 1, 1, 0, 0, 0);//起源時間
        return (long)(dt - ori).TotalMilliseconds;
    }

    /// <summary>
    /// 回傳當前時間微秒 + 1 Long 型態
    /// </summary>
    /// <returns></returns>
    public static long GetTimeSpanReturnNextSecondLong()
    {
        DateTime dt = DateTime.Now.AddMilliseconds(1);//增加1微秒
        DateTime ori = new DateTime(1970, 1, 1, 0, 0, 0);//起源時間
        return (long)(dt - ori).TotalMilliseconds;
    }

}
#endregion

#region Sequence 12bit

/// <summary>
/// 取得序列號
/// </summary>
private static class GetSequence
{
    /// <summary>
    /// 12bit 最大長度
    /// </summary>
    private static long BIT12 = 4095;

    public static bool checkSeq(long nowSeq)
    {
        var check=  (nowSeq) & BIT12;
        if (check == 0)
            return true;
        else
            return false;
    }

}

#endregion

#endregion

Step 4: 執行結果

 

四、參考文獻

Twitter Blog：https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html

 

系列文章