[database] DBMS와 Disk, Buffer Management(LRU)

본 게시글은

서울대학교 데이터사이언스대학원 이상원 교수님의

데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을

학습을 목적으로 재구성하였습니다

---

이번 시간은 DBMS와 관련되어있는

전반적인 디스크 메모리에 관한 내용들

그리고 DBMS의 DRAM 역할을 하는 buffer cache의

management에 대해서 배운다

 

 

우선 RAID라는 개념에 대해 알아보자

Redundant Arrays of Independent Disk의 약자인데

싸고 작은 독립적인 디스크들을 여러개 모아서

하나의 큰 space disk처럼 사용하는 개념이다

 

예전에는 디스크를 1개만 사용했고

이를 Single Large Expensive Disk라고 해서

SLED라고 불렀다

 

하지만 80년대 중반에

작고 싼 디크스들을 모아서 마치 하나의 큰 디스크처럼

보여지게 하는 것이 더 경제적이고 빠르다는

RAID 개념이 등장하게 되었다

 

위 사진이 실제로 RAID를 지원하는 카드라고 한다

물리적으로는 여러 개의 작은 디스크들이 모여있는 것이지만

컴퓨터에게는 실제 그냥 하나의 큰 디스크가 있는 것처럼 보이게 하는데

이를 하드웨어에 RAID card 형태로 제공해준다

 

가격과 성능 측면에서 RAID는

SLED에 비해 훨씬 이득이라고 한다

 

 

그렇다면 RAID는 구체적으로 어떻게 동작할까

우선 striping이 있다

테이터를 잘라서 striping 방식으로 분산시키는 것이다

그런 다음 각각의 디스크에서 한 개씩 읽으면 된다

이렇게 하게되면 bandwidth도 좋아지고

IOPS도 높아지게 된다

 

두번째는 redundancy이다

싼 디스크를 붙여서 데이터를 복제하는 방식으로

redundant하게 관리를 한다고 한다

independent한 디스크에 똑같은 데이터를 copy하는 것인데

이러한 방식으로 하면 시스템 동작의 안정성을 제공한다고한다

 

따라서 RAID의 장점은

1. bandwidth 좋아짐

2. IPOS 높아짐

3. redundancy를 통한 안정성

크게 이 3가지가 된다

 

이제 Disk Space에 대해서 간단하게 배워보자

 

 

DBMS의 입장에서는 가장 밑단에 위치하고있다

space를 allocate하고 de-allocate하는 역할을 해주는데

disk space manager가 이러한 역할을 해줌으로서

윗단에서는 disk space가 어디에 있고

얼마나 비었고 등을 따로 확인해줄 필요가 없다

 

이제 오늘 배울 내용의 핵심

DBMS의 DRAM인

buffer management이다

 

 

OLTP를 대표하는 TPC-C 예제이다

이게 갑자기 나온 이유는

이후에 과제로 TPC-C benchmark를 이용해서

DBMS transaction 수행시

CPU utilization, cache hit ratio등

성능 측정하는 과제가(...) 나갈 것이기 때문이다

 

아무튼 database는 결국 transactio들의 집합이고

이는 개별 sql문들의 연속되어있는 집합이라는 뜻이다

그리고 보통 TPC같은 OLTP 계열은

index기반으로 access를 하게 된다

 

 

 

DB에서 어떤 작업을 수행하게 되면

수많은 transaction들이 동시에 달라붙어서

각각 transaction들은 자신들의 sql문들을 수행시키기 된다

결국 DB 입장에서는 n개의 transaction들이

active하게 돌아가는 것이다

 

그리고 이전 수업시간에서 계속 강조했듯이

sql 수행하는데 있어서 모든 데이터의 기본 단위는 page이다

이 page 단위를 기반으로 read write 연산을 하게 된다

 

그렇다면 정확하게 Database Buffer가 무엇이냐

교수님께서는 계속 DB의 DRAM..이라고 하셨는데

