原创 古月方源 2024-12-18 18:30 上海
数据库DBMS是当前互联网开发者最熟悉的基础设施之一，很多后端开发者的入门项目就是一个简单的基于MySQL的数据管理系统。笔者一直想自己编写一个简单的SQL数据库，借助学习RocksDB和Zig语言的内容，利用这个机会作为学习成果的检验。
目录
一、前言
二、什么是RocksDB
三、什么是Zig语言
四、项目结构
五、实现解析
1. RocksDB Layer
2. Lexer
3. AST
4. Parser
5. Table to KV
6. Storage
7. Executer
8. All In One
六、总结
一
前言
数据库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 = ;const rdb = );pub const Iter = .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);}
第三步，我们需要在build.zig中添加RocksDB三方库的link，关于Zigcc的具体细节可以参考这篇文章（https://ziglang.org/learn/build-system/）。
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, // selectcreate_table_keyword, // create tableinsert_keyword, // insert intovalues_keyword, // valuesfrom_keyword, // fromwhere_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 ;}};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 },};
第二步，我们定义一下Token的数据结构：
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;}}// 由于我们关键字是按长度倒排序的，所以匹配到的一定是最长的keywordif (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语法
以一个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条件 ?表示可以为nullallocator: 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语法
以一个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和intpub 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 Into语法
以一个Insert的SQL语句为例子：INSERT INTO dewuer VALUES (2010, 35, 'Zhangsan')
这个语法最为简单，只有2个基本元素：
数据表Table；
插入赋值数组；
由此，我们可以给出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语法分析
分析Select语法也很简单，可以按照如下流程分析：
这个过程中，分析column表达式的过程需要注意，当有多个选择字段时，需要判断字段中间的逗号分隔符。
实现代码如下：
fn parseSelect(self: Self,tokens: []Token,) !ast.SelectAST {var i: usize = 0;// expect select keywordif (!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);// 分析columnswhile (!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 nameif (!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;}
Create Table语法分析
建表的语法可以按照如下流程分析：
注意此处建表的columns相较于Select语法的columns有点不同，建表的columns不仅有字段名的标识符，还有类型标识，其余的逻辑与Select语法的columns分析方法一致：
fn parseCreateTable(self: Self, tokens: []Token) !ast.CreateTableAST {var i: usize = 0;// create tableif (!isExpectTokenKind(tokens, i, Token.Kind.create_table_keyword)) {return ParserError.ExpectCreateKeyword;}i += 1;// table nameif (!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语法分析
Insert语法相较于建表语法更为简单一些，可以按照如下流程分析：
实现代码如下：
fn parseInsert(self: Self, tokens: []Token) !ast.InsertAST {var i: usize = 0;// insert intoif (!isExpectTokenKind(tokens, i, Token.Kind.insert_keyword)) {return ParserError.ExpectInsertKeyword;}i += 1;// table nameif (!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/）的文档和博客，例如：
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);}};
row
一个数据行由每个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();}};
rowIter
当我们做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: *[]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..], .big);}// [length: 4bytes][bytes]pub fn serializeBytes(allocator: std.mem.Allocator, bytes: []const u8) ![]const u8 {var h: [4]u8 = undefined;serializeInteger(u32, , &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 nameconst 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 existsif (!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 datavar 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 infovar 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 columnsvar 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
表达式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,}},};}
CreateTable AST
创建表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); // 写入KVreturn QueryResponse{.fields = undefined,.rows = undefined,.allocator = self.allocator,};}
Insert AST
插入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 rowtry 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 AST
目前最复杂的就是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, yvar 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 allwhereable = 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 existsreturn 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 scriptconst 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 scriptconst 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 scriptconst ast = try Parser.init(allocator).parse(tokens);// init rocksdbconst db = try Rocksdb.init(allocator, database_path);defer db.deinit();// execute ASTconst executer = Executer.init(allocator, db);var resp = try executer.execute(ast);defer resp.deinit();// for `create table` and `insert` SQL, we print OKif (resp.rows.len == 0) {try stdout.print("OK\n", .{});return;}// for select SQL// print fieldstry 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 rowsfor (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。
活动推荐
活动一：即日起至12月22日18:00，任意转发得物技术文章至朋友圈，可在得物技术后台回复「得物」参与抽奖。（得物x王者荣耀联名亚克力鞋盒、得物限定马克杯、极光蓝笔记本等你来抽）
活动二：12月21日 Pulsar Developer Day 火热报名中，详情：议程介绍 | 国内 Pulsar 顶级头部大厂齐聚 Pulsar 开发者 2024 大会，报名倒计时！
往期回顾
3.二十万分之一几率：if语句变do-while卡死问题分析｜得物技术
文 / 古月方源
关注得物技术，每周一、三更新技术干货
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
未经得物技术许可严禁转载，否则依法追究法律责任。
“
扫码添加小助手微信
如有任何疑问，或想要了解更多技术资讯，请添加小助手微信：
