Nell'autunno del 2019 si è svolto un evento tanto atteso nel team Mail.ru Cloud iOS. Il database principale per l'archiviazione persistente dello stato dell'applicazione è diventato piuttosto esotico per il mondo mobile Database mappato in memoria Lightning (LMDB). Sotto il taglio, la tua attenzione è invitata alla sua recensione dettagliata in quattro parti. Innanzitutto parliamo dei motivi di una scelta così non banale e difficile. Quindi passiamo alla considerazione di tre balene al centro dell'architettura LMDB: file mappati in memoria, albero B +, approccio copy-on-write per l'implementazione transazionale e multiversioning. Infine, per dessert, la parte pratica. In esso, esamineremo come progettare e implementare uno schema di base con diverse tabelle, inclusa una indice, oltre all'API di valore-chiave di basso livello.​

contenuto

1. Motivazione dell'implementazione
2. Posizionamento LMDB
3. Tre balene LMDB
   3.1 Balena n. 1. File mappati in memoria
   3.2 Balena #2. B+-albero
   3.3 Balena #3. copia su scrittura
4. Progettazione di uno schema di dati in cima all'API chiave-valore
   4.1 Astrazioni di base
   4.2 Modellazione di tavoli
   4.3 Modellazione delle relazioni tra tabelle

1. Motivazione dell'implementazione

Una volta all'anno, nel 2015, ci siamo occupati di misurare la frequenza con cui l'interfaccia della nostra applicazione è in ritardo. Non abbiamo fatto solo questo. Abbiamo sempre più lamentele sul fatto che a volte l'applicazione smetta di rispondere alle azioni dell'utente: i pulsanti non vengono premuti, gli elenchi non scorrono, ecc. Sulla meccanica delle misurazioni ho detto su AvitoTech, quindi qui do solo l'ordine dei numeri.

I risultati della misurazione sono diventati una doccia fredda per noi. Si è scoperto che i problemi causati dai blocchi sono molto più di qualsiasi altro. Se, prima di rendersi conto di questo fatto, il principale indicatore tecnico di qualità era privo di crash, allora dopo il focus spostato senza congelamento.

Dopo aver costruito cruscotto con blocchi e aver speso quantitativo и qualità analizzando le loro cause, il principale nemico è diventato chiaro: la pesante logica aziendale in esecuzione nel thread principale dell'applicazione. Una reazione naturale a questa disgrazia è stata un ardente desiderio di inserirla nei flussi di lavoro. Per una soluzione sistematica di questo problema si è fatto ricorso ad un'architettura multi-thread basata su attori leggeri. Ho dedicato i suoi adattamenti per il mondo iOS due fili nel twitter collettivo e articolo su Habré. Come parte della storia attuale, voglio sottolineare quegli aspetti della decisione che hanno influenzato la scelta del database.​

Il modello dell'attore dell'organizzazione del sistema presuppone che il multithreading diventi la sua seconda essenza. Gli oggetti del modello in esso amano attraversare i confini del filo. E lo fanno non a volte e in alcuni punti, ma quasi costantemente e ovunque.

Il database è uno dei componenti fondamentali nel diagramma presentato. Il suo compito principale è implementare un modello macro Database condiviso. Se nel mondo aziendale viene utilizzato per organizzare la sincronizzazione dei dati tra servizi, nel caso di un'architettura attore, dati tra thread. Pertanto, avevamo bisogno di un tale database, lavorare con il quale in un ambiente multi-thread non causa nemmeno difficoltà minime. In particolare, ciò significa che gli oggetti derivati ​​da esso devono essere almeno thread-safe e idealmente non mutabili affatto. Come sapete, quest'ultimo può essere utilizzato contemporaneamente da più thread senza ricorrere a nessun tipo di blocco, il che ha un effetto benefico sulle prestazioni.

Il secondo fattore significativo che ha influenzato la scelta del database è stata la nostra API cloud. È stato ispirato dall'approccio git alla sincronizzazione. Come lui abbiamo puntato prima API offline, che sembra più che appropriato per i client cloud. Si presumeva che avrebbero pompato solo una volta lo stato completo del cloud, quindi la sincronizzazione nella stragrande maggioranza dei casi sarebbe avvenuta attraverso modifiche in sequenza. Purtroppo, questa possibilità è ancora solo nella zona teorica e in pratica i clienti non hanno imparato a lavorare con le patch. Ci sono una serie di ragioni oggettive per questo, che, per non ritardare l'introduzione, tralasceremo tra parentesi. Ora molto più interessanti sono i risultati istruttivi della lezione su cosa succede quando l'API dice "A" e il suo consumatore non dice "B".

Quindi, se immagini git, che, durante l'esecuzione di un comando pull, invece di applicare patch a uno snapshot locale, confronta il suo stato completo con quello del server completo, allora avrai un'idea abbastanza precisa di come sincronizzare si verifica nei client cloud. È facile intuire che per la sua implementazione è necessario allocare in memoria due alberi DOM con meta-informazioni su tutti i file server e locali. Si scopre che se un utente archivia 500mila file nel cloud, per sincronizzarlo è necessario ricreare e distruggere due alberi con 1 milione di nodi. Ma ogni nodo è un aggregato contenente un grafico di sottooggetti. In questa luce, i risultati della profilazione erano attesi. Si è scoperto che anche senza tener conto dell'algoritmo di unione, la stessa procedura di creazione e quindi distruzione di un numero enorme di piccoli oggetti costa un bel centesimo.La situazione è aggravata dal fatto che l'operazione di sincronizzazione di base è inclusa in un gran numero degli script utente. Di conseguenza, fissiamo il secondo criterio importante nella scelta di un database: la capacità di implementare operazioni CRUD senza allocazione dinamica di oggetti.

Altri requisiti sono più tradizionali e il loro elenco completo è il seguente.

1. Sicurezza del filo.
2. Multielaborazione. Dettato dal desiderio di utilizzare la stessa istanza del database per sincronizzare lo stato non solo tra i thread, ma anche tra l'applicazione principale e le estensioni iOS.
3. La capacità di rappresentare le entità archiviate come oggetti non modificabili
4. Mancanza di allocazioni dinamiche all'interno delle operazioni CRUD.
5. Supporto delle transazioni per le proprietà di base ACIDOParole chiave: atomicità, consistenza, isolamento e affidabilità.
6. Velocità sui casi più popolari.

Con questo insieme di requisiti, SQLite era ed è ancora una buona scelta. Tuttavia, come parte dello studio delle alternative, mi sono imbattuto in un libro "Introduzione a LevelDB". Sotto la sua guida, è stato scritto un benchmark che confronta la velocità di lavoro con diversi database in scenari cloud reali. Il risultato ha superato le più rosee aspettative. Nei casi più popolari - ottenere un cursore su un elenco ordinato di tutti i file e un elenco ordinato di tutti i file per una determinata directory - LMDB si è rivelato 10 volte più veloce di SQLite. La scelta è diventata ovvia.

2. Posizionamento LMDB

LMDB è una libreria molto piccola (solo 10 righe) che implementa il livello fondamentale più basso dei database: l'archiviazione.

Il diagramma sopra mostra che confrontare LMDB con SQLite, che implementa livelli ancora più elevati, non è generalmente più corretto di SQLite con Core Data. Sarebbe più giusto citare gli stessi motori di archiviazione come concorrenti uguali: BerkeleyDB, LevelDB, Sophia, RocksDB, ecc. Ci sono persino sviluppi in cui LMDB funge da componente del motore di archiviazione per SQLite. Il primo esperimento del genere nel 2012 condotto autore LMDB Howard Chu. Giudizio si è rivelato così intrigante che la sua iniziativa è stata accolta dagli appassionati di OSS e ha trovato la sua continuazione di fronte a LumoSQL. Nel gennaio 2020 l'autore di questo progetto è Den Shearer presentata su LinuxConfAu.

