pkglog
EN

C++로 작은 DB 엔진 만들기: Pager·B-Tree 저장 엔진, SQL 파서, 실행기, WAL 트랜잭션

작성 · · 40분 읽기 · 수정 중급 실습

들어가며: “100만 행에서 특정 키를 찾는데 왜 이렇게 느릴까요?”

왜 DB 엔진 기초인가

데이터베이스는 저장 엔진, 쿼리 파서, 실행기, 트랜잭션이 결합된 시스템입니다. SQLite나 MySQL을 쓰더라도 내부 동작을 이해하지 못하면 “인덱스가 왜 필요한가?”, “트랜잭션이 어떻게 원자성을 보장하는가?” 같은 질문에 답하기 어렵습니다. 이 글은 페이지 기반 Pager, B-Tree, SQL 토크나이저·파서, 실행기, WAL 트랜잭션을 작은 C++ 코드로 만들어 보면서 각 부품이 왜 필요한지 설명합니다. 코드는 구조를 보여 주기 위한 교육용 최소 구현이라 일부러 생략한 부분이 많은데, 각 절에서 “이대로 쓰면 어디서 깨지는지”를 함께 짚어 실제 엔진(SQLite, PostgreSQL)이 그 부분을 어떻게 처리하는지 연결합니다.

관련 글: 데이터베이스 연동, 바이너리 직렬화.

DB 엔진은 도서관에 비유하기 좋습니다. 저장 엔진은 책이 꽂히는 책장(페이지), B-Tree 인덱스는 색인 카드, 실행기는 서가에서 책을 찾아 읽는 절차입니다. 인덱스 없이 풀 스캔만 하면, 서가를 처음부터 끝까지 훑는 것과 같아서 행이 많을수록 비용이 커집니다.

느린 조회·롤백·크래시 복구: DB 엔진이 풀어야 할 문제

상황: 사용자 테이블에 100만 행이 있고, SELECT * FROM users WHERE id = 12345 쿼리가 몇 초씩 걸립니다. 원인: 풀 스캔(Full Scan) 때문입니다. 인덱스 없이 모든 행을 순차적으로 읽어 조건에 맞는지 확인하므로 O(N) 복잡도가 됩니다. 해결: B-Tree 인덱스를 id 컬럼에 구축하면 O(log N) 검색이 됩니다. 한 노드에 키를 수백 개 담으면 트리 높이가 3~4 정도에 불과해, 100만 행이라도 페이지 몇 개만 읽으면 원하는 행에 도달합니다. 이진 트리가 아니라 B-Tree를 쓰는 이유가 바로 이것입니다. 디스크에서 비싼 것은 비교 횟수가 아니라 페이지를 읽는 횟수이므로, 노드 하나를 페이지 하나에 맞춰 팬아웃을 키웁니다. 상황: 배치 INSERT 중 5번째 행에서 제약 조건 위반이 발생했습니다. 이미 삽입된 4개는 어떻게 될까요? 원인: 트랜잭션 없이 각 INSERT를 개별 커밋하면 부분 커밋이 발생하고, 롤백이 불가능합니다. 해결: BEGIN → INSERT 10개 → COMMIT, 에러 시에는 ROLLBACK합니다. WAL(Write-Ahead Logging) 으로 원자성을 보장합니다. 상황: 단순한 SQL 문자열을 파싱하려는데 “Expected FROM” 에러가 납니다. 원인: 대소문자 구분, 앞뒤 공백, 따옴표 처리가 미흡하기 때문입니다. "select * from users" 같은 입력에 취약합니다. 해결: 토크나이저에서 정규화(소문자 변환, trim)를 하고, 따옴표 문자열을 하나의 토큰으로 처리합니다. 상황: Pager가 모든 페이지를 메모리에 캐시하면 OOM이 발생합니다. 원인: 무제한 캐시 때문입니다. get_page() 호출마다 새 페이지를 캐시에 추가하고, eviction이 없습니다. 해결: LRU 캐시로 MAX_CACHED_PAGES(예: 1000)를 제한합니다. eviction 시 dirty 페이지는 flush한 뒤 제거합니다. 상황: 트랜잭션 커밋 도중 전원이 나갔습니다. 재시작 후 일부 데이터만 복구됩니다. 원인: WAL을 fsync하기 전에 크래시하면 로그가 디스크에 완전히 기록되지 않았을 수 있습니다. 또는 WAL 복구 순서가 잘못된 경우입니다. 해결: WAL 쓰기 후 반드시 fsync한 뒤에 커밋 완료로 간주합니다. 복구 시에는 WAL 전체를 순차적으로 REDO합니다. 상황: 클라이언트 A와 B가 동시에 UPDATE users SET balance = balance - 100을 실행합니다. 최종 balance가 잘못됩니다. 원인: 동시성 제어가 없기 때문입니다. 두 트랜잭션이 같은 데이터를 읽고 각자 수정한 뒤 커밋하면 한쪽 변경이 손실됩니다. 해결: 락(Lock) 또는 MVCC(Multi-Version Concurrency Control). 이 글에서는 단일 스레드 기준으로 다루며, 동시성은 프로덕션 패턴에서 언급합니다.

문제와 담당 컴포넌트 다이어그램

flowchart TB
    subgraph Problems[실무 문제 시나리오]
        P1[풀 스캔 수 초]
        P2[부분 커밋 롤백 불가]
        P3[SQL 파싱 실패]
        P4[캐시 OOM]
        P5[크래시 후 데이터 손실]
    end
    subgraph Solutions[해결 방향]
        S1[B-Tree 인덱스]
        S2[WAL 트랜잭션]
        S3[토크나이저 정규화]
        S4[LRU 페이지 캐시]
        S5[WAL fsync + REDO]
    end
    P1 --> S1
    P2 --> S2
    P3 --> S3
    P4 --> S4
    P5 --> S5

미니 DB 엔진의 구성

전체 구조

