Generate unique, yet sortable identifiers

Overview

ulid-lite

About

An implementation of the ULID ("Universally Unique Lexicographically Sortable Identifier") standard.

A ULID is

  • 128-bit compatible 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)

Usage

From the command line

The bundled application generates a ULID and prints it to stdout:

$ ulid
01F5QNHN4G55VHQHA8XG1N6H9H

From Rust

Here is a minimal application that uses this crate:

use libc;
use ulid_lite::ulid;

fn main() {
    unsafe {
        let now = libc::time(0 as *mut _);
        let now_u32 = (now & u32::MAX as i64) as u32;
        libc::srand(now_u32);
    }

    println!("{}", ulid());
}

To correctly use this crate, you need to seed libc::rand.

The primary API is the ulid() function, which returns a String.

ulid_lite::ulid() -> String

For more control, the ulid::Ulid type is also available.

ulid_lite::Ulid::new() -> ulid::Ulid

The Ulid struct is a wrapper around a u128, with a few extra methods.

let id = ulid_lite::Ulid::new();

// Ulid structs can be converted to strings..
let _: String = id.to_string();

// They implmement Display, LowerHex and UpperHex
println!("{}", id);
println!("{:x}", id);
println!("{:X}", id);

More recent ULIDs are higher than older ones:

use std::thread::sleep;
use std::time::Duration;

let a = ulid();
sleep(Duration::from_millis(1));
let b = ulid();
assert!(a < b);

Installation

At this early stage, this implementation is only available to people who can install it from source:

$ cargo install --git https://github.com/timClicks/ulid-lite.git

Roadmap

C library ("libulid"?)

This implementation is designed to make it easy to add a fast implemention to your language. Accordingly, it'll expose

PostgreSQL extension

I would like to use this crate to develop pg_ulid extension.

Warning: Work in progress

A few important features are not yet implemented.

  • parsing pre-existing ULIDs
  • monotonicity within the same millisecond
  • overflow checks
  • no_std: at the moment, this crate uses the std::time module to access the clock in a cross-portable manner. Over time, I would like make syscalls directly.

Why add another crate?

I wanted to implement a crate with a minimalist feel. It is intended to be easy and fast to build. ulid-lite has minimal dependencies: its only external dependency is libc. This keeps build times fast and binary size small.

ulid does not take a long time to compile:

$ cargo clean
$ cargo build --release
   Compiling libc v0.2.94
   Compiling ulid v0.1.0 (/.../ulid)
    Finished release [optimized] target(s) in 1.44s

Acknowledgements

I've relied on two other implementations to develop ulid-lite:

