java語言自行實現(xiàn)ULID過程底層原理詳解

更新時間：2022年10月17日 09:58:09 作者：Throwable

這篇文章主要為大家介紹了java語言自行實現(xiàn)ULID過程底層原理詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

前提

最近發(fā)現(xiàn)各個頻道推薦了很多ULID相關(guān)文章，這里對ULID的規(guī)范文件進(jìn)行解讀，并且基于Java語言自行實現(xiàn)ULID，通過此實現(xiàn)過程展示ULID的底層原理。

ULID出現(xiàn)的背景

ULID全稱是Universally Unique Lexicographically Sortable Identifier，直譯過來就是通用唯一按字典排序的標(biāo)識符，它的原始倉庫是https://github.com/ulid/javascript，該項目由前端開發(fā)者alizain發(fā)起，基于JavaScript語言編寫。從項目中的commit歷史來看已經(jīng)超過了5年，理論上得到充分的實踐驗證。ULID出現(xiàn)的原因是一些開發(fā)者認(rèn)為主流的UUID方案在許多場景下可能不是最優(yōu)的，存在下面的原因：

UUID不是128 bit隨機(jī)編碼（由128 bit隨機(jī)數(shù)通過編碼生成字符串）的最高效實現(xiàn)方式
UUID的v1/v2實現(xiàn)在許多環(huán)境中是不切實際的，因為這兩個版本的的實現(xiàn)需要訪問唯一的、穩(wěn)定的MAC地址
UUID的v3/v5實現(xiàn)需要唯一的種子，并且產(chǎn)生隨機(jī)分布的ID，這可能會導(dǎo)致在許多數(shù)據(jù)結(jié)構(gòu)中出現(xiàn)碎片
UUID的v4除了隨機(jī)性之外不需要提供其他信息，隨機(jī)性可能會在許多數(shù)據(jù)結(jié)構(gòu)中導(dǎo)致碎片

這里概括一下就是：UUID的v1/v2實現(xiàn)依賴唯一穩(wěn)定MAC地址不現(xiàn)實，v3/v4/v5實現(xiàn)因為隨機(jī)性產(chǎn)生的ID會"碎片化"。

基于此提出了ULID，它用起來像這樣：

ulid() // 01ARZ3NDEKTSV4RRFFQ69G5FAV

ULID的特點如下：

設(shè)計為128 bit大小，與UUID兼容
每毫秒生成1.21e+24個唯一的ULID（高性能）
按字典順序（字母順序）排序
標(biāo)準(zhǔn)編碼為26個字符的字符串，而不是像UUID那樣需要36個字符
使用Crockford的base32算法來提高效率和可讀性（每個字符5 bit）
不區(qū)分大小寫
沒有特殊字符串（URL安全，不需要進(jìn)行二次URL編碼）
單調(diào)排序（正確地檢測并處理相同的毫秒，所謂單調(diào)性，就是毫秒數(shù)相同的情況下，能夠確保新的ULID隨機(jī)部分的在最低有效位上加1位）

ULID規(guī)范

下面的ULID規(guī)范在ULID/javascript類庫中實現(xiàn)，此二進(jìn)制格式目前沒有在JavaScript中實現(xiàn)：

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

組成

時間戳(Timestamp)

占據(jù)48 bit(high)
本質(zhì)是UNIX-time，單位為毫秒
直到公元10889年才會用完

隨機(jī)數(shù)(Randomness)

占據(jù)80 bit(low)
如果可能的話，使用加密安全的隨機(jī)源

排序

"最左邊"的字符必須排在最前面，"最右邊"的字符排在最后（詞法順序，或者俗稱的字典排序），并且所有字符必須使用默認(rèn)的ASCII字符集。在相同的毫秒（時間戳）內(nèi)，無法保證排序順序。

規(guī)范的表示形式

ULID規(guī)范的字符串表示形式如下：

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

也就是：

時間戳占據(jù)高（左邊）10個（編碼后的）字符
隨機(jī)數(shù)占據(jù)低（右邊）16個（編碼后的）字符

ULID規(guī)范的字符串表示形式的長度是確定的，共占據(jù)26個字符。

編碼

使用Crockford Base32編碼算法，這個編碼算法的字母表如下：

0123456789ABCDEFGHJKMNPQRSTVWXYZ

該字母表排除了I、 L、O、U字母，目的是避免混淆和濫用。此算法實現(xiàn)不難，它的官網(wǎng)有詳細(xì)的算法說明（https://www.crockford.com/base32.html）：

單調(diào)性

（如果啟用了單調(diào)性這個特性為前提下）當(dāng)在相同的毫秒內(nèi)生成多個ULID時，可以保證排序的順序。也就是說，如果檢測到相同的毫秒，則隨機(jī)分量在最低有效位上加1位（帶進(jìn)位）。例如：

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

溢出錯誤處理

