All Projects → kentik → Patricia

kentik / Patricia

Licence: bsd-2-clause
Garbage collector-sensitive patricia tree for IP/CIDR tagging

Programming Languages

go
31211 projects - #10 most used programming language

Projects that are alternatives of or similar to Patricia

Sam
System Architecture Mapper
Stars: ✭ 176 (-9.28%)
Mutual labels:  networking
Tiny Networking
Tiny Networking Library
Stars: ✭ 183 (-5.67%)
Mutual labels:  networking
Vpp
Kubernetes CNI plugin based on FD.io VPP
Stars: ✭ 187 (-3.61%)
Mutual labels:  networking
Dpitunnel
DPITunnel is an android app made for censorship bypass
Stars: ✭ 179 (-7.73%)
Mutual labels:  networking
Dlib
Allocators, I/O streams, math, geometry, image and audio processing for D
Stars: ✭ 182 (-6.19%)
Mutual labels:  networking
Siesta
The civilized way to write REST API clients for iOS / macOS
Stars: ✭ 2,142 (+1004.12%)
Mutual labels:  networking
Ansible Role Wireguard
Ansible role for installing WireGuard VPN. Supports Ubuntu, Debian, Archlinx, Fedora and CentOS.
Stars: ✭ 176 (-9.28%)
Mutual labels:  networking
Ctf Tools
Useful CTF Tools
Stars: ✭ 190 (-2.06%)
Mutual labels:  networking
Zenoh
zenoh unifies data in motion, data in-use, data at rest and computations. It carefully blends traditional pub/sub with geo-distributed storages, queries and computations, while retaining a level of time and space efficiency that is well beyond any of the mainstream stacks.
Stars: ✭ 182 (-6.19%)
Mutual labels:  networking
Opencc4j
🇨🇳Open Chinese Convert is an opensource project for conversion between Traditional Chinese and Simplified Chinese.(java 中文繁简体转换)
Stars: ✭ 187 (-3.61%)
Mutual labels:  trie
Inlets Pro
Secure TCP and HTTP tunnels that work anywhere
Stars: ✭ 179 (-7.73%)
Mutual labels:  networking
Txeh
Go library and CLI utilty for /etc/hosts management.
Stars: ✭ 181 (-6.7%)
Mutual labels:  networking
Scaproust
Implementation of the nanomsg "Scalability Protocols" in rust.
Stars: ✭ 183 (-5.67%)
Mutual labels:  networking
Leetcode
High-quality LeetCode solutions
Stars: ✭ 178 (-8.25%)
Mutual labels:  trie
P4 Learning
Compilation of P4 exercises, examples, documentation, slides for learning or teaching
Stars: ✭ 190 (-2.06%)
Mutual labels:  networking
Tracepkt
Trace a ping packet journey across network interfaces and namespace on recent Linux. Supports IPv4 and IPv6.
Stars: ✭ 176 (-9.28%)
Mutual labels:  networking
Kuma
🐻 The Universal Service Mesh. CNCF Sandbox Project.
Stars: ✭ 2,516 (+1196.91%)
Mutual labels:  networking
Insolar
Enterprise-ready blockchain platform
Stars: ✭ 192 (-1.03%)
Mutual labels:  networking
Arenagame
A Unity First Person Shooter game made with Forge networking as an example project.
Stars: ✭ 190 (-2.06%)
Mutual labels:  networking
Moya
Network abstraction layer written in Swift.
Stars: ✭ 13,607 (+6913.92%)
Mutual labels:  networking

Garbage collector-sensitive patricia tree for IP/CIDR tagging

What is this?

A Go implemenation of a patricia tree (radix tree with radix=2), specifically for tagging IPv4 and IPv6 addresses with CIDR bits, with a focus on producing as little garbage for the garbage collector to manage as possible. This allows you to tag millions of IP addresses without incurring a penalty during GC scanning.

This library requires Go >= 1.9.

IP/CIDR tagging

IP addresses can be tagged by any of the built-in types that we generate trees for. It's no accident that we don't support pointers, slices, or interface{} for reasons described below. Once your IPv4 or IPv6 tree is initialized, you can tag a full 32/128 bit address, or IP/CIDR.

For example, on an IPv4 tree, you can create the following tags:

  • 123.0.0.0/8: "HELLO"
  • 123.54.66.20/32: "THERE"
  • 123.54.66.0/24: "GOPHERS"
  • 123.54.66.21/32: ":)"

Searching for:

  • 123.1.2.3/32 or 123.0.0.0/8 returns "HELLO"
  • 123.54.66.20/32 returns ["HELLO", "THERE", "GOPHERS"]
  • 123.54.66.21/32 returns ["HELLO", "GOPHERS", ":)"]

Generated types, but why not reference types?

The initial version of this effort included many references to structs. The nodes in the tree were all tied together with pointers, and each node had an array of tags. Even as the tree grew, it seemed to perform well. However, CPU was higher than expected. Profiling revealed this to be largely due to garbage collection. Even though the objects in the tree were mostly static, each one needed to be scanned by the garbage collector when it ran. The strategy then became: remove all pointers possible.

At this point, the internal structure is tuned to be left alone by the garbage collector. Storing references in the tree would defeat much of the purpose of these optimizations. If you need to store references, then consider storing integers that index the data you need in a separate structure, like a map or array.

In addition, to support custom payload types would require interface{}, which adds noticeable overhead at high volume. To avoid this, a separate set of strongly-typed trees is generated for:

  • bool
  • byte
  • complex64
  • complex128
  • float32
  • float64
  • int8
  • int16
  • int32
  • int64
  • rune
  • string
  • uint
  • uint8
  • uint16
  • uint32
  • uint64

How does this avoid garbage collection scanning?

A scarcely-populated patricia tree will require about 2x as many nodes as addresses, and each node with tags needs to maintain that list. This means, in a pointer-based tree of 1 million IP addresses, you'll end up with around 3 million references - this puts a considerable load on the garbage collector.

To avoid this, the nodes in this tree are stored in a single array, by value. This array of nodes is a single reference that the GC needs to manage. Nodes are wired together by uint32 indexes in that array. This has the added benefit of saving us 8 bytes of memory per node: rather than two 64-bit pointers, we have two 32-bit integers.

The way we avoid a reference to each collection of tags is a little trickier. Thanks to an optimization introduced in 1.5, the GC now ignores maps with keys and values that do not contain pointers. So, our collection of tags is flattened into a map[uint64]GENERATED_TYPE. The keys into the map use the following convention:

    (nodeIndex << 32) + (tagArrayIndex...)

That is... we use a 64 bit number, setting the most significant 32 bits to the node index, then adding to it the 0-based index into the tag array.

With these strategies, in a tree of 1 million tags, we reduce the pointer count from 3 million to 3: the tree, its node array, and its tag map. Your garbage collector thanks you.

Notes

  • This is not thread-safe. If you need concurrency, it needs to be managed at a higher level.
  • The tree is tuned for fast reads, but update performance shouldn't be too bad.
  • IPv4 addresses are represented as uint32
  • IPv6 addresses are represented as a pair of uint64's
  • The tree maintains as few nodes as possible, deleting unnecessary ones when possible, to reduce the amount of work needed during tree search.
  • The tree doesn't currently compact its array of nodes, so you could end up with a capacity that's twice as big as the max number of nodes ever seen, but each node is only 20 bytes. Deleted node indexes are reused.
  • Code generation isn't performed with go generate, but rather a Makefile with some simple search and replace from the ./template directory. Development is performed on the IPv4 tree. The IPv6 tree is generated from it, again, with simple search & replaces.
Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].