Reading DDIA and Solving Gossip Glomers in Python: Part 2

Welcome back to my fun adventures of solving fly.io’s Gossip Glomers. In this post, I’ll tackle Challenge #2: Unique ID Generation. First, let’s chat through the requirements. Your code will receive the following from a client:

{
  "type": "generate"
}

And you will return:

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

Now, let’s write some code to come up with your_generated_id. With our current setup, the following boilerplate will get you started:

#!/usr/bin/env python3

from maelstrom import Body, Node, Request

node = Node()


@node.handler
async def generate(req: Request) -> Body:
    """Write some code here to generate 'new_id'."""
    new_id = generate_a_unique_id()  # You will write this
    return {"type": "generate_ok", "id": new_id}


node.run()

We also have the following stipulations:

Your service should be totally available, meaning that it can continue to operate even in the face of network partitions.

UUIDs might seem like a no-brainer since they promise uniqueness. I mean, the words “unique” and “id” are right in the name. We must fight this initial pattern-matching solution our monkey brains give us. UUIDs don’t account for distributed systems’ quirks, like network partitions. If two nodes independently generate the same UUID, it breaks the promise of uniqueness. How do we keep track of the already generated IDs? We don’t!

Instead, we take a different approach. In the event of a network partition, we can never know the IDs generated by other nodes. Let’s instead generate IDs that can never conflict.

Lamport Timestamps

The Wikipedia definition of Lamport Timestamps is a little convoluted to follow. Turn to page 345 of DDIA for a much more succinct definition:

Each node has a unique identifier, and each node keeps a counter of the number of operations it has processed. The Lamport timestamp is then simply a pair of (counter, node ID).

In other words, a Lamport Timestamps works like this:

  1. Each node in the system has a unique ID (e.g., n1, n2).
  2. Each node maintains a local counter starting at 0.
  3. When a request comes in, the node increments its counter and combines it with its ID to create a unique timestamp, like n1_1, n2_3, etc.

If you look inside maelstrom.py, you will notice each node has a node_id. These come in the form of n1 or n2 and are guaranteed to be unique. The only part missing is a counter, which you can declare globally and then increment after each request. Our unique id can then be something like f"{node.node_id}_{counter}".

With this solution, the nodes don’t need to know anything about the other nodes. This means we don’t need to worry about consistency with the network partitions. Mountain avoided, only a tiny molehill.