| 1 | use std::cell::Cell; |
| 2 | |
| 3 | const ALPHABET: &[u8; 32] = b"0123456789abcdefghjkmnpqrstvwxyz"; |
| 4 | |
| 5 | thread_local! { |
| 6 | /// The millisecond and counter of the last id made, to keep ids made in |
| 7 | /// the same millisecond in order. |
| 8 | static LAST: Cell<(u64, u16)> = const { Cell::new((0, 0)) }; |
| 9 | } |
| 10 | |
| 11 | /// A new id in [TypeID](https://github.com/jetify-com/typeid) format: a type |
| 12 | /// prefix, then a UUIDv7 in lowercase Crockford base32, such as |
| 13 | /// `att_01jb2k7x9hfq0b3zj0f5s2m8ra`. |
| 14 | /// |
| 15 | /// - The prefix says what the id refers to, so ids cannot be mixed up. |
| 16 | /// - Sorting ids as strings sorts them by creation time, which also keeps |
| 17 | /// inserts at the end of the primary-key index. |
| 18 | /// - The suffix decodes to a standard UUIDv7 for systems that want one. |
| 19 | /// |
| 20 | /// Ids made in the same millisecond by one process increase monotonically: |
| 21 | /// the UUID's 12-bit `rand_a` field is used as a counter. |
| 22 | pub fn new_id(prefix: &str, now_ms: u64) -> String { |
| 23 | let mut bytes = [0u8; 16]; |
| 24 | getrandom::getrandom(&mut bytes).expect("no source of randomness"); |
| 25 | |
| 26 | let counter = LAST.with(|last| { |
| 27 | let (last_ms, last_counter) = last.get(); |
| 28 | let counter = if now_ms == last_ms { |
| 29 | last_counter.wrapping_add(1) & 0x0fff |
| 30 | } else { |
| 31 | // Start in the lower half so there is room to count up. |
| 32 | u16::from_be_bytes([bytes[6], bytes[7]]) & 0x07ff |
| 33 | }; |
| 34 | last.set((now_ms, counter)); |
| 35 | counter |
| 36 | }); |
| 37 | |
| 38 | bytes[..6].copy_from_slice(&now_ms.to_be_bytes()[2..]); |
| 39 | bytes[6] = 0x70 | (counter >> 8) as u8; // version 7 |
| 40 | bytes[7] = counter as u8; |
| 41 | bytes[8] = 0x80 | (bytes[8] & 0x3f); // RFC 9562 variant |
| 42 | encode(prefix, bytes) |
| 43 | } |
| 44 | |
| 45 | /// The smallest id with `prefix` that could have been made at or after |
| 46 | /// `now_ms`: its time, and every other bit zero. Ids sort by time, so |
| 47 | /// `id >= id_floor(p, from) AND id < id_floor(p, until)` picks the ids made |
| 48 | /// in `[from, until)` as a range of any index that ends in the id, without |
| 49 | /// a time column. No real id ever equals one: a real id's version bits are |
| 50 | /// set. |
| 51 | pub fn id_floor(prefix: &str, now_ms: u64) -> String { |
| 52 | let mut bytes = [0u8; 16]; |
| 53 | bytes[..6].copy_from_slice(&now_ms.to_be_bytes()[2..]); |
| 54 | encode(prefix, bytes) |
| 55 | } |
| 56 | |
| 57 | fn encode(prefix: &str, bytes: [u8; 16]) -> String { |
| 58 | let value = u128::from_be_bytes(bytes); |
| 59 | let mut id = String::with_capacity(prefix.len() + 27); |
| 60 | id.push_str(prefix); |
| 61 | id.push('_'); |
| 62 | // 128 bits in 26 characters of 5 bits; the first carries only 3. |
| 63 | for index in 0..26 { |
| 64 | let shift = 125 - 5 * index; |
| 65 | id.push(ALPHABET[((value >> shift) & 31) as usize] as char); |
| 66 | } |
| 67 | id |
| 68 | } |
| 69 | |
| 70 | #[cfg(test)] |
| 71 | mod tests { |
| 72 | use super::*; |
| 73 | |
| 74 | #[test] |
| 75 | fn has_prefix_and_26_character_suffix() { |
| 76 | let id = new_id("att", 1_790_000_000_000); |
| 77 | let (prefix, suffix) = id.split_once('_').unwrap(); |
| 78 | assert_eq!(prefix, "att"); |
| 79 | assert_eq!(suffix.len(), 26); |
| 80 | assert!(suffix.bytes().all(|byte| ALPHABET.contains(&byte))); |
| 81 | // A 128-bit value never needs more than 3 bits in the first character. |
| 82 | assert!(suffix.as_bytes()[0] <= b'7'); |
| 83 | } |
| 84 | |
| 85 | #[test] |
| 86 | fn sorts_by_time_then_by_order_made() { |
| 87 | let earlier = new_id("evt", 1_790_000_000_000); |
| 88 | let later = new_id("evt", 1_790_000_000_001); |
| 89 | assert!(earlier < later); |
| 90 | |
| 91 | let same_ms: Vec<String> = (0..100).map(|_| new_id("evt", 1_790_000_000_002)).collect(); |
| 92 | assert!(same_ms.windows(2).all(|pair| pair[0] < pair[1])); |
| 93 | } |
| 94 | |
| 95 | #[test] |
| 96 | fn a_floor_bounds_the_ids_of_a_span() { |
| 97 | let from = 1_790_000_000_000; |
| 98 | let before = new_id("evt", from - 1); |
| 99 | let at = new_id("evt", from); |
| 100 | let later = new_id("evt", from + 60_000); |
| 101 | let floor = id_floor("evt", from); |
| 102 | let ceiling = id_floor("evt", from + 60_000); |
| 103 | assert_eq!(floor.len(), at.len()); |
| 104 | assert!(before < floor); |
| 105 | assert!(floor < at && at < ceiling); |
| 106 | // An id made at the very millisecond of the ceiling is past it. |
| 107 | assert!(later >= ceiling); |
| 108 | } |
| 109 | } |