Vlákno názorů k článku SIEVE: algoritmus pro kešování lepší než LRU? od [object Object] - > .. kvůli odstranění čištění keše založeného na...

No tahle analogie je mizerná. Protože po nákupu Starobrna a jeho vypití (fuj) už bys do batohu (cache) dal prazdnou flašku a při dalším requestu Starobrna bys stejně musel do obchodu. A ještě bys měl v cachi prázdné flašky (null objekty) :))

Třeba si toho Starobahna jenom ucucne a vrátí ho do batohu. Vylije ho až když bude úplně vyšuměné.

Uklízení mrtvol je drahý, proto se to odkládá až není jiná možnost. Každou sekundu něco expiruje, uklízelo by se pořád.
Jedno CMP pro TTL na každý hit není moc práce.
U DNS se vrací záznamy i ze stale-cache, když je autoritativní server nedostupný.

Nezlobte se, ale bohužel nemám čas na to, abych vás dovzdělával. To musíte udělat vy sám.

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.

bez 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.