Dylan Hart github.com/dylanhart/ulid-rs
Marcos Macedo github.com/mmacedoeu/rulid.rs
Comments
  • libc's rand not thread-safe

    libc's rand not thread-safe

    In multi-threaded environments, the current code won't behave properly. Multiple threads can created the same ID.

    From the rand(3) manpage:

    The function rand() is not reentrant, since it uses hidden state that is modified on each call. This might just be the seed value to be used by the next call, or it might be something more elaborate. In order to get reproducible behavior in a threaded application, this state must be made explicit; this can be done using the reentrant function rand_r().

    The difficulty in deciding what to do is that I would prefer to avoid Linux-specific APIs. So perhaps a stopgap would be a semaphore/spinlock. In the worst case, this would stall other threads for ~20 nanoseconds.

    opened by timClicks 4
  • Provide safer C APIs with buffer size and overflow checking

    Provide safer C APIs with buffer size and overflow checking

    A few more changes to the C APIs, hopefully making them safer and (a bit) more natural to use. Commit b7bfb81239b8 has the bulk of them, and a more in depth explanation.

    opened by jonasmalacofilho 3
  • Possible unsoundness in the C/C++ interface

    Possible unsoundness in the C/C++ interface

    Hi,

    I saw your tweet asking for opinions on how ergonomic the C/C++ API is, and while I'm not well suited to answer that, I wanted to see how you implemented this library. While taking a look at the code, I think I may have accidentally spotted a couple of problems.1

    The first is that ulid_new() appears to return a pointer to the stack: it creates a new Ulid on the stack, transmutes it to a UlidArray, and returns a pointer to it. There are no allocations, so isn't that a pointer to the stack and, more importantly, a pointer that becomes invalid as soon as that function returns? Miri seems to agree.

    Another issue, is that in ulid_new_string() the returned pointer is derived from a temporary String (created with Ulid::new().to_string()), which is immediately dropped, making the pointer invalid. Miri also seems to agree.

    That string is also allocated with Rust's Global allocator, so it's probably not sound to free it with any other allocator.

    As a minor final observation, the function transmutes a const pointer into a mutable one. This is (probably) fine in that instance, as at that point we own the value anyway, but wouldn't as_mut_ptr() be a bit more direct?


    P.S. The Miri examples used a simplified implementation to avoid calling functions from libc, which Miri doesn't yet support.

    1 I'm pretty new to Rust, and even more so to unsafe Rust. So I'm sorry if I'm missing something obvious...

    opened by jonasmalacofilho 2
  • ffi: delegate all allocations to the caller

    ffi: delegate all allocations to the caller

    This is a follow up to our email conversation.

    As in this design both ulid_new_string() and ulid_write_new() would be identical, the latter is dropped.

    Due to the increased number of tests, a problem with rand() not being reentrant became a lot more apparent. The tests can be made to work reliably with --test-threads 1, but a proper solution is still needed, as that is a bug that affects normal use of the public APIs.

    Most of the tests can also be executed in Miri with:

    MIRIFLAGS="-Zmiri-disable-isolation" cargo +nightly miri test
    

    (-Zmiri-disable-isolation is required for SystemTime::new() ).

    opened by jonasmalacofilho 1
  • WIP remove libc rand; rework Rust API

    WIP remove libc rand; rework Rust API

    I have been working to improve the Rust API and also fix #8 by avoiding rand().

    use ulid::{UlidGenerator};
    
    fn main() {
        let mut ulid_gen = UlidGenerator::new();
        for _ in 0..10 {
            println!("{}", ulid_gen.ulid());
        }
    }
    

    You still have the ability to seed things yourself:

    use ulid::{UlidGenerator};
    
    fn main() {
        let mut ulid_gen = UlidGenerator::from_seed(12345);
        for _ in 0..10 {
            println!("{}", ulid_gen.ulid());
        }
    }
    

    New benchmarks are promising. My laptop can now produce a ULID in ~28 nanoseconds.


    TODO

    • [x] use thread_rng API provided by the xorshift crate
    • [x] update documentation
    opened by timClicks 0
  • Is `ERANGE` widely supported?

    Is `ERANGE` widely supported?

    We've recently introduced libc::ERANGE with the chance in C APIs. One thing to decide is the supported platforms for ulid-lite - because libc is less standard than I would have hoped.

    help wanted portability 
    opened by timClicks 1
Owner
Tim McNamara
Tim McNamara
A type-safe, K-sortable, globally unique identifier

type-safe-id A type-safe, K-sortable, globally unique identifier. Typed implementation of https://github.com/jetpack-io/typeid in Rust. Examples Stati

Conrad Ludgate 13 Jul 10, 2023
Base 32 + 64 encoding and decoding identifiers + bytes in rust, quickly

fast32 Base32 and base64 encoding in Rust. Primarily for integer (u64, u128) and UUID identifiers (behind feature uuid), as well as arbitrary byte arr

Chris Rogus 9 Dec 18, 2023
Costless typed identifiers backed by UUID, with kind readable in serialized versions

Why kind ? With kind, you use typed identifiers in Rust, with no overhead over Uuid have the type be human readable and obvious in JSON and any export

Wingback 67 Mar 24, 2024
Rodrigo's Unique Identifier

