Domain matching

A single geosite:cn rule expands to roughly 100,000 domain patterns, and the router has to test the target of every new connection against all of them. Checking patterns one by one would make routing the slowest part of the proxy — so common/strmatcher never iterates rules at all. Match cost depends on the length of the domain being looked up, not on the size of the rule list.

One interface, four pattern types — and only two of them scale

Every rule compiles to one of four strmatcher.Type values, and the type decides which data structure it lands in. Full requires exact equality, Domain matches the pattern or any subdomain of it, Substr matches anywhere in the string, and Regex is a compiled regexp.Regexp:

const (
	Full Type = iota   // input == pattern
	Substr             // pattern is a substring of input
	Domain             // input is pattern or a subdomain of it
	Regex              // case-sensitive regexp
)

The generic MatcherGroup (used by the DNS app in app/dns/dns.go) already buckets by type: Full patterns go into a plain map[string][]uint32, Domain patterns into a label trie (DomainMatcherGroup), and everything else into otherMatchers — a slice that is linearly scanned on every match. In this generic group, substr and regex rules never get cheaper than O(rules). The router’s MPH group (below) rescues substrings with an automaton — but regex rules stay a linear scan everywhere.

Domains are matched backwards

Every purpose-built structure in strmatcher — the label trie, the rolling hash, the automaton — consumes the input right-to-left, because a domain rule is a suffix rule — domain:google.com must match www.google.com — and reversing the string turns suffix matching into prefix matching, which tries and rolling hashes handle natively.

DomainMatcherGroup stores patterns as a trie of labels inserted last-label-first: adding v2fly.org creates the path root → org → v2fly. Matching walks the query from its final label backwards, collecting rule ids at every node that has values, so one lookup of www.v2fly.org can hit both org-level and v2fly.org-level rules in a single walk. When several nodes match, the results are emitted deepest-first — the source comments this as “the subdomain that matches further ranks higher”.

The router pays per dot, not per rule

For geosite-scale lists the router builds a minimal perfect hash table, so a lookup does one O(1) probe per . in the target domain — whether the rule set holds a hundred entries or a million. This is not opt-in: app/router/config.go compiles every domain rule with NewMphMatcherGroup, and can even load a pre-built serialized table from disk via the xray.mph.cache env flag to skip build time at startup.

At build time each Domain pattern is inserted twice into the rule map: once as example.com (the exact match) and once as .example.com (the subdomain suffix). Build() then constructs a two-level table: Level0 (sized n/4, rounded to a power of two) maps a Rabin-Karp hash bucket to a per-bucket seed, and the seed is brute-forced — largest buckets first — until every key in the bucket lands in an empty Level1 slot. The result is a hash table with zero collisions by construction.

Matching walks the domain from the end, extending a rolling hash (h = h*16777619 + uint32(s[i])) one byte at a time. Every time it passes a . it already has the hash of that suffix for free, and probes the table:

Because the table is collision-free, verification is a single string comparison against g.Rules[n] — no chains, no probing loops, no per-rule work.

Substrings still need an automaton

Substring patterns can’t be hashed — they can start anywhere — so the MPH group delegates them to an Aho-Corasick automaton and runs it only after the hash lookups miss. The automaton matches all substring patterns simultaneously in one pass over the (reversed) input.

ACAutomaton is a goto/fail automaton over a compressed 53-symbol alphabet: char2Index folds A–Z and a–z into the same 26 indices (matching is case-insensitive by construction) plus digits and URL punctuation. Build() computes fail links with a BFS, then overwrites every missing trie edge with its fail destination — collapsing the goto/fail pair into a plain DFA — so Match never chases fail links at runtime: one table read per input byte. A fullMatch flag tracks whether the walk ever took a fail edge; a Substr hit returns immediately, while Full and Domain hits only count if the entire walk stayed on trie edges (a Domain pattern gets an extra accepting node after a . edge for the subdomain case).