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