flowchart TB
    subgraph Client[클라이언트]
        C1["SQL 문자열"]
    end
    subgraph Engine[DB 엔진]
        subgraph Parser[쿼리 파서]
            P1[토크나이저]
            P2[구문 분석]
        end
        subgraph Executor[실행기]
            E1[실행 계획]
            E2[연산 수행]
        end
        subgraph Storage[저장 엔진]
            S1[Pager]
            S2[B-Tree]
        end
        subgraph Txn[트랜잭션]
            T1[WAL]
        end
    end
    C1 --> Parser
    Parser --> Executor
    Executor --> Storage
    Storage --> Txn

컴포넌트 역할

컴포넌트역할비유
쿼리 파서SQL 문자열 → 구문 트리(AST)번역기
실행기AST → 실제 연산(스캔, 필터, 삽입)일꾼
저장 엔진페이지 I/O, B-Tree 인덱스창고
트랜잭션WAL, 커밋/롤백회계장부

Pager와 B-Tree로 만든 저장 엔진

페이지 기반 저장의 이유

디스크 I/O는 페이지 단위로 수행하는 것이 효율적입니다. 4KB 페이지로 묶어 읽고 쓰면 랜덤 I/O를 줄이며, OS 페이지 캐시와도 잘 맞습니다.

Pager: 페이지 캐시

// pager.hpp
#pragma once
#include <fstream>
#include <unordered_map>
#include <memory>
#include <cstring>
#include <cstdint>
constexpr size_t PAGE_SIZE = 4096;
struct Page {
    uint32_t page_id;
    uint8_t data[PAGE_SIZE];
    bool dirty = false;
};
class Pager {
    std::string filename_;
    std::fstream file_;
    std::unordered_map<uint32_t, std::unique_ptr<Page>> cache_;
    uint32_t num_pages_ = 0;
public:
    explicit Pager(const std::string& filename) : filename_(filename) {
        file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
        if (!file_) {
            file_.open(filename, std::ios::out | std::ios::binary);
            file_.close();
            file_.open(filename, std::ios::in | std::ios::out | std::ios::binary);
        }
        file_.seekg(0, std::ios::end);
        auto size = file_.tellg();
        num_pages_ = static_cast<uint32_t>(size) / PAGE_SIZE;
    }
    Page* get_page(uint32_t page_id) {
        auto it = cache_.find(page_id);
        if (it != cache_.end()) {
            return it->second.get();
        }
        auto page = std::make_unique<Page>();
        page->page_id = page_id;
        if (page_id < num_pages_) {
            file_.seekg(static_cast<std::streamoff>(page_id) * PAGE_SIZE);
            file_.read(reinterpret_cast<char*>(page->data), PAGE_SIZE);
        } else {
            std::memset(page->data, 0, PAGE_SIZE);
            num_pages_ = page_id + 1;
        }
        auto* ptr = page.get();
        cache_[page_id] = std::move(page);
        return ptr;
    }
    void mark_dirty(uint32_t page_id) {
        auto it = cache_.find(page_id);
        if (it != cache_.end()) {
            it->second->dirty = true;
        }
    }
    void flush_page(uint32_t page_id) {
        auto it = cache_.find(page_id);
        if (it == cache_.end() || !it->second->dirty) return;
        file_.seekp(static_cast<std::streamoff>(page_id) * PAGE_SIZE);
        file_.write(reinterpret_cast<const char*>(it->second->data), PAGE_SIZE);
        file_.flush();
        it->second->dirty = false;
    }
    void flush_all() {
        for (auto& [id, page] : cache_) {
            if (page->dirty) flush_page(id);
        }
    }
    uint32_t allocate_page() {
        return num_pages_++;
    }
    ~Pager() {
        flush_all();
    }
};

핵심 포인트:

  • get_page(): 캐시 미스 시 디스크에서 로드. 새 페이지는 0으로 초기화.
  • mark_dirty(): 수정된 페이지 표시.
  • flush_all(): 커밋 시 모든 dirty 페이지를 디스크에 기록.

이 Pager에서 눈여겨볼 설계 결정은 “언제 dirty 페이지를 디스크에 쓰는가”입니다. 이 구현은 커밋 전까지 dirty 페이지를 메모리에 붙잡아 두는데, 데이터베이스 용어로 no-steal 정책입니다. 커밋되지 않은 변경이 디스크에 내려가지 않으므로 롤백은 메모리의 페이지만 되돌리면 되어 단순합니다. 대신 트랜잭션이 커지면 dirty 페이지를 모두 메모리에 들고 있어야 합니다. 뒤에 나오는 LRU 캐시가 dirty 페이지를 내쫓으면서 디스크에 쓰는 순간 이 가정이 깨지고(steal), 크래시 시 디스크에 커밋 안 된 데이터가 남으므로 WAL에 UNDO 정보가 필요해집니다. PostgreSQL이나 InnoDB가 쓰는 ARIES 계열 복구가 REDO와 UNDO를 모두 다루는 이유가 이 steal/no-force 조합 때문입니다.

소멸자에서 flush_all()을 호출하는 것도 같은 맥락에서 조심해야 합니다. 트랜잭션을 커밋하지 않은 채 프로그램이 정상 종료되면, 소멸자가 커밋되지 않은 dirty 페이지까지 디스크에 써 버립니다. 또 file_.flush()는 데이터를 OS로 넘길 뿐 디스크에 기록됐다는 보장이 아니라는 점은 WAL 절에서 다시 다룹니다.

B-Tree 노드 (간소화)

