Adaptives Caching in verteilten Informationssysteme

Abstract

In dieser Arbeit stellen wir eine neuartige Methode für verteiltes Caching vor, die das Ausnutzen des aggregierten Hauptspeichers eines lokalen Rechnernetzwerkes für datenintensive Anwendungen erlaubt. Ein detailliertes Kostenmodell dient als Basis für die Bestimmung einer guten Cache-Allokation. Da im allgemeinen die Eingabegrößen für dieses Kostenmodell im Online- Fall nicht a priori bekannt sind und darüber hinaus dynamisch schwanken können, werden speziell angepaßte Protokolle zur Bestimmung und Verteilung dieser Informationen benutzt. Durch eine approximative Online-Auswertung des Kostenmodells paßt sich unsere Caching-Strategie adaptiv an die aktuelle Last an und kann dadurch Engpäße auf den Systemressourcen verhindern. Zur Vermeidung von Lastungleichgewichten wird aus dem Kostenmodell zusätzlich eine Lastverteilungsheuristik abgeleitet, die im Hintergrund zielgerichtete Migrationen von Objekten zur Balancierung des Systems durchführen kann. Sowohl die Anpassung an die aktuelle Last als auch die Vermeidung von Ungleichgewichten führt zu einer — verglichen mit bisherigen Methoden — deutlich besseren Leistungsfähigkeit unserer Heuristik. Eine Erweiterung des entwickelten Caching- Verfahrens berechnet eine Partitionierung des aggregierten Hauptspeichers, so daß Antwortzeitziele für unterschiedliche Klassen von Operationen sichergestellt werden.

This dissertation presents a new method for distributed caching to exploit the aggregate memory of networks of workstations in data-intensive applications. The approach is based on a detailed cost model to compute a good cache allocation. As the input parameters for the cost model are in general a-priori unkown and possibly evolve, we use specifically designed protocols to estimate and disseminate this information. Using an approximative online evaluation of the cost model,our caching heuristics adapts automatically to evolving workloads and thus avoids bottlenecks on system resources. To prevent load imbalances we further derive a load distribution method from the cost model. This load distribution method asynchronously migrates objects from highly loaded nodes onto lightly loaded nodes. The adaptation to the current workload and the prevention of imbalances result in significant performance improvements compared to prior methods. We further present a goal-oriented extension of the developed caching method, which determines a partitioning of the aggregate cache to satisfy given response-time goals for different classes of operations.