DEV Community

Bill Tu
Bill Tu

Posted on

Who Should Own the Order ID? Moving ID Generation Inside the Matching Engine

#go #matchengine

Order IDs seem trivial. Every order needs one, they need to be unique, and they show up in every trade record. In the first version of MatchEngine, the caller provided the ID as a string. It worked. Then it didn't.

This article explains why we moved ID generation inside the engine, the design choices behind the implementation, and the three new API methods that replaced the old approach.

The Problem With Caller-Provided IDs

The original API looked like this:

order := model.NewLimitOrder("my-order-1", model.Buy, price, quantity)
trades, err := e.SubmitOrder("BTC/USD", order)
Enter fullscreen mode Exit fullscreen mode

The caller chose the ID. The engine accepted it. This created three problems:

1. Uniqueness is the caller's problem. The engine added duplicate detection in v0.2.0, but that just turned a silent corruption into an error. The caller still had to generate unique IDs — and every caller had to solve the same problem independently. In a system with multiple order sources (REST API, WebSocket, FIX gateway), coordinating unique IDs across all of them is a real engineering challenge.

2. No ordering guarantee. Caller-provided IDs are arbitrary strings. There is no way to determine which order came first by looking at the IDs. For debugging, auditing, and replay, monotonically increasing IDs are invaluable. They give you a total ordering of events without consulting timestamps.

3. The API is noisy. Every call site has to construct an Order struct with an ID, a side, a type, a price, a quantity, and a timestamp. The ID and timestamp are boilerplate — the caller doesn't care about them. They care about "sell 5 BTC at 50,000."

The Design: Atomic Counter

We chose the simplest possible ID generator: an atomic uint64 counter.

type Engine struct {
    nextID   uint64  // atomic counter
    idPrefix string  // optional prefix
    // ...
}

func (e *Engine) generateID() string {
    id := atomic.AddUint64(&e.nextID, 1)
    return e.idPrefix + strconv.FormatUint(id, 10)
}
Enter fullscreen mode Exit fullscreen mode

atomic.AddUint64 increments the counter and returns the new value in a single atomic operation. No mutex needed. No allocation. The result is converted to a string with strconv.FormatUint, which is the fastest integer-to-string conversion in Go's standard library.

Why Not UUID?

UUIDs (google/uuid) are globally unique, which sounds appealing. But they have drawbacks for this use case:

Property Atomic Counter UUID v4
Uniqueness Unique within engine instance Globally unique
Ordering Monotonically increasing Random (no ordering)
Size 1-20 chars ("1" to "18446744073709551615") 36 chars ("550e8400-e29b-41d4-a716-446655440000")
Speed ~1ns (atomic add + format) ~200ns (crypto/rand + format)
Readability "ORD-42" "550e8400-e29b-41d4-a716-446655440000"

