- **正确答案**：雪花算法是一种分布式唯一ID生成算法，最初由Twitter提出并实现为Snowflake。它能够高效地在分布式系统中生成全局唯一的64位整数ID。每个ID由以下部分组成：1位符号位（始终为0），41位时间戳，10位机器ID（数据中心ID和机器ID），以及12位序列号。 - **解答思路**：首先，雪花算法将64位的二进制数划分为多个部分，每一部分都有特定的意义。时间戳部分记录了从某个起始时间点到当前时间的毫秒数，确保了时间的递增性。机器ID用于区分不同的机器，避免在同一毫秒内不同机器生成相同的ID。序列号则是在同一毫秒内生成的不同ID的计数器，保证即使在同一毫秒内也能生成多个唯一ID。当时间回拨时，算法会等待直到时间追上之前的值，或者抛出异常。 - **深度知识讲解**： - **数据结构与实现原理**：雪花算法的核心在于如何利用64位整数的不同部分来构造唯一ID。时间戳部分占用了41位，这意味着它可以表示大约69年的时间跨度（从一个自定义的纪元开始）。机器ID通常由10位组成，其中5位用于标识数据中心，另外5位用于标识单个机器。这样可以支持最多2^5=32个数据中心，每个数据中心最多支持32台机器。序列号部分占用12位，允许每毫秒最多生成2^12=4096个唯一ID。 - **时间回拨问题**：如果系统时间被调整到过去（即时间回拨），可能会导致生成重复的ID。为了解决这个问题，通常有两种策略：一是让系统等待直到时间追上原来的值，二是直接抛出异常，要求调用方处理这种情况。 - **优点**：雪花算法生成的ID是有序的，因为高阶位是时间戳，这使得基于时间的排序变得非常容易。此外，由于ID是64位整数，它可以直接用作数据库中的主键，适合大规模分布式系统的场景。 - **缺点**：需要预先分配机器ID，并且对系统时钟依赖较大，时间回拨可能导致问题。 - **扩展知识**： - **其他分布式ID生成算法**：除了雪花算法外，还有UUID、Redis自增计数器等方法。UUID虽然能保证全球唯一性，但其长度较长且无序，不适合某些高性能场景。Redis自增计数器简单易用，但在单点故障和性能方面存在局限性。 - **实际应用场景**：雪花算法广泛应用于大型互联网公司，如微博、抖音等，用于生成订单号、用户ID等需要全局唯一性的场景。 - **伪代码**： ``` class Snowflake { private final long twepoch = 1288834974657L; // 自定义纪元 private final long workerIdBits = 5L; // 工作机器ID所占位数 private final long datacenterIdBits = 5L; // 数据中心ID所占位数 private final long maxWorkerId = -1L ^ (-1L << workerIdBits); // 最大工作机器ID private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 最大数据中心ID private final long sequenceBits = 12L; // 序列号所占位数 private final long workerIdShift = sequenceBits; // 工作机器ID左移位数 private final long datacenterIdShift = sequenceBits + workerIdBits; // 数据中心ID左移位数 private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 时间戳左移位数 private final long sequenceMask = -1L ^ (-1L << sequenceBits); // 序列号掩码 private long sequence = 0L; // 序列号 private long lastTimestamp = -1L; // 上一次生成ID的时间戳 public Snowflake(long workerId, long datacenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0"); } if (datacenterId > maxDatacenterId || datacenterId < 0) { throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0"); } this.workerId = workerId; this.datacenterId = datacenterId; } public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { System.err.printf("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp); throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; return ((timestamp - 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(); } } ```

美团一面凉经(30min）

全站热榜

创作者周榜