L'uso principale di LMDB è come motore per i database delle applicazioni. La libreria deve il suo aspetto agli sviluppatori OpenLDAP, che erano fortemente insoddisfatti di BerkeleyDB come base del loro progetto. Allontanandosi dall'umile biblioteca btree, Howard Chu è stato in grado di creare una delle alternative più popolari del nostro tempo. Ha dedicato il suo bellissimo rapporto a questa storia, così come alla struttura interna di LMDB. "Il database mappato in memoria Lightning". Leonid Yuriev (alias yleo) di Positive Technologies nel suo discorso a Highload 2015 "Il motore LMDB è un campione speciale". In esso, parla di LMDB nel contesto di un compito simile di implementazione di ReOpenLDAP e LevelDB è già stato oggetto di critiche comparative. Come risultato dell'implementazione, Positive Technologies ha persino ottenuto un fork in via di sviluppo attivo MDBX con caratteristiche molto gustose, ottimizzazioni e correzioni di bug.

LMDB viene spesso utilizzato anche come archivio. Ad esempio, il browser Mozilla Firefox scelto it per una serie di esigenze e, a partire dalla versione 9, Xcode preferito il suo SQLite per memorizzare gli indici.

Il motore ha preso piede anche nel mondo dello sviluppo mobile. Le tracce del suo utilizzo possono essere trovare nel client iOS per Telegram. LinkedIn ha fatto un ulteriore passo avanti e ha scelto LMDB come archivio predefinito per il suo framework di memorizzazione nella cache dei dati, Rocket Data, di cui detto in un articolo del 2016.

LLMDB sta lottando con successo per un posto al sole nella nicchia lasciata da BerkeleyDB dopo il passaggio sotto il controllo di Oracle. La libreria è amata per la sua velocità e affidabilità, anche rispetto ai suoi simili. Come sai, non ci sono pranzi gratuiti e vorrei sottolineare il compromesso che dovrai affrontare quando scegli tra LMDB e SQLite. Il diagramma sopra mostra chiaramente come si ottiene l'aumento della velocità. In primo luogo, non paghiamo ulteriori livelli di astrazione oltre all'archiviazione su disco. Certo, in una buona architettura non puoi ancora farne a meno e appariranno inevitabilmente nel codice dell'applicazione, ma saranno molto più sottili. Non avranno funzionalità che non sono richieste da un'applicazione specifica, ad esempio il supporto per le query nel linguaggio SQL. In secondo luogo, diventa possibile implementare in modo ottimale la mappatura delle operazioni dell'applicazione alle richieste all'archiviazione su disco. Se SQLite Nel mio lavoro deriva dalle esigenze medie di un'applicazione media, quindi tu, come sviluppatore di applicazioni, sei ben consapevole dei principali scenari di carico. Per una soluzione più produttiva, dovrai pagare un prezzo maggiorato sia per lo sviluppo della soluzione iniziale che per il suo successivo supporto.

3. Tre balene LMDB

Dopo aver osservato l'LMDB da una prospettiva a volo d'uccello, è ora di approfondire. Le prossime tre sezioni saranno dedicate all'analisi delle principali balene su cui poggia l'architettura di stoccaggio:

1. File mappati in memoria come meccanismo per lavorare con il disco e sincronizzare le strutture di dati interne.
2. B+-tree come organizzazione della struttura dei dati immagazzinati.
3. Copy-on-write come approccio per fornire proprietà transazionali ACID e multiversioning.

3.1. Balena n. 1. File mappati in memoria

I file mappati in memoria sono un elemento architettonico così importante che compaiono persino nel nome del repository. I problemi di memorizzazione nella cache e sincronizzazione dell'accesso alle informazioni memorizzate sono interamente alla mercé del sistema operativo. LMDB non contiene alcuna cache al suo interno. Questa è una decisione consapevole dell'autore, dal momento che la lettura dei dati direttamente dai file mappati consente di tagliare molti scorciatoie nell'implementazione del motore. Di seguito è riportato un elenco tutt'altro che completo di alcuni di essi.

1. Mantenere la coerenza dei dati nell'archiviazione quando si lavora con esso da diversi processi diventa responsabilità del sistema operativo. Nella sezione successiva, questa meccanica è discussa in dettaglio e con immagini.
2. L'assenza di cache solleva completamente LMDB dall'overhead associato alle allocazioni dinamiche. Leggere i dati in pratica significa impostare il puntatore sull'indirizzo corretto nella memoria virtuale e nient'altro. Sembra fantasia, ma nella fonte del repository, tutte le chiamate calloc sono concentrate nella funzione di configurazione del repository.
3. L'assenza di cache significa anche l'assenza di blocchi associati alla sincronizzazione per accedervi. I lettori, di cui può esistere un numero arbitrario contemporaneamente, non incontrano un singolo mutex nel loro percorso verso i dati. Per questo motivo, la velocità di lettura ha una scalabilità lineare ideale in termini di numero di CPU. In LMDB, vengono sincronizzate solo le operazioni di modifica. Può esserci un solo scrittore alla volta.
4. Un minimo di logica di memorizzazione nella cache e sincronizzazione salva il codice da un tipo estremamente complesso di errori associati al lavoro in un ambiente multi-thread. Ci sono stati due interessanti studi sui database alla conferenza Usenix OSDI 2014: "Tutti i file system non sono creati uguali: sulla complessità della creazione di applicazioni coerenti con i crash" и Torturare database per divertimento e profitto. Da loro è possibile ottenere informazioni sia sull'affidabilità senza precedenti di LMDB, sia sull'implementazione quasi impeccabile delle proprietà ACID delle transazioni, che la supera nello stesso SQLite.
5. Il minimalismo di LMDB consente di collocare completamente la rappresentazione della macchina del suo codice nella cache L1 del processore con le caratteristiche di velocità risultanti.

Sfortunatamente, in iOS, i file mappati in memoria non sono così rosei come vorremmo. Per parlare più consapevolmente degli svantaggi ad essi associati, è necessario richiamare i principi generali per l'implementazione di questo meccanismo nei sistemi operativi.

Informazioni generali sui file mappati in memoria

Ad ogni applicazione eseguibile, il sistema operativo associa un'entità chiamata processo. Ad ogni processo viene assegnato un intervallo contiguo di indirizzi, in cui colloca tutto ciò di cui ha bisogno per funzionare. Gli indirizzi più bassi contengono sezioni con codice e dati e risorse hardcoded. Segue poi il blocco in crescita dello spazio degli indirizzi dinamici, a noi ben noto come heap. Contiene gli indirizzi delle entità che compaiono durante il funzionamento del programma. In alto c'è l'area di memoria utilizzata dallo stack dell'applicazione. O cresce o si restringe, in altre parole, anche le sue dimensioni hanno una natura dinamica. In modo che lo stack e l'heap non si spingano e non interferiscano l'uno con l'altro, sono separati alle diverse estremità dello spazio degli indirizzi, c'è un buco tra le due sezioni dinamiche in alto e in basso. Gli indirizzi in questa sezione centrale vengono utilizzati dal sistema operativo per associarsi a un processo di varie entità. In particolare, può mappare un certo insieme continuo di indirizzi su un file su disco. Tale file è chiamato file mappato in memoria

Lo spazio degli indirizzi assegnato a un processo è enorme. Teoricamente, il numero di indirizzi è limitato solo dalla dimensione del puntatore, che è determinata dalla profondità di bit del sistema. Se la memoria fisica gli fosse assegnata 1 in 1, il primo processo divorerebbe l'intera RAM e non ci sarebbe alcun problema di multitasking.​

