Contquer: An optimized distributed cooperative query caching architecture

The backend database system is often the performance bottleneck in multi-tier architectures. This is particularly true if there is a cluster of application servers while there is only a single database backend. A common approach to scale the database component is query result caching. The idea is to cache the results of a query submitted to the database in a cache. If the query is consequently requested again, the result can be retrieved from the cache instead of the query again being submitted to the database. Query caching can play a vital role in reducing latency by avoiding access to the database, and improving throughput by avoiding a database bottleneck. Existing approaches, however, have two limitations. First, they do not exploit the full capacity of the caches. Each application server has its own cache and frequently used objects will likely be cached in all caches, limiting the number of different objects and queries that can be cached. Furthermore, a query can only be served from the cache if previously the exact same query was posed. In this thesis, we introduce Contquer, a distributed cooperative caching algorithm that uses a distributed caching architecture where each object is only cached at one application server and each application server has access to local and remote caches. Thus, the full capacity of all caches can be exploited. Furthermore, we optimize the query cache by exploiting the cache even if only part of a query can be served from the cache. For that we analyze the containment of queries within other queries. Contquer determines when a query can be fully or partially served from the cache, and automatically generates remainder queries to the database if necessary. This thesis reports on the design and implementation of Contquer. It also conducts experiments that show that performance is improved considerably with the proposed algorithm. We conclude that the use of a distributed caching infrastructure and the ability to retrieve partial results from the cache improves performance in terms of hit-rate, throughput and latency.Le système de base de données est souvent un point critique en terme de performance dans les architectures multi-tiers. Ceci est particulièrement vrai dans le cas d'un groupe de serveurs d'application alors qu'il y a seulement une seule base de données. Une approche commune pour améliorer la performance de base de données est la mise en cache de résultat de requêtes. L'idée est de mettre en cache les résultats d'une requête soumise à la base de données. Si cette requête est demandée à nouveau, le résultat peut être récupéré à partir du cache au lieu de soumettre la requête à nouveau à la base de données. La mise en cache de requêtes peut jouer un rôle vital dans la réduction de latence en évitant l'accès à la base de données, et d'améliorer le débit en évitant la congestion de la base de données. Les approches existantes ont cependant deux limitations. D'abord, ils n'exploitent pas la pleine capacité des caches. Chaque serveur d'application a son propre cache et des objets fréquemment utilisés seront probablement mis en cache dans tous les caches, ce qui limite le nombre d'objets et de requêtes qui peuvent être mis en cache. En outre, une requête ne peut être servie à partir du cache que si elle a déjà été servie de la base données. Dans cette thèse, nous introduisons Contquer, un algorithme de mise en cache distribué et coopérative qui utilise une architecture de mise en cache distribuée où chaque objet est uniquement mis en cache à un seul serveur d'application et que chaque serveur d'application a accès à des caches locaux et distants. Ainsi, la capacité totale de tous les caches peut être exploitée. En outre, nous optimisons le cache de requête en exploitant la mémoire cache, même si une partie seulement d'une requête peut être servie à partir du cache. Pour cela, nous analysons le confinement de requêtes dans les autres requêtes. Contquer détermine le moment où une requête peut être totalement ou partiellement servie à partir du cache, et s'il le faut génère automatiquement le reste des requêtes à la base de données. Cette thèse porte sur la conception et la mise en œuvre de Contquer. Il mène également des expériences qui montrent que la performance est considérablement améliorée avec l'algorithme proposé. Nous concluons que l'utilisation d'une infrastructure de mise en cache distribuée et la possibilité de récupérer les résultats partiels de la mémoire cache améliore la performance en termes de taux de réussite, de débit et de latence