A tudósok megtalálják az adattárolás és az idő optimális egyensúlyát | Quanta Magazin

Körülbelül 70 évvel ezelőtt az IBM egyik mérnöke, Hans Peter Luhn csendben megváltoztatta a számítástechnika irányvonalát. Luhn már több szabadalommal rendelkezett, köztük egy olyan eszközre, amely képes mérni egy ruha szálak számát, egy másikat pedig egy útmutatóra, amely meghatározta, hogy milyen kevert italokat készíthet a konyhájában lévő összetevőkből. Egy 1953-as belső IBM közleményben azonban egy új technikát javasolt az információk tárolására és visszakeresésére, amely ma már szinte minden számítási rendszerbe beépült: a hash táblát.

A hash táblák az adatstruktúrák egyik fő osztályát képezik. Különösen kényelmes módszert kínálnak a hatalmas adatbázisokban található információk elérésére és módosítására. Ez a technológia azonban elkerülhetetlen kompromisszumokkal jár.

Egy 1957 papír a IBM kutatási és fejlesztési folyóirat, W. Wesley Peterson azonosította a fő technikai kihívást, amelyet a hash táblák jelentenek: gyorsnak kell lenniük, ami azt jelenti, hogy gyorsan lekérhetik a szükséges információkat. De kompaktnak is kell lenniük, a lehető legkevesebb memóriát használva. Ezek a kettős célkitűzések alapvetően ellentmondanak egymásnak. Az adatbázis elérése és módosítása gyorsabban elvégezhető, ha a hash tábla több memóriával rendelkezik; és a műveletek lelassulnak a kevesebb helyet igénylő hash táblákban. Mióta Peterson felvázolta ezt a kihívást, a kutatók megpróbálták megtalálni a legjobb egyensúlyt idő és tér között.

Az informatikusok most matematikailag bebizonyították, hogy megtalálták az optimális kompromisszumot. A megoldást a pár a legújabb papírok amelyek kiegészítették egymást. "Ezek a dokumentumok megoldják a régóta nyitott kérdést a lehető legjobb tér-idő kompromisszumokról, és mélyen meglepő eredményeket adnak, amelyek várhatóan még sok éven át jelentős hatással lesznek" Michael Mitzenmacher, a Harvard Egyetem informatikusa, aki egyik tanulmányban sem vett részt.

„Határozottan azt mondanám, hogy ez nagy dolog” – tette hozzá Rasmus Pagh, a Koppenhágai Egyetem informatikusa. „Sokan dolgoztak ezen a problémán, próbálták megnézni, mennyi helyet lehet szűkíteni, miközben időhatékony műveleteket is végeztek. Ez az, amit szívesen megoldottam volna.”

Hash készítése belőle

A hash táblák ma a legrégebbi, legegyszerűbb, leggyorsabb és legszélesebb körben használt adatstruktúrák közé tartoznak. Három alapvető művelet végrehajtására tervezték őket: beszúrások, amelyek új elemeket adnak az adatbázishoz; lekérdezések, amelyek hozzáférnek egy elemhez, vagy ellenőrzik, hogy létezik-e; és törlések. A hash-tábla lehet mulandó – csak addig létezhet, amíg egy adott program fut –, vagy lehet a számítógép operációs rendszerének állandó része. Egy webböngésző, például a Chrome vagy a Safari több beépített hash-táblázattal is rendelkezhet, amelyek célja a különböző típusú adatok nyomon követése.

A hash-táblázat bejegyzései párokként tárolódnak, és az elem – maga az információ – egy, az információt azonosító kulccsal van összekötve. Csatlakoztasson egy kulcsot a hash tábla lekérdezési algoritmusához, és közvetlenül az elemhez viszi. Lehet, hogy ez nem hangzik olyan rendkívülinek, de hatalmas adatbázisok esetén nagyszerű időmegtakarítást jelenthet.

Hogy egy rendkívül leegyszerűsített példát vegyünk, vegyük figyelembe az Oxford English Dictionaryt, amely több mint 600,000 XNUMX szóra tartalmaz definíciókat. Ha egy digitális kiadás hash-táblázatra támaszkodik, egyszerűen használhat egy adott szót kulcsként, és közvetlenül a definícióhoz léphet. Kivonattábla nélkül a szótár valószínűleg sokkal lassabb keresési mechanizmusra támaszkodna, és egy eliminációs folyamatot használna, hogy végül konvergáljon a kért definícióhoz. És míg egy hash tábla bármilyen szót képes megtalálni állandó idő alatt (általában a másodperc töredéke alatt), a többi módszer keresési ideje megnőhet, ahogy a szótárban lévő szavak száma növekszik. A hash tábla egy másik előnyt is kínál: képes megőrizni a szótár dinamikáját, megkönnyítve az új szavak beszúrását és az elavult szavak törlését.

