Gli scienziati trovano l'equilibrio ottimale tra archiviazione dei dati e tempo | Rivista Quanti

Circa 70 anni fa, un ingegnere dell’IBM di nome Hans Peter Luhn cambiò silenziosamente il corso dell’informatica. Luhn deteneva già numerosi brevetti, tra cui uno per un dispositivo in grado di misurare il numero di fili di un tessuto e un altro per una guida che determinava quali bevande miste si potevano preparare dagli ingredienti della propria cucina. Ma in un documento interno dell’IBM del 1953, propose una nuova tecnica per archiviare e recuperare le informazioni che ora è integrata in quasi tutti i sistemi computazionali: la tabella hash.

Le tabelle hash sono una classe importante di strutture dati. Offrono un metodo particolarmente conveniente per accedere e modificare le informazioni in enormi database. Ma questa tecnologia comporta un inevitabile compromesso.

In un 1957 carta pubblicato nella Giornale IBM di ricerca e sviluppo, W. Wesley Peterson ha identificato la principale sfida tecnica posta dalle tabelle hash: devono essere veloci, nel senso che possono recuperare rapidamente le informazioni necessarie. Ma devono anche essere compatti e utilizzare la minor quantità di memoria possibile. Questi due obiettivi gemelli sono fondamentalmente in contrasto. L'accesso e la modifica a un database possono essere eseguiti più rapidamente quando la tabella hash ha più memoria; e le operazioni diventano più lente nelle tabelle hash che utilizzano meno spazio. Da quando Peterson ha lanciato questa sfida, i ricercatori hanno cercato di trovare il miglior equilibrio tra tempo e spazio.

Gli informatici hanno ora dimostrato matematicamente di aver trovato il compromesso ottimale. La soluzione è venuta da a coppia di recente documenti che si completavano a vicenda. “Questi documenti risolvono l’annosa questione aperta sui migliori compromessi spazio-temporali possibili, producendo risultati profondamente sorprendenti che mi aspetto avranno un impatto significativo per molti anni a venire”, ha affermato Michael Mitzenmacher, uno scienziato informatico dell'Università di Harvard che non è stato coinvolto in nessuno dei due studi.

"Direi sicuramente che è un grosso problema", ha aggiunto Rasmus Pagh, uno scienziato informatico presso l'Università di Copenaghen. “Molte persone hanno lavorato su questo problema, cercando di vedere quanto è possibile spremere lo spazio e allo stesso tempo eseguire operazioni efficienti in termini di tempo. Questo è quello che mi sarebbe piaciuto risolvere.

Farne un hash

Le tabelle hash sono tra le strutture dati più antiche, semplici, veloci e maggiormente utilizzate oggi. Sono progettati per eseguire tre operazioni fondamentali: inserimenti, che aggiungono nuovi elementi al database; query, che accedono a un elemento o verificano se esiste; ed eliminazioni. Una tabella hash può essere effimera, ovvero esiste solo finché viene eseguito un particolare programma, oppure può essere una parte permanente del sistema operativo del computer. Un browser Web come Chrome o Safari può avere più tabelle hash integrate destinate a tenere traccia di diversi tipi di dati.

Le voci in una tabella hash vengono archiviate in coppie, con l'elemento (l'informazione stessa) collegato a una chiave che identifica l'informazione. Inserisci una chiave nell'algoritmo di query di una tabella hash e ti porterà direttamente all'elemento. Potrebbe non sembrare così straordinario, ma per database enormi può essere un grande risparmio di tempo.

Per fare un esempio estremamente semplificato, consideriamo l’Oxford English Dictionary, che contiene le definizioni di oltre 600,000 parole. Se un'edizione digitale si basa su una tabella hash, puoi semplicemente utilizzare una determinata parola come chiave e procedere direttamente alla definizione. Senza una tabella hash, il dizionario probabilmente farebbe affidamento su un meccanismo di ricerca molto più lento, utilizzando un processo di eliminazione per convergere infine sulla definizione richiesta. E mentre una tabella hash può trovare qualsiasi parola in un periodo di tempo costante (di solito una piccola frazione di secondo), il tempo di ricerca per altri metodi può aumentare man mano che aumenta il numero di parole nel dizionario. Una tabella hash offre anche un altro vantaggio: può mantenere dinamico il dizionario, facilitando l'inserimento di nuove parole e l'eliminazione di quelle obsolete.

I ricercatori hanno trascorso decenni a costruire tabelle hash che tentassero di massimizzare la velocità e ridurre al minimo la memoria. Nel 20° secolo, le soluzioni tendevano a offrire vantaggi significativi in ​​un solo aspetto, tempo o spazio. Poi, nel 2003, i ricercatori ha mostrato che teoricamente era possibile fare un grande salto di efficienza sia nel tempo che nello spazio simultaneamente. Ci vorranno altri due decenni, tuttavia, prima che i ricercatori trovino l’equilibrio ideale tra i due.

La mescolanza dei dati

Il primo passo importante verso questo obiettivo è avvenuto nel 2022 a importante convegno di informatica A Roma. Lì, un team ha proposto una tabella hash con nuove funzionalità che potrebbero offrire la migliore combinazione di efficienza in termini di tempo e spazio mai concepita. Il primo autore dell'articolo (elencato in ordine alfabetico) è stato Michael Bender della Stony Brook University, quindi è comunemente indicato come Bender et al. tabella hash. Anche se il team non ha provato a costruire una tabella hash funzionante, ha dimostrato che, in linea di principio, potrebbe essere costruita con le caratteristiche descritte.

Per valutare la tabella hash creata, il gruppo ha prodotto una curva di compromesso, un grafico che traccia il tempo per operazione (inserimento o cancellazione) su un asse e lo spazio occupato dalla memoria sull'altro. Ma questo grafico definisce lo spazio in un modo speciale: a causa del modo in cui sono costruite, le tabelle hash necessitano di più memoria rispetto al minimo indispensabile per archiviare un dato insieme di elementi. Gli informatici chiamano questo spazio extra “pezzi sprecati”, anche se in realtà non sono sprecati e sono, in una certa misura, necessari. L'asse spaziale su una curva di compromesso misura il numero di bit sprecati per chiave.

Analizzando una curva di compromesso, i ricercatori possono calcolare il tempo più veloce possibile per una tabella hash che utilizza una determinata quantità di spazio. Possono anche capovolgere la domanda per individuare lo spazio più piccolo possibile per un determinato tempo di operazione. Di solito, un piccolo cambiamento in una variabile porterà a un piccolo cambiamento nell’altra William Kuszmaul, informatico teorico ad Harvard e coautore dell'articolo del 2022. "Se raddoppi il tempo, forse dimezzerai il numero di bit sprecati per chiave."

Ma non è il caso della tabella hash che hanno progettato. "Se si aumenta leggermente il tempo, i bit sprecati per tasto diminuiscono in modo esponenziale", ha affermato Kuszmaul. La curva di trade-off era così ripida da essere letteralmente fuori scala.

Il team ha costruito la tabella hash in due parti. Avevano una struttura dati primaria, in cui gli elementi vengono archiviati senza alcun bit sprecato, e una struttura dati secondaria, che aiuta una richiesta di query a trovare l'elemento che sta cercando. Anche se il gruppo non ha inventato il concetto di struttura dati secondaria, ha fatto una scoperta cruciale che ha reso possibile la realizzazione di una tabella hash iperefficiente: l'efficienza complessiva della memoria della struttura dipende da come la struttura primaria organizza i suoi elementi archiviati.

L'idea di base è che ogni articolo nella struttura primaria abbia posizioni di archiviazione preferite: una posizione migliore, una seconda migliore, una terza migliore e così via. Se un elemento è nella sua posizione migliore, gli viene apposto il numero 1 e quel numero viene memorizzato nella struttura dati secondaria. In risposta a una query, la struttura secondaria fornisce solo il numero 1, che indica l'esatta posizione dell'elemento nella struttura primaria.

Se l'elemento si trova al centesimo posto migliore, la struttura dati secondaria allega il numero 100. E poiché il sistema utilizza il codice binario, rappresenta il numero 100 come 100. Naturalmente, per memorizzare il numero 1100100 è necessaria più memoria di 1100100 — il numero assegnato a un articolo quando si trova nella posizione migliore. Differenze del genere diventano significative se si memorizzano, ad esempio, un milione di articoli.

Il team si è quindi reso conto che se si spostano continuamente gli elementi della struttura dati primaria nelle posizioni preferite, è possibile ridurre in modo significativo la memoria consumata dalla struttura secondaria senza dover aumentare i tempi di query.

"Prima di questo lavoro, nessuno si era reso conto che era possibile comprimere ulteriormente la struttura dei dati spostando le informazioni", ha affermato Pagh. "Questa è stata la grande intuizione del documento di Bender."

Gli autori hanno dimostrato che la loro invenzione stabiliva un nuovo limite superiore per le tabelle hash più efficienti, il che significa che si trattava della migliore struttura dati mai concepita in termini di efficienza sia temporale che spaziale. Ma restava la possibilità che qualcun altro potesse fare ancora meglio.

Destinato al successo

