Vahemälualgoritmid: LRU, LFU, ARC ja teised selgitatud

Sügav juhend vahemälualgoritmidest: LRU, LFU, ARC ja teised selgitatud — toimimine, eelised, näited ja optimeerimisnõuanded arendus- ja andmebaasikeskkondadele.

Cache-algoritm on algoritm, mida kasutatakse vahemälu või andmegrupi haldamiseks. Peamised eesmärgid on maksimeerida tabavust (hit rate) ja vähendada päringute latentsust (vt ka latentsus). Kui vahemälu on täis, peab algoritm otsustama, milline kirje eemaldada — see otsus mõjutab suuresti süsteemi jõudlust. Lisaks tabavusele tuleb arvesse võtta ka hankekulusid, elementide suurust, aegumist ja andmete sidusust mitme vahemälu vahel.

Põhimõisted ja mõõdikud

• Hit rate — protsent päringutest, mida saab teenindada vahemälust (mida kõrgem, seda parem).
• Miss rate — päringute osa, mis läheb vahemälust mööda (1 − hit rate).
• Aegumine / TTL — mõnede vahemäluelementide eluea lõpp, mille järel neid ei tohi enam kasutada.
• Kulu — kui kallis on andme objekti uuesti hankimine (näiteks andmebaasipäring vs kohalik mälu).
• Suurus — eri üksuste mahuline erinevus mõjutab, kas on otstarbekas eemaldada üks suur element või mitu väiksemat.

Optimaalne (teoreetiline) algoritm

Kõige tõhusam vahemälualgoritm viskaks alati ära selle kirje, mida ei vajata kõige kauem tulevikus. Seda optimaalset tulemust nimetatakse Belady optimaalseks algoritmiks ehk selgeltnägija algoritmiks. Kuna tuleviku päringuid täpselt ennustada ei saa, pole seda tavaliselt reaalses süsteemis rakendada, kuid Belady annab madalaima võimaliku miss-rate'i, mille vastu teisi algoritme võrrelda.

Levimad vahemälu asenduspoliitikad

• LRU (Least Recently Used, viimati kasutatu) — eeldab, et hiljuti kasutatud objektid tõenäoliselt korduvad, seega viskab ära viimati kõige kauem kasutamata olnud elemendi. Täpne LRU saab olla kulukas: praktikas rakendatakse seda tavaliselt räsitabeli + topeltsidetud lingitud nimekirja kombinatsiooniga, mis tagab O(1) otsingu ja uuenduse. LRU perekonda kuuluvad variandid nagu 2Q (Theodore Johnson ja Dennis Shasha) ning LRU/K (Pat O'Neil, Betty O'Neil ja Gerhard Weikum); need on kasulikud eri töökoormuste puhul, et eristada lühiajalist ja püsivamat kasutust. LRU on tegelikult vahemälualgoritmide perekond.
• MRU (Most Recently Used, viimati kasutatud) — eemaldab eelistatult kõige viimati kasutatud elemendi. See on kasulik teatud mustrite korral (näiteks lineaarse skannimise puhul), kus viimane element on kõige vähem tõenäoline, et seda peagi vaja läheb. MRU-d kasutatakse mõnikord andmebaasi mälu vahemäludes (andmebaasid).
• Pseudo-LRU (PLRU) — lihtsustatud LRU-approximation, kus iga rea või väljundi kohta hoitakse ainult mõnda bitti (nt "puu" või "ring" skeem). PLRU sobib olukordadesse, kus täpne LRU on riistvaras liiga kallis (nt CPU vahemälud), kuid soovitakse siiski ligikaudset viimase kasutuse poliitikat.
• LFU (Least Frequently Used, kõige harvemini kasutatud) — jälgib, kui tihti iga kirjet kasutatakse; viskab ära need, mille kasutussagedus on madalaim. LFU on hea, kui mõnede objektide populaarsus on stabiilselt kõrgem kui teiste. LFU-l on aga oht "saastuda" vanade kõrge sagedusega elementidega, seetõttu kasutatakse tihti vananemise (decay) või piiratud pikkusega loenduritega variatsioone.
• ARC (Adaptive Replacement Cache) — dünaamiline algoritm, mis tasakaalustab LRU ja LFU käitumist. ARC hoiab mitu listi (nt T1, T2 ja vastavad "ghost" listid B1, B2) ja reguleerib automaatselt nende suurusi vastavalt töökoormusele, parandades seeläbi nii lühiajalise kui pikaajalise populaarsuse käsitlemist.
• Multi Queue (MQ) — mitme järjekorra lähenemine (Y. Zhou, J.F. Philbin ja Kai Li), kus eri järjekorrad hoiavad erineva eluea/püsivusega kirjeid; element liigub järk-järgult järjestuses, kui selle kasutussagedus/viimatisus muutub.
• Clock / Second-chance — lihtne ja efektiivne LRU-approximation, mis kasutab ühe bitti iga kirje jaoks (viited), et anda "teine võimalus" enne eemaldamist; sobib hästi operatsioonisüsteemi lehekülje asendamiseks.

