LSM puu

LSM-puu (sanasta Log-structured merge-tree  - log -structured merge tree) on monissa DBMS -järjestelmissä käytetty tietorakenne , joka tarjoaa nopean indeksin pääsyn toistuvissa lisäyspyynnöissä (esimerkiksi tapahtumalokeja tallennettaessa ). LSM-puut, kuten muutkin, tallentavat avainarvopareja. LSM-puu ylläpitää kahta tai useampaa erilaista rakennetta, joista kukin on optimoitu sille laitteelle, johon se tallennetaan. Synkronointi näiden rakenteiden välillä tapahtuu lohkoissa.

Kuinka se toimii

Yksinkertainen versio LSM-puusta, kaksitasoinen puu, koostuu kahdesta puumaisesta rakenteesta C 0 ja C 1 . C 0 on pienempi ja se on tallennettu kokonaan RAM-muistiin, kun taas C 1 on haihtumattomassa muistissa. Uudet merkinnät lisätään kohtaan C 0 . Jos C0:n koko ylittää lisäyksen jälkeen jonkin ennalta määrätyn kynnyksen, viereinen segmentti poistetaan C0:stä ja yhdistetään Cl : n kanssa jatkuvassa varastoinnissa. Hyvä suorituskyky saavutetaan sillä, että puut on optimoitu varastointia varten ja yhdistäminen suoritetaan tehokkaasti ja useiden tietueiden ryhmissä yhdistämislajittelua muistuttavalla algoritmilla .

Useimmat käytännössä käytetyt LSM-puut toteuttavat useita tasoja. Taso 0 (kutsutaanko sitä MemTableksi) on tallennettu RAM-muistiin ja se voidaan esittää tavallisella puulla. Pysyvien tallennuslaitteiden tiedot tallennetaan avainten mukaan lajiteltuina taulukoina ( SSTable ). Taulukko voidaan tallentaa erillisenä tiedostona tai tiedostojoukona, jonka avainarvot eivät ole päällekkäisiä. Tietyn avaimen löytämiseksi sinun on tarkistettava sen läsnäolo MemTablessa ja käytävä sitten läpi kaikki pysyvän tallennuslaitteen SSTables.

Kaava työskentely LSM-puun kanssa:

Haettu avain voi esiintyä useissa taulukoissa yhtä aikaa pysyvillä tallennuslaitteilla, ja lopullinen vastaus riippuu ohjelmasta. Useimmat sovellukset tarvitsevat vain viimeisen arvon, joka liittyy tiettyyn avaimeen. Toisten, kuten Apache Cassandra , jossa jokainen arvo on tietokantarivi (ja rivillä voi olla eri määrä sarakkeita eri taulukoissa pysyvästä tallennustilasta), on käsiteltävä kaikki arvot jollakin tavalla saadakseen oikea tulos [1] . Kyselyn suoritusajan lyhentämiseksi käytännössä pyritään välttämään tilanne, jossa pysyviä tallennuslaitteita on liikaa.

Laajennuksia "taso"-menetelmään B+‍-rakenteiden ylläpitämiseksi on kehitetty , kuten bLSM [2] ja Diff-Index. [3]

Aukioloajat

LSM-puuarkkitehtuurin avulla voit täyttää lukupyynnöt joko RAM-muistista tai yhdellä kutsulla pysyviin tallennuslaitteisiin. Kirjoittaminen on myös aina nopeaa tallennustilan koosta riippumatta.

Pysyvien tallennuslaitteiden SSTable on muuttumaton. Siksi muutokset tallennetaan MemTableen, ja poistojen on lisättävä MemTableen erityinen arvo. Koska uusia lukuja tapahtuu peräkkäin indeksissä, päivitetty arvo tai arvon poistomerkintä tapahtuu ennen vanhoja arvoja. Säännöllisesti suoritettava vanhojen SST-taulukoiden yhdistäminen pysyvään tallennustilaan tekee nämä muutokset ja itse asiassa poistaa ja päivittää arvot, mikä poistaa tarpeettomat tiedot.

Muistiinpanot

  1. ↑ Tasoitettu tiivistys Apache Cassandrassa / datastax.com
  2. ↑ Margo Seltzer | MARGO I. SELTZER on Kanadan tietojenkäsittelytieteen 150-tutkimuksen johtaja British Columbian yliopistossa. Hänen tutkimuskohteensa ovat systeemit, rakennettu q... . Haettu 5. marraskuuta 2016. Arkistoitu alkuperäisestä 3. tammikuuta 2017.
  3. ↑ Arkistoitu kopio . Haettu 5. marraskuuta 2016. Arkistoitu alkuperäisestä 3. elokuuta 2016.

Linkit