// btree.hpp
#pragma once
#include "pager.hpp"
#include <vector>
#include <optional>
#include <algorithm>
#include <cstring>
struct BTreeNode {
    bool is_leaf;
    uint32_t num_keys;
    std::vector<int32_t> keys;
    std::vector<uint32_t> children;
    std::vector<std::vector<uint8_t>> values;
    static constexpr size_t MAX_KEYS = 100;
    void serialize(uint8_t* buf) const {
        size_t offset = 0;
        std::memcpy(buf + offset, &is_leaf, sizeof(is_leaf));
        offset += sizeof(is_leaf);
        std::memcpy(buf + offset, &num_keys, sizeof(num_keys));
        offset += sizeof(num_keys);
        for (uint32_t i = 0; i < num_keys; ++i) {
            std::memcpy(buf + offset, &keys[i], sizeof(keys[i]));
            offset += sizeof(keys[i]);
        }
        if (!is_leaf) {
            for (uint32_t i = 0; i <= num_keys; ++i) {
                std::memcpy(buf + offset, &children[i], sizeof(children[i]));
                offset += sizeof(children[i]);
            }
        } else {
            for (uint32_t i = 0; i < num_keys; ++i) {
                uint16_t sz = static_cast<uint16_t>(values[i].size());
                std::memcpy(buf + offset, &sz, sizeof(sz));
                offset += sizeof(sz);
                std::memcpy(buf + offset, values[i].data(), sz);
                offset += sz;
            }
        }
    }
    static BTreeNode deserialize(const uint8_t* buf) {
        BTreeNode node;
        size_t offset = 0;
        std::memcpy(&node.is_leaf, buf + offset, sizeof(node.is_leaf));
        offset += sizeof(node.is_leaf);
        std::memcpy(&node.num_keys, buf + offset, sizeof(node.num_keys));
        offset += sizeof(node.num_keys);
        node.keys.resize(node.num_keys);
        for (uint32_t i = 0; i < node.num_keys; ++i) {
            std::memcpy(&node.keys[i], buf + offset, sizeof(node.keys[i]));
            offset += sizeof(node.keys[i]);
        }
        if (!node.is_leaf) {
            node.children.resize(node.num_keys + 1);
            for (uint32_t i = 0; i <= node.num_keys; ++i) {
                std::memcpy(&node.children[i], buf + offset, sizeof(node.children[i]));
                offset += sizeof(node.children[i]);
            }
        } else {
            node.values.resize(node.num_keys);
            for (uint32_t i = 0; i < node.num_keys; ++i) {
                uint16_t sz;
                std::memcpy(&sz, buf + offset, sizeof(sz));
                offset += sizeof(sz);
                node.values[i].resize(sz);
                std::memcpy(node.values[i].data(), buf + offset, sz);
                offset += sz;
            }
        }
        return node;
    }
};
class BTree {
    Pager& pager_;
    uint32_t root_page_id_;
public:
    BTree(Pager& pager, uint32_t root_page_id)
        : pager_(pager), root_page_id_(root_page_id) {}
    std::optional<std::vector<uint8_t>> search(int32_t key) {
        return search_recursive(root_page_id_, key);
    }
    void insert(int32_t key, const std::vector<uint8_t>& value) {
        auto* root_page = pager_.get_page(root_page_id_);
        auto root = BTreeNode::deserialize(root_page->data);
        if (root.num_keys >= BTreeNode::MAX_KEYS) {
            uint32_t new_root = pager_.allocate_page();
            split_root(root_page_id_, new_root);
            root_page_id_ = new_root;
        }
        insert_non_full(root_page_id_, key, value);
    }
private:
    std::optional<std::vector<uint8_t>> search_recursive(uint32_t page_id, int32_t key) {
        auto* page = pager_.get_page(page_id);
        auto node = BTreeNode::deserialize(page->data);
        auto it = std::lower_bound(node.keys.begin(), node.keys.end(), key);
        size_t pos = it - node.keys.begin();
        if (it != node.keys.end() && *it == key) {
            if (node.is_leaf) return node.values[pos];
            return search_recursive(node.children[pos + 1], key);
        }
        if (node.is_leaf) return std::nullopt;
        return search_recursive(node.children[pos], key);
    }
    void split_root(uint32_t old_root, uint32_t new_root) {
        (void)old_root;
        (void)new_root;
    }
    void insert_non_full(uint32_t page_id, int32_t key, const std::vector<uint8_t>& value) {
        auto* page = pager_.get_page(page_id);
        auto node = BTreeNode::deserialize(page->data);
        if (node.is_leaf) {
            auto it = std::lower_bound(node.keys.begin(), node.keys.end(), key);
            size_t pos = it - node.keys.begin();
            node.keys.insert(it, key);
            node.values.insert(node.values.begin() + pos, value);
            node.num_keys++;
            node.serialize(page->data);
            pager_.mark_dirty(page_id);
        } else {
            auto it = std::lower_bound(node.keys.begin(), node.keys.end(), key);
            size_t pos = it - node.keys.begin();
            insert_non_full(node.children[pos], key, value);
        }
    }
};

이 B-Tree는 검색과 리프 삽입 경로만 보여 주는 뼈대라, 그대로 쓰면 곧 문제가 생깁니다.

  • 분할이 구현되어 있지 않습니다: split_root는 빈 스텁입니다. 루트가 MAX_KEYS에 도달하면 새로 할당한 빈 페이지가 루트가 되고, 기존 키가 담긴 옛 루트와의 연결이 사라져 이후 검색이 모두 실패합니다. 또 바뀐 root_page_id_는 이 BTree 객체 안에만 있고, Executor는 호출마다 테이블에 저장된 옛 루트 번호로 새 BTree를 만들기 때문에 루트 변경이 반영되지 않습니다. 실제 엔진은 루트 페이지 번호를 메타데이터(시스템 카탈로그) 페이지에 저장하거나, SQLite처럼 루트 페이지 번호를 바꾸지 않고 루트 내용을 자식으로 옮기는 방식으로 이 문제를 피합니다.
  • 분할 기준이 키 개수입니다: 리프에는 가변 길이 값이 함께 저장되므로, 값이 큰 행이 많으면 키 100개보다 훨씬 적은 수에서도 직렬화 결과가 4096바이트를 넘습니다. serialize는 버퍼 크기를 검사하지 않으므로 페이지 뒤의 메모리를 그대로 덮어써 힙 손상으로 이어집니다. 분할 판단은 “다음 키를 넣으면 직렬화 크기가 페이지를 넘는가”로 해야 하고, 페이지보다 큰 값은 오버플로 페이지로 따로 빼야 합니다.
  • 직렬화가 플랫폼에 묶여 있습니다: bool과 정수를 memcpy로 그대로 쓰므로 엔디안이 다른 기계에서는 파일을 읽을 수 없습니다. 파일 형식을 고정하려면 리틀 엔디안 같은 한 가지 바이트 순서로 명시적으로 인코딩해야 합니다.