Vahemälu arhitektuurilised variandid

• 2-suunaline assotsiatiivne kogum — iga aadress mapitakse vahemälu komplekti; komplektis on kaks võimalikku pesa (way), kuhu kirje võib minna. Asenduspoliitika otsustab, kumb kahe seast visata (tavaliselt LRU kahe vahel), ja selleks hoitakse ühte bitti iga rea paari kohta, mis näitab, kumb oli viimati kasutatud.
• Otse kaardistatud vahemälu (direct-mapped) — iga aadress loob ühe kindla asukoha vahemälus; uus element kirjutab selle asukoha sisu üle. See on kiire ja lihtne, kuid võib põhjustada rohkem konflikte (thrashing) kui assotsiatiivsed skeemid.
• Riistvarapõhised PLRU skeemid — protsessorite vahemäludes kasutatakse sageli puu-struktuure või ringe, et hoida asendusinformatsiooni väiksema bitimahuga, säilitades kõrge kiiruse.

Implementatsioonimõtted ja kompleksus

• LRU täpne rakendamine — tavaliselt räsitabel + topeltsidetud lingitud nimekiri: otsimine (hit) tagab O(1) ning liigutamine esimese positsiooni samuti O(1). Mälu- ja kuluplussina on see lihtsam väiksematele tarkvara-vahemäludele.
• LFU rakendamine — nõuab loendurite hooldust; efektiivseks saab kasutada mitmetasandilisi loendeid või min-heap-i. On oluline lisada loendurite vananemine, et vältida üksikute ajalooliselt populaarsete elementide püsivat eelistamist.
• ARC ja sarnased — keerukamad, aga annavad hea üldise jõudluse eri töökoormuste korral; nõuavad täiendavat metaandmete haldust (ghost-lists jms).
• Riistvara piirangud — CPU vahemälud eelistavad lihtsamaid, lühikese latentsusega skeeme (PLRU, 2-way), et minimeerida kritilise rada viivitust.

Muud olulised kaalutlused

• Erineva maksumusega esemed: säilitage või eelistage objekte, mille uuesti hankimine on kallis või aeglane (nt kauge andmeallikas).
• Elementide suurus: kui üksused on erineva suurusega, võib olla otstarbekas eemaldada suur kirje, et teha ruumi mitmele väiksemale; mõnel süsteemil kasutatakse "valjuse" (cost/size) suhte alusel skoorimist.
• Aegumisperioodid: uudiste, DNS-i või brauseri vahemälude puhul on objektidel kehtivusaeg (TTL). Sellistel juhtudel eemaldatakse vananenud kirjed automaatselt või neile ei osutata juba kui neid tahetakse kasutada.
• Kirjutuspoliitika: write-through vs write-back mõjutab, millal andmed kettale/baasi tagasi kirjutatakse ja millal on vaja hoolitseda "dirty" blokkide eest enne eemaldamist.
• Mitme vahemäluga sidusus (coherence): erinevad algoritmid ja mehhanismid on vajalikud siis, kui sama andme koopia on mitmes sõltumatus vahemälus (näiteks mitu andmebaasiserverit või jagatud vahemälud). Seda teemat käsitleb ka vahemälu sidususe probleem.
• Edenemine ja ebaühtlane töökoormus: reaalsetes süsteemides võivad esineda mustrid (näiteks skaneerimine või hooajalised populaarsuse kõikumised), mis nõuavad kohanduvat strateegiat (nt ARC, MQ või LRU/K).

Praktilised soovitused

• Vali algoritm vastavalt töökoormusele: lühiajalist korrapärasust arvestav töökoormus sobib LRU-ga; stabiilselt populaarseid elemente eelistav töökoormus võib kasu saada LFU-st või ARC-ist.
• Kui riistvaralised piirangud on ranged, eelistada lihtsamaid PLRU- või assotsiatiivseid skeeme.
• Mõõda ja simuleeri: võrdle oma töökoormuse puhul tegelikku hit-rate'i Belady-optimumiga, testi erinevaid poliitikaid ja jälgi ka latentsust ning I/O-kulusid.
• Kombineeri strateegiaid: näiteks LRU + LFU hübriidid või ghost-listid (ARC) annavad sageli parem vastupidavuse erinevatele mustritele.

Kokkuvõttes ei ole olemas ühte universaalset "parimat" vahemälualgoritmi — igal poliitikatel on oma tugevused ja piirangud olenevalt töökoormusest, riistvarapiirangutest ja ärivajadustest. Hea lahendus sünnib meetmete (hit-rate, latentsus, kulu) selgest määratlemisest, simulatsioonist ja vajadusel adaptatiivsest poliitikast.

Küsimused ja vastused

K: Mis on vahemälu algoritm?

K: Mis on tabamuse määr?

K: Mida kirjeldab latentsus?

K: Mis on Belady optimaalne algoritm?

K: Kuidas töötab LRU (Least Recently Used)?

K: Kuidas töötab kõige hiljuti kasutatud (MRU)?

K: Millised muud algoritmid on olemas vahemälu sidususe säilitamiseks?

Otsing