LIRS 캐싱 알고리즘

LIRS caching algorithm

LIRS(Low Inter-Reference Recency Set)는 페이지 치환 알고리즘으로 LRU(Last Recently Used) 및 기타 많은 새로운 [1]치환 알고리즘보다 성능이 향상되었습니다.이것은, 액세스 된 페이지의 순위를 동적으로 매겨 치환을 결정하기 위한 인접성 메트릭으로서 「재사용 거리」[2]를 사용하는 것으로 실현됩니다.

요약

지역 수량화

모든 페이지 치환 알고리즘이 기능하기 위해서는 참조 로컬리티의 유무에 의존하지만, 다른 치환 알고리즘의 큰 차이는 이 로컬리티를 수량화하는 방법에 있습니다.LIRS는 페이지의 재사용 거리 또는 페이지의 2개의 연속된 참조 간에 액세스되는 개별 페이지 수를 사용하여 로컬리티를 정량화합니다.특히 LIRS는 이 목적으로 마지막 및 두 번째에서 마지막까지의 참조(존재하는 경우)를 사용합니다.처음 페이지에 액세스하는 경우 해당 페이지의 재사용 거리는 무한합니다.이와는 대조적으로 LRU는 페이지의 참조 후 액세스되는 고유 페이지 수인 페이지의 반복성을 사용하여 로컬리티를 정량화합니다.LIRS 실장에서는, 최신의 액세스 이력을 고려해, 실제로는, 페이지의 재이용 거리와 빈도가 큰 것을 메트릭으로서 사용해, 그 인접성을 정량화합니다(RD-R).캐시의 캐퍼시티가 C페이지라고 가정하면 LIRS 알고리즘은 최근에 액세스한 페이지의 RD-R 값에 따라 순위를 매겨 캐시 내에서 가장 순위가 높은 C페이지를 유지합니다.

재사용 거리와 반복성의 개념은 다음과 같이 시각화할 수 있습니다. 여기서 T1과 T2는 각각 페이지 B의 두 번째에서 마지막까지 및 마지막 참조 시간이고 T3은 현재 시간입니다. 

. . B . . . B . . . . B . . . . ^ -- -- -- ------------------------------------------------------------------------------------------------------------------------------------------------------------

교체 대상자 선택

LIRS는 캐시된 페이지와 캐시되지 않은 페이지의 메타데이터를 정리하고 다음과 같이 치환 작업을 수행합니다.이것도 그래프에 예시되어 있습니다.

LIRS 교환 작업
  1. 캐시는 Low Inter-Reference Recency(LIR) 파티션과 High Inter-Reference Recency(HIR) 파티션으로 나뉩니다.LIR 파티션은 최상위 페이지(LIR 페이지)를 저장하고 HIR 파티션은 기타 페이지(HIR 페이지)를 저장합니다.
  2. LIR 파티션은 캐시의 대부분을 차지하며 모든 LIR 페이지는 캐시에 상주합니다.
  3. 최근에 액세스한 모든 페이지는 LIRS 스택(그래프에서는 스택S)라고 불리는 FIFO 큐에 배치되며 모든 상주 HIR 페이지도 다른 FIFO 큐(그래프에서는 스택Q)에 배치됩니다.
  4. 액세스 된 페이지는 스택S 의 상부로 이동해, 스택의 하부에 있는 HIR 페이지는 삭제됩니다.예를 들어 그래프(a)의 페이지 B에 접속한 후 그래프(b)를 생성한다.
  5. 스택 S 의 HIR 페이지에 액세스 하면, LIR 페이지가 되고, 따라서 스택S 의 하부에 있는 LIR 페이지가 HIR 페이지로 바뀌어 스택Q 의 상부로 이동합니다.예를 들어 그래프(c)는 그래프(a)의 페이지 E에 액세스한 후에 작성된다.
  6. 누락되어 상주 페이지를 교체해야 할 경우 스택Q 하단의 상주 HIR 페이지가 교체 대상으로 선택됩니다.예를 들어 그래프(d)와 (e)는 각각 그래프(a)에서 페이지 D와 페이지 C에 접속한 후에 작성된다.

도입

LIRS는 버전 5.[4]1부터 MySQL에 도입되어 있습니다.Infinispan 데이터 그리드 [5]플랫폼에도 채택되어 있습니다.NetBSD [7]에서는, LIRS 의 근사 CLOCK-Pro [6]가 채용되고 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Jiang, Song; Zhang, Xiaodong (June 2002). "LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance". ACM SIGMETRICS Performance Evaluation Review. 30 (1): 31–42. doi:10.1145/511399.511340.
  2. ^ Mattson, R.L.; Gecsei, J.; Slutz, D. R.; Traiger, I. L. (1970). "Evaluation techniques for storage hierarchies". IBM Systems Journal. 9 (2): 78–117. doi:10.1147/sj.92.0078.
  3. ^ Song Jiang; Xiaodong Zhang (2005). "Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache Performance". IEEE Transactions on Computers. 54 (8): 939–952. doi:10.1109/TC.2005.130. S2CID 11539061.
  4. ^ svn commit - mysqldoc@subrva : r6768 - trunk / ndbapi
  5. ^ Infinispan 제거, 배치 업데이트 및 LIRS
  6. ^ Song Jiang, Feng Chen 및 Xiaodong Zhang은 2005 USENIX 연차 기술 회의(USENIX'05)에서 CLOCK-Pro: A Effective Revalment of the CLOCK Replacement of the CLOCK Replacement)를 발표했습니다.
  7. ^ FreeBSD/Linux 커널 상호 참조 sys/uvm/uvm_pdpolicy_clockpro.c

외부 링크

  • Rik van Riel의 O(1) VM에 대해 Linux에서 캐시와 프로그램 메모리의 균형을 맞추기 위해 LIRS를 사용할 수 있는 가능성에 대해 설명합니다.
  • CLOCK-Pro 페이지 치환 구현에 관한 보고서.
  • Linux 메모리 관리 개발 팀에 의해 확립된 고도의 페이지 교환 프로젝트.
  • Rik van Riel이 개발한 CLOCK-Pro 패치.
  • Peter Zijlstra가 개발한 CLOCK-Pro 패치.
  • CLOCK-Pro는 Wolfgan Mauerer의 Book Professional Linux 커널 아키텍처의 Linux 및 Academy 섹션의 한 예입니다.
  • Ali R의 LIRS 및 기타 알고리즘의 퍼포먼스 차이를 상술한 논문.엉덩이, 크리스 그니아디, 그리고 Y.찰리 후