分布式ID的常见3种做法

分布式ID的常见3种做法

Tags
雪花算法
UUID
SQL
分布式设计
CreatedTime
Aug 18, 2022 11:22 AM
Slug
2020-08-14-uuid
UpdatedTime
Last updated August 18, 2022

UUID

格式

长度 32、16 进制。
形如:550e8400-e29b-41d4-a716-446655440000

优点

  1. 数量多:UUID 理论上的总数为 16^32 =2^128 约等于 3.4 x 10^38。也就是说若每纳秒(ns)产生 1 万亿个 UUID,要花 100 亿年才会将所有 UUID 用完。
  1. 位数长,涉及 mac 地址,很难重复
  1. 本地生成,无网络消耗

缺点

  1. 不携带信息。例如不递增,不含有业务含义
  1. 长度长,占用位数多。32 bytes = 32 x 8 bits = 256 bits
  1. 作为 mysql 主键,太长会影响 mysql 性能,无序性会导致位置变动频繁

数据库唯一ID

单机自增

优点:实现简单。
缺点:单机是性能瓶颈。

集群自增

设置不同的「自增步长」和「自增步长」。
notion image
# 代码demo set @@auto_increment_offset = 1; -- 起始值 set @@auto_increment_increment = 2; -- 步长
缺点:新增机器容易出现重复问题,需要人工介入。

号段模式(主流)

思想是从数据库批量获取自增 ID。
重点是数据表设计:
CREATE TABLE id_generator ( id int(10) NOT NULL, biz_type int(20) NOT NULL COMMENT '业务标识', max_id bigint(20) NOT NULL COMMENT '业务标识对应的当前最大id', step int(20) NOT NULL COMMENT '业务标识对应的号段步长', version int(20) NOT NULL COMMENT '版本号', // 乐观锁,每次都更新version,保证并发时数据的正确性 PRIMARY KEY (`id`) )
流程是:
  • 从数据库取出号段范围,例如 1000-2000 使用乐观锁,防止并发问题:
    • update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} // 防止并发问题 and biz_type = XXX
  • 本地化存储取出的号段,例如放入内存
  • 使用取出的号段
  • 用完后,回到第一步,继续取出 2k-3k
  • 如此循环

Snowflake雪花算法

notion image
  • 1bit:默认为 0,代表+-
  • 时间戳:单位 ms,通常采用相对时间戳。当前时间戳 - 指定开始时间戳
  • 工作机器:机房、机器号或者其组合
  • 序列号:12bit,支持同一 ms 下,生成 2^12 个 ID

二次封装

  • 美团 Leaf:支持号段+雪花算法

代码实现

实现的关键点是:nextId() 函数。
  1. 系统时间回拨:直接抛错
  1. ID 上限:通过对 2^12 取余实现。
public class IdWorker{ private long workerId; private long datacenterId; private long sequence = 0; /** * 2018/9/29日,从此时开始计算,可以用到2089年 */ private long twepoch = 1538211907857L; private long workerIdBits = 5L; private long datacenterIdBits = 5L; private long sequenceBits = 12L; private long workerIdShift = sequenceBits; private long datacenterIdShift = sequenceBits + workerIdBits; private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 得到0000000000000000000000000000000000000000000000000000111111111111 private long sequenceMask = -1L ^ (-1L << sequenceBits); private long lastTimestamp = -1L; public IdWorker(long workerId, long datacenterId){ this.workerId = workerId; this.datacenterId = datacenterId; } public synchronized long nextId() { long timestamp = timeGen(); //时间回拨,抛出异常 if (timestamp < lastTimestamp) { System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); 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 = 0; } lastTimestamp = timestamp; return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; } /** * 当前ms已经满了 * @param lastTimestamp * @return */ 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) { IdWorker worker = new IdWorker(1,1); for (int i = 0; i < 30; i++) { System.out.println(worker.nextId()); } } }