Teadlased leiavad andmete salvestamise ja aja optimaalse tasakaalu | Ajakiri Quanta

Umbes 70 aastat tagasi muutis IBMi insener Hans Peter Luhn vaikselt arvutiteaduse kurssi. Luhnil oli juba mitu patenti, sealhulgas üks seadmele, millega saab mõõta riide niitide arvu, ja teine ​​​​juhendile, mis määras kindlaks, milliseid jooke saate oma köögis olevatest koostisosadest valmistada. Kuid 1953. aasta IBM-i sisepaberis pakkus ta välja uue teabe salvestamise ja hankimise tehnika, mis on nüüd sisse ehitatud peaaegu kõikidesse arvutussüsteemidesse: räsitabeli.

Räsitabelid on suur andmestruktuuride klass. Need pakuvad eriti mugavat meetodit massiivsetes andmebaasides teabele juurdepääsuks ja teabe muutmiseks. Kuid selle tehnoloogiaga kaasneb vältimatu kompromiss.

Aastal 1957 paber avaldatakse IBMi teadus- ja arendustegevuse ajakiri, W. Wesley Peterson tuvastas räsitabelite peamise tehnilise väljakutse: need peavad olema kiired, mis tähendab, et nad saavad vajaliku teabe kiiresti kätte. Kuid need peavad olema ka kompaktsed, kasutades võimalikult vähe mälu. Need kaks eesmärki on põhimõtteliselt vastuolus. Juurdepääsu andmebaasile ja selle muutmist saab teha kiiremini, kui räsitabelis on rohkem mälu; ja toimingud muutuvad aeglasemaks räsitabelites, mis kasutavad vähem ruumi. Alates sellest, kui Peterson selle väljakutse esitas, on teadlased püüdnud leida parimat tasakaalu aja ja ruumi vahel.

Arvutiteadlased on nüüd matemaatiliselt tõestanud, et nad on leidnud optimaalse kompromissi. Lahendus tuli a paar hiljutistest dokumendid mis üksteist täiendasid. "Need dokumendid lahendavad kaua kestnud lahtise küsimuse parimate võimalike aegruumi kompromisside kohta, andes sügavalt üllatavaid tulemusi, millel on minu arvates märkimisväärne mõju veel paljudeks aastateks," ütles ta. Michael Mitzenmacher, Harvardi ülikooli arvutiteadlane, kes ei osalenud kummaski uuringus.

"Ma ütleksin kindlasti, et see on suur asi," lisas Rasmus Pagh, Kopenhaageni ülikooli arvutiteadlane. "Paljud inimesed on selle probleemi kallal töötanud, püüdes näha, kui palju saate ruumi kokku hoida, tehes samal ajal ka ajasäästlikke toiminguid. See on see, mida ma oleksin tahtnud lahendada."

Sellest räsi tegemine

Räsitabelid on tänapäeval ühed vanimad, lihtsamad, kiiremad ja enim kasutatavad andmestruktuurid. Need on loodud kolme põhitoimingu tegemiseks: sisestused, mis lisavad andmebaasi uusi üksusi; päringud, mis pääsevad üksuse juurde või kontrollivad, kas see on olemas; ja kustutamised. Räsitabel võib olla lühiajaline – eksisteerida vaid seni, kuni konkreetne programm töötab – või olla teie arvuti operatsioonisüsteemi püsiv osa. Veebibrauseris, nagu Chrome või Safari, võib olla mitu sisseehitatud räsitabelit, mis on mõeldud erinevat tüüpi andmete jälgimiseks.

Räsitabelis olevad kirjed salvestatakse paaridena, kusjuures üksus – teave ise – on ühendatud võtmega, mis teavet tuvastab. Ühendage võti räsitabeli päringualgoritmiga ja see viib teid otse üksuse juurde. See ei pruugi kõlada nii erakordselt, kuid tohutute andmebaaside jaoks võib see olla suurepärane aja kokkuhoid.

Äärmiselt lihtsustatud näite võtmiseks vaadake Oxfordi inglise keele sõnaraamatut, milles on definitsioonid enam kui 600,000 XNUMX sõna jaoks. Kui digitaalne väljaanne tugineb räsitabelile, saate lihtsalt kasutada antud sõna võtmena ja jätkata otse definitsiooniga. Ilma räsitabelita tugineks sõnastik tõenäoliselt palju aeglasemale otsingumehhanismile, kasutades eemaldamisprotsessi, et lõpuks soovitud määratlusele läheneda. Ja kuigi räsitabel suudab konstantse aja jooksul (tavaliselt murdosa sekundist) leida mis tahes sõna, võib muude meetodite otsinguaeg sõnaraamatu sõnade arvu suurenedes pikeneda. Räsitabel pakub ka veel ühe eelise: see võib hoida sõnastikku dünaamilisena, muutes uute sõnade sisestamise ja aegunud sõnade kustutamise lihtsaks.

