Sto cercando di costruire un negozio con valore-chiave (per imparare, sono uno studente) che servirebbe da livello di persistenza per le applicazioni software. Ho esaminato la letteratura del database e mi sono immerso un po 'negli interni di LevelDB e SQLite. Ecco i miei obiettivi:
-
Nessuna dimensione del cappuccio sulla dimensione di chiavi o valori
-
Nessun vincolo sui tipi di chiavi o valori
-
Riduci al minimo le costose operazioni del disco
-
Grazia sotto pressione (scrivere applicazioni intensive)
-
Controlli di appartenenza veloci
E in seguito è il design che ho creato. Innanzitutto una rapida dichiarazione di non responsabilità per farti sapere che mi sembra una cattiva pratica per un'app di produzione fare affidamento su un formato di database non testato non sottoposto a peer review. Come ho detto, sono solo uno studente che cerca di imparare di più anche se voglio fare le cose nel modo migliore possibile.
Dato che vogliamo consentire chiavi / valori di dimensioni illimitate, ho pensato che utilizzare una funzione di hash per ottenere un identificatore di chiave normalizzato e univoco sarebbe utile. Non ho cercato quale funzione di hash sarebbe più adatta quindi supporremo che usiamo FNV-1a dove ogni hash risultante è 8 bytes .
La mia strategia per gestire la collisione non è ancora ben definita, devo indagare e vedere che sarebbe una buona idea tenere una tabella di collisione mappata in memoria o piuttosto aggiungere un puntatore al mio record di metadati ( [collision: uint8 1 byte][offset: uint64 8 bytes][reserved: 1 byte] )
Quindi abbiamo key := input() e hKey := hash(key) a cui è assegnato un value memorizzato su disco in <value of hKey>.db . Chiamiamo quel file a hashfile .
Registra i metadati memorizzati nei primi 12 byte di un file hash:
[total_size: uint64 8 bytes][overflow_pointer: uint16 2 bytes][size_chunk: uint16 2 bytes]
E di seguito è riportato un record di valori, che segue direttamente i metadati: [valore: blockSize - 32 byte]
Qui blockSize := 4096B
Consentiamo di memorizzare fino a 4096B (o qualsiasi altra dimensione del blocco del disco) in un hashfile. Se il valore è maggiore di questo, incrementiamo overflow_pointer e memorizziamo il resto del valore in un nuovo hashfile <overflow_pointer>_<value hKey>.db . E così via fino a quando value è esaurito. Questo è un punto del design di cui sono più incerto: sarebbe più efficiente o pratico archiviarlo nello stesso file?
Ho intenzione di fare in modo che un processo watcher cerchi casi in cui un insieme di chiavi adiacenti contiene piccoli blocchi di dati e può essere unito per formare un bucket. Ma questo è per dopo.
Inoltre, poiché gli hash hanno una larghezza di soli 8 byte, ho intenzione di mantenere un indice mappato in memoria di hashfiles per fornire controlli rapidi sull'appartenenza.
Per favore fatemi sapere cosa ne pensate, non vedo l'ora di sentirvi tutti!