Erweiterte Suche


Ein Kunde berichtete über eine Nichterreichbarkeit des Webservers der Piratenpartei. Die Störung sah aus wie ein Routingproblem, aber es war viel viel schlimmer.

Zusätzlich zu der Nichterreichbarkeit der Webseite waren auch zwei Traceroutes mitgeliefert worden. Einer aus Kundensicht und einer vom Webserver aus. Die sehen so aus (IP Adresse des Kunden durch die eines Routers ersetzt)

traceroute from 178.19.71.117 to 178.19.224.1
 1  178.19.71.1 (178.19.71.1) [AS29551]  0.673 ms * *
 2  * * *
 3  * * *
 4  80.81.193.74 (80.81.193.74) [AS6695]  0.660 ms * *
 5  * * *
 6  * * 217.71.99.134 (217.71.99.134) [AS13237]  8.215 ms
 7  109.73.31.194 (109.73.31.194) [AS196714]  8.227 ms * *
 8  * * *
 9  * * *

Sowie

traceroute from 178.19.224.1 to 178.19.71.117
 1  rudo1-g01-115 (217.17.207.161)  18.793 ms  1.234 ms  5.662 ms
 2  NUE-2.de.lambdanet.net (217.71.100.33)  4.153 ms  4.303 ms  4.192 ms
 3  xe0-0-0.irt1.fra44.de.as13237.net (217.71.96.73)  7.408 ms  7.421 ms  7.426 ms
 4  decix.fra2.tng.de (80.81.192.83)  12.095 ms  12.027 ms  12.094 ms
 5  t4-1.decix.rt02.of.aixit.net (83.141.1.187)  12.080 ms  12.286 ms  12.279 ms
 6  v7.rt03.boe.aixit.net (83.141.0.249)  12.015 ms  12.500 ms  13.041 ms
 7  v3-rt01.boe.aixit.net (83.141.1.97)  12.021 ms  12.247 ms  12.502 ms
 8  * * *
 9  * * *

Führt man Traces von anderen Systemen aus, so scheint alles ok zu sein.

Nach direktem Kontakt zu einem Admin der BundesIT (vielen Dank für die Geduld mit meinen doch sehr erstaunten Fragen) stellte sich heraus.

  • Eingehende ICMP-Pakete sind bei der Firewall der Piratenpartei rate-limited.
  • Einige Server dort hatten die falsche Netzmaske, deswegen glaubte der Webserver, die Antworten im lokalen Netz ausliefern zu können.

Wie kommt man zu einer falschen Netzmaske? Ganz einfach: Die Server waren classful konfiguriert. 178.19.224.1 und 178.19.71.117 liegen nun mal im gleichen /16 (ehemals Class-B Netz).

Ob des Ratelimits weist der Traceroute die Sterne unterwegs auf: Die Antworten erreichen die tracende Maschine gar nicht.

Nebenbei stellte sich auch heraus, warum Ping komplett gesperrt und ICMP rate-limited ist: Man könnte ja herausbekommen, welche IPs benutzt werden.

Und das Problem wird schon länger gesucht, wie eine Diskussion auf Twitter zeigt.

Dokumentation ist das Stiefkind der IT. Aktuelle Doku is jedoch das Rückrat erfolgreicher Projekte. Wie hält man Dokumentation aktuell? In dem man sie freiwillig benutzt, weil sie einen Mehrwert abwirft. Netzplänen sollten also nicht nur das "Was ist" dokumentieren, sondern auch das "Was geschieht".

Admin kontra Managment

Typischerweise benutzt man zur Beantwortung der Frage, was denn da im Netz geschieht Trafficgraphen und für den groben Überblick eine Weathermap. Installation und Aufbereitung solcher Systeme ist ziemlich aufwendig. Wenn man sie schon hat, will man möglichst komplette Informationen an einer Stelle abrufen können.

Darüberhinaus benutzt man für die Projektdokumentation gern vereinfachende AdHoc Darstellungen, die schnell und auf Zuruf z.B. mit Visio erstellt werden. Diese verstauben dann in den Projektunterlagen, bis irgend ein Manager ein seit Monaten veraltetes Dokument in den Händen hält, um damit neue Planungen vorzunehmen und Entscheidungen zu fällen.

Obwohl Visio mächtig genug ist, die Dokumentation auch mit externen Datenquellen zu animieren, weigert sich der Netzwerkadmin, diesem Tool direkten Zugriffe auf die Netzwerkknoten zu erlauben. Außerdem müßte der Zugriff dann auch beim Kunden oder auf Präsentationen funktionieren.

Andererseits ist das Netzwerkmonitoring der Admins für den Manager zu komplex und zu mächtig. Endkunden will man gar nicht alle Details des realen Netzes zeigen. Schon gar nicht will man einen externen Zugriff des Endkunden auf die Managementsysteme selbst.

Einfach erstellt, einfach genutzt

Was liegt also näher, die Visio-Dokumente, die für den Endkunden erstellt wurden, auf eine Supportwebseite zu legen und dieser Webseite zu erlauben, die Graphik zu animieren? Zum einen sind die Dokumente nicht webtauglich und andererseits will man auf den Webseiten keine Office-Software aktiv laufen lassen.

Glücklicherweise kann Visio nach SVG exportieren. Und dieser Output ist hervorragend maschinell nachbearbeitbar. Mittlerweile ist SVG auch browserseitig ausreichend unterstützt, um dort bedenkenlos den Einsatz freizugeben. Die Anfangszeiten, bei denen extra Plugins benötigt wurden, sind glücklicherweise vorbei.

<g id="shape69-50" v:mID="69" v:groupContext="shape" v:layerMember="2"
     transform="translate(276.378,-523.305)">
 <title>Dynamic connector.69</title>
 <desc>G0/2</desc>
 <v:textBlock v:margins="rect(4,4,4,4)" v:tabSpace="42.5197"/>
 <v:textRect cx="21.292" cy="602.833" width="40" height="17.6036"/>
 <path d="M0 601.45 L336.41 603.27" class="st1" />
 <rect v:rectContext="textBkgnd" x="12.2454" y="598.034"
         width="17.3436" height="9.59985" class="st5"/>
 <text x="12.62" y="605.23" class="st6" v:langID="1031">
   <v:paragraph v:horizAlign="1"/>
   <v:tabList/>
   G0/2
  </text>
</g>

Um aus einem Visio-SVG eine Weathermap zu machen, müssen die manuell angelegten Verbinder eingefärbt werden. Je nach Auslastung der Leitung ändern sich die Farben von einem leichten Grün bis zu einem kräftigen Rot. (Hier mit einer anderen Linie.)

 <path d="M-6.07 595.28 L-8.11 806.72" class="st1" style='stroke:red'/>
netzplan-linie1

