转载自:IT虾米网

概述

SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:

  • 1位,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0
  • 41位,用来记录时间戳(毫秒)。

    <ul style="margin-left:3em;"><li>41位可以表示241−1个数字,</li> 
    	<li>如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至&nbsp;241−1,减1是因为可表示的数值范围是从0开始算的,而不是1。</li> 
    	<li>也就是说41位可以表示241−1个毫秒的值,转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年</li> 
    </ul></li> 
    <li> 
    <p><code>10位</code>,用来记录工作机器id。</p> 
     
    <ul style="margin-left:3em;"><li>可以部署在210=1024个节点,包括<code>5位datacenterId</code>和<code>5位workerId</code></li> 
    	<li><code>5位(bit)</code>可以表示的最大正整数是25−1=31,即可以用0、1、2、3、....31这32个数字,来表示不同的datecenterId或workerId</li> 
    </ul></li> 
    <li> 
    <p><code>12位</code>,序列号,用来记录同毫秒内产生的不同id。</p> 
     
    <ul style="margin-left:3em;"><li><code>12位(bit)</code>可以表示的最大正整数是212−1=4096,即可以用0、1、2、3、....4095这4096个数字,来表示同一机器同一时间截(毫秒)内产生的4096个ID序号</li> 
    </ul></li> 
    

由于在Java中64bit的整数是long类型,所以在Java中SnowFlake算法生成的id就是long来存储的。

SnowFlake可以保证:

  • 所有生成的id按时间趋势递增
  • 整个分布式系统内不会产生重复id(因为有datacenterId和workerId来做区分)

Talk is cheap, show you the code

