SnowFlake 算法实现

x33g5p2x  于2022-03-18 转载在 其他  
字(3.9k)|赞(0)|评价(0)|浏览(294)

一 背景

在分布式系统中,如何在各个不同的服务器产生 ID 值?例如,有一个订单系统部署在 A、B 两个节点上,那么如何在这两个节点上产生各自的订单 ID,并且保证 ID 值不会冲突。

通常有三种解决方案。

  • 使用数据库的自增特性(或 Oracle 中的序列),不同节点直接使用相同数据库的自增 ID 值
  • 使用 UUID 算法产生 ID 值
  • 使用雪花算法生成 ID 值

二 雪花算法

1 说明

SnowFlake 被称为雪花算法,它是分布式 ID 生成器。

雪花算法是由 Twitter 公布的分布式主键生成算法,它能够保证不同表的主键的不重复性,以及相同表的主键的有序性。

核心思想:

长度共 64bit(一个 long 型)。

首先是一个符号位,1 bit 标识,由于 long 基本类型在Java中是带符号的,最高位是符号位,正数是 0,负数是 1,所以 id 一般是正数,最高位是 0。

41 bit 时间截(毫秒级),存储的是时间截的差值(当前时间截 - 开始时间截),结果约等于69.73年。

10 bit 作为机器的ID(5个bit是数据中心,5个bit的机器ID,可以部署在1024个节点)。

12 bit作为毫秒内的流水号(意味着每个节点在每毫秒可以产生 4096 个 ID)。

2 优点

  • 毫秒数在高位,自增序列在低位,整个 ID 都是趋势递增的。整体上按照时间自增排序,并且整个分布式系统内不会产生 ID 碰撞,并且效率较高。
  • 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成 ID 的性能也是非常高的。可以根据自身业务特性分配 bit 位,非常灵活。

3 缺点

  • 依赖机器时钟,如果机器时钟回拨,会导致重复 ID 生成。
  • 可能在单机上是递增的,但是由于涉及到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况(此缺点可以忽略,,一般分布式 ID 只要求趋势递增,并不会严格要求递增,90% 的需求都只要求趋势递增 )。

4 思想

当多个节点需要生成多个 ID 值时,先判断这些节点是否在同一个时刻(精确到 ms )生成的 ID。如果不是,可以直接根据 41 位时间戳区分 ID 值;如果是在同一时刻生成的,再根据“ 10 位机器码和12 位流水号”区分。

三 源码

