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

Twitter的分布式自增ID算法snowflake（雪花算法） C#和Java版_twitter雪花算法集成

作者：AllinToyou | 2024-04-07 09:45:44

赞

踩

twitter雪花算法集成

目录

概述

结构

C# 

C#调用

 java

概述


分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，
但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。
有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。
而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，
因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。


结构

snowflake的结构如下(每部分用-分开):
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位
workerId(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节
点每毫秒产生4096个ID序号）
一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)
snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和
workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID

C# 

public class IdWorker
    {
        //机器ID
        private static long workerId;
        private static long twepoch = 687888001020L; //唯一时间，这是一个避免重复的随机量，自行设定不要大于当前时间戳
        private static long sequence = 0L;
        private static int workerIdBits = 4; //机器码字节数。4个字节用来保存机器码(定义为Long类型会出现，最大偏移64位，所以左移64位没有意义)
        public static long maxWorkerId = -1L ^ -1L << workerIdBits; //最大机器ID
        private static int sequenceBits = 10; //计数器字节数，10个字节用来保存计数码
        private static int workerIdShift = sequenceBits; //机器码数据左移位数，就是后面计数器占用的位数
        private static int timestampLeftShift = sequenceBits + workerIdBits; //时间戳左移动位数就是机器码和计数器总字节数
        public static long sequenceMask = -1L ^ -1L << sequenceBits; //一微秒内可以产生计数，如果达到该值则等到下一微妙在进行生成
        private long lastTimestamp = -1L;

        /// <summary>
        /// 机器码
        /// </summary>
        /// <param name="workerId"></param>
        public IdWorker(long workerId)
        {
            if (workerId > maxWorkerId || workerId < 0)
                throw new Exception(string.Format("worker Id can't be greater than {0} or less than 0 ", workerId));
            IdWorker.workerId = workerId;
        }

        public long nextId()
        {
            lock (this)
            {
                long timestamp = timeGen();
                if (this.lastTimestamp == timestamp)
                { //同一微妙中生成ID
                    IdWorker.sequence = (IdWorker.sequence + 1) & IdWorker.sequenceMask; //用&运算计算该微秒内产生的计数是否已经到达上限
                    if (IdWorker.sequence == 0)
                    {
                        //一微妙内产生的ID计数已达上限，等待下一微妙
                        timestamp = tillNextMillis(this.lastTimestamp);
                    }
                }
                else
                { //不同微秒生成ID
                    IdWorker.sequence = 0; //计数清0
                }
                if (timestamp < lastTimestamp)
                { //如果当前时间戳比上一次生成ID时时间戳还小，抛出异常，因为不能保证现在生成的ID之前没有生成过
                    throw new Exception(string.Format("Clock moved backwards.  Refusing to generate id for {0} milliseconds",
                        this.lastTimestamp - timestamp));
                }
                this.lastTimestamp = timestamp; //把当前时间戳保存为最后生成ID的时间戳
                long nextId = (timestamp - twepoch << timestampLeftShift) | IdWorker.workerId << IdWorker.workerIdShift | IdWorker.sequence;
                return nextId;
            }
        }

        /// <summary>
        /// 获取下一微秒时间戳
        /// </summary>
        /// <param name="lastTimestamp"></param>
        /// <returns></returns>
        private long tillNextMillis(long lastTimestamp)
        {
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp)
            {
                timestamp = timeGen();
            }
            return timestamp;
        }

        /// <summary>
        /// 生成当前时间戳
        /// </summary>
        /// <returns></returns>
        private long timeGen()
        {
            return (long)(DateTime.UtcNow - new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc)).TotalMilliseconds;
        }
    }

  1. public class IdWorker
  2.     {
  3.         //机器ID
  4.         private static long workerId;
  5.         private static long twepoch = 687888001020L; //唯一时间，这是一个避免重复的随机量，自行设定不要大于当前时间戳
  6.         private static long sequence = 0L;
  7.         private static int workerIdBits = 4; //机器码字节数。4个字节用来保存机器码(定义为Long类型会出现，最大偏移64位，所以左移64位没有意义)
  8.         public static long maxWorkerId = -1L ^ -1L << workerIdBits; //最大机器ID
  9.         private static int sequenceBits = 10; //计数器字节数，10个字节用来保存计数码
  10.         private static int workerIdShift = sequenceBits; //机器码数据左移位数，就是后面计数器占用的位数
  11.         private static int timestampLeftShift = sequenceBits + workerIdBits; //时间戳左移动位数就是机器码和计数器总字节数
  12.         public static long sequenceMask = -1L ^ -1L << sequenceBits; //一微秒内可以产生计数，如果达到该值则等到下一微妙在进行生成
  13.         private long lastTimestamp = -1L;
  14.  
  15.         /// <summary>
  16.         /// 机器码
  17.         /// </summary>
  18.         /// <param name="workerId"></param>
  19.         public IdWorker(long workerId)
  20.         {
  21.             if (workerId > maxWorkerId || workerId < 0)
  22.                 throw new Exception(string.Format("worker Id can't be greater than {0} or less than 0 ", workerId));
  23.             IdWorker.workerId = workerId;
  24.         }
  25.  
  26.         public long nextId()
  27.         {
  28.             lock (this)
  29.             {
  30.                 long timestamp = timeGen();
  31.                 if (this.lastTimestamp == timestamp)
  32.                 { //同一微妙中生成ID
  33.                     IdWorker.sequence = (IdWorker.sequence + 1) & IdWorker.sequenceMask; //用&运算计算该微秒内产生的计数是否已经到达上限
  34.                     if (IdWorker.sequence == 0)
  35.                     {
  36.                         //一微妙内产生的ID计数已达上限，等待下一微妙
  37.                         timestamp = tillNextMillis(this.lastTimestamp);
  38.                     }
  39.                 }
  40.                 else
  41.                 { //不同微秒生成ID
  42.                     IdWorker.sequence = 0; //计数清0
  43.                 }
  44.                 if (timestamp < lastTimestamp)
  45.                 { //如果当前时间戳比上一次生成ID时时间戳还小，抛出异常，因为不能保证现在生成的ID之前没有生成过
  46.                     throw new Exception(string.Format("Clock moved backwards.  Refusing to generate id for {0} milliseconds",
  47.                         this.lastTimestamp - timestamp));
  48.                 }
  49.                 this.lastTimestamp = timestamp; //把当前时间戳保存为最后生成ID的时间戳
  50.                 long nextId = (timestamp - twepoch << timestampLeftShift) | IdWorker.workerId << IdWorker.workerIdShift | IdWorker.sequence;
  51.                 return nextId;
  52.             }
  53.         }
  54.  
  55.         /// <summary>
  56.         /// 获取下一微秒时间戳
  57.         /// </summary>
  58.         /// <param name="lastTimestamp"></param>
  59.         /// <returns></returns>
  60.         private long tillNextMillis(long lastTimestamp)
  61.         {
  62.             long timestamp = timeGen();
  63.             while (timestamp <= lastTimestamp)
  64.             {
  65.                 timestamp = timeGen();
  66.             }
  67.             return timestamp;
  68.         }
  69.  
  70.         /// <summary>
  71.         /// 生成当前时间戳
  72.         /// </summary>
  73.         /// <returns></returns>
  74.         private long timeGen()
  75.         {
  76.             return (long)(DateTime.UtcNow - new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc)).TotalMilliseconds;
  77.         }
  78.     }