以下是Twitter官方原版的,用Scala写的,(我也不懂Scala,当成Java看即可):


   
  1. /** Copyright 2010-2012 Twitter, Inc.*/
  2. package com.twitter.service.snowflake
  3. import com.twitter.ostrich.stats. Stats
  4. import com.twitter.service.snowflake.gen._
  5. import java.util. Random
  6. import com.twitter.logging. Logger
  7. /**
  8. * An object that generates IDs.
  9. * This is broken into a separate class in case
  10. * we ever want to support multiple worker threads
  11. * per process
  12. */
  13. class IdWorker(
  14. val workerId: Long,
  15. val datacenterId: Long,
  16. private val reporter: Reporter,
  17. var sequence: Long = 0L) 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. val twepoch = 1288834974657L
  26. private[ this] val workerIdBits = 5L
  27. private[ this] val datacenterIdBits = 5L
  28. private[ this] val maxWorkerId = -1L ^ ( -1L << workerIdBits)
  29. private[ this] val maxDatacenterId = -1L ^ ( -1L << datacenterIdBits)
  30. private[ this] val sequenceBits = 12L
  31. private[ this] val workerIdShift = sequenceBits
  32. private[ this] val datacenterIdShift = sequenceBits + workerIdBits
  33. private[ this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
  34. private[ this] val sequenceMask = -1L ^ ( -1L << sequenceBits)
  35. private[ this] var lastTimestamp = -1L
  36. // sanity check for workerId
  37. if (workerId > maxWorkerId || workerId < 0) {
  38. exceptionCounter.incr( 1)
  39. throw new IllegalArgumentException( "worker Id can't be greater than %d or less than 0".format(maxWorkerId))
  40. }
  41. if (datacenterId > maxDatacenterId || datacenterId < 0) {
  42. exceptionCounter.incr( 1)
  43. throw new IllegalArgumentException( "datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))
  44. }
  45. log.info( "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
  46. timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
  47. def get_id(useragent: String): Long = {
  48. if (!validUseragent(useragent)) {
  49. exceptionCounter.incr( 1)
  50. throw new InvalidUserAgentError
  51. }
  52. val id = nextId()
  53. genCounter(useragent)
  54. reporter.report( new AuditLogEntry(id, useragent, rand.nextLong))
  55. id
  56. }
  57. def get_worker_id(): Long = workerId
  58. def get_datacenter_id(): Long = datacenterId
  59. def get_timestamp() = System.currentTimeMillis
  60. protected[snowflake] def nextId(): Long = synchronized {
  61. var timestamp = timeGen()
  62. if (timestamp < lastTimestamp) {
  63. exceptionCounter.incr( 1)
  64. log.error( "clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
  65. throw new InvalidSystemClock( "Clock moved backwards. Refusing to generate id for %d milliseconds".format(
  66. lastTimestamp - timestamp))
  67. }
  68. if (lastTimestamp == timestamp) {
  69. sequence = (sequence + 1) & sequenceMask
  70. if (sequence == 0) {
  71. timestamp = tilNextMillis(lastTimestamp)
  72. }
  73. } else {
  74. sequence = 0
  75. }
  76. lastTimestamp = timestamp
  77. ((timestamp - twepoch) << timestampLeftShift) |
  78. (datacenterId << datacenterIdShift) |
  79. (workerId << workerIdShift) |
  80. sequence
  81. }
  82. protected def tilNextMillis(lastTimestamp: Long): Long = {
  83. var timestamp = timeGen()
  84. while (timestamp <= lastTimestamp) {
  85. timestamp = timeGen()
  86. }
  87. timestamp
  88. }
  89. protected def timeGen(): Long = System.currentTimeMillis()
  90. val AgentParser = "" "([a-zA-Z][a-zA-Z\-0-9]*)" "".r
  91. def validUseragent(useragent: String): Boolean = useragent match {
  92. case AgentParser(_) => true
  93. case _ => false
  94. }
  95. }

Scala是一门可以编译成字节码的语言,简单理解是在Java语法基础上加上了很多语法糖,例如不用每条语句后写分号,可以使用动态类型等等。抱着试一试的心态,我把Scala版的代码“翻译”成Java版本的,对scala代码改动的地方如下:


   
  1. /** Copyright 2010-2012 Twitter, Inc.*/
  2. package com.twitter.service.snowflake
  3. import com.twitter.ostrich.stats. Stats
  4. import com.twitter.service.snowflake.gen._
  5. import java.util. Random
  6. import com.twitter.logging. Logger
  7. /**
  8. * An object that generates IDs.
  9. * This is broken into a separate class in case
  10. * we ever want to support multiple worker threads
  11. * per process
  12. */
  13. class IdWorker( // |
  14. val workerId: Long, // |
  15. val datacenterId: Long, // |<--这部分改成 Java 的构造函数形式
  16. private val reporter: Reporter, //日志相关,删 // |
  17. var sequence: Long = 0L) // |
  18. extends Snowflake. Iface { //接口找不到,删 // |
  19. private[ this] def genCounter(agent: String) = { // |
  20. Stats.incr( "ids_generated") // |
  21. Stats.incr( "ids_generated_%s".format(agent)) // |<--错误、日志处理相关,删
  22. } // |
  23. private[ this] val exceptionCounter = Stats.getCounter( "exceptions") // |
  24. private[ this] val log = Logger. get // |
  25. private[ this] val rand = new Random // |
  26. val twepoch = 1288834974657L
  27. private[ this] val workerIdBits = 5L
  28. private[ this] val datacenterIdBits = 5L
  29. private[ this] val maxWorkerId = -1L ^ ( -1L << workerIdBits)
  30. private[ this] val maxDatacenterId = -1L ^ ( -1L << datacenterIdBits)
  31. private[ this] val sequenceBits = 12L
  32. private[ this] val workerIdShift = sequenceBits
  33. private[ this] val datacenterIdShift = sequenceBits + workerIdBits
  34. private[ this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
  35. private[ this] val sequenceMask = -1L ^ ( -1L << sequenceBits)
  36. private[ this] var lastTimestamp = -1L
  37. //----------------------------------------------------------------------------------------------------------------------------//
  38. // sanity check for workerId //
  39. if (workerId > maxWorkerId || workerId < 0) { //
  40. exceptionCounter.incr( 1) //<--错误处理相关,删 //
  41. throw new IllegalArgumentException( "worker Id can't be greater than %d or less than 0".format(maxWorkerId)) //这
  42. // |-->改成:throw new IllegalArgumentException //部
  43. // (String.format("worker Id can't be greater than %d or less than 0",maxWorkerId)) //分
  44. } //放
  45. //到
  46. if (datacenterId > maxDatacenterId || datacenterId < 0) { //构
  47. exceptionCounter.incr( 1) //<--错误处理相关,删 //造
  48. throw new IllegalArgumentException( "datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId)) //函
  49. // |-->改成:throw new IllegalArgumentException //数
  50. // (String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId)) //中
  51. } //
  52. //
  53. log.info( "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", //
  54. timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId) //
  55. // |-->改成:System.out.printf("worker...%d...",timestampLeftShift,...); //
  56. //----------------------------------------------------------------------------------------------------------------------------//
  57. //-------------------------------------------------------------------//
  58. //这个函数删除错误处理相关的代码后,剩下一行代码:val id = nextId() //
  59. //所以我们直接调用nextId()函数可以了,所以在“翻译”时可以删除这个函数 //
  60. def get_id(useragent: String): Long = { //
  61. if (!validUseragent(useragent)) { //
  62. exceptionCounter.incr( 1) //
  63. throw new InvalidUserAgentError //删
  64. } //除
  65. //
  66. val id = nextId() //
  67. genCounter(useragent) //
  68. //
  69. reporter.report( new AuditLogEntry(id, useragent, rand.nextLong)) //
  70. id //
  71. } //
  72. //-------------------------------------------------------------------//
  73. def get_worker_id(): Long = workerId // |
  74. def get_datacenter_id(): Long = datacenterId // |<--改成Java函数
  75. def get_timestamp() = System.currentTimeMillis // |
  76. protected[snowflake] def nextId(): Long = synchronized { // 改成Java函数
  77. var timestamp = timeGen()
  78. if (timestamp < lastTimestamp) {
  79. exceptionCounter.incr( 1) // 错误处理相关,删
  80. log.error( "clock is moving backwards. Rejecting requests until %d.", lastTimestamp); // 改成System.err.printf(...)
  81. throw new InvalidSystemClock( "Clock moved backwards. Refusing to generate id for %d milliseconds".format(
  82. lastTimestamp - timestamp)) // 改成RumTimeException
  83. }
  84. if (lastTimestamp == timestamp) {
  85. sequence = (sequence + 1) & sequenceMask
  86. if (sequence == 0) {
  87. timestamp = tilNextMillis(lastTimestamp)
  88. }
  89. } else {
  90. sequence = 0
  91. }
  92. lastTimestamp = timestamp
  93. ((timestamp - twepoch) << timestampLeftShift) | // |<--加上关键字return
  94. (datacenterId << datacenterIdShift) | // |
  95. (workerId << workerIdShift) | // |
  96. sequence // |
  97. }
  98. protected def tilNextMillis(lastTimestamp: Long): Long = { // 改成Java函数
  99. var timestamp = timeGen()
  100. while (timestamp <= lastTimestamp) {
  101. timestamp = timeGen()
  102. }
  103. timestamp // 加上关键字return
  104. }
  105. protected def timeGen(): Long = System.currentTimeMillis() // 改成Java函数
  106. val AgentParser = "" "([a-zA-Z][a-zA-Z\-0-9]*)" "".r // |
  107. // |
  108. def validUseragent(useragent: String): Boolean = useragent match { // |<--日志相关,删
  109. case AgentParser(_) => true // |
  110. case _ => false // |
  111. } // |
  112. }

改出来的Java版:


   
  1. public class IdWorker{
  2. private long workerId;
  3. private long datacenterId;
  4. private long sequence;
  5. public IdWorker ( long workerId, long datacenterId, long sequence){
  6. // sanity check for workerId
  7. if (workerId > maxWorkerId || workerId < 0) {
  8. throw new IllegalArgumentException(String.format( "worker Id can't be greater than %d or less than 0",maxWorkerId));
  9. }
  10. if (datacenterId > maxDatacenterId || datacenterId < 0) {
  11. throw new IllegalArgumentException(String.format( "datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
  12. }
  13. System. out.printf( "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
  14. timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);
  15. this.workerId = workerId;
  16. this.datacenterId = datacenterId;
  17. this.sequence = sequence;
  18. }
  19. private long twepoch = 1288834974657L;
  20. private long workerIdBits = 5L;
  21. private long datacenterIdBits = 5L;
  22. private long maxWorkerId = - 1L ^ ( - 1L << workerIdBits);
  23. private long maxDatacenterId = - 1L ^ ( - 1L << datacenterIdBits);
  24. private long sequenceBits = 12L;
  25. private long workerIdShift = sequenceBits;
  26. private long datacenterIdShift = sequenceBits + workerIdBits;
  27. private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
  28. private long sequenceMask = - 1L ^ ( - 1L << sequenceBits);
  29. private long lastTimestamp = - 1L;
  30. public long getWorkerId (){
  31. return workerId;
  32. }
  33. public long getDatacenterId (){
  34. return datacenterId;
  35. }
  36. public long getTimestamp (){
  37. return System.currentTimeMillis();
  38. }
  39. public synchronized long nextId () {
  40. long timestamp = timeGen();
  41. if (timestamp < lastTimestamp) {
  42. System.err.printf( "clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
  43. throw new RuntimeException(String.format( "Clock moved backwards. Refusing to generate id for %d milliseconds",
  44. lastTimestamp - timestamp));
  45. }
  46. if (lastTimestamp == timestamp) {
  47. sequence = (sequence + 1) & sequenceMask;
  48. if (sequence == 0) {
  49. timestamp = tilNextMillis(lastTimestamp);
  50. }
  51. } else {
  52. sequence = 0;
  53. }
  54. lastTimestamp = timestamp;
  55. return ((timestamp - twepoch) << timestampLeftShift) |
  56. (datacenterId << datacenterIdShift) |
  57. (workerId << workerIdShift) |
  58. sequence;
  59. }
  60. private long tilNextMillis ( long lastTimestamp) {
  61. long timestamp = timeGen();
  62. while (timestamp <= lastTimestamp) {
  63. timestamp = timeGen();
  64. }
  65. return timestamp;
  66. }
  67. private long timeGen (){
  68. return System.currentTimeMillis();
  69. }
  70. //---------------测试---------------
  71. public static void main (String[] args) {
  72. IdWorker worker = new IdWorker( 1, 1, 1);
  73. for ( int i = 0; i < 30; i++) {
  74. System. out.println(worker.nextId());
  75. }
  76. }
  77. }

代码理解

上面的代码中,有部分位运算的代码,如:


   
  1. sequence = (sequence + 1) & sequenceMask;
  2. private long maxWorkerId = - 1L ^ (- 1L << workerIdBits);
  3. return ((timestamp - twepoch) << timestampLeftShift) |
  4. (datacenterId << datacenterIdShift) |
  5. (workerId << workerIdShift) |
  6. sequence;

为了能更好理解,我对相关知识研究了一下。

负数的二进制表示

在计算机中,负数的二进制是用补码来表示的。
假设我是用Java中的int类型来存储数字的,
int类型的大小是32个二进制位(bit),即4个字节(byte)。(1 byte = 8 bit)
那么十进制数字3在二进制中的表示应该是这样的:


   
  1. 00000000 00000000 00000000 00000011
  2. // 3的二进制表示,就是原码

那数字-3在二进制中应该如何表示?
我们可以反过来想想,因为-3+3=0,
在二进制运算中把-3的二进制看成未知数x来求解
求解算式的二进制表示如下:


   
  1. 00000000 00000000 00000000 00000011 //3,原码
  2. + xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx //-3,补码
  3. -----------------------------------------------
  4. 00000000 00000000 00000000 00000000

反推x的值,3的二进制加上什么值才使结果变成00000000 00000000 00000000 00000000?:


   
  1. 00000000 00000000 00000000 00000011 //3,原码
  2. + 11111111 11111111 11111111 11111101 //-3,补码
  3. -----------------------------------------------
  4. 1 00000000 00000000 00000000 00000000

反推的思路是3的二进制数从最低位开始逐位加1,使溢出的1不断向高位溢出,直到溢出到第33位。然后由于int类型最多只能保存32个二进制位,所以最高位的1溢出了,剩下的32位就成了(十进制的)0。

补码的意义就是可以拿补码和原码(3的二进制)相加,最终加出一个“溢出的0”

以上是理解的过程,实际中记住公式就很容易算出来:

  • 补码 = 反码 + 1
  • 补码 = (原码 - 1)再取反码

因此-1的二进制应该这样算:


   
  1. 00000000 00000000 00000000 00000001 //原码: 1 的二进制
  2. 11111111 11111111 11111111 11111110 //取反码: 1 的二进制的反码
  3. 11111111 11111111 11111111 11111111 //加 1 :- 1 的二进制表示(补码)

用位运算计算n个bit能表示的最大数值

比如这样一行代码:


   
  1. private long workerIdBits = 5L;
  2. private long maxWorkerId = -1L ^ (-1L << workerIdBits);

上面代码换成这样看方便一点:
long maxWorkerId = -1L ^ (-1L << 5L)

咋一看真的看不准哪个部分先计算,于是查了一下Java运算符的优先级表:

所以上面那行代码中,运行顺序是:

  • -1 左移 5,得结果a
  • -1 异或 a

long maxWorkerId = -1L ^ (-1L << 5L)的二进制运算过程如下:

-1 左移 5,得结果a :


   
  1. 11111111 11111111 11111111 11111111 //-1的二进制表示(补码)
  2. 11111 11111111 11111111 11111111 11100000 //高位溢出的不要,低位补0
  3. 11111111 11111111 11111111 11100000 //结果a

-1 异或 a :


   
  1. 11111111 11111111 11111111 11111111 //-1的二进制表示(补码)
  2. ^ 11111111 11111111 11111111 11100000 //两个操作数的位中,相同则为0,不同则为1
  3. ---------------------------------------------------------------------------
  4. 00000000 00000000 00000000 00011111 //最终结果31

最终结果是31,二进制00000000 00000000 00000000 00011111转十进制可以这么算:

24+23+22+21+20=16+8+4+2+1=31

那既然现在知道算出来long maxWorkerId = -1L ^ (-1L << 5L)中的maxWorkerId = 31,有什么含义?为什么要用左移5来算?如果你看过概述部分,请找到这段内容看看:

5位(bit)可以表示的最大正整数是25−1=31,即可以用0、1、2、3、....31这32个数字,来表示不同的datecenterId或workerId

-1L ^ (-1L << 5L)结果是31,25−1的结果也是31,所以在代码中,-1L ^ (-1L << 5L)的写法是利用位运算计算出5位能表示的最大正整数是多少

用mask防止溢出

有一段有趣的代码:

sequence = (sequence + 1) & sequenceMask;
  

分别用不同的值测试一下,你就知道它怎么有趣了:


   
  1. long seqMask = -1L ^ ( -1L << 12L); //计算12位能耐存储的最大正整数,相当于:2^12-1 = 4095
  2. System. out.println( "seqMask: "+seqMask);
  3. System. out.println( 1L & seqMask);
  4. System. out.println( 2L & seqMask);
  5. System. out.println( 3L & seqMask);
  6. System. out.println( 4L & seqMask);
  7. System. out.println( 4095L & seqMask);
  8. System. out.println( 4096L & seqMask);
  9. System. out.println( 4097L & seqMask);
  10. System. out.println( 4098L & seqMask);
  11. /**
  12. seqMask: 4095
  13. 1
  14. 2
  15. 3
  16. 4
  17. 4095
  18. 0
  19. 1
  20. 2
  21. */

这段代码通过位与运算保证计算的结果范围始终是 0-4095 !

用位运算汇总结果

还有另外一段诡异的代码:


   
  1. return ((timestamp - twepoch) << timestampLeftShift) |
  2. (datacenterId << datacenterIdShift) |
  3. (workerId << workerIdShift) |
  4. sequence;

为了弄清楚这段代码,

首先 需要计算一下相关的值:


   
  1. private long twepoch = 1288834974657L; //起始时间戳,用于用当前时间戳减去这个时间戳,算出偏移量
  2. private long workerIdBits = 5L; //workerId占用的位数:5
  3. private long datacenterIdBits = 5L; //datacenterId占用的位数:5
  4. private long maxWorkerId = -1L ^ (-1L << workerIdBits); // workerId可以使用的最大数值:31
  5. private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // datacenterId可以使用的最大数值:31
  6. private long sequenceBits = 12L;//序列号占用的位数:12
  7. private long workerIdShift = sequenceBits; // 12
  8. private long datacenterIdShift = sequenceBits + workerIdBits; // 12+5 = 17
  9. private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 12+5+5 = 22
  10. private long sequenceMask = -1L ^ (-1L << sequenceBits);//4095
  11. private long lastTimestamp = -1L;

其次 写个测试,把参数都写死,并运行打印信息,方便后面来核对计算结果:


   
  1. //---------------测试---------------
  2. public static void main (String[] args) {
  3. long timestamp = 1505914988849L;
  4. long twepoch = 1288834974657L;
  5. long datacenterId = 17L;
  6. long workerId = 25L;
  7. long sequence = 0L;
  8. System. out.printf( "\ntimestamp: %d \n",timestamp);
  9. System. out.printf( "twepoch: %d \n",twepoch);
  10. System. out.printf( "datacenterId: %d \n",datacenterId);
  11. System. out.printf( "workerId: %d \n",workerId);
  12. System. out.printf( "sequence: %d \n",sequence);
  13. System. out.println();
  14. System. out.printf( "(timestamp - twepoch): %d \n",(timestamp - twepoch));
  15. System. out.printf( "((timestamp - twepoch) << 22L): %d \n",((timestamp - twepoch) << 22L));
  16. System. out.printf( "(datacenterId << 17L): %d \n" ,(datacenterId << 17L));
  17. System. out.printf( "(workerId << 12L): %d \n",(workerId << 12L));
  18. System. out.printf( "sequence: %d \n",sequence);
  19. long result = ((timestamp - twepoch) << 22L) |
  20. (datacenterId << 17L) |
  21. (workerId << 12L) |
  22. sequence;
  23. System. out.println(result);
  24. }
  25. /** 打印信息:
  26. timestamp: 1505914988849
  27. twepoch: 1288834974657
  28. datacenterId: 17
  29. workerId: 25
  30. sequence: 0
  31. (timestamp - twepoch): 217080014192
  32. ((timestamp - twepoch) << 22L): 910499571845562368
  33. (datacenterId << 17L): 2228224
  34. (workerId << 12L): 102400
  35. sequence: 0
  36. 910499571847892992
  37. */

代入位移的值得之后,就是这样:


   
  1. return ((timestamp - 1288834974657) << 22) |
  2. (datacenterId << 17) |
  3. (workerId << 12) |
  4. sequence;

对于尚未知道的值,我们可以先看看概述 中对SnowFlake结构的解释,再代入在合法范围的值(windows系统可以用计算器方便计算这些值的二进制),来了解计算的过程。
当然,由于我的测试代码已经把这些值写死了,那直接用这些值来手工验证计算结果即可:


   
  1. long timestamp = 1505914988849L;
  2. long twepoch = 1288834974657L;
  3. long datacenterId = 17L;
  4. long workerId = 25L;
  5. long sequence = 0L;

   
  1. 设:timestamp = 1505914988849,twepoch = 1288834974657
  2. 1505914988849 - 1288834974657 = 217080014192 (timestamp相对于起始时间的毫秒偏移量),其(a)二进制左移 22位计算过程如下:
  3. |<--这里开始左右 22位 ‭
  4. 00000000 00000000 000000| 00 00110010 10001010 11111010 00100101 01110000 // a = 217080014192
  5. 00001100 10100010 10111110 10001001 01011100 00| 000000 00000000 00000000 // a左移22位后的值(la)
  6. |<--这里后面的位补 0


   
  1. 设:datacenterId = 17,其(b)二进制左移 17位计算过程如下:
  2. |<--这里开始左移 17
  3. 00000000 00000000 0| 000000000000000 00000000 00000000 00000000 00010001 // b = 17
  4. 00000000 00000000 00000000 00000000 00000000 0010001| 0 00000000 00000000 // b左移17位后的值(lb)
  5. |<--这里后面的位补 0


   
  1. 设:workerId = 25,其( c)二进制左移 12位计算过程如下:
  2. |<--这里开始左移 12
  3. 00000000 0000| 0000 00000000 00000000 00000000 00000000 00000000 00011001// c = 25
  4. 00000000 00000000 00000000 00000000 00000000 00000001 1001| 0000 00000000// c左移12位后的值(lc)
  5. |<--这里后面的位补 0


   
  1. 设:sequence = 0,其二进制如下:
  2. 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000// sequence = 0

现在知道了每个部分左移后的值(la,lb,lc),代码可以简化成下面这样去理解:


   
  1. return ((timestamp - 1288834974657) << 22) |
  2. (datacenterId << 17) |
  3. (workerId << 12) |
  4. sequence;
  5. -----------------------------
  6. |
  7. |简化
  8. \|/
  9. -----------------------------
  10. return (la) |
  11. (lb) |
  12. (lc) |
  13. sequence;

上面的管道符号|在Java中也是一个位运算符。其含义是:
x的第n位和y的第n位 只要有一个是1,则结果的第n位也为1,否则为0,因此,我们对四个数的位或运算如下:


   
  1. 1 | 41 | 5 | 5 | 12
  2. 0| 0001100 10100010 10111110 10001001 01011100 00| 00000| 0 0000| 0000 00000000 //la
  3. 0| 0000000 00000000 00000000 00000000 00000000 00| 10001| 0 0000| 0000 00000000 //lb
  4. 0| 0000000 00000000 00000000 00000000 00000000 00| 00000| 1 1001| 0000 00000000 //lc
  5. or 0| 0000000 00000000 00000000 00000000 00000000 00| 00000| 0 0000|‭ 0000 00000000//sequence
  6. ------------------------------------------------------------------------------------------
  7. 0| 0001100 10100010 10111110 10001001 01011100 00| 10001| 1 1001|‭ 0000 00000000//结果:910499571847892992

结果计算过程:
1) 从至左列出1出现的下标(从0开始算):


   
  1. 0000 1 1 00 1 0 1 000 1 0 1 0 1 1 1 1 1 0 1 000 1 00 1 0 1 0 1 1 1 0000 1 000 1 1 1 00 10000 0000 0000
  2. 59 58 55 53 49 47 45 44 43 42 41 39 35 32 30 28 27 26 21 17 16 15 12

2) 各个下标作为2的幂数来计算,并相加:

259+258+255+253+249+247+245+244+243+242+241+239+235+232+230+228+227+226+221+217+216+215+22


   
  1. 2^ 59} : 576460752303423488
  2. 2^ 58} : 288230376151711744
  3. 2^ 55} : 36028797018963968
  4. 2^ 53} : 9007199254740992
  5. 2^ 49} : 562949953421312
  6. 2^ 47} : 140737488355328
  7. 2^ 45} : 35184372088832
  8. 2^ 44} : 17592186044416
  9. 2^ 43} : 8796093022208
  10. 2^ 42} : 4398046511104
  11. 2^ 41} : 2199023255552
  12. 2^ 39} : 549755813888
  13. 2^ 35} : 34359738368
  14. 2^ 32} : 4294967296
  15. 2^ 30} : 1073741824
  16. 2^ 28} : 268435456
  17. 2^ 27} : 134217728
  18. 2^ 26} : 67108864
  19. 2^ 21} : 2097152
  20. 2^ 17} : 131072
  21. 2^ 16} : 65536
  22. 2^ 15} : 32768
  23. + 2 ^ 12 } : 4096
  24. ----------------------------------------
  25. 910499571847892992

