分布式ID ¶
雪花算法 ¶
介绍 ¶
Snowflake 是 Twitter 开源的分布式 ID 生成算法。Snowflake 由 64 bit 的二进制数字组成，这 64bit 的二进制被分成了几部分，每一部分存储的数据都有特定的含义：
- 第 0 位：符号位（标识正负），始终为 0，没有用，不用管。
- 第 1~41 位：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑 2 ^41 毫秒（约 69 年）
- 第 42~52 位：一共 10 位，一般来说，前 5 位表示机房 ID，后 5 位表示机器 ID（实际项目中可以根据实际情况调整）。这样就可以区分不同集群/机房的节点。
- 第 53~64 位：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096),也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID
优点：生成速度比较快、生成的 ID 有序递增、比较灵活（可以对 Snowflake 算法进行简单的改造比如加入业务 ID）
缺点：需要解决重复 ID 问题（依赖时间，当机器时间不对的情况下，可能导致会产生重复 ID）
Java实现 ¶
java
1/**
2 * twitter的snowflake算法 -- java实现
3 * 下面代码每秒理论上可生成id数为：2048000
4 *
5 * @author 总共 64bit位 最大为 9,223,372,036,854,775,807（2^63 -1）
6 */
7public class SnowFlake {
8
9 /**
10 * 起始的时间戳 2020-01-01 00:00:00
11 */
12 private static final long START_TIMESTAMP = 1577808000000L;
13
14 // 预留1 bit 符号位（默认为0）
15
16 /**
17 * 序列号占用的位数 每毫秒可生成2048个序列号
18 */
19 private static final long SEQUENCE_BIT = 11;
20 /**
21 * 机器标识占用的位数 最大32
22 */
23 private static final long MACHINE_BIT = 5;
24 /**
25 * 数据中心占用的位数 最大32
26 */
27 private static final long DATACENTER_BIT = 5;
28 /**
29 * 时间戳占用的位数 139年左右
30 */
31 private static final long TIMESTAMP_BIT = 42;
32
33 /**
34 * 机器id最大为31
35 */
36 private static final long MAX_MACHINE = ~(-1L << MACHINE_BIT);
37
38 /**
39 * 数据中心id最大为31
40 */
41 private static final long MAX_DATACENTER = ~(-1L << DATACENTER_BIT);
42
43 /**
44 * 序列最大大小
45 */
46 private static final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
47
48 /**
49 * 每一部分向左的位移
50 */
51 private static final long MACHINE_LEFT = SEQUENCE_BIT;
52 private static final long DATACENTER_LEFT = MACHINE_LEFT + MACHINE_BIT;
53 private static final long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
54
55 /**
56 * 序列号
57 */
58 private long sequence = 1L;
59
60 /**
61 * 上一次时间戳
62 */
63 private long lastTimestamp = -1L;
64
65 /**
66 * 机器id
67 */
68 private long machineId = 1L;
69
70 /**
71 * 数据中心id
72 */
73 private long datacenterId = 1L;
74
75
76 public SnowFlake(long machineId, long datacenterId) {
77 if (machineId > MAX_MACHINE) {
78 throw new AppException("机器id最大为31");
79 }
80 if (datacenterId > MAX_DATACENTER) {
81 throw new AppException("数据中心id最大为31");
82 }
83 this.machineId = machineId;
84 this.datacenterId = datacenterId;
85 }
86
87 /**
88 * 产生一下个id
89 *
90 * @return long
91 */
92 public synchronized long nextId() {
93 long currTimestamp = getNewTimestamp();
94 if (currTimestamp < lastTimestamp) {
95 throw new AppException("Clock moved backwards. Refusing to generate id");
96 }
97 // 相同毫秒内，序列号自增
98 if (currTimestamp == lastTimestamp) {
99 sequence = (sequence + 1) & MAX_SEQUENCE;
100 // 同一毫秒的序列数已经达到最大，等待到下一毫秒
101 if (sequence == 0L) {
102 currTimestamp = getNextMill();
103 }
104 } else {
105 // 不同毫秒 序列置为 0
106 sequence = 1L;
107 }
108 lastTimestamp = currTimestamp;
109 // 这里隐藏了首位 0L
110 return (currTimestamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
111 | datacenterId << DATACENTER_LEFT //数据中心部分
112 | machineId << MACHINE_LEFT //机器标识部分
113 | sequence; //序列号部分
114 }
115
116 private long getNextMill() {
117 long mill = getNewTimestamp();
118 while (mill <= lastTimestamp) {
119 mill = getNewTimestamp();
120 }
121 return mill;
122 }
123
124 private long getNewTimestamp() {
125 return System.currentTimeMillis();
126 }
127
128
129 public static final SnowFlake SNOW_FLAKE = new SnowFlake(1L, 1L);
130
131 public static long getSeq() {
132 return SNOW_FLAKE.nextId();
133 }
134
135 public static void main(String[] args) {
136 long start = System.currentTimeMillis();
137 List<Long> arr = Collections.synchronizedList(new ArrayList<>(100000));
138 new Thread(() -> {
139 while (System.currentTimeMillis() - start < 1000) {
140 arr.add(getSeq());
141 }
142 }).start();
143 new Thread(() -> {
144 while (System.currentTimeMillis() - start < 1000) {
145 arr.add(getSeq());
146 }
147 }).start();
148 try {
149 TimeUnit.SECONDS.sleep(1);
150 } catch (InterruptedException e) {
151 e.printStackTrace();
152 }
153 System.out.println(String.format("耗时：%sms,生成id数量：%s", System.currentTimeMillis() - start, arr.size()));
154
155
156 }
157}UUID ¶
介绍 ¶
UUID 是 Universally Unique Identifier（通用唯一标识符） 的缩写。UUID 包含 32 个 16 进制数字（8-4-4-4-12）
优点：生成速度比较快、简单易用
缺点：存储消耗空间大（32 个字符串，128 位）、 不安全（基于 MAC 地址生成 UUID 的算法会造成 MAC 地址泄露)、无序（非自增）、没有具体业务含义、需要解决重复 ID 问题（当机器时间不对的情况下，可能导致会产生重复 ID）
Java代码 ¶
java
1public class UUIDUtil {
2 public static void main(String[] args) {
3 UUID randomUUID = UUID.randomUUID();
4 // 示例：c1c74128-0fc4-454b-b4bc-248d945d25a9
5 String toString = randomUUID.toString();
6 }
7}