사실 도대체 DB의 DRAM이 정확하게 뭔지 몰라서 따로 찾아봤다

따라서 gpt에게 질문을 한 결과

실제 컴퓨터의 물리적 DRAM 영역에 존재하는 메모리지만

DBMS가 소프트웨어적으로 따로 관리하는 방식으로 동작한다고한다

운영체제는 이 영역을 그냥 일반 메모리로 인식하지만

DBMS가 그 위에 이 메모리를 관리하는 캐시 구조를 만들어 운용한다고한다

흔히 buffer pool이라는 용어로도 불린다고한다

 

아무튼 결론은 실제 컴퓨터 DRAM에 존재하는 메모리지만

DBMS가 따로 관리하는 cache 영역이라는 뜻!

 

DBMS 전용같은 느낌인 듯하지만

어쨋든 cache는 cache라서

우리가 흔히 생각하는 cache와 유사한 구조로 작동한다

어떤 page를 읽기를 원하는데

그게 buffer cache에 있으면 thank you

아니면 disk에서 읽어와야하는 것이고

disk에 접근하려면 IO시간이 오래걸리고

그 시간동안 CPU는 대기해야해서 놀게된다

 

 

DBMS buffer cache의 아주 간단한 구조와

동작 원리를 한 번 살펴보자

 

transaction의 sql들은 CPU에서 동작한다

그래서 우리의 목표는 buffer pool의

hit ratio를 높이는 것이다

 

위 buffer pool의 조그만 사각형들은 page단위이고

지금 노란색, 보라색, 파란색 데이터들이 cache에 올라와있다

따라서 우리의 CPU가 파란색, 노란색, 보라색 데이터들을 필요로하면

이미 buffer cache에 있으므로 hit!이 되어서

disk에 접근할 필요없이 바로 CPU가 가져다 쓸 수 있는 것인데

만약 CPU가 빨간색 데이터를 필요로한다?

그런데 빨간색은 DB disk에만 있고 buffer pool에 존재하지않는다

그렇게 되면 cache miss가 나게 되고 disk IO가 발생하게 된다

 

일반 cache와 마찬가지로 buffer pool은 DRAM이기 때문에

공간 제한이 있고 이는 금방 차버리게 된다

따라서 새로운 데이터를 쓰려고 하는데 buffer pool 공간이 다 차게되면

그 중에 하나를 빼서 빈 자리를 만들고 거기에 새로 쓰는 작업을 수행해야한다

그렇게 되면 기존에 어떤 데이터를 빼야할까?

이게 cache를 관리하는데에 있어서 아주아주 중요한 issue가 된다

 

교체되는 페이지, 즉 evict page를 어떤 것으로 할까가

매우 중요한 issue가 되고

이러한 작업을 일컫는 말이

buffer replacement policy이다

 

우리의 disk가 보통 1TB의 용량을 갖고있다고한다면

DRAM buffer cache는 보통 10% 수준이라

100G가 정도가 된다고 한다

 

그렇다면 이러한 buffer cache가 동작하는 원리가 뭘까?

이 세상에서의 모든 data는 uniform하게 접근하지 않는다

이게 무슨 뜻일까?

인기 상품은 늘 접근이 많아지게 되고 더 많이 팔리게 되고

인기 없는 상품은 여전히 인기가 없게 되는 것이다

데이터의 접근성에는 편향성이 반드시 존재하게 되고

이것은 자연의 법칙이다

 

computer science의 세계에서는 이러한 접근의 편향성을

locality, 즉 지역성이라고 부른다

크게 공간지역성과 시간지역성이 있고

이러한 지역성 때문에 buffer cache는

아주 효과적으로 동작할 수 있는 것이다

 

이 지역성과 공간지역성, 시간지역성의 개념이 더 궁금하다면

본 블로그의 system programming -> cache memory편을

읽어보길바란다 (ㅎㅎ..)

 

아무튼 따라서 보통 상품을 판매하는 기업들도

인기가 많은 상품들은 이미 DRAM buffer에 올려놓고 운영하며

이렇게 하면 hit ratio를 굉장히 높일 수 있다

 

buffer pool에 대해서 조금 더 구체적으로 살펴보자

위에서 봤던 pool의 사각형들을

frame이라고 부른다

 

따라서 frame number가 있고,

몇 번째 page가 지금 frame에 있는지를 나타내는 pageid,

몇 개의 transaction에서 나를 접근하고 있는지 말하는 pin_cnt,

dirty(update)가 되었는지의 flag인 dirty 등이

buffer pool information table에 존재한다

 

만약에 requested page가 pool에 존재하지 않는다면

어떤 frame을 제거하고 새로운 page를 올릴지 결정해야한다

그런데 이 기존의 frame이 clean이면 그냥 교체해도 괜찮은데

dirty flag가 켜져있는 경우 단순히 교체할 수 없게 된다

 

왜냐하면 dirty의 경우 이전에 update가 된 frame이라는 뜻으로

아직 disk까지 update된 데이터가 반영이 되지않았기 때문에

함부로 교체할 수가 없는 것이다

 

따라서 만약 교체하고자하는 frame이 dirty이면

disk에 접근해서 데이터를 쓴 다음 교체하게 되는 것이고

불필요한 IO가 많이 발생하게 된다

 

또한 pin_cnt가 0이어야지 해당 frame을 교체할 수 있다

 

 

어떤 transaction이 buffer pool에서 어떤 page를 읽어오게되면

해당 페이지는 사용중이라는 의미에서 고정(pin)이 되게 된다

따라서 만약 해당 transaction이 해당 page 사용이 끝났다면

반드시 unpin을 시켜줘야한다

또한, 작업이 끝나게 되면 만약 해당 페이지를 수정했는데

아직 디스크에는 쓰지 않았다면

dirty bit를 1로 변경해줘야한다

 

앞에서 설명했듯이 해당 page가 몇 개의 transaction에 의해서

사용되고 있는지 체크하는 것이 pin_cnt이다

따라서 만약에 이 pin_cnt가 높으면

많은 transcation에서 해당 page를 필요로 한다는 뜻이다

이를 이용해서 buffer replacement policy를 세운 것이 바로

LRU(Least Recently Used(Unfixed))이다

 

이는 어떤 페이지를 교체할지를 찾는

evict page를 찾는 기법으로

어떤 page를 unpin 시키면

걔의 pin_cnt가 0이 되는데

그 timestamp를 보고 가장 오래전에 unpin이 된 page를 제거하는 기법이다

 

 

 

LRU의 pseudo code이다

 

 

요청한 전체 페이지에서 몇 개가 hit인지의 비율을

hit ratio라고 한다

하나의 page에 대한 miss는 1개 또는 2개의 disk IO가 발생한다고 한다

 

hit ratio는 최소 95%~97%로 하는 것이 좋으며

replacement policy에 따라서도

hit ratio 차이가 많이 나기 때문에 중요하다고 한다

 

 

우리가 앞에서 배운건 LRU였지만

FIFO, LRU, MRU, LFU같은

다양한 Replacement policy가 있다

 

그렇다면 예를 들어서

A를 사용했더니 hit ratio가 90%가 됐는데

B를 썼더니 91%가 됐다고 한다

그렇다면 hit ratio가 1%가 좋아진 것일까?

아니면 10%가 좋아진 것일까?

 

이게 hit ratio의 입장에서는 1%가 좋아진 것이지만

miss ratio의 입장에서는 10%가 좋아진 것이라고 한다

 

 

 

가장 popular하게 사용되는 정책은 앞에서 봤던 LRU이다

이는 시간지역성의 원리를 사용한 것으로

가장 최근에 사용되지 않았다면

앞으로도 사용되지 않을 확률이 높다는 것에서 기반한 것이다

 

아무튼 이러한 이유때문에 LRU는 잘 동작하는

버퍼 정책 중 하나이다

 

그렇다면 실제로 DRAM에서는 이 LRU를 어떻게 구현하고 있을까?

앞에서는 timestamp를 확인해서 구현한다고 했는데

사실상 이것도 완벽하게 구현하기는 쉽지는 않다고 한다

 

 

아주 simple하게 LRU를 구현한 것을 살펴보자

 

각 사각형들은 page frame이고

이 frame들을 양방향 linked-list로 구현했다

 

예를 들어서 9번 page가 access 된다고 가정하다

그럼 9번을 List의 가장 앞쪽으로 보낸다

그런식으로 계속 반복하다 보면

결국 tail에 있는 page가 가장 덜 접근한 page가 되는 것이다

따라서 linked list 형태로 구현하는 것이

가장 일반적인 형태의 LRU가 된다

 

하지만 9번을 head로 옮긴다는 뜻은

각각의 pointer들을 다 바꿔줘야한다는 뜻이다

그래서 9번을 옮기는 순간

기존에 9번을 가리키고 있던 9번 앞뒤의 포인터들

그리고 새로 가면서 연결되어야할 포인터들 해서

총 4개의 pointer를 바꿔줘야한다

그런데 이게 어떤 page가 hit이 될때마다 바꿔줘야하는데

이게 CPU로 동작하면 금방되긴 하지만

너무 자주 발생하기 때문에 그만큼 overhead가 발생하는 일이라고 한다

 

 

오른쪽 위에 있는 그래프가

DB size에 대한 DRAM buffer cache의 size를 나타낸다고 한다

그리고 오른쪽 아래는 Hit ratio를 나타내는 그래프이다

 

우리가 생각하기에 그럼 buffer cache size를 올리면

무조건 hit ratio가 올라가는게 아닐까라고 생각할 수 있다

이게 어느정도는 맞는 말이다

당연히 buffer cache size를 늘리면 hit ratio가 올라가지만

이 hit ratio가 동일한 비율로 계속 증가하지는 않는다

초반에 확 ratio가 올라갔다가 계속해서 size가 증가할수록

hit ratio의 증가 기울기는 작아지게 된다

 

또한 우리가 사용할 수 있는 모든 data들을 전부다

cache에 올려놓지 않는 이상

hit ratio는 절대 100%가 발생할 수 없다

 

 

또한 그렇다면 DB의 transaction의 문제가

온전히 DRAM 혹은 Disk IO의 문제일까?

CPU에서 발생하는 문제도 있다

 

오직 CPU 때문에 발생하는 문제들이 있고

이를 CPU Bound라고 부른다고 한다

 

따라서 가장 좋은 상태는 balanced 되어있는 형태라고한다

 

 

 

2000년대 후반 정도의 디스크 현황을 잠깐 살펴보자

위는 IBM에서 나온 어떤 시스템의 스펙이라고 한다

OLTP를 돌리는 시스템 구성을 IBM에서 개발했는데

총 비용이 35M불이 된다

 

그런데 자세히 살펴보면

HW, SW가 총 1400불인데

storage가 2000불이 된다

따라서 가격의 절반 이상이 storage에서 잡아먹힌 것이다

 

해당 시스템에서는 용랑 73G의

아주 작으면서 초당 IO가 가장 빠른

10000개의 disk를 사용했다고 한다

따라서 전체 storage는 700TB정도가 나왔다고한다

이렇게 구성하는 이유는 시스템을 balanced로 만들기 위해서라고한다

 

 

 

무어의 법칙..?이라는게 있다고 한다

이게 무슨 법칙이냐면

내가 어떤 컴퓨팅 시스템을 구매했는데

18개월이 지나면 같은 가격을 주고 살 수 있는

컴퓨팅 시스템의 파워는 2배가 된다고 한다

즉 컴퓨팅 시스템의 빠른 발전속도를 말하는 법칙인 듯 했다

 

예를 들어서 내가 옛날에 10000개의 디스크를 사서 100만 IO를 만들었는데

18개월 지나면 동일한 가격으로 200만 IO를 만들 수 있다는 것이다

 

아무튼 이런식의 문제 때문에 IO를

굉장히 비싼 돈 주고 살 수 밖에 없는 구조가 되었고

이 당시에 DRAM 가격이 굉장히 급하게 떨어지면서

DRAM을 늘려서 IO를 없애자! 해서

급속도로 발전했던게 main memory DB

즉, in-memory DBMS라고 한다

 

 

또한 다행히도 그 무렵에 Flash SSD가 나왔다고한다

하드디스크는 초당 200 IO가 최대인데

FlashSSD는 초당 100만 IO도 나올 수 있다

따라서 IO와 관련된 문제를

굉장히 해소해주었다

(이에따라 in-memory DB도 급락..했다고한다)

 

 

 

page size에 대한 내용이다

계속 말했듯이

block = Disk IO의 unit인데

일반적으로 DBMS에서는 8KB를 사용한다고 한다

시간나면 천천히 읽어보면 좋다고 하셨다

 

 

 

main memory DB와 flashSSD를 사용한 DBM?

교수님의 개인적인 생각이라고 하신다

 

교수님의 개인적인 생각으로는

flashSSD의 등장으로 인해

flashSSD를 사용한 DBMS가 대세가 된 것 같다고 하셨다

 

 

DB분야의 디스크와 당시 hot 했던 회사들에 대한 간단한 설명이다

 

2000년대의 DB분야에서는 EMC나 SEAGATE와 같은

하드디스크 회사들이 돈을 많이 벌었다고한다

하지만 과도기적인 2000~2010년에는

main memoryDB가 성공을 이루면서

SAPHANA, ALTIBASE같은 회사들도 인기가 있었다

 

그러다가 2010년도에는 SSD가 HDD를 능가하면서

하이닉스와 삼성의 시대가 도래하게 되었다

 

또한 교수님께서는 현재는 DB를 떠나 GenAI의 시대로 바뀌면서

GPU의 시대로 들어가게 되었다고 하셨다..

 

 

NVIDA의 컴퓨팅 파워는 계속해서 증가하고 있지만

메모리가 이걸 못따라가고있다고 한다

KV cache와 DRAM buffer와 같은 기능적인 부분들도

NVIDIA에서 따라가야한다고 하셨다

따라서 이런 부분을 연구적으로 진행해야한다고 하셨다

 

 

마지막으로

5 min rule과 pareto's law를 잠깐만 살펴보고 끝내자

 

5 min rule이란

어떤 페이지를 DRAM에 상주시키는 것이 좋을까

아니면 disk에 두고있다가 serving하는 것이 좋을까에 대한

연구를 진행한 내용이다

따라서 어떤 데이터를 어디에다가 위치시키는 것이

좋을까 하는 rule이다

 

이를 1987년도에 Jim Gray 박사가 관찰하였는데

그 당시의 DRAM 가격 + 하드디스크 가격 + Disk IO 등

기술적인 요소들을 고려해서

어떤 page가 5분보다 자주 access되면

DRAM에다 저장하는 것이 더 경제적이라는 결론이 나왔다고 한다

 

두 번째로 파레토 법칙이다

이는 이탈리아의 경제학자가 만든 것인데

인간 세계의 법칙에 대한 내용이다

80/20 rule에 관한 내용인다

보통 80%에 대한 것은 20%가 담당한다는 내용으로

대표적인 예시로는

백화점에서 20%의 고객이 80%의 순이익을 형성한다는 것이 있다

 

이 파레토 법칙은

이러한 자연의 법칙으로 인해서

buffer manager가 잘 작동할 수 있다고한다