從技術(shù)實現(xiàn)上來看，26個字符的Base32編碼字符串可以包含130 bit信息，而ULID只包含128 bit信息，所以該編碼算法是能完全滿足ULID的需要?；?code>Base32編碼能夠生成的最大的合法ULID其實就是7ZZZZZZZZZZZZZZZZZZZZZZZZZ，并且使用的時間戳為epoch time的281474976710655或者說2 ^ 48 - 1。對于任何對大于此值的ULID進(jìn)行解碼或編碼的嘗試都應(yīng)該被所有實現(xiàn)拒絕，以防止溢出錯誤。

二進(jìn)制布局

二進(jìn)制布局的多個部分被編碼為16 byte，每個部分都以最高字節(jié)優(yōu)先（網(wǎng)絡(luò)字節(jié)序，也就是big-endian）進(jìn)行編碼，布局如下：

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標(biāo)簽引用：

<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實現(xiàn)：

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

然后調(diào)用UlidCreator#getUlid()系列方法：

// 常規(guī)
Ulid ulid = UlidCreator.getUlid();
// 單調(diào)排序
Ulid ulid = UlidCreator.getMonotonicUlid();

實現(xiàn)ULID

前面已經(jīng)提到ULID的規(guī)范，其實具體實現(xiàn)ULID就是對著規(guī)范里面的每一個小節(jié)進(jìn)行編碼實現(xiàn)。先看二進(jìn)制布局，由于使用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的組成來看，可以提供一個入?yún)闀r間戳和隨機(jī)數(shù)字節(jié)數(shù)組的構(gòu)造：

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位，低位補(bǔ)零準(zhǔn)備填入部分隨機(jī)數(shù)位，即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中，要左移相應(yīng)的位
    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;
}

這是完全按照規(guī)范的二進(jìn)制布局編寫代碼，可以像UUID的構(gòu)造那樣精簡一下：

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;
}
// 靜態(tài)工廠方法，由UUID實例生成ULID實例
public static ULID fromUUID(UUID uuid) {
    return new ULID(uuid.getMostSignificantBits(), uuid.getLeastSignificantBits());
}
// 實例方法，當(dāng)前ULID實例轉(zhuǎn)換為UUID實例
public UUID toUUID() {
    return new UUID(this.msb, this.lsb);
}

接著需要覆蓋toString()方法，這是ULID的核心方法，需要通過Crockford Base32編碼生成規(guī)范的字符串表示形式。由于128 bit要映射為26 char，這里可以考慮分三段進(jìn)行映射，也就是48 bit時間戳映射為10 char，剩下的兩部分隨機(jī)數(shù)分別做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;
    // 第一部分隨機(jī)數(shù)取msb的低16位+lsb的高24位，這里(msb & 0xffff) << 24作為第一部分隨機(jī)數(shù)的高16位，所以要左移24位
    long randMost = ((this.msb & 0xffffL) << 24) | (this.lsb >>> 40);
    // 第二部分隨機(jī)數(shù)取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));
}

默認(rèn)使用ThreadLocalRandom生成隨機(jī)數(shù)，如果是JDK17以上，還可以選用更高性能的新型PRNG實現(xiàn)，對應(yīng)接口是RandomGenerator，默認(rèn)實現(xiàn)是L32X64MixRandom。編寫一個main方法運行一下：

public static void main(String[] args) {
    System.out.println(ULID.ulid());
}
// 某次執(zhí)行結(jié)果
01GFGGMBFGB5WKXBN7S84ATRDG

最后實現(xiàn)"單調(diào)遞增"的ULID構(gòu)造，先提供一個"增長"方法：

/**
  * 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。接著添加一個靜態(tài)內(nèi)部子類和響應(yīng)方法如下：

// 構(gòu)造函數(shù)
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);
    }
    // 這里沒設(shè)計好，子類緩存了上一個節(jié)點，需要重寫一下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的判斷，后面再研讀其他代碼進(jìn)行修改
        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);
    }
}

關(guān)于上一個ULID和下一個ULID之間的時間戳判斷，這里從規(guī)范文件沒看出細(xì)節(jié)實現(xiàn)，先簡單做一個永遠(yuǎn)為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

這里為了更加靈活，沒有采用全局靜態(tài)屬性緩存上一個ULID實例，而是簡單使用繼承方式實現(xiàn)。

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();
    }
}

某次測試報告如下（開發(fā)環(huán)境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

小結(jié)

本文就ULID的規(guī)范進(jìn)行解讀，通過規(guī)范和參考現(xiàn)有類庫進(jìn)行ULID的Java實現(xiàn)。ULID適用于一些"排序ID"生成或者需要"單調(diào)ID"生成的場景，可以考慮用于數(shù)據(jù)庫鍵設(shè)計、順序號設(shè)計等等場景。從實現(xiàn)上看它性能會優(yōu)于UUID（特別是單調(diào)ULID，因為不需要重新獲取隨機(jī)數(shù)部分，吞吐量會提升一個數(shù)量級）。

Demo項目倉庫：