Forskare hittar optimal balans mellan datalagring och tid | Quanta Magazine

För cirka 70 år sedan ändrade en ingenjör vid IBM vid namn Hans Peter Luhn tyst kursen inom datavetenskap. Luhn hade redan flera patent, inklusive ett för en apparat som kunde mäta en trasa trådantal och en annan för en guide som bestämde vilka blandade drycker du kunde göra av ingredienserna i ditt kök. Men i en intern IBM-tidning från 1953 föreslog han en ny teknik för att lagra och hämta information som nu är inbyggd i nästan alla beräkningssystem: hashtabellen.

Hash-tabeller är en stor klass av datastrukturer. De erbjuder en särskilt bekväm metod för att komma åt och ändra information i massiva databaser. Men denna teknik kommer med en oundviklig kompromiss.

I en 1957 papper offentliggjordes i IBM Journal of Research and Development, W. Wesley Peterson identifierade den största tekniska utmaningen som hashtabeller utgör: De måste vara snabba, vilket innebär att de snabbt kan hämta nödvändig information. Men de måste också vara kompakta och använda så lite minne som möjligt. Dessa dubbla mål är i grunden motstridiga. Att komma åt och ändra en databas kan göras snabbare när hashtabellen har mer minne; och operationerna blir långsammare i hashtabeller som använder mindre utrymme. Ända sedan Peterson lade ut denna utmaning har forskare försökt hitta den bästa balansen mellan tid och rum.

Datavetare har nu matematiskt bevisat att de har hittat den optimala avvägningen. Lösningen kom från en par av de senaste papper som kompletterade varandra. "Dessa uppsatser löser den långvariga öppna frågan om bästa möjliga avvägningar mellan rum och tid, och ger djupt överraskande resultat som jag förväntar mig kommer att ha en betydande inverkan under många år framöver," sa Michael Mitzenmacher, en datavetare vid Harvard University som inte var involverad i någon av studierna.

"Jag skulle definitivt säga att det är en stor sak", tillade jag Rasmus Pagh, en datavetare vid Köpenhamns universitet. "Många människor har arbetat med det här problemet och försökt se hur mycket man kan pressa utrymme samtidigt som man har en tidseffektiv verksamhet. Det här är den jag skulle ha älskat att lösa.”

Gör en hash av det

Hash-tabeller är bland de äldsta, enklaste, snabbaste och mest använda datastrukturerna idag. De är designade för att utföra tre grundläggande operationer: infogning, som lägger till nya objekt till databasen; frågor, som kommer åt ett objekt eller kontrollerar om det finns; och strykningar. En hashtabell kan vara tillfällig – existerar bara så länge ett visst program körs – eller så kan den vara en permanent del av din dators operativsystem. En webbläsare som Chrome eller Safari kan ha flera inbyggda hashtabeller avsedda att hålla reda på olika typer av data.

Poster i en hashtabell lagras som par, med objektet – själva informationen – kopplat till en nyckel som identifierar informationen. Koppla in en nyckel i en hashtabells frågealgoritm, och den tar dig direkt till objektet. Detta kanske inte låter så extraordinärt, men för enorma databaser kan det vara en stor tidsbesparing.

För att ta ett extremt förenklat exempel, överväg Oxford English Dictionary, som har definitioner för mer än 600,000 XNUMX ord. Om en digital utgåva förlitar sig på en hashtabell kan du helt enkelt använda ett givet ord som nyckel och gå direkt till definitionen. Utan en hashtabell skulle ordboken sannolikt förlita sig på en mycket långsammare sökmekanism, med hjälp av en elimineringsprocess för att så småningom konvergera till den begärda definitionen. Och medan en hashtabell kan hitta vilket ord som helst under en konstant tid (vanligtvis en liten bråkdel av en sekund), kan söktiden för andra metoder gå upp när antalet ord i ordboken ökar. En hashtabell erbjuder också en annan fördel: Den kan hålla ordboken dynamisk, vilket gör det enkelt att infoga nya ord och ta bort föråldrade.

Forskare har ägnat decennier åt att bygga hashtabeller som försöker maximera hastigheten och minimera minnet. På 20-talet tenderade lösningar att erbjuda betydande vinster inom bara en aspekt, tid eller rum. Sedan 2003, forskare visade att det teoretiskt var möjligt att göra ett stort effektivitetssprång i både tid och rum samtidigt. Det skulle dock ta ytterligare två decennier för forskare att ta reda på den ideala balansen mellan de två.

