前提
最近发现各个频道推荐了很多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
随机数通过编码生成字符串)的最高效实现方式 -
UUID
的v1/v2
实现在许多环境中是不切实际的,因为这两个版本的的实现需要访问唯一的、稳定的MAC
地址 -
UUID
的v3/v5
实现需要唯一的种子,并且产生随机分布的ID
,这可能会导致在许多数据结构中出现碎片 -
UUID
的v4
除了随机性之外不需要提供其他信息,随机性可能会在许多数据结构中导致碎片
这里概括一下就是:UUID
的v1/v2
实现依赖唯一稳定MAC
地址不现实,v3/v4/v5
实现因为随机性产生的ID
会”碎片化”。
基于此提出了ULID
,它用起来像这样:
ulid() // 01ARZ3NDEKTSV4RRFFQ69G5FAV
ULID
的特点如下:
- 设计为
128 bit
大小,与UUID
兼容 - 每毫秒生成
1.21e+24
个唯一的ULID
(高性能) - 按字典顺序(字母顺序)排序
- 标准编码为
26
个字符的字符串,而不是像UUID
那样需要36
个字符 - 使用
Crockford
的base32
算法来提高效率和可读性(每个字符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
该字母表排除了I
、 L
、O
、U
字母,目的是避免混淆和滥用。此算法实现不难,它的官网有详细的算法说明(https://www.crockford.com/base32.html):
单调性
(如果启用了单调性这个特性为前提下)当在相同的毫秒内生成多个ULID
时,可以保证排序的顺序。也就是说,如果检测到相同的毫秒,则随机分量在最低有效位上加1
位(带进位)。例如:
monotonicUlid() // 01BX5ZZKBKACTAV9WEVGEMMVRZ monotonicUlid() // 01BX5ZZKBKACTAV9WEVGEMMVS0
溢出错误处理
从技术实现上来看,26
个字符的Base32
编码字符串可以包含130 bit
信息,而ULID
只包含128 bit
信息,所以该编码算法是能完全满足ULID
的需要。基于Base32
编码能够生成的最大的合法ULID
其实就是7ZZZZZZZZZZZZZZZZZZZZZZZZZ
,并且使用的时间戳为epoch time
的281474976710655
或者说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
标签引用:
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
实现:
com.github.f4b6a3 ulid-creator 5.0.2
然后调用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
这是完全按照规范的二进制布局编写代码,可以像UUID
的构造那样精简一下:
long msb = 0; long lsb = 0; byte[] data = new byte[16]; byte[] ts = ByteBuffer.allocate(8).putLong(0, timestamp
接着可以简单添加下面几个方法:
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 bit
到8 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) >> 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(SuppliertimestampProvider, IntFunction 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<Long> timestampProvider, IntFunction<byte[]> 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<Long> timestampProvider; private final IntFunction<byte[]> randomnessProvider; public MonotonicULID(Supplier<Long> timestampProvider, IntFunction<byte[]> 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 >= timestamp || timestamp - lastTimestamp <= 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
的规范进行解读,通过规范和参考现有类库进行ULID
的Java
实现。ULID
适用于一些”排序ID”生成或者需要”单调ID”生成的场景,可以考虑用于数据库键设计、顺序号设计等等场景。从实现上看它性能会优于UUID
(特别是单调ULID
,因为不需要重新获取随机数部分,吞吐量会提升一个数量级)。
Demo
项目仓库:
-
framework-mesh/ulid4j
:https://github.com/zjcscut/framework-mesh/tree/master/ulid4j
参考资料:
以上就是java语言自行实现ULID过程底层原理详解的详细内容,更多关于java ULID底层原理的资料请关注IT俱乐部其它相关文章!