03. Storage (Part 1 - Page, Slot)

서울대학교 데이터사이언스대학원 정형수 교수님의 "데이터사이언스 응용을 위한 빅데이터 및 지식 관리 시스템" 강의를 필기한 내용입니다.

• 목차

Overview §

• File: named storage abstraction
  • 이놈을 관리하는 것은 file system
• DBMS 에서는 table 을 logical file 들로 저장하고 여기에는 page 들이 들어있으며 각각은 tuple (record) 들로 구성되어 있다.
• Disk manager 는 이 logical file 들을 관리하고, “page” API 로 위의 계층에 노출한다.
  • 바로 위의 Buffer manager 에서는 이 page 들에 대한 in-memory 상태를 관리한다.

Disk-based DBMS §

• Disk-base architecture: 일반적으로는 DBMS 는 disk 를 저장장치로 삼는다.
  • 물론 in-memory 도 있지만 이것은 관심범위가 아님.
  • 이때 disk 와 관련된 몇가지 정보들을 알아보면

Storage hierarchy §

• Volatile: random access, byte-addressable
• Non-volatile: sequential access, block addr
  • 이놈은 latency 가 크니까 한번에 큰 단위 (block) 으로 가져와서 bandwidth 를 늘려 latency 를 hiding 하게 된다.
    • 따라서 한번에 여러 page 들을 allocate 하게 되고, 이 단위는 extent 라고 부른다.
  • 그리고 random 보다는 sequential 이 더 빠르다.
    • 따라서 DBMS 는 최대한 random access 를 줄이고 sequential access 를 늘리려고 한다.

MMAP? §

• OS 의 MMAP 을 활용하지는 않는다고 한다.
• MMAP 을 사용하면 memory 접근하는 것처럼 file 저장이 가능하고 replacement 도 OS 이 해주니까 좋을 것 같을 수도 있다.
  • 또한 여러 thread 가 접근하는 상황에서 MMAP 을 사용하면 page fault stall 도 줄일 수 있다.
• 하지만 사용하지 않는다: OS 는 DBMS 에서 뭐하는지 모르기 때문.
  • OS 가 메모리 부족하다고 evict 시켜버렸는데 DBMS 에서는 지금 당장 필요한 놈인 상황이 발생하는 등의 문제가 생길 수 있다.
  • 그리고 당장은 잘 이해되진 않지만 이런 문제가있을 수 있다고 한다:
    • 그리고 dirty page 를 OS 마음대로 evict 할 수 있기 때문에 transaction safety 에도 문제가 생길 수 있고
    • DBMS 가 직접 page 를 관리하지 못하기 때문에 어떤 page 가 memory 에 있는지도 모르고 page fault 에 stall 되는 등의 문제가 있댄다.
• 이런 문제를 해결하기 위해 madvise, msync, mlock 와 같은 syscall 이 추가했지만 잘 안된다고 한다.
• 그래서 보통은 DBMS 가 직접 관리한다고 한다.
  • O_DIRECT 로 가져올 것 같지만, MySQL 이나 PostgreSQL 이나 기본적으로는 사용하지 않고 있었다.
  • 왜인지는 모르겠지만 뭐 그럴만한 이유가 있겠지

File storage §

• 보통 DBMS 는 여러 file 들로 data 를 저장하는데, 일반적으로는 자신들이 사용하기 편한 file format (proprietary format) 을 이용한다.
• 참고로 block interface 나 custom filesystem 를 옛날에는 사용했는데, 요즘은 사용하지 않는다고 한다.
  • 다만 cloud provider 에서는 아직도 사용한다.
  • 어차피 노드를 DBaaS 하나만 사용하고 block interface 를 사용하는게 filesystem 끼는 것보다 더 빠르니까.

Storage (disk) manager §

• 결론부터 말해보자면, Storage manager (혹은 disk manager) 는 DBMS 에서 사용하는 file 들을 관리한다.
• File 들은 page 단위로 쪼개지고 (pagination), page 에는 tuple 이 slot 이라는 것으로 관리된다.
• 여기서 page_id 와 slot_id 는 모두 logical address 이고 이것에 대한 physical location 과의 mapping 을 관리해서 저 storage manager 의 핵심 역할이라고 볼 수 있다.
• 따라서 어떤 tuple (record) 는 (filename + page_id + slot_id) 으로 특정지을 수 있으며 이것을 Record ID (RID) 라고 한다.
• 그럼 저 page, slot 이 뭔지, 어떻게 생겼는지, 어떻게 이것으로 해당 tuple 을 찾아가는지 등을 알아보자.

Page §

• Page 는 고정 크기의 data block 이다.
  • 이 page size 는 configurable 하다: Psql 에서는 8k, MySQL 에서는 16k
    • PostgreSQL 에서는 hugepage 로 2m 까지 늘릴 수 있다.
