Tiedemiehet löytävät optimaalisen tasapainon tietojen tallennuksen ja ajan välillä | Quanta-lehti

Noin 70 vuotta sitten IBM:n insinööri Hans Peter Luhn muutti hiljaa tietojenkäsittelytieteen kurssia. Luhnilla oli jo useita patentteja, mukaan lukien yksi laitteelle, joka pystyi mittaamaan kankaan lankamäärän, ja toinen oppaasta, joka määritti, mitä juomasekoituksia voit valmistaa keittiösi ainesosista. Mutta vuoden 1953 sisäisessä IBM-paperissa hän ehdotti uutta tekniikkaa tietojen tallentamiseen ja hakemiseen, joka on nyt rakennettu lähes kaikkiin laskentajärjestelmiin: hash-taulukkoa.

Hash-taulukot ovat suuri tietorakenteiden luokka. Ne tarjoavat erityisen kätevän tavan päästä käsiksi ja muuttaa valtavien tietokantojen tietoja. Mutta tämä tekniikka sisältää väistämättömän kompromissin.

In 1957 paperi julkaistu IBM:n tutkimus- ja kehityslehti, W. Wesley Peterson tunnisti hash-taulukoiden suurimman teknisen haasteen: Niiden on oltava nopeita, mikä tarkoittaa, että ne voivat nopeasti hakea tarvittavat tiedot. Mutta niiden on myös oltava kompakteja ja käytettävä mahdollisimman vähän muistia. Nämä kaksi tavoitetta ovat pohjimmiltaan ristiriidassa keskenään. Tietokannan käyttö ja muokkaaminen voidaan tehdä nopeammin, kun hash-taulukossa on enemmän muistia; ja toiminnot hidastuvat hajautustaulukoissa, jotka käyttävät vähemmän tilaa. Siitä lähtien, kun Peterson esitti tämän haasteen, tutkijat ovat yrittäneet löytää parhaan tasapainon ajan ja tilan välillä.

Tietojenkäsittelytieteilijät ovat nyt matemaattisesti osoittaneet löytäneensä optimaalisen kompromissin. Ratkaisu tuli a pari viimeisimmistä paperit jotka täydensivät toisiaan. "Nämä paperit ratkaisevat pitkään kestäneen avoimen kysymyksen parhaista mahdollisista aika-avaruuden kompromisseista ja tuottavat syvästi yllättäviä tuloksia, joilla odotan olevan merkittävä vaikutus monien vuosien ajan", sanoi Michael Mitzenmacher, tietojenkäsittelytieteilijä Harvardin yliopistosta, joka ei ollut mukana kummassakaan tutkimuksessa.

"Sanoisin ehdottomasti, että se on iso juttu", lisäsi Rasmus Pagh, tietojenkäsittelytieteilijä Kööpenhaminan yliopistosta. "Monet ihmiset ovat työskennelleet tämän ongelman parissa yrittäen nähdä, kuinka paljon tilaa voi puristaa, mutta samalla myös aikaa säästävää toimintaa. Tämän olisin halunnut ratkaista."

Hashin tekeminen siitä

Hash-taulukot ovat tämän päivän vanhimpia, yksinkertaisimpia, nopeimpia ja laajimmin käytettyjä tietorakenteita. Ne on suunniteltu suorittamaan kolme perustoimintoa: lisäykset, jotka lisäävät uusia kohteita tietokantaan; kyselyt, jotka käyttävät kohdetta tai tarkistavat, onko se olemassa; ja poistot. Hajautustaulukko voi olla lyhytaikainen – olemassa vain niin kauan kuin tietty ohjelma on käynnissä – tai se voi olla pysyvä osa tietokoneesi käyttöjärjestelmää. Verkkoselaimessa, kuten Chromessa tai Safarissa, voi olla useita sisäänrakennettuja hash-taulukoita, jotka on tarkoitettu seuraamaan erilaisia ​​​​tietoja.

Hajautustaulukon merkinnät tallennetaan pareina, jolloin kohde – itse tieto – on yhdistetty avaimeen, joka tunnistaa tiedot. Kytke avain hash-taulukon kyselyalgoritmiin, niin pääset suoraan kohteeseen. Tämä ei ehkä kuulosta niin erikoiselta, mutta valtaville tietokannoille se voi säästää paljon aikaa.

