Un nou algoritm ar putea accelera semnificativ navigarea pe web, făcând ca stocarea în cache să fie mai eficientă.
Programul open-source, numit „SITĂ,” introduce o nouă modalitate de a gestiona stocarea în cache web – procesul de stocare și recuperare a obiectelor din stocarea pe termen lung a unui computer pe măsură ce le întâlniți în timp ce navigați pe internet.
Aceste obiecte – fișiere minuscule stocate pe hard disk – includ imagini, logo-uri sau copii întregi ale paginilor web. Când întâlniți aceste elemente pentru prima dată, le preluați de pe server, dar sunt stocate pe hard disk pentru reutilizare. A doua oară când întâlniți aceste obiecte, browserul dvs. le poate prelua din memoria computerului, mai degrabă decât de pe server, ceea ce economisește timp și consumă mai puțină energie.
Dar, deoarece stocarea locală este limitată, algoritmii de evacuare a memoriei cache funcționează pentru a decide cât timp să stocheze obiectele și când să le înlocuiască pe cele mai vechi accesate mai rar de un utilizator, cu altele mai noi sau mai populare.
Deși există mulți astfel de algoritmi, SIEVE este o opțiune mult mai simplă și eficientă care poate accelera dramatic navigarea pe web dacă este implementată pe internet, au spus oamenii de știință în lucrarea lor preprint, publicată pe 17 decembrie 2023. Ei intenționează să prezinte lucrarea la Cel de-al 21-lea simpozion USENIX privind proiectarea și implementarea sistemelor în rețea în aprilie.
„Un motiv principal pentru care computerele și internetul sunt deloc rapide este memoria cache. Credem că cache-urile software sunt acest pilon omniprezent și totuși subapreciat care permite funcționarea web-ului modern și, prin urmare, lucrul la ele poate avea un impact imens”, co-primul. autorul lucrării Yazhuo Zhang, doctorand la Universitatea Emory din Atlanta, a declarat pentru Live Science.
Testarea unei noi abordări a stocării în cache web
Algoritmii primul intrat, primul ieșit (FIFO) funcționează prin adăugarea de noi obiecte în secvență pe o „bandă transportoare” pentru uitare. Când obiectele ajung la capătul liniei, ele sunt îndepărtate. Utilizată mai puțin recent (LRU) este o altă metodă în care obiectele se deplasează de-a lungul benzii transportoare ca în FIFO, dar dacă un obiect este solicitat din nou, acesta sare înapoi în față. Există variații mai sofisticate, dar cu cât sunt mai complexe, cu atât au mai multe bug-uri, a spus Zhang. SIEVE, prin contrast, a fost implementat cu mai puțin de 20 de linii de cod.
SIEVE folosește același mecanism de bandă transportoare, dar obiectele sunt etichetate „zero” pentru început. Când un obiect este solicitat din nou, starea lui se schimbă în „unu” și se alătură frontului liniei. Obiectele sunt evacuate în mod normal când ajung la capăt. Aceasta este cunoscută sub numele de „promovare leneșă”. Între timp, o „mână în mișcare” care scanează lungimea centurii și se întoarce la început, este programată pentru a elimina orice obiect etichetat „zero”. Această funcție asemănătoare sită se numește „retrogradare rapidă”. Oamenii de știință au spus că SIEVE este cel mai simplu algoritm care realizează atât promovarea leneșă, cât și retrogradarea rapidă.
Ei au efectuat 1.500 de teste separate împotriva a nouă algoritmi de ultimă generație, folosind istoriile reale de stocare în cache bazate pe urme urmărite din cache web de la Meta, Wikimedia, X și alte patru surse. O urmă, de exemplu, a constat în 2,8 miliarde de solicitări web făcute pentru a accesa media pe Wikipedia în 2019. Împreună, cele 1.500 de urme au cuprins 247 de miliarde de solicitări către aproape 15 miliarde de obiecte.
Ei căutau un „raport ratat” scăzut sau fracțiunea de obiecte preluate de pe web versus stocare, unde „raportul” este considerat preluarea unui obiect de pe web – cu cât este mai mic, cu atât mai bine. Nu se așteaptă ca un singur algoritm să aibă cel mai scăzut raport de rateuri în fiecare test, dar SIEVE a fost cel mai performant în 45% dintre teste, a spus Zhang pentru Live Science. Următorul cel mai bun algoritm, prin contrast, a fost cel mai performant cu doar 15%.
SIEVE a fost deja implementat în peste 10 biblioteci populare care alimentează aplicații și site-uri web moderne. Multe site-uri s-ar putea actualiza în curând la SIEVE „fără efort”, a spus Zhang. Ea a adăugat că Meta este pe cale să evalueze SIEVE în producție, în timp ce Google și-a exprimat, de asemenea, interesul de a adopta SIEVE alături de alte companii web.
„Este o tracțiune remarcabilă și neobișnuită”, a spus Zhang. Niciun algoritm de cache în ultimii 20 de ani nu a cunoscut o utilizare largă în mai multe sisteme de producție.”