算法概述
分布式系统中，有一些需要使用全局唯一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——讲解的较为细致
No comments:
Post a Comment