golang高性能路由表算法实现插件库bart的使用

概述

package bart 提供了一个平衡路由表(BART)实现，用于非常快速的IP到CIDR查找等功能。

BART在内存使用和最长前缀匹配查找时间之间取得了平衡。它是一个多比特trie，固定步长为8位，使用基于Donald E. Knuth的ART算法的快速映射函数，将每个级别节点中的256个前缀映射形成一个完全二叉树。

特性

高性能IP路由查找
支持IPv4和IPv6
并发安全(读操作无锁)
低内存占用
提供完整的API进行路由表操作

安装

import "github.com/gaissmai/bart"

基本使用示例

创建路由表并插入路由

package main

import (
	"fmt"
	"net/netip"
	"github.com/gaissmai/bart"
)

func main() {
	// 创建一个字符串类型的路由表
	t := new(bart.Table[string])
	
	// 插入路由
	t.Insert(netip.MustParsePrefix("192.168.1.0/24"), "LAN1")
	t.Insert(netip.MustParsePrefix("10.0.0.0/8"), "Backbone")
	t.Insert(netip.MustParsePrefix("2001:db8::/32"), "IPv6-Net")
	
	// 查找IP
	val, ok := t.Lookup(netip.MustParseAddr("192.168.1.100"))
	fmt.Printf("Lookup 192.168.1.100: %v, %v\n", val, ok)
	
	// 查找CIDR
	val, ok = t.LookupPrefix(netip.MustParsePrefix("10.0.0.0/8"))
	fmt.Printf("Lookup 10.0.0.0/8: %v, %v\n", val, ok)
	
	// 查找最长前缀匹配
	lpm, val, ok := t.LookupPrefixLPM(netip.MustParsePrefix("192.168.1.128/25"))
	fmt.Printf("LPM for 192.168.1.128/25: %v, %v, %v\n", lpm, val, ok)
}

使用Lite版本(无payload)

package main

import (
	"fmt"
	"net/netip"
	"github.com/gaissmai/bart"
)

func main() {
	// 创建一个Lite路由表(无payload)
	l := new(bart.Lite)
	
	// 插入路由
	l.Insert(netip.MustParsePrefix("192.168.1.0/24"))
	l.Insert(netip.MustParsePrefix("10.0.0.0/8"))
	
	// 检查IP是否存在
	exists := l.Contains(netip.MustParseAddr("192.168.1.100"))
	fmt.Printf("Contains 192.168.1.100: %v\n", exists)
	
	// 检查CIDR是否存在
	exists = l.Exists(netip.MustParsePrefix("10.0.0.0/8"))
	fmt.Printf("Exists 10.0.0.0/8: %v\n", exists)
}

并发使用示例

package main

import (
	"fmt"
	"net/netip"
	"sync"
	"github.com/gaissmai/bart"
)

func main() {
	var mu sync.RWMutex
	t := new(bart.Table[string])
	
	// 并发写入需要加锁
	mu.Lock()
	t.Insert(netip.MustParsePrefix("192.168.1.0/24"), "LAN1")
	mu.Unlock()
	
	// 并发读取无需加锁
	var wg sync.WaitGroup
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			val, ok := t.Lookup(netip.MustParseAddr("192.168.1.100"))
			fmt.Printf("Lookup: %v, %v\n", val, ok)
		}()
	}
	wg.Wait()
	
	// 使用Persist方法实现无锁更新
	newTable := t.InsertPersist(netip.MustParsePrefix("10.0.0.0/8"), "Backbone")
	val, ok := newTable.Lookup(netip.MustParseAddr("10.0.0.1"))
	fmt.Printf("Lookup in new table: %v, %v\n", val, ok)
}

性能基准

BART提供了极高的性能，以下是基准测试结果示例：

BenchmarkFullMatch4/Contains         83951143        14.15 ns/op
BenchmarkFullMatch6/Contains         62731105        19.14 ns/op
BenchmarkFullMiss4/Contains          74333276        16.17 ns/op
BenchmarkFullMiss6/Contains          142984221        8.610 ns/op

BenchmarkFullMatch4/Lookup           54066939        22.09 ns/op
BenchmarkFullMatch6/Lookup           27839944        44.13 ns/op
BenchmarkFullMiss4/Lookup            55061455        21.80 ns/op
BenchmarkFullMiss6/Lookup            100000000       11.21 ns/op

API概览

BART提供了丰富的API方法，包括：

基本操作：Insert, Delete, Lookup, Contains
持久化操作：InsertPersist, DeletePersist, UpdatePersist
集合操作：Union, Clone
重叠检查：Overlaps, OverlapsPrefix
子网/超网查询：Subnets, Supernets
遍历：All, All4, All6, AllSorted等
序列化：String, MarshalText, MarshalJSON

注意事项

当前版本为pre-v1，API可能会有变动
写入操作需要同步机制保护
编译时建议指定CPU特性集以获得最佳性能(如GOAMD64=v2)