A kutatók évtizedeket töltöttek olyan hash-táblázatok létrehozásával, amelyek megpróbálják maximalizálni a sebességet és minimalizálni a memóriát. A 20. században a megoldások csak egy vonatkozásban, időben vagy térben jelentős előnyöket kínáltak. Aztán 2003-ban a kutatók kimutatta, hogy elméletileg lehetséges volt egyszerre jelentős hatékonysági ugrás időben és térben egyaránt. A kutatóknak azonban további két évtizedbe telne, hogy megtalálják a kettő közötti ideális egyensúlyt.

A Data Shuffle

Az első nagy lépést e cél felé 2022-ben, a jelentős számítástechnikai konferencia Rómában. Ott egy csapat új funkciókkal rendelkező hash-táblázatot javasolt, amely az idő és a tér hatékonyságának eddig elképzelt legjobb kombinációját nyújtja. A cikk első szerzője (ábécé sorrendben) Michael Bender, a Stony Brook Egyetem munkatársa volt, ezért általában Bender et al. hash tábla. Noha a csapat nem próbált működő hash-táblát építeni, bebizonyították, hogy az elvileg az általuk leírt jellemzőkkel elkészíthető.

Az általuk kidolgozott hash-tábla értékeléséhez a csoport egy kompromisszumos görbét készített – egy grafikont, amely az egyik tengelyen ábrázolja a műveletenkénti időt (beszúrás vagy törlés), a másik tengelyen pedig a memória által elfoglalt helyet. Ez a grafikon azonban különleges módon határozza meg a teret: felépítésük miatt a hash tábláknak több memóriára van szükségük, mint egy adott elemkészlet tárolásához szükséges minimális minimumra. Az informatikusok ezt az extra helyet „elpazarolt biteknek” nevezik, még akkor is, ha valójában nem vesztegelnek, és bizonyos mértékig szükségesek is. A kompromisszumos görbén lévő tértengely a kulcsonkénti elpazarolt bitek számát méri.

Egy kompromisszumos görbe elemzésével a kutatók kitalálhatják a lehető leggyorsabb időt egy adott mennyiségű helyet használó hash-táblázathoz. Megfordíthatják a kérdést, hogy kitalálják a lehető legkisebb helyet egy adott működési időhöz. Általában egy kis változás az egyik változóban kis változáshoz vezet a másikban, mondta Vilmos Kuszmaul, a Harvard elméleti informatikusa és a 2022-es tanulmány társszerzője. "Ha megduplázza az időt, talán felére csökkenti a kulcsonkénti elvesztegetett bitek számát."

De nem ez a helyzet az általuk tervezett hash-táblázattal. "Ha egy kicsit növeli az időt, a kulcsonkénti elvesztegetett bitek száma exponenciálisan csökken" - mondta Kuszmaul. A kompromisszumos görbe olyan meredek volt, hogy szó szerint lekerült a listáról.

A csapat két részre osztotta a hash-táblázatát. Elsõdleges adatstruktúrájuk volt, amelyben az elemek elpazarolt bitek nélkül vannak tárolva, és egy másodlagos adatszerkezetük, amely segít a lekérdezésnek megtalálni a keresett elemet. Noha a csoport nem találta fel a másodlagos adatstruktúra fogalmát, egy döntő felfedezést tettek, amely lehetővé tette a hiperhatékony hash-táblázatot: A struktúra általános memóriahatékonysága attól függ, hogy az elsődleges struktúra hogyan rendezi el a tárolt elemeit.

Az alapötlet az, hogy az elsődleges struktúra minden elemének van preferált tárolási helye – a legjobb hely, a második legjobb, a harmadik legjobb és így tovább. Ha egy elem a legjobb helyen van, akkor az 1-es szám kerül rá, és ez a szám a másodlagos adatstruktúrában tárolódik. Egy lekérdezésre válaszul a másodlagos szerkezet csak az 1-es számot adja meg, amely kiírja az elem pontos helyét az elsődleges szerkezetben.

Ha az elem a 100. legjobb helyén van, a másodlagos adatstruktúra hozzáfűzi a 100-as számot. És mivel a rendszer binárist használ, a 100-as számot 1100100-ként ábrázolja. Természetesen több memóriát igényel az 1100100 szám tárolása, mint az 1. — egy tételhez rendelt szám, amikor az a legjobb helyen van. Az ilyen különbségek jelentőssé válnak, ha mondjuk egymillió elemet tárol.

Így a csapat rájött, hogy ha az elsődleges adatstruktúra elemeit folyamatosan áthelyezi a preferáltabb helyekre, jelentősen csökkentheti a másodlagos struktúra által felhasznált memóriát anélkül, hogy növelni kellene a lekérdezési időt.

„A munka előtt senki sem tudta, hogy az adatok mozgatásával tovább tömöríthető az adatstruktúra” – mondta Pagh. "Ez volt a Bender újság nagy betekintése."

A szerzők kimutatták, hogy találmányuk új felső korlátot állított fel a leghatékonyabb hash táblák számára, ami azt jelenti, hogy ez az eddigi legjobb adatstruktúra mind idő-, mind térhatékonyság szempontjából. De fennáll annak a lehetősége, hogy valaki más még jobban teljesít.

