一、前言
数据库DBMS是当前互联网开发者最熟悉的基础设施之一，很多后端开发者的入门项目就是一个简单的基于MySQL的数据管理系统。笔者一直想自己编写一个简单的SQL数据库，正好最近正在学习RocksDB和Zig语言的内容，就想利用这个机会作为学习成果的检验，于是就有了这个小项目。
话不多说，先来看看这个小项目成品的效果：
当然这个小小的数据库只支持创建表、插入和简单查询的能力，并不包含复杂SQL、索引、多租户、事务等高级功能，有兴趣的同学可以自行扩展。
二、什么是RocksDB
RocksDB是由Facebook开发的一款高效的嵌入式键值存储引擎，基于Google的LevelDB进行了多项优化。它主要用于快速存储和高并发读写场景，特别适合在闪存等快速存储介质上运行。
RocksDB是C++开发的，不过它提供了一套C语言API，为不会C++的开发者提供了便利。
三、什么是Zig语言
Zig语言是一种新兴的系统编程语言，由Andrew Kelley于2015年开始开发。其设计目标是改进C语言，并借鉴Rust等其他语言的优点。Zig强调强健性、最佳性和可维护性，并致力于提供高效的手动内存管理和编译时特性。
Zig语言对开发者来说最好的一点就是简单（特别相比Rust来说，Rust笔者已经学了好几次都没能入门），如果你熟悉Rust或者C语言，那么上手Zig只需要2~3天，就算完全没有C家族语言的经验，2周也足够学这门语言。
Zig语言有这些值得关注的特点：
- 并没有提供类似Rust的生命周期管理，所以需要手动管理内存和C一样；
- Zig支持编译时执行代码（comptime），允许开发者在编译期间进行类型操作和函数调用，从而提高性能和灵活性（Go语言开发者默泪）；
- 可以无缝衔接C语言的API，继承C生态的库非常简单；
- 强大的编译工具ZigCC，ZigCC 是一个强大的工具，旨在简化 C/C++ 项目的编译过程，同时提供现代编程语言的优势。它不仅提高了编译效率，还通过增量编译和高效的二进制生成，帮助开发者更好地管理和维护他们的代码库。
四、项目结构
为了实现这个简单SQL数据库，我们可以按照如下的架构来对这个项目做功能分层：
接下来，我们就分模块详解介绍。
五、实现解析
RocksDB Layer
我们第一步先完成对RocksDB库的桥接，RocksDB虽然提供了C的API，但是并没有过多的文档说明，好在RocksDB提供了一些使用的例子，我们可以根据这些例子知道这些API的用法。
Zig集成C语言的三方库非常容易：
- 首先，我们把RocksDB的API声明加入项目的include目录
- 第二步，我们添加一个RocksDB.zig文件，调用header中的API，由于这个项目比较简单，所以我们只需要set/get/iteration这几个简单的API：
const std = @import("std");
const rdb = @cImport(@cInclude("rocksdb.h"));
pub const Iter = @import("iter.zig").Iter;
pub fn init(allocator: std.mem.Allocator, dir: []const u8) !Self {
const options: ?*rdb.rocksdb_options_t = rdb.rocksdb_options_create();
rdb.rocksdb_options_set_create_if_missing(options, 1);
var err: ?[*:0]u8 = null;
const db = rdb.rocksdb_open(options, dir.ptr, &err);
const r = Self{
.db = db.?,
.allocator = allocator,
.dir = dir,
};
if (err) |errStr| {
std.log.err("Failed to open RocksDB: {s}.\n", .{errStr});
return RocksdbErrors.RocksDBOpenError;
}
return r;
}
pub fn deinit(self: Self) void {
rdb.rocksdb_close(self.db);
}
pub fn set(self: Self, key: []const u8, value: []const u8) !void {
const writeOptions = rdb.rocksdb_writeoptions_create();
var err: ?[*:0]u8 = null;
rdb.rocksdb_put(
self.db,
writeOptions,
key.ptr,
key.len,
value.ptr,
value.len,
&err,
);
if (err) |errStr| {
std.log.err("Failed to write RocksDB: {s}.\n", .{errStr});
return RocksdbErrors.RocksDBWriteError;
}
}
pub fn get(self: Self, key: []const u8, buf: *std.ArrayList(u8)) !void {
const readOptions = rdb.rocksdb_readoptions_create();
var value_length: usize = 0;
var err: ?[*:0]u8 = null;
const v = rdb.rocksdb_get(
self.db,
readOptions,
key.ptr,
key.len,
&value_length,
&err,
);
if (v == null) {
return;
}
if (err) |errStr| {
std.log.err("Failed to read RocksDB: {s}.\n", .{errStr});
return RocksdbErrors.RocksDBReadError;
}
for (0..value_length) |i| {
try buf.append(v[i]);
}
}
pub fn getIter(self: Self, prefix: []const u8) !Iter {
return Iter.init(self.db, prefix);
}
const rocksdb_unit_tests = b.addTest(.{
.root_source_file = b.path("src/Rocksdb.zig"),
.target = target,
.optimize = optimize,
});
rocksdb_unit_tests.linkLibC();
rocksdb_unit_tests.addIncludePath(LazyPath{ .cwd_relative = "./include" });
rocksdb_unit_tests.linkSystemLibrary("rocksdb");
rocksdb_unit_tests.addLibraryPath(LazyPath{ .cwd_relative = "/opt/homebrew/lib" });
const run_rocksdb_unit_tests = b.addRunArtifact(rocksdb_unit_tests);
Lexer
在完成了RocksDB的桥接层后，我们可以着手编写SQL语句的词法分析器。顾名思义，词法分析就是将用户输入的SQL语句转换为一组Token的过程。
- 第一步，我们需要总结一下SQL语句中总共有哪些分词：
分析上述的几个SQL语句，我们可以将Token分为如下分类：
pub const Kind = enum {
unknown,
// ----------- 保留关键字 ------------
select_keyword, // select
create_table_keyword, // create table
insert_keyword, // insert into
values_keyword, // values
from_keyword, // from
where_keyword,// where
// ----------- 运算符关键字 -------------
plus_operator,// +
equal_operator,// =
lt_operator,// <
gt_operator, // >
concat_operator, // ||
// ---------- 符号关键字 -------------
left_paren_syntax, // (
right_paren_syntax, // )
comma_syntax, // ,
identifier, // 普通标识符
integer, // 整型
string, // 字符串
pub fn toString(self: Kind) []const u8 {
return @tagName(self);
}
};
const BUILTINS = [_]Builtin{
.{ .name = "CREATE TABLE", .Kind = Token.Kind.create_table_keyword },
.{ .name = "INSERT INTO", .Kind = Token.Kind.insert_keyword },
.{ .name = "SELECT", .Kind = Token.Kind.select_keyword },
.{ .name = "VALUES", .Kind = Token.Kind.values_keyword },
.{ .name = "WHERE", .Kind = Token.Kind.where_keyword },
.{ .name = "FROM", .Kind = Token.Kind.from_keyword },
.{ .name = "||", .Kind = Token.Kind.concat_operator },
.{ .name = "=", .Kind = Token.Kind.equal_operator },
.{ .name = "+", .Kind = Token.Kind.plus_operator },
.{ .name = "<", .Kind = Token.Kind.lt_operator },
.{ .name = ">", .Kind = Token.Kind.gt_operator },
.{ .name = "(", .Kind = Token.Kind.left_paren_syntax },
.{ .name = ")", .Kind = Token.Kind.right_paren_syntax },
.{ .name = ",", .Kind = Token.Kind.comma_syntax },
};
start: u64,
end: u64,
kind: Kind,
source: []const u8,
pub fn init(start: u64, end: u64, kind: Kind, source: []const u8) Self {
return Self{
.start = start,
.end = end,
.kind = kind,
.source = source,
};
}
pub fn getKind(self: Self) Kind {
return self.kind;
}
pub fn string(self: Self) []const u8 {
return self.source[self.start..self.end];
}
fn nextKeyword(self: *LexIterator) ?Token {
var longest_len: usize = 0;
var kind = Token.Kind.unknown;
for (BUILTINS) |builtin| {
if (self.index + builtin.name.len > self.source.len) continue;
// 大小写不敏感
if (asciiCaseInsensitiveEqual(self.source[self.index .. self.index + builtin.name.len], builtin.name)) {
longest_len = builtin.name.len;
kind = builtin.Kind;
break;
}
}
// 由于我们关键字是按长度倒排序的，所以匹配到的一定是最长的keyword
if (longest_len == 0) return null;
defer self.index += longest_len;
return Token.init(self.index, self.index + longest_len, kind, self.source);
}
fn nextInteger(self: *LexIterator) ?Token {
var end = self.index;
var i = self.index;
while (i < self.source.len and self.source[i] >= '0' and self.source[i] <= '9') {
end += 1;
i += 1;
}
if (self.index == end) return null;
defer self.index = end;
return Token.init(self.index, end, Token.Kind.integer, self.source);
}
fn nextString(self: *LexIterator) ?Token {
var i = self.index;
if (self.source[i] != '\'') return null;
i += 1;
const start = i;
var end = i;
while (i < self.source.len and self.source[i] != '\'') {
end += 1;
i += 1;
}
if (self.source[i] == '\'') i += 1;
if (start == end) return null;
defer self.index = i;
return Token.init(start, end, Token.Kind.string, self.source);
}
fn nextIdentifier(self: *LexIterator) ?Token {
var i = self.index;
var end = self.index;
while (i < self.source.len and ((self.source[i] >= 'a' and self.source[i] <= 'z') or (self.source[i] >= 'A' and self.source[i] <= 'Z') or self.source[i] == '*')) {
i += 1;
end += 1;
}
if (self.index == end) return null;
defer self.index = end;
return Token.init(self.index, end, Token.Kind.identifier, self.source);
}
- 第五步，按照关键字>整型>字符串>普通标识符的优先级完成Lexer
pub fn hasNext(self: *LexIterator) bool {
self.index = eatWhitespace(self.source, self.index);
return self.index < self.source.len;
}
pub fn next(self: *LexIterator) !Token {
// std.debug.print("index: {d}, len: {d}, src: {s}\n", .{ self.index, self.source.len, self.source[self.index..] });
self.index = eatWhitespace(self.source, self.index);
if (self.index >= self.source.len) return error.OutOfSource;
if (self.nextKeyword()) |token| {
return token;
}
if (self.nextInteger()) |token| {
return token;
}
if (self.nextString()) |token| {
return token;
}
if (self.nextIdentifier()) |token| {
return token;
}
return error.BadToken;
}
AST
有了词法分析，我们就得到了SQL语句的一串Token，此时，我们需要语法分析将这些没什么具体意义的Token拼装成符合SQL语义的AST。
首先，我们需要分析中SQL语法中有哪些语法单元，我们在这里一一列举，逐个分析。
例如select name, age from dewuer where age > 10这个语句中name、age、age > 10都是表达式，表达式要么是一段字面逻辑，要么是一段计算逻辑。
所以，我们可以编写出表达式的数据结构：
pub const ExpressionAST = union(enum) {
literal: Token, // 字面逻辑
binary_operation: BinaryOperationAST, // 计算逻辑
pub fn deinit(self: ExpressionAST) void {
switch (self) {
.binary_operation => |m| {
var bin = m;
bin.deinit();
},
else => {},
}
}
};
pub const BinaryOperationAST = struct {
operator: Token,
allocator: std.mem.Allocator,
left: *ExpressionAST,
right: *ExpressionAST,
pub fn init(
allocator: std.mem.Allocator,
operator: Token,
) !BinaryOperationAST {
return .{
.operator = operator,
.allocator = allocator,
.left = try allocator.create(ExpressionAST),
.right = try allocator.create(ExpressionAST),
};
}
pub fn deinit(self: BinaryOperationAST) void {
self.left.deinit();
self.allocator.destroy(self.left);
self.right.deinit();
self.allocator.destroy(self.right);
}
};
以一个Select的SQL语句为例：SELECT age, name FROM dewuer WHERE age > 10
不难分析出，一个Select语法由如下元素构成：
- 选择的columns；
- 数据表Table；
- 选择条件where(optional)；
综上，我们给出Select语法树的数据结构：
pub const SelectAST = struct {
columns: []ExpressionAST, // 选择字段
from: Token, // 数据表
where: ?ExpressionAST, // where条件 ?表示可以为null
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) SelectAST {
return .{
.columns = undefined,
.from = undefined,
.where = null,
.allocator = allocator,
};
}
pub fn deinit(self: *SelectAST) void {
for (self.columns) |m| {
var col = m;
col.deinit();
}
self.allocator.free(self.columns);
if (self.where) |m| {
var where = m;
where.deinit();
}
}
};
以一个Create Table的sql语句为例子：CREATE TABLE dewuer (year int, age int, name text)
不难分析出，一个Create Table语法由如下元素构成：
- 数据表Table；
- 表字段的(字段名，字段类型)数组；
由此，我们可以给出Create Table语法树的数据结构：
pub const CreateTableColumnAST = struct {
name: Token, // 字段名
kind: Token, // 字段类型，目前只支持string和int
pub fn init() CreateTableColumnAST {
return .{
.name = undefined,
.kind = undefined,
};
}
};
pub const CreateTableAST = struct {
table: Token, // 数据表
columns: []CreateTableColumnAST, // 表字段定义
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) CreateTableAST {
return .{
.table = undefined,
.columns = undefined,
.allocator = allocator,
};
}
pub fn deinit(self: *CreateTableAST) void {
self.allocator.free(self.columns);
}
};
以一个Insert的SQL语句为例子：INSERT INTO dewuer VALUES (2010, 35, 'Zhangsan')
这个语法最为简单，只有2个基本元素：
由此，我们可以给出Insert语法的数据结构：
pub const InsertAST = struct {
table: Token, // 数据表
values: []ExpressionAST, // 插入赋值
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) InsertAST {
return .{
.table = undefined,
.values = undefined,
.allocator = allocator,
};
}
pub fn deinit(self: *InsertAST) void {
for (self.values) |m| {
var value = m;
value.deinit();
}
self.allocator.free(self.values);
}
};
Parser
有了各类AST的定义之后，我们需要完成语法分析，即从Tokens到AST的分析过程：
@spec parse(tokens) -> AST
与AST的分析步骤类似，我们也是按照AST的种类来逐一编写分析器：
在AST分析篇幅中，我们已经知道了基本表达式分为字面逻辑和计算逻辑两类，这里我们可以进一步归纳：
- token中遇到string\整型\普通标识符时，我们可以归纳为字面逻辑；
- token中遇到+><=这些关键字时，我们需要递归分析这些符号前后两个表达式，构建为一个计算逻辑，这里前后表达式分析任然可能为计算逻辑，例如select * from xxx where (age + (2+1) ) > (year - 4)；
综上，我们可以编写出基本表达式的分析过程：
fn isExpectTokenKind(tokens: []Token, index: usize, kind: Token.Kind) bool {
if (index >= tokens.len) {
return false;
}
return tokens[index].kind == kind;
}
fn parseExpression(
self: Self,
tokens: []Token,
index: *usize,
) !ast.ExpressionAST {
var i = index.*;
var e: ast.ExpressionAST = undefined;
// 字符串、整型和普通标识符
if (isExpectTokenKind(
tokens,
i,
Token.Kind.string,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.integer,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.identifier,
)) {
e = .{ .literal = tokens[i] };
index.* += 1;
} else {
return ParserError.InvalidStatement;
}
i += 1;
// 计算符号
if (isExpectTokenKind(
tokens,
i,
Token.Kind.equal_operator,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.lt_operator,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.gt_operator,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.plus_operator,
) or isExpectTokenKind(
tokens,
i,
Token.Kind.concat_operator,
)) {
const new_expression = ast.ExpressionAST{
.binary_operation = try ast.BinaryOperationAST.init(
self.allocator,
tokens[i],
),
};
new_expression.binary_operation.left.* = e;
e = new_expression;
index.* += 1;
const parsed_expression = try self.parseExpression(tokens, index); // 递归分析
e.binary_operation.right.* = parsed_expression;
}
return e;
}
分析Select语法也很简单，可以按照如下流程分析：
这个过程中，分析column表达式的过程需要注意，当有多个选择字段时，需要判断字段中间的逗号分隔符。
实现代码如下：
fn parseSelect(
self: Self,
tokens: []Token,
) !ast.SelectAST {
var i: usize = 0;
// expect select keyword
if (!isExpectTokenKind(tokens, i, Token.Kind.select_keyword)) {
return ParserError.ExpectSelectKeyword;
}
i += 1;
var columns = std.ArrayList(ast.ExpressionAST).init(self.allocator);
var select = ast.SelectAST.init(self.allocator);
// 分析columns
while (!isExpectTokenKind(tokens, i, Token.Kind.from_keyword)) {
if (columns.items.len > 0) { // 不止一个字段时，expect逗号分隔符
if (!isExpectTokenKind(tokens, i, Token.Kind.comma_syntax)) {
return ParserError.ExpectCommaSyntax;
}
i += 1;
}
// 分析columns表达式
const parsed_expression = try self.parseExpression(
tokens,
&i,
);
defer parsed_expression.deinit();
try columns.append(parsed_expression);
}
select.columns = try columns.toOwnedSlice();
if (select.columns.len == 0) { // columns不能为空
return ParserError.ExpectIdentifier;
}
i += 1;
// table name
if (!isExpectTokenKind(tokens, i, Token.Kind.identifier)) {
return ParserError.ExpectIdentifier;
}
select.from = tokens[i];
i += 1;
// 分析where条件
if (isExpectTokenKind(tokens, i, Token.Kind.where_keyword)) {
i += 1;
const parsed_expression = try self.parseExpression(
tokens,
&i,
);
select.where = parsed_expression;
}
return select;
}
建表的语法可以按照如下流程分析：
注意此处建表的columns相较于Select语法的columns有点不同，建表的columns不仅有字段名的标识符，还有类型标识，其余的逻辑与Select语法的columns分析方法一致：
fn parseCreateTable(self: Self, tokens: []Token) !ast.CreateTableAST {
var i: usize = 0;
// create table
if (!isExpectTokenKind(tokens, i, Token.Kind.create_table_keyword)) {
return ParserError.ExpectCreateKeyword;
}
i += 1;
// table name
if (!isExpectTokenKind(tokens, i, Token.Kind.identifier)) {
return ParserError.ExpectIdentifier;
}
var create_table_ast = ast.CreateTableAST.init(self.allocator);
create_table_ast.table = tokens[i];
i += 1;
// columns: (field1 type, field2 type,...)
var columns = std.ArrayList(ast.CreateTableColumnAST).init(self.allocator);
if (!isExpectTokenKind(tokens, i, Token.Kind.left_paren_syntax)) {
return ParserError.ExpectLeftParenSyntax;
}
i += 1;
while (!isExpectTokenKind(tokens, i, Token.Kind.right_paren_syntax)) {
if (columns.items.len > 0) {
if (!isExpectTokenKind(tokens, i, Token.Kind.comma_syntax)) {
return ParserError.ExpectCommaSyntax;
}
i += 1;
}
var column = ast.CreateTableColumnAST.init();
if (!isExpectTokenKind(tokens, i, Token.Kind.identifier)) {
return ParserError.ExpectIdentifier;
}
column.name = tokens[i];
i += 1;
if (!isExpectTokenKind(tokens, i, Token.Kind.identifier)) {
return ParserError.ExpectIdentifier;
}
column.kind = tokens[i];
i += 1;
try columns.append(column);
}
if (columns.items.len == 0) {
return ParserError.EmptyColumns;
}
// )
i += 1;
if (i < tokens.len) {
return ParserError.UnexpectedToken;
}
create_table_ast.columns = try columns.toOwnedSlice();
return create_table_ast;
}
Insert语法相较于建表语法更为简单一些，可以按照如下流程分析：
实现代码如下：
fn parseInsert(self: Self, tokens: []Token) !ast.InsertAST {
var i: usize = 0;
// insert into
if (!isExpectTokenKind(tokens, i, Token.Kind.insert_keyword)) {
return ParserError.ExpectInsertKeyword;
}
i += 1;
// table name
if (!isExpectTokenKind(tokens, i, Token.Kind.identifier)) {
return ParserError.ExpectIdentifier;
}
var insert_ast = ast.InsertAST.init(self.allocator);
insert_ast.table = tokens[i];
i += 1;
// values (val1, val2,...)
var values = std.ArrayList(ast.ExpressionAST).init(self.allocator);
if (!isExpectTokenKind(tokens, i, Token.Kind.values_keyword)) {
return ParserError.ExpectValueKeyword;
}
i += 1;
if (!isExpectTokenKind(tokens, i, Token.Kind.left_paren_syntax)) {
return ParserError.ExpectLeftParenSyntax;
}
i += 1;
while (!isExpectTokenKind(tokens, i, Token.Kind.right_paren_syntax)) {
if (values.items.len > 0) {
if (!isExpectTokenKind(tokens, i, Token.Kind.comma_syntax)) {
return ParserError.ExpectCommaSyntax;
}
i += 1;
}
const exp = try self.parseExpression(tokens, &i);
defer exp.deinit();
try values.append(exp);
}
if (values.items.len == 0) {
return ParserError.EmptyValues;
}
// )
i += 1;
if (i < tokens.len) {
return ParserError.UnexpectedToken;
}
insert_ast.values = try values.toOwnedSlice();
return insert_ast;
}
Table to KV
至此，我们已经完成了SQL语法层面的解析，如果按编程语言的设计行话来说，我们已经完成了这门语言的前端，现在是时候开始后端的工作了。
就我们这个小项目而言，后端的工作就是将SQL的各类AST映射至RocksDB的KV操作上。在开始这项工作之前，我们先介绍一下关系型数据到KV数据的一般映射方法论，这里笔者强烈推荐大家阅读CockroachDB家（www.cockroachlabs.com/）的文档和博客，例如：
- Structured data encoding in CockroachDB SQL
- SQL in CockroachDB: Mapping table data to key-value storage
我们这里也提纲挈领的介绍一下表数据到KV数据转换的基本思想：
现在让我们考虑以下表和数据：
CREATE TABLE dewuer (
id INT PRIMARY KEY,
name STRING,
age INTEGER
)
INSERT INTO dewuer VALUES (10, "Zhangsan", 34)
每个表都必须有一个主键，主键由一个或多个列组成。
在我们上面的dewuer表中，它由一个单独的列id组成。我们将每个非主键列存储在由主键前缀和列名后缀的单独键下， 例如：
我们使用 /dewuer/ 作为表ID的占位符， /name 和 /age 作为列ID的占位符（表中的每一列都有一个在表中唯一的 ID）。
假设dewuer这张表的元数据如下：
那么我们表格中映射数据看起来如下：
有些同学可能认为这些键有很多重叠的前缀，可能造成存储的写放大。这点大家大可不必担心，主流的键值引擎例如RocksDB底层的数据结构都会有类似前缀树这样的压缩能力，所以放心大胆的存就行了。
此时如果我们执行查询语句:
SELECT * FROM dewuer WHERE id = 10
这句SQL就会被映射为：
SCAN(/666/10, /666/10/$) // $代表最大的后缀串
这里有个小问题，如果所有的列都为NULL值，那么KV映射中就什么也不剩了，为了解决这一问题，我们给每个column加上一个哨兵键：
当我们需要二级索引时，例如我们执行如下SQL：
CREATE INDEX dewuer-age ON dewuer (age)
这是一个非唯一索引，所以允许重复值。我们通过引入一个索引ID来实现这一点，该ID对于表中的每个索引都是唯一的，包括主键索引。这样，所有的key格式就演变为如下：
/tableID/indexID/indexColumns[/columnID]
这样，我们的KV表格就变成了这个样子：
当我们执行二级索引查询时例如SQL：SELECT name FROM deuwer WHERE age = 34
此时我们发现这张表存在age的二级索引，于是我们将这局SQL转换为如下的扫描任务：
SCAN(/666/dewuer-age/34/, /666/dewuer-age/34/$)
// 将检索出该键：/666/dewuer-age/34/10
注意，我们检索出的键中包含了索引值和主键索引值，如果查询语句中没有这两项以外的column，那么就不需要再去根据主键索引检索了，这就是平常我们所说的索引覆盖。
而唯一索引的情况有所不同，例如我们执行SQL：
CREATE UNIQUE INDEX uniq-name ON dewuer (name)
与普通索引不同，唯一索引的键仅由索引的部分列组成。存储在键中的值是所有非索引主键列的编码
当我们再次插入一个name=Zhangsan的数据时例如：
INSERT INTO dewuer VALUES (11, "Zhangsan", 35)
就会出现/666/uniq-name/Zhangsan这个键的碰撞导致插入失败，违反了唯一性约束。
Storage
在我们正式开始编写上述的映射逻辑之前，我们先准备好几个数据结构。
Table
一张表由表名、columns、column-types组成，我们的小项目不涉及索引这类高级功能，所以不需要更复杂的元数据。
定义如下：
pub const Table = struct {
name: []const u8,
columns: []const []const u8,
types: []const []const u8,
allocator: std.mem.Allocator,
pub fn init(
allocator: std.mem.Allocator,
name: []const u8,
columns: []const []const u8,
types: []const []const u8,
) Table {
return Table{
.name = name,
.columns = columns,
.types = types,
.allocator = allocator,
};
}
pub fn deinit(self: Table) void {
for (self.columns, 0..) |_, i| {
self.allocator.free(self.columns[i]);
}
self.allocator.free(self.columns);
for (self.types, 0..) |_, i| {
self.allocator.free(self.types[i]);
}
self.allocator.free(self.types);
}
};
一个数据行由每个columns的数据以及关联Table组成：
pub const Row = struct {
const Self = @This();
allocator: std.mem.Allocator,
cells: std.ArrayList(Value),
table: Table,
pub fn init(allocator: std.mem.Allocator, table: Table) Self {
return Self{
.allocator = allocator,
.cells = std.ArrayList(Value).init(allocator),
.table = table,
};
}
pub fn deinit(self: Self) void {
for (self.cells.items) |c| {
c.deinit(self.allocator);
}
self.cells.deinit();
}
pub fn append(self: *Self, cell: Value) !void {
return self.cells.append(try cell.clone(self.allocator));
}
// 取出对应field的值
pub fn get(self: Self, field: []const u8, val: *Value) bool {
if (field.len == 0) {
return false;
}
for (self.table.columns, 0..) |f, i| {
if (std.mem.eql(u8, f, field)) {
val.* = self.cells.items[i];
return true;
}
}
return false;
}
pub fn reset(self: *Self) void {
for (self.cells.items) |c| {
c.deinit(self.allocator);
}
self.cells.clearRetainingCapacity();
}
};
当我们做Select查询时，会对RocksDB执行前缀匹配搜索，所以我们需要一个获取特定前缀的数据行迭代器，该迭代器由RocksDB的迭代器和数据表组成：
const RowIter = struct {
const Self = @This();
iter: Rocksdb.Iter,
row_prefix: []const u8,
allocator: std.mem.Allocator,
table: Table,
fn init(
allocator: std.mem.Allocator,
db: Rocksdb,
row_prefix: []const u8,
table: Table,
) !Self {
const rp = try allocator.dupe(u8, row_prefix);
return .{
.iter = try db.getIter(rp),
.row_prefix = rp,
.allocator = allocator,
.table = table,
};
}
pub fn deinit(self: Self) void {
self.allocator.free(self.row_prefix);
self.iter.deinit();
}
pub fn next(self: *Self) !?Row {
var b: []const u8 = undefined;
if (self.iter.next()) |m| { // 对rocksdb执行前缀搜索
b = m.value;
} else {
return null;
}
var row = Row.init(self.allocator, self.table);
var offset: usize = 0;
while (offset < b.len) {
var buf: []const u8 = undefined;
offset += value.deserializeBytes(b[offset..], &buf);
try row.append(Value.deserialize(buf));
}
return row;
}
};
有了上述的数据结构，我们可以开始着手编写映射逻辑，由于我们这是一个非常简单的玩具项目，没必要非常严格的定义映射模型，甚至我们连主键索引都可以不用，用最简单直白的文本键值对来实现。
由于KV引擎中只能存储二进制数据，所以我们还需要实现一个小小的序列化协议，当然对于网络编程选手来说，这些都是轻车熟路了：
fn serializeInteger(comptime T: type, i: T, buf: *[@sizeOf(T)]u8) void {
std.mem.writeInt(T, buf, i, .big);
}
fn deserializeInteger(comptime T: type, buf: []const u8) T {
return std.mem.readInt(T, buf[0..@sizeOf(T)], .big);
}
// [length: 4bytes][bytes]
pub fn serializeBytes(allocator: std.mem.Allocator, bytes: []const u8) ![]const u8 {
var h: [4]u8 = undefined;
serializeInteger(u32, @intCast(bytes.len), &h);
const parts = [_][]const u8{ &h, bytes };
return std.mem.concat(allocator, u8, &parts);
}
pub fn deserializeBytes(bytes: []const u8, buf: *[]const u8) usize {
const length = deserializeInteger(u32, bytes);
const offset = length + 4;
buf.* = bytes[4..offset];
return offset;
}
pub fn serialize(self: Value, buf: *std.ArrayList(u8)) !void {
switch (self) {
.null_value => return buf.append('0'),
.bool_value => |v| {
try buf.append('1');
return buf.append(if (v) '1' else '0');
},
.string_value => |v| {
try buf.append('2');
return buf.appendSlice(v);
},
.integer_value => |v| {
try buf.append('3');
var b2: [8]u8 = undefined;
serializeInteger(i64, v, &b2);
return buf.appendSlice(b2[0..]);
},
}
}
pub fn deserialize(buf: []const u8) Value {
if (buf.len == 0) {
unreachable;
}
switch (buf[0]) {
'0' => return Value{ .null_value = true },
'1' => {
if (buf[1] == '1') {
return Value{ .bool_value = true };
} else {
return Value{ .bool_value = false };
}
},
'2' => return .{ .string_value = buf[1..] },
'3' => {
return Value{ .integer_value = deserializeInteger(i64, buf[1..]) };
},
else => unreachable,
}
}
当我们执行创建表语句时：
CREATE TABLE dewuer (year int, age int, name text)
我们将其转换为如下键值对用于存储表元数据
@spec serialize(int | string | bool) -> bytes // alias s/1
@spec serializeBytes(bytes) -> bytes // alias sB/1
table_dewuer => |sB(year)|sB(int)|sB(age)|sB(int)|sB(name)|sB(text)|
实现代码如下：
// table_{table} => |{column}|{type}|{column}|{type}|....
pub fn writeTable(self: Self, table: Table) !void {
// table name
const k = try std.fmt.allocPrint(self.allocator, "table_{s}", .{table.name});
defer self.allocator.free(k);
var cb = std.ArrayList(u8).init(self.allocator);
defer cb.deinit();
for (table.columns, 0..) |col, i| {
const b1 = try value.serializeBytes(self.allocator, col);
defer self.allocator.free(b1);
try cb.appendSlice(b1);
const b2 = try value.serializeBytes(self.allocator, table.types[i]);
defer self.allocator.free(b2);
try cb.appendSlice(b2);
}
try self.db.set(k, cb.items);
}
当我们执行插入数据语句时：
INSERT INTO dewuer VALUES (2020, 34, 'Lisi')
我们将其转换为如下键值对：
@spec serialize(int | string | bool) -> bytes // alias s/1
@spec serializeBytes(bytes) -> bytes // alias sB/1
row_dewuer_{random_id()} => sB(s(2020))++sB(s(34))++sB(s('Lisi'))
按照这个模型，我们可以实现插入语句的逻辑：
// row_{tablel}_{id} => {row}
pub fn writeRow(self: Self, table: []const u8, row: Row) !void {
// make sure table exists
if (!try self.tableExists(table)) {
return StorageError.TableNotFound;
}
const buf = try self.allocator.alloc(u8, table.len + 21);
defer self.allocator.free(buf);
var id: [16]u8 = undefined;
generateId(&id); // 生成随机串当做主键
const k = try std.fmt.bufPrint(buf, "row_{s}_{s}", .{ table, id });
// row data
var va = std.ArrayList(u8).init(self.allocator);
defer va.deinit();
for (row.items()) |cell| {
var b = std.ArrayList(u8).init(self.allocator);
defer b.deinit();
try cell.serialize(&b);
const bin = try value.serializeBytes(self.allocator, b.items);
defer self.allocator.free(bin);
try va.appendSlice(bin);
}
return self.db.set(k, va.items);
}
当我们需要从KV中重建出表结构时，就是创建表的逆过程，我们需要重建出表各个字段的名字和类型，生成一个Table结构：
pub fn getTable(self: Self, table_name: []const u8) !?Table {
const k = try std.fmt.allocPrint(self.allocator, "table_{s}", .{table_name});
defer self.allocator.free(k);
var columns = std.ArrayList([]const u8).init(self.allocator);
var types = std.ArrayList([]const u8).init(self.allocator);
// get table info
var b = std.ArrayList(u8).init(self.allocator);
defer b.deinit();
try self.db.get(k, &b);
const detail = b.items;
if (detail.len == 0) {
return null;
}
// rebuild columns
var offset: usize = 0;
while (offset < detail.len) {
var buf: []const u8 = undefined;
offset += value.deserializeBytes(detail[offset..], &buf);
try columns.append(try self.allocator.dupe(u8, buf));
offset += value.deserializeBytes(detail[offset..], &buf);
try types.append(try self.allocator.dupe(u8, buf));
}
return Table.init(
self.allocator,
table_name,
try columns.toOwnedSlice(),
try types.toOwnedSlice(),
);
}
由于我们的数据结构中主键索引是自动生成的随机串，所以没法按主键来查询，我们选择根据Table作为维度，一次性把一张表的数据全部读入内存中，所以Iterator的设计非常简单：
pub fn getRowIter(self: Self, table: Table) !RowIter {
const row_prefix = try std.fmt.allocPrint(self.allocator, "row_{s}", .{table.name});
defer self.allocator.free(row_prefix);
return RowIter.init(self.allocator, self.db, row_prefix, table);
}
Executer
至此，我们已经有了从SQL到AST的前端层，也有了从Table到KV的后端映射层，距离我们完整的SQL引擎只剩下了AST到Table的执行层了。
我们这个项目中AST有4类：表达式AST、SelectAST、CreateTableAST、InsertAST，我们只需要逐个实现它们即可。
表达式AST有2类：字面逻辑表达式和计算逻辑表达式，所以我们的实现中也要分开讨论。
对于字面逻辑较为简单，要么是字符串或者整型、要么是column的名称，只需要从数据行中取出对应column的值即可。
对于计算逻辑则比较复杂，我们需要先递归的计算出计算表达式的两臂，再根据具体计算符号的含义来分别实现，好在我们这个项目中计算符号不多。
一般来说数据类型不一致的无法做计算，不过我们这个项目不考虑强类型的情况，这里可以做一些隐式转换。
fn executeExpression(self: Self, expr: ast.ExpressionAST, row: storage.Row) !Value {
return switch (expr) {
.literal => |literal| {
switch (literal.getKind()) {
.string => return Value{ .string_value = literal.string() },
.integer => return Value{ .integer_value = try std.fmt.parseInt(i64, literal.string(), 10) },
.identifier => { // 普通标记符，一般为column名
var val: Value = undefined;
if (row.get(literal.string(), &val)) {
return val;
}
unreachable;
},
else => unreachable,
}
},
.binary_operation => |binary_operation| {
const left = try self.executeExpression(binary_operation.getLeft(), row);
defer left.deinit(self.allocator);
const right = try self.executeExpression(binary_operation.getRight(), row);
defer right.deinit(self.allocator);
var lb = std.ArrayList(u8).init(self.allocator);
defer lb.deinit();
var rb = std.ArrayList(u8).init(self.allocator);
defer rb.deinit();
// 先将两臂的值都转换为字符串，方便后续的比较逻辑，这里实现有点丑陋==
try left.asString(&lb);
try right.asString(&rb);
switch (binary_operation.getOpKind()) {
// 相等计算 -> 比较两臂字符串是否相等
.equal_operator => return Value{ .bool_value = std.mem.eql(u8, lb.items, rb.items) },
// 连接计算 -> 将两臂字符串连接
.concat_operator => {
var result = std.ArrayList(u8).init(self.allocator);
try result.appendSlice(lb.items);
try result.appendSlice(rb.items);
return Value{ .string_value = try result.toOwnedSlice() };
},
// 大于计算 -> 将两臂转换为整型后比较
.lt_operator => {
if (try left.asInteger() < try right.asInteger()) {
return Value.TRUE;
} else {
return Value.FALSE;
}
},
// 小于计算 -> 同理大于计算
.gt_operator => {
if (try left.asInteger() > try right.asInteger()) {
return Value.TRUE;
} else {
return Value.FALSE;
}
},
// 加法计算 -> 将两臂转换为整型后相加
.plus_operator => {
return Value{ .integer_value = try left.asInteger() + try right.asInteger() };
},
else => unreachable,
}
},
};
}
创建表AST中包含了column名和column类型的Token，所以我们只需要取出AST中的对应信息，构建一个Table数据结构，然后按照Storage中的逻辑存入KV即可：
fn executeCreateTable(self: Self, create_table: ast.CreateTableAST) !QueryResponse {
const table_name = create_table.getTableName();
if (try self.storage.getTable(table_name)) |t| {
t.deinit();
return ExecuteError.TableAlreadyExists;
}
var columns = std.ArrayList([]const u8).init(self.allocator);
defer columns.deinit();
var types = std.ArrayList([]const u8).init(self.allocator);
defer types.deinit();
for (create_table.columns) |c| {
try columns.append(c.getName()); // 取出字段名
try types.append(c.getKind()); // 取出字段类型
}
const table = Table.init(
self.allocator,
table_name,
columns.items,
types.items,
);
try self.storage.writeTable(table); // 写入KV
return QueryResponse{
.fields = undefined,
.rows = undefined,
.allocator = self.allocator,
};
}
插入AST的结构中，各个Value都是表达式，所以我们在执行AST的过程中，需要先执行各个Value的表达式，例如：
INSERT INTO dewuer VALUES (2020+1, 34-2, 'Lisi' || 'Dalao')
这个SQL中Value都是需要递归处理，所以在实现中，Value部分的逻辑需要执行表达式AST的计算。
fn executeInsert(self: Self, insert: ast.InsertAST) !QueryResponse {
const table_name = insert.getTableName();
if (try self.storage.getTable(table_name)) |t| {
defer t.deinit();
var empty_row = Row.init(self.allocator, t);
defer empty_row.deinit();
var row = Row.init(self.allocator, t);
defer row.deinit();
for (insert.values) |v| {
try row.append(try self.executeExpression(v, empty_row));
}
// write row
try self.storage.writeRow(table_name, row);
return QueryResponse{
.fields = undefined,
.rows = undefined,
.allocator = self.allocator,
};
}
return ExecuteError.TableNotFound;
}
注意到我们在执行表达式AST时用了一个空Row传入，只用其中Table的信息，我们这个小项目不支持字面量的取值再计算的复杂SQL，所以在Insert AST的执行时，不会遇到column的取值逻辑。
目前最复杂的就是Select的查询实现了，Select AST执行的复杂性来自以下几个方面：
- Select的columns和Where条件都可能是计算表达式；
- 当执行Select * 时需要将*转换为所有columns；
- Where条件需要判断；
我们的执行逻辑如下：
由于我们的KV层只能实现全表取出，所以Where条件的匹配只能在内存中进行。
具体实现如下：
fn executeSelect(self: Self, select: ast.SelectAST) !QueryResponse {
const table_name = select.getTableName();
// select x, y
var select_fields = std.ArrayList([]const u8).init(self.allocator);
for (select.columns) |column| {
var field_name: []const u8 = undefined;
switch (column) {
.literal => |l| {
if (l.getKind() == .identifier) {
field_name = l.string();
} else {
unreachable;
}
},
else => unreachable,
}
try select_fields.append(field_name);
}
// 判断是否为Select *
var select_all = false;
if (select_fields.items.len == 1 and std.mem.eql(u8, select_fields.items[0], "*")) {
select_all = true;
select_fields.clearRetainingCapacity();
if (try self.storage.getTable(table_name)) |table| {
defer table.deinit();
for (table.getColumns()) |c| {
try select_fields.append(try self.allocator.dupe(u8, c));
}
} else {
return ExecuteError.TableNotFound;
}
}
var rows = std.ArrayList([][]const u8).init(self.allocator);
if (try self.storage.getTable(table_name)) |table| {
defer table.deinit();
var iter = try self.storage.getRowIter(table);
defer iter.deinit();
while (try iter.next()) |row| {
defer row.deinit();
// 判断这条Row是否满足Where条件
var whereable = false;
if (select.where) |where| {
const wv = try self.executeExpression(where, row);
defer wv.deinit(self.allocator);
if (wv.asBool()) {
whereable = true;
}
} else {
// no where clause, add all
whereable = true;
}
if (whereable) {
var select_res = std.ArrayList([]const u8).init(self.allocator);
if (select_all) {
for (table.getColumns()) |c| {
var val: Value = undefined;
if (row.get(c, &val)) {
var b = std.ArrayList(u8).init(self.allocator);
try val.asString(&b);
try select_res.append(try b.toOwnedSlice());
} else {
unreachable;
}
}
} else {
for (select.columns) |column| {
const val = try self.executeExpression(column, row);
defer val.deinit(self.allocator);
var b = std.ArrayList(u8).init(self.allocator);
try val.asString(&b);
try select_res.append(try b.toOwnedSlice());
}
}
try rows.append(try select_res.toOwnedSlice());
}
}
return QueryResponse{
.fields = try select_fields.toOwnedSlice(),
.rows = try rows.toOwnedSlice(),
.allocator = self.allocator,
};
}
// table not exists
return ExecuteError.TableNotFound;
}
All In One
到目前为止，我们已经完成了本项目所有需要的基础组件，现在我们只需要将这些组件拼装起来，加入输入参数处理以及结果的打印就可以完成这个小型的SQL数据库了。
我们又回到了最开始我们介绍的项目结构，不过这里我们需要加上输入输出的部分：
由于是命令行类的工具，内存管理可以更为奔放一些，Zig非常贴心的提供了Arena内存管理器（Go程序员应该很熟悉），非常适合命令行这类的用完即走的工具，我们可以一次性的申请内存，用完后一次性丢弃。
Zig 中的Arena Allocator是一种特殊的内存管理策略，它与传统分配器不同，通过将释放操作推迟到程序执行结束时进行。这种方法可以在内存一次性分配和释放的场景中提高性能，而不是在整个程序生命周期中逐步释放。
我们最后的main函数实现如下：
pub fn main() !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();
const stdout = std.io.getStdOut().writer();
var args = try std.process.argsWithAllocator(allocator);
defer args.deinit();
var database_path: []const u8 = undefined;
var script: []const u8 = undefined;
while (args.next()) |arg| {
if (std.mem.eql(u8, arg, "--database")) {
database_path = args.next().?; // database
} else if (std.mem.eql(u8, arg, "--script")) {
script = args.next().?; // script
}
}
if (database_path.len == 0) {
std.log.err("No database specified", .{});
return ZigRocksError.InvalidArgument;
}
if (script.len == 0) {
std.log.err("No script specified", .{});
return ZigRocksError.InvalidArgument;
}
// read script
const script_file = try std.fs.cwd().openFile(script, .{});
defer script_file.close();
const file_size = try script_file.getEndPos();
const script_buffer = try allocator.alloc(u8, file_size);
defer allocator.free(script_buffer);
_ = try script_file.readAll(script_buffer);
// lex SQL script
const tokens = try Lexer.init(script_buffer).lex(allocator);
defer allocator.free(tokens);
if (tokens.len == 0) {
std.log.err("No tokens found", .{});
return ZigRocksError.InvalidArgument;
}
// parse SQL script
const ast = try Parser.init(allocator).parse(tokens);
// init rocksdb
const db = try Rocksdb.init(allocator, database_path);
defer db.deinit();
// execute AST
const executer = Executer.init(allocator, db);
var resp = try executer.execute(ast);
defer resp.deinit();
// for `create table` and `insert` SQL, we print OK
if (resp.rows.len == 0) {
try stdout.print("OK\n", .{});
return;
}
// for select SQL
// print fields
try stdout.print("| ", .{});
for (resp.fields) |field| {
try stdout.print("{s}\t\t ", .{field});
}
try stdout.print("\n+", .{});
// print ----
for (resp.fields) |field| {
var fl = field.len;
while (fl > 0) : (fl -= 1) {
try stdout.print("-", .{});
}
try stdout.print("\t\t ", .{});
}
try stdout.print("\n", .{});
// print rows
for (resp.rows) |row| {
try stdout.print("| ", .{});
for (row) |value| {
try stdout.print("{s}\t\t ", .{value});
}
try stdout.print("\n", .{});
}
}
六、总结
这篇文章中，我利用RocksDB引擎和Zig语言对C家族的集成能力，成功实现了一个简单的SQL数据库。
这个项目中，我们从词法分析器开始，逐步介绍了SQL语句的分析方法、AST的构建以及如何将关系型表数据转换为KV类型的数据。
通过这个玩具项目的经历，我们不仅学习感受了SQL这个计算机行业底座的实现方法，也了解了当下很流行的KV引擎到关系型表的桥接思想，同时锻炼了自身模块组织和编码的能力。
当然这个小项目的功能还是非常简陋的，有兴趣的同学可以按照以下方向继续迭代：
- 改进Table到KV的映射模型，让其具备KV层的二级索引检索能力；
- 扩充SQL支持的语法，例如UPDATE语句和DELET语句；
- 支持多租户能力和事务的能力；
- 添加一个Server，将SQL Cli工具转换为SQL Server。
文 / 古月方源
关注得物技术，每周更新技术干货
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
未经得物技术许可严禁转载，否则依法追究法律责任。
登录