Google Intervista Domanda

Question

Questa era una delle domande di Google Intervista.

Qual è il possibile problema se Hash Table cresce più di 30 GB (ignorare i problemi come la funzione di hash male)

non lo sapevo. Quale potrebbe essere una risposta soddisfacente?

Grazie

Answer 1

Alcuni problemi:

1. Hash Collision potrebbe essere uno dei maggiori problemi possibile.
2. Sarà inoltre inefficiente eseguire frequenti letture del disco quando i dati vengono archiviati nel disco come tabella hash.

Answer 2

penso che l'intervistatore si aspettava qualcosa sulle linee di Distributed Hash table, dal momento che una tabella hash da 30GB non può essere memorizzato su una singola macchina (almeno nel mondo attuale 64 bit); Dalla mia esperienza personale, alcune delle Qs di google ruotano attorno al calcolo distribuito, alla riduzione delle mappe, ecc.,

Answer 3

La risposta dipende in parte dal fatto che stiano parlando di una classica implementazione di hashtable (come HashTable/HashMap in Java) o qualcosa di più sofisticato. Alla fine, 30 GB di memoria sono ancora abbastanza grandi per una singola macchina/VM per gli standard odierni.

Quindi, pensare a quello che sta succedendo sotto:

1. Deve leggere scrivere in una posizione arbitraria in qualche massiccia serie.
2. Deve crescere se si riempie oltre una certa misura; vedi 'load factor' in implementazione Java.
3. In una garbage collection lingua/implementazione, tutti gli oggetti memorizzati nella tabella hash devono essere ispezionati dal garbage collector

che conduce alle seguenti problemi:

1. Non è chiaro che anche i sistemi operativi odierni gestiscono bene l'allocazione di blocchi di memoria nelle decine di GB
2. Per semplicità, dite che metà della tabella è stata effettivamente utilizzata dalla tabella stessa (non gli oggetti chiave e valore). Quindi c'è un array da 15 GB all'interno. Pertanto, ogni volta che la tabella cresce, è necessario allocare almeno 15 gb
3. Anche se è stata allocata una decina di array GB, il sistema operativo visualizza una parte di questa memoria. Dato che stiamo assumendo una buona funzione di hash, interromperemo il caching delle pagine se usiamo la maggior parte dei dati nell'array. Ci saranno molti errori di pagina.
4. Diciamo che non utilizzare utilizzare tutti i dati. Alcuni tasti sono usati frequentemente, altri no. Per illustrare, dì che ogni valore-chiave è piccolo - 128 byte. E per semplicità, diciamo che archiviamo tutti i valori nella tabella hash come valori. Quindi 30G/128 = ~ 250 milioni di voci. Ma diciamo 25k tasti comunemente usati. (25k/250M = 0,01%). Ma con una buona funzione di hash, questi sarebbero equamente distribuiti attraverso l'enorme array. Anche con dimensioni di pagina ridotte - ad esempio 4kb, 25K (voci) * 128 byte (dimensione della voce) = ~ 3.5 Mb di dati comunemente usati ci costa 25K (voci) * 4K (dimensione della pagina) = ~ 100 MB di memoria che deve essere conservata all'interno ... con un'efficienza del 3,5%!
5. Nel mondo Java, i professionisti non consigliano dimensioni di heap più grandi di 4 - 8 GB. Certo, ci sono cose come Azul, ma ciò dimostra semplicemente il punto: un garbage collector tipico non si adatta molto bene a queste dimensioni.

Sono d'accordo con gli altri poster che Google sta cercando distribuiti come soluzione. Ma penso che al centro, un semplice hashtable smette di ridimensionarsi oltre un punto. In precedenza,

1. Si dovrebbe distribuire se tutte le voci sono accessibili in modo relativamente uniforme
2. Se alcuni sono accessibili la maggior parte del tempo, con due mappe (una per più usata) può comprare una sacco.
3. Nel mondo Java, l'utilizzo di mappe specializzate che archiviano i dati dall'heap possono comprarti anche le prestazioni; vedi Peter Lawrey's work per esempio.
4. Anche semplicemente lo striping dell'array sottostante in un hashtable (come fa ConcurrentHashMap di Java) può offrirti importanti miglioramenti quando devi aumentare la tabella hash.