lpm

README

Longest Prefix Match (LPM) in Go

This repository provides a high-performance Longest Prefix Match (LPM) data structure implemented in Go.

Origin and Attribution

The original idea and baseline implementation are based on the lpm.h from the yanet2 project. See the original source here:

• yanet2/common/lpm.h: https://github.com/yanet-platform/yanet2/blob/main/common/lpm.h

This project is a Go port of that implementation.

What’s different from the original

• The original implementation required inserting prefixes sorted by length (longest to shortest). This requirement has been lifted in this Go port; you can insert prefixes in any order.
• Implemented in pure Go, with idiomatic APIs and tests.

Repository layout

• lpm.go: Core LPM implementation
• lpm_test.go and related *_test.go: Test suites and benchmarks
• examples/simple: Minimal runnable example

Getting started

Install dependencies and run tests:

go test ./...

Run the simple example:

cd examples/simple
go run .

Benchmarks

Run all benchmarks with memory stats:

go test -bench=. -benchmem ./...

Run specific large-scale benchmarks (e.g., the 100k dataset):

go test -run=^$ -bench=100k -benchmem

Shared memory

This implementation supports zero-copy shared memory usage for read-heavy, multi-process scenarios:

• Build a trie normally, then serialize it with PackToSharedStorage().
• Map the resulting byte slice in other processes and load it with NewWithSharedStorage(storage).
• Stats() reports block/value counts and approximate storage footprint across shared and dynamic data.

Notes:

• Values are limited to 255 bytes (length-prefixed), enforced during packing.
• Shared storage is ideal for read-mostly workloads; new prefixes can still be inserted dynamically after loading.
• See tests around shared storage behavior and persistence.

Run only shared-memory related tests:

go test -run SharedStorage

License

This project is distributed under the terms of the license found in LICENSE. Please also refer to the original yanet2 project license for their code.

Documentation

Overview

Package lpm implements a Longest Prefix Match (LPM) trie for fast IP address lookups.

Overview

This package provides an efficient data structure for storing and querying IP prefixes (CIDR blocks) with associated values. It supports both IPv4 and IPv6 addresses and uses a 256-way trie structure for optimal lookup performance.

Basic Usage

Create a new LPM trie and insert prefixes:

lpm := lpm.New()
lpm.Insert(netip.MustParsePrefix("192.168.1.0/24"), "local-network")
lpm.Insert(netip.MustParsePrefix("10.0.0.0/8"), "private-network")
lpm.Insert(netip.MustParsePrefix("2001:db8::/32"), "ipv6-network")

Lookup an IP address to find the most specific matching prefix:

value, found := lpm.Lookup(netip.MustParseAddr("192.168.1.100"))
if found {
    fmt.Println("Matched:", value) // Output: Matched: local-network
}

Longest Prefix Match Behavior

The trie implements longest prefix matching, meaning more specific prefixes take precedence over less specific ones:

lpm.Insert(netip.MustParsePrefix("10.0.0.0/8"), "broad")
lpm.Insert(netip.MustParsePrefix("10.1.0.0/16"), "specific")

value, _ := lpm.Lookup(netip.MustParseAddr("10.1.2.3"))
// Returns "specific" because /16 is more specific than /8

Shared Memory Support

For high-performance scenarios with multiple processes, the trie can be serialized to shared memory:

// Process 1: Build and serialize the trie
lpm := lpm.New()
lpm.Insert(netip.MustParsePrefix("192.168.0.0/16"), "data")
storage, err := lpm.PackToSharedStorage()
// Write storage to shared memory or file

// Process 2: Load from shared memory
lpm, err := lpm.NewWithSharedStorage(storage)
value, found := lpm.Lookup(netip.MustParseAddr("192.168.1.1"))

Shared storage provides zero-copy access to the trie data, making it ideal for read-heavy workloads across multiple processes.

Performance Characteristics

• Lookup: O(address_length) - constant time for IPv4 (4 bytes), IPv6 (16 bytes)
• Insert: O(address_length) - may allocate new blocks as needed
• Memory: Each block uses 1KB (256 × 4 bytes), allocated on-demand

Statistics

Get memory usage and block allocation statistics:

stats := lpm.Stats()
fmt.Printf("IPv4 blocks: %d, IPv6 blocks: %d\n",
    stats.IPv4Blocks, stats.IPv6Blocks)
fmt.Printf("Total memory: %d bytes\n", stats.TotalSize)

Thread Safety

The LPM trie is NOT thread-safe. External synchronization is required for concurrent access. For read-only workloads after initial construction, consider using shared memory with separate LPM instances per process.

Index

• type LPM
  • func New() *LPM
  • func NewWithSharedStorage(storage []byte) (*LPM, error)
  • func (m *LPM) Insert(net netip.Prefix, value string)
  • func (m *LPM) Lookup(addr netip.Addr) (string, bool)
  • func (m *LPM) MarshalBinary() ([]byte, error)
  • func (m *LPM) PackToSharedStorage() ([]byte, error)
  • func (m *LPM) Stats() Stats
  • func (m *LPM) UnmarshalBinary(data []byte) error
• type LPMBlock
• type Stats
• type StorageHeader

Examples

• LPM.Insert

Types

type LPM

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

