funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Střeva databází

6. 1. 2016 — k47

Tenhle článek je mojí skrom­nou snahou si udělat po­řá­dek v ně­kte­rých tech­ni­kách a da­to­vých struk­tu­rách, které se po­u­ží­vají uvnitř da­ta­bází. Nejde o nijak kom­pletní nebo hlu­boký výčet, pro­tože re­a­lita je vždycky mnohem kom­pli­ko­va­nější a zdán­livé de­taily (jako třeba kon­zis­tence) hrají vždycky větší roli, než se může na první pohled zdát.

Non-clus­te­red index

Ne­cluste­ro­vané indexy (jako na­pří­klad MyISAM mo­rálně vy­chá­ze­jící ze sta­řič­kého ISAM) mají od­dě­lený B-strom určený k na­vi­gaci a datový soubor ob­sa­hu­jící data jed­not­li­vých řádků. Listy B-stromu ob­sa­hují uka­za­tele do da­to­vého sou­boru a řádky se na­chá­zejí v pořadí vlo­žení, které ne­za­ru­čuje, že bude od­po­ví­dat pořadí pri­már­ního klíče.

Dů­sledky tohoto uspo­řá­dání jsou jasné: Vklá­dání nových řádků je rychlé, pro­tože stačí najít volné místo v da­to­vém sou­boru, vložit klíč do B-stromů všech indexů (pri­már­ních i sekun­dár­ních), na­mí­řit poin­ter na řádek a voilà, data jsou ulo­žená. Do­ta­zo­vání jed­noho řádku je celkem ne­za­jí­mavé, stačí najít klíč v pří­sluš­ném B-stromu a skočit na poin­ter. Na­proti tomu hle­dání roz­sahů podle pri­már­ního klíče není tak růžové. Na rozdíl od cluste­ro­va­ného indexu data nejsou ulo­žena se­řa­zená – je proto třeba najít po­ža­do­vaný rozsah v B-stromu a de­re­fe­ren­co­vat všechny na­le­zené poin­tery, které můžou vést na ne­před­ví­da­telná místa v da­to­vém sou­boru a ná­hod­nému IO, které je ka­ta­stro­fální na ro­tu­jí­cích dis­cích, ale i na mo­der­něj­ších mé­di­ích je po­ma­lejší než sek­venční čtení.

Clus­te­red index

Jak je vidět z pří­jemně kryp­tic­kého sché­matu, cluste­ro­vaný index3 (jako je na­pří­klad v InnoDB) ob­sa­huje řádky se­řa­ze­ném stejně jako pri­mární klíč. Ty můžou být buď přímo v lis­tech B-stromu nebo v jiném sou­boru, na který se listy B-stromu od­ka­zují, ale který stále ob­sa­huje řádky se­řa­zené. Toto uspo­řá­dání při­dává ur­či­tou režii pro vklá­dání nových zá­znamů, pro­tože musí udr­žo­vat řazení, ale na druhou stranu vede k rych­lým range select do­ta­zům podle pri­már­ního klíče, pro­tože stačí najít za­čá­tek a pak číst data dokud pre­di­kát dotazu platí.

Při hle­dání podle sekun­dár­ních indexů je třeba jedna úroveň ne­pří­mosti navíc. B-strom sekun­dár­ního indexu v lis­tech ob­sa­huje pri­mární klíč pří­sluš­ného řádku, ten je třeba použít pro pro­hle­dání pri­már­ního B-stromu a zís­kání sa­mot­ného řádku. Pro­tože jsou místo fy­zic­kých poin­terů mí­ří­cích do dis­ko­vých bloků, po­u­žity vir­tu­ální iden­ti­fi­ká­tory pri­már­ního klíče, je tento pří­stup vý­razně fle­xi­bil­nější a do­vo­luje pře­sou­vat řádky bez toho, aby bylo třeba změnit všechny indexy, které na pře­stě­ho­vaný řádek uka­zují.

