All Projects → f4b6a3 → tsid-creator

f4b6a3 / tsid-creator

Licence: MIT License
A Java library for generating Time Sortable Identifiers (TSID).

Programming Languages

java
68154 projects - #9 most used programming language

Projects that are alternatives of or similar to tsid-creator

ulid-creator
A Java library for generating Universally Unique Lexicographically Sortable Identifiers (ULID)
Stars: ✭ 38 (+137.5%)
Mutual labels:  id, ulid, unique-id, identifier, id-generator
Butterfly
分布式ID生成器框架:超高性能的发号器框架。通过引入多种新的方案,彻底解决雪花算法的时间回拨等问题,并将雪花算法原生QPS提高最少十几~二十倍
Stars: ✭ 111 (+593.75%)
Mutual labels:  snowflake, unique-id, snowflake-twitter, snowflake-java
sno
Compact, sortable and fast unique IDs with embedded metadata.
Stars: ✭ 77 (+381.25%)
Mutual labels:  snowflake, unique-id, id-generator
IdGenerator
💎迄今为止最全面的分布式主键ID生成器。 💎优化的雪花算法(SnowFlake)——雪花漂移算法,在缩短ID长度的同时,具备极高瞬时并发处理能力(50W/0.1s)。 💎原生支持 C#/Java/Go/Rust/C/SQL 等多语言,且提供 PHP 扩展及 Python、Node.js、Ruby 多线程安全调用动态库(FFI)。💎支持容器环境自动扩容(自动注册 WorkerId ),单机或分布式唯一IdGenerator。💎顶尖优化,超强效能。
Stars: ✭ 548 (+3325%)
Mutual labels:  snowflake, unique-id
ids
高效的分布式id生成器,每个客户端实例tps可达到100万,服务端毫无压力。即使服务端宕机了,id生成依然可用。支持多数据中心,支持id加密。
Stars: ✭ 47 (+193.75%)
Mutual labels:  id, id-generator
sid
Generate Sortable Identifiers
Stars: ✭ 26 (+62.5%)
Mutual labels:  id, identifier
python-ulid
ULID implementation for Python
Stars: ✭ 177 (+1006.25%)
Mutual labels:  ulid, unique-id
monoton
Highly scalable, single/multi node, sortable, predictable and incremental unique id generator with zero allocation magic on the sequential generation
Stars: ✭ 21 (+31.25%)
Mutual labels:  snowflake, id-generator
hashids.sql
PL/pgSQL implementation of hashids library
Stars: ✭ 40 (+150%)
Mutual labels:  id, shortid
snowflake
Yet another snowflake
Stars: ✭ 22 (+37.5%)
Mutual labels:  snowflake, twitter-snowflake
shortid
Super short, fully unique, non-sequential and URL-friendly Ids
Stars: ✭ 20 (+25%)
Mutual labels:  id, shortid
distributed-id
基于netty4+twitter-snowFlake分布式Id生成之服务实现
Stars: ✭ 18 (+12.5%)
Mutual labels:  id, snowflake
shortid
Short id generator. Url-friendly. Non-predictable. Cluster-compatible.
Stars: ✭ 28 (+75%)
Mutual labels:  unique-id, shortid
leafserver
🍃A high performance distributed unique ID generation system
Stars: ✭ 31 (+93.75%)
Mutual labels:  id, unique-id
go-snowflake
go-snowflake
Stars: ✭ 101 (+531.25%)
Mutual labels:  snowflake
fuuid
Functional UUIDs for Python.
Stars: ✭ 145 (+806.25%)
Mutual labels:  unique-id
microvm.nix
NixOS MicroVMs
Stars: ✭ 136 (+750%)
Mutual labels:  flake
snowworker
Website snow! It'll settle on anything that has a .rooftop class.
Stars: ✭ 25 (+56.25%)
Mutual labels:  snowflake
piccolo
Netty4长连接网关
Stars: ✭ 19 (+18.75%)
Mutual labels:  snowflake
vue-uniq-ids
Vue.js 2.x plugin that helps to use id-related attributes with no side-effect
Stars: ✭ 32 (+100%)
Mutual labels:  id