Teadlased on aastakümneid ehitanud räsitabeleid, mis püüavad maksimeerida kiirust ja minimeerida mälu. 20. sajandil kippusid lahendused pakkuma märkimisväärset kasu ainult ühes aspektis, ajas või ruumis. Seejärel 2003. aastal teadlased näitas et teoreetiliselt oli võimalik teha suur efektiivsushüpe nii ajas kui ruumis üheaegselt. Kuid teadlastel kuluks veel kaks aastakümmet, et välja selgitada nende kahe ideaalne tasakaal.

Andmete segamine

Esimene suur samm selle eesmärgi poole tehti 2022. aastal a suur arvutiteaduse konverents Roomas. Seal pakkus meeskond välja uute funktsioonidega räsitabeli, mis võiks pakkuda parimat seni väljamõeldud aja- ja ruumitõhususe kombinatsiooni. Töö esimene autor (loetletud tähestikulises järjekorras) oli Michael Bender Stony Brooki ülikoolist, nii et seda nimetatakse tavaliselt Benderiks jt. räsi tabel. Kuigi meeskond ei püüdnud luua toimivat räsitabelit, tõestasid nad, et seda saab põhimõtteliselt koostada nende kirjeldatud funktsioonidega.

Nende väljamõeldud räsitabeli hindamiseks koostas rühm kompromisskõvera - graafiku, mis kujutab ühele teljele toimingu (sisestamise või kustutamise) aega ja teisele teljele mälu poolt hõivatud ruumi. Kuid see graafik määratleb ruumi erilisel viisil: nende ülesehituse tõttu vajavad räsitabelid rohkem mälu kui ainult miinimum, mis on vajalik antud üksuste komplekti salvestamiseks. Arvutiteadlased nimetavad seda lisaruumi "raisatud bittideks", kuigi need pole tegelikult raisatud ja on teatud määral vajalikud. Kompromissikõvera ruumitelg mõõdab raisatud bittide arvu võtme kohta.

Kompromissikõverat analüüsides saavad teadlased välja selgitada kiireima võimaliku aja räsitabeli jaoks, mis kasutab teatud ruumi. Samuti saavad nad küsimuse ümber pöörata, et selgitada välja väikseim võimalik ruum antud tööaja jaoks. Tavaliselt toob väike muutus ühes muutujas kaasa väikese muutuse teises, ütles William Kuszmaul, Harvardi teoreetiline arvutiteadlane ja 2022. aasta artikli kaasautor. "Kui kahekordistate aega, vähendate võib-olla poole võrra raisatud bittide arvu klahvi kohta."

Kuid see ei kehti nende kavandatud räsitabeli kohta. "Kui suurendate aega veidi, vähenevad raisatud bitid võtme kohta eksponentsiaalselt, " ütles Kuszmaul. Kompromissikõver oli nii järsk, et see oli sõna otseses mõttes edetabelitest väljas.

Meeskond koostas oma räsitabeli kahes osas. Neil oli esmane andmestruktuur, milles üksused salvestatakse ilma raisatud bittideta, ja sekundaarne andmestruktuur, mis aitab päringupäringul otsida otsitava üksuse. Kuigi rühm ei leiutanud sekundaarse andmestruktuuri mõistet, tegid nad siiski olulise avastuse, mis tegi nende ülitõhusa räsitabeli võimalikuks: struktuuri üldine mälutõhusus sõltub sellest, kuidas primaarstruktuur oma salvestatud üksusi korraldab.

Põhiidee seisneb selles, et igal põhistruktuuri elemendil on eelistatud ladustamiskohad – parim asukoht, paremuselt teine, paremuselt kolmas ja nii edasi. Kui üksus on oma parimas kohas, kinnitatakse sellele number 1 ja see number salvestatakse teiseses andmestruktuuris. Vastuseks päringule annab sekundaarstruktuur vaid numbri 1, mis määrab üksuse täpse asukoha põhistruktuuris.

Kui üksus on paremuselt 100. kohal, lisab sekundaarne andmestruktuur numbri 100. Ja kuna süsteem kasutab kahendkoodi, esitab see arvu 100 kui 1100100. Arvu 1100100 salvestamiseks kulub muidugi rohkem mälu kui 1 — üksusele määratud number, kui see on parimas kohas. Sellised erinevused muutuvad märkimisväärseks, kui hoiate näiteks miljonit eset.

Nii mõistis meeskond, et kui nihutate pidevalt esmases andmestruktuuris olevaid üksusi nende eelistatumatesse asukohtadesse, saate sekundaarse struktuuri poolt tarbitavat mälu oluliselt vähendada, ilma et peaksite päringuaegu pikendama.

"Enne seda tööd ei olnud keegi aru saanud, et saate teabe ümberpaigutamise abil andmestruktuuri veelgi tihendada, " ütles Pagh. "See oli Benderi paberi suur ülevaade."

Autorid näitasid, et nende leiutis kehtestas kõige tõhusamate räsitabelite jaoks uue ülemise piiri, mis tähendab, et see oli parim andmestruktuur, mis seni välja töötatud nii aja- kui ruumitõhususe osas. Kuid säilis võimalus, et keegi teine ​​võib veelgi paremini hakkama saada.

