Today I was trying to implement the Snowflake Id generator for Fly.io Gossip Glomers second challenge, Unique Id generation. Here’s what I came up with.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

package main

import (
	"encoding/json"
	"log"
	"strconv"
	"time"

	maelstrom "github.com/jepsen-io/maelstrom/demo/go"
)

type Snowflake struct {
	sequenceNumber uint64
	selfId         int
	lastTs         int64
}

func nextId(s *Snowflake) uint64 {
	ts := time.Now().UnixMilli() // this is 41 bits
	if s.lastTs == ts {
		s.sequenceNumber++
	} else {
		s.sequenceNumber = 0
	}
	s.lastTs = ts
	var id uint64 = uint64(ts << 22) // (64 - 1 sign bit - 41 unix timestamp bits)
	log.Printf("shifted %d", id)
	id = id | ((uint64(s.selfId) & 0x3f) << 16) // machine id is 10 bits
	log.Printf("after self Id %d", id)
	id = id | ((s.sequenceNumber & 0xffff) )
	return id
}

func main() {

	n := maelstrom.NewNode()

	sf := &Snowflake{}
	n.Handle("generate", func(msg maelstrom.Message) error {

		var body map[string]any
		if err := json.Unmarshal(msg.Body, &body); err != nil {
			return err
		}

		selfId, err := strconv.Atoi(msg.Dest[1:])
		if err != nil {
			log.Fatal("Cannot parse destination as a number", msg.Dest)
		}
		sf.selfId = selfId

		body["type"] = "generate_ok"
		body["id"] = nextId(sf)

		return n.Reply(msg, body)
	})

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

}

It wasn’t too bad for how simple its supposed to be. My solution wasn’t getting accepted by maelstrom because there were duplicate Ids generated by my program. After looking at my code for very long and not finding any idea what went wrong, I asked ChatGPT, it suggested the sequenceNumber bits were too few and must probably be overflowing. After looking at the maelstrom logs I found the lines which had duplicate Ids.

That was very strange. I noticed all IDs generated ended with 000. Surely, I made a mistake on the bitwise OR of the sequence number, right?

Wrong.

I figured out how to log to stderr and looked at what my Ids were.

1
2

	id = id | ((s.sequenceNumber & 0xffff) )
	log.Printf("Sequence Number: %d %u %lu", id, id, id)

And they were unique alright. For a second I thought that Golang must be casting my Ids into some other datatype and truncating my IDs. But that was not it. It was maelstrom it wouldn’t accept the last 3 digits. I think this is because we’re using JSON and while JSON doesn’t limit the size of the number in its spec (see here), there might be something in the middle that cannot accept that number and is thus being truncated. NodeJS for example can only process numbers upto

1
2
3

> Number.MAX_SAFE_INTEGER
9007199254740991
>

So the solution is to just move the sequenceNumber a few bits up as we have plenty of space left in the sequenceNumber space. maelstrom test cases dont generate too many ids in the same millisecond.

1

	id = id | ((s.sequenceNumber & 0xffff) << 10)