Tady se taky vy­platí zmínit co­ve­ring index, který není to samé, co clus­te­red index. Co­ve­ring index (nebudu se snažit pře­klá­dat) je takový index, který kom­pletně po­krývá všechny sloupce jed­noho dotazu. Když tedy na­pří­klad sekun­dární index ob­sa­huje všechny sloupce zmí­něné v dotazu, není třeba hledat v B-stromu pri­már­ního indexu. Pri­mární clus­te­red index je z prin­cipu zá­ro­veň co­ve­ring pokud dotaz hledá podle pri­már­ního klíče. Ně­které da­ta­báze (na­pří­klad TokuDB, pokud se ne­pletu) na­bí­zejí mož­nost co­ve­ring sekun­dár­ních indexů. V ta­ko­vém pří­padě listy B-stromu ne­ob­sa­hují pri­mární klíč, ale všechny sloupce, které nejsou sou­částí klíče sekun­dár­ního indexu. Když se pak dotaz roz­hodne použít sekun­dární co­ve­ring index, má všechna data k dis­po­zici.

Fractal trees

Fractal trees, po­u­ží­vané v da­ta­bá­zo­vém enginu TokuDB, jsou ve své pod­statě oby­čejné B-stromy, ve kte­rých je každý vnitřní uzel obo­ha­cený o buffer, do kte­rého smě­řují zápisy. Když se buffer naplní, změny jsou za­tla­čeny a pro­pa­go­vány do pří­sluš­ných uzlů o úroveň níž. Díky tomuto uspo­řá­dání jsou všechny zápisy sek­venční, stejně jako IO, pro­tože se vždy za­pi­suje sek­venčně do bu­f­feru nebo se změny sek­venčně za­pi­sují o úroveň níže. To vede k nízké write am­pli­fi­cation a dob­rému cho­vání, když se kostra B-stromu ne­ve­jde do paměti. Není třeba pro každou ak­tu­a­li­zaci dělat až log(n) ná­hod­ných IO ope­rací, pro­tože zápisy jsou amor­ti­zo­vané a pro­vede se jen pár sek­venč­ních IO ope­rací.

Frak­tální stromy, po­dobně jako LSMT, ex­ce­lují velice rych­lými in­serty, ale na rozdíl od LSMT si stále za­cho­vá­vají podobu B-stromů. Není tedy třeba na rozdíl od LSMT pro­hle­dá­vat log(n) se­řa­ze­ných sou­borů, ale jen jeden index o hloubce logb(n), kde b je nějaké re­la­tivně velké číslo + pří­slušné bu­f­fery.

Bu­f­fery se hodí na víc než jen na do­čas­nou aku­mu­laci insert/update/delete ope­rací. Dají se také využít pro od­lo­žené změny struk­tury ta­bulky. V ty­pic­kém pří­padě, když pomocí alter table přidám nebo ode­beru slou­pec, da­ta­báze musí pře­sta­vět celou ta­bulku, což může trvat velice dlou­hou dobu. Ve frak­tál­ním stromě můžu do bu­f­feru vložit zprávu addcolumn, která se po­stupně pro­pa­guje k listům, jak je třeba, a když jich do­sáhne, přidá po­ža­do­vaný slou­pec. Struk­tura ta­bulky se tedy ne­změní hned, ale až někdy v bu­douc­nosti, když se zápisy do­sta­nou k listům B-stromu. Da­ta­báze přitom udr­žuje iluzi, že slou­pec byl přidán a dotazy vrací správná data.

Log-structu­red merge-tree

LSMT (po­u­ží­vané na­pří­klad v Le­velDB nebo RocksDB) je in­terně uspo­řá­dané jako série se­řa­ze­ných polí/sou­borů. V nej­jed­no­duš­ším pří­padě může jít o ně­ko­lik úrovní (0..k), z nichž k-tá má ve­li­kost 2k. Nový ele­ment je vložen do nulté úrovně. Pokud je prázdná, všechno skončí, pokud je plná, dvě pole nulté úrovně se sloučí do dva­krát vět­šího se­řa­ze­ného pole první úrovně1. Když je i ta úroveň ob­sa­zená, do­chází re­kur­zivně ke slu­čo­vání dokud ne­na­razí na prázd­nou úroveň. Sku­tečně po­u­žitá sché­mata můžou být slo­ži­tější, kdy v každé úrovni je ně­ko­lik sou­borů nebo se všechny sou­bory na­chá­zejí v jedné úrovni a kan­di­dáty na kom­pakci jsou vy­bí­rány heu­ris­ticky, mohou se také lišit tím, jestli je do­vo­leno, aby různé sou­bory ze stejné úrovně ob­sa­ho­valy pře­krý­va­jící se roz­sahy klíčů.

