Forskere finner optimal balanse mellom datalagring og tid | Quanta Magazine

For rundt 70 år siden endret en ingeniør ved IBM ved navn Hans Peter Luhn stille kursen for informatikk. Luhn hadde allerede flere patenter, inkludert en for en enhet som kunne måle en kluts trådantall og en annen for en guide som bestemte hvilke blandede drinker du kunne lage av ingrediensene på kjøkkenet ditt. Men i en intern IBM-artikkel fra 1953 foreslo han en ny teknikk for å lagre og hente informasjon som nå er innebygd i omtrent alle beregningssystemer: hashtabellen.

Hash-tabeller er en hovedklasse av datastrukturer. De tilbyr en spesielt praktisk metode for å få tilgang til og endre informasjon i massive databaser. Men denne teknologien kommer med en uunngåelig avveining.

I en 1957 papir publisert i IBM Journal of Research and Development, W. Wesley Peterson identifiserte den viktigste tekniske utfordringen som hashtabeller utgjør: De må være raske, noe som betyr at de raskt kan hente den nødvendige informasjonen. Men de må også være kompakte og bruke så lite minne som mulig. Disse tvillingmålene er fundamentalt motstridende. Å få tilgang til og endre en database kan gjøres raskere når hashtabellen har mer minne; og operasjoner blir tregere i hashtabeller som bruker mindre plass. Helt siden Peterson la ut denne utfordringen, har forskere forsøkt å finne den beste balansen mellom tid og rom.

Dataforskere har nå matematisk bevist at de har funnet den optimale avveiningen. Løsningen kom fra en par av nyere papirer som utfylte hverandre. "Disse papirene løser det langvarige åpne spørsmålet om best mulig rom-tid-avveininger, og gir dypt overraskende resultater som jeg forventer vil ha en betydelig innvirkning i mange år fremover," sa Michael Mitzenmacher, en informatiker ved Harvard University som ikke var involvert i noen av studiene.

"Jeg vil definitivt si at det er en stor sak," la til Rasmus Pagh, en informatiker ved Københavns Universitet. "Mange mennesker har jobbet med dette problemet, og prøvd å se hvor mye du kan presse plass, samtidig som du har tidseffektiv drift. Dette er den jeg ville elsket å løse.»

Å lage en hasj av det

Hash-tabeller er blant de eldste, enkleste, raskeste og mest brukte datastrukturene i dag. De er designet for å utføre tre grunnleggende operasjoner: innsettinger, som legger til nye elementer til databasen; spørringer, som får tilgang til et element eller sjekker om det eksisterer; og slettinger. En hashtabell kan være flyktig - eksisterer bare så lenge et bestemt program kjører - eller den kan være en permanent del av datamaskinens operativsystem. En nettleser som Chrome eller Safari kan ha flere innebygde hashtabeller beregnet på å holde styr på forskjellige typer data.

Oppføringer i en hash-tabell lagres som par, med elementet – selve informasjonen – koblet til en nøkkel som identifiserer informasjonen. Plugg en nøkkel inn i en hash-tabells spørringsalgoritme, og den tar deg direkte til elementet. Dette høres kanskje ikke så ekstraordinært ut, men for enorme databaser kan det være en stor tidsbesparelse.

For å ta et ekstremt forenklet eksempel, vurder Oxford English Dictionary, som har definisjoner for mer enn 600,000 XNUMX ord. Hvis en digital utgave er avhengig av en hash-tabell, kan du ganske enkelt bruke et gitt ord som nøkkel og gå rett til definisjonen. Uten en hash-tabell, ville ordboken sannsynligvis stole på en mye langsommere søkemekanisme, ved å bruke en elimineringsprosess for til slutt å konvergere til den forespurte definisjonen. Og mens en hash-tabell kan finne et hvilket som helst ord i en konstant tidsperiode (vanligvis en liten brøkdel av et sekund), kan søketiden for andre metoder gå opp etter hvert som antall ord i ordboken øker. En hash-tabell tilbyr også en annen fordel: Den kan holde ordboken dynamisk, noe som gjør det enkelt å sette inn nye ord og slette utdaterte.

Forskere har brukt flere tiår på å bygge hasjtabeller som prøver å maksimere hastigheten og minimere minnet. På 20-tallet hadde løsninger en tendens til å tilby betydelige gevinster i bare ett aspekt, tid eller rom. Så i 2003, forskere viste at det teoretisk var mulig å gjøre et stort effektivitetssprang i både tid og rom samtidig. Det ville imidlertid ta ytterligere to tiår for forskere å finne ut den ideelle balansen mellom de to.

