이전까지
이전까지는 DataBase에 실제 데이터가 어떤 형식으로 저장되는지에 대해서 배웠다. 이번 강에서 배울 부분은 Buffer Pool에 관해서이다.
Introduction
첫강의 3. Storage1에서 배웠지만 결국 데이터 베이스는 Execution Engine이 Query를 수행하는데 필요한 데이터를 Buffer Pool에 효율적으로 가져다주는 프로세스가 가장 중요하다고 할 수 있다. 이번강에서는 이 Buffer Pool과 그 기본에 대해서 배우게 된다.
DataBase Hieracy를 통해 알다시피 Disk <-> Memory의 과정은 굉장히 비용이 많이드는 과정이다. 강의에서는 2가지 시사점을 이야기하는데 “Spatial Control”과 “Temporal Control”이다.
Spatial Control
공간 제어라는 이상한 한국어로 번역이 되지만 결국 **한정된 메모리 공간에 어떻게 효율적으로 데이터를 넣고 뺼 것이냐?**라는 것에 대한 주안점이 존재한다.
여기에는 Buffer Pool이 사용하는 Page Table, Pre-fetch전략, Dirty Page전략과 같은 여러 방식들이 존재한다.
Temporal Control
시간 제어라는 말로 번역이 되지만 결국 evition Policy에 대한 이야기이다. Page를 load하는 과정에서 빈 Page가 없다면 결국 있던 Page를 쫓아 내고 새로운 페이지를 올리게 되는데, 이를 효율적으로 실행하는 방식에 대해서 이야기 한다.
대표적으로는 LRU(Least-Recent used), Clock, LRU-K와 같은 전략을 설명할 수 있다.
Lock vs Latches
두가지 측면에서 보기 전에 우선적으로 이해해야하는 부분이 Lock과 Latches이다. 이둘의 차이점은 뭘까?
- Lock
- Transaction에 대해서 자원을 점유 하는 상황을 이야기 한다. (High Level Concept)
- DB에 변화가 있어야 하는 경우 rollback의 개념을 포함하여 자원을 held하는 과정을 이야기한다.
- Latch
- Mutex와 같이 Operation에 대해서 자원을 점유하는 상황을 이야기한다. (Low Level Concept)
- Transaction과 같이 rollback을 고려하지는 않지만 DeadLock과 같은 상황이 생길 수 있다.
Buffer Pool
Buffer Pool이 동작하는 원리는 꽤나 단순하다. 아래 그림을 보면 Buffer Pool이 비어있는 상황에서 Execution Engine이 Page를 요청하게 된다면 필요한 Page를 Buffer Pool에 올려주면 되는 것이다.
Buffer Pool은 거의 고정된 (상업용 DB는 조금 다를 수 있다.) size를 가지게 된다. 또한 Buffer Pool는 “frame” 이라는 단위로 쪼개진 영역에 Disk의 Page를 올리게 된다.
여기서 Buffer Pool에 있는 Page를 referancing하는 Page Table이 등장하게 된다.
Page Table
page table이 하는 역할은 Buffer Pool에 존재하는 Page를 referancing하는 역할을 한다. Execution Engine이 데이터를 요청을 하면 아래와 같은 순서로 데이터를 가져온다.
Q. 그냥 Buffer Pool에 접근해서 읽고 쓰면 되지 왜 Page Table이라는 걸 만드냐? A. 안전하게 데이터를 조작하기 위해서 라고 할 수 있을 것 같다. 데이터 변화의 반영을 2중으로 쪼개 놓음으로써 page를 손상되지 않게 하면서 데이터를 조작할 수 있게 하기 때문이다.
또한 Page table은 각 Page에 대한 meta-data를 가지고 있게 되며 이를 통해 dirty-flag, pin/reference counter를 관리하고 있다.
dirty-flag
network packet이 손상되는 것처럼 page가 의도치 않게 손상되는 경우를 위해 dirty-flag를 심어 놓는다. 이를 통해서 해당 손상된 page의 변경을 모두 없애거나 반영하는등의 정책을 결정할 수 있다.
pin/reference counter
Execution Engine에 의해 필요한 page가 요청되면 page를 읽을 수도 혹은 읽지 않을 수도 있다.(모두 읽은 경우는 쓰지 않을 수 있다.) 만약 Buffer Pool이 모두 꽉찬 상황이라면 어떤 Page든 쫓아내야 할 텐데 이때 Exection Engine이 참조하고 있는 경우 := reference counter !=0 에는 해당 Page를 쫓아낼 수 없도록 pin하고 evition 대상에서 제외시켜야한다.
Page Table vs Page Dictionary
Page Table
- Page Table은 in-memory에 존재하는 hash table로써 현재 Memory에 어떤 page가 있는 지를 추적할 수 있다.
- page id를 각 frame과 연결하면서 buffer pool의 상태를 추적할 수 있게된다.
Page Dictionary
- Page Id를 실제 Disk에 있는 Page와 Mapping 시켜 놓은 자료구조라고 할 수 있다.
- DBMS에 의해서 관리되면 모든 변화는 여기에 기록후 Disk에 반영된다.
Global vs Local Policy
- Global Policy : 메모리의 관점에서 보았을 때 전체 DBMS상에서 효율적인 결정을 내리는 정책
- Local Policy : 메모리 관점에서 보았을 때 단일 Query에서 효율적인 결정을 내리는 정책
Buffer Pool Optimization
Buffer Pool을 구성하는 용어에 대해서 알았다면 어떻게 하면 얘를 효율적으로 쓸 수 있을 것인가에 대한 이야기를 진행 해야한다.
1. Mutiple Buffer Pool
Memory공간은 한정되어 있지만 해당 공간을 어떻게 쓰는지는 프로그래머의 재량이다. 결국 Buffer Pool을 여러 용도로 나눠서 쓰는게 불필요한 evition을 방지하는 방법일 수 있다.
이는 latch contention과 locality를 증가 시킬 수 있다는 장점이 존재하고, 이런 방법은 object ID와Hashing을 통해 page를 추적할 수 있게 된다.
Q. 그럼 각기다른 Buffer Pool에 같은 Page가 들어갈 수도 있자나? A. 이는 별로 효과적인 방법일 수 없다. -> 메모리를 낭비하는 것도 문제지만 동시에 Buffer Pool에 올라간 경우 한 쪽에서의 수정이 다른쪽에서 반영이 될 수 없기 때문에 문제가 될 수 있다.
2. pre-fetching
두번째는 미리 Page를 Buffer Pool에 올릴 수 있지않을까? 하는 생각에서 출발한다.
앞선 강의 5. Storage3에서 OLTP와 OLAP에 대해서 언급한 적이 있다. 이중 대량의 집계 작업을 더 편하게 할 수 있는 게 OLAP라고 했다.
예를 들어 .com으로 끝나는 이메일이 몇개인지 알고 싶다면 모든 table을 스캔해서 .com 이메일을 찾을 것이다.
이때 모든 table을 스캔시 다음에 올 page를 미리 알 수 있다. 왜냐하면 반드시 특정 page의 다음은 데이터는 예측가능한 page에 있을 것이기 때문이다.
이처럼 예측이 가능한 OLAP system같은 경우는 pre-fetching을 이용하는 것도 좋은 전략이라고 할 수 있다.
3. Scan Sharing
Exection Engine으로 부터 query는 이전 query가 모두 진행되지 않음에도 생길 수 있다. 이때 같은 page cluster를 읽는 상황이라면 이전 query가 읽는 page부터 다음 query가 읽는게 이미 buffer pool에 올라온 데이터를 쫓아내고 읽지 않아도 되기 때문에 조금 더 효율 적일 수 있다.
4. Buffer Pool Bypass
이는 Buffer Pool을 우회해서 직접 Disk에 접근하도록 프로그래밍 하는 것인데 때로는 system성능을 최적화 할 수 있는 방법일 수 있다.
대규모 데이터 작업, 임시 작업, 백업 및 복원등 buffer pool을 우회하면서 (page evition을 최소화 하면서) 작업을 진행하면 메모리 자원을 절약할 수 있는 과정이 될 수 있다.
다만 직접 disk에 접근하는 상황은 여러 문제가 존재할 수 있음으로 주의를 필요로 한다.
Buffer Replacement Policies
지금까지 Spatial Control에 관한 개념을 보았다. 이제 Temporal Control관점으로 보면 결국 어떤 알고리즘이 page를 덜 쫓아 내면서 연산을 할 수 있나? 혹은 적절하게 쓰지 않는 page를 해제 할것이냐에 대한 이야기 이다.
1. LRU
쉽게 설명하면 가장 오랫동안 사용하지 않은 page를 쫓아내는 알고리즘입니다.
구현은 이중 연결리스트로 가능한데 동작은 아래와 같습니다.
- cache가 찰때까지 page를 fetching합니다.(맨 뒤쪽으로 붙는다고 가정)
- 만약 cache가 찼다면 가장 앞쪽에 있는 page를 쫓아냅니다.
- 중간에 cache된 page를 읽었다면 해당 page의 연결을 끊고 맨뒤로 붙여줍니다.
2. Clock
page에 최초 접근했다면 clock_bit를 1로 바꿔줍니다. 만약 cache가 모두 차게 된다면 시계 방향으로 자료구조를 돌면서 clock_bit가 1인 page를 0으로 바꾸고 만약 clock_bit가 0이라면 해당 page를 쫓아내느 방식으로 진행합니다.
3. LRU-K
LRU-K는 LRU와 Clock의 이점을 합친 친구인데, 결국 LRU구조에서 목숨을 K번 주는것에 대한 부분으로 알고리즘을 구성합니다.