Concurrency-Safe ULID Generation using Go Mutexes

Use native Go toolset to solve real-life concurrency challenges.

Go offers one of the more “developer-friendly” toolsets for concurrency orchestration and synchronisation. This article demonstrates how to solve a monotonic ID generation problem using these tools.

Case Study: Event Logs #

Consider a common scenario in distributed systems: we need to capture event logs in a high-traffic environment and ensure that logs are ordered. Assume multiple services can open connections to an event-log service and append logs, while our observability services can query results or run batch CSV exports. We need a way to guarantee that ordering is preserved.

One workaround is to rely on timestamps (e.g. ISO-8601: 2024-01-01T10:00:00.000Z).

We could embed this into our event log IDs to provide weak ordering. Let’s look into that next.

Partial Solution: ULIDs #

A ULID (Universally Unique Lexicographically Sortable Identifier) is a 128-bit, time-sortable ID encoded as 26 characters. It is ideal for indexed columns without needing a separate timestamp field.

That said, ULIDs are not suitable for use cases where end users have access to entities. Bad actors can decode the timestamp bits relatively easily and exploit your systems. ULIDs also carry weaker entropy than UUIDv4 (80 random bits versus 122).

The first 48 bits of a ULID encode the timestamp down to millisecond accuracy, followed by 80 bits of entropy supplied by the caller. Examples in this article use the oklog/ulid/v2 Go package.

Even with millisecond-accurate timestamps, there is still an edge case: if two callers request a ULID within the same millisecond, there is a slight chance that both could be issued the same ID.

Monotonic Entropy #

Let’s draw this picture from a Go perspective. Assume two goroutines request ULIDs from a shared entropy source at the same time:

This translates to the code sample below:

// ulidSource is unsafe for concurrent use.
type ulidSource struct {
	entropy *ulid.MonotonicEntropy
}

func newULIDSource() *ulidSource {
	return &ulidSource{
		entropy: ulid.Monotonic(rand.Reader, 0),
	}
}

// New has no lock!!!
// Multiple goroutines will race on s.entropy.
func (s *ulidSource) New(t time.Time) ulid.ULID {
	return ulid.MustNew(ulid.Timestamp(t), s.entropy)
}

func main() {
	source := newULIDSource()

	var (
		wg      sync.WaitGroup
		mu      sync.Mutex      // Used for concurrency-safe access to results
		results []ulid.ULID
	)

	for i := 0; i < 2; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			for j := 0; j < 3; j++ {
				// Two goroutines can enter ulid.MustNew simultaneously.
				// This results in either:
				//   - duplicate ULIDs (same value emitted twice), or
				//   - corruption of the entropy state.
				u := source.New(time.Now())

				mu.Lock()
				results = append(results, u)
				mu.Unlock()

				fmt.Printf("goroutine %d generated: %s\n", id, u)
			}
		}(i)
	}

	wg.Wait()

	// Check for duplicates (detect race condition)
	seen := make(map[string]int)
	for i, u := range results {
		s := u.String()
		if prev, ok := seen[s]; ok {
			fmt.Printf("DUPLICATE: index %d and %d produced %s\n", prev, i, s)
		}
		seen[s] = i
	}

	// Check for ordering violations
	for i := 1; i < len(results); i++ {
		if results[i].Compare(results[i-1]) < 0 {
			fmt.Printf("ORDER VIOLATION: index %d (%s) < index %d (%s)\n",
				i, results[i], i-1, results[i-1])
		}
	}
}

As the two checker loops demonstrate, the generated ULIDs can collide or be emitted out of order.

One way to fix this is to acquire a lock around the entropy source so that, even when the timestamp is identical, the random bits are guaranteed to advance monotonically. The next section looks at the Go primitives we’ll use to do that.

Concurrency and Concurrency Orchestration in Go #

No programming language implements concurrency perfectly, and Go is no exception. The aim here is not to dive into Go scheduler mechanics, but we need to clarify a few key concepts first.

A Go program runs a main goroutine on an OS thread (call this M). We do not need to worry about the coordination between the logical processor (P) and the OS thread. The Go scheduler sits between the OS scheduler and the Go program and handles this for us. Other goroutines are likewise managed by the Go scheduler under its run queues.

The diagram shows how the main goroutine relates to other goroutines and how messaging between them is handled using channels.

Three key concepts to clarify here:

• Orchestration: a broader term, but in concurrency it refers to the lifecycle management of goroutines (e.g. waiting for a group of them to finish). sync.WaitGroup falls in this category.
• Synchronisation: protecting shared state from concurrent access. sync.Mutex and friends fall in this category.
• Signalling: communication between goroutines, achieved via select statements and channels.

To solve our problem we need a synchronisation mechanism to protect the shared entropy source. sync.Mutex does exactly that:

type ulidSource struct {
	mu      sync.Mutex               // Added for concurrency-safe access to entropy resource
	entropy *ulid.MonotonicEntropy
}

func newULIDSource() *ulidSource {
	return &ulidSource{
		entropy: ulid.Monotonic(rand.Reader, 0),
	}
}

// The mutex serialises access to the shared MonotonicEntropy.
func (s *ulidSource) New(t time.Time) ulid.ULID {
	s.mu.Lock()
	defer s.mu.Unlock()
	return ulid.MustNew(ulid.Timestamp(t), s.entropy)
}

func main() {
	source := newULIDSource()

	var (
		wg      sync.WaitGroup
		mu      sync.Mutex
		results []ulid.ULID
	)

	// Spawn 2 goroutines, each generating 3 ULIDs from the same source.
	for i := 0; i < 2; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			for j := 0; j < 3; j++ {
				// All goroutines share one source; the internal mutex
				// guarantees that MonotonicEntropy is never accessed
				// concurrently.
				u := source.New(time.Now())

				mu.Lock()
				results = append(results, u)
				mu.Unlock()

				fmt.Printf("goroutine %d generated: %s\n", id, u)
			}
		}(i)
	}

	wg.Wait()

	// Verify monotonicity
	for i := 1; i < len(results); i++ {
		if results[i].Compare(results[i-1]) < 0 {
			fmt.Printf("ORDERING VIOLATION at index %d\n", i)
		}
	}
	fmt.Printf("\nGenerated %d ULIDs, all monotonically ordered.\n", len(results))
}

References #

• oklog/ulid
• ulid/javascript
• Ultimate Go: Notebook by Ardan Labs
• Ultimate Go Programming
• The Go Programming Language
• asungur/squid