Building a High-Performance IP Prefix Map in Go
When working at scale with network devices and BGP peers, efficiently managing and querying IP address information becomes crucial. In this post, I’ll share how we built a high-performance IP prefix map using a Trie data structure in Go, and how it solved real-world problems.
The Problem: BGP Peer to Interface Mapping
While working at a previous company, we faced an interesting challenge: we needed to quickly determine which interface a BGP peer was associated with. Each network device had multiple interfaces, each with its own subnet, and BGP peers could connect from any of these ranges. Traditional IP lookup methods were either too slow or memory-intensive for our needs.
Here’s what a typical network device configuration looked like:
interface Ethernet1
ip address 10.1.1.0/24
description "peer-rack-1"
interface Ethernet2
ip address 10.1.2.0/24
description "peer-rack-2"
router bgp 65000
neighbor 10.1.1.100 remote-as 65001
neighbor 10.1.2.100 remote-as 65002
The challenge was to quickly answer questions like: “Which interface is BGP peer 10.1.1.100 connected to?”
The Solution: IP Trie
We implemented a Trie-based prefix map that could efficiently store and query IP addresses while maintaining metadata about each prefix. A Trie (also known as a prefix tree) is perfect for this use case because:
- It provides O(k) lookup time, where k is the length of the IP address
- It naturally handles IP prefix matching
- It’s memory-efficient for storing large numbers of prefixes
- It can store metadata with each prefix
Here’s how we use it:
package main
import (
"fmt"
"github.com/metajar/trie-network"
)
func main() {
// Create a new IP Trie
prefixMap := iptrie.NewIPTrie()
// Insert interface information
eth1Meta := map[string]interface{}{
"interface": "Ethernet1",
"description": "peer-rack-1",
"speed": "100G",
}
prefixMap.Insert("10.1.1.0/24", eth1Meta)
eth2Meta := map[string]interface{}{
"interface": "Ethernet2",
"description": "peer-rack-2",
"speed": "100G",
}
prefixMap.Insert("10.1.2.0/24", eth2Meta)
// Look up a BGP peer's interface
peer := "10.1.1.100"
cidr, metadata, err := prefixMap.Find(peer)
if err != nil {
fmt.Printf("Error finding peer: %v\n", err)
return
}
fmt.Printf("BGP peer %s is on interface %s (%s)\n",
peer,
metadata["interface"],
metadata["description"])
}
Output:
BGP peer 10.1.1.100 is on interface Ethernet1 (peer-rack-1)
Performance
The implementation is highly efficient:
BenchmarkIPv4Find-8 5000000 242 ns/op 0 B/op 0 allocs/op
BenchmarkIPv6Find-8 2000000 645 ns/op 0 B/op 0 allocs/op
- IPv4 lookups complete in under 250 nanoseconds
- Zero allocations during lookups
- Scales linearly with prefix length
- Memory usage grows sublinearly with the number of prefixes
Key Features
- Dual Stack Support: Handles both IPv4 and IPv6 addresses
- CIDR Notation: Uses standard CIDR notation for prefix ranges
- Metadata Storage: Attach arbitrary metadata to each prefix
- Overlapping Ranges: Can find all matching prefixes for an IP
- Memory Efficient: Compact storage of prefixes
- Thread Safe: Safe for concurrent use (with proper synchronization)
Implementation Details
The core of the implementation uses a binary trie where:
- Each node represents a bit in the IP address
- Each path from root to leaf represents a prefix
- Metadata is stored at leaf nodes
- The trie automatically compresses paths when possible
type Node struct {
children map[byte]*Node
isEnd bool
metadata map[string]interface{}
cidr string
}
Real-World Impact
This implementation allowed us to:
- Quickly map thousands of BGP peers to their interfaces
- Reduce lookup latency by 90% compared to our previous solution
- Better handle network events by quickly identifying affected interfaces
- Improve troubleshooting by having immediate access to interface metadata
Best Practices
When using this IP Trie implementation:
- Pre-populate the trie during initialization to avoid runtime insertions
- Use meaningful metadata keys that are consistent across your application
- Consider adding mutex locks if you need concurrent access
- Keep metadata size reasonable to maintain memory efficiency
Conclusion
Building a custom IP prefix map using a Trie data structure solved our specific needs for mapping BGP peers to interfaces. The implementation is efficient, maintainable, and can be adapted for various IP management needs.
The complete implementation is available on GitHub: IP Trie Implementation
Future Improvements
Some potential enhancements we’re considering:
- PATRICIA trie optimization for even better memory usage
- Built-in concurrent access support
- Serialization support for persistence
- Real-time prefix updates with minimal lock contention