LSM strom

Strom LSM (od Log-structured merge-tree  - log -structured merge tree) je datová struktura používaná v mnoha DBMS , která poskytuje rychlý přístup k indexu v podmínkách častých požadavků na vkládání (například při ukládání transakčních protokolů ). Stromy LSM, stejně jako jiné stromy, ukládají páry klíč–hodnota. Strom LSM udržuje dvě nebo více různých struktur, z nichž každá je optimalizovaná pro zařízení, na kterém bude uložena. Synchronizace mezi těmito strukturami probíhá v blocích.

Jak to funguje

Jednoduchá verze LSM stromu, dvouúrovňový strom, se skládá ze dvou stromových struktur C 0 a C 1 . C 0 je menší a je celý uložen v paměti RAM, zatímco C 1 je v energeticky nezávislé paměti. Nové položky se vkládají do C 0 . Pokud po vložení velikost Co překročí určitou předem stanovenou prahovou hodnotu, souvislý segment je odstraněn z Co a sloučen s C1 při trvalém ukládání. Dobrého výkonu je dosaženo díky skutečnosti, že stromy jsou optimalizovány pro jejich ukládání a sloučení se provádí efektivně a ve skupinách několika záznamů pomocí algoritmu připomínajícího slučovací řazení .

Většina LSM stromů používaných v praxi implementuje několik úrovní. Úroveň 0 (říkejme jí MemTable) je uložena v paměti RAM a může být reprezentována běžným stromem. Data na perzistentních úložných zařízeních jsou ukládána ve formě tabulek seřazených podle klíče ( SSTable ). Tabulku lze uložit jako samostatný soubor nebo jako sadu souborů s nepřekrývajícími se hodnotami klíče. Chcete-li najít konkrétní klíč, musíte zkontrolovat jeho přítomnost v MemTable a poté projít všechny SSTables na trvalém úložném zařízení.

Schéma práce se stromem LSM:

Hledaný klíč se může objevit v několika tabulkách najednou na perzistentních úložných zařízeních a konečná odpověď závisí na programu. Většina aplikací potřebuje pouze poslední hodnotu spojenou s daným klíčem. Jiní, jako je Apache Cassandra , ve kterém je každá hodnota řádkem databáze (a řádek může mít různý počet sloupců v různých tabulkách z trvalého úložiště), musí všechny hodnoty nějakým způsobem zpracovat, aby získali správný výsledek [1] . Aby se zkrátila doba provádění dotazu, v praxi se snaží vyhnout situaci s příliš mnoha tabulkami na perzistentních úložných zařízeních.

Byla vyvinuta rozšíření „úrovňové“ metody pro udržování B+‍-struktur , jako je bLSM [2] a Diff-Index. [3]

Otevírací doba

Stromová architektura LSM vám umožňuje uspokojit požadavek na čtení buď z paměti RAM, nebo v jednom volání na zařízení s trvalým úložištěm. Zápis je také vždy rychlý bez ohledu na velikost úložiště.

SSTable na perzistentních úložných zařízeních je neměnný. Proto jsou změny uloženy v MemTable a odstranění musí přidat zvláštní hodnotu do MemTable. Protože k novým čtením dochází postupně v indexu, aktualizovaná hodnota nebo položka odstranění hodnoty se objeví před starými hodnotami. Pravidelně spouštěné slučování starých SSTables na trvalém úložišti provede tyto změny a skutečně odstraní a aktualizuje hodnoty, čímž se zbaví nepotřebných dat.

Poznámky

  1. ↑ Vyrovnané zhutnění v Apache Cassandra / datastax.com
  2. ↑ Margo Seltzer | MARGO I. SELTZER je kanadskou 150 výzkumnou katedrou v oboru počítačových věd na University of British Columbia. Její výzkumné zájmy jsou v systémech, konstruovaných q... . Získáno 5. listopadu 2016. Archivováno z originálu 3. ledna 2017.
  3. ↑ Archivovaná kopie . Získáno 5. listopadu 2016. Archivováno z originálu 3. srpna 2016.

Odkazy