Oamenii de știință găsesc echilibrul optim între stocarea datelor și timp | Revista Quanta

Cu aproximativ 70 de ani în urmă, un inginer de la IBM pe nume Hans Peter Luhn a schimbat în liniște cursul informaticii. Luhn deținea deja mai multe brevete, inclusiv unul pentru un dispozitiv care ar putea măsura numărul de fire ale unei cârpe și altul pentru un ghid care determina ce băuturi amestecate poți face din ingredientele din bucătărie. Dar într-o lucrare internă IBM din 1953, el a propus o nouă tehnică de stocare și regăsire a informațiilor care este acum integrată în aproape toate sistemele de calcul: tabelul hash.

Tabelele hash sunt o clasă majoră de structuri de date. Ele oferă o metodă deosebit de convenabilă pentru accesarea și modificarea informațiilor din bazele de date masive. Dar această tehnologie vine cu un compromis inevitabil.

Într-o 1957 hârtie publicată în Jurnalul IBM de Cercetare și Dezvoltare, W. Wesley Peterson a identificat principala provocare tehnică pe care o reprezintă tabelele hash: trebuie să fie rapide, ceea ce înseamnă că pot prelua rapid informațiile necesare. Dar trebuie să fie și compacte, folosind cât mai puțină memorie posibil. Aceste obiective duble sunt în mod fundamental în contradicție. Accesarea și modificarea unei baze de date se poate face mai rapid atunci când tabelul hash are mai multă memorie; iar operațiunile devin mai lente în tabelele hash care folosesc mai puțin spațiu. De când Peterson a prezentat această provocare, cercetătorii au încercat să găsească cel mai bun echilibru între timp și spațiu.

Informaticienii au demonstrat acum matematic că au găsit compromisul optim. Soluția a venit de la a pereche de recente lucrări care se completau reciproc. „Aceste lucrări rezolvă întrebarea deschisă de lungă durată cu privire la cele mai bune compromisuri spațiu-timp posibile, dând rezultate profund surprinzătoare, care mă aștept să aibă un impact semnificativ pentru mulți ani de acum înainte”, a spus Michael Mitzenmacher, un informatician de la Universitatea Harvard care nu a fost implicat în niciunul dintre studii.

„Aș spune cu siguranță că este o afacere mare”, a adăugat Rasmus Pagh, un informatician la Universitatea din Copenhaga. „Mulți oameni au lucrat la această problemă, încercând să vadă cât de mult poți strânge spațiul, având și operațiuni eficiente din timp. Acesta este cel pe care mi-ar fi plăcut să o rezolv.”

Făcând un hash din ea

Tabelele hash sunt printre cele mai vechi, mai simple, mai rapide și mai utilizate structuri de date astăzi. Sunt concepute pentru a efectua trei operațiuni de bază: inserții, care adaugă elemente noi în baza de date; interogări, care accesează un articol sau verifică dacă acesta există; și ștergeri. Un tabel hash poate fi efemer - existent doar atâta timp cât rulează un anumit program - sau poate fi o parte permanentă a sistemului de operare al computerului dvs. Un browser web, cum ar fi Chrome sau Safari, poate avea mai multe tabele hash încorporate menite să țină evidența diferitelor tipuri de date.

Intrările dintr-un tabel hash sunt stocate ca perechi, cu elementul – informația în sine – conectat la o cheie care identifică informația. Conectați o cheie la algoritmul de interogare al unui tabel hash și vă duce direct la element. Poate că nu sună atât de extraordinar, dar pentru bazele de date enorme poate economisi timp.

Pentru a lua un exemplu extrem de simplificat, luați în considerare Oxford English Dictionary, care are definiții pentru mai mult de 600,000 de cuvinte. Dacă o ediție digitală se bazează pe un tabel hash, puteți pur și simplu să utilizați un anumit cuvânt ca cheie și să treceți direct la definiție. Fără un tabel hash, dicționarul s-ar baza probabil pe un mecanism de căutare mult mai lent, folosind un proces de eliminare pentru a converge în cele din urmă către definiția solicitată. Și în timp ce un tabel hash poate găsi orice cuvânt într-o perioadă constantă de timp (de obicei o mică fracțiune de secundă), timpul de căutare pentru alte metode poate crește pe măsură ce numărul de cuvinte din dicționar crește. Un tabel hash oferă și un alt avantaj: poate menține dicționarul dinamic, facilitând inserarea cuvintelor noi și ștergerea celor învechite.

