Challenge #2: Unique ID Generation

The second challenge is unique-ids which is to implement a globally unique ID generator, which should work in the face of network partitions.

The Unique ID here can be constructed by simply concatenating the node name along with the current time in milliseconds and a counter. It is similar to the Snowflake ID Since ID generation only depends on the node and time, it should be totally available.

An implementation can be as follows.

type Counter struct {
	mu sync.Mutex
	x  uint16
}

func (c *Counter) Up() {
	c.mu.Lock()
	c.x += 1
	c.mu.Unlock()
}

func (c *Counter) V() uint16 {
	c.mu.Lock()
	x := c.x
	c.mu.Unlock()
	return x
}

func main() {
	n := maelstrom.NewNode()
	counter := Counter{
		mu: sync.Mutex{},
		x:  0,
	}

	n.Handle("generate", func(msg maelstrom.Message) error {
		var body map[string]any
		if err := json.Unmarshal(msg.Body, &body); err != nil {
			return err
		}

		body["type"] = "generate_ok"
		// Sort of like Snowflake implementation, but UID size is not formatted properly.
        // We don't have to handle overflows as they will rollover.
		id := fmt.Sprintf("%s%010d%08d", n.ID(), time.Now().UnixMilli(), counter.V())
		counter.Up()
		body["id"] = id

		return n.Reply(msg, body)
	})

	if err := n.Run(); err != nil {
		log.Fatal(err)
	}
}
go

We can run it with the below command.

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

And it works :)

Please take a look at the complete commit here.