SIEVE: algoritmus pro kešování lepší než LRU?

Rekurzivní DNS servery jsou pak v podstatě jen velké keše obalené DNS protokolem. Nicméně pro kešování nikdy nemáme k dispozici neomezenou paměť, ať už se jedná o čistě paměťovou keš, nebo jsou dočasná data uložena na pevném disku. S omezenou pamětí je spojeno i zásadní rozhodování: co si ponechat a co zahodit.

V takovou chvíli přicházejí na řadu cache-eviction algoritmy. Jejich úkolem je zachovat taková data, která se nejspíše znovu použijí, a zahodit ta, která nebudou v nejbližší době zapotřebí.

Cache-eviction algoritmy

Nejprve si pojďme ukázat nejběžnější cache-eviction algoritmy. Na tomto místě je zapotřebí zmínit, že důležitou vlastností je jejich jednoduchost. Komplexní algoritmy mohou mít sice lepší výkon, ale v případě podivného chování je daleko obtížnější jejich diagnostika.

Jelikož se tyto algoritmy většinou nachází v takzvané hot-path cestě (tj. místě, které je kritické na výkon), tak složitější algoritmy více zatěžují CPU. Může se tak stát, že sice dosáhneme lepšího poměru cache-hit/cache-miss, ale výsledný výkon celku bude menší.

Do přehledu jsem zahrnul jen základní výčet, podrobnější informace lze najít např. ve článku na Wikipedii: Cache replacement policies.

Béládyho algoritmus

Béládyho algoritmus je čistě teoretický koncept, který také můžeme pojmenovat jako jasnozřivý algoritmus. Jedná se o algoritmus, který z keše vyhazuje takové položky, které budou zapotřebí za nejdelší dobu. Ale protože nemáme věšteckou kouli, používá se tento koncept pouze při porovnávání efektivity algoritmů, které skutečně lze implementovat.

Náhodný výběr

Tento algoritmus vybírá náhodným způsobem z mezipaměti položky, které budou vyřazeny. Na první pohled tato strategie nevypadá jako vhodná, ale ukazuje se, že pro některé zátěže to nemusí být nutně špatná volba.

First In First Out (FIFO) a Last In First Out (LIFO)

Tyto dva jednoduché algoritmy, založené na spojovém seznamu, vyhazují nediskriminačně položky čistě na základě toho, kdy byly zařazeny do seznamu. FIFO vyhazuje položky, které vstoupily do seznamu jako první. Funguje tedy jako fronta (queue). LIFO pak vyhazuje položky, které do fronty vstoupily jako poslední. Chová se tedy jako zásobník (stack).

Least Recently Used (LRU)

Jak již název napovídá, tato cache-eviction politika vyhazuje z keše takové položky, které byly použity nejméně (least) nedávno (recent). Jednoduchý LRU algoritmus se implementuje tak, že dokud je v paměti místo, přidávají se nové položky (cache-miss) na začátek seznamu, zatímco stávající položky (cache-hit) se na začátek seznamu přesunují při přístupu na ně. Ve chvíli, kdy dojde místo na ukládání nových položek, začnou se položky odstraňovat z konce seznamu. LRU je ve skutečnosti celá rodina algoritmů, které vždy nějakým způsobem vylepšují původní jednoduchý LRU algoritmus.

Least Frequently Used (LFU)

Další rodina algoritmů LFU je založena na počítání četnosti použití položek v keši. Po naplnění paměti algoritmus z keše vyhazuje takové položky, které byly použity nejméně často. Tento algoritmus je pro některé druhy zátěže vhodnější, ale je složitější na implementaci.

Design SIEVE

SIEVE je nový cache-eviction algoritmus, který vyniká svoji efektivitou a jednoduchostí. Pojďme si jej nyní představit. Implementace SIEVE potřebuje jednu frontu (např. spojový seznam) a jeden ukazatel, kterému říkáme ruka (hand). Fronta zachovává pořadí vložení položek, kdy každá položka ve frontě musí obsahovat jeden bit pro označení stavu, zda byl či nebyl navštíven. Ruka ukazuje na dalšího kandidáta pro vyřazení z fronty a pohybuje se frontou od konce k začátku. Pokud je ruka na začátku fronty, přesune se v případě potřeby zpátky na její konec.