TSID Creator

This is a Java library for Time Sortable Identifier.

It brings together ideas from Twitter's Snowflake and ULID Spec.

In summary:

  • Sorted by generation time;
  • Can be stored as an integer of 64 bits;
  • Can be stored as a string of 13 chars;
  • String format is encoded to Crockford's base32;
  • String format is URL safe, is case insensitive, and has no hyphens;
  • Shorter than UUID, ULID and KSUID.

This library contains a good amount of unit tests. It also has a micro benchmark for you to check if the performance is good enough.

Read Snowflake ID on Wikipedia.

How to Use

Create a TSID:

Tsid tsid = TsidCreator.getTsid1024();

Create a TSID number:

long number = TsidCreator.getTsid1024().toLong(); // 38352658567418872

Create a TSID string:

String string = TsidCreator.getTsid1024().toString(); // 01226N0640J7Q

There are three predefined node ranges: 256, 1024 and 4096.

The TSID generator is thread-safe.

Maven dependency

Add these lines to your pom.xml:

<!-- https://search.maven.org/artifact/com.github.f4b6a3/tsid-creator -->
<dependency>
  <groupId>com.github.f4b6a3</groupId>
  <artifactId>tsid-creator</artifactId>
  <version>4.1.4</version>
</dependency>

See more options in maven.org.

Modularity

Module and bundle names are the same as the root package name.

  • JPMS module name: com.github.f4b6a3.tsid
  • OSGi symbolic name: com.github.f4b6a3.tsid

TSID as Long

This section shows how to create TSID numbers.

The method Tsid.toLong() simply unwraps the internal long value.

// Create a TSID for up to 256 nodes and 16384 ID/ms
long tsid = TsidCreator.getTsid256().toLong();
// Create a TSID for up to 1024 nodes and 4096 ID/ms
long tsid = TsidCreator.getTsid1024().toLong();
// Create a TSID for up to 4096 nodes and 1024 ID/ms
long tsid = TsidCreator.getTsid4096().toLong();

Sequence of TSIDs:

38352658567418867
38352658567418868
38352658567418869
38352658567418870
38352658567418871
38352658567418872
38352658567418873
38352658567418874
38352658573940759 < millisecond changed
38352658573940760
38352658573940761
38352658573940762
38352658573940763
38352658573940764
38352658573940765
38352658573940766
         ^      ^ look
                                   
|--------|------|
   time   random

TSID as String

This section shows how to create TSID strings.

The TSID string is a 13 characters long string encoded to Crockford's base 32.

// Create a TSID string for up to 256 nodes and 16384 ID/ms
String tsid = TsidCreator.getTsid256().toString();
// Create a TSID string for up to 1024 nodes and 4096 ID/ms
String tsid = TsidCreator.getTsid1024().toString();
// Create a TSID string for up to 4096 nodes and 1024 ID/ms
String tsid = TsidCreator.getTsid4096().toString();

Sequence of TSID strings:

01226N0640J7K
01226N0640J7M
01226N0640J7N
01226N0640J7P
01226N0640J7Q
01226N0640J7R
01226N0640J7S
01226N0640J7T
01226N0693HDA < millisecond changed
01226N0693HDB
01226N0693HDC
01226N0693HDD
01226N0693HDE
01226N0693HDF
01226N0693HDG
01226N0693HDH
        ^   ^ look
                                   
|-------|---|
   time random

TSID Structure

The term TSID stands for (roughly) Time Sortable ID. A TSID is a number that is formed by the creation time along with random bits.

The TSID has 2 components:

  • Time component (42 bits)
  • Random component (22 bits)

The time component is the count of milliseconds since 2020-01-01 00:00:00 UTC.

The Random component has 2 sub-parts:

  • Node ID (0 to 20 bits)
  • Counter (2 to 22 bits)

The counter bits depend on the node bits. If the node bits are 10, the counter bits are limited to 12. In this example, the maximum node value is 2^10-1 = 1023 and the maximum counter value is 2^12-1 = 4095. So the maximum TSIDs that can be generated per millisecond is 4096.