Datashuffle

Det første store skrittet mot dette målet kom i 2022 kl stor informatikkkonferanse I Roma. Der foreslo et team en hash-tabell med nye funksjoner som kan levere den beste kombinasjonen av tids- og plasseffektivitet som til nå er unnfanget. Den første forfatteren av artikkelen (oppført alfabetisk) var Michael Bender fra Stony Brook University, så det blir ofte referert til som Bender et al. hasjtabell. Mens teamet ikke prøvde å bygge en fungerende hash-tabell, beviste de at den i prinsippet kunne konstrueres med funksjonene de beskrev.

For å evaluere hash-tabellen de kom opp med, produserte gruppen en avveiningskurve - en graf som plotter tiden per operasjon (innsetting eller sletting) på den ene aksen og plassen som er tatt opp av minnet på den andre. Men denne grafen definerer plass på en spesiell måte: På grunn av hvordan de er bygget, trenger hash-tabeller mer minne enn bare det minimum som kreves for å lagre et gitt sett med elementer. Dataforskere kaller denne ekstra plassen "bortkastede biter", selv om de egentlig ikke er bortkastet og til en viss grad er nødvendige. Romaksen på en avveiningskurve måler antall bortkastede biter per nøkkel.

Ved å analysere en avveiningskurve, kan forskere finne ut raskest mulig tid for en hashtabell som bruker en gitt mengde plass. De kan også snu spørsmålet rundt for å finne ut minst mulig plass for en gitt operasjonstid. Vanligvis vil en liten endring i en variabel føre til en liten endring i den andre, sa William Kuszmaul, en teoretisk informatiker ved Harvard og medforfatter av 2022-artikkelen. "Hvis du dobler tiden, vil du kanskje halvere antall bortkastede biter per nøkkel."

Men det er ikke tilfellet med hashtabellen de har designet. "Hvis du øker tiden med litt, reduseres de bortkastede bitene per nøkkel eksponentielt," sa Kuszmaul. Avveiningskurven var så bratt at den var bokstavelig talt utenfor listene.

Teamet bygde hasjbordet sitt i to deler. De hadde en primær datastruktur, der elementene lagres uten bortkastede biter i det hele tatt, og en sekundær datastruktur, som hjelper en spørringsforespørsel med å finne elementet den leter etter. Selv om gruppen ikke oppfant ideen om en sekundær datastruktur, gjorde de en avgjørende oppdagelse som gjorde deres hypereffektive hash-tabell mulig: Strukturens samlede minneeffektivitet avhenger av hvordan den primære strukturen ordner sine lagrede elementer.

Den grunnleggende ideen er at hvert element i den primære strukturen har foretrukne lagringsplasser - en beste plassering, en nest beste, en tredje beste og så videre. Hvis en vare er på sitt beste sted, er nummer 1 festet til den, og dette nummeret lagres i den sekundære datastrukturen. Som svar på en spørring gir den sekundære strukturen bare tallet 1, som staver varens eksakte plassering i primærstrukturen.

Hvis elementet er på sin 100. beste plass, legger den sekundære datastrukturen til tallet 100. Og fordi systemet bruker binær, representerer det tallet 100 som 1100100. Det krever selvfølgelig mer minne for å lagre tallet 1100100 enn 1 — nummeret som er tildelt en vare når den er på det beste stedet. Slike forskjeller blir betydelige hvis du oppbevarer for eksempel en million gjenstander.

Så teamet innså at hvis du kontinuerlig flytter elementer i den primære datastrukturen til deres mer foretrukne plasseringer, kan du redusere minnet som forbrukes av den sekundære strukturen betydelig uten å måtte øke spørringstiden.

"Før dette arbeidet hadde ingen skjønt at du kunne komprimere datastrukturen ytterligere ved å flytte informasjon rundt," sa Pagh. "Det var den store innsikten til Bender-avisen."

Forfatterne viste at oppfinnelsen deres etablerte en ny øvre grense for de mest effektive hashtabellene, noe som betyr at det var den beste datastrukturen som ennå er utviklet når det gjelder både tids- og romeffektivitet. Men muligheten forble for at noen andre kunne gjøre det enda bedre.

Bundet til å lykkes