Cercetătorii au petrecut zeci de ani construind tabele hash care încearcă să maximizeze viteza și să minimizeze memoria. În secolul al XX-lea, soluțiile tindeau să ofere câștiguri semnificative doar într-un singur aspect, timp sau spațiu. Apoi, în 20, cercetătorii a arătat că teoretic era posibil să se facă un salt major de eficiență atât în ​​timp cât și în spațiu simultan. Cu toate acestea, ar fi nevoie de încă două decenii pentru ca cercetătorii să descopere echilibrul ideal între cele două.

Amestecarea datelor

Primul pas major spre acest obiectiv a venit în 2022 la a importantă conferință de informatică în Roma. Acolo, o echipă a propus un tabel hash cu funcții noi care ar putea oferi cea mai bună combinație de eficiență în timp și spațiu concepută până acum. Primul autor al lucrării (enumerat în ordine alfabetică) a fost Michael Bender de la Universitatea Stony Brook, așa că este denumit în mod obișnuit Bender et al. masa hash. Deși echipa nu a încercat să construiască un tabel hash funcțional, ei au dovedit că, în principiu, ar putea fi construit cu caracteristicile pe care le-au descris.

Pentru a evalua tabelul hash cu care au venit, grupul a produs o curbă de compromis - un grafic care prezintă timpul per operație (inserție sau ștergere) pe o axă și spațiul ocupat de memorie pe cealaltă. Dar acest grafic definește spațiul într-un mod special: din cauza modului în care sunt construite, tabelele hash au nevoie de mai multă memorie decât doar minimul necesar pentru a stoca un anumit set de elemente. Oamenii de știință în informatică numesc acest spațiu suplimentar „biți risipi”, chiar dacă nu sunt cu adevărat irosite și sunt, într-o oarecare măsură, necesare. Axa spațială de pe o curbă de compromis măsoară numărul de biți irosi pe cheie.

Analizând o curbă de compromis, cercetătorii pot afla cel mai rapid timp posibil pentru un tabel hash care utilizează o anumită cantitate de spațiu. De asemenea, pot răsturna întrebarea pentru a afla cel mai mic spațiu posibil pentru un anumit timp de operare. De obicei, o mică modificare a unei variabile va duce la o mică modificare a celeilalte, a spus William Kuszmaul, un informatician teoretic la Harvard și co-autor al lucrării din 2022. „Dacă dublezi timpul, poate vei înjumătăți numărul de biți irosi pe cheie.”

Dar nu este cazul cu tabelul de hash pe care l-au proiectat. „Dacă creșteți timpul cu puțin, biții irosi pe cheie scad exponențial”, a spus Kuszmaul. Curba de schimb a fost atât de abruptă, încât a fost literalmente în afara graficelor.

Echipa și-a construit tabelul de hash în două părți. Ei aveau o structură de date primară, în care articolele sunt stocate fără niciun biți irosi, și o structură de date secundară, care ajută o solicitare de interogare să găsească elementul pe care îl caută. Deși grupul nu a inventat noțiunea unei structuri de date secundare, ei au făcut o descoperire crucială care a făcut posibilă tabelul lor hash hipereficient: eficiența generală a memoriei structurii depinde de modul în care structura primară își aranjează elementele stocate.

Ideea de bază este că fiecare articol din structura principală are locații de depozitare preferate - o locație cea mai bună, una a doua cea mai bună, a treia cea mai bună și așa mai departe. Dacă un articol se află în cel mai bun loc, numărul 1 este atașat acestuia, iar acel număr este stocat în structura de date secundară. Ca răspuns la o interogare, structura secundară furnizează doar numărul 1, care precizează locația exactă a articolului în structura principală.

Dacă articolul se află în cel mai bun loc al 100-lea, structura de date secundară atașează numărul 100. Și deoarece sistemul folosește binar, acesta reprezintă numărul 100 ca 1100100. Este nevoie de mai multă memorie, desigur, pentru a stoca numărul 1100100 decât 1. — numărul atribuit unui articol atunci când acesta se află în cel mai bun loc. Diferențele de acest fel devin semnificative dacă depozitați, să zicem, un milion de articole.

Astfel, echipa și-a dat seama că, dacă mutați continuu elementele din structura de date primară în locațiile lor preferate, puteți reduce semnificativ memoria consumată de structura secundară fără a fi nevoie să măriți timpul de interogare.

„Înainte de această lucrare, nimeni nu și-a dat seama că puteți comprima și mai mult structura datelor prin mutarea informațiilor”, a spus Pagh. „Aceasta a fost marea perspectivă a lucrării Bender.”

Autorii au arătat că invenția lor a stabilit o nouă limită superioară pentru cele mai eficiente tabele hash, ceea ce înseamnă că a fost cea mai bună structură de date concepută până acum în ceea ce privește eficiența în timp și spațiu. Dar a rămas posibilitatea ca altcineva să se descurce și mai bine.

Obligat să reușească