Datablandningen

Det första stora steget mot det målet kom 2022 kl stora datavetenskapskonferensen i Rom. Där föreslog ett team en hashtabell med nya funktioner som skulle kunna leverera den bästa kombinationen av tids- och utrymmeseffektivitet som hittills kommit till. Den första författaren till artikeln (listad i alfabetisk ordning) var Michael Bender från Stony Brook University, så det brukar kallas Bender et al. hashtabell. Även om teamet inte försökte bygga en fungerande hashtabell, visade de att den i princip kunde konstrueras med de funktioner de beskrev.

För att utvärdera hashtabellen de kom fram till tog gruppen fram en avvägningskurva - en graf som plottar tiden per operation (infogning eller radering) på en axel och utrymmet som tas upp av minnet på den andra. Men den här grafen definierar utrymmet på ett speciellt sätt: På grund av hur de är byggda behöver hashtabeller mer minne än bara det absoluta minimum som krävs för att lagra en given uppsättning objekt. Datavetare kallar detta extra utrymme för "bortkastade bitar", även om de egentligen inte är bortkastade och i viss mån är nödvändiga. Rymdaxeln på en avvägningskurva mäter antalet bortkastade bitar per nyckel.

Genom att analysera en avvägningskurva kan forskare räkna ut den snabbaste möjliga tiden för en hashtabell som använder en viss mängd utrymme. De kan också vända på frågan för att räkna ut minsta möjliga utrymme för en given operationstid. Vanligtvis kommer en liten förändring i en variabel att leda till en liten förändring i den andra, sa William Kuszmaul, en teoretisk datavetare vid Harvard och medförfattare till 2022-uppsatsen. "Om du fördubblar tiden kanske du halverar antalet bortkastade bitar per nyckel."

Men så är det inte med hashtabellen de designat. "Om du ökar tiden med lite, minskar de bortkastade bitarna per nyckel exponentiellt," sa Kuszmaul. Avvägningskurvan var så brant att den var bokstavligen utanför listorna.

Teamet byggde sitt hashbord i två delar. De hade en primär datastruktur, där objekten lagras utan några bortkastade bitar alls, och en sekundär datastruktur, som hjälper en frågeförfrågan att hitta objektet den letar efter. Även om gruppen inte uppfann begreppet en sekundär datastruktur, gjorde de en avgörande upptäckt som möjliggjorde deras hypereffektiva hashtabell: Strukturens totala minneseffektivitet beror på hur den primära strukturen ordnar sina lagrade objekt.

Grundidén är att varje föremål i den primära strukturen har föredragna lagringsplatser - en bästa plats, en näst bästa, en tredje bästa och så vidare. Om ett objekt är på sin bästa plats, fästs siffran 1 på den, och det numret lagras i den sekundära datastrukturen. Som svar på en fråga ger den sekundära strukturen bara siffran 1, vilket anger objektets exakta plats i den primära strukturen.

Om objektet är på sin 100:e bästa plats, bifogar den sekundära datastrukturen siffran 100. Och eftersom systemet använder binärt representerar det talet 100 som 1100100. Det krävs naturligtvis mer minne för att lagra numret 1100100 än 1 — numret som tilldelas ett föremål när det är på den bästa platsen. Sådana skillnader blir betydande om du förvarar, säg, en miljon föremål.

Så teamet insåg att om du kontinuerligt flyttar objekt i den primära datastrukturen till deras mer föredragna platser, kan du avsevärt minska minnet som förbrukas av den sekundära strukturen utan att behöva öka frågetiderna.

"Innan detta arbete hade ingen insett att du kunde komprimera datastrukturen ytterligare genom att flytta runt information," sa Pagh. "Det var den stora insikten i Bender-tidningen."

Författarna visade att deras uppfinning fastställde en ny övre gräns för de mest effektiva hashtabellerna, vilket betyder att det var den bästa datastrukturen som hittills utarbetats vad gäller både tids- och rumseffektivitet. Men möjligheten kvarstod att någon annan kunde göra det ännu bättre.

Bundna att lyckas