Tuttavia, sappiamo per esperienza che i moderni sistemi operativi possono eseguire tutti i processi desiderati contemporaneamente. Ciò è possibile perché assegnano molta memoria ai processi solo su carta, ma in realtà caricano nella memoria fisica principale solo quella parte che è richiesta qui e ora. Pertanto, la memoria associata al processo è chiamata virtuale.

Il sistema operativo organizza la memoria virtuale e fisica in pagine di una certa dimensione. Non appena viene richiesta una determinata pagina di memoria virtuale, il sistema operativo la carica nella memoria fisica e mette una corrispondenza tra di loro in un'apposita tabella. Se non ci sono slot liberi, una delle pagine caricate in precedenza viene copiata su disco e quella richiesta prende il suo posto. Questa procedura, su cui torneremo tra poco, si chiama swapping. La figura seguente illustra il processo descritto. Su di essa è stata caricata la pagina A con indirizzo 0 e collocata nella pagina di memoria principale con indirizzo 4. Questo fatto si rifletteva nella tabella delle corrispondenze nella cella numero 0.​

Con i file mappati in memoria, la storia è esattamente la stessa. Logicamente, sono presumibilmente continuamente e interamente collocati nello spazio degli indirizzi virtuali. Tuttavia, entrano nella memoria fisica pagina per pagina e solo su richiesta. La modifica di tali pagine è sincronizzata con il file su disco. Pertanto, puoi eseguire l'I / O di file, semplicemente lavorando con i byte in memoria: tutte le modifiche verranno automaticamente trasferite dal kernel del sistema operativo al file originale.​

L'immagine seguente mostra come LMDB sincronizza il suo stato quando lavora con il database da diversi processi. Mappando la memoria virtuale di diversi processi sullo stesso file, di fatto obblighiamo il sistema operativo a sincronizzare in modo transitivo alcuni blocchi dei loro spazi di indirizzi tra loro, che è dove LMDB cerca.​

Una sfumatura importante è che LMDB modifica il file di dati per impostazione predefinita tramite il meccanismo di chiamata di sistema di scrittura e il file stesso viene visualizzato in modalità di sola lettura. Questo approccio ha due implicazioni importanti.

La prima conseguenza è comune a tutti i sistemi operativi. La sua essenza è aggiungere protezione contro danni involontari al database causati da codice errato. Come sai, le istruzioni eseguibili di un processo sono libere di accedere ai dati da qualsiasi punto del suo spazio di indirizzi. Allo stesso tempo, come abbiamo appena ricordato, visualizzare un file in modalità lettura-scrittura significa che qualsiasi istruzione può anche modificarlo in aggiunta. Se lo fa per errore, cercando, ad esempio, di sovrascrivere effettivamente un elemento dell'array su un indice inesistente, in questo modo può modificare accidentalmente il file mappato a questo indirizzo, il che porterà al danneggiamento del database. Se il file viene visualizzato in modalità di sola lettura, un tentativo di modificare lo spazio degli indirizzi corrispondente ad esso porterà al crash del programma con il segnale SIGSEGVe il file rimarrà intatto.

La seconda conseguenza è già specifica per iOS. Né l'autore né altre fonti lo menzionano esplicitamente, ma senza di esso, LMDB non sarebbe adatto per funzionare su questo sistema operativo mobile. La prossima sezione è dedicata alla sua considerazione.

Specifiche dei file mappati in memoria in iOS

Nel 2018, c'è stato un meraviglioso rapporto al WWDC Approfondimento della memoria iOS. Dice che in iOS tutte le pagine che si trovano nella memoria fisica appartengono a uno dei 3 tipi: sporche, compresse e pulite.

La memoria pulita è una raccolta di pagine che possono essere scambiate in modo sicuro dalla memoria fisica. I dati che contengono possono essere ricaricati dalle fonti originali secondo necessità. I file mappati in memoria di sola lettura rientrano in questa categoria. iOS non ha paura di scaricare dalla memoria le pagine associate a un file in qualsiasi momento, poiché è garantita la sincronizzazione con il file su disco.

Tutte le pagine modificate entrano nella memoria sporca, indipendentemente da dove si trovano originariamente. In particolare, verranno classificati in questo modo anche i file mappati in memoria modificati mediante scrittura nella memoria virtuale ad essi associata. Apertura di LMDB con flag MDB_WRITEMAP, dopo aver apportato modifiche ad esso, puoi vedere di persona.​

Non appena un'applicazione inizia a occupare troppa memoria fisica, iOS comprime le sue pagine sporche. La raccolta di memoria occupata da pagine sporche e compresse è la cosiddetta impronta di memoria dell'applicazione. Quando raggiunge un certo valore di soglia, il demone del sistema killer OOM arriva dopo il processo e lo termina forzatamente. Questa è la particolarità di iOS rispetto ai sistemi operativi desktop. Al contrario, la riduzione dell'impronta di memoria mediante lo scambio di pagine dalla memoria fisica al disco non è prevista in iOS e si possono solo indovinare i motivi. Forse la procedura per spostare intensamente le pagine su disco e viceversa consuma troppo energia per i dispositivi mobili, oppure iOS risparmia la risorsa di riscrivere le celle su unità SSD, o forse i progettisti non erano soddisfatti delle prestazioni complessive del sistema, dove tutto è costantemente scambiato. Comunque sia, resta il fatto.

La buona notizia, già menzionata in precedenza, è che LMDB non utilizza il meccanismo mmap per aggiornare i file per impostazione predefinita. Ne consegue che i dati sottoposti a rendering vengono classificati come memoria pulita da iOS e non contribuiscono al footprint di memoria. Questo può essere verificato utilizzando lo strumento Xcode chiamato VM Tracker. Lo screenshot seguente mostra lo stato della memoria virtuale dell'applicazione iOS Cloud durante il funzionamento. All'inizio, al suo interno sono state inizializzate 2 istanze LMDB. Il primo è stato autorizzato a mappare il proprio file su 1GiB di memoria virtuale, il secondo su 512MiB. Nonostante il fatto che entrambi gli archivi occupino una certa quantità di memoria residente, nessuno dei due contribuisce alla dimensione sporca.

Ora è il momento delle cattive notizie. Grazie al meccanismo di scambio nei sistemi operativi desktop a 64 bit, ogni processo può occupare tanto spazio di indirizzi virtuali quanto lo spazio libero sul disco rigido consente il suo potenziale scambio. La sostituzione dello scambio con la compressione in iOS riduce drasticamente il massimo teorico. Ora tutti i processi viventi devono rientrare nella memoria principale (leggi RAM) e tutti quelli che non si adattano sono soggetti a terminazione forzata. È menzionato come sopra rapportoe in documentazione ufficiale. Di conseguenza, iOS limita fortemente la quantità di memoria disponibile per l'allocazione tramite mmap. Qui qui puoi esaminare i limiti empirici sulla quantità di memoria che potrebbe essere allocata su diversi dispositivi utilizzando questa chiamata di sistema. Sui modelli di smartphone più moderni, iOS è diventato generoso di 2 gigabyte e sulle versioni top dell'iPad - di 4. In pratica, ovviamente, devi concentrarti sui modelli di dispositivi supportati più giovani, dove tutto è molto triste. Ancora peggio, osservando lo stato della memoria dell'applicazione in VM Tracker, scoprirai che LMDB è tutt'altro che l'unico che rivendica la memoria mappata in memoria. I pezzi buoni vengono divorati da allocatori di sistema, file di risorse, framework di immagini e altri predatori più piccoli.

