Forskere finder den optimale balance mellem datalagring og tid | Quanta Magasinet

For omkring 70 år siden ændrede en ingeniør hos IBM ved navn Hans Peter Luhn stille og roligt datalogiens kurs. Luhn havde allerede flere patenter, herunder et for en enhed, der kunne måle en kluds trådantal og en anden for en guide, der bestemte, hvilke blandede drinks du kunne lave af ingredienserne i dit køkken. Men i et internt IBM-papir fra 1953 foreslog han en ny teknik til lagring og hentning af information, som nu er indbygget i stort set alle beregningssystemer: hashtabellen.

Hash-tabeller er en stor klasse af datastrukturer. De tilbyder en særlig bekvem metode til at få adgang til og ændre information i massive databaser. Men denne teknologi kommer med en uundgåelig afvejning.

I en 1957 papir offentliggjort i IBM Journal of Research and Development, W. Wesley Peterson identificerede den største tekniske udfordring, som hashtabeller udgør: De skal være hurtige, hvilket betyder, at de hurtigt kan hente de nødvendige oplysninger. Men de skal også være kompakte og bruge så lidt hukommelse som muligt. Disse dobbelte mål er grundlæggende modstridende. Adgang til og ændring af en database kan gøres hurtigere, når hash-tabellen har mere hukommelse; og operationer bliver langsommere i hashtabeller, der bruger mindre plads. Lige siden Peterson lagde denne udfordring op, har forskere forsøgt at finde den bedste balance mellem tid og rum.

Dataloger har nu matematisk bevist, at de har fundet den optimale afvejning. Løsningen kom fra en par for nylig papirer der supplerede hinanden. "Disse papirer løser det langvarige åbne spørgsmål om de bedst mulige rum-tid-afvejninger, hvilket giver dybt overraskende resultater, som jeg forventer vil have en betydelig indflydelse i mange år fremover," sagde Michael Mitzenmacher, en datalog ved Harvard University, som ikke var involveret i nogen af ​​undersøgelserne.

"Jeg vil helt klart sige, at det er en stor sag," tilføjede Rasmus Pagh, datamatiker ved Københavns Universitet. "Mange mennesker har arbejdet på dette problem og forsøgt at se, hvor meget man kan presse plads, samtidig med at man har en tidseffektiv drift. Det er den, jeg gerne ville have løst."

At lave en hash af det

Hash-tabeller er blandt de ældste, enkleste, hurtigste og mest udbredte datastrukturer i dag. De er designet til at udføre tre grundlæggende handlinger: indsættelser, som tilføjer nye elementer til databasen; forespørgsler, som får adgang til et element eller kontrollerer, om det eksisterer; og sletninger. En hash-tabel kan være flygtig - eksisterer kun, så længe et bestemt program kører - eller den kan være en permanent del af din computers operativsystem. En webbrowser såsom Chrome eller Safari kan have flere indbyggede hashtabeller beregnet til at holde styr på forskellige slags data.

Indtastninger i en hash-tabel gemmes som par, hvor elementet - selve informationen - er forbundet med en nøgle, der identificerer informationen. Sæt en nøgle ind i en hash-tabels forespørgselsalgoritme, og den fører dig direkte til emnet. Dette lyder måske ikke så ekstraordinært, men for enorme databaser kan det være en stor tidsbesparelse.

For at tage et ekstremt forenklet eksempel, overvej Oxford English Dictionary, som har definitioner for mere end 600,000 ord. Hvis en digital udgave er afhængig af en hash-tabel, kan du blot bruge et givet ord som nøgle og gå direkte til definitionen. Uden en hash-tabel ville ordbogen sandsynligvis stole på en meget langsommere søgemekanisme, ved at bruge en elimineringsproces for til sidst at konvergere til den ønskede definition. Og mens en hash-tabel kan finde et hvilket som helst ord i en konstant mængde tid (normalt en lille brøkdel af et sekund), kan søgetiden for andre metoder gå op, efterhånden som antallet af ord i ordbogen stiger. En hash-tabel tilbyder også en anden fordel: Den kan holde ordbogen dynamisk, hvilket gør det nemt at indsætte nye ord og slette forældede ord.

Forskere har brugt årtier på at bygge hashtabeller, der forsøger at maksimere hastigheden og minimere hukommelsen. I det 20. århundrede havde løsninger en tendens til at tilbyde betydelige gevinster i blot ét aspekt, tid eller rum. Så i 2003, forskere viste at det teoretisk var muligt at lave et stort effektivitetsspring i både tid og rum samtidigt. Det ville dog tage yderligere to årtier for forskere at finde ud af den ideelle balance mellem de to.