LSMT tedy má 1 až log(n) úrovní a všechny in­serty do nej­nižší z nich jsou velice rychlé, pro­tože nej­nižší úrovně zcela žijí v paměti2 a všechny IO ope­race zápisů jsou z pod­staty věci sek­venční. Amor­ti­zo­vaná cena je také kon­stantní, jen někdy může zápis čekat, pro­tože spustí kom­pakci. Slu­čo­vání však může pro­bí­hat pa­ra­lelně na pozadí a ne­blo­ko­vat pro­bí­ha­jící čtení nebo jiné zápisy, pro­tože se­řa­zený soubor je efek­tivně ne­měnný. Pro­blém ale může před­sta­vo­vat si­tu­ace, kdy slu­čo­vání ne­stíhá, pro­tože rych­lost zápisu je li­mi­to­vaná rych­lostí kom­pakce a kom­pakce mezi úrov­němi vede k write apli­fi­cation.

Při hle­dání je třeba pro­chá­zet se­řa­zené sou­bory jeden po druhém od nej­no­věj­šího k nej­star­šímu a pomocí bi­nár­ního hle­dání v nich pátrat po po­ža­do­va­ném klíči a to má v jed­no­du­chém sché­matu na­črt­nu­tém výše slo­ži­tost něco jako log^2(n). Pro range scan dotazy je nutné vždycky projít všechny sou­bory a není možné, jako v pří­padě bo­do­vých dotazů, pře­stat, když je klíč na­le­zen.

Pro urych­lení bo­do­vých dotazů může každý soubor ob­sa­ho­vat ně­ja­kou verzi Bloom fil­teru (nebo něco po­dob­ného) pro každý soubor. Pro range scan dotazy může mít bloom filter na pre­fi­xech klíčů nebo něco jako Adap­tive Range Filter.

Fracti­o­nal cas­ca­ding

LSMT má slo­ži­tost dotazů log^2(n). Ob­sa­huje log(n) úrovní a v každé je třeba pro­vést bi­nární hle­dání o slo­ži­tosti ±log(n). Fracti­o­nal cas­ca­ding zlep­šuje asymptoty hle­dání na log(n)+log(m) tím, že každá úroveň ob­sa­huje uka­za­tele do hlubší úrovně na od­po­ví­da­jící rozsah klíčů. Je­li­kož od­ka­zo­vaný rozsah v hlubší úrovni má kon­stantní ve­li­kost, je třeba udělat log(m) bi­nární hle­dání v jedné úrovni a pak ná­sle­do­vat poin­tery do malého výseku hlubší úrovně, ten pro­hle­dat a v pří­padě nouze po­kra­čo­vat hlou­běji ma­xi­málně log(n) úrovní – tudíž log(n)+log(m). Na druhou stanu to při­dává režii, která je po­třeba k udr­žo­vání a po­čí­tání těchto poin­terů. Pro­tože jsou často krajní hod­noty ko­pí­ro­vány z vyšší úrovně do té nižší, zvy­šuje to o něco pro­sto­rové nároky.

Fracti­o­nal cas­ca­ding bylo po­u­žité v TokuDB jako první verze frak­tál­ních stromů, než přešli na vy­lep­šené B-stromy. To někdy vy­vo­lává zmatek, pro­tože ně­které články po­pi­sují jedno a ně­které to druhé.


Dále k tématu:

Pozn:

  1. Po­u­žitý al­go­rit­mus je pod­statě merge sort, jen je počítá s ně­ko­lika spe­ci­ál­ními pří­pady. Např. když je ele­ment v obou slu­čo­va­ných úrov­ních, do vý­sledné ko­lekce zapíše jen ten nej­no­vější, když narazí na tomb­stone ozna­ču­jící sma­zaný ele­ment, musí ho zapsat jen pokud nejde o slu­čo­vání do nej­vyšší úrovně, atd.
  2. Data v paměti se na­chá­zejí ve struk­tuře, které se říká mem­table (může být im­ple­men­to­vána jako skip list), se­řa­zené sou­bory na disku se v ně­kte­rých im­ple­men­ta­cích ozna­čují sst­file.
  3. Dopad cluste­ro­va­ných/ne-cluste­ro­va­ných indexů na slo­ži­tost ope­rací a funkci plá­no­vače je de­mon­stro­ván v Access Path Se­lection in a Re­lati­o­nal Da­ta­base Ma­nage­ment System.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články