[CS186] Introduction to Database Systems - Week 4

⛅ Buffer Management ⛅

Buffer Manager

• 메모리에 있는 페이지들을 관리하고 파일 및 인덱스 매니저의 페이지 요청을 처리한다
• 메모리 공간은 한정적이기 때문에 버퍼 매니저는 공간이 다 찰 경우 어떤 페이지를 퇴출할지도 결정해야 한다

Buffer Pool

• 메모리는 페이지가 들어갈 수 있는 프레임으로 공간을 분할하여 버퍼 풀로 변환된다
• 버퍼 프레임은 페이지가 저장할 수 있는 양의 데이터 만큼 저장할 수 있다. (그래서 페이지는 프레임에 딱 맞게 들어간다)
• 효율적으로 프레임을 추적하기 위해 메타데이터를 가지고 있는 테이블이 필요하고 버퍼 매니저는 메타데이터 테이블을 저장할 추가적인 공간을 메모리에 할당한다
• 메타테이블은 4가지 정보를 가지고 있다
  • 1. Frame ID: 메모리 주소와 고유하게 연결되있다
  • 2. Page ID: 현재 프레임이 포함하는 페이지를 알려준다
  • 3. Dirty Bit: 페이지가 수정되었는지 여부를 확인한다
  • 4. Pin Count: 현재 페이지를 사용 중인 요청자 수를 추적한다
• replacement policy: 페이지의 접근 패턴에 의존한다
• optimal policy: page hit에 의해 결정된다
• page hit: 요청된 페이지가 디스크에 갈 필요없이 메모리에서 찾은 경우
• hit rate: (# of page hits) / (# of page access)

LRU Replacement and Clock Policy

• 가장 보편적으로 사용되는 replacement policy는 LRU (Least Recently Used)이다. 
• 하지만 LRU는 일반적으로 비용이 많이 들 수 있기 때문에 clock policy는 LRU를 대체할 수 있는 구현을 제공한다
• Clock policy는 메타데이터 테이블의 참조 비트 열과 clock hand variable을 사용해서 현재 프레임을 추적해서 LRU를 계산한다
• 참조 비트를 사용하는 것은 공간과 시간비용이 줄어든다
• LRU에서는 버퍼 매니저가 Last Used 열의 가장 작은 값을 찾아야 하는데 시간이 소요되지만 clock policy에서는 clock hand만 따라가면 된다
• Sequential Scan + LRU => sequential flooding (버퍼 풀 사이즈가 페이지의 수보다 작고 반복해서 순차적으로 페이지를 읽어야 할 때 캐시의 hit rate이 0% 가 된다)

MRU Replacement

• 다른 교체 정책으로는 MRU, Most Recently Used가 있다
• 가장 최근에 사용된 페이지를 제거한다
• sequential flooding 접근 패턴에서는 MRU가 LRU보다 더 효과적이다