funkcionálně.cz

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

Pár poznámek k pár poznámkám o sloupcových databázích

6. 7. 2015 — k47

Teorie je jed­no­du­chá: Sloup­cové da­ta­báze jsou takové, které uklá­dají data po sloup­cích místo po řád­cích, jak je v da­ta­bá­zo­vém světě běžné.

To má ně­ko­lik zá­sad­ních výhod, které jsou v ur­či­tých si­tu­a­cích k ne­za­pla­cení. Když po­tře­buji při­stou­pit jen k ně­ko­lika málo sloup­cům, načtu pouze jejich data a ne­mu­sím se ob­tě­žo­vat s jinými po­lož­kami ze stej­ného řádku. V řád­ko­vých da­ta­bá­zích je vždycky nutné načíst celý řádek, pro­tože data se z disků na­čí­tají po blo­cích, které ob­sa­hují mnoho řádků na­jed­nou. Nemůžu si vy­nu­tit, aby mi disk po­skytl jen bajty z těch pár sloupců, které mě za­jí­mají. Do­stanu všechno nebo nic. Na­proti tomu ve sloup­cové DB je každý slou­pec uložen jako sou­vislý region dat. Jeden dis­kový blok tedy ob­sa­huje jen a pouze data jed­noho sloupce. V nej­jed­no­dušší podobě jde o velké pole (jehož prvky mají často fixní délku) pro každý slou­pec (jako v pří­padě Mo­ne­tDB) nebo o sérii krat­ších seg­mentů (jako v X100).

Ta­ko­véto uspo­řá­dání dat se hodí pro OLAP, tedy když mě místo jed­not­li­vých zá­znamů za­jí­mají agre­gace jed­noho nebo ně­ko­lika málo sloupců (např. ta­bulka jich má 50, ale v dotazu se dva vy­sky­tují v pod­mínce a z ně­ko­lika dal­ších se po­čí­tají prů­měry). Pro­tože jde kon­cepčně o pole, na­le­zení od­po­ví­da­jí­cích po­lo­žek v růz­ných sloup­cích je tri­vi­ální: jde o pouhý index * velikost položky a dotaz se dá pře­lo­žit do série jed­no­du­chých a velice efek­tiv­ních smyček.5

Sloup­cové da­ta­báze jsou krásné (jak je vidět v The Design and Im­ple­men­tation of Modern Column-Ori­en­ted Da­ta­base Sys­tems), ale přesto o nich dneska nechci psát.

Ne­dávno jsem si pře­četl článek Ně­ko­lik po­zná­mek ke sloup­co­vým da­ta­bá­zím, který ve mě za­ne­chal pří­jemný hře­jivý pocit, hlavně proto, že se zmi­ňo­val o hard­waru, SIMD in­struk­cích a efek­ti­vitě práce s in-memory daty. Tam někde mě na­padlo vy­zkou­šet, jak rychle taková te­o­re­tická in-memory da­ta­báze může běžet. Když z rov­nice vy­pad­nou všechny ro­tu­jící disky, SSD nebo síťové karty, záleží jen na pa­mě­tech a pro­ce­soru. Z kom­pli­ko­va­ného sys­tému se stane něco tri­vi­ál­ního, co je možné pro­zkou­mat a po­cho­pit. Na­pří­klad jaký vliv má kom­prese, SIMD ope­race, in­strukce gather (která načte ně­ko­lik pro­ce­so­ro­vých slov na­je­dou, po­ten­ci­álně pa­ra­lelně), pre­fetch (která sig­na­li­zuje pro­ce­soru, jaká data budou brzo po­třeba)2 nebo non-tem­po­ral load4?

Ale tak daleko jsem se ne­do­stal. Pro­tože jak to vypadá na tom zas tak moc ne­zá­leží, li­mi­tu­jí­cím fak­to­rem je hlavně pro­pust­nost pamětí.

Napsal jsem tri­vi­ální test, který de­fi­no­val struct row s ně­ko­lika os­mi­baj­to­vými po­lož­kami.

struct row {
  long a,b,c,d,e,f,g,h;
  long i,j,k,l,m,n,o,p;
};

Pak jsem vy­tvo­řil veliký špalek dat, který se vešel do paměti.

struct row *rows = malloc(sizeof(struct row) * 50000000);

for (int i = 0; i < 50000000; i++) {
  rows[i].a = 1;
}

Na­ko­nec jsem jím pro­le­těl během jedné krásné ite­race.

for (int i = 0; i < 50000000; i++) {
  sum += rows[i].a;
}

