对于单体架构，用数据库自增ID完全足够了，但是分布式环境下，如果还利用数据库自增，很容易引起id冲突。所以我们要寻找一种高并发，高性能，高可用的方案。

数据库自增

假如我们设计分库分表，分了10个库。那么我们可以设计成

  • 库1，自增id从1开始，步进为10
  • 库2，自增id从2开始，步进为10
  • …

这样的确很容易就解决了id的问题，但非常不利于扩容缩容。而且需要而外维护数据自增id从哪里开始，这一步很容易出错。

uuid

uuid是本地生成的32位长度的无序字符串。生成效率的缺很高，但由于生成的字符串无序，在读写数据库的时候，需要频繁打开不同的页。所以uuid也是不推荐的

利用数据库表

比如在某个数据库下新建一个表，利用该表主键自增策略，当我们需要⼀个ID的时候，向表中插⼊⼀条记录返回主键ID，但这种⽅式有⼀个⽐较致命的缺点，访问量激增时MySQL本⾝就是系统的瓶颈，⽤它来实现分布式服务风险⽐较⼤，不推荐！

Redis自增

利用Redis的INCR命令进行自增。的确支持高并发了，但是也会造成redis压力过大，而且在redis丢失数据后，会导致id重复。

zk

利用ZooKeeper 的顺序节点，生成全局唯一的ID。利用中间件的形式，比如mysql，redis，zk，mongodb等等，都会造成额外的网络消耗，并且当id生成器不可用时，会导致全部服务不可用。

号段模式

这种是批量发号，比如去请求主键时，不是返回一个id，而是一组id（比如500-1000），这种避免了频繁的网络消耗，但也有问题：假如当前服务获得了500-1000的号码段，但意外宕机了，系统会缺少这组号码段的id，造成id不连续。

雪花算法（推荐）

image.png
雪花算法的原理就是生成一个的 64 位比特位的 long 类型的唯一 id。

  • 最高 1 位固定值 0，因为生成的 id 是正整数，如果是 1 就是负数了。
  • 接下来 41 位存储毫秒级时间戳，2^41/(1000606024365)=69，大概可以使用 69 年。
  • 再接下 10 位存储机器码，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台机器。
  • 最后 12 位存储序列号。同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 id。