제가 이런 교육용 엔진을 직접 만들어 보면서 가장 오래 헤맨 부분도 분할 이후의 포인터 갱신이었습니다. 자식 페이지를 둘로 나누고 부모에 구분 키를 올리는 것까지는 금방 되는데, 형제 포인터나 루트 번호처럼 “다른 곳에 저장된 페이지 번호”를 빠뜨리면 당장은 동작하다가 재시작 후에만 데이터가 사라집니다. B-Tree 코드를 검증할 때는 삽입 후 전체 키를 순회해 정렬 순서와 개수를 확인하는 불변식 검사 함수를 먼저 만들어 두는 편이 빠릅니다.

토크나이저와 구문 분석으로 만든 쿼리 파서

토크나이저 + 구문 분석

// parser.hpp
#pragma once
#include <string>
#include <vector>
#include <optional>
#include <sstream>
#include <algorithm>
#include <cctype>
enum class TokenType { SELECT, INSERT, INTO, VALUES, FROM, WHERE, IDENT, NUMBER, STRING, COMMA, LPAREN, RPAREN, EQ, SEMICOLON, STAR, END };
struct Token {
    TokenType type;
    std::string value;
};
class Tokenizer {
    std::string input_;
    size_t pos_ = 0;
    char peek() const {
        return pos_ < input_.size() ? input_[pos_] : '\0';
    }
    char consume() {
        return pos_ < input_.size() ? input_[pos_++] : '\0';
    }
    void skip_whitespace() {
        while (std::isspace(static_cast<unsigned char>(peek()))) consume();
    }
public:
    explicit Tokenizer(const std::string& input) : input_(input) {}
    Token next() {
        skip_whitespace();
        if (pos_ >= input_.size()) return {TokenType::END, ""};
        size_t start = pos_;
        if (std::isalpha(static_cast<unsigned char>(peek())) || peek() == '_') {
            while (std::isalnum(static_cast<unsigned char>(peek())) || peek() == '_') consume();
            std::string word = input_.substr(start, pos_ - start);
            std::transform(word.begin(), word.end(), word.begin(), ::tolower);
            if (word == "select") return {TokenType::SELECT, word};
            if (word == "insert") return {TokenType::INSERT, word};
            if (word == "into") return {TokenType::INTO, word};
            if (word == "values") return {TokenType::VALUES, word};
            if (word == "from") return {TokenType::FROM, word};
            if (word == "where") return {TokenType::WHERE, word};
            return {TokenType::IDENT, word};
        }
        if (std::isdigit(static_cast<unsigned char>(peek()))) {
            while (std::isdigit(static_cast<unsigned char>(peek()))) consume();
            return {TokenType::NUMBER, input_.substr(start, pos_ - start)};
        }
        if (peek() == '\'' || peek() == '"') {
            char quote = consume();
            start = pos_;
            while (peek() != quote && peek() != '\0') consume();
            std::string s = input_.substr(start, pos_ - start);
            if (peek() == quote) consume();
            return {TokenType::STRING, s};
        }
        if (peek() == ',') { consume(); return {TokenType::COMMA, ","}; }
        if (peek() == '(') { consume(); return {TokenType::LPAREN, "("}; }
        if (peek() == ')') { consume(); return {TokenType::RPAREN, ")"}; }
        if (peek() == '=') { consume(); return {TokenType::EQ, "="}; }
        if (peek() == ';') { consume(); return {TokenType::SEMICOLON, ";"}; }
        if (peek() == '*') { consume(); return {TokenType::STAR, "*"}; }
        throw std::runtime_error(std::string("Unexpected character: ") + consume());
    }
};
struct SelectStmt {
    std::vector<std::string> columns;
    std::string table_name;
    std::optional<std::string> where_column;
    std::optional<std::string> where_value;
};
struct InsertStmt {
    std::string table_name;
    std::vector<std::string> values;
};
class SQLParser {
    Tokenizer tokenizer_;
    Token current_;
    void advance() { current_ = tokenizer_.next(); }
    bool check(TokenType t) const { return current_.type == t; }
    void expect(TokenType t) {
        if (!check(t)) throw std::runtime_error("Expected token, got: " + current_.value);
        advance();
    }
public:
    explicit SQLParser(const std::string& sql) : tokenizer_(sql) {
        advance();
    }
    SelectStmt parse_select() {
        SelectStmt stmt;
        expect(TokenType::SELECT);
        while (!check(TokenType::FROM)) {
            if (check(TokenType::END)) throw std::runtime_error("Expected FROM");
            if (check(TokenType::IDENT) || check(TokenType::STAR)) {
                stmt.columns.push_back(current_.value);
                advance();
            } else {
                throw std::runtime_error("Unexpected token in column list: " + current_.value);
            }
            if (check(TokenType::COMMA)) advance();
        }
        expect(TokenType::FROM);
        stmt.table_name = current_.value;
        expect(TokenType::IDENT);
        if (check(TokenType::WHERE)) {
            advance();
            stmt.where_column = current_.value;
            expect(TokenType::IDENT);
            expect(TokenType::EQ);
            stmt.where_value = current_.value;
            if (current_.type == TokenType::STRING) advance();
            else expect(TokenType::NUMBER);
        }
        return stmt;
    }
    InsertStmt parse_insert() {
        InsertStmt stmt;
        expect(TokenType::INSERT);
        expect(TokenType::INTO);
        stmt.table_name = current_.value;
        expect(TokenType::IDENT);
        expect(TokenType::VALUES);
        expect(TokenType::LPAREN);
        while (!check(TokenType::RPAREN)) {
            if (check(TokenType::END)) throw std::runtime_error("Expected )");
            if (current_.type == TokenType::NUMBER)
                stmt.values.push_back(current_.value);
            else if (current_.type == TokenType::STRING)
                stmt.values.push_back(current_.value);
            advance();
            if (check(TokenType::COMMA)) advance();
        }
        expect(TokenType::RPAREN);
        return stmt;
    }
    bool is_select() const { return current_.type == TokenType::SELECT; }
    bool is_insert() const { return current_.type == TokenType::INSERT; }
};

핵심 포인트:

  • 정규화: 키워드를 소문자로 변환해 SELECT/select 모두 인식.
  • 따옴표 문자열: 'Alice'를 하나의 토큰으로 처리.
  • expect(): 예상 토큰이 아니면 명확한 에러 메시지.

