RUID — Time-Travel-Safe, Distributed, Unique, 64 bit ids generated in Rust

Rodrigo Roim
Wed May 05 2021
DISTRIBUTED-SYSTEMS ALGORITHMS RUST CLOUD-COMPUTING TIME-TRAVEL

RUID — Time-Travel-Safe, Distributed, Unique, 64 bit ids generated in Rust

Photo by Jason Leung on Unsplash

RUIDs (Rodrigo’s Unique Identifiers) are 64 bit ids mathematically guaranteed to be unique when generated within the same RUID root. Check it out on GitHub.

An RUID root is a set of RUID generators where each generator can be uniquely identified through shared configuration. E.g. a root can be implemented as a set of VMs on the same subnet, each identified by the last n bits of its internal IP address.

Schema Design

The canonical version of RUIDs (this repo) uses 41 bits for timestamp, 14 bits for a monotonically increasing sequence, and 9 bits for the root id.

- 41 bits is enough to cover Rodrigo’s projected lifespan in milliseconds.
- 14 bits is about the # of RUIDs that can be generated single threaded in Rodrigo’s personal computer (~20M ids per second).
- 9 bits is what remains after the calculations above, and is used for root id. The root id is further split into 5 bits for a cluster id, and 4 bits for a node id.

Time Travel

RUIDs are designed with time travel as a requirement. Whereas other unique id implementations fail (sometimes silently) if the system generating ids goes back in time, RUIDs will still output valid, unique ids.

In v0.1, this is achieved by:

  • Defining a millisecond maximum time travel threshold MMTTT (sometimes shortened as M2T3).
  • Comparing the current generation timestamp Ct with the previous generation timestamp Pt. When Ct < Ct + MMTTT < Pt, RUIDs are generated with Pt as the timestamp.
  • Sleeping for MMTTT when the server starts, and validating the system clock indeed increased by at least MMTTT at the end.

Note that timestamps for RUIDs generated after time travel and before MMTTT has elapsed will not match the system’s clock, which is both a feature and a bug (unsurprisingly, time travel incurs bug/feature duality).

Unfortunately this design is not mathematically correct if time travel happens while the RUID generator is not running; plans for fixing this bug — technically a higgs-bugson — are underway and planned for a v2 release of RUID.

Performance

Being coded in Rust and statically linked to musl, the RUID generator is exceptionally performant. v0.1 provides RUIDs via an actix HTTP server, for ease of integration and testing. The resulting standalone docker container is less than 15MB uncompressed. Further optimizations can be made by moving to a more performant RPC framework, and are planned for the RUID v1 release.

Why?

Rodrigo needed unique 64 bit ids to run benchmarks against 128 bit UUIDs in various distributed, database-intensive scenarios. Rodrigo was unsatisfied with existing implementations for various reasons, including questionable programming language choices and flaky project names.

Should you use it?

You probably don’t need distributed 64 bit ids, so no, you shouldn’t use RUID.

However, if you do need distributed 64-bit ids, give it a shot. Setting up RUID is easier than alternatives, since there is no external dependency at all (the single dependency on IP attribution is solved implicitly by DHCP). If Rust is not your thing, you can port RUID over to your favorite environment: RUID has < 100 SLOC, so porting it over is still easier than reusing (and configuring) any alternatives that depend on an external service.

Inspiration

RUIDs were inspired by the great efforts other engineers have gone through to generate 64 bit application-unique identifiers. In particular, inspiration was drawn from Instagram’s IDs, Twitter’s Snowflake, and Sony’s Sonyflake.

GitHub Repo

To see how RUID is currently implemented, head over to GitHub: https://github.com/statsig-io/ruid


Try Statsig Today

Explore Statsig’s smart feature gates with built-in A/B tests, or create an account instantly and start optimizing your web and mobile applications. You can also schedule a live demo or chat with us to design a custom package for your business.

MORE POSTS

Recently published

My Summer as a Statsig Intern

RIA RAJAN

This summer I had the pleasure of joining Statsig as their first ever product design intern. This was my first college internship, and I was so excited to get some design experience. I had just finished my freshman year in college and was still working on...

Read more

Long-live the 95% Confidence Interval

TIMOTHY CHAN

The 95% confidence interval currently dominates online and scientific experimentation; it always has. Yet it’s validity and usefulness is often questioned. It’s called too conservative by some [1], and too permissive by others. It’s deemed arbitrary...

Read more

Realtime Product Observability with Apache Druid

JASON WANG

Statsig’s Journey with Druid This is the text version of the story that we shared at Druid Summit Seattle 2022. Every feature we build at Statsig serves a common goal — to help you better know about your product, and empower you to make good decisions for...

Read more

Quant vs. Qual

MARGARET-ANN SEGER

💡 How to decide between leaning on data vs. research when diagnosing and solving product problems Four heuristics I’ve found helpful when deciding between data vs. research to diagnose + solve a problem. Earth image credit of Moncast Drawing. As a PM, data...

Read more

The Importance of Default Values

TORE

Have you ever sent an email to the wrong person? Well I have. At work. From a generic support email address. To a group of our top customers. Facepalm. In March of 2018, I was working on the games team at Facebook. You may remember that month as a tumultuous...

Read more
ANNOUNCEMENT

CUPED on Statsig

CRAIG

Run experiments with more speed and accuracy We’re pleased to announce the rollout of CUPED for all our customers. Statsig will now automatically use CUPED to reduce variance and bias on experiments’ key metrics. This gives you access to a powerful experiment...

Read more

We use cookies to ensure you get the best experience on our website.

Privacy Policy