Snowflake

世界上没有两片完全相同的雪花。

​ — twitter

Snowflake原理

这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图所示：

在java里，64bit正好是long类型的大小。

41-bit的时间可以表示（1L<<41）/(1000ms * 60s * 60m * 24h * 365d)=69年的时间，10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。12个自增序列号可以表示212个ID，理论上snowflake方案的QPS约为212=4096/ms, 也就是409.6w/s，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

+-----------+--------------------------+---------------------+----------------------+----------------+

| sign | time_stamp | datacenter | worker node | sequence |

+-----------+--------------------------+---------------------+----------------------+----------------+

​ 1bit 41 bits 5bits 5bits 12bits

+-----------+--------------------------+---------------------+----------------------+----------------+

  • 1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0

  • 41位，用来记录时间戳（毫秒）。

    • 41位可以表示$2^{41}-1$个数字，
    • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 $2^{41}-1$，减1是因为可表示的数值范围是从0开始算的，而不是1。
    • 也就是说41位可以表示$2{41}-1$个毫秒的值，转化成单位年则是$(2{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年

  • 10位，用来记录工作机器id。

    • 可以部署在$2^{10} = 1024$个节点，包括5位datacenterId和5位workerId
    • 5位（bit）可以表示的最大正整数是$2^{5}-1 = 31$，即可以用0、1、2、3、....31这32个数字，来表示不同的datecenterId或workerId

  • 12位，序列号，用来记录同毫秒内产生的不同id。

    • 12位（bit）可以表示的最大正整数是$2^{12}-1 = 4095$，即可以用0、1、2、3、....4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号

位操作解释

    /**

     * define the initial bit for each part of 64 bits of one Id

     */

    private final long sequenceBits = 12L;

    private final long datacenterIdBits = 5L;

    private final long workerIdBits = 5L;

    private final long timestampBits = 41L;

    /*

     * max values of workerId, datacenterId and sequence

     * 11111111 11111111 11111111 11111111  // -1 in binary format

     */

    // 2^5-1 = 31

    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    // 2^10-1 = 1023

    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    // 2^12-1 = 4095

    private final long maxSequence = -1L ^ (-1L << sequenceBits);

先看snowflake里面定义成员变量的一个神操作，为什么这么定义呢？需要先了解下二进制位操作的原理。

负数的二进制表示

在计算机中，负数的二进制是用补码来表示的。

假设我是用Java中的int类型来存储数字的，

int类型的大小是32个二进制位（bit），即4个字节（byte）。（1 byte = 8 bit）

那么十进制数字3在二进制中的表示应该是这样的：

00000000 00000000 00000000 00000011

// 3的二进制表示，就是原码

那数字-3在二进制中应该如何表示？

我们可以反过来想想，因为-3+3=0，

在二进制运算中把-3的二进制看成未知数x来求解，

求解算式的二进制表示如下：



   00000000 00000000 00000000 00000011 //3，原码

+  xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx //-3，补码

-----------------------------------------------

   00000000 00000000 00000000 00000000

反推x的值，3的二进制加上什么值才使结果变成00000000 00000000 00000000 00000000？：

  00000000 00000000 00000000 00000011 //3，原码

+ 11111111 11111111 11111111 11111101 //-3，补码

-----------------------------------------------

 1 00000000 00000000 00000000 00000000

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

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

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

  • 补码 = 反码 + 1
  • 补码 = （原码 - 1）再取反码

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

00000000 00000000 00000000 00000001 //原码：1的二进制

11111111 11111111 11111111 11111110 //取反码：1的二进制的反码

11111111 11111111 11111111 11111111 //加1：-1的二进制表示（补码）

用位运算 得出n个bit能存储最大值

private long workerIdBits = 5L;

// 2^5-1 = 31

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

其中：

^ 操作符是 异或 操作, 即：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

异或[1]也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。

延伸：巧用异或算法

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现

一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空

间，能否设计一个算法实现？

解法一、显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去1+2+…+1000的和。

这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。

解法二、异或就没有这个问题，并且性能更好。

将所有的数全部异或，得到的结果与123…1000的结果进行异或，得到的结果就是重复数。

google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？

Leecode：https://leetcode-cn.com/problems/single-number/solution/

@Test

public void fun() {

	int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };

	int temp = 0;

	for (int i = 0; i < a.length; i++) {

		temp ^= a[i];

	}

	System.out.println(temp);

}

解法有很多，但是最好的和上面一样，就是把所有数异或，最后结果就是要找的，原理同上！！

<< 是 左移 操作

private long workerIdBits = 5L;

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

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

  • -1 左移 5，得结果a
      11111111 11111111 11111111 11111111 //-1的二进制表示（补码）

11111 11111111 11111111 11111111 11100000 //高位溢出的不要，低位补0

      11111111 11111111 11111111 11100000 //结果a
  • -1 异或 a
  11111111 11111111 11111111 11111111 //-1的二进制表示（补码）

^ 11111111 11111111 11111111 11100000 //两个操作数的位中，相同则为0，不同则为1

  ---------------------------------------------------------------------------

  00000000 00000000 00000000 00011111 //最终结果31

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

2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 16 + 8 + 4 +2 +1 = 31

所以这一通操作其实是通过位运算计算出来5bit的work id 最多能存储31个值，也就是最多支持31个节点。

位与 操作防止溢出

我们在跨毫秒时，序列号总是归0，会使得序列号为0的ID比较多，导致生成的ID取模后不均匀。优化的点是，序列号不是每次都归0，而是归一个0到100的随机数。

//如果当前操作落在同一个ms（timestamp位相同）的话

if (lastTimestamp == currentTimestamp) {

  					//sequence++ 且 保证不溢出，下面测试可知道如果溢出了maxSequence就会变成0

            sequence = (sequence + 1) & maxSequence;

            if (sequence == 0) {

                // overflow: greater than max sequence

                sequence = RANDOM.nextInt(100);

                currentTimestamp = waitNextMillis(lastTimestamp);

            }

        } else {

            //如果是新的ms开始，防止并发不够每次都是0

            //sequence = 0L;

            sequence = RANDOM.nextInt(100);

        }

关于这里的溢出操作分别用不同的值测试一下，就知道原理了：

long seqMask = -1L ^ (-1L << 12L); //计算12位能耐存储的最大正整数，相当于：2^12-1 = 4095

System.out.println("seqMask: "+seqMask);

System.out.println(1L & seqMask);

System.out.println(2L & seqMask);

System.out.println(3L & seqMask);

System.out.println(4L & seqMask);

System.out.println(4095L & seqMask);

System.out.println(4096L & seqMask);

System.out.println(4097L & seqMask);

System.out.println(4098L & seqMask);

/**

* 输出结果是：

    seqMask: 4095

    1

    2

    3

    4

    4095

    0

    1

    2

*/

因为maxSequence 我们选用12bit最大值是4095，这段代码通过位与运算保证计算的结果范围始终是 0-4095 ！

生成id的核心代码

long id = ((currentTimestamp - epoch) << timestampShift) |

                (datacenterId << datacenterIdShift) |

                (workerId << workerIdShift) |

                sequence;

计算分为2部分：

  1. << 每个对应部分的id 左移对应的bits；

  2. 管道符号|在Java中也是一个位运算符。其含义是：

    x的第n位和y的第n位 只要有一个是1，则结果的第n位也为1，否则为0，因此，我们对四个数的位或运算如下：

1  |                    41                        |  5  |   5  |     12      

  0|0001100 10100010 10111110 10001001 01011100 00|00000|0 0000|0000 00000000

  0|000000‭0 00000000 00000000 00000000 00000000 00|10001|0 0000|0000 00000000

  0|0000000 00000000 00000000 00000000 00000000 00|00000|1 1001|0000 00000000

or0|0000000 00000000 00000000 00000000 00000000 00|00000|0 0000|‭0000 00000000‬

------------------------------------------------------------------------------------------

  0|0001100 10100010 10111110 10001001 01011100 00|10001|1 1001|‭0000 00000000‬

  //结果：910499571847892992

从位或运算角度简化看是这样的视角

1  |                    41                        |  5  |   5  |     12      

  0|0001100 10100010 10111110 10001001 01011100 00|     |      |      //la

  0|                                              |10001|      |      //lb

  0|                                              |     |1 1001|      //lc

or0|                                              |     |      |‭0000 00000000‬ //seq

------------------------------------------------------------------------------------------

   0|0001100 10100010 10111110 10001001 01011100 00|10001|1 1001|‭0000 00000000‬

   //结果：910499571847892992

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

  • 纵向观察发现:

    • 在41位那一段，除了la一行有值，其它行（lb、lc、seq）都是0
    • 在左起第一个5位那一段，除了lb一行有值，其它行都是0
    • 在左起第二个5位那一段，除了lc一行有值，其它行都是0
    • 按照这规律，如果seq是0以外的其它值，12位那段也会有值的，其它行都是0
  • 横向观察发现:
    • 在la行，由于左移了5+5+12位，5、5、12这三段都补0了，所以la行除了41那段外，其它肯定都是0
    • 同理，lb、lc、seq行也以此类推
    • 正因为左移的操作，使四个不同的值移到了SnowFlake理论上相应的位置，然后四行做位或运算（只要有1结果就是1），就把4段的二进制数合并成一个二进制数。

结论：

所以，在这段代码中左移运算是为了将数值移动到对应的段(41、5、5，12那段因为本来就在最右，因此不用左移)。然后对每个左移后的值(la、lb、lc、seq)做位或运算，是为了把各个短的数据合并起来，合并成一个二进制数。最后转换成10进制，就是最终生成的id。

延伸：long和double底层

问题： java中 long 和double都是64位。为什么double表示的范围大那么多呢？

标准答案是这样子的：

double是n*2^m(n乘以2的m次方)这种形式存储的，只需要记录n和m两个数就行了，m的值影响范围大，所以表示的范围比long大。

但是m越大，n的精度就越小，所以double并不能把它所表示的范围里的所有数都能精确表示出来，而long就可以。

贴上一些整数类型的范围：

1.整型 (一个字节占8位)

类型 存储需求 bit数 取值范围 备注

int 4字节 48 (32) -231~231-1

short 2字节 28 (16) -215~215-1

long 8字节 88 (64) -263~263-1

byte 1字节 18 (8) -27~27-1 = -128~127

2.浮点型

类型 存储需求 bit数 取值范围 备注

float 4字节 48 (32) 3.4028235E38 ~= 3.410^38

double 8字节 88 (64) 1.7976931348623157E308 ~=1.710^308

从范围来看double和long完全不是一个级别的了吧？long最大为=263-1，而double为21024。

Snowflake的优缺点

优点：

  • 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  • 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
  • 可以根据自身业务特性分配bit位，非常灵活。

缺点：

  • 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
  • 我们通过5ms的等待来兼容ntp的同步，如果大于5ms就报错。

服务部署

部署模式支持2种

  1. 部署zookeeper, 配置zk地址，然后启动Spring boot

  2. 也可以把snowflake单独作为包引入项目，独立使用

配置方式

  1. Rest Server的配置在server/src/main/resources/application.properties中:
配置项 含义 默认值
spring.application.name web服务名 default
server.port web服务注册端口
snowflake.zk.address zk地址
  1. 如果只是配置snowflake这个单独的模块，可以参考snowflake/src/test/resources/snowflake.properties中:

    | 配置项 | 含义 | 默认值 |

    | ------------------------- | ----------------------------- | ------ |

    | snowflake.name | snowflake服务名 | default|

    | snowflake.node.port | snowflake服务注册端口 | |

    | snowflake.zk.address | zk地址 | |

远程调用方式

  1. HTTP调用拿一个id：

curl http://localhost:8789/api/snowflake/get

response

{

    "code":0,

    "message":"ok",

    "content":{

        "id":9546332062617603,

        "status":"SUCCESS"

    }

}
  1. HTTP调用解析一个id：

curl http://localhost:8789/api/snowflake/decode?snowflakeId=9546332062617603

response

{

    "code":0,

    "message":"ok",

    "content":{

        "format":"2019-10-27 08:13:42.926, #3, @(0,1)",

        "timestamp":"2019-10-27 08:13:42.926",

        "datacenterId":0,

        "workerId":1,

        "sequenceId":3

    }

}

欢迎关注我的公众号：好奇心森林

  1. https://www.cnblogs.com/fuck1/p/5899402.html ︎

最新文章

  1. 【翻译】《深入解析windows操作系统第6版下册》第10章:内存管理
  2. node.js动态调试
  3. 学习C++——只声明忘记定义了
  4. Linux系统编程（35）—— socket编程之TCP服务器的并发处理
  5. Cognos配置管理
  6. BZOJ 2199: [Usaco2011 Jan]奶牛议会 [2-SAT 判断解]
  7. (Python3) 求中位数 代码
  8. Python开发者年度调研，结果出乎意料！
  9. BSGS&amp;扩展BSGS
  10. nltk——文本分类
  11. tmux常用配置
  12. Windows7安装nginx后，&#39;nginx -t -c nginx.conf&#39; 命令出现 “could not open error log file: CreateFile() &quot;logs/error.log&quot; failed” 错误的原因
  13. Tensorflow中的name_scope和variable_scope
  14. 20155307 2016-2017-2 《Java程序设计》第6周学习总结
  15. GraphQL：一种不同于REST的接口风格
  16. L131
  17. web前端开发的好工具sublime
  18. 金庸的武侠世界和SAP的江湖
  19. z作业二总结
  20. spring data jpa使用原生sql查询

热门文章

  1. java -&gt;Servlet接口
  2. 黑马程序员_毕向东_Java基础视频教程——常量（随笔）
  3. 数学分析新讲(1) NOTE
  4. 仙人掌图判定及求直径HDU3594 BZOJ1023
  5. 《机器学习Python实现_09_02_决策树_CART》
  6. PowerDesigner使用教程（二）
  7. [Unity2d系列教程] 001.引用外部DLL - C#
  8. BUUCTF Crypto_WP(2)
  9. Netty学习笔记（二） - ChannelPipeline和ChannelHandler
  10. ArcCore重构-打通Can各层ID配置