The node identifier uses 10 bits of the random component by default in the TsidFactory. It's possible to adjust the node bits to a value between 0 and 20. The counter bits are affected by the node bits.

This is the default TSID structure:

                                            adjustable
                                           <---------->
|------------------------------------------|----------|------------|
       time (msecs since 2020-01-01)           node       counter
                42 bits                       10 bits     12 bits

- time:    2^42 = ~139 years (with adjustable epoch)
- node:    2^10 = 1,024 (with adjustable bits)
- counter: 2^12 = 4,096 (initially random)

Notes:
The node is adjustable from 0 to 20 bits.
The node bits affect the counter bits.
The time component can be used for ~69 years if stored in a SIGNED 64 bits integer field.

The node identifier is a random number from 0 to 1023 (default). It can be replaced by a value given to the TsidFactory constructor or method factory.

Another way to replace the random node is by using a system property tsidcreator.node or a environment variable TSIDCREATOR_NODE.

Node identifier

The node identifier can be given to the TsidFactory by defining a system property tsidcreator.node or a environment variable TSIDCREATOR_NODE. If this property or variable exists, the node identifier is its value. Otherwise, the node identifier is random number.

The simplest way to avoid collisions is to ensure that each generator has its exclusive node identifier.

  • Using system property:
// append to VM arguments
-Dtsidcreator.node="755"
  • Using environment variable:
# append to /etc/environment or ~/.profile
export TSIDCREATOR_NODE="492"

More Examples

Create a TSID from a canonical string (13 chars):

Tsid tsid = Tsid.from("0123456789ABC");

Convert a TSID into a canonical string in lower case:

String string = tsid.toLowerCase(); // 0123456789abc

Get the creation instant of a TSID:

Instant instant = tsid.getInstant(); // 2020-04-15T22:31:02.458Z

A key generator that makes substitution easy if necessary:

package com.example;

import com.github.f4b6a3.tsid.TsidCreator;

public class KeyGenerator {
    public static String next() {
        return TsidCreator.getTsid1024().toString();
    }
}
String key = KeyGenerator.next();

A TsidFactory with a FIXED node identifier:

int node = 256; // max: 2^10
TsidFactory factory = new TsidFactory(node);

// use the factory
Tsid tsid = factory.create();

A TsidFactory with a FIXED node identifier and CUSTOM node bits:

// setup a factory for up to 64 nodes and 65536 ID/ms.
TsidFactory factory = TsidFactory.builder()
    .withNodeBits(6)      // max: 20
    .withNode(63)         // max: 2^nodeBits
    .build();

// use the factory
Tsid tsid = factory.create();

A TsidFactory with a CUSTOM epoch:

// use a CUSTOM epoch that starts from the fall of the Berlin Wall
Instant customEpoch = Instant.parse("1989-11-09T00:00:00Z");
TsidFactory factory = TsidFactory.builder().withCustomEpoch(customEpoch).build();

// use the factory
Tsid tsid = factory.create();

A TsidFactory with java.util.Random:

// use a `java.util.Random` instance for fast generation
TsidFactory factory = TsidFactory.builder().withRandom(new Random()).build();

// use the factory
Tsid tsid = factory.create();

A TsidFactory with ThreadLocalRandom inside of an IntFunction<byte[]>:

// use a random function that returns an array of bytes with a given length
TsidFactory factory = TsidFactory.builder()
    .withRandomFunction(length -> {
        final byte[] bytes = new byte[length];
        ThreadLocalRandom.current().nextBytes(bytes);
        return bytes;
    }).build();

// use the factory
Tsid tsid = factory.create();

A less-blocking factory that wraps an array of factories to generate more than 4 million TSIDs per second:

package com.example;

import com.github.f4b6a3.tsid.Tsid;
import com.github.f4b6a3.tsid.TsidFactory;

/**
 * A less-blocking factory that wraps an array of factories.
 * 
 * It can be used to generate TSIDs with less thread contention.
 * 
 * It can generate more than 4 million TSIDs per second.
 */
