Adaptivní náhradní mezipaměť - Adaptive replacement cache

Adaptivní náhradní mezipaměť (OBLOUK) je algoritmus nahrazení stránky s lepším výkonem[1] než LRU (Nejméně uživaný v poslední době). Toho je dosaženo sledováním často používaných i nedávno použitých stránek a nedávné historie vystěhování obou. Algoritmus byl vyvinut[2] v IBM Výzkumné centrum Almaden. V roce 2006 bylo společnosti IBM uděleno patent na politiku adaptivní náhradní mezipaměti.

souhrn

Základní LRU udržuje seřazený seznam (adresář mezipaměti) položek prostředků v mezipaměti, přičemž pořadí řazení je založeno na čase posledního přístupu. Nové položky se přidávají na začátek seznamu po vyřazení spodního záznamu. Hity mezipaměti se přesunou nahoru a všechny ostatní položky se posunou dolů.

ARC vylepšuje základní strategii LRU rozdělením adresáře mezipaměti na dva seznamy, T1 a T2, pro nedávno a často odkazované položky. Na druhé straně je každý z nich rozšířen o duch seznam (B1 nebo B2), který je připojen ke spodní části obou seznamů. Tyto duch seznamy fungují jako přehledy výkonů sledováním historie naposledy vystěhovaných položek mezipaměti a použití algoritmu duch zásahy, aby se přizpůsobily nedávné změně ve využívání zdrojů. Všimněte si, že duch seznamy obsahují pouze metadata (klíče pro položky) a nikoli samotná data o prostředku, tj. protože je položka vypuzena do duch seznam jeho data jsou zahozena. Adresář kombinované mezipaměti je uspořádán do čtyř seznamů LRU:

  1. T1, pro nedávné položky mezipaměti.
  2. T2, u častých záznamů, odkazováno alespoň dvakrát.
  3. B1, duch položky nedávno vyřazené z mezipaměti T1, ale stále sledovány.
  4. B2, podobné duch záznamů, ale vystěhován z T2.

T1 a B1 jsou společně označovány jako L1, kombinovaná historie nedávných jednotlivých odkazů. Podobně je L2 kombinací T2 a B2.

Celý adresář mezipaměti lze vizualizovat na jednom řádku:

. . . [   B1 <-[     T1 <-!-> T2 ]-> B2 ] . .      [ . . . . [ . . . . . . ! . .^. . . . ] . . . . ]                [   pevná velikost mezipaměti (c) ]

Vnitřní [ ] závorky označují skutečnou mezipaměť, která, i když má pevnou velikost, se může volně pohybovat napříč historii B1 a B2.

L1 se nyní zobrazuje zprava doleva, začíná nahoře a je označena symbolem ! popisovač. ^ označuje cílovou velikost pro T1 a může být rovna, menší než nebo větší než skutečná velikost (jak ukazuje !).

  • Nové položky zadejte T1 nalevo od !, a jsou postupně tlačeni doleva, nakonec jsou vypuzeni z T1 do B1 a nakonec úplně vypadli.
  • Jakýkoli záznam v L1, na který se odkazuje ještě jednou, dostane další šanci a vstoupí do L2, napravo od středu ! popisovač. Odtud je opět tlačen ven, z T2 do B2. Záznamy v L2, které získají další zásah, to mohou opakovat donekonečna, až nakonec vypadnou úplně vpravo od B2.

Výměna, nahrazení

Položky (znovu) vstupující do mezipaměti (T1, T2) způsobí ! pohybovat se směrem k cílové značce ^. Pokud v mezipaměti není volné místo, určuje tato značka také to, zda buď T1 nebo T2 vypudí záznam.

  • Hity v B1 zvětší velikost T1, tlačí ^ doprava. Poslední položka v T2 je vypuzena do B2.
  • Hity v B2 zmenší T1 a budou tlačit ^ zpět doleva. Poslední položka v T1 je nyní vypuzena do B1.
  • Chybějící mezipaměť to neovlivní ^, ale ! hranice se přiblíží k ^.

Rozvinutí

ARC je aktuálně nasazeno v řadičích úložiště IBM DS6000 / DS8000.

Sun Microsystems škálovatelný souborový systém ZFS používá variantu[3] ARC jako alternativa k tradičnímu Solaris mezipaměť stránky souborového systému ve virtuální paměti. Byla upravena tak, aby umožňovala uzamčené stránky, které se aktuálně používají a nelze je uvolnit.

PostgreSQL používal ARC ve svém bufferu na krátkou dobu (verze 8.0.0), ale rychle jej nahradil jiným algoritmem s odvoláním na obavy ohledně patentu IBM na ARC.[4]

VMware vSAN (dříve Virtual SAN) je produkt s hyperkonvergovaným softwarovým úložištěm (SDS) vyvinutý společností VMware. Ve svém algoritmu pro ukládání do mezipaměti používá variantu ARC. [5]

Viz také

Reference

  1. ^ Jeden na LRU, Usenix: přihlášení; Srpna 2003
  2. ^ Nimrod Megiddo a Dharmendra Modha, 09.03.2010 archiv domovské stránky ARC, s odkazy na několik článků
  3. ^ komentáře v systému Solaris ZFS arc.c zdrojový soubor vysvětluje rozdíly oproti původní práci
  4. ^ Článek v Postgresql General Bits, „Sága algoritmu a patentu ARC“, publikovaná 6. února 2005
  5. ^ Referenční dokument, „Algoritmy mezipaměti VMware vSAN“[trvalý mrtvý odkaz ]

externí odkazy