For a single-instance matching engine, the atomic counter is strictly better. It is faster, smaller, ordered, and human-readable. If the engine were distributed across multiple nodes, UUIDs or a distributed ID service (like Twitter's Snowflake) would be necessary. But that is a different problem for a different architecture.

Why Not Inside the Mutex?

The generateID method uses atomic.AddUint64, which is lock-free. It runs before the engine acquires its mutex in SubmitOrder. This is deliberate:

func (e *Engine) SubmitLimitOrder(symbol string, side model.Side, price, quantity decimal.Decimal) (string, []model.Trade, error) {
    id := e.generateID()  // lock-free, outside mutex
    order := model.NewLimitOrder(id, side, price, quantity)
    trades, err := e.SubmitOrder(symbol, order)  // acquires mutex internally
    return id, trades, err
}
Enter fullscreen mode Exit fullscreen mode

If ID generation were inside the mutex, it would add contention for no reason. The atomic operation is already thread-safe on its own. Keeping it outside the mutex means the critical section is no longer than before.

The Prefix Option

IDs can be prefixed for readability or multi-engine disambiguation:

e := engine.New(engine.WithIDPrefix("ORD-"))
// Generates: "ORD-1", "ORD-2", "ORD-3", ...

e := engine.New(engine.WithIDPrefix("ENGINE-A-"))
// Generates: "ENGINE-A-1", "ENGINE-A-2", ...
Enter fullscreen mode Exit fullscreen mode

The prefix is concatenated at generation time. No extra allocation — strconv.FormatUint returns a string, and + on two strings is a single allocation.

The New API

Three new methods replace the old pattern:

SubmitLimitOrder 

func (e *Engine) SubmitLimitOrder(
    symbol string,
    side model.Side,
    price, quantity decimal.Decimal,
) (string, []model.Trade, error)
Enter fullscreen mode Exit fullscreen mode

The caller provides only what they care about: symbol, side, price, quantity. The engine generates the ID and returns it.

id, trades, err := e.SubmitLimitOrder("BTC/USD", model.Sell, price, qty)
// id = "1" (or "ORD-1" with prefix)
Enter fullscreen mode Exit fullscreen mode

SubmitMarketOrder 

func (e *Engine) SubmitMarketOrder(
    symbol string,
    side model.Side,
    quantity decimal.Decimal,
) (string, []model.Trade, error)
Enter fullscreen mode Exit fullscreen mode

Same pattern, no price parameter (market orders don't have one).

id, trades, err := e.SubmitMarketOrder("BTC/USD", model.Buy, qty)
Enter fullscreen mode Exit fullscreen mode

SubmitRequest

For cases where the order type is determined at runtime (e.g., from a JSON payload), SubmitRequest accepts an OrderRequest struct:

type OrderRequest struct {
    Side     Side
    Type     OrderType
    Price    decimal.Decimal
    Quantity decimal.Decimal
}
Enter fullscreen mode Exit fullscreen mode

No ID field. No timestamp. Just the intent.

req := model.NewLimitOrderRequest(model.Buy, price, qty)
id, trades, err := e.SubmitRequest("BTC/USD", req)
Enter fullscreen mode Exit fullscreen mode

This is particularly useful when deserializing from external input:

// From a REST API handler
var req model.OrderRequest
json.NewDecoder(r.Body).Decode(&req)
id, trades, err := e.SubmitRequest(symbol, req)
Enter fullscreen mode Exit fullscreen mode

The caller never touches an order ID. The engine owns the lifecycle.

Backward Compatibility

The original SubmitOrder method is unchanged:

func (e *Engine) SubmitOrder(symbol string, order *model.Order) ([]model.Trade, error)
Enter fullscreen mode Exit fullscreen mode

It still accepts caller-provided IDs, still checks for duplicates, and still works exactly as before. The new methods are built on top of it — they generate an ID, construct an Order, and call SubmitOrder internally.

This means existing code continues to work without modification. Migration is opt-in.

How the Pieces Fit Together

The call chain for SubmitLimitOrder:

SubmitLimitOrder("BTC/USD", Sell, 50000, 1)
    │
    ├── generateID()              ← atomic, lock-free
    │   └── "ORD-7"
    │
    ├── NewLimitOrder("ORD-7", Sell, 50000, 1)
    │   └── Order{ID: "ORD-7", ...}
    │
    └── SubmitOrder("BTC/USD", order)
        ├── normalize symbol      ← "BTC/USD"
        ├── acquire mutex
        ├── validate symbol
        ├── check duplicate ID    ← "ORD-7" not in index
        ├── match against book
        ├── add to book if unfilled
        ├── record trades
        └── release mutex
Enter fullscreen mode Exit fullscreen mode

The ID is generated before the mutex is acquired. If SubmitOrder returns an error (invalid price, bad symbol, etc.), the ID is "wasted" — the counter has already incremented. This is fine. Gaps in the ID sequence are harmless, and avoiding them would require either rolling back the atomic counter (unsafe) or generating the ID inside the mutex (unnecessary contention).

Testing Concurrency

The most important property of the ID generator is uniqueness under concurrent access. We test this with 10 goroutines each submitting 20 orders simultaneously:

func TestIDsUniqueAcrossGoroutines(t *testing.T) {
    e := New()

    idCh := make(chan string, 200)
    var wg sync.WaitGroup
    for g := 0; g < 10; g++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := 0; i < 20; i++ {
                id, _, _ := e.SubmitLimitOrder("BTC", model.Sell, d("100"), d("1"))
                idCh <- id
            }
        }()
    }
    wg.Wait()
    close(idCh)

    seen := make(map[string]bool)
    for id := range idCh {
        if seen[id] {
            t.Errorf("duplicate ID generated: %s", id)
        }
        seen[id] = true
    }
    if len(seen) != 200 {
        t.Errorf("expected 200 unique IDs, got %d", len(seen))
    }
}
Enter fullscreen mode Exit fullscreen mode