Data-shuffle

Det første store skridt mod dette mål kom i 2022 kl større datalogikonference i Rom. Der foreslog et team en hash-tabel med nye funktioner, der kunne levere den bedste kombination af tid og pladseffektivitet, der endnu er blevet udtænkt. Den første forfatter af papiret (opført alfabetisk) var Michael Bender fra Stony Brook University, så det omtales almindeligvis som Bender et al. hash tabel. Selvom holdet ikke forsøgte at bygge en fungerende hash-tabel, beviste de, at den i princippet kunne konstrueres med de funktioner, de beskrev.

For at evaluere den hash-tabel, de kom med, producerede gruppen en afvejningskurve - en graf, der plotter tiden pr. operation (indsættelse eller sletning) på den ene akse og pladsen optaget af hukommelsen på den anden. Men denne graf definerer rummet på en speciel måde: På grund af hvordan de er bygget, har hashtabeller brug for mere hukommelse end blot det absolutte minimum, der kræves for at gemme et givet sæt elementer. Dataloger kalder denne ekstra plads "spildte stykker", selvom de ikke rigtig er spildt og til en vis grad er nødvendige. Rumaksen på en afvejningskurve måler antallet af spildte bits pr. nøgle.

Ved at analysere en afvejningskurve kan forskere finde ud af den hurtigst mulige tid for en hash-tabel, der bruger en given mængde plads. De kan også vende spørgsmålet rundt for at finde ud af den mindst mulige plads til en given operationstid. Normalt vil en lille ændring i en variabel føre til en lille ændring i den anden William Kuszmaul, en teoretisk datamatiker ved Harvard og medforfatter til 2022-opgaven. "Hvis du fordobler tiden, vil du måske halvere antallet af spildte bits pr. nøgle."

Men det er ikke tilfældet med hashbordet, de har designet. "Hvis du øger tiden med en lille smule, falder de spildte bits pr. nøgle eksponentielt," sagde Kuszmaul. Afvejningskurven var så stejl, at den bogstaveligt talt var ude af hitlisterne.

Holdet byggede deres hashbord i to dele. De havde en primær datastruktur, hvor emnerne er gemt uden spildte bits overhovedet, og en sekundær datastruktur, som hjælper en forespørgsel med at finde det emne, den leder efter. Selvom gruppen ikke opfandt begrebet en sekundær datastruktur, gjorde de en afgørende opdagelse, der gjorde deres hypereffektive hash-tabel mulig: Strukturens samlede hukommelseseffektivitet afhænger af, hvordan den primære struktur arrangerer sine lagrede elementer.

Den grundlæggende idé er, at hvert element i den primære struktur har foretrukne opbevaringssteder - en bedste placering, en næstbedste, en tredjebedste og så videre. Hvis en vare er på sit bedste sted, er tallet 1 påsat det, og det nummer gemmes i den sekundære datastruktur. Som svar på en forespørgsel giver den sekundære struktur kun tallet 1, som angiver varens nøjagtige placering i den primære struktur.

Hvis elementet er på dets 100. bedste sted, tillægger den sekundære datastruktur tallet 100. Og fordi systemet bruger binær, repræsenterer det tallet 100 som 1100100. Det kræver selvfølgelig mere hukommelse at gemme tallet 1100100 end 1 — nummeret, der er tildelt en vare, når den er på det bedste sted. Sådanne forskelle bliver betydelige, hvis du f.eks. opbevarer en million genstande.

Så teamet indså, at hvis du konstant flytter elementer i den primære datastruktur til deres mere foretrukne placeringer, kan du reducere den hukommelse, der forbruges af den sekundære struktur, betydeligt uden at skulle øge forespørgselstiden.

"Før dette arbejde havde ingen indset, at du kunne komprimere datastrukturen yderligere ved at flytte information rundt," sagde Pagh. "Det var den store indsigt i Bender-avisen."

Forfatterne viste, at deres opfindelse etablerede en ny øvre grænse for de mest effektive hashtabeller, hvilket betyder, at det var den bedste datastruktur, der hidtil var udtænkt med hensyn til både tids- og rumeffektivitet. Men muligheden forblev, at en anden kunne gøre det endnu bedre.

Forbundet til at lykkes

Det næste år, et hold ledet af Huacheng Yu, en datalog ved Princeton University, forsøgte at forbedre Bender-holdets hash-tabel. "Vi arbejdede virkelig hårdt og kunne ikke gøre det," sagde Renfei Zhou, studerende ved Tsinghua University i Beijing og medlem af Yus team. "Det var da vi havde mistanke om, at deres øvre grænse [også] var en nedre grænse" - det bedste, der overhovedet kan opnås. "Når den øvre grænse er lig med den nedre grænse, er spillet slut, og du har dit svar." Uanset hvor klog du er, kan ingen hash-tabel gøre det bedre.

Yus team brugte en ny strategi for at finde ud af, om den anelse var korrekt ved at beregne en nedre grænse ud fra de første principper. For det første ræsonnerede de, at for at udføre en indsættelse eller en sletning, skal en hash-tabel - eller i virkeligheden enhver datastruktur - have adgang til computerens hukommelse et antal gange. Hvis de kunne finde ud af det mindste antal gange, der kræves til en pladseffektiv hash-tabel, kunne de gange det med den tid, der kræves pr. adgang (en konstant), hvilket giver dem en nedre grænse for kørselstiden.

Men hvis de ikke vidste noget om hash-tabellen (bortset fra at den var pladsbesparende), hvordan kunne forskerne finde ud af det mindste antal gange, der kræves for at få adgang til hukommelsen? De udledte det udelukkende fra teori ved at bruge et tilsyneladende ikke-relateret felt kaldet teorien om kommunikationskompleksitet, som studerer, hvor mange bits der kræves for at formidle information mellem to parter. Til sidst lykkedes det for holdet: De fandt ud af, hvor mange gange en datastruktur skal få adgang til sin hukommelse pr. operation.

Dette var deres vigtigste præstation. De var derefter i stand til at etablere en nedre grænse for køretiden for enhver pladseffektiv hash-tabel. Og de så, at det matchede Bender hashtabellen nøjagtigt. "Vi troede [først] det kunne forbedres," sagde Zhou. "Det viste sig, at vi tog fejl." Det betød til gengæld, at Petersons problem endelig var blevet løst.

Udover at besvare det årtier gamle spørgsmål, sagde Kuszmaul, er det forbløffende ved Yu-beviset dets almindelighed. "Deres nedre grænse gælder for alle mulige datastrukturer, inklusive dem, der ikke er opfundet endnu." Det betyder, at ingen metode til datalagring nogensinde kan slå Bender hash-tabellen med hensyn til hukommelse og hastighed.

Hashing ind i fremtiden

På trods af den nye hash-tabels hidtil usete effektivitet, er der sandsynligvis ingen, der vil prøve at bygge den på et tidspunkt. Det er simpelthen for kompliceret at konstruere. "En algoritme, der er hurtig i teorien, er ikke nødvendigvis hurtig i praksis," sagde Zhou.

Det er ikke usædvanligt, at sådanne kløfter mellem teori og praksis varer ved i lang tid, sagde Kuszmaul, fordi teoretikere har en tendens til at ignorere konstante faktorer. Den tid, det tager at udføre en operation, ganges typisk med et tal, en konstant, hvis nøjagtige værdi kan være uvæsentlig fra et teoretisk synspunkt. "Men i praksis betyder konstanter virkelig noget," sagde han. "I den virkelige verden er en faktor 10 en ende på spillet."

Faktiske hashtabeller forbedres stadig på materielle måder, selvom de er langt fra det teoretiske ideal. For eksempel kaldes en ny hash-tabel IsbjergHT, bygget af Bender, Kuszmaul og andre, er langt bedre end sine forgængere. Ifølge Kuszmaul er det dobbelt så hurtigt som det mest pladseffektive hashbord, der findes i dag, og det bruger tre gange mindre plads end det hurtigste hashbord.

Mitzenmacher håber, at 2023-resultatet snart kan give en anden form for fordel: "Når du får en ny nedre grænse - især en, der involverer nogle nye teknikker - er der altid håb om, at du kan bruge dem ... til relaterede problemer."

Der er også den intellektuelle tilfredsstillelse, der kommer af at vide, at du har løst et vanskeligt og langvarigt problem, sagde datalogen Piotr Indyk fra Massachusetts Institute of Technology. "Når du er sikker på, at visse datastrukturer ikke kan forbedres, kan det hjælpe med at fokusere forskningsindsatsen." Endelig kan dataforskere vende opmærksomheden væk fra Petersons udfordring og fokusere på nye problemer inden for teoretisk datalogi, som der ikke er mangel på.