LSM-träd

LSM-träd (från Log-structured merge-tree  - log- structured merge tree) är en datastruktur som används i många DBMS:er som ger snabb indexåtkomst under förhållanden med frekventa infogningsbegäranden (till exempel vid lagring av transaktionsloggar ). LSM-träd, liksom andra träd, lagrar nyckel-värdepar. Ett LSM-träd upprätthåller två eller flera olika strukturer, var och en optimerad för den enhet som den ska lagras på. Synkronisering mellan dessa strukturer sker i block.

Hur det fungerar

En enkel version av ett LSM-träd, ett tvånivåträd, består av två trädliknande strukturer C 0 och C 1 . C 0 är mindre och lagras helt och hållet i RAM, medan C 1 är i icke-flyktigt minne. Nya poster infogas i C 0 . Om, efter införandet, storleken på C0 överstiger någon förutbestämd tröskel, tas det sammanhängande segmentet bort från C0 och slås samman med C1 vid beständig lagring. Bra prestanda uppnås tack vare det faktum att träden är optimerade för sin lagring, och sammanslagningen utförs effektivt och i grupper om flera poster, med hjälp av en algoritm som påminner om merge sort .

De flesta LSM-träd som används i praktiken implementerar flera nivåer. Nivå 0 (låt oss kalla det MemTable) lagras i RAM och kan representeras av ett vanligt träd. Data på beständiga lagringsenheter lagras i form av tabeller sorterade efter nyckel ( SSTable ). Tabellen kan lagras som en separat fil eller en uppsättning filer med icke-överlappande nyckelvärden. För att hitta en specifik nyckel måste du kontrollera dess närvaro i MemTable och sedan gå igenom alla SSTables på den beständiga lagringsenheten.

Schema för att arbeta med LSM-träd:

Den sökta nyckeln kan visas i flera tabeller samtidigt på beständiga lagringsenheter, och det slutliga svaret beror på programmet. De flesta applikationer behöver bara det sista värdet som är associerat med en given nyckel. Andra, som Apache Cassandra , där varje värde är en databasrad (och en rad kan ha olika antal kolumner i olika tabeller från beständig lagring), måste bearbeta alla värden på något sätt för att få korrekt resultat [1] . För att minska exekveringstiden för frågor försöker de i praktiken undvika situationen med för många tabeller på beständiga lagringsenheter.

Tillägg till "nivåmetoden" för att underhålla B+‍-strukturer har utvecklats , såsom bLSM [2] och Diff-Index. [3]

Öppettider

LSM-trädarkitekturen tillåter dig att tillfredsställa en läsbegäran antingen från RAM eller i ett anrop till beständiga lagringsenheter. Skrivandet går också alltid snabbt oavsett lagringsstorlek.

SSTable på beständiga lagringsenheter är oföränderlig. Därför lagras ändringar i MemTable, och borttagningar måste lägga till ett speciellt värde till MemTable. Eftersom nya läsningar sker sekventiellt över indexet, kommer det uppdaterade värdet eller värderaderingsposten att ske före de gamla värdena. En periodisk sammanslagning av gamla SSTables på beständig lagring kommer att göra dessa ändringar och faktiskt ta bort och uppdatera värden, vilket tar bort onödig data.

Anteckningar

  1. ↑ Utjämnad komprimering i Apache Cassandra / datastax.com
  2. ↑ Margo Seltzer | MARGO I. SELTZER är Canada 150 Research Chair in Computer Science vid University of British Columbia. Hennes forskningsintressen är system, konstruerade q... . Hämtad 5 november 2016. Arkiverad från originalet 3 januari 2017.
  3. ↑ Arkiverad kopia . Hämtad 5 november 2016. Arkiverad från originalet 3 augusti 2016.

Länkar