A seguito di esperimenti nel Cloud, siamo giunti ai seguenti valori di compromesso della memoria allocata da LMDB: 384 megabyte per i dispositivi a 32 bit e 768 per quelli a 64 bit. Dopo che questo volume è esaurito, qualsiasi operazione di modifica inizia a completarsi con il codice MDB_MAP_FULL. Osserviamo tali errori nel nostro monitoraggio, ma sono abbastanza piccoli da essere trascurati in questa fase.

Una ragione non ovvia per l'eccessivo consumo di memoria da parte dell'archiviazione può essere costituita da transazioni di lunga durata. Per capire come questi due fenomeni sono correlati, ci aiuterà a considerare le restanti due balene LMDB.

3.2. Balena #2. B+-albero

Per emulare le tabelle in cima a un archivio di valori-chiave, le seguenti operazioni devono essere presenti nella sua API:

1. Inserimento di un nuovo elemento.
2. Cerca un elemento con una data chiave.
3. Eliminazione di un elemento.
4. Iterare su intervalli chiave nel loro ordinamento.

La struttura dati più semplice che può facilmente implementare tutte e quattro le operazioni è un albero di ricerca binario. Ciascuno dei suoi nodi è una chiave che divide l'intero sottoinsieme di chiavi figlie in due sottoalberi. A sinistra ci sono quelli più piccoli del genitore ea destra quelli più grandi. L'ottenimento di un set ordinato di chiavi si ottiene attraverso uno dei classici attraversamenti ad albero.​

Gli alberi binari hanno due inconvenienti fondamentali che impediscono loro di essere efficaci come struttura di dati del disco. Innanzitutto, il grado del loro equilibrio è imprevedibile. Esiste un rischio considerevole di ottenere alberi in cui l'altezza dei diversi rami può variare notevolmente, il che peggiora notevolmente 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à nella memoria: i nodi vicini (in termini di collegamenti tra loro) possono trovarsi su pagine completamente diverse nella memoria virtuale. Di conseguenza, anche un semplice attraversamento di diversi nodi vicini in un albero può richiedere la visita di un numero comparabile di pagine. Questo è un problema anche quando parliamo dell'efficienza degli alberi binari come struttura dati in memoria, poiché la rotazione costante delle pagine nella cache del processore non è economica. Quando si tratta di aumentare frequentemente le pagine relative ai nodi dal disco, le cose si mettono davvero male. deplorevole.

I B-tree, essendo un'evoluzione degli alberi binari, risolvono i problemi individuati nel paragrafo precedente. Innanzitutto, sono autobilanciati. In secondo luogo, ciascuno dei loro nodi divide l'insieme di chiavi figlie non in 2, ma in M ​​sottoinsiemi ordinati e il numero M può essere piuttosto grande, dell'ordine di diverse centinaia o addirittura migliaia.

In tal modo:

1. Ogni nodo ha un gran numero di chiavi già ordinate e gli alberi sono molto bassi.
2. L'albero acquisisce la proprietà di località in memoria, poiché le chiavi che hanno un valore vicino si trovano naturalmente l'una accanto all'altra su uno o nodi vicini.
3. Riduce il numero di nodi di transito durante la discesa dell'albero durante un'operazione di ricerca.
4. Riduce il numero di nodi di destinazione letti per query di intervallo, poiché ognuno di essi contiene già un numero elevato di chiavi ordinate.

LMDB utilizza una variante dell'albero B chiamato albero B+ per memorizzare i dati. Il diagramma sopra mostra i tre tipi di nodi che contiene:

1. In cima c'è la radice. Non materializza nient'altro che il concetto di un database all'interno di un repository. All'interno di una singola istanza LMDB, puoi creare più database che condividono lo spazio degli indirizzi virtuali mappati. Ognuno di loro parte dalla propria radice.
2. Al livello più basso ci sono le foglie (foglia). Sono loro e solo loro che contengono le coppie chiave-valore memorizzate nel database. A proposito, questa è la particolarità degli alberi B+. Se un albero B normale immagazzina le parti di valore nei nodi di tutti i livelli, allora la variazione B+ è solo a quello più basso. Fissato questo fatto, nel seguito chiameremo semplicemente B-tree il sottotipo dell'albero utilizzato in LMDB.
3. Tra la radice e le foglie ci sono 0 o più livelli tecnici con nodi di navigazione (ramo). Il loro compito è dividere il mazzo di chiavi ordinato tra le foglie.

Fisicamente, i nodi sono blocchi di memoria di lunghezza predeterminata. La loro dimensione è un multiplo della dimensione delle pagine di memoria nel sistema operativo, di cui abbiamo parlato sopra. La struttura del nodo è mostrata di seguito. L'intestazione contiene meta-informazioni, la più ovvia delle quali, ad esempio, è il checksum. Seguono le informazioni sugli offset, lungo i quali si trovano le celle con i dati. Il ruolo dei dati può essere o chiavi, se parliamo di nodi di navigazione, o intere coppie chiave-valore nel caso di foglie.Puoi leggere di più sulla struttura delle pagine nel lavoro "Valutazione dei negozi di valore-chiave ad alte prestazioni".

Dopo aver affrontato il contenuto interno dei nodi di pagina, rappresenteremo ulteriormente il B-tree di LMDB in modo semplificato nella forma seguente.

Le pagine con nodi sono disposte in sequenza sul disco. Le pagine con un numero più alto si trovano verso la fine del file. La cosiddetta meta pagina (meta pagina) contiene informazioni sugli offset, che possono essere utilizzate per trovare le radici di tutti gli alberi. Quando un file viene aperto, LMDB scansiona il file pagina per pagina dalla fine all'inizio alla ricerca di una meta pagina valida e trova i database esistenti attraverso di essa.​

Ora, avendo un'idea della struttura logica e fisica dell'organizzazione dei dati, possiamo procedere a considerare la terza balena di LMDB. È con il suo aiuto che tutte le modifiche all'archiviazione avvengono in modo transazionale e in isolamento l'una dall'altra, conferendo al database nel suo insieme anche la proprietà multiversione.

3.3. Balena #3. copia su scrittura

Alcune operazioni dell'albero B comportano l'esecuzione di un'intera serie di modifiche ai suoi nodi. Un esempio è l'aggiunta di una nuova chiave a un nodo che ha già raggiunto la sua capacità massima. In questo caso, è necessario, in primo luogo, dividere il nodo in due e, in secondo luogo, aggiungere un collegamento al nuovo nodo figlio scorporato nel suo genitore. Questa procedura è potenzialmente molto pericolosa. Se per qualche motivo (arresto anomalo, interruzione di corrente, ecc.) si verifica solo una parte dei cambiamenti della serie, l'albero rimarrà in uno stato incoerente.

Una soluzione tradizionale per rendere un database tollerante agli errori consiste nell'aggiungere un'ulteriore struttura dati basata su disco, il registro delle transazioni, noto anche come registro write-ahead (WAL), accanto al B-tree. È un file, alla fine del quale, rigorosamente prima della modifica del B-tree stesso, viene scritta l'operazione prevista. Pertanto, se durante l'autodiagnosi viene rilevato un danneggiamento dei dati, il database consulta il registro per ripulirsi.

LLMDB ha scelto un metodo diverso come meccanismo di tolleranza agli errori, chiamato copia su scrittura. La sua essenza è che invece di aggiornare i dati su una pagina esistente, prima li copia interamente e apporta tutte le modifiche già nella copia.​

Inoltre, affinché i dati aggiornati siano disponibili, è necessario modificare il collegamento al nodo che è diventato aggiornato nel nodo genitore in relazione ad esso. Poiché anche per questo deve essere modificato, è anche precopiato. Il processo continua in modo ricorsivo fino alla radice. I dati sulla meta pagina sono gli ultimi a cambiare.​​

