IdGenerator

Seata 優化的雪花演演算法

Seata基於改良版雪花演演算法的分散式UUID生成器分析

關於新版雪花演演算法的答疑

csharp 移植程式碼

    public class IdGenerator
    {
        private readonly long twepoch = 1588435200000L;
        private const int workerIdBits = 10;
        private const int timestampBits = 41;
        private const int sequenceBits = 12;
        private const int maxWorkerId = ~(-1 << workerIdBits);
        private long workerId;
        private long timestampAndSequence;
        private readonly long timestampAndSequenceMask = ~(-1L << (timestampBits + sequenceBits));

        public static readonly IdGenerator Instance = new IdGenerator(GenerateWorkerId());

        public IdGenerator(long workerId)
        {
            InitTimestampAndSequence();
            InitWorkerId(workerId);
        }

        private void InitTimestampAndSequence()
        {
            long timestamp = GetNewestTimestamp();
            long timestampWithSequence = timestamp << sequenceBits;
            this.timestampAndSequence = timestampWithSequence;
        }

        private void InitWorkerId(long workerId)
        {
            if (workerId > maxWorkerId || workerId < 0)
            {
                string message = string.Format("worker Id can't be greater than {0} or less than 0", maxWorkerId);
                throw new ArgumentException(message);
            }
            this.workerId = workerId << (timestampBits + sequenceBits);
        }

        public long NextId()
        {
            WaitIfNecessary();
            long next = Interlocked.Increment(ref timestampAndSequence);
            long timestampWithSequence = next & timestampAndSequenceMask;
            return workerId | timestampWithSequence;
        }

        public static long NewId()
        {
            return Instance.NextId();
        }

        private void WaitIfNecessary()
        {
            long currentWithSequence = timestampAndSequence;
            long current = currentWithSequence >> sequenceBits;
            long newest = GetNewestTimestamp();
            if (current >= newest)
            {
                Thread.Sleep(5);
            }
        }

        private long GetNewestTimestamp()
        {
            return DateTimeOffset.UtcNow.ToUnixTimeMilliseconds() - twepoch;
        }

        public static long GenerateWorkerId()
        {
            try
            {
                return GenerateWorkerIdBaseOnK8S();
            }
            catch (Exception)
            {
                try
                {
                    return GenerateWorkerIdBaseOnMac();
                }
                catch (Exception)
                {
                    return GenerateRandomWorkerId();
                }
            }
        }

        public static long GenerateWorkerIdBaseOnMac()
        {
            IEnumerable<NetworkInterface> all = NetworkInterface.GetAllNetworkInterfaces();
            foreach (NetworkInterface networkInterface in all)
            {
                bool isLoopback = networkInterface.NetworkInterfaceType == NetworkInterfaceType.Loopback;
                //bool isVirtual = networkInterface.;
                //if (isLoopback || isVirtual)
                if (isLoopback)
                {
                    continue;
                }
                byte[] mac = networkInterface.GetPhysicalAddress().GetAddressBytes();
                return ((mac[4] & 0B11) << 8) | (mac[5] & 0xFF);
            }
            throw new Exception("no available mac found");
        }

        public static long GenerateWorkerIdBaseOnK8S()
        {
            return GenerateWorkerIdBaseOnString(Environment.GetEnvironmentVariable("K8S_POD_ID"));
        }

        public static long GenerateWorkerIdBaseOnString(string str)
        {
            ArgumentNullException.ThrowIfNull(str, nameof(str));
            int hashValue = 0;
            int cc = 2 << (workerIdBits - 1);
            foreach (char c in str)
            {
                hashValue = (hashValue * 31 + c) % cc;
            }
            return hashValue + 1;
        }

        public static long GenerateRandomWorkerId()
        {
            return Random.Shared.NextInt64(maxWorkerId + 1);
        }
    }

YitIdHelper

開源庫 https://github.com/yitter/IdGenerator

❄ 這是優化的雪花演演算法（雪花漂移），它生成的ID更短、速度更快。

❄ 支援 k8s 等容器環境自動擴容（自動註冊 WorkerId），可在單機或分散式環境生成數位型唯一ID。

Guid

https://learn.microsoft.com/zh-cn/dotnet/api/system.guid?view=net-7.0

全域性唯一識別符號（GUID，Globally Unique Identifier）是一種由演演算法生成的二進位制長度為128位元的數位識別符號。GUID主要用於在擁有多個節點、多臺計算機的網路或系統中。

Nanoid

開源庫 https://github.com/codeyu/nanoid-net

一個小巧、安全、URL友好、唯一的字串ID生成器。

「一個驚人的無意義的完美主義水平，這簡直讓人無法不敬佩。」

• 小巧. 130位元組 (經過壓縮和gzip處理)。沒有依賴。Size Limit 控制大小。
• 安全. 它使用硬體隨機生成器。可在叢集中使用。
• 緊湊. 它使用比 UUID（A-Za-z0-9_-）更大的字母表。因此，ID 大小從36個符號減少到21個符號。
• 可移植. Nano ID 已被移植到 20種程式語言。

Nano ID 與 UUID v4 (基於亂數) 相當。 它們在 ID 中有相似數量的隨機位 (Nano ID 為126，UUID 為122),因此它們的碰撞概率相似：:

要想有十億分之一的重複機會, 必須產生103萬億個版本4的ID.

Nano ID 和 UUID v4之間有兩個主要區別:

Nano ID 使用更大的字母表，所以類似數量的隨機位 被包裝在21個符號中，而不是36個。
Nano ID 程式碼比 uuid/v4 包少 4倍: 130位元組而不是423位元組.

效能測試程式碼

[AllStatisticsColumn]
public class IdGeneratorTest
{
    public IdGeneratorTest()
    {
        var options = new IdGeneratorOptions()
        {
            WorkerId = 55,
            WorkerIdBitLength = 6,
            SeqBitLength = 12,
        };
        YitIdHelper.SetIdGenerator(options);
    }

    [Benchmark]
    public long IdGeneratorNewId() => IdGenerator.NewId();


    [Benchmark]
    public long YitIdHelperNextId() => YitIdHelper.NextId();

    [Benchmark]
    public string NewGuid() => Guid.NewGuid().ToString();

    [Benchmark]
    public string NanoidGenerate() => Nanoid.Generate();
}

結果

BenchmarkDotNet v0.13.10, Windows 11 (10.0.22000.2538/21H2/SunValley)
Intel Core i7-10700 CPU 2.90GHz, 1 CPU, 16 logical and 8 physical cores
.NET SDK 7.0.403
  [Host]     : .NET 6.0.24 (6.0.2423.51814), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.24 (6.0.2423.51814), X64 RyuJIT AVX2