探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式

简介: 【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。

在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。

一、雪花算法原理

雪花算法由Twitter开源,其核心思想是通过一定的位运算,将时间戳、机器ID和序列号组合成一个64位的长整型ID。具体结构如下:

  1. 时间戳(41位):记录当前时间与特定起始时间(如Twitter使用的是2010-11-04)的差值,单位通常为毫秒,可使用69年。
  2. 机器ID(10位):支持部署最多1024个节点(包括机器和数据中心)。
  3. 序列号(12位):支持同一毫秒内生成最多4096个ID。

结构图如下:

复制代码
| 1 位符号位 | 41 位时间戳 | 10 位机器ID | 12 位序列号 |

二、时钟回拨问题

时钟回拨是指系统时钟由于某种原因(如人为调整、NTP同步错误等)突然倒退,这可能导致雪花算法生成的ID重复。处理时钟回拨的常见策略包括:

  1. 记录上一次生成ID的时间戳:每次生成ID时,比较当前时间戳与上一次的时间戳,如果检测到回拨,则拒绝生成ID或等待时间追上。
  2. 使用逻辑时钟:逻辑时钟保证总是递增,不依赖系统时钟。但需要额外的机制来同步和持久化逻辑时钟。

三、Java实现雪花算法

以下是雪花算法的Java实现,包括处理时钟回拨的逻辑:

java复制代码
public class SnowflakeIdGenerator {  
// 起始时间戳(2020-01-01 00:00:00 的 Unix 时间戳)  
private final long twepoch = 1577836800000L;  
// 机器ID所占的bit数  
private final long workerIdBits = 10L;  
// 数据中心ID所占的bit数  
private final long datacenterIdBits = 10L;  
// 支持的最大机器ID数量,结果为1024 (这个位数的机器ID最多1024个(0-1023))  
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);  
// 支持的最大数据中心ID数为1024  
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);  
// 序列在ID中占的位数  
private final long sequenceBits = 12L;  
// 机器ID向左移12位  
private final long workerIdShift = sequenceBits;  
// 数据中心ID向左移22位  
private final long datacenterIdShift = sequenceBits + workerIdBits;  
// 时间戳向左移22位  
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;  
// 生成序列的掩码,这里位运算保证只取12位  
private final long sequenceMask = -1L ^ (-1L << sequenceBits);  
private long workerId;  
private long datacenterId;  
private long sequence = 0L;  
private long lastTimestamp = -1L;  
public SnowflakeIdGenerator(long workerId, long datacenterId) {  
if (workerId > maxWorkerId || workerId < 0) {  
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));  
        }  
if (datacenterId > maxDatacenterId || datacenterId < 0) {  
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));  
        }  
this.workerId = workerId;  
this.datacenterId = datacenterId;  
    }  
// 产生下一个ID  
public synchronized long nextId() {  
long currentTimestamp = timeGen();  
if (currentTimestamp < lastTimestamp) {  
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));  
        }  
if (currentTimestamp == lastTimestamp) {  
// 如果在同一毫秒内  
            sequence = (sequence + 1) & sequenceMask;  
if (sequence == 0) {  
// 阻塞到下一个毫秒  
                currentTimestamp = tilNextMillis(lastTimestamp);  
            }  
        } else {  
            sequence = 0L;  
        }  
        lastTimestamp = currentTimestamp;  
return ((currentTimestamp - twepoch) << timestampLeftShift) |  
                (datacenterId << datacenterIdShift) |  
                (workerId << workerIdShift) |  
                sequence;  
    }  
// 阻塞到下一个毫秒,直到获得新的时间戳  
private long tilNextMillis(long lastTimestamp) {  
long timestamp = timeGen();  
while (timestamp <= lastTimestamp) {  
            timestamp = timeGen();  
        }  
return timestamp;  
    }  
// 获取当前时间戳  
private long timeGen() {  
return System.currentTimeMillis();  
    }  
public static void main(String[] args) {  
SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(1, 1);  
for (int i = 0; i < 10; i++) {  
long id = idWorker.nextId();  
            System.out.println(id);  
        }  
    }  
}

