在 Go 中构建内存数据库

Posted on by

在软件工程师职位的设计面试中，您可能会遇到的问题之一是设计内存数据库。这个问题有很多变化，但通常是这样的：

Implement an in-memory database using object-oriented design. Examples of the interaction with the database are shown in SQL as a reference, but there is no need to parse SQL. You are free to implement your own API to work with it.

It must support the creation of tables, where columns type can be int or varchar: 
CREATE TABLE cities (id int, name varchar, population int);

The API must allow inserting rows into created table:
INSERT INTO cities (id, name, population) VALUES ("Tokyo", 37);
INSERT INTO cities (id, name, population) VALUES ("Delhi", 28);
INSERT INTO cities (id, name, population) VALUES ("Shanghai", 28);

API must support select operation with the ability to select all columns implicitly (*) or explicitly specified columns. You must also be able to filter rows based on multiple column values combined with AND, where the column is equal (=) or not equal (!=) to a value.
SELECT * FROM cities;
SELECT population FROM cities WHERE name = "Tokyo";
SELECT * FROM cities WHERE name != "Delhi" AND population = 28;

It must also support update and delete operations, with filtering capabilities mentioned above:
UPDATE cities SET population = 25 WHERE name = "Shanghai";
DELETE FROM cities WHERE population != 37;

如果您不熟悉此类问题，您可能想知道这是什么类型的问题。很明显，实现一个具有生产价值的内存数据库需要付出很多努力。您需要控制内存的分配和释放方式、解决线程安全问题、实施大量输入验证、使用测试覆盖许多边缘案例、收集指标以更好地了解数据库的执行情况、运行严格的压力测试等。获得所有相关问题的答案可能比一般面试花费的时间要长得多。那么，为什么还要问这个问题呢？

事实证明，这类问题是了解受访者编码方法的好方法。正是“一张图抵千言”的情况。这里的图片基本上是一个开放式问题，在面试过程中提供了广泛的选择来探索。例如，在面试中问一个人“你会写测试吗？”是没有用的。或“您是否验证输入数据？” – 谁会说“不”？对于带回家的编码测试或“向我们发送您的代码示例”也是正确的。通常，您将获得的内容与人们在工作环境中编写代码的方式不同。而这类问题可以非常贴切地复制工作环境：你有时间压力，你可以做的选择太多；

让我们尝试在 Go 中实现这个问题的解决方案并探索一些可能性。在解决这类问题时，我更喜欢通过一系列步骤来解决。

第0步是提问

提出问题以澄清期望并减少工作量。例如，从一开始就明确你是否需要处理错误以及面试官对数据验证的期望。有时只需将 TODO 放在正确的位置即可，节省大量时间。以下是一些我想到的：

  • 你需要担心线程安全吗？
  • 例如，您可以通过放置 TODO 来省略返回错误和数据验证吗？
  • Select 必须返回一些东西 – 对象数组是否可以，或者您是否需要打印记录？
  • 你需要控制内存吗？

显然，当您开始使用代码时，您会想到更多。

第一步是创建一个数据库和一个表

如果您仔细查看所讨论的 SQL 查询，您会注意到它们可以分为两种类型的 SQL：DDL和DML。第一个定义表，并与数据操作查询无关。在对数据进行任何查询之前，我们需要一个数据库和一个表。让我们实现它。

我更喜欢在执行实现时先编写测试。当您听到：“好的，看起来不错。让我们试试它是否有效！” 在采访的最后几分钟。这不是一个合适的 TDD 方法——只是一个简单的测试，它随着实现的每一步而增长，并将一些查询从任务定义复制到数据库。

import (
	"testing"
	"github.com/google/go-cmp/cmp"
)

type Database struct {
	tables map[string]Table
}

func NewDatabase() *Database {
	return &Database{
		tables: make(map[string]Table),
	}
}

func (d *Database) CreateTable(name string, cols []Column) *Table {
	// TODO: Validation
	t := NewTable(name, cols)
	d.tables[t.Name] = t
	return &t
}

const (
	ColumnInt = 1 << iota
	ColumnVarchar
)

type Column struct {
	Name string
	Type int
}

type Table struct {
	Name    string
	columns []Column
	rows    [][]any
}

func NewTable(name string, cols []Column) Table {
	t := Table{
		Name:    name,
		columns: cols,
	}
	return t
}

func TestDatabase(t *testing.T) {
	db := NewDatabase()

	// CREATE TABLE cities (id int, name varchar, population int);
	tab := db.CreateTable("cities", []Column{
		{"id", ColumnInt},
		{"name", ColumnVarchar},
		{"population", ColumnInt},
	})

	if diff := cmp.Diff(len(db.tables), 1); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}
}

现在我们有了 Database 和 Table 对象。该表使用数组作为行存储。现在它可以处理修改数据的查询了。

第 2 步 – 插入、选择、更新和删除

再仔细看一下，很明显 INSERT 可以很容易地实现，我们在其他查询之前需要它。

//...
func (t *Table) Insert(data ...any) {
	// TODO: Validate data
	t.rows = append(t.rows, data)
}

func TestDatabase(t *testing.T) {
	//...
	// INSERT INTO cities (id, name, population) VALUES ("Tokyo", 37);
	// INSERT INTO cities (id, name, population) VALUES ("Delhi", 28);
	// INSERT INTO cities (id, name, population) VALUES ("Shanghai", 28);
	tab.Insert(1, "Tokyo", 37)
	tab.Insert(2, "Delhi", 28)
	tab.Insert(3, "Shanghai", 28)
}

