clusterpath

clusterpath is a bounded-memory Go library and CLI for reducing URL cardinality before indexing request streams in ClickHouse or another analytics store. It learns structural path and query patterns online, then emits stable templates.

• Module: github.com/optimiweb/clusterpath
• Go: 1.21 or newer
• License: MIT

Before and after

Properties

• One streaming pass for learning, with optional Freeze for stable replay.
• Fixed-size parsing scratch, cardinality sketches, and heavy-hitter tracking.
• Preallocated slab LRU with an open-addressed uint64 index.
• Zero allocations in Normalize and Apply when the destination has capacity.
• Stateless masking for numeric IDs, long hexadecimal IDs, UUIDs, random tokens, and build fingerprints.
• Learned masking for high-cardinality literal path positions.
• Query-key sorting and typed high-cardinality value templates.
• Shared-nothing worker model through structural sharding.

Placeholder vocabulary

Treat these as part of the output schema when storing templates downstream:

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

How it works

Each URL is parsed and every path segment is classified (numeric id, long hex, UUID, random token, or literal). Obviously machine-generated segments — including build fingerprints in static asset names — are masked immediately (statelessly). The remaining literals and query values are handled online:

1. A structural signature (host, depth, per-position class, extension, and an optional literal prefix) maps each URL to a bucket in a fixed-size LRU.
2. Each bucket estimates distinct-value cardinality and tracks heavy hitters per path position and query key with compact sketches.
3. Once a bucket has enough samples, near-unique positions become placeholders while bounded enumerations (sections, categories, API resources) stay literal.
4. Query keys are sorted; tracking parameters are dropped; high-cardinality values become typed placeholders.

Grouping by structural signature makes clustering O(N) in the number of URLs rather than O(N²): each URL is examined once and routed to its bucket.

Library usage

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

for _, rawURL := range input {
    dst = c.Normalize(dst[:0], rawURL) // learns and renders
    emit(dst)
}

c.Freeze()
dst = c.Apply(dst[:0], rawURL) // stable replay, no learning or LRU changes

Concurrency

A Clusterer belongs to one goroutine, including after Freeze. For parallel ETL:

1. Create a Sharded.
2. Use Shard(rawURL) to route each URL (Shard is safe for concurrent use).
3. Give each At(index) result to exactly one worker.

Clusterers share no mutable model state across shards.

CLI

Two-pass mode (learn, then emit stable templates) against a seekable file:

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

On the included 1,000-URL fixture, the default configuration ends with:

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

For a non-seekable stream, use -two-pass=false. That mode learns and renders in one pass, so earlier output can differ from later output as the model learns.

Query parameters

By default these keys are removed: utm_*, gclid, dclid, fbclid, msclkid, _ga, session*, token, and auth_token.

Session and token keys are dropped so secret or per-user values never land in templates.

• DropParams — change the drop list; pass a non-nil empty slice to disable it.
• KeepParams — retain specific keys even when they would otherwise be dropped or templated.

Memory and performance

• Hot-path memory is preallocated by New; resident memory is bounded by Config.MaxBuckets regardless of stream size.
• Default budget: 4,096 structural buckets (~6 KB each, plus the index).
• If the active set of shapes exceeds MaxBuckets, the LRU evicts buckets and learned reduction quality drops. Monitor Stats() and size the cache above the expected simultaneous shape count per worker.
• Normalize / Apply follow Go's append convention: no allocation when dst has capacity.

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

Tuning cardinality reduction

Fewer clusters is not automatically better: over-masking destroys useful taxonomy (a section name turned into {slug}). The goal is to mask near-unique leaves while keeping bounded enums literal.

On the fixture, defaults yield 30 templates. A more aggressive configuration yields 22 while retaining API endpoint taxonomy:

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

Next

• Budgeted metric clusters — fixed 96-ID dictionaries for hit counters and dashboards.
• Open source overview — other Optimi projects.