Skip to content
雪花算法学习笔记
Java
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.idea
src/com/lzhpo
.gitignore
README.md
SnowFlake-Java.iml
UUID源码.md

README.md

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
You can’t perform that action at this time.