四、代码解释

  1. 常量定义
  • twepoch:起始时间戳。
  • workerIdBitsdatacenterIdBitssequenceBits:定义workerId、datacenterId和序列号占用的位数。
  • maxWorkerIdmaxDatacenterId:计算支持的最大workerId和datacenterId。
  • workerIdShiftdatacenterIdShifttimestampLeftShift:定义各部分在64位ID中的左移位数。
  • sequenceMask:序列号掩码,用于保证序列号不超过12位。
  1. 构造函数
  • 校验并初始化workerId和datacenterId。
  1. nextId方法
  • 获取当前时间戳,如果小于上一次时间戳,抛出异常处理时钟回拨。
  • 如果当前时间戳等于上一次时间戳,说明在同一毫秒内,序列号自增;如果序列号超过最大值(4095),则阻塞等待到下一毫秒。
  • 时间戳左移,并与datacenterId、workerId和序列号进行按位或运算,生成最终ID。
  1. tilNextMillis方法
  • 阻塞等待直到下一毫秒,以获取新的时间戳。
  1. timeGen方法
  • 获取当前系统时间戳。

五、总结

雪花算法通过时间戳、机器ID和序列号的组合,在分布式环境下生成全局唯一的64位ID。本文介绍了雪花算法的原理、处理了时钟回拨问题的策略,并提供了Java实现。这种算法不仅高效,而且保证了ID的有序性,是大数据量系统中常用的分布式ID生成方案。

目录
打赏
0
2
2
0
507
分享
相关文章
Java大厂面试高频:Collection 和 Collections 到底咋回答?
Java中的`Collection`和`Collections`是两个容易混淆的概念。`Collection`是集合框架的根接口,定义了集合的基本操作方法,如添加、删除等;而`Collections`是一个工具类,提供了操作集合的静态方法,如排序、查找、同步化等。简单来说,`Collection`关注数据结构,`Collections`则提供功能增强。通过小王的面试经历,我们可以更好地理解这两者的区别及其在实际开发中的应用。希望这篇文章能帮助你掌握这个经典面试题。
46 4
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
133 2
|
29天前
|
Java社招面试中的高频考点:Callable、Future与FutureTask详解
大家好,我是小米。本文主要讲解Java多线程编程中的三个重要概念:Callable、Future和FutureTask。它们在实际开发中帮助我们更灵活、高效地处理多线程任务,尤其适合社招面试场景。通过 Callable 可以定义有返回值且可能抛出异常的任务;Future 用于获取任务结果并提供取消和检查状态的功能;FutureTask 则结合了两者的优势,既可执行任务又可获取结果。掌握这些知识不仅能提升你的编程能力,还能让你在面试中脱颖而出。文中结合实例详细介绍了这三个概念的使用方法及其区别与联系。希望对大家有所帮助!
167 60
Java社招面试题:一个线程运行时发生异常会怎样?
大家好,我是小米。今天分享一个经典的 Java 面试题:线程运行时发生异常,程序会怎样处理?此问题考察 Java 线程和异常处理机制的理解。线程发生异常,默认会导致线程终止,但可以通过 try-catch 捕获并处理,避免影响其他线程。未捕获的异常可通过 Thread.UncaughtExceptionHandler 处理。线程池中的异常会被自动处理,不影响任务执行。希望这篇文章能帮助你深入理解 Java 线程异常处理机制,为面试做好准备。如果你觉得有帮助,欢迎收藏、转发!
52 14
Java 面试必问!线程构造方法和静态块的执行线程到底是谁?
大家好,我是小米。今天聊聊Java多线程面试题:线程类的构造方法和静态块是由哪个线程调用的?构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节有助于掌握Java多线程机制。下期再见! 简介: 本文通过一个常见的Java多线程面试题,详细讲解了线程类的构造方法和静态块是由哪个线程调用的。构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节对掌握Java多线程编程至关重要。
38 13
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
72 16
Java 高级面试技巧:yield() 与 sleep() 方法的使用场景和区别
本文详细解析了 Java 中 `Thread` 类的 `yield()` 和 `sleep()` 方法,解释了它们的作用、区别及为什么是静态方法。`yield()` 让当前线程释放 CPU 时间片,给其他同等优先级线程运行机会,但不保证暂停;`sleep()` 则让线程进入休眠状态,指定时间后继续执行。两者都是静态方法,因为它们影响线程调度机制而非单一线程行为。这些知识点在面试中常被提及,掌握它们有助于更好地应对多线程编程问题。
57 9
Java面试必问!run() 和 start() 方法到底有啥区别?
在多线程编程中,run和 start方法常常让开发者感到困惑。为什么调用 start 才能启动线程,而直接调用 run只是普通方法调用?这篇文章将通过一个简单的例子,详细解析这两者的区别,帮助你在面试中脱颖而出,理解多线程背后的机制和原理。
62 12
Java Dubbo 面试题
Java Dubbo相关基础面试题
Java MyBatis 面试题
Java MyBatis相关基础面试题

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等