Ampio elenco di liste a doppio collegamento (o altro) su disco per il sistema di code; opzioni su come conservare

5

Sto cercando di creare una libreria di accodamento messaggi in Go, che verrà utilizzata come parte di un'applicazione più grande. Una lista doppiamente collegata sembra un approccio ragionevole per una struttura di dati in memoria, ma diciamo che questo elenco cresce di 4 milioni di elementi e ogni elemento è 10k, le cose non sono più garantite per la memoria, più ne ho bisogno essere persistente durante i riavvii.

La maggior parte dell'attività in coda sarà scritta fino alla fine e verrà letta e cancellata dall'inizio, tuttavia ci sono casi in cui il consumo di un messaggio potrebbe fallire per ragioni non correlate alla coda e l'elemento deve essere spostato nel fine della coda.

Ho familiarità con alcune strutture dati che funzionano bene su disco per altri casi specifici. Un albero di unione strutturato log sembra essere ottimo per i dati di accesso casuale, ma non quando le letture e le scritture sono localizzate alla fine e all'inizio dell'albero (in base alla mia comprensione). Anche B Trees e B + Trees sembrano destinati ad accessi e attraversamenti casuali.

Curioso quali algoritmi o approcci esistano già personalizzati per questo problema.

NOTA: Per quanto riguarda SQLite, una delle mie preoccupazioni è il tempo di compattazione. È probabile che i contenuti della coda abbiano un turnover molto elevato ed è importante che qualsiasi tipo di compattazione che deve essere eseguita possa avvenire su un set di dati abbastanza grande senza un impatto sulle prestazioni molto ampio. Cioè se ci sono 4G di messaggi in coda, non voglio uno scenario in cui le cose si bloccano per 2 minuti mentre compattano, il che è ciò che sospetto succederà con SQLite.

    
posta Brad Peabody 01.06.2017 - 21:36
fonte

3 risposte

3

Penso di avere abbastanza informazioni per fornire una risposta. Potrebbe non essere quello che stai cercando, però.

Da quello che abbiamo discusso e ho capito, abbiamo il seguente scenario:

  • Numero elevato di messaggi da elaborare;
  • Persistenza necessaria per gestire i reboot puliti (non sto parlando di sbalzi di tensione o interruzioni di corrente);
  • Dimensione incoerente di ciascun messaggio;
  • Una necessità per la struttura FIFO;
  • Possibilità di utilizzare il filesystem come archivio;
  • Necessario essere portatili, all'interno di ambienti supportati (MacOS, Linux, Windows);
  • È necessario essere auto-ospitati, non è possibile utilizzare un fornitore di code esterne;

Detto questo, progetterei qualcosa che si baserebbe al 100% sul filesystem.

Memorizza ogni messaggio come un singolo file, assegna loro un timestamp o un contatore che puoi controllare da una fonte affidabile e sfruttare le capacità del filesystem per te.

Sarai limitato da ciò che il filesystem può fare per te (numero di file per directory, numero di directory per disco, dimensione massima per file, ecc.), ma è molto flessibile, facile da debugare e monitorare ed estremamente portatile e flessibile, che ti consente di aumentare la velocità del tuo IO semplicemente cambiando l'hardware (HD - > SSD - > Raid - > Storage Server, ecc.).

Dovrai studiare diversi filesystem per spingere ciascuno al limite, ma i più comuni possono gestire questi requisiti molto bene:

Dati di seguito copiati dall'eccellente risposta su StackOverflow :

FAT32 :

  • Numero massimo di file: 268.173.300
  • Numero massimo di file per directory: 2 16 - 1 (65.535)
  • Dimensione massima del file: 2 GiB - 1 senza LFS , 4 GiB - 1 con

NTFS :

  • Numero massimo di file: 2 32 - 1 (4.294.967.295)
  • Dimensione massima del file
    • Implementazione: 2 44 - 2 6 byte (16 TiB - 64 KiB)
    • Teorico: 2 64 - 2 6 byte (16 EiB - 64 KiB)
  • Dimensione massima del volume
    • Implementazione: 2 32 - 1 cluster (256 TiB - 64 KiB)
    • Teorico: 2 64 - 1 cluster

