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的生成策略？
- randomly: 基于随机数生成UUID，由于Java中的随机数是伪随机数，其重复的概率是可以被计算出来的。
- time-based:基于时间的UUID,这个一般是通过当前时间，随机数，和本地Mac地址来计算出来，自带的JDK包并没有这个算法的我们在一些UUIDUtil中，比如我们的log4j.core.util，会重新定义UUID的高位和低位。
- DCE security:DCE安全的UUID。
- name-based：基于名字的UUID，通过计算名字和名字空间的MD5来计算UUID。
UUID的优缺点？
优点
- 通过本地生成，没有经过网络I/O，性能较快。
- 无序，无法预测他的生成顺序。(当然这个也是他的缺点之一)
缺点
- 128位二进制一般转换成36位的16进制，太长了只能用String存储，空间占用较多。
- 不能生成递增有序的数字。
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
- 本文标签： Java 数据结构与算法
- 本文链接： http://www.lzhpo.com/article/19
- 版权声明： 本文由lzhpo原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
热门推荐
相关文章
关于我
