一、前言
数据库 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 语言的三方库非常容易：
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 语句，我们可以将 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);}
复制代码
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 家（https://www.cockroachlabs.com/）的文档和博客，例如：
我们这里也提纲挈领的介绍一下表数据到 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/1table_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/1row_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。
文 / 古月方源
关注得物技术，每周更新技术干货
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
未经得物技术许可严禁转载，否则依法追究法律责任。
评论