# 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`:

```csharp
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`:

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

`RoutedSubKey` is a compact value key:

```csharp
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:

```csharp
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](Overview.md)

<!-- Last verified against codebase: 2026-03-13 -->