• 그리고 이건 data (tuple) 뿐 아니라, 여러 metadata 나 index, log 도 저장하는 단위로 사용된다.
• Page 는 unique logical ID (즉, page ID) 를 할당 받고 상위 layer 에서는 이것으로 page 에 접근하게 한다.
• 그리고 disk manager 는 이 page ID 에 대한 page 가 disk 상에 어디에 있는지 (physical location) 을 mapping 하여 table 로 갖고 있게 된다 (Indirection mapping table).
  • 이 정보는 중요하기 때문에 여러 copy 를 갖고있는다고 한다.
• 이렇게 해서 page 의 physical location 이 바뀌어도 상위 layer 에서는 이것을 알지 못하게 한다.
  • 즉, physical location 과 logical address space 를 indirection 하는 것.
  • Data (physical) independence 를 위해 indirection 을 하는 또 하나의 사례인 것이다.
• 근데 storage 에서 LBA 를 제공하는데 또 이렇게 abstraction 하는 이유는 무엇일까?
  • 일단 하나 생각나는 것은 cloud 나 distributed 에서는 필요할듯: remote node 를 찾아갈 필요가 있으니
  • 그리고 이 LBA 공간도 (위에서의 MMAP 과 비슷하게) DBMS 가 직접 관리하는게 아니다 보니 직접 관리하는 단위가 필요했을 듯

Heap file organization §

• File 에서 어떻게 page 들을 관리하는 지는 여러 종류가 있는데, 여기서는 Heap file organization 만 알아보자.
• 우선 heap file 은 page 들을 딱히 정렬해놓지 않는 (unordered collection of page) pagination 방법 이다.
  • Page 들도 정렬되어 있지 않고,
  • Page 안의 tuple 들도 정렬되어 있지 않다고 한다.
  • 즉, Heap 자료구조와는 거의 연관이 없는 용어인 것.
• Page ID 로 page 를 찾아갈 때는,
  • 일단 file 이 하나인 경우에는 그냥 page ID 를 file 내에서의 page index 로 사용할 수 있다고 한다.
    • 이 부분은 좀 이해가 안되긴 한다.
      • Heap file 은 정렬이 안되어 있다는데 이건 page ID 로 정렬된게 아닌건지?
      • Page index 를 page ID 로 쓸거면 indirection mapping table 은 왜 필요한지?
    • 어쨋든 이때는 page ID 에 page size 를 곱하면 file 내에서의 offset 이 나오기 때문에 그냥 슥 읽어가면 된다.
  • 그리고 file 이 여러개인 경우에는 해당 page ID 가 어떤 file 의 어느 page index 에 있는지 에 대한 mapping 이 필요하다.
    • 여기서도 이해 안되는 부분은:
      • 그럼 이 mapping 이 disk manager 가 관리하는 indirection mapping table 일까?
      • File 정보는 RID 에 들어있는데, 그럼 file 별로 page id address space 가 존재하는건가? 만약에 그렇다면, 이때도 위처럼 그냥 page ID 를 in-file offset 으로 계산해 내서 찾아가는 건가? 그리고 만약에 그렇다면, 왜 mapping table 이 필요한건가?
    • 어쨋든 이 mapping 을 확인한 뒤에는 위에서와 동일한 방법으로 page 를 찾아갈 수 있다.
• 그럼 이런 mapping 정보들과 더불어 free page 가 어디에 있는지를 관리해야 하는데, 관리하는 방법은 크게 두 종류가 있다.

• Linked list 방식
  • 여기에서는 file 의 맨 앞에 header page 가 있고, 여기에는 두 개의 pointer 가 담긴다.
    • Data page linked list 의 head, 그리고 free page linked list 의 head.
  • 그리고 각 page 들의 맨 앞에도 이런 두 개의 pointer 가 있어서 data page 의 경우에는 다음 data page 의 위치, free page 의 경우에는 다음 free page 의 위치가 담긴다.
  • 그리고 각 page 의 header 에 free slot (slot 이 뭔지는 뒤에 나온다) 에 대한 정보가 담긴다.

• Directory 방식
  • 일단 directory page 라는게 있는데, 이놈은 data page 가 어느 file 에 있는지에 대한 mapping 을 갖고 있다.
    • 아마 data page 에 대한 page id 와 filename + page index 의 mapping 을 저장하지 않을까.
  • 그리고 free (empty) page 들에 대한 정보, 그리고 page 별 free slot 의 개수도 여기에 저장된다고 한다.
• 당연히 linked list 보다는 directory 방식을 보통 사용한다.

Page header, slotted array §

• Page header 에는 page 내에서 slot 을 찾기 위한 metadata 가 들어있다.
• 일단 tuple 이 page 에 어떻게 저장되면 좋을 지 생각해 보자.
• 우선 그냥 tuple 을 sequential 하게 쭉 채울 수 있을 것이다.
  • 근데 이때는 delete 시에 이 공간에 대한 fragmentation 이 생기고 결국에는 compaction 을 해야 된다.
  • 따라서 이 방식은 잘 사용하지 않는다.

