谈一谈分布式ID生成方案的了解？

分布式系统中生成唯一ID是非常重要的，常见的分布式ID生成方案包括以下几种，每种方案都有其优缺点： #### 1. UUID UUID（Universally Unique Identifier）是一种生成唯一标识符的算法，生成的ID由32位字符组成，包括字母和数字。 **优点**： - 本地生成，生成简单，性能好，没有高可用风险。 **缺点**： - 长度过长，存储冗余，且无序不可读，查询效率低。 ```java String uniqueID = UUID.randomUUID().toString(); ``` #### 2. 数据库自增ID 使用数据库的自增ID策略（如 MySQL 的 `auto_increment`），可以利用两台数据库分别设置不同步长，生成不重复的ID来实现高可用。 **优点**： - 数据库生成的ID绝对有序，高可用实现方式简单。 **缺点**： - 需要独立部署数据库实例，成本高，有性能瓶颈。 ```sql CREATE TABLE id_generator ( id BIGINT AUTO_INCREMENT PRIMARY KEY ); INSERT INTO id_generator () VALUES (); SELECT LAST_INSERT_ID(); ``` #### 3. 批量生成ID 一次性从数据库中批量生成多个ID，将数据库修改为最大的ID值，并在内存中记录当前值及最大值。 **优点**： - 避免每次生成ID都要访问数据库，减少数据库压力，提高性能。 **缺点**： - 属于本地生成策略，存在单点故障，服务重启造成ID不连续。 ```java public class IDGenerator { private long currentId; private long maxId; public synchronized long getNextId() { if (currentId >= maxId) { fetchNewIds(); } return currentId++; } private void fetchNewIds() { // 从数据库批量获取新的ID段 // 更新 currentId 和 maxId } } ``` #### 4. Redis生成ID 利用Redis的自增命令（`incr` 和 `incrby`），生成唯一有序的ID。 **优点**： - 不依赖于数据库，灵活方便，性能优于数据库；数字ID天然排序，对分页或排序的结果有帮助。 **缺点**： - 如果系统中没有Redis，需要引入新的组件，增加系统复杂度；需要编码和配置的工作量较大。 ```java Jedis jedis = new Jedis("localhost"); long id = jedis.incr("id_key"); ``` #### 5. Twitter的Snowflake算法 Twitter的Snowflake算法使用64位的长整型数字来生成唯一ID，结构如下： - 1位符号位：最高位，始终为0。 - 41位时间戳：存储的是时间戳的差值（当前时间戳 - 起始时间戳），可以使用69年。 - 10位机器ID：包括5位数据标识位和5位机器标识位，最多支持1024个节点。 - 12位序列号：每个节点每毫秒最多生成4096个ID。 **优点**： - 高性能，低延迟，按时间有序，一般不会造成ID碰撞。 **缺点**： - 需要独立的开发和部署，依赖于机器的时钟。 ```java public class SnowflakeIdGenerator { private final long epoch = 1609459200000L; // 起始时间戳 private final long workerIdBits = 5L; private final long datacenterIdBits = 5L; private final long sequenceBits = 12L; private final long workerIdShift = sequenceBits; private final long datacenterIdShift = sequenceBits + workerIdBits; private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; 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 > ((1 << workerIdBits) - 1) || workerId < 0) { throw new IllegalArgumentException("worker Id out of range"); } if (datacenterId > ((1 << datacenterIdBits) - 1) || datacenterId < 0) { throw new IllegalArgumentException("datacenter Id out of range"); } this.workerId = workerId; this.datacenterId = datacenterId; } public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { throw new RuntimeException("Clock moved backwards."); } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; return ((timestamp - epoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; } protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } protected long timeGen() { return System.currentTimeMillis(); } } ``` #### 6. 百度UidGenerator UidGenerator是百度开源的分布式ID生成器，基于Snowflake算法实现，提供了一些优化和改进。 #### 7. 美团Leaf Leaf是美团开源的分布式ID生成器，保证全局唯一性、趋势递增、单调递增和信息安全，依赖数据库和Zookeeper等中间件。

