TDD im Flow – Teil 3

Was bisher geschah:

• TDD im Flow – Teil 1
• TDD im Flow – Teil 2
  

Test #4: Blockierte Entnahme

Nun geht es an den Kern meines Abstrakten Datentyps: die Sequentialisierung.

Ich muss die Entnahme aus den Queues nach Round Robbin einschränken. Es darf nur entnommen werden, wenn eine Queue nicht gerade blockiert wird. Die Blockierung beginnt, wenn ein Worker aus einer unblockierten Queue entnimmt – und wird automatisch aufgehoben, wenn er wieder nach Arbeit fragt.

Anders als im Datenmodell entworfen, implementiere ich die Sperren für Queues in einem Dictionary. Die Einträge darin sind die Flags des Datenmodells. Ich finde es jedoch besser, sie von der Liste der Queues zu trennen. Die Blockade der Entnahme ist ein anderer Aspekt als die Entnahme nach Round Robbin. Beide durch Verwaltung in unterschiedlichen Datenstrukturen zu trennen, scheint mir konsequente Anwendung des SRP.

Falls sich etwas an der Blockadestrategie ändert, muss ich nicht die Datenstruktur für die Entnahme anfassen. Es ist auch nur TryDequeue() betroffen.

internal class NotifyingMultiQueue<T>
{
    …
    readonly Dictionary<string, string> _readLocks =
        new Dictionary<string,string>(); 

    …
    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        var namedQueue = _queues[0];
        _queues.RemoveAt(0);
        _queues.Add(namedQueue);

        if (_readLocks.ContainsKey(namedQueue.Key) &&
            _readLocks[namedQueue.Key] != workerId)
            return false;

        message = namedQueue.Value.Dequeue();
        _readLocks[namedQueue.Key] = workerId;

        return true;
    }
    …

Diese Implementation erreicht das Ziel natürlich noch nicht ganz. Sie dient nur der Erfüllung eines Tests, ohne die vorherigen zu brechen.

Bevor ich aber den nächsten Test beschreibe: Haben Sie meine TDD Sünde entdeckt?

Ich habe mehr Code geschrieben, als für den Test nötig ist. Die Prüfung, ob der “arbeitsuchende” Worker derjenige ist, der eine Queue bisher blockiert hat, kommt nicht zum Tragen. Dafür müsste ich einen weiteren Test schreiben. Aber das ist nicht nötig, weil der nächste Test dafür sorgen wird, dass diese Prüfung gar nicht mehr nötig ist.

Warum habe ich dann aber _readLocks[namedQueue.Key] != workerId geschrieben? Weil es mir in dem Moment cool vorkam, an diese Feinheit gedacht zu haben. Da hab ich mich von der Idee davontragen lassen… Erst später beim nächsten Test ist mir die Überflüssigkeit der Bedingung aufgefallen.

Ich hatte sie aber nach erfolgreichem Test eingecheckt. Deshalb zeige ich sie Ihnen hier auch. So kann es halt kommen, auch wenn man sich bemüht. Mit Pair Programming wäre das vielleicht nicht passiert. Am Ende ists aber auch kein Beinbruch. Mir ist es ja aufgefallen. Wichtig ist, daraus zu lernen. Nobody is perfect – but everybody should strive for improvement. Oder so ähnlich ;-)

Test #5: Blockierte Queue wieder freigeben

Bisher wurde eine Queue bei Entnahme nur gesperrt. Jetzt muss sie wieder entsperrt werden. Das geschieht, wenn der Worker, der sie gesperrt hat, wieder frei ist. Der ADT bemerkt, wann ein Worker seine Arbeit an einer Nachricht beendet hat daran, dass der Worker wieder um eine Nachricht bittet:

Beim ersten Aufruf von TryDequeue() sperrt w1 die Queue q1. Bei zweiten Aufruf sperrt er q2 – und gibt damit implizit q1 wieder frei, so dass w2 daraus entnehmen kann.

In der Implementation erreiche ich das, indem ich einfach bei Aufruf immer eine eventuell durch den anfragenden Worker gesetzte Sperre lösche:

internal class NotifyingMultiQueue<T>
{
    …
    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        if (_readLocks.ContainsValue(workerId))
            _readLocks.Remove(
                 _readLocks.Where(kvp => kvp.Value == workerId)
                           .Select(kvp => kvp.Key)
                           .First());

        var namedQueue = _queues[0];
        _queues.RemoveAt(0);
        _queues.Add(namedQueue);

        if (_readLocks.ContainsKey(namedQueue.Key))
            return false;

        message = namedQueue.Value.Dequeue();
        _readLocks[namedQueue.Key] = workerId;

        return true;
    }
    …

Damit entfällt dann auch die Prüfung, ob eine Sperre durch den aktuellen Worker gesetzt worden ist. Der Fall kann nicht mehr eintreten.

Leider ist das Löschen eines Dictionary-Eintrags über den Wert statt dem Key nicht so leicht. Ich muss erst den Key (Queue-Name) aus dem Wert (Worker-ID) ermitteln. Die Linq-Query liest sich etwas umständlich.

Alternativ hätte ich ein zweites Dictionary aufsetzen können, in dem die Worker-ID als Key steht und über den Queue-Namen auf _readLocks zeigt. Aber das würde zusätzlichen Pflegeaufwand bedeuten. So scheint mir der hier eingeschlagene Weg KISS-konform.

