关于ID生成器的思考

开发中经常遇到关于唯一ID生成的问题,而如何高效生成有序且再分布式环境全局唯一无疑是其核心。

目前常用的有雪花算法。每秒数十万级的产生,但其缺陷也是非常明显的,ID再未解析的时候,基本无规律可言,无法直接让业务人员分辨ID类型。对于一些业务场景,显然并不合适。于是引发一起对分布式ID生成的思考。

带时间格式和业务编码的生成

对于业务中常用的如 202111171613160000001000000230 这种携带日期格式和业务序列号的ID 就需要自己去改造和定义了。看似普普通通的这种序列号,如何满足单台机器每秒百万级别的产生且不冲突。

先贴一下自己最终的代码。可以很容易单机器生成数百万携带时间的ID。依然是参考雪花算法完成的该功能。不过再ID的处理方式上有了一些区别。

import java.time.LocalDateTime
import java.time.format.DateTimeFormatter

class DateTimeIdGeneratorImpl(
  private val driverId: Int = 0,
  private val businessId: Int = 0,
  private val dateTimeFormatter: DateTimeFormatter = DateTimeFormatter.ofPattern("yyyyMMddHHmmss")
) : IdGenerator<String> {

  init {
    if (driverId > 999 || driverId < 0) {
      throw RuntimeException("driver id 不能大于 999 或小于 0")
    }
    if (businessId > 999 || businessId < 0) {
      throw RuntimeException("business id 不能大于 999 或小于 0")
    }
  }

  private val driverIdStr = String.format("%03d", driverId)

  private val businessIdStr = String.format("%03d", businessId)

  private val maxSequence: Int = Int.MAX_VALUE

  private val defaultSequence: Int = 0

  private var sequence = defaultSequence

  private var lastTimestamp: Long = 0L

  private var lastDateTimeStr = ""

  @Synchronized
  override fun next(): String {
    val currentTimestamp = currentTimestamp()
    if (currentTimestamp < lastTimestamp) {
      throw RuntimeException("机器时钟发生回拨")
    }
    if (currentTimestamp == lastTimestamp) {
      sequence = (sequence + 1) and maxSequence
      if (sequence == 0) {
        waitNextTimestamp(currentTimestamp)
        sequence = defaultSequence
        lastDateTimeStr = LocalDateTime.now().format(dateTimeFormatter)
      }
    } else {
      sequence = defaultSequence
      lastDateTimeStr = LocalDateTime.now().format(dateTimeFormatter)
    }
    this.lastTimestamp = currentTimestamp
//    return String.format(
//      "%s%03d%03d%010d",
//      lastDateTimeStr,
//      driverId,
//      businessId,
//      sequence
//    )
//    return lastDateTimeStr + driverIdStr + businessIdStr + fillZero(sequence, 10)
    return lastDateTimeStr + driverIdStr + businessIdStr + (1000000000 + sequence)
  }

  /**
   * 对 number 填充 0
   */
  private fun fillZero(number: Int, length: Int): String {
    var numberString = number.toString()
    while (numberString.length < length) {
      numberString = "0$numberString"
    }
    return numberString
  }

  /**
   * 等待下一个时间.
   */
  private fun waitNextTimestamp(lastTimestamp: Long) {
    while (this.lastTimestamp <= lastTimestamp) {
      this.lastTimestamp = currentTimestamp()
    }
  }

  private fun currentTimestamp(): Long {
    return System.currentTimeMillis() / 1000
  }

}

最初版本是通过 String.format()sequence 进行补零,但看似方便的操作,实际性能却是最差的,让本身非常高效的算法,只能每秒三万左右的生成量

String.format(
      "%s%03d%03d%010d",
      LocalDateTime.now().format(dateTimeFormatter),
      driverId,
      businessId,
      sequence
    )

这和设想差距了好几个数量级,通过一番测试,确认了确实是因为 String.format 的原因,于是自己实现了一个简单的填充算法,但是依然并不高效,总算迈入了每秒百万的,压测后每秒大概 200 万

  fun fillZero(number: Int): String {
    var numberString = number.toString()
    while (numberString.length < 10) {
      numberString = "0$numberString"
    }
    return numberString
  }

后又突然想到目标是百万级别乃至于千万级别,可产生的数值,最多也就千万,何不之间采用大数加小数的方式进行补零,于是有了采用最终实现的方式,sequence 从一个大数开始自增,这样就避免了需要补零而影响效率,而多出来的一位, 也就是最终的版本,压测后,每秒最多可达到 600万。

简单改进后的雪花算法

不需要携带时间格式的, 这里我也对其进行了一番改造,雪花算法有一个缺陷就是长度有可能在 19 和 20 之间浮动,在这里添加了一个不使用的首位,保证了最终生成出来的ID的长度保持唯一,不过牺牲了能容纳ID的个数,但是对绝大多数系统来说,依然还是绰绰有余, 最大支持每秒 50 W 的生成量。

