devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

简单实用算法—分布式自增ID算法snowflake（雪花算法）_snowflake 分布式自增id

作者：小蓝xlanll | 2024-04-07 09:43:05

赞

踩

snowflake 分布式自增id

算法概述#
分布式系统中，有一些需要使用全局唯一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;                             //序列号部分
        }

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119

算法测试#
测试代码：

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();
        }               
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

测试结果：

开始单线程测试：
产生26万个ID需要972.9153毫秒

开始多线vb.net教程程测试：
运行10个线程，每个线程产生100000个ID等待执行结果…
待执行结果…
待执行结果…
待执行结果…
待执行结果…
单个线程产生ID耗c#教程时的最小为1895.3256毫秒，最大为3828.659毫秒
ID总数为1000000，ID重复个数0
参考文章：
Twitter的分布式自增ID算法snowflake（雪花算法） - C#版——博客园
一口气说出9种分布式ID生成方式，阿里面试官都懵了——知乎
雪花算法（SnowFlake）Java实现——简书
理解分布式id生成算法SnowFlake——segmentfault——讲解的较为细致

作者： time-flies

出处：https://www.cnblogs.com/timefiles/p/Snowflake.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/377838
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号