원래 코드에는 파서를 처음 만들 때 거의 반드시 한 번은 겪는 버그가 두 가지 있었습니다. 하나는 모르는 문자를 END로 바꿔 버린 것입니다. SELECT * FROM users에서 *가 END 토큰이 되면, 컬럼 목록 루프는 FROM을 만날 때까지 도는데 END에서는 토큰이 더 이상 진행하지 않으므로 무한 루프에 빠집니다. 오류 메시지 없이 프로그램이 멈추기 때문에 원인을 찾기 어렵습니다. 모르는 문자는 즉시 예외로 알리고, “특정 토큰이 나올 때까지” 도는 루프에는 반드시 END 탈출 조건을 두어야 합니다. 다른 하나는 식별자 루프가 _를 허용하지 않아 user_id가 user와 _id로 쪼개지던 문제입니다. 첫 글자에서만 _를 허용하고 이후에는 빼먹는 실수가 흔합니다.

이 파서는 재귀 하강(recursive descent) 방식의 가장 단순한 형태입니다. 문법 규칙 하나를 함수 하나로 옮기고, expect로 다음 토큰을 확인하며 내려갑니다. WHERE a = 1 AND b = 2나 괄호가 있는 식을 지원하려면 연산자 우선순위를 처리하는 식 파서(Pratt 파서 등)를 추가해 where_column/where_value 대신 식 트리(AST)를 만들어야 합니다. 또 문자열 리터럴 안의 따옴표 이스케이프('O''Brien')도 처리되지 않으므로, 실제 입력을 받는다면 토크나이저가 연속된 따옴표 두 개를 하나로 합쳐야 합니다.

SELECT·INSERT를 수행하는 실행기

SELECT / INSERT 실행

// executor.hpp
#pragma once
#include "parser.hpp"
#include "pager.hpp"
#include "btree.hpp"
#include <functional>
#include <vector>
#include <string>
#include <unordered_map>
struct Schema {
    std::string table_name;
    std::vector<std::pair<std::string, std::string>> columns;
};
class Executor {
    Pager& pager_;
    std::unordered_map<std::string, std::pair<Schema, uint32_t>> tables_;
public:
    explicit Executor(Pager& pager) : pager_(pager) {}
    void create_table(const Schema& schema) {
        uint32_t root = pager_.allocate_page();
        tables_[schema.table_name] = {schema, root};
    }
    std::vector<std::vector<std::string>> execute_select(const SelectStmt& stmt) {
        std::vector<std::vector<std::string>> results;
        auto it = tables_.find(stmt.table_name);
        if (it == tables_.end()) throw std::runtime_error("Table not found: " + stmt.table_name);
        const auto& [schema, root_id] = it->second;
        BTree btree(pager_, root_id);
        if (stmt.where_column && stmt.where_value) {
            int32_t key = std::stoi(*stmt.where_value);
            auto opt = btree.search(key);
            if (opt) {
                auto row = deserialize_row(*opt, schema);
                results.push_back(row);
            }
        } else {
            scan_all(btree, schema, [&](const std::vector<std::string>& row) {
                results.push_back(row);
            });
        }
        return results;
    }
    void execute_insert(const InsertStmt& stmt) {
        auto it = tables_.find(stmt.table_name);
        if (it == tables_.end()) throw std::runtime_error("Table not found: " + stmt.table_name);
        const auto& [schema, root_id] = it->second;
        BTree btree(pager_, root_id);
        int32_t key = std::stoi(stmt.values[0]);
        std::vector<uint8_t> row_data = serialize_row(stmt.values, schema);
        btree.insert(key, row_data);
    }
private:
    std::vector<uint8_t> serialize_row(const std::vector<std::string>& values, const Schema& schema) {
        std::vector<uint8_t> data;
        for (size_t i = 0; i < schema.columns.size() && i < values.size(); ++i) {
            const auto& [name, type] = schema.columns[i];
            const auto& val = values[i];
            (void)name;
            if (type == "int") {
                int32_t num = std::stoi(val);
                data.insert(data.end(),
                    reinterpret_cast<const uint8_t*>(&num),
                    reinterpret_cast<const uint8_t*>(&num) + sizeof(num));
            } else {
                uint16_t len = static_cast<uint16_t>(val.size());
                data.insert(data.end(),
                    reinterpret_cast<const uint8_t*>(&len),
                    reinterpret_cast<const uint8_t*>(&len) + sizeof(len));
                data.insert(data.end(), val.begin(), val.end());
            }
        }
        return data;
    }
    std::vector<std::string> deserialize_row(const std::vector<uint8_t>& data, const Schema& schema) {
        std::vector<std::string> row;
        size_t offset = 0;
        for (const auto& [name, type] : schema.columns) {
            (void)name;
            if (type == "int") {
                int32_t num;
                std::memcpy(&num, data.data() + offset, sizeof(num));
                row.push_back(std::to_string(num));
                offset += sizeof(num);
            } else {
                uint16_t len;
                std::memcpy(&len, data.data() + offset, sizeof(len));
                offset += sizeof(len);
                row.push_back(std::string(data.begin() + offset, data.begin() + offset + len));
                offset += len;
            }
        }
        return row;
    }
    void scan_all(BTree& btree, const Schema& schema,
                  const std::function<void(const std::vector<std::string>&)>& callback) {
        (void)btree;
        (void)schema;
        (void)callback;
    }
};

실행기에서 가장 큰 단순화는 WHERE 절의 컬럼을 무시한다는 점입니다. execute_select는 where_column이 무엇이든 값을 정수로 바꿔 기본 키(B-Tree 키)로 검색합니다. 그래서 WHERE name = 'Alice'를 실행하면 std::stoi("Alice")가 std::invalid_argument를 던집니다. 실제 실행기는 조건 컬럼이 인덱스가 있는 키인지 보고, 그렇다면 인덱스 탐색을, 아니라면 전체 스캔 + 필터를 선택합니다. 이 선택이 바로 쿼리 옵티마이저가 하는 일의 출발점이고, scan_all이 비어 있는 이 예제에서는 인덱스가 없는 조건 검색이 아예 불가능하다는 점도 기억해 두세요.

WAL로 구현한 트랜잭션

WAL (Write-Ahead Logging)

