natsdotnet/Documentation/Subscriptions/SubList.md

SubList

SubList is the subscription routing trie for the core server. Every publish path calls Match() to find the local plain subscribers and queue groups interested in a subject. The type also tracks remote route and gateway interest so clustering code can answer HasRemoteInterest(...) and MatchRemote(...) queries without a second routing structure.

Go reference: golang/nats-server/server/sublist.go

---

Thread Safety

SubList uses a single ReaderWriterLockSlim (_lock) to protect trie mutation, remote-interest bookkeeping, and cache state.

Operation	Lock
Cache hit in Match()	Read lock
Cache miss in Match()	Write lock
Insert() / Remove() / RemoveBatch()	Write lock
Remote-interest mutation (ApplyRemoteSub, UpdateRemoteQSub, cleanup)	Write lock
Read-only queries (Count, HasRemoteInterest, MatchRemote, Stats)	Read lock

Match() uses generation-based double-checked locking. It first checks the cache under a read lock, then retries under the write lock before traversing the trie and updating the cache.

---

Trie Structure

The trie is built from TrieLevel and TrieNode:

private sealed class TrieLevel
{
    public readonly Dictionary<string, TrieNode> Nodes = new(StringComparer.Ordinal);
    public TrieNode? Pwc;
    public TrieNode? Fwc;
}

private sealed class TrieNode
{
    public TrieLevel? Next;
    public readonly HashSet<Subscription> PlainSubs = [];
    public readonly Dictionary<string, HashSet<Subscription>> QueueSubs = new(StringComparer.Ordinal);
    public bool PackedListEnabled;
}

• Nodes stores literal-token edges by exact token string.
• Pwc stores the * edge for the current token position.
• Fwc stores the > edge for the current token position.
• PlainSubs stores non-queue subscriptions attached to the terminal node.
• QueueSubs groups queue subscriptions by queue name at the terminal node.

The root of the trie is _root, a TrieLevel with no parent node.

---

Token Traversal

TokenEnumerator walks a subject string token-by-token using ReadOnlySpan<char> slices, so traversal itself does not allocate. Literal-token insert and remove paths use TryGetLiteralNode(...) plus SubjectMatch.TokenEquals(...) to reuse the existing trie key string when the token is already present, instead of calling token.ToString() on every hop.

That keeps literal-subject maintenance allocation-lean while preserving the current Dictionary<string, TrieNode> storage model.

---

Local Subscription Operations

Insert

Insert(Subscription sub) walks the trie one token at a time:

• * follows or creates Pwc
• > follows or creates Fwc and terminates further token traversal
• literal tokens follow or create Nodes[token]

The terminal node stores the subscription in either PlainSubs or the appropriate queue-group bucket in QueueSubs. Every successful insert increments _generation, which invalidates cached match results.

Remove

Remove(Subscription sub) and RemoveBatch(IEnumerable<Subscription>) walk the same subject path, remove the subscription from the terminal node, and then prune empty trie nodes on the way back out. Removing a subscription also bumps _generation, so any stale cached result is ignored on the next lookup.

---

Remote Interest Bookkeeping

Remote route and gateway subscriptions are stored separately from the local trie in _remoteSubs:

private readonly Dictionary<RoutedSubKey, RemoteSubscription> _remoteSubs = [];

RoutedSubKey is a compact value key:

internal readonly record struct RoutedSubKey(
    string RouteId,
    string Account,
    string Subject,
    string? Queue);

This replaces the earlier "route|account|subject|queue" composite string model. The change removes repeated string concatenation, Split('|'), and runtime reparsing in remote cleanup paths.

Remote-interest APIs:

• ApplyRemoteSub(...) inserts or removes a RemoteSubscription
• UpdateRemoteQSub(...) updates queue weight for an existing remote queue subscription
• RemoveRemoteSubs(routeId) removes all remote interest for a disconnected route
• RemoveRemoteSubsForAccount(routeId, account) removes only one route/account slice
• HasRemoteInterest(account, subject) answers whether any remote subscription matches
• MatchRemote(account, subject) returns the expanded weighted remote matches

Cleanup paths collect matching RoutedSubKey values into a reusable per-thread list and then remove them, avoiding _remoteSubs.ToArray() snapshots on every sweep.

---

Match Pipeline

Match(string subject) is the hot path.

1. Increment _matches
2. Read the current _generation
3. Try the cache under a read lock
4. On cache miss, tokenize the subject and retry under the write lock
5. Traverse the trie and build a SubListResult
6. Cache the result with the generation that produced it

Cached entries are stored as:

private readonly record struct CachedResult(SubListResult Result, long Generation);

A cache entry is valid only if its stored generation matches the current _generation. Any local or remote-interest mutation increments _generation, so stale entries are ignored automatically.

Match Builder

Cache misses use a reusable per-thread MatchBuilder instead of allocating fresh nested List<List<Subscription>> structures on every traversal. The builder:

• reuses a List<Subscription> for plain subscribers
• reuses queue-group lists across matches
• merges queue matches by queue name during traversal
• materializes the public SubListResult arrays only once at the end

This keeps the public contract unchanged while removing temporary match-building churn from the publish path.

Intentional Remaining Allocations

The current implementation still allocates in two places by design:

• the tokenized string[] produced by Tokenize(subject) on cache misses
• the final Subscription[] and Subscription[][] arrays stored in SubListResult

Those allocations are part of the current public result shape and cache model.

---

Cache Strategy

The cache is a Dictionary<string, CachedResult> keyed by literal publish subject with StringComparer.Ordinal.

• CacheMax = 1024
• CacheSweep = 256

When the cache grows past CacheMax, SubListCacheSweeper schedules a sweep that removes enough keys to return to the target size. The sweep is intentionally simple; it is not LRU.

The cache stores fully materialized SubListResult instances because publish callers need stable array-based results immediately after lookup.

---

Statistics and Monitoring

Stats() exposes:

• subscription count
• cache entry count
• insert/remove/match counts
• cache hit rate
• fanout statistics derived from cached results

These counters are used by tests and monitoring code to validate routing behavior and cache effectiveness.

---

Related Documentation

• Overview