Pár poznámek k pár poznámkám o sloupcových databázích
Teorie je jednoduchá: Sloupcové databáze jsou takové, které ukládají data po sloupcích místo po řádcích, jak je v databázovém světě běžné.
To má několik zásadních výhod, které jsou v určitých situacích k nezaplacení. Když potřebuji přistoupit jen k několika málo sloupcům, načtu pouze jejich data a nemusím se obtěžovat s jinými položkami ze stejného řádku. V řádkových databázích je vždycky nutné načíst celý řádek, protože data se z disků načítají po blocích, které obsahují mnoho řádků najednou. Nemůžu si vynutit, aby mi disk poskytl jen bajty z těch pár sloupců, které mě zajímají. Dostanu všechno nebo nic. Naproti tomu ve sloupcové DB je každý sloupec uložen jako souvislý region dat. Jeden diskový blok tedy obsahuje jen a pouze data jednoho sloupce. V nejjednodušší podobě jde o velké pole (jehož prvky mají často fixní délku) pro každý sloupec (jako v případě MonetDB) nebo o sérii kratších segmentů (jako v X100).
Takovéto uspořádání dat se hodí pro OLAP, tedy když mě místo jednotlivých
záznamů zajímají agregace jednoho nebo několika málo sloupců (např. tabulka
jich má 50, ale v dotazu se dva vyskytují v podmínce a z několika dalších se
počítají průměry). Protože jde koncepčně o pole, nalezení odpovídajících
položek v různých sloupcích je triviální: jde o pouhý index * velikost položky
a dotaz se dá přeložit do série jednoduchých a velice efektivních smyček.5
Sloupcové databáze jsou krásné (jak je vidět v The Design and Implementation of Modern Column-Oriented Database Systems), ale přesto o nich dneska nechci psát.
Nedávno jsem si přečetl článek Několik poznámek ke sloupcovým databázím, který ve mě zanechal příjemný hřejivý pocit, hlavně proto, že se zmiňoval o hardwaru, SIMD instrukcích a efektivitě práce s in-memory daty. Tam někde mě napadlo vyzkoušet, jak rychle taková teoretická in-memory databáze může běžet. Když z rovnice vypadnou všechny rotující disky, SSD nebo síťové karty, záleží jen na pamětech a procesoru. Z komplikovaného systému se stane něco triviálního, co je možné prozkoumat a pochopit. Například jaký vliv má komprese, SIMD operace, instrukce gather (která načte několik procesorových slov najedou, potenciálně paralelně), prefetch (která signalizuje procesoru, jaká data budou brzo potřeba)2 nebo non-temporal load4 ?
Ale tak daleko jsem se nedostal. Protože jak to vypadá na tom zas tak moc nezáleží, limitujícím faktorem je hlavně propustnost pamětí.
Napsal jsem triviální test, který definoval struct row
s několika osmibajtovými
položkami.
struct row { long a,b,c,d,e,f,g,h; long i,j,k,l,m,n,o,p; };
Pak jsem vytvoř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; }
Nakonec jsem jím proletěl během jedné krásné iterace.
for (int i = 0; i < 50000000; i++) { sum += rows[i].a; }
Zaznamenával jsem výsledky s různým počtem položek ve structu row
. V prvním
řádku má row
položky od a
do p
(dohromady 128 bajtů), v posledním obsahuje jen
jedinou položku (8 bajtů). Výsledky byly celkem překvapivé.
longs | bytes | time | throughput |
---|---|---|---|
16 | 128 B | 320 ms | ~ |
8 | 64 B | 227 ms | 13.1 GB/s |
4 | 32 B | 112 ms | 13.3 GB/s |
2 | 16 B | 55 ms | 13.5 GB/s |
1 | 8 B | 33 ms | 11.3 GB/s |
Jak je vidět, že i když sčítám jen hodnoty prvního atributu, rychlost klesá plus/mínus lineárně s přibývajícím počtem položek v řádku. Procesor totiž z paměti nenačítá data po 64-bitových slovech, ale po cache line, které mají 64 bajtů. Musí tedy z RAM vydolovat celých 64 bajtů, i když z nich využije jen jednu osminu a to věci značně zpomalí.
Dále je vidět, že rychlost je limitovaná propustností pamětí. V mém desktopu jsou dva 1333MHz DDR3 moduly, které by podle tabulek měly dokázat protlačit 2x10.6 GB za vteřinu. Jedno jádro běžící na plné otáčky dokáže rozpoutat takové peklo, že sežere většinu tohoto objemu. Kdybych použil všechna čtyři jádra, program by byl limitován propustností pamětí a běžel by v nejlepším případě ~2x rychleji. Hyperthreading by v tomto případě nepřinesl žádné zrychlení.
Z toho vyplývá, že v této situaci komplikované gather
/prefetch
instrukce
nemají moc velký význam. Program ve všech případech běží s nízkým IPC (lehce
nad 1 instrukci na takt pro velké row
structy, skoro 1.2 pro row
s jednou
položkou). gather
může načíst několik míst paměti, ale stejně jako normální
load musí načítat celé cache line. Může tak skrýt latence, ale
když je hlavním nepřítelem paměťová propustnost, nemá žádný pozitivní dopad.
Toto zjištění jen dále potvrzuje výhody sloupcových databází: I když se všechna data nacházízcela v paměti, je čtení po sloupcích rychlejší než po řádcích. V nejhorším případě, kdy mě zajímají všechny sloupce, bude stejně rychlé, jako čtení po řádcích. Podobná situace platí v případě diskových bloků1 .
Propustnost je natolik limitující, že když mám struct row s 8 atributy
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 odpovídá skoro
20 taktům a to stačí na vykonání všech mov
ů, add
ů a instrukcí smyčky s rozumným ILP.6
MonetDB je na tom ještě hůř, protože v jednom okamžiku zpracovává jeden operátor. Musí tedy číst jeden nebo více sloupců a výsledná data, která budou použita v dalších operátorech, zapisovat do paměti. A k tomu si je nutné připočítat fakt, že některé sloupce můžou být zpracovávány několika různými operátory. Ve výsledku je tedy Monet propustností limitován mnohem více.
Logickým řešením (jak to dělají některé novější a rafinovanější, viz)
je rozlámat sloupec na menší bloky, které se vejdou do nějaké úrovně cache (L1
nebo L2) a provést všechny operace na nich a pak se posunout na další blok. Jde
tedy o jakýsi hybrid mezi zpracováváním po celých řádcích a po celých
sloupcích. Když se dočasné výsledky vejdou do procesorových cache, není je
třeba streamovat do hlavní paměti a propustnost paměti přestane představovat
takový problém.
CPU dokáže z cache tahat data mnohem větší rychlostí. 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 instrukce a mikro-optimalizace,
nebo jen jednoduché gcc -O3 -mavx2 -funroll-loops
.
S tímhle vším na mysli jsem v jednom nestřeženém okamžiku zkusmo napsal DilettanteDB - program, který dotazy na nějakou hypotetickou sloupcovou databázi přeloží do javovského bytekódu. Výsledkem je jednoduchá smyčka, ktera v jedné iteraci proletí databázi, čte data plnou rychlostí 10GB/s a spočítá všechny požadované agregace. Najednou nevyhodnocuje jeden operátor, ale všechny.
Dále k tématu:
- The Design and Implementation of Modern Column-Oriented Database Systems
- Video o implementaci X100 - vylepšené verzi MonetDB, ze které se vyvinula databáze ColumnWise
- Michael Stonebraker - Everything You Learned in Your DBMS Class is Wrong
- MonetDB: Two Decades of Research in Column-oriented Database Architectures
- MonetDB/X100: Hyper-Pipelining Query Execution
- Monet - A Next-Generation DBMS Kernel For Query-Intensive Applications
- The design and implementation of modern column-oriented database systems
- Tady se sluší krátce zmínit o takzvaných cache-oblivious algoritmech, které berou v potaz, že data data jsou přístupná jen v blocích větších než jedno procesorové slovo, a chovají se optimálně, i když neznají velikost těchto bloků. Viz např. tohle nebo tohle nebo toto nebo tohleto.
- Jak se ukazuje, tak softwarový prefetch často nemá žádný pozitivní dopad (ale ani neublíží), protože hardwarový prefetch dělá svoji práci velice dobře.
- Program neužije celou přenosovou kapacitu obou modulů nejspíš kvůli tomu, jak je fyzická paměť mapována na jednotlivé moduly. Hlavní paměť používá high-order interleaving, kdy je fyzická paměť rozdělena na velké spojité kusy, které jsou rozděleny na paměťové banky. Když tedy čtu sekvenčně z paměti, čtu z jednoho paměťového modulu a dvojitou kapacita nemůžu využít. GPU naproti tomu mají low-order interleaving, kdy je jedno slovo namapované 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 optimalizovaný pro vysoký paralelismus a průtok. Viz první kapitoly Programming on Parallel Machines - GPU, Multicore, Clusters and More (Aktualizace: Rozložením paměti na PC si nejsem tak jistý, viz: tento článek, který říká, že dual-channel paměti se netváří jako dvě 64-bitová zařízení, ale jako jedno 128 bitové a to znamená, že tam jde o low-order interleaving.)
- Jak se ukazuje, tak s non-temporal instrukcemi to není tak jednoduché a v tomto případě vůbec nemusejí pomoci, protože stejně načítají celou cache line.
- Tak je například implementován MonetDB. Každý operátor (porovnání, join, podmínka, atd) odpovídá jednomu předkompilovanému fragmentu v C. Tím se eliminuje režie interpreteru, který je v typické databázi volán nad každým sloupcem.
- A co je nejhorší, když paměť nesíhá dodávat data, v
perf
u se to ukáže jako obyčejný cache-miss, bez indikace, co ho způsobilo.