Da Leitungen in beide Richtungen Daten transportieren können, müssen die Verbinderlinien doppelt eingefärbt werden. Weathermaps lösen dies, in dem sie zwei Pfeile statt einer Verbindung einzeichnen und diese Pfeile separate einfärben. Schöner wäre es aber, wenn der Verbinder selbst seine Farbe ändern könnte. Glücklicherweise beherscht SVG Gradienten, um lineare Farbverläufe vorzugeben.

<linearGradient id="gruen-rot">
 <stop offset="0" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#ff0000;stop-opacity:1"/>
</linearGradient>
[...]
<path d="M-6.07 595.28 L-8.11 806.72" class="st1" style='stroke:url(#gruen-rot)'/>

Unglücklicherweise ist der Farbverlauf streng horizontal, so daß diese steile Linie den Farbwechsel nur in ihrer Breite durchmacht. Der Farbverlauf hätte eigentlich der Linie folgen sollen. Alle Versuchen mit Transformationen den Farbverlauf zu beeinflussen, waren vergeblich. Denn der Farbverlauf kann und muß separat gedreht werden.

<linearGradient id="gruen-rot" gradientTransform="rotate(90)">
 <stop offset="0" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#ff0000;stop-opacity:1"/>
</linearGradient>

Jetzt verlaufen die Farben wie gewünscht der Linie entlang.

Für jede Linie ist nun ein extra Gradient anzulegen. Dabei ist darauf zu achten, daß der Verlauf der Definition der Linie folgt, damit man später automatisiert die Leitungsauslastungen als Farbwerte an den Endstellen einsetzen kann. Die Zeichenrichtung im Visio hat wenig mit der Zeichenrichtung im SVG zu tun. Dies kann also komplexere Transformationen erfordern, denn eine Rotation um 180° dreht den Farbverlauf komplett aus dem Liniensegment heraus. Mit einer Matixoperation kann man den Verlauf gleich wieder an die richtige Stelle schieben.

Darüberhinaus empfiehlt es sich, kleine Ansätze an den Verbindern stehen zu lassen, um keinen so abrupten Farbwechsel am Gerät zu bekommen. Man setzt dazu seine Start- und Endwerte erst bei 10% vorm Ende. Da die Farbwerte später ersetzt werden sollen, muß bereits hier vermerkt werden, welches Interface an welchem Gerät zum Einsatz kommen soll.

<!-- device:interface max_bandwith -->
<linearGradient id="line13" gradientTransform="matrix(-1,0,0,-1,1,1)">
 <stop offset="0" style="stop-color:#000000;stop-opacity:1"/>
 <stop offset=".1" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset=".9" style="stop-color:#ff0000;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#000000;stop-opacity:1"/>
</linearGradient>

Es kann aber passieren, daß die Umfärbung völlig scheitert: Die Linie verschwindet ganz. Dies passiert, wenn eine Linie exakt horizontal oder vertikal liegt. Dann ist die Höhe oder Breite der Linie exakt Null und die Gradientenoperation bricht mit einer Division durch Null ab. In dem Fall muß man einfach einen Endpunkt der Linie um ein winziges Stück verschieben. (Wieder eine andere Linie.)

<path d="M0 588.19 L222.79 588.20" class="st1" style='stroke:url(#line3)'/>

Alles zusammen sollte sich dann ein Bild ergeben, bei dem klar ersichtlich ist, welche Meßstelle die Daten liefern wird. Diese wurde hier beschriftet und muß das grüne Ende des Verbinders erhalten. Damit sind die Voraussetzungen für eine maschinelle Überarbeitung geschaffen.

netzplan-animiert

Besonders hübsch ist, wie der Farbverlauf auch den gebogenen Pfaden folgt.

Diese manuellen Anpassungen des Visio-Exportes sind in einer guten halben Stunde zu erledigen. Mit etwas Übung geht dauert es nur einige Minuten. Komplexere Netzpläne oder ewig wiederkehrende Exports kann man automatisieren.

Die SVG Graphik kann nur auf einem beliebigen Webserver als statische Datei abgelegt werden (Mime-Type: image/svg+xml). Die URL kann zur Abnahme herumgeschickt werden.

Leben einhauchen

Zur Weathermap mutiert dieses Bild dann, indem es von einem Perl/PHP/Whatever-Script überarbeitet wird. Dieses holt sich bei Bedarf die notwendigen Daten aus einer Datenbank (MRTG, etc.) oder live von den Geräten. Der Farbwert wechselt gemäß rgb(255*load, 255*(1-load), 0) für die Hin- und Rückrichtung des Links.

Es spricht überhaupt nichts dagegen, weitere Angaben mit der Graphik zu verknüpfen. So kann das Symbol der aktiven Technik zwischen grau und rot umgefärbt werden, um die CPU-Last zu visualisieren. Ebenso bietet es sich an, die Speicherauslastung als "Füllhöhe" der Füllfarbe anzuzeigen. Wer noch Ideen hat, möge sie in die Kommentare schreiben oder einfach selbst umsetzen.

Die Implementation auf dem Webserver kann als PHP Datei die Daten, z.B. per SSH von einem zu SNMP berechtigten Host, holen und die SVG Datei vor der Ausliefung überarbeiten. Der SNMP-Host liefert, z.B. per command="/usr/local/sbin/obtain-line-rates.pl customer", die aktuellen Input- und Outputraten ausschließlich für die hinterlegten Geräte und Interfaces.

#! /usr/bin/perl

use strict;
use warnings;

my %points = ();

if($ARGV[0] eq 'customer') {
    %points = (
        'S1' => ['Port-channel32', 'Port-channel1', 'GigabitEthernet4/3', 'GigabitEthernet1/3', 'GigabitEthernet1/2'],
        'R1' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/3'],
        'R2' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/2'],
        'R3' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/2'],
    );
} else {
    die "Usage: $0 name\n";
}

my %conf = ();
# Fill the config with the SNMP communities

# Read in the interface Name-ID mapping
my %ids = ();
foreach my $host (keys %conf) {
    open(S, "snmpbulkwalk -v2c -c '$conf{$host}' -t 2 -r 2 -L o: $host IF-MIB::ifDescr |") || next;
    while(<S>) {
        next unless my ($id,$val) = /\.([^\s.]+) = \S+: (.*\S)/;
        next unless grep {$_ eq $val} @{$points{$host}};
        $ids{$host}{$id} = $val;
    }
    close(S);
}

# Read the line rates and print them
while(my($host,$hh) = each %ids) {
    my @m = ((map {"1.3.6.1.4.1.9.2.2.1.1.6.$_"}  keys %$hh),
             (map {"1.3.6.1.4.1.9.2.2.1.1.8.$_"} keys %$hh));
    my $mc = $#m + 1;
    my $ms = join(" ", sort @m);

    my %c = ();

    open(S, "snmpget -v2c -c '$conf{$host}' -t 2 -r 2 -L o: $host $ms |") || next
    while(<S>) {
        next unless my ($dir,$id,$val) = /(\d+)\.([^\s.]+) = \S+: (.*\S)/;
        next unless defined $hh->{$id};
        $c{$hh->{$id}}{$dir} = $val;
    }
    close(S);

    while(my($name,$vals) = each %c) {
        print "$host:$name ".$vals->{6}," ".$vals->{8}."\n";
    }
}