Anul următor, o echipă condusă de Huachheng Yu, un informatician la Universitatea Princeton, a încercat să îmbunătățească tabelul hash al echipei Bender. „Am muncit foarte mult și nu am putut face asta”, a spus Renfei Zhou, student la Universitatea Tsinghua din Beijing și membru al echipei lui Yu. „Atunci am bănuit că limita lor superioară era [și] o limită inferioară” – cel mai bun lucru care poate fi atins. „Când limita superioară este egală cu limita inferioară, jocul se termină și ai răspunsul tău.” Indiferent cât de inteligent ai fi, nicio masă hash nu poate face mai bine.

Echipa lui Yu a folosit o strategie nouă pentru a afla dacă acea bănuială era corectă, calculând o limită inferioară din primele principii. În primul rând, au motivat că, pentru a efectua o inserare sau o ștergere, un tabel hash - sau, într-adevăr, orice structură de date - trebuie să acceseze memoria computerului de câteva ori. Dacă ar putea da seama de numărul minim de ori necesar pentru o tabelă hash eficientă din punct de vedere al spațiului, ar putea să-l înmulțească cu timpul necesar per acces (o constantă), oferindu-le o limită inferioară a timpului de execuție.

Dar dacă nu știau nimic despre tabelul hash (cu excepția faptului că era eficient din punct de vedere al spațiului), cum ar putea cercetătorii să-și dea seama de numărul minim de ori necesar pentru a accesa memoria? Ei au derivat-o pur din teorie, folosind un domeniu aparent fără legătură numit teoria complexității comunicării, care studiază câți biți sunt necesari pentru a transmite informații între două părți. În cele din urmă, echipa a reușit: și-au dat seama de câte ori o structură de date trebuie să-și acceseze memoria pentru fiecare operație.

Aceasta a fost realizarea lor cheie. Apoi au reușit să stabilească o limită inferioară a timpului de execuție pentru orice tabel hash eficient din punct de vedere al spațiului. Și au văzut că se potrivește exact cu masa de hash Bender. „Ne-am gândit [la început] că ar putea fi îmbunătățit”, a spus Zhou. „S-a dovedit că ne-am înșelat.” Asta, la rândul său, însemna că problema lui Peterson fusese în sfârșit rezolvată.

Pe lângă faptul că răspunde la întrebarea veche de zeci de ani, a spus Kuszmaul, lucrul uimitor despre dovada Yu este generalitatea ei. „Limita lor inferioară se aplică tuturor structurilor de date posibile, inclusiv celor care nu au fost încă inventate.” Asta înseamnă că nicio metodă de stocare a datelor nu poate depăși tabelul hash Bender în ceea ce privește memoria și viteza.

Hashing în viitor

În ciuda eficienței fără precedent a noului tabel hash, nimeni nu va încerca să o construiască în curând. Este prea complicat de construit. „Un algoritm care este rapid în teorie nu este neapărat rapid în practică”, a spus Zhou.

Nu este neobișnuit ca astfel de decalaje între teorie și practică să persistă mult timp, a spus Kuszmaul, deoarece teoreticienii tind să ignore factorii constanti. Timpul necesar pentru a efectua o operație este de obicei înmulțit cu un număr, o constantă a cărei valoare exactă poate fi nesemnificativă din punct de vedere teoretic. „Dar, în practică, constantele contează cu adevărat”, a spus el. „În lumea reală, un factor de 10 este un final de joc.”

Tabelele de hash efective încă se îmbunătățesc din punct de vedere material, chiar dacă sunt cu mult sub idealul teoretic. De exemplu, un nou tabel hash numit AisbergHT, construit de Bender, Kuszmaul și alții, este mult mai bun decât predecesorii săi. Potrivit lui Kuszmaul, este de două ori mai rapid decât cel mai eficient tabel hash disponibil în prezent și utilizează de trei ori mai puțin spațiu decât cel mai rapid tabel hash.

Mitzenmacher speră că rezultatul din 2023 poate aduce în curând un alt tip de beneficiu: „De câte ori obțineți o nouă limită inferioară – în special una care implică niște tehnici noi – există întotdeauna speranța că le puteți folosi... pentru probleme conexe.”

Există, de asemenea, satisfacția intelectuală care vine din a ști că ai rezolvat o problemă dificilă și de lungă durată, a spus informaticianul Piotr Indyk al Institutului de Tehnologie din Massachusetts. „Odată ce ești sigur că anumite structuri de date nu pot fi îmbunătățite, asta poate ajuta la concentrarea efortului de cercetare.” În cele din urmă, cercetătorii de date își pot îndrepta atenția de la provocarea lui Peterson și se pot concentra asupra noilor probleme din informatica teoretică, dintre care nu lipsesc.