Názory k článku SIEVE: algoritmus pro kešování lepší než LRU?
-
Mrkněte se tady: https://isc-projects.gitlab-pages.isc.org/-/bind9-shotgun-ci/-/jobs/5497673/artifacts/index.html pro verzi se SIEVE-LRU a tady: https://isc-projects.gitlab-pages.isc.org/-/bind9-shotgun-ci/-/jobs/5498355/artifacts/index.html pro verzi před SIEVE-LRU.
Jsou to grafy pro 64, 128, … 1024 MB velikosti keše. Pro představu, co to dělá s výkonem…
-
![[object Object]](https://i.iinfo.cz/sh/profile/avatar/avatar-default.gif)
> .. 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.
Pamat a cache je na pouzivanie, ale nema vyznam ukladat nepouzitelne data. DNS zaznam po vyprsani TTL by sa uz predsa nemal vracat. (edit: zase je pravda, ze pamat stoji par korun a nema zmysel to riesit, ked sme pod limitom vyuzitia)
LRU ma jednu dolezitu vlastnost - a sice ze LRU s cache velkosti 2N funguje vzdy rovnako alebo lepsie ako optimalny (Beladyho) algoritmus s cache velkosti N.
3. 4. 2025, 07:52 editováno autorem komentáře
-
Nakonec jsme do vývojové větve začlenili variantu, která TTL-based cleaning zachovává, ale jiné DNS servery (např. Unbound) žádné čištění na základě TTL nemají, a fungujou. Takže je možné, že to do budoucna ještě přehodnotíme. Jako další experiment je naplánováno nahrazení heap za skiplist, a uvidíme, jestli a jaký to bude mít dopad na výkon.
-
> kdyz se zaznam nenajde v cache, je to o dost rychlejsi, nez ho tam najit a resit ze je expirovanej.
Ne. Nesmíte si cache představovat jako knihovnici, která vám hledá knížku v papírové kartotéce…
> Ucelem cache pak rozhodne neni skladovat neplatna data.
To nikdo netvrdí. Nicméně náklady na mazání neplatných dat nejsou nulové, proto se mazání dělá pouze oportunisticky nebo až ve chvíli, kdy je to potřeba (cache-miss při plné keše).
-
ja si predstavuju cache jako batoh co si nesu na zadech a mam v nem lahvace.
kdyz mam zizen a chci plzen a najdu v batohu plzen tak je to rychla akce a muzu se napit z lahvace plzne.
kdyz mam chut na starobrno, ale nemam ho v batohu, tak musim daleko do obchodu, nakoupit a jako zalohu si ho pridat do batohu.
ale kdyz vim, ze uz jsem dlouho nedostal chut na svijany, tak je radeji z batohu vyndam a venuju mistnimu popelarovi a uz neni v cache :-) -
"Ne."
Dukaz?
1 ... select do databaze (cache neni nic jinyho)
2a ... vratim nalezenou odpoved
2b ... poslu select do externi databazevs
1 ... select do databaze (cache neni nic jinyho)
2* ... jdu overit, zda nalezeny zaznam je platny
3a ... vratim nalezenou odpoved
...Je tam zcela jeznoznacne krok navic ktery delat nemusim pokud zaridim, ze zadne neplatne zaznamy v cache nebudou, Coz se specielne u DNS da udelat naprosto vpohode.
* Navic ten krok narozdil od mazani neplatnych zaznamu musim udelat okamzite s kazdym jednim dotazem.
-
Takze konstatuji, ze neni k dispozici naprosto zadny argument. Casu na blaboleni a osobni utoky je ovsem zjevne dost.
2Marvin: Je to mnohem vic prace nez zadna prace, zaznamy z cache nemusim vyhazovat v okamzik expirace kterou maji typicky pomerne dlouhou, takze kdyz to budu delat 1x za hodinu a klidne budu aktivne vyhazovat ty, ktere konci pristi hodinu, porad to bude mnohem levnejsi, nez s kazdym dotazem overovat platnost. A klidne ty co maji pripadne ttl pod hodinu nebudu do cache davat vubec.
-
Tu důkazní nouzi máte vy, ne já. Předložil jste nějakou hypotézu, ze které jde vidět, že problematice nerozumíte. To není ani námět k diskuzi, ani osobní útok. Nemůžete po ostatních chtít, aby vaše hypotézy dokazovali nebo vyvraceli, a trávili tím čas, který má nějakou hodnotu. Podložte svou hypotézu teorií a daty, a bude možné v diskuzi pokračovat. Opakování nepravdivé hypotézy pořád dokolečka nepřináší žádnou hodnotu.
-
Filip JirsákStříbrný podporovatelbez prezdivky ... Argumenty jsou. Ale pro pochopení argumentů jsou potřeba nějaké základní znalosti, které vy nemáte. A není povinností nikoho zde v diskusi vám ty základy vysvětlovat.
Vyhození záznamu z cache je práce, dost drahá práce. To, že ověřovat s každým dotazem platnost, je mnohem levnější, než vyhazovat záznamy z cache, je vaše ničím nepodložená domněnka.
Když nebudete cachovat záznamy s TTL menší než hodinu, s největší pravděpodobností nebudete cachovat většinu provozu. Protože ty nejzajímavější záznamy, kam lidé lezou nejčastěji, mají právě krátkou TTL.
-
Zkuste si pořádně prohlédnout výstup digu při dotazech na populární weby. Zkuste parametr +ttlu. Většina obsahu poskytovaného nějakou CDN má krátká TTL, rozhodně po hodinových intervalech nemůžou pracovat. To sice platí pro servery TLD nebo root serverů, ale není tolik běžné u jiných serverů. Zkuste dig +ttlu www.root.cz www.lupa.cz, jak vysoké jsou.
Poté, co ověříte platnost a bude vypršená, můžete ten kontrolovaný záznam přehodit do listu "vypršené k použití přístě". Takže nutně nechodíte pořád na ten stejný záznam a neděláte to dokola.
Ty záznamy s kratším TTL budou chtít vaši klienti častěji, protože i oni obvykle mají svoji cache. Ty určitě nechcete nechat viditelně čekat.
-
Ten krok navíc bude porovnání dvou čísel, tipuji tak jednu instrukcí. Ve srovnání se zbytkem je to řádově zanedbatelné.
Druhá věc ale je, jaká je alternativa. Mohli bychom cache uklízet hned, jak něco vyprší. V takovém případě bychom asi nechtěli procházet celou cache, tedy nejspíš bychom si udržovali i seřazený seznam expirací, a s každým uložením do cache bychom si museli ten seznam aktualizovat. Když ignoruju race conditions (teoreticky bychom mohli čerstvě vypršený záznam vrátit jako platný, protože úklid taky chvilku trvá*), udržování dlouhého seřazeného seznamu, do kterého pořád něco vkládáme, není úplně zanedbatelná operace.
*) Šlo by to samozřejmě řešit zámkem, což ale bude stát nemálo výkonu v situaci, kdy každou chvíli něco expiruje.
-
Ondřej dělá už v desítkách let kolem DNS. Je to k neuvěření, ale asi mezitím něco pochytil. Váš příklad pěkně popisuje hledání záznamu, ovšem nikoliv proces úklidu vypršených záznamů. Ten se neděje jednou instrukcí.
Ano, DNS cache je databáze, která se typicky skládá ze stromu, ve kterém se hledá podle jména záznamu. Uložená data nebývají velká, často mohou být velká podobně jako pointer do paměti. A záznamy se vejdou dva do jednoho 64b pointeru, AAAA záznam potřebuje velikost 2 pointerů na 1 adresu. Moc se kvůli tomu nevyplatí dělat druhý index podle TTL, aby se vám snadno a rychle mazalo vypršené záznamy. Pokud v rámci bodu 1. ověříte, že to jméno máte, porovnání TTL záznamu už je v porovnání s hledáním ve stromu konstantní operace. 2* dostane handle na nalezené záznamy toho jména, nehledá znovu od začátku. Tohle není web cache, kde ukládáte celé stránky.
Nějak jste nevysvětlil, jak ze stromu uspořádaného podle jména rychle smažete ty vypršené záznamy, na které nemáte separátní frontu řazenou podle (zbývající) TTL. Mít dodatečný index k TTL každého záznamu je drahé a zabírá to dost místa, která by se mohla využít pro uložená data. Hit ratio je celkem zásadní parametr pro rychlé DNS, velká cache dost pomůže.
Vaše varianta s 3a je (pokud vím) v bind9 kódu použitá. Rád se nechám poučit, kde přesně to dělají jinak.
-
na wiki jsem nasel u cpu cache zajimavy vypocet rychlosti ziskani dat z pameti s pouzitim ruznych cache:
Example: main memory = 50 ns, L1 = 1 ns with 10% miss rate, L2 = 5 ns with 1% miss rate, L3 = 10 ns with 0.2% miss rate.
No cache, AAT = 50 ns
L1 cache, AAT = 1 ns + (0.1 × 50 ns) = 6 ns
L1–2 caches, AAT = 1 ns + (0.1 × [5 ns + (0.01 × 50 ns)]) = 1.55 ns
L1–3 caches, AAT = 1 ns + (0.1 × [5 ns + (0.01 × [10 ns + (0.002 × 50 ns)])]) = 1.5101 ns -
Více-úrovňová keš nemá až zas tak velký smysl, protože RAM má pořád stejnou "cenu" narozdíl od keší na procesoru, které jsou spíše implementovány pomocí SRAM.
Nicméně existují hybridní cache-eviction algoritmy, kde se položky přesouvají mezi jednotlivými vrstvami na základě zvoleného algoritmu, a každá vrstva má jinak řešeno vyhazování. Viz ten odkazovaný článek do wikipedie.
-
Filip JirsákStříbrný podporovatel
Víceúrovňová cache se případně používá na úrovni sítě – váš počítač má svou DNS cache. Když v ní nenajde odpověď, zeptá se cache v síti. Když ta nenajde odpověď, zeptá se cache u ISP, když ta nemá odpověď, zeptá se třeba ještě cache Googlu, Cloudflare nebo CZ.NICu.
Pak to někdo celé obejde, když si rovnou na počítači nastaví cache Googlu… (A někdy oprávněně, pokud místní cachující resolver nebo resolver ISP odpovídá pomaleji, než Google…)
-
DannyStříbrný podporovatelNo, kdyz jako pojmenovani zvolite pomerne genericke slovo (v prekladu sito), tak k podobne kolizi dojde celkem snadno... :-) A rozhodne to neni prvni ani posledni "kolizni" oznaceni neceho v IT. Na druhou stranu, vzdy je dulezite vnimat i kontext uziti daneho pojmenovani a pak moc omylu nehrozi.
A kdybychom chteli byt jo velci puntickari, tak predmetne RFC hovori o "Sieve" a nikoliv o "SIEVE" :-) A alespon my "unixari" jsme zvykli na to, ze i velikost pismen hraje roli.
-
Dobry den.
Mohl bych se zeptat, proc jsou na tom histogramu ty schody, kdyz tam jsou evidentne nejake vyskyty i mimo ostra cisla 1,2,3,4,5...ms?
Ja mam namereno, ze nase cache maji vetsinu dotazu odpovezenych do 0.000062500s, takze bych ocekaval, ze tam jeste budou zajimava data.
Nicmene da se ocekavat ze i tam byl SIEVE uspesnejsi.
Dekuji.
Marek -
To je vlastnost toho měřícího nástroje. Pokud dobře rozumím kolegům, tak už takhle je to docela dost dat, takže se to nějakým způsobem agreguje.
Každopádně ten dopad na samotnou latenci odpovědí je až sekundární - tedy v tom, že při cache-hit se nikdy nehýbe položkami v seznamu, ale je to Blind-CAS zápis. Nicméně pořád je tam read-lock, takže je tam ještě prostor pro zlepšení.
Ten primární dopad, který je vidět na latenci je jednak v poměru cache-hit/cache-miss, a také ve změně toho, kdy se dělá cache-eviction při overmem. Původní “overmem” implementace dělala cache-eviction i při cache-hit, nově se cache-eviction děje jen při cache-miss. Bylo by určitě zajímavé tyhle dvě změny oddělit, ale to už je spíš taková akademická práce, a cílem tohoto článku bylo spíše ukázat, že nahrazení LRU za SIEVE-LRU může mít takhle významný dopad na výkon.
