Skip to content
/ idem Public

Idem provides decentralized k-ordered ID generation.

License

Notifications You must be signed in to change notification settings

mguenther/idem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

26 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Idem

Build Status Maven Central

This repository hosts Idem, a Java library that implements a decentralized, k-ordered approach to ID generation using Flake IDs. Idem comes with a couple of building blocks that are used to implement a variety of Flake IDs with differing characteristics. Currently, Idem realizes Flake-64 and Flake-128 IDs.

Why should I bother?

If you are looking for ways to generate unique IDs that exhibit certain properties and require no coordination between individual nodes in your cluster, then you probably hit one of the following problems:

  • Generating technical identifiers for database entities hits a bottleneck, since your demand on the write-side of your application is too frequent for any database-centric approach to ID generation to keep up. You need to generate unique IDs and you need it done fast without any coordination required between individual nodes in your cluster.
  • Generated IDs should have exhibit some loose form of ordering if they are sorted lexicographically.
  • Application-level generated UUIDs of versions that incorporate time are of no use either, since they are susceptible to clock drift.
  • Of course you can implement your own library, but have you thought about NTP updates messing with your local time source (e.g. time flows backwards due to adjustments for clock drift)?

Idem implements a fast and reliable way to generate Flake IDs that require no coordination between nodes in your cluster.

Provided ID generators

Idem currently comes with the following ID generators equipped.

Generator Width Target Representation Comprises
Flake64L 64 Long 41-bit timestamp, 10-bit worker ID, 12-bit sequence
Flake64S 64 String (Base62-encoded) 41-bit timestamp, 10-bit worker ID, 12-bit sequence
Flake128S 128 String (Base62-encoded) 64-bit timestamp, 48-bit worker ID, 16-bit sequence

Using Idem

Using the individual Flake ID generators is quite easy. Have a look at the following example which demonstrates how to instantiate a Flake-64 generator that represents generated IDs as java.lang.Long-typed values.

Flake64L flake64 = new Flake64L(
        new LinearTimeProvider(),
        new StaticWorkerIdProvider("your-application-process"));
Long generatedId = flake64.nextId();

How fast is it?

Idem uses JMH to generate microbenchmarks that exercise the ID generation for the provided Flake IDs. All tests were conducted on a Dell XPS 15" with Intel Core i7-7700HQ CPU @ 2.80 GHz (8 cores). Test were executed with 20 warmup iterations (each one second) before 20 measurement iterations (each one second as well), all single-threaded.

Benchmark for Mode Threads Mean Mean Error
Flake64L Throughput 1 2.269.683 op / s 16.148 op / s
Flake64S Throughput 1 2.322.619 op / s 12.502 op / s
Flake128S Throughput 1 2.774.614 op / s 5.874 op / s
java.util.UUID (*) Throughput 1 1.512.316 op / s 2.363 op / s

(*) This is simply a call to UUID.randomUUID().toString() which incorporates generation (cf. randomUUID()) and encoding (cf. toString()).

You can run the benchmarks for yourself of course. The module idem-benchmark contains all benchmarks that can be run by selecting the Maven profile benchmark when building the solution.

License

This work is released under the terms of the Apache 2.0 license.

About

Idem provides decentralized k-ordered ID generation.

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages