• Entwicklung/Architektur
  • Methoden
  • Programmiersprachen
• Betrieb
  • Datenbanken
  • Server
  • IT-Security
  • Speicher
  • Netzwerke
  • Virtualisierung
  • Verfügbarkeit
  • Künstliche Intelligenz
• Management und Recht
  • Projektmanagement
  • Digitalisierung
  • IT-Recht
  • IT-Selbständige
• Aktuelles
• Termine
• IT-Jobs

☰

• Entwicklung/Architektur
• Betrieb
• Management und Recht
• News
• IT-Jobs
• Newsletter

Martin Boßlet 23. Mai 2017

Memoisation in Ruby [Teil 1]

Wann nutze ich Memoisation und wann nicht?

Es wird augenblicklich klar, dass die Vorteile von Memoisation verpuffen, wenn der Code-Teil, dessen Ergebnis es zu speichern gilt, nur einmal aufgerufen wird. Möchte man eine Methode mit Argumenten memoisieren, macht dies nur Sinn, wenn die Menge der möglichen Argumente überschaubar bleibt. Sollten diese in der Mehrheit unterschiedlich sein, kommt der Memoisationseffekt kaum zum Tragen. Ein anderer Fall, bei dem sich Memoisation nicht lohnt: Wenn der memoisierte Code-Teil so schnell ausgeführt werden kann, dass sich der Overhead der Memoisation unter Umständen sogar negativ auf die Laufzeit auswirken würde.

Im Kontext von Rails z. B. sollte man sich bewusst sein, dass die meisten Objekte nur für die Dauer eines einzelnen Requests bestehen, z. B. Controller werden pro Request jedes Mal neu erzeugt (dazu gleich mehr). Folglich lohnt sich Memoisation auch nur dann, wenn der memoisierte Teil mehrfach während ein- und desselben Requests aufgerufen wird.

Gefahr von Speicherlecks bei langlebigen Objekten

Vorsicht ist geboten, wenn ein Objekt, welches Memoisation nutzt, von weiteren Objekten referenziert wird. Sollte eines der referenzierenden Objekte z. B. über Requestgrenzen hinweg Bestand haben, läuft man Gefahr, ein Speicherleck zu schaffen. Obwohl das referenzierte Objekt, welches Memoisation implementiert, unter Umständen nicht mehr gebraucht wird, wird es dennoch nicht vom Garbage Collector erfasst, weil die Referenz innerhalb des langlebigen Objekts weiterhin Gültigkeit besitzt. Ähnliches kann auch passieren, wenn das memoisierende Objekt selbst z. B. als globale Singleton-Instanz oder Konstante Request-Grenzen überdauert. Nehmen wir als (zugegebenermaßen recht konstruiertes) Beispiel:

class MemoizedUsers

  def initialize
    @users = {}
  end

  def []=(id, user)
    @users[id] = user
  end

  def [](id)
    @users[id]
  end

end

USER_CACHE = MemoizedUsers.new

class UsersController

  def show
    id = params[:id]
    return USER_CACHE[id] if USER_CACHE[id]
    USER_CACHE[id] = User.find(id)
  end

end

Da USER_CACHE als Konstante niemals vom Garbage Collector erfasst wird, tummeln sich mit zunehmender Laufzeit immer mehr User-Objekte in USER_CACHE. Es wird immer mehr Speicher verbraucht, der nicht wieder freigegeben werden kann – irgendwann kommt es unausweichlich zum NoMemoryError.

Thread-Safety-Probleme beim Zugriff mehrerer Threads

Wie vorhin erwähnt erzeugt Rails für jeden Request eigene Controller-Instanzen und schafft somit eine "Shared Nothing Architecture" [4]. Und dies aus gutem Grund. Denn würde man Controller-Instanzen über Requests hinweg wiederverwenden, würde sich die Anwendung schlagartig verkomplizieren: Man müsste fortan den Zugriff auf geteilte Objekte synchronisieren und darauf achten, dass Thread-lokale Zustände eigens und unabhängig verwaltet werden. Obwohl technisch möglich, vermeidet man eine solche Architektur, da sie fehleranfällig ist, schlecht skaliert (wegen der Flaschenhälse bei der Synchronisation) und letztlich nur Frust bringt. Die Nachteile überwiegen bei weitem die Vorteile, die man durch die geringere Allokation von Objekten gewinnen würde.

Und gerade weil Rails diesen Ansatz wählt, müssen wir uns bei der Entwicklung selten Gedanken über Threads und etwaige Synchronisationsprobleme machen. In Bezug auf Memoisation bilden hier allerdings Singleton-Objekte oder Konstanten, die Request-Grenzen überdauern, eine Ausnahme, auf die es zu achten gilt. In solchen Fällen können potenziell mehrere Threads gleichzeitig auf ein Objekt zugreifen, was zu Race Conditions bei der Memoisierung führen kann.

Ein Beispiel für eine Race Condition

Um die Problematik zu verdeutlichen, sehen wir uns folgendes Beispiel an:

class Shared

  attr_reader :counter

  def initialize
    @counter = 0
    @mutex = Mutex.new
  end

  def expensive_computation
    @result ||= begin
      # To force the issue, uncomment
      # sleep 0.001
      @mutex.synchronize do
        @counter +=1
      end
      42
    end
  end

end

1000.times do
  shared = Shared.new

  5.times.map do
    Thread.new do
      shared.expensive_computation
    end
  end.map(&:join)

  if shared.counter != 1
    puts "Danger: #{shared.counter}"
  end
end

Wenn Sie dieses Beispiel ausführen, tritt das Problem je nach verwendeter Ruby-Version mit entsprechend höherer oder niedrigerer Wahrscheinlichkeit auf: Mit CRuby (der Standardversion, die Sie z. B. von ruby-lang.org beziehen) ist die Wahrscheinlichkeit geringer, während bei JRuby die Wahrscheinlichkeit wesentlich höher ist. Der Grund hierfür ist das GIL (Global Interpreter Lock), was dazu führt, dass in CRuby immer nur genau ein Thread und ein CPU-Kern zu gegebener Zeit Code ausführen kann. Bei einer Implementation wie JRuby, die echte Parallelität unterstützt und diese Einschränkung nicht besitzt, tritt das Problem entsprechend öfter auf. Wenn Sie den Code aber oft genug mit CRuby ausführen, werden Sie auch dort das Problem antreffen. Dies dient gleichzeitig auch als Gegenbeweis für die falsche Annahme, dass das GIL CRuby-Code automatisch Thread-sicher macht [5,6,7].

Was genau ist das Problem mit obigem Code? Obwohl wir einen Mutex verwenden, um das Hochzählen von counter selbst gegen Race Conditions abzusichern, passiert es, dass counter nicht gleich 1 ist. Doch das war die eigentliche Intention, denn Memoisation soll uns ja genau diesen Fall garantieren, dass Shared::expensive_computation eben nur genau ein einziges Mal ausgeführt wird. Und doch wird es oft genug zweifach oder sogar noch öfter ausgeführt. Der Grund ist, dass die bedingte Zuweisung kein atomarer Ausdruck ist. Vielmehr wird @result erst ausgelesen, um zu prüfen, ob es zu true evaluiert, und falls nicht, wird der begin-Block ausgeführt, und am Ende seines Ergebnisses @result zugewiesen. Vereinfacht passiert dies:

1. Lese @result
2. Prüfe @result == true
    2.1 Falls Ja mit 3. fortfahren
    2.2 Falls Nein:
        2.2.1 Führe begin-Block aus und erhalte Ergebnis
        2.2.2 Weise Ergebnis @result zu
3. Gebe @result zurück

Die Race Condition kann nun wie folgt auftreten. Nehmen wir an, zwei Threads, T1 und T2, rufen Shared::expensive_computation auf. Nehmen wir weiter an, T1 führt 1. und 2. aus, und @result ist noch unberührt, hat also den Wert nil. T1 will nun also folgerichtig mit 2.2 weitermachen. Nehmen wir nun an, dass in genau diesem Moment der Thread-Scheduler einen Context Switch veranlässt und somit T1 angehalten wird und danach T2 angestoßen wird. T2 führt nun 1. aus, danach 2. und jetzt macht sich das Problem bemerkbar. Obwohl T1 sich bereits in dem Code-Zweig befindet, wo der begin-Block ausgeführt wird und letzten Endes dessen Ergebnis @result? zugewiesen wird, ist dies zum jetzigen Zeitpunkt noch nicht geschehen. Das bedeutet also, dass @result nach wie vor nil ist, und daher T2 genauso mit 2.2 fortsetzt, wie das T1 schon zuvor begonnen hatte. Egal, wie die weiteren Context Switches von T1 und T2 nun in der Folge verlaufen, Fakt ist, dass 2.2. von beiden Threads ausgeführt wird und somit doppelt ausgeführt wird. Wenn @result aber erst einmal gesetzt ist, tritt dieses Problem im weiteren Verlauf natürlich nicht mehr auf. Es ist also nur die Initialisierung von @result, die Probleme bereiten kann.

Race Conditions vermeiden

Was also tun, um dieses Problem zu vermeiden? Die naheliegende Lösung: Auf Memoisation in solchen Fällen verzichten. Dies ist aber natürlich keine befriedigende Antwort, da man sicher nicht ohne Grund den entsprechenden Code memoisieren will, etwa weil es aus Performancegründen einfach nicht möglich ist, die entsprechende Stelle für jeden Thread erneut auszuführen. Oft kann man aber damit leben, dass der Code zur Memoisation doppelt oder mehrfach ausgeführt wird und akzeptiert dies stillschweigend. Dennoch muss man sich des Problems bewusst sein, da es äußerst schwierig zu debuggen ist, sollte es dann doch irgendwann einmal auftreten. Leider ist es häufig der Fall, dass solche Probleme erst in Produktion auftreten, weil beim Entwickeln oder in der Testumgebung einfach noch nicht genügend Traffic vorhanden war, um das Problem zu forcieren.

Es gibt aber Fälle, wo mehrfache Ausführung absolut inakzeptabel ist, etwa weil mehrfaches Ausführen schlicht unmöglich ist. Eine Lösung in solchen Fällen ist im Code-Beispiel bereits angedeutet: Man nutzt einen Mutex, um die Zugriffe programmatisch zu synchronisieren. Wenn wir im obigen Beispiel Shared::expensive_computation entsprechend synchronisieren, indem wir den synchronize-Block nach außen ziehen, ist das Problem gelöst.

def expensive_computation
  @mutex.synchronize do
    @result ||= begin
      @counter +=1
      42
    end
  end
end

Double-Checked Locking

Allerdings bringt diese Lösung einen Nachteil mit sich. Die Synchronisation via Mutex kostet natürlich Zeit und kann sich schnell als Flaschenhals erweisen, wenn die memoisierte Ressource entsprechend häufig frequentiert wird. Wie oben bereits ausgeführt, ist dies doppelt ärgerlich, weil ja eigentlich nur die Initialisierung von @result anfällig für Race Conditions ist. Sobald einmal geschehen, ist die Synchronisation in der Folge überflüssig. Und doch wird jeder Zugriff mit obiger Lösung synchronisiert, egal ob @result bereits initialisiert wurde oder nicht.

Gibt es eine Lösung, die genau das tut, was wir uns wünschen? Also allein die Initialisierung mittels Synchronisation abzusichern und danach unsynchronisierten Zugriff zu erlauben? Es gibt sie in der Tat, jedoch ist sie komplizierter, als man zunächst annehmen möchte. Die Lösung wird allgemein als Double-Checked Locking [8] bezeichnet. In Ruby, angewandt auf unser Beispiel sähe dies so aus:

def expensive_computation
  unless defined?(@result)
    @mutex.synchronize do
      unless defined?(@result)
        @counter +=1
        @result = 42
      end
    end
  end

  @result
end

Wir prüfen erst generell, ob @result initialisiert wurde. Klären wir erst den einfachen Fall, dass dies bereits geschehen ist. Dann gibt es auch nichts mehr zu tun, wir geben @result direkt zurück – ohne Synchronisation. Interessant ist der Fall, dass @result noch nicht initialisiert wurde. Da wir in diesem Fall synchronisieren müssen, ist die synchronize-Anweisung noch keine Überraschung. Überraschend ist allerdings die folgende erneute Prüfung, ob @result initialisiert wurde. Dies erscheint erst einmal nicht intuitiv, schließlich haben wir dies doch bereits zuvor schon geprüft. Wieso ist es also nötig, erneut zu prüfen? Stellen wir uns dazu wieder zwei Threads T1 und T2 vor, die beide obigen Code ausführen. T1 prüft, ob @result initialisiert wurde, was noch nicht geschehen ist, und läuft nun auf den synchronize-Block auf. Nehmen wir erneut an, dass in genau diesem Moment der Context Switch geschieht und T2 übernimmt. T2 führt die gleichen Schritte aus und auch hier ist @result noch nicht initialisiert, also läuft auch T2 auf den synchronize-Block auf. Nehmen wir an, der Thread-Scheduler gewährt T2 Einlass in den Block, T2 führt den Block aus und initialisiert in der Folge @result. Wenn jetzt der Context Switch zurück zu T1 erfolgt und T1 Einlass in den synchronized-Block gewährt wird, dann weiß T1 an dieser Stelle erst einmal nichts davon, dass T2 @result bereits initialisiert hat. Wir erkennen also, dass Eintritt in den synchronized-Block nicht gleichbedeutend damit ist, dass die Initialisierung notwendig ist. Zwar ist ein Thread, der sich innerhalb des Blocks befindet, der einzige, der ihn gerade ausführt, jedoch ist das keine Garantie dafür, dass nicht ein anderer zuvor schon den Block ausgeführt hatte. Wir müssen also als allererstes prüfen, ob die Arbeit nicht bereits verrichtet wurde.

Das Arbeiten mit Threads wird nicht umsonst gefürchtet und passend hierzu ist die Tatsache, dass selbst Double-Checked Locking noch nicht vollkommen ausreicht, um das Problem ein für alle Mal zu lösen [9,10]. Falls die zugrundeliegende Programmiersprache kompiliert ist oder zumindest wie im Fall von Ruby nicht direkt interpretiert wird, sondern aus Programmcode eine Zwischenform von Bytecode generiert wird, hat man ohne entsprechende Garantien des Compilers oder Bytecode-Generators keine Sicherheit, dass Double-Checked Locking tatsächlich funktioniert, da der Generator Code-Sequenzen optimiert und die Reihenfolge nach Gutdünken ändern kann. In Java z. B. hat man dieses Problem ab Version 5 durch ein überarbeitetes Speichermodell gelöst [11,12,13]. Das hat zur Folge, dass z. B. für als volatile deklarierte Variablen vom Bytecode-Generator bestimmte Garantien gegeben werden. Es gibt strikte Regeln zu erlaubten sowie nicht erlaubten Umstrukturierungen bezüglich lesender bzw. schreibender Zugriffe. In Ruby gibt es zu diesem Zeitpunkt leider keine äquivalenten Garantien, jedoch wird auch hier ein entsprechendes Speichermodell diskutiert [14,15,16].

Die gute Nachricht ist, dass wir Double-Checked Locking schon jetzt nutzen können, bevor das Speichermodell umgesetzt wird. Mit Hilfe des Gems concurrent-ruby[17], ist es möglich, Double-Checked Locking verlässlich für Memoisation zu implementieren. concurrent-ruby implementiert dazu die fehlenden Bausteine mittels nativem Code für CRuby, so dass plattformübergreifend (auch in JRuby) Garantien gemacht werden können, die uns die Sprache selbst mangels Speichermodell nicht machen kann. Die finale Implementierung mit concurrent-ruby für unser Problem:

require 'concurrent'

class Shared

  attr_reader :counter

  def initialize
    @counter = 0
    @mutex = Mutex.new
    @cache = Concurrent::Map.new
  end

  def expensive_computation
    @cache[:memoized] || @mutex.synchronize do
      @cache.compute_if_absent(:memoized) do
        @counter +=1
        42
      end
    end
  end

end

Hier endet der erste Teil von Memoisation in Ruby. Im zweiten Teil steigen Sie ein in Fortgeschrittene Memoisierung.
 

Autor

Das könnte Sie auch interessieren