Seotud edu saavutamiseks

Järgmisel aastal meeskond eesotsas Huacheng Yu, Princetoni ülikooli arvutiteadlane, püüdis parandada Benderi meeskonna räsitabelit. "Tegime kõvasti tööd ja ei saanud hakkama," ütles Renfei Zhou, Pekingi Tsinghua ülikooli üliõpilane ja Yu meeskonna liige. "See oli siis, kui me kahtlustasime, et nende ülemine piir oli [ka] alumine piir" - parim, mida võimalik saavutada. "Kui ülemine piir on võrdne alumise piiriga, on mäng läbi ja teil on vastus." Ükskõik kui tark sa ka poleks, ükski räsitabel ei suuda midagi paremini teha.

Yu meeskond kasutas uudset strateegiat, et välja selgitada, kas see aimdus oli õige, arvutades esimeste põhimõtete põhjal alampiiri. Esiteks põhjendasid nad, et sisestamise või kustutamise teostamiseks peab räsitabel – või tegelikult mis tahes andmestruktuur – pääsema mitu korda juurde arvuti mälule. Kui nad suudaksid välja selgitada ruumisäästliku räsitabeli jaoks vajaliku minimaalse kordade arvu, saaksid nad selle korrutada juurdepääsuks vajaliku ajaga (konstant), andes neile käitusaja alampiiri.

Aga kui nad ei teadnud räsitabelist midagi (välja arvatud see, et see oli ruumisäästlik), kuidas saaksid teadlased aru saada, kui palju kordi on vaja mälule juurdepääsuks? Nad tuletasid selle puhtalt teooriast, kasutades näiliselt mitteseotud valdkonda, mida nimetatakse kommunikatsiooni keerukuse teooriaks, mis uurib, mitu bitti on vaja teabe edastamiseks kahe osapoole vahel. Lõpuks õnnestus meeskonnal: nad leidsid, mitu korda peab andmestruktuur oma mälule juurde pääsema toimingu kohta.

See oli nende peamine saavutus. Seejärel suutsid nad määrata iga ruumisäästliku räsitabeli jaoks käitusaja alampiiri. Ja nad nägid, et see sobis täpselt Benderi räsitabeliga. "Arvasime [alguses], et seda saab parandada, " ütles Zhou. "Selgus, et me eksisime." See omakorda tähendas, et Petersoni probleem sai lõpuks lahenduse.

Lisaks aastakümnete vanusele küsimusele vastamisele ütles Kuszmaul, et Yu tõendi puhul on hämmastav selle üldistus. "Nende alumine piir kehtib kõigi võimalike andmestruktuuride, sealhulgas nende jaoks, mida pole veel leiutatud." See tähendab, et ükski andmete salvestamise meetod ei saa kunagi mälu ja kiiruse osas Benderi räsitabelit ületada.

Räsimine tulevikku

Hoolimata uue räsitabeli enneolematust tõhususest ei proovi keegi tõenäoliselt seda niipea ehitada. See on lihtsalt liiga keeruline ehitada. "Teoorias kiire algoritm ei pruugi olla praktikas kiire," ütles Zhou.

Kuszmaul ütles, et pole ebatavaline, et sellised lõhed teooria ja praktika vahel püsivad pikka aega, sest teoreetikud kipuvad konstantseid tegureid ignoreerima. Toimingu sooritamiseks kuluv aeg korrutatakse tavaliselt arvuga, mõne konstandiga, mille täpne väärtus võib teoreetilisest seisukohast olla ebaoluline. "Kuid praktikas on konstandid tõesti olulised," ütles ta. "Päris maailmas on 10-kordne tegur mängu lõpp."

Tegelikud räsitabelid paranevad endiselt materiaalselt, isegi kui need jäävad teoreetilisest ideaalist kaugele alla. Näiteks uus räsitabel nimega JäämägiHT, mille ehitasid Bender, Kuszmaul ja teised, on palju parem kui tema eelkäijad. Kuszmauli sõnul on see kaks korda kiirem kui tänapäeval saadaolev kõige ruumisäästlikum räsilaud ja see kasutab kolm korda vähem ruumi kui kiireim räsilaud.

Mitzenmacher loodab, et 2023. aasta tulemus võib peagi anda teist tüüpi kasu: "Iga kord, kui saate uue alampiiri – eriti sellise, mis hõlmab uusi tehnikaid –, on alati lootust, et saate neid kasutada… seotud probleemide lahendamiseks."

Arvutiteadlane ütles ka intellektuaalset rahulolu teadmisest, et olete lahendanud keerulise ja pikaajalise probleemi. Piotr Indyk Massachusettsi Tehnoloogiainstituudist. "Kui olete kindel, et teatud andmestruktuure ei saa parandada, võib see aidata uurimistööd keskenduda." Lõpuks saavad andmeuurijad pöörata tähelepanu Petersoni väljakutselt kõrvale ja keskenduda uutele probleemidele teoreetilises arvutiteaduses, millest puudust pole.