Artikel ini merupakan terjemahan dari seri Let's Build a Simple Database yang ditulis oleh Connor Stack

Pendahuluan dan Mempersiapkan REPL

Sebagai seorang web devleoper, penulis sering menggunakan relational databases hampir setiap hari untuk menyelesaikan pekerjaan. Tetapi ada beberapa pertanyaan yang selalu muncul dikepala penulis:

• Dalam format apa data disimpan (di dalam memori atau di disk)?
• Kapan ia memindah data dari memori ke dalam disk?
• Kenapa harus ada satu primary key untuk satu tabel?
• Bagaimana cara kerja transaksi suatu rolling back?
• Bagaimana index di format?
• Kapan dan bagaimana sebuah pembacaan tabel menyeluruh dilakukan?
• Dalam format apa sebuah prepared statement di simpan?

Dengan kata lain, bagaimana sebetulnya sebuah database bekerja?

Untuk mencari tahu jawaban pertanyaan-pertanyaan di atas, tulisan ini dibuat. Dasar dari aplikasi yang akan dibuat adalah sqlite karena didesain agar berukuran kecil dan memiliki fitur lebih sedikit dibanding MySQL atau PostgreSQL, sehingga penulis memiliki kesempatan untuk memahaminya lebih baik. Keseluruhan database disimpan di dalam sebuah file!

Sqlite

Telah tersedia banyak dokumen yang menjelaskan cara kerja sistem SQLite di website mereka, plus penulis juga memiliki buku SQLite Database System: Design and Implementation.

sqlite architecture (https://www.sqlite.org/zipvfs/doc/trunk/www/howitworks.wiki)

---

Sebuah query akan melalui serangkaian komponen untuk menerima atau memodifikasi data. Bagian front-end terdiri dari:

• tokenizer
• parser
• code generator

Masukan untuk front-end adalah sebuah query SQL. Keluarannya adalah sebuah bytecode virtual machine sqlite (sederhananya sebuah program yang terkompilasi yang dapat beroperasi di database).

Sisi back-end terdiri dari:

• virtual machine

• B-tree

• pager

• os interface

Virtual machine akan membaca bytecode yang di-generate oleh front-end sebagai sebuah instruksi. Lalu ia akan melakukan operasi di satu tabel atau lebih atau pada index yang akan disimpan dalam sebuah struktur data bernama B-tree. VM dapat dianggap sebagai sebuah perintah switch raksasa yang membaca instruksi dari bytecode.

Setiap B-tree terdiri dari banyak node. Setiap node panjangnya satu halaman. Halaman yang dibaca oleh B-tree dapat diambil dari disk atau menyimpannya lagi ke disk menggunakan perintah kepada pager.

Pager menerima perintah untuk menulis atau membaca halaman data. Ia bertugas untuk membaca/menulis bagian-bagian tertentu di file database. Ia juga menyimpan sebuah cache halaman-halaman yang baru diakses di memori, lalu menentukan kapan halaman-halaman tersebut ditulis kembali ke disk.

Os interface merupakan lapisan yang menentukan sistem operasi apa aplikasi ini ditulis. Dalam tutorial ini, penulis tidak akan mendukung multiple platform.

Sebuah perjanalan panjang dimulai dengan satu langkah, jadi mari kita mulai dengan sesuatu yang disebut dengan REPL.

Membuat REPL Sederhana

SQLite memulai sebuah perulangan read-execute-print saatu membukanya dari command line:

~ sqlite3
SQLite version 3.16.0 2016-11-04 19:09:39
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> create table users (id int, username varchar(255), email varchar(255));
sqlite> .tables
users
sqlite> .exit
~

Untuk melakukan hal tersebut, kita akan menulis sebuah infinite loop di dalam fungsi utama kita yang mencetak perintah, membaca sebaris masukan lalu memproses masukan tersebut:

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) {
      exit(EXIT_SUCCESS);
    } else {
      printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    }
  }
}

Kita akan mendefinisikan InputBuffer sebagai sebuah wrapper diluar state yang akan menyimpan data dari getline().

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

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

  return input_buffer;
}

Selanjutnya, print_prompt() akan mencetak sebuah baris baru ke pengguna. Kita akan mencetak baris ini setiap saat sebelum membaca baris masukan.

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

Untuk membaca sebaris masukan gunakan getline():

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

lineptr : sebuah pointer ke variabel yang kita gunakan untuk menunjuk buffer yang menyimpan baris masukan.

n : sebuah pointer ke variabel dimana kita menggunakannya untuk menyimpan ukuran yang dialokasikan untuk buffer.

stream : tempat asal dimana kita membaca data. Kita akan membaca dari standard input.

return value : jumlah byte yang dibaca, sehingga memungkinkan untuk memiliki ukuran lebih kecil dari buffer.

Kita memberitahu getline untuk menyimpan baris masukan di input_buffer->buffer dan ukuran untuk buffer di input_buffer->buffer_length. Kita menyimpan nilai baliknya di input_buffer->input_length.

buffer dimulai sebagai null, sehingga getline dapat mengalokasikan cukup memori untuk menyimpan baris masukan dan membuat buffer` menunjuk nilai tersebut.

void read_input(InputBuffer* input_buffer) {
  ssize_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;
}

Terakhir, kita membaca dan mengeksekusi perintah yang telah dimasukan. Saat ini baru satu perintah yang dikenal yaitu : .exit, yang mana akan menutup program. Selain perintah itu kita akan mencetak pesan kesalahan dan melanjutkan pengulangan.

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

Mari kita jalankan!

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

Baik, sekarang kita sudah memiliki sebuah REPL yang bekerja. Dibagian berikutnya, kita akan mulai mengembangkan perintah aplikasi kita. Sementara itu, berikut kode keseluruhan program untuk bagian ini:

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

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

InputBuffer* new_input_buffer() {
  InputBuffer* input_buffer = 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) {
  ssize_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;
}

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) {
      exit(EXIT_SUCCESS);
    } else {
      printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    }
  }
}