Perché LevelDB richiede più di due livelli?

Question

Penso che solo due livelli (livello-0 e livello-1) siano ok, perché LevelDB ha bisogno di livello 2, livello 3 e altro?

Answer 1

Ti indicherò la direzione di alcuni articoli su LevelDB e la struttura di archiviazione sottostante.

Quindi nello documentation for LevelDB si discute di unioni tra livelli.

Queste unioni hanno l'effetto di migrare gradualmente i nuovi aggiornamenti dal livello dei giovani al livello più grande utilizzando solo le letture e le scritture di massa (ovvero, riducendo al minimo i costi di ricerca).

LevelDB è simile nella struttura a Log Structured Merge Trees. Il documento discute i diversi livelli se sei interessato all'analisi di esso. Se riesci a superare la matematica, sembra essere la soluzione migliore per comprendere la struttura dei dati.

Un molto più facile da leggere analysis di LevelDB parla rapporto del datastore per LSM alberi, ma in termini di vostre domande su tutti i livelli che dice è:

Infine, avendo centinaia di SSTables su disco è Inoltre non è una grande idea, quindi periodicamente eseguiremo un processo per unire gli SSTables su disco.

Probabilmente la documentazione LevelDB fornisce la migliore risposta: (massimizzando la dimensione dei scrive e legge, dal momento che è LevelDB su disco (lenta memorizzazione dei dati cercare)).

Buona fortuna!

Answer 2

Penso che si tratti principalmente di una fusione facile e rapida dei livelli.

In Leveldb, il livello (i + 1) ha ca. 10 volte i dati rispetto al livello-i. Questo è più analogo a una struttura di cache multilivello in cui, se il database ha 1000 record tra le chiavi da x1 a x2, 10 tra quelli con accesso più frequente in tale intervallo si troveranno nel livello 1 e 100 nello stesso intervallo sarebbe nel livello 2 e resto nel livello 3 (questo non è esatto ma solo per dare un'idea intuitiva dei livelli). In questa configurazione, per unire un file in level-i dobbiamo guardare al massimo 10 file in level- (i + 1) e può essere tutto portato in memoria, una fusione veloce fatta e riscritta. Questi risultati nella lettura di blocchi di dati relativamente piccoli per ogni operazione di compattazione/fusione.

D'altra parte se avevi solo 2 livelli, l'intervallo di chiavi in ​​un file di livello 0 potrebbe potenzialmente corrispondere a 1000 di file nel livello 1 e tutti devono essere aperti per la fusione che sarà piuttosto lento. Si noti che un importante presupposto qui è che abbiamo risolto i file di dimensioni (ad esempio 2 MB). Con file di lunghezza variabile nel livello 1, la tua idea potrebbe ancora funzionare e penso che una variante di questo sia utilizzata in sistemi come HBase e Cassandra.

Ora, se la preoccupazione riguarda il ritardo di ricerca con molti livelli, anche in questo caso si tratta di una struttura cache multilivello, i dati scritti più di recente si trovano in livelli più alti per aiutare con la tipica località di riferimento.

Answer 3

Il livello 0 è un dato in memoria altri livelli sono dati del disco. La parte importante è che i dati nei livelli sono ordinati. Se level1 consiste di 3 file 2Mb, in file1 sono i tasti 0..50 (ordinati) nel file2 150..200 e nel file3 300..400 (come esempio). Quindi, quando il livello di memoria è pieno, è necessario inserire i dati sul disco nel modo più efficiente, ovvero la scrittura sequenziale (utilizzando il minor numero di ricerche possibile sul disco).Immaginiamo in memoria che abbiamo i tasti 60-120, cool, li scriviamo solo in sequenza come file che diventa file2 in level1. Molto efficiente! Ma ora immagina che level1 sia molto più grande di level0 (che è ragionevole dato che il livello0 è la memoria). In questo caso ci sono molti file in level1. E ora le nostre chiavi in ​​memoria (60-120) appartengono a molti file poiché l'intervallo chiave in level1 è a grana molto fine. Ora per unire level0 con level1 dobbiamo leggere molti file e fare un sacco di ricerche casuali, creare nuovi file in memoria e scriverli. Quindi è qui che entra in gioco l'idea di molti livelli, avremo molti livelli, ognuno un po 'più grande del precedente (x10), ma non molto più grande quindi quando dobbiamo migrare i dati da i-1 a i-esimo strato abbiamo un buone possibilità di leggere meno quantità di file.

Ora, poiché i dati potrebbero cambiare, potrebbe non essere necessario propagarlo a livelli più elevati (potrebbe essere modificato o eliminato) e quindi evitiamo del tutto fusioni costose. I dati che finiscono nell'ultimo livello sono statisticamente meno suscettibili di cambiare, quindi è la soluzione migliore per il più costoso da unire con l'ultimo livello.