欢迎光临
我的个人博客网站

简单实用算法—分布式自增ID算法snowflake(雪花算法)

 

算法概述

分布式系统中,有一些需要使用全局唯一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算法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位可以表示简单实用算法—分布式自增ID算法snowflake(雪花算法)个毫秒的值。
  • 转化成单位年则是简单实用算法—分布式自增ID算法snowflake(雪花算法)年。

10bit-工作机器id:用来记录工作机器id。

  • 可以部署在简单实用算法—分布式自增ID算法snowflake(雪花算法)个节点,包含5位datacenterId和5位workerId
  • 5位(bit)可以表示的最大正整数是简单实用算法—分布式自增ID算法snowflake(雪花算法),即可以用0、1、2、3、….31这32个数字,来表示不同的datecenterId或workerId

12bit-序列号:序列号,用来记录同毫秒内产生的不同id。

  • 12位(bit)可以表示的最大正整数是简单实用算法—分布式自增ID算法snowflake(雪花算法),即可以用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——讲解的较为细致

赞(0) 打赏
未经允许不得转载:张拓的天空 » 简单实用算法—分布式自增ID算法snowflake(雪花算法)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