1 代码

  1. package snowflake;
  2. // 本例将 10 位机器码看成是5位 datacenterId 和 5位 workerId
  3. public class SnowFlake {
  4. private long workerId;
  5. private long datacenterId;
  6. // 每毫秒生产的序列号之从0开始递增;
  7. private long sequence = 0L;
  8. /*
  9. 1288834974657L是1970-01-01 00:00:00到2010年11月04日01:42:54所经过的毫秒数;
  10. 因为现在二十一世纪的某一时刻减去1288834974657L的值,正好在2^41内。
  11. 因此1288834974657L实际上就是为了让时间戳正好在2^41内而凑出来的。
  12. 简言之,1288834974657L(即1970-01-01 00:00:00),就是在计算时间戳时用到的“起始时间”。
  13. */
  14. private long twepoch = 1288834974657L;
  15. private long workerIdBits = 5L;
  16. private long datacenterIdBits = 5L;
  17. private long maxWorkerId = -1L ^ (-1L << workerIdBits);
  18. private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
  19. private long sequenceBits = 12L;
  20. private long workerIdShift = sequenceBits;
  21. private long datacenterIdShift = sequenceBits + workerIdBits;
  22. private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
  23. private long sequenceMask = -1L ^ (-1L << sequenceBits);
  24. private long lastTimestamp = -1L;
  25. public SnowFlake(long datacenterId, long workerId) {
  26. if ((datacenterId > maxDatacenterId || datacenterId < 0)
  27. || (workerId > maxWorkerId || workerId < 0)) {
  28. throw new IllegalArgumentException("datacenterId/workerId值非法");
  29. }
  30. this.datacenterId = datacenterId;
  31. this.workerId = workerId;
  32. }
  33. // 通过 SnowFlake 生成 id 的核心算法
  34. public synchronized long nextId() {
  35. // 获取计算 id 时刻的时间戳
  36. long timestamp = System.currentTimeMillis();
  37. if (timestamp < lastTimestamp) {
  38. throw new RuntimeException("时间戳值非法");
  39. }
  40. // 如果此次生成 id 的时间戳,与上次的时间戳相同,就通过机器码和序列号区分id值(机器码已通过构造方法传入)
  41. if (lastTimestamp == timestamp) {
  42. /*
  43. 下一条语句的作用是:通过位运算保证sequence不会超出序列号所能容纳的最大值。
  44. 例如,本程序产生的12位sequence值依次是:1、2、3、4、...、4094、4095
  45. (4095是2的12次方的最大值,也是本sequence的最大值)
  46. 那么此时如果再增加一个sequence值(即sequence + 1),下条语句就会
  47. 使sequence恢复到0。
  48. 即如果sequence==0,就表示sequence已满。
  49. */
  50. sequence = (sequence + 1) & sequenceMask;
  51. // 如果 sequence 已满,就无法再通过sequence区分id值;因此需要切换到下一个时间戳重新计算。
  52. if (sequence == 0) {
  53. timestamp = tilNextMillis(lastTimestamp);
  54. }
  55. } else {
  56. // 如果此次生成 id 的时间戳,与上次的时间戳不同,就已经可以根据时间戳区分id值
  57. sequence = 0L;
  58. }
  59. // 更新最近一次生成id的时间戳
  60. lastTimestamp = timestamp;
  61. /*
  62. 假设此刻的值是(二进制表示):
  63. 41位时间戳的值是:00101011110101011101011101010101111101011
  64. 5位datacenterId(机器码的前5位)的值是:01101
  65. 5位workerId(机器码的后5位)的值是:11001
  66. sequence的值是:01001
  67. 那么最终生成的id值,就需要:
  68. 1.将41位时间戳左移动22位(即移动到snowflake值中时间戳应该出现的位置);
  69. 2.将5位datacenterId向左移动17位,并将5位workerId向左移动12位
  70. (即移动到snowflake值中机器码应该出现的位置);
  71. 3.sequence本来就在最低位,因此不需要移动。
  72. 以下<<和|运算,实际就是将时间戳、机器码和序列号移动到snowflake中相应的位置。
  73. */
  74. return ((timestamp - twepoch) << timestampLeftShift)
  75. | (datacenterId << datacenterIdShift) | (workerId << workerIdShift)
  76. | sequence;
  77. }
  78. protected long tilNextMillis(long lastTimestamp) {
  79. long timestamp = System.currentTimeMillis();
  80. /*
  81. 如果当前时刻的时间戳<=上一次生成id的时间戳,就重新生成当前时间。
  82. 即确保当前时刻的时间戳,与上一次的时间戳不会重复。
  83. */
  84. while (timestamp <= lastTimestamp) {
  85. timestamp = System.currentTimeMillis();
  86. }
  87. return timestamp;
  88. }
  89. }

2 测试代码

  1. package snowflake;
  2. public class TestSnowFlake {
  3. // 测试1秒能够生成的 id 个数
  4. public static void generateIdsInOneSecond() {
  5. SnowFlake idWorker = new SnowFlake(1, 1);
  6. long start = System.currentTimeMillis();
  7. int i = 0;
  8. for (; System.currentTimeMillis() - start < 1000; i++) {
  9. idWorker.nextId();
  10. }
  11. long end = System.currentTimeMillis();
  12. System.out.println("耗时:" + (end - start));
  13. System.out.println("生成id个数:" + i);
  14. }
  15. public static void main(String[] args) {
  16. generateIdsInOneSecond();
  17. }
  18. }

3 测试结果

  1. 耗时:1000
  2. 生成id个数:4078490

相关文章