-
Notifications
You must be signed in to change notification settings - Fork 683
/
Copy pathSnowFlake 雪花算法生成分布式 ID.md.html
896 lines (799 loc) · 44.2 KB
/
SnowFlake 雪花算法生成分布式 ID.md.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>SnowFlake 雪花算法生成分布式 ID.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/文章/AQS 万字图文全面解析.md.html">AQS 万字图文全面解析.md.html</a>
</li>
<li>
<a href="/文章/Docker 镜像构建原理及源码分析.md.html">Docker 镜像构建原理及源码分析.md.html</a>
</li>
<li>
<a href="/文章/ElasticSearch 小白从入门到精通.md.html">ElasticSearch 小白从入门到精通.md.html</a>
</li>
<li>
<a href="/文章/JVM CPU Profiler技术原理及源码深度解析.md.html">JVM CPU Profiler技术原理及源码深度解析.md.html</a>
</li>
<li>
<a href="/文章/JVM 垃圾收集器.md.html">JVM 垃圾收集器.md.html</a>
</li>
<li>
<a href="/文章/JVM 面试的 30 个知识点.md.html">JVM 面试的 30 个知识点.md.html</a>
</li>
<li>
<a href="/文章/Java IO 体系、线程模型大总结.md.html">Java IO 体系、线程模型大总结.md.html</a>
</li>
<li>
<a href="/文章/Java NIO浅析.md.html">Java NIO浅析.md.html</a>
</li>
<li>
<a href="/文章/Java 面试题集锦（网络篇）.md.html">Java 面试题集锦（网络篇）.md.html</a>
</li>
<li>
<a href="/文章/Java-直接内存 DirectMemory 详解.md.html">Java-直接内存 DirectMemory 详解.md.html</a>
</li>
<li>
<a href="/文章/Java中9种常见的CMS GC问题分析与解决（上）.md.html">Java中9种常见的CMS GC问题分析与解决（上）.md.html</a>
</li>
<li>
<a href="/文章/Java中9种常见的CMS GC问题分析与解决（下）.md.html">Java中9种常见的CMS GC问题分析与解决（下）.md.html</a>
</li>
<li>
<a href="/文章/Java中的SPI.md.html">Java中的SPI.md.html</a>
</li>
<li>
<a href="/文章/Java中的ThreadLocal.md.html">Java中的ThreadLocal.md.html</a>
</li>
<li>
<a href="/文章/Java线程池实现原理及其在美团业务中的实践.md.html">Java线程池实现原理及其在美团业务中的实践.md.html</a>
</li>
<li>
<a href="/文章/Java魔法类：Unsafe应用解析.md.html">Java魔法类：Unsafe应用解析.md.html</a>
</li>
<li>
<a href="/文章/Kafka 源码阅读笔记.md.html">Kafka 源码阅读笔记.md.html</a>
</li>
<li>
<a href="/文章/Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别以及高可用原理.md.html">Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别以及高可用原理.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB Buffer Pool.md.html">MySQL · 引擎特性 · InnoDB Buffer Pool.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB IO子系统.md.html">MySQL · 引擎特性 · InnoDB IO子系统.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 事务系统.md.html">MySQL · 引擎特性 · InnoDB 事务系统.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 同步机制.md.html">MySQL · 引擎特性 · InnoDB 同步机制.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 数据页解析.md.html">MySQL · 引擎特性 · InnoDB 数据页解析.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB崩溃恢复.md.html">MySQL · 引擎特性 · InnoDB崩溃恢复.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · 临时表那些事儿.md.html">MySQL · 引擎特性 · 临时表那些事儿.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制 半同步复制.md.html">MySQL 主从复制 半同步复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制 基于GTID复制.md.html">MySQL 主从复制 基于GTID复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制.md.html">MySQL 主从复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 事务日志(redo log和undo log).md.html">MySQL 事务日志(redo log和undo log).md.html</a>
</li>
<li>
<a href="/文章/MySQL 亿级别数据迁移实战代码分享.md.html">MySQL 亿级别数据迁移实战代码分享.md.html</a>
</li>
<li>
<a href="/文章/MySQL 从一条数据说起-InnoDB行存储数据结构.md.html">MySQL 从一条数据说起-InnoDB行存储数据结构.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：事务和锁的面纱.md.html">MySQL 地基基础：事务和锁的面纱.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：数据字典.md.html">MySQL 地基基础：数据字典.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：数据库字符集.md.html">MySQL 地基基础：数据库字符集.md.html</a>
</li>
<li>
<a href="/文章/MySQL 性能优化：碎片整理.md.html">MySQL 性能优化：碎片整理.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：一个 ALTER TALBE 执行了很久，你慌不慌？.md.html">MySQL 故障诊断：一个 ALTER TALBE 执行了很久，你慌不慌？.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：如何在日志中轻松定位大事务.md.html">MySQL 故障诊断：如何在日志中轻松定位大事务.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：教你快速定位加锁的 SQL.md.html">MySQL 故障诊断：教你快速定位加锁的 SQL.md.html</a>
</li>
<li>
<a href="/文章/MySQL 日志详解.md.html">MySQL 日志详解.md.html</a>
</li>
<li>
<a href="/文章/MySQL 的半同步是什么？.md.html">MySQL 的半同步是什么？.md.html</a>
</li>
<li>
<a href="/文章/MySQL中的事务和MVCC.md.html">MySQL中的事务和MVCC.md.html</a>
</li>
<li>
<a href="/文章/MySQL事务_事务隔离级别详解.md.html">MySQL事务_事务隔离级别详解.md.html</a>
</li>
<li>
<a href="/文章/MySQL优化：优化 select count().md.html">MySQL优化：优化 select count().md.html</a>
</li>
<li>
<a href="/文章/MySQL共享锁、排他锁、悲观锁、乐观锁.md.html">MySQL共享锁、排他锁、悲观锁、乐观锁.md.html</a>
</li>
<li>
<a href="/文章/MySQL的MVCC（多版本并发控制）.md.html">MySQL的MVCC（多版本并发控制）.md.html</a>
</li>
<li>
<a href="/文章/QingStor 对象存储架构设计及最佳实践.md.html">QingStor 对象存储架构设计及最佳实践.md.html</a>
</li>
<li>
<a href="/文章/RocketMQ 面试题集锦.md.html">RocketMQ 面试题集锦.md.html</a>
</li>
<li>
<a class="current-tab" href="/文章/SnowFlake 雪花算法生成分布式 ID.md.html">SnowFlake 雪花算法生成分布式 ID.md.html</a>
</li>
<li>
<a href="/文章/Spring Boot 2.x 结合 k8s 实现分布式微服务架构.md.html">Spring Boot 2.x 结合 k8s 实现分布式微服务架构.md.html</a>
</li>
<li>
<a href="/文章/Spring Boot 教程：如何开发一个 starter.md.html">Spring Boot 教程：如何开发一个 starter.md.html</a>
</li>
<li>
<a href="/文章/Spring MVC 原理.md.html">Spring MVC 原理.md.html</a>
</li>
<li>
<a href="/文章/Spring MyBatis和Spring整合的奥秘.md.html">Spring MyBatis和Spring整合的奥秘.md.html</a>
</li>
<li>
<a href="/文章/Spring 帮助你更好的理解Spring循环依赖.md.html">Spring 帮助你更好的理解Spring循环依赖.md.html</a>
</li>
<li>
<a href="/文章/Spring 循环依赖及解决方式.md.html">Spring 循环依赖及解决方式.md.html</a>
</li>
<li>
<a href="/文章/Spring中眼花缭乱的BeanDefinition.md.html">Spring中眼花缭乱的BeanDefinition.md.html</a>
</li>
<li>
<a href="/文章/Vert.x 基础入门.md.html">Vert.x 基础入门.md.html</a>
</li>
<li>
<a href="/文章/eBay 的 Elasticsearch 性能调优实践.md.html">eBay 的 Elasticsearch 性能调优实践.md.html</a>
</li>
<li>
<a href="/文章/不可不说的Java“锁”事.md.html">不可不说的Java“锁”事.md.html</a>
</li>
<li>
<a href="/文章/互联网并发限流实战.md.html">互联网并发限流实战.md.html</a>
</li>
<li>
<a href="/文章/从ReentrantLock的实现看AQS的原理及应用.md.html">从ReentrantLock的实现看AQS的原理及应用.md.html</a>
</li>
<li>
<a href="/文章/从SpringCloud开始，聊微服务架构.md.html">从SpringCloud开始，聊微服务架构.md.html</a>
</li>
<li>
<a href="/文章/全面了解 JDK 线程池实现原理.md.html">全面了解 JDK 线程池实现原理.md.html</a>
</li>
<li>
<a href="/文章/分布式一致性理论与算法.md.html">分布式一致性理论与算法.md.html</a>
</li>
<li>
<a href="/文章/分布式一致性算法 Raft.md.html">分布式一致性算法 Raft.md.html</a>
</li>
<li>
<a href="/文章/分布式唯一 ID 解析.md.html">分布式唯一 ID 解析.md.html</a>
</li>
<li>
<a href="/文章/分布式链路追踪：集群管理设计.md.html">分布式链路追踪：集群管理设计.md.html</a>
</li>
<li>
<a href="/文章/动态代理种类及原理，你知道多少？.md.html">动态代理种类及原理，你知道多少？.md.html</a>
</li>
<li>
<a href="/文章/响应式架构与 RxJava 在有赞零售的实践.md.html">响应式架构与 RxJava 在有赞零售的实践.md.html</a>
</li>
<li>
<a href="/文章/大数据算法——布隆过滤器.md.html">大数据算法——布隆过滤器.md.html</a>
</li>
<li>
<a href="/文章/如何优雅地记录操作日志？.md.html">如何优雅地记录操作日志？.md.html</a>
</li>
<li>
<a href="/文章/如何设计一个亿级消息量的 IM 系统.md.html">如何设计一个亿级消息量的 IM 系统.md.html</a>
</li>
<li>
<a href="/文章/异步网络模型.md.html">异步网络模型.md.html</a>
</li>
<li>
<a href="/文章/当我们在讨论CQRS时，我们在讨论些神马？.md.html">当我们在讨论CQRS时，我们在讨论些神马？.md.html</a>
</li>
<li>
<a href="/文章/彻底理解 MySQL 的索引机制.md.html">彻底理解 MySQL 的索引机制.md.html</a>
</li>
<li>
<a href="/文章/最全的 116 道 Redis 面试题解答.md.html">最全的 116 道 Redis 面试题解答.md.html</a>
</li>
<li>
<a href="/文章/有赞权限系统(SAM).md.html">有赞权限系统(SAM).md.html</a>
</li>
<li>
<a href="/文章/有赞零售中台建设方法的探索与实践.md.html">有赞零售中台建设方法的探索与实践.md.html</a>
</li>
<li>
<a href="/文章/服务注册与发现原理剖析（Eureka、Zookeeper、Nacos）.md.html">服务注册与发现原理剖析（Eureka、Zookeeper、Nacos）.md.html</a>
</li>
<li>
<a href="/文章/深入浅出Cache.md.html">深入浅出Cache.md.html</a>
</li>
<li>
<a href="/文章/深入理解 MySQL 底层实现.md.html">深入理解 MySQL 底层实现.md.html</a>
</li>
<li>
<a href="/文章/漫画讲解 git rebase VS git merge.md.html">漫画讲解 git rebase VS git merge.md.html</a>
</li>
<li>
<a href="/文章/生成浏览器唯一稳定 ID 的探索.md.html">生成浏览器唯一稳定 ID 的探索.md.html</a>
</li>
<li>
<a href="/文章/缓存 如何保证缓存与数据库的双写一致性？.md.html">缓存 如何保证缓存与数据库的双写一致性？.md.html</a>
</li>
<li>
<a href="/文章/网易严选怎么做全链路监控的？.md.html">网易严选怎么做全链路监控的？.md.html</a>
</li>
<li>
<a href="/文章/美团万亿级 KV 存储架构与实践.md.html">美团万亿级 KV 存储架构与实践.md.html</a>
</li>
<li>
<a href="/文章/美团点评Kubernetes集群管理实践.md.html">美团点评Kubernetes集群管理实践.md.html</a>
</li>
<li>
<a href="/文章/美团百亿规模API网关服务Shepherd的设计与实现.md.html">美团百亿规模API网关服务Shepherd的设计与实现.md.html</a>
</li>
<li>
<a href="/文章/解读《阿里巴巴 Java 开发手册》背后的思考.md.html">解读《阿里巴巴 Java 开发手册》背后的思考.md.html</a>
</li>
<li>
<a href="/文章/认识 MySQL 和 Redis 的数据一致性问题.md.html">认识 MySQL 和 Redis 的数据一致性问题.md.html</a>
</li>
<li>
<a href="/文章/进阶：Dockerfile 高阶使用指南及镜像优化.md.html">进阶：Dockerfile 高阶使用指南及镜像优化.md.html</a>
</li>
<li>
<a href="/文章/铁总在用的高性能分布式缓存计算框架 Geode.md.html">铁总在用的高性能分布式缓存计算框架 Geode.md.html</a>
</li>
<li>
<a href="/文章/阿里云PolarDB及其共享存储PolarFS技术实现分析（上）.md.html">阿里云PolarDB及其共享存储PolarFS技术实现分析（上）.md.html</a>
</li>
<li>
<a href="/文章/阿里云PolarDB及其共享存储PolarFS技术实现分析（下）.md.html">阿里云PolarDB及其共享存储PolarFS技术实现分析（下）.md.html</a>
</li>
<li>
<a href="/文章/面试最常被问的 Java 后端题.md.html">面试最常被问的 Java 后端题.md.html</a>
</li>
<li>
<a href="/文章/领域驱动设计在互联网业务开发中的实践.md.html">领域驱动设计在互联网业务开发中的实践.md.html</a>
</li>
<li>
<a href="/文章/领域驱动设计的菱形对称架构.md.html">领域驱动设计的菱形对称架构.md.html</a>
</li>
<li>
<a href="/文章/高效构建 Docker 镜像的最佳实践.md.html">高效构建 Docker 镜像的最佳实践.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>SnowFlake 雪花算法生成分布式 ID</h1>
<h3>SnowFlake 雪花算法基本概念</h3>
<p>SnowFlake 雪花算法是 Twitter 开源的分布式唯一 ID 生成算法，其具有简洁、高性能、低延迟、ID 按时间趋势有序等特点。如采用 12 位序列号，则理论支持每毫秒生成 4096 个不同数字，能够满足绝大多数高并发场景下的互联网应用。SnowFlake 雪花算法能保证在 datacenterId 和 workerId 唯一的情况下不会生成重复值。如果单位毫秒并发量 >4096，将会等到下一毫秒继续生成 ID。因此如果单台服务器并发量大于 4096/ms，是时候考虑自研算法了。</p>
<p>SnowFlake 的结构如下：</p>
<p><img src="assets/50ba2570-e86c-11ea-8115-8d7d715b7847" alt="在这里插入图片描述" /></p>
<pre><code>0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
</code></pre>
<p>总共 64 个 bit 位，对应于 Java 基本数据类型的 Long 类型 1 位符号位，正数是 0，负数是 1，id 一般是正数，因此最高位是 0 41 位时间戳（毫秒级），41 位时间戳不是存储当前时间的时间戳，而是存储时间戳差值（当前时间戳 - 开始时间戳）。开始时间戳一般是 Id 生成器开始投入使用的时间，可在程序中指定。</p>
<ul>
<li>41 位时间戳，可以使用 69 年，年数 = (1L << 41) / (1000L * 60 * 60 * 24 * 365) ≈ 69</li>
<li>10 位机器位，可以部署 1024 个节点，包括 5 位 datacenterId 和 5 位 workerId</li>
<li>12 位序列号，毫秒内计数，支持每个节点每毫秒产生 4096 个不重复 ID 序号</li>
</ul>
<h3>基于原版算法的改进</h3>
<h4>增加毫秒内初始 id 随机生成</h4>
<p>毫秒内初始 id 随机生成可以有效避免逆向工程导致 id 的可推测性。具体开发时通过可配置参数决定是否启用单位毫秒内随机生成起始 ID。随机生成的起始 ID 可能很大，会很快到达单位毫秒内的最大值，比如 4095（12 位序列号情况下），所以需要对 4095 处理，比如取模、或者和二进制位数&运算 循环使用单位毫秒内的可用数字，避免浪费。</p>
<h4>增加 workerId、datacenterId 自动生成</h4>
<p>为了能够简单快捷地使用 SnowFlake 算法，可以基于 mac\hostip\jvmid 等信息自动生成 workerId、datacenterId，尽最大可能不重复。要完全保证 workerId、datacenterId 的唯一性还得借助第三方工具，比如 Redis、ZooKeeper 等开源中间件。</p>
<p>在单个数据中心机器数远 <32 台、数据中心数远 <32 个时，使用本文介绍的方法在不同机器上生成完全相同的 workerId、datacenterId 的概率极低。</p>
<p>具体开发时也保留原生接口，让使用者（比如业务系统）传入自行生成的 workerId、datacenterId ，调用方可以借助 Redis、ZK 等第三方中间件自行保证机器号和数据中心号唯一。</p>
<h4>时钟回拨处理</h4>
<p><strong>运行时</strong></p>
<p>若偏差在指定时间（可配置）以内，则等待 2 倍的时间差后开始生成；若两者偏差大于某个设定的时间阈值（可配置），则立即抛出异常，避免阻塞。</p>
<p><strong>系统重启时</strong></p>
<p>jvmId 变化，基于 mac\hostip\jvmid 生成的机器 WorkerId 变化，即使在时钟回拨时也可以尽最大可能避免生成重复 id。</p>
<p>当然也可以借助第三方中间件实现时间回拨处理，比如算法运行时将 lastTimestamp 写入 redis，系统启动时读取 redis 存储的 lastTimestamp 值和当前时间比较。若当前时间戳 <lastTimestamp，则启动失败。</p>
<h4>字符串位数补齐</h4>
<p>正数的 Long 类型转换为 10 进制数范围：0~9,223,372,036,854,775,807，可见长度为最多 19 位，因此 SnowFlake 算法生成的 id 位数统一设定为 19 位为宜。</p>
<p>一般刚开始使用时为 18 位，但时间距离起始时间超过一定值后，会变为 19 位。</p>
<p>消耗完 18 位所需的时间：1*10^18 / (3600 * 24 * 365 * 1000 * 2^22) ≈ 7.56 年，即时间差超过 7.56 年，就会达到 19 位。</p>
<p>因此我们设置初始时间 < 当前时间 - 7.56 年，保证雪花算法生成的 id 位数统一为 19 位。</p>
<h3>接口设计</h3>
<h4>原始算法接口</h4>
<p>使用者可以传入自行生成的 workerId、datacenterId，原汁原味的 SnowFlake。</p>
<h4>自动生成 workerId、datacenterId 接口</h4>
<p>简化 SnowFlake 的使用，不保证 100%不重复，尽最大概率不重复。</p>
<h4>业务定制接口</h4>
<p>调整雪花算法的 bit 位，即可以根据业务对 64 个 bit 位作出调整。</p>
<p>有的场景下我们需要定制雪花算法，比如生成 15 位的 10 进制数字。</p>
<p>生成 15 位十进制数字需要 53 位二进制数，除了 41 位时间戳 + 1 位符号位之外，还有 11 位可以用，可以采用 2 + 3 + 6（datacenterId + workerId + seqId）。</p>
<p>15 位的场景下理论支持单位毫秒 64 笔，每秒 64000 笔不重复，从中小规模业务量来看， tps>64000 的性能瓶颈短期不大可能出现。</p>
<h4>订单号生成</h4>
<p>业务系统使用基于 snowflake 的 ID 生成器，比如拼接一些业务字段，比如生成订单号时传入 pid\appId\时间戳等。</p>
<h3>算法实现</h3>
<p>本文提供 Java 版的算法实现，欢迎评论区留言批评指正。</p>
<pre><code>import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;
import java.util.Date;
import java.util.concurrent.ThreadLocalRandom;
/**
* @author NiaoGe
* <p>
* 雪花算法生成唯一 id,参考开源项目：
* https://gitee.com/yu120/sequence
* https://apidoc.gitee.com/loolly/hutool/cn/hutool/core/util/IdUtil.html
* </p>
*/
public class IdGenerator {
private static final Logger logger = LoggerFactory.getLogger(IdGenerator.class);
//工作机器 id
private long workerId;
//数据中心 id
private long datacenterId;
//序列号
private long sequence = 0L;
//基准时间，一般取系统的最近时间（一旦确定不能变动）
private long twepoch;
private long workerIdBits;
private long datacenterIdBits;
private long maxWorkerId;
private long maxDatacenterId;
//毫秒内自增位数
private long sequenceBits;
//位与运算保证毫秒内 Id 范围
private long sequenceMask;
//工作机器 id 需要左移的位数
private long workerIdShift;
//数据中心 id 需要左移位数
private long datacenterIdShift;
//时间戳需要左移位数
private long timestampLeftShift;
//上次生成 id 的时间戳，初始值为负数
private long lastTimestamp = -1L;
//true 表示毫秒内初始序列采用随机值
private boolean randomSequence;
//随机初始序列计数器
private long count = 0L;
//允许时钟回拨的毫秒数
private long timeOffset;
private final ThreadLocalRandom tlr = ThreadLocalRandom.current();
/**
* 无参构造器，自动生成 workerId/datacenterId
*/
public IdGenerator() {
this(false, 10, null, 5L, 5L, 12L);
}
/**
* 有参构造器,调用者自行保证数据中心 ID+机器 ID 的唯一性
* 标准 snowflake 实现
*
* @param workerId 工作机器 ID
* @param datacenterId 数据中心 ID
*/
public IdGenerator(long workerId, long datacenterId) {
this(workerId, datacenterId, false, 10, null, 5L, 5L, 12L);
}
/**
* @param randomSequence true 表示每毫秒内起始序号使用随机值
* @param timeOffset 允许时间回拨的毫秒数
* @param epochDate 基准时间
* @param workerIdBits workerId 位数
* @param datacenterIdBits datacenterId 位数
* @param sequenceBits sequence 位数
*/
public IdGenerator(boolean randomSequence, long timeOffset, Date epochDate, long workerIdBits, long datacenterIdBits, long sequenceBits) {
if (null != epochDate) {
this.twepoch = epochDate.getTime();
} else {
// 2012/12/12 23:59:59 GMT
this.twepoch = 1355327999000L;
}
this.workerIdBits = workerIdBits;
this.datacenterIdBits = datacenterIdBits;
this.maxWorkerId = -1L ^ (-1L << workerIdBits);
this.maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
this.sequenceBits = sequenceBits;
this.sequenceMask = -1L ^ (-1L << sequenceBits);
this.workerIdShift = sequenceBits;
this.datacenterIdShift = sequenceBits + workerIdBits;
this.timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
this.datacenterId = getDatacenterId(maxDatacenterId);
this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
this.randomSequence = randomSequence;
this.timeOffset = timeOffset;
String initialInfo = String.format("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, datacenterid %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, datacenterId, workerId);
logger.info(initialInfo);
}
/**
* 自定义 workerId+datacenterId+其它初始配置
* 调整 workerId、datacenterId、sequence 位数定制雪花算法,控制生成的 Id 的位数
*
* @param workerId 工作机器 ID
* @param datacenterId 数据中心 ID
* @param randomSequence true 表示每毫秒内起始序号使用随机值
* @param timeOffset 允许时间回拨的毫秒数
* @param epochDate 基准时间
* @param workerIdBits workerId 位数
* @param datacenterIdBits datacenterId 位数
* @param sequenceBits sequence 位数
*/
public IdGenerator(long workerId, long datacenterId, boolean randomSequence, long timeOffset, Date epochDate, long workerIdBits, long datacenterIdBits, long sequenceBits) {
this.workerIdBits = workerIdBits;
this.datacenterIdBits = datacenterIdBits;
this.maxWorkerId = -1L ^ (-1L << workerIdBits);
this.maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0\r\n", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0\r\n", maxDatacenterId));
}
if (null != epochDate) {
this.twepoch = epochDate.getTime();
} else {
// 2012/12/12 23:59:59 GMT
this.twepoch = 1355327999000L;
}
this.sequenceBits = sequenceBits;
this.sequenceMask = -1L ^ (-1L << sequenceBits);
this.workerIdShift = sequenceBits;
this.datacenterIdShift = sequenceBits + workerIdBits;
this.timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
this.workerId = workerId;
this.datacenterId = datacenterId;
this.timeOffset = timeOffset;
this.randomSequence = randomSequence;
String initialInfo = String.format("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, datacenterid %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, datacenterId, workerId);
logger.info(initialInfo);
}
private static long getDatacenterId(long maxDatacenterId) {
long id = 0L;
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
if (network == null) {
id = 1L;
} else {
byte[] mac = network.getHardwareAddress();
if (null != mac) {
id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
id = id % (maxDatacenterId + 1);
}
}
} catch (Exception e) {
throw new RuntimeException("GetDatacenterId Exception", e);
}
return id;
}
private static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
StringBuilder macIpPid = new StringBuilder();
macIpPid.append(datacenterId);
try {
String name = ManagementFactory.getRuntimeMXBean().getName();
if (name != null && !name.isEmpty()) {
//GET jvmPid
macIpPid.append(name.split("@")[0]);
}
//GET hostIpAddress
String hostIp = InetAddress.getLocalHost().getHostAddress();
String ipStr = hostIp.replaceAll("\\.", "");
macIpPid.append(ipStr);
} catch (Exception e) {
throw new RuntimeException("GetMaxWorkerId Exception", e);
}
//MAC + PID + IP 的 hashcode 取低 16 位
return (macIpPid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}
public synchronized long nextId() {
long currentTimestamp = timeGen();
//获取当前时间戳如果小于上次时间戳，则表示时间戳获取出现异常
if (currentTimestamp < lastTimestamp) {
// 校验时间偏移回拨量
long offset = lastTimestamp - currentTimestamp;
if (offset > timeOffset) {
throw new RuntimeException("Clock moved backwards, refusing to generate id for [" + offset + "ms]");
}
try {
// 时间回退 timeOffset 毫秒内，则允许等待 2 倍的偏移量后重新获取，解决小范围的时间回拨问题
this.wait(offset << 1);
} catch (Exception e) {
throw new RuntimeException(e);
}
currentTimestamp = timeGen();
if (currentTimestamp < lastTimestamp) {
throw new RuntimeException("Clock moved backwards, refusing to generate id for [" + offset + "ms]");
}
}
//如果获取的当前时间戳等于上次时间戳（即同一毫秒内），则序列号自增
if (lastTimestamp == currentTimestamp) {
// randomSequence 为 true 表示随机生成允许范围内的起始序列,否则毫秒内起始值从 0L 开始自增
long tempSequence = sequence + 1;
if (randomSequence) {
sequence = tempSequence & sequenceMask;
count = (count + 1) & sequenceMask;
if (count == 0) {
currentTimestamp = this.tillNextMillis(lastTimestamp);
}
} else {
sequence = tempSequence & sequenceMask;
if (sequence == 0) {
currentTimestamp = this.tillNextMillis(lastTimestamp);
}
}
} else {
sequence = randomSequence ? tlr.nextLong(sequenceMask + 1) : 0L;
count = 0L;
}
lastTimestamp = currentTimestamp;
return ((currentTimestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tillNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
// for (int i = 0; i < 10; i++) {
// IdGenerator idGenerator = new IdGenerator();
// new Thread(() -> {
// for (int j = 0; j < 100; j++) {
// System.out.println(idGenerator.nextId());
// }
// }).start();
// }
// IdGenerator idGenerator = new IdGenerator(1, 1);
// for (int j = 0; j < 2000; j++) {
// System.out.println(System.currentTimeMillis() + " " + idGenerator.nextId());
// }
// IdGenerator idGenerator = new IdGenerator(true, 10, null, 3L, 2L, 7L);
// for (int j = 0; j < 2000; j++) {
// System.out.println(System.currentTimeMillis() + " " + idGenerator.nextId());
// }
IdGenerator shortIdGenerator = new IdGenerator(7, 3, true, 10, null, 3, 2, 7);
for (int j = 0; j < 1000; j++) {
System.out.println(System.currentTimeMillis() + " " + shortIdGenerator.nextId());
}
}
}
</code></pre>
<p>订单号生成案例</p>
<pre><code>import java.text.SimpleDateFormat;
import java.util.Date;
/**
* 使用 IdGenerator 生成唯一订单号
*/
public class OrderNoGenerator {
private IdGenerator idGenerator;
/**
* 无参构造器，自动生成 workerId/datacenterId
*/
public OrderNoGenerator() {
this.idGenerator = new IdGenerator();
}
/**
* 有参构造器,使用者自行保证数据中心 ID+机器 ID 的唯一性
*
* @param idGenerator
*/
public OrderNoGenerator(IdGenerator idGenerator) {
this.idGenerator = idGenerator;
}
/**
* 生成订单号
* @param env 1=dev,2=sit,3=uat,4=prd
* @param pid 1=产品线 1,2=产品线 2,3=产品线 3
* @param dateFormat 日期格式
* @return
*/
public String getOrderNo(String env, String pid, String dateFormat) {
if (dateFormat == null || dateFormat.isEmpty()) {
dateFormat = "yyMMddHH";
}
String dateStr = new SimpleDateFormat(dateFormat).format(new Date());
return env + pid + dateStr + idGenerator.nextId();
}
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
OrderNoGenerator orderNoGenerator = new OrderNoGenerator();
for (int i = 0; i < 1000; i++) {
System.out.println(System.currentTimeMillis() + " " + orderNoGenerator.getOrderNo("3", "1", null));
}
System.out.println("-------------------------------------------------");
//雪花算法生成 15 位 ID
IdGenerator shortIdGenerator = new IdGenerator(1, 2, false, 10, null, 3L, 2L, 7L);
OrderNoGenerator shortOrderNoGenerator = new OrderNoGenerator(shortIdGenerator);
for (int i = 0; i < 1000; i++) {
System.out.println(System.currentTimeMillis() + " " + shortOrderNoGenerator.getOrderNo("3", "1", null));
}
}
}
</code></pre>
</div>
</div>
<div>
<div style="float: left">
<a href="/文章/RocketMQ 面试题集锦.md.html">上一页</a>
</div>
<div style="float: right">
<a href="/文章/Spring Boot 2.x 结合 k8s 实现分布式微服务架构.md.html">下一页</a>
</div>
</div>
</div>
</div>
</div>
</div>
<a class="off-canvas-overlay" onclick="hide_canvas()"></a>
</div>
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v652eace1692a40cfa3763df669d7439c1639079717194" integrity="sha512-Gi7xpJR8tSkrpF7aordPZQlW2DLtzUlZcumS8dMQjwDHEnw9I7ZLyiOj/6tZStRBGtGgN6ceN6cMH8z7etPGlw==" data-cf-beacon='{"rayId":"709980177a1c8b66","version":"2021.12.0","r":1,"token":"1f5d475227ce4f0089a7cff1ab17c0f5","si":100}' crossorigin="anonymous"></script>
</body>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-NPSEEVD756"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'G-NPSEEVD756');
var path = window.location.pathname
var cookie = getCookie("lastPath");
console.log(path)
if (path.replace("/", "") === "") {
if (cookie.replace("/", "") !== "") {
console.log(cookie)
document.getElementById("tip").innerHTML = "<a href='" + cookie + "'>跳转到上次进度</a>"
}
} else {
setCookie("lastPath", path)
}
function setCookie(cname, cvalue) {
var d = new Date();
d.setTime(d.getTime() + (180 * 24 * 60 * 60 * 1000));
var expires = "expires=" + d.toGMTString();
document.cookie = cname + "=" + cvalue + "; " + expires + ";path = /";
}
function getCookie(cname) {
var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i].trim();
if (c.indexOf(name) === 0) return c.substring(name.length, c.length);
}
return "";
}
</script>
</html>