Cache-hit. Pokud položka ve frontě již existuje, označíme ji jen jako navštívenou a s frontou nijak jinak nemanipulujeme. Pokud je položka již označena jako navštívená, nedochází k žádné změně.

Cache-miss. Jak přicházejí nové položky (cache-miss), tak jej SIEVE algoritmus vždy zařazuje na začátek fronty. Ve chvíli, kdy ve frontě již není místo, algoritmus se podívá na položku, na kterou ukazuje ruka. Pokud je položka označena jako navštívená, je tento příznak odebrán a ruka se přesunuje na předchozí položku – jak jsme si řekli již výše, ruka se pohybuje směrem k začátku fronty. Toto se opakuje až do chvíle, dokud ruka neukazuje na položku, která není označena jako navštívená. Pak dochází k odstranění této nenavštívené položky z fronty a tím vznikne místo na uložení nové položky do keše. I když se většina odstraněných položek nachází někde uprostřed fronty, nové položky jsou vždy ukládány na začátek fronty.

Celý algoritmus je pěkně znázorněn na následujícím obrázku (převzato ze stránek projektu):

Líná povýšení a rychlé sesazení

Povýšení (promotion) a sesazení (demotion) jsou dva základní principy pro řazení položek v keši. Ukazuje se, že líné povýšení a rychlé sesazení jsou dvě důležité vlastnosti dobrých cache-eviction algoritmů. Princip líného povýšení odkazuje na strategii povýšení položek, které mají být zachovány až do chvíle, kdy je zapotřebí uvolnit místo v keši. Cílem je zachovávat položky s minimálním úsilím. Líné povýšení zvyšuje propustnost díky menší potřebě výpočetního výkonu. Zároveň dochází ke zvýšení efektivity díky tomu, že v době zahazování nepotřebných položek máme o všech položkách a jejich využití více informací.

Rychlé sesazení pracuje tak, že odstraňuje položky velmi rychle po tom, co byly do keše vloženy. Výše odkazovaný výzkum ukazuje, že rychlé sesazení je vhodné i pro webové keše. SIEVE je v tuto chvíli nejjednodušší algoritmus, který implementuje oba dva principy.

Malá odolnost proti procházení celé keše

Abychom na SIEVE nepěli jenom chválu jako oni přísloveční žľuťoučcí koně, tak musím zmínit jednu nevýhodu. SIEVE algoritmus není z principu odolný proti sekvenčním průchodům (scan), což ho činí nevhodným k nasazení do míst, kde je toto častá operace. Přístupy vygenerované sekvenčním průchodem se proplétají dohromady s populárními objekty, a výkon SIEVE je v takovém případě horší než při použití LRU.

Marc Brooker na svém blogu uvádí pár nápadů, jak se s tímto při použítí SIEVE vyrovnat – použití malého čítače místo jednoduchého příznaku by umožnilo SIEVE použít v nasazeních, kde se často prochází celá keš.

SIEVE v BIND 9 – Implementace a výkon

SIEVE je velmi jednoduchý algoritmus na implementaci. Jeho prvotní implementace pro BIND 9 zabrala velmi krátký čas. Ve výsledku je kód keše po odstranění stávajících cache-eviction mechanismů v BIND 9 a jejich nahrazení za SIEVE celkem chudší o více než 300 řádků.

Základní implementace LRU přesouvá při cache-hit položky vždy na konec seznamu. U více vláknových programů to znamená, že při každém cache-hit, které by mělo být převážně čtení, se musí celá datová struktura zamknout, což negativně ovlivňuje výkon. V praxi se běžně používají dvě techniky, a BIND 9 obě dvě z nich implementoval – zpomalená aktualizace a segmentace LRU. Není to žádná věda.

