InnoDB 버퍼풀의 LRU 구현해보기 !

버퍼풀

디스크에 접근해 데이터를 가져오는것은 메모리에 접근해 데이터를 가져오는것보다 비용이 큰 작업입니다.

버퍼풀은 InnoDB를 사용했을때 디스크가 아닌 메모리에서 데이터를 가져올 수 있도록, 데이터를 보관하고 있는 메모리 공간입니다.

LRU

항상 메모리에서 데이터를 가져올 수 있다면 좋겠지만, 메모리공간은 디스크보다 비용이 높고, 용량이 제한적이라 모든 데이터를 메모리에 가지고 있기 어렵습니다.

따라서 DB는 전체 데이터의 일부분만 캐시해 관리합니다. 이때 어떤 데이터를 메모리에 유지할지 결정하기 위해 다양한 캐시 알고리즘이 사용됩니다.

Least Recently Used(LRU)는 그러한 알고리즘 중 하나로, 가장 오래 사용되지 않은 데이터가 가까운 미래에도 사용될 가능성이 낮다는 가정을 해, 이러한 데이터를 캐시에서 제거하는 전략입니다. 이 방식으로 캐시는 최근에 자주 사용되는 데이터로 유지되고, 데이터 접근시간이 최적화됩니다.

변형된 LRU

InnoDB 버퍼풀이 선택한 캐시 알고리즘은 변형된 LRU입니다.

LRU방식을 그대로 사용하지 않는 이유는 DB에서 전체스캔을 할 경우 모든 캐시데이터가 바뀌기 때문입니다.

그렇기때문에 단순히 최근에 사용된 데이터가 미래에 사용될 가능성이 높다고 생각하는것이 아니고, 버퍼풀에 있는 데이터가 한번더 사용되었을때 미래에 사용될 가능성이 높다고 판단합니다.

InnoDB 버퍼풀의 LRU리스트 실제 구현은 어떻게 되어있나요?

위 요구사항을 지키기 위해, 버퍼풀의 LRU리스트는 아래의 그림과 같이 구현되어 있습니다.

쿼리한 페이지가 LRU리스트에 없다면, 디스크에서 읽어 5/8 지점에 추가합니다.

쿼리한 페이지가 LRU리스트에 있다면 new Sublist의 head로 이동시킵니다.

LRU리스트에서 페이지를 삭제해야한다면 OldSublist의 tail을 삭제합니다.

왜 RealMySQL 8.0에서는 버퍼풀의 LRU리스트를 MRU와 LRU 리스트를 사용해 구현했다고 되어있나요?

MRU는 가장 최근에 사용한 페이지를 교체하는 알고리즘인데 버퍼풀 LRU 리스트에서는 가장 최근에 사용한 페이지를 교체하지 않는데, 왜 MRU를 사용했다고 하는거지? 라는 궁금점이 있었습니다.

이 질문에 대해 제가 생각한 해답은 아래와 같습니다.

New Sublist의 목표는 버퍼풀내의 가장 최근에 사용한 페이지를 유지하는것입니다. 이 목표를 달성하기 위해 MRU개념을 사용했다. 또 Old Sublist의 목표는 가장 최근에 사용하지 않은 페이지를 인식하는것입니다. 이 목표를 달성하기위해 LRU개념을 사용했다.

MRU가 페이지 교체 알고리즘이긴 하지만, 이것보다는 MRU라는 단어 뜻자체에 집중하면 이해가 되는 대목이라고 생각합니다.

버퍼풀의 LRU리스트를 구현해보자!

LRU리스트의 동작에 대해 구체적으로 떠오르지 않는 부분이 있어 실제로 구현해보기로 했습니다.

제가 생각한 궁금증은 다음과 같습니다.

• LRU리스트내에 이미 데이터가 있는지 어떻게 판단할까?
• 데이터를 삽입하며 midpoint를 전체 리스트의 5/8지점으로 유지하려면 어떻게 해야할까?

요구사항 정하기

1. 변형된 LRU리스트의 동작에 집중해 구현한다.
2. 버퍼풀의 구성요소중 LRU리스트이외의 다른 요소는 고려하지 않는다.

구현하기