Mein PHP Script zur Überarbeitung der Graphik ist dann ebenfalls ziemlich einfach:

<?
$unknown_color = '909090'; // Make links grey if no data is available
$svg_file = 'path/to/plan.svg';

// Read the current in/out bandwith values
$max_bandwidth = 1;
$max_bandwidth = max($max_bandwidth, $match[2], $match[3]);
$traf = popen("ssh -i path/to/sshkey user@snmp-host true", "r");
while($line = fgets($traf)) {
    if(preg_match('/^(\S+:\S+) (\d+) (\d+)$/', $line, $match)) {
        $inrate [$match[1]] = $match[2];
        $outrate[$match[1]] = $match[3];
        $max_bandwidth = max($max_bandwidth, $match[2], $match[3]);
    }
}
pclose($traf);

header("Content-Type: image/svg+xml");

$svg = fopen($svg_file, "r");
while($line = fgets($svg)) {
    if(preg_match('/<!-- (\S+:\S+) (\d+) -->/', $line, $match)) {
        $current_interface = $match[1];
        $current_speed = $match[2];
        if(is_numeric($_REQUEST['maxscale']))
          $current_speed *= $_REQUEST['maxscale'];
        elseif($_REQUEST['maxscale'] == 'max')
          $current_speed = min($max_bandwidth, $current_speed);
    }
    if(preg_match('/<linearGradient id="(\S+)"/', $line, $match)) {
        $current_gradient = $match[1];
    }
    if($current_speed > 0 &&
       preg_match('/^(\s+<stop offset=".(\d)" style="stop-color:#)\S{6}(;.*)/', $line, $match)) {
        if(isset($inrate[$current_interface])) {
            $util = (1.0*$inrate[$current_interface])/$current_speed;
            $incolor = sprintf("%02x%02x00", 255*$util, 255*(1-$util));
            $inline[$current_gradient] = sprintf("%02d%% %.2fMbps", $util*100, $inrate[$current_interface]/1000000.0);
        } else {
            $incolor = $unknown_color;
            $inline[$current_gradient] = "n/a";
        }
        if(isset($outrate[$current_interface])) {
            $util = (1.0*$outrate[$current_interface])/$current_speed;
            $outcolor = sprintf("%02x%02x00", 255*$util, 255*(1-$util));
            $outline[$current_gradient] = sprintf("%02d%% %0.2fMbps", $util*100, $outrate[$current_interface]/1000000.0);
        } else {
            $outcolor = $unknown_color;
            $outline[$current_gradient] = "n/a";
        }
        switch($match[2]) {
         case  1: print "$match[1]$outcolor$match[3]\n"; break;
         case  9: print "$match[1]$incolor$match[3]\n"; break;
         default: print $line; break;
        }
    } elseif(preg_match('/^\s*<title>Dynamic connector[.\d]*<\/title>\s*$/', $line)) {
        // Skip output of title
    } elseif(preg_match('/style=.stroke:url\(#(\S+)\)./', $line, $match) && isset($inline[$match[1]])) {
        print $line;
        print "\t\t\t<title>In: {$inline[$match[1]]}\nOut: {$outline[$match[1]]}</title>\n";
    } else {
        print $line;
    }
}
fclose($svg);
?>

Fazit

Kundenspezifische Views wurden mit dem Monitoringsystem verknüpft, so daß alle Beteiligte einen Vorteil davon haben:

  • Der Kunde kann seinen Teil des Netzes anhand der für ihn erstellen Dokumentation live einsehen.
  • Der Admin bekommt einen Einblick der Kundensicht und kann bei Wartungen die Auswirkungen auf den Kunden überprüfen.
  • Der Admin kann - wenn live verknüpft - eine aktuelle Weathermap eines beschränkten Bereiches während einer Umbaus offen halten. Die Dokumentation wurde beispielsweise adhoc für diesen Umbau erstellt und enthält so nur die interessanten Teile.
  • Der Support kann auf einen für den Kunden relevanten Teil der Netzstruktur schauen, während er mit dem Kunden telefoniert.
  • Da die Dokumentation auf der Supportwebseite liegt, kann sie nicht in veralteter Form im Mailpostfach eines Vertrieblers oder in den "Eigenen Dokumenten" eines Managers versauern.

Es gibt also durchaus Gründe, Netze zu dokumentieren und diese Dokumentation aktuell zu halten: Sie aktiv zu nutzen.

Für eine große Anzahl an DSL Kunden wurde mir für die LNS Funktionalität die Software MPD auf FreeBSD empfohlen. Ein Blick in die Suchergebnisse zeigt, dass vor allem in Russland wirklich große Installationen damit gefahren werden. Als Alternative stand OpenL2TP im Raum. Allerdings handelt OpenL2TP die PPP Sessions im Userspace ab, während MPD auf NetGraph zurück greift.

Erstkontakt

Das Setup ist einfach, wenn auch die Dokumentation von MPD spartanisch ist. Was ein Kommando tut, steht höchstens an einer Stelle. Wenn man die nicht kennt, ist man schlicht aufgeschmissen.

Darüberhinaus unterscheidet MPD strikt zwischen den Layern der Verbindung. Man kann also nur dort etwas konfigurieren (und nachlesen), wo diese Einstellung relevant ist. So findet sich VanJacobson Compression im IPCP-Teil eine (PPP-)Bundles. Protocol Field Compression als Bestandteil der PPP Session wird aber im Link-Layer ausgehandelt. Deswegen findet sich die Einstellung dort: wie auch die Authenisierungsprotokolle, die LCP verwenden soll.

Die Konfigurationsdatei ist strikt linear. Jedes Kommando kann den aktuellen Layer ändern. Damit sind die Folgekommandos in einem anderen Kontext auszuführen. Am besten ist es also, die Konfiguration manuell zu erstellen und parallel dazu die Eingaben mitzuschreiben (log +console).

Ernüchterung

Die ersten Tests waren das Grauen.

lasttest-mpd-patch1

Es ging ganz lustig los, brach aber dann mit "no more threads" und "Fatal message queue overflow!" ab. Der MPD stürzte kontrolliert ab, beendete alle Sessions und sich selbst.

Als Grund dafür fand sich schnell das Event-Handling für Radius Anfragen. Die Implementation erfolgt als threadinterne Pipe aus der gelesen und geschrieben wird. Parallel dazu gibt es einen Ringpuffer an Ereignisinformationen. Damit ein write auf die Pipe nicht blockt, dürfen nicht mehr Bytes (Dummywert für "Es gibt ein Ereignis") geschrieben werden, als in die Kernel-Puffer passen.

Der offenkundige Patch besteht darin, die Pipegröße und den Ringpuffer zu vergrößern. Aber damit hatte ich gar keinen Erfolg: Es knallte mit einem Segfault.