ext2 :

  • Numero massimo di file: 10 18
  • Numero massimo di file per directory: ~ 1.3 × 10 20 (problemi di prestazioni passati 10.000)
  • Dimensione massima del file
    • 16 GiB (dimensione blocco di 1 KiB)
    • 256 GiB (dimensione blocco di 2 KiB)
    • 2 TiB (dimensione blocco di 4 KiB)
    • 2 TiB (dimensione blocco di 8 KiB)
  • Dimensione massima del volume
    • 4 TiB (dimensione blocco di 1 KiB)
    • 8 TiB (dimensione blocco di 2 KiB)
    • 16 TiB (dimensione blocco di 4 KiB)
    • 32 TiB (dimensione blocco di 8 KiB)

ext3 :

  • Numero massimo di file: min (volumeSize / 2 13 , numberOfBlocks)
  • Dimensione massima del file: uguale a ext2
  • Dimensione massima del volume: uguale a ext2

ext4 :

  • Numero massimo di file: 2 32 - 1 (4.294.967.295)
  • Numero massimo di file per directory: illimitato
  • Dimensione massima del file: 2 44 - 1 byte (16 TiB - 1)
  • Dimensione massima del volume: 2 48 - 1 byte (256 TiB - 1)
risposta data 02.06.2017 - 18:34
fonte
1

Un altro modo per approcciare questo è semplicemente memorizzare i messaggi in blocchi di dimensioni ragionevoli, e ogni blocco è memorizzato in un file su disco, e può essere letto (o possibilmente mem-mappato) per l'uso in memoria quando necessario .

I blocchi potrebbero essere, ad esempio, 64 MB ciascuno. Ciascuno è un file, denominato con timestamp e numero casuale. Lo scopo di raggruppare i messaggi è di evitare la proliferazione di piccoli messaggi dalla creazione di un collo di bottiglia a livello di file system. Se il numero di messaggi raggiunge i milioni, potrebbe risultare difficile navigare in modo efficiente su FS per trovare il primo e l'ultimo messaggio. Le dimensioni dei blocchi devono essere più grandi del messaggio più grande possibile e devono essere garantite per adattarle alla memoria almeno alcune alla volta.

È possibile utilizzare il prefisso delle cartelle per semplificare la navigazione. Cioè se il timestamp del file è 201706021852, allora potrebbe vivere nella cartella 20170602/18. Il prefisso potrebbe essere configurabile per diversi volumi di messaggi previsti, se necessario.

Quando i blocchi vengono letti in memoria, una lista doppiamente collegata funzionerebbe come rappresentazione in memoria. Il primo e l'ultimo blocco dovrebbero essere facilmente reperibili sul disco eseguendo la scansione della struttura delle cartelle, questi blocchi vengono caricati in memoria e quindi le versioni in memoria hanno funzionato - i messaggi vengono spostati sul retro e spuntati dalla parte anteriore. I messaggi in un blocco quando sono consumati possono semplicemente essere contrassegnati come tali e quando tutti i messaggi nel blocco vengono consumati il blocco viene eliminato.

A qualunque intervallo sia appropriato, i blocchi caricati vengono scaricati su disco e tutto fsync () ed. Le operazioni che sono garantite come atomiche (rinomina) verrebbero utilizzate per sapere in modo affidabile se la scrittura è stata eseguita correttamente.

La struttura sopra dovrebbe funzionare bene se non hai mai bisogno di trovare un messaggio nel mezzo della coda (che richiederebbe una scansione completa di tutti i blocchi).

    
risposta data 03.06.2017 - 05:57
fonte
0

E l'ennesima soluzione sarebbe semplicemente utilizzare una tabella SQLite. Internamente SQLite utilizza alberi binari sia per i dati delle tabelle che per gli indici (non ottimizzati in modo specifico per letture e scritture pesanti e pesanti, ma anche non particolarmente inefficienti). E riutilizzerà le pagine che diventano completamente disponibili. Potrebbe benissimo essere che SQLite svolgerà il lavoro con prestazioni ragionevoli e non richiederà mai la compattazione (dal momento che una coda che viene consumata in sequenza dovrebbe in teoria rimuovere completamente le pagine complete, poiché tutti i record verranno eliminati in sequenza). Deve essere testato.

    
risposta data 03.06.2017 - 06:08
fonte

Leggi altre domande sui tag