import java.text.SimpleDateFormat;
import java.util.Date;

public class SnowSerialNumberGenerator implements SerialNumberGenerator<Long> {

    private static final long version = 1L;

    /**
     * 不参与使用的首位.
     */
    private static final long unusedBits = 1L;

    /**
     * 版本使用位数.
     */
    private static final long versionBits = 3L;

    /**
     * 时间戳使用位数.
     * 最多使用年限 = (1 << 39) / (1000 * 60 * 60 * 24 * 365) 约 17 年
     */
    private static final long timestampBits = 39L;

    /**
     * 业务编号使用位数.
     */
    private static final long businessNumberBits = 6L;

    /**
     * 设备编号使用位数.
     */
    private static final long deviceNumberBits = 6L;

    /**
     * 序列使用位数.
     */
    private static final long sequenceBits = 9L;

    /**
     * 版本号位移位数.
     */
    private static final long versionShift = timestampBits + businessNumberBits + deviceNumberBits + sequenceBits;

    /**
     * 时间戳位移位数.
     */
    private static final long timestampShift = businessNumberBits + deviceNumberBits + sequenceBits;

    /**
     * 业务编号位移位数.
     */
    private static final long businessNumberShift = deviceNumberBits + sequenceBits;

    /**
     * 工作机器ID位移位数.
     */
    private static final long deviceNumberShift = sequenceBits;

    /**
     * 最大业务编号.
     */
    private static final int maxBusinessNumber = ~(-1 << businessNumberBits);

    /**
     * 最大工作机器ID.
     */
    private static final int maxDeviceNumber = ~(-1 << deviceNumberBits);

    /**
     * 最大序列数.
     */
    private static final long maxSequence = ~(-1 << sequenceBits);

    /**
     * 开始时间 2021-04-01 00:00:00
     */
    private static final long epoch = 1617206400000L;

    /**
     * 上次生成ID时间.
     */
    private long lastTimestamp = -1L;

    /**
     * 当前生成序列.
     */
    private long sequence = 0L;

    /**
     * 设备编号.
     */
    private final long deviceNumber;

    /**
     * 业务编号.
     */
    private final long businessNumber;

    public SnowSerialNumberGenerator(int deviceNumber, int businessNumber) {

        if (deviceNumber > maxDeviceNumber || deviceNumber < 0) {
            throw new IllegalArgumentException("设备编号不能大于 " + maxDeviceNumber + " 且不能小于0");
        }
        if (businessNumber > maxBusinessNumber || businessNumber < 0) {
            throw new IllegalArgumentException("业务编号不能大于 " + maxBusinessNumber + " 且不能小于0");
        }
        this.deviceNumber = deviceNumber;
        this.businessNumber = businessNumber;
    }

    /**
     * 生成ID
     *
     * @return 业务ID
     */
    @Override
    public synchronized Long next() {


        long currentTimestamp = currentTimestamp();
        if (currentTimestamp < lastTimestamp) {
            throw new IllegalStateException("机器时钟发生回拨 : " + (lastTimestamp - currentTimestamp) + ",请重新生成");
        }
        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) & maxSequence;
            if (sequence == 0) {
                currentTimestamp = waitNextTimestamp(currentTimestamp);
            }
        } else {
            sequence = 0;
        }
        lastTimestamp = currentTimestamp;

        return version << versionShift | (lastTimestamp - epoch) << timestampShift
                | businessNumber << businessNumberShift | deviceNumber << deviceNumberShift | sequence;
    }

    private long waitNextTimestamp(long currentTimestamp) {
        while (currentTimestamp <= lastTimestamp) {
            currentTimestamp = currentTimestamp();
        }
        return currentTimestamp;
    }

    private long currentTimestamp() {
        return System.currentTimeMillis();
    }

    private long[] parseId(long id) {
        long[] arr = new long[6];
        arr[0] = (id & diode(unusedBits, versionBits)) >> versionShift;
        arr[1] = (id & diode(unusedBits + versionBits, timestampBits)) >> timestampShift;
        arr[2] = (id & diode(unusedBits + versionBits + timestampBits, businessNumberBits)) >> businessNumberShift;
        arr[3] = (id & diode(unusedBits + versionBits + +timestampBits + businessNumberBits, deviceNumberBits)) >> deviceNumberShift;
        arr[4] = (id & diode(unusedBits + versionBits + timestampBits + businessNumberBits + deviceNumberBits, sequenceBits));
        arr[5] = arr[1] + epoch;
        return arr;
    }

    private long diode(long offset, long length) {
        int lb = (int) (64 - offset);
        int rb = (int) (64 - (offset + length));
        return (-1L << lb) ^ (-1L << rb);
    }

    public String formatId(long id) {
        long[] arr = parseId(id);
        String tmf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(arr[5]));
        return String.format("V%d %s, #%d, @(%d,%d)", arr[0], tmf, arr[4], arr[2], arr[3]);
    }

}
本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