SQLite 직접 만들어보기 Step 3 - 메모리에서만 동작하는 단일 테이블 DB 만들어보기

원본 글

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

많은 제약이 걸려있는 DB 구성해보기

• 종래엔 복잡한 DB 가 완성되어 있겠지만 시작할 땐 작게 개발을 시작하는 전략을 사용한다.
  • start small

어떤 제약이 걸리게 되는가?

• 단 두가지 연산만 지원한다.
  • insert: 행을 삽입한다.
  • select: 모든 행을 출력한다.
• 오직 메모리에만 데이터를 올린다.
  • 디스크에 영속화 시키지 않는다.
• 하드코딩된 단 하나의 테이블만 제공한다.

하드코딩된 단일 테이블의 구조

• id: integer
• username: varchar(32)
• email: varchar(255)

앞으로 사용할 insert 명령어의 구성

insert 1 jakeseo foo@bar.com

• 앞에서부터 순서대로 id, username, email 순이다.

insert 명령어를 사용하기 위한 구조체 추가 및 수정

#define COLUMN_USERNAME_SIZE 32
#define COLUMN_EMAIL_SIZE 255

typedef struct
{
  __uint32_t id;
  char username[COLUMN_USERNAME_SIZE];
  char email[COLUMN_EMAIL_SIZE];
} Row;

typedef struct
{
  StatementType type;
  Row row_to_insert; // only used by insert statement
} Statement;

• Row 구조체를 추가했다. 하드코딩된 테이블과 같은 데이터 구조를 띈다.
• Statement 구조체에 Row 타입의 필드를 하나 추가했다.

이후에 해야할 일

• 받은 데이터를 테이블에 복사해 넣어야 한다.
• SQLite 는 빠른 조회, 삽입, 삭제를 위해 B-Tree 를 이용한다.

행을 페이지로 그룹화 하는 것은 같지만 페이지를 트리로 정렬하는 대신 배열로 정렬하는 식으로 일단 간단히 만들어보자.

계획

• 페이지라 불리는 메모리 블록에 행을 저장한다.
• 각 페이지는 최대한 많은 행을 저장한다.
• 행은 각 페이지마다 간결한 표현(compact representation)으로 직렬화된다.
• 페이지는 오직 필요한 만큼만 할당된다.
• 페이지에 대해 고정 크기의 포인터 배열을 유지한다.

Row 의 간결한 표현 정의하기

#define size_of_attribute(Struct, Attribute) sizeof(((Struct *)0)->Attribute)
// some enum and struct codes ...

const __uint32_t ID_SIZE = size_of_attribute(Row, id);
const __uint32_t USERNAME_SIZE = size_of_attribute(Row, username);
const __uint32_t EMAIL_SIZE = size_of_attribute(Row, email);
const __uint32_t ID_OFFSET = 0;
const __uint32_t USERNAME_OFFSET = ID_OFFSET + ID_SIZE;
const __uint32_t EMAIL_OFFSET = USERNAME_OFFSET + USERNAME_SIZE;
const __uint32_t ROW_SIZE = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;

• 직렬화된 Row 는 다음과 같이 표현될 것이다.
  • column size(bytes) offset 순의 데이터이다.
  • id 4 0
  • username 32 4
  • email 255 36
  • total 291

Row 의 직렬화와 역직렬화 구현하기

// Row 의 구조를 띈 source 의 데이터를 임의의 메모리 포인터 destination 으로 복사한다.
void serialize_row(Row *source, void *destination)
{
  memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
  memcpy(destination + USERNAME_OFFSET, &(source->username), USERNAME_SIZE);
  memcpy(destination + EMAIL_OFFSET, &(source->email), EMAIL_SIZE);
}

// 임의의 메모리 포인터 source 의 데이터를 Row 의 구조를 띈 destination 으로 복사한다.
void deserialize_row(void *source, Row *destination)
{
  memcpy(&(destination->id), source + ID_OFFSET, ID_SIZE);
  memcpy(&(destination->username), source + USERNAME_OFFSET, USERNAME_SIZE);
  memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
}

테이블 구조 만들기

#define TABLE_MAX_PAGES 100

// 테이블 페이지 계산 등에 필요한 상수들
const __uint32_t PAGE_SIZE = 4096;
const __uint32_t ROWS_PER_PAGE = PAGE_SIZE / ROW_SIZE;
const __uint32_t TABLE_MAX_ROWS = ROWS_PER_PAGE * TABLE_MAX_PAGES;

typedef struct
{
  __uint32_t num_rows;
  void *pages[TABLE_MAX_PAGES];
} Table;

• 테이블은 행 번호를 주면 행이 포함된 페이지를 가리킨다.
• 행이 총 몇개인지 추적하기도 한다.

페이지 사이즈에 대해 생각해보기

• 위에 정의에서 PAGE_SIZE 는 4096 이라는 숫자를 갖는다.
• 4096 은 4KB 를 의미하며, 이는 많은 컴퓨터 아키텍처의 가상 메모리에서 사용되는 페이지와 동일한 크기이다.
• DB 의 한 페이지 크기를 OS 가상 메모리의 한 페이지 크기와 일치시켰다.
• OS 는 페이지를 분할하지 않고 전체 단위로 메모리 안팎으로 이동시킬 수 있다.

페이지의 개수에 대해 생각해보기

• 현재는 할당할 페이지 (TABLE_MAX_PAGES) 를 100 개로 제한하고 있다.
• 트리 구조로 전환하면 DB 의 최대 크기는 파일의 최대 크기로 제한된다.
  • 한 번에 메모리에 보관할 수 있는 페이지 수는 여전히 제한된다.
• 행은 페이지 경계를 넘지 않아야 한다.
  • 메모리에 페이지가 나란히 존재하지 않을 가능성이 높기 때문에 이렇게 구성하면 페이지를 읽고 쓰기 더 쉽게 만든다.

row_slot(): 테이블에서 행의 위치 찾기

// 테이블에서 입력받은 번호의 행이 위치한 곳을 찾아준다
void *row_slot(Table *table, __uint32_t row_num)
{
  __uint32_t page_num = row_num / ROWS_PER_PAGE;
  void *page = table->pages[page_num];

  if (page == NULL)
  {
    // 페이지에 접근하려 할 때만 메모리 할당하기
    page = table->pages[page_num] = malloc(PAGE_SIZE);
  }

  __uint32_t row_offset = row_num % ROWS_PER_PAGE;
  __uint32_t byte_offset = row_offset * ROW_SIZE;

  return page + byte_offset;
}

• 테이블에서 특정한 row 의 포인터를 계산한다.

byte_offset 을 구하는 이유는 row_num 만으로는 페이지 번호를 알 수 없어서이다. 50 번 row 라고 하면, 3 번 페이지의 8 번 row 임을 알 수 있다.

execute_statement() 를 이용해 테이블 읽고/쓰기

typedef enum
{
  EXECUTE_SUCCESS,
  EXECUTE_TABLE_FULL
} ExecuteResult;

void print_row(Row *row)
{
  printf("(%d, %s, %s)\n", row->id, row->username, row->email);
}

ExecuteResult execute_select(Statement *statement, Table *table)
{
  Row row;

  for (__uint32_t i = 0; i < table->num_rows; i++)
  {
    deserialize_row(row_slot(table, i), &row);
    print_row(&row);
  }

  return EXECUTE_SUCCESS;
}

ExecuteResult execute_statement(Statement *statement, Table *table)
{
  switch (statement->type)
  {
  case (STATEMENT_INSERT):
    return execute_insert(statement, table);
  case (STATEMENT_SELECT):
    return execute_select(statement, table);
  }
}

테이블 메모리 할당 및 해제 함수 구현하기

// 새로운 테이블을 만드는 함수 (초기엔 페이지별 메모리할당 되지 않음)
Table *new_table()
{
  Table *table = (Table *)malloc(sizeof(Table));
  table->num_rows = 0;

  for (__uint32_t i = 0; i < TABLE_MAX_PAGES; i++)
  {
    table->pages[i] = NULL;
  }

  return table;
}

// 테이블 메모리 해제하기
void free_table(Table *table)
{
  for (int i = 0; table->pages[i]; i++)
  {
    free(table->pages[i]);
  }

  free(table);
}

main() 함수에 개발 내용 적용하기

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

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

    if (input_buffer->buffer[0] == '.')
    {
      switch (do_meta_command(input_buffer))
      {
      case (META_COMMAND_SUCCESS):
        continue;
      case (META_COMMAND_UNRECOGNIZED_COMMAND):
        printf("Unrecognized command '%s'\n", input_buffer->buffer);
        continue;
      }
    }

    Statement statement;
    switch (prepare_statement(input_buffer, &statement))
    {
    case (PREPARE_SUCCESS):
      break;
    case (PREPARE_SYNTAX_ERROR):
      printf("Syntax error. Could not parse statement.\n");
      continue;
    case (PREPARE_UNRECOGNIZED_STATEMENT):
      printf("Unrecognized keyword at start of '%s'.\n", input_buffer->buffer);
      continue;
    }

    switch (execute_statement(&statement, table))
    {
    case (EXECUTE_SUCCESS):
      printf("Executed.\n");
      break;
    case (EXECUTE_TABLE_FULL):
      printf("Error: Table full.\n");
      break;
    }
  }
}

• 이제 DB 를 테스트해볼 준비가 되었다.

개발사항 확인해보기

db > insert 1 jake n00nietzsche@gmail.com
Executed.
db > insert 2 jack jack@naver.com
Executed.
db > select
(1, jake, n00nietzsche@gmail.com)
(2, jack, jack@naver.com)
Executed.
db > insert jack 3 a
Syntax error. Could not parse statement.
db >

• 의도한대로 잘 동작한다.

테스트 코드에 관하여

지금은 사실 테스트 코드를 작성하기 가장 좋은 타이밍이다.

• 우린 테이블을 가득 채워보지 않았다. (수동 테스트의 부족)
• 또 이외에도 몇가지 엣지 케이스를 테스트해보아야 한다. (너무 큰 데이터 등등...)

앞으로 테이블을 저장하는 데이터 구조를 크게 변경할 계획이므로 테스트를 잘 작성해놓으면 도움이 될 것이다. 테스트를 통해 우리는 퇴보를 막을 수 있다.