Zpomalená aktualizace znamená, že při přesunu položky na začátek seznamu si poznamenáme čas poslední aktualizace a následně v definovaném časovém okně takovou položku při dalších přístupech již neaktualizujeme. Segmentace LRU znamená, že máme více LRU seznamů, kde každá položka má na základě svých charakteristik pevně přiřazený seznam. Např. v případě DNS keše se položky přiřazují k jednotlivým seznamům na základě doménového jména, pod kterým jsou v keši uloženy.

Tento přístup funguje hůře v případě hierarchických dat jako je DNS strom, kde se přistupuje častěji na DNS jména položená výše v DNS stromu. Nicméně v kombinaci s odloženou aktualizací funguje uspokojivě.

Výše jsme si říkali, že SIEVE algoritmus v případě nalezení existující položky (cache-hit) pouze označí takovou položku jako navštívenou. To má jeden zásadní pozitivní dopad na výkon – v případně cache-hit se nemusí zamykat celý seznam, pouze je zapotřebí zajistit konzistentní přístup k výše uvedenému příznaku.

Jak to pak vypadá v praxi? Připravil jsem dva testy BIND 9 ve funkci resolveru, které probíhají nad reálnými daty poskytnutými telekomunikačním operátorem. V prvním testu je paměť resolveru ( max-cache-size) omezena na 128 MB, což je vcelku malá hodnota, keš se proto rychle zaplní. Následující obrázek zobrazuje latenci odpovědí. Podobné obrázky byly popsány předchozím článku o BIND 9, ale připomeňme si, že se jedná o logaritmický histogram percentilů. Zjednodušeně řečeno chceme, aby se linie měření tlačila co nejvíce doleva a co nejvíce dolů, což znamená, že server odpověděl co nerychleji na co nejvíce odpovědí.

První obrázek zobrazuje latenci v první polovině testu, kdy se začíná s prázdnou keší. Druhý obrázek zobrazuje druhou polovinu testu, kde je keš už víceméně naplněná. Jde patrné, že zejména v případě naplněné keše, se SIEVE chová mnohem lépe a server je schopen odpovědět více klientům.

Na dalších dvou grafech vidíme využití paměti a procesoru v čase. Myslím si, že je zřejmé, že implementace SIEVE algoritmu přinesla větší stabilitu ve využití paměti v případě nepříznivých podmínek a menší zátěž na CPU.

Současné verze BIND 9 používají dva mechanismy čištění paměti. Jeden je založen na LRU a použije se pouze v případě, že došlo místo v paměti. Druhý mechanismus je více oportunistický a čistí z keše položky, kterým vypršelo TTL (ve smyslu DNS TTL). Jak to tedy vypadá, pokud máme paměti pro keš dostatek a nahradíme oba dva tyto mechanismy pouze SIEVE algoritmem? Abychom parafrázovali jedno peprné české úsloví: „Myslet znamená… nic nevědět“.

Pojďme se opět vrátit k měření nad reálnými daty. Budeme porovnávat stávající a novou implementaci s maximální velikostí keše nastavenou na 30 GB, která nám během dvaceti minut měření nepřetekla. Obrázek níže ukazuje, že dochází k mírnému zlepšení výkonu celého DNS resolveru i ve chvíli, kdy je keš už z velké části naplněná, tedy v druhé polovině testu:

Ve využití CPU pak nedochází k žádnému pozorovatelnému rozdílu. Ve využití paměti lze ale pozorovat, že kvůli odstranění čištění keše založeného na TTL, dochází k nárůstu spotřebované paměti. To je ve své podstatě v pořádku, protože cílem keše je ukládat data, nikoli je preventivně zahazovat.

Implementace

V případě zájmu o implementaci SIEVE do vlastních systémů, se podívejte na řešení v Pythonu, které jeho autorka uvádí na blogu projektu. Pro případné využití v C se můžete podívat na Merge Request, který algoritmus implementuje pro BIND 9. Na stránkách projektu jsou uvedeny i další projekty a knihovny, které tento nový algoritmus implementují.

(Autorem obrázků je Ondřej Surý).