go - 在 golang 的大型 ip/子网列表中搜索 ip 的最快方法？

Question

请帮助我以最快的方式解决下一个任务

我有一个很大的 ip/子网列表，比如...

35.132.199.128/27
8.44.144.248/32
87.117.185.193
45.23.45.45

等我需要尽可能快地在该列表中找到一些 ip。

当我尝试使用字符串 slice 和范围时，它在大列表上非常慢。

我可以使用 map，例如 map[string]string，它看起来可用，但仅用于 ip 检查，不能用于子网检查。

谁能帮我解决这个问题？谢谢。

我的代码

func (app *application) validateIP(ip string) bool {

for _, item := range app.IPList {

    itemIsIP := net.ParseIP(item)

    if itemIsIP != nil {
        if ip == itemIsIP.String() {
            return true
        }
        continue
    }

    _, itemNet, err := net.ParseCIDR(item)
    if err != nil {
        log.Printf("[ERROR] %+v", err)
    }

    checkedIP := net.ParseIP(ip)

    if itemNet.Contains(checkedIP) {
        return true
    }
}
return false

Answer 1

trie 是用于快速包含搜索地址和 CIDR 地址 block 的理想数据结构。以下代码显示了如何使用 ipaddress-go library地址 trie 实现以进行快速包含搜索。免责声明:我是 IPAddress 库的项目经理。

package main

import (
    "fmt"
    "github.com/seancfoley/ipaddress-go/ipaddr"
)

func main() {
    addrStrs := []string{
        "35.132.199.128/27", "8.44.144.248/32", "87.117.185.193", "45.23.45.45",
    }
    trie := ipaddr.AddressTrie{}
    for _, addrStr := range addrStrs {
        addr := ipaddr.NewIPAddressString(addrStr).GetAddress().ToAddressBase()
        trie.Add(addr)
    }
    fmt.Println("The trie is", trie)

    addrSearchStrs := []string{
        "35.132.199.143", "8.44.144.248", "45.23.45.45", "127.0.0.1",
    }
    for _, addrStr := range addrSearchStrs {
        addr := ipaddr.NewIPAddressString(addrStr).GetAddress().ToAddressBase()
        triePath := trie.ElementsContaining(addr)
        if triePath.Count() > 0 {
            fmt.Println("The blocks and addresses containing", addr, "are",
            triePath)
        } else {
            fmt.Println("No blocks nor addresses contain", addr)
        }
    }
}

输出:

The trie is 
○ 0.0.0.0/0 (4)
└─○ 0.0.0.0/1 (4)
  ├─○ 0.0.0.0/2 (3)
  │ ├─● 8.44.144.248 (1)
  │ └─○ 32.0.0.0/4 (2)
  │   ├─● 35.132.199.128/27 (1)
  │   └─● 45.23.45.45 (1)
  └─● 87.117.185.193 (1)

The blocks and addresses containing 35.132.199.143 are 
● 35.132.199.128/27 (1)

The blocks and addresses containing 8.44.144.248 are 
● 8.44.144.248 (1)

The blocks and addresses containing 45.23.45.45 are 
● 45.23.45.45 (1)

No blocks nor addresses contain 127.0.0.1