Ottaaksesi erittäin yksinkertaistetun esimerkin, harkitse Oxford English Dictionary -sanakirjaa, jossa on määritelmät yli 600,000 XNUMX sanalle. Jos digitaalinen painos perustuu hash-taulukkoon, voit yksinkertaisesti käyttää annettua sanaa avaimena ja siirtyä suoraan määritelmään. Ilman hash-taulukkoa sanakirja todennäköisesti tukeutuisi paljon hitaampaan hakumekanismiin, joka käyttää poistoprosessia päästäkseen lopulta yhteen pyydettyyn määritelmään. Ja vaikka hash-taulukko voi löytää minkä tahansa sanan tasaisessa ajassa (yleensä sekunnin murto-osassa), muiden menetelmien hakuaika voi kasvaa sanakirjan sanojen määrän kasvaessa. Hajautustaulukolla on myös toinen etu: se voi pitää sanakirjan dynaamisena, mikä helpottaa uusien sanojen lisäämistä ja vanhentuneiden sanojen poistamista.

Tutkijat ovat käyttäneet vuosikymmeniä rakentaneet hash-taulukoita, jotka pyrkivät maksimoimaan nopeuden ja minimoimaan muistia. 20-luvulla ratkaisuilla oli taipumus tarjota merkittäviä etuja vain yhdessä suhteessa, ajassa tai tilassa. Sitten vuonna 2003 tutkijat osoittivat että oli teoriassa mahdollista tehdä suuri tehokkuusloikka sekä ajassa että tilassa samanaikaisesti. Kestäisi kuitenkin vielä kaksi vuosikymmentä, ennen kuin tutkijat löytävät ihanteellisen tasapainon näiden kahden välillä.

Data Shuffle

Ensimmäinen suuri askel kohti tätä tavoitetta otettiin vuonna 2022 a suuri tietojenkäsittelytieteen konferenssi Roomassa. Siellä ryhmä ehdotti hash-taulukkoa uusilla ominaisuuksilla, jotka voisivat tarjota parhaan yhdistelmän aika- ja tilatehokkuutta, joka on tähän mennessä suunniteltu. Paperin ensimmäinen kirjoittaja (aakkosjärjestyksessä) oli Michael Bender Stony Brookin yliopistosta, joten sitä kutsutaan yleisesti nimellä Bender et al. hash-taulukko. Vaikka tiimi ei yrittänyt rakentaa toimivaa hash-taulukkoa, he osoittivat, että se voidaan periaatteessa rakentaa heidän kuvailemillaan ominaisuuksilla.

Arvioidakseen laatimaansa hash-taulukkoa ryhmä tuotti kompromissikäyrän - kaavion, joka kuvaa toimintoa (lisäämistä tai poistamista) kohti kuluvan ajan yhdelle akselille ja muistin viemän tilan toiselle akselille. Mutta tämä kaavio määrittelee avaruuden erityisellä tavalla: tiivistetaulukot tarvitsevat enemmän muistia niiden rakenteesta johtuen kuin vain vähimmäismäärä tietyn kohteiden tallentamiseen. Tietojenkäsittelytieteilijät kutsuvat tätä ylimääräistä tilaa "hukatuiksi bitteiksi", vaikka ne eivät todellakaan ole hukattu ja ovat jossain määrin tarpeellisia. Kompromissikäyrän tila-akseli mittaa hukattujen bittien määrää avainta kohti.

Analysoimalla kompromissikäyrää tutkijat voivat selvittää nopeimman mahdollisen ajan hash-taulukolle, joka käyttää tiettyä tilaa. He voivat myös kääntää kysymyksen ympäri selvittääkseen pienimmän mahdollisen tilan tietylle toimintaajalle. Yleensä pieni muutos yhdessä muuttujassa johtaa pieneen muutokseen toisessa, sanoi William Kuszmaul, teoreettinen tietojenkäsittelytieteilijä Harvardissa ja vuoden 2022 artikkelin toinen kirjoittaja. "Jos kaksinkertaistat ajan, ehkä puolitat hukattujen bittien määrän näppäintä kohti."

