Cache replacement policies in NoSQL databases and full-text search engines

Abstract

Problemet, eller utfordringen bak optimale måter å erstatte innhold i en cache har lenge vært populære tema innen forskning, som stammer fra sidet virtuelt minne. I det meste har foregående arbeid konsentrert seg på algoritmiske forbedringer uten å ta i bruk hvilke miljø cachen befinner seg i og hvilke bruksområder det miljøet har. NoSQL databaser og dokument søkemotorer jobber med å holde tritt med den stadig økende mengden data de skal lagre og bearbeide, som krever aktiv bruk av caching. Deres ytelse er avhengig av hvilken algoritme eller policy som blir brukt for erstatning av cachen når dens kapasitet er nådd. Gjennom tidligere arbeid som baserer seg på alt fra algoritmer for utskifting av sider i sidet virtuelt minne til moderne adaptive cache erstatnings policyer, prøver denne masteroppgaven å tilnærme seg probleme som ofte blir oversett innen cache erstatnings policyer, som for eksempel bruk av historiske data aksess mønstre for å tilpasse seg endringer i arbeidsmengden, samt å bruke størrelse av objektet eller kostnaden involvert i å hente objektet på nytt fra sitt primære lagringsmedium til utskiftning av cachen. Implementasjonene av cache erstatnings policyene som tar for seg størrelse og kostnad er simulert mot en mengde med datasett i to forskjellige kontekster, som er vektet caching og kostnadsbasert caching, mens for historiske data aksess mønstre, en simulering med vanskelig løkke lignende data viser effekten av at en menneskelig ekspert går aktivt inn for å forberede systemet. Resultatene antyder at å bruke historiske data aksess mønstre kan hjelpe i å opprettholde høy ytelse selv når utfordrene endringer skjer med arbeidslasten, og de enkleste endringene av topp moderne cache erstatnings policyer fører til høyere ytelse.

The problem of replacing cache content in the most performant way to optimize system performance has been a popular research topic, originating from paged virtual memory systems. In most cases, the previous work focuses on algorithmic improvements without considering the environments and use cases of the systems. NoSQL databases and full-text search engines are trying to keep up with the ever-increasing amount of data they store and process, which requires active use of caching. Their performance is highly dependent on the cache replacement policy, which dictates which items should reside in the cache, and how it should replace items, once its capacity is reached. Building on existing work that spans from page replacement algorithms in paged virtual memory systems to modern adaptive cache replacement policies, it tries to approach some of the more overlooked issues in cache replacement policies, such as utilizing historical access patterns when adapting to workload changes and utilizing size or retrieval cost when replacing items. The size and retrieval cost implementations are simulated towards a variety of datasets in two different runtime scenarios, weighted and cost-based caching simulations, while for historical access patterns, a simulation with a loopy workload is performed to display the effects of a human expert preparing the system. The results suggest that utilizing historical access patterns may contribute to cache performance, but it is highly dependent on identifying trends in data access patterns, and also that the simplest extensions of state-of-the-art cache replacement policies contribute to higher performance.