计算截图:

跟测试程序打印出来的结果一样,手工验证完毕!

观察


   
  1. 1 | 41 | 5 | 5 | 12
  2. 0| 0001100 10100010 10111110 10001001 01011100 00| | | //la
  3. 0| | 10001| | //lb
  4. 0| | | 1 1001| //lc
  5. or 0| | | |‭ 0000 00000000//sequence
  6. ------------------------------------------------------------------------------------------
  7. 0| 0001100 10100010 10111110 10001001 01011100 00| 10001| 1 1001|‭ 0000 00000000//结果:910499571847892992

上面的64位我按1、41、5、5、12的位数截开了,方便观察。

  • 纵向观察发现:

    <ul style="margin-left:3em;"><li>在41位那一段,除了la一行有值,其它行(lb、lc、sequence)都是0,(我爸其它)</li> 
    	<li>在左起第一个5位那一段,除了lb一行有值,其它行都是0</li> 
    	<li>在左起第二个5位那一段,除了lc一行有值,其它行都是0</li> 
    	<li>按照这规律,如果sequence是0以外的其它值,12位那段也会有值的,其它行都是0</li> 
    </ul></li> 
    <li> 
    <p><code>横向</code>观察发现:</p> 
     
    <ul style="margin-left:3em;"><li>在la行,由于左移了5+5+12位,5、5、12这三段都补0了,所以la行除了41那段外,其它肯定都是0</li> 
    	<li>同理,lb、lc、sequnece行也以此类推</li> 
    	<li>正因为左移的操作,使四个不同的值移到了SnowFlake理论上相应的位置,然后四行做<code>位或</code>运算(只要有1结果就是1),就把4段的二进制数合并成一个二进制数。</li> 
    </ul></li> 
    

结论:
所以,在这段代码中


   
  1. return ((timestamp - 1288834974657) << 22) |
  2. (datacenterId << 17) |
  3. (workerId << 12) |
  4. sequence;

左移运算是为了将数值移动到对应的段(41、5、5,12那段因为本来就在最右,因此不用左移)。

然后对每个左移后的值(la、lb、lc、sequence)做位或运算,是为了把各个短的数据合并起来,合并成一个二进制数。

最后转换成10进制,就是最终生成的id

扩展

在理解了这个算法之后,其实还有一些扩展的事情可以做:

  1. 根据自己业务修改每个位段存储的信息。算法是通用的,可以根据自己需求适当调整每段的大小以及存储的信息。
  2. 解密id,由于id的每段都保存了特定的信息,所以拿到一个id,应该可以尝试反推出原始的每个段的信息。反推出的信息可以帮助我们分析。比如作为订单,可以知道该订单的生成日期,负责处理的数据中心等等。

原文地址:https://blog.csdn.net/Ka_Ka314/article/details/79594485


发布评论
IT序号网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

全局唯一iD的生成 雪花算法详解及其他用法知识解答
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。