Da pro Layer verschiedene Ereignisse generiert werden, kann bei der Verarbeitung eines einzigen Ereignisses eine Flut von Folgeevents angefordert werden. Aber der Thread für die Eventverarbeitung darf nicht blockieren! Deswegen werden für externe Ereignisse ständig neue Threads aufgemacht, die dann für sich allein warten können. In diesem Fall hat Radius-Authenisierung und -Accounting die Grenze von 5000 Threads pro Prozess überschritten. Auf dem Radiusserver sah die Last dann ähnlich aus.

Wie schlimm diese Radiuskaskade werden kann, hat ein Zulieferer während eines solches Tests erlebt. Die kommerzielle LAC Lösung dort fragt pro Loginversuch einen Radiusserver nach dem Realm, um den passenden LNS zu ermitteln. Als spontan alles zusammenbrach, wurde er von so vielen Requests überrannt, dass der Radiusserver – genauer dessen Datenbank-Backend – in die Hände klatschte und die gesamte DSL-Zuführung den Dienst quittierte. Inzwischen läuft die Verteilung an die LNS statisch.

Schön langsam

Man soll also freundlich zu seinen Zulieferern sein, besonders zu seinen Radius-Servern. Ich habe das komplette Eventhandling des MPD entsorgt und auf Basis von mesg_queue neu geschrieben. Die verwendete Bibliothek war sowieso schon im MPD eingebunden.

Unterschieden wird nach "sequentiellen" und "parallelen" Ereignissen. Sequentielle Ereignisse laufen unter dem globalen Lock des MPD serialisiert und in der Reihenfolge, in der sie generiert wurden. So kommen die Layer nicht durcheinander und die Ereignisverarbeitung kann sich auf die vorbereitenden Aktionen verlassen. Die parallele Verarbeitung dient der externen Kommunikation. Dabei die die Anzahl der aktiv laufenden Worker-Threads limitiert.

Die Länge beider Warteschlangen wird dem MPD zur Overload Berechnung (Load = 2×queue_len(seriell) + 10×queue_len(parallel)) vorgelegt, so dass er bei Last die Annahme neuer Verbindungen verweigern kann.

So ausgerüstet war ich voller Hoffnung und wurde jäh enttäuscht. Der Kernel warf hin: Tief tief drin.

bsd-lasttest-panic-1

Und nicht nur einmal, sondern auch an ganz anderer Stelle.

bsd-lasttest-panic-2

War der NetGraph Code defekt? Kommt der Kernel nicht mit dem schnellen Anlegen und Löschen von Interfaces klar? Bin ich zu schnell?

Schon im Radius-Accounting gab es Probleme, weil des Testgeräten gelang dreimal innerhalb einer Sekunde eine Verbindung auf- und abzubauen. Das verletzte die unique-Constraints meines Datenschemas. Das Teil ist also definitiv zu schnell! Im Code habe ich also dann eine Pause von 20ms (konfigurierbar) zwischen zwei seriellen Ereignissen eingebaut.

Da der Thread für die serielle Abarbeitung nun vom Hauptthread getrennt läuft, was vorher nicht der Fall war, habe ich um die NetGraph Aufrufe ein separates Lock gelegt. Dies verhindert, dass konkurrierend auf den NetGraph-Sockets gearbeitet wird.

Damit wurde der Systemverhalten stabil.

Lasttests

Zum Testen wird von einem Linux mit OpenL2TP aus:

  • eine zufällige Anzahl von L2TP Tunneln aufgemacht und
  • auf diesen so schnell wie möglich reiherum bis zu 9000 Sessions aufgerissen.
  • Danach werden die Sessions mit einigen Dezisekunden Pause generiert, bis die Anzahl der der gewünschten Clients verbunden ist.
  • Anschließend wird ein Ausfall und Wiederherstellen von ca. 300 zufälligen Sessions mehrfach wiederholt.
  • Nach einer Weile Ruhe werden die Sessions kontrolliert abgebaut.

Ein typisches Beispiel dieses Tests sieht so aus: Die "Sessions" sind vom lastgenerierenden OpenL2TP, diese generieren auf den MPD L2TP-"Links" und darauf PPP-"Bundles". Mitgeplottet werden auch die Längen der Eventqueues.

mpd-logins-13040106

Initial ist die Länge der parallelen Queue groß, dann greift die Limitierung durch Overload. Die Kurven für Sessions, Links und Bundles liegen praktisch aufeinander, es gibt keine Differenzen zwischen den Systemen, denn nicht aufgebaute Sessions werden nicht mit aufgeschrieben.

Ebenso ist schön zu sehen, wie heftig die serielle Queue anwächst, wenn Interfaces wegfallen: Der MPD ist in seiner originalen Version definitiv anfällig gegen Queueoverrun. Tritt dieser Effekt ein, beendet sich der originale MPD. Ein inakzeptabler Zustand.

Die FreeBSD Kiste mit MPD hat dabei einen maximalen Load von 3 und benötigt 280 MB RAM. Die Linux Maschine hat einen Load von 20 beim Verbindungsaufbau und einen Load von 50 beim Verbindungsabbau. Der Speicherbedarf auf der Linux-Seite beträgt 2 GB, um die vielen PPPD Instanzen zu halten.

Knalleffekte

Und nun der Test mit einem heftigeren Abbruch: Anstatt die PPPD Instanzen auf Linux einzeln zu killen, wird der L2TP Kanal unterbrochen.

mpd-logins-13040211

Deutlich erkennbar ist, wie die "übergeordneten" Bundles zuerst abgebaut werden und dann die dazugehörigen L2TP-Links. Der Load auf BSD-Seite steigt auf 6.

Auf Linux-Seite nimmt eine Katastrophe ihren Lauf: Alle pppd-Instanzen konkurrieren um den Scheduler, um sich zu beenden. Der Load steigt auf über 700 und die Maschine braucht zu lange, um sich zu beruhigen. Ein beherztes "killall -9 pppd" erlöste die Maschine nach einer halben Stunde.

Aber wie weit kann man gehen? Mehr als 10000? Mehr als 20000? Probieren wir es aus:

mpd-logins-13040213

Die Kombination steigt rasant auf 11500 Sessions und hört spontan auf. Auf Linux-Seite meldet der OpenL2TP fehlerhafte "RPC"-Parameter: Er ist in die Limits seiner Implementation gelaufen. Die Maschine verheddert sich und muß neu gebootet werden. Dem BSD hat es nichts getan.

Und nun mehrfach hintereinander:

mpd-logins-130401

Hoch und runter, immer wieder. Ab und zu einen Absturz durch Dummheit, aber es tut!

Ab in die Produktion

In der produktiven Umgebung ist es erstaunlich ruhig angelaufen. Trotzdem stürzt das System weiter ab:

bsd-lasttest-panic-3