首先ID生成方案的技术考虑点： 唯一性：不能重复。 趋势递增：保证id作为主键时，插入数据库时的顺序性，避免随机插入。 单调递增：满足某些特殊业务的要求，保证后一秒请求生成的id比前一秒的大。 信息安全性：不要像UUID一样泄露mac地址，也不要像数据库主键ID自增完全连续，泄露每日id生成数据量。 ### 1.UUID模式 太长，占用存储空间过大 id是字符串类型，查询成本高于数字类型 如果是包含mac地址的UUID会泄密 ### 2.单机数据库主键自增模式 id生成的量受限于单机MySQL数据库的性能 强依赖于数据库，主从切换时容易导致重复发号 容易泄露id生成量 ### 3.多机数据库主键自增模式 主要是将每个数据库的步长设置为一样，但是起始值不一样，以此错开生成的id，不便于扩展。 ### 4.Leaf号段模式模式 就是数据库存储一个maxId代表已经发放的id最大值，每次将maxId更新为max+step，取step数量的id发放。 优点： 1.便于扩展，发号性能取决于step，可以动态调整。(Leaf做了Step动态调整策略，一个号段使用时间<15分钟，就让号段拥有的id量step翻倍(直到最大阀值100万)，一个号段使用时间>30分钟,step减半(直到最低阀值，初始号段id量)。) 2.即便主节点的宕机，短时间Leaf也能继续提供服务，其次是主从切换时影响较小。 缺点： 1.当号段里面的id用完时，会去数据库取新的号段，此时如果来了获取id的请求会需要进行等待。(Leaf做了双Buffer优化，使用了双Buffer各存储一个号段，当一个号段使用量达到10%后，就触发另一个号段去数据库取新号段进行更新，以便于当一个号段使用完时，可以直接切换到未使用的号段。) 2.id是连续的，容易泄密。(可以自定义抛弃策略，取号段时的时候抛弃一些id，或者定时抛弃掉一些id。) ### 5.Leaf-snowflake模式 就是沿用了snowflake原本的位数分配算法，1标志位+41位毫秒时间戳+10位机器位+12位序列号。使用zookeeper作为注册中心，id生成服务启动时，去指路径下获取所有节点的列表，判断当前ip+port是否有对应的workid存在，有就使用，没有就往插入一个新的永久顺序节点，序号则为workId(并且会将workid缓存到本地磁盘上)。运行期间每过3s，都会上报最新的时间戳到zookeeper。 时钟回滚的处理： 启动时： zookeeper里面会存上次生成id的时间戳，如果上次存储的时间戳>当前系统时间戳，那么就抛出异常，启动失败。 运行时： 如果获取id时，发现上次生成id时的时间戳>当前系统时间戳，那么说明运行时发生了时钟回滚，如果回滚的时间差<5ms，就调用wait()方法等待10ms，然后再获取id，时间差>5ms，就抛出异常。 优点： 时钟回滚优化 1.对时钟回滚做了特殊处理。 #### zookeeper弱依赖 2.为了减轻了zookeeper的弱依赖，实现在zookeeper挂了的情况下，id生成服务也能启动，每次启动后，在本地也缓存workid配置，一旦启动时，发现zookeeper连接不上，就通过从本地缓存配置中读取workid。(但是这样也有问题，本地缓存配置只存了workid，没有存上次生成id的最大时间戳，所以一旦启动前发生了时钟回滚，或者是修改了系统时间，这样从本地缓存配置中读取workid生成的id就可能是重复的。) #### 时间差优化 3.做了时间差优化，就是默认的时间戳是从1970年开始的，leaf是自己选定了2010年的一个时间点，以此来计算时间戳，这样可以在时间位数固定的情况下，增长服务最大运行时间。在毫秒时间戳为41位的情况下，时间差最大是69年，如果以1970年为起点，那么最大时间就是1970+69年，如果以2010年为起点就是2010+69年。 #### 序列号优化 4.为了防止生成的id的序列号部分都是从0开始，导致插入数据库时，有数据倾斜的问题，所以每次用新的毫秒时间戳时，序列号不是从0开始，而是计算一个0到100之间的随机数作为起点。 缺点： 1.注册中心只支持Zookeeper 2.潜在的时钟回拨问题 3.时间差过大时，生成id为负数。 ### 6.百度的uid-generator模式 #### 默认模式 每次启动时向数据库插入一条数据，这行数据的主键是自增的，主键id就是workId， 因为默认是snowflake算法是1标志位+41位时间戳+10位机器号+12位序列号， 因为百度的是每次启动都获取新的机器号，所以它修改了这些位数配比，是 1标志位+28位的秒级时间差+22位的机器号+13位的序列号，所以总共支出2的22次方次启动，也就是400万次启动。最大服务支持时间是228次方，也就是8.7年。（优化点是修改位数分配，让服务时间更长，我们的位数分配是*30位秒级时间差+16位机器号+7位序列号**，最长服务时间支持34年，6.5w次机器启动，每个机器每秒128个并发，总共位数没有用到64位，只用到53位，这样生成的id转化为10进制更小。） 解决时间回拨问题： 启动时时间回拨 因为是每次都用新的机器号，所以当前机器号都是之前没有的，所以即便时间戳回拨也不影响。 运行时时间回拨 会使用lastSecond来记录上次生成id的时间戳，如果当前时间戳比lastSecond还小，就抛出异常。（优化点就是回拨时间差较小时进行等待，较长时再抛出异常。） 缺点： 1.默认的最大服务年限太短，只有8年。 2.回拨时间差较小时也是抛出异常，没有额外的判断逻辑。 3.没有像Leaf一样做序列号优化，可能生成的id序列号部分都是从0开始的多一些，可能会存在数据倾斜的问题。 #### 缓存模式 主要继承自默认模式，只是用一个环形数组来存储生成好的id，每次去环形数组中去，默认大小是2的13次方，8192。这种模式使用的时间取得不是实时的系统时间，而且使用启动时的时间，每次生成一组id时，对之前保存的时间+1。 阀值检测预填充：取id时，发现可用id数小于阀值50%时，就对后面已经使用的id进行再填充。 定期填充：每5分钟定期会去检查环形数组中id使用情况，然后生成一组最大序列号个数的id(默认是8192个)，然后进行填充，多的直接丢弃掉。 #### 缺点： 1.id只有在定期填充时，会丢弃掉一些id，其他情况下，id是完全连续的。假如每次使用量比较大，大部分时候都是5分钟内能用掉50%的话，那么就就不会触发定期填充，也没有id丢弃，导致id会一直连续，容易泄露数据信息，所以最好自定义丢弃逻辑。 2.其次是id跟生成id时系统的时间戳无关了，可能无法满足一些特殊业务的需求。 ### 自己的方案 我们自己的主要是根据uid-generator来做的，因为只是启动的时候依赖数据库，不需要引进新的依赖。做的优化主要是修改了位数分配，使得支持最大服务年限更长，30位时间差+16位机器号+7位序列号。做了时钟回拨优化，回拨差值较小时进行等待。以及做了序列号丢弃的优化。