C#调用

  1.       IdWorker idworker = new IdWorker(1);
  2.       for (int i = 0; i < 1000; i++)
  3.       {
  4.            Response.Write(idworker.nextId() + "<br/>");
  5.       }

 java

  1. public class IdWorker {
  2.     private final long workerId;
  3.     private final static long twepoch = 1288834974657L;
  4.     private long sequence = 0L;
  5.     private final static long workerIdBits = 4L;
  6.     public final static long maxWorkerId = -1L ^ -1L << workerIdBits;
  7.     private final static long sequenceBits = 10L;
  8.     private final static long workerIdShift = sequenceBits;
  9.     private final static long timestampLeftShift = sequenceBits + workerIdBits;
  10.     public final static long sequenceMask = -1L ^ -1L << sequenceBits;
  11.     private long lastTimestamp = -1L;
  12.     public IdWorker(final long workerId) {
  13.         super();
  14.         if (workerId > this.maxWorkerId || workerId < 0) {
  15.               throw new IllegalArgumentException(String.format(
  16.                                           "worker Id can't be greater than %d or less than 0",
  17.                     this.maxWorkerId));
  18.         }
  19.         this.workerId = workerId;
  20.     }
  21.     public synchronized long nextId() {
  22.         long timestamp = this.timeGen();
  23.         if (this.lastTimestamp == timestamp) {
  24.             this.sequence = (this.sequence + 1) & this.sequenceMask;
  25.             if (this.sequence == 0) {
  26.                 System.out.println("###########" + sequenceMask);
  27.                 timestamp = this.tilNextMillis(this.lastTimestamp);
  28.              }
  29.             } else {
  30.                 this.sequence = 0;
  31.             }
  32.             if (timestamp < this.lastTimestamp) {
  33.                 try {
  34.                     throw new Exception(
  35.                           String.format(
  36.                               "Clock moved backwards. Refusing to generate id for %d milliseconds",
  37.                               this.lastTimestamp - timestamp));
  38.                 } catch (Exception e) {
  39.                     e.printStackTrace();
  40.                 }
  41.             }
  42.  
  43.         this.lastTimestamp = timestamp;
  44.         long nextId = ((timestamp - twepoch << timestampLeftShift))
  45.               | (this.workerId << this.workerIdShift) | (this.sequence);
  46.         System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"
  47.                                       + timestampLeftShift + ",nextId:" + nextId + ",workerId:"
  48.                                       + workerId + ",sequence:" + sequence);
  49.         return nextId;
  50.     }
  51.  
  52.     private long tilNextMillis(final long lastTimestamp) {
  53.         long timestamp = this.timeGen();
  54.         while (timestamp <= lastTimestamp) {
  55.             timestamp = this.timeGen();
  56.         }
  57.         return timestamp;
  58.     }
  59.  
  60.     private long timeGen() {
  61.         return System.currentTimeMillis();
  62.     }
  63.  
  64.     //调用
  65.     public static void main(String[] args){
  66.         IdWorker worker2 = new IdWorker(2);
  67.         System.out.println(worker2.nextId());
  68.     }
  69. }

转自：Twitter的分布式自增ID算法snowflake（雪花算法） C#和Java版 - 简书

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

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

  

闽ICP备14008679号