• LRU리스트의 기본적인 자료구조로 양방향 리스트를 사용했습니다.
  • 특수하게 5/8 지점에서 insert하는것을 제외하면, head와 tail에만 접근하기 때문입니다.
• LRU리스트의 구현방법으로 리스트 두개를 사용했습니다.
  • 리스트 하나로 구현했을때 midpoint의 위치를 5/8로 맞추기 위해 반복해서 이동하는게 어렵다고 생각해, MRU와 LRU를 내부적으로 다른 리스트를 사용했습니다.
• LRU리스트에 들어가는 값은 페이지번호만 넣었습니다.
  • 페이지 번호 자체가 페이지의 주소이고 주소를 따라가면 값을 찾을수 있다고 생각해 값은 넣지 않았습니다.
• 자료구조를 hashmap도 사용했습니다.
  • 페이지 번호가 주어졌을때, LRU리스트에서 이미 관리하고 있는 페이지인지, 아닌지를 판단해야했습니다.
  • 이때 리스트를 순회하지않고 빠르게 확인하고 싶어, cpp의 hashmap인 unordered_map을 사용해서 더 나은 시간복잡도로 찾을 수 있게 작성했습니다.
• 아래는 제가 작성한 소스코드입니다. 주요로직에 대해 일부분만 작성하였고 전체코드는 여기서 볼 수 있습니다.

// 페이지 푸시
  void push(int pageNumber) {
    // 페이지가 리스트에 이미 있다면
    if (_existPage(pageNumber)) {
      // 해당 페이지를 newList의 head로 올림
      auto it = _pageMap.find(pageNumber);
      if (it->second.second == OLDLIST)
        _oldList.erase(it->second.first);
      else
        _newList.erase(it->second.first);
      _newList.push_front(pageNumber);
      // map에 페이지숫자와 리스트의 위치, 리스트의 종류를 매핑시킨다.
      _pageMap[pageNumber] =
          pair<list<int>::iterator, int>(_newList.begin(), NEWLIST);
      // newList가 과다해진 상황에 대비해 oldList newList 균형 맞춤
      _balanceList();
      return;
    }
    // 페이지가 리스트에 없는 경우
    // oldList에 추가
    _oldList.push_front(pageNumber);
    // map에 페이지숫자와 리스트의 위치, 리스트의 종류를 매핑시킨다.
    _pageMap[pageNumber] =
        pair<list<int>::iterator, int>(_oldList.begin(), OLDLIST);
  }

void _balanceList() {
    // 만약 newList크기 / oldList크기가 5/8보다 크다면 조정
    if ((double)_newList.size() / (double)_oldList.size() > midPoint) {
      int num = _newList.back();
      _newList.pop_back();
      _oldList.push_front(num);
    }
  }

궁금증에 대한 대답

Q. LRU리스트내에 이미 데이터가 있는지 어떻게 판단할까?

A. 이를 리스트를 사용했을때 바로 판단하기 어렵기때문에, 효율적인 동작을 위해 hashmap, map등 자료구조를 하나 더 사용해야한다.

Q. 데이터를 삽입하며 midpoint를 전체 리스트의 5/8지점으로 유지하려면 어떻게 해야할까?

A. 삽입 이후, 데이터를 정규화하는 과정을 거쳐야한다. 그리고 이 과정은 구현에 따라 달라진다.

마무리하며

RealMySQL을 읽으며 버퍼풀에 대한 설명이 어려워서 시작한 공부입니다. LRU, MRU, 페이지 등 용어 하나하나가 어렵게 다가와 이해하기 힘들었습니다.

하지만 막상 구현해보니 어려운 알고리즘이나 원리는 전혀 아니었습니다. 어려움을 느끼는 이유가 활자로만 받아들이고 실제로 돌아가는 방식을 충분히 고민하지 않아 그렇다는것을 알 수 있었습니다. 어려울때는 구현해보기! 라는 해결방식을 얻을 수 있었던 시간이었습니다.

참고자료

https://dev.mysql.com/doc/refman/8.0/en/innodb-performance-midpoint_insertion.html

https://minervadb.xyz/how-is-cache-eviction-implemented-in-innodb/

https://omty.tistory.com/58

https://www.geeksforgeeks.org/lru-cache-implementation/