当前位置 : 主页 > 编程语言 > java >

java语言自行实现ULID过程底层原理详解

来源:互联网 收集:自由互联 发布时间:2023-01-30
目录 前提 ULID出现的背景 ULID规范 组成 排序 规范的表示形式 编码 单调性 溢出错误处理 二进制布局 ULID使用 实现ULID ULID性能评估 小结 前提 最近发现各个频道推荐了很多 ULID 相关文章
目录
  • 前提
  • ULID出现的背景
  • ULID规范
    • 组成
    • 排序
    • 规范的表示形式
    • 编码
    • 单调性
    • 溢出错误处理
    • 二进制布局
  • ULID使用
    • 实现ULID
      • ULID性能评估
        • 小结

          前提

          最近发现各个频道推荐了很多ULID相关文章,这里对ULID的规范文件进行解读,并且基于Java语言自行实现ULID,通过此实现过程展示ULID的底层原理。

          ULID出现的背景

          ULID全称是Universally Unique Lexicographically Sortable Identifier,直译过来就是通用唯一按字典排序的标识符,它的原始仓库是https://github.com/ulid/javascript,该项目由前端开发者alizain发起,基于JavaScript语言编写。从项目中的commit历史来看已经超过了5年,理论上得到充分的实践验证。ULID出现的原因是一些开发者认为主流的UUID方案在许多场景下可能不是最优的,存在下面的原因:

          • UUID不是128 bit随机编码(由128 bit随机数通过编码生成字符串)的最高效实现方式
          • UUIDv1/v2实现在许多环境中是不切实际的,因为这两个版本的的实现需要访问唯一的、稳定的MAC地址
          • UUIDv3/v5实现需要唯一的种子,并且产生随机分布的ID,这可能会导致在许多数据结构中出现碎片
          • UUIDv4除了随机性之外不需要提供其他信息,随机性可能会在许多数据结构中导致碎片

          这里概括一下就是:UUIDv1/v2实现依赖唯一稳定MAC地址不现实,v3/v4/v5实现因为随机性产生的ID会"碎片化"。

          基于此提出了ULID,它用起来像这样:

          ulid() // 01ARZ3NDEKTSV4RRFFQ69G5FAV
          

          ULID的特点如下:

          • 设计为128 bit大小,与UUID兼容
          • 每毫秒生成1.21e+24个唯一的ULID(高性能)
          • 按字典顺序(字母顺序)排序
          • 标准编码为26个字符的字符串,而不是像UUID那样需要36个字符
          • 使用Crockfordbase32算法来提高效率和可读性(每个字符5 bit
          • 不区分大小写
          • 没有特殊字符串(URL安全,不需要进行二次URL编码)
          • 单调排序(正确地检测并处理相同的毫秒,所谓单调性,就是毫秒数相同的情况下,能够确保新的ULID随机部分的在最低有效位上加1位)

          ULID规范

          下面的ULID规范在ULID/javascript类库中实现,此二进制格式目前没有在JavaScript中实现:

           01AN4Z07BY      79KA1307SR9X4MV3
          |----------|    |----------------|
           Timestamp          Randomness
             48bits             80bits
          

          组成

          时间戳(Timestamp)

          • 占据48 bit(high)
          • 本质是UNIX-time,单位为毫秒
          • 直到公元10889年才会用完

          随机数(Randomness)

          • 占据80 bit(low)
          • 如果可能的话,使用加密安全的随机源

          排序

          "最左边"的字符必须排在最前面,"最右边"的字符排在最后(词法顺序,或者俗称的字典排序),并且所有字符必须使用默认的ASCII字符集。在相同的毫秒(时间戳)内,无法保证排序顺序。

          规范的表示形式

          ULID规范的字符串表示形式如下:

          ttttttttttrrrrrrrrrrrrrrrr
          where
          t is Timestamp (10 characters)
          r is Randomness (16 characters)
          

          也就是:

          • 时间戳占据高(左边)10个(编码后的)字符
          • 随机数占据低(右边)16个(编码后的)字符

          ULID规范的字符串表示形式的长度是确定的,共占据26个字符。

          编码

          使用Crockford Base32编码算法,这个编码算法的字母表如下:

          0123456789ABCDEFGHJKMNPQRSTVWXYZ
          

          该字母表排除了ILOU字母,目的是避免混淆和滥用。此算法实现不难,它的官网有详细的算法说明(https://www.crockford.com/base32.html):

          单调性

          (如果启用了单调性这个特性为前提下)当在相同的毫秒内生成多个ULID时,可以保证排序的顺序。也就是说,如果检测到相同的毫秒,则随机分量在最低有效位上加1位(带进位)。例如:

          monotonicUlid()  // 01BX5ZZKBKACTAV9WEVGEMMVRZ
          monotonicUlid()  // 01BX5ZZKBKACTAV9WEVGEMMVS0
          

          溢出错误处理

          从技术实现上来看,26个字符的Base32编码字符串可以包含130 bit信息,而ULID只包含128 bit信息,所以该编码算法是能完全满足ULID的需要。基于Base32编码能够生成的最大的合法ULID其实就是7ZZZZZZZZZZZZZZZZZZZZZZZZZ,并且使用的时间戳为epoch time281474976710655或者说2 ^ 48 - 1。对于任何对大于此值的ULID进行解码或编码的尝试都应该被所有实现拒绝,以防止溢出错误。

          二进制布局

          二进制布局的多个部分被编码为16 byte,每个部分都以最高字节优先(网络字节序,也就是big-endian)进行编码,布局如下:

          0                   1                   2                   3
           0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |                      32_bit_uint_time_high                    |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |     16_bit_uint_time_low      |       16_bit_uint_random      |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |                       32_bit_uint_random                      |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |                       32_bit_uint_random                      |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          

          ULID使用

          对于script标签引用:

          <script src="https://unpkg.com/ulid@latest/dist/index.umd.js"></script>
          <script>
              ULID.ulid()
          </script>
          

          NPM安装:

          npm install --save ulid
          

          TypeScript, ES6+, Babel, Webpack, Rollup等等下使用:

          // import
          import { ulid } from 'ulid'
          ulid()
          // CommonJS env
          const ULID = require('ulid')
          ULID.ulid()
          

          后端Maven项目中使用需要引入依赖,这里选用ulid-creator实现:

          <dependency>
            <groupId>com.github.f4b6a3</groupId>
            <artifactId>ulid-creator</artifactId>
            <version>5.0.2</version>
          </dependency>
          

          然后调用UlidCreator#getUlid()系列方法:

          // 常规
          Ulid ulid = UlidCreator.getUlid();
          // 单调排序
          Ulid ulid = UlidCreator.getMonotonicUlid();
          

          实现ULID

          前面已经提到ULID的规范,其实具体实现ULID就是对着规范里面的每一个小节进行编码实现。先看二进制布局,由于使用128 bit去存储,可以借鉴UUID那样,使用两个long类似的成员变量存储ULID的信息,看起来像这样:

          public final class ULID {
              /*
               * The most significant 64 bits of this ULID.
               *
               */
              private final long msb;
              /*
               * The least significant 64 bits of this ULID.
               *
               */
              private final long lsb;
              public ULID(long msb, long lsb) {
                  this.msb = msb;
                  this.lsb = lsb;
              }
          }
          

          按照ULID的组成来看,可以提供一个入参为时间戳和随机数字节数组的构造:

          public ULID(long timestamp, byte[] randomness) {
              if ((timestamp & TIMESTAMP_MASK) != 0) {
                  throw new IllegalArgumentException("Invalid timestamp");
              }
              if (Objects.isNull(randomness) || RANDOMNESS_BYTE_LEN != randomness.length) {
                  throw new IllegalArgumentException("Invalid randomness");
              }
              long msb = 0;
              long lsb = 0;
              // 时间戳左移16位,低位补零准备填入部分随机数位,即16_bit_uint_random
              msb |= timestamp << 16;
              // randomness[0]左移0位填充到16_bit_uint_random的高8位,randomness[1]填充到16_bit_uint_random的低8位
              msb |= (long) (randomness[0x0] & 0xff) << 8;
              // randomness[1]填充到16_bit_uint_random的低8位
              msb |= randomness[0x1] & 0xff;
              // randomness[2] ~ randomness[9]填充到剩余的bit_uint_random中,要左移相应的位
              lsb |= (long) (randomness[0x2] & 0xff) << 56;
              lsb |= (long) (randomness[0x3] & 0xff) << 48;
              lsb |= (long) (randomness[0x4] & 0xff) << 40;
              lsb |= (long) (randomness[0x5] & 0xff) << 32;
              lsb |= (long) (randomness[0x6] & 0xff) << 24;
              lsb |= (long) (randomness[0x7] & 0xff) << 16;
              lsb |= (long) (randomness[0x8] & 0xff) << 8;
              lsb |= (randomness[0x9] & 0xff);
              this.msb = msb;
              this.lsb = lsb;
          }
          

          这是完全按照规范的二进制布局编写代码,可以像UUID的构造那样精简一下:

          long msb = 0;
          long lsb = 0;
          byte[] data = new byte[16];
          byte[] ts = ByteBuffer.allocate(8).putLong(0, timestamp << 16).array();
          System.arraycopy(ts, 0, data, 0, 6);
          System.arraycopy(randomness, 0, data, 6, 10);
          for (int i = 0; i < 8; i++)
              msb = (msb << 8) | (data[i] & 0xff);
          for (int i = 8; i < 16; i++)
              lsb = (lsb << 8) | (data[i] & 0xff);
          

          接着可以简单添加下面几个方法:

          public long getMostSignificantBits() {
              return this.msb;
          }
          public long getLeastSignificantBits() {
              return this.lsb;
          }
          // 静态工厂方法,由UUID实例生成ULID实例
          public static ULID fromUUID(UUID uuid) {
              return new ULID(uuid.getMostSignificantBits(), uuid.getLeastSignificantBits());
          }
          // 实例方法,当前ULID实例转换为UUID实例
          public UUID toUUID() {
              return new UUID(this.msb, this.lsb);
          }
          

          接着需要覆盖toString()方法,这是ULID的核心方法,需要通过Crockford Base32编码生成规范的字符串表示形式。由于128 bit要映射为26 char,这里可以考虑分三段进行映射,也就是48 bit时间戳映射为10 char,剩下的两部分随机数分别做40 bit8 char的映射,加起来就是26 char

           |----------|      |----------------|
            Timestamp     Randomness[split to 2 part]
          48bit => 10char    80bit => 16char
          

          编写方法:

          /**
            * Default alphabet of ULID
            */
          private static final char[] DEFAULT_ALPHABET = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C',
                  'D', 'E', 'F', 'G', 'H', 'J', 'K', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z'};
          /**
            * Default alphabet mask
            */
          private static final int DEFAULT_ALPHABET_MASK = 0b11111;
          /**
            * Character num of ULID
            */
          private static final int ULID_CHAR_LEN = 0x1a;
          @Override
          public String toString() {
              return toCanonicalString(DEFAULT_ALPHABET);
          }
          public String toCanonicalString(char[] alphabet) {
              char[] chars = new char[ULID_CHAR_LEN];
              long timestamp = this.msb >> 16;
              // 第一部分随机数取msb的低16位+lsb的高24位,这里(msb & 0xffff) << 24作为第一部分随机数的高16位,所以要左移24位
              long randMost = ((this.msb & 0xffffL) << 24) | (this.lsb >>> 40);
              // 第二部分随机数取lsb的低40位,0xffffffffffL是2^40-1
              long randLeast = (this.lsb & 0xffffffffffL);
              // 接着每个部分的偏移量和DEFAULT_ALPHABET_MASK(31)做一次或运算就行,就是char[index] = alphabet[(part >> (step * index)) & 31]
              chars[0x00] = alphabet[(int) (timestamp >>> 45 & DEFAULT_ALPHABET_MASK)];
              chars[0x01] = alphabet[(int) (timestamp >>> 40 & DEFAULT_ALPHABET_MASK)];
              chars[0x02] = alphabet[(int) (timestamp >>> 35 & DEFAULT_ALPHABET_MASK)];
              chars[0x03] = alphabet[(int) (timestamp >>> 30 & DEFAULT_ALPHABET_MASK)];
              chars[0x04] = alphabet[(int) (timestamp >>> 25 & DEFAULT_ALPHABET_MASK)];
              chars[0x05] = alphabet[(int) (timestamp >>> 20 & DEFAULT_ALPHABET_MASK)];
              chars[0x06] = alphabet[(int) (timestamp >>> 15 & DEFAULT_ALPHABET_MASK)];
              chars[0x07] = alphabet[(int) (timestamp >>> 10 & DEFAULT_ALPHABET_MASK)];
              chars[0x08] = alphabet[(int) (timestamp >>> 5 & DEFAULT_ALPHABET_MASK)];
              chars[0x09] = alphabet[(int) (timestamp & DEFAULT_ALPHABET_MASK)];
              chars[0x0a] = alphabet[(int) (randMost >>> 35 & DEFAULT_ALPHABET_MASK)];
              chars[0x0b] = alphabet[(int) (randMost >>> 30 & DEFAULT_ALPHABET_MASK)];
              chars[0x0c] = alphabet[(int) (randMost >>> 25 & DEFAULT_ALPHABET_MASK)];
              chars[0x0d] = alphabet[(int) (randMost >>> 20 & DEFAULT_ALPHABET_MASK)];
              chars[0x0e] = alphabet[(int) (randMost >>> 15 & DEFAULT_ALPHABET_MASK)];
              chars[0x0f] = alphabet[(int) (randMost >>> 10 & DEFAULT_ALPHABET_MASK)];
              chars[0x10] = alphabet[(int) (randMost >>> 5 & DEFAULT_ALPHABET_MASK)];
              chars[0x11] = alphabet[(int) (randMost & DEFAULT_ALPHABET_MASK)];
              chars[0x12] = alphabet[(int) (randLeast >>> 35 & DEFAULT_ALPHABET_MASK)];
              chars[0x13] = alphabet[(int) (randLeast >>> 30 & DEFAULT_ALPHABET_MASK)];
              chars[0x14] = alphabet[(int) (randLeast >>> 25 & DEFAULT_ALPHABET_MASK)];
              chars[0x15] = alphabet[(int) (randLeast >>> 20 & DEFAULT_ALPHABET_MASK)];
              chars[0x16] = alphabet[(int) (randLeast >>> 15 & DEFAULT_ALPHABET_MASK)];
              chars[0x17] = alphabet[(int) (randLeast >>> 10 & DEFAULT_ALPHABET_MASK)];
              chars[0x18] = alphabet[(int) (randLeast >>> 5 & DEFAULT_ALPHABET_MASK)];
              chars[0x19] = alphabet[(int) (randLeast & DEFAULT_ALPHABET_MASK)];
              return new String(chars);
          }
          

          上面的方法toCanonicalString()看起来很"臃肿",但是能保证性能比较高。接着添加常用的工厂方法:

          public static ULID ulid() {
              return ulid(System::currentTimeMillis, len -> {
                  byte[] bytes = new byte[len];
                  ThreadLocalRandom.current().nextBytes(bytes);
                  return bytes;
              });
          }
          public static ULID ulid(Supplier<Long> timestampProvider,
                                  IntFunction<byte[]> randomnessProvider) {
              return new ULID(timestampProvider.get(), randomnessProvider.apply(RANDOMNESS_BYTE_LEN));
          }
          

          默认使用ThreadLocalRandom生成随机数,如果是JDK17以上,还可以选用更高性能的新型PRNG实现,对应接口是RandomGenerator,默认实现是L32X64MixRandom。编写一个main方法运行一下:

          public static void main(String[] args) {
              System.out.println(ULID.ulid());
          }
          // 某次执行结果
          01GFGGMBFGB5WKXBN7S84ATRDG
          

          最后实现"单调递增"的ULID构造,先提供一个"增长"方法:

          /**
            * The least significant 64 bits increase overflow, 0xffffffffffffffffL + 1
            */
          private static final long OVERFLOW = 0x0000000000000000L;
          public ULID increment() {
              long msb = this.msb;
              long lsb = this.lsb + 1;
              if (lsb == OVERFLOW) {
                  msb += 1;
              }
              return new ULID(msb, lsb);
          }
          

          其实就是低位加1,溢出后高位加1。接着添加一个静态内部子类和响应方法如下:

          // 构造函数
          public ULID(ULID other) {
              this.msb = other.msb;
              this.lsb = other.lsb;
          }
          public static byte[] defaultRandomBytes(int len) {
              byte[] bytes = new byte[len];
              ThreadLocalRandom.current().nextBytes(bytes);
              return bytes;
          }
          public static MonotonicULIDSpi monotonicUlid() {
              return monotonicUlid(System::currentTimeMillis, ULID::defaultRandomBytes);
          }
          public static MonotonicULIDSpi monotonicUlid(Supplier&lt;Long&gt; timestampProvider,
                                                        IntFunction&lt;byte[]&gt; randomnessProvider) {
              return new MonotonicULID(timestampProvider, randomnessProvider, timestampProvider.get(),
                      randomnessProvider.apply(RANDOMNESS_BYTE_LEN));
          }
          // @SPI MonotonicULID
          public interface MonotonicULIDSpi {
            ULID next();
          }
          private static class MonotonicULID extends ULID implements MonotonicULIDSpi {
              @Serial
              private static final long serialVersionUID = -9158161806889605101L;
              private volatile ULID lastULID;
              private final Supplier&lt;Long&gt; timestampProvider;
              private final IntFunction&lt;byte[]&gt; randomnessProvider;
              public MonotonicULID(Supplier&lt;Long&gt; timestampProvider,
                                    IntFunction&lt;byte[]&gt; randomnessProvider,
                                    long timestamp,
                                    byte[] randomness) {
                  super(timestamp, randomness);
                  this.timestampProvider = timestampProvider;
                  this.randomnessProvider = randomnessProvider;
                  this.lastULID = new ULID(timestamp, randomness);
              }
              // 这里没设计好,子类缓存了上一个节点,需要重写一下increment方法,父类可以移除此方法 
              @Override
              public ULID increment() {
                  long newMsb = lastULID.msb;
                  long newLsb = lastULID.lsb + 1;
                  if (newLsb == OVERFLOW) {
                      newMsb += 1;
                  }
                  return new ULID(newMsb, newLsb);
              }
              @Override
              public synchronized ULID next() {
                  long lastTimestamp = lastULID.getTimestamp();
                  long timestamp = getTimestamp();
                  // 这里做了一个恒为true的判断,后面再研读其他代码进行修改
                  if (lastTimestamp &gt;= timestamp || timestamp - lastTimestamp &lt;= 1000) {
                      this.lastULID = this.increment();
                  } else {
                      this.lastULID = new ULID(timestampProvider.get(), randomnessProvider.apply(RANDOMNESS_BYTE_LEN));
                  }
                  return new ULID(this.lastULID);
              }
          }
          

          关于上一个ULID和下一个ULID之间的时间戳判断,这里从规范文件没看出细节实现,先简单做一个永远为true的分支判断,后面再深入研究然后修改。使用方式如下:

          public static void main(String[] args) {
              MonotonicULIDSpi spi = ULID.monotonicUlid();
              System.out.println(spi.next());
              System.out.println(spi.next());
              System.out.println(spi.next());
              System.out.println(spi.next());
          }
          // 某次运行输出
          01GFGASXXQXD5ZJ26PKSCFGNPF
          01GFGASXXQXD5ZJ26PKSCFGNPG
          01GFGASXXQXD5ZJ26PKSCFGNPH
          01GFGASXXQXD5ZJ26PKSCFGNPJ
          

          这里为了更加灵活,没有采用全局静态属性缓存上一个ULID实例,而是简单使用继承方式实现。

          ULID性能评估

          引入JMH做了一个简单的性能测试,代码如下:

          @Fork(1)
          @Threads(10)
          @State(Scope.Benchmark)
          @BenchmarkMode(Mode.Throughput)
          @Warmup(iterations = 1, time = 1)
          @Measurement(iterations = 5, time = 3)
          @OutputTimeUnit(TimeUnit.MILLISECONDS)
          public class BenchmarkRunner {
              private static ULID.MonotonicULIDSpi SPI;
              @Setup
              public void setup() {
                  SPI = ULID.monotonicUlid();
              }
              @Benchmark
              public UUID createUUID() {
                  return UUID.randomUUID();
              }
              @Benchmark
              public String createUUIDToString() {
                  return UUID.randomUUID().toString();
              }
              @Benchmark
              public ULID createULID() {
                  return ULID.ulid();
              }
              @Benchmark
              public String createULIDToString() {
                  return ULID.ulid().toString();
              }
              @Benchmark
              public ULID createMonotonicULID() {
                  return SPI.next();
              }
              @Benchmark
              public String createMonotonicULIDToString() {
                  return SPI.next().toString();
              }
              public static void main(String[] args) throws Exception {
                  new Runner(new OptionsBuilder().build()).run();
              }
          }
          

          某次测试报告如下(开发环境Intel 6700K 4C8T 32G,使用OpenJDK-19):

          Benchmark                                     Mode  Cnt       Score       Error   Units
          BenchmarkRunner.createMonotonicULID          thrpt    5   20335.118 ±  1656.772  ops/ms
          BenchmarkRunner.createMonotonicULIDToString  thrpt    5   13091.975 ±  1207.403  ops/ms
          BenchmarkRunner.createULID                   thrpt    5  152574.703 ± 23740.021  ops/ms
          BenchmarkRunner.createULIDToString           thrpt    5   51559.800 ±  3608.085  ops/ms
          BenchmarkRunner.createUUID                   thrpt    5     819.890 ±    15.508  ops/ms
          BenchmarkRunner.createUUIDToString           thrpt    5     786.072 ±    44.770  ops/ms

          小结

          本文就ULID的规范进行解读,通过规范和参考现有类库进行ULIDJava实现。ULID适用于一些"排序ID"生成或者需要"单调ID"生成的场景,可以考虑用于数据库键设计、顺序号设计等等场景。从实现上看它性能会优于UUID(特别是单调ULID,因为不需要重新获取随机数部分,吞吐量会提升一个数量级)。

          Demo项目仓库:

          • framework-mesh/ulid4jhttps://github.com/zjcscut/framework-mesh/tree/master/ulid4j

          参考资料:

          crockford-base32

          ulid-creator

          以上就是java语言自行实现ULID过程底层原理详解的详细内容,更多关于java ULID底层原理的资料请关注自由互联其它相关文章!

          上一篇:Spring超详细讲解AOP面向切面
          下一篇:没有了
          网友评论