적응형 교체 캐시

Adaptive replacement cache

Adaptive Replacement Cache(ARC)는 페이지 치환 알고리즘으로 LRU(최신 사용)보다[1] 성능이 우수합니다.이는 자주 사용되는 페이지와 최근에 사용된 페이지를 모두 추적하고 두 페이지에 대한 최근 삭제 내역을 기록함으로써 이루어집니다.이 알고리즘은 IBM Almaden Research Center에서 개발되었습니다[2].2006년에 IBM은 적응형 교체 캐시 정책에 대한 특허를 받았습니다.

요약

기본 LRU는 캐시 내의 자원 엔트리의 순서 목록(캐시 디렉토리)을 최신 액세스 시간에 따른 정렬 순서로 유지합니다.맨 아래 엔트리가 삭제된 후 목록의 맨 위에 새 엔트리가 추가됩니다.캐시 적중률이 맨 위로 이동하면 다른 모든 엔트리가 아래로 밀립니다.

ARC는 캐시 디렉토리를 최근 자주 참조되는 엔트리에 대해 T1과 T2의 2개의 목록으로 분할함으로써 기본적인 LRU 전략을 개선합니다.다음으로 이들 각각은 Ghost 목록(B1 또는 B2)으로 확장되며, Ghost 목록(B1 또는 B2)은 2개의 목록 하단에 첨부됩니다.이러한 고스트 목록은 최근에 제거된 캐시 엔트리의 이력을 추적하여 스코어 카드 역할을 하며 알고리즘은 고스트 히트를 사용하여 리소스 사용량의 최근 변화에 적응합니다.Ghost 목록에는 메타데이터(엔트리의 키)만 포함되며 리소스 데이터 자체는 포함되지 않습니다. 즉, 엔트리가 Ghost 목록으로 제거되면 데이터가 폐기됩니다.결합된 캐시 디렉토리는 다음 4개의 LRU 목록으로 구성됩니다.

  1. T1(최근 캐시 엔트리용).
  2. 빈번한 엔트리의 경우 T2는 적어도2회 참조됩니다.
  3. B1, Ghost 엔트리는 최근에 T1 캐시에서 삭제되었지만 추적되고 있습니다.
  4. B2는 비슷한 고스트엔트리를 사용하지만 T2에서 제외됩니다.

T1과 B1을 함께 L1이라고 부릅니다.L1은 최근의 단일 참조의 결합 이력입니다.마찬가지로 L2는 T2와 B2의 조합입니다.

캐시 디렉토리 전체를 한 줄에 표시할 수 있습니다.

. . [ B1 < - [ T1 < - ! - > T2 ] -> [ . . . . . . ][ . . ^ . . ][ 고정 캐시 크기 ( c ) ]

안쪽 [ ] 괄호는 크기가 고정되어 있지만 B1 및 B2 이력에 걸쳐 자유롭게 이동할 수 있는 실제 캐시를 나타냅니다.

이제 L1이! 마커로 표시된 맨 위에서 시작하여 오른쪽에서 왼쪽으로 표시됩니다.^는 T1의 타깃사이즈를 나타내며 실제 사이즈보다 작거나 클 수 있습니다(!로 나타냄).

  • 새로운 엔트리는!의 왼쪽에 T1로 들어가 왼쪽으로 서서히 밀려나 T1에서 B1로 퇴출되어 최종적으로 완전히 폐기됩니다.
  • L1 내의 엔트리가 한 번 더 참조되고 다시 기회가 주어지며 중앙!마커의 오른쪽 끝에 L2로 들어갑니다거기서 다시 바깥쪽으로 밀려나 T2에서 B2로 넘어갑니다.L2 내의 엔트리가 다시 히트하면 최종적으로 B2의 오른쪽 끝에서 드롭될 때까지 이 엔트리를 무기한 반복할 수 있습니다.

교환

캐시(T1, T2)에 들어가는 엔트리(재입력)는 !를 타겟마커 ^ 쪽으로 이동시킵니다.캐시에 사용 가능한 공간이 없는 경우 이 마커는 T1 또는 T2 중 하나가 엔트리를 제거할 것인지도 결정합니다.

  • B1을 누르면 T1의 크기가 커지고 ^가 오른쪽으로 밀립니다.T2의 마지막 엔트리는 B2로 삭제됩니다.
  • B2에 적중하면 T1이 축소되어 ^가 왼쪽으로 밀립니다.이것으로 T1의 마지막 엔트리가 B1로 삭제됩니다.
  • 캐시 누락은 ^에 영향을 주지 않지만 ! 경계가 ^에 가까워집니다.

도입

ARC는 현재 IBM의 DS6000/DS8000 스토리지 컨트롤러에 구축되어 있습니다.

Sun Microsystems의 확장 가능한 파일 시스템 ZFS는 가상 메모리의 기존 Solaris 파일 시스템 페이지 캐시 대신 ARC를[3] 사용합니다.현재 사용 중이며 비워 둘 수 없는 잠긴 페이지를 허용하도록 수정되었습니다.

PostgreSQL은 버퍼 매니저(버전 8.0.0)에서 ARC를 잠깐 사용했지만,[4] ARC에 대한 IBM 특허에 대한 우려를 이유로 이를 다른 알고리즘으로 빠르게 대체했다.

VMware의 vSAN(이전의 Virtual SAN)은 VMware가 개발한 하이퍼 컨버전스 소프트웨어 정의 스토리지(SDS) 제품입니다.캐싱 알고리즘에서는 ARC의 배리언트를 사용합니다.[5]

OpenZFS는 멀티 레벨 캐시 내의 ARC 및 L2ARC를 읽기 캐시로 사용할 수 있습니다.OpenZFS에서 디스크 읽기는 종종 ARC를 사용하여 RAM의 첫 번째 레벨 디스크 캐시에 도달합니다.SSD가 두 번째 수준의 디스크 캐시를 저장하도록 설정된 경우 L2ARC라고 합니다.L2ARC는 동일한 ARC 알고리즘을 사용하지만 캐시된 데이터를 RAM에 저장하는 대신 캐시된 데이터를 고속 [6][7][8][9][10][11]SSD에 저장합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ One Up on LRU, USenix : 로그인, 2003년8월
  2. ^ Nimrod Megiddo and Dharmendra Modha, 2010-03-09 ARC 홈페이지 아카이브 (여러 기사에 대한 포인터 포함)
  3. ^ Solaris ZFS arc.c 소스 파일의 코멘트는 원래 작업과의 차이를 설명합니다.
  4. ^ Postgresql General Bits 기사 "The Saga of the ARC Algorithm and Patent" (ARC 알고리즘과 특허의 사가) 2005년 2월 6일 발행
  5. ^ 레퍼런스 문서 "VMware vSAN 캐싱 알고리즘"[permanent dead link]
  6. ^ "ZFS 캐싱"
  7. ^ 'ZFS 프라이머'
  8. ^ 짐 솔터."Linux에서 영구 L2ARC가 ZFS로 전송될 수 있습니다."2020.
  9. ^ "캐시: L2ARC 액세스"
  10. ^ 브렌단 그레그."ZFS L2ARC"
  11. ^ 란비르 싱."Adaptive Replacement Cache(ARC) 및 L2ARC"입니다.

외부 링크