[밑바닥 부터 구현하는 데이터베이스] 1 - 운영체제에 파일을 어떻게 읽고 쓸까?
우리가 저장하는 모든 데이터는 컴퓨터에 바이트(byte) 로 저장된다. 그래서 우리는 고 수준의 자료형을 직렬화(Serialize) 하여 저장하여야 한다. 예를 들어, 우리가 int[] 형을 직렬화 한다고 해보자.
[1, 2, 3] => [0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x03]
각 정수를 4 Byte 로 이어 붙이는걸 생각해볼 수 있다. 다만 여기서 byte 로 변환한 것을 어떻게 적어야 할지 고민해볼 수 있다. 예를 들어 [1] => [0x00, 0x00, 0x00, 0x01] 으로 적는 사람도 있을 것이고, [1] => [0x01, 0x00, 0x00, 0x00] 으로 적는 사람도 있을 것이다.
실제로 이러한 사유때문에 매핑(mapping) 방식이 별도로 존재하게 된다. [0x00, 0x00, 0x00, 0x01] 에서 0x00 을 가장 상위 바이트(MSB) 라고 표현하고, 0x01 을 가장 하위 바이트(LSB) 라고 표현한다. 메모리는 일반적으로 0x00, 0x01, 0x02, … 와 같이 증가하므로 이 상위 바이트에서 하위 바이트의 흐름을 어떻게 메모리 주소상에 맵핑할지를 나타내는 방식을 엔디안(Endian) 이라고 한다.
BigEndian
네트워크나 포맷에서 자주 쓰는BigEndian 은 상위 바이트(MSB) 를 메모리에 낮은 주소(앞쪽)에 쓰는 방식이다. 즉, [0x00, 0x00, 0x00, 0x01] 이 된다.
LittleEndian
그와 반대로 LittleEndian 은 하위 바이트(LSB) 를 메모리의 낮은 주소(앞쪽)에 쓰는 방식이다. 따라서, [0x01, 0x00, 0x00, 0x00] 이 된다.
왜 이렇게 세분화 되어 있는걸까? 그 이유는 네트워크 프로토콜, CPU 아키텍쳐 마다 이와 같이 맵핑하는 방식이 다르기 때문이다. 따라서 이를 잘 인지하는 것이 중요하다. 다른 맵핑 방식으로 읽게 되면 아예 다른 값으로 해석될 수 있기 때문이다.
Go lang 에서는?
Golang 에서는 이를 어떻게 처리할까? binary.BigEndian.PutUint32 를 사용하면 쉽게 인코딩이 가능하다. 예시를 위해 정수값을 4 바이트로 변환하여 byte 로 변환한다고 해보자. 첫번째로 해야할 일은 무엇일까? 바로 len(nums) * 4 만큼의 byte 배열을 확보해주는 것이다.
buffer := make([]byte, 4*len(nums))
이후에는 binary.BigEndian.PutUint32 을 이용하면 쉽게 4byte 배열에 맞게 들어가도록 변환 가능하다.
// PutUint32 stores v into b[0:4].
func (bigEndian) PutUint32(b []byte, v uint32) {
_ = b[3] // early bounds check to guarantee safety of writes below
b[0] = byte(v >> 24)
b[1] = byte(v >> 16)
b[2] = byte(v >> 8)
b[3] = byte(v)
}
여기서 “비트연산” 이 생소하면 이 부분이 잘 이해가 안갈 수 있는데, 이 연산(right shift) 은 간단하게 비트를 오른쪽으로 미는 역할을 한다. 이 부분을 잘 이해하지 못하면 앞으로 시리즈가 어려우므로 예시를 들고 넘어가 보겠다.
비트연산(부가 설명)
예를 들어 어떤 수를 이진수로 변환했는데 00010010 00110100 01010110 01111000 과 같이 나왔다고 해보자. 우리가 이걸 4byte 에 하나하나 담으려면 어떻게 해야할까? 이럴때 비트 연산을 사용하면 쉽다. 첫번째로 00010010 을 담으려면 총 24번 오른쪽으로 밀어야 00000000 00000000 00000000 00010010 형태가 된다. (정확히는 shift 연산이지만 이해를 위해 민다는 표현을 차용했다)
즉, 이 상태에서 1 byte = 8bit 이므로 byte (v >> 24) 를 하게 되면 byte 는 00010010 을 가지게 된다. 나머지도 똑같다. 즉 담고 싶은 부분을 마지막 8bit 로 만들기 위해 shift 연산을 하는 것이다. 이해가 갔다면 스스로 Little-endian 방식도 한번 구현해보길 바란다.
import "encoding/binary"
func IntSliceToBytes(nums []uint32) []byte {
buffer := make([]byte, 4*len(nums))
for i, n := range nums {
binary.BigEndian.PutUint32(buffer[i*4:], n)
}
return buffer
}
본문으로 돌아와서 다시 코드를 보면 이제 이 코드가 어떤 동작을 하는지 명확하게 이해갔을 것이다. 그렇다면 이제 이 byte 들을 파일에 쓰는 작업을 진행해보자.
파일(os.File)
일단 운영체제는 우리가 적어놨던 파일 또는 데이터들을 어떻게 읽고 가져올까? 우리가 파일을 읽을때 파일 전체를 로드해서 가져올까? 아니면 부분만 읽어서 가져올까? OS 를 공부해봤다면 들어봤겠지만 운영체제는 블럭단위로 파일을 읽게 된다.
그렇다면 운영체제는 이를 어떻게 나눠서 읽는걸까? 예를 들어 우리가 10KB 짜리 파일을 읽는데 1KB 블럭단위로 이 페이지를 읽어온다고 해보자. 첫번째로 1KB 를 읽고, 다음 부터는 마지막으로 읽은(1024~2048) 까지를 읽어야 할 것이다.
오프셋(Offset)
이를 위해 파일에서 어디까지 읽었는지를 알려주는 오프셋(Offset) 을 필요로 하게 되었고, 이는 파일 포인터에 값으로 저장되어 있다. 코드로 보면 조금 더 수월하게 이해할 수 있으니 코드로 한번 작성해보면서 알아보자.
f, err := os.OpenFile("test.txt", os.O_RDWR|os.O_CREATE, 0666) // 파일을 생성
if err != nil {
panic(err)
}
arr := make([]uint32, 12) // 정수형 배열(우리가 쓸값)
buf := make([]byte, 12*4) // 정수형 배열을 byte 로 변환할때 사용할 buffer (len(nums) * 4)
for i := 0; i < 12; i++ {
arr[i] = i
}
n, err := f.Write(IntSliceToBytes(arr))
파일을 쓰기 위해 파일을 생성하고, 우리가 원하는 정수 배열을 byte 배열로 전환한 다음에 f.Write(b byte[]) 를 통하여 해당 파일에 값을 쓰게 된다. 값을 쓸때 우리는 0번째 부터 48번째까지 offset 을 옮겨가며 파일에 값을 기록하게 된다.
_, err = f.Read(buf)
if err != nil {
panic(err)
}
fmt.Printf("%v\n", BytesToIntSlice(buf))
// error
panic: EOF
goroutine 1 [running]:
main.main()
/home/roach/btree/file/main.go:51 +0x246
exit status 2
만약에, 우리가 이를 생각하지 않고 여기서 바로 Read 메소드를 호출하게 되면 어떻게 될까? 우리는 당연하게도 0번부터 읽을 것 같지만 offset 부터 읽게 된다. 즉, 48번째 부터 읽게 되므로 우리는 EOF 라는 에러를 마주하게 된다.
Seek 메소드
// Seek sets the offset for the next Read or Write on file to offset, interpreted
// according to whence: 0 means relative to the origin of the file, 1 means
// relative to the current offset, and 2 means relative to the end.
// It returns the new offset and an error, if any.
// The behavior of Seek on a file opened with O_APPEND is not specified.
func (f *File) Seek(offset int64, whence int) (ret int64, err error) {
if err := f.checkValid("seek"); err != nil {
return 0, err
}
r, e := f.seek(offset, whence)
if e == nil && f.dirinfo.Load() != nil && r != 0 {
e = syscall.EISDIR
}
if e != nil {
return 0, f.wrapErr("seek", e)
}
return r, nil
}
따라서 이러한 문제를 마주하지 않기 위해서는 offset 을 우리가 원하는 위치로 이동시켜야 한다. Seek 함수를 보면 offset 은 양수/음수 값에 따라 현재 기준점(whence) 에서 오프셋을 계산하게 된다.
주석의 설명을 보면 0 은 파일의 시작 지점을 의미하고, 1 은 현재 offset 의 위치에서, 2 는 마지막을 기준으로 계산된다. 그렇다면 현재 Offset 위치를 알아낼때는 f.Seek(0, 1) 을 이용하면 현재의 오프셋 위치를 알아낼 수 있을 것이다. 실제로 테스트를 한번 해보자.
pos, err := f.Seek(0, 1) // 48 출력
따라서 파일을 읽기전에 f.Seek(0, 0) 으로 옮겨주자. 쓰기 이후 실행해보면 48이 잘 출력되는 걸 확인할 수 있다. 그렇다면 우리가 읽기 작업전에 해줘야 할 것은 무엇일까? 바로 파일의 offset 을 시작지점으로 옮겨줘야 한다.
f.Seek(0, 0) // 0 이점 시작지 이므로
_, err = f.Read(buf)
if err != nil {
panic(err)
}
fmt.Printf("%v\n", BytesToIntSlice(buf)) // [0 1 2 3 4 5 6 7 8 9 10 11]
위와 같이 파일을 시작지점으로 옮기고 이후 읽기를 실행하면 값을 잘 읽어오는 것을 확인할 수 있다. 그렇다면 여기서 아까의 질문인 운영 체제는 어떻게 파일을 나눠서 읽을 수 있을까? 에 대답할 수 있게 된다. 즉, Offset 으로 일정 단위로 읽는다면 충분히 나눠 읽을 수 있다는 것이다.
왜 나눠 읽지?
그렇다면 왜 나눠 읽는 것일까? 바이트를 하나하나 가져오면 안되는 걸까? 우리가 일반적으로 특정 데이터를 어디서 부터 가져오는 행위는 항상 가벼운 행위는 아니다. 따라서, 배치로 묶어서 처리하는 이유는 보통 I/O 와 같은 무거운 행위를 덜 하기 위해서이다.
즉, 운영체제가 나눠 읽는 이유도 이러한 성능적인 부분에서 최적화의 목적에 있다. 따라서 나눠 읽는 부분을 구현해보고 생각해보면서 어떤 최적화가 되는지 생각해보자.
Page
예를 들어 우리가 16 byte 씩 데이터를 읽고, 이를 특정 구조체에 저장한다고 해보자. 우리는 이러한 블럭단위를 Page 라고 부를 것이고, 이를 아래와 같이 구조체로 정의할 것이다.
const PAGE_SIZE = 16 // Byte
type Page struct {
Id int32
Data []byte
}
만약 24개의 정수(96byte) 를 Page 로 읽게 되면 몇개의 Page 가 생성되게 될까? 96 / PAGE_SIZE = 96 / 16 = 6 개가 필요하게 될 것이다. 즉, 우리는 6 개의 Page 를 가지게 된다. 하지만 Page 마다 순서가 있으므로 이를 구분하기 위해 Id 라는 값을 둔다.
첫번째 페이지를 읽고, 두번째 페이지를 읽을 때 [f.Seek](http://f.Seek)`(첫번째](http://f.Seek\)\(첫번째)페이지 이후, 0)으로 만들어야 하기 때문에 Id 를 두는 것이다. 그렇다면 [f.Seek](http://f.Seek) 의 첫번째 인자로 들어갈 인자는PAGE_SIZE * Id` 가 됨을 알 수 있다.
Page 로 읽기
그렇다면 위의 예시(총 크기 96Byte) 에서 Page 단위로 우리가 읽는 부분의 프로세스는 어떻게 될까? 이미 예측하고 있을 수 있겠지만 아래와 같이 진행된다.
읽기 알고리즘
총 크기 / PageSize 만큼의 루프를 생성한다.
루프 내부에서 PageSize 만큼의 Buffer(byte 배열) 을 생성한다.
루프 내부에서 현재 루프의
I(반복 횟수) * PAGE_SIZE로 offset 을 설정한다. (i=0 일때 0 * 16, i = 1 일때 1 * 16, …)파일 포인터의 offset 을 계산된 값으로 이동시킨다.
f.seek(I(반복 횟수) * PAGE_SIZE, 0)제공된 버퍼를 넣어 값을 읽는다.
여기서 고민이 한가지 생긴다. 어떻게 파일 단위로 이 페이지를 관리하지? 🤔 이를 위해 PageManager 라는 객체를 하나 만들어 볼수 있다.
type PageManager struct {
f *os.File
pages []*Page
}
이렇게 되면 우리가 읽은 페이지를 Id 를 인덱스 삼아 Page 를 관리할 수 있게 되고, 필요한 전체 읽기(ReadAll) 이라는 함수 또한 이 객체에서 관리하게 할 수 있다.
func (p *PageManager) ReadAll() error {
for i := 0; i < BYTE_LENGTH/PAGE_SIZE; i++ {
buf := make([]byte, PAGE_SIZE)
p.f.Seek(int64(i*PAGE_SIZE), 0) // 이건 사실 옮겨지기 때문에 불필요하나 명확한 예시를 위해 적음
p.f.Read(buf)
p.pages[i] = &Page{
Id: int32(i),
Data: buf,
}
}
return nil
}
이 ReadAll 이라는 함수를 이용하면 우리는 내부 SYSTEM_CALL 을 통해 디스크에서 파일을 읽어오게 된다. 근데 만약 정수 배열 0~4 번째 에 Read 가 유독 많다면 어떻게 될까? 이 SYSTEM_CALL 을 통해 계속 디스크로 부터 읽어오는 작업을 해야 할까?
이제는 그럴 필요가 없다. 우리가 이미 객체화 하여 메모리에 값을 올려뒀기 때문이다. ReadAt(id int32) 를 통해 메모리에서 값이 있다면 리턴하게 해보자.
func (p *PageManager) ReadAt(id int32) []byte {
return p.pages[id].Data
}
이제는 SYSTEM_CALL 이 아닌 단순 Memory Random Access 로 해당 부분에 적혀있는 값을 가져올 수 있게 됬다. 즉, 이전의 Disk 에서 읽어오는 것보다는 가벼운 행위가 되었다.
전체 코드
package main
import (
"encoding/binary"
"fmt"
"os"
)
const PAGE_SIZE = 16 // Byte
const INT_LENGTH = 24
const BYTE_LENGTH = INT_LENGTH * 4
type Page struct {
Id int32
Data []byte
}
type PageManager struct {
f *os.File
pages []*Page
}
func (p *PageManager) ReadAt(id int32) []byte {
return p.pages[id].Data
}
func (p *PageManager) ReadAll() error {
for i := 0; i < BYTE_LENGTH/PAGE_SIZE; i++ {
buf := make([]byte, PAGE_SIZE)
p.f.Seek(int64(i*PAGE_SIZE), 0)
p.f.Read(buf)
p.pages[i] = &Page{
Id: int32(i),
Data: buf,
}
}
return nil
}
func IntSliceToBytes(nums []uint32) []byte {
buf := make([]byte, 4*len(nums))
for i, n := range nums {
binary.BigEndian.PutUint32(buf[i*4:], n)
}
return buf
}
func BytesToIntSlice(buf []byte) []int {
n := len(buf) / 4
out := make([]int, n)
for i := 0; i < n; i++ {
out[i] = int(binary.BigEndian.Uint32(buf[i*4:]))
}
return out
}
func main() {
f, err := os.OpenFile("test.txt", os.O_RDWR|os.O_CREATE, 0666)
if err != nil {
panic(err)
}
pageManager := &PageManager{
f: f,
pages: make([]*Page, BYTE_LENGTH/PAGE_SIZE),
}
arr := make([]uint32, INT_LENGTH)
for i := 0; i < INT_LENGTH; i++ {
arr[i] = uint32(i)
}
_, err = f.Write(IntSliceToBytes(arr))
if err != nil {
panic(err)
}
f.Seek(0, 0)
pageManager.ReadAll()
fmt.Printf("%v\n", BytesToIntSlice(pageManager.ReadAt(0)))
}
헷갈릴 만한 부분
- 우리가 Page 단위로 읽어야만 운영체제가 블럭 단위로 읽는 것은 아니다. 운영체제는 기본적으로 블럭단위로 읽고, 필요에 의해서는 더많은 데이터를 prefetch 하기도 한다.