算法实现

  1. package util;
  3. import java.util.Date;
  5. /**
  6.  * @ClassName: SnowFlakeUtil
  7.  * @Description:
  8.  */
  9. public class SnowFlakeUtil {
  11.     private static SnowFlakeUtil snowFlakeUtil;
  12.     static {
  13.         snowFlakeUtil = new SnowFlakeUtil();
  14.     }
  16.     // 初始时间戳(纪年)，可用雪花算法服务上线时间戳的值
  17.     // 1650789964886：2022-04-24 16:45:59
  18.     private static final long INIT_EPOCH = 1650789964886L;
  20.     // 时间位取&
  21.     private static final long TIME_BIT = 0b1111111111111111111111111111111111111111110000000000000000000000L;
  23.     // 记录最后使用的毫秒时间戳，主要用于判断是否同一毫秒，以及用于服务器时钟回拨判断
  24.     private long lastTimeMillis = -1L;
  26.     // dataCenterId占用的位数
  27.     private static final long DATA_CENTER_ID_BITS = 5L;
  29.     // dataCenterId占用5个比特位，最大值31
  30.     // 0000000000000000000000000000000000000000000000000000000000011111
  31.     private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS);
  33.     // dataCenterId
  34.     private long dataCenterId;
  36.     // workId占用的位数
  37.     private static final long WORKER_ID_BITS = 5L;
  39.     // workId占用5个比特位，最大值31
  40.     // 0000000000000000000000000000000000000000000000000000000000011111
  41.     private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);
  43.     // workId
  44.     private long workerId;
  46.     // 最后12位，代表每毫秒内可产生最大序列号，即 2^12 - 1 = 4095
  47.     private static final long SEQUENCE_BITS = 12L;
  49.     // 掩码（最低12位为1，高位都为0），主要用于与自增后的序列号进行位与，如果值为0，则代表自增后的序列号超过了4095
  50.     // 0000000000000000000000000000000000000000000000000000111111111111
  51.     private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);
  53.     // 同一毫秒内的最新序号，最大值可为 2^12 - 1 = 4095
  54.     private long sequence;
  56.     // workId位需要左移的位数 12
  57.     private static final long WORK_ID_SHIFT = SEQUENCE_BITS;
  59.     // dataCenterId位需要左移的位数 12+5
  60.     private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
  62.     // 时间戳需要左移的位数 12+5+5
  63.     private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;
  65.     /**
  66.      * 无参构造
  67.      */
  68.     public SnowFlakeUtil() {
  69.         this(1, 1);
  70.     }
  72.     /**
  73.      * 有参构造
  74.      * @param dataCenterId
  75.      * @param workerId
  76.      */
  77.     public SnowFlakeUtil(long dataCenterId, long workerId) {
  78.         // 检查dataCenterId的合法值
  79.         if (dataCenterId < 0 || dataCenterId > MAX_DATA_CENTER_ID) {
  80.             throw new IllegalArgumentException(
  81.                     String.format("dataCenterId 值必须大于 0 并且小于 %d", MAX_DATA_CENTER_ID));
  82.         }
  83.         // 检查workId的合法值
  84.         if (workerId < 0 || workerId > MAX_WORKER_ID) {
  85.             throw new IllegalArgumentException(String.format("workId 值必须大于 0 并且小于 %d", MAX_WORKER_ID));
  86.         }
  87.         this.workerId = workerId;
  88.         this.dataCenterId = dataCenterId;
  89.     }
  91.     /**
  92.      * 获取唯一ID
  93.      * @return
  94.      */
  95.     public static Long getSnowFlakeId() {
  96.         return snowFlakeUtil.nextId();
  97.     }
  99.     /**
  100.      * 通过雪花算法生成下一个id，注意这里使用synchronized同步
  101.      * @return 唯一id
  102.      */
  103.     public synchronized long nextId() {
  104.         long currentTimeMillis = System.currentTimeMillis();
  105.         System.out.println(currentTimeMillis);
  106.         // 当前时间小于上一次生成id使用的时间，可能出现服务器时钟回拨问题
  107.         if (currentTimeMillis < lastTimeMillis) {
  108.             throw new RuntimeException(
  109.                     String.format("可能出现服务器时钟回拨问题，请检查服务器时间。当前服务器时间戳：%d，上一次使用时间戳：%d", currentTimeMillis,
  110.                             lastTimeMillis));
  111.         }
  112.         if (currentTimeMillis == lastTimeMillis) {
  113.             // 还是在同一毫秒内，则将序列号递增1，序列号最大值为4095
  114.             // 序列号的最大值是4095，使用掩码（最低12位为1，高位都为0）进行位与运行后如果值为0，则自增后的序列号超过了4095
  115.             // 那么就使用新的时间戳
  116.             sequence = (sequence + 1) & SEQUENCE_MASK;
  117.             if (sequence == 0) {
  118.                 currentTimeMillis = getNextMillis(lastTimeMillis);
  119.             }
  120.         } else { // 不在同一毫秒内，则序列号重新从0开始，序列号最大值为4095
  121.             sequence = 0;
  122.         }
  123.         // 记录最后一次使用的毫秒时间戳
  124.         lastTimeMillis = currentTimeMillis;
  125.         // 核心算法，将不同部分的数值移动到指定的位置，然后进行或运行
  126.         // <<：左移运算符, 1 << 2 即将二进制的 1 扩大 2^2 倍
  127.         // |：位或运算符, 是把某两个数中, 只要其中一个的某一位为1, 则结果的该位就为1
  128.         // 优先级：<< > |
  129.         return
  130.                 // 时间戳部分
  131.                 ((currentTimeMillis - INIT_EPOCH) << TIMESTAMP_SHIFT)
  132.                 // 数据中心部分
  133.                 | (dataCenterId << DATA_CENTER_ID_SHIFT)
  134.                 // 机器表示部分
  135.                 | (workerId << WORK_ID_SHIFT)
  136.                 // 序列号部分
  137.                 | sequence;
  138.     }
  140.     /**
  141.      * 获取指定时间戳的接下来的时间戳，也可以说是下一毫秒
  142.      * @param lastTimeMillis 指定毫秒时间戳
  143.      * @return 时间戳
  144.      */
  145.     private long getNextMillis(long lastTimeMillis) {
  146.         long currentTimeMillis = System.currentTimeMillis();
  147.         while (currentTimeMillis <= lastTimeMillis) {
  148.             currentTimeMillis = System.currentTimeMillis();
  149.         }
  150.         return currentTimeMillis;
  151.     }
  153.     /**
  154.      * 获取随机字符串,length=13
  155.      * @return
  156.      */
  157.     public static String getRandomStr() {
  158.         return Long.toString(getSnowFlakeId(), Character.MAX_RADIX);
  159.     }
  161.     /**
  162.      * 从ID中获取时间
  163.      * @param id 由此类生成的ID
  164.      * @return
  165.      */
  166.     public static Date getTimeBySnowFlakeId(long id) {
  167.         return new Date(((TIME_BIT & id) >> 22) + INIT_EPOCH);
  168.     }
  170.     public static void main(String[] args) {
  171.         SnowFlakeUtil snowFlakeUtil = new SnowFlakeUtil();
  172.         long id = snowFlakeUtil.nextId();
  173.         System.out.println(id);
  174.         Date date = SnowFlakeUtil.getTimeBySnowFlakeId(id);
  175.         System.out.println(date);
  176.         long time = date.getTime();
  177.         System.out.println(time);
  178.         System.out.println(getRandomStr());
  180.     }
  182. }

优点

  • 生成的id，是有序的long数字
  • 高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
  • 基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
  • 不依赖第三方库或者中间件。
  • 算法简单，在内存中进行，效率高。

缺点
依赖服务器时间，服务器时钟回拨时可能会生成重复 id。算法中可通过记录最后一个生成 id 时的时间戳来解决，每次生成 id 之前比较当前服务器时钟是否被回拨，避免生成重复 id。

UidGenerator(百度)

UidGenerator 对 Snowflake(雪花算法)进行了改进
image.png

Leaf(美团)

Leaf 提供了 号段模式 和 Snowflake(雪花算法) 这两种模式来生成分布式 ID。并且，它支持双号段，还解决了雪花 ID 系统时钟回拨问题。不过，时钟问题的解决需要弱依赖于 Zookeeper 。

Tinyid(滴滴)

基于数据库号段模式的唯一 ID 生成器，相比于基于数据库号段模式的简单架构方案，Tinyid 方案主要做了下面这些优化：

  • 双号段缓存 ：为了避免在获取新号段的情况下，程序获取唯一 ID 的速度比较慢。 Tinyid 中的号段在用到一定程度的时候，就会去异步加载下一个号段，保证内存中始终有可用号段。
  • 增加多 db 支持 ：支持多个 DB，并且，每个 DB 都能生成唯一 ID，提高了可用性。
  • 增加 tinyid-client ：纯本地操作，无 HTTP 请求消耗，性能和可用性都有很大提升。