Problématique : pourquoi éviter map + slice pour un carnet d'ordres

Lors d'un test de charge sur un moteur de matching d'options traitant 2 millions d'ordres limites par seconde, le profilage CPU révèle deux points critiques :

• runtime.mapaccess2_fast64 consomme 18% du CPU — recherche de niveau par hashmap
• runtime.growSlice consomme 11% du CPU — expansion des slices d'ordres à chaque niveau de prix

Trois causes fondamentales sont identifiées :

• La recherche par map implique un calcul de hash puis un parcours de buckets, coûtant 40 à 60ns par accès, soit la moitié du budget temporel
• L'ajout d'ordres dans chaque slice de niveau déclenche fréquemment growSlice, surtout en pic où 3 à 5 ordres s'accumulent par niveau
• Le GC scanne les tableaux sous-jacents des maps et slices ; avec 500 000 niveaux résidents, chaque STW dure 2 à 3ms, et trois STW consécutifs font passer le P99 de 80ns à plus de 2μs

La conclusion est claire : concevoir un carnet d'ordres de moteur de matching n'est pas un exercice de structure de données, mais un exercice de disposition mémoire. L'approche LMAX Disruptor — pré-allocation, emplacements de taille fixe, indexation par modulo — se transpose au carnet d'ordres en remplaçant chaque slice de niveau par un RingBuffer de capacité fixe, et en encodant le prix comme indice de tableau plutôt que comme clé de map.

Choix d'architecture : encodage prix → niveau

Les options et crypto-monnaies partagent une caractéristique clé : les ordres se concentrent autour du prix courant ± N niveaux. Par exemple, si le BTC est à 90 000, les niveaux actifs se situent entre 89 990 et 90 010, soit une vingtaine de niveaux.

Le principe consiste à encoder le prix en indice de tableau via une transformation de coordonnées avec un prix de base et un pas de cotation :

// engine/priceindex.go
package engine

const TickInterval = 100 // 100 satoshis par niveau, contexte BTC

func PrixVersIndice(prixFondation, prix int64) int {
    ecart := (prix - prixFondation) / TickInterval
    return int(ecart)
}

func IndiceVersPrix(prixFondation int64, indice int) int64 {
    return prixFondation + int64(indice)*TickInterval
}

Structure centrale : un mini RingBuffer par niveau

Au lieu d'un RingBuffer global unique (rôle du Disruptor), chaque niveau possède son propre mini RingBuffer. La sémantique du matching est « priorité par prix, puis par temps à prix égal », ce qui correspond à un FIFO au sein d'un même niveau.

// engine/niveau.go
package engine

import (
    "sync/atomic"
    _ "unsafe"
)

const capaciteNiveau = 64

type Ordre struct {
    Identifiant int64
    Prix       int64
    Quantite   int64
    Sequence   uint32
    Cote       uint8
    _          [3]byte // alignement 32 octets
}

type Niveau struct {
    // Zone chaude : 64 octets pour une cache line dédiée
    compteur  uint64    // séquence d'écriture, atomique
    tete      uint32    // curseur de consommation
    queue     uint32    // curseur de production
    _         [5]uint32 // padding jusqu'à 64 octets

    emplacements [capaciteNiveau]Ordre
    suivant      *Niveau
}

Le faux partage (false sharing) doit impérativement être éliminé : si compteur, tete et queue sont adjacents à emplacements[0], le producteur écrivant le compteur et le consommateur lisant le premier emplacement provoquent des allers-retours incessants de la même cache line entre cœurs L1, faisant passer une opération de 11ns à 47ns. Le padding [5]uint32 pousse la zone chaude à 64 octets, occupant une cache line entière.

Vérification de l'efficacité du padding :

// engine/layout_test.go
func TestDispositionNiveau(t *testing.T) {
    var n Niveau
    offsetCompteur := unsafe.Offsetof(n.compteur)       // 0
    offsetEmplacements := unsafe.Offsetof(n.emplacements) // doit valoir 64
    if offsetEmplacements != 64 {
        t.Fatalf("padding défectueux : emplacements à %d, attendu 64", offsetEmplacements)
    }
}

Chemin d'écriture : ajout sans verrou par niveau

Plusieurs goroutines peuvent simultanément placer des ordres au même niveau. L'obtention du numéro de séquence se fait via une opération atomique :

