Kaj je algoritem predpomnilnika: definicija, vrste in primeri (LRU, LFU, ARC)

Definicija in osnovni pojmi

Algoritem predpomnilnika je algoritem, ki upravlja vsebino predpomnilnika (cache) — torej nabor podatkov, ki jih želimo hraniti lokalno za hitrejši dostop. Ko je predpomnilnik poln, mora algoritem odločiti, kateri element iz njega izbrisati (evict). Dva ključna merila za oceno algoritmov sta stopnja zadetkov (hit rate), ki pove, kako pogosto se zahtevam uspešno postreže iz predpomnilnika, in zakasnitev (latency), ki opisuje, koliko časa traja pridobitev elementa iz predpomnilnika ali iz izvorne shrambne plasti. Algoritmi predpomnilnika torej pogosto iščejo kompromis med visoko stopnjo zadetkov in nizko zakasnitvijo.

Teoretično najboljši algoritem je t. i. Beladyjev optimalni algoritem (znan tudi kot jasnovidni ali clairvoyant algoritem): vedno bi odstranil tisti element, ki bo najkasneje v prihodnosti ponovno potreben. Ker zahteva znanje o prihodnjih zahtevah, je v praksi neuresničljiv, a služi kot teoretična spodnja meja, s katero primerjamo praktične algoritme. V nekaterih primerih (analize, simulacije) lahko izračunamo optimalni rezultat retrospektivno, da ocenimo učinkovitost dejanskih algoritmov.

Temeljne vrste in njih značilnosti

Najmanj nedavno uporabljeni (LRU) — Least Recently Used: odstrani elemente, ki so bili najdlje časa neuporabljeni. LRU je ena najpogostejših strategij, saj dobro izkorišča lokalnost sklicev (temporal locality). Implementacijsko zahteva strukture, ki sledijo vrstnemu redu uporabe (npr. povezani seznam + hash tabela za O(1) posodobitve v programski izvedbi). V strojnih predpomnilnikih se pogosto uporabijo poenostavitve zaradi stroškovnih omejitev (npr. PLRU).
Najnovejše uporabljeni (MRU) — Most Recently Used: odstrani elemente, ki so bili pravkar uporabljeni (nazadnje uporabljeni). MRU je redkejši, a koristen v posebnih vzorcih, kot so zaporedni skenirni dostopi (scan), kjer je verjetnost ponovne uporabe pravkar dostopanega elementa majhna. MRU se občasno uporablja v nekaterih predpomnilnikih podatkovnih baz, kjer tak vzorec prevladuje.
Psevdo-LRU (PLRU): poenostavljena izvedba LRU, ki zahteva manj pomnilniških bitov in manjše stroške posodobitev. Pri strojnih cache-jih (set-associative) se pogosto uporablja različica, ki uporablja eno ali nekaj kontrolnih bitov (npr. drevesni PLRU) in zagotavlja, da se v večini primerov odstrani eden od najstarejših elementov, čeprav ni strogo LRU.
Najnajredkeje uporabljeni (LFU) — Least Frequently Used: šteje, kako pogosto je bil vsak element zahtevan in odstrani tiste z najmanjšo frekvenco. LFU dobro deluje, če gre za elemente, ki imajo stalno visoko pogostost dostopov, vendar lahko trpi zaradi "težkih" elementov, ki so bili pogosto uporabljeni v preteklosti, nato pa jih pritiskajo v predpomnilniku brez aktualne vrednosti. Pogosto se uporablja LFU z dodatnim staranjem (decay) ali z omejitvijo števcev, da se temu izognemo.
Prilagodljivi nadomestni predpomnilnik (ARC): ARC (Adaptive Replacement Cache) dinamično uravnava ravnovesje med recency (LRU-gibanje) in frequency (LFU-gibanje) glede na delovne vzorce. Uporablja ločene sezname za nedavno in pogosto uporabljene elemente ter dodatne "ghost" sezname, ki sledijo elementom, izpuščenim iz predpomnilnika, da se parametri prilagodijo v realnem času. ARC je bil razvit kot samouravnotežen algoritem, ki zmanjša potrebo po ročnem nastavljanju.
Algoritem predpomnilnika za več čakalnih vrst (MQ): večslojni pristop, kjer se elementi urejajo v več čakalnih vrstah glede na njihovo frekvenco in starost; imenujejo ga tudi Multi-Queue (MQ). (Philbin in Kai Li so med avtorji, povezanimi s sorodnimi idejami.)

Arhitekture predpomnilnika (izvedbe)

Popolnoma asociativni predpomnilnik: element se lahko shrani kamorkoli v predpomnilniku — največja fleksibilnost, a zahteva kompleksno iskanje (v strojni izvedbi je običajno drago).
Dvosmerni (2-way) set-asociativni predpomnilnik: za hitre predpomnilnike procesorjev – naslov novega elementa se preslika v en set, kjer so točno dve možni mesti (ways). Pri vstavljanju se izmed obeh, po pravilu (npr. LRU ali PLRU), odstrani en element. Zahteva en nadzorni bit na par vrstic, da se označi, katera od obeh je bila nazadnje uporabljena.
Predpomnilnik z neposrednim preslikavanjem (direct-mapped): najhitrejša strojna rešitev, kjer vsak naslov preslika natanko eno mesto v predpomnilniku; vse, kar je bilo tam prej, se zamenja. Preprosta in hitra, a lahko trpi zaradi visokega konflikta (več naslovov se preslika na isto mesto).

Praktične implementacijske opombe