Alle Abstürze sind nun nur noch im NAT-Code. Obwohl der Code dem Stand von HEAD entspricht ... Dazu anderweitig mehr.

Änderungen am MPD haben sich noch weitere ergeben:

  • Um den Code in der Produktion schnell austauschen zu können, beendet sich der MPD selbst, wenn er keine Sessions mehr offen hat. Die Konfiguationsoption heißt "delayed-one-shot". Der Aufruf des MPD erfolgt nun in einem Loop (/usr/local/etc/rc.d/mpd5 enthält command="/usr/local/sbin/${name}.loop")
$ cat /usr/local/sbin/mpd5.loop
#! /usr/local/bin/bash

nohup /usr/local/bin/bash -c "
cd /
while true; do
  /usr/local/sbin/mpd5 -k -p /var/run/mpd5.pid -O
  sleep 5
done
"  >/dev/null 2>/dev/null </dev/null &
  • Das Radius-Accounting für die Abbruchgründe ist mangelhaft, die komplette Fehlermeldung wird nun ebenfalls reportet:
ATTRIBUTE      mpd-term-cause  23      string
  • Systemrelevantes Logging (Interfaces kommen und gehen, Nutzer melden sich an und ab) ist nun dauerhaft an und nicht mehr nur für Debugging. Ebenso sind relevante Fehler immer zu loggen. Andernfalls fährt der Server im Blindflug.

Achja, der Patch: Bitteschön. Wir liefern gern auch kommerziellen Support dafür.

Bloggen, erzählen, kommunizieren von Problemen hilft. Man bekommt Aufmerksamkeit, die man sonst nie bekommen würde.

Vorwärts immer, rückwärts nimmer

Inzwischen sind auch Entwickler von FreeBSD aufmerksam geworden und empfehlen einen radikalen Schnitt:

  • Upgrade auf SVN-HEAD, die aktuelle Entwicklerversion. Schließlich läuft darauf auch die FreeBSD.org Plattform.
  • Das Treiberproblem mit dem Adaptec ist ja auch gelöst. Wenn auch erst seit heute mittag.
  • Man kann auf pf statt libalias wechseln. Das Locking bremst nicht mehr die Performance aus wie in 8.x oder 9.x.
  • Deine Probelme werden nicht weg sein, aber developers sind deutlich motivierter.

Das klingt nach einem Plan. Aber nach einem, den man erstmal an einer Testmaschine und dedizierten Lasttests ausprobiert.

Wird fortgesetzt ...

Wird der MPD als LNS unter Hochlast gesetzt, können die L2TP Verbindungen wegbrechen. Die Gründe dafür sind manigfaltig, exemplarisch werden hier einige betrachtet.

Schadensmaximierung

Im Code des MPD sind verschiedenste Asserts verteilt. Wenn davon einer zuschlägt, beendet sich der MPD kontrolliert. Und wenn sich der MPD beendet, fliegen alle Nutzer raus. Ein typischer Assert ist:

ASSERT "new == PHASE_DEAD || new == PHASE_TERMINATE || new == PHASE_AUTHENTICATE"
 failed: file "lcp.c", line 418

Auslöser der Bedingung ist eine Nutzeranmeldung, die nicht protokollkonform abläuft. Das kann immer mal passieren.

Abstürzen darf eine Software deswegen aber nicht. Was könnte man stattdessen tun?

Man sollte diese eine Anmeldung abbrechen, den einzelnen Kanal herunterfahren und einfach weiter machen.

Interface dicht

Wenn es richtig brummt, geht viel Datenvolumen in Richtung der Endgeräte über den L2TP Tunnel. Auf der Datenleitung mischen sich L2TP-Datenpakete und L2TP-Steuerbefehle.

L2TP: Control connection terminated: 6 (No buffer space available)

Wenn ein Interface ausgehend unter Volllast steht, kann es nicht mehr die Daten von den einliefernden Prozessen abnehmen. Die Unmöglichkeit Daten abzunehmen, signalisiert das Unix mit ENOBUFS.

Der MPD beendet daraufhin sofort den L2TP Kanal und wirft alle Nutzer raus. Eine viel bessere Lösung gibt es vermutlich nicht: Man könnte etwas warten und die Aussendung erneut probieren. Für den L2TP Kanal sollte es einem die Mühe wert sein.

Andererseits kann man die Netzwerkkarte effektiver konfigurieren. Denn die hat wirklich ein Problem.

# sysctl dev.igb | fgrep no_desc_avail
dev.igb.1.queue0.no_desc_avail: 19
dev.igb.1.queue1.no_desc_avail: 0
dev.igb.1.queue2.no_desc_avail: 9
dev.igb.1.queue3.no_desc_avail: 0 

Die Defaulteinstellung von hw.igb.txd und hw.igb.rxd kann und sollte man von 1024 auf 4096 erhöhen. Das entschärft das Problem.

Darüberhinaus ist besonders eine Karte mit mehreren Queues anfällig für dieses Problem: Der MPD handelt alle L2TP Verbindungen in einem Thread ab und so landen diese alle in der gleichen Sendequeue. Da vier Sendequeues vorhanden sind, werden diese nur mit einem Viertel der möglichen Geschwindigkeit geleert.

Mehrere LNS laufen unter igb, andere unter em-Treibern. Der em-Treiber hat nur eine ausgehende Warteschlange und diese Maschinen sind deutlich unauffälliger gegen diese Abbrüche. Also wechseln alle LNS von igb auf em.

Die 5%-Hürde führte bei der diesjährigen Bundestagswahl spektakulär zu einem Verwerfen von fast sechs Millionen Stimmen. Auch ich hatte mir dazu Gedanken gemacht. Der überarbeitete Vorschlag besteht darin bis zu 5% der Stimmen im Sinne einer stabilen Mehrheitsfindung zu opfern. Doch was würde eine solche Änderung normalerweise bedeuten?

Für die Beantwortung der Frage, ob die Wahl 2013 ein Ausreißer war oder einem Trend folgt, ist ein Blick in die Vergangenheit notwendig. Dabei stehen ausschließlich die Stimmen und Parteien im Vordergrund, die es nicht in den Bundenstag geschafft haben: Die Sonstigen.

Ausgehend von den Daten des Bundeswahlleiters wurden für jedes Jahr die Bundesergebnisse erfaßt. Zu beachten sind zwei Ausnahmen:

  • Im Jahr 1949 gab es keine 5%.-Hürde
  • Im Jahr 1990 wurde in Ost und West getrennt eine 5%-Hürde angewandt.
