Znanstveniki najdejo optimalno razmerje med shranjevanjem podatkov in časom | Revija Quanta

Pred približno 70 leti je inženir pri IBM-u po imenu Hans Peter Luhn tiho spremenil tok računalništva. Luhn je imel že več patentov, vključno z enim za napravo, ki je lahko izmerila število niti v blagu, in drugim za vodnik, ki je določal, katere mešane pijače lahko pripravite iz sestavin v vaši kuhinji. Toda v internem dokumentu IBM-a iz leta 1953 je predlagal novo tehniko za shranjevanje in pridobivanje informacij, ki je zdaj vgrajena v skoraj vse računalniške sisteme: zgoščeno tabelo.

Zgoščevalne tabele so glavni razred podatkovnih struktur. Ponujajo posebno priročno metodo za dostop do in spreminjanje informacij v ogromnih zbirkah podatkov. Toda ta tehnologija prihaja z neizogibnim kompromisom.

V 1957 papirja objavljen v IBM Journal of Research and Development, W. Wesley Peterson je opredelil glavni tehnični izziv, ki ga predstavljajo zgoščene tabele: biti morajo hitre, kar pomeni, da lahko hitro pridobijo potrebne informacije. Morajo pa biti tudi kompaktni in uporabljati čim manj pomnilnika. Ta dvojna cilja sta v bistvu v nasprotju. Dostop do baze podatkov in njeno spreminjanje je mogoče narediti hitreje, če ima zgoščena tabela več pomnilnika; in operacije postanejo počasnejše v zgoščenih tabelah, ki uporabljajo manj prostora. Odkar je Peterson predstavil ta izziv, so raziskovalci poskušali najti najboljše ravnovesje med časom in prostorom.

Računalniški znanstveniki so zdaj matematično dokazali, da so našli optimalen kompromis. Rešitev je prišla od a par nedavnih članki ki sta se dopolnjevala. "Ti dokumenti rešujejo dolgotrajno odprto vprašanje o najboljših možnih kompromisih med prostorom in časom, pri čemer so prinesli zelo presenetljive rezultate, za katere pričakujem, da bodo imeli pomemben vpliv v prihodnjih letih," je dejal Michael Mitzenmacher, računalniški znanstvenik na univerzi Harvard, ki ni bil vključen v nobeno študijo.

"Vsekakor bi rekel, da je to velik posel," je dodal Rasmus Pagh, računalniški znanstvenik na Univerzi v Kopenhagnu. »Veliko ljudi se je ukvarjalo s to težavo, da bi ugotovili, koliko lahko stisnete prostora, hkrati pa izvajate časovno učinkovite operacije. To je tisto, kar bi rad rešil.«

Ustvarjanje razpršitve

Zgoščevalne tabele so danes med najstarejšimi, najpreprostejšimi, najhitrejšimi in najbolj razširjenimi podatkovnimi strukturami. Zasnovani so za izvajanje treh osnovnih operacij: vstavljanje, ki dodaja nove elemente v zbirko podatkov; poizvedbe, ki dostopajo do predmeta ali preverjajo, ali obstaja; in izbrisov. Zgoščevalna tabela je lahko efemerna – obstaja samo, dokler se izvaja določen program – ali pa je stalni del operacijskega sistema vašega računalnika. Spletni brskalnik, kot sta Chrome ali Safari, ima lahko več vgrajenih zgoščenih tabel, namenjenih spremljanju različnih vrst podatkov.

Vnosi v zgoščevalno tabelo so shranjeni kot pari, pri čemer je element – ​​informacija sama – povezana s ključem, ki identificira informacijo. Vstavite ključ v poizvedovalni algoritem razpršilne tabele in pripeljal vas bo neposredno do elementa. To morda ne zveni tako nenavadno, a za ogromne baze podatkov je lahko odličen prihranek časa.

Če vzamemo zelo poenostavljen primer, razmislite o Oxfordovem angleškem slovarju, ki vsebuje definicije za več kot 600,000 besed. Če digitalna izdaja temelji na zgoščevalni tabeli, lahko preprosto uporabite dano besedo kot ključ in nadaljujete neposredno z definicijo. Brez zgoščevalne tabele bi se slovar verjetno zanašal na veliko počasnejši mehanizem iskanja z uporabo postopka izločanja, da bi se na koncu zbližal z zahtevano definicijo. In medtem ko lahko zgoščevalna tabela najde katero koli besedo v konstantnem času (običajno majhen delček sekunde), se lahko čas iskanja za druge metode poveča, ko se število besed v slovarju poveča. Zgoščevalna tabela ponuja še eno prednost: slovar lahko ohranja dinamičen, kar olajša vstavljanje novih besed in brisanje zastarelih.

Raziskovalci so desetletja gradili zgoščevalne tabele, ki poskušajo povečati hitrost in zmanjšati pomnilnik. V 20. stoletju so rešitve ponavadi ponujale pomembne pridobitve v samo enem vidiku, času ali prostoru. Nato so leta 2003 raziskovalci je pokazala, da je teoretično mogoče narediti velik preskok učinkovitosti tako v času kot v prostoru hkrati. Vendar bi trajalo še dve desetletji, da bi raziskovalci ugotovili idealno ravnovesje med obema.