BART是一个高性能、低内存占用的路由表实现，特别适合需要快速IP查找和路由管理的应用场景。

更多关于golang高性能路由表算法实现插件库bart的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

caililin 1楼

更多关于golang高性能路由表算法实现插件库bart的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html

Golang高性能路由表算法实现插件库BART使用指南

BART(Binary ART)是一个基于基数树(ART)算法的高性能路由表实现库，专为Golang设计，特别适合需要高效路由匹配的场景，如API网关、HTTP路由器等。

安装BART

go get github.com/kentik/bart

基本使用

1. 创建路由表

package main

import (
	"fmt"
	"github.com/kentik/bart"
)

func main() {
	// 创建新的路由表
	rt := bart.NewRouter()
	
	// 添加路由
	rt.AddRoute("/user/:id", "userHandler")
	rt.AddRoute("/product/:category/:id", "productHandler")
	rt.AddRoute("/static/*filepath", "staticHandler")
	
	// 查找路由
	if handler, params, found := rt.FindRoute("/user/123"); found {
		fmt.Printf("Handler: %s, Params: %v\n", handler, params)
		// 输出: Handler: userHandler, Params: map[id:123]
	}
}

2. 路由参数匹配

BART支持两种参数匹配方式：

:param - 匹配单个路径段
*param - 匹配剩余所有路径

rt.AddRoute("/blog/:year/:month/:day", "blogHandler")
rt.AddRoute("/images/*path", "imageHandler")

// 匹配示例
handler, params, _ := rt.FindRoute("/blog/2023/10/15")
// params = map[year:2023 month:10 day:15]

handler, params, _ = rt.FindRoute("/images/user/avatar.jpg")
// params = map[path:user/avatar.jpg]

高级特性

1. 路由优先级

BART支持精确匹配优先于参数匹配：

rt.AddRoute("/user/profile", "exactProfileHandler")
rt.AddRoute("/user/:id", "userHandler")

// 访问/user/profile会匹配exactProfileHandler
// 访问/user/123会匹配userHandler

2. 性能优化建议

// 1. 预分配路由表大小(适用于已知路由数量的情况)
rt := bart.NewRouterWithSize(1000)

// 2. 批量添加路由(减少锁竞争)
routes := []struct {
	path    string
	handler interface{}
}{
	{"/api/v1/users", "usersHandler"},
	{"/api/v1/products", "productsHandler"},
}
for _, route := range routes {
	rt.AddRoute(route.path, route.handler)
}

// 3. 并发安全读取(适合高并发场景)
// FindRoute方法是线程安全的
go func() {
	handler, _, _ := rt.FindRoute("/some/path")
	// 使用handler
}()

3. 自定义匹配逻辑

// 创建自定义匹配器
type RoleMatcher struct {
	Role string
}

func (m *RoleMatcher) Match(value string) bool {
	return value == m.Role
}

// 使用自定义匹配器
rt.AddRoute("/admin/:role<admin>", "adminHandler")
// 只有/role/admin会匹配

性能对比

BART相比标准库http.ServeMux和其他流行路由库(如gorilla/mux)有显著性能优势：

操作	BART	http.ServeMux	gorilla/mux
添加路由	1x	1.2x	3x
查找路由	1x	2.5x	5x
内存使用	1x	1.8x	4x

实际应用示例

package main

import (
	"fmt"
	"net/http"
	"github.com/kentik/bart"
)

func main() {
	rt := bart.NewRouter()
	
	// 注册路由处理函数
	rt.AddRoute("/", homeHandler)
	rt.AddRoute("/about", aboutHandler)
	rt.AddRoute("/users/:id", userHandler)
	rt.AddRoute("/posts/*slug", postHandler)
	
	http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
		if handler, params, found := rt.FindRoute(r.URL.Path); found {
			switch h := handler.(type) {
			case http.HandlerFunc:
				// 将参数存入上下文
				ctx := context.WithValue(r.Context(), "params", params)
				h.ServeHTTP(w, r.WithContext(ctx))
			case func(http.ResponseWriter, *http.Request):
				h(w, r)
			default:
				http.Error(w, "Invalid handler", http.StatusInternalServerError)
			}
		} else {
			http.NotFound(w, r)
		}
	})
	
	fmt.Println("Server started on :8080")
	http.ListenAndServe(":8080", nil)
}

func homeHandler(w http.ResponseWriter, r *http.Request) {
	fmt.Fprintf(w, "Welcome to the homepage!")
}

func userHandler(w http.ResponseWriter, r *http.Request) {
	params := r.Context().Value("params").(map[string]string)
	fmt.Fprintf(w, "User ID: %s", params["id"])
}

总结

BART作为高性能路由库，具有以下优势：

基于高效的ART算法实现
支持参数匹配和通配符
内存占用低
查找速度快
线程安全

适合需要高性能路由匹配的Golang应用场景，特别是API网关、微服务路由等对性能要求较高的系统。