In het najaar van 2019 vond een langverwacht evenement plaats in het Mail.ru Cloud iOS-team. De belangrijkste database voor permanente opslag van de applicatiestatus is behoorlijk exotisch geworden voor de mobiele wereld (LMDB). Onder de snit wordt uw aandacht gevraagd voor de gedetailleerde beoordeling in vier delen. Laten we het eerst hebben over de redenen voor zo'n niet-triviale en moeilijke keuze. Laten we dan verder gaan met de overweging van drie walvissen in het hart van de LMDB-architectuur: memory-mapped files, B+tree, copy-on-write-benadering voor het implementeren van transactionele en multiversioning. Eindelijk, als toetje - het praktische gedeelte. Daarin zullen we bekijken hoe we een basisschema kunnen ontwerpen en implementeren met verschillende tabellen, waaronder een indextabel, bovenop de low-level key-value API.
Inhoud
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Implementatiemotivatie
Een keer per jaar, in 2015, zorgden we ervoor dat we een metriek namen, hoe vaak de interface van onze applicatie achterblijft. Dit hebben we niet zomaar gedaan. We krijgen steeds meer klachten over het feit dat de applicatie soms niet meer reageert op acties van gebruikers: knoppen worden niet ingedrukt, lijsten scrollen niet, enz. Over de mechanica van metingen op AvitoTech, dus hier geef ik alleen de volgorde van de nummers.
De meetresultaten werden voor ons een koude douche. Het bleek dat de problemen veroorzaakt door bevriezingen veel groter zijn dan alle andere. Als, voordat we ons dit realiseerden, de belangrijkste technische indicator van kwaliteit crashvrij was, dan na de focus op vriesvrij.
Hebben gebouwd en hebben doorgebracht и analyse van hun oorzaken, werd de belangrijkste vijand duidelijk: zware zakelijke logica die wordt uitgevoerd in de rode draad van de applicatie. Een natuurlijke reactie op deze schande was een brandend verlangen om het in werkstromen te stoppen. Voor een systematische oplossing van dit probleem hebben we onze toevlucht genomen tot een multi-threaded architectuur gebaseerd op lichtgewicht actoren. Ik heb haar aanpassingen opgedragen voor de iOS-wereld in het collectief twitter en . Als onderdeel van het huidige verhaal wil ik die aspecten van de beslissing benadrukken die de keuze van de database hebben beïnvloed
Het actormodel van systeemorganisatie gaat ervan uit dat multithreading de tweede essentie wordt. Modelobjecten daarin overschrijden graag threadgrenzen. En dat doen ze niet soms en op sommige plaatsen, maar bijna constant en overal.
De database is een van de hoeksteencomponenten in het gepresenteerde diagram. De belangrijkste taak is het implementeren van een macropatroon . Als het in de bedrijfswereld wordt gebruikt om gegevenssynchronisatie tussen services te organiseren, dan in het geval van een actorarchitectuur, gegevens tussen threads. We hadden dus zo'n database nodig, waarmee in een omgeving met meerdere threads niet eens minimale problemen worden veroorzaakt. Dit betekent met name dat de daarvan afgeleide objecten op zijn minst thread-safe moeten zijn en idealiter helemaal niet veranderlijk. Zoals u weet, kan de laatste gelijktijdig vanuit verschillende threads worden gebruikt zonder toevlucht te nemen tot enige vorm van vergrendeling, wat een gunstig effect heeft op de prestaties.
De tweede belangrijke factor die de keuze van de database beïnvloedde, was onze cloud-API. Het is geïnspireerd door de git-benadering van synchronisatie. Zoals hij waar we op mikten , wat meer dan geschikt lijkt voor cloudclients. Er werd aangenomen dat ze slechts één keer de volledige staat van de cloud zouden leegpompen, waarna synchronisatie in de overgrote meerderheid van de gevallen zou plaatsvinden door middel van doorlopende wijzigingen. Helaas bevindt deze mogelijkheid zich nog steeds alleen in de theoretische zone en in de praktijk hebben klanten niet geleerd hoe ze met patches moeten werken. Daar is een aantal objectieve redenen voor, die we, om de introductie niet te vertragen, buiten de haakjes laten. Nu veel interessanter zijn de leerzame resultaten van de les over wat er gebeurt als de API "A" zegt en de consument niet "B" zegt.
Dus als je je git voorstelt, dat bij het uitvoeren van een pull-opdracht, in plaats van patches toe te passen op een lokale snapshot, de volledige status vergelijkt met die van de volledige server, dan heb je een redelijk nauwkeurig idee van hoe synchronisatie gebeurt in cloudclients. Het is gemakkelijk te raden dat het voor de implementatie nodig is om twee DOM-bomen in het geheugen toe te wijzen met meta-informatie over alle server- en lokale bestanden. Het blijkt dat als een gebruiker 500 bestanden in de cloud opslaat, om deze te synchroniseren, het nodig is om twee bomen met 1 miljoen knooppunten opnieuw te maken en te vernietigen. Maar elk knooppunt is een aggregaat dat een grafiek van subobjecten bevat. In dit licht werden de profileringsresultaten verwacht. Het bleek dat zelfs zonder rekening te houden met het samenvoegalgoritme, de procedure van het maken en vervolgens vernietigen van een groot aantal kleine objecten een aardige cent kost.De situatie wordt verergerd door het feit dat de basissynchronisatiebewerking is opgenomen in een groot aantal van gebruikersscripts. Als gevolg hiervan leggen we het tweede belangrijke criterium vast bij het kiezen van een database: de mogelijkheid om CRUD-bewerkingen te implementeren zonder dynamische toewijzing van objecten.
Andere vereisten zijn meer traditioneel en hun volledige lijst is als volgt.
- Draad veiligheid.
- Multiprocessing. Gedicteerd door de wens om dezelfde database-instantie te gebruiken om de status niet alleen tussen threads te synchroniseren, maar ook tussen de hoofdtoepassing en iOS-extensies.
- De mogelijkheid om opgeslagen entiteiten weer te geven als niet-veranderlijke objecten
- Gebrek aan dynamische toewijzingen binnen CRUD-operaties.
- Transactieondersteuning voor basiseigenschappen Sleutelwoorden: atomiciteit, consistentie, isolatie en betrouwbaarheid.
- Snelheid op de meest populaire gevallen.
Met deze set van eisen was en is SQLite een goede keuze. Als onderdeel van de studie van alternatieven kwam ik echter een boek tegen . Onder haar leiding is een benchmark geschreven die de werksnelheid vergelijkt met verschillende databases in echte cloudscenario's. Het resultaat overtrof de stoutste verwachtingen. In de meest populaire gevallen - een cursor krijgen op een gesorteerde lijst van alle bestanden en een gesorteerde lijst van alle bestanden voor een bepaalde map - bleek LMDB 10 keer sneller te zijn dan SQLite. De keuze werd duidelijk.
2. LMDB-positionering
LMDB is een zeer kleine bibliotheek (slechts 10 regels), die de laagste fundamentele laag van databases implementeert: opslag.
Het bovenstaande diagram laat zien dat het vergelijken van LMDB met SQLite, dat nog hogere niveaus implementeert, over het algemeen niet correcter is dan SQLite met Core Data. Het zou eerlijker zijn om dezelfde storage-engines te noemen als gelijkwaardige concurrenten - BerkeleyDB, LevelDB, Sophia, RocksDB, enz. Er zijn zelfs ontwikkelingen waarbij LMDB fungeert als een storage-engine-component voor SQLite. Het eerste dergelijke experiment in 2012 auteur LMDB . bleek zo intrigerend dat zijn initiatief werd opgepikt door OSS-enthousiastelingen en zijn voortzetting vond in het aangezicht van . In januari 2020 is de auteur van dit project Den Shearer het op LinuxConfAu.
Het belangrijkste gebruik van LMDB is als motor voor toepassingsdatabases. De bibliotheek heeft haar uitstraling te danken aan de ontwikkelaars , die zeer ontevreden waren over BerkeleyDB als basis van hun project. Wegduwen van de nederige bibliotheek , was Howard Chu in staat om een van de meest populaire alternatieven van onze tijd te creëren. Hij wijdde zijn zeer coole rapport aan dit verhaal, evenals aan de interne structuur van LMDB. . Leonid Joerjev (aka ) van Positive Technologies in zijn toespraak op Highload 2015 . Daarin spreekt hij over LMDB in de context van een vergelijkbare taak om ReOpenLDAP te implementeren, en LevelDB is al onderworpen aan vergelijkende kritiek. Als resultaat van de implementatie kreeg Positive Technologies zelfs een zich actief ontwikkelende fork met zeer smakelijke functies, optimalisaties en .
LMDB wordt ook vaak gebruikt als as-storage. Bijvoorbeeld de browser Mozilla Firefox het voor een aantal behoeften, en vanaf versie 9, Xcode het is SQLite om indexen op te slaan.
De motor sloeg ook aan in de wereld van mobiele ontwikkeling. Er kunnen sporen van gebruik zijn in de iOS-client voor Telegram. LinkedIn ging nog een stap verder en koos LMDB als standaardopslag voor zijn eigen datacaching-framework, Rocket Data, waarover in een artikel uit 2016.
LMDB vecht met succes voor een plekje onder de zon in de niche die BerkeleyDB heeft achtergelaten na de transitie onder controle van Oracle. De bibliotheek is geliefd om zijn snelheid en betrouwbaarheid, zelfs in vergelijking met zijn soortgenoten. Zoals u weet, zijn er geen gratis lunches en ik zou graag de afweging willen benadrukken waarmee u te maken krijgt bij het kiezen tussen LMDB en SQLite. In het bovenstaande diagram is duidelijk te zien hoe de verhoogde snelheid wordt bereikt. Ten eerste betalen we niet voor extra abstractielagen bovenop schijfopslag. In een goede architectuur kun je natuurlijk nog steeds niet zonder, en ze zullen onvermijdelijk in de applicatiecode verschijnen, maar ze zullen veel dunner zijn. Ze hebben geen functies die niet vereist zijn voor een specifieke toepassing, bijvoorbeeld ondersteuning voor query's in de SQL-taal. Ten tweede wordt het mogelijk om de mapping van applicatiebewerkingen naar verzoeken naar schijfopslag optimaal te implementeren. Als SQLite komt uit de gemiddelde behoefte van een gemiddelde applicatie, dan ben jij als applicatieontwikkelaar goed op de hoogte van de belangrijkste belastingsscenario's. Voor een productievere oplossing moet u een hoger prijskaartje betalen voor zowel de ontwikkeling van de initiële oplossing als de daaropvolgende ondersteuning.
3. Drie walvissen LMDB
Nadat je de LMDB vanuit vogelperspectief hebt bekeken, is het tijd om dieper te gaan. De volgende drie secties zullen gewijd zijn aan de analyse van de belangrijkste walvissen waarop de opslagarchitectuur berust:
- Geheugen-toegewezen bestanden als een mechanisme voor het werken met schijf en het synchroniseren van interne gegevensstructuren.
- B+-tree als een organisatie van de opgeslagen datastructuur.
- Copy-on-write als een benadering om ACID-transactionele eigenschappen en multiversiebeheer te bieden.
3.1. Walvis #1. Geheugen toegewezen bestanden
Memory-mapped bestanden zijn zo'n belangrijk architectonisch element dat ze zelfs in de naam van de repository verschijnen. Problemen met caching en synchronisatie van toegang tot opgeslagen informatie zijn volledig overgeleverd aan het besturingssysteem. LMDB bevat zelf geen caches. Dit is een bewuste keuze van de auteur, aangezien het rechtstreeks lezen van gegevens uit toegewezen bestanden u in staat stelt om veel te besparen op de implementatie van de engine. Hieronder is een verre van volledige lijst van enkele van hen.
- Het handhaven van de consistentie van gegevens in de opslag wanneer ermee vanuit verschillende processen wordt gewerkt, wordt de verantwoordelijkheid van het besturingssysteem. In het volgende gedeelte wordt deze monteur in detail en met foto's besproken.
- De afwezigheid van caches ontlast LMDB volledig van de overhead die gepaard gaat met dynamische toewijzingen. Het lezen van gegevens in de praktijk is het instellen van de aanwijzer op het juiste adres in het virtuele geheugen en niets meer. Klinkt als fantasie, maar in de repository-bron zijn alle calloc-oproepen geconcentreerd in de repository-configuratiefunctie.
- De afwezigheid van caches betekent ook de afwezigheid van vergrendelingen die verband houden met synchronisatie om er toegang toe te krijgen. Lezers, waarvan er een willekeurig aantal tegelijkertijd kan bestaan, komen geen enkele mutex tegen op weg naar de data. Hierdoor heeft de leessnelheid een ideale lineaire schaalbaarheid in termen van het aantal CPU's. In LMDB worden alleen wijzigingsbewerkingen gesynchroniseerd. Er kan maar één schrijver tegelijk zijn.
- Een minimum aan caching- en synchronisatielogica bespaart de code van een uiterst complex soort fouten die samenhangen met het werken in een omgeving met meerdere threads. Er waren twee interessante database-onderzoeken op de Usenix OSDI 2014-conferentie: и . Van hen kunt u informatie krijgen over zowel de ongekende betrouwbaarheid van LMDB als de bijna foutloze implementatie van de ACID-eigenschappen van transacties, die deze overtreft in dezelfde SQLite.
- Door het minimalisme van LMDB kan de machinerepresentatie van zijn code volledig in de L1-cache van de processor worden geplaatst met de resulterende snelheidskenmerken.
Helaas zijn in iOS geheugen-toegewezen bestanden niet zo rooskleurig als we zouden willen. Om meer bewust te praten over de nadelen die eraan verbonden zijn, is het noodzakelijk om de algemene principes voor het implementeren van dit mechanisme in besturingssystemen in herinnering te brengen.
Algemene informatie over geheugen toegewezen bestanden
Aan elke uitvoerbare toepassing koppelt het besturingssysteem een entiteit die een proces wordt genoemd. Elk proces krijgt een aaneengesloten bereik van adressen toegewezen, waarin het alles plaatst wat het nodig heeft om te werken. De laagste adressen bevatten secties met code en hardgecodeerde gegevens en bronnen. Vervolgens komt het opwaarts groeiende blok dynamische adresruimte, bij ons bekend als de heap. Het bevat de adressen van entiteiten die verschijnen tijdens de werking van het programma. Bovenaan staat het geheugengebied dat wordt gebruikt door de applicatiestack. Het groeit of krimpt, met andere woorden, ook zijn omvang heeft een dynamisch karakter. Om ervoor te zorgen dat de stapel en de stapel elkaar niet duwen en hinderen, zijn ze gescheiden aan verschillende uiteinden van de adresruimte.Er is een gat tussen de twee dynamische secties aan de boven- en onderkant. De adressen in dit middelste gedeelte worden door het besturingssysteem gebruikt om te associëren met een proces van verschillende entiteiten. Het kan met name een bepaalde continue reeks adressen toewijzen aan een bestand op schijf. Zo'n bestand wordt een memory-mapped bestand genoemd
De adresruimte die aan een proces is toegewezen, is enorm. Theoretisch wordt het aantal adressen alleen beperkt door de grootte van de aanwijzer, die wordt bepaald door de bitdiepte van het systeem. Als er fysiek geheugen 1-in-1 aan zou worden toegewezen, zou het eerste proces het hele RAM-geheugen opslokken en zou er geen sprake zijn van multitasking.
Uit ervaring weten we echter dat moderne besturingssystemen zoveel processen tegelijk kunnen uitvoeren als je wilt. Dit is mogelijk vanwege het feit dat ze veel geheugen toewijzen aan processen die alleen op papier staan, maar in werkelijkheid laden ze alleen dat deel in het fysieke hoofdgeheugen waar hier en nu vraag naar is. Daarom wordt het geheugen dat aan het proces is gekoppeld virtueel genoemd.
Het besturingssysteem organiseert virtueel en fysiek geheugen in pagina's van een bepaalde grootte. Zodra er vraag is naar een bepaalde pagina virtueel geheugen, laadt het besturingssysteem deze in het fysieke geheugen en legt een correspondentie daartussen vast in een speciale tabel. Als er geen vrije slots zijn, wordt een van de eerder geladen pagina's naar schijf gekopieerd en komt de gevraagde in de plaats. Deze procedure, waar we straks op terugkomen, wordt swapping genoemd. Onderstaande figuur illustreert het beschreven proces. Daarop werd pagina A met adres 0 geladen en op de hoofdgeheugenpagina met adres 4 geplaatst. Dit feit werd weerspiegeld in de correspondentietabel in cel nummer 0.
Met memory-mapped bestanden is het verhaal precies hetzelfde. Logischerwijs worden ze zogenaamd continu en volledig in de virtuele adresruimte geplaatst. Ze komen echter pagina voor pagina in het fysieke geheugen en alleen op verzoek. Wijziging van dergelijke pagina's wordt gesynchroniseerd met het bestand op schijf. U kunt dus bestands-I / O uitvoeren door simpelweg met bytes in het geheugen te werken - alle wijzigingen worden automatisch door de kernel van het besturingssysteem overgebracht naar het originele bestand.
De onderstaande afbeelding laat zien hoe LMDB zijn status synchroniseert bij het werken met de database vanuit verschillende processen. Door het virtuele geheugen van verschillende processen op hetzelfde bestand af te beelden, verplichten we het besturingssysteem de facto om bepaalde blokken van hun adresruimten transitief met elkaar te synchroniseren, en dat is waar LMDB naar kijkt.
Een belangrijke nuance is dat LMDB het gegevensbestand standaard wijzigt via het schrijfsysteemoproepmechanisme en dat het bestand zelf wordt weergegeven in alleen-lezenmodus. Deze aanpak heeft twee belangrijke implicaties.
Het eerste gevolg is hetzelfde voor alle besturingssystemen. De essentie is om bescherming toe te voegen tegen onbedoelde schade aan de database door onjuiste code. Zoals u weet, zijn de uitvoerbare instructies van een proces vrij om overal in de adresruimte toegang te krijgen tot gegevens. Tegelijkertijd, zoals we ons net herinnerden, betekent het weergeven van een bestand in lees-schrijfmodus dat elke instructie het ook kan wijzigen. Als ze dit per ongeluk doet, bijvoorbeeld door te proberen een array-element daadwerkelijk te overschrijven bij een niet-bestaande index, dan kan ze op deze manier per ongeluk het bestand wijzigen dat aan dit adres is toegewezen, wat zal leiden tot databasecorruptie. Als het bestand wordt weergegeven in alleen-lezen modus, zal een poging om de bijbehorende adresruimte te wijzigen leiden tot een crash van het programma met het signaal SIGSEGVen het bestand blijft intact.
Het tweede gevolg is al specifiek voor iOS. Noch de auteur, noch enige andere bron vermeldt het expliciet, maar zonder dit zou LMDB ongeschikt zijn om op dit mobiele besturingssysteem te draaien. Het volgende deel is gewijd aan de overweging ervan.
Bijzonderheden van in het geheugen toegewezen bestanden in iOS
In 2018 was er een prachtige reportage op WWDC . Het vertelt dat in iOS alle pagina's in het fysieke geheugen tot een van de drie typen behoren: vies, gecomprimeerd en schoon.
Schoon geheugen is een verzameling pagina's die veilig uit het fysieke geheugen kunnen worden verwisseld. De gegevens die ze bevatten, kunnen indien nodig opnieuw worden geladen vanuit hun oorspronkelijke bronnen. Alleen-lezen memory-mapped bestanden vallen in deze categorie. iOS is niet bang om de pagina's die aan een bestand zijn toegewezen op elk moment uit het geheugen te halen, aangezien ze gegarandeerd worden gesynchroniseerd met het bestand op schijf.
Alle gewijzigde pagina's komen in het vuile geheugen terecht, ongeacht waar ze zich oorspronkelijk bevinden. Met name geheugen-toegewezen bestanden die zijn gewijzigd door te schrijven naar het virtuele geheugen dat eraan is gekoppeld, zullen ook op deze manier worden geclassificeerd. LMDB openen met vlag MDB_WRITEMAP, nadat u er wijzigingen in heeft aangebracht, kunt u het zelf zien.
Zodra een applicatie te veel fysiek geheugen in beslag neemt, comprimeert iOS de vuile pagina's. De verzameling geheugen die wordt ingenomen door vuile en gecomprimeerde pagina's is de zogenaamde geheugenvoetafdruk van de toepassing. Wanneer het een bepaalde drempelwaarde bereikt, komt de OOM killer-systeemdaemon na het proces en beëindigt het met geweld. Dit is de eigenaardigheid van iOS in vergelijking met desktopbesturingssystemen. Het verkleinen van de geheugenvoetafdruk door pagina's van fysiek geheugen naar schijf te wisselen, is daarentegen niet aanwezig in iOS.Naar de redenen kan men alleen maar gissen. Misschien is de procedure voor het intensief verplaatsen van pagina's naar schijf en terug te energieverslindend voor mobiele apparaten, of bespaart iOS de bron van het herschrijven van cellen op SSD-schijven, of misschien waren de ontwerpers niet tevreden met de algehele prestaties van het systeem, waar alles is voortdurend verwisseld. Hoe het ook zij, het feit blijft.
Het goede nieuws, al eerder vermeld, is dat LMDB niet standaard het mmap-mechanisme gebruikt om bestanden bij te werken. Hieruit volgt dat de weergegeven gegevens door iOS worden geclassificeerd als schoon geheugen en niet bijdragen aan de geheugenvoetafdruk. Dit kan worden geverifieerd met behulp van de Xcode-tool genaamd VM Tracker. De onderstaande schermafbeelding toont de status van het virtuele geheugen van de iOS Cloud-applicatie tijdens het gebruik. In het begin werden er 2 LMDB-instanties in geïnitialiseerd. De eerste mocht zijn bestand toewijzen aan 1GiB virtueel geheugen, de tweede - 512MiB. Ondanks het feit dat beide opslagplaatsen een bepaalde hoeveelheid intern geheugen innemen, draagt geen van beide bij aan de vuile grootte.
Nu is het tijd voor het slechte nieuws. Dankzij het wisselmechanisme in 64-bits desktopbesturingssystemen kan elk proces evenveel virtuele adresruimte innemen als de vrije ruimte op de harde schijf toelaat voor de mogelijke wissel. Het vervangen van swap door compressie in iOS verlaagt het theoretische maximum drastisch. Nu moeten alle levende processen in het hoofdgeheugen (lees RAM) passen, en alle processen die niet passen, worden gedwongen beëindigd. Het wordt vermeld zoals in het bovenstaande en . Als gevolg hiervan beperkt iOS de hoeveelheid geheugen die beschikbaar is voor toewijzing via mmap ernstig. Hier u kunt de empirische limieten bekijken van de hoeveelheid geheugen die op verschillende apparaten kan worden toegewezen met behulp van deze systeemaanroep. Op de modernste smartphonemodellen is iOS met 2 gigabyte genereus geworden en op topversies van de iPad - met 4. In de praktijk moet je je natuurlijk concentreren op de jongste ondersteunde apparaatmodellen, waar alles erg triest is. Erger nog, als je naar de geheugenstatus van de applicatie in VM Tracker kijkt, zul je zien dat LMDB verre van de enige is die aanspraak maakt op memory-mapped geheugen. Goede brokken worden weggevreten door systeemtoewijzers, bronbestanden, afbeeldingsframeworks en andere kleinere roofdieren.
Als resultaat van experimenten in de cloud kwamen we tot de volgende compromiswaarden van geheugen toegewezen door LMDB: 384 megabytes voor 32-bits apparaten en 768 voor 64-bits apparaten. Nadat dit volume is opgebruikt, beginnen alle wijzigingsbewerkingen te worden voltooid met de code MDB_MAP_FULL. We nemen dergelijke fouten waar in onze monitoring, maar ze zijn klein genoeg om in dit stadium te worden verwaarloosd.
Een niet voor de hand liggende reden voor overmatig geheugengebruik door opslag kunnen langdurige transacties zijn. Om te begrijpen hoe deze twee verschijnselen met elkaar verband houden, zal het ons helpen om de resterende twee LMDB-walvissen te beschouwen.
3.2. Walvis #2. B+-boom
Om tabellen bovenop een sleutel/waarde-archief te emuleren, moeten de volgende bewerkingen aanwezig zijn in de API:
- Een nieuw element invoegen.
- Zoek naar een element met een bepaalde sleutel.
- Een onderdeel verwijderen.
- Herhaal sleutelintervallen in hun sorteervolgorde.
De eenvoudigste gegevensstructuur die alle vier de bewerkingen gemakkelijk kan implementeren, is een binaire zoekboom. Elk van zijn knooppunten is een sleutel die de volledige subset van onderliggende sleutels verdeelt in twee substructuren. Aan de linkerkant zijn degenen die kleiner zijn dan de ouder, en aan de rechterkant - degenen die groter zijn. Het verkrijgen van een geordende set sleutels wordt bereikt door een van de klassieke boomtraversals
Binaire bomen hebben twee fundamentele nadelen die voorkomen dat ze effectief zijn als schijfgegevensstructuur. Ten eerste is de mate van hun evenwicht onvoorspelbaar. Er is een aanzienlijk risico op het verkrijgen van bomen waarin de hoogte van verschillende takken sterk kan variëren, wat de algoritmische complexiteit van het zoeken aanzienlijk verslechtert in vergelijking met wat wordt verwacht. Ten tweede, de overvloed aan kruisverbindingen tussen knooppunten berooft binaire bomen van lokaliteit in het geheugen.Nauwe knooppunten (in termen van koppelingen ertussen) kunnen zich op totaal verschillende pagina's in het virtuele geheugen bevinden. Bijgevolg kan zelfs een eenvoudige doorgang van verschillende aangrenzende knooppunten in een boom een vergelijkbaar aantal pagina's vereisen. Dit is zelfs een probleem als we het hebben over de efficiëntie van binaire bomen als een in-memory datastructuur, aangezien het constant draaien van pagina's in de processorcache niet goedkoop is. Als het gaat om het regelmatig ophalen van knooppuntgerelateerde pagina's van schijf, wordt het echt slecht. .
B-bomen, die een evolutie zijn van binaire bomen, lossen de problemen op die in de vorige paragraaf zijn geïdentificeerd. Ten eerste zijn ze zelfbalancerend. Ten tweede splitst elk van hun knooppunten de set kindsleutels niet in 2, maar in M geordende subsets, en het aantal M kan behoorlijk groot zijn, in de orde van enkele honderden of zelfs duizenden.
Daarbij:
- Elk knooppunt heeft een groot aantal reeds bestelde sleutels en de bomen zijn erg laag.
- De boom verwerft de eigenschap van lokaliteit in het geheugen, aangezien sleutels die qua waarde dicht bij elkaar liggen, van nature naast elkaar liggen op een of aangrenzende knooppunten.
- Vermindert het aantal transitknooppunten bij het afdalen van de boom tijdens een zoekactie.
- Vermindert het aantal doelknooppunten dat wordt gelezen voor bereikquery's, aangezien elk van hen al een groot aantal geordende sleutels bevat.
LMDB gebruikt een variant van de B-tree, de B+ tree genaamd, om gegevens op te slaan. Het bovenstaande diagram toont de drie soorten knooppunten die het bevat:
- Bovenaan zit de wortel. Het materialiseert niets meer dan het concept van een database binnen een repository. Binnen een enkele LMDB-instantie kunt u meerdere databases maken die de toegewezen virtuele adresruimte delen. Elk van hen vertrekt vanuit zijn eigen wortel.
- Op het laagste niveau bevinden zich de bladeren (blad). Zij en alleen zij bevatten de sleutel-waardeparen die in de database zijn opgeslagen. Dit is trouwens de eigenaardigheid van B+-bomen. Als een normale B-boom de waarde-delen opslaat op de knooppunten van alle niveaus, dan is de B+-variatie alleen op de laagste. Nu we dit feit hebben opgelost, zullen we in wat volgt het subtype van de boom die in LMDB wordt gebruikt eenvoudigweg een B-boom noemen.
- Tussen de wortel en de bladeren bevinden zich 0 of meer technische niveaus met navigatie(tak)knooppunten. Hun taak is om de gesorteerde set sleutels tussen de blaadjes te verdelen.
Fysiek zijn knooppunten geheugenblokken van een vooraf bepaalde lengte. Hun grootte is een veelvoud van de grootte van de geheugenpagina's in het besturingssysteem, waar we het hierboven over hadden. De knooppuntstructuur is hieronder weergegeven. De header bevat meta-informatie, waarvan bijvoorbeeld de checksum de meest voor de hand liggende is. Vervolgens komt informatie over offsets, waarlangs cellen met gegevens zich bevinden. De rol van gegevens kan ofwel een sleutel zijn, als we het hebben over navigatieknooppunten, ofwel hele sleutel-waardeparen in het geval van bladeren.U kunt meer lezen over de structuur van pagina's in het werk .
Nadat we de interne inhoud van de paginaknooppunten hebben behandeld, zullen we de LMDB B-boom verder op een vereenvoudigde manier weergeven in de volgende vorm.
Pagina's met knooppunten worden opeenvolgend op schijf gerangschikt. Pagina's met een hoger nummer bevinden zich aan het einde van het bestand. De zogenaamde metapagina (metapagina) bevat informatie over offsets, waarmee de wortels van alle bomen kunnen worden gevonden. Wanneer een bestand wordt geopend, scant LMDB het bestand pagina voor pagina van het einde naar het begin op zoek naar een geldige metapagina en vindt via deze pagina bestaande databases.
Nu we een idee hebben van de logische en fysieke structuur van de gegevensorganisatie, kunnen we verder gaan met de derde walvis van LMDB. Het is met zijn hulp dat alle opslagmodificaties transactioneel en geïsoleerd van elkaar plaatsvinden, waardoor de database als geheel ook de multiversie-eigenschap krijgt.
3.3. Walvis #3. kopiëren-op-schrijven
Sommige B-tree-bewerkingen omvatten het maken van een hele reeks wijzigingen aan de knooppunten. Een voorbeeld is het toevoegen van een nieuwe sleutel aan een node die al zijn maximale capaciteit heeft bereikt. In dit geval is het ten eerste nodig om het knooppunt in tweeën te splitsen en ten tweede om een link toe te voegen naar het nieuwe afgesplitste onderliggende knooppunt in zijn ouder. Deze procedure is potentieel zeer gevaarlijk. Als om de een of andere reden (crash, stroomuitval, enz.) slechts een deel van de wijzigingen in de reeks plaatsvindt, dan blijft de boom in een inconsistente toestand.
Een traditionele oplossing om een database fouttolerant te maken, is door naast de B-tree een extra datastructuur op schijf toe te voegen, het transactielogboek, ook wel het write-ahead log (WAL) genoemd. Het is een bestand, aan het einde waarvan, strikt vóór de wijziging van de B-tree zelf, de beoogde bewerking is geschreven. Dus als gegevensbeschadiging wordt gedetecteerd tijdens zelfdiagnose, raadpleegt de database het logboek om zichzelf op te schonen.
LMDB heeft een andere methode gekozen als fouttolerantiemechanisme, namelijk copy-on-write. De essentie is dat in plaats van de gegevens op een bestaande pagina bij te werken, deze eerst volledig wordt gekopieerd en alle wijzigingen al in de kopie worden aangebracht.
Om ervoor te zorgen dat de bijgewerkte gegevens beschikbaar zijn, is het verder noodzakelijk om de link naar het knooppunt dat up-to-date is geworden in het bovenliggende knooppunt in relatie daarmee te wijzigen. Aangezien het ook hiervoor moet worden aangepast, is het ook vooraf gekopieerd. Het proces gaat recursief door tot aan de root. De gegevens op de metapagina worden als laatste gewijzigd.
Als het proces plotseling crasht tijdens de updateprocedure, wordt er geen nieuwe metapagina gemaakt of wordt deze pas aan het einde naar schijf geschreven en is de checksum onjuist. In elk van deze twee gevallen zijn de nieuwe pagina's onbereikbaar en worden de oude niet beïnvloed. Dit elimineert de noodzaak voor LMDB om een logboek vooruit te schrijven om de gegevensconsistentie te behouden. De facto neemt de hierboven beschreven structuur van gegevensopslag op de schijf tegelijkertijd zijn functie over. De afwezigheid van een expliciet transactielogboek is een van de kenmerken van LMDB, dat zorgt voor een hoge leessnelheid van gegevens
De resulterende constructie, genaamd B-tree met alleen toevoegsels, zorgt natuurlijk voor transactie-isolatie en multiversiebeheer. In LMDB is aan elke openstaande transactie een up-to-date tree root gekoppeld. Zolang de transactie niet is voltooid, worden de pagina's van de bijbehorende boom nooit gewijzigd of hergebruikt voor nieuwe versies van gegevens. U kunt dus zo lang als u wilt precies werken met de gegevensset die relevant was op het moment dat de transactie is voltooid. moment dat de transactie werd geopend, zelfs als de opslag op dit moment actief wordt bijgewerkt. Dit is de essentie van multiversiebeheer, waardoor LMDB een ideale gegevensbron is voor onze geliefden UICollectionView. Nadat u een transactie hebt geopend, hoeft u de geheugenvoetafdruk van de toepassing niet te vergroten, door de huidige gegevens haastig naar een structuur in het geheugen te pompen, bang om niets achter te laten. Deze functie onderscheidt LMDB van dezelfde SQLite, die niet kan bogen op zo'n totale isolatie. Na het openen van twee transacties in de laatste en het verwijderen van een bepaald record binnen een ervan, kan hetzelfde record niet meer worden verkregen binnen de tweede resterende.
De keerzijde van de medaille is het potentieel aanzienlijk hogere verbruik van virtueel geheugen. De dia laat zien hoe de databasestructuur eruit zal zien als deze tegelijkertijd wordt gewijzigd met 3 open leestransacties waarbij naar verschillende versies van de database wordt gekeken. Aangezien LMDB geen nodes kan hergebruiken die bereikbaar zijn vanaf de root die is gekoppeld aan de daadwerkelijke transacties, heeft de opslag geen andere keuze dan nog een vierde root in het geheugen toe te wijzen en de gewijzigde pagina's eronder opnieuw te klonen.
Hier is het niet overbodig om het gedeelte over in het geheugen toegewezen bestanden op te roepen. Het lijkt erop dat het extra verbruik van virtueel geheugen ons niet veel zou moeten storen, aangezien het niet bijdraagt aan de geheugenvoetafdruk van de applicatie. Tegelijkertijd werd echter opgemerkt dat iOS erg gierig is in het toewijzen ervan, en we kunnen geen LMDB-regio van 1 terabyte op een server of desktop vanaf de schouder van de meester bieden en helemaal niet aan deze functie denken. Probeer waar mogelijk de looptijd van transacties zo kort mogelijk te houden.
4. Een dataschema ontwerpen bovenop de key-value API
Laten we beginnen met het ontleden van de API door te kijken naar de basisabstracties van LMDB: omgeving en databases, sleutels en waarden, transacties en cursors.
Een opmerking over codevermeldingen
Alle functies in de openbare API van LMDB retourneren het resultaat van hun werk in de vorm van een foutcode, maar in alle volgende lijsten wordt de controle ervan weggelaten omwille van de beknoptheid.In de praktijk gebruikten we onze eigen code om te communiceren met de repository. C++-wrappers , waarin fouten zich voordoen als C++-uitzonderingen.
Als de snelste manier om LMDB aan een iOS- of macOS-project te koppelen, bied ik mijn CocoaPod aan .
4.1. Basale abstracties
Omgeving
Structuur MDB_env is de repository van de interne status van de LMDB. Familie van vooraf ingestelde functies mdb_env stelt u in staat enkele van zijn eigenschappen te configureren. In het eenvoudigste geval ziet de initialisatie van de motor er zo uit.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);In de Mail.ru Cloud-applicatie hebben we de standaardwaarden voor slechts twee parameters gewijzigd.
De eerste is de grootte van de virtuele adresruimte waaraan het opslagbestand is toegewezen. Helaas kan de specifieke waarde zelfs op hetzelfde apparaat aanzienlijk variëren van run tot run. Om rekening te houden met deze functie van iOS, selecteren we dynamisch de maximale hoeveelheid opslagruimte. Vanaf een bepaalde waarde wordt het achtereenvolgens gehalveerd tot de functie mdb_env_open geeft geen ander resultaat dan ENOMEM. In theorie is er een tegenovergestelde manier: wijs eerst een minimum aan geheugen toe aan de engine en vervolgens, wanneer er fouten worden ontvangen MDB_MAP_FULL, verhoog het. Het is echter veel stekeliger. De reden is dat de procedure voor het opnieuw toewijzen van geheugen met behulp van de functie mdb_env_set_map_size maakt alle entiteiten (cursors, transacties, sleutels en waarden) die eerder van de engine zijn ontvangen, ongeldig. Rekening houden met een dergelijke gang van zaken in de code zal tot aanzienlijke complicaties leiden. Als virtueel geheugen je desondanks erg dierbaar is, dan kan dit een reden zijn om naar de splitsing te kijken die ver vooruit is gegaan. , waar onder de verklaarde functies "automatische on-the-fly aanpassing van de databasegrootte" is.
De tweede parameter, waarvan de standaardwaarde niet bij ons past, regelt de mechanismen om de draadveiligheid te waarborgen. Helaas zijn er, in ieder geval in iOS 10, problemen met de ondersteuning van lokale thread-opslag. Om deze reden wordt in het bovenstaande voorbeeld de repository geopend met de vlag MDB_NOTLS. Bovendien was het ook vereist C++-wrapper om variabelen met en in dit attribuut te knippen.
Databank
De database is een apart exemplaar van de B-tree waar we het hierboven over hadden. De opening vindt plaats binnen een transactie, wat in eerste instantie misschien een beetje vreemd lijkt.
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);Een transactie in LMDB is inderdaad een opslagentiteit, geen specifieke database. Met dit concept kunt u atomaire bewerkingen uitvoeren op entiteiten die zich in verschillende databases bevinden. In theorie opent dit de mogelijkheid om tabellen te modelleren in de vorm van verschillende databases, maar ooit ging ik de andere kant op, die hieronder in detail wordt beschreven.
Sleutels en waarden
Structuur MDB_val modelleert het concept van zowel een sleutel als een waarde. De repository heeft geen idee van hun semantiek. Voor haar is iets dat anders is, slechts een reeks bytes van een bepaalde grootte. De maximale sleutelgrootte is 512 bytes.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;De winkel gebruikt een comparator om de sleutels in oplopende volgorde te sorteren. Als u het niet door uw eigen vervangt, wordt de standaardversie gebruikt, die ze byte voor byte sorteert in lexicografische volgorde.
Transactie
Het transactieapparaat wordt in detail beschreven in , dus hier zal ik hun belangrijkste eigenschappen in het kort herhalen:
- Ondersteuning voor alle basiseigenschappen Sleutelwoorden: atomiciteit, consistentie, isolatie en betrouwbaarheid. Ik kan het niet helpen, maar merk op dat er in termen van duurzaamheid op macOS en iOS een bug is opgelost in MDBX. U kunt meer lezen in hun .
- De benadering van multithreading wordt beschreven door het schema "enkele schrijver / meerdere lezers". Schrijvers blokkeren elkaar, maar ze blokkeren geen lezers. Lezers blokkeren geen schrijvers of elkaar.
- Ondersteuning voor geneste transacties.
- Ondersteuning voor meerdere versies.
Multiversioning in LMDB is zo goed dat ik het in actie wil demonstreren. De onderstaande code laat zien dat elke transactie werkt met exact de versie van de database die relevant was op het moment van openen, volledig geïsoleerd van alle latere wijzigingen. Het initialiseren van de repository en het toevoegen van een testrecord is niet interessant, dus deze rituelen blijven onder de spoiler.
Een testinvoer toevoegen
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);Optioneel raad ik aan dezelfde truc met SQLite te proberen en te kijken wat er gebeurt.
Multiversioning brengt zeer mooie voordelen met zich mee in het leven van een iOS-ontwikkelaar. Met behulp van deze eigenschap kunt u eenvoudig en natuurlijk de updatesnelheid van de gegevensbron voor schermformulieren aanpassen op basis van overwegingen van de gebruikerservaring. Laten we bijvoorbeeld zo'n functie van de Mail.ru Cloud-applicatie nemen als het automatisch laden van inhoud uit de systeemmediagalerij. Bij een goede verbinding kan de client meerdere foto's per seconde aan de server toevoegen. Als u na elke download een update uitvoert UICollectionView met media-inhoud in de cloud van de gebruiker, kunt u tijdens dit proces ongeveer 60 fps en soepel scrollen vergeten. Om frequente schermupdates te voorkomen, moet u op de een of andere manier de snelheid van gegevensverandering in de basis beperken UICollectionViewDataSource.
Als de database multiversiebeheer niet ondersteunt en u alleen met de huidige huidige status kunt werken, moet u deze, om een tijdstabiele gegevensmomentopname te maken, kopiëren naar een gegevensstructuur in het geheugen of naar een tijdelijke tabel. Elk van deze benaderingen is erg duur. In het geval van opslag in het geheugen krijgen we zowel de geheugenkosten die worden veroorzaakt door het opslaan van geconstrueerde objecten als de tijdskosten die gepaard gaan met redundante ORM-transformaties. Wat betreft de tijdelijke tafel, dit is een nog duurder genoegen, wat alleen zinvol is in niet-triviale gevallen.
Multiversioning LMDB lost het probleem van het onderhouden van een stabiele gegevensbron op een zeer elegante manier op. Het volstaat om een transactie te openen en voila - totdat we deze hebben voltooid, is de dataset gegarandeerd vast. De logica van de updatesnelheid is nu volledig in handen van de presentatielaag, zonder overhead van aanzienlijke bronnen.
cursors
Cursors bieden een mechanisme voor geordende iteratie over sleutel-waardeparen door een B-boom te doorlopen. Zonder hen zou het onmogelijk zijn om de tabellen in de database effectief te modelleren, waar we nu naar kijken.
4.2. Tabelmodellering
Met de eigenschap sleutelordening kunt u een abstractie op het hoogste niveau construeren, zoals een tabel bovenop basisabstracties. Laten we dit proces eens bekijken aan de hand van het voorbeeld van de hoofdtabel van de cloudclient, waarin informatie over alle bestanden en mappen van de gebruiker in de cache is opgeslagen.
Tabel Schema
Een van de veelvoorkomende scenario's waarvoor de structuur van een tabel met een mappenboom moet worden aangescherpt, is het selecteren van alle elementen die zich binnen een bepaalde map bevinden. Een goed gegevensorganisatiemodel voor dit soort efficiënte query's is . Om het bovenop de opslag van sleutelwaarden te implementeren, is het noodzakelijk om de sleutels van bestanden en mappen zo te sorteren dat ze worden gegroepeerd op basis van het behoren tot de bovenliggende map. Bovendien, om de inhoud van de map weer te geven in de vorm die een Windows-gebruiker kent (eerst mappen, dan bestanden, beide worden alfabetisch gesorteerd), is het noodzakelijk om de overeenkomstige extra velden in de sleutel op te nemen.
De onderstaande afbeelding laat zien hoe, op basis van de taak, de weergave van sleutels als een reeks bytes eruit kan zien. Eerst worden de bytes met de parent directory identifier (rood) geplaatst, dan met het type (groen) en al in de staart met de naam (blauw).Gesorteerd door de standaard LMDB comparator in lexicografische volgorde, zijn ze geordend in de gewenste manier. Opeenvolgend doorlopen van toetsen met hetzelfde rode voorvoegsel geeft ons de bijbehorende waarden in de volgorde waarin ze moeten worden weergegeven in de gebruikersinterface (rechts), zonder dat er extra nabewerking nodig is.
Serialisatie van sleutels en waarden
Er zijn veel methoden voor het serialiseren van objecten over de hele wereld. Omdat we geen andere vereiste hadden dan snelheid, kozen we voor onszelf de snelst mogelijke - een geheugendump die wordt ingenomen door een instantie van de taalstructuur C. De sleutel van een directory-element kan dus worden gemodelleerd door de volgende structuur NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Opslaan NodeKey in opslagbehoefte in object MDB_val plaats de aanwijzer op de gegevens op het adres van het begin van de structuur en bereken hun grootte met de functie sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}In het eerste hoofdstuk over databaseselectiecriteria noemde ik het minimaliseren van dynamische allocaties als onderdeel van CRUD-operaties als een belangrijke selectiefactor. Functiecode serialize laat zien hoe ze in het geval van LMDB volledig kunnen worden vermeden wanneer nieuwe records in de database worden ingevoegd. De inkomende reeks bytes van de server wordt eerst omgezet in stapelstructuren en vervolgens triviaal in de opslag gedumpt. Aangezien er ook geen dynamische toewijzingen zijn binnen LMDB, kun je een fantastische situatie krijgen volgens de normen van iOS - gebruik alleen stapelgeheugen om met gegevens te werken, helemaal van het netwerk tot de schijf!
Sleutels bestellen met een binaire comparator
De sleutelvolgorderelatie wordt gegeven door een speciale functie die een comparator wordt genoemd. Omdat de engine niets weet over de semantiek van de bytes die ze bevatten, heeft de standaardcomparator geen andere keuze dan de sleutels in lexicografische volgorde te rangschikken en hun toevlucht te nemen tot byte-voor-byte vergelijking. Het gebruiken om structuren te rangschikken is vergelijkbaar met scheren met een snijbijl. In eenvoudige gevallen vind ik deze methode echter acceptabel. Het alternatief wordt hieronder beschreven, maar hier zal ik een paar harken opmerken die onderweg zijn verspreid.
Het eerste dat u in gedachten moet houden, is de geheugenrepresentatie van primitieve gegevenstypen. Dus op alle Apple-apparaten worden integer-variabelen opgeslagen in het formaat . Dit betekent dat de minst significante byte zich aan de linkerkant bevindt en dat u gehele getallen niet kunt sorteren met behulp van hun byte-voor-byte vergelijking. Als u dit bijvoorbeeld probeert te doen met een reeks getallen van 0 tot 511, krijgt u het volgende resultaat.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Om dit probleem op te lossen, moeten de gehele getallen in de sleutel worden opgeslagen in een formaat dat geschikt is voor de bytevergelijker. Functies uit het gezin zullen helpen om de noodzakelijke transformatie uit te voeren. hton* (met name htons voor dubbelbyte-nummers uit het voorbeeld).
Het formaat voor het weergeven van tekenreeksen bij het programmeren is, zoals u weet, een geheel . Als de semantiek van strings, evenals de codering die wordt gebruikt om ze in het geheugen weer te geven, suggereert dat er meer dan één byte per teken kan zijn, dan is het beter om onmiddellijk af te zien van het idee om een standaardvergelijker te gebruiken.
Het tweede ding om in gedachten te houden is struct-veldcompiler. Hierdoor kunnen bytes met afvalwaarden in het geheugen tussen velden worden gevormd, wat natuurlijk de bytesortering verbreekt. Om rommel te elimineren, moet u de velden in een strikt gedefinieerde volgorde declareren, rekening houdend met de uitlijningsregels, of het attribuut gebruiken in de structuurdeclaratie packed.
Sleutel bestellen door een externe vergelijker
De sleutelvergelijkingslogica kan te complex blijken te zijn voor een binaire comparator. Een van de vele redenen is de aanwezigheid van technische velden binnen de structuren. Ik zal hun optreden illustreren aan de hand van het voorbeeld van een sleutel die ons al bekend is voor een directory-element.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Ondanks al zijn eenvoud verbruikt het in de overgrote meerderheid van de gevallen te veel geheugen. De titelbuffer is 256 bytes, hoewel bestands- en mapnamen gemiddeld zelden langer zijn dan 20-30 tekens.
Een van de standaardtechnieken om de grootte van een plaat te optimaliseren, is deze bij te snijden tot de werkelijke grootte. De essentie is dat de inhoud van alle velden met variabele lengte wordt opgeslagen in een buffer aan het einde van de structuur en dat hun lengte wordt opgeslagen in afzonderlijke variabelen. NodeKey wordt op de volgende manier getransformeerd.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Verder, tijdens serialisatie, niet opgegeven als de gegevensgrootte sizeof de gehele structuur, en de grootte van alle velden is een vaste lengte plus de grootte van het feitelijk gebruikte deel van de buffer.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Als resultaat van de refactoring hebben we een aanzienlijke besparing behaald in de ruimte die wordt ingenomen door de toetsen. Wel vanwege het technische veld nameLength, is de standaard binaire vergelijker niet langer geschikt voor sleutelvergelijking. Als we het niet vervangen door het onze, zal de lengte van de naam een hogere prioriteit hebben bij het sorteren dan de naam zelf.
Met LMDB kan elke database zijn eigen sleutelvergelijkingsfunctie hebben. Dit wordt gedaan met behulp van de functie mdb_set_compare strikt voor opening. Om voor de hand liggende redenen kan een database tijdens zijn levensduur niet worden gewijzigd. Aan de ingang ontvangt de vergelijker twee sleutels in binair formaat en aan de uitgang geeft hij het resultaat van de vergelijking terug: kleiner dan (-1), groter dan (1) of gelijk aan (0). Pseudocode voor NodeKey ziet eruit als.
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 // ...
}Zolang alle sleutels in de database van hetzelfde type zijn, is het legaal om hun byterepresentatie onvoorwaardelijk te casten naar het type van de applicatiestructuur van de sleutel. Er is hier één nuance, maar deze zal iets lager worden besproken in de subsectie "Records lezen".
Waarde serialisatie
Met de sleutels van opgeslagen records werkt LMDB enorm intensief. Ze worden met elkaar vergeleken binnen het kader van elke toepassingsoperatie, en de prestaties van de volledige oplossing zijn afhankelijk van de snelheid van de vergelijker. In een ideale wereld zou de standaard binaire comparator voldoende moeten zijn om sleutels te vergelijken, maar als u echt uw eigen comparator zou moeten gebruiken, dan zou de procedure voor het deserialiseren van sleutels daarin zo snel mogelijk moeten zijn.
De database is niet bijzonder geïnteresseerd in het Value-gedeelte van het record (value). De conversie van een byte-representatie naar een object vindt alleen plaats wanneer de toepassingscode dit al vereist, bijvoorbeeld om het op het scherm weer te geven. Aangezien dit relatief zelden gebeurt, zijn de vereisten voor de snelheid van deze procedure niet zo kritisch en kunnen we ons bij de implementatie veel meer concentreren op gemak.Om bijvoorbeeld metadata te serialiseren over bestanden die nog niet zijn gedownload, gebruiken we NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Er zijn echter momenten waarop prestaties er toe doen. Bij het opslaan van meta-informatie over de bestandsstructuur van de gebruikerscloud gebruiken we bijvoorbeeld dezelfde objectgeheugendump. Het hoogtepunt van de taak van het genereren van hun geserialiseerde representatie is het feit dat de elementen van een directory worden gemodelleerd door een klassenhiërarchie.
Voor de implementatie in de C-taal worden de specifieke velden van de erfgenamen in afzonderlijke structuren ondergebracht en hun verbinding met de basis wordt gespecificeerd via een veld van het vakbondstype. De daadwerkelijke inhoud van de unie wordt gespecificeerd via het type technisch attribuut.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Records toevoegen en bijwerken
De geserialiseerde sleutel en waarde kunnen aan de winkel worden toegevoegd. Hiervoor wordt de functie gebruikt mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);In de configuratiefase kan de repository worden toegestaan of verboden om meerdere records met dezelfde sleutel op te slaan. Als het dupliceren van sleutels verboden is, kunt u bij het invoegen van een record bepalen of het bijwerken van een reeds bestaand record is toegestaan of niet. Als rafelen alleen kan optreden als gevolg van een fout in de code, dan kunt u zich hiertegen verzekeren door de vlag op te geven NOOVERWRITE.
Records lezen
De functie voor het lezen van records in LMDB is mdb_get. Als het sleutel-waardepaar wordt weergegeven door eerder gedumpte structuren, ziet deze procedure er als volgt uit.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}De gepresenteerde lijst laat zien hoe serialisatie door middel van een dump van structuren u in staat stelt dynamische toewijzingen kwijt te raken, niet alleen bij het schrijven, maar ook bij het lezen van gegevens. Afgeleid van functie mdb_get de aanwijzer kijkt precies naar het virtuele geheugenadres waar de database de byterepresentatie van het object opslaat. In feite krijgen we een soort ORM, bijna gratis, waardoor gegevens op zeer hoge snelheid kunnen worden gelezen. Met alle schoonheid van de aanpak, is het noodzakelijk om verschillende kenmerken te onthouden die ermee verbonden zijn.
- Voor een alleen-lezen transactie blijft een verwijzing naar een waardestructuur gegarandeerd alleen geldig totdat de transactie is gesloten. Zoals eerder opgemerkt, blijven de pagina's van de B-tree waarop het object zich bevindt, dankzij het copy-on-write-principe, ongewijzigd zolang er minstens één transactie naar verwijst. Tegelijkertijd kunnen de pagina's, zodra de laatste bijbehorende transactie is voltooid, opnieuw worden gebruikt voor nieuwe gegevens. Als het nodig is dat objecten de transactie overleven waarmee ze zijn gemaakt, moeten ze nog steeds worden gekopieerd.
- Voor een lees-schrijftransactie is de pointer naar de resulterende structuurwaarde alleen geldig tot de eerste wijzigingsprocedure (gegevens schrijven of verwijderen).
- Ook al is de structuur
NodeValueniet volwaardig, maar ingekort (zie subsectie "Sleutels bestellen door een externe comparator"), via de aanwijzer kunt u gemakkelijk toegang krijgen tot de velden. Het belangrijkste is om het niet te derefereren! - In geen geval kunt u de structuur wijzigen via de ontvangen aanwijzer. Alle wijzigingen moeten alleen via de methode worden aangebracht
mdb_put. Echter, met alle wens om dit te doen, zal het niet werken, aangezien het geheugengebied waar deze structuur zich bevindt, in kaart wordt gebracht in de alleen-lezen modus. - Wijs een bestand opnieuw toe aan de adresruimte van een proces om bijvoorbeeld de maximale opslagcapaciteit te vergroten met behulp van de functie
mdb_env_set_map_sizemaakt alle transacties en gerelateerde entiteiten in het algemeen en verwijzingen naar leesobjecten in het bijzonder volledig ongeldig.
Ten slotte is er nog een kenmerk dat zo verraderlijk is dat de onthulling van de essentie ervan niet in slechts één punt past. In het hoofdstuk over de B-boom heb ik een diagram gegeven van de organisatie van de pagina's in het geheugen. Hieruit volgt dat het adres van het begin van de buffer met geserialiseerde gegevens absoluut willekeurig kan zijn. Hierdoor is de verwijzing naar hen verkregen in de structuur MDB_val en cast naar een aanwijzer naar een structuur is over het algemeen niet uitgelijnd. Tegelijkertijd vereisen de architecturen van sommige chips (in het geval van iOS is dit armv7) dat het adres van alle gegevens een veelvoud is van de grootte van een machinewoord, of met andere woorden, de bitness van het systeem (voor armv7 is dit 32 bits). Met andere woorden, een operatie als *(int *foo)0x800002 op hen wordt gelijkgesteld met ontsnappen en leidt tot executie met een vonnis EXC_ARM_DA_ALIGN. Er zijn twee manieren om zo'n triest lot te vermijden.
De eerste is om de gegevens van tevoren naar een bekende uitgelijnde structuur te kopiëren. Op een aangepaste vergelijker wordt dit bijvoorbeeld als volgt weergegeven.
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 // ...
}Een alternatieve manier is om de compiler vooraf te informeren dat structuren met een sleutel en waarde niet uitgelijnd mogen worden met behulp van een attribuut aligned(1). Op ARM kan hetzelfde effect zijn en het kenmerk verpakt gebruiken. Gezien het feit dat het ook bijdraagt aan de optimalisatie van de ruimte die door de constructie wordt ingenomen, lijkt deze methode mij echter de voorkeur te hebben om de kosten van operaties voor gegevenstoegang te verhogen.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Bereik vragen
Om een groep records te herhalen, biedt LMDB een cursorabstractie. Laten we eens kijken hoe we ermee kunnen werken aan de hand van het voorbeeld van een tabel met metadata van de gebruikerscloud die we al kennen.
Als onderdeel van het weergeven van een lijst met bestanden in een map, moet u alle sleutels vinden waaraan de onderliggende bestanden en mappen zijn gekoppeld. In de vorige paragrafen hebben we de sleutels gesorteerd NodeKey zodat ze eerst worden gerangschikt op basis van hun bovenliggende map-ID. Dus technisch gezien wordt de taak van het verkrijgen van de inhoud van een map gereduceerd tot het plaatsen van de cursor op de bovengrens van een groep sleutels met een bepaald voorvoegsel, gevolgd door iteratie naar de ondergrens.
U kunt de bovengrens "op het voorhoofd" vinden door sequentieel te zoeken. Om dit te doen, wordt de cursor aan het begin van de volledige lijst met sleutels in de database geplaatst en vervolgens verhoogd totdat de sleutel met de bovenliggende map-ID eronder verschijnt. Deze aanpak heeft 2 duidelijke nadelen:
- De lineaire complexiteit van het zoeken, hoewel, zoals u weet, in bomen in het algemeen en in een B-boom in het bijzonder, het kan worden gedaan in logaritmische tijd.
- Tevergeefs worden alle pagina's die aan de gewenste pagina voorafgaan, uit het bestand naar het hoofdgeheugen gehaald, wat extreem duur is.
Gelukkig biedt de LMDB API een efficiënte manier om de cursor in eerste instantie te positioneren. Om dit te doen, moet u een dergelijke sleutel vormen, waarvan de waarde zeker kleiner zal zijn dan of gelijk is aan de sleutel die zich op de bovengrens van het interval bevindt . Met betrekking tot de lijst in de bovenstaande afbeelding kunnen we bijvoorbeeld een sleutel maken waarin het veld parentId zal gelijk zijn aan 2, en de rest is gevuld met nullen. Zo'n gedeeltelijk gevulde toets wordt ingevoerd in de functie mdb_cursor_get werking aangeeft 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);Als de bovengrens van de groep sleutels is gevonden, herhalen we deze totdat we elkaar ontmoeten of de sleutel met een andere parentId, of de sleutels raken helemaal niet op
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 groupWat leuk is, als onderdeel van iteratie met behulp van mdb_cursor_get, krijgen we niet alleen de sleutel, maar ook de waarde. Als het, om aan de selectievoorwaarden te voldoen, nodig is om onder andere de velden uit het waardegedeelte van het record te controleren, dan zijn ze vrij toegankelijk voor zichzelf zonder extra gebaren.
4.3. Relaties tussen tabellen modelleren
Tot op heden zijn we erin geslaagd om alle aspecten van het ontwerpen van en werken met een database met één tabel te overwegen. We kunnen zeggen dat een tabel een set gesorteerde records is die bestaat uit sleutel-waardeparen van hetzelfde type. Als u een sleutel weergeeft als een rechthoek en de bijbehorende waarde als een vak, krijgt u een visueel diagram van de database.
In het echte leven is het echter zelden mogelijk om rond te komen met zo weinig bloed. Vaak is het in een database ten eerste vereist om meerdere tabellen te hebben en ten tweede om selecties daarin uit te voeren in een andere volgorde dan de primaire sleutel. Dit laatste deel is gewijd aan de kwesties van hun creatie en onderlinge verbinding.
Index tabellen
De cloud-app heeft een sectie "Galerij". Het toont media-inhoud uit de hele cloud, gesorteerd op datum. Voor de optimale implementatie van een dergelijke selectie moet u naast de hoofdtabel een andere maken met een nieuw type sleutels. Ze bevatten een veld met de datum waarop het bestand is gemaakt, dat zal fungeren als het primaire sorteercriterium. Omdat de nieuwe sleutels naar dezelfde gegevens verwijzen als de sleutels in de onderliggende tabel, worden ze indexsleutels genoemd. Op de onderstaande afbeelding zijn ze oranje gemarkeerd.
Om de sleutels van verschillende tabellen binnen dezelfde database van elkaar te scheiden, is aan alle tabellen een extra technisch veld tableId toegevoegd. Door dit de hoogste prioriteit te geven bij het sorteren, groeperen we de sleutels eerst op tabellen en al binnen de tabellen - volgens onze eigen regels.
De indexsleutel verwijst naar dezelfde gegevens als de primaire sleutel. De ongecompliceerde implementatie van deze eigenschap door er een kopie van het waardegedeelte van de primaire sleutel aan te koppelen, is vanuit verschillende gezichtspunten tegelijk suboptimaal:
- Vanuit het oogpunt van ruimtebeslag kunnen de metadata behoorlijk rijk zijn.
- Vanuit het oogpunt van prestaties, aangezien u bij het bijwerken van de metadata van het knooppunt twee sleutels moet overschrijven.
- Vanuit het oogpunt van code-ondersteuning, als we vergeten de gegevens voor een van de sleutels bij te werken, krijgen we immers een subtiele bug van gegevensinconsistentie in de opslag.
Vervolgens zullen we bekijken hoe we deze tekortkomingen kunnen verhelpen.
Organisatie van relaties tussen tabellen
Het patroon is goed geschikt om een indextabel aan de hoofdtabel te koppelen "sleutel als waarde". Zoals de naam al aangeeft, is het waardegedeelte van het indexrecord een kopie van de primaire sleutelwaarde. Deze aanpak elimineert alle hierboven genoemde nadelen die gepaard gaan met het opslaan van een kopie van het waardegedeelte van het primaire record. De enige vergoeding is dat om de waarde door de indexsleutel te krijgen, u 2 query's naar de database moet maken in plaats van één. Schematisch ziet het resulterende databaseschema er als volgt uit.
Een ander patroon voor het organiseren van relaties tussen tabellen is "overbodige sleutel". De essentie is om extra attributen aan de sleutel toe te voegen, die niet nodig zijn om te sorteren, maar om de bijbehorende sleutel opnieuw te maken.Er zijn echter echte voorbeelden van het gebruik ervan in de Mail.ru Cloud-applicatie om te voorkomen dat u diep in de context van specifieke iOS-frameworks, zal ik een fictief, maar begrijpelijker voorbeeld geven.
Mobiele cloudclients hebben een pagina waarop alle bestanden en mappen worden weergegeven die de gebruiker met andere mensen heeft gedeeld. Aangezien er relatief weinig van dergelijke bestanden zijn en er veel specifieke informatie over publiciteit aan verbonden is (aan wie toegang wordt verleend, met welke rechten, enz.), zal het niet rationeel zijn om het te belasten met het waardegedeelte van het record in de hoofdtabel. Als u dergelijke bestanden echter offline wilt weergeven, moet u ze toch ergens opslaan. Een natuurlijke oplossing is om er een aparte tabel voor te maken. In het onderstaande diagram wordt de sleutel voorafgegaan door "P", en kan de tijdelijke aanduiding "propname" worden vervangen door de meer specifieke waarde "public info".
Alle unieke metadata, waarvoor de nieuwe tabel is gemaakt, wordt verplaatst naar het waardegedeelte van het record. Tegelijkertijd wil ik de gegevens over bestanden en mappen die al in de hoofdtabel zijn opgeslagen, niet dupliceren. In plaats daarvan worden redundante gegevens toegevoegd aan de "P"-sleutel in de vorm van de velden "node ID" en "timestamp". Dankzij hen kun je een indexsleutel maken, waarmee je de primaire sleutel kunt krijgen, waarmee je uiteindelijk de metadata van het knooppunt kunt krijgen.
Conclusie
We beoordelen de resultaten van de LMDB-implementatie positief. Daarna daalde het aantal bevriezingen van applicaties met 30%.
De resultaten van het verrichte werk hebben een reactie gevonden buiten het iOS-team. Momenteel is een van de belangrijkste "Bestanden" -secties in de Android-applicatie ook overgeschakeld naar het gebruik van LMDB, en andere delen zijn onderweg. De C-taal, waarin de key-value-opslag is geïmplementeerd, was een goede hulp om de applicatie in eerste instantie platformonafhankelijk te maken in de C++-taal. Voor een naadloze verbinding van de resulterende C++-bibliotheek met platformcode in Objective-C en Kotlin werd een codegenerator gebruikt van Dropbox, maar dat is een ander verhaal.
Bron: www.habr.com