第10章:考古学启发的函数式数据库
作者:Yoav Rubin
Yoav Rubin 是微软的高级软件工程师,之前曾在 IBM Research 担任研究人员和发明大师。
简介
软件开发通常被视为一个严格的过程,但开发者本身是有自己视角和偏见的人,这会影响到他们工作的结果。在本章中,我们将探讨视角的改变如何影响数据库的设计和实现。
数据库系统被设计用来存储和查询数据。然而,这些系统本身是由计算机科学家设计的,因此现代数据库系统深受计算机科学家对数据定义和数据操作的影响。
例如,大多数现代数据库通过就地覆盖旧数据来实现更新,而不是追加新数据并保留旧数据。这种被 Rich Hickey 称为"面向位置编程"的机制节省了存储空间,但使得检索特定记录的完整历史变得不可能。这个设计决策反映了计算机科学家的观点:认为"历史"不如其存储成本重要。
如果你问一位考古学家旧数据在哪里,答案会是"希望它就埋在下面"。
像考古学家一样设计数据库
如果我们让考古学家设计数据库,需求可能会反映在挖掘现场发现的内容:
- 墙壁可能在一层有罗马符号,在较低层有希腊符号
- 这两个观察都被记录为墙的状态的一部分
这个类比可以可视化为挖掘现场的图示。
如果我们将考古学家的语言翻译成数据库设计师使用的术语:
- 数据是不可变的:一旦写入,数据永远不会被更改
- 查询返回特定时间点的数据
- 可以查询任何时间点的数据
这种设计有时被称为"函数式数据库",因为它使用了函数式编程领域的思想。
奠定基础
让我们从声明构成数据库的核心结构开始。
(defrecord Database [layers top-id curr-time])数据库由以下部分组成:
- layers: 数据库的不同版本层
- top-id: 分配给实体的最高ID
- curr-time: 当前时间戳
(defrecord Layer [storage VAET AVET VEAT EAVT])每一层由以下部分组成:
- storage: 实际数据存储
- VAET, AVET, VEAT, EAVT: 四种不同的索引
在我们的设计中,一个概念上的"数据库"可能由许多 Database 实例组成,每个实例代表数据库在 curr-time 的快照。
实体(Entities)
我们的数据库如果没有要存储的实体就没有用处,所以接下来定义实体。如前所述,实体有一个ID和一个属性列表;我们使用 make-entity 函数创建它们。
(defrecord Entity [id attrs])
(defn make-entity
([] (make-entity :db/no-id-yet))
([id] (Entity. id {})))注意,如果没有给定ID,实体的ID被设置为 :db/no-id-yet,这意味着其他东西负责给它一个ID。
属性(Attributes)
每个属性由其名称、值和最近更新的时间戳以及之前的时间戳组成。每个属性还有两个字段,描述其 type 和 cardinality。
索引数据
现在我们已经定义了数据库的基本元素,可以开始考虑如何查询它。任何查询都必然对实体的ID以及某些属性的名称和值感兴趣。这个三元组 (entity-id, attribute-name, attribute-value) 对我们的查询过程非常重要,我们给它一个明确的名称:datom。
Datom 很重要,因为它们代表事实,而我们的数据库积累事实。
在我们的数据库中有四个索引:EAVT、AVET、VEAT 和 VAET。索引以地图的地图实现,根地图的键充当第一级,每个这样的键指向一个地图,其键充当索引的第二级,值是索引的第三级。
数据行为和生命周期
到目前为止,我们的讨论集中在数据的结构上:核心组件是什么以及它们如何聚合在一起。现在该探索系统的动态性了:数据如何通过添加-更新-删除的数据生命周期随时间变化。
在考古学家的世界中,数据实际上从不改变。一旦创建,它永远存在,只能被更新层中的数据隐藏。"隐藏"这个词在这里很关键。旧数据不会"消失"——它被埋藏,可以通过暴露更旧的层再次显现。
基本必需品
数据生命周期由三个基本操作组成:
- add-entity: 添加实体
- remove-entity: 删除实体
- update-entity: 更新实体
记住,即使这些函数提供了可变性的错觉,我们实际上在每种情况下所做的只是向数据添加另一层。
查询数据库
第二个库提供查询功能,这是本节的主要关注点。数据库如果没有强大的查询机制对用户来说就不是很有用。这个特性通常通过查询语言暴露给用户,用于声明性地指定感兴趣的数据集。
我们的数据模型基于随时间积累事实(即datoms)。对于这个模型,查找正确查询语言的自然位置是逻辑编程。一个受逻辑编程影响的常用查询语言是 Datalog,除了非常适合我们的数据模型外,它还有一个非常优雅的适应 Clojure 语法的方式。
查询语言
让我们看一个查询示例:
{ :find [?nm ?bd ]
:where [
[?e :likes "pizza"]
[?e :name ?nm]
[?e :speak "English"]
[?e :bday (bday-mo? ?bd)]]}这个查询询问:"喜欢披萨、说英语且本月生日的实体的名字和生日是什么?"
查询引擎涉及四个步骤:
- 转换: 将查询转换为易于处理的表示
- 制定计划: 检查查询以构建生成结果的计划
- 执行计划: 实际执行查询
- 统一和报告: 提取用户请求的值
总结
我们的旅程始于对不同类型数据库的构想,最终得到了一个:
- 支持ACI事务(当我们决定将数据存储在内存中时,持久性丢失了)
- 支持"假如"交互
- 回答与时间相关的问题
- 处理使用索引优化的简单datalog查询
- 为图查询提供API
- 引入并实现进化查询的概念
最终产品可以做很多事情,用488行Clojure源代码实现,其中73行是空行,55行是文档字符串。
最后,还缺少一样东西:名字。对于一个内存中、索引优化、支持查询、对库开发者友好、时间感知的函数式数据库,用360行Clojure代码实现,唯一合理的选择是 CircleDB。