Nell'autunno del 2019, nel team di iOS di Mail.ru Cloud, si è verificato un evento molto atteso. La principale base di dati per la memorizzazione persistente dello stato dell'app è diventata piuttosto esotica per il mondo mobile. (LMDB). Di seguito, vi proponiamo una panoramica dettagliata in quattro parti. Iniziamo a parlare delle ragioni di una scelta così inusuale e difficile. Poi passeremo a esaminare i tre pilastri dell'architettura LMDB: file mappati in memoria, B+-tree, e l'approccio copy-on-write per l'implementazione della transazionalità e della multi-versioning. Infine, per concludere, la parte pratica. In essa esamineremo come progettare e implementare uno schema di database con più tabelle utilizzando l'API key-value di basso livello, compresi gli indici.
Contenuto
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motivazione dell'implementazione
Un giorno nel 2015 ci siamo preoccupati di misurare quanto spesso l'interfaccia della nostra applicazione avesse dei rallentamenti. Non ci siamo impegnati in questo per caso. Abbiamo ricevuto sempre più segnalazioni che l'applicazione a volte smette di rispondere alle azioni dell'utente: i pulsanti non si cliccano, le liste non scorrono, ecc. Sulla meccanica delle misurazioni sono su AvitoTech, quindi qui riporto soltanto l'ordine di grandezza.
I risultati delle misurazioni sono stati per noi un secchio di acqua fredda. Si è scoperto che i problemi causati dai blocchi erano molto più numerosi di qualsiasi altro. Se prima di comprendere questo fatto l'indicatore tecnico principale della qualità era l'assenza di crash, dopo il focus sull'assenza di freeze.
Dopo aver costruito e aver condotto e delle loro cause, è diventato chiaro che il nostro principale nemico era la pesante logica di business che veniva eseguita nel thread principale dell'applicazione. La reazione naturale a questo disguido è stata il vivo desiderio di distribuirla su thread lavorativi. Per una soluzione sistematica di questo problema abbiamo fatto ricorso a un'architettura multi-thread basata su attori leggeri. All'adattamento di questa per il mondo iOS ho dedicato sul nostro Twitter collettivo e . Nel contesto di questo racconto, voglio sottolineare quegli aspetti della soluzione che hanno influenzato la scelta del database.
Il modello attoriale dell'organizzazione del sistema implica che il multithreading diventi la sua seconda essenza. Gli oggetti del modello amano attraversare i confini dei thread. E lo fanno non occasionalmente e in alcune situazioni, ma praticamente costantemente e ovunque.
Il database è uno dei componenti chiave nello schema presentato. Il suo compito principale è l'implementazione del macropattern . Se nel mondo enterprise viene utilizzato per organizzare la sincronizzazione dei dati tra i servizi, nel caso di un'architettura attoriale — i dati tra i thread. In questo modo, avevamo bisogno di un database con cui lavorare in un ambiente multithreading senza nemmeno le più piccole difficoltà. In particolare, ciò significa che gli oggetti ottenuti da esso devono essere almeno thread-safe e, idealmente, immutabili. Come è noto, questi ultimi possono essere utilizzati simultaneamente da più thread senza alcun blocco, il che ha un effetto benefico sulle prestazioni.
Un secondo fattore significativo che ha influenzato la scelta del database è stata la nostra API cloud. È stata ispirata all'approccio di sincronizzazione adottato in git. Come esso, puntavamo a , che per i clienti cloud sembra più che appropriata. Si prevedeva che avrebbero scaricato una sola volta lo stato completo del cloud e poi la sincronizzazione nella stragrande maggioranza dei casi sarebbe avvenuta tramite l'applicazione delle modifiche. Purtroppo, questa possibilità è ancora solo in una zona teorica, mentre nella pratica i clienti non sono riusciti a lavorare con i patch. Ci sono diverse ragioni oggettive per questo, che, per non allungare l'introduzione, lasciamo da parte. Ora, tuttavia, sono molto più interessanti le conclusioni istruttive della lezione su ciò che accade quando l'API dice "A", e il suo consumatore non dice "B".
Quindi, se immaginate git, che durante l'esecuzione del comando pull invece di applicare patch a uno snapshot locale confronta il suo stato completo con quello completo del server, avrete un'idea piuttosto precisa di come avviene la sincronizzazione nei client cloud. Non è difficile dedurre che per realizzarla è necessario allocare in memoria due alberi DOM con meta-informazioni su tutti i file server e locali. Ne deriva che se un utente memorizza 500.000 file nel cloud, per la sua sincronizzazione è necessario ricreare e distruggere due alberi con 1 milione di nodi. E ogni nodo è un aggregato che contiene un grafo di sotto-oggetti. Da questa prospettiva, i risultati della profilazione sono stati attesi. È emerso che anche senza considerare l'algoritmica della fusione, la semplice procedura di creazione e successiva distruzione di un enorme numero di piccoli oggetti può risultare costosa. La situazione è complicata dal fatto che l'operazione di sincronizzazione di base è inclusa in un grande numero di scenari utente. Di conseguenza, registriamo il secondo criterio importante nella scelta del database: la possibilità di implementare operazioni CRUD senza allocazione dinamica di oggetti.
Altri requisiti sono più tradizionali e il loro elenco completo appare come segue.
- Thread safety.
- Multiprocesso. È dettato dalla necessità di utilizzare la stessa istanza del database per la sincronizzazione dello stato non solo tra i thread, ma anche tra l'applicazione principale e le estensioni iOS.
- Possibilità di rappresentare le entità memorizzate come oggetti immutabili.
- Assenza di allocazioni dinamiche all'interno delle operazioni CRUD.
- Supporto per le transazioni con proprietà di base : atomicità, coerenza, isolamento e affidabilità.
- Velocità nei casi d'uso più popolari.
Una buona scelta con questo insieme di requisiti è stata e rimane SQLite. Tuttavia, mentre esploravo alternative, mi è capitato tra le mani un libro . Sotto la sua guida è stato scritto un benchmark che confronta la velocità di lavoro con diversi database in scenari reali nel cloud. Il risultato ha superato le più audaci aspettative. Nei casi più popolari—ottenere un cursore per un elenco ordinato di tutti i file e un elenco ordinato di tutti i file per una directory specifica—LMDB si è rivelato essere dieci volte più veloce di SQLite. La scelta è diventata ovvia.
2. Posizionamento di LMDB
LMDB è una libreria molto piccola (solo 10K righe), che realizza il livello fondamentale più basso dei database—il datastore.
Il diagramma fornito mostra che confrontare LMDB con SQLite, che implementa anche livelli superiori, in effetti non è più corretto di quanto non sia confrontare SQLite con Core Data. Come concorrenti di pari dignità sarebbe più equo citare gli stessi motori di storage—BerkeleyDB, LevelDB, Sophia, RocksDB e altri. Ci sono persino sviluppi in cui LMDB funge da componente di storage engine per SQLite. Il primo di questi esperimenti è stato condotto nel 2012 Howard Chu . LumoSQL lo presentò a LinuxConfAu. L'uso principale di LMDB è come motore per database applicativi. La libreria deve la sua nascita agli sviluppatori di
OpenLDAP btree «Il database Lightning Memory-mapped» yleo «Il motore LMDB—un campione speciale» MDBX correzioni di bug. .
ha scelto ha preferito LMDB a SQLite per la memorizzazione degli indici.
Il motore è ora noto anche nel mondo dello sviluppo mobile. Le sue tracce possono nella client per iOS di Telegram. LinkedIn è andato ancora oltre e ha scelto LMDB come archivio predefinito per il framework di cache dei dati Rocket Data, su cui nel suo articolo nel 2016.
LMDB sta combattendo con successo per un posto al sole nel settore lasciato libero da BerkeleyDB dopo il passaggio sotto il controllo di Oracle. La libreria è apprezzata per la sua velocità e affidabilità, anche in confronto ai suoi simili. Come si sa, non ci sono pranzi gratis, e desidero sottolineare il trade-off che si presenterà nella scelta tra LMDB e SQLite. Lo schema sopra illustra chiaramente come venga raggiunta una velocità superiore. Prima di tutto, non paghiamo per strati aggiuntivi di astrazione sopra l'archiviazione su disco. È ovvio che in una buona architettura non si può fare a meno di essi, e appariranno inevitabilmente nel codice dell'applicazione, tuttavia saranno molto più leggeri. Non ci saranno funzionalità che non sono richieste dall'applicazione specifica, ad esempio, il supporto per le query SQL. In secondo luogo, si presenta l'opportunità di mappare in modo ottimale le operazioni applicative sulle richieste di archiviazione su disco. Se SQLite si basa sulle esigenze medie di un'applicazione media, voi come sviluppatori applicativi siete ben consapevoli degli scenari di carico principali. Per una soluzione più performante bisognerà pagare un prezzo maggiore sia per lo sviluppo della soluzione iniziale che per il suo successivo supporto.
3. I tre pilastri di LMDB
Guardando LMDB dall'alto, è giunto il momento di scendere più in profondità. Le prossime tre sezioni saranno dedicate all'analisi dei principali pilastri su cui poggia l'architettura dell'archivio:
- File mappati in memoria come meccanismo di gestione del disco e sincronizzazione delle strutture dati interne.
- B+-albero come organizzazione della struttura dei dati memorizzati.
- Copy-on-write come approccio per garantire le proprietà ACID delle transazioni e la multi-versione.
3.1. Pilastro n. 1. File mappati in memoria
I file visualizzati in memoria sono un elemento architettonico così importante che figurano anche nel nome del database. Le questioni relative alla cache e alla sincronizzazione dell'accesso alle informazioni archiviate sono completamente delegate al sistema operativo. LMDB non contiene alcuna cache interna. Questa è una decisione consapevole dell'autore, poiché la lettura dei dati direttamente dai file mappati consente di risparmiare notevolmente nella realizzazione del motore. Di seguito fornisco un elenco non esaustivo di alcuni di questi.
- Mantenere la coerenza dei dati nel database durante l'accesso da più processi diventa compito del sistema operativo. Nel prossimo capitolo, questa meccanica è trattata in dettaglio con illustrazioni.
- L'assenza di cache libera completamente LMDB da costi generali legati alle allocazioni dinamiche. La lettura dei dati, nella pratica, si traduce nell'impostare un puntatore sull'indirizzo corretto nella memoria virtuale e nient'altro. Sembra fantascienza, ma nel codice sorgente del database tutte le chiamate a salloc sono concentrate nella funzione di configurazione del database.
- L'assenza di cache implica anche l'assenza di blocchi legati alla sincronizzazione del loro accesso. I lettori, di cui può esistere un numero arbitrario contemporaneamente, non incontrano alcun mutex nel loro percorso verso i dati. Questo consente una velocità di lettura con un'ideale scalabilità lineare in base al numero di CPU. In LMDB, solo le operazioni modificative sono soggette a sincronizzazione. In un dato momento, può esserci solo un scrittore.
- Il minimo di logica di caching e sincronizzazione libera il codice da errori estremamente complessi, legati al funzionamento in un ambiente multi-thread. Alla conferenza Usenix OSDI 2014 ci sono stati due interessanti studi sui database: e . Da essi si possono trarre informazioni sulla straordinaria affidabilità di LMDB, così come sulla realizzazione praticamente impeccabile delle proprietà ACID delle transazioni, che supera quella di SQLite.
- La minimalità di LMDB consente che la rappresentazione in codice possa essere completamente ospitata nella cache L1 del processore, con le conseguenti caratteristiche di velocità.
Purtroppo, in iOS la gestione dei file mappati in memoria non è così semplice come si vorrebbe. Per discutere in modo più consapevole delle relative carenze, è necessario ricordare i principi generali di implementazione di questo meccanismo nei sistemi operativi.
Informazioni generali sui file mappati in memoria
Ogni applicazione eseguibile è associata a un'entità chiamata processo dall'operating system. A ogni processo viene assegnato un intervallo continuo di indirizzi, in cui deve memorizzare tutto il necessario per il suo funzionamento. Negli indirizzi più bassi si trovano le sezioni con il codice e i dati e risorse hardcoded. Poi c'è un blocco di spazio indirizzo dinamico, ben noto a noi come heap, che cresce verso l'alto. Esso contiene indirizzi di entità che compaiono durante l'esecuzione del programma. In cima c'è l'area di memoria utilizzata dallo stack dell'applicazione. Essa cresce e si contrae, insomma la sua dimensione ha una natura dinamica. Per evitare che lo stack e l'heap si sovrappongano e si disturbino, sono separati agli estremi opposti dello spazio indirizzo. Tra queste due sezioni dinamiche, in alto e in basso, c'è un intervallo vuoto. L'operating system utilizza gli indirizzi in questa zona intermedia per associare al processo le entità più varie. In particolare, può mappare a un certo insieme continuo di indirizzi un file presente su disco. Questo file è chiamato mappato in memoria.
Lo spazio indirizzo assegnato al processo è enorme. Teoricamente, il numero di indirizzi è limitato solo dalla dimensione del puntatore, determinata dalla bitness del sistema. Se la memoria fisica fosse mappata 1-a-1, il primo processo consumerebbe tutta la RAM, e non ci sarebbe spazio per il multitasking.
Tuttavia, dalla nostra esperienza sappiamo che i moderni sistemi operativi possono eseguire simultaneamente un numero qualsiasi di processi. Ciò è possibile perché, solo sulla carta, attribuiscono ai processi una grande quantità di memoria, mentre in realtà caricano nella memoria fisica principale solo la parte che è richiesta qui e ora. Per questo motivo, la memoria associata al processo è chiamata virtuale.
Il sistema operativo organizza la memoria virtuale e fisica in pagine di dimensioni specifiche. Non appena una certa pagina della memoria virtuale viene richiesta, il sistema operativo la carica nella memoria fisica e stabilisce una corrispondenza tra di esse in una tabella speciale. Se non ci sono slot liberi, una delle pagine precedentemente caricate viene copiata su disco, e quella richiesta prende il suo posto. Questa procedura, alla quale torneremo presto, è chiamata swapping. L'immagine qui sotto illustra il processo descritto. In essa, la pagina A con indirizzo 0 è stata caricata e posizionata nella pagina della memoria principale con indirizzo 4. Questo fatto è riflesso nella tabella delle corrispondenze nella cella numero 0.
La storia con i file mostrati in memoria è esattamente la stessa. Logicamente, essi sembrano essere collocati in modo continuo e totale nello spazio degli indirizzi virtuali. Tuttavia, nella memoria fisica arrivano pagina per pagina e solo su richiesta. La modifica di tali pagine viene sincronizzata con il file su disco. In questo modo, è possibile eseguire input/output di file semplicemente lavorando con i byte in memoria, poiché tutte le modifiche saranno automaticamente trasferite dal kernel del sistema operativo al file originale.
L'immagine qui sotto dimostra come LMDB sincronizza il proprio stato quando si lavora con un database da diversi processi. Mappando la memoria virtuale di diversi processi su un unico file, di fatto obblighiamo il sistema operativo a sincronizzare transitivamente tra loro determinati blocchi dei loro spazi di indirizzi, dove LMDB si concentra.
Un aspetto importante è che LMDB, per impostazione predefinita, modifica il file con i dati tramite il meccanismo della chiamata di sistema write, mentre il file stesso è mappato in modalità sola lettura. Questo approccio ha due conseguenze importanti.
La prima conseguenza è comune a tutti i sistemi operativi. La sua essenza consiste nell'aggiungere una protezione contro il danneggiamento accidentale del database causato da codice errato. Come è noto, le istruzioni eseguibili di un processo possono accedere ai dati da qualsiasi punto del proprio spazio indirizzi. Allo stesso tempo, come abbiamo appena ricordato, il mapping di un file in modalità read-write implica che qualsiasi istruzione possa anche modificarlo. Se ciò avviene per errore, cercando ad esempio di sovrascrivere realmente un elemento di un array a un indice inesistente, può accidentalmente cambiare il file mappato su quell'indirizzo, portando alla corruzione del database. Se invece il file è mappato in modalità read-only, il tentativo di modificare lo spazio indirizzabile corrispondente porterà a un'interruzione del programma con il segnale SIGSEGV, e il file rimarrà integro.
La seconda conseguenza è specifica per iOS. Né l'autore né alcuna altra fonte ne parlano esplicitamente, ma senza di essa LMDB sarebbe inadeguata per funzionare in questo sistema operativo mobile. La sua trattazione sarà oggetto della prossima sezione.
Specificità dei file mappati in memoria in iOS
Nel 2018, alla WWDC, c'è stata una presentazione straordinaria . In essa si spiega che in iOS tutte le pagine presenti nella memoria fisica appartengono a uno dei 3 tipi: dirty, compressed e clean.
La clean memory è l'insieme delle pagine che possono essere scaricate dalla memoria fisica senza problemi. I dati in esse possono essere ricaricati, se necessario, dalle loro fonti originali. I file mappati in memoria in sola lettura rientrano esattamente in questa categoria. iOS non teme di scaricare in qualsiasi momento le pagine associate al file dalla memoria, poiché sono garantite come sincronizzate con il file su disco.
Nella dirty memory rientrano tutte le pagine modificate, indipendentemente da dove si trovassero inizialmente. In particolare, così saranno classificati anche i file mappati in memoria, modificati tramite scritture nella memoria virtuale associata. Aprendo LMDB con il flag MDB_WRITEMAP, dopo aver apportato modifiche, è possibile verificarlo di persona.
Non appena l'applicazione inizia a occupare troppa memoria fisica, iOS sottopone le sue pagine sporche a compressione. La memoria occupata dalle pagine sporche e compresse costituisce il cosiddetto memory footprint dell'applicazione. Una volta raggiunto un certo valore soglia, il demone di sistema OOM killer interviene e termina forzatamente il processo. Questa è una caratteristica di iOS rispetto ai sistemi operativi desktop. A differenza di essi, la riduzione del memory footprint tramite lo swapping delle pagine dalla memoria fisica al disco non è prevista in iOS. Le cause possono essere oggetto di congetture. Forse la procedura di spostamento intensivo delle pagine sul disco e viceversa è troppo dispendiosa in termini di energia per i dispositivi mobili, o iOS risparmia risorse nella riscrittura delle celle sui dischi SSD, oppure i progettisti non erano soddisfatti delle prestazioni complessive del sistema, dove tutto viene continuamente scambiato. In ogni caso, il fatto rimane.
La buona notizia, già menzionata in precedenza, è che LMDB per impostazione predefinita non utilizza il meccanismo mmap per aggiornare i file. Di conseguenza, i dati mappati sono classificati da iOS come clean memory e non contribuiscono al memory footprint. È possibile verificarlo utilizzando uno strumento di Xcode chiamato VM Tracker. Nello screenshot qui sotto è mostrato lo stato della memoria virtuale dell'applicazione Cloud di iOS durante il funzionamento. All'avvio, sono stati inizializzati 2 istanze di LMDB. La prima ha avuto il permesso di mappare il proprio file su 1GiB di memoria virtuale, la seconda su 512MiB. Nonostante entrambi i repository occupino un certo volume di memoria residenziale, nessuno dei due contribuisce alla dirty size.
E ora è tempo di brutte notizie. Grazie al meccanismo di swapping nei sistemi operativi desktop a 64 bit, ogni processo può occupare tanto spazio di indirizzamento virtuale quanto consentito dallo spazio libero sul disco fisso per il suo potenziale swapping. La sostituzione dello swapping con la compressione in iOS riduce drasticamente il massimo teorico. Ora tutti i processi attivi devono rientrare nella memoria principale (cioè RAM), e tutti quelli che non ci stanno devono essere terminati forzatamente. Questo è quanto viene detto nel sopra citato , sia in . Di conseguenza, iOS limita rigidamente la dimensione della memoria disponibile per la allocazione tramite mmap. Ecco si possono esaminare i limiti empirici dei volumi di memoria che è stato possibile allocare su diversi dispositivi utilizzando questa chiamata di sistema. Su modelli di smartphone iOS tra i più moderni è stata generosa con 2 gigabyte, mentre sulle versioni top di iPad con 4. Nella pratica, ovviamente, si deve fare riferimento ai modelli di dispositivi più datati supportati, dove la situazione è piuttosto triste. Peggio ancora, osservando lo stato della memoria dell'applicazione nel VM Tracker, si può scoprire che LMDB non è l'unico a pretendere memoria mappata. Buona parte è occupata dagli allocatori di sistema, dai file di risorse, dai framework per la gestione delle immagini e da altri predatori più piccoli.
Dai risultati degli esperimenti nel Cloud, siamo giunti ai seguenti valori di compromesso per la memoria allocata da LMDB: 384 megabyte per dispositivi a 32 bit e 768 per quelli a 64 bit. Dopo aver esaurito questo volume, qualsiasi operazione di modifica inizia a terminare con il codice MDB_MAP_FULL. Osserviamo alcuni di questi errori nel nostro monitoraggio, ma sono abbastanza rari da poter essere trascurati in questa fase.
Una causa non ovvia di consumo eccessivo di memoria da parte del database possono essere le transazioni a lunga vita. Per comprendere il legame tra questi due fenomeni, ci aiuterà l'analisi dei rimanenti due pilastri di LMDB.
3.2. Pilastro n. 2. Albero B+-
Per emulare tabelle sopra uno storage key-value, è necessario che la sua API contenga le seguenti operazioni:
- Inserimento di un nuovo elemento.
- Ricerca di un elemento con una chiave specificata.
- Cancellazione di un elemento.
- Iterazione su intervalli di chiavi in ordine di ordinamento.
La struttura dati più semplice, con cui è possibile implementare facilmente tutte e quattro le operazioni, è l'albero di ricerca binario. Ogni nodo rappresenta una chiave, che divide l'intero sottoinsieme di chiavi figlie in due sotto-alberi. A sinistra ci sono quelle che sono inferiori al genitore, mentre a destra quelle che sono superiori. L'ottenimento di un insieme ordinato di chiavi si raggiunge attraverso uno dei classici percorsi nell'albero.
Gli alberi binari presentano due fondamentali svantaggi che non permettono loro di essere efficaci come struttura dati su disco. In primo luogo, il grado di bilanciamento è imprevisto. C'è un notevole rischio di ottenere alberi in cui l'altezza dei vari rami può differire notevolmente, il che complica significativamente la complessità algoritmica della ricerca rispetto a quanto previsto. In secondo luogo, l'abbondanza di collegamenti incrociati tra i nodi priva gli alberi binari della località in memoria. Nodi vicini (in termini di connessioni tra di loro) possono trovarsi su pagine completamente diverse nella memoria virtuale. Di conseguenza, anche per una semplice traversata di alcuni nodi adiacenti nell'albero, potrebbe essere necessario accedere a un numero comparabile di pagine. Questo è un problema anche quando parliamo dell'efficacia degli alberi binari come struttura dati in memoria, dato che la costante rotazione delle pagine nella cache della CPU è un'operazione costosa. Quando si tratta di dover frequentemente caricare pagine collegate ai nodi dal disco, la situazione diventa davvero .
Gli alberi B, essendo un'evoluzione degli alberi binari, risolvono i problemi evidenziati nel paragrafo precedente. In primo luogo, si autobilanciano. In secondo luogo, ogni nodo suddivide un insieme di chiavi figlie non in 2, ma in M sottoinsiemi ordinati, dove M può essere piuttosto grande, nell'ordine di alcune centinaia o persino migliaia.
Grazie a questo:
- Ogni nodo contiene un gran numero di chiavi già ordinate e gli alberi risultano molto bassi.
- L'albero acquisisce la proprietà della località di allocazione in memoria, poiché chiavi vicine per valore si trovano naturalmente vicine tra loro su uno stesso nodo o su nodi adiacenti.
- Si riduce il numero di nodi intermedi durante la discesa nell'albero durante l'operazione di ricerca.
- Si riduce il numero di nodi target letti durante le query di intervallo, poiché ognuno di essi già contiene un gran numero di chiavi ordinate.
In LMDB viene utilizzata una delle varianti dell'albero B chiamata albero B+. Nello schema soprastante sono rappresentati i tre tipi di nodi che vi si possono trovare:
- In cima si trova la radice (root). Essa materializza nient'altro che il concetto di database all'interno dello storage. All'interno di un'istanza di LMDB è possibile creare diversi database che condividono uno spazio indirizzato virtuale mappato. Ognuno di essi inizia con la propria radice.
- Al livello più basso si trovano le foglie (leaf). Esse contengono e solo esse le coppie chiave-valore memorizzate nel database. A proposito, qui sta la particolarità degli alberi B+. Se un normale albero B memorizza le parti value nei nodi di tutti i livelli, la variazione B+ solo nel livello più basso. Stabilito questo fatto, ci riferiremo al sotto-tipo di albero usato in LMDB semplicemente come albero B.
- Tra la radice e le foglie si posizionano 0 o più livelli tecnici con nodi di navigazione (branch). Il loro compito è suddividere un insieme ordinato di chiavi tra le foglie.
Fisicamente, i nodi sono blocchi di memoria di lunghezza precedentemente definita. La loro dimensione è un multiplo della dimensione delle pagine di memoria del sistema operativo, di cui abbiamo parlato in precedenza. Di seguito è rappresentata la struttura di un nodo. Nell'intestazione si trova la meta-informazione, la più ovvia delle quali, ad esempio, è il checksum. Segue l'informazione sugli offset dove si trovano le celle con i dati. I dati possono essere o chiavi, se parliamo di nodi di navigazione, oppure coppie chiave-valore complete nel caso delle foglie. Maggiori dettagli sulla struttura delle pagine possono essere letti nel lavoro .
Comprendendo il contenuto interno dei nodi-pagina, rappresenteremo quindi l'albero B di LMDB semplificato nel seguente modo.
Le pagine con i nodi sono disposte sequenzialmente sul disco. Le pagine con numeri più alti si trovano più vicino alla fine del file. La cosiddetta meta-pagina (meta page) contiene informazioni sugli offset, da cui è possibile trovare le radici di tutti gli alberi. All'apertura del file, LMDB scansiona il file pagina per pagina dall'ultima alla prima in cerca della meta-pagina valida e attraverso di essa trova i database esistenti.
Ora che abbiamo un'idea della struttura logica e fisica dell'organizzazione dei dati, possiamo passare alla considerazione del terzo pilastro di LMDB. È grazie a esso che tutte le modifiche al database avvengono in modo transazionale e isolate le une dalle altre, conferendo al database in generale anche la proprietà di multiversionalità.
3.3. Pilastro n. 3. Copy-on-write
Alcune operazioni con l'albero B richiedono una serie di modifiche ai suoi nodi. Un esempio è l'aggiunta di una nuova chiave a un nodo che ha già raggiunto la massima capienza. In tal caso, è necessario, prima di tutto, dividere il nodo in due, e in secondo luogo, aggiungere un riferimento al nuovo nodo figlio distaccato nel suo genitore. Questa procedura è potenzialmente molto pericolosa. Se per qualche motivo (crash, mancanza di alimentazione, ecc.) si verificano solo alcune modifiche della serie, l'albero rimarrà in uno stato incoerente.
Una delle soluzioni tradizionali per garantire la resilienza del database ai guasti consiste nell'aggiungere, accanto all'albero B, una struttura dati su disco aggiuntiva: il log delle transazioni, noto anche come write-ahead log (WAL). Questo è un file in cui, rigorosamente prima di modificare l'albero B, viene registrata l'operazione prevista. Pertanto, se durante l'autodiagnosi si riscontra una corruzione dei dati, il database consulta il log per ripristinare la propria integrità.
LMDB ha scelto un altro approccio come meccanismo per garantire la resilienza ai guasti, chiamato copy-on-write. La sua essenza è che, invece di aggiornare i dati su una pagina esistente, essi vengono prima totalmente copiati e tutte le modifiche vengono effettuate sulla copia.
Successivamente, affinché i dati aggiornati siano accessibili, è necessario modificare il riferimento al nodo diventato attuale nel nodo genitore. Poiché è necessario modificare anche questo, esso viene anch'esso coperto in anticipo. Il processo continua ricorsivamente fino alla radice. I dati sulla meta-pagina vengono aggiornati per ultimi.
Se durante la procedura di aggiornamento si verifica un'interruzione imprevista del processo, non verrà creata una nuova meta-pagina o non verrà scritta su disco completamente, e la sua somma di controllo sarà errata. In entrambi i casi, le nuove pagine saranno irraggiungibili mentre le pagine esistenti non subiranno danni. Questo consente a LMDB di evitare la necessità di mantenere un write ahead log per garantire la coerenza dei dati. De facto, la struttura di archiviazione dei dati su disco descritta sopra svolge anche questa funzione. L'assenza di un log delle transazioni esplicito è uno dei tratti distintivi di LMDB, che garantisce un'alta velocità di lettura dei dati.
La struttura risultante chiamata append-only B-tree fornisce naturalmente isolamento delle transazioni e multi-versioning. In LMDB, a ciascuna transazione aperta è associata la radice attuale dell'albero. Finché la transazione non è completata, le pagine dell'albero ad essa associate non verranno mai modificate o riutilizzate per nuove versioni dei dati. In questo modo, è possibile lavorare per tutto il tempo necessario esattamente con il set di dati che era attuale al momento dell'apertura della transazione, anche se il deposito continua a essere attivamente aggiornato. Questo è il nucleo del multi-versioning, che rende LMDB una fonte di dati ideale per il nostro amato UICollectionView. Aprendo una transazione, non è necessario aumentare l'impronta di memoria dell'applicazione estraendo frettolosamente i dati rilevanti in qualche struttura in memoria, temendo di restare a mani vuote. Questa caratteristica distingue favorevolmente LMDB da SQLite, che non può vantare un isolamento così totale. Aprendo due transazioni in quest'ultimo e cancellando una certa registrazione all'interno di una di esse, non sarà più possibile accedere a quella registrazione nemmeno all'interno della seconda rimasta.
Il rovescio della medaglia è un potenziale consumo significativamente maggiore della memoria virtuale. Nella diapositiva è mostrata come apparirà la struttura del database se viene modificata contemporaneamente con 3 transazioni di lettura aperte, che guardano a diverse versioni del database. Poiché LMDB non può riutilizzare i nodi accessibili dalle radici associate alle transazioni attuali, allo storage non rimane altro che allocare in memoria un'altra quarta radice e clonare ancora una volta le pagine modificabili.
È opportuno ricordare la sezione sui file mappati in memoria. Sembrerebbe che il consumo aggiuntivo di memoria virtuale non dovrebbe preoccuparci troppo, poiché non contribuisce all'impronta di memoria dell'applicazione. Tuttavia, è stato notato che iOS è molto avaro nella sua allocazione, e non possiamo, come sul server o sul desktop, dare a LMDB una regione di 1 terabyte senza pensarci affatto. È importante cercare di mantenere la durata delle transazioni il più breve possibile.
4. Progettazione dello schema dei dati sopra l'API key-value
Iniziamo l'analisi dell'API esaminando le astrazioni di base fornite da LMDB: ambiente e database, chiavi e valori, transazioni e cursori.
Osservazione sulle liste di codice
Tutte le funzioni nell'API pubblica di LMDB restituiscono il risultato del loro lavoro sotto forma di codice di errore, ma nei listing successivi il suo controllo è stato omesso per motivi di brevità. In pratica, abbiamo utilizzato il nostro wrapper C++ , in cui gli errori si materializzano sotto forma di eccezioni C++.
Come modo più veloce per collegare LMDB al progetto per iOS o macOS, propongo il mio CocoaPod .
4.1. Astrazioni di base
Ambiente (environment)
Struttura MDB_env è il contenitore dello stato interno di LMDB. La famiglia di funzioni con il prefisso mdb_env consente di configurare alcune delle sue proprietà. Nel caso più semplice, l'inizializzazione del motore appare come segue.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);Nell'applicazione Mail.ru Cloud, abbiamo modificato i valori predefiniti solo per due parametri.
Il primo di essi è la dimensione dello spazio degli indirizzi virtuali su cui viene mappato il file di archiviazione. Purtroppo, anche sullo stesso dispositivo, un valore specifico può variare significativamente da un avvio all'altro. Per tenere conto di questa peculiarità di iOS, la dimensione massima dell'archiviazione viene selezionata dinamicamente. Partendo da un certo valore, essa viene successivamente dimezzata finché la funzione mdb_env_open non restituirà un risultato diverso da ENOMEM. In teoria esiste anche l'approccio opposto: prima assegnare al motore un minimo di memoria e poi, in caso di errori MDB_MAP_FULL, aumentarne la quantità. Tuttavia, questo è significativamente più complesso. La ragione è che la procedura di ripristino della memoria (remap) utilizzando la funzione mdb_env_set_map_size invaliderebbe tutte le entità (cursori, transazioni, chiavi e valori) ottenute dal motore in precedenza. Tenere conto di un tale sviluppo degli eventi nel codice comporterebbe una complicazione notevole. Se, tuttavia, la memoria virtuale è molto preziosa per voi, potrebbe essere un motivo per considerare un fork progredito , dove tra le funzioni dichiarate è presente l'«automatic adjustment della dimensione del database on-the-fly».
Il secondo parametro, il cui valore di default non ci soddisfa, regola la meccanica della sicurezza dei thread. Purtroppo, almeno su iOS 10, ci sono problemi con il supporto per lo storage locale dei thread. Per questo motivo, nell'esempio sopra, l'archiviazione viene aperta con il flag MDB_NOTLS. Inoltre, è stato necessario anche il wrapper C++ , per rimuovere le variabili con questo attributo in esso.
Database
Il database è un'istanza separata di un B-albero, di cui abbiamo parlato in precedenza. La sua apertura avviene all'interno di una transazione, il che inizialmente può sembrare un po' strano.
MDB_txn *txn;
MDB_dbi dbi;
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);
mdb_txn_abort(txn);In effetti, una transazione in LMDB è un'entità di archiviazione, non specifica di un database. Questa concezione permette di effettuare operazioni atomiche su entità situate in diversi database. In teoria, ciò apre la possibilità di modellare le tabelle come diversi database, ma a suo tempo ho seguito un'altra strada, descritta nei dettagli di seguito.
Chiavi e valori
Struttura MDB_val modella il concetto sia di chiave che di valore. Lo storage non ha la minima idea della loro semantica. Per esso, qualcosa o qualcos'altro è semplicemente un array di byte di dimensione fissata. La dimensione massima della chiave è di 512 byte.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Con l'ausilio di un comparatore, lo storage ordina le chiavi in ordine crescente. Se non viene sostituito con uno proprio, verrà utilizzato il valore predefinito, che le ordina byte per byte in ordine lessicografico.
Transazioni
Il meccanismo delle transazioni è descritto in , perciò qui ripeterò brevemente le loro principali caratteristiche:
- Supporto di tutte le proprietà di base : atomicità, coerenza, isolamento e Durabilità. Non posso non notare che in parte della durabilità su macOS e iOS c'è un bug, corretto in MDBX. Maggiori dettagli possono essere letti nel loro .
- L'approccio alla multithreading è descritto dallo schema "single writer / multiple readers". Gli scrittori bloccano l'uno con l'altro, ma non bloccano i lettori. I lettori non bloccano né gli scrittori né l'uno con l'altro.
- Supporto per transazioni annidate.
- Supporto per la multiversione.
La multiversione in LMDB è così buona che voglio mostrarla in azione. Dal codice qui sotto si vede che ogni transazione lavora precisamente con la versione del database che era attiva al momento della sua apertura, essendo completamente isolata da tutti i successivi cambiamenti. L'inizializzazione dello storage e l'aggiunta di un record di prova non presentano nulla di interessante, quindi queste operazioni sono state lasciate sotto spoiler.
Aggiunta di un record di prova
MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;
mdb_env_create(&env);
mdb_env_open(env, ".\/testdb", MDB_NOTLS, 0664);
mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);
char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;
int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;
mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);MDB_txn *txn1, *txn2, *txn3;
MDB_val val;
// Apriamo 2 transazioni, ognuna delle quali guarda
// alla versione del database con un singolo record.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only
// Nell'ambito della prima transazione, eliminiamo dal database il record esistente.
mdb_del(txn1, dbi, &key, NULL);
// Registriamo l'eliminazione.
mdb_txn_commit(txn1);
// Apriamo la terza transazione, che guarda
// all'ultima versione del database, dove il record non esiste più.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Verifichiamo che il record per la chiave cercata non esista più.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Concludiamo la transazione.
mdb_txn_abort(txn3);
// Ci assicuriamo che nell'ambito della seconda transazione, aperta nel momento
// dell'esistenza del record nel database, sia ancora possibile trovarlo con la chiave.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Verifichiamo che per la chiave siano stati recuperati dati validi e non spazzatura.
assert(*(int *)val.mv_data == 997);
// Concludiamo la transazione, operando anche se con un database obsoleto ma coerente.
mdb_txn_abort(txn2);Facoltativamente, consiglio di provare a fare lo stesso trucco con SQLite e vedere cosa ne risulta.
La multiversione introduce dei vantaggi molto graditi nella vita dei programmatori iOS. Grazie a questa caratteristica, è possibile regolare facilmente e senza sforzo la velocità di aggiornamento della fonte dati (data source) per i form sullo schermo, tenendo conto dell'esperienza utente. Per esempio, consideriamo una funzionalità dell'applicazione Cloud Mail.ru come il caricamento automatico di contenuti dalla galleria multimediale di sistema. Con una buona connessione, il client è in grado di caricare sul server diverse fotografie al secondo. Se dopo ogni caricamento aggiorniamo UICollectionView il contenuto multimediale nel cloud dell'utente, possiamo dimenticare i 60 fps e lo scorrimento fluido durante questo processo. Per evitare aggiornamenti frequenti dello schermo, è necessario limitare in qualche modo la velocità di modifica dei dati alla base UICollectionViewDataSource.
Se il database non supporta il multi-versioning e consente di lavorare solo con lo stato attuale e aggiornato, è necessario eseguire una copia dei dati per creare uno snapshot stabile nel tempo, sia in una struttura dati in memoria sia in una tabella temporanea. Entrambi questi approcci sono molto costosi. Nel caso di uno storage in memoria, ci sono costi sia di memoria, causati dal salvataggio degli oggetti costruiti, sia di tempo, legati a trasformazioni ORM superflue. Per quanto riguarda la tabella temporanea, è un piacere ancora più costoso, che ha senso solo in casi non triviali.
Il multi-versioning di LMDB risolve il problema di mantenere una fonte di dati stabile in modo molto elegante. È sufficiente aprire una transazione e voilà: fino a quando non la concludiamo, il set di dati è garantito. La logica della velocità del suo aggiornamento ora è completamente nelle mani dello strato di presentazione, con un totale assente di spese generali significative.
Cursori
I cursori forniscono un meccanismo per l'iterazione ordinata attraverso coppie chiave-valore mediante la traversata di un B-albero. Senza di essi, sarebbe impossibile modellare efficacemente le tabelle nel database che stiamo per esaminare.
4.2. Modellazione delle tabelle
La proprietà di ordinamento delle chiavi permette di costruire sopra le astrazioni di base qualcosa di più avanzato come una tabella. Esaminiamo questo processo prendendo come esempio la tabella principale del cliente cloud, in cui è memorizzata la cache delle informazioni su tutti i file e le cartelle dell'utente.
Schema della tabella
Uno degli scenari più comuni per cui deve essere progettata la struttura della tabella con un albero di cartelle è l'estrazione di tutti gli elementi presenti all'interno di una directory specificata. Un buon modello di organizzazione dei dati per query di questo tipo è . Per la sua realizzazione sopra un archivio key-value, è necessario ordinare le chiavi di file e cartelle in modo tale che vengano raggruppate in base all'appartenenza alla directory genitore. Inoltre, per visualizzare il contenuto della directory nella forma familiare per l'utente di Windows (prima le cartelle, poi i file, entrambi ordinati in base all'alfabeto), è necessario includere nei key i corrispondenti campi aggiuntivi.
Nell'immagine sottostante è mostrato come, in base al compito assegnato, possa apparire la rappresentazione delle chiavi in forma di array di byte. Inizialmente vengono posizionati i byte con l'identificatore della directory padre (rossi), poi quelli con il tipo (verdi) e infine quelli con il nome (blu). Ordinati dal comparatore predefinito di LMDB in ordine lessicografico, vengono disposti nel modo richiesto. Un attraversamento sequenziale delle chiavi con lo stesso prefisso rosso ci fornisce i valori associati nell'ordine in cui devono essere visualizzati nell'interfaccia utente (a destra), senza richiedere alcun ulteriore post-processing.
Serializzazione delle chiavi e dei valori
Sono stati inventati molti metodi di serializzazione degli oggetti. Poiché non avevamo alcun altro requisito oltre alla velocità, abbiamo scelto il più veloce possibile — un dump della memoria occupata dall'istanza della struttura del linguaggio C. Così, la chiave di un elemento di directory può essere modellata come la seguente struttura NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Per la memorizzazione NodeKey nello storage, è necessario posizionare il puntatore ai dati all'indirizzo dell'inizio della struttura e calcolare le loro dimensioni con la funzione MDB_val sizeof MDB_val serialize(NodeKey * const key) { return MDB_val { .mv_size = sizeof(NodeKey), .mv_data = (void *)key }; }.
Nel primo capitolo riguardante i criteri di scelta del database, come fattore importante, ho menzionato la minimizzazione delle allocazioni dinamiche nelle operazioni CRUD. Il codice della funzioneserialize mostra come nel caso di LMDB si possano completamente evitare durante l'inserimento di nuovi record nel database. L'array di byte ricevuto dal server viene inizialmente trasformato in strutture di stack e poi queste vengono dumpate in modo triviale nello storage. Considerando che all'interno di LMDB non ci sono allocazioni dinamiche, si può ottenere una situazione straordinaria per gli standard di iOS — utilizzare per lavorare con i dati lungo tutto il loro percorso dalla rete al disco solo memoria stack! Ordinamento delle chiavi con un comparatore binario
Ordinamento delle chiavi con un comparatore binario
Il modo in cui i tasti vengono ordinati è definito da una funzione speciale chiamata comparatore. Poiché il motore non conosce la semantica dei byte in essi contenuti, al comparatore predefinito non resta altro da fare che ordinare le chiavi in ordine lessicografico, confrontandole byte per byte. Usarlo per ordinare le strutture è come radersi con un'accetta. Tuttavia, in casi semplici trovo questo metodo accettabile. L'alternativa è descritta un po' più sotto, e qui voglio sottolineare un paio di insidie sparse lungo questo percorso.
La prima cosa da tenere a mente è la rappresentazione in memoria dei tipi di dati primitivi. Così, su tutti i dispositivi Apple, le variabili intere sono memorizzate in formato . Questo significa che il byte meno significativo si trova a sinistra, e ordinare numeri interi utilizzando il confronto byte per byte non è possibile. Ad esempio, cercare di farlo con un insieme di numeri da 0 a 511 porterà al seguente risultato.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Per risolvere questo problema, i numeri interi devono essere memorizzati nella chiave in un formato adeguato per il comparatore byte per byte. Le funzioni della famiglia hton* aiuteranno a effettuare la trasformazione necessaria (in particolare htons per i numeri a due byte dell'esempio).
Il formato di rappresentazione delle stringhe nella programmazione è noto come una . Se la semantica delle stringhe e la codifica utilizzata per la loro rappresentazione in memoria implicano che un simbolo può occupare più di un byte, è meglio rinunciare all'idea di utilizzare il comparatore predefinito.
La seconda cosa da tenere a mente sono i del compilatore dei campi di una struttura. A causa di essi, in memoria possono formarsi byte con valori spazzatura tra i campi, il che, ovviamente, compromette l'ordinamento byte per byte. Per eliminare la spazzatura, è necessario dichiarare i campi in un ordine rigorosamente definito, tenendo a mente le regole di allineamento, o utilizzare l'attributo packed.
Ordinamento delle chiavi tramite comparatore esterno
La logica di confronto delle chiavi potrebbe risultare troppo complessa per un comparatore binario. Una delle molte ragioni è la presenza di campi tecnici all'interno delle strutture. Illustrerò la loro comparsa utilizzando l'esempio della chiave già nota per l'elemento della directory.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Nonostante la sua semplicità, nella stragrande maggioranza dei casi consuma troppa memoria. Il buffer per il nome occupa 256 byte, mentre in media i nomi di file e cartelle raramente superano i 20-30 caratteri.
Uno dei metodi standard per ottimizzare la dimensione della registrazione consiste nel 'ridurre' la registrazione alla dimensione effettiva. La sostanza è che il contenuto di tutti i campi a lunghezza variabile è memorizzato nel buffer alla fine della struttura, mentre le loro lunghezze sono in variabili separate. Secondo questo approccio, la chiave NodeKey viene trasformata nel seguente modo.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Successivamente, durante la serializzazione, come dimensione dei dati non si indica MDB_val serialize(NodeKey * const key) { return MDB_val { .mv_size = sizeof(NodeKey), .mv_data = (void *)key }; } l'intera struttura, ma la dimensione di tutti i campi a lunghezza fissa più la dimensione della parte effettivamente utilizzata del buffer.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}A seguito del refactoring effettuato, abbiamo ottenuto un notevole risparmio di spazio occupato dalle chiavi. Tuttavia, a causa del campo tecnico nameLength, il comparatore binario predefinito non è più adatto per confrontare le chiavi. Se non lo sostituiamo con il nostro, la lunghezza del nome sarà un fattore più prioritario nella ordinazione rispetto al nome stesso.
LMDB consente di impostare per ciascuna database la propria funzione di confronto delle chiavi. Questo avviene tramite la funzione mdb_set_compare strictamente prima dell'apertura. Per ovvi motivi, non si può cambiarla durante la vita del database. Il comparatore riceve due chiavi in formato binario e restituisce il risultato del confronto: minore (-1), maggiore (1) o uguale (0). Il pseudocodice per NodeKey è il seguente.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey * const aKey = (NodeKey * const)a->mv_data;
NodeKey * const bKey = (NodeKey * const)b->mv_data;
return // ...
}Finché in un database tutte le chiavi hanno lo stesso tipo, è legittimo effettuare un cast incondizionato della loro rappresentazione in byte al tipo della struttura applicativa della chiave. Qui c'è un dettaglio, ma verrà esaminato più avanti nella sezione 'Lettura delle registrazioni'.
Serializzazione dei valori
Con le chiavi delle registrazioni memorizzate in LMDB si lavora in modo estremamente intensivo. Il loro confronto avviene all'interno di qualsiasi operazione applicativa, e la performance del comparatore influisce sulla produttività dell'intera soluzione. In un mondo ideale, un comparatore binario predefinito sarebbe sufficiente per il confronto delle chiavi, ma se si è costretti a utilizzare il proprio, la procedura di deserializzazione delle chiavi deve essere il più veloce possibile.
La parte Value di una registrazione (il valore) non interessa particolarmente al database. La sua conversione da rappresentazione byte a oggetto avviene solo quando è realmente necessaria per il codice applicativo, ad esempio per la visualizzazione sullo schermo. Poiché ciò avviene relativamente raramente, le esigenze di velocità di questa procedura non sono così critiche, e nella sua implementazione possiamo orientarci molto di più verso la comodità. Ad esempio, per la serializzazione dei metadati sui file non caricati utilizziamo NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Tuttavia, ci sono casi in cui la performance ha comunque importanza. Ad esempio, per la salvaguardia delle meta-informazioni sulla struttura dei file del cloud utente, utilizziamo sempre quel dump della memoria degli oggetti. La particolarità del compito di formare la loro rappresentazione serializzata è il fatto che gli elementi della directory sono modellati da una gerarchia di classi.
Per la sua implementazione in linguaggio C, i campi specifici degli eredi vengono estratti in strutture separate, e la loro connessione con la base è stabilita tramite un campo di tipo union. Il contenuto attuale dell'unione è definito tramite l'attributo tecnico type.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Aggiunta e aggiornamento delle registrazioni
Le chiavi e i valori serializzati possono essere aggiunti allo storage. A tal fine, viene utilizzata la funzione mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);Nella fase di configurazione, è possibile autorizzare o vietare il salvataggio di più record con la stessa chiave. Se la duplicazione delle chiavi è vietata, è possibile determinare se è consentito aggiornare un record esistente durante l'inserimento. Se la sovrascrittura può avvenire solo a causa di un errore nel codice, si può proteggersi da essa specificando un flag NOOVERWRITE.
Lettura dei record
Per la lettura dei record in LMDB è pensata la funzione mdb_get. Se la coppia chiave-valore è stata rappresentata in precedenza tramite strutture dumpate, questa procedura appare come segue.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}Il listing presentato mostra come la serializzazione tramite dump delle strutture consenta di eliminare le allocazioni dinamiche non solo durante la scrittura, ma anche nella lettura dei dati. Il puntatore restituito dalla funzione mdb_get puntatore guarda esattamente all'indirizzo di memoria virtuale dove il database memorizza la rappresentazione in byte dell'oggetto. Di fatto, otteniamo una sorta di ORM, praticamente gratuito, che garantisce una velocità di lettura dei dati molto elevata. Nonostante la bellezza dell'approccio, è necessario tenere a mente alcune peculiarità ad esso associate.
- Per le transazioni readonly, il puntatore alla struttura-valore rimarrà validamente garantito solo fino a quando la transazione non verrà chiusa. Come già indicato, le pagine dell'albero B, su cui si trova l'oggetto, grazie al principio copy-on-write rimangono inalterate fintanto che almeno una transazione vi fa riferimento. Allo stesso tempo, non appena l'ultima transazione ad esse associata termina, le pagine possono essere riutilizzate per nuovi dati. Se è necessario che gli oggetti sopravvivano alla transazione che li ha generati, dovranno comunque essere copiati.
- Per una transazione readwrite, il puntatore alla struttura-valore ottenuta sarà valido solo fino alla prima procedura di modifica (scrittura o cancellazione dei dati).
- Nonostante la struttura
NodeValuenon sia completa, ma limitata (vedi sezione 'Ordinamento delle chiavi tramite comparatore esterno'), tramite il puntatore è possibile accedere tranquillamente ai suoi campi. L'importante è non dereferenziarlo! - In nessun caso si può modificare la struttura attraverso il puntatore ottenuto. Tutte le modifiche devono essere effettuate solo tramite il metodo
mdb_put. Tuttavia, anche volendolo fare, non sarà possibile, poiché l'area di memoria in cui si trova questa struttura è mappata in modalità di sola lettura. - Il remapping del file nello spazio degli indirizzi del processo, ad esempio, per aumentare la dimensione massima dello storage tramite la funzione
mdb_env_set_map_sizeinvaliderebbe completamente tutte le transazioni e le entità correlate in generale, e i puntatori agli oggetti letti in particolare.
Infine, un'altra caratteristica è così insidiosa che la sua essenza non può essere facilmente riassunta in un ulteriore punto. Nel capitolo sull'albero B ho mostrato lo schema delle pagine in memoria. Da esso si deduce che l'indirizzo dell'inizio del buffer con i dati serializzati può essere del tutto arbitrario. Di conseguenza, il puntatore a essi, ottenuto all'interno della struttura MDB_val e convertito in un puntatore alla struttura, risulta in generale non allineato. Allo stesso tempo, le architetture di alcuni chip (nel caso di iOS, ARMv7) richiedono che l'indirizzo di qualsiasi dato sia un multiplo della dimensione della parola macchina o, in altre parole, della larghezza del sistema (per ARMv7, sono 32 bit). In altre parole, operazioni come *(int *foo)0x800002 su di essi equivalgono a una fuga e portano a una condanna EXC_ARM_DA_ALIGN. È possibile evitare un destino così triste in due modi.
Il primo prevede di copiare preventivamente i dati in una struttura già allineata. Ad esempio, su un comparatore personalizzato, ciò si rifletterebbe nel seguente modo.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey aKey, bKey;
memcpy(&aKey, a->mv_data, a->mv_size);
memcpy(&bKey, b->mv_data, b->mv_size);
return \/\/ ...
}Un'alternativa è informare in anticipo il compilatore che le strutture con chiave e valore possono non essere allineate utilizzando l'attributo aligned(1). Su ARM si può ottenere lo stesso effetto comporta un aumento dei costi delle operazioni di accesso ai dati. typedef struct __attribute__((packed)) NodeKey { uint8_t parentId; uint8_t type; uint8_t nameLength; uint8_t nameBuffer[256]; } NodeKey;
Richieste di tipo RangeRange-запросы
Per l'iterazione su un gruppo di record in LMDB, è prevista l'astrazione del cursore. Vedremo come lavorarci con l'esempio della tabella dei metadati del cloud dell'utente che già conosciamo.
Nel contesto della visualizzazione dell'elenco dei file in una directory, è necessario trovare tutte le chiavi associate ai suoi file e folder figlio. Nei precedenti sottosezioni abbiamo ordinato le chiavi NodeKey in modo che siano prima ordinate per l'identificativo della directory padre. Pertanto, dal punto di vista tecnico, il compito di ottenere il contenuto della cartella si riduce a posizionare il cursore sul confine superiore del gruppo di chiavi con un prefisso specificato, seguito dall'iterazione fino al confine inferiore.
Il confine superiore può essere trovato "in modo diretto" con una ricerca sequenziale. Per fare ciò, si posiziona il cursore all'inizio dell'intero elenco di chiavi nel database e poi si incrementa finché sotto di esso non si trova una chiave con l'identificativo della directory padre. Questo approccio ha 2 evidenti svantaggi:
- La complessità lineare della ricerca, sebbene, come è noto, negli alberi in generale e negli alberi B in particolare, possa essere effettuata in tempo logaritmico.
- È insensato caricare dalla memoria del file tutte le pagine precedenti a quella cercata, il che è estremamente costoso.
Fortunatamente, l'API LMDB prevede un metodo efficace per la posizione iniziale del cursore. Per fare ciò, è necessario formare una chiave tale che il suo valore sia sicuramente inferiore o uguale alla chiave che si trova sul confine superiore dell'intervallo. Ad esempio, applicabile all'elenco nell'immagine sopra, possiamo creare una chiave in cui il campo parentId è uguale a 2 e tutti gli altri sono riempiti di zeri. Questa chiave parzialmente riempita viene passata alla funzione mdb_cursor_get con l'operazione MDB_SET_RANGE.
NodeKey upperBoundSearchKey = {
.parentId = 2,
.type = 0,
.nameLength = 0
};
MDB_val value, key = serialize(upperBoundSearchKey);
MDB_cursor *cursor;
mdb_cursor_open(..., &cursor);
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);Se il confine superiore del gruppo di chiavi è stato trovato, si itera su di esso finché non si incontra o una chiave diversa parentId, o non si esauriscono le chiavi.
do {
rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
// elaborazione...
} while (MDB_NOTFOUND != rc && // controllo fine tabella
IsTargetKey(key)); // controllo fine gruppo chiaviÈ piacevole notare che durante l'iterazione con mdb_cursor_get otteniamo non solo la chiave, ma anche il valore. Se per soddisfare le condizioni di selezione è necessario controllare anche i campi nella parte value del record, questi sono facilmente accessibili senza ulteriori movimenti.
4.3. Modellazione delle relazioni tra le tabelle
Fino a questo momento abbiamo esaminato tutti gli aspetti della progettazione e dell'uso di un database a singola tabella. Si può dire che una tabella è un insieme di record ordinati, costituiti da coppie chiave-valore omogenee. Se rappresentiamo la chiave come un rettangolo e il valore ad essa associato come un parallelepipedo, otteniamo uno schema visivo del database.
Tuttavia, nella vita reale è raro riuscire a farne a meno in modo così semplice. Spesso, è necessario avere più tabelle nel database e, in secondo luogo, effettuare selezioni in un ordine diverso da quello della chiave primaria. Questo ultimo segmento è dedicato alla creazione e alla connessione tra tali tabelle.
Tabelle indicizzate
Nell'applicazione cloud c'è una sezione "Galleria". In essa viene visualizzato il contenuto multimediale dell'intero cloud, ordinato per data. Per implementare in modo ottimale tale selezione, accanto alla tabella principale è necessario creare un'altra tabella con un nuovo tipo di chiavi. Questa conterrà un campo che indica la data di creazione del file, che fungerà da criterio primario di ordinamento. Poiché le nuove chiavi fanno riferimento agli stessi dati delle chiavi nella tabella principale, vengono chiamate chiavi indicizzate. Nella figura sottostante, esse sono evidenziate in arancione.
Per separare le chiavi di diverse tabelle all'interno di un database, è stato aggiunto a tutte un campo tecnico aggiuntivo chiamato tableId. Rendendolo la priorità principale per l'ordinamento, otterremo una raggruppamento delle chiavi prima per tabelle e poi, all'interno delle tabelle, secondo le proprie regole.
La chiave indicizzata si riferisce agli stessi dati della chiave primaria. L'implementazione diretta di questa proprietà attraverso l'associazione di una copia della parte value della chiave primaria non è ottimale sotto diversi punti di vista.
- Dal punto di vista dello spazio occupato, poiché i metadati possono essere piuttosto ricchi.
- Dal punto di vista delle prestazioni, poiché durante l'aggiornamento dei metadati sarà necessario fare una riscrittura su due chiavi.
- Dal punto di vista del supporto al codice, non appena dimentichiamo di aggiornare i dati su una delle chiavi, otteniamo un bug sfuggente di incoerenza dei dati nel repository.
Vediamo ora come eliminare questi difetti.
Organizzazione delle relazioni tra le tabelle
Per collegare la tabella degli indici a quella principale, si adatta bene il pattern «chiave come valore». Come suggerisce il nome, come parte del valore, la registrazione dell'indice presenta una copia del valore della chiave primaria. Questo approccio neutralizza tutti i difetti sopra menzionati relativi alla conservazione di una copia della parte valore della registrazione primaria. L'unico costo è che per ottenere un valore tramite la chiave dell'indice è necessario effettuare 2 query nel database invece di una. Schema concettuale risultante del database appare nel seguente modo.
Un altro pattern di organizzazione delle relazioni tra le tabelle è «chiave ridondante». La sua essenza risiede nell'aggiunta di attributi extra alla chiave, necessari non per l'ordinamento, ma per la ricreazione della chiave correlata. Nell'applicazione OblaCloud di Mail.ru ci sono esempi reali del suo utilizzo, tuttavia, per evitare un'immersione profonda nel contesto di specifici framework iOS, fornirò un esempio immaginario, ma più comprensibile.
Nei client mobili cloud c'è una pagina che mostra tutti i file e le cartelle a cui l'utente ha fornito accesso ad altre persone. Poiché ci sono relativamente pochi di questi file, e molte informazioni specifiche relative alla loro pubblicità (a chi è stato concesso l'accesso, con quali diritti, ecc.), non sarebbe razionale appesantire la parte valore della registrazione nella tabella principale con esse. Tuttavia, se si desidera visualizzare tali file offline, è necessario comunque conservarli da qualche parte. Una soluzione naturale è creare una tabella separata per essi. Nello schema sottostante, la sua chiave ha il prefisso «P», e il segnaposto «propname» può essere sostituito da un valore più specifico «informazioni pubbliche».
T tutte le metadati unici, per i quali è stata creata la nuova tabella, vengono trasferiti nella parte value della registrazione. Nel frattempo, non si desidera duplicare quei dati su file e cartelle che sono già memorizzati nella tabella principale. Invece, nel campo "P" vengono aggiunti dati ridondanti sotto forma dei campi "node ID" e "timestamp". Grazie a questi ultimi è possibile costruire una chiave indice, da cui ottenere la chiave primaria, dalla quale infine ricavare i metadati del nodo.
Conclusioni
Valutiamo positivamente i risultati dell'implementazione di LMDB. Dopo di essa, il numero di blocchi dell'applicazione è diminuito del 30%.
I risultati del lavoro effettuato hanno trovato risonanza al di là del team iOS. Al momento, una delle sezioni principali "File" nell'applicazione Android ha anche iniziato a utilizzare LMDB, mentre altre parti sono in fase di transizione. Il linguaggio C, su cui si basa il database key-value, ha fornito un valido supporto per implementare originariamente il wrapper applicativo in modo cross-platform utilizzando C++. Per la connessione fluida della libreria C++ risultante con il codice della piattaforma in Objective-C e Kotlin è stato utilizzato un generatore di codice. di Dropbox, ma questa è un'altra storia.
Fonte: habr.com
