Zenn
Closed10

ULIDの実装 - ulid-rsを読む

Rust
コードリーディング
ULID
kyoheiukyoheiu

ULIDはTimeを表す48bitとランダムな80bitから作られる128bitのsortable identifier。

128-bit compatibility with UUID
1.21e+24 unique ULIDs per millisecond
Lexicographically sortable!
Canonically encoded as a 26 character string, as opposed to the 36 character UUID
Uses Crockford's base32 for better efficiency and readability (5 bits per character)
Case insensitive
No special characters (URL safe)
Monotonic sort order (correctly detects and handles the same millisecond)
https://github.com/ulid/spec

くわしくは上記リポジトリ。
たくさんの言語で実装されているが、今回はRustのulid-rsを読んでいきます。理由は、自分が読める言語であることと、なんとなくわかりやすそうだったので。目標は、別言語で自力で実装すること。

impl Ulid {
    pub fn new() -> Ulid {
        Ulid::from_datetime(SystemTime::now())
    }
    pub fn with_source<R: rand::Rng>(source: &mut R) -> Ulid {
        Ulid::from_datetime_with_source(SystemTime::now(), source)
    }
    pub fn from_datetime_with_source<R>(datetime: SystemTime, source: &mut R) -> Ulid
    where
        R: rand::Rng,
    {
        let timestamp = datetime
            .duration_since(SystemTime::UNIX_EPOCH)
            .unwrap_or(Duration::ZERO)
            .as_millis();
        let timebits = (timestamp & bitmask!(Self::TIME_BITS)) as u64;

        let msb = timebits << 16 | u64::from(source.gen::<u16>());
        let lsb = source.gen::<u64>();
        Ulid::from((msb, lsb))
    }

なので、実質Ulid::new() = Ulid::from_datetime_with_source(SystemTime::now(), &mut rng)。

kyoheiukyoheiu
use rand::prelude::*;
use std::time::SystemTime;
use ulid::Ulid;

fn main() {
    let mut rng = StdRng::from_entropy();
    let ulid = Ulid::from_datetime_with_source(SystemTime::now(), &mut rng);
    println!("{}", ulid.to_string());
}

サンプルのmain関数を上記のようにして、git cloneしたライブラリの中にprintln!を埋め込みまくることで愚直に表示していく。

kyoheiukyoheiu
        let timestamp = datetime
            .duration_since(SystemTime::UNIX_EPOCH)
            .unwrap_or(Duration::ZERO)
            .as_millis();

まずここでは、UNIX TIMEをmillisで取得している。取得できなければ0としている。

1662408777120 timestamp
kyoheiukyoheiu
        let timebits = (timestamp & bitmask!(Self::TIME_BITS)) as u64;

このbitmask!は何回も出てくるので、まずここから。

macro_rules! bitmask {
    ($len:expr) => {
        ((1 << $len) - 1)
    };
}

integerをとり、1をそのinteger分シフトして1を引く…というマクロ。デバッグしてみる。

    let bitmask: u64 = ulid::bitmask!(40);
    println!("{:b}", bitmask);

1111111111111111111111111111111111111111

つまり全てのbitが1の、任意の長さのビットマスクを作るマクロですね。
気をつけないといけないのは、u64などと型をきちんと指定してあげないと、overflowでパニックを起こす点。

thread 'main' panicked at 'attempt to shift left with overflow', src/main.rs:9:19
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

型を指定しない場合、コンパイラがi32と推測してくるのでこうなってしまう。何桁ほしいのかをちゃんと指定すれば問題なし。

で、そのビットマスクとtimestampを&演算子でつないでいるので、timebitsというのは64bitで表されたtimestampということになる。

11000001100001111010100110101000100001001 timebits

ただしleading 0sは:bだけでは表示されないので注意。

kyoheiukyoheiu
        let msb = timebits << 16 | u64::from(source.gen::<u16>());
        // println!("{:b} msb", msb);
        let lsb = source.gen::<u64>();
        // println!("{:b} lsb", lsb);

残りのここは最初何をやっているのかよくわからなかったのだけど、要するに、残りの80bit = randomnessを担保している部分を、16bitと64bitに分けて作って入れている、ということらしい。

kyoheiukyoheiu
impl From<(u64, u64)> for Ulid {
    fn from((msb, lsb): (u64, u64)) -> Self {
        let base = u128::from(msb) << 64 | u128::from(lsb);
        Ulid(base)
    }
}

そしてここに飛ぶ。
msbとlsbに分けているのは、それぞれをu64として扱うため（多分）。
まずmsbを左シフトしてから、u128として読み込んだlsbとOR演算子でつないで、完成形の128bitのULIDを生成している。

1100000110000111101010011010100010000100100100001010011000010110110100000111101100001101110011100100111110000001010001110 base

※leading 0sは非表示。

kyoheiukyoheiu

ULIDは通常01GC7N6M894562V87P3EE9Y0MEといった形でよく見かけるが、これはbase32にエンコーディングされた見かけ。
このエンコード処理はbase32.rsに定義されている。

pub fn encode_to(mut value: u128, buffer: &mut [u8]) -> Result<usize, EncodeError> {
    // NOTE: This function can't be made const because mut refs aren't allowed for some reason

    if buffer.len() < ULID_LEN {
        return Err(EncodeError::BufferTooSmall);
    }

    for i in 0..ULID_LEN {
        buffer[ULID_LEN - 1 - i] = ALPHABET[(value & 0x1f) as usize];
        value >>= 5;
    }

    Ok(ULID_LEN)
}

引数のbufferは通常[u8, ULID_LEN]（ULID_LEN = 26）として呼ばれるので、このエラーはほぼ発生しないタイプのエラーじゃないかなと思われる。

メインのforループについて。bufferの後ろから文字を詰めていくスタイル。
これをデバッグプリントしてみると…

    for i in 0..ULID_LEN {
        let v = (value & 0x1f) as usize;
        println!("{:05b} v", v);
        buffer[ULID_LEN - 1 - i] = ALPHABET[v];
        value >>= 5;
    }

1100000110000111101100011110110011101111111010110101011010111011011101001010100100001110010001101010101000010001010101000 base
01000 v
10101 v
01000 v
...

となる。つまり11111と＆でつなぐことで、右のほうから５桁ずつ切り出して5bitのusizeを取り出しているというわけですね。そのusizeにより、

const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";

と定義されている使用文字から一つをとってくることで、エンコードしている。
たとえば01000はusizeでいうと8で、ALPHABET[8]は…8なので、このULIDの一番右の文字は

01GC7P7PEZTTPQDTAJ3J6N88N8

ちゃんと8になっている。なるほどー。

128bitなので最後のほうは足りてないということになるはずだが、それはあんまり気にしなくていいやつなんですかね。

kyoheiukyoheiu

https://github.com/kyoheiu/ulideno

Deno向けのシンプルなULID生成ライブラリを作ってみた。
Rustのようにu128なんて便利な型が用意されているわけでもないので、最初はstring型でtimestamp部分とrandom部分の疑似バイナリを扱っていたけれど、やっぱりなんか気持ちが良くないので、bigintでなるべく処理するようにしたらまあまあコードがすっきりしたような気がします。

このスクラップは2023/06/20にクローズされました