LRU 알고리즘

LRU(Least Recently Used) 알고리즘

가장 오래 전에 사용된 것은 디스크에 저장하고 메모리에는 가장 최근에 사용된 데이터를 저장 함으로써, 디스크 I/O를 줄이고, 데이터베이스 시스템의 성능은 증가하도록 하는 관리 기법이다.

Working Set

• LRU 리스트
  
  
• 메인 리스트 : 사용된 버퍼들의 리스트가 hot, cold로 분류
• 보조 리스트 : 미사용된 버퍼나 DBWR에 의해 기록된 버퍼들의 리스트
  
  

• LRUW 리스트
  
  
• 메인 리스트 : 변경된 버퍼들의 리스트
• 보조 리스트 : DBWR에 의해 기록중인 버퍼들의 리스트
  
  

LRU 보조 -> LRU 메인 -> LRUW 메인 -> LRUW 보조 순으로 순환하며 버퍼를 탐색한다.



1. Standard LRU

• 가장 최근에 사용한 버퍼는 LRU 리스트의 MRU end로 이동 된다.
  
  
• 서버 프로세스가 래치 획득 후 뒤에서 부터 1/3 지점까지 찾은 후 없으면 서버 프로세스가 sleep 상태로 변경된다.
  
  
• 문제점 :
  Full Table Scan시 LRU end에 더티 버퍼가 모이기 때문에 검색시간이 오래 걸리고, 다른 서버 프로세스 대기시간이 길어진다. 또한 이로인해 DBWR이 데이터를 내려쓰기 위해 불필요한 I/O가 많이 발생하게 된다. 

2. Modified LRU

• Standard LRU의 단점을 극복하기 위해 full table 스캔에 사용된 buffer의 주소는 LRU end에 쌓이고 dml 혹은 index로 읽혀진 buffer의 헤더는 MRU end로 옮긴다.
  
  
• 문제점 :
  Index Full Scan이나 작고 자주사용하는 코드성 table을 full table 스캔했을 경우 LRU end로 들어가기 때문에 메모리 상에서 금방 사라지는 문제로 I/O가 많이 발생한다.
  
  
• 보완 방법 :
• keep 버퍼풀을 사용한다.
• cache 속성을 걸어 메모리상에 남아있게 한다.
  - create table 이름 ... cache;
  - alter table 이름 cache;,
  - select /*+ cache */ * from 이름;

3. Touch count LRU

• Modified LRU의 단점을 극복하기 위해 만든 알고리즘으로 가장 효율적이다. Touch count를 적용하여 가능한 자주 사용하는 작은 테이블을 caching하여 메모리에 오래 남아있게 한다.
  
  
• hot 영역과 cold, mid 영역으로 나뉜다.
  
  
• _db_percent_hot_default 히든 파라메터를 사용하면 mid 영역을 50% 위치가 아닌 다른 위치로 변경할 수 있다.
    
  

• Single Block Reads
  
  - 사용된 buffer의 head는 touch count 넘버를 변경한 후 cold나 hot 영역으로 이동한다.
  
  - cold end 부터 조회하여 동일 블록이 존재할 경우에는 재활용 하며 동일 블록이 없을 경우 touch count가 1 이하이면 재 이용한 후 cold의 head 영역으로 이동시키고 touch count는 1로 변경한다. touch count가 2일 경우에는 hot 영역의 head로 이동시킨 후 touch count는 0으로 초기화 한다.
  
  
• Multie Block Reads
  
  - cold end에서 4개씩 block을 가지고 와서 사용한 후 mid point로 삽입되고 다시 cold end로 이동한다. 모든 multie block을 읽어 들일때까지 반복한다.
   인덱스 풀스캔으로 읽힌 블록들은 콜드 영역의 꼬리에 위치함으로써 버퍼 캐시에 머무를 확률이 낮아진다.
  
  - db_file_bultiblcok_read_count = 4 파라미터가 multie block reads에서 한번에 읽어들이는 블럭의 수를 나타낸다.
  
  
• Keep 버퍼 풀
  
  - 멀티 블록 I/O로 읽은 블록들도 싱글 블록 I/O로 읽은 블록과 동일하게 콜드 영역의 제일 앞으로 이동시킨다.

참고문헌 : OWI - 조동욱 저