雪花算法，网上随随便便都能搜到很多，然后无一例外，都说明了算法的一些场景限制，可就是没有一篇文章直接给出一个已经解决或部分解决了这些限制，可以直接使用的算法……
因为我们面向的用户不是互联网企业，所以服务器不需要支持到25，数据中心不需要支持到25，毫秒内最大的序列数量不需要支持到212，反倒是时间戳，默认241只支持69年不太够，如果按1970年开始，那么2039年Id就要到最大值了，算算那时候我还没退休呢（我可是希望能够在当前公司做到退休的，毕竟老东西在外面已经没市场了 😛）！另外目前接触到的客户，基本服务器都是在域控内，所以NTP时间回拨问题肯定避免不了……
算法实现原始参考：snowflake-net
与原始算法的区别：
- 构造函数去除：sequence
- 构造函数增加：基准时间戳，默认为UTC时间2020/01/01；NTP回拨时间支持，默认2000ms；默认服务器3个Bit；默认数据中心2个Bit；默认序列12Bit，也就是说默认构造函数中，从服务器位和数据中心位扣除了5个Bit填补到时间戳，这样时间戳最大支持241+5（69*32=2208年，差不多22个世纪了 😛）
public class IdWorker{/// <summary>/// UTC-Time 2020/01/01 0:00:00 +00:00/// </summary>const long DefaultBenchmarkTimestamp = 1577836800000L;const byte IdMaxBits = 64;const int TimestampMinBits = 41;const int WorkerIdAndDatacenterIdMinBits = 2;const int WorkerIdAndDatacenterIdMaxBits = 6;const int SequenceMinBits = 10;const int SequenceMaxBits = 14;const int ExtraClockCallbackMillisToCleanUp = 1000;const int AllowedNTPClockCallbackMaxMillis = 60000;public long BenchmarkTimestamp { get; private set; }public long WorkId { get; private set; }public long DatacenterId { get; private set; }public int TimestampBits { get; private set; }public int WorkerIdBits { get; private set; }public int DatacenterIdBits { get; private set; }public int SequenceBits { get; private set; }public int AllowedNTPClockCallbackMillis { get; private set; } //https://blog.csdn.net/a2279338659/article/details/143637143private readonly int _sequenceIdMaxValue;private readonly int _workerIdShift;private readonly int _datacenterIdShift;private readonly int _timestampShift;private readonly object _lock = new();private readonly int _maxCountMustBeCleanUp;protected long _sequence;protected long _firstTimestamp = -1L;protected long _lastTimestamp = -1L;/// <summary>/// key: timestamp value: sequence/// </summary>protected readonly Dictionary<long, long> _storageTimestamps = new Dictionary<long, long>();public IdWorker(int workerId, int datacenterId, int allowedNTPClockCallbackMillis = 2000,long benchmarkTimestamp = DefaultBenchmarkTimestamp,int workerIdBits = 3, int datacenterIdBits = WorkerIdAndDatacenterIdMinBits, int sequenceBits = 12){ValidNumberRange(allowedNTPClockCallbackMillis, AllowedNTPClockCallbackMaxMillis, nameof(allowedNTPClockCallbackMillis));var nowTimeStamp = this.TimeGen();if (benchmarkTimestamp >= nowTimeStamp){throw new ArgumentException($"{nameof(benchmarkTimestamp)} is greater than the current timestamp");}ValidBitsRange(workerIdBits, WorkerIdAndDatacenterIdMinBits, WorkerIdAndDatacenterIdMaxBits, nameof(workerIdBits));ValidBitsRange(datacenterIdBits, WorkerIdAndDatacenterIdMinBits, WorkerIdAndDatacenterIdMaxBits, nameof(datacenterId));ValidBitsRange(sequenceBits, SequenceMinBits, SequenceMaxBits, nameof(sequenceBits));TimestampBits = IdMaxBits - workerIdBits - datacenterIdBits - sequenceBits - 1;if (TimestampBits < TimestampMinBits){throw new ArgumentException($"The number of bits used for Timestamp must be greater than or equal to {TimestampMinBits}, and currently it is only {TimestampBits}");}var workIdMaxValue = GetNumberWithBits(workerIdBits);ValidNumberRange(workerId, workIdMaxValue, nameof(workerId));var datacenterIdMaxValue = GetNumberWithBits(datacenterIdBits);ValidNumberRange(datacenterId, datacenterIdMaxValue, nameof(datacenterId));this._sequenceIdMaxValue = GetNumberWithBits(sequenceBits);this.AllowedNTPClockCallbackMillis = allowedNTPClockCallbackMillis;this.WorkerIdBits = workerIdBits;this.DatacenterIdBits = datacenterIdBits;this.SequenceBits = sequenceBits;this.BenchmarkTimestamp = benchmarkTimestamp;this.WorkId = workerId;this.DatacenterId = datacenterId;this._workerIdShift = this.SequenceBits;this._datacenterIdShift = this.SequenceBits + this.WorkerIdBits;this._timestampShift = this.SequenceBits + this.WorkerIdBits + this.DatacenterIdBits;this._maxCountMustBeCleanUp = this.AllowedNTPClockCallbackMillis + ExtraClockCallbackMillisToCleanUp;}private static int GetNumberWithBits(int bits){return -1 ^ (-1 << bits);}private static void ValidNumberRange(int inputValue, int maxValue, string numberName){if (inputValue < 0 || inputValue > maxValue){throw new ArgumentException($"The allowed range for {numberName} is {0}-{maxValue}, and {inputValue} is out of the range");}}private static void ValidBitsRange(int inputBit, int minBits, int maxBits, string bitName){if (inputBit < minBits || inputBit > maxBits){throw new ArgumentException($"The allowed range for {bitName} is {minBits}-{maxBits}, and {inputBit} is out of the range");}}public virtual DateTimeOffset GetDateTimeOffset(long snowflakeId){if (snowflakeId < 0){throw new ArgumentException($"{nameof(snowflakeId)} must be greater than or equals to 0");}var timestamp = (snowflakeId >> this._timestampShift) + this.BenchmarkTimestamp;if (timestamp <= 0){throw new Exception("Conversion failed");}return DateTimeOffset.FromUnixTimeMilliseconds(timestamp);}public virtual long NextId(){lock (_lock){var timestamp = 0L;var prevTimestamp = -1L;var compareTimestamp = this._lastTimestamp - this.AllowedNTPClockCallbackMillis;do{timestamp = this.TimeGen();if (prevTimestamp == timestamp){continue;}if (timestamp < compareTimestamp){throw new Exception("Serious clock callback, requiring manual handling");}if (!this._storageTimestamps.ContainsKey(timestamp)){this._sequence = 0;this._storageTimestamps[timestamp] = this._sequence;break;}else{this._sequence = this._storageTimestamps[timestamp];this._sequence = (this._sequence + 1) & this._sequenceIdMaxValue;if (this._sequence > 0){this._storageTimestamps[timestamp] = this._sequence;break;}prevTimestamp = timestamp;}}while (true);UpdateAndCleanUp();return ((timestamp - this.BenchmarkTimestamp) << this._timestampShift)| (this.DatacenterId << this._datacenterIdShift)| (this.WorkId << this._workerIdShift)| _sequence;void UpdateAndCleanUp(){if (this.AllowedNTPClockCallbackMillis > 0){if (this._lastTimestamp < timestamp){this._lastTimestamp = timestamp;}if (this._firstTimestamp < 0){this._firstTimestamp = timestamp;}if (this._storageTimestamps.Count >= this._maxCountMustBeCleanUp){var cleanTimestamp = timestamp - this.AllowedNTPClockCallbackMillis;while (this._firstTimestamp < cleanTimestamp){this._storageTimestamps.Remove(this._firstTimestamp);this._firstTimestamp++;}}}else{this._lastTimestamp = timestamp;if (this._storageTimestamps.Count >= this._maxCountMustBeCleanUp){var allowedDicCount = this.AllowedNTPClockCallbackMillis + 1;var i = -1;do{this._storageTimestamps.Remove(timestamp + i);i--;}while (this._storageTimestamps.Count > allowedDicCount);}}}}}protected virtual long TimeGen(){return DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();}}
使用起来的代码还是与参考算法实现没区别，我可是保留了所有的命名 😛
var idWorker = new IdWorker(0, 0);
var id = idWorker.NextId();
除默认的NextId方法外，我还增加了方法GetDateTimeOffset，根据生成的Id来解析出该Id生成时的时间戳，方便反向测试时间戳是否正确，测试代码如下
Console.WriteLine($"Id: {long.MaxValue} Long Max");var idWorker = new IdWorker(0, 0, sequenceBits: 10, allowedNTPClockCallbackMillis: 0);Console.WriteLine("Test in single thread, press any key to start...");Console.ReadKey();var idList = GenerateId();PrintIdList(idList);Console.WriteLine("Test in multi-thread, press any key to start...");Console.ReadKey();var threadCount = 5;var listArr = new List<long>[threadCount];Parallel.For(0, threadCount, i =>{listArr[i] = GenerateId();});for (var i = 0; i < listArr.Length; i++){Console.WriteLine($"List index: {i}");PrintIdList(listArr[i]);}Console.WriteLine($"All Count: {listArr.SelectMany(_ => _).Distinct().Count()}");List<long> GenerateId(int count=1000){var tmpList = new List<long>();for (var j = 0; j < count; j++){var id = idWorker.NextId();tmpList.Add(id);}return tmpList;}void PrintIdList(IList<long> idList){Console.WriteLine($"Id Total Count:{idList.Count}");foreach (var id in idList){var time = idWorker.GetDateTimeOffset(id);Console.WriteLine($"Id: {id} Time: {time}");}}
算法参考资料:分布式唯一ID生成算法——雪花算法（Snowflake）