// transaction.hpp
#pragma once
#include "pager.hpp"
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdio>  // EOF
struct WALEntry {
    enum Type { INSERT, UPDATE, DELETE } type;
    uint32_t page_id;
    std::vector<uint8_t> before_image;
    std::vector<uint8_t> after_image;
};
class TransactionManager {
    std::string wal_path_;
    std::fstream wal_file_;
    std::vector<WALEntry> current_txn_;
    bool in_transaction_ = false;
public:
    explicit TransactionManager(const std::string& db_path)
        : wal_path_(db_path + ".wal") {
        wal_file_.open(wal_path_, std::ios::in | std::ios::out | std::ios::binary | std::ios::app);
        if (!wal_file_) {
            wal_file_.open(wal_path_, std::ios::out | std::ios::binary);
            wal_file_.close();
            wal_file_.open(wal_path_, std::ios::in | std::ios::out | std::ios::binary | std::ios::app);
        }
    }
    void begin() {
        if (in_transaction_) throw std::runtime_error("Transaction already in progress");
        current_txn_.clear();
        in_transaction_ = true;
    }
    void log_page_change(uint32_t page_id,
                         const uint8_t* before, const uint8_t* after) {
        WALEntry entry;
        entry.type = WALEntry::UPDATE;
        entry.page_id = page_id;
        entry.before_image.assign(before, before + PAGE_SIZE);
        entry.after_image.assign(after, after + PAGE_SIZE);
        current_txn_.push_back(entry);
    }
    void commit(Pager& pager) {
        if (!in_transaction_) return;
        for (const auto& e : current_txn_) {
            write_entry(e);
        }
        wal_file_.flush();
        pager.flush_all();
        current_txn_.clear();
        in_transaction_ = false;
    }
    void rollback(Pager& pager) {
        if (!in_transaction_) return;
        for (auto it = current_txn_.rbegin(); it != current_txn_.rend(); ++it) {
            auto* page = pager.get_page(it->page_id);
            std::memcpy(page->data, it->before_image.data(), PAGE_SIZE);
            pager.mark_dirty(it->page_id);
        }
        current_txn_.clear();
        in_transaction_ = false;
    }
    void recover(Pager& pager) {
        wal_file_.seekg(0, std::ios::beg);
        while (wal_file_.good() && wal_file_.peek() != EOF) {
            auto entry = read_entry();
            auto* page = pager.get_page(entry.page_id);
            std::memcpy(page->data, entry.after_image.data(), PAGE_SIZE);
            pager.mark_dirty(entry.page_id);
        }
        pager.flush_all();
    }
    bool is_in_transaction() const { return in_transaction_; }
private:
    void write_entry(const WALEntry& e) {
        uint8_t t = static_cast<uint8_t>(e.type);
        wal_file_.write(reinterpret_cast<const char*>(&t), sizeof(t));
        wal_file_.write(reinterpret_cast<const char*>(&e.page_id), sizeof(e.page_id));
        uint32_t before_sz = static_cast<uint32_t>(e.before_image.size());
        wal_file_.write(reinterpret_cast<const char*>(&before_sz), sizeof(before_sz));
        wal_file_.write(reinterpret_cast<const char*>(e.before_image.data()), before_sz);
        uint32_t after_sz = static_cast<uint32_t>(e.after_image.size());
        wal_file_.write(reinterpret_cast<const char*>(&after_sz), sizeof(after_sz));
        wal_file_.write(reinterpret_cast<const char*>(e.after_image.data()), after_sz);
    }
    WALEntry read_entry() {
        WALEntry e;
        uint8_t t;
        wal_file_.read(reinterpret_cast<char*>(&t), sizeof(t));
        e.type = static_cast<WALEntry::Type>(t);
        wal_file_.read(reinterpret_cast<char*>(&e.page_id), sizeof(e.page_id));
        uint32_t before_sz, after_sz;
        wal_file_.read(reinterpret_cast<char*>(&before_sz), sizeof(before_sz));
        e.before_image.resize(before_sz);
        wal_file_.read(reinterpret_cast<char*>(e.before_image.data()), before_sz);
        wal_file_.read(reinterpret_cast<char*>(&after_sz), sizeof(after_sz));
        e.after_image.resize(after_sz);
        wal_file_.read(reinterpret_cast<char*>(e.after_image.data()), after_sz);
        return e;
    }
};

핵심 포인트:

  • Write-Ahead: 디스크에 변경 전에 WAL에 먼저 기록.
  • rollback: before_image로 페이지 복구.
  • recover: WAL 전체 REDO.

이 트랜잭션 관리자는 WAL의 구조를 보여 주지만, 그대로는 원자성과 내구성을 보장하지 못합니다. 실제 WAL이 반드시 갖추는 요소와 비교하면 빠진 부분이 분명히 보입니다.

  • 커밋 레코드가 없습니다: commit은 엔트리를 차례로 쓰기만 하므로, 세 번째 엔트리를 쓰던 중 크래시가 나면 WAL에는 앞의 두 엔트리만 남습니다. recover는 이를 모두 재적용하므로 트랜잭션의 일부만 반영됩니다. 실제 WAL은 트랜잭션의 마지막에 COMMIT 레코드를 쓰고, 복구 시 커밋 레코드까지 온전히 남은 트랜잭션만 재적용합니다.
  • 체크섬이 없습니다: 엔트리를 쓰는 도중 끊기면 마지막 엔트리가 잘린 채 남습니다. read_entry는 길이 필드를 그대로 믿으므로 잘린 길이 값으로 거대한 resize를 시도할 수 있습니다. 엔트리마다 CRC32 같은 체크섬을 붙이고, 체크섬이 맞지 않는 지점부터는 무시하는 것이 표준 방식입니다.
  • flush()는 디스크 기록이 아닙니다: std::fstream::flush()는 스트림 버퍼를 OS에 넘길 뿐이고, OS 페이지 캐시에 있는 데이터는 전원이 나가면 사라집니다. 커밋을 응답하기 전에 WAL을 fsync해야 내구성이 생기는데, 표준 fstream은 파일 디스크립터를 노출하지 않아 fsync를 부를 방법이 없습니다. 그래서 실제 엔진은 WAL을 POSIX open/write/fsync(Windows는 FlushFileBuffers)로 직접 다룹니다.
  • 로그가 실제로 기록되지 않습니다: log_page_change는 정의만 되어 있고 실행기의 INSERT 경로에서 호출되지 않으므로, 이 예제를 그대로 돌리면 WAL은 항상 비어 있습니다. 페이지를 수정하기 직전에 before 이미지를 떠 두고, 수정 후 after 이미지와 함께 로그에 남기는 연결 고리가 필요합니다.

