Optimal prüfen, ob IP im Subnetz ist

Question

Ich möchte überprüfen, ob eine IP-Adresse zu einem Subnetz gehört. Der Schmerz kommt, wenn ich gegen 300.000 CIDR-Blöcke mit Subnetzen im Bereich von/3 bis/31 mehrere Millionen mal/Sekunde überprüfen muss.

Nehmen https://github.com/indutny/node-ip zum Beispiel:

ich konnte ip.cidrSubnet('ip/subnet') für jede alle der 300.000 Blöcke und überprüfen, ob die IP ich gesucht habe in der ersten letzten Adressbereich ist, aber das ist sehr teuer.

Wie kann ich optimal prüfen, ob eine IP-Adresse zu einem dieser Blöcke gehört, ohne sie jedes Mal zu durchlaufen?

Answer 1

Speichern Sie die Informationen in einem binären Baum, der für Bereichsüberprüfungen optimiert ist.

Eine naive Möglichkeit besteht darin, jeden CIDR-Block in ein Ereignispaar zu verwandeln, eines beim Eintritt in den Block, eines beim Verlassen des Blocks. Sortieren Sie dann die Liste der Ereignisse nach IP-Adresse. Führen Sie einen Durchlauf durch und erstellen Sie ein sortiertes Array von IP-Adressen und wie viele Blöcke Sie sich befinden. Für 300.000 CIDR-Blöcke werden 600.000 Ereignisse und Ihre Suche 19-20 Lookups sein.

Jetzt können Sie eine Binärsuche dieser Datei durchführen, um den letzten Übergang vor Ihrer aktuellen IP-Adresse zu finden, und true/false zurückgeben, je nachdem, ob das in einem oder mehreren Blöcken war.

Die Suche wird schneller, wenn Sie statt einer Dateisuche einen dedizierten Index suchen. (Die Anzahl der Suchvorgänge in der Suche ist gleich oder etwas höher, aber Sie verwenden CPU-Caches besser.) Ich habe BerkeleyDBs BTree-Datenstruktur für diese Art von Dingen in anderen Sprachen verwendet und bin sehr glücklich.