Twitter的分布式自增ID算法snowflake（有改动Java版）

小咪咪 2022-06-13 10:14 175阅读 0赞

分布式ID生成器  
全局唯一ID生成  
分布式纯数字ID

> 其实这也不是Twitter独有的，mongodb也采用类似的方法生产自增ID。对于全局唯一ID的说明请参考我另一篇文章 : [高并发分布式环境中获取全局唯一ID\[分布式数据库全局唯一主键生成\]][ID]

> 该算法最大的好处就是：**纯数字**；**基本有序递增**

为了简单起见，我这里对snowflake算法进行了一点点修改，修改后的格式为：`41位时间戳 |10位进程号 |12位计数器`。共计63位（为什么不是64位：第一位是符号位

# 加锁实现 #

具体逻辑情况先忙代码中的注释：

import java.io.File;
 import java.io.FileWriter;
 import java.io.IOException;
 import java.util.Set;
 import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.ConcurrentSkipListSet;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 
 /** * 64位生成规则【首位是符号位，代表正副，所以实际有效是63位】： * * 41位时间戳 |10位进程号 |12位计数器 * * 41位时间戳： * 注意：这里没有直接使用时间戳，因为直接使用的话只能用到2039-09-07 23:47:35 * 这里采用（当前时间戳-初始时间戳）。最多这样可以使用69年【(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69】 * 10位机器：最多1023台机器 * 12位计数器：每毫秒最多生成4095条记录 * * 这里可以根据项目中实际情况，调整每个位置的长度，比如分布式集群机器数量比较少，可以缩减机器的位数，增加计数器位数 * * * 使用注意事项：1、必须关闭时钟同步；2、currentTimeMillis一经定义，不可修改；3、并发量太高的时候，超过了4095，未做处理；4、最大不超过64位 * * 自测性能：一秒能有三四十万的数据产生。 * * 无锁没写出来...... * * Created by hzliubenlong on 2017/6/28. */
 public class IDGeneratorUtil { 
 
 
 /** * 初始时间戳：2017-1-1 0:0:0 * 一经定义，不可修改 */
 private static final long initTimeMillis = 1483200000929L;
 /** * 进程。 * 这里也可以手动指定每台实例的ID号；或者通过ZK的临时递增节点自动获取。 * 固定值 */
 private static final int pid = 3;
 /** * 计数器 * 需要保证线程安全 */
 private static volatile long counter;
 private static volatile long currentTimeMillis = System.currentTimeMillis() - initTimeMillis;
 private static volatile long lastTimeMillis = currentTimeMillis;
 
 
 /** * 无锁模式暂时没有写出来 * * @return */
 public static synchronized long nextId() { 
 long series = counter++;
 if (series >= (1 << 12) - 1) { //单位毫秒内计时器满了，需要重新计时
 while (lastTimeMillis == currentTimeMillis) { //等待到下一秒
 currentTimeMillis = System.currentTimeMillis() - initTimeMillis;
 }
 
 lastTimeMillis = currentTimeMillis;
 counter = 0;
 series = counter++;
 }
 return (currentTimeMillis << 22) | (pid << 12) | series;
 }
 }

测试代码：

static Set<Long> set = new ConcurrentSkipListSet<>();
 
 
 ExecutorService fixedThreadPool = Executors.newFixedThreadPool(10);
 for (int i = 0; i < 10; i++) {
 fixedThreadPool.execute(() -> {
 while (true) {
 long l = nextId();
 boolean add = set.add(l);
 if (!add) {
 System.out.println(System.currentTimeMillis() + " " + l + " : " + Long.toBinaryString(l));
 System.exit(0);
 }
 }
 });
 }

> 这种加锁的实现，自测，每秒钟可以产生30W条记录。足够了

# 时间回调，时钟同步问题 #

**snowflake算法时间回拨问题思考**  
由于存在时间回拨问题，但是他又是那么快和简单，我们思考下是否可以解决呢？ 零度在网上找了一圈没有发现具体的解决方案，但是找到了一篇美团不错的文章：Leaf——美团点评分布式ID生成系统（https://tech.meituan.com/MT\_Leaf.html）文章很不错，可惜并没有提到时间回拨如何具体解决。下面看看零度的一些思考：

**分析时间回拨产生原因**  
第一：人为操作，在真实环境一般不会有那个傻逼干这种事情，所以基本可以排除。  
第二：由于有些业务等需要，机器需要同步时间服务器（在这个过程中可能会存在时间回拨，查了下我们服务器一般在10ms以内（2小时同步一次））。

> \*\*上面也说了，这个算法存在一个问题就是时钟同步的问题，尤其时钟回调。百度的uid-generator给出了一种解决办法，大家可以直接拿来使用： https://github.com/baidu/uid-generator \*\*

[ID]: http://blog.csdn.net/liubenlong007/article/details/53884447