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

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