Střeva databází

Tenhle článek je mojí skromnou snahou si udělat pořádek v některých technikách a datových strukturách, které se používají uvnitř databází. Nejde o nijak kompletní nebo hluboký výčet, protože realita je vždycky mnohem komplikovanější a zdánlivé detaily (jako třeba konzistence) hrají vždycky větší roli, než se může na první pohled zdát.

Non-clustered index

Neclusterované indexy (jako například MyISAM morálně vycházející ze stařičkého ISAM) mají oddělený B-strom určený k navigaci a datový soubor obsahující data jednotlivých řádků. Listy B-stromu obsahují ukazatele do datového souboru a řádky se nacházejí v pořadí vložení, které nezaručuje, že bude odpovídat pořadí primárního klíče.

Důsledky tohoto uspořádání jsou jasné: Vkládání nových řádků je rychlé, protože stačí najít volné místo v datovém souboru, vložit klíč do B-stromů všech indexů (primárních i sekundárních), namířit pointer na řádek a voilà, data jsou uložená. Dotazování jednoho řádku je celkem nezajímavé, stačí najít klíč v příslušném B-stromu a skočit na pointer. Naproti tomu hledání rozsahů podle primárního klíče není tak růžové. Na rozdíl od clusterovaného indexu data nejsou uložena seřazená – je proto třeba najít požadovaný rozsah v B-stromu a dereferencovat všechny nalezené pointery, které můžou vést na nepředvídatelná místa v datovém souboru a náhodnému IO, které je katastrofální na rotujících discích, ale i na modernějších médiích je pomalejší než sekvenční čtení.

Clustered index

Jak je vidět z příjemně kryptického schématu, clusterovaný index3 (jako je například v InnoDB) obsahuje řádky seřazeném stejně jako primární klíč. Ty můžou být buď přímo v listech B-stromu nebo v jiném souboru, na který se listy B-stromu odkazují, ale který stále obsahuje řádky seřazené. Toto uspořádání přidává určitou režii pro vkládání nových záznamů, protože musí udržovat řazení, ale na druhou stranu vede k rychlým range select dotazům podle primárního klíče, protože stačí najít začátek a pak číst data dokud predikát dotazu platí.

Při hledání podle sekundárních indexů je třeba jedna úroveň nepřímosti navíc. B-strom sekundárního indexu v listech obsahuje primární klíč příslušného řádku, ten je třeba použít pro prohledání primárního B-stromu a získání samotného řádku. Protože jsou místo fyzických pointerů mířících do diskových bloků, použity virtuální identifikátory primárního klíče, je tento přístup výrazně flexibilnější a dovoluje přesouvat řádky bez toho, aby bylo třeba změnit všechny indexy, které na přestěhovaný řádek ukazují.

Tady se taky vyplatí zmínit covering index, který není to samé, co clustered index. Covering index (nebudu se snažit překládat) je takový index, který kompletně pokrývá všechny sloupce jednoho dotazu. Když tedy například sekundární index obsahuje všechny sloupce zmíněné v dotazu, není třeba hledat v B-stromu primárního indexu. Primární clustered index je z principu zároveň covering pokud dotaz hledá podle primárního klíče. Některé databáze (například TokuDB, pokud se nepletu) nabízejí možnost covering sekundárních indexů. V takovém případě listy B-stromu neobsahují primární klíč, ale všechny sloupce, které nejsou součástí klíče sekundárního indexu. Když se pak dotaz rozhodne použít sekundární covering index, má všechna data k dispozici.

Fractal trees

Fractal trees, používané v databázovém enginu TokuDB, jsou ve své podstatě obyčejné B-stromy, ve kterých je každý vnitřní uzel obohacený o buffer, do kterého směřují zápisy. Když se buffer naplní, změny jsou zatlačeny a propagovány do příslušných uzlů o úroveň níž. Díky tomuto uspořádání jsou všechny zápisy sekvenční, stejně jako IO, protože se vždy zapisuje sekvenčně do bufferu nebo se změny sekvenčně zapisují o úroveň níže. To vede k nízké write amplification a dobrému chování, když se kostra B-stromu nevejde do paměti. Není třeba pro každou aktualizaci dělat až log(n) náhodných IO operací, protože zápisy jsou amortizované a provede se jen pár sekvenčních IO operací.

Fraktální stromy, podobně jako LSMT, excelují velice rychlými inserty, ale na rozdíl od LSMT si stále zachovávají podobu B-stromů. Není tedy třeba na rozdíl od LSMT prohledávat log(n) seřazených souborů, ale jen jeden index o hloubce logb(n), kde b je nějaké relativně velké číslo + příslušné buffery.

Buffery se hodí na víc než jen na dočasnou akumulaci insert/update/de­lete operací. Dají se také využít pro odložené změny struktury tabulky. V typickém případě, když pomocí alter table přidám nebo odeberu sloupec, databáze musí přestavět celou tabulku, což může trvat velice dlouhou dobu. Ve fraktálním stromě můžu do bufferu vložit zprávu addcolumn, která se postupně propaguje k listům, jak je třeba, a když jich dosáhne, přidá požadovaný sloupec. Struktura tabulky se tedy nezmění hned, ale až někdy v budoucnosti, když se zápisy dostanou k listům B-stromu. Databáze přitom udržuje iluzi, že sloupec byl přidán a dotazy vrací správná data.

Log-structured merge-tree

LSMT (používané například v LevelDB nebo RocksDB) je interně uspořádané jako série seřazených polí/souborů. V nejjednodušším případě může jít o několik úrovní (0..k), z nichž k-tá má velikost 2k. Nový element je vložen do nulté úrovně. Pokud je prázdná, všechno skončí, pokud je plná, dvě pole nulté úrovně se sloučí do dvakrát většího seřazeného pole první úrovně1. Když je i ta úroveň obsazená, dochází rekurzivně ke slučování dokud nenarazí na prázdnou úroveň. Skutečně použitá schémata můžou být složitější, kdy v každé úrovni je několik souborů nebo se všechny soubory nacházejí v jedné úrovni a kandidáty na kompakci jsou vybírány heuristicky, mohou se také lišit tím, jestli je dovoleno, aby různé soubory ze stejné úrovně obsahovaly překrývající se rozsahy klíčů.

LSMT tedy má 1 až log(n) úrovní a všechny inserty do nejnižší z nich jsou velice rychlé, protože nejnižší úrovně zcela žijí v paměti2 a všechny IO operace zápisů jsou z podstaty věci sekvenční. Amortizovaná cena je také konstantní, jen někdy může zápis čekat, protože spustí kompakci. Slučování však může probíhat paralelně na pozadí a neblokovat probíhající čtení nebo jiné zápisy, protože seřazený soubor je efektivně neměnný. Problém ale může představovat situace, kdy slučování nestíhá, protože rychlost zápisu je limitovaná rychlostí kompakce a kompakce mezi úrovněmi vede k write aplification.

Při hledání je třeba procházet seřazené soubory jeden po druhém od nejnovějšího k nejstaršímu a pomocí binárního hledání v nich pátrat po požadovaném klíči a to má v jednoduchém schématu načrtnutém výše složitost něco jako log2(n). Pro range scan dotazy je nutné vždycky projít všechny soubory a není možné, jako v případě bodových dotazů, přestat, když je klíč nalezen.

Pro urychlení bodových dotazů může každý soubor obsahovat nějakou verzi Bloom filteru (nebo něco podobného) pro každý soubor. Pro range scan dotazy může mít bloom filter na prefixech klíčů nebo něco jako Adaptive Range Filter.

Fractional cascading

LSMT má složitost dotazů log2(n). Obsahuje log(n) úrovní a v každé je třeba provést binární hledání o složitosti ±log(n). Fractional cascading zlepšuje asymptoty hledání na log(n)+log(m) tím, že každá úroveň obsahuje ukazatele do hlubší úrovně na odpovídající rozsah klíčů. Jelikož odkazovaný rozsah v hlubší úrovni má konstantní velikost, je třeba udělat log(m) binární hledání v jedné úrovni a pak následovat pointery do malého výseku hlubší úrovně, ten prohledat a v případě nouze pokračovat hlouběji maximálně log(n) úrovní – tudíž log(n)+log(m). Na druhou stanu to přidává režii, která je potřeba k udržování a počítání těchto pointerů. Protože jsou často krajní hodnoty kopírovány z vyšší úrovně do té nižší, zvyšuje to o něco prostorové nároky.

Fractional cascading bylo použité v TokuDB jako první verze fraktálních stromů, než přešli na vylepšené B-stromy. To někdy vyvolává zmatek, protože některé články popisují jedno a některé to druhé.

  • fractional cascading se zmiňuje v kontextu datových struktur v paměti Kmett ve svých přednáškách.
  • Něco málo o COLA a fractional cascading tady a tady.

Dále k tématu:

Pozn:

  1. Použitý algoritmus je podstatě merge sort, jen je počítá s několika speciálními případy. Např. když je element v obou slučovaných úrovních, do výsledné kolekce zapíše jen ten nejnovější, když narazí na tombstone označující smazaný element, musí ho zapsat jen pokud nejde o slučování do nejvyšší úrovně, atd.
  2. Data v paměti se nacházejí ve struktuře, které se říká memtable (může být implementována jako skip list), seřazené soubory na disku se v některých implementacích označují sstfile.
  3. Dopad clusterovaných/ne-clusterovaných indexů na složitost operací a funkci plánovače je demonstrován v Access Path Selection in a Relational Database Management System.

Flattr this!

This entry was posted in DB, DS. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *