Arborele LSM

Arborele LSM (de la Log-structured merge-tree  - Log -structured merge-tree) este o structură de date utilizată în multe SGBD -uri care oferă acces rapid la index în condițiile solicitărilor de inserare frecvente (de exemplu, când se stochează jurnalele de tranzacții ). Arborii LSM, ca și alți arbori, stochează perechi cheie-valoare. Un arbore LSM menține două sau mai multe structuri diferite, fiecare optimizată pentru dispozitivul pe care va fi stocat. Sincronizarea între aceste structuri are loc în blocuri.

Cum funcționează

O versiune simplă a unui arbore LSM, un arbore cu două niveluri, constă din două structuri asemănătoare arborelui C 0 și C 1 . C 0 este mai mic și este stocat în întregime în RAM, în timp ce C 1 este în memoria nevolatilă. Intrările noi sunt introduse în C 0 . Dacă, după inserare, dimensiunea lui C0 depășește un prag predeterminat, segmentul învecinat este îndepărtat din C0 și fuzionat cu C1 pe stocare persistentă. Performanțe bune se obțin datorită faptului că arborele sunt optimizați pentru stocarea lor, iar îmbinarea se realizează eficient și în grupuri de mai multe înregistrări, folosind un algoritm care amintește de sort sort .

Majoritatea arborilor LSM utilizați în practică implementează mai multe niveluri. Nivelul 0 (să-l numim MemTable) este stocat în RAM și poate fi reprezentat printr-un arbore obișnuit. Datele de pe dispozitivele de stocare persistente sunt stocate sub formă de tabele sortate după cheie ( SSTable ). Tabelul poate fi stocat ca un fișier separat sau un set de fișiere cu valori cheie care nu se suprapun. Pentru a găsi o anumită cheie, trebuie să verificați prezența acesteia în MemTable și apoi să parcurgeți toate SSTables-urile de pe dispozitivul de stocare persistent.

Schema de lucru cu LSM-tree:

Cheia căutată poate apărea în mai multe tabele simultan pe dispozitivele de stocare persistente, iar răspunsul final depinde de program. Majoritatea aplicațiilor au nevoie doar de ultima valoare asociată cu o anumită cheie. Alții, cum ar fi Apache Cassandra , în care fiecare valoare este un rând de bază de date (și un rând poate avea un număr diferit de coloane în tabele diferite din stocarea persistentă), trebuie să proceseze toate valorile într-un fel pentru a obține rezultat corect [1] . Pentru a reduce timpul de execuție a interogărilor, în practică se încearcă să evite situația cu prea multe tabele pe dispozitivele de stocare persistente.

Au fost dezvoltate extensii la metoda „nivel” pentru menținerea structurilor B+ ‍, cum ar fi bLSM [2] și Diff-Index. [3]

Orele de deschidere

Arhitectura arborescentă LSM vă permite să satisfaceți o solicitare de citire fie din RAM, fie într-un singur apel către dispozitivele de stocare persistente. De asemenea, scrierea este întotdeauna rapidă, indiferent de dimensiunea de stocare.

SSTable pe dispozitivele de stocare persistente este imuabil. Prin urmare, modificările sunt stocate în MemTable, iar ștergerile trebuie să adauge o valoare specială la MemTable. Deoarece citirile noi apar secvenţial în index, valoarea actualizată sau intrarea de ştergere a valorii va avea loc înaintea valorilor vechi. O îmbinare periodică a SSTables vechi pe stocare persistentă va face aceste modificări și va șterge și actualiza valorile, scăpând de datele inutile.

Note

  1. ↑ Compactare nivelată în Apache Cassandra / datastax.com
  2. ↑ Margo Seltzer | MARGO I. SELTZER este catedra de cercetare Canada 150 în informatică la Universitatea din Columbia Britanică. Interesele ei de cercetare sunt în sisteme, construit q... . Consultat la 5 noiembrie 2016. Arhivat din original la 3 ianuarie 2017.
  3. ↑ Copie arhivată . Consultat la 5 noiembrie 2016. Arhivat din original la 3 august 2016.

Link -uri