Mutta näin ei ole heidän suunnittelemansa hash-taulukon tapauksessa. "Jos lisäät aikaa hieman, hukatut bitit avainta kohti vähenevät eksponentiaalisesti", Kuszmaul sanoi. Vaihtokäyrä oli niin jyrkkä, että se oli kirjaimellisesti listan ulkopuolella.

Tiimi rakensi hash-taulukkonsa kahdessa osassa. Niissä oli ensisijainen tietorakenne, jossa kohteet tallennetaan ilman hukkaan heitettyjä bittejä, ja toissijainen tietorakenne, joka auttaa kyselypyyntöä löytämään etsimän kohteen. Vaikka ryhmä ei keksinyt käsitettä toissijaisesta tietorakenteesta, he tekivät ratkaisevan löydön, joka teki heidän hypertehokkaan hash-taulukon mahdolliseksi: Rakenteen yleinen muistin tehokkuus riippuu siitä, kuinka ensisijainen rakenne järjestää tallennetut kohteet.

Perusajatuksena on, että jokaisella ensisijaisen rakenteen esineellä on ensisijaiset säilytyspaikat - paras sijainti, toiseksi paras, kolmanneksi paras ja niin edelleen. Jos kohde on parhaalla paikallaan, siihen kiinnitetään numero 1 ja tämä numero tallennetaan toissijaiseen tietorakenteeseen. Vastauksena kyselyyn toissijainen rakenne tarjoaa vain numeron 1, joka ilmaisee kohteen tarkan sijainnin ensisijaisessa rakenteessa.

Jos kohde on 100. parhaalla paikallaan, toissijainen tietorakenne liittää luvun 100. Ja koska järjestelmä käyttää binääriä, se edustaa lukua 100 muodossa 1100100. Numeron 1100100 tallentamiseen kuluu tietysti enemmän muistia kuin 1:n — numero, joka annetaan tuotteelle, kun se on parhaalla paikalla. Tällaisista eroista tulee merkittäviä, jos tallennat esimerkiksi miljoona tuotetta.

Joten tiimi ymmärsi, että jos siirrät jatkuvasti ensisijaisen tietorakenteen kohteita niiden suosituimpiin paikkoihin, voit merkittävästi vähentää toissijaisen rakenteen muistia ilman, että sinun tarvitsee pidentää kyselyaikoja.

"Ennen tätä työtä kukaan ei ollut tajunnut, että tietorakennetta voi pakata edelleen siirtämällä tietoa", Pagh sanoi. "Se oli Bender-paperin suuri oivallus."

Kirjoittajat osoittivat, että heidän keksintönsä loi uuden ylärajan tehokkaimmille hash-taulukoille, mikä tarkoittaa, että se oli paras tähän mennessä kehitetty tietorakenne sekä aika- että tilatehokkuuden kannalta. Mutta mahdollisuus, että joku muu voisi tehdä vielä paremmin, säilyi.

Sitoutunut menestymään

Seuraavana vuonna johtama tiimi Huacheng Yu, tietojenkäsittelytieteilijä Princetonin yliopistosta, yritti parantaa Bender-tiimin hash-taulukkoa. "Työskentelimme todella kovasti, emmekä voineet tehdä sitä", sanoi Renfei Zhou, opiskelija Tsinghuan yliopistossa Pekingissä ja Yun tiimin jäsen. "Silloin epäilimme, että heidän ylärajansa oli [myös] alaraja" - parasta mitä voidaan saavuttaa. "Kun yläraja on yhtä suuri kuin alaraja, peli on ohi ja sinulla on vastaus." Olitpa kuinka älykäs tahansa, mikään hash-taulukko ei voi tehdä parempaa.

Yun tiimi käytti uutta strategiaa selvittääkseen, oliko tämä aavistus oikea laskemalla alaraja ensimmäisten periaatteiden perusteella. Ensinnäkin he päättelivät, että lisäyksen tai poiston suorittamiseksi hash-taulukon – tai oikeastaan ​​minkä tahansa tietorakenteen – täytyy päästä tietokoneen muistiin muutaman kerran. Jos he voisivat selvittää, kuinka monta kertaa tilaa säästävälle hash-taulukolle tarvitaan, he voisivat kertoa sen käyttökohtaisella ajalla (vakio), mikä antaisi heille ajoajan alarajan.

