Distributed Unique ID Generation

This is a walkthrough of my solution for the second problem statement for Distributed Systems Challenge where we need to implement a totally available globally unique id generator comprising of multiple nodes. It has to pass the unique-ids workload of maelstrom.

My solution for this challenge made use of snowflake ids without knowing about their existence.

Problem Statement

The request for generate RPC is as below:

{
  "type": "generate"
}

For each of the generate RPC we need to respond with a unique id in the following format:

{
  "type": "generate_ok",
  "id": 123
}

An implicit but obvious requirement is that no ids generated by system should be same i.e. no two nodes in the system should generate same id and the same node should also not generate same id if it’s handling multiple requests.

The last requirement for fulfillment of the challenge is that system should be totally available i.e. even in presence of a network partition each node of the system should be able to handle the request in the expected manner.

Solution

Given the requirement of total availability we can’t have a shared state in our distributed system so that each node can handle request without needing to reference any non-local state or coordinate with other nodes.

The next thing is we need to add enough variants in our key generation logic so that there can’t be an id collision.

• The first thing that comes into mind for a constantly changing variant is time.
• The second thing that I made use of was the node id which separates the ids generated by two nodes in the system.
• The third thing we can use is the client id which again provides us a way to get more variation.

To remedy that we will retain a local counter and the access to it will be controlled using a mutex lock. This will provide us two things:

• The request might not be processed at the same epoch given the lock will be held with another request.
• Even if requests are processed sub-second leading to same epoch, the counter will get incremented by the last request.

Example

• Epoch time = 1697040000 (Unix timestamp)
• Source node ID = c1 (converted to integer1)
• Destination node ID = n2 (converted to integer2)
• Counter = 42

The 64 bit unique ID would be calculated as:

UniqueID = (1697040000 << 32) | (1 << 24) | (2 << 16) | 42
         = 72866491809705994

Additional Notes

The counter is a 16 bit unsigned integer that increments with each ID generation. If the counter exceeds 65,535 within a single second (i.e. at a rate higher than 65,535 QPS), it will overflow and wrap back to 0.

Given we aren’t going over 1000 requests for this challenge, so we can live with this limitation.

Before responding the result back to maelstrom we need to convert the uint64 id into a string because maelstrom’s analysis path reads JSON numbers as IEEE‑754 doubles, which only preserve 53 bits of precision. That means the low 32 bits get rounded away so different replies collapse to the same value.

This was something codex figured out for me whereas claude code failed terribly. The suggestion here was to either restrict the size of ids to 2^53 or return back a string.

The below also works:

id := uint64(s.counter) << 48 | uint64(srcInt) << 40 | uint64(destInt) << 32 | epoch

The reason being, we get uniqueness using counter, src and dest whereas epoch gets rounded off which is the source of duplicate ids.

Test

./maelstrom test -w unique-ids --bin ~/go/bin/maelstrom-unique-ids --time-limit 30 --rate 1000 --node-count 3 --availability total --nemesis partition

Drumroll 🥁🎊

Everything looks good! ヽ(‘ー`)ノ

Talk is cheap! Show me the code.

You can find the code for this particular problem in my github repository gossip-glomers.

Thanks for reading through in case you are interested in more of my writings head over to my blog.

Cover photo by CHUTTERSNAP on time lapse photography.