Za­zna­me­ná­val jsem vý­sledky s různým počtem po­lo­žek ve structu row. V prvním řádku má row po­ložky od a do p (do­hro­mady 128 bajtů), v po­sled­ním ob­sa­huje jen je­di­nou po­ložku (8 bajtů). Vý­sledky byly celkem pře­kva­pivé.

longsbytestimethrou­gh­put
16128 B320 ms~
864 B227 ms13.1 GB/s
432 B112 ms13.3 GB/s
216 B55 ms13.5 GB/s
18 B33 ms11.3 GB/s

Jak je vidět, že i když sčítám jen hod­noty prv­ního atri­butu, rych­lost klesá plus/mínus li­ne­árně s při­bý­va­jí­cím počtem po­lo­žek v řádku. Pro­ce­sor totiž z paměti ne­na­čítá data po 64-bi­to­vých slo­vech, ale po cache line, které mají 64 bajtů. Musí tedy z RAM vy­do­lo­vat celých 64 bajtů, i když z nich vy­u­žije jen jednu osminu a to věci značně zpo­malí.

Dále je vidět, že rych­lost je li­mi­to­vaná pro­pust­ností pamětí. V mém desktopu jsou dva 1333MHz DDR3 moduly, které by podle ta­bu­lek měly do­ká­zat pro­tla­čit 2x10.6 GB za vte­řinu. Jedno jádro běžící na plné otáčky dokáže roz­pou­tat takové peklo, že sežere vět­šinu tohoto objemu. Kdy­bych použil všechna čtyři jádra, pro­gram by byl li­mi­to­ván pro­pust­ností pamětí a běžel by v nej­lep­ším pří­padě ~2x rych­leji. Hy­perthrea­ding by v tomto pří­padě ne­při­nesl žádné zrych­lení.

Z toho vy­plývá, že v této si­tu­aci kom­pli­ko­vané gather/prefetch in­strukce nemají moc velký význam. Pro­gram ve všech pří­pa­dech běží s nízkým IPC (lehce nad 1 in­strukci na takt pro velké row structy, skoro 1.2 pro row s jednou po­lož­kou). gather může načíst ně­ko­lik míst paměti, ale stejně jako nor­mální load musí na­čí­tat celé cache line. Může tak skrýt la­tence, ale když je hlav­ním ne­pří­te­lem pa­mě­ťová pro­pust­nost, nemá žádný po­zi­tivní dopad.

Toto zjiš­tění jen dále po­tvr­zuje výhody sloup­co­vých da­ta­bází: I když se všechna data na­chá­zíz­cela v paměti, je čtení po sloup­cích rych­lejší než po řád­cích. V nej­hor­ším pří­padě, kdy mě za­jí­mají všechny sloupce, bude stejně rychlé, jako čtení po řád­cích. Po­dobná si­tu­ace platí v pří­padě dis­ko­vých bloků1.

Pro­pust­nost je na­to­lik li­mi­tu­jící, že když mám struct row s 8 atri­buty

struct row {
  long a,b,c,d,e,f,g,h; // 64 bajtů
};

tak tato smyčka

for (int i = 0; i < N; i++) {
  sums[0] += rows[i].a;
}

běží stejně rychle jako tato

for (int i = 0; i < N; i++) {
  sums[0] += rows[i].a;
  sums[1] += rows[i].b;
  sums[2] += rows[i].c;
  sums[3] += rows[i].d;
  sums[4] += rows[i].e;
  sums[5] += rows[i].f;
  sums[6] += rows[i].g;
  sums[7] += rows[i].h;
}

Při 10GB/s nová cache-line dorazí kaž­dých 6.4 ns, což při 3 GHz od­po­vídá skoro 20 taktům a to stačí na vy­ko­nání všech movů, addů a in­strukcí smyčky s ro­zum­ným ILP.6

Mo­ne­tDB je na tom ještě hůř, pro­tože v jednom oka­mžiku zpra­co­vává jeden ope­rá­tor. Musí tedy číst jeden nebo více sloupců a vý­sledná data, která budou po­u­žita v dal­ších ope­rá­to­rech, za­pi­so­vat do paměti. A k tomu si je nutné při­po­čí­tat fakt, že ně­které sloupce můžou být zpra­co­vá­vány ně­ko­lika růz­nými ope­rá­tory. Ve vý­sledku je tedy Monet pro­pust­ností li­mi­to­ván mnohem více.