Se improvvisamente il processo si arresta in modo anomalo durante la procedura di aggiornamento, non verrà creata una nuova meta pagina o non verrà scritta su disco fino alla fine e il suo checksum non sarà corretto. In entrambi i casi, le nuove pagine saranno irraggiungibili e quelle vecchie non ne risentiranno. Ciò elimina la necessità per LMDB di scrivere in anticipo il registro per mantenere la coerenza dei dati. Di fatto, la struttura di memorizzazione dei dati su disco, sopra descritta, assume contemporaneamente la sua funzione. L'assenza di un registro delle transazioni esplicito è una delle caratteristiche di LMDB, che fornisce un'elevata velocità di lettura dei dati

Il costrutto risultante, chiamato B-tree append-only, fornisce naturalmente l'isolamento delle transazioni e il multiversioning. In LMDB, a ogni transazione aperta è associata una radice dell'albero aggiornata. Finché la transazione non viene completata, le pagine dell'albero ad essa associate non verranno mai modificate o riutilizzate per nuove versioni dei dati, quindi puoi lavorare per tutto il tempo che desideri esattamente con il set di dati che era rilevante al momento ora in cui la transazione è stata aperta, anche se l'archiviazione continua ad essere aggiornata attivamente in questo momento. Questa è l'essenza del multiversioning, che rende LMDB una fonte di dati ideale per i nostri cari UICollectionView. Dopo aver aperto una transazione, non è necessario aumentare l'impronta di memoria dell'applicazione, pompando frettolosamente i dati correnti in una struttura in memoria, temendo di non rimanere senza nulla. Questa caratteristica distingue LMDB dallo stesso SQLite, che non può vantare un isolamento così totale. Avendo aperto due transazioni in quest'ultima e cancellando un certo record all'interno di una di esse, non è più possibile ottenere lo stesso record all'interno della seconda rimanente.

Il rovescio della medaglia è il consumo potenzialmente significativamente più elevato di memoria virtuale. La diapositiva mostra come apparirà la struttura del database se viene modificata contemporaneamente con 3 transazioni di lettura aperte che esaminano diverse versioni del database. Poiché LMDB non può riutilizzare i nodi raggiungibili dalle radici associate alle transazioni effettive, lo storage non ha altra scelta che allocare un'altra quarta radice in memoria e clonare ancora una volta le pagine modificate sotto di essa.

Qui non sarà superfluo richiamare la sezione sui file mappati in memoria. Sembra che il consumo aggiuntivo di memoria virtuale non dovrebbe infastidirci molto, dal momento che non contribuisce al footprint di memoria dell'applicazione. Tuttavia, allo stesso tempo, è stato notato che iOS è molto avaro nell'allocarlo e non possiamo fornire una regione LMDB da 1 terabyte su un server o desktop dalla spalla del master e non pensare affatto a questa funzione. Quando possibile, dovresti cercare di mantenere la durata delle transazioni il più breve possibile.

4. Progettare uno schema di dati sopra l'API chiave-valore

Cominciamo ad analizzare l'API osservando le astrazioni di base fornite da LMDB: ambiente e database, chiavi e valori, transazioni e cursori.

Una nota sui listati di codice

Tutte le funzioni dell'API pubblica LMDB restituiscono il risultato del loro lavoro sotto forma di codice di errore, ma in tutti i listati successivi il suo controllo viene omesso per motivi di concisione.In pratica, abbiamo utilizzato il nostro codice per interagire con il repository. forchetta Wrapper C++ ldbxx, in cui gli errori si materializzano come eccezioni C++.

Come modo più veloce per connettere LMDB a un progetto iOS o macOS, offro il mio CocoaPod POSLMDB.

4.1. Astrazioni di base

Ambiente

Struttura MDB_env è il repository dello stato interno dell'LMDB. Famiglia di funzioni prefissate mdb_env consente di configurare alcune delle sue proprietà. Nel caso più semplice, l'inizializzazione del motore è simile a questa.

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 è la dimensione dello spazio degli indirizzi virtuali a cui è mappato il file di archiviazione. Sfortunatamente, anche sullo stesso dispositivo, il valore specifico può variare in modo significativo da un'esecuzione all'altra. Per tenere conto di questa funzionalità di iOS, selezioniamo dinamicamente la quantità massima di spazio di archiviazione. Partendo da un certo valore, si dimezza successivamente fino alla funzione mdb_env_open non restituirà un risultato diverso da ENOMEM. In teoria, c'è un modo opposto: prima assegna un minimo di memoria al motore e poi, quando vengono ricevuti errori MDB_MAP_FULL, aumentalo. Tuttavia, è molto più spinoso. Il motivo è che la procedura per rimappare la memoria utilizzando la funzione mdb_env_set_map_size invalida tutte le entità (cursori, transazioni, chiavi e valori) ricevute in precedenza dal motore. Tenere conto di una tale svolta di eventi nel codice porterà alla sua significativa complicazione. Se, tuttavia, la memoria virtuale ti è molto cara, allora questo potrebbe essere un motivo per guardare al fork che è andato molto avanti. MDBX, dove tra le funzionalità dichiarate c'è la “regolazione automatica delle dimensioni del database al volo”.

Il secondo parametro, il cui valore predefinito non ci andava bene, regola i meccanismi per garantire la sicurezza del thread. Sfortunatamente, almeno in iOS 10, ci sono problemi con il supporto dell'archiviazione locale dei thread. Per questo motivo, nell'esempio precedente, il repository viene aperto con il flag MDB_NOTLS. Inoltre, è anche richiesto forchetta wrapper C++ ldbxxper tagliare le variabili con e in questo attributo.

Basi di dati

Il database è un'istanza separata dell'albero B di cui abbiamo parlato sopra. La sua apertura avviene all'interno di una transazione, che a prima vista può sembrare un po' strana.

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 un database specifico. Questo concetto consente di eseguire operazioni atomiche su entità situate in diversi database. In teoria, questo apre la possibilità di modellare tabelle sotto forma di diversi database, ma una volta sono andato dall'altra parte, descritto in dettaglio di seguito.

Chiavi e valori

Struttura MDB_val modella il concetto sia di una chiave che di un valore. Il repository non ha idea della loro semantica. Per lei, qualcosa di diverso è solo un array di byte di una data dimensione. La dimensione massima della chiave è di 512 byte.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Il negozio utilizza un comparatore per ordinare le chiavi in ​​ordine crescente. Se non lo sostituisci con il tuo, verrà utilizzato quello predefinito, che li ordina byte per byte in ordine lessicografico.​

Operazioni

Il dispositivo di transazione è descritto in dettaglio in capitolo precedente, quindi qui ripeterò le loro proprietà principali in una breve riga:

1. Supporto per tutte le proprietà di base ACIDOParole chiave: atomicità, consistenza, isolamento e affidabilità. Non posso fare a meno di notare che in termini di durabilità su macOS e iOS c'è un bug risolto in MDBX. Puoi leggere di più nel loro README.
2. L'approccio al multithreading è descritto dallo schema "single writer / multiple reader". Gli scrittori si bloccano a vicenda, ma non bloccano i lettori. I lettori non bloccano gli scrittori o l'un l'altro.
3. Supporto per transazioni nidificate.
4. Supporto multiversione.

Il multiversioning in LMDB è così buono che voglio dimostrarlo in azione. Il codice sottostante mostra che ogni transazione funziona esattamente con la versione del database che era rilevante al momento della sua apertura, essendo completamente isolata da tutte le modifiche successive. L'inizializzazione del repository e l'aggiunta di un record di test non ha alcun interesse, quindi questi rituali vengono lasciati sotto lo spoiler.

Aggiunta di una voce 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;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Facoltativamente, consiglio di provare lo stesso trucco con SQLite e vedere cosa succede.