func New

func New() *LPM

func NewWithSharedStorage

func NewWithSharedStorage(storage []byte) (*LPM, error)

NewWithSharedStorage creates a new LPM instance with shared storage from a byte slice. The storage must start with a StorageHeader followed by the data sections.

func (*LPM) Insert

func (m *LPM) Insert(net netip.Prefix, value string)

Example

package main

import (
	"encoding/json"
	"fmt"
	"net/netip"
	// "os"
)

type DCNet struct {
	CIDR string `json:"cidr"`
	DC   string `json:"dc"`
}

func unwrap[V any](value V, err error) V {
	if err != nil {
		panic(err)
	}
	return value
}

func main() {
	data := []byte(`
	[
	  { "cidr": "192.168.1.0/18", "dc": "dc1" },
	  { "cidr": "10.45.19.0/24", "dc": "dc2" },
	  { "cidr": "10.4.1.0/24", "dc": "dc3" },
	  { "cidr": "0.0.0.0/0", "dc": "default-v4" },
	  { "cidr": "192.168.1.128/25", "dc": "dc1-edge" },
	  { "cidr": "8.8.8.0/24", "dc": "public-dns-1" },
	  { "cidr": "1.1.1.0/24", "dc": "public-dns-2" },
	  { "cidr": "203.0.113.0/24", "dc": "test-net-3" },
	  { "cidr": "::/0", "dc": "default-v6" },
	  { "cidr": "2001:db8::/32", "dc": "documentation" },
	  { "cidr": "2001:db8:1::/48", "dc": "doc-subnet1" },
	  { "cidr": "2001:db8:2::/48", "dc": "doc-subnet2" },
	  { "cidr": "fe80::/10", "dc": "link-local" },
	  { "cidr": "2001:4860::/32", "dc": "public-v6-1" },
	  { "cidr": "2606:4700::/32", "dc": "public-v6-2" }
	]
`)

	var resp []DCNet
	unwrap(0, json.Unmarshal(data, &resp))

	lpm := New()

	for _, dcnet := range resp {
		net := netip.MustParsePrefix(dcnet.CIDR)

		lpm.Insert(net, dcnet.DC)
	}

	stats := lpm.Stats()
	fmt.Printf("Size of v4 storage: %d\n", stats.IPv4StorageSize)
	fmt.Printf("Size of v6 storage: %d\n", stats.IPv6StorageSize)
	fmt.Printf("Number of v4 blocks: %d\n", stats.IPv4Blocks)
	fmt.Printf("Number of v6 blocks: %d\n", stats.IPv6Blocks)
	fmt.Printf("Size of the lpm: %d\n", stats.TotalSize)
	fmt.Printf("Values storage size: %d\n", stats.ValuesStorage)

	// storage := unwrap(lpm.PackToSharedStorage())
	// os.WriteFile("dcnets.lpm", storage, 0o755)

}

Output:

Size of v4 storage: 13440
Size of v6 storage: 11376
Number of v4 blocks: 13
Number of v6 blocks: 11
Size of the lpm: 25822
Values storage size: 1006

func (*LPM) Lookup

func (m *LPM) Lookup(addr netip.Addr) (string, bool)

func (*LPM) MarshalBinary

func (m *LPM) MarshalBinary() ([]byte, error)

MarshalBinary implements encoding.BinaryMarshaler. It serializes the LPM trie into a binary format using PackToSharedStorage.

func (*LPM) PackToSharedStorage

func (m *LPM) PackToSharedStorage() ([]byte, error)

PackToSharedStorage serializes the LPM trie into a byte slice suitable for shared memory. The returned byte slice contains a StorageHeader followed by the block and value data. It automatically determines the maximum value length and returns an error if any value exceeds 255 bytes.

func (*LPM) Stats

func (m *LPM) Stats() Stats

Stats returns statistics about the LPM trie including block counts and storage sizes

func (*LPM) UnmarshalBinary

func (m *LPM) UnmarshalBinary(data []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler. It deserializes the LPM trie from a binary format using NewWithSharedStorage.

type LPMBlock

type LPMBlock [blockSize]uint32

type Stats

type Stats struct {
	IPv4Blocks      int // Number of blocks allocated for IPv4
	IPv6Blocks      int // Number of blocks allocated for IPv6
	IPv4StorageSize int // Storage size in bytes for IPv4 trie
	IPv6StorageSize int // Storage size in bytes for IPv6 trie
	ValuesStorage   int // Storage size in bytes for values
	TotalSize       int // Total storage size in bytes
}

Stats contains statistics about the LPM trie

type StorageHeader

type StorageHeader struct {
	Magic          uint32 // Magic number: 0x4C504D00 ("LPM\0")
	Version        uint32 // Format version
	V4BlockCount   uint32 // Number of IPv4 blocks
	V6BlockCount   uint32 // Number of IPv6 blocks
	ValueCount     uint32 // Number of preallocated values
	ValueSlotSize  uint32 // Size of each value slot in bytes
	V4BlocksOffset uint32 // Offset to IPv4 blocks data
	V6BlocksOffset uint32 // Offset to IPv6 blocks data
	ValuesOffset   uint32 // Offset to values data
}

StorageHeader describes the layout of preallocated storage