Granularita kešování

Školení, která pořádám

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ě?

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 v zá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í.

Srová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í.

Jakub Vrána, Seznámení s oblastí, 24.2.2012, diskuse: 11 (nové: 0)

Diskuse

Franta:

A jaký je důvod pro to, aby mezipaměť v aplikaci byla efektivnější než mezipaměť v DBMS (a disková mezipaměť)?

IMHO tohle má smysl hlavně když se s těmi daty dělají nějaké drahé operace, zpracování (např. bych měl články v nějakém jiném jazyce než XHTML a před vypsáním bych je proháněl nějakým pomalým překladačem).

24.2.2012 12:55:55

Jakub Vrána :

Přesně takhle jsem také uvažoval – proč data ukládat do samostatné keše, když je kešuje přímo databáze (např. MySQL query cache)? Ale realita nás k tomu bohužel nutí – jednoduchý key-value in-memory storage (např. Memcache, případně APC) je prostě rychlejší než databáze, která dělá milión dalších věcí. A to i v případě, kdy používá stejné úložiště (paměť) a přístupové algoritmy se stejnou asymptotickou složitostí O(1).

Nicméně myšlenka článku se dá použít i v případě, kdy žádnou explicitní keš nepoužíváme a spolehneme se na tu implicitní: spousta malých dotazů = vysoká granularita, několik megajoinů = nízká granularita. Jen s tou kombinovanou granularitou asi moc nepochodíme, protože např. MySQL pokud vím neumí využít kešované dotazy do samostatných tabulek pro sestavení joinu.

24.2.2012 16:33:12

Franta:

Tím ale vlastně říkáš, že jsi schopný napsat lepší kód než autoři daného DBMS – což může být klidně možné, ale v takovém případě bych spíš změnil DBMS nebo pomohl zlepšit ten stávající, aby pracoval efektivněji.

Obecně ale nevidím důvod, proč by stejná operace (vytažení stejných dat na základě klíče ze stejně velké množiny) měla být na úrovni aplikace rychlejší než na úrovni databáze.

Nějakou režii má předávání dat daným protokolem – zatímco v rámci aplikace si jen sáhneš do paměti v rámci stejného procesu – ale pokud ta mezipaměť bude třeba v memcache, tak se stejně kvůli každému dotazu do cache navazuje TCP spojení (případně může být trvalé stejně jako může být trvalé k databázi) a opět je tu nějaká režie protokolu.

Dokážu to pochopit jako dočasný hack*, ale nepřijde mi to jako systémové a čisté řešení – tohle je věc, o kterou se má starat nižší vrstva a aplikace se takovým kódem nemá zamořovat. Něco jiného je mezipaměť pro nějak pracně zpracovaná data, nebo stažená po pomalé síti.

Jinak na SQL se mi líbí, že dotazem řekneš, co chceš – ale jak toho dosáhnout už neřešíš – to je úloha DBMS, vybrat nejlepší způsob – a pokud to nezvládá, je to chyba a mělo by se to řešit na úrovni DBMS** a ne tenhle problém přesouvat na úroveň aplikace.

*) něco na způsob „vybrali jsme si mizerný DBMS, navíc ho nemůžeme teď změnit a nemáme ani čas, ho vylepšovat, tak nezbývá než udělat cache v aplikaci a nějak ten problém obejít“

**) úprava datového modelu, úprava indexů, úprava konfigurace DBMS na daném stroji, optimalizace kódu DBMS.

24.2.2012 17:05:30

Jakub Vrána :

Jednoduché nástroje, které umí jen jednu věc (např. Memcache) mají tendenci být rychlé. Složité nástroje, které umí spoustu věci a mezi nimi i tuhle jednu (např. MySQL), tuto tendenci nemají. Nástroj pro řešení dané úlohy je vhodné vybrat na základě měření. Když by měření ukázalo, že třeba PostgreSQL dokáže vrátit data rychleji než Memcache, tak bych klidně pro kešování použil PostgreSQL.

Ale tvrdit „to přece nemá být proč pomalé“ a „není to systémové a čisté“ je alibismus.

Jinak kešování (podívám se do rychlého úložiště a když to nenajdu, tak to tam zkopíruji z pomalého úložiště) samozřejmě patří do abstraktní vrstvy, nebudu ho řešit u každého dotazu zvlášť. Pokud můžu už nějakou takovouhle existující vrstvu využít, tak tím lépe pro mě. Ale pokud si ji musím napsat sám, tak těch pět řádek mě nezabije.

Třeba MySQL Query Cache pracuje v nízké granularitě (ukládá výsledky celých dotazů a keš invaliduje při jakémkoliv zápisu do tabulek, které dotaz používá – třeba i do řádků, které ve výsledku vůbec nejsou), takže se do mé aplikace nemusí hodit.

24.2.2012 19:12:01

Franta:

BTW: tyto stránky jsou ukázkou, jak to nedělat :-) Po vložení předchozího příspěvku jsem kliknul na logo webu (vpravo nahoře) a na titulní stránce vidím u tohoto článku 0 komentářů, stisknu F5 a vidím 1 komentář. Rozkliknu si článek a můj komentář nikde. Opět mačkám F5 a už ho vidím.

24.2.2012 12:59:48

Jakub Vrána :

Jaký používáš prohlížeč, není to náhodou Opera? Ta kešuje tak agresivně, že ji ani poslání správných HTTP hlaviček (které tento server nastavuje podle invalidačních pravidel) nepřesvědčí o tom, aby si stránku milostivě stáhla znovu. Takže na vině nejsou stránky, ale prohlížeč nerespektující standard.

24.2.2012 16:22:52

Franta:

Opera fakt ne :-) Firefox, aktuálně ve verzi 10.0.2.

24.2.2012 16:35:45

Jakub Vrána :

V něm nic takového nepozoruji.

24.2.2012 16:36:44

Franta:

A co je ještě zajímavější: po vložení druhého komentáře jsem zopakoval stejný scénář, ale tento komentář už byl vidět hned.

24.2.2012 13:01:21

Martin:

Psát o kešování a sám to mít blbě napsané, to chce hodně odvahy :-) Přišel jsem na tuhle stránku poprvé a ukazuje to "diskuse: 9 (nové: 0)". Prohlížeč Google Chrome.

27.2.2012 05:44:13