Nästa år, ett team ledd av Huacheng Yu, en datavetare vid Princeton University, försökte förbättra Bender-teamets hashtabell. "Vi jobbade riktigt hårt och kunde inte göra det," sa Renfei Zhou, student vid Tsinghua University i Peking och medlem i Yus team. "Det var då vi misstänkte att deras övre gräns [också] var en nedre gräns" - det bästa som möjligen kan uppnås. "När den övre gränsen är lika med den nedre gränsen är spelet över och du har ditt svar." Oavsett hur smart du är kan inget hashbord göra bättre.

Yus team använde en ny strategi för att ta reda på om den aningen var korrekt genom att beräkna en nedre gräns utifrån de första principerna. Först resonerade de att för att utföra en infogning eller en radering måste en hashtabell – eller egentligen vilken datastruktur som helst – komma åt datorns minne ett antal gånger. Om de kunde räkna ut det minsta antalet gånger som behövs för en utrymmeseffektiv hashtabell, skulle de kunna multiplicera det med tiden som krävs per åtkomst (en konstant), vilket ger dem en lägre gräns för körtiden.

Men om de inte visste något om hashtabellen (förutom att den var utrymmeseffektiv), hur kunde forskarna räkna ut det minsta antal gånger som krävs för att komma åt minnet? De härledde det enbart från teorin, med hjälp av ett till synes orelaterade fält som kallas teorin om kommunikationskomplexitet, som studerar hur många bitar som krävs för att förmedla information mellan två parter. Så småningom lyckades teamet: De räknade ut hur många gånger en datastruktur måste komma åt sitt minne per operation.

Detta var deras viktigaste prestation. De kunde sedan fastställa en nedre gräns för körtiden för alla utrymmeseffektiva hashtabeller. Och de såg att det matchade Benders hashtabell exakt. "Vi trodde [först] att det kunde förbättras," sa Zhou. – Det visade sig att vi hade fel. Det innebar i sin tur att Petersons problem äntligen var löst.

Förutom att svara på den decennier gamla frågan, sa Kuszmaul, är det fantastiska med Yu-beviset dess generella karaktär. "Deras nedre gräns gäller alla möjliga datastrukturer, inklusive de som inte har uppfunnits ännu." Det betyder att ingen metod för datalagring någonsin kan slå Bender-hashtabellen när det gäller minne och hastighet.

Hashing in i framtiden

Trots den nya hashtabellens oöverträffade effektivitet är det troligt att ingen kommer att försöka bygga den när som helst snart. Det är bara för komplicerat att konstruera. "En algoritm som är snabb i teorin är inte nödvändigtvis snabb i praktiken," sa Zhou.

Det är inte ovanligt att sådana klyftor mellan teori och praktik kvarstår under en lång stund, sa Kuszmaul, eftersom teoretiker tenderar att ignorera konstanta faktorer. Den tid det tar att utföra en operation multipliceras vanligtvis med ett tal, en konstant vars exakta värde kan vara oväsentligt ur teoretisk synvinkel. "Men i praktiken spelar konstanter verkligen roll," sa han. "I den verkliga världen är en faktor 10 ett slut på spelet."

Faktiska hash-tabeller förbättras fortfarande på materiellt sätt, även om de är långt ifrån det teoretiska idealet. Till exempel kallas en ny hashtabell IsbergHT, byggd av Bender, Kuszmaul och andra, är mycket bättre än sina föregångare. Enligt Kuszmaul är det dubbelt så snabbt som det mest utrymmeseffektiva hashbordet som finns tillgängligt idag, och det använder tre gånger mindre utrymme än det snabbaste hashbordet.

Mitzenmacher hoppas att resultatet från 2023 snart kan ge en annan typ av fördel: "När du får en ny nedre gräns - speciellt en som involverar några nya tekniker - finns det alltid hopp om att du kan använda dem ... för relaterade problem."

Det finns också den intellektuella tillfredsställelsen som kommer av att veta att du har löst ett svårt och långvarigt problem, sa datavetaren Piotr Indyk vid Massachusetts Institute of Technology. "När du är säker på att vissa datastrukturer inte kan förbättras, kan det hjälpa till att fokusera forskningsansträngningen." Slutligen kan dataforskare vända uppmärksamheten från Petersons utmaning och fokusera på nya problem inom teoretisk datavetenskap, som det inte råder någon brist på.