Det neste året, et team ledet av Huacheng Yu, en informatiker ved Princeton University, prøvde å forbedre Bender-teamets hashtabell. "Vi jobbet veldig hardt og klarte det ikke," sa Renfei Zhou, en student ved Tsinghua University i Beijing og medlem av Yus team. "Det var da vi mistenkte at deres øvre grense [også] var en nedre grense" - det beste som muligens kan oppnås. "Når den øvre grensen er lik den nedre grensen, er spillet over, og du har svaret ditt." Uansett hvor smart du er, kan ingen hashtabell gjøre noe bedre.

Yus team brukte en ny strategi for å finne ut om den anelsen var riktig ved å beregne en nedre grense fra de første prinsippene. Først begrunnet de at for å utføre en innsetting eller en sletting, må en hash-tabell - eller egentlig en hvilken som helst datastruktur - få tilgang til datamaskinens minne et antall ganger. Hvis de kunne finne ut minimum antall ganger nødvendig for en plasseffektiv hash-tabell, kunne de multiplisere det med tiden som kreves per tilgang (en konstant), og gi dem en nedre grense for kjøretiden.

Men hvis de ikke visste noe om hash-tabellen (bortsett fra at den var plasseffektiv), hvordan kunne forskerne finne ut det minste antallet ganger som kreves for å få tilgang til minnet? De hentet det utelukkende fra teori, ved å bruke et tilsynelatende ikke-relatert felt kalt teorien om kommunikasjonskompleksitet, som studerer hvor mange biter som kreves for å formidle informasjon mellom to parter. Til slutt lyktes teamet: De fant ut hvor mange ganger en datastruktur må få tilgang til minnet per operasjon.

Dette var deres viktigste prestasjon. De var da i stand til å etablere en nedre grense for kjøretiden for enhver plasseffektiv hash-tabell. Og de så at det stemte nøyaktig med Bender-hash-tabellen. "Vi trodde [først] det kunne forbedres," sa Zhou. – Det viste seg at vi tok feil. Det betydde igjen at Petersons problem endelig var løst.

Foruten å svare på det flere tiår gamle spørsmålet, sa Kuszmaul, er det utrolige med Yu-beviset dets generelle. "Deres nedre grense gjelder for alle mulige datastrukturer, inkludert de som ikke er oppfunnet ennå." Det betyr at ingen metode for datalagring noensinne kan slå Bender-hash-tabellen når det gjelder minne og hastighet.

Hashing inn i fremtiden

Til tross for den nye hash-tabellens enestående effektivitet, er det sannsynligvis ingen som vil prøve å bygge den når som helst snart. Det er rett og slett for komplisert å konstruere. "En algoritme som er rask i teorien er ikke nødvendigvis rask i praksis," sa Zhou.

Det er ikke uvanlig at slike gap mellom teori og praksis vedvarer i lang tid, sa Kuszmaul, fordi teoretikere har en tendens til å ignorere konstante faktorer. Tiden det tar å utføre en operasjon multipliseres vanligvis med et tall, en konstant hvis nøyaktige verdi kan være uvesentlig fra et teoretisk synspunkt. "Men i praksis betyr konstanter virkelig," sa han. "I den virkelige verden er en faktor på 10 en slutt på spillet."

Faktiske hashtabeller forbedres fortsatt på materielle måter, selv om de kommer langt fra det teoretiske idealet. For eksempel kalles en ny hash-tabell IsfjellHT, bygget av Bender, Kuszmaul og andre, er langt bedre enn sine forgjengere. Ifølge Kuszmaul er det dobbelt så raskt som det mest plasseffektive hashbordet som er tilgjengelig i dag, og det bruker tre ganger mindre plass enn det raskeste hashbordet.

Mitzenmacher håper at 2023-resultatet snart kan gi en annen type fordel: "Når du får en ny nedre grense - spesielt en som involverer noen nye teknikker - er det alltid håp om at du kan bruke dem ... for relaterte problemer."

Det er også den intellektuelle tilfredsstillelsen som kommer av å vite at du har løst et vanskelig og langvarig problem, sa informatikeren Piotr Indyk ved Massachusetts Institute of Technology. "Når du er sikker på at visse datastrukturer ikke kan forbedres, kan det bidra til å fokusere forskningsinnsatsen." Endelig kan dataforskere vende oppmerksomheten bort fra Petersons utfordring og fokusere på nye problemer innen teoretisk informatikk, som det ikke er mangel på.