Jahr Angetretene Parteien Gültige Stimmen Sonstige Parteien 5%-Hürde Verworfene Stimmen %-Anteil Sonstige
1949 15 23732398 Wahl ohne 5%-Hürde
1953 13 27551272 6 1377564 1803026 6,54
1957 13 29905428 6 1495271 2010826 6,72
1961 9 31550901 5 1577545 1796408 5,69
1965 11 32620442 7 1631022 1186449 3,64
1969 12 32966024 8 1648301 1801699 5,47
1972 8 37459750 4 1872988 348579 0,93
1976 16 37822500 12 1891125 333595 0,88
1980 12 37938981 8 1896949 749646 1,98
1983 13 38940687 8 1947034 201962 0,52
1987 16 37867319 11 1893366 512817 1,35
1990 24 46455772 18 2322789 3740292 8,05
1994 22 47105174 16 2355259 1698766 3,61
1998 33 49308512 27 2465426 2899822 5,88
2002 24 47996480 18 2399824 1459299 3,04
2005 25 47187988 19 2359399 1757610 3,72
2009 27 43371190 21 2168560 2606902 6,01
2013 30 43726856 25 2186343 6859439 15,69

Für die Trendanalyse sind Graphen aber sicher besser geeignet. Also mal schauen, wie die "Sonstigen Parteien" sich so verteilen. Die Anzahl der Stimmen, die unter die 5%-Hürde fallen habe ich im Sinne meines Vorschlags gleich gestrichen.

wahl-sonstige-historie

Es ist klar zu erkennen, daß der Trend zu immer mehr Parteien bei der Wahl geht. Erst 2013 ist ein so erheblicher Teil der Stimmen verworfen worden. Der Wert im Jahr 1990 geht maßgeblich auf den knappen Verlust der Grünen im Westgebiet mit 4,8% zurück. Insofern besteht in beiden Jahren eine ähnliche Situation: Es gibt in beiden Fällen Parteien, die knapp die 5%-Hürde verfehlen, deren Stimmen aber fast komplett über der summierten 5%-Hürde liegen.

Die nun offene Frage ist, wie sich die Begrenzung der 5%-Hürde auf maximal 5% der zu verwerfenden Stimmen auswirkt. Welche Parteien kommen somit wie stark in die Parlamente? Ist dann die damals geschlossene Koalition immer noch möglich?

Jahr Gebildete
Koalition
Zusätzliche Parteien beim Abschneiden
von unten
Zusätzliche Parteien beim Abschneiden
von allen
Alte Koalition weiterhin noch möglich?
1953 CDU/CSU,FDP, DP, GB/BHE   12 KPD    6 KPD
   3 BP
Ja/Ja
1957 CDU/CSU, DP   26 GB/BHE   10 GB/BHE Ja/Ja
1961 CDU/CSU, FDP   15 GDP (DP-BHE)    4 GDP (DP-BHE) Ja/Ja
1965 CDU/CSU, FDP 5%-Hürde nicht überschritten
1969 SPD, FDP   23 NPD    3 NPD Nein/Ja
1972 SPD, FDP 5%-Hürde nicht überschritten
1976 SPD, FDP
1980 SPD, FDP
1983 CDU/CSU, FDP
1987 CDU/CSU, FDP
1990 CDU/CSU, FDP   27 GRÜNE   17 GRÜNE
   5 REP
Ja/Ja
1994 CDU/CSU, FDP 5%-Hürde nicht überschritten
1998 SPD, GRÜNE   13 REP    5 REP
   1 DVU
Nein/Ja
2002 SPD, GRÜNE 5%-Hürde nicht überschritten
2005 CDU/CSU,SPD
2009 CDU/CSU, FDP   13 PIRATEN    5 PIRATEN
   2 NPD
Ja/Ja
2013 CDU/CSU, SPD
CDU/CSU, GRÜNE
SPD, LINKE, GRÜNE
  31 FDP
  31 AfD
  14 PIRATEN
  27 FDP
  27 AfD
  10 PIRATEN
   4 NPD
   2 FREIE WÄHLER
Ja/Ja
Ja/Ja
Nein/Nein

Fazit

Die Beschränkung der zu verwerfenden Stimmen auf maximal 5% der gültigen Stimmen ist historisch gesehen nicht schädlich.

Das Verfahren, die Parteien solange rauszuwerfen, bis die 5%-Hürde überschritten würde (Abschneiden von unten), verhindert in zwei Jahren (1969/1998) die doch knappe Koalition. Es kam in den letzten Jahren immer nur die stärkste der sonstigen Parteien hinzu, oft sogar fast in Fraktionsstärke.

Das Verfahren, allen sonstigen Parteien die Stimmen wegzunehmen, bis die 5%-Hürde erreicht ist (Abschneiden von allen), verändert an den historischen Regierungen nichts. In allen Fällen sind die zusätzlich hinzukommenden Parteien deutlich unter Fraktionsstärke und es kommen mehr Parteien ins Parlament.

Die Auswirkungen des "Abschneidens von allen" sind demokratischer (mehr sonstige Parteien, geringerere Einfluß für einzelene sonstige Parteien).

Die Cisco ASA kann mit mehreren CAs umgehen, aber wann kommen welche Zertifikate zur Anwendung? Wie funktioniert das mit mehren CA? Wie überlebt man den Rollover von CA-Schlüsseln?

Hier kommt fast ausschließlich L2TP over IPSec zum Einsatz, weil dieses von praktisch allen Betriebssystemen nativ unterstützt wird. Es ist also keine Clientsoftware notwendig. Für diesen Artikel wird auch nur der Fall behandelt, wenn überhaupt eine Zertifikatsauthenisierung stattfindet.

Was im Hintergrund passiert

Wählt sich ein VPN-Client ein, präsentiert er zuerst sein Zertifikat (aggressive Mode). Zu diesem Zeitpunkt hat die ASA noch keinerlei weitere Informationen und prüft das Client-Zertifikat gegen alle konfigurierten trust-points.

Wurde das Nutzerzertifikat für gültig befunden, schaut die ASA anhand der Angaben des Client-Zertifikats in den certificate map nach, welche Kennung in der tunnel-group-map nachgeschlagen werden soll. Dort findet sich dann die entsprechende tunnel-group. Diese Indirektion gestattet es verschiedene Zertifikatseigenschaften zu analysieren die dann doch nur auf wenigetunnel-groups zusammenfallen.

Fehlt ein passender Eintrag in der certificate-map, wird versucht, den OU-Eintrag im Subject des Client-Zertifikats alstunnel-group Bezeichner zu finden.

Schlägt auch dieses fehl, so wird die Gruppe DefaultRAGroup genutzt.

Nun steht fest, welche tunnel-group genutzt werden soll. Von dort holt sich die ASA den zu verwendenden trust-point. Dieser legt fest, welches Server-Zertifikat ausgewählt wird.

Steht in der tunnel-group auch das Kommando chain, so wird nicht nur das Server-Zertifikat, sondern die ganze Zertifikatskette dieses trust-points mitgeschickt.

CA-Rollover

Es ist möglich, als CA-Zertifikat eines Trust-Points auch ein Zwischenzertifikat (intermediate) einzuspielen. In Verbindung mit derchain Option liefert die ASA dann die Zertifikatskette aus, die der Client zur Validierung benötigt.