Il multiversioning porta vantaggi molto interessanti alla vita di uno sviluppatore iOS. Utilizzando questa proprietà, è possibile regolare in modo semplice e naturale la frequenza di aggiornamento dell'origine dati per i form delle schermate in base a considerazioni sull'esperienza dell'utente. Ad esempio, prendiamo una tale funzionalità dell'applicazione Mail.ru Cloud come il caricamento automatico dei contenuti dalla galleria multimediale di sistema. Con una buona connessione, il client è in grado di aggiungere diverse foto al secondo al server. Se aggiorni dopo ogni download UICollectionView con i contenuti multimediali nel cloud dell'utente, puoi dimenticare i 60 fps e lo scorrimento fluido durante questo processo. Per evitare frequenti aggiornamenti dello schermo, è necessario limitare in qualche modo la velocità di modifica dei dati nella base UICollectionViewDataSource.

Se il database non supporta il multiversioning e ti consente di lavorare solo con lo stato corrente corrente, per creare uno snapshot dei dati stabile nel tempo, devi copiarlo in una struttura di dati in memoria o in una tabella temporanea. Entrambi questi approcci sono molto costosi. Nel caso dell'archiviazione in memoria, otteniamo sia i costi di memoria causati dall'archiviazione di oggetti costruiti sia i costi di tempo associati alle trasformazioni ORM ridondanti. Per quanto riguarda il tavolo temporaneo, questo è un piacere ancora più costoso, che ha senso solo in casi non banali.

Multiversioning LMDB risolve il problema di mantenere un'origine dati stabile in un modo molto elegante. È sufficiente aprire una transazione e voilà: fino a quando non la completiamo, è garantito che il set di dati sarà corretto. La logica della sua velocità di aggiornamento è ora interamente nelle mani del livello di presentazione, senza sovraccarico di risorse significative.

Cursori

I cursori forniscono un meccanismo per l'iterazione ordinata su coppie chiave-valore attraversando un albero B. Senza di essi, sarebbe impossibile modellare in modo efficace le tabelle nel database, a cui ora ci rivolgiamo.

4.2. Modellazione di tavoli

La proprietà di ordinamento chiave consente di costruire un'astrazione di primo livello come una tabella sopra le astrazioni di base. Consideriamo questo processo sull'esempio della tabella principale del client cloud, in cui sono memorizzate nella cache le informazioni su tutti i file e le cartelle dell'utente.

Schema della tabella

Uno degli scenari comuni per cui la struttura di una tabella con un albero di cartelle dovrebbe essere affinata è quello di selezionare tutti gli elementi che si trovano all'interno di una determinata directory.Un buon modello di organizzazione dei dati per query efficienti di questo tipo è Elenco di adiacenza. Per implementarlo sopra l'archiviazione di valori-chiave, è necessario ordinare le chiavi di file e cartelle in modo tale che siano raggruppate in base all'appartenenza alla directory principale. Inoltre, per visualizzare il contenuto della directory nella forma familiare a un utente Windows (prima le cartelle, poi i file, entrambi in ordine alfabetico), è necessario includere nella chiave i corrispondenti campi aggiuntivi.

L'immagine seguente mostra come, in base all'attività, potrebbe apparire la rappresentazione delle chiavi come un array di byte. Prima vengono posizionati i byte con l'identificatore della directory principale (rosso), quindi con il tipo (verde) e già nella coda con il nome (blu).Essendo ordinati dal comparatore LMDB predefinito in ordine lessicografico, vengono ordinati in il modo richiesto. L'attraversamento sequenziale delle chiavi con lo stesso prefisso rosso ci fornisce i valori ad esse associati nell'ordine in cui dovrebbero essere visualizzati nell'interfaccia utente (a destra), senza richiedere alcuna ulteriore post-elaborazione.

Serializzazione di chiavi e valori

Esistono molti metodi per serializzare oggetti in tutto il mondo. Poiché non avevamo altri requisiti oltre alla velocità, abbiamo scelto per noi stessi il più veloce possibile: un dump della memoria occupato da un'istanza della struttura del linguaggio C. Quindi, la chiave di un elemento di directory può essere modellata dalla seguente struttura NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Salvare NodeKey nella necessità di archiviazione nell'oggetto MDB_val posizionare il puntatore ai dati all'indirizzo dell'inizio della struttura e calcolarne la dimensione con la funzione sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

Nel primo capitolo sui criteri di selezione del database, ho menzionato la riduzione al minimo delle allocazioni dinamiche come parte delle operazioni CRUD come un importante fattore di selezione. Codice funzione serialize mostra come, nel caso di LMDB, possono essere completamente evitati quando nuovi record vengono inseriti nel database. L'array di byte in entrata dal server viene prima trasformato in strutture stack, quindi vengono banalmente scaricati nello storage. Dato che non ci sono allocazioni dinamiche all'interno di LMDB, puoi ottenere una situazione fantastica per gli standard di iOS: usa solo la memoria dello stack per lavorare con i dati dalla rete al disco!

Chiavi di ordinazione con un comparatore binario

La relazione di ordine chiave è data da una funzione speciale chiamata comparatore. Poiché il motore non sa nulla della semantica dei byte che contengono, il comparatore predefinito non ha altra scelta che disporre le chiavi in ​​ordine lessicografico, ricorrendo al loro confronto byte per byte. Usarlo per sistemare le strutture è simile alla rasatura con un'ascia da intaglio. Tuttavia, in casi semplici, trovo questo metodo accettabile. L'alternativa è descritta di seguito, ma qui noterò un paio di rastrelli sparsi lungo il percorso.

