clusterpath

clusterpath est une bibliothèque Go et un CLI à mémoire bornée pour réduire la cardinalité des URL avant d'indexer des flux de requêtes dans ClickHouse ou un autre store analytique. Il apprend des modèles structurels de chemin et de requête en ligne, puis émet des templates stables.

• Module : github.com/optimiweb/clusterpath
• Go : 1.21 ou plus récent
• Licence : MIT

Avant / après

Propriétés

• Une passe de streaming pour l'apprentissage, avec Freeze optionnel pour un replay stable.
• Scratch de parsing, sketches de cardinalité et suivi des heavy hitters à taille fixe.
• LRU en slab préallouée avec index uint64 à adressage ouvert.
• Zéro allocation dans Normalize et Apply lorsque la destination a la capacité.
• Masquage stateless pour IDs numériques, longs IDs hexadécimaux, UUID, tokens aléatoires et empreintes de build.
• Masquage appris pour les positions de chemin littérales à forte cardinalité.
• Tri des clés de requête et templates typés pour les valeurs à forte cardinalité.
• Modèle workers shared-nothing via sharding structurel.

Vocabulaire de placeholders

Traitez-le comme partie du schéma de sortie lorsque vous stockez les templates en aval :

{id}, {hex}, {uuid}, {token}, {slug}, {value}, {hash}, {more}

Comment ça marche

Chaque URL est parsée et chaque segment de chemin est classé (id numérique, long hex, UUID, token aléatoire ou littéral). Les segments manifestement générés par machine — y compris les empreintes de build dans les noms d'assets statiques — sont masqués immédiatement (stateless). Les littéraux restants et les valeurs de requête sont traités en ligne :

1. Une signature structurelle (hôte, profondeur, classe par position, extension, et un préfixe littéral optionnel) mappe chaque URL vers un bucket d'une LRU à taille fixe.
2. Chaque bucket estime la cardinalité des valeurs distinctes et suit les heavy hitters par position de chemin et clé de requête avec des sketches compactes.
3. Une fois qu'un bucket a assez d'échantillons, les positions quasi uniques deviennent des placeholders tandis que les énumérations bornées (sections, catégories, ressources API) restent littérales.
4. Les clés de requête sont triées ; les paramètres de tracking sont supprimés ; les valeurs à forte cardinalité deviennent des placeholders typés.

Le regroupement par signature structurelle rend le clustering O(N) en nombre d'URL plutôt que O(N²) : chaque URL est examinée une fois et routée vers son bucket.

Utilisation bibliothèque

c := clusterpath.New(clusterpath.DefaultConfig())
dst := make([]byte, 0, 512)

for _, rawURL := range input {
    dst = c.Normalize(dst[:0], rawURL) // apprend et rend
    emit(dst)
}

c.Freeze()
dst = c.Apply(dst[:0], rawURL) // replay stable, sans apprentissage ni mutation LRU

Concurrence

Un Clusterer appartient à une goroutine, y compris après Freeze. Pour un ETL parallèle :

1. Créez un Sharded.
2. Utilisez Shard(rawURL) pour router chaque URL (Shard est sûr en concurrence).
3. Donnez chaque résultat At(index) à exactement un worker.

Les clusterers ne partagent aucun état de modèle mutable entre shards.

CLI

Mode deux passes (apprendre, puis émettre des templates stables) sur un fichier seekable :

go run ./cmd/clusterpath \
  -in testdata/url-clusters.txt \
  -out normalized.paths \
  -report clusters.tsv

Sur la fixture incluse de 1 000 URL, la configuration par défaut se termine par :

# paths=1000 clusters=30 buckets=10 evictions=0

Pour un flux non seekable, utilisez -two-pass=false. Ce mode apprend et rend en une passe : la sortie précoce peut différer de la sortie tardive à mesure que le modèle apprend.

Paramètres de requête

Par défaut ces clés sont supprimées : utm_*, gclid, dclid, fbclid, msclkid, _ga, session*, token et auth_token.

Les clés session et token sont écartées pour que des valeurs secrètes ou par-utilisateur ne se retrouvent jamais dans les templates.

• DropParams — modifier la liste de suppression ; passer une slice vide non nulle pour la désactiver.
• KeepParams — conserver des clés spécifiques même si elles seraient sinon supprimées ou templatées.

Mémoire et performance

• La mémoire du hot path est préallouée par New ; la mémoire résidente est bornée par Config.MaxBuckets indépendamment de la taille du flux.
• Budget par défaut : 4 096 buckets structurels (~6 Ko chacun, plus l'index).
• Si l'ensemble actif de formes dépasse MaxBuckets, la LRU évince des buckets et la qualité de réduction apprise chute. Surveillez Stats() et dimensionnez le cache au-dessus du nombre de formes simultanées attendues par worker.
• Normalize / Apply suivent la convention append de Go : aucune allocation lorsque dst a la capacité.

go test ./...
go test -run '^$' -bench . -benchmem

Régler la réduction de cardinalité

Moins de clusters n'est pas automatiquement mieux : le sur-masquage détruit une taxonomie utile (un nom de section devenu {slug}). L'objectif est de masquer les feuilles quasi uniques tout en gardant les enums bornés littéraux.

Sur la fixture, les défauts donnent 30 templates. Une configuration plus agressive en donne 22 tout en conservant la taxonomie d'endpoints API :

go run ./cmd/clusterpath -in testdata/url-clusters.txt -report clusters.tsv \
  -signature-prefix -1 -min-samples 8 -distinct-limit 48 -high-card-ratio 0.8

Suite

• Clusters métriques budgetés — dictionnaires fixes à 96 IDs pour compteurs de hits et dashboards.
• Vue d'ensemble open source — autres projets Optimi.