Test #6: Blockierte Queue überspringen

Es ist merkwürdig, aber bisher bin ich ohne eine Schleife bei der Entnahme ausgekommen. Wäre ich nicht nach TDD vorgegangen, hätte ich die wahrscheinlich schon gleich am Anfang eingebaut – und die Lösung damit komplexer gemacht.

Mit TDD habe ich dagegen einige Schwierigkeiten schon aus dem Weg geräumt. Anweisungssequenzen sind leichter zu verstehen und zu testen als Schleifen.

Jetzt hilft es aber nichts mehr. Eine Schleife muss sein, wenn blockierte Queues übersprungen werden sollen. Es müssen bei TryDequeue()-Aufruf potenziell ja mehrere Queues geprüft werden.

TDD besteht aus 3 Phasen: roter Test, grüner Test und Refactoring. Bisher habe ich die letzte Phase übersprungen. Es gab nicht viel zu refaktorisieren. Jetzt wird es mir aber zuviel, was da alles in TryDequeue() passiert. Und auch KeyValuePair ist mir zu wenig aussagekräftig; mehr Domänensprache darf sein.

Zur Befriedigung des neuen Tests füge ich deshalb nicht nur Code hinzu, sondern ziehe auch Code raus in eigene Methoden. Das Listing unterscheidet Änderungen im Rahmen des Refactoring und Änderungen zur Erfüllung der neuen Anforderungen.

internal class NotifyingMultiQueue<T>
{
    readonly List<NamedQueue> _queues =
        new List<NamedQueue>();
    readonly Dictionary<string, string> _readLocks =
        new Dictionary<string,string>();

    class NamedQueue
    {
        public string Name;
        public Queue<T> Queue;
    }

    public void Enqueue(T message, string queueName)
    {
        var queue = _queues.Where(nq => nq.Name == queueName)
                           .Select(nq => nq.Queue)
                           .FirstOrDefault();
        if (queue == null)
        {
            queue = new Queue<T>();
            _queues.Add(new NamedQueue{Name=queueName, Queue=queue});
        }
        queue.Enqueue(message);
    }

    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        Free_queue_locked_for_worker(workerId);

        NamedQueue namedQueue = null;
        for (var i = 0; i < _queues.Count(); i++)
        {
            namedQueue = Get_next_queue();
            if (Queue_not_locked(namedQueue)) break;
            namedQueue = null;
        }
        if (namedQueue == null) return false;

        message = namedQueue.Queue.Dequeue();
        Lock_queue_for_worker(workerId, namedQueue);
        return true;
    }
    …

Hier zeigt es sich jetzt, dass TDD letztlich kein Verfahren ist, das zu Unit Tests führt. TryDequeue() ruft jetzt andere Methoden auf, d.h. es integriert. Noch sind diese Methoden einfach und wurden 1:1 aus Code, der eben noch in TryDequeue() stand erzeugt. Bei der Weiterentwicklung des ADT kann es aber jederzeit passieren, dass Änderungen an diesen Methoden nötig werden. Und dann stellt sich die Frage, wie diese Änderungen getestet werden.

Klar, ich kann dafür dann gezielte Tests schreiben. Doch beim Refactoring mit ReSharper sind die “Hilfsmethoden” automatisch als private deklariert worden. Es kostet dann schon einige Überwindung, die auf internal zu setzen und als Units für sich zu testen. Deshalb wird in den meisten Fällen weiter durch das Interface getestet, d.h. mit Integrationstests gearbeitet. Die testen dann natürlich auch immer noch alles andere mit. Vorteil: Black Box Tests sind unabhängig von interner Struktur. Nachteil: Black Box Tests können aufwändig werden, wenn für Kleinigkeiten das Drumherum mit getestet werden muss. Das wird besonders auffallend, sobald Attrappen ins Spiel kommen. Dazu kommt, dass bei Integrationstests eine Fehlerquelle nicht so leicht lokalisiert werden kann.

Fazit

Mit diesem Artikel wollte ich Ihnen zeigen, dass ein expliziter Entwurf von Software mittels Flow-Design nicht bedeutet, alles über Bord zu werfen, was Ihnen lieb und teuer geworden ist: Ich finde, der Abstrakte Datentyp NotifyingMultiQueue<T> ist ein solider Vertreter der Objektorientierung. Und seine Entwicklung ist eine solide Anwendung von TDD.

Darüber hinaus wollte ich Ihnen an einem realen Beispiel zeigen, wie TDD funktionieren kann: mit expliziter Testplanung, in kleinen Schritten. Nicht perfekt, aber good enough.

Schließlich haben Sie gesehen, dass selbst ich als Verfechter von Nachdenken vor dem Codieren nicht dogmatisch bin ;-) Wenn die Codierungsrealität es nahelegt, dann kann ich von meinem Entwurf auch abweichen. Erkenntnisse sind jederzeit willkommen.

Wenn Sie mögen, verfolgen Sie meine TDD-Fortschritte auch im Code. Hier die relevanten Changesets (insb. 43..50) im Mercurial Repository npantarhei.codeplex.com.

Und nun kommen Sie mit TDD und FD.

Spendieren Sie mir doch einen Kaffee, wenn Ihnen dieser Artikel gefallen hat...