Mutta jos he eivät tienneet mitään hash-taulukosta (paitsi että se oli tilaa säästävä), kuinka tutkijat saattoivat selvittää muistin käyttämiseen tarvittavan vähimmäismäärän? He johtivat sen puhtaasti teoriasta käyttämällä näennäisesti toisiinsa liittymätöntä kenttää, jota kutsutaan viestinnän monimutkaisuuden teoriaksi, joka tutkii kuinka monta bittiä tarvitaan tiedon välittämiseen kahden osapuolen välillä. Lopulta ryhmä onnistui: he selvittivät, kuinka monta kertaa tietorakenteen on käytettävä muistiaan operaatiota kohden.

Tämä oli heidän tärkein saavutuksensa. Sitten he pystyivät määrittämään alarajan suoritusajalle mille tahansa tilaa säästävälle hash-taulukolle. Ja he näkivät, että se vastasi täsmälleen Benderin hash-taulukkoa. "Ajattelimme [alkuvaiheessa], että sitä voitaisiin parantaa", Zhou sanoi. "Kävi ilmi, että olimme väärässä." Se puolestaan ​​merkitsi, että Petersonin ongelma oli vihdoin ratkaistu.

Sen lisäksi, että Kuszmaul vastasi vuosikymmeniä vanhaan kysymykseen, hämmästyttävä asia Yu-todistuksessa on sen yleisyys. "Niiden alaraja koskee kaikkia mahdollisia tietorakenteita, myös sellaisia, joita ei ole vielä keksitty." Tämä tarkoittaa, että mikään tiedon tallennusmenetelmä ei voi koskaan lyödä Benderin hash-taulukkoa muistin ja nopeuden suhteen.

Hashing tulevaisuuteen

Huolimatta uuden hash-taulukon ennennäkemättömästä tehokkuudesta, kukaan ei todennäköisesti yritä rakentaa sitä lähiaikoina. Se on vain liian monimutkaista rakentaa. "Algoritmi, joka on nopea teoriassa, ei välttämättä ole nopea käytännössä", Zhou sanoi.

Ei ole epätavallista, että tällaiset kuilut teorian ja käytännön välillä jatkuvat pitkään, Kuszmaul sanoi, koska teoreetikot jättävät huomioimatta jatkuvat tekijät. Toiminnon suorittamiseen kuluva aika kerrotaan tyypillisesti luvulla, jollain vakiolla, jonka tarkka arvo voi olla teoreettisesta näkökulmasta epäolennainen. "Mutta käytännössä vakioilla on todella merkitystä", hän sanoi. "Oikeassa maailmassa kerroin 10 on pelin loppu."

Todelliset hash-taulukot paranevat edelleen aineellisella tavalla, vaikka ne jäävätkin kaukana teoreettisesta ihanteesta. Esimerkiksi uusi hash-taulukko nimeltään IcebergHTBenderin, Kuszmaulin ja muiden rakentama, on paljon parempi kuin edeltäjänsä. Kuszmaulin mukaan se on kaksi kertaa nopeampi kuin tämän päivän tilatehokkain hash-taulukko, ja se käyttää kolme kertaa vähemmän tilaa kuin nopein hash-taulukko.

Mitzenmacher toivoo, että vuoden 2023 tuloksesta voi pian olla toisenlaista hyötyä: "Aina kun saat uuden alarajan - erityisesti sellaisen, joka sisältää uusia tekniikoita - on aina toivoa, että voit käyttää niitä ... liittyviin ongelmiin."

Tietojenkäsittelytieteilijä sanoi, että on myös älyllinen tyytyväisyys, joka tulee siitä, että tietää, että olet ratkaissut vaikean ja pitkäaikaisen ongelman. Piotr Indyk Massachusetts Institute of Technologysta. "Kun olet varma, että tiettyjä tietorakenteita ei voida parantaa, se voi auttaa keskittämään tutkimustyötä." Lopuksi datatutkijat voivat kääntää huomionsa pois Petersonin haasteesta ja keskittyä uusiin teoreettisen tietojenkäsittelytieteen ongelmiin, joista ei ole pulaa.