Lo­gic­kým ře­še­ním (jak to dělají ně­které no­vější a ra­fi­no­va­nější, viz) je roz­lá­mat slou­pec na menší bloky, které se vejdou do nějaké úrovně cache (L1 nebo L2) a pro­vést všechny ope­race na nich a pak se po­su­nout na další blok. Jde tedy o jakýsi hybrid mezi zpra­co­vá­vá­ním po celých řád­cích a po celých sloup­cích. Když se do­časné vý­sledky vejdou do pro­ce­so­ro­vých cache, není je třeba stre­a­mo­vat do hlavní paměti a pro­pust­nost paměti pře­stane před­sta­vo­vat takový pro­blém. CPU dokáže z cache tahat data mnohem větší rych­lostí. V pří­padě Haswellu to je 64 bajtů každý takt – tedy něco jako 192 GB/s pro každé jádro. A tady přijde ke slovu rychlý kód, SIMD in­strukce a mikro-op­ti­ma­li­zace, nebo jen jed­no­du­ché gcc -O3 -mavx2 -funroll-loops.

S tímhle vším na mysli jsem v jednom ne­stře­že­ném oka­mžiku zkusmo napsal Di­let­tan­teDB – pro­gram, který dotazy na ně­ja­kou hy­po­te­tic­kou sloup­co­vou da­ta­bázi pře­loží do ja­vov­ského by­te­kódu. Vý­sled­kem je jed­no­du­chá smyčka, ktera v jedné ite­raci pro­letí da­ta­bázi, čte data plnou rych­lostí 10GB/s a spo­čítá všechny po­ža­do­vané agre­gace. Na­jed­nou ne­vy­hod­no­cuje jeden ope­rá­tor, ale všechny.


Dále k tématu:


  1. Tady se sluší krátce zmínit o tak­zva­ných cache-ob­li­vi­ous al­go­rit­mech, které berou v potaz, že data data jsou pří­stupná jen v blo­cích vět­ších než jedno pro­ce­so­rové slovo, a cho­vají se op­ti­málně, i když ne­znají ve­li­kost těchto bloků. Viz např. tohle nebo tohle nebo toto nebo to­hleto.
  2. Jak se uka­zuje, tak soft­wa­rový pre­fetch často nemá žádný po­zi­tivní dopad (ale ani ne­u­blíží), pro­tože hard­wa­rový pre­fetch dělá svoji práci velice dobře.
  3. Pro­gram ne­u­žije celou pře­no­so­vou ka­pa­citu obou modulů nej­spíš kvůli tomu, jak je fy­zická paměť ma­po­vána na jed­not­livé moduly. Hlavní paměť po­u­žívá high-order in­ter­lea­ving, kdy je fy­zická paměť roz­dě­lena na velké spo­jité kusy, které jsou roz­dě­leny na pa­mě­ťové banky. Když tedy čtu sek­venčně z paměti, čtu z jed­noho pa­mě­ťo­vého modulu a dvo­ji­tou ka­pa­cita nemůžu využít. GPU na­proti tomu mají low-order in­ter­lea­ving, kdy je jedno slovo na­ma­po­vané na modul 0, další na modul 1, další na modul 2 a tak dále dokola. To se hodí pro GPU model vý­po­čtů, který je op­ti­ma­li­zo­vaný pro vysoký pa­ra­le­lis­mus a průtok. Viz první ka­pi­toly Pro­gra­m­ming on Pa­ral­lel Ma­chi­nes – GPU, Mul­ti­core, Clus­ters and More (Ak­tu­a­li­zace: Roz­lo­že­ním paměti na PC si nejsem tak jistý, viz: tento článek, který říká, že dual-chan­nel paměti se ne­tváří jako dvě 64-bitová za­ří­zení, ale jako jedno 128 bitové a to zna­mená, že tam jde o low-order in­ter­lea­ving.)
  4. Jak se uka­zuje, tak s non-tem­po­ral in­struk­cemi to není tak jed­no­du­ché a v tomto pří­padě vůbec ne­musejí pomoci, pro­tože stejně na­čí­tají celou cache line.
  5. Tak je na­pří­klad im­ple­men­to­ván Mo­ne­tDB. Každý ope­rá­tor (po­rov­nání, join, pod­mínka, atd) od­po­vídá jed­nomu před­kom­pi­lo­va­nému frag­mentu v C. Tím se eli­mi­nuje režie in­ter­pre­teru, který je v ty­pické da­ta­bázi volán nad každým sloup­cem.
  6. A co je nej­horší, když paměť nesíhá do­dá­vat data, v perfu se to ukáže jako oby­čejný cache-miss, bez in­di­kace, co ho způ­so­bilo.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články