Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版

简介:

在分布式系统中,需要生成全局UID的场合还是比较多的,twitter的snowflake解决了这种需求,实现也还是很简单的,除去配置信息,核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。

该项目地址为:https://github.com/twitter/snowflake是用Scala实现的。

python版详见开源项目https://github.com/erans/pysnowflake

核心代码为其IdWorker这个类实现,其原理结构如下,我分别用一个0表示一位,用—分割开部分的作用:

1 0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。

且看其核心代码:

1 </pre>
2 /** Copyright 2010-2012 Twitter, Inc.*/
3 package com.twitter.service.snowflake
4  
5 import com.twitter.ostrich.stats.Stats
6 import com.twitter.service.snowflake.gen._
7 import java.util.Random
8 import com.twitter.logging.Logger
9  
10 /**
11  * An object that generates IDs.
12  * This is broken into a separate class in case
13  * we ever want to support multiple worker threads
14  * per process
15  */
16 class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L)
17 extends Snowflake.Iface {
18   private[this] def genCounter(agent: String) = {
19     Stats.incr("ids_generated")
20     Stats.incr("ids_generated_%s".format(agent))
21   }
22   private[this] val exceptionCounter = Stats.getCounter("exceptions")
23   private[this] val log = Logger.get
24   private[this] val rand = new Random
25  
26   val twepoch = 1288834974657L
27  
28  //机器标识位数
29  
30   private[this] val workerIdBits = 5L
31  
32 //数据中心标识位数
33   private[this] val datacenterIdBits = 5L
34  
35 //机器ID最大值
36   private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits)
37  
38 //数据中心ID最大值
39   private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)
40  
41 //毫秒内自增位
42   private[this] val sequenceBits = 12L
43  
44 //机器ID偏左移12位
45  
46   private[this] val workerIdShift = sequenceBits
47  
48 //数据中心ID左移17位
49   private[this] val datacenterIdShift = sequenceBits + workerIdBits
50  
51 //时间毫秒左移22位
52   private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
53   private[this] val sequenceMask = -1L ^ (-1L << sequenceBits)
54  
55   private[this] var lastTimestamp = -1L
56  
57   // sanity check for workerId
58   if (workerId > maxWorkerId || workerId < 0) {
59     exceptionCounter.incr(1)
60     throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId))
61   }
62  
63   if (datacenterId > maxDatacenterId || datacenterId < 0) {
64     exceptionCounter.incr(1)
65     throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))
66   }
67  
68   log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
69     timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
70  
71   def get_id(useragent: String): Long = {
72     if (!validUseragent(useragent)) {
73       exceptionCounter.incr(1)
74       throw new InvalidUserAgentError
75     }
76  
77     val id = nextId()
78     genCounter(useragent)
79  
80     reporter.report(new AuditLogEntry(id, useragent, rand.nextLong))
81     id
82   }
83  
84   def get_worker_id(): Long = workerId
85   def get_datacenter_id(): Long = datacenterId
86   def get_timestamp() = System.currentTimeMillis
87  
88   protected[snowflake] def nextId(): Long = synchronized {
89     var timestamp = timeGen()
90  
91  //时间错误
92  
93     if (timestamp < lastTimestamp) {
94       exceptionCounter.incr(1)
95       log.error("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
96       throw new InvalidSystemClock("Clock moved backwards.  Refusing to generate id for %d milliseconds".format(
97         lastTimestamp - timestamp))
98     }
99  
100     if (lastTimestamp == timestamp) {
101 //当前毫秒内,则+1
102       sequence = (sequence + 1) & sequenceMask
103       if (sequence == 0) {
104 //当前毫秒内计数满了,则等待下一秒
105         timestamp = tilNextMillis(lastTimestamp)
106       }
107     } else {
108       sequence = 0
109     }
110  
111     lastTimestamp = timestamp
112 //ID偏移组合生成最终的ID,并返回ID   
113  
114 ((timestamp - twepoch) << timestampLeftShift) |
115       (datacenterId << datacenterIdShift) |
116       (workerId << workerIdShift) |
117       sequence
118   }
119  
120 //等待下一个毫秒的到来 
121  
122 protected def tilNextMillis(lastTimestamp: Long): Long = {
123     var timestamp = timeGen()
124     while (timestamp <= lastTimestamp) {
125       timestamp = timeGen()
126     }
127     timestamp
128   }
129  
130   protected def timeGen(): Long = System.currentTimeMillis()
131  
132   val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r
133  
134   def validUseragent(useragent: String): Boolean = useragent match {
135     case AgentParser(_) => true
136     case _ => false
137   }
138 }
139 <pre>

上述为twitter的实现,下面且看一个Java实现,貌似为淘宝的朋友写的。

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

再来看一个php的实现

1 <?php
2 class Idwork
3 {
4 const debug = 1;
5 static $workerId;
6 static $twepoch = 1361775855078;
7 static $sequence = 0;
8 const workerIdBits = 4;
9 static $maxWorkerId = 15;
10 const sequenceBits = 10;
11 static $workerIdShift = 10;
12 static $timestampLeftShift = 14;
13 static $sequenceMask = 1023;
14 private  static $lastTimestamp = -1;
15  
16 function __construct($workId){
17 if($workId > self::$maxWorkerId || $workId< 0 )
18 {
19 throw new Exception("worker Id can't be greater than 15 or less than 0");
20 }
21 self::$workerId=$workId;
22  
23 echo 'logdebug->__construct()->self::$workerId:'.self::$workerId;
24 echo '</br>';
25  
26 }
27  
28 function timeGen(){
29 //获得当前时间戳
30 $time = explode(' ', microtime());
31 $time2= substr($time[0], 2, 3);
32 $timestramp = $time[1].$time2;
33 echo 'logdebug->timeGen()->$timestramp:'.$time[1].$time2;
34 echo '</br>';
35 return  $time[1].$time2;
36 }
37 function  tilNextMillis($lastTimestamp) {
38 $timestamp = $this->timeGen();
39 while ($timestamp <= $lastTimestamp) {
40 $timestamp = $this->timeGen();
41 }
42  
43 echo 'logdebug->tilNextMillis()->$timestamp:'.$timestamp;
44 echo '</br>';
45 return $timestamp;
46 }
47  
48 function  nextId()
49 {
50 $timestamp=$this->timeGen();
51 echo 'logdebug->nextId()->self::$lastTimestamp1:'.self::$lastTimestamp;
52 echo '</br>';
53 if(self::$lastTimestamp == $timestamp) {
54 self::$sequence = (self::$sequence + 1) & self::$sequenceMask;
55 if (self::$sequence == 0) {
56     echo "###########".self::$sequenceMask;
57     $timestamp = $this->tilNextMillis(self::$lastTimestamp);
58     echo 'logdebug->nextId()->self::$lastTimestamp2:'.self::$lastTimestamp;
59     echo '</br>';
60   }
61 } else {
62 self::$sequence  = 0;
63     echo 'logdebug->nextId()->self::$sequence:'.self::$sequence;
64     echo '</br>';
65 }
66 if ($timestamp < self::$lastTimestamp) {
67    throw new Excwption("Clock moved backwards.  Refusing to generate id for ".(self::$lastTimestamp-$timestamp)." milliseconds");
68    }
69 self::$lastTimestamp  = $timestamp;
70 echo 'logdebug->nextId()->self::$lastTimestamp3:'.self::$lastTimestamp;
71 echo '</br>';
72  
73 echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):'.((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch) ));
74 echo '</br>';
75 $nextId = ((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch)  )) | ( self::$workerId << self::$workerIdShift ) | self::$sequence;
76 echo 'timestamp:'.$timestamp.'-----';
77 echo 'twepoch:'.sprintf('%.0f', self::$twepoch).'-----';
78 echo 'timestampLeftShift ='.self::$timestampLeftShift.'-----';
79 echo 'nextId:'.$nextId.'----';
80 echo 'workId:'.self::$workerId.'-----';
81 echo 'workerIdShift:'.self::$workerIdShift.'-----';
82 return $nextId;
83 }
84  
85 }
86 $Idwork = new Idwork(1);
87 $a= $Idwork->nextId();
88 $Idwork = new Idwork(2);
89 $a= $Idwork->nextId();
90 ?>
目录
相关文章
|
18天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
51 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
21天前
|
数据采集 缓存 Java
Python vs Java:爬虫任务中的效率比较
Python vs Java:爬虫任务中的效率比较
|
1天前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
1天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
16天前
|
人工智能 文字识别 Java
SpringCloud+Python 混合微服务,如何打造AI分布式业务应用的技术底层?
尼恩,一位拥有20年架构经验的老架构师,通过其深厚的架构功力,成功指导了一位9年经验的网易工程师转型为大模型架构师,薪资逆涨50%,年薪近80W。尼恩的指导不仅帮助这位工程师在一年内成为大模型架构师,还让他管理起了10人团队,产品成功应用于多家大中型企业。尼恩因此决定编写《LLM大模型学习圣经》系列,帮助更多人掌握大模型架构,实现职业跃迁。该系列包括《从0到1吃透Transformer技术底座》、《从0到1精通RAG架构》等,旨在系统化、体系化地讲解大模型技术,助力读者实现“offer直提”。此外,尼恩还分享了多个技术圣经,如《NIO圣经》、《Docker圣经》等,帮助读者深入理解核心技术。
SpringCloud+Python 混合微服务,如何打造AI分布式业务应用的技术底层?
|
24天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
55 2
|
2月前
|
Java Linux Python
Linux环境下 代码java调用python出错
Linux环境下 代码java调用python出错
42 3
|
20天前
|
Java Python
如何通过Java程序调用python脚本
如何通过Java程序调用python脚本
18 0
|
21天前
|
安全 Java Python
基于python-django的Java网站全站漏洞检测系统
基于python-django的Java网站全站漏洞检测系统
28 0
|
2月前
|
SQL JavaScript 前端开发
用Java、Python来开发Hive应用
用Java、Python来开发Hive应用
30 6

热门文章

最新文章