SQLite 직접 만들어보기 Step 1 - 매우 간단한 REPL 만들어보기

원본 글

https://cstack.github.io/db_tutorial/parts/part1.html

DB 동작에서 의문점

• 디스크와 메모리에서 데이터는 어떤 포멧으로 저장되는가?
• 데이터는 언제 메모리에서 디스크로 이동하는가?
• 테이블당 기본키 (primary key) 는 왜 하나여야만 하는가?
• 트랜잭션 롤백은 어떻게 동작하는가?
• 인덱스는 어떻게 포맷되는가?
• 풀 테이블 스캔 (full table scan) 은 언제 어떻게 수행되는가?
• prepared statement 는 어떤 포맷으로 저장되는가?

SQLite

SQLite 는 작고 내부 구현에 대한 참고자료도 풍부해 공부하기 좋다.

프론트엔드 (front-end)

• 토크나이저 (tokenizer)
• 파서 (parser)
• 코드 생성기 (code generator)

SQL query 가 앞단에서 거치는 컴포넌트들이다. 토큰화, 의미분석, 코드 생성의 과정을 거친다.
최종 결과물은 가상머신 바이트 코드이다.
본질적으로 DB 에서 작동할 수 있는 컴파일된 프로그램을 말한다.

백엔드 (back-end)

• 가상 머신 (Virtual Machine)
• 비트리 (B-tree)
• 페이저 (Pager)
• OS 인터페이스 (OS Interface)

가상 머신 (Virtual Machine)

• 프론트엔드에서 받은 바이트코드를 명령 (instructions) 으로 사용한다.
• 하나 이상의 테이블 혹은 인덱스에 대한 작업을 수행할 수 있다.
• 각 테이블 혹은 인덱스는 B-Tree 라는 데이터 구조로 저장된다.
• 가상 머신은 본질적으로 바이트코드 명령어 타입에 대한 큰 스위치 문이다.

비트리 (B-Tree)

• 각각의 비트리는 많은 노드를 포함한다.
• 각 노드의 길이는 한 페이지다.
• 비트리는 페이저 (Pager) 에 명령하여 디스크에서 페이지를 검색하거나 디스크에 데이터를 저장할 수 있다.

페이저 (Pager)

• 명령을 받아 페이지의 데이터를 읽거나 씁니다.
• DB 파일 내부의 데이터를 적절한 오프셋 (offsets) 으로 읽거나 쓸 책임을 가집니다.
• 최근 접근한 페이지를 메모리에 캐시로 보관하고 해당 페이지를 다시 디스크로 기록해야 하는 시기를 결정합니다.

OS 인터페이스 (OS Interface)

• sqlite 가 컴파일된 운영체제에 따라 달라지는 계층이다.
• 이번에 구현할 DB 에서는 여러 플랫폼을 지원하지 않는다.

천리길도 REPL 부터

REPL 이란, Read-Eval-Print Loop 의 줄임말로 읽고, 평가하고, 프린트 하기의 반복이란 뜻이다. 검은 화면에 명령어를 입력하여 소통하는 인터페이스를 가진 프로그램들을 말한다.

• SQLite 는 명령어를 통해 읽고(Read)-실행하고(Execute)-프린트(Print)하고 를 반복(Loop)하는 프로그램이다
• 아래는 테이블을 생성하고 생성된 테이블을 확인한 후 DB 프로그램을 종료하는 예시이다

sqlite> create table users (id int, username varchar(255), email varchar(255));
sqlite> .tables
users
sqlite> .exit

간단한 REPL 프로그램을 작성해보자

InputBuffer 구조체 및 초기화 함수 정의하기

typedef struct
{
  char *buffer;
  size_t buffer_length;
  size_t input_length;
} InputBuffer;

InputBuffer *new_input_buffer()
{
  InputBuffer *input_buffer = (InputBuffer *)malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}

• InputBuffer 라는 구조체를 정의하는 이유는 getline() 함수를 이용하기 위한 버퍼가 필요하기 때문이다.
• 사용자가 명령어를 통해 DB 와 소통할 때 임시로 상태를 담고 있는 작은 버퍼이다.

getline() 함수 잠시 알아보기

size_t getline(char **lineptr, size_t *n, FILE *stream);

• 사용자의 입력을 읽기 위해 사용되는 함수이다.
• 매개변수에 대해 각각 설명하자면
  • lineptr: 읽은 줄이 포함된 버퍼를 가리키는데 사용하는 변수에 대한 포인터다. NULL 로 설정되어 있어도 getline() 은 라인을 저장할 버퍼를 할당하기 때문에 getline() 이 실패하더라도 사용자 프로그램에서 메모리를 해제해주어야 한다.
  • n: 할당된 버퍼의 크기를 저장하는데 사용하는 변수에 대한 포인터다.
  • stream: 입력을 읽을 스트림이다. 이번엔 standard input 에서 읽는다.
• 반환 값은 읽은 바이트 수가 나온다. 버퍼 크기보다 작을 수도 있다.

read_input() 함수 정의하기

void read_input(InputBuffer *input_buffer)
{
  size_t bytes_read =
      getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);

  if (bytes_read <= 0)
  {
    printf("Error reading input\n");
    exit(EXIT_FAILURE);
  }

  // ignore trailing newline
  input_buffer->input_length = bytes_read - 1;
  input_buffer->buffer[bytes_read - 1] = 0;
}

• getline() 에서 읽은 줄을 input_buffer->buffer 에 저장하고 할당된 버퍼의 크기는 input_buffer->buffer_length 에 저장한다. 반환 값은 input_buffer->input_length 에 저장할 것이다.
• 버퍼는 NULL 로 시작하므로 getline() 은 입력 라인을 충분히 담을 수 있는 메모리를 할당하고 버퍼가 이를 가리키도록 한다.
• 사용자가 입력이 끝났다는 표시 알린 엔터 (trailing newline) 는 input_length 를 저장할 때 bytes_read - 1 을 해주고 버퍼의 마지막에 0 을 넣어줌으로써 지워준다.

close_input_buffer() 함수 정의하기

void close_input_buffer(InputBuffer *input_buffer)
{
  free(input_buffer->buffer);
  free(input_buffer);
}

• input_buffer 와 input_buffer->buffer 메모리를 free 해준다.
  • input_buffer->buffer 의 메모리를 free 해주는 이유는 getline() 에서 할당된 메모리가 있기 때문이다.

print_prompt() 함수 정의하기

void print_prompt() { printf("db > "); }

• 사용자에게 db > 라는 메세지를 띄워주는 작은 역할을 하는 함수이다

전체 main() 함수 구성해보기

int main(int argc, char *argv[])
{
  InputBuffer *input_buffer = new_input_buffer();

  while (true)
  {
    print_prompt();
    read_input(input_buffer);

    if (strcmp(input_buffer->buffer, ".exit") == 0)
    {
      close_input_buffer(input_buffer);
      exit(EXIT_SUCCESS);
    }
    else
    {
      printf("Unrecognized command '%s' .\n", input_buffer->buffer);
    }
  }
}

• 간단한 명령어를 통해 소통할 수 있는 REPL 이 완성되었다.

REPL 테스트해보기

db > .tables
Unrecognized command '.tables' .
db > .exit

• 잘 동작한다.

여태까지의 전체 프로그램 소스코드 살펴보기

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
  char *buffer;
  size_t buffer_length;
  size_t input_length;
} InputBuffer;

InputBuffer *new_input_buffer()
{
  InputBuffer *input_buffer = (InputBuffer *)malloc(sizeof(InputBuffer));
  input_buffer->buffer = NULL;
  input_buffer->buffer_length = 0;
  input_buffer->input_length = 0;

  return input_buffer;
}

void print_prompt() { printf("db > "); }

void read_input(InputBuffer *input_buffer)
{
  size_t bytes_read =
      getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);

  if (bytes_read <= 0)
  {
    printf("Error reading input\n");
    exit(EXIT_FAILURE);
  }

  // ignore trailing newline
  input_buffer->input_length = bytes_read - 1;
  input_buffer->buffer[bytes_read - 1] = 0;
}

void close_input_buffer(InputBuffer *input_buffer)
{
  free(input_buffer->buffer);
  free(input_buffer);
}

int main(int argc, char *argv[])
{
  InputBuffer *input_buffer = new_input_buffer();

  while (true)
  {
    print_prompt();
    read_input(input_buffer);

    if (strcmp(input_buffer->buffer, ".exit") == 0)
    {
      close_input_buffer(input_buffer);
      exit(EXIT_SUCCESS);
    }
    else
    {
      printf("Unrecognized command '%s' .\n", input_buffer->buffer);
    }
  }
}