[database] simpleDB로 buffermanager에서 LRU 알고리즘 구현하기
이번 수업 과제로
DB의 buffer cache에서
hit ratio를 높이기 위한 대표적인 알고리즘인
LRU를 구현하는 과제를 받았다
simpleDB란?
simpleDB란 작은 규모의 database를 빌드해볼 수 있는
간단한 database 구현 프로젝트이다
java와 c++ 버전이 있다고 하는데
본 과제에서는 c++ 버전을 사용하였다
https://github.com/rotaki/simpledb
GitHub - rotaki/simpledb: A C++ version of SimpleDB originally written in Java by Edward Sciore. The structure of SimpleDB is ex
A C++ version of SimpleDB originally written in Java by Edward Sciore. The structure of SimpleDB is explained in detail in the book Database Design and Implementation. - rotaki/simpledb
github.com
cmake로 build를 한 다음
우선
./createstudentdb
를 실행해서 구축한 database에 table들을 넣어준다
그런 다음
./server
를 실행해서 쿼리를 통해 data들을 확인해준다
server를 실행 성공하면
Connect가 뜨는데 root:password@localhost를 입력하면
SQL을 입력하라고 뜬다
./server
Connect> root:password@localhost
SQL> select sid, sname, majorid, gradyear from student
SQL> select did, dname from dept
SQL> select sid, sname, gradyear, dname from student, dept where did = majorid
위에 맞게 SQL문들을 입력해서
table들이 잘 들어갔는지 확인해보면 된다
나같은 경우는 잘 들어간 것을 확인할 수 있었다
CLion을 docker 환경에서 실행하기
나같은 경우는 CLion을 IDE로 선택하였는데
(c/c++ 코딩계의 혁명)
docker 환경에서 빌드하기 위해서
Toochains과 cmake를 도커 환경으로 설정해줘서
그 안에서 하도록 설정해주었다
이렇게 toolchain을 내가 코드를 실행시키고 싶은
도커 이미지로 설정해주면 된다
도커 이미지 내부에는 gmake, cmake, cc, c++ 등은
반드시 설치되어있어야한다
그 다음에 CMake도 동일하게
toolchain으로 설정해준 도커를 선택해주면된다
그런 다음 ok해주면 해당 이미지로
CLion이 알아서 docker container를 생성하고
이렇게 해당 도커 컨테이너 환경 내부에서
cmake 디렉토리가 생기는 것을 확인할 수 있다
Introduction
이제 작업을 할 환경 세팅을 완료했으니
본격적으로 과제를 시작해보자
simpleDB에서 우리가 해결해야할 과제는
2가지가 있다
첫 번째는 지금 구조는 buffer가 꽉차고 이를 Replace할 때
그냥 가장 첫번째 unpinned된 buffer를 replace한다
해당 데이터의 사용 빈도 등을 확인하지 않기 때문에
hit ratio에 안좋은 영향을 줄 수 밖에 없다
두 번째는 replace할 buffer를 찾기 위해서
buffer들을 sequential하게 scan하는데
이런 구조는 시간이 오래 걸려서 성능에 영향을 준다
따라서 적절한 자료구조를 사용해서
이런 sequntial scan을 방지하고
빠르게 대체가능한 buffer를 찾을 수 있도록 변경해줘야한다
따라서 simpleDB 프로젝트에서 buffermanger 부분의 코드를 수정해
LRU 알고리즘을 구현한 뒤
수정 전과 수정 후의 hit ratio를 비교해보는 것이다
vanilla_buffer_manager의 구조는 위와 같다
LRU를 구현하려면 simpleDB 코드 중에서
buffermanager 부분을 수정해야한다
buffermanager의 header 파일과 실행파일의 경로이다
그다음 과제에서 친절하게 어디에 코드를 실행하면 되는지
주석을 달아주셨다
buffermanager에는 크게 4개의 class가 존재한다
1. buffer
2. buffer_manager
3. vanilla_buffer_manager
4. lru_buffer_manager
이렇게 4개의 클래스가 있는데
buffer는 말 그대로 buffer이고
vanilla는 아무것도 구현되지않은
그냥 buffer_manager이고
lru_buffer_manager는 우리가 LRU 로직을
추가해줘야할 클래스이다
buffermanger.hpp의 전체 코드는 아래와 같다
#pragma once
#include <condition_variable>
#include <memory>
#include <mutex>
#include "file/filemanager.hpp"
#include "log/logmanager.hpp"
namespace simpledb {
class buffer {
public:
buffer(file_manager *pFileManager, log_manager *pLogManager);
page *contents() const;
block_id block() const;
void set_modified(int pTxNum, int pLSN);
bool is_pinned() const;
int modifying_tx() const;
void assign_to_block(const block_id &pBlockId);
void flush();
void pin();
void unpin();
int get_ID() const;
private:
file_manager *mFileManager;
log_manager *mLogManager;
std::unique_ptr<page> mContents;
block_id mBlockId;
int mPins = 0;
int mTxNum = -1; // transaction that touched the buffer last
int mLSN = -1;
int buffer_id;
};
class buffer_manager {
public:
virtual ~buffer_manager() {}
virtual int available() = 0;
virtual void flush_all(int pTxNum) = 0;
virtual void unpin(buffer *pBuff) = 0;
virtual buffer *pin(const block_id &pBlockId) = 0;
virtual float get_hit_ratio() = 0;
virtual void print_status() = 0;
};
class vanilla_buffer_manager: public buffer_manager {
public:
vanilla_buffer_manager(file_manager *pFileManager, log_manager *pLogManager,
int pNumBuffs);
// ~vanilla_buffer_manager() ;
int available() override;
void flush_all(int pTxNum) override;
void unpin(buffer *pBuff) override;
buffer *pin(const block_id &pBlockId) override;
float get_hit_ratio() override;
void print_status() override;
private:
std::vector<std::unique_ptr<buffer>> mBufferPool;
int mNumAvailable; // number of unpinned buffers
const int mMaxTime = 10000;
std::mutex mMutex;
std::condition_variable mCondVar;
bool waiting_too_long(
std::chrono::time_point<std::chrono::high_resolution_clock> pStartTime);
buffer *try_to_pin(const block_id &pBlockId);
buffer *find_existing_buffer(const block_id &pBlockId);
buffer *choose_unpinned_buffer();
};
class lru_buffer_manager: public buffer_manager {
public:
lru_buffer_manager(file_manager *pFileManager, log_manager *pLogManager,
int pNumBuffs);
// ~lru_buffer_manager();
int available() override;
void flush_all(int pTxNum) override;
void unpin(buffer *pBuff) override;
buffer *pin(const block_id &pBlockId) override;
float get_hit_ratio() override;
void print_status() override;
private:
std::vector<std::unique_ptr<buffer>> mBufferPool;
int mNumAvailable; // number of unpinned buffers
const int mMaxTime = 10000;
std::mutex mMutex;
std::condition_variable mCondVar;
bool waiting_too_long(
std::chrono::time_point<std::chrono::high_resolution_clock> pStartTime);
buffer *try_to_pin(const block_id &pBlockId);
buffer *find_existing_buffer(const block_id &pBlockId);
buffer *choose_unpinned_buffer();
};
} // namespace simpledb
Implementation
이제 과제 안내에 따라서
본격적으로 구현을 해보자
차근차근 구현을 하려고 해봤다
어떤 buffer가 pin이 0이 아니라는 뜻은
어떤 transaction에서 해당 buffer의 데이터를
사용하고 있다는 뜻이다
그렇다면 Replace가 될 buffer는 당연히
사용 중이면 안되기 때문에 pin이 0이어야한다
따라서 처음으로 pin이 0인 buffer들만 담을
list를 따로 생성해서
교체가 가능한 후보 buffer들의 list를 생성한다
이제 대체될 buffer를 찾아야한다면
unpin이 가장 오래된 buffer를 head에 놓이게해서
이를 반환하게 해주어야한다
그런 다음 buffer의 pin이 0이 된다면
unpinned list에 추가를 해줘야하고
반대로 unpinned list에 있다가 pin이 0보다 커지면
unpinned list에서 제거해줘야한다
위 설명을 보고 가장 먼저 생각난건 queue 구조이다
따라서 unpinnedList를 queue로 만들어야겠다고 생각했다
우선 unpinnedList를 list로 선언해줬다
따라서 buffermanager 헤더파일에서
lru_buffer_manager class에
buffer 포인터를 담은 list인
unpinnedList와 unpinned buffer들을 관리할 공간인
unpinnedBufferMap을 unordered_map으로 선언해줬다
그런다음 buffermanager.cpp 파일에 들어가서
lru_buffer_manger의 unpin 함수를 수정해줬다
unpin이 되면 해당 pBuff를 unpin 해주고
unpinnedBufferMap에 해당 unpin된 buffer가 없다면
unpinnedList에 buffer를 넣어주고
unpinnedBufferMap에도 방금 넣어준 buffer를 담아준다
// buffermanager.cpp
void lru_buffer_manager::unpin(buffer *pBuff) {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
std::unique_lock<std::mutex> lock(mMutex);
pBuff->unpin();
if (!pBuff->is_pinned()) {
if (unpinnedBufferMap.find(pBuff) == unpinnedBufferMap.end()) {
unpinnedList.push_back(pBuff);
unpinnedBufferMap[pBuff] = std::prev(unpinnedList.end());
}
mNumAvailable++;
mCondVar.notify_all();
}
}
그 다음 buffer를 pin하려고 할때
unpinnedList와 bufferMap에 해당 buffer가 존재하면
이걸 지워주는 로직도 추가해준다
buffer *lru_buffer_manager::try_to_pin(const block_id &pBlockId) {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
buffer *buff = find_existing_buffer(pBlockId);
// if buffer is not found
if (!buff) {
return buff;
}
buff->assign_to_block(pBlockId);
// if buffer is not pinned
if (!buff->is_pinned()) {
mNumAvailable--;
}
// unpinnedList와 unpinnedBufferMap 새로 pin된 buffer가 있으면 제거
auto it = unpinnedBufferMap.find(buff);
if (it != unpinnedBufferMap.end()) {
unpinnedList.erase(it->second);
unpinnedBufferMap.erase(it);
}
buff->pin();
return buff;
}
그런 다음 unpinned buffer를 선택하는 함수에서
unpinnedList의 가장 앞에 있는 buffer를
선택하도록 변경해주자
buffer *lru_buffer_manager::choose_unpinned_buffer() {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
while (!unpinnedList.empty()) {
buffer *oldestBuffer = unpinnedList.front();
unpinnedList.pop_front();
unpinnedBufferMap.erase(oldestBuffer);
if (!oldestBuffer->is_pinned()) {
return oldestBuffer;
}
}
return nullptr;
}
이제 두 번째 구현을 살펴보자
이제 2번째 문제인 sequential scanning을 해결해보자
static의 bufferpool 대신에 hash map과 같은 map을 이용해서
blockID를 key로 하게끔 만들어 buffer들을 관리해주는
새로운 bufferpool map을 만들어준다
한 번 allocate 된 buffer는 pin이 되었든 unpin이 되었든
해당 map에 계속 존재해야한다
buffer가 이미 load되었는지 아닌지 확인하기 위해
위에서 만든 bufferMap을 활용할 수도 있고
가장 처음 buffer가 할당될 때
bufferMap에 넣은 다음
replacement를 할 때
대체가 된 buffer는 map에서 제거해주고
새로운 buffer를 map에 추가해줘야한다
따라서 전체 buffer를 관리해 줄
bufferMap을 unordered_map으로 선언해주고
key를 block_id로 설정해줬다
또한 hash_map으로 구현해줘야해서
hash function도 따로 선언해줬는데
block_id class 내부에
hash_fn을 구현해줬다
#pragma once
#include <string>
namespace simpledb {
class block_id {
friend bool operator==(const block_id &pLhs, const block_id &pRhs);
friend bool operator!=(const block_id &pLhs, const block_id &pRhs);
friend bool operator<(const block_id &pLhs, const block_id &pRhs);
friend bool operator>(const block_id &pLhs, const block_id &pRhs);
friend bool operator<=(const block_id &pLhs, const block_id &pRhs);
friend bool operator>=(const block_id &pLhs, const block_id &pRhs);
public:
block_id();
block_id(const block_id &pBlk);
block_id(const std::string &pFileName, int pBlockNum);
block_id &operator=(const block_id &pBlk);
bool is_null();
std::string file_name() const;
int number() const;
bool equals(const block_id &obj) const;
std::string to_string() const;
// hash_fn 구현
struct hash_fn {
std::size_t operator()(const block_id &b) const {
const std::size_t h1 = std::hash<std::string>()(b.file_name());
const std::size_t h2 = std::hash<int>()(b.number());
return h1 ^ (h2 << 1);
}
};
private:
std::string mFileName;
int mBlockNum;
};
} // namespace simpledb
block_id.hpp을 확인해봤더니
block_id의 각종 연산자와
필요한 메소드들이 선언되어있는 것을 확인할 수 있었다
그 아래에 hash_fn로 해시함수를 구현해줬다
try_to_pin 함수에서 buffer에 새로운 block이 할당될 때
이전 oldBlock을 제거해준 다음
새로운 block_id와 함께 buffer를 다시 map에 넣어준다
전체 try_to_unpin 함수 구조는 아래와 같다
buffer *lru_buffer_manager::try_to_pin(const block_id &pBlockId) {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
buffer *buff = find_existing_buffer(pBlockId);
// if buffer is not found
if (!buff) {
buff = choose_unpinned_buffer();
if (!buff) return nullptr;
}
if (block_id oldBlock = buff->block(); !oldBlock.is_null()) {
bufferMap.erase(oldBlock);
}
buff->assign_to_block(pBlockId);
bufferMap[pBlockId] = buff;
if (!buff->is_pinned()) {
mNumAvailable--;
if (const auto it = unpinnedBufferMap.find(buff); it != unpinnedBufferMap.end()) {
unpinnedList.erase(it->second);
unpinnedBufferMap.erase(it);
}
}
buff->pin();
return buff;
}
그 다음에 기존에 선언되어있었던
bufferPool에서 existing buffer를 찾았던 것을
bufferMap에서 찾도록 변경해준다
find_existing_buffer 함수를 아래와 같이 고쳐줬다
bufferMap에 blockId가 있으면 buffer 포인터를 반환하고
발견하지 못하면 Nullptr을 반환하게 했다
buffer *lru_buffer_manager::find_existing_buffer(const block_id &pBlockId) {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
if (auto it = bufferMap.find(pBlockId); it != bufferMap.end()) {
return it->second;
}
return nullptr;
}
이제 세번째로 넘어가보자
hit ratio를 반환하는 함수를 완성해보자
이를 위해선 hit count와 reference count가 있어야한다
reference count는 전체 들어오는 모든 block requests를 말하고
hit count은 그 중에서 buffer 내부에 있었던 block의 개수이다
따라서 다시 헤더파일에
refCnt와 hitCnt를 선언해주고
초기에 0으로 초기화를 해주었다
buffer *lru_buffer_manager::try_to_pin(const block_id &pBlockId) {
//////////////VANILLA VERSION ////////////////////
///////////CHANGE THE CODE BELOW /////////////////
buffer *buff = find_existing_buffer(pBlockId);
refCnt++;
if (buff) {
hitCnt++;
}
그런 다음 try_to_pin 함수에서
우선 들어오는 모든 요청에 대해서는 refCnt를 올려주고
그 다음에 buff가 존재하면 hitCnt를 올려주게 해줬다
그다음 get_hit_ratio 함수를 아래와 같이 구현해줬다
float lru_buffer_manager::get_hit_ratio() {
//implement your own code
if (refCnt == 0) return 0.0f;
const float ratio = static_cast<float>(hitCnt) / static_cast<float>(refCnt);
return std::round(ratio * 10000) / 100;
}
마지막 네 번째 안내를 보자
마지막으로 지금까지의 상황을 확인할 수 있는
print_status 함수를 구현해보자
위의 형식에 맞게 현재 status를 출력할 수 있도록 구현하라고 한다
우선 pin이 되었든 안되었든 file과 blockID, 그리고 pin 여부를 출력하게하고
가장 덜 사용된 순서대로 LRU order를 출력한 다음
hit ratio를 출력하도록 한다
아래와 같이 print_status 함수를 구현해줬다
void lru_buffer_manager::print_status(){
//implement your own code
std::cout << "**Buffer Allocation**" << std::endl;
for (const auto& [blkId, buff] : bufferMap) {
std::string blkStr = blkId.to_string();
std::string pinStatus = buff->is_pinned() ? "pinned" : "unpinned";
std::cout << "Buffer " << std::to_string(buff->get_ID()) << ": [" << blkStr << "] " << pinStatus << std::endl;
}
std::cout << "Unpinned Buffers in LRU order: ";
for (const auto& buff : unpinnedList) {
std::cout << std::to_string(buff->get_ID()) << " ";
}
std::cout << std::endl;
std::cout << "**Hit Ratio**" << std::endl;
std::cout << std::fixed << std::setprecision(2) << get_hit_ratio() << std::endl;
}
이대로 다 구현을 했으면
simpledb_test를 실행시켜서
잘 구현이 되었는지 확인해주면 된다
buffermangertest.cpp는 아래와 같이 구현되어있었다
test를 실행시키면 위와 같이 buffer size는 3개로 할당해서
pin과 unpin을 수행시켜준다
#include <iostream>
#include "buffer/buffermanager.hpp"
#include "file/blockid.hpp"
#include "file/filemanager.hpp"
#include "file/page.hpp"
#include "server/simpledb.hpp"
#include "gtest/gtest.h"
namespace simpledb {
TEST(buffer, buffermanager_test) {
simpledb db("buffermgrtest", 400, 3, "vanilla"); // three buffers, type: "vanilla", "lru"
buffer_manager &bM = db.buffer_mgr();
std::vector<buffer *> buff(6); //test buffers
std::string testFile = "testfile";
buff[0] = bM.pin(block_id(testFile, 0));
buff[1] = bM.pin(block_id(testFile, 1));
buff[2] = bM.pin(block_id(testFile, 2));
bM.unpin(buff[1]);
buff[1] = nullptr;
buff[3] = bM.pin(block_id(testFile, 0));
buff[4] = bM.pin(block_id(testFile, 1));
std::cout << "Available buffers " << bM.available() << std::endl;
try {
std::cout << "Attempting to pin block 3" << std::endl;
buff[5] = bM.pin(block_id(testFile, 3));
} catch (std::exception &e) {
std::cout << e.what() << std::endl;
}
bM.unpin(buff[2]);
buff[2] = nullptr;
buff[5] = bM.pin(block_id(testFile, 3));
bM.print_status();
}
} // namespace simpledb
우선 buffer_manager를 "vanilla"로 해서 실행해보았다
그런데 실행시켰는데 에러가 ㅎ..
buffer abort exception을 띄우며 에러가 발생했다
디버거를 걸어보고싶었으나
이상하게 디버거를 거니까 자꾸 에러가 떠서..
우선 print 찍으면서 어디서 에러가 뜨는지 확인해봤다
Attempting to pin block 3까지 출력되는걸 확인했으므로
그 밑에 Available buffer를 또 출력해줬는데
저기까지는 출력이 되었고 이후에 안되었다
한 마디로 buff[5] = bM.pin 부분에서 에러가 발생하는 것이었다
따라서 vanilla_buffer_manager의 pin 함수를 확인해보니
buff가 nullptr일 경우 buffer abort exception이 뜨는 것을 확인할 수 있었다
그런데 vanilla_buffer_manager는 수정해준적이 없는데
도대체 왜 에러가..
함수를 타고타고 가다보니
try_to_pin에서 choose_unpinned_buffer를 해주는데
여기서 buff가 없으면 그냥 없는채로 return해주는데
저기에 걸리는 것을 확인할 수 있었다
unpinned buffer가 없나본데..?
아 잠시 ㅋㅋㅋㅋ
잠시..
이 에러는 의도된거였다
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
ㅋㅋㅋㅋㅋㅋㅋ
총 사용가능한 buffer는 3개만 설정했고
맨처음에 0, 1, 2 모든 buffer를 pin 시켜줬다
그런다음 buff[1]을 unpin을 해주면서
사용가능한 buffer가 1개가 된다
available buffer가 1이 되는거 확인
그다음에 blockNum 0과 1을 다시 pin 해주는데
blockNum 0을 해줄 때는
이미 blockNum 0은 pin 되어있으므로 그냥 pinCnt만 올라가는 것이다
그 다음 blockNum 1을 다시 pin 해주는데
이전에 unpin 했던걸 다시 pin해주는것이므로
다시 buffer를 사용하게 되고 available count는 0이 된다
그 다음에 이제 사용가능한 buffer가 없는데
blockNum 3을 pin 해주려고하니
당연히 에러가 발생..
아무생각없이 코딩을 하면 이렇게 된다
ㅋㅋ
아무튼 에러가 잘 뜨는 것도 확인해줬으니
lru_buffer_manager에서 해준것과 동일하게
vanilla_buffer_manager에도 get_hit_ratio와
print_status 함수를 작성해주었다
함수는 이렇게 작성했고
여기서 윗부분에 refCnt와 hitCnt가
각각 증가하도록 해주었다
그다음에 try catch문 부분 주석처리하고
다시 test를 실행시켰다
이런식으로 이쁘게 출력이 되는 것을 확인할 수 있었다
Hit Ratio는 33.33이 나왔다
이제 LRU로 테스트를 진행해보자
pBuffMgrType을 lru로 바꾸고 실행시켜줬는데 ..
아앗..
대충 아무거나 print 찍히게 해봤는데
가장 처음 pin부터 에러가 뜬 것을 확인할 수 있었다..
아까 봤던 에러와 동일해서
try_to_pin 부분에 buffer를 못찾는지 봤더니
역시나 사용가능한 buffer를 못찾는 것을 확인할 수 있었다
이 함수에 들어가서 코드를 확인해보니
맨 처음에 unpinnedList에 아무것도 안넣어주므로
당연히 list가 empty라서 nullptr을 반환한다는 것을 깨달았다
따라서 lru_buffer_manger 초기화 할 때
unpinnedList와 unpinnedBufferMap에
현재 존재하는 buff를 다 넣어주도록 수정하였다
그런 다음 재도전..
에러는 안뜨는데 결과가..
..?
ㅋㅋㅋㅋ
-1은 뭐냐
그 numAvailable--을 해줄 때
이전에 pin인지 unpin인지 여부를 확인안하고
무조건 --해줘서 그런 것 같은데
일단 저건 중요한게 아니라서 넘어가보도록 하겠다
제대로 실행이 되고있는건지 잘 모르겠어서
중간중간에 print_status를 계속 넣어봤다
이런식으로 unpin 하고 pin 할때마다 출력시켰더니
결과는 정확한 것을 확인할 수 있었다
gpt한테 부탁해서 lru와 vanilla의 차이를 극명하게 볼 수 있는
test case를 작성해달라고 부탁했다
그래서 test code를 아래와 같이 작성해보았다
namespace simpledb {
TEST(buffer, buffermanager_test) {
simpledb db("buffermgrtest", 400, 3, "lru");
buffer_manager &bM = db.buffer_mgr();
std::string testFile = "testfile";
std::vector<block_id> pattern = {
block_id(testFile, 0),
block_id(testFile, 1),
block_id(testFile, 2),
block_id(testFile, 0),
block_id(testFile, 1),
block_id(testFile, 2),
block_id(testFile, 0),
block_id(testFile, 1),
block_id(testFile, 2),
};
std::unordered_map<int, buffer *> activeBuffers;
for (size_t i = 0; i < pattern.size(); ++i) {
try {
buffer *buf = bM.pin(pattern[i]);
activeBuffers[i] = buf;
// 바로 unpin해서 LRU에 들어가게
bM.unpin(buf);
} catch (std::exception &e) {
std::cout << "Exception: " << e.what() << std::endl;
}
}
bM.print_status();
std::cout << "Final Hit Ratio: " << std::fixed << std::setprecision(2)
<< bM.get_hit_ratio() << "%" << std::endl;
}
} // namespace simpledb
block_id에는 pattern이 있고
0,1,2의 순서대로 접근한다
LRU의 핵심은 가장 오래 사용되지 않은 buffer를 교체한다는 점이다
따라서 저 pattern대로 pin과 unpin을 수행했을 때
가장 처음 0, 1, 2는 최초이므로
cold miss가 발생해서 miss가 뜨게되고
0, 1, 2가 끝나게 되면 unpinnedList에는 {0, 1, 2}가 담겨있게된다
LRU에서는 가장 오래 사용되지 않는 것만 교체하기 때문에
0, 1, 2가 그대로 남아있는 것이다
그럼 그 이후로 계속해서 0, 1, 2를 access 했을 때
buffer cache에 0, 1, 2가 다 남아있으니 hit이 발생하게 된다
따라서 전체 ref가 9번 중에서
처음 3번의 cold miss를 제외한 6번이
다 hit이 뜨므로 hit ratio는 66.67%가 나오게 된다
for loop 하나하나에서 status를 print하게해서 분석해보자
가장 처음의 0, 1, 2에 access 할 때이다
cold miss가 발생해서 hit ratio는 전부다 0.00이지만
buffer cache에 LRU 순서로 저장되어있고
access 순서로 계속해서 queue 구조로 밀리는 것을 볼 수 있다
그런 다음 그 이후의 status이다
buffer cache에서는 LRU 순서만 바뀌지
block id 자체가 변하지 않는다
따라서 0, 1, 2가 계속해서 남아있기 때문에
이후의 모든 접근은 다 hit이 되고
hit ratio가 계속해서 증가하는 것을 확인할 수 있다
따라서 최종적으로는 66.67%가 나오고 종료되는 것을 볼 수 있다
그럼 같은 test case에서 vanilla로 해보자
최초 0, 1, 2 일때의 access이다
pin을 해준다음 바로 unpin을 해주기 때문에
순서대로 계속해서 unpin이 되는 것을 확인할 수 있지만
vanilla의 경우 그냥 loop로 순회하다가
가장 처음 unpin인것만 가져오게되므로
계속해서 buffer 0만 가져와서 사용하게 되는 것이다
따라서 절대 Hit이 날 수가 없는 구조가 되는 것이다
따라서 9번 모두 수행해도
최종적으로 단 한번의 hit도 경험하지못한채(?)
테스트가 종료되게된다
이렇게 simpleDB 코드를 활용해서
buffermanger에서의 LRU 알고리즘을 직접 구현해보고
아무것도 하지 않는 vanilla와 LRU에서의
hit ratio 차이를 직접 실험해서 살펴보았다
최근 시스템 프로그래밍과 DB강의를 동시에 듣고있는데
두 강의 모두에서 정말 많이 강조하는게 바로 cache hit이다
cache에서 miss가 뜰 경우 penalty가 굉장히 크기 때문에
cache hit은 컴퓨터 프로그램에서 성능을 좌지우지하는
정말 중요한 요소 중에 하나라고한다
이런게 어떤방식으로 구체적으로 구현이 되고
정확하게 어떻게 차이가 나는지 피부에 와닿지는 못했는데
이렇게 직접 맨땅에 헤딩하며 구현해보니 이해가 훨씬 깊어진 것 같다
이번 과제는 여기서 마무리-!