Wenn die Standardbibliothek einer Programmiersprache oder eine etablierte Bibliothek eine Funktionalität bereits mitbringt, macht es häufig nicht viel Sinn das Rad selbst neu zu erfinden. Manchmal ist es aber doch notwendig, besonders wenn man mit großen Datenmengen hantieren muss.
In diesem speziellen Fall ging es darum, eine lange Liste von IPv4-Netzen, zu denen der Zugang geblockt werden soll, für den Proxyserver Squid aufzubereiten. Das Hauptproblem: Squid akzeptiert an dieser Stelle keine Überlappungen. Wenn, zum Beispiel, das fünfte Netz in der Liste und das achtundzwanzigste Netz gemeinsame IP-Adressen enthalten, verweigert Squid die gesamte Liste.
Das ist theoretisch schnell gelöst, nämlich mit Supernetting. Das Gem netaddr bringt dafür die Funktionen summ_IPv4Net() und summ_IPv6Net() mit.
Das Problem? Wie gesagt, es handelte sich um eine lange Liste. Eine sehr lange Liste. Eine Liste im Bereich von 250.000 Einträgen. Und daran verschluckte sich netaddr völlig. Wir haben das Skript nach 15+ Minuten abgebrochen.
Die Implementierung war in Ordnung, die Testsuite lief ohne Probleme durch. Aber natürlich arbeitete die Testsuite nur mit einer Handvoll Einträgen. Das war der Punkt, an der wir neugierig wurden: Wie entwickelt sich die Bearbeitungszeit bei steigender Länge der Liste? Lässt sich abschätzen, wie lange die Verarbeitung insgesamt dauern würde? Für die Ermittlung der Daten kann man das Benchmark module verwenden.
Das Benchmark-Skript ist schnell geschrieben
require 'netaddr'
require 'benchmark'
def generate_random_nets(count)
Array.new(count) do
ip = "#{rand(1..254)}.#{rand(0..255)}.#{rand(0..255)}.0"
NetAddr::IPv4Net.parse("#{ip}/24")
end
end
sizes = [100, 1000, 5000, 7500, 10_000, 20_000, 30_000, 40_000]
Benchmark.bm(10) do |run|
sizes.each do |size|
nets = generate_random_nets(size)
run.report("#{size} Netzwerke") do
NetAddr.summ_IPv4Net(nets)
end
end
end
In dieser Form fliegt einem das Skript schon bei “nur” 10.000 Einträgen in der Liste um die Ohren, weil auf dem Stack der Platz ausgeht:
(...) in 'NetAddr::IPv4Net#rel': stack level too deep (SystemStackError) (...)
Gibt man Ruby 50 MB als Stack mit RUBY_THREAD_VM_STACK_SIZE=50000000, läuft das Skript immerhin durch. Und an den Ergebnissen sieht man direkt, dass die Entwicklung nicht linear ist
| user | system | total | real | |
|---|---|---|---|---|
| 100 Netze | 0.001933 | 0.000000 | 0.001933 | ( 0.001931) |
| 1.000 Netze | 0.165706 | 0.005027 | 0.170733 | ( 0.170849) |
| 5.000 Netze | 4.267032 | 0.057012 | 4.324044 | ( 4.327078) |
| 7.500 Netze | 9.881719 | 0.056987 | 9.938706 | ( 9.943873) |
| 10.000 Netze | 17.654528 | 0.115938 | 17.770466 | ( 17.779809) |
| 20.000 Netze | 76.361159 | 0.543775 | 76.904934 | ( 76.940205) |
| 30.000 Netze | 195.184755 | 1.243654 | 196.428409 | (196.486374) |
| 40.000 Netze | 422.378795 | 1.688977 | 424.067772 | (424.336313) |
Ein Graph zeigt es noch deutlicher
Die Funktion wächst also ungefähr quadratisch. Wenn man eine quadratische Funktion approximiert und bis zur tatsächlichen Größe der Liste von 250.000 Einträgen weiterführt, landet man bei einer geschätzten Zeit von 20.221 Sekunden, also mehr als fünfeinhalb Stunden. Da hätten wir lange auf das Ergebnis warten können.