Premešanje podatkov

Prvi večji korak k temu cilju je bil narejen leta 2022 ob a velika računalniška konferenca v Rimu. Tam je ekipa predlagala razpršilno tabelo z novimi funkcijami, ki bi lahko zagotovile najboljšo kombinacijo časovne in prostorske učinkovitosti, kar jih je bilo do zdaj. Prvi avtor prispevka (naveden po abecedi) je bil Michael Bender z Univerze Stony Brook, zato se običajno imenuje Bender et al. zgoščena tabela. Čeprav ekipa ni poskušala zgraditi delujoče razpršilne tabele, so dokazali, da jo je načeloma mogoče sestaviti s funkcijami, ki so jih opisali.

Da bi ovrednotili razpršilno tabelo, do katere so prišli, je skupina izdelala krivuljo kompromisa – graf, ki prikazuje čas na operacijo (vstavljanje ali brisanje) na eni osi in prostor, ki ga zasede pomnilnik, na drugi. Toda ta graf opredeljuje prostor na poseben način: zgoščene tabele zaradi tega, kako so zgrajene, potrebujejo več pomnilnika kot le najmanjši minimum, potreben za shranjevanje določenega nabora elementov. Računalniški znanstveniki temu dodatnemu prostoru pravijo »zapravljeni koščki«, čeprav v resnici niso zapravljeni in so do neke mere potrebni. Vesoljska os na krivulji kompromisa meri število izgubljenih bitov na ključ.

Z analizo krivulje kompromisa lahko raziskovalci ugotovijo najhitrejši možni čas za zgoščevalno tabelo, ki uporablja določeno količino prostora. Lahko tudi obrnejo vprašanje, da ugotovijo najmanjši možni prostor za določen čas delovanja. Običajno bo majhna sprememba ene spremenljivke povzročila majhno spremembo druge William Kuszmaul, teoretični računalniški znanstvenik na Harvardu in soavtor prispevka 2022. "Če podvojite čas, boste morda prepolovili število izgubljenih bitov na ključ."

Vendar to ne velja za razpršilno tabelo, ki so jo oblikovali. "Če malo povečate čas, se zapravljeni bitovi na tipko eksponentno zmanjšajo," je dejal Kuszmaul. Krivulja kompromisov je bila tako strma, da je bila dobesedno izven lestvic.

Ekipa je svojo razpršilno tabelo sestavila v dveh delih. Imeli so primarno podatkovno strukturo, v kateri so elementi shranjeni brez kakršnih koli izgubljenih bitov, in sekundarno podatkovno strukturo, ki pomaga zahtevi poizvedbe najti element, ki ga išče. Čeprav skupina ni izumila pojma sekundarne podatkovne strukture, so prišli do ključnega odkritja, ki je omogočilo njihovo hiperučinkovito zgoščeno tabelo: splošna učinkovitost pomnilnika strukture je odvisna od tega, kako primarna struktura razporedi svoje shranjene elemente.

Osnovna ideja je, da ima vsak element v primarni strukturi prednostne lokacije za shranjevanje – najboljša lokacija, druga najboljša, tretja najboljša in tako naprej. Če je postavka na svojem najboljšem mestu, je nanjo pritrjena številka 1 in ta številka je shranjena v sekundarni podatkovni strukturi. Kot odgovor na poizvedbo sekundarna struktura zagotovi samo številko 1, ki pove točno lokacijo predmeta v primarni strukturi.

Če je element na 100. najboljšem mestu, sekundarna podatkovna struktura pripne številko 100. In ker sistem uporablja binarno vrednost, predstavlja številko 100 kot 1100100. Za shranjevanje številke 1100100 je seveda potrebnih več pomnilnika kot 1 — številka, dodeljena predmetu, ko je na najboljšem mestu. Takšne razlike postanejo pomembne, če shranjujete, recimo, milijon predmetov.

Tako je ekipa ugotovila, da če nenehno premikate elemente v primarni podatkovni strukturi na njihove bolj želene lokacije, lahko znatno zmanjšate pomnilnik, ki ga porabi sekundarna struktura, ne da bi morali povečati čas poizvedbe.

"Pred tem delom se nihče ni zavedal, da lahko strukturo podatkov dodatno stisnete s premikanjem informacij," je dejal Pagh. "To je bil velik vpogled Benderjevega papirja."

Avtorji so pokazali, da je njihov izum vzpostavil novo zgornjo mejo za najučinkovitejše zgoščevalne tabele, kar pomeni, da je to najboljša podatkovna struktura, ki je bila doslej zasnovana v smislu časovne in prostorske učinkovitosti. Ostala pa je možnost, da bo komu drugemu šlo še bolje.

Zavezani k uspehu

