生成单调有序的 ULID 字符串

功能说明

ULID 是一种 128 位标识符：高 48 位是毫秒时间戳，低 80 位是随机数，编码成 26 个 Crockford Base32 字符。由于时间戳在高位，ULID 按字符串排序就近似按创建时间排序，适合做主键、事件 ID 或日志关联 ID。

这段代码不依赖第三方库，生成 26 位字符串，并在同一毫秒内让随机部分递增，保证同一进程产生的 ID 严格单调，避免数据库索引因随机主键而频繁分裂。

关键代码

new_ulid 读取 SystemTime 的毫秒数，然后在 STATE 互斥锁中比较上一次的时间戳。如果仍在同一毫秒，就把上次随机数加一；否则用 splitmix64 从时间戳、计数器和常量混合出 80 位随机数。

最终值由 (millis << 80) | randomness 组成，再由 encode 每次取低 5 位映射到 Crockford 字母表，共 26 个字符。main 断言长度、字典序递增和字符集合合法。

使用注意

splitmix64 是伪随机函数，不是密码学安全随机源；如果需要不可预测性，应接入操作系统随机源。进程重启后计数器归零，同一毫秒内可能与旧进程产生重复，生产环境应结合机器 ID 或持久化序列。

系统时钟回拨会破坏跨毫秒的单调性，代码没有检测这种情况。80 位随机数加一溢出后会回绕，概率极低但理论上存在。Crockford Base32 解码时通常把 I/L 映射为 1、O 映射为 0，本实现只负责生成。

验证方式

示例连续生成两个 ID，断言长度都是 26、第一个字典序小于第二个，且所有字符都在 0123456789ABCDEFGHJKMNPQRSTVWXYZ 中。随后生成 100 个 ID，用 windows(2) 检查严格递增。可以快速连续生成上万个，确认同一毫秒内的单调逻辑持续生效。

代码示例

use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};

const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
const MAX_RANDOM: u128 = (1u128 << 80) - 1;

static STATE: Mutex<Option<(u64, u128)>> = Mutex::new(None);
static COUNTER: AtomicU64 = AtomicU64::new(0);

fn splitmix64(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
    let mut value = *state;
    value = (value ^ (value >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    value = (value ^ (value >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    value ^ (value >> 31)
}

fn encode(mut value: u128, length: usize) -> String {
    let mut characters = vec![b'0'; length];
    for index in (0..length).rev() {
        characters[index] = ALPHABET[(value & 31) as usize];
        value >>= 5;
    }
    String::from_utf8(characters).expect("alphabet is ASCII")
}

fn new_ulid() -> String {
    let millis = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .expect("system clock is before the Unix epoch")
        .as_millis() as u64;

    let mut guard = STATE.lock().expect("ULID state poisoned");
    let randomness = match *guard {
        Some((last_millis, last_random)) if last_millis == millis => {
            last_random.wrapping_add(1) & MAX_RANDOM
        }
        _ => {
            let sequence = COUNTER.fetch_add(1, Ordering::Relaxed);
            let mut seed = millis ^ sequence.rotate_left(17) ^ 0x9E37_79B9_7F4A_7C15;
            let high = splitmix64(&mut seed);
            let low = splitmix64(&mut seed);
            (((high as u128) << 64) | (low as u128)) >> 48
        }
    };
    *guard = Some((millis, randomness));

    let value = ((millis as u128) << 80) | randomness;
    encode(value, 26)
}

fn main() {
    let first = new_ulid();
    let second = new_ulid();
    println!("{first}\n{second}");
    assert_eq!(first.len(), 26);
    assert!(first < second, "ULIDs should sort in creation order");
    assert!(first.bytes().all(|byte| ALPHABET.contains(&byte)));

    let identifiers: Vec<String> = (0..100).map(|_| new_ulid()).collect();
    assert!(identifiers.windows(2).all(|pair| pair[0] < pair[1]));
}