SELECT、UPDATE 和 DELETE 都有带有过滤条件的 WHERE 部分。让我们将其定义为 Condition 结构。SELECT 还需要返回数组列——我们称这个结构为 Expression。UPDATE 需要定义哪些字段被更新——它将是 Set 结构。现在所有这些额外的结构都可以用一个包含所有字段的 Column 结构来替换，但它会使 API 调用对我的口味来说过于冗长（需要明确命名结构字段：）[]Set{{"population", 25}} → []Column{{name: "population", value: 25}}。

type Table struct {
	//...
	colIdx map[string]int
}

func NewTable(name string, cols []Column) Table {
	// ...
	t.colIdx = make(map[string]int, len(cols))
	for i, v := range cols {
		t.colIdx[v.Name] = i
	}
	return t
}

// ...
type Condition struct {
	Column string
	Eq     string
	Value  any
}

type Expression struct {
	Column string
}

func (t *Table) Select(cols []Expression, cond []Condition) [][]any {
	// TODO: cols and cond validation
	res := [][]any{}
	for i := 0; i < len(t.rows); i++ {
		if t.rowMatch(cond, i) {
			res = append(res, t.filterColumns(cols, i))
		}
	}
	return res
}

type Set struct {
	Column string
	Value  any
}

func (t *Table) Update(set []Set, cond []Condition) {
	for i := 0; i < len(t.rows); i++ {
		if t.rowMatch(cond, i) {
			for _, s := range set {
				t.rows[i][t.getColumnIndex(s.Column)] = s.Value
			}
		}
	}
}

func (t *Table) Delete(cond []Condition) {
	for i := 0; i < len(t.rows); i++ {
		if t.rowMatch(cond, i) {
			t.rows[i] = nil
		}
	}
}

func (t *Table) getColumnIndex(name string) int {
	return t.colIdx[name]
}

// ... 
func TestDatabase(t *testing.T) {
	// ...
	var got, want [][]any

	// SELECT * FROM cities;
	got = tab.Select([]Expression{{"*"}}, nil)
	want = [][]any{{1, "Tokyo", 37}, {2, "Delhi", 28}, {3, "Shanghai", 28}}
	if diff := cmp.Diff(want, got); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}

	// SELECT population FROM cities WHERE name = "Tokyo";
	got = tab.Select(
		[]Expression{{"population"}},
		[]Condition{{"name", ConditionEq, "Tokyo"}},
	)
	want = [][]any{{37}}
	if diff := cmp.Diff(want, got); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}

	// SELECT * FROM cities WHERE name != "Delhi" AND population = 28;
	got = tab.Select(
		[]Expression{{"*"}},
		[]Condition{{"name", ConditionNe, "Delhi"}, {"population", ConditionEq, 28}},
	)
	want = [][]any{{3, "Shanghai", 28}}
	if diff := cmp.Diff(want, got); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}

	// UPDATE cities SET population = 25 WHERE name = "Shanghai";
	tab.Update(
		[]Set{{"population", 25}},
		[]Condition{{"name", ConditionEq, "Shanghai"}},
	)

	got = tab.Select([]Expression{{"*"}}, nil)
	want = [][]any{{1, "Tokyo", 37}, {2, "Delhi", 28}, {3, "Shanghai", 25}}
	if diff := cmp.Diff(want, got); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}

	// DELETE FROM cities WHERE population != 37;
	tab.Delete([]Condition{{"population", ConditionNe, 37}})

	got = tab.Select([]Expression{{"*"}}, nil)
	want = [][]any{{1, "Tokyo", 37}}
	if diff := cmp.Diff(want, got); diff != "" {
		t.Errorf("Select: (-want +got)\n%s", diff)
	}
}

测试看起来已经完成了。rowMatch除和filterColumns函数外，所有代码均已实现。对于更新，我需要通过名称getColumnIndex以及相关代码来了解更新的列索引。删除很棘手 – 我不想删除行，因为它会破坏索引并需要从数组的尾部进行迭代。

第三步过滤

在这里，我添加了行匹配、条件评估和列过滤。如果需要，可以使用新类型的条件扩展代码。

// ...
const (
	ConditionEq = "="
	ConditionNe = "!="
)

func (c Condition) Eval(val any) bool {
	if c.Eq == ConditionEq {
		return c.Value == val
	} else if c.Eq == ConditionNe {
		return c.Value != val
	}
	return false
}

// ...
func (t *Table) rowMatch(cond []Condition, i int) bool {
	// Skip deleted row
	if t.rows[i] == nil {
		return false
	}

	if cond == nil {
		return true
	}

	for _, c := range cond {
		j := t.getColumnIndex(c.Column)
		if !c.Eval(t.rows[i][j]) {
			return false
		}
	}
	return true
}

func (t *Table) filterColumns(cols []Expression, i int) []any {
	row := t.rows[i]

	if cols[0].Column == "*" {
		return append([]any(nil), row...)
	}

	res := make([]any, len(cols))
	for i, c := range cols {
		res[i] = row[t.getColumnIndex(c.Column)]
	}
	return res
}

现在它应该可以工作了。如您所见，使用正确的方法，这个问题并不难。

以下是我的一些观察和结论：

  • 这不是炫耀您的 OOP 技能的练习。OOP 只是一个工具；明智地使用它。
  • 问问题。这是一个开放式问题，通过提出正确的问题可以打开许多路径。
  • 与面试官谈谈你的想法。那个人在那里可以更好地了解您的思维方式、编码方法以及您的知识渊博。
  • 如果您被卡住，请不要冻结 – 谈论它。最终被卡住是工作的一部分。寻求帮助的能力对于有效的团队合作很重要。
  • 准备很重要。面试太短了，无法在运行中弄清楚事情。做好准备将帮助您涵盖问题的更多方面。

祝你好运！

building-an-in-memory-database-in-go

推荐阅读：