public class LessBlockingFactory {

    private final TsidFactory[] factories;

    public LessBlockingFactory(int[] nodes) {
        factories = new TsidFactory[nodes.length];
        for (int i = 0; i < factories.length; i++) {
            factories[i] = new TsidFactory(nodes[i]);
        }
    }

    public Tsid create() {
        // calculate the factory index given the current thread ID
        final int index = (int) Thread.currentThread().getId() % factories.length;
        return factories[index].create();
    }
}
// instantiate an array of 8 UNIQUE node identifiers to be used
int[] nodes = { 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008 };

// instantiate a less-blocking factory with an array of 8 factories
LessBlockingFactory factory = new LessBlockingFactory(nodes);
    
// use the less-blocking factory
TSID tsid = factory.create();

A TsidFactory that creates TSIDs similar to Twitter Snowflakes:

// Twitter Snowflakes have 5 bits for datacenter ID and 5 bits for worker ID
int datacenter = 1; // max: 2^5-1 = 31
int worker = 1;     // max: 2^5-1 = 31
int node = (datacenter << 5 | worker); // max: 2^10-1 = 1023

// Twitter Epoch is fixed in 1288834974657 (2010-11-04T01:42:54.657Z)
Instant customEpoch = Instant.ofEpochMilli(1288834974657L);

// a function that returns an array with ZEROS, making the factory
// to RESET the counter to ZERO when the millisecond changes
IntFunction<byte[]> randomFunction = (x) -> new byte[x];

// a factory that returns TSIDs similar to Twitter Snowflakes
TsidFactory factory = TsidFactory.builder()
		.withRandomFunction(randomFunction)
		.withCustomEpoch(customEpoch)
		.withNode(node)
		.build();

// use the factory
Tsid tsid = factory.create();

A TsidFactory that creates TSIDs similar to Discord Snowflakes:

// Discord Snowflakes have 5 bits for worker ID and 5 bits for process ID
int worker = 1;  // max: 2^5-1 = 31
int process = 1; // max: 2^5-1 = 31
int node = (worker << 5 | process); // max: 2^10-1 = 1023

// Discord Epoch starts in the first millisecond of 2015
Instant customEpoch = Instant.parse("2015-01-01T00:00:00.000Z");

// a function that returns NULL, making the factory to
// INCREMENT the counter when the millisecond changes
IntFunction<byte[]> randomFunction = (x) -> null;

// a factory that returns TSIDs similar to Discord Snowflakes
TsidFactory factory = TsidFactory.builder()
		.withRandomFunction(randomFunction)
		.withCustomEpoch(customEpoch)
		.withNode(node)
		.build();

// use the factory
Tsid tsid = factory.create();

Benchmark

This section shows benchmarks comparing TsidCreator to java.util.UUID.

--------------------------------------------------------------------------------
THROUGHPUT (operations/msec)            Mode  Cnt      Score     Error   Units
--------------------------------------------------------------------------------
UUID_randomUUID                        thrpt    5   2062,642 ±  34,230  ops/ms
UUID_randomUUID_toString               thrpt    5   1166,183 ±  16,001  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
TsidCreator_getTsid256                 thrpt    5  16075,867 ± 274,681  ops/ms
TsidCreator_getTsid256_toString        thrpt    5  15379,666 ± 167,178  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
TsidCreator_getTsid1024                thrpt    5   4093,735 ±   0,272  ops/ms
TsidCreator_getTsid1024_toString       thrpt    5   4076,510 ±   2,437  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
TsidCreator_getTsid4096                thrpt    5   1024,009 ±   0,252  ops/ms
TsidCreator_getTsid4096_toString       thrpt    5   1023,653 ±   0,379  ops/ms
--------------------------------------------------------------------------------
Total time: 00:10:40
--------------------------------------------------------------------------------

System: JVM 8, Ubuntu 20.04, CPU i5-3330, 8G RAM.

To execute the benchmark, run ./benchmark/run.sh.

Other identifier generators

Check out the other ID generators from the same family:

License

This library is Open Source software released under the MIT license.

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].