Die bisherige aktive CA besteht, weil nach wie vor von ihr ausgestellte CA-Zertifikate im Umlauf sind, die validiert werden müssen. Das Zertifikate der ASA unter dieser CA ist allerdings abgelaufen.

asa-hosting# sh crypto ca certificates iks2013 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 09:15:08 CET Jan 10 2013
    end   date: 09:15:08 CET Jan 10 2014
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Validity Date:
    start date: 16:48:03 CET Jan 9 2013
    end   date: 16:48:03 CET Feb 8 2015

Zuerst einmal wird die CA des neuen Jahres von der alten CA signiert. Diese Zwischenzertifikat ist der Ersatz für die bisherige alte "iks2013". Überall, wo ikev1 trust-point iks2013, steht nun ikev1 trust-point iks2013-14.

asa-hosting# sh crypto ca certificates iks2013-14 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 02:50:30 CET Jan 10 2014
    end   date: 02:50:30 CET Jan 10 2015
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Validity Date:
    start date: 22:09:53 CET Jan 8 2014
    end   date: 22:09:53 CET Jan 18 2016

Dazu kommt noch das CA des neuen Jahres, die überall dort als trust-point verwendet wird, wo keine alten Zertifikate mehr im Umlauf sind.

asa-hosting# sh crypto ca certificates iks2014 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 02:50:30 CET Jan 10 2014
    end   date: 02:50:30 CET Jan 10 2015
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Validity Date:
    start date: 22:08:13 CET Jan 8 2014
    end   date: 22:08:13 CET Feb 7 2016

Mittels der crypto ca certificate map Regeln werden die Tunnel-Gruppen so ausgewählt, daß dem Client das jeweils passende Server-Zertifikat vorgelegt wird.

Praktisch genügt es überall, iks2013-14 zu verwenden, weil jeder Client die alte oder neue CA kennt. Mit dem Zwischenzertifikat können beide Clientarten korrekt validieren. Man kann aber mit diesen drei Trust-Points die alten CA-Zertifikate stückweise und im laufenden Betrieb entfernen.

asa-aa-9

In unserer shared Exchange-Umgebung, auf der auch kleine Kunden ein paar Postfächer preisgünstig hosten können, gibt es Quota für die Postfächer. Und wenn dann jemand gegen das Quota rennt, will er natürlich wissen, warum das Postfach voll ist. Als Admin hat man aber sinnvollerweise keinen Einblick in die Inhalte. Was also tun?

Werkzeuge

Glücklicherweise gibt es die PowerShell. Microsoft hat schon vor einigen Jahren damit angefangen, Funktionalitäten zuerst für die Kommandozeile bereit zu stellen und die graphischen Interfaces dann nur bei Bedarf anzubinden. Fast logischerweise ist eine solche Statistikfunktion also auch nicht über die graphischen Administrationsoberflächen erreichbar.

Das benötigte Kommando heißt Get-MailboxFolderStatistics. Es liefert eine Statistik über die Ordner eines Postfaches. Also genau das, was ich brauche.

Als erste Frage stellt die nach der Auswahl. Optionen, die die GUID oder ähnlichen Quatsch haben wollen, sind ungeeignet. Aber mit -Identity kann man E-Mail-Adressen angeben.

Bleibt also nur noch mit Where-Object sich auf die relevanten Folder zu beschränken, diese nach Größe zu sortieren und das Ergebnis in Tablenform auszugeben.

Ergebnis:

[PS] C:\Windows\system32>Get-MailboxFolderStatistics -Identity email@domain |
> where-object FolderSize -gt 0 |
> Sort-Object FolderSize -Descending |
> format-table FolderPath,FolderSize,ItemsInFolder

FolderPath                FolderSize  ItemsInFolder
----------                ----------  -------------
/Posteingang               646.6 MB           1407
/Sent                      236.5 MB            678
/Trash                     2.239 MB             64
/Deletions                 1.691 MB             48
/Drafts                    781.2 KB              8
/Gelöschte Elemente        476.3 KB              9
/Gesendete Elemente         39.0 KB              4
/Kalender                   12.4 KB              3
/Kontakte/Recipient Cache  8.212 KB              6
/Calendar Logging          7.019 KB              1  

Was will mensch mehr?

Nebenan beschäftigt man sich mit der Laufzeit von Programmen anhand des Spieles Subtract a Square. Da ich aus einem anderen Projekt heraus in eine ähnliche Situation geriet, möchte ich diese Vorlage hier nutzen. Es geht darum, eine effiziente Methode zu finden, eine größere Menge an Werten systematisch nach verschiedenen Kriterien zu durchsuchen.

Aufgabestellung

Beim Spiel geht es darum, abwechselnd von einer vorgegebenen, positiven Zahl eine Quadratzahl abzuziehen, ohne ins Minus zu rutschen. Wer die letzte positive Zahl abziehen kann, hat gewonnen. Das Spiel endet offensichtlich mit dem Wert 0.

Für derartige Nimm-Spiele gibt es eine allgemeine Gewinnstrategie: Man zieht so, dass der Gegner nicht gewinnen kann.

Dazu tabellarisiert man alle Spiele mit kleineren Startzahlen und schaut, ob man dieses kleinere Spiel gewinnen könnte. Kann man das nicht, hat man eine Verliererposition. Mit der Kenntnis aller kleineren Spielausgänge muss man nur den ersten Spielzug betrachten.

Prozedurale Lösung

Zum Verständnis hier eine prozedurale Lösung des Problems:

with Ada.Text_IO;
with Ada.Command_Line;

procedure SubtractSquare is

   function Winners(i : Natural) return Boolean is
      type bitfield is array(0 .. i) of Boolean;
      pragma Pack(bitfield);
      win : bitfield := (0 => False, others => True);
   begin
      for pos in win'Range loop
         for offset in 1 .. pos loop
            declare
               square : Natural := offset*offset;
            begin
               exit when square > pos;
               if win(pos - square) then
                  win(pos) := False;
                  exit;
               end if;
            end;
         end loop;
      end loop;
      return win(i);
   end;

   package Cmd renames Ada.Command_Line;
   package BIO is new Ada.Text_IO.Enumeration_IO(Boolean);

   pos : Positive := Positive'Value(Cmd.Argument(1));
begin
   BIO.Put(Winners(pos));
end SubtractSquare;

Dieses Programm erzeugt ein (kompaktes) Bitfeld und setzt die Werte von kleinen zu großen Positionen. Der letzte Wert ist dann das gewünschte Ergebnis. Die gewünschte Position wird dem ersten Argument der Kommandozeile entnommen.

$ gnatmake -O2 subtractsquare.adb 
ada -c -O2 subtractsquare.adb
gnatbind -x subtractsquare.ali
gnatlink subtractsquare.ali -O2
$ ./subtractsquare 9
FALSE

Soweit so einfach.

Die Laufzeit ist maximal quadratisch (wegen der Doppelschleife), es besteht aber Hoffnung nur knapp über linear zu landen, weil die zweite Schleife vorzeitig abgebrochen wird.