Naslednje leto je ekipa pod vodstvom Huacheng Yu, računalničar na Univerzi Princeton, je poskušal izboljšati razpršilno tabelo ekipe Bender. "Res smo trdo delali in nam ni uspelo," je dejal Renfei Zhou, študent univerze Tsinghua v Pekingu in član Yujeve ekipe. "Takrat smo posumili, da je njihova zgornja meja [tudi] spodnja meja" - najboljše, kar je mogoče doseči. "Ko je zgornja meja enaka spodnji meji, je igre konec in imate svoj odgovor." Ne glede na to, kako pametni ste, nobena zgoščena tabela ne more narediti nič boljšega.

Yujeva ekipa je uporabila novo strategijo, da bi ugotovila, ali je bila ta slutnja pravilna, z izračunom spodnje meje iz prvih načel. Najprej so sklepali, da mora zgoščena tabela - ali pravzaprav katera koli podatkovna struktura - za izvedbo vstavljanja ali brisanja nekajkrat dostopati do pomnilnika računalnika. Če bi lahko ugotovili najmanjše število krat, potrebnih za prostorsko učinkovito zgoščevalno tabelo, bi to lahko pomnožili s časom, potrebnim za dostop (konstanta), kar bi jim dalo spodnjo mejo izvajalnega časa.

Če pa niso vedeli ničesar o zgoščevalni tabeli (razen tega, da je prostorsko učinkovita), kako so lahko raziskovalci ugotovili, kolikokrat je najmanj potrebno za dostop do pomnilnika? Izpeljali so ga izključno iz teorije z uporabo na videz nepovezanega področja, imenovanega teorija komunikacijske kompleksnosti, ki preučuje, koliko bitov je potrebnih za prenos informacij med dvema stranema. Sčasoma je ekipi uspelo: ugotovili so, kolikokrat mora podatkovna struktura dostopati do svojega pomnilnika na operacijo.

To je bil njihov ključni dosežek. Nato so lahko določili spodnjo mejo izvajalnega časa za katero koli prostorsko učinkovito zgoščeno tabelo. In videli so, da se natančno ujema z Benderjevo razpršilno tabelo. "Mislili smo [sprva], da bi ga lahko izboljšali," je dejal Zhou. "Izkazalo se je, da smo se motili." To pa je pomenilo, da je bil Petersonov problem končno rešen.

Kuszmaul je poleg odgovora na desetletja staro vprašanje dejal, da je neverjetna stvar pri dokazu Yu njegova splošnost. "Njihova spodnja meja velja za vse možne podatkovne strukture, vključno s tistimi, ki še niso bile izumljene." To pomeni, da noben način shranjevanja podatkov ne more premagati Benderjeve zgoščene tabele v smislu pomnilnika in hitrosti.

Hashing v prihodnost

Kljub neverjetni učinkovitosti nove zgoščevalne tabele je verjetno nihče ne bo kmalu poskusil zgraditi. To je preprosto preveč zapleteno za izdelavo. "Algoritem, ki je hiter v teoriji, ni nujno hiter v praksi," je dejal Zhou.

Ni nenavadno, da takšne vrzeli med teorijo in prakso trajajo dolgo časa, je dejal Kuszmaul, ker teoretiki ponavadi ignorirajo stalne dejavnike. Čas, potreben za izvedbo operacije, se običajno pomnoži s številom, neko konstanto, katere natančna vrednost je s teoretičnega stališča lahko nepomembna. "Toda v praksi so konstante res pomembne," je dejal. "V resničnem svetu je faktor 10 zaključek igre."

Dejanske zgoščene tabele se še vedno bistveno izboljšujejo, čeprav so daleč od teoretičnega ideala. Na primer, nova razpršilna tabela, imenovana IcebergHT, ki so ga zgradili Bender, Kuszmaul in drugi, je veliko boljši od svojih predhodnikov. Po besedah ​​Kuszmaula je dvakrat hitrejša od prostorsko najbolj učinkovite zgoščevalne tabele, ki je danes na voljo, in uporablja trikrat manj prostora kot najhitrejša zgoščevalna tabela.

Mitzenmacher upa, da bo rezultat iz leta 2023 morda kmalu prinesel drugo vrsto koristi: "Kadarkoli dobite novo spodnjo mejo - še posebej tisto, ki vključuje nekaj novih tehnik - vedno obstaja upanje, da bi jih lahko uporabili ... za sorodne težave."

Obstaja tudi intelektualno zadovoljstvo, ki izhaja iz spoznanja, da ste rešili težaven in dolgotrajen problem, je dejal računalničar Piotr Indyk Tehnološkega inštituta Massachusetts. "Ko ste prepričani, da določenih podatkovnih struktur ni mogoče izboljšati, lahko to pomaga osredotočiti raziskovalna prizadevanja." Končno lahko raziskovalci podatkov preusmerijo svojo pozornost stran od Petersonovega izziva in se osredotočijo na nove probleme v teoretični računalniški znanosti, ki jih ne manjka.