페이지 전체(4KB)를 before/after 두 벌로 기록하는 방식은 이해하기 쉽지만 로그가 매우 커집니다. 키 하나를 넣어도 8KB 넘는 로그가 생깁니다. 그래서 실제 엔진은 “페이지 N의 오프셋 X에 이 바이트를 넣었다” 같은 논리적·물리논리적 로그를 쓰고, 체크포인트 직후 페이지가 처음 수정될 때만 페이지 전체 이미지를 남깁니다(PostgreSQL의 full page write). SQLite의 WAL 모드는 반대로 변경된 페이지 전체를 WAL에 쓰되, 읽는 쪽이 WAL의 최신 페이지를 먼저 보도록 해 롤백 저널 없이 읽기와 쓰기를 동시에 허용합니다.

통합 Database 클래스와 실행 예시

통합 Database 클래스

// database.hpp
#pragma once
#include "pager.hpp"
#include "parser.hpp"
#include "executor.hpp"
#include "transaction.hpp"
#include <iostream>
#include <stdexcept>
class Database {
    Pager pager_;
    TransactionManager txn_mgr_;
    Executor executor_;
public:
    explicit Database(const std::string& path)
        : pager_(path),
          txn_mgr_(path),
          executor_(pager_) {
        txn_mgr_.recover(pager_);
    }
    void execute(const std::string& sql) {
        SQLParser parser(sql);
        if (parser.is_select()) {
            auto stmt = parser.parse_select();
            auto results = executor_.execute_select(stmt);
            for (const auto& row : results) {
                for (const auto& col : row) std::cout << col << " ";
                std::cout << "\n";
            }
        } else if (parser.is_insert()) {
            auto stmt = parser.parse_insert();
            executor_.execute_insert(stmt);
        } else {
            throw std::runtime_error("Unknown statement type");
        }
    }
    void begin() { txn_mgr_.begin(); }
    void commit() { txn_mgr_.commit(pager_); }
    void rollback() { txn_mgr_.rollback(pager_); }
    void create_table(const Schema& schema) {
        executor_.create_table(schema);
    }
};

실행 예시

// main.cpp
#include "database.hpp"
int main() {
    Database db("mydb.dat");
    Schema schema;
    schema.table_name = "users";
    schema.columns = {{"id", "int"}, {"name", "varchar"}, {"age", "int"}};
    db.create_table(schema);
    db.begin();
    try {
        db.execute("INSERT INTO users VALUES (1, 'Alice', 30)");
        db.execute("INSERT INTO users VALUES (2, 'Bob', 25)");
        db.execute("INSERT INTO users VALUES (3, 'Charlie', 35)");
        db.commit();
    } catch (const std::exception& e) {
        db.rollback();
        std::cerr << "Rollback: " << e.what() << "\n";
    }
    db.execute("SELECT id, name, age FROM users WHERE id = 2");
    return 0;
}

시퀀스 다이어그램: SELECT 실행

sequenceDiagram
    participant Client
    participant Database
    participant Parser
    participant Executor
    participant Pager
    participant BTree
    Client->>Database: execute("SELECT ... WHERE id=2")
    Database->>Parser: parse_select()
    Parser->>Parser: 토큰화, 구문 분석
    Parser-->>Database: SelectStmt
    Database->>Executor: execute_select(stmt)
    Executor->>BTree: search(2)
    BTree->>Pager: get_page()
    Pager-->>BTree: Page*
    BTree-->>Executor: row data
    Executor-->>Database: results
    Database-->>Client: 출력

빈 페이지 읽기, B-Tree 인덱스 오류, WAL 복구 손실: 구현 실수

”Page not found” 또는 빈 페이지 읽기

증상: get_page(0) 호출 시 쓰레기 값이 나오거나 크래시가 납니다. 원인: 빈 파일에서 num_pages_=0이라 file_.read()가 0바이트를 읽기 때문입니다.

// ❌ 잘못된 코드
if (page_id < num_pages_) {
    file_.read(...);
}
// ✅ 올바른 코드
if (page_id < num_pages_) {
    file_.seekg(...);
    file_.read(reinterpret_cast<char*>(page->data), PAGE_SIZE);
} else {
    std::memset(page->data, 0, PAGE_SIZE);
    num_pages_ = page_id + 1;
}

B-Tree “vector subscript out of range”

증상: 리프 노드 삽입 시 node.values[pos] 접근에서 크래시가 납니다. 원인: num_keys와 values 크기가 일치하지 않기 때문입니다.

// ✅ 올바른 코드: keys와 values 동기화
node.keys.insert(it, key);
node.values.insert(node.values.begin() + pos, value);
node.num_keys++;

WAL 복구 후 데이터 손실

증상: 크래시 후 재시작하면 일부 트랜잭션이 사라집니다. 원인: WAL 쓰기 후 fsync 없이 커밋 완료로 간주했기 때문입니다.

// ❌ 잘못된 코드: OS 페이지 캐시까지만 전달
wal_file_.flush();
// ✅ 올바른 코드: WAL을 POSIX fd로 열고 커밋 시 fsync
int wal_fd = ::open("mydb.dat.wal", O_WRONLY | O_APPEND | O_CREAT, 0644);
::write(wal_fd, buf.data(), buf.size());   // 커밋 레코드까지 포함
::fsync(wal_fd);                            // 이 호출이 성공한 뒤에야 커밋 완료 응답