Funktionale Lösung

Die direkte Übernahme dieses Ansatzes in eine funktionale Programmiersprache wie Haskell ist trivial:

import System.Environment

squares = [ i*i | i <- [ 1 .. ] ]

winners :: [Bool]
winners = False : [ and [ not $ winners !! (i-x)
                        | x <- takeWhile (<= i) squares
                        ]
                  | i <- [1 .. ]
                  ]

main = do [c] <- getArgs
          count <- readIO c
          print (winners !! count)

Man baut sich also eine unendliche Liste der möglichen Offsets (Quadrate). Mit der bastelt man die unendliche Liste der Gewinnerwerte zusammen, indem man beim Aufbau auf die Liste selbst zurückgreift. Das funktioniert, weil man nur auf Werte zugreift, die schon berechnet werden konnten.

Von der Liste gibt man das entsprechende Element zurück.

Unglücklicherweise ist das ziemlich langsam, denn die Doppelschleife ist eigentlich eine Dreifachschleife. Die Datenstruktur "[]" ist eine einfach verkettete Liste, die der "!!"-Operator immer von Anfang an durchlaufen muss.

Und genau das Problem habe ich in einem anderen Kontext auch. Also muss da eine Lösung her.

Effizientere Implementierung

Um die ständigen Rücksprünge zu vermeiden, kann man die Tatsache ausnutzen, dass man eigentlich mit mehreren Indizes (um Quadrate versetzt) linear durch die Liste durchläuft.

winners :: [Bool]
winners = False : worker 1 squares []
 where
  worker i so@(s:sn) rs
    | s == i    = worker' i sn (winners:rs)
    | otherwise = worker' i so          rs
  worker' i ss rs = and (map (not . head) rs)
                  : worker (i+1) ss (map tail rs)

Die Implementierung besteht also darin, mitzuzählen und jedes mal, wenn man eine Quadratzahl erreicht hat, einen weiteren Runner über das bisherige Feld aufzunehmen. Das macht die Teilfunktion worker.

Die eigentliche Wertermittlung erfolgt in der Teilfunktion worker', die von allen Runnern das erste Element auswertet und mit den Resten in die nächste Iteration läuft.

Ein direkter Vergleich der Laufzeiten zeigt einen durchschlagenden Erfolg:

subsquare-value-runtime

Seltsame Spitzen

Ungewöhnlich sind die Spitzen der violetten Kurve in diesem Graphen. Wo kommen die her? Fehlmessungen?

Also lass ich weitere Werte berechnen und sehe, dass die Spitzen bleiben. (Den Teil mit dem count ignoriere man mal vorerst.)

subsquare-stream-valuesum

Nun gut, es mag an der Schrittweite liegen, denn ich nehme nur alle 1000 Werte einen Messpunkt. Also mal in Einzelschritten in ein solches Intervall hinein hüpfen:

subsquare-stream-detail

Auch hier zeigt die violette Kurve ein extrem zackiges Bild. Warum?

Weil Haskell faul ist. Lazy evaluation ist eine Eigenschaft von Haskell, nur dann einen Wert auszurechnen, wenn der auch gebraucht wird.

In diesem Fall lautet die Aufgabe, einen bestimmten Wert in einer Liste auszugeben. Dazu geht Haskell die Listenkonstruktion durch und stellt fest, dass in jeder Iteration ein neues Element erzeugt wird. (In worker')

Um den konkreten Wert dann doch zu ermitteln, geht Haskell die Berechnung an und beginnt mit dem letzten hinzugefügten Runner. Der steht aber am Anfang der Liste und mit etwas Glück erwischt er gleich einen Abbruchwert. Damit kann Haskell das Ergebnis ausgeben und ist fertig.

Nur, wenn das Spiel wirklich eine komplexere Situation zu bewerten hat, muss Haskell deutlich mehr berechnen.

Um ihn zu zwingen, alle Werte zu ermitteln lasse ich die Anzahl der Gewinnzahlen bis zu der angefragten Position zu ermitteln.

--          print $ winners !! count
          print . length . filter id . take count $ winners

Eine alternative Formulierung wäre:

          print $ length [ x | x <- take count winners , x ]

Das Ergebnis ist verblüffend. Es ist genau die grüne count-Kurve in den oben stehenden Diagrammen.

Immer, wenn ein neuer Gewinnwert dazu kommt (oder in kleinen Schritten erreichbar wäre), steigt die Rechenzeit deutlich an. Das ist an der überlagerten blauen Stufenkurve zu sehen.

Als Gegentest kann man die Konstruktion "(winners:xs)" in worker durch "(xs ++ [winners])" ersetzen und zuerst den Wert des direkten Vorgängers benutzen. Das stellt ebenfalls sicher, dass alle Werte ermittelt werden. Die Laufzeiten liegen dann in vergleichbaren Größenordnungen wie beim count-Fall.

Warum dauert die Abarbeitung in Einzelfällen aber deutlich länger als im count-Fall? Er hat doch eigentlich weniger zu berechnen?

Die von Haskell zurückgelegten Teilberechnungen sind eine teuere Angelegenheit, sie anzulegen und später auszurechnen kostet deutlich mehr Zeit (und Speicher) als direkt zur Rechnung zu schreiten.

Nochmal!

Mit diesen Erkenntnissen vergleiche ich jetzt nochmal die beiden Algorithmen: Backreferenz per "!!"-Operator und mehrere Stream-Runner. Allerdings berechne ich diesmal die Anzahl der Gewinnzahlen.

subsquare-sum-runtime

Auch hier ist der Vergleich ähnlich: Die Runner gewinnen deutlich.

Evtl. hat ja die count-Berechnung auch das andere Verfahren massiv verlangsamt? Also beide Laufzeiten im direkten Vergleich:

subsquare-backref-valuesum

Die Backreferenz-Methode benötigt auch dann viel Zeit, wenn sie gar nicht alle Werte berechnen muss. Die Berechnung aller Werte dauert aber konstant länger. Beide Laufzeiten sind aber vergleichbar.

Zum Abschluss noch der direkte Vergleich der Methoden in der logarithmischen Darstellung:

subsquare-sum-runtime-log

Die Backreferenz-Methode ist klar polynomial (vermutlich O(n3)) während die Stream-Methode noch exponentiell aussieht (was sie aber nicht ist).

Fazit

Man achte bei der Programmierung stets darauf, ob der Algorithmus zum Programmumgebung passt.

Ist das nicht der Fall, verschlechtern sich die Ergebnisse erheblich. Dann muss entweder der Algorithmus (Streams statt Backreferenzen) oder die Umgebung (Data.Array statt Listen) angepasst werden.

Will man die Vorteile der Programmumgebung (Lazy Evaluation) erhalten, muss man die gewohnten algorithmischen Bahnen verlassen.

Als Belohnung winkt eine überdurchschnittliche Performance.