原创

Java实现雪花算法

Java实现雪花算法

源代码和笔记参考我的GitHub:https://github.com/lzhpo/Snowflake-Java

什么是雪花算法SnowFlake?

SnowFlake算法是Twitter设计的一个可以在分布式系统中生成唯一的ID的算法,它可以满足Twitter每秒上万条消息ID分配的请求,这些消息ID是唯一的且有大致的递增顺序。

雪花算法SnowFlake和UUID的区别?

解析UUID

UUID是什么?

  • UUID是通用唯一识别码(Universally Unique Identifier)的缩写,开放软件基金会(OSF)规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素。利用这些元素来生成UUID。
  • UUID是由128位二进制组成,一般转换成十六进制,然后用String表示。
  • 在java中有个UUID类,有四种不同的UUID的生成策略。

四种不同的UUID的生成策略?

  1. randomly: 基于随机数生成UUID,由于Java中的随机数是伪随机数,其重复的概率是可以被计算出来的。
  2. time-based:基于时间的UUID,这个一般是通过当前时间,随机数,和本地Mac地址来计算出来,自带的JDK包并没有这个算法的我们在一些UUIDUtil中,比如我们的log4j.core.util,会重新定义UUID的高位和低位。
  3. DCE security:DCE安全的UUID。
  4. name-based:基于名字的UUID,通过计算名字和名字空间的MD5来计算UUID。

UUID的优缺点?

优点
  1. 通过本地生成,没有经过网络I/O,性能较快。
  2. 无序,无法预测他的生成顺序。(当然这个也是他的缺点之一)
缺点
  1. 128位二进制一般转换成36位的16进制,太长了只能用String存储,空间占用较多。
  2. 不能生成递增有序的数字。

UUID的使用场景?

UUID的适用场景可以为不需要担心过多的空间占用,以及不需要生成有递增趋势的数字。在Log4j里面他在UuidPatternConverter中加入了UUID来标识每一条日志。

雪花算法SnowFlake比UUID好在哪?

雪花算法可以生成递增有序的数字,而UUID不能。

雪花算法实现原理?

SnowFlake算法产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔):
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1位标识部分:在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以为0;

41位时间戳部分:这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L 60 60 24 365) = 69年。

10位节点部分:Twitter实现中使用前5位作为数据中心标识,后5位作为机器标识,可以部署1024个节点。

12位序列号部分:支持同一毫秒内同一个节点可以生成4096个ID。

SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的。或许我们不一定都需要像上面那样使用5位作为数据中心标识,5位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部10位作为机器标识;若数据中心不多,也可以只使用3位作为数据中心,7位作为机器标识。

实现雪花算法snowflake

参见我的GitHub源代码:https://github.com/lzhpo/Snowflake-Java/blob/master/src/com/lzhpo/snowflake/SnowFlake.java

使用雪花算法注意事项

SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的。

左移、右移运算符

左移位运算符<<

将一个运算对象的各二进制位全部左移若干位(左边的二进制丢弃,右边补0)。

注意:java中 整数位 32位。

小技巧:
对于正数来说,左移相当于乘以2(但效率比乘法高)。

例如:1向左移12位,就相当于1乘以2的12次方。结果为4096。

System.out.println(1 << 12);  //4096
System.out.println(Math.pow(2, 12));  //4096

右移运算符>>

将一个运算对象的各二进制位全部右移若干位,正数左补0,负数左补1。

小技巧:
对于正数来说,右1移相当于除以2(但效率比除法高)。

例如:4向右移2位,就相当于4除以2的2次方。结果为1。

System.out.println(4 >> 2);  //1
System.out.println(4 / Math.pow(2, 2));  //1
正文到此结束