La prima cosa da tenere a mente è la rappresentazione in memoria dei tipi di dati primitivi. Quindi, su tutti i dispositivi Apple, le variabili intere sono memorizzate nel formato piccolo endian. Ciò significa che il byte meno significativo sarà a sinistra e non sarai in grado di ordinare i numeri interi utilizzando il loro confronto byte per byte. Ad esempio, provare a eseguire questa operazione con un insieme di numeri da 0 a 511 produrrà il 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, gli interi devono essere memorizzati nella chiave in un formato adatto al comparatore di byte. Le funzioni della famiglia aiuteranno a realizzare la necessaria trasformazione. hton* (in particolare htons per i numeri a doppio byte dell'esempio).

Il formato per rappresentare le stringhe nella programmazione è, come sai, un intero storia. Se la semantica delle stringhe, così come la codifica utilizzata per rappresentarle in memoria, suggerisce che potrebbe esserci più di un byte per carattere, allora è meglio abbandonare immediatamente l'idea di utilizzare un comparatore predefinito.

La seconda cosa da tenere a mente è principi di allineamento compilatore di campi struct. A causa loro, in memoria tra i campi possono essere formati byte con valori spazzatura, il che, ovviamente, interrompe l'ordinamento dei byte. Per eliminare la spazzatura, devi dichiarare i campi in un ordine rigorosamente definito, tenendo a mente le regole di allineamento, oppure utilizzare l'attributo nella dichiarazione della struttura packed.

Ordinamento delle chiavi tramite un comparatore esterno

La logica di confronto delle chiavi può rivelarsi troppo complessa per un comparatore binario. Uno dei tanti motivi è la presenza di campi tecnici all'interno delle strutture. Illustrerò la loro occorrenza sull'esempio di una chiave a noi già familiare per un elemento di directory.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Nonostante tutta la sua semplicità, nella stragrande maggioranza dei casi consuma troppa memoria. Il title buffer è di 256 byte, anche se in media i nomi di file e cartelle raramente superano i 20-30 caratteri.

​Una delle tecniche standard per ottimizzare le dimensioni di un record consiste nel ritagliarlo per adattarlo alle dimensioni effettive. La sua essenza è che i contenuti di tutti i campi di lunghezza variabile sono memorizzati in un buffer alla fine della struttura e le loro lunghezze sono memorizzate in variabili separate.Secondo questo approccio, la chiave NodeKey si trasforma nel modo seguente.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

Inoltre, durante la serializzazione, non specificato come dimensione dei dati sizeof l'intera struttura e la dimensione di tutti i campi è una 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, abbiamo ottenuto un notevole risparmio nello spazio occupato dalle chiavi. Tuttavia, a causa del campo tecnico nameLength, il comparatore binario predefinito non è più adatto per il confronto delle chiavi. Se non lo sostituiamo con il nostro, la lunghezza del nome sarà un fattore prioritario nell'ordinamento rispetto al nome stesso.

LMDB consente a ciascun database di avere la propria funzione di confronto delle chiavi. Questo viene fatto usando la funzione mdb_set_compare rigorosamente prima dell'apertura. Per ovvi motivi, un database non può essere modificato per tutta la sua durata. In ingresso, il comparatore riceve due chiavi in ​​formato binario, e in uscita restituisce il risultato del confronto: minore di (-1), maggiore di (1) o uguale (0). pseudocodice per NodeKey sembra così.

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é tutte le chiavi nel database sono dello stesso tipo, è consentito trasmettere incondizionatamente la loro rappresentazione in byte al tipo della struttura dell'applicazione della chiave. C'è una sfumatura qui, ma sarà discussa un po 'più in basso nella sottosezione "Lettura dei record".

Serializzazione del valore

Con le chiavi dei record memorizzati, LMDB lavora in modo estremamente intenso. Vengono confrontati tra loro nell'ambito di qualsiasi operazione applicativa e le prestazioni dell'intera soluzione dipendono dalla velocità del comparatore. In un mondo ideale, il comparatore binario predefinito dovrebbe essere sufficiente per confrontare le chiavi, ma se dovessi davvero usare il tuo, allora la procedura per deserializzare le chiavi dovrebbe essere il più veloce possibile.

Il database non è particolarmente interessato alla parte Valore del record (valore). La sua conversione da rappresentazione byte a oggetto avviene solo quando è già richiesta dal codice dell'applicazione, ad esempio per visualizzarla sullo schermo. Poiché ciò accade relativamente raramente, i requisiti per la velocità di questa procedura non sono così critici e nella sua implementazione siamo molto più liberi di concentrarci sulla comodità.Ad esempio, per serializzare i metadati sui file che non sono ancora stati scaricati, utilizziamo NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

Tuttavia, ci sono momenti in cui le prestazioni contano. Ad esempio, quando salviamo metainformazioni sulla struttura dei file del cloud utente, utilizziamo lo stesso dump della memoria dell'oggetto. Il clou del compito di generare la loro rappresentazione serializzata è il fatto che gli elementi di una directory sono modellati da una gerarchia di classi.

Per la sua implementazione nel linguaggio C, i campi specifici degli eredi vengono portati in strutture separate e la loro connessione con quella di base viene specificata tramite un campo di tipo unione. Il contenuto effettivo dell'unione è specificato 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 di record

La chiave e il valore serializzati possono essere aggiunti all'archivio. Per questo, viene utilizzata la funzione mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

In fase di configurazione, al repository può essere consentito o vietato di memorizzare più record con la stessa chiave.​​ Se la duplicazione delle chiavi è vietata, quando si inserisce un record, è possibile determinare se è consentito o meno l'aggiornamento di un record già esistente. Se lo sfilacciamento può verificarsi solo a causa di un errore nel codice, puoi assicurarti contro di esso specificando il flag NOOVERWRITE.

Lettura dei record

La funzione per leggere i record in LMDB è mdb_get. Se la coppia chiave-valore è rappresentata da strutture scaricate in precedenza, questa procedura è simile a questa.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

L'elenco presentato mostra come la serializzazione attraverso un dump di strutture consente di eliminare le allocazioni dinamiche non solo durante la scrittura, ma anche durante la lettura dei dati. Derivato da funzione mdb_get il puntatore guarda esattamente l'indirizzo di memoria virtuale in cui il database memorizza la rappresentazione in byte dell'oggetto. Otteniamo infatti una sorta di ORM, quasi gratuito che fornisce un'altissima velocità di lettura dei dati. Nonostante tutta la bellezza dell'approccio, è necessario ricordare diverse caratteristiche ad esso associate.

1. Per una transazione di sola lettura, è garantito che un puntatore a una struttura di valore rimanga valido solo fino alla chiusura della transazione. Come notato in precedenza, le pagine del B-tree su cui risiede l'oggetto, grazie al principio del copy-on-write, rimangono invariate fintanto che almeno una transazione fa riferimento ad esse. Allo stesso tempo, non appena completata l'ultima transazione ad esse associata, le pagine possono essere riutilizzate per nuovi dati. Se è necessario che gli oggetti sopravvivano alla transazione che li ha creati, devono comunque essere copiati.
2. Per una transazione readwrite, il puntatore al valore-struttura risultante sarà valido solo fino alla prima procedura di modifica (scrittura o eliminazione di dati).
3. Anche se la struttura NodeValue non a tutti gli effetti, ma ritagliato (vedere la sottosezione "Ordinamento delle chiavi tramite un comparatore esterno"), tramite il puntatore, è possibile accedere facilmente ai suoi campi. L'importante è non dereferenziarlo!
4. In nessun caso è possibile modificare la struttura tramite il puntatore ricevuto. Tutte le modifiche devono essere apportate solo tramite il metodo mdb_put. Tuttavia, con tutto il desiderio di farlo, non funzionerà, poiché l'area di memoria in cui si trova questa struttura è mappata in modalità di sola lettura.
5. Rimappare un file nello spazio degli indirizzi di un processo per, ad esempio, aumentare la dimensione massima di archiviazione utilizzando la funzione mdb_env_set_map_size invalida completamente tutte le transazioni e le entità correlate in generale e i puntatori alla lettura degli oggetti in particolare.

Infine, un'altra caratteristica è così insidiosa che la divulgazione della sua essenza non rientra solo in un altro punto. Nel capitolo sull'albero B, ho fornito un diagramma dell'organizzazione delle sue pagine in memoria. Ne consegue che l'indirizzo dell'inizio del buffer con dati serializzati può essere assolutamente arbitrario. Per questo motivo, il puntatore a loro, ottenuto nella struttura MDB_val e il cast a un puntatore a una struttura è generalmente non allineato. Allo stesso tempo, le architetture di alcuni chip (nel caso di iOS, questo è armv7) richiedono che l'indirizzo di qualsiasi dato sia un multiplo della dimensione di una parola macchina, o, in altre parole, il testimone del sistema (per armv7, questo è 32 bit). In altre parole, un'operazione come *(int *foo)0x800002 su di loro è equiparato alla fuga e conduce all'esecuzione con un verdetto EXC_ARM_DA_ALIGN. Ci sono due modi per evitare un destino così triste.

Il primo consiste nel copiare in anticipo i dati in una struttura allineata nota. Ad esempio, su un comparatore personalizzato, ciò si rifletterà come segue.

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 modo alternativo consiste nel notificare in anticipo al compilatore che le strutture con una chiave e un valore potrebbero non essere allineate utilizzando un attributo aligned(1). Su ARM lo stesso effetto può essere per ottenere e utilizzando l'attributo imballato. Considerando che contribuisce anche all'ottimizzazione dello spazio occupato dalla struttura, questo metodo mi sembra comunque preferibile приводит per aumentare il costo 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;

Intervallo di query

Per iterare su un gruppo di record, LMDB fornisce un'astrazione del cursore. Diamo un'occhiata a come lavorarci usando l'esempio di una tabella con i metadati del cloud dell'utente che ci sono già familiari.

Come parte della visualizzazione di un elenco di file in una directory, è necessario trovare tutte le chiavi a cui sono associati i file e le cartelle figlio. Nelle sottosezioni precedenti, abbiamo ordinato le chiavi NodeKey in modo che vengano prima ordinati in base all'ID della directory padre. Pertanto, tecnicamente, il compito di ottenere il contenuto di una cartella si riduce a posizionare il cursore sul limite superiore di un gruppo di tasti con un dato prefisso, seguito dall'iterazione fino al limite inferiore.

Puoi trovare il limite superiore "sulla fronte" mediante ricerca sequenziale. Per fare ciò, il cursore viene posizionato all'inizio dell'intero elenco di chiavi nel database e quindi incrementato finché la chiave con l'identificatore della directory padre non appare sotto di essa. Questo approccio ha 2 ovvi inconvenienti:

1. La complessità lineare della ricerca, anche se, come sai, negli alberi in generale e in un B-tree in particolare, può essere effettuata in tempo logaritmico.​
2. Invano, tutte le pagine che precedono quella desiderata vengono sollevate dal file alla memoria principale, che è estremamente costosa.

Fortunatamente, l'API LMDB fornisce un modo efficiente per posizionare inizialmente il cursore.Per fare ciò, è necessario formare una chiave il cui valore sia noto essere minore o uguale alla chiave situata sul limite superiore dell'intervallo. Ad esempio, in relazione all'elenco nella figura sopra, possiamo creare una chiave in cui il campo parentId sarà uguale a 2, e tutto il resto è riempito di zeri. Tale tasto parzialmente riempito viene inserito nell'input della funzione mdb_cursor_get indicando il funzionamento 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 viene trovato il limite superiore del gruppo di chiavi, lo ripetiamo finché non incontriamo o la chiave con un'altra parentId, o le chiavi non si esauriranno affatto.​

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

Ciò che è bello, come parte dell'iterazione usando mdb_cursor_get, otteniamo non solo la chiave, ma anche il valore. Se, per soddisfare le condizioni di selezione, è necessario controllare, tra le altre cose, i campi dalla parte del valore del record, allora sono abbastanza accessibili a se stessi senza gesti aggiuntivi.

4.3. Modellazione delle relazioni tra tabelle

Ad oggi, siamo riusciti a considerare tutti gli aspetti della progettazione e del lavoro con un database a tabella singola. Possiamo dire che una tabella è un insieme di record ordinati costituiti da coppie chiave-valore dello stesso tipo. Se visualizzi una chiave come un rettangolo e il suo valore associato come una casella, ottieni un diagramma visivo del database.

Tuttavia, nella vita reale, raramente è possibile cavarsela con così poco sangue. Spesso in un database è necessario, in primo luogo, disporre di più tabelle e, in secondo luogo, effettuare selezioni in esse in un ordine diverso dalla chiave primaria. Quest'ultima sezione è dedicata ai problemi della loro creazione e interconnessione.

Tabelle indice

L'app cloud ha una sezione "Galleria". Visualizza i contenuti multimediali dell'intero cloud, ordinati per data. Per l'implementazione ottimale di tale selezione, accanto alla tabella principale, è necessario crearne un'altra con un nuovo tipo di chiavi. Conterranno un campo con la data di creazione del file, che fungerà da criterio di ordinamento principale. Poiché le nuove chiavi fanno riferimento agli stessi dati delle chiavi nella tabella sottostante, vengono denominate chiavi di indice. Sono evidenziati in arancione nell'immagine qui sotto.

Al fine di separare tra loro le chiavi di tabelle diverse all'interno dello stesso database, è stato aggiunto a tutte un ulteriore campo tecnico tableId. Impostando la massima priorità per l'ordinamento, raggrupperemo le chiavi prima per tabelle e già all'interno delle tabelle, secondo le nostre regole.​

La chiave di indice fa riferimento agli stessi dati della chiave primaria. La semplice implementazione di questa proprietà associando ad essa una copia della parte di valore della chiave primaria non è ottimale da diversi punti di vista contemporaneamente:​

1. Dal punto di vista dello spazio occupato, i metadati possono essere piuttosto ricchi.
2. Dal punto di vista delle prestazioni, poiché durante l'aggiornamento dei metadati del nodo, dovrai sovrascrivere due chiavi.
3. Dal punto di vista del supporto del codice, dopotutto, se dimentichiamo di aggiornare i dati per una delle chiavi, otterremo un sottile bug di incoerenza dei dati nell'archiviazione.

Successivamente, considereremo come eliminare queste carenze.

Organizzazione delle relazioni tra tabelle

Il modello è adatto per collegare una tabella di indice con quella principale "chiave come valore". Come suggerisce il nome, la parte del valore del record dell'indice è una copia del valore della chiave primaria. Questo approccio elimina tutti gli svantaggi sopra elencati associati all'archiviazione di una copia della parte valore del record primario. L'unico costo è che per ottenere il valore dalla chiave dell'indice, è necessario effettuare 2 query al database invece di una. Schematicamente, lo schema del database risultante è il seguente.

Un altro modello per organizzare le relazioni tra le tabelle è "chiave ridondante". La sua essenza è aggiungere ulteriori attributi alla chiave, che non sono necessari per l'ordinamento, ma per ricreare la chiave associata.Ci sono esempi reali del suo utilizzo nell'applicazione Mail.ru Cloud, tuttavia, per evitare di immergersi in profondità nel contesto di framework iOS specifici, darò un esempio fittizio, ma più comprensibile.

I client mobili cloud hanno una pagina che mostra tutti i file e le cartelle che l'utente ha condiviso con altre persone. Poiché esistono relativamente pochi file di questo tipo e vi sono molte informazioni specifiche sulla pubblicità ad essi associata (a chi è concesso l'accesso, con quali diritti, ecc.), non sarà razionale caricarlo della parte relativa al valore di il record nella tabella principale. Tuttavia, se desideri visualizzare tali file offline, devi comunque archiviarli da qualche parte. Una soluzione naturale è creare una tabella separata per questo. Nel diagramma seguente, la sua chiave è preceduta da "P" e il segnaposto "propname" può essere sostituito con il valore più specifico "public info".​

Tutti i metadati univoci, per il bene dei quali è stata creata la nuova tabella, vengono spostati nella parte del valore del record. Allo stesso tempo, non voglio duplicare i dati su file e cartelle già archiviati nella tabella principale. Invece, i dati ridondanti vengono aggiunti alla chiave "P" sotto forma dei campi "ID nodo" e "timestamp". Grazie a loro, puoi costruire una chiave di indice, dalla quale puoi ottenere la chiave primaria, dalla quale, infine, puoi ottenere i metadati del nodo.

Conclusione

Valutiamo positivamente i risultati dell'implementazione di LMDB. Successivamente, il numero di blocchi delle applicazioni è diminuito del 30%.

I risultati del lavoro svolto hanno trovato riscontro al di fuori del team iOS. Attualmente, anche una delle principali sezioni "File" nell'applicazione Android è passata all'utilizzo di LMDB e altre parti sono in arrivo. Il linguaggio C, in cui è implementata l'archiviazione del valore-chiave, è stato di grande aiuto per rendere inizialmente l'associazione dell'applicazione attorno ad essa multipiattaforma nel linguaggio C ++. Per una connessione perfetta della libreria C ++ risultante con il codice della piattaforma in Objective-C e Kotlin, è stato utilizzato un generatore di codice Jinni da Dropbox, ma questa è un'altra storia.

Fonte: habr.com