Skip to content

PATTERN Cited by 1 source

Regional forwarding on CIDR trie

When state is partitioned by region but a minority of queries cross regions, avoid global state replication by combining:

  1. A global, compact, read-only index mapping IP/CIDR → region (a trie over all known VPC CIDRs).
  2. A regional-forwarding hop that sends cross-region queries to the peer region's service, where local state answers them.

This replaces global broadcast of fast-moving per-resource state with a much smaller globally-replicated topology table.

When to use

  • State changes are high-volume / high-frequency.
  • Cross-region queries are a small fraction of all queries.
  • The global topology (which regions own which address space / shards) changes slowly.
  • An extra in-fabric forward hop is latency-acceptable for the minority path.

Canonical instance

systems/netflix-flowcollector runs a cluster per AWS region. Cross-regional flow attribution:

  • A regional FlowCollector node receives a flow whose remote IP is outside its region.
  • Lookup in the CIDR trie — keyed on all Netflix VPC CIDRs — returns the remote region.
  • The node forwards the flow to a peer in that region.
  • The peer region resolves the remote IP from its own in-memory heartbeat time-range map.

Only ~1% of Netflix's flows are cross-regional, so forward hops are cheap in aggregate. By contrast, global broadcast of per-IP time ranges would push 100% of updates across regions.

Why a trie

The trie shape matches the structure of CIDR ranges. Walking bit by bit returns the most specific match in O(address-length):

  • IPv4: 32 comparisons worst case.
  • IPv6: 128 comparisons worst case.

Compared to linear scan over a list of CIDRs, a trie is orders of magnitude faster and its size is bounded by the number of CIDRs, not the number of IPs. See concepts/trie-data-structure.

Trade-offs

  • Cross-region latency hop. Adds round-trip across AWS regions for cross-region queries. Acceptable because (a) only ~1% of queries and (b) attribution is not a synchronous user-facing path.
  • Topology drift. CIDR trie must be kept in sync with VPC changes; slower-moving state, easier to keep consistent than per-IP ownership maps.
  • Availability. If the target region is unreachable, cross- region queries fail. Same failure mode as any regional dependency.

Alternatives

  • Global state replication. Pay full cross-region bandwidth for every update so cross-region queries are local reads. Wrong when cross-region queries are a small minority.
  • Client-side routing. Force the caller to hit the correct regional service directly. Works if the caller has topology knowledge; doesn't when the caller only has a remote IP.
  • Two-tier cache. Global cache of cross-region answers; falls back to forward hop on miss. Adds a cache-management axis; often not worth it.

Seen in

Last updated · 319 distilled / 1,201 read