Algoritmi per l'ottimizzazione con Fast Disk Storage (SSD)?

Question

Dato che i dischi a stato solido (SSD) stanno diminuendo di prezzo e presto diventeranno più prevalenti come unità di sistema, e dato che i loro tassi di accesso sono significativamente più elevati rispetto ai supporti magnetici rotanti, quali algoritmi standard otterranno prestazioni dall'uso degli SSD per l'archiviazione locale? Ad esempio, l'alta velocità di lettura casuale degli SSD rende qualcosa come un hash basato su disco una viabilità per i grandi hash; 4 GB di spazio su disco sono prontamente disponibili, il che rende praticabile l'hashing dell'intero intervallo di un intero a 32 bit (più per la ricerca che per la popolazione, il che richiederebbe comunque molto tempo); mentre questa dimensione di un hashtable sarebbe proibitivo per lavorare con i media rotanti a causa della velocità di accesso, non dovrebbe essere un problema con gli SSD.

Esistono altre aree in cui la transizione imminente agli SSD fornirà potenziali vantaggi in termini di prestazioni algoritmiche? Preferisco vedere il ragionamento su come una cosa funzionerà piuttosto che un'opinione; Non voglio che questo diventi polemico.

Answer 1

L'esempio di hashtables è in effetti la struttura del database chiave che ne trarrà vantaggio. Invece di dover caricare un intero file da 4 GB o più in memoria per sondare i valori, l'SSD può essere esaminato direttamente. L'SSD è ancora più lento della RAM, per ordine di grandezza, ma è abbastanza ragionevole avere una tabella hash da 50 GB sul disco, ma non nella RAM, a meno che non si paghi un sacco di soldi per il grande ferro.

Un esempio sono i database di posizione degli scacchi. Ho oltre 50 GB di posizioni hash. C'è un codice complesso per provare a raggruppare le posizioni correlate l'una accanto all'altra nell'hash, così posso pagina in 10MB del tavolo alla volta e spero di riutilizzarne alcune per più query di posizione simili. C'è un sacco di codice e complessità per renderlo efficiente.

Sostituito con un SSD, sono stato in grado di eliminare tutta la complessità del clustering e utilizzare solo gli hash randomizzati davvero stupidi. Ho anche ottenuto un aumento delle prestazioni poiché recupero solo i dati di cui ho bisogno dal disco, non grandi blocchi da 10 MB. La latenza è effettivamente più grande, ma l'aumento della velocità è significativo .. e il codice super-pulito (20 linee, non 800+), è forse ancora più bello.

Answer 2

Non illuderti. Gli SSD sono ancora molto più lenti della memoria di sistema. Qualsiasi algoritmo che sceglie di usare la memoria di sistema sul disco fisso sarà comunque molto più veloce, a parità di tutte le altre cose.

Answer 3

Gli SSD sono significativamente più veloci per l'accesso casuale. Accesso sequenziale al disco sono due volte più performanti delle unità rotazionali tradizionali. Molti SSD hanno prestazioni peggiori in molti scenari che li inducono a peggiorare, come descritto here.

Mentre gli SSD spostano considerevolmente l'ago, sono ancora molto più lenti delle operazioni della CPU e della memoria fisica. Per il tuo esempio di tabella hash da 4 GB, potresti essere in grado di sostenere 250+ MB/s da un SSD per accedere a bucket hash casuali. Per un disco rotazionale, potresti essere fortunato a rompere il MB/s di una sola cifra. Se è possibile mantenere questa tabella hash da 4 GB in memoria, è possibile accedervi nell'ordine dei gigabyte al secondo, molto più velocemente di un SSD molto veloce.

L'articolo di riferimento elenca diverse modifiche apportate da MS per Windows 7 durante l'esecuzione su SSD, che può darti un'idea del tipo di modifiche che potresti prendere in considerazione. Innanzitutto, SuperFetch per il precaricamento dei dati su disco è disabilitato - è progettato per aggirare i tempi di accesso casuale lento per disco che sono alleviati dagli SSD. Defrag è disabilitato, perché i file sparpagliati sul disco non sono un problema di prestazioni per gli SSD.

Answer 4

Ipso facto, qualsiasi algoritmo a cui si possa pensare richiede un sacco di I/O su disco casuale (a caso è la parola chiave, che aiuta a lanciare il principio di località sugli uccelli, eliminando così l'utilità di un sacco di cache va avanti).

Potrei vedere alcuni sistemi di database che stanno ottenendo da questo però. MySQL, ad esempio utilizzando il motore di archiviazione MyISAM (dove i record di dati sono fondamentalmente glorificati CSV). Tuttavia, penso che gli hashtables molto grandi saranno la soluzione migliore per buoni esempi.

Answer 5

SSD sono molto più veloci per letture casuali, un po 'per letture sequenziali e correttamente più lento per le scritture (casuali o meno).

Quindi una tabella hash basata su disco è correttamente non utile con un SSD, poiché ora richiede molto tempo per aggiornarlo, ma la ricerca del disco diventa (rispetto a un normale hdd) molto economica.