RUID - Time-Travel-Safe Unique 64 bit ids generated in Rust RUIDs (Rodrigo's Unique Identifiers) are 64 bit ids mathematically guaranteed to be unique

Statsig 18 Sep 26, 2022
Parallel finance a decentralized lending protocol built on top of the Polkadot ecosystem. Our unique approach will allow users to earn "double interests" from staking and lending their tokens simultaneously.

Parallel Finance A new Cumulus-based Substrate node, ready for hacking ?? Getting Started Follow these steps to get started with the Cumulus Template

parallel-finance 100 Dec 17, 2022
Mononym is a library for creating unique type-level names for each value in Rust.

Mononym is a library for creating unique type-level names for each value in Rust.

MaybeVoid 52 Dec 16, 2022
httm prints the size, date and corresponding locations of available unique versions of files residing on ZFS snapshots

httm prints the size, date and corresponding locations of available unique versions of files residing on ZFS snapshots, as well as allowing their interactive viewing and restoration.

null 837 Dec 30, 2022
A small, 8-byte, ID type for use in rust applications that need a pretty unique identifier

TinyId A small, 8-byte, ID type for use in rust applications that need a pretty unique identifier that is not required to be cryptographically secure

Tony B 1 May 4, 2022
Generates a unique hash/identifier for a system given a set of parameters.

uniqueid ?? Generates a unique hash/identifier for a system given a set of parameters. Example usage use uniqueid; pub fn main() { let data = vec

Checksum 2 Aug 19, 2022
Game of life rendered in your terminal with over 500+ unique patterns to choose from.

Controls a: play animation n: next generation s: stop j or down arrow: go down next pattern (note: you have to stop the animation to browse the patter

Omar Magdy 20 Dec 22, 2022
A fast, simple and powerful open-source cross platform utility tool for generating strong, unique and random passwords

password-generator-pro A fast, simple and powerful open-source cross platform utility tool for generating strong, unique and random passwords. Feature

Sebastien Rousseau 3 Dec 16, 2022
Yet another fancy watcher. (Rust)

funzzy Yet another fancy watcher. (Inspired by antr / entr) Configure execution of different commands using semantic yaml. # .watch.yaml # list here a

Cristian Oliveira 188 Dec 12, 2022
Yet Another Technical Analysis library [for Rust]

YATA Yet Another Technical Analysis library YaTa implements most common technical analysis methods and indicators. It also provides you an interface t

Dmitry 197 Dec 29, 2022
Yet Another Serializer/Deserializer

yaserde   Yet Another Serializer/Deserializer specialized for XML Goal This library will support XML de/ser-ializing with all specific features. Suppo

null 137 Jan 5, 2023
Yarte stands for Yet Another Rust Template Engine

Should we start to worry? bytes-buf feature can produce SIGILL. avx and sse flags are in almost all cpus of x86 and x86_64 architectures. More details

Juan Aguilar 249 Dec 19, 2022
Yet another pager in Rust

rust-pager Yet another pager in Rust Features Vim like keybindings Search substring Mouse wheel support Install cargo install rust-pager Usage <comman

null 19 Dec 7, 2022
Yet another trojan-gfw in Rust

Trojan-rust Yet another trojan-gfw implementation in Rust. Features Server mode only (for now). Supports Redis auth & flow stat. Uses OpenSSL as crypt

粒粒橙 34 Oct 25, 2022
Yet Another Kev-Value DataBase

Yet Another Kev-Value DataBase Extremely simple (simplest possible?) single-file BTree-based key-value database. Build for fun and learning: goal is t

Sergey Melnychuk 18 May 23, 2022
Yet another ROS2 client library written in Rust

RclRust Target CI Status Document Foxy (Ubuntu 20.04) Introduction This is yet another ROS2 client library written in Rust. I have implemented it inde

rclrust 42 Dec 1, 2022
Yet another gem miner

Rusty Pickaxe Multithreaded CPU miner for Provably Rare Gems, written in Rust. There is also closed-source GPU version, waiting to be released. Config

Someone 7 Aug 11, 2022