fileno()는 C의 FILE*에만 쓸 수 있고 std::fstream에는 없습니다. 원래 예제의 주석처럼 fsync(fileno(wal_file_))를 쓰면 컴파일되지 않습니다. 파일을 새로 만들었다면 그 파일이 들어 있는 디렉터리도 fsync해야 크래시 후 파일 자체가 사라지지 않는다는 점, 그리고 fsync가 실패(EIO)하면 그 뒤로는 페이지 캐시 상태를 믿을 수 없으므로 재시도보다 프로세스를 중단하는 편이 안전하다는 점도 실제 엔진들이 겪은 교훈입니다.

캐시 메모리 폭증 (OOM)

증상: 10GB DB 파일을 열면 메모리가 10GB까지 증가합니다. 원인: Pager 캐시에 eviction이 없습니다. 해결: MAX_CACHED = 1000으로 LRU eviction을 적용하고, cache_.size() >= MAX_CACHED일 때 evict_lru_page()를 호출합니다.

SQL 파서 “Expected FROM” 에러

증상: "select * from users" 입력 시 파싱에 실패합니다. 원인: * 토큰을 처리하지 않았습니다. 해결: if (peek() == '*') { consume(); stmt.columns.push_back("*"); }를 추가합니다.

트랜잭션 중첩·직렬화 버전 불일치

트랜잭션 중첩: BEGIN을 두 번 호출하면 상태가 꼬입니다. 중첩 카운트나 SAVEPOINT를 지원해야 합니다. 직렬화 불일치: 스키마 변경 후 기존 데이터 읽기에 실패합니다. 스키마 버전을 페이지 헤더에 저장하고 마이그레이션 로직을 추가합니다.

페이지 크기·fsync·배치 플러시 권장 사항

  1. 페이지 크기: PAGE_SIZE = 4096으로 OS 페이지와 맞추기.
  2. WAL fsync: 커밋 시 flush()만으로는 부족. 프로덕션에서는 platform-specific fsync() 필수.
  3. B-Tree 노드 용량: 키 개수 상한 대신 직렬화 바이트 크기로 분할을 판단합니다. 고정 길이 키만 있는 내부 노드는 수백 개를 담을 수 있지만, 가변 길이 값을 담는 리프는 값 크기에 따라 들어가는 개수가 달라집니다.
  4. 배치 플러시: 커밋 시점에 한 번에 flush. 매 페이지 수정마다 flush하면 I/O 폭증.
  5. 페이지 정렬 플러시: dirty 페이지를 page_id 순으로 정렬해 순차 I/O로 디스크 효율 향상.
  6. 에러 메시지: throw std::runtime_error("Expected FROM, got: " + current_.value); 처럼 컨텍스트 포함.
  7. 스키마 분리: 테이블 메타데이터는 별도 시스템 페이지에 저장.

LRU 캐시·WAL 체크포인트·백업: 운영 기능

LRU 페이지 캐시

class LRUPager {
    std::list<uint32_t> lru_list_;
    std::unordered_map<uint32_t, std::pair<std::unique_ptr<Page>, std::list<uint32_t>::iterator>> cache_;
    static constexpr size_t MAX_PAGES = 1000;
    void evict() {
        while (cache_.size() >= MAX_PAGES && !lru_list_.empty()) {
            uint32_t victim = lru_list_.back();
            lru_list_.pop_back();
            auto it = cache_.find(victim);
            if (it->second.first->dirty) flush_page(victim);
            cache_.erase(it);
        }
    }
};

WAL 체크포인트

void checkpoint() {
    pager_.flush_all();
    wal_file_.close();
    std::ofstream(wal_path_, std::ios::trunc).close();
    wal_file_.open(wal_path_, std::ios::in | std::ios::out | std::ios::binary | std::ios::app);
}

체크포인트의 순서는 매우 중요합니다. 위 코드는 flush_all()로 데이터 페이지를 OS에 넘긴 직후 WAL을 비우는데, 데이터 파일을 fsync하지 않았으므로 이 시점에 전원이 나가면 데이터 페이지도 디스크에 없고 WAL도 비어 있어 커밋된 데이터가 영구히 사라집니다. 올바른 순서는 “dirty 페이지 쓰기 → 데이터 파일 fsync → 그다음에 WAL 비우기”입니다. 또 체크포인트 중에 새 트랜잭션이 WAL에 쓰고 있을 수 있으므로, 실제 엔진은 WAL을 통째로 지우기보다 “여기까지 반영했다”는 체크포인트 위치(LSN)를 기록하고 그 이전 로그만 재활용합니다.

헬스 체크 메트릭

cache_size, cache_hits, cache_misses를 추적하고, hit_ratio = cache_hits / (cache_hits + cache_misses)로 모니터링합니다.

백업 및 복원

void backup(const std::string& backup_path) {
    pager_.flush_all();
    std::filesystem::copy(db_path_, backup_path, std::filesystem::copy_options::overwrite_existing);
    std::filesystem::copy(db_path_ + ".wal", backup_path + ".wal",
        std::filesystem::copy_options::overwrite_existing);
}

설정 외부화·스레드 안전성

설정은 DBConfig { page_size, max_cached_pages, fsync_on_commit }로 외부화합니다. 다중 스레드에서는 std::shared_mutex로 Pager를 보호합니다(get_page는 shared_lock, flush_page는 unique_lock).

DB 엔진 구성 요약

컴포넌트별 역할

컴포넌트역할
저장 엔진페이지 기반 Pager, B-Tree 인덱스
쿼리 파서토크나이저 + 구문 분석 → AST
실행기SELECT/INSERT 실행, 직렬화/역직렬화
트랜잭션WAL, REDO/UNDO

컴포넌트별 구현 점검 항목

  • Pager: 빈 페이지 memset, flush_all
  • B-Tree: keys/values 동기화, split_root
  • 파서: 토큰 정규화, * 처리
  • 실행기: 스키마 기반 직렬화
  • 트랜잭션: WAL, rollback 시 before_image
  • LRU 캐시 (프로덕션)
  • WAL 체크포인트 (프로덕션)

페이지 저장, B-Tree, 쿼리 파서, 실행기, WAL 트랜잭션으로 DB 엔진의 뼈대를 만들 수 있지만, 실제 엔진의 어려움은 노드 분할·커밋 레코드·체크섬·fsync 순서처럼 “크래시가 어느 순간에 나도 일관된 상태를 유지하는” 세부에 있습니다. 참고 자료:

같이 보면 좋은 글