Icicle

A distributed, k-sortable unique ID generation system using Redis and Lua.

Icicle is a project to generate 64-bit, k-sortable unique IDs in a distributed fashion by using Redis' Lua scripting.

Implementations of Icicle could be written in any language using just a Redis client library and the Lua script.

Icicle v1.x users: There are some important breaking changes in v2.x! Please read the release notes for more information.

Using Icicle

Setup Your Redis Nodes

You need to have some Redis nodes available and running to use with Icicle. Icicle works on Redis >= v2.6 as it requires Lua support. Redis 3.x is supported and tested. We recommend running at least 2 Redis nodes, allowing for redundancy and better performance.

Once you have the Redis servers up and running, you must assign a logical shard ID to each Redis instance. This is a unique number between 0 and 1023 (inclusive) that is assigned to each node to prevent duplicate IDs:

SET icicle-generator-logical-shard-id 123

Make sure this is unique per node, or you run the risk you will generate duplicate IDs. Icicle will otherwise report an error to you if you set the ID too small or too large.

Configure NTP

To keep your system clock in check, you should install and configure NTP on every Redis node server. You need to run NTP in a mode where it won't move the clock backwards, as Icicle will not guarantee an ID won't be duplicated it does this. See this Stack Overflow post for more information on the behaviour of NTP.

Use The Client Library

With Jedis

A pre-rolled icicle-jedis library is available and using it is really simple. Create yourself an instance of the IcicleIdGenerator class, passing the

JedisIcicle redisServerOne = new JedisIcicle("server-one:6379");
JedisIcicle redisServerTwo = new JedisIcicle("server-two:6379");
JedisIcicle redisServerThree = new JedisIcicle("server-three:6379");
List<JedisIcicle> redises = Arrays.asList(redisServerOne, redisServerTwo, redisServerThree);

RoundRobinRedisPool roundRobinRedisPool = new RoundRobinRedisPool(redises);
IcicleIdGenerator icicleIdGenerator = new IcicleIdGenerator(roundRobinRedisPool);

And now to generate an ID:

Optional<Id> id = icicleIdGenerator.generateId();

Or a batch of IDs;

Optional<List<Id>> ids = icicleIdGenerator.generateIdBatch(10); // Get up to 10 IDs
Optional<List<Id>> ids = icicleIdGenerator.generateIdBatch(); // Get up to 4096 IDs

When requesting a batch of IDs, the generator cannot always return you the amount you asked for (this is a limitation related to our strong uniqueness guarantees) - instead, it will return between 1 and n, where n is the number of IDs you asked for in the batch. You may wish to check how many you actually received, and request more until you have the total you need.

With Another Redis Library

You can use Icicle with any Redis library you please. All you have to do is implement the Redis interface, and you can then use the RoundRobinRedisPool and IcicleIdGenerator classes as above with icicle-jedis.

Structure

We chose to pack our IDs in a 64-bit long, structured as follows:

The first bit is the reserved signed bit (which we chose not to use because some platforms make it difficult to get at and it messes with ordering).
Secondly, the timestamp in milliseconds since a custom epoch, 41 bits in total.
Next is the logical shard ID, 10 bits in total.
Finally, the sequence, 12 bits in total.

Kudos

The name of our project was inspired by a sadly now defunct project from Twitter called "Snowflake", from which we drew much inspiration.

anismiles/icicle