• 요즘 쓰는것은 slotted array 방식이다.
  • Page 에는 slot 들로 구성된 array 가 있고, slot 에는 각 tuple 의 starting point 와 size 를 저장한다.
  • 그럼 tuple 이 추가되면 slot 도 추가된다
    • Tuple 의 증가 방향과 slot 의 증가 방향은 반대로 구성되어 tuple 과 slot 이 증가되는 것을 고정 크기의 page 로 감당한다.
    • 보통 tuple 은 page 시작부터 채워지고, header 는 page 마지막에, slot 은 header 이후부터 성장하는 느낌으로 생각하면 된다.
  • 따라서 이 slot 또한 logical indirection 이라고 할 수 있다.
    • 즉, tuple 이 삭제되면 이후의 것들을 전부 땡기고
    • 위치가 변경된 tuple 들에 대해 slot 의 내용만 바꿔주면
    • Tuple 에 접근할 때는 그냥 이 slot 만 보고 접근하면 되기 때문에 이 tuple 이 여기저기 움직여도 접근을 위한 logical address 인 slot id 는 바꾸지 않아도 된다는 것.
• Page header 에 slot 들에 대한 metadata 가 저장되는데,
  • 가령 빈 slot 이나 사용중인 slot 의 개수라던지
  • 마지막 사용된 slot 에 대한 tuple 의 시작지점이라던지
    • 이것은 다음 slot 을 생성할 때 사용된다.
• 어떤 DBMS (가령 Oracle) 의 경우에는 self-contained page 를 사용한다고 한다.
  • 이 말은 page header 에 table 의 schema 와 같은 정보들까지 다 들어있는 것을 말한다.
  • 이 정보들은 recovery 시에 사용한다고 하네
• 그리고 어떤 DBMS 는 JOIN 할 때 같이 불려나가는 애들을 같은 page 에 위치시키기도 한다.
  • 당연히 JOIN 성능은 좋아지지만, update 성능은 구려진다고 한다.

Tuple layout §

• Tuple 은 각 slot 내에서 어떻게 저장되는지 알아보자.
• 일단 당연히 이 tuple 안에도 header 가 있어서 여기에 여러 metadata 가 담긴다.
• Tuple 의 domain 이 가질 수 있는 값은 크게 세 가지가 있다: fixed size value, variable size value, NULL
• Fixed sized value 는 딱히 고려할 것이 없다.
  • 어차피 data 의 사이즈가 고정되어 있기 때문에, offset 을 알아낼 때는 이 고정 사이즈만 더해주면 되기 때문.

• Variable sized value 를 처리하는 방법들은 대강 다음을 생각할 수 있다.
  • Fixed-size with padding: 당연히 padding 만큼 공간이 낭비된다.
  • Delimiter: CSV 처럼 delimiter 를 사용하자는 것인데,
    • 이것이 등장할 때까지 계속 읽어야 되고 (얼마나 읽어야 되는지 사전에 알 수 없음)
    • 해당 delimiter 는 domain value 내에 포함될 수 없다는 문제점이 있다.
  • Domain 앞에 length 적기 (DNS packet 과 동일한 방식) 도 가능한데,
    • 이건 얼마나 읽어야 하는지는 바로 알 수 있지만 offset 을 바로 계산하지는 못한다는 단점이 있다.
  • Header 에 length 적기
    • Offset 은 이 length 들로 계산할 수 있기 때문에, variable sized value 들에 대해서만 순서대로 header 에 length 를 적으면 해결된다.
    • 요즘은 이것을 사용한다고 한다.
• NULL 을 표현하는 것은 nullmap 을 사용한다. (null bitmap)
  • 이걸로 어디가 null 인지 표시하고, NULL 이면 해당 domain 은 누락하고 다음 domain 저장
  • 그리고 bitmap 의 크기는 attr size 가 아니다; nullable attr 의 개수만큼만 bitmap 을 유지한다.
• 따라서 어떤 값에 대한 tuple 내에서의 offset 을 계산하는 것은 다음처럼 요약할 수 있다:
  • 원하는 값이 $T$ 번째 column $C_T$ 라면, iterator $i$ ($0\le i<T$) 에 대해
  • 만약 $C_i$ 가 fixed sized 라면, 해당 크기를 그냥 offset 에 더한다.
  • 만약 $C_i$ 가 variable sized 라면, 이놈이 몇번째 variable sized column 확인해서 header 에 저장된 length 들을 통해 이놈의 length 를 알아내 offset 에 더한다.
  • 만약 $C_i$ 가 nullable 이고 nullmap 에 해당 bit 가 켜져 있으면, 다음 column 으로 넘어간다.