L'anno successivo, una squadra guidata da Huacheng Yu, uno scienziato informatico dell'Università di Princeton, ha cercato di migliorare la tabella hash del team Bender. "Abbiamo lavorato davvero duro e non potevamo farcela", ha detto Renfei Zhou, studente dell'Università Tsinghua di Pechino e membro del team di Yu. “È stato allora che abbiamo sospettato che il loro limite superiore fosse [anche] un limite inferiore” – il meglio che si possa ottenere. "Quando il limite superiore è uguale al limite inferiore, il gioco finisce e tu hai la tua risposta." Non importa quanto tu sia intelligente, nessuna tabella hash può fare di meglio.

Il team di Yu ha utilizzato una nuova strategia per scoprire se quell'intuizione era corretta calcolando un limite inferiore a partire dai principi primi. In primo luogo, hanno pensato che per eseguire un inserimento o una cancellazione, una tabella hash – o, in realtà, qualsiasi struttura dati – deve accedere alla memoria del computer un certo numero di volte. Se riuscissero a calcolare il numero minimo di volte necessario per una tabella hash efficiente in termini di spazio, potrebbero moltiplicarlo per il tempo richiesto per accesso (una costante), dando loro un limite inferiore al tempo di esecuzione.

Ma se non sapessero nulla della tabella hash (tranne che era efficiente in termini di spazio), come avrebbero potuto calcolare il numero minimo di volte richiesto per accedere alla memoria? Lo hanno derivato puramente dalla teoria, utilizzando un campo apparentemente non correlato chiamato teoria della complessità della comunicazione, che studia quanti bit sono necessari per trasmettere informazioni tra due parti. Alla fine, il team ci è riuscito: ha calcolato quante volte una struttura dati deve accedere alla sua memoria per operazione.

Questo è stato il loro risultato chiave. Sono stati quindi in grado di stabilire un limite inferiore del tempo di esecuzione per qualsiasi tabella hash efficiente in termini di spazio. E hanno visto che corrispondeva esattamente alla tabella hash di Bender. "Abbiamo pensato che [all'inizio] potesse essere migliorato", ha detto Zhou. "Si è scoperto che ci sbagliavamo." Ciò, a sua volta, significava che il problema di Peterson era stato finalmente risolto.

Oltre a rispondere a una domanda vecchia di decenni, ha detto Kuszmaul, la cosa sorprendente della prova di Yu è la sua generalità. “Il loro limite inferiore si applica a tutte le possibili strutture di dati, comprese quelle che non sono ancora state inventate”. Ciò significa che nessun metodo di archiviazione dei dati potrà mai battere la tabella hash di Bender in termini di memoria e velocità.

Hashing nel futuro

Nonostante l'efficienza senza precedenti della nuova tabella hash, è probabile che nessuno provi a costruirla a breve. È semplicemente troppo complicato da costruire. “Un algoritmo veloce in teoria non è necessariamente veloce nella pratica”, ha detto Zhou.

Non è insolito che tali divari tra teoria e pratica persistano a lungo, ha detto Kuszmaul, perché i teorici tendono a ignorare i fattori costanti. Il tempo necessario per eseguire un'operazione viene generalmente moltiplicato per un numero, una costante il cui valore esatto può essere irrilevante da un punto di vista teorico. "Ma in pratica, le costanti contano davvero", ha detto. "Nel mondo reale, un fattore 10 indica la fine del gioco."

Le attuali tabelle hash stanno ancora migliorando in termini materiali, anche se sono molto al di sotto dell'ideale teorico. Ad esempio, una nuova tabella hash chiamata IcebergHT, costruito da Bender, Kuszmaul e altri, è di gran lunga migliore dei suoi predecessori. Secondo Kuszmaul, è due volte più veloce della tabella hash più efficiente in termini di spazio oggi disponibile e utilizza tre volte meno spazio della tabella hash più veloce.

Mitzenmacher spera che il risultato del 2023 possa presto portare un altro tipo di beneficio: “Ogni volta che si ottiene un nuovo limite inferiore – specialmente uno che coinvolge alcune nuove tecniche – c’è sempre la speranza che si possano usare… per problemi correlati”.

C'è anche la soddisfazione intellettuale che deriva dal sapere di aver risolto un problema difficile e di lunga data, ha detto l'informatico Piotr Indyk del Massachusetts Institute of Technology. "Una volta che si è sicuri che determinate strutture di dati non possano essere migliorate, ciò può aiutare a concentrare gli sforzi di ricerca." Infine, i ricercatori di dati possono distogliere la loro attenzione dalla sfida di Peterson e concentrarsi su nuovi problemi di informatica teorica, di cui non mancano certo.