A sikerhez kötve

A következő évben egy csapat vezetésével Huacheng Yu, a Princeton Egyetem informatikusa megpróbálta javítani a Bender csapat hash-táblázatát. „Nagyon keményen dolgoztunk, és nem tudtuk megcsinálni” – mondta Renfei Zhou, a pekingi Tsinghua Egyetem hallgatója és Yu csapatának tagja. „Ekkor gyanítottuk, hogy a felső határuk [egyben] alsó korlát” – ez a lehető legjobb, amit el lehet érni. "Amikor a felső korlát egyenlő az alsó korláttal, a játéknak vége, és megvan a válasz." Nem számít, milyen okos vagy, egyetlen hash-tábla sem tud jobbat csinálni.

Yu csapata egy új stratégiát alkalmazott annak kiderítésére, hogy ez a sejtés helyes volt-e, és az első alapelvek alapján egy alsó korlátot számolt ki. Először is azzal érveltek, hogy a beszúrás vagy törlés végrehajtásához egy hash táblának – vagy tulajdonképpen bármilyen adatstruktúrának – néhányszor hozzá kell férnie a számítógép memóriájához. Ha ki tudnák találni, hogy hányszor kell egy helytakarékos hash táblához, akkor ezt megszorozhatnák a hozzáférésenkénti idővel (konstans), így alsó korlátot adva nekik a futásidőre.

De ha semmit sem tudtak a hash tábláról (kivéve, hogy helytakarékos), hogyan tudták kitalálni a kutatók, hogy hányszor kell minimálisan hozzáférni a memóriához? Pusztán elméletből származtatták, a kommunikációs komplexitás elméletének nevezett, látszólag nem kapcsolódó területet használva, amely azt vizsgálja, hogy hány bitre van szükség az információ továbbításához két fél között. Végül a csapatnak sikerült: rájöttek, hogy műveletenként hányszor kell egy adatstruktúrának hozzáférnie a memóriájához.

Ez volt a legfontosabb eredményük. Ezután minden helytakarékos hash-táblához alsó korlátot tudtak megállapítani a futásidőben. És látták, hogy pontosan megegyezik a Bender hash táblázatával. "Azt hittük [eleinte], hogy javítható" - mondta Zhou. – Kiderült, hogy tévedtünk. Ez viszont azt jelentette, hogy Peterson problémája végre megoldódott.

A több évtizedes kérdés megválaszolása mellett Kuszmaul azt mondta, hogy a Yu-bizonyításban az a csodálatos, hogy az általános. "Az alsó korlátjuk minden lehetséges adatszerkezetre vonatkozik, beleértve azokat is, amelyeket még nem találtak fel." Ez azt jelenti, hogy a memória és a sebesség tekintetében egyetlen adattárolási módszer sem tudja felülmúlni a Bender hash táblát.

Hashing Into the Future

Az új hash-tábla példátlan hatékonysága ellenére valószínűleg senki sem próbálkozik egyhamar megépíteni. Egyszerűen túl bonyolult megépíteni. "Az elméletben gyors algoritmus nem feltétlenül gyors a gyakorlatban" - mondta Zhou.

Nem szokatlan, hogy az elmélet és a gyakorlat között ilyen szakadékok hosszú ideig fennmaradnak, mondta Kuszmaul, mert a teoretikusok hajlamosak figyelmen kívül hagyni az állandó tényezőket. A művelet végrehajtásához szükséges időt általában megszorozzák egy számmal, valamilyen állandóval, amelynek pontos értéke elméleti szempontból lényegtelen. „De a gyakorlatban az állandók igazán számítanak” – mondta. "A való világban a 10-es tényező a játék végét jelenti."

A tényleges hash táblák még mindig javulnak anyagi szempontból, még akkor is, ha messze elmaradnak az elméleti ideálistól. Például egy új hash tábla, melynek neve IcebergHT, amelyet Bender, Kuszmaul és mások építettek, sokkal jobb, mint elődei. Kuszmaul szerint kétszer olyan gyors, mint a ma elérhető leghelytakarékosabb hash-tábla, és háromszor kevesebb helyet foglal el, mint a leggyorsabb hash-tábla.

Mitzenmacher reméli, hogy a 2023-as eredmény hamarosan másfajta haszonnal járhat: „Amikor új alsó határt kap – különösen, amelyik új technikákat foglal magában –, mindig van remény arra, hogy felhasználhatja… kapcsolódó problémákra.”

Az intellektuális elégedettség is abból fakad, ha tudod, hogy megoldottál egy nehéz és régóta fennálló problémát – mondta az informatikus. Piotr Indyk a Massachusetts Institute of Technology munkatársa. "Ha biztos abban, hogy bizonyos adatstruktúrákon nem lehet javítani, ez segíthet a kutatási erőfeszítések összpontosításában." Végül az adatkutatók elterelhetik figyelmüket Peterson kihívásáról, és az elméleti számítástechnika új problémáira összpontosíthatnak, amelyekből nincs hiány.