Trie, in depth: bitwise tries, longest-prefix match for IP routing, multibit strides, HAMT bitmap nodes and the lock-free Ctrie

Longest-prefix match: the problem bit tries solve

A routing table maps prefixes to next hops. 10.0.0.0/8 means "any address whose first 8 bits match 10". Prefixes nest, and the rule is that the most specific match wins. With routes for /8, /16 and /24 that all contain an address, the /24 decides. That is longest-prefix match (LPM), and it isn't a hash lookup, because you don't know in advance which prefix length will match.

A trie over bits answers it naturally. Insert each prefix as a path of its first L bits and store the next hop at the node where the path ends. To look up an address, walk its bits from the most significant one and remember the last stored value you passed. When the path ends, or the bits run out, the remembered value is the longest match. Prefixes that share leading bits share nodes, and the walk sees every candidate prefix in order of increasing length.

Worked example: a binary trie for routing

Here is a complete binary trie with LPM, in Python. Nodes have two child slots and an optional value. Insertion masks off the host bits first, because a route written as 10.1.2.7/24 means 10.1.2.0/24.

class Node:
    __slots__ = ("child", "value")
    def __init__(self):
        self.child = [None, None]
        self.value = None              # next hop if a prefix ends here

class BinaryTrie:
    def __init__(self, width=32):
        self.root, self.width = Node(), width

    def insert(self, prefix: int, length: int, value):
        prefix &= ~((1 << (self.width - length)) - 1) if length else 0
        node = self.root
        for i in range(length):
            bit = (prefix >> (self.width - 1 - i)) & 1
            if node.child[bit] is None:
                node.child[bit] = Node()
            node = node.child[bit]
        node.value = value

    def lookup(self, addr: int):
        node, best = self.root, self.root.value
        for i in range(self.width):
            node = node.child[(addr >> (self.width - 1 - i)) & 1]
            if node is None:
                break
            if node.value is not None:
                best = node.value      # longest match so far
        return best

The worked example loads four routes: 0.0.0.0/0 to default, 10.0.0.0/8 to A, 10.1.0.0/16 to B, and 10.1.2.0/24 to C. Running the lookups printed: 10.1.2.7 -> C, 10.1.9.9 -> B, 10.200.0.1 -> A, 8.8.8.8 -> default. Take 10.1.9.9: its first 16 bits follow the shared path past A to B, and its 21st bit is 1 where the /24 path has 0, so the walk falls off and returns B. The whole table used 25 nodes, the root plus one 24-node chain, because all three prefixes nest.

Why one bit per level is too slow

The binary trie is correct and compact for nested prefixes, but slow in the way that matters to hardware. Each level is a dependent memory read: you can't fetch level 9 until level 8 tells you where it is. An IPv4 lookup can take 32 of them, and IPv6 up to 128. A cache miss costs on the order of 100 ns, while a line-rate router has a few nanoseconds per packet. Even in software, a trie of millions of routes doesn't fit in cache.

Path compression, the Patricia trie, removes single-child chains by storing a skip count. That cuts node count dramatically on sparse tables, but the depth of the deepest real branch remains. For speed you need fewer, wider levels. Every structure below is a trade between the number of dependent reads and the memory and update cost of wider nodes.

Multibit strides and prefix expansion

A multibit trie consumes k bits per level, so each node is an array of 2^k slots indexed directly by the next k bits. IPv4 with strides 16, 8, 8 needs at most three reads. The catch is that prefixes no longer end on level boundaries. A /9 doesn't correspond to any single slot in a 16-bit first level. Controlled prefix expansion (Srinivasan and Varghese) fixes this by rounding each prefix length up to the next stride boundary and writing it into every slot it covers.

import ipaddress
ip = lambda s: int(ipaddress.IPv4Address(s))

def expand(prefix, length, stride):
    target = -(-length // stride) * stride        # round up to a stride multiple
    extra = target - length
    base = prefix >> (32 - length) << extra if length else 0
    return target, [base | i for i in range(1 << extra)]

expand(ip("10.1.0.0"), 16, 8)     # (16, 1 slot)
expand(ip("10.128.0.0"), 9, 8)    # (16, 128 slots: 0xa80, 0xa81, ...)

That run shows the cost: a /16 lands in one slot, but a /9 becomes 128 slots of /16. When an expanded slot already holds a longer, more specific route, the longer one must win, so inserts compare original lengths, and deletes must restore whatever shorter prefix the slot used to inherit. Updates get expensive in exactly the way lookups got cheap.

The classic extreme is DIR-24-8 (Gupta, Lin and McKeown, 1998): a first table with 2^24 entries indexed by the top 24 bits, and small second-level tables for the rare routes longer than /24. Most lookups take one read and the rest take two, in exchange for tens of megabytes and expensive updates for short prefixes. DPDK's LPM library follows this design. Linux takes the other side of the trade with fib_trie, a level-compressed trie (LC-trie) that picks a stride per node depending on how full the subtree is.

Bitmap nodes and hash array mapped tries

Wide nodes waste memory when most slots are empty. A 32-way node with three children carries 29 null pointers. Bitmap compression stores a 32-bit bitmap with one bit per possible child, plus a dense array of only the children that exist. The array index of child c is the number of set bits below bit c, which modern CPUs compute in one popcount instruction.

def hamt_index(node, chunk):              # chunk: 5 bits of the key, 0..31
    bit = 1 << chunk
    if node.bitmap & bit == 0:
        return None                       # no child: key absent
    return (node.bitmap & (bit - 1)).bit_count()

# a node holding children for chunks 3, 17 and 30:
#   bitmap = 0b1000000000000100000000000001000, slots = [c3, c17, c30]
#   hamt_index(n, 3) -> 0, (n, 17) -> 1, (n, 30) -> 2, (n, 5) -> None

Apply the same trick to the hash of a key, 5 bits per level, and you have Bagwell's hash array mapped trie (HAMT). The hash 0x9E3779B9 splits into the chunks 25, 13, 30 and 14 for levels 0 to 3. Each level consumes the next chunk until a slot holds a single entry. Lookups take about log32(n) levels, which means 4 for a million keys, and nodes stay dense. When two keys share every hash bit, the trie bottoms out in a collision node that is searched linearly. Clojure's persistent maps are HAMTs. Scala 2.13's immutable HashMap uses CHAMP, a refinement with a different node layout that keeps entries and sub-nodes in separate bitmaps for better iteration and equality performance (see Scala collections performance).

Path copying: persistent tries

A trie makes immutable updates cheap through path copying. To change one key, copy the nodes on the path from the root to it, about four of them in a million-entry HAMT, each up to 32 slots, and point the copies at the untouched siblings. The old root still describes the old map and the new root the new one, and they share everything off the path. A map update costs a few small allocations rather than a full copy, and old versions stay valid for as long as someone holds them. That is how a functional program can keep a history of states, or hand a snapshot to another thread without locking.

The same idea serves routing control planes. Build the new forwarding table by path-copying the changed routes, then publish the new root with one atomic pointer store. Readers on the data path either see the old table or the new one, never a half-updated node. Old versions are freed once readers have moved on, with read-copy-update (RCU) in the Linux kernel or the garbage collector in managed languages.

Concurrent tries: the Ctrie

Path copying gives one writer and many readers. The Ctrie (Prokopec, Bronson, Bagwell and Odersky, 2012) allows many concurrent writers without locks. It is a HAMT with one extra level of indirection: every bitmap node, a C-node, hangs off an I-node. A writer copies the C-node with its change and uses compare-and-swap on the I-node to install it. If another writer got there first, the CAS fails and the writer retries from that I-node. Readers never block. Removals leave tombstone nodes that later operations compress, so the trie doesn't keep empty branches.

The design's notable feature is a constant-time snapshot. A generation tag on I-nodes plus a double-compare primitive (GCAS) let a snapshot be taken by swapping the root. Nodes are then copied lazily, as later operations touch them. Scala ships this as scala.collection.concurrent.TrieMap, with snapshot() and readOnlySnapshot(). That makes consistent iteration over a map that's being updated cheap, which is something ConcurrentHashMap deliberately doesn't offer (its iterators are only weakly consistent).

Failure modes

• Unmasked host bits. Inserting 10.1.2.7/24 without masking creates a path no lookup matches the way you intended. Normalise when parsing, as the code above does.
• Bit-order and width bugs. Walking from the least significant bit, or mixing IPv4 and IPv4-mapped IPv6 in one trie, gives plausible but wrong matches. Keep one trie per address family and test the edge cases /0 and /32.
• Expansion blowup. Short prefixes in a wide first level expand into thousands or millions of slots. A route flap of one /9 rewrites 128 slots, or about 32,000 in DIR-24-8. Measure update latency as well as lookup latency.
• Lost shorter routes on delete. When an expanded slot's owner is deleted, it must fall back to the next shorter covering prefix, not to empty. Keep the original prefixes in a side structure so expansion can be recomputed.
• Hash flooding. A HAMT over an attacker-chosen key set with a weak or unseeded hash degenerates into deep collision nodes. Use the platform's seeded hashing for untrusted keys.
• Object overhead. A node per bit in Python or Java can cost 50 bytes or more each. Benchmark with real tables, and prefer arrays of integers for anything large.

Choosing a bitwise trie

What to do next

1. Implement the binary trie above, and test it against a brute-force scan over every prefix, using random addresses plus the /0 and /32 edge cases.
2. Add a fixed-stride version (16, 8, 8) with controlled prefix expansion. Measure lookup and update time and memory with a real route table dump.
3. Write the delete path for the expanded version and check that slots fall back to the right shorter prefix.
4. Implement a small HAMT with 5-bit chunks and popcount indexing, then make it persistent with path copying and confirm that old versions are unchanged.
5. Read a production implementation, such as DPDK's LPM, Linux fib_trie or Scala's TrieMap, and map its parts onto this page.
6. Before choosing a structure, write down your ratio of lookups to updates and your memory budget. Those two numbers decide the row of the table above.