200 orders, 10 goroutines, zero duplicates. The atomic counter guarantees this without any locking.

We also verify monotonic ordering:

func TestIDsAreMonotonicallyIncreasing(t *testing.T) {
    e := New()

    var ids []string
    for i := 0; i < 10; i++ {
        id, _, _ := e.SubmitLimitOrder("BTC", model.Sell, d("100"), d("1"))
        ids = append(ids, id)
    }

    for i := 1; i < len(ids); i++ {
        if ids[i] <= ids[i-1] {
            t.Errorf("IDs not monotonically increasing: %s <= %s", ids[i], ids[i-1])
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Note: monotonic ordering is guaranteed only within a single goroutine. Across goroutines, the IDs are unique but the observation order depends on scheduling. Goroutine A might generate ID 5 before goroutine B generates ID 4, but B might write to the channel first. The IDs themselves are still strictly ordered by their numeric value.

Before and After

Before (caller manages IDs) 

e := engine.New()

// Caller must generate unique IDs
sellID := fmt.Sprintf("sell-%d", time.Now().UnixNano())
sell := model.NewLimitOrder(sellID, model.Sell, price, qty)
trades, err := e.SubmitOrder("BTC/USD", sell)

buyID := fmt.Sprintf("buy-%d", time.Now().UnixNano())
buy := model.NewLimitOrder(buyID, model.Buy, price, qty)
trades, err = e.SubmitOrder("BTC/USD", buy)

// Hope the IDs are unique...
e.CancelOrder("BTC/USD", sellID)
Enter fullscreen mode Exit fullscreen mode

After (engine manages IDs) 

e := engine.New(engine.WithIDPrefix("ORD-"))

sellID, _, _ := e.SubmitLimitOrder("BTC/USD", model.Sell, price, qty)
buyID, trades, _ := e.SubmitLimitOrder("BTC/USD", model.Buy, price, qty)

// IDs are guaranteed unique
e.CancelOrder("BTC/USD", sellID)
Enter fullscreen mode Exit fullscreen mode

Less code, no uniqueness bugs, and the returned IDs are useful for logging, cancellation, and client responses.

Summary

Aspect Before After
ID source Caller-provided string Engine-generated atomic counter
Uniqueness Caller's responsibility (error on duplicate) Guaranteed by engine
Ordering Arbitrary Monotonically increasing
Thread safety N/A (caller's problem) Lock-free atomic operation
API surface SubmitOrder(symbol, *Order) SubmitLimitOrder, SubmitMarketOrder, SubmitRequest
Backward compat N/A SubmitOrder still works

The change is small — one new field on the engine, one three-line method, three thin wrapper methods, and one new OrderRequest type. But it shifts the responsibility for a correctness-critical property (ID uniqueness) from every caller to a single, tested, atomic implementation inside the engine. That is the right place for it.

GitHub: https://github.com/iwtxokhtd83/MatchEngine
Release: v0.4.0
Issue: #6 — Engine should generate unique order IDs internally

Top comments (0)