// engine/niveau.go (suite)
func (n *Niveau) deposer(o Ordre) (reussi bool, complet *Niveau) {
    s := atomic.AddUint64(&n.compteur, 1) - 1
    pos := s % capaciteNiveau

    teteActuelle := atomic.LoadUint32(&n.tete)
    if s-uint64(teteActuelle) >= capaciteNiveau {
        return false, n
    }

    n.emplacements[pos] = o
    atomic.StoreUint32(&n.queue, uint32(s+1))
    return true, nil
}

Le chemin de lecture est plus simple — le consommateur (moteur de matching) est une goroutine unique balayant les niveaux en série, garantissant la priorité de prix. tete n'a donc pas besoin de lecture atomique :

func (n *Niveau) extraire() (Ordre, bool) {
    if n.tete >= n.queue {
        return Ordre{}, false
    }
    o := n.emplacements[n.tete%capaciteNiveau]
    n.tete++
    return o, true
}

Le « sans verrou » du carnet d'ordres ne signifie pas une absence totale de verrou, mais plutôt : chemin d'écriture (placement d'ordre) sans verrou, chemin de lecture (matching) en goroutine unique sans concurrence. Tenter de paralléliser le matching est une erreur : la sémantique de priorité de prix l'interdit.

Carnet d'ordres : carnet double sens et pointeurs de meilleur prix

// engine/carnet.go
package engine

import (
    "sync"
    "sync/atomic"
)

const (
    coteVente = 0
    coteAchat = 1
    rayonMax  = 4096
)

type Carnet struct {
    prixFondation int64
    ventes       []*Niveau
    achats       []*Niveau
    meilleureVente int32
    meilleurAchat  int32
    verrou        sync.Mutex
}

func NouveauCarnet(prixFondation int64) *Carnet {
    c := &Carnet{
        prixFondation: prixFondation,
        ventes:       make([]*Niveau, rayonMax),
        achats:       make([]*Niveau, rayonMax),
        meilleureVente: rayonMax,
        meilleurAchat:  0,
    }
    for i := 0; i < 32; i++ {
        c.ventes[i] = &Niveau{}
        c.achats[i] = &Niveau{}
    }
    return c
}

Point d'entrée pour le placement d'ordres limites :

func (c *Carnet) PlacerLimite(o Ordre) {
    idx := PrixVersIndice(c.prixFondation, o.Prix)
    var cote int
    if o.Cote == 'V' {
        cote = coteVente
    } else {
        cote = coteAchat
    }

reessayer:
    var n *Niveau
    if cote == coteVente {
        n = c.obtenirVente(idx)
    } else {
        n = c.obtenirAchat(idx)
    }
    if n == nil {
        n = c.allouerNiveau(cote, idx)
    }

    ok, plein := n.deposer(o)
    if !ok {
        plein.suivant = &Niveau{}
        goto reessayer
    }

    if cote == coteVente {
        for {
            ancien := atomic.LoadInt32(&c.meilleureVente)
            if idx >= int(ancien) && ancien != rayonMax {
                break
            }
            if atomic.CompareAndSwapInt32(&c.meilleureVente, ancien, int32(idx)) {
                break
            }
        }
    } else {
        for {
            ancien := atomic.LoadInt32(&c.meilleurAchat)
            if idx <= int(ancien) && ancien != 0 {
                break
            }
            if atomic.CompareAndSwapInt32(&c.meilleurAchat, ancien, int32(idx)) {
                break
            }
        }
    }
}

func (c *Carnet) obtenirVente(idx int) *Niveau {
    if idx >= len(c.ventes) {
        return nil
    }
    return c.ventes[idx]
}

func (c *Carnet) obtenirAchat(idx int) *Niveau {
    if idx >= len(c.achats) {
        return nil
    }
    return c.achats[idx]
}

func (c *Carnet) allouerNiveau(cote, idx int) *Niveau {
    c.verrou.Lock()
    defer c.verrou.Unlock()
    n := &Niveau{}
    if cote == coteVente {
        if idx >= len(c.ventes) {
            nouveau := make([]*Niveau, idx+256)
            copy(nouveau, c.ventes)
            c.ventes = nouveau
        }
        c.ventes[idx] = n
    } else {
        if idx >= len(c.achats) {
            nouveau := make([]*Niveau, idx+256)
            copy(nouveau, c.achats)
            c.achats = nouveau
        }
        c.achats[idx] = n
    }
    return n
}

Cœur du matching : balayage du meilleur prix, exécution, avancement du curseur

// engine/matching.go
package engine

func (c *Carnet) BoucleMatching(canalTrade chan<- Transaction) {
    for {
        meilleurVente := atomic.LoadInt32(&c.meilleureVente)
        meilleurAchat := atomic.LoadInt32(&c.meilleurAchat)

        prixVente := IndiceVersPrix(c.prixFondation, int(meilleurVente))
        prixAchat := IndiceVersPrix(c.prixFondation, int(meilleurAchat))

        if prixAchat < prixVente {
            continue
        }

        nivVente := c.ventes[meilleurVente]
        nivAchat := c.achats[meilleurAchat]
        ordreVente, vOk := nivVente.extraire()
        ordreAchat, aOk := nivAchat.extraire()

        if !vOk || !aOk {
            c.avancerMeilleur()
            continue
        }

        quantiteExecutee := min(ordreVente.Quantite, ordreAchat.Quantite)
        tx := Transaction{
            Prix:          ordreVente.Prix,
            Quantite:      quantiteExecutee,
            IDOrdreVente: ordreVente.Identifiant,
            IDOrdreAchat: ordreAchat.Identifiant,
        }
        canalTrade <- tx
    }
}

func (c *Carnet) avancerMeilleur() {
    for i := atomic.LoadInt32(&c.meilleureVente); i < int32(len(c.ventes)); i++ {
        n := c.ventes[i]
        if n != nil && atomic.LoadUint32(&n.tete) < atomic.LoadUint32(&n.queue) {
            atomic.StoreInt32(&c.meilleureVente, i)
            break
        }
    }
}

Résultats de benchmark (16 cœurs, 64 Go RAM, Go 1.22, 2M QPS mixte)

Le chiffre de 11ns se décompose ainsi : atomic.AddUint64 (4ns) + vérification de borne seq-head (2ns) + écriture emplacements[pos] (3ns) + retour (2ns). L'élimination du hash de map, du growSlice et du scan GC explique l'essentiel du gain.

Instrumentation Prometheus

// engine/metrics.go
var (
    totalDepots = promauto.NewCounterVec(
        prometheus.CounterOpts{
            Namespace: "matching",
            Name:      "depots_total",
        }, []string{"cote"})

    profondeurCarnet = promauto.NewGaugeVec(
        prometheus.GaugeOpts{
            Namespace: "matching",
            Name:      "profondeur",
        }, []string{"cote", "indice_prix"})

    latenceMatching = promauto.NewHistogram(
        prometheus.HistogramOpts{
            Namespace: "matching",
            Name:      "latence_matching_ns",
            Buckets:   []float64{50, 100, 200, 500, 1000, 5000},
        })
)

Alertes clés :

• latence_matching_ns{bucket="5000"} non nul → la goroutine de matching souffre de latence d'ordonnancement, vérifier les limites cgroup sur GOMAXPROCS
• profondeur_carnet{cote="vente"} dépassant 1000 sur un niveau → accumulation unilatérale, alerter le contrôle des risques

Limites et cas d'inadaptation

Cette approche n'est pas universelle :

• Rayon de carnet imprévisible (par exemple actions dont le prix saute de 10x) : l'encodage prixFondation + indice est inadapté, préférer un grand tableau indexé par prix ou un B+Tree
• Concurernce extrême par niveau (plus de 100 ordres par microseconde) : atomic.AddUint64 devient un goulot, il faut sharder chaque niveau en plusieusr sous-buckets en round-robin
• Besoin de relecture persistante : ajouter un préfixe WAL vers etcd ou RocksDB, mais c'est un sujet distinct

Les équipes utilisant sync.Map ou map + mutex sans atteindre 500k QPS ni un P99 sous la microseconde n'ont pas besoin de refondre — la différence entre « fonctionnel » et « performant » relève du stade commercial, pas de la maîtrise technique.

Organisation du code

moteur-matching/
├── main.go                  # entrée benchmark : 2M QPS mixte
├── engine/
│   ├── carnet.go            # carnet double sens + pointeurs meilleur prix
│   ├── niveau.go            # mini RingBuffer par niveau, padding antifaux-partage
│   ├── priceindex.go        # encodage coordonnées prixFondation + tick
│   ├── matching.go          # boucle de matching, balayage meilleur prix
│   ├── metrics.go           # instrumentation Prometheus
│   └── layout_test.go       # vérification cache line 64 octets
├── bench/
│   └── bench_test.go        # go test -bench=. -benchtime=10s -count=3
└── README.md