Granularita kešování
Data, která se často čtou a jejichž získání trvá dlouho, se vyplatí uložit do nějaké rychlejší vyrovnávací paměti. To je jeden ze základních obratů zrychlování programu. Jaká data ale do keše uložit pohromadě?
Nálepky:
Článek vyšel na blogu Jakuba Vrány, na Zdrojáku ho přetiskujeme s autorovým souhlasem.
Vysoká granularita
V keši budeme mít samostatné záznamy pro každou jednotlivou částečku, kterou chceme zpracovat:
- Celkový počet článků.
- Seznam ID článků podle zvoleného řazení.
- Nadpis, URL, perex, datum vydání a ID autora každého článku.
- Jméno a URL autora.
- URL a rozměry perexového obrázku.
- Seznam ID skupin, do kterých je článek zařazen.
- Název a URL těchto skupin.
- Celkový počet názorů každého článku.
- Počet nových názorů každého článku.
To je spousta údajů, které musíme získávat samostatně, což bude zdržovat. Některé údaje jsou navíc závislé na dříve načtených datech, takže s jejich získáním musíme počkat, až tato data budeme mít.
Nízká granularita
Často se proto přistupuje ke snížení granularity. Uložíme:
- Celkový počet článků.
- Seznam ID článků podle zvoleného řazení.
- Všechna potřebná data o každém článku, ať už strukturovaně nebo případně rovnou jako HTML kód.
- Počet nových názorů bychom z toho asi vyjmuli, protože ten bude pro každého čtenáře jiný.
Problém tohoto přístupu spočívá v tom, že pokud se cokoliv změní (např. někdo přidá názor), tak musíme keš invalidovat, případně i kaskádově. Buď tedy musíme definovat složité invalidační závislosti nebo každému záznamu nastavit platnost a po uplynutí určité doby ho obnovit, ať už se změnil nebo ne. První přístup vede k větší komplexnosti aplikace a invalidaci velkých částí keše třeba i při malé změně. Druhý přístup způsobuje zobrazování zastaralých dat a zbytečné obnovování keše, i když se data nezměnila.
Kombinovaná granularita
Oba přístupy lze zkombinovat:
- Když dojde k zneplatnění keše s nízkou granularitou, tak stále platná data získáme z keše s vysokou granularitou.
Zásadní nevýhoda tohoto přístupu spočívá v tom, že se spousta dat ukládá duplicitně.
Co si vybrat
Já jsem dříve často jako jedinou možnost zrychlení aplikace viděl snižování granularity – čím víc toho budeme ukládat a načítat pohromadě, tím to přece bude rychlejší! Náročnost invalidace keše a s tím spojená větší komplexnost aplikace ale může tuto snahu zcela zhatit. Navíc můžeme dospět k tomu, že data do keše budeme ukládat jen proto, abychom je vzápětí smazali a uložili znovu. Keš tedy paradoxně může celou aplikaci zpomalit.
Nyní se proto zásadně kloním ke kešování s vysokou granularitou. Aby mohlo dobře fungovat, je potřeba splnit tři podmínky:
- Data získávat pokud možno v atomických celcích. Vyhnout se tedy např. spojování tabulek. S tím pomáhá NotORM.
- Dotazy do keše dávkovat a provádět je ve velkých blocích. V příkladu tedy např. informace o autorovi, seznamu skupin, perexovém obrázku a počtu názorů získat během jediné komunikace s keší pro všechny tyto údaje ze všech zobrazených článků najednou. S tím pomáhá NotORM 2.
- Každý požadavek musí proběhnout v konstantním čase, i logaritmický čas (k vidění např. u stromových indexů) toto řešení diskvalifikuje. To splňuje např. Memcache nebo MEMORY tabulky v MySQL.
Ve výsledku získáme aplikaci, která je jednoduchá (neobsahuje žádné invalidační závislosti), bezchybná (nezobrazuje zastaralá data), šetrná ke zdrojům (data ukládá jen jednou) a přitom výkonnostně obvykle optimální.
Srovnání: Basecamp Next používá kombinovanou granularitu – stejná data ukládá do keše třeba čtyřikrát a např. při přidání komentáře musí všechny tyto čtyři kopie zahodit a sestavit a uložit je znovu.
Přijďte si o tomto tématu popovídat na školení Výkonnost webových aplikací.
Fajn čánok, princíp NotORM sa mi veľmi páči. Mysliš, že keby bol NotORM postavený nad Zend_Db bol by pomaľší?
Cokoli postavené nad Zend_Db (minimálně co se MySQL týče) bude výrazně pomalejší než přímé provádění dotazů z principu fungování Zend_Db – každý dotaz transformuje na statement … který okamžitě po provedení zruší – fakticky tedy 3 požadavky na SQL server na provedení 1 query + na statementy MySQL neaplikuje query cache … tedy extrémní případ mnoha složitějších SQL dotazů, které by za normálních okolností vyřídila query cache, může Zendu trvat třeba 1000x déle …
Pokud se Zend_Db použije s PDO_MySQL, tak by měl jít tento neduh vyřešit pomocí
PDO::MYSQL_ATTR_DIRECT_QUERY.MySQL podporuje query cache u prepared statements od verze 5.1.17.
Uvádět tento článek na Twitteru větou ve smyslu „jak by ti idioti mohli zrychlit Basecamp Next čtyřikrát, kdyby si odě mě nechali poradit“, to už je fakt vrchol.
Přitom řada tvrzení v článku je špatně na tolika frontách! Ale napsal to pan Vrána a proto to je prostě tak!
Opravdu jste chtěl použít slovo atrofovat (ubývat, zmenšovat)?
hoops.. nikolivěk. byl jsem rozčilen :)
A neni preci jen dulezitejsi co se tam pise, nez kdo to pise? A nebylo by tedy lepsi, i pro nas nezkusene, v diskuzi uvest, co je v clanku spatne, pripadne pokud je clanek spatne jako celek napsat jiny, lepsi, ktery by poslouzil jako oponentsk?. :-)
Tak přesně pan Vrána článek uvedl takto: „Jak by mohl být Basecamp Next ještě čtyřikrát rychlejší, než je.“
Přitom autoři Basecamp Next (37signals) nejsou žádní začátečníci, stojí za vývojem frameworku Ruby on Rails a nějaké zkušenosti očividně mají. Dle svých vlastních slov se v nové verzi zaměřili především na rychlost.
Položme si otázku – opravdu by nechali jen tak bez povšimnutí možnost čtyřnásobného zrychlení?
Pan Vrána je ale geniální a tak si vybral vhodnou cache bez benchmarku jen na základě dojmologie. Ovšem možná že to je dobře, protože jeho přístup k benchmarkům je více než originální – viz zde http://php.vrana.cz/notorm-2.php na konci.
Ale k samotnemu tematu clanku – tedy zda vubec a pripadne jak, pomoci jakych nastroju apod. pouzivat cache,k tomu nam tu nic nenapisete? Ja opravdu nectu ty clanky proto, abych vedel kdo z autoru je chytrejsi nez nekdo jiny, ale abych se naucil neco co neznam, abych se necemu priucil. Tak mi prosim odpuste, ze je mi jedno, jak bylo nazvane nejake tweetnuti (nebo jak se tomu dnes rika ), ale spis me zajima, jestli a v jakych pripadech jsou jeho zavery spravne, pripadne nespravne.
Podle mě – čím větší balík dat leží v cache, tím lépe. Ideálně celá stránka. Tedy pravý opak.
Tvrzení z článku v odstavci „Nízká granularita“ považuji za vyloženě nesmyslné.
Nástroje: memcache či obdoba + něco na asynchronní zpracování dlouhých akcí – např. Resque. To je asi tak dnešní minimum.
Tak přesně tohle „podle mě“ se článek snažil nahlodat. Je to totiž velmi častá představa.
Co získáme nízkou granularitou? Především málo komunikací s keší. Při využití odložené komunikace s keší ale můžeme zůstat v řádu jednotek i u vysoké granularity (uvědomit si tento fakt je klíčové pro pochopení celého článku), což se na výsledné rychlosti stránky projeví jen nepatrně.
Co naopak s nízkou granularitou musíme obětovat? Rychlý zápis, resp. rychlé čtení po jakémkoliv zápisu. Pokud se cokoliv v tom balíku dat změní, musíme ho skládat celý znovu. To se snaží řešit kombinovaná granularita, ovšem za cenu obrovského plýtvání (všechna data uložená třeba čtyřikrát, takže buď se nám toho do keše vejde čtyřikrát méně, nebo si musíme koupit čtyřikrát více serverů). V obou případech navíc vzroste i komplexnost aplikace, kdy musíme definovat invalidační závislosti. S vysokou granularitou nic takového nemusíme řešit.
Pokud se data v keši prakticky nemění, bývá nízká granularita skutečně nejlepší. Pokud se ale mění, je lepší zvolit něco jiného.
Ad „Pokud se data v keši prakticky nemění, bývá nízká granularita skutečně nejlepší.“
To přece záleží na tom, jak pracné je následné zpracování těch „nízko granulovaných dat“ a nelze to říct takhle obecně.
Např. když budeš ta data z databáze validovat, transformovat a třeba prohánět přes Markdown*, tak můj skromný odhad je ten, že následné zpracování trvá déle, než vytažení dat z databáze – tudíž, když už používat mezipaměť, tak na vyšší úrovni (těch zpracovaných/zkontrolovaných výstupů, ne těch surových dat, která vylezla z DB).
*) ono někdy stačí použít nějaký ne zrovna efektivní šablonovací nástroj a bude to znát a bude mít smysl si ukládat jeho výstupy do mezipaměti – ani nemusíme nic transformovat nebo markdownovat.
Nízká granularita znamená, že toho ukládáme co nejvíc pohromadě, v malém počtu velkých „granulí“. Takže tvé myšlenky jsou zcela v souladu s mým výrokem.
Všiml jsem si toho až po odeslání (větu jsem si přečetl špatně ovlivněn tím, jak tu propaguješ vysokou granularitu).
Nicméně obsah mého sdělení zůstává stejný – ty píšeš:
„Nyní se proto zásadně kloním ke kešování s vysokou granularitou.“
a s tím právě nesouhlasím, resp. nemůžu říct, že bych se k tomu „zásadně klonil“. Vtip je v tom, že obecně rozhodnout tuto otázku nejde a záleží na tom, kolik dá práce vytažení dat z databáze a kolik páce dá jejich následné zpracování.
BTW: nemáš po ruce nějaký test/měření, který by srovnával 1) aplikaci, která přistupuje přímo k dobře nastavené databázi 2) s toutéž aplikací, která by si vysoce granulovaná data kopírovala z databáze do cache a sama si ošetřovala aktualizace cache (např. po přidání článku/komentáře)?
Granularita nesouvisí s tím, v jakém tvaru data do keše uložím, ale kolik jich tam uložím najednou. Takže pokud data vyžadují nějaké časově náročné zpracování, tak do keše uložím samozřejmě až tu zpracovanou verzi. Ale pořád si můžu vybrat, jestli je tam uložím samostatně (např. jen tělo článku prohnané Markdownem) nebo pohromadě s ostatními daty (např. s nadpisem článku, který Markdownem neproháním, nebo s počtem názorů onoho článku). Samostatné ukládání (vysoká granularita) má tu výhodu, že při invalidaci (např. aktualizací Markdownu) nepřijdu o ostatní data.
Test/měření je potřeba dělat pro konkrétní aplikaci. Např. Facebook by bez kešování ve vysoké granularitě byl o několik řádů pomalejší.
Jen u hodně jednoduchých aplikací to funguje tak, že by údaj ze sloupečku tabulky odpovídal 1:1 nějakému kousku výstupu a nesouvisel s ničím jiným. Spíš to bude tak, že čím víc zpracovaná data (tzn. dál od databáze a blíž uživateli), tím víc atributů bylo použito – tzn. výstup je nějakou agregací a poskládáním/přeskládáním původních dat, ne jen vyplivnutí databázové tabulky na stránku formou HTML tabulky nebo třeba seznamu.
Ne, přesně takhle jsem článek neuvedl. Uvedl jsem ho takto: „Jak by mohl být Basecamp Next ještě čtyřikrát rychlejší, než je (výrok poněkud bulvarizován)“. Ten dovětek je velmi důležitý, protože říká, že výrok je záměrně přehnaný, až vlastně skoro nesmyslný, jak už to tak u bulváru bývá. Ale to člověku s nezatemněnou myslí není třeba vysvětlovat.
V článku nikde neříkám, co jsem si „vybral“. Napsal jsem, ke kterému řešení se kloním, ale u každé aplikace samozřejmě míru této náklonnosti uzpůsobím té konkrétní aplikaci. Pokud je aplikace jednoduchá, tak ani žádné kešování potřebovat nemusí. Pokud je téměř read-only (např. obsah vytváří jen omezený počet uživatelů), tak pro ni může být nejlepší nízká granularita. Nicméně pro Basecamp Next ani jedno z toho neplatí a stojím si za tím, že by na přechodu na vysokou granularitu mohli vydělat.
Článek se především snažil ukázat, že se není potřeba uchylovat k nízké nebo kombinované granularitě (které mají své problémy) a že specifickým návrhem aplikace lze maximum vytěžit i z vysoké granularity. To se mu ve vašem případě zdá se nepovedlo, což mě mrzí.
Pořád je to jen dojem vs. jiný dojem. Podloženo pouze silnými slovy.
Můj dojem zase je, že ve znalostním víceboji vás proti 37signals by vyhráli oni. Takže když o nich napíšete, že něco mají vymyšlené neefektivně, opravdu zpozorním. A taky nevěřím.
Nejde o dojem nebo jiný dojem. Jde o algoritmus nebo jiný algoritmus. A nejde o věřím nebo nevěřím, ale o pochopím nebo nepochopím.
Navrhnout aplikaci tak, aby mohla efektivně pracovat i s vysokou granularitou kešování, dá trochu práce a chce to trochu jiný způsob programování, např. s využitím anonymních funkcí jako v NotORM 2 nebo operátoru
yieldv HipHop for PHP.Takže klidně může jít i o racionální rozhodnutí – pořídíme si čtyřikrát víc kešovacích serverů, ale program budeme moc psát hezky konvenčně odshora dolů, bez nějakého odloženého načítání dat.
Dovoluji si podotknout, že 37signals mají všechno v Ruby a tam jsou anonymní funkce a operátor yield tak nějak od začátku :)
Ano, já vím. Ale ono nejde jen o to, jestli mám k dispozici odpovídající vyjadřovací prostředky (celá myšlenka se dá ostatně implementovat i bez anonymních funkcí a
yield, jen je kód ještě neobvyklejší, než na co je většina lidí zvyklá). Jde i o to, jestli tomu chci přizpůsobit architekturu aplikace, která pak může být pro někoho třeba hůř pochopitelná.Takže proto jsem psal, že může jít o racionální rozhodnutí – utratíme sice čtyřikrát víc za kešovací servery, ale budeme mít standardní kód prováděný odshora dolů, na který jsou všichni zvyklí a který všichni chápou.
Řekněme, jen tak bokem, že kluci v ROR, jsou pašáci, takoví malí egoisti:
http://zdrojak.root.cz/clanky/aktualne-tak-nam-hackli-github/
Mohl byste prosím vyjmenovat tato tvrzení a vysvětlit, proč jsou podle vás špatná?
Nedává mi matematicky moc smysl, jak může mít kombinovaná granularita horší výsledky než vysoká. Sice se občas zahodí nějaká cache, ale taková, která při vysoké granularitě vůbec neexistovala. Vychází mi to tedy tak, že kombinovaná granularita kombinuje výhody obou, jen je paměťově náročnější.
Jde o to, jak časté je to „občas“. Data v keši mají smysl jenom tehdy, když je do ní jednou pomalu zapíšu a pak z ní mnohokrát rychle přečtu. Pokud se data mění často, tak je do keše zapisuji zbytečně, protože než je stihnu načíst, tak přestanou být platná a musím je tam zapsat znovu – výsledkem je, že aplikace je s keší pomalejší než bez keše, protože dělá přesně tu stejnou práci, jen navíc data soustavně zapisuje do keše a zase je z ní maže.
Samozřejmě záleží na konkrétní aplikaci a na konkrétním úložišti, jaký poměr se ještě vyplatí (např. na 1 zápis průměrně alespoň 3 přečtení), ale myšlenka je snad jasná.
Jak už jsem psal, tak to „jen paměťově náročnější“ znamená buď to, že utratím např. čtyřikrát víc za servery, nebo se mi do keše vejde čtyřikrát míň dat, takže třeba starší záznamy budu muset pomalu vytahovat z primárního úložiště.
Myslím, že Basecamp netrpí tak častými změnami, aby se mu nevyplatilo cachovat. Já v něm často hledám informace, kde co kdo napsal, což jsou jen čtecí požadavky. Facebook na tom asi bude o dost hůř, tam pořád někdo něco komentuje nebo lajkuje.
Navíc pokud si v BC zacachují třeba výpis jednoho komentáře, tak už to asi nemusí invalidovat nikdy – jeho html se nemění. Nebo počet diskuzí v projektu asi neni taky tak stěžejní číslo, aby se to muselo invalidovat při každé změně.
Jeden z problémů kombinované granularity je v tom, že i data, která se vůbec nemění, se musí neustále znovu a znovu zapisovat do vyšších celků, které jsou invalidované změnou jejich jiné části.
Hezké dopoledne,
přijde mi, že od pragmatických záležitostí jste se v obhajobě toho či onoho názoru dostali do tak obecné a teoretické roviny, že se naprosto vytratilo to, co se článek snaží řešit.
Celé je to o tom, že když se řeší jakýkoliv projekt, vychází se z provozních požadavků daného řešení a terpve až jsou známé tyto požadavky, může se řešit otázka, jestli cache, a pokud ano, pak jaké řešení je to správné. Řešit, jestli se něco provede o 0.005s rychleji při návštěvnosti 1000 lidí denně (= 5s/den) je plýtvání časem. Naopak, pokud se jedná o zrychlení 0.02 při návštěvnosti 5000 lidí za hodinu (= 100s/hodina), pak už stojí za to o tom nejen přemýšlet.
Nejde o chyby autoru Ruby, ani není řečeno, že nějaké udělali, jde o návrh architektury s ohledem na výkonnost.
Pokud by článek obsahoval v úvodu počáteční přepoklady či podmínky a malý příklad, na kterém se ukazuje smysluplnost, tak by tyhle empty diskuze s null přínosem !isset.
Samozřejmě, na totéž upozorňuji i v předchozím názoru. I v perexu je jasně uvedeno, že kešování se vyplatí u dat, která se často čtou a jejichž získání trvá dlouho.
Článek se především snaží ukázat, že nízká a kombinovaná granularita mají své problémy a vedou ke složitější aplikaci, u kombinované granularity spojené navíc s plýtváním. Pokud by se nám podařilo vyřešit problémy vysoké granularity, tak můžeme zůstat u ní, i když podle obecného přesvědčení musí být nutně pomalejší než ostatní přístupy. Článek vysvětluje, že tomu tak být nemusí, a ukazuje, jak na to.
Samozřejmě je tedy řešení potřeba zvolit na základě aplikace. Aplikace, které hodně čtou a skoro nikdy nezapisují, můžou klidně použít nízkou granularitu. Ty, které mají celkově málo dat a moc nezapisují, můžou použít kombinovanou. Ostatní aplikace můžou s odpovídajícím návrhem aplikace použít vysokou granularitu a vydělat na tom.
Každý požadavek musí proběhnout v konstantním čase, i logaritmický čas (k vidění např. u stromových indexů) toto řešení diskvalifikuje. To splňuje např. Memcache nebo MEMORY tabulky v MySQL.
Tohle nechapu vite vubec jaky zaklad ma ten logaritmus? Jsou to radove stovky. Hloubka indexu je v realu „konstantni“ a pohybuje se mezi 3-5.
Díky za doplnění, to jsem skutečně nevěděl. Mohl byste odkázat na nějakou technickou dokumentaci, případně zdrojáky (třeba MySQL), kde se to popisuje?
Nicméně na situaci to mnoho nemění. Pokud se pro nalezení hodnoty v uzlu používá binární vyhledávání, tak v každém patře spotřebuji O(log2M). Celkový čas tedy bude O(logMN * log2M) = O(log2N). Pro rovnoměrně rozdělená data by šel použít chytřejší algoritmus, ale nejhorší případ zůstane obávám se tento. Takže přestože je hloubka stromu v reálu „konstantní“, ještě to vůbec neznamená, že prvek bude také nalezen v „konstantním“ čase.