C++ 데이터베이스 엔진 구현: B-Tree 인덱스, WAL, MVCC, SQL 파서와 실행 계획
들어가며: “SQLite처럼 간단한 DB 엔진을 만들고 싶어요”
데이터베이스 엔진의 핵심
관계형 데이터베이스는 저장 엔진, 인덱스, 트랜잭션, 쿼리 처리로 구성됩니다. 이 글에서는 간단한 DB 엔진의 핵심을 구현합니다.
구체적으로는 페이지 기반 저장 엔진, B-Tree 인덱스, WAL 로그를 이용한 트랜잭션, 간단한 SQL 파서와 실행 엔진, 쿼리 최적화를 차례로 구현합니다.
요구 환경: 예제가 std::shared_mutex를 쓰므로 C++17 이상(-std=c++17)으로 컴파일합니다.
DB 엔진을 직접 만들어 보는 상황
임베디드 환경의 로컬 저장소
IoT 디바이스나 엣지 서버에서 SQLite 없이 경량 DB가 필요할 때가 있습니다. 외부 라이브러리 의존성을 줄이며, 메모리·디스크 제약에 맞춘 최소 구현이 필요합니다.
특수 목적 인덱스
게임 세이브 데이터, 시계열 로그, 지리공간 데이터처럼 도메인 특화 인덱스가 필요할 때, 범용 DB보다 직접 B-Tree를 구현해 제어할 수 있습니다.
DB 내부 동작 학습
“인덱스가 왜 빠른가?”, “트랜잭션이 어떻게 원자성을 보장하는가?”를 이해하려면 직접 구현하는 것이 가장 효과적입니다.
인메모리 캐시 엔진
Redis처럼 키-값 캐시를 만들되, B-Tree 기반 범위 쿼리가 필요할 때, 페이지 기반 저장 구조를 이해하면 설계가 수월합니다.
쿼리 최적화 이해
“왜 이 쿼리가 느린가?”를 파악하려면 실행 계획·인덱스 스캔 vs 풀 스캔 개념이 필요합니다. 직접 파서와 옵티마이저를 구현하면 원리를 깊이 이해할 수 있습니다.
페이지 기반 저장 엔진
아키텍처 다이어그램
flowchart TB
subgraph Client[클라이언트]
C1[SQL 쿼리]
end
subgraph DB[데이터베이스 엔진]
subgraph Parser[파서]
P1[SQL 파싱]
end
subgraph Optimizer[옵티마이저]
O1[실행 계획]
end
subgraph Storage[저장 엔진]
S1[Pager]
S2[B-Tree]
end
subgraph Txn[트랜잭션]
T1[WAL]
end
end
C1 --> Parser
Parser --> Optimizer
Optimizer --> Storage
Storage --> Txn
페이지 기반 저장
디스크 I/O는 페이지 단위로 수행하는 것이 효율적입니다. 4KB 페이지로 묶어 읽고 쓰면 랜덤 I/O를 줄일 수 있습니다.
constexpr size_t PAGE_SIZE = 4096; // 4KB
struct Page {
uint32_t page_id;
uint8_t data[PAGE_SIZE];
bool dirty = false;
};
class Pager {
std::fstream file_;
std::unordered_map<uint32_t, std::unique_ptr<Page>> cache_;
uint32_t num_pages_ = 0;
public:
Pager(const std::string& 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_ = 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(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 flush_page(uint32_t page_id) {
auto it = cache_.find(page_id);
if (it == cache_.end() || !it->second->dirty) {
return;
}
file_.seekp(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는 페이지를 한 번 읽으면 캐시에 두고, 수정은 메모리의 페이지에만 한 뒤 dirty 표시를 해 두었다가 나중에 한꺼번에 씁니다. 이 구조가 데이터베이스 I/O 설계의 출발점이지만, 예제에는 실무에서 바로 문제가 되는 부분이 몇 가지 있습니다. 첫째, file_.flush()는 C++ 스트림 버퍼를 운영체제에 넘길 뿐이고 디스크에 기록되었다는 보장이 아닙니다. 정전이나 커널 패닉에서 살아남으려면 POSIX fsync()(Windows는 FlushFileBuffers)를 호출해야 하는데, 표준 fstream에는 이 기능이 없어 실제 엔진들은 파일 디스크립터를 직접 다룹니다. 둘째, fstream은 읽기가 파일 끝을 넘으면 failbit/eofbit가 켜지고, 그 뒤의 모든 seekp/write가 조용히 실패합니다. 스트림 상태를 clear()하지 않으면 “쓴 줄 알았는데 파일이 그대로”인 버그가 생깁니다. 셋째, 4KB 페이지 쓰기가 중간에 끊기면 한 페이지 안에 옛 데이터와 새 데이터가 섞이는 찢어진 쓰기(torn write)가 생길 수 있어, SQLite는 롤백 저널이나 WAL로, PostgreSQL은 체크포인트 후 첫 수정 때 페이지 전체를 로그에 남기는 full page write로 이를 막습니다.
테이블 구조
struct Column {
std::string name;
enum Type { INT, VARCHAR, FLOAT } type;
size_t size;
};
struct Schema {
std::string table_name;
std::vector<Column> columns;
std::vector<std::string> primary_keys;
};
class Table {
Schema schema_;
Pager& pager_;
uint32_t root_page_id_;
public:
Table(const Schema& schema, Pager& pager)
: schema_(schema), pager_(pager) {
root_page_id_ = pager_.allocate_page();
}
void insert(const std::vector<std::string>& values) {
// 행을 직렬화
std::vector<uint8_t> row_data = serialize_row(values);
// B-Tree에 삽입
insert_into_btree(root_page_id_, row_data);
}
std::vector<std::vector<std::string>> select(
const std::function<bool(const std::vector<std::string>&)>& predicate
) {
std::vector<std::vector<std::string>> results;
scan_btree(root_page_id_, [&](const std::vector<uint8_t>& row_data) {
auto row = deserialize_row(row_data);
if (predicate(row)) {
results.push_back(row);
}
});
return results;
}
private:
std::vector<uint8_t> serialize_row(const std::vector<std::string>& values) {
std::vector<uint8_t> data;
for (size_t i = 0; i < schema_.columns.size(); ++i) {
const auto& col = schema_.columns[i];
const auto& val = values[i];
switch (col.type) {
case Column::INT: {
int32_t num = std::stoi(val);
data.insert(data.end(),
reinterpret_cast<uint8_t*>(&num),
reinterpret_cast<uint8_t*>(&num) + sizeof(num));
break;
}
case Column::VARCHAR: {
uint16_t len = val.length();
data.insert(data.end(),
reinterpret_cast<uint8_t*>(&len),
reinterpret_cast<uint8_t*>(&len) + sizeof(len));
data.insert(data.end(), val.begin(), val.end());
break;
}
case Column::FLOAT: {
float num = std::stof(val);
data.insert(data.end(),
reinterpret_cast<uint8_t*>(&num),
reinterpret_cast<uint8_t*>(&num) + sizeof(num));
break;
}
}
}
return data;
}
std::vector<std::string> deserialize_row(const std::vector<uint8_t>& data) {
std::vector<std::string> values;
size_t offset = 0;
for (const auto& col : schema_.columns) {
switch (col.type) {
case Column::INT: {
int32_t num;
std::memcpy(&num, data.data() + offset, sizeof(num));
values.push_back(std::to_string(num));
offset += sizeof(num);
break;
}
case Column::VARCHAR: {
uint16_t len;
std::memcpy(&len, data.data() + offset, sizeof(len));
offset += sizeof(len);
values.push_back(std::string(
data.begin() + offset,
data.begin() + offset + len
));
offset += len;
break;
}
case Column::FLOAT: {
float num;
std::memcpy(&num, data.data() + offset, sizeof(num));
values.push_back(std::to_string(num));
offset += sizeof(num);
break;
}
}
}
return values;
}
};행 직렬화는 int32_t와 float를 메모리 표현 그대로 복사하므로, 이 파일은 같은 바이트 순서(엔디안)의 머신에서만 읽을 수 있습니다. x86과 ARM은 둘 다 리틀 엔디안이라 대부분 문제가 없지만, 파일 형식을 문서화하려면 바이트 순서를 명시하는 것이 좋습니다. SQLite가 정수를 빅 엔디안 가변 길이 형식으로 저장하는 것도 이식성 때문입니다. VARCHAR 길이를 uint16_t에 담기 때문에 65,535바이트를 넘는 문자열은 길이가 잘려 이후 모든 필드의 오프셋이 어긋나고, std::stoi에 숫자가 아닌 값이 들어오면 예외가 나므로 스키마 검증은 직렬화 전에 해야 합니다.
B-Tree 인덱스
B-Tree 노드 구조
B-Tree는 균형 트리로, O(log N) 검색·삽입을 보장합니다. 각 노드는 한 페이지에 저장됩니다.
struct BTreeNode {
bool is_leaf;
uint32_t num_keys;
std::vector<int32_t> keys;
std::vector<uint32_t> children; // 자식 페이지 ID
std::vector<std::vector<uint8_t>> values; // 리프 노드만
static constexpr size_t MAX_KEYS = 100;
void serialize(uint8_t* page_data) {
size_t offset = 0;
std::memcpy(page_data + offset, &is_leaf, sizeof(is_leaf));
offset += sizeof(is_leaf);
std::memcpy(page_data + offset, &num_keys, sizeof(num_keys));
offset += sizeof(num_keys);
for (uint32_t i = 0; i < num_keys; ++i) {
std::memcpy(page_data + offset, &keys[i], sizeof(keys[i]));
offset += sizeof(keys[i]);
}
if (!is_leaf) {
for (uint32_t i = 0; i <= num_keys; ++i) {
std::memcpy(page_data + offset, &children[i], sizeof(children[i]));
offset += sizeof(children[i]);
}
} else {
// 값 직렬화
for (uint32_t i = 0; i < num_keys; ++i) {
uint16_t value_size = values[i].size();
std::memcpy(page_data + offset, &value_size, sizeof(value_size));
offset += sizeof(value_size);
std::memcpy(page_data + offset, values[i].data(), value_size);
offset += value_size;
}
}
}
static BTreeNode deserialize(const uint8_t* page_data) {
BTreeNode node;
size_t offset = 0;
std::memcpy(&node.is_leaf, page_data + offset, sizeof(node.is_leaf));
offset += sizeof(node.is_leaf);
std::memcpy(&node.num_keys, page_data + 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], page_data + 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], page_data + 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 value_size;
std::memcpy(&value_size, page_data + offset, sizeof(value_size));
offset += sizeof(value_size);
node.values[i].resize(value_size);
std::memcpy(node.values[i].data(), page_data + offset, value_size);
offset += value_size;
}
}
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) {}
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_id = pager_.allocate_page();
split_root(root_page_id_, new_root_id);
root_page_id_ = new_root_id;
}
insert_non_full(root_page_id_, key, value);
}
std::optional<std::vector<uint8_t>> search(int32_t key) {
return search_recursive(root_page_id_, key);
}
private:
void split_root(uint32_t old_root_id, uint32_t new_root_id) {
auto* old_page = pager_.get_page(old_root_id);
auto old_node = BTreeNode::deserialize(old_page->data);
auto* new_page = pager_.get_page(new_root_id);
BTreeNode new_root;
new_root.is_leaf = false;
new_root.num_keys = 1;
size_t mid = old_node.num_keys / 2;
new_root.keys.push_back(old_node.keys[mid]);
new_root.children.push_back(old_root_id);
// 오른쪽 절반을 새 페이지로
uint32_t right_id = pager_.allocate_page();
auto* right_page = pager_.get_page(right_id);
BTreeNode right_node;
right_node.is_leaf = old_node.is_leaf;
// 리프는 중간 키를 오른쪽에 남기고(부모에는 복사), 내부 노드는 중간 키를 부모로 올림
size_t right_start = old_node.is_leaf ? mid : mid + 1;
right_node.keys.assign(old_node.keys.begin() + right_start, old_node.keys.end());
right_node.num_keys = right_node.keys.size();
if (old_node.is_leaf) {
right_node.values.assign(old_node.values.begin() + mid, old_node.values.end());
} else {
right_node.children.assign(old_node.children.begin() + mid + 1, old_node.children.end());
}
new_root.children.push_back(right_id);
// 기존 노드 크기 줄임
old_node.keys.resize(mid);
old_node.num_keys = mid;
if (old_node.is_leaf) {
old_node.values.resize(mid);
} else {
old_node.children.resize(mid + 1);
}
new_root.serialize(new_page->data);
new_page->dirty = true;
old_node.serialize(old_page->data);
old_page->dirty = true;
right_node.serialize(right_page->data);
right_page->dirty = true;
}
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);
page->dirty = true;
} else {
// 내부 노드: 적절한 자식 찾기
auto it = std::lower_bound(node.keys.begin(), node.keys.end(), key);
size_t pos = it - node.keys.begin();
uint32_t child_id = node.children[pos];
auto* child_page = pager_.get_page(child_id);
auto child = BTreeNode::deserialize(child_page->data);
if (child.num_keys >= BTreeNode::MAX_KEYS) {
split_child(page_id, pos);
// 분할 후 다시 적절한 자식 선택
node = BTreeNode::deserialize(page->data);
if (key > node.keys[pos]) {
pos++;
}
}
insert_non_full(node.children[pos], key, value);
}
}
void split_child(uint32_t parent_id, size_t child_index) {
auto* parent_page = pager_.get_page(parent_id);
auto parent = BTreeNode::deserialize(parent_page->data);
uint32_t child_id = parent.children[child_index];
auto* child_page = pager_.get_page(child_id);
auto child = BTreeNode::deserialize(child_page->data);
// 새 노드 생성
uint32_t new_child_id = pager_.allocate_page();
auto* new_child_page = pager_.get_page(new_child_id);
BTreeNode new_child;
new_child.is_leaf = child.is_leaf;
size_t mid = child.num_keys / 2;
// 중간 키를 부모로 올림
int32_t mid_key = child.keys[mid];
parent.keys.insert(parent.keys.begin() + child_index, mid_key);
parent.children.insert(parent.children.begin() + child_index + 1, new_child_id);
parent.num_keys++;
// 오른쪽 절반을 새 노드로 이동 (리프는 중간 키를 오른쪽에 남김)
size_t right_start = child.is_leaf ? mid : mid + 1;
new_child.keys.assign(child.keys.begin() + right_start, child.keys.end());
new_child.num_keys = new_child.keys.size();
if (child.is_leaf) {
new_child.values.assign(child.values.begin() + mid, child.values.end());
} else {
new_child.children.assign(child.children.begin() + mid + 1, child.children.end());
}
// 원래 노드 크기 줄임
child.keys.resize(mid);
child.num_keys = mid;
if (child.is_leaf) {
child.values.resize(mid);
} else {
child.children.resize(mid + 1);
}
// 페이지에 저장
parent.serialize(parent_page->data);
parent_page->dirty = true;
child.serialize(child_page->data);
child_page->dirty = true;
new_child.serialize(new_child_page->data);
new_child_page->dirty = true;
}
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);
}
};이 구현은 값을 리프에만 두는 B+Tree 방식이라, 노드를 분할할 때 리프와 내부 노드를 다르게 다뤄야 합니다. 내부 노드는 중간 키를 부모로 올리고 양쪽에서 제거하지만, 리프는 중간 키를 부모에 복사하고 자기 자신(오른쪽 리프)에도 남겨 둬야 합니다. 원래 코드는 두 경우를 똑같이 처리해 리프 분할 때마다 중간 위치의 키와 값이 아무 노드에도 남지 않고 사라지는 버그가 있었고, 위 코드는 리프일 때 오른쪽 노드를 mid부터 시작하도록 고친 것입니다. search_recursive가 내부 노드에서 키가 일치하면 오른쪽 자식(pos + 1)으로 내려가는 것도 이 “오른쪽 리프에 남긴다”는 규칙과 짝을 이룹니다. 이런 버그는 작은 데이터로는 드러나지 않다가 키가 MAX_KEYS를 넘어 첫 분할이 일어나는 순간부터 “넣은 키를 못 찾는” 증상으로 나타나므로, 분할 경계(MAX_KEYS, MAX_KEYS + 1, 두 번째 분할)를 일부러 넘기는 테스트를 꼭 두어야 합니다.
MAX_KEYS로 키 개수만 제한하는 것도 위험합니다. 리프에는 가변 길이 값이 함께 들어가므로, 값이 큰 행 100개는 4KB를 훌쩍 넘고 serialize가 페이지 버퍼 밖에 써서 메모리를 오염시킵니다. 실제 엔진은 노드의 바이트 크기로 분할 여부를 판단하고, 한 페이지에 들어가지 않는 큰 값은 SQLite의 오버플로 페이지나 PostgreSQL의 TOAST처럼 별도 페이지로 빼냅니다. 또 루트가 분할되면 root_page_id_가 바뀌는데, 이 값을 메타데이터 페이지(보통 0번 페이지)에 저장하지 않으면 재시작 후 옛 루트부터 탐색해 데이터 절반을 잃게 됩니다.
WAL 기반 트랜잭션 관리
WAL (Write-Ahead Logging)
WAL은 디스크에 변경 전에 로그를 먼저 기록하는 방식입니다. 크래시 시 REDO/UNDO로 복구할 수 있습니다.
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::fstream wal_file_;
std::vector<WALEntry> current_transaction_;
uint64_t next_txn_id_ = 1;
public:
TransactionManager(const std::string& wal_filename) {
wal_file_.open(wal_filename,
std::ios::in | std::ios::out | std::ios::binary | std::ios::app);
}
uint64_t begin_transaction() {
current_transaction_.clear();
return next_txn_id_++;
}
void log_write(uint32_t page_id,
const std::vector<uint8_t>& before,
const std::vector<uint8_t>& after) {
WALEntry entry;
entry.type = WALEntry::UPDATE;
entry.page_id = page_id;
entry.before_image = before;
entry.after_image = after;
current_transaction_.push_back(entry);
}
void commit() {
// WAL에 기록
for (const auto& entry : current_transaction_) {
write_wal_entry(entry);
}
wal_file_.flush();
current_transaction_.clear();
}
void rollback(Pager& pager) {
// UNDO: before_image로 복구
for (auto it = current_transaction_.rbegin();
it != current_transaction_.rend(); ++it) {
auto* page = pager.get_page(it->page_id);
std::memcpy(page->data, it->before_image.data(), PAGE_SIZE);
page->dirty = true;
}
current_transaction_.clear();
}
void recover(Pager& pager) {
wal_file_.seekg(0, std::ios::beg);
while (wal_file_.peek() != EOF) {
auto entry = read_wal_entry();
// REDO: after_image 적용
auto* page = pager.get_page(entry.page_id);
std::memcpy(page->data, entry.after_image.data(), PAGE_SIZE);
page->dirty = true;
}
pager.flush_all();
}
private:
void write_wal_entry(const WALEntry& entry) {
uint8_t type = static_cast<uint8_t>(entry.type);
wal_file_.write(reinterpret_cast<const char*>(&type), sizeof(type));
wal_file_.write(reinterpret_cast<const char*>(&entry.page_id), sizeof(entry.page_id));
uint32_t before_size = entry.before_image.size();
wal_file_.write(reinterpret_cast<const char*>(&before_size), sizeof(before_size));
wal_file_.write(reinterpret_cast<const char*>(entry.before_image.data()), before_size);
uint32_t after_size = entry.after_image.size();
wal_file_.write(reinterpret_cast<const char*>(&after_size), sizeof(after_size));
wal_file_.write(reinterpret_cast<const char*>(entry.after_image.data()), after_size);
}
WALEntry read_wal_entry() {
WALEntry entry;
uint8_t type;
wal_file_.read(reinterpret_cast<char*>(&type), sizeof(type));
entry.type = static_cast<WALEntry::Type>(type);
wal_file_.read(reinterpret_cast<char*>(&entry.page_id), sizeof(entry.page_id));
uint32_t before_size;
wal_file_.read(reinterpret_cast<char*>(&before_size), sizeof(before_size));
entry.before_image.resize(before_size);
wal_file_.read(reinterpret_cast<char*>(entry.before_image.data()), before_size);
uint32_t after_size;
wal_file_.read(reinterpret_cast<char*>(&after_size), sizeof(after_size));
entry.after_image.resize(after_size);
wal_file_.read(reinterpret_cast<char*>(entry.after_image.data()), after_size);
return entry;
}
};이 TransactionManager는 WAL의 뼈대만 보여 주며, 실제 복구에 필요한 몇 가지가 빠져 있습니다. 먼저 로그에 트랜잭션 경계가 없습니다. 커밋 시 엔트리를 차례로 쓰다가 세 번째 엔트리를 쓰는 도중 크래시가 나면, recover()는 앞의 두 엔트리만 REDO해 트랜잭션의 일부만 반영된 상태를 만듭니다. 원자성을 지키려면 엔트리들 뒤에 COMMIT 레코드(트랜잭션 ID 포함)를 쓰고 fsync한 뒤에야 커밋 성공으로 응답하며, 복구 시에는 COMMIT 레코드가 있는 트랜잭션만 REDO해야 합니다. 마지막 엔트리가 잘려 있을 수 있으므로 각 레코드에 길이와 CRC 같은 체크섬을 두고, 검증에 실패한 지점에서 로그 읽기를 멈추는 것도 필요합니다(아래 “WAL 복구 후 데이터 손실” 항목).
commit()의 wal_file_.flush() 역시 OS 버퍼로 넘길 뿐이라 이것만으로는 내구성(D)이 보장되지 않습니다. 그리고 복구가 끝난 뒤에도 WAL을 비우지 않으므로 재시작할 때마다 같은 로그를 전부 다시 적용하고, 파일은 계속 커집니다. 아래 운영 패턴의 “체크포인트”처럼 페이지를 모두 디스크에 반영한 시점을 기록하고 그 이전 로그를 잘라 내는 과정이 함께 있어야 합니다. 참고로 이 글의 WAL은 페이지 전체의 before/after 이미지를 남기는 물리 로깅이라 구현이 단순한 대신 로그가 크고, 실제 엔진은 ARIES처럼 LSN(로그 순번)을 페이지마다 기록해 “이 페이지에 이미 반영된 로그는 건너뛰는” 방식으로 복구 시간을 줄입니다.
제목에 MVCC가 들어 있지만 이 글의 엔진은 MVCC를 구현하지 않습니다. MVCC는 행을 제자리에서 덮어쓰는 대신 새 버전을 추가하고, 각 버전에 “만든 트랜잭션 ID”와 “지운 트랜잭션 ID”를 기록해 읽는 트랜잭션이 자신의 시작 시점 스냅샷에 보이는 버전만 고르게 하는 방식입니다. 이렇게 하면 읽기가 쓰기를 기다리지 않지만, 더 이상 아무도 보지 않는 옛 버전을 치우는 작업(PostgreSQL의 VACUUM)이 필요해집니다. WAL은 “크래시에서 살아남기”, MVCC는 “동시 실행 중 일관된 읽기”를 담당하는 별개의 메커니즘이라 둘을 함께 쓰는 엔진이 많습니다.
간단한 SQL 쿼리 파서
토큰화와 구문 분석
struct SelectStatement {
std::vector<std::string> columns;
std::string table_name;
std::optional<std::string> where_clause;
};
class SQLParser {
public:
SelectStatement parse_select(const std::string& sql) {
SelectStatement stmt;
// 간단한 토크나이저
std::istringstream iss(sql);
std::string token;
// SELECT
iss >> token;
if (token != "SELECT") {
throw std::runtime_error("Expected SELECT");
}
// 컬럼 목록
std::string columns_str;
std::getline(iss, columns_str, ' ');
// FROM 전까지 읽기
while (iss >> token && token != "FROM") {
columns_str += " " + token;
}
// 컬럼 파싱
std::istringstream col_stream(columns_str);
std::string col;
while (std::getline(col_stream, col, ',')) {
col.erase(0, col.find_first_not_of(" \t"));
col.erase(col.find_last_not_of(" \t") + 1);
stmt.columns.push_back(col);
}
// 테이블 이름
iss >> stmt.table_name;
// WHERE 절 (선택사항)
if (iss >> token && token == "WHERE") {
std::string where;
std::getline(iss, where);
stmt.where_clause = where;
}
return stmt;
}
};실행 계획 최적화
쿼리 최적화
struct QueryPlan {
enum Type { FULL_SCAN, INDEX_SCAN } type;
std::string table_name;
std::optional<std::string> index_name;
std::function<bool(const std::vector<std::string>&)> filter;
};
class QueryOptimizer {
std::unordered_map<std::string, std::vector<std::string>> table_indexes_;
public:
QueryPlan optimize(const SelectStatement& stmt) {
QueryPlan plan;
plan.table_name = stmt.table_name;
if (stmt.where_clause) {
// WHERE 절 분석
auto condition = parse_where(*stmt.where_clause);
// 인덱스 사용 가능 여부 확인
if (can_use_index(stmt.table_name, condition.column)) {
plan.type = QueryPlan::INDEX_SCAN;
plan.index_name = condition.column;
} else {
plan.type = QueryPlan::FULL_SCAN;
}
plan.filter = create_filter(condition);
} else {
plan.type = QueryPlan::FULL_SCAN;
plan.filter = [](const std::vector<std::string>&) { return true; };
}
return plan;
}
private:
struct Condition {
std::string column;
std::string op;
std::string value;
};
Condition parse_where(const std::string& where_clause) {
// 간단한 파싱: "column = value"
std::istringstream iss(where_clause);
Condition cond;
iss >> cond.column >> cond.op >> cond.value;
return cond;
}
bool can_use_index(const std::string& table, const std::string& column) {
auto it = table_indexes_.find(table);
if (it == table_indexes_.end()) return false;
return std::find(it->second.begin(), it->second.end(), column)
!= it->second.end();
}
std::function<bool(const std::vector<std::string>&)> create_filter(const Condition& cond) {
return [cond](const std::vector<std::string>& row) {
// 간단한 비교 (실제로는 컬럼 인덱스 필요)
if (cond.op == "=") {
return row[0] == cond.value; // 예시
}
return false;
};
}
};이 옵티마이저는 인덱스가 있으면 무조건 INDEX_SCAN을 고르지만, 실제 옵티마이저는 선택도(selectivity)를 봅니다. WHERE age > 10처럼 테이블의 90%가 조건을 만족한다면, 인덱스로 행마다 페이지를 무작위로 읽는 것보다 전체를 순차로 읽는 편이 빠르기 때문입니다. 그래서 PostgreSQL이나 MySQL은 컬럼 값 분포 통계(히스토그램)를 모아 두고, 예상 행 수와 I/O 비용을 계산해 계획을 고릅니다. create_filter가 row[0]만 비교하고 = 외의 연산자는 항상 false를 돌려주는 것도 예제용 단순화라, 아래 실행 예시의 age > 28은 실제로는 결과가 나오지 않습니다. 컬럼 이름을 스키마의 인덱스로 바꾸고, 문자열이 아닌 타입별로 비교하는 단계가 필요합니다.
통합 Database 클래스와 실행 예시
통합 Database 클래스
class Database {
Pager pager_;
TransactionManager txn_mgr_;
SQLParser parser_;
QueryOptimizer optimizer_;
std::unordered_map<std::string, std::unique_ptr<Table>> tables_;
public:
Database(const std::string& db_file)
: pager_(db_file),
txn_mgr_(db_file + ".wal") {
// 복구
txn_mgr_.recover(pager_);
}
void create_table(const Schema& schema) {
tables_[schema.table_name] = std::make_unique<Table>(schema, pager_);
}
void execute(const std::string& sql) {
// 단순화를 위해 SELECT만 처리합니다.
// INSERT/UPDATE/DELETE는 각각 별도 파서·실행 경로가 필요하며,
// 위 SQLParser::parse_select는 SELECT가 아니면 예외를 던집니다.
// 실제 엔진이라면 첫 토큰을 보고 파서를 분기하는 라우팅 계층이 필요합니다.
auto stmt = parser_.parse_select(sql);
auto plan = optimizer_.optimize(stmt);
auto* table = tables_[plan.table_name].get();
auto results = table->select(plan.filter);
// 결과 출력
for (const auto& row : results) {
for (const auto& val : row) {
std::cout << val << " ";
}
std::cout << "\n";
}
}
void begin_transaction() {
txn_mgr_.begin_transaction();
}
void commit() {
txn_mgr_.commit(); // 1. WAL을 먼저 기록 (write-ahead)
pager_.flush_all(); // 2. 그다음 데이터 페이지 반영
}
void rollback() {
txn_mgr_.rollback(pager_);
}
};commit()에서 호출 순서가 곧 WAL의 규칙입니다. 원래 코드처럼 pager_.flush_all()을 먼저 하면, 데이터 파일에 페이지 일부를 쓰다가 크래시가 났을 때 WAL에는 아직 아무 기록이 없어 되돌리지도, 다시 적용하지도 못하는 반쯤 쓰인 파일이 남습니다. 로그를 먼저 쓰고(실제로는 fsync까지) 데이터 페이지를 나중에 써야 어느 시점에 크래시가 나도 로그를 기준으로 일관된 상태를 복원할 수 있습니다. 실제 엔진은 데이터 페이지를 커밋 시점에 강제로 쓰지 않고(no-force) 체크포인트 때 모아서 쓰기 때문에, 커밋 지연은 로그 fsync 한 번으로 줄어듭니다. 이 순서 하나 때문에 “크래시 테스트를 하면 가끔 파일이 깨진다”는 문제를 오래 찾는 경우가 많은데, 저라면 이런 엔진을 만들 때 가장 먼저 쓰기 도중 프로세스를 강제 종료하는 테스트부터 만들겠습니다.
실행 예시: 사용자 테이블 생성 및 쿼리
주의: 아래 예시의 db.execute("INSERT ...") 호출은 흐름을 보여주기 위한 것으로, 위 Database::execute는 SELECT 파서만 연결되어 있어 실제로는 INSERT 문에서 예외가 발생합니다. 완전히 동작하게 하려면 SQLParser에 INSERT 파싱을 추가하고, execute()가 첫 토큰(SELECT/INSERT/UPDATE/DELETE)에 따라 적절한 파서·실행 경로로 분기하도록 확장해야 합니다.
// main.cpp
#include <iostream>
#include "database.h"
int main() {
Database db("mydb.dat");
// 스키마 정의
Schema user_schema;
user_schema.table_name = "users";
user_schema.columns = {
{"id", Column::INT, 4},
{"name", Column::VARCHAR, 64},
{"age", Column::INT, 4}
};
user_schema.primary_keys = {"id"};
// 테이블 생성 및 데이터 삽입
db.create_table(user_schema);
db.begin_transaction();
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();
// SELECT 쿼리
db.execute("SELECT id, name, age FROM users WHERE age > 28");
// 출력: 1 Alice 30
// 3 Charlie 35
return 0;
}잘못된 페이지 읽기, B-Tree 삽입 오류, WAL 복구 손실: 에러 해결
”Page not found” 또는 잘못된 페이지 읽기
원인: 빈 파일에서 get_page(0) 호출 시 num_pages_=0이라 0바이트 읽음. 해결: else 분기에서 std::memset(page->data, 0, PAGE_SIZE)로 초기화하고 num_pages_ = std::max(num_pages_, page_id + 1)로 갱신.
B-Tree 삽입 시 “vector subscript out of range”
원인: 리프 노드가 비어 있을 때 node.values에 접근. 해결: num_keys와 동기화, values.resize 후 insert.
WAL 복구 후 데이터 손실
원인: recover()에서 커밋되지 않은 트랜잭션까지 REDO 적용하거나 WAL 손상. 해결: WAL 엔트리에 magic·checksum 추가해 무결성 검증.
캐시 메모리 폭증
원인: Pager 캐시에 제한이 없음. 해결: MAX_CACHED_PAGES(예: 1000)로 LRU 캐시 구현. evict_lru_page()로 가장 오래된 dirty 페이지 flush 후 제거.
SQL 파서 “Expected SELECT” 에러
원인: 대소문자 구분, 앞뒤 공백. 해결: to_upper(token)으로 정규화 후 비교, "Expected SELECT, got: " + token으로 에러 메시지 출력.
배치 플러시·그룹 커밋·프리페치로 성능 올리기
배치 플러시
한 트랜잭션 내 여러 페이지 수정 시, 커밋 시점에 한 번에 플러시하면 I/O 횟수를 줄일 수 있습니다.
// ✅ 커밋 시에만 flush
void commit() {
for (const auto& entry : current_transaction_) {
write_wal_entry(entry);
}
wal_file_.flush();
// Pager는 commit()에서 한 번에 flush
pager_.flush_all();
current_transaction_.clear();
}페이지 정렬 플러시
디스크는 순차 I/O가 랜덤 I/O보다 훨씬 빠릅니다. dirty 페이지를 page_id 순으로 정렬해 플러시하면 디스크 헤드 이동을 줄입니다.
void flush_all() {
std::vector<uint32_t> dirty_ids;
for (const auto& [id, page] : cache_) {
if (page->dirty) dirty_ids.push_back(id);
}
std::sort(dirty_ids.begin(), dirty_ids.end());
for (uint32_t id : dirty_ids) {
flush_page(id);
}
}B-Tree 노드 크기 튜닝
MAX_KEYS를 페이지 크기에 맞게 조정하면 트리 높이를 줄일 수 있습니다. 4KB 페이지에서 int32 키 + 4바이트 자식 페이지 ID 기준 내부 노드는 최대 약 340개 키를 담을 수 있고, 아래는 여유를 두어 200으로 잡은 예입니다. 리프는 값 크기에 따라 들어가는 개수가 달라지므로 앞에서 말한 바이트 기준 분할이 필요합니다. 팬아웃이 200이면 3단계 트리로 약 800만 개 키를 다룰 수 있어, 루트와 두 번째 단계를 캐시에 두면 대부분의 조회가 디스크 읽기 한 번으로 끝납니다.
// PAGE_SIZE 4096, 키 4바이트, 자식 4바이트
// 내부 노드: 1 + 4 + num_keys*4 + (num_keys+1)*4 <= 4096
// num_keys <= 340
static constexpr size_t MAX_KEYS = 200; // 여유 있게WAL 그룹 커밋
여러 트랜잭션이 동시에 커밋할 때, WAL 쓰기를 묶어서 fsync 횟수를 줄입니다. 10ms 대기 후 또는 100개 엔트리 모이면 배치 flush.
프리페치
범위 스캔 시 다음 페이지를 미리 읽어 I/O 대기 시간을 숨깁니다. pager_.prefetch(next_leaf_page_id) 호출로 다음 리프를 비동기 로드합니다.
체크포인트·백업·설정 외부화
스레드 안전성
다중 스레드에서 Pager 접근 시 std::shared_mutex로 보호. get_page는 shared_lock, flush_page는 unique_lock 사용.
체크포인트
WAL이 무한히 커지지 않도록 주기적으로 pager_.flush_all() 후 WAL 파일을 비웁니다. truncate로 WAL을 초기화하고 다시 app 모드로 열면 됩니다.
헬스 체크
wal_size_bytes, cache_size, cache_hits, cache_misses를 추적하고 hit_ratio = cache_hits / (cache_hits + cache_misses)로 모니터링합니다.
백업 및 복원
온라인 백업 시 WAL을 함께 복사합니다.
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);
}설정 외부화
struct DBConfig {
size_t page_size = 4096;
size_t max_cached_pages = 1000;
size_t wal_checkpoint_interval = 1000;
bool fsync_on_commit = true;
};컴포넌트별 역할 요약
| 컴포넌트 | 역할 |
|---|---|
| Pager | 페이지 기반 저장 |
| B-Tree | 인덱스 구조 |
| WAL | 트랜잭션 로그 |
| Parser | SQL 파싱 |
| Optimizer | 쿼리 최적화 |
핵심 원칙:
- 페이지 단위로 I/O 최소화
- B-Tree로 빠른 검색
- WAL로 ACID 보장
- 인덱스 활용으로 성능 향상
- 쿼리 최적화로 효율성 확보