Stroški in kompleksnost: LRU v programski implementaciji se običajno doseže z dvema strukturama — hash tabelo za hitro iskanje in povezan seznam, ki ohranja vrstni red uporabe (prvi/zgoraj = najnovejši). To omogoča O(1) hitre posodobitve in odstranitve. V strojnih implementacijah pa so zahtevane poenostavitve (PLRU, omejena asociativnost) zaradi stroškov časa in prostora.
Števci in staranje: pri LFU morajo biti števci lahko obvladljivi (npr. omejevanje velikosti števcev ali periodično staranje/urejanje), da se prepreči zajem zgodovinsko pogostih, a zdaj neuporabnih elementov.
Predmeti z različnimi stroški pridobivanja: včasih je smiselno obdržati elemente, ki jih je drago pridobiti (v času ali resursih), tudi če so manj pogosto uporabljeni.
Predmeti različnih velikosti: če so predmeti različnih velikosti, je smiselno upoštevati prostor, ki ga zasedejo — morda je bolj smiselno zavreči en velik element, da naredimo prostor za več manjših, če s tem izboljšamo skupno stopnjo zadetkov.
Veljavnost/iztek (TTL): nekateri predpomnilniki (npr. DNS, predpomnilniki spletnih brskalnikov, predpomnilniki novic) hranijo podatke le omejen čas. Takšni elementi potečejo in jih sistem lahko odstrani ne glede na algoritem zamenjave; v manjših predpomnilnikih morda ni potreben dodaten algoritem za evikcijo.

Primeri in kdaj uporabiti katerega

- LRU je dobra izbira za številne splošne scenarije (aplikacijski cache, OS strani pomnilnika), kjer velja temporalna lokalnost. V programski opremi je pogosto implementirana kot kombinacija povezane strukture in hash tabele.

- LFU je primeren, kadar obstajajo stalno priljubljeni (hot) elementi, ki jih želimo dolgoročno obdržati. Dodatek staranja pomaga preprečiti, da bi stari popularni predmeti zasedli predpomnilnik brez trenutne vrednosti.

- ARC in sorodni adaptivni algoritmi so uporabni, ko delovni vzorci nihajo med recency-in frequency-obnašanjem; ARC avtomatično prilagaja svoje parametre, da doseže boljše splošne rezultate.

- MRU je uporaben pri skeniranju velikih podatkovnih nizov, kjer je verjetnost ponovne uporabe pravkar dostopanega elementa majhna (npr. pri nekaterih vrstah zaporednih poizvedb v podatkovnih bazah).

Koherenca predpomnilnika

Obstajajo tudi različni algoritmi za vzdrževanje koherence predpomnilnika. To velja, kadar iste podatke uporabljajo več neodvisnih predpomnilnikov (npr. več strežnikov podatkovnih baz ali več procesorskih jeder s svojim lokalnim predpomnilnikom) — takrat je potrebno zagotoviti, da posodobitve ostanejo vidne in dosledne napram drugim kopijam.

Zaključek

Izbira pravega algoritma za zamenjavo v predpomnilniku je odvisna od vrste delovnih obremenitev, omejitev strojne opreme, stroškov pridobitve podatkov in velikosti predmetov. V praksi se pogosto uporabljajo hibridne ali adaptivne rešitve (npr. ARC, 2Q, MQ), ki poskušajo zajeti prednosti več enostavnejših pristopov in zmanjšati njihove slabosti.

Katera pomnilniška mesta je mogoče shraniti v predpomnilnik, katera mesta predpomnilnika

Vprašanja in odgovori

V: Kaj je algoritem predpomnilnika?

O: Algoritem predpomnilnika je algoritem, ki se uporablja za upravljanje predpomnilnika ali skupine podatkov. Z njim se odloči, kateri element je treba izbrisati iz predpomnilnika, ko je ta poln.

V: Kaj je stopnja zadetkov?

O: Stopnja zadetkov opisuje, kako pogosto je mogoče iz predpomnilnika obdelati zahtevo.

V: Kaj opisuje zakasnitev?

O: Zakasnitev opisuje, kako dolgo je mogoče dobiti element iz predpomnilnika.

V: Kaj je Beladyjev optimalni algoritem?

O: Beladyjev optimalni algoritem, znan tudi kot jasnovidni algoritem, je učinkovit algoritem predpomnilnika, ki vedno zavrže informacije, ki jih v prihodnosti ne bomo potrebovali najdlje. Tega rezultata na splošno ni mogoče izvesti v praksi, ker zahteva predvidevanje, kaj bo potrebno daleč v prihodnosti.

V: Kako deluje sistem LRU (Least Recently Used)?

O: LRU najprej izbriše najmanj nedavno uporabljene elemente in zahteva sledenje, kaj je bilo kdaj uporabljeno, z uporabo "bitov starosti" za vsako vrstico predpomnilnika in sledenjem, katera je bila nazadnje uporabljena na podlagi bitov starosti. Vsakič, ko je uporabljena vrstica predpomnilnika, se starost vseh drugih vrstic predpomnilnika ustrezno spremeni.

V: Kako deluje funkcija MRU (Most Recent Used)?

O: MRU najprej izbriše nazadnje uporabljene elemente in ta mehanizem predpomnjenja se pogosto uporablja za predpomnilnike podatkovnih baz.

V: Kateri drugi algoritmi obstajajo za ohranjanje skladnosti predpomnilnika?

O: Obstajajo različni algoritmi za ohranjanje skladnosti predpomnilnika, kadar se za skupne podatke uporablja več neodvisnih predpomnilnikov, na primer več strežnikov zbirke podatkov, ki posodabljajo eno samo skupno datoteko s podatki.