iptrie

README

iptrie

Highly performant IP storage & lookup using a trie in Golang.

The trie is a compressed IP radix trie implementation, similar to what is described at https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-linux. Path compression is used to merge nodes with only one child into their parent, decreasing the amount of traversals needed when looking up a value.

This project was originally derived from cidranger.

Path compressed trie

This is visualization of a trie storing CIDR blocks 128.0.0.0/2 192.0.0.0/2 200.0.0.0/5 without path compression, the 0/1 number on the path indicates the bit value of the IP address at specified bit position, hence the path from root node to a child node represents a CIDR block that contains all IP ranges of its children, and children's children.

Visualization of trie storing same CIDR blocks with path compression, improving both lookup speed and memory footprint.

Getting Started

Configure imports.

import (
  "net"
  "net/netip"

  "github.com/phemmer/go-iptrie"
)

Create a new ranger implemented using Path-Compressed prefix trie.

ipt := iptrie.NewTrie()

Inserts CIDR blocks.

ipt.Insert(netip.MustParsePrefix("10.0.0.0/8"), "foo")
ipt.Insert(netip.MustParsePrefix("10.1.0.0/16"), "bar")
ipt.Insert(netip.MustParsePrefix("192.168.0.0/24"), nil)
ipt.Insert(netip.MustParsePrefix("192.168.1.1/32"), nil)

The prefix trie can be visualized as:

ipt.String()

::/0
├ ::ffff:0.0.0.0/96
├ ├ ::ffff:10.0.0.0/104 • foo
├ ├ ├ ::ffff:10.1.0.0/112 • bar
├ ├ ::ffff:192.168.0.0/119
├ ├ ├ ::ffff:192.168.0.0/120 • <nil>
├ ├ ├ ::ffff:192.168.1.1/128 • <nil>

^{^ Note that addresses are normalized to IPv6}

To test if given IP is contained in the trie:

ipt.Contains(netip.MustParseAddr("10.0.0.1")) // returns true
ipt.Contains(netip.MustParseAddr("11.0.0.1")) // returns false

To get all the networks containing the given IP:

ipt.ContainingNetworks(netip.MustParseAddr("10.1.0.0"))

Bulk inserts

For insertion of a large number (millions) of addresses, it will likely be much faster to use TrieLoader.

ipt := iptrie.NewTrie()
loader := iptrie.NewTrieLoader(ipt)

for network in []string{
    "10.0.0.0/8",
    "10.1.0.0/16",
    "192.168.0.0/24",
    "192.168.1.1/32",
} {
    loader.Insert(netip.MustParsePrefix(network), "net=" + network))
}

Benchmark

The below table represents the results of benchmarking operations against different IP tree implementations. Full details can be found here.

These results measure the performance of each test. The value is the number of operations per second, with the percentage compared to the fastest result in parentheses.

(OPs/Sec)	IPTrie	Infoblox	NRadix	Ranger
LoadNets Random	187,028 (43.0%)	157,774 (36.3%)	434,458 (100.0%)	12,856 (3.0%)
LoadNets Sorted	500,611 (88.6%)	198,723 (35.2%)	564,891 (100.0%)	18,555 (3.3%)
Read Check	10,757,118 (100.0%)	2,335,254 (21.7%)	4,818,485 (44.8%)	7,099,999 (66.0%)
Read Lookup	2,680,126 (100.0%)	2,661,177 (99.3%)	N/A	439,872 (16.4%)

Name	Package	Repo
IPTrie	github.com/phemmer/go-iptrie	https://www.github.com/phemmer/go-iptrie
Infoblox	github.com/infobloxopen/go-trees/iptree	https://github.com/infobloxopen/go-trees/
NRadix	github.com/asergeyev/nradix	https://github.com/asergeyev/nradix
Ranger	github.com/yl2chen/cidranger	https://github.com/yl2chen/cidranger/

Documentation

Overview

Package iptrie provides an IP/network tree (trie) implementation for fast IP address lookups.

Index

• type Trie
  • func NewTrie() *Trie
  • func (pt *Trie) ContainingNetworks(ip netip.Addr) []netip.Prefix
  • func (pt *Trie) Contains(ip netip.Addr) bool
  • func (pt *Trie) CoveredNetworks(network netip.Prefix) []netip.Prefix
  • func (pt *Trie) Find(ip netip.Addr) any
  • func (pt *Trie) FindLargest(ip netip.Addr) any
  • func (pt *Trie) Insert(network netip.Prefix, value any)
  • func (pt *Trie) Remove(network netip.Prefix) any
  • func (pt *Trie) String() string
• type TrieLoader
  • func NewTrieLoader(trie *Trie) *TrieLoader
  • func (ptl *TrieLoader) Insert(pfx netip.Prefix, v any)

Examples

• Trie
• Trie.String
• TrieLoader

Types

type Trie

type Trie struct {
	// contains filtered or unexported fields
}

Trie is a compressed IP radix trie implementation, similar to what is described at https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-linux

Path compression merges nodes with only one child into their parent, decreasing the amount of traversals needed when looking up a value.

Example

ipt := NewTrie()
ipt.Insert(netip.MustParsePrefix("10.0.0.0/8"), "foo")
ipt.Insert(netip.MustParsePrefix("10.1.0.0/24"), "bar")

fmt.Printf("10.2.0.1: %+v\n", ipt.Find(netip.MustParseAddr("10.2.0.1")))
fmt.Printf("10.1.0.1: %+v\n", ipt.Find(netip.MustParseAddr("10.1.0.1")))
fmt.Printf("11.0.0.1: %+v\n", ipt.Find(netip.MustParseAddr("11.0.0.1")))

Output:

10.2.0.1: foo
10.1.0.1: bar
11.0.0.1: <nil>

func NewTrie

func NewTrie() *Trie

NewTrie creates a new Trie.

func (*Trie) ContainingNetworks

func (pt *Trie) ContainingNetworks(ip netip.Addr) []netip.Prefix

ContainingNetworks returns the list of networks containing the given ip in ascending prefix order (largest network to smallest).

Note: Inserted addresses are normalized to IPv6, so the returned list will be IPv6 only.

func (*Trie) Contains

func (pt *Trie) Contains(ip netip.Addr) bool

Contains indicates whether the trie contains the given ip.

func (*Trie) CoveredNetworks

func (pt *Trie) CoveredNetworks(network netip.Prefix) []netip.Prefix

CoveredNetworks returns the list of networks contained within the given network.

Note: Inserted addresses are normalized to IPv6, so the returned list will be IPv6 only.

func (*Trie) Find

func (pt *Trie) Find(ip netip.Addr) any

Find returns the value from the most specific network (largest prefix) containing the given address.

func (*Trie) FindLargest

func (pt *Trie) FindLargest(ip netip.Addr) any

FindLargest returns the value from the largest network (smallest prefix) containing the given address.

func (*Trie) Insert

func (pt *Trie) Insert(network netip.Prefix, value any)

Insert inserts an entry into the trie.

func (*Trie) Remove

func (pt *Trie) Remove(network netip.Prefix) any

Remove removes the entry identified by given network from trie.

func (*Trie) String

func (pt *Trie) String() string

String returns string representation of trie.

The result will contain implicit nodes which exist as parents for multiple entries, but can be distinguished by the lack of a value.

Note: Addresses are normalized to IPv6.

Example

inserts := []string{"192.168.0.0/24", "192.168.1.0/24", "192.168.1.0/30"}
trie := NewTrie()
for _, insert := range inserts {
	network := netip.MustParsePrefix(insert)
	trie.Insert(network, "net="+insert)
}
fmt.Println(trie.String())

Output:

::/0
├ ::ffff:192.168.0.0/119
├ ├ ::ffff:192.168.0.0/120 • net=192.168.0.0/24
├ ├ ::ffff:192.168.1.0/120 • net=192.168.1.0/24
├ ├ ├ ::ffff:192.168.1.0/126 • net=192.168.1.0/30

type TrieLoader

type TrieLoader struct {
	// contains filtered or unexported fields
}

TrieLoader can be used to improve the performance of bulk inserts to a Trie. It caches the node of the last insert in the tree, using it as the starting point to start searching for the location of the next insert. This is highly beneficial when the addresses are pre-sorted.

Example

pt := NewTrie()
ptl := NewTrieLoader(pt)

networks := []string{
	"10.0.0.0/8",
	"10.1.0.0/16",
	"192.168.0.0/24",
	"192.168.1.1/32",
}
for _, n := range networks {
	ptl.Insert(netip.MustParsePrefix(n), "net="+n)
}

fmt.Printf("%s\n", pt.String())

Output:

::/0
├ ::ffff:0.0.0.0/96
├ ├ ::ffff:10.0.0.0/104 • net=10.0.0.0/8
├ ├ ├ ::ffff:10.1.0.0/112 • net=10.1.0.0/16
├ ├ ::ffff:192.168.0.0/119
├ ├ ├ ::ffff:192.168.0.0/120 • net=192.168.0.0/24
├ ├ ├ ::ffff:192.168.1.1/128 • net=192.168.1.1/32

func NewTrieLoader

func NewTrieLoader(trie *Trie) *TrieLoader

func (*TrieLoader) Insert

func (ptl *TrieLoader) Insert(pfx netip.Prefix, v any)