Appearance
考古学启发的数据库
Yoav Rubin 是微软的高级软件工程师，此前曾在 IBM Research 担任研究员和杰出发明人。他目前从事云端数据安全领域的工作，过去则专注于开发基于云和 Web 的开发环境。Yoav 拥有神经科学领域的医学研究硕士学位和信息系统工程学士学位。他的 Twitter 账号是 @yoavrubin，偶尔在 http://yoavrubin.blogspot.com 发表博客。
简介
软件开发通常被视为一个严谨的过程，输入是需求，输出是可用的产品。然而，软件开发者也是人，有着自己的视角和偏见，这些都会影响他们工作的成果。
在本章中，我们将探讨改变一个常见视角如何影响一种被广泛研究的软件类型——数据库——的设计和实现。
数据库系统的设计目的是存储和查询数据。这是所有信息工作者都在做的事情；然而，这些系统本身是由计算机科学家设计的。因此，现代数据库系统深受计算机科学家对数据定义以及数据可操作方式的影响。
例如，大多数现代数据库通过就地覆盖旧数据来实现更新，而不是追加新数据并保留旧数据。这种机制被 Rich Hickey 戏称为"面向位置编程 (place-oriented programming)"，它节省了存储空间，但使得检索某条记录的完整历史变得不可能。这一设计决策反映了计算机科学家的观点："历史"不如存储它的成本重要。
如果你转而问一位考古学家旧数据在哪里可以找到，答案会是"希望它就埋在下面"。
(免责声明：我对典型考古学家观点的理解基于参观过几个博物馆、阅读过几篇维基百科文章，以及看完了整个《印第安纳·琼斯》系列。)
像考古学家一样设计数据库
如果我们请这位友善的考古学家设计一个数据库，我们可以预期这些需求会反映出在考古发掘现场会发现的东西：
- 所有数据都在现场被发现和编目。
- 向更深处挖掘将揭示过去事物的状态。
- 在同一层发现的文物来自同一时期。
- 每件文物都由它在不同时期积累的状态组成。
例如，一面墙在某一层上可能有罗马符号，而在更低的一层可能有希腊符号。这两项观察结果都被记录为墙壁状态的一部分。
这个类比在图 10.1 中进行了可视化表示：
- 整个圆圈是考古发掘现场。
- 每个环是一个层 (layer)（这里编号从 0 到 4）。
- 每个扇形是一个带标签的文物（'A' 到 'E'）。
- 每个文物有一个 'symbol' 属性（空白表示没有更新）。
- 实线箭头表示层之间 symbol 的变化。
- 虚线箭头是文物之间的任意关联关系（例如从 'E' 到 'A'）。
图 10.1 - 考古发掘现场
如果我们把考古学家的语言翻译成数据库设计者使用的术语：
- 考古发掘现场就是一个数据库 (database)。
- 每件文物是一个实体 (entity)，拥有对应的 ID。
- 每个实体有一组属性 (attribute)，这些属性可能随时间变化。
- 每个属性在特定时间有一个特定的值 (value)。
这可能看起来与你习惯使用的数据库非常不同。这种设计有时被称为"函数式数据库 (functional database)"，因为它使用了函数式编程领域的思想。本章的其余部分将描述如何实现这样一个数据库。
由于我们要构建一个函数式数据库，我们将使用一种名为 Clojure 的函数式编程语言。
Clojure 有几个特性使其成为函数式数据库的优秀实现语言，比如开箱即用的不可变性 (immutability)、高阶函数 (higher order functions) 和元编程 (metaprogramming) 能力。但最终，选择 Clojure 的原因是它对简洁、严谨设计的强调，这是很少有编程语言具备的品质。
奠定基础
让我们从声明构成数据库的核心结构开始。
clojure
(defrecord Database [layers top-id curr-time])一个数据库由以下部分组成：
- 多层实体，每层都有自己唯一的时间戳（图 10.1 中的各个环）。
- 一个 top-id 值，即下一个可用的唯一 ID。
- 数据库最后一次更新的时间。
clojure
(defrecord Layer [storage VAET AVET VEAT EAVT])每一层由以下部分组成：
- 一个实体数据存储。
- 用于加速数据库查询的索引。（这些索引及其名称的含义将在后面解释。）
在我们的设计中，一个概念上的"数据库"可能由多个 Database 实例组成，每个实例代表数据库在 curr-time 时刻的快照。如果实体的状态在两个时间点之间没有发生变化，一个 Layer 可以与另一个 Layer 共享完全相同的实体。
实体
如果没有实体可以存储，我们的数据库就毫无用处，所以接下来定义实体。如前所述，一个实体有一个 ID 和一个属性列表；我们使用 make-entity 函数来创建它们。
clojure
(defrecord Entity [id attrs])
(defn make-entity
([] (make-entity :db/no-id-yet))
([id] (Entity. id {})))注意，如果没有给定 ID，实体的 ID 将被设置为 :db/no-id-yet，这意味着由其他部分负责给它分配一个 ID。我们稍后会看到这是如何工作的。
属性
每个属性由其名称、值、最近一次更新的时间戳以及上一次更新的时间戳组成。每个属性还有两个字段描述其 type（类型）和 cardinality（基数）。
当一个属性用于表示与另一个实体的关系时，其 type 将是 :db/ref，其值将是相关实体的 ID。这个简单的类型系统同时也是一个扩展点。用户可以自由定义自己的类型，并利用它们为数据提供额外的语义。
属性的 cardinality 指定该属性表示的是单个值还是一组值。我们使用这个字段来确定允许对该属性执行的操作集合。
创建属性通过 make-attr 函数完成。
clojure
(defrecord Attr [name value ts prev-ts])
(defn make-attr
([name value type ; these ones are required
& {:keys [cardinality] :or {cardinality :db/single}} ]
{:pre [(contains? #{:db/single :db/multiple} cardinality)]}
(with-meta (Attr. name value -1 -1) {:type type :cardinality cardinality})))这个构造函数中使用了几种有趣的模式：
- 我们使用 Clojure 的契约式设计 (Design by Contract) 模式来验证 cardinality 参数是否为允许的值。
- 我们使用 Clojure 的解构机制 (destructuring) 来提供默认值
:db/single（如果未提供的话）。 - 我们使用 Clojure 的元数据 (metadata) 功能来区分属性的数据（名称、值和时间戳）及其元数据（类型和基数）。在 Clojure 中，元数据处理通过函数
with-meta（设置）和meta（读取）完成。
属性只有作为实体的一部分时才有意义。我们通过 add-attr 函数建立这种连接，它将给定的属性添加到实体的属性映射 (attribute map)（称为 :attrs）中。
注意，我们不直接使用属性的名称，而是先将其转换为关键字 (keyword)，以遵循 Clojure 惯用的映射用法。
clojure
(defn add-attr [ent attr]
(let [attr-id (keyword (:name attr))]
(assoc-in ent [:attrs attr-id] attr)))存储
到目前为止，我们已经讨论了很多关于要存储什么的内容，却没有考虑在哪里存储。在本章中，我们采用最简单的存储机制：将数据存储在内存中。这当然不可靠，但它简化了开发和调试，使我们能够专注于程序中更有趣的部分。
我们将通过一个简单的协议 (protocol) 来访问存储，这使得定义额外的存储提供者成为可能，供数据库拥有者选择。
clojure
(defprotocol Storage
(get-entity [storage e-id] )
(write-entity [storage entity])
(drop-entity [storage entity]))这是我们基于内存的协议实现，它使用一个映射作为存储：
clojure
(defrecord InMemory [] Storage
(get-entity [storage e-id] (e-id storage))
(write-entity [storage entity] (assoc storage (:id entity) entity))
(drop-entity [storage entity] (dissoc storage (:id entity))))索引数据
现在我们已经定义了数据库的基本元素，可以开始考虑如何查询它了。由于数据的结构方式，任何查询都必然会关注实体的 ID、某些属性的名称和值中的至少一项。(entity-id, attribute-name, attribute-value) 这个三元组对查询过程非常重要，所以我们给它一个明确的名称：datom。
Datom 之所以重要，是因为它们代表事实 (fact)，而我们的数据库在积累事实。
如果你以前使用过数据库系统，你可能已经熟悉索引 (index) 的概念，它是一种辅助数据结构，以消耗额外空间为代价来降低平均查询时间。在我们的数据库中，索引是一个三层结构，按特定顺序存储 datom 的各个组成部分。每个索引的名称来源于它存储 datom 组成部分的顺序。
例如，让我们看一下图 10.2 中所示的索引：
- 第一层存储实体 ID
- 第二层存储相关的属性名称
- 第三层存储相关的值
这个索引被命名为 EAVT，因为顶层映射保存实体 ID (Entity ID)，第二层保存属性名称 (Attribute name)，叶子节点保存值 (Value)。"T" 来源于数据库中每一层都有自己的索引，因此索引本身与特定的时间 (Time) 相关。
图 10.2 - EAVT
图 10.3 展示了一个被称为 AVET 的索引，因为：
- 第一层映射保存属性名称 (Attribute name)。
- 第二层映射保存值 (Value)（属性的值）。
- 第三层集合保存实体 ID (Entity ID)（第一层属性所属实体的 ID）。
图 10.3 - AVET
我们的索引实现为映射的映射 (map of maps)，其中根映射的键作为第一层，每个这样的键指向一个映射，该映射的键作为索引的第二层，值是索引的第三层。第三层的每个元素是一个集合 (set)，保存索引的叶子节点。
每个索引以某种 'EAV' 规范顺序（entity_id、attribute-name、attribute-value）的排列方式存储 datom 的组成部分。然而，当我们在索引之外处理 datom 时，我们期望它们是规范格式。因此，我们为每个索引提供了 from-eav 和 to-eav 函数来在这些顺序之间进行转换。
在大多数数据库系统中，索引是可选组件；例如，在像 PostgreSQL 或 MySQL 这样的关系型数据库管理系统 (RDBMS, Relational Database Management System) 中，你会选择只为表中的某些列添加索引。我们为每个索引提供了一个 usage-pred 函数，用于确定某个属性是否应被包含在该索引中。
clojure
(defn make-index [from-eav to-eav usage-pred]
(with-meta {} {:from-eav from-eav :to-eav to-eav :usage-pred usage-pred}))
(defn from-eav [index] (:from-eav (meta index)))
(defn to-eav [index] (:to-eav (meta index)))
(defn usage-pred [index] (:usage-pred (meta index)))在我们的数据库中有四个索引：EAVT（见图 10.2）、AVET（见图 10.3）、VEAT 和 VAET。我们可以通过 indexes 函数返回的值向量来访问它们。
clojure
(defn indexes[] [:VAET :AVET :VEAT :EAVT])为了演示这一切是如何组合在一起的，将以下五个实体编入索引的结果如表 10.1 所示。
- Julius Caesar（也称为 JC）住在罗马
- Brutus（也称为 B）住在罗马
- Cleopatra（也称为 Cleo）住在埃及
- 罗马的河流是台伯河
- 埃及的河流是尼罗河
| EAVT 索引 | AVET 索引 |
|---|---|
| JC => {lives-in => {Rome}} | lives-in => {Rome => {JC, B}} |
| B => {lives-in => {Rome}} | {Egypt => {Cleo}} |
| Cleo => {lives-in => {Egypt}} | river => {Rome => {Tiber}} |
| Rome => {river => {Tiber}} | {Egypt => {Nile}} |
| Egypt => {river => {Nile}} |
| VEAT 索引 | VAET 索引 |
|---|---|
| Rome => {JC => {lives-in}} | Rome => {lives-in => {JC, B}} |
| {B => {lives-in}} | Egypt => {lives-in => {Cleo}} |
| Egypt => {Cleo => {lives-in}} | Tiber => {river => {Rome}} |
| Tiber => {Rome => {river}} | Nile => {river => {Egypt}} |
| Nile => {Egypt => {river}} |
表 10.1 - 索引
数据库
我们现在拥有了构建数据库所需的所有组件。初始化数据库意味着：
- 创建一个没有数据的初始空层
- 创建一组空索引
- 将
top-id和curr-time设置为 0
clojure
(defn ref? [attr] (= :db/ref (:type (meta attr))))
(defn always[& more] true)
(defn make-db []
(atom
(Database. [(Layer.
(fdb.storage.InMemory.) ; storage
(make-index #(vector %3 %2 %1) #(vector %3 %2 %1) #(ref? %));VAET
(make-index #(vector %2 %3 %1) #(vector %3 %1 %2) always);AVET
(make-index #(vector %3 %1 %2) #(vector %2 %3 %1) always);VEAT
(make-index #(vector %1 %2 %3) #(vector %1 %2 %3) always);EAVT
)] 0 0)))不过有一个问题：Clojure 中所有的集合都是不可变的。由于写操作对数据库至关重要，我们将结构定义为一个 Atom，这是 Clojure 的一种引用类型 (reference type)，提供原子写入的能力。
你可能会好奇为什么我们对 AVET、VEAT 和 EAVT 索引使用 always 函数，而对 VAET 索引使用 ref? 谓词。这是因为这些索引在不同场景下使用，当我们稍后深入探讨查询时就会看到。
基础访问器
在我们构建复杂的查询功能之前，需要提供一个底层 API，系统的不同部分可以使用它从任何时间点检索我们构建的组件及其关联标识符。数据库的使用者也可以使用这个 API；不过，他们更可能使用建立在其之上的更全面的组件。
这个底层 API 由以下四个访问器函数组成：
clojure
(defn entity-at
([db ent-id] (entity-at db (:curr-time db) ent-id))
([db ts ent-id] (get-entity (get-in db [:layers ts :storage]) ent-id)))
(defn attr-at
([db ent-id attr-name] (attr-at db ent-id attr-name (:curr-time db)))
([db ent-id attr-name ts] (get-in (entity-at db ts ent-id) [:attrs attr-name])))
(defn value-of-at
([db ent-id attr-name] (:value (attr-at db ent-id attr-name)))
([db ent-id attr-name ts] (:value (attr-at db ent-id attr-name ts))))
(defn indx-at
([db kind] (indx-at db kind (:curr-time db)))
([db kind ts] (kind ((:layers db) ts))))由于我们将数据库视为和其他值一样，这些函数中的每一个都接受一个数据库作为参数。每个元素通过其关联的标识符检索，并可选择传入感兴趣的时间戳。这个时间戳用于找到我们的查找应该应用到的对应层。
演化
基础访问器的第一个用途是提供"回溯历史"的 API。这是可能的，因为在我们的数据库中，更新操作是通过追加新层来完成的（而非覆盖）。因此我们可以使用 prev-ts 属性查看该层的属性，并继续深入历史，观察属性值随时间的演化过程。
evolution-of 函数正是这样做的。它返回一个由对组成的序列，每对包含属性更新的时间戳和值。
clojure
(defn evolution-of [db ent-id attr-name]
(loop [res [] ts (:curr-time db)]
(if (= -1 ts) (reverse res)
(let [attr (attr-at db ent-id attr-name ts)]
(recur (conj res {(:ts attr) (:value attr)}) (:prev-ts attr))))))数据行为和生命周期
到目前为止，我们的讨论集中在数据的结构上：核心组件是什么以及它们如何聚合在一起。现在是时候探索系统的动态行为了：数据如何通过添加-更新-删除的数据生命周期 (data lifecycle) 随时间变化。
正如我们已经讨论的，在考古学家的世界中，数据实际上永远不会改变。一旦被创建，它就永远存在，只能被更新层中的数据从世界中隐藏。"隐藏"这个术语在这里至关重要。旧数据不会"消失"——它被埋葬了，可以通过暴露更老的层来重新揭示。相反地，更新数据意味着在旧数据上面添加新的一层来遮蔽它。因此我们可以通过在数据上面添加一层"什么都没有"来"删除"数据。
这意味着当我们谈论数据生命周期时，我们实际上是在谈论随时间向数据添加层。
最基本的操作
数据生命周期由三个基本操作组成：
- 使用
add-entity函数添加实体 - 使用
remove-entity函数删除实体 - 使用
update-entity函数更新实体
请记住，即使这些函数提供了可变性的假象，我们在每种情况下实际上做的只是向数据添加另一层。此外，由于我们使用的是 Clojure 的持久化数据结构 (persistent data structures)，从调用者的角度来看，我们为这些操作付出的代价与"就地"变更相同（即性能开销可忽略不计），同时为数据结构的所有其他用户保持不可变性。
添加实体
添加实体需要我们做三件事：
- 准备实体以供添加（通过给它一个 ID 和一个时间戳）
- 将实体放入存储
- 根据需要更新索引
这些步骤在 add-entity 函数中执行。
clojure
(defn add-entity [db ent]
(let [[fixed-ent next-top-id] (fix-new-entity db ent)
layer-with-updated-storage (update-in
(last (:layers db)) [:storage] write-entity fixed-ent)
add-fn (partial add-entity-to-index fixed-ent)
new-layer (reduce add-fn layer-with-updated-storage (indexes))]
(assoc db :layers (conj (:layers db) new-layer) :top-id next-top-id)))准备实体是通过调用 fix-new-entity 函数及其辅助函数 next-id、next-ts 和 update-creation-ts 来完成的。后两个辅助函数负责找到数据库的下一个时间戳（由 next-ts 完成）和更新给定实体的创建时间戳（由 update-creation-ts 完成）。更新实体的创建时间戳意味着遍历实体的属性并更新它们的 :ts 字段。
clojure
(defn- next-ts [db] (inc (:curr-time db)))
(defn- update-creation-ts [ent ts-val]
(reduce #(assoc-in %1 [:attrs %2 :ts ] ts-val) ent (keys (:attrs ent))))
(defn- next-id [db ent]
(let [top-id (:top-id db)
ent-id (:id ent)
increased-id (inc top-id)]
(if (= ent-id :db/no-id-yet)
[(keyword (str increased-id)) increased-id]
[ent-id top-id])))
(defn- fix-new-entity [db ent]
(let [[ent-id next-top-id] (next-id db ent)
new-ts (next-ts db)]
[(update-creation-ts (assoc ent :id ent-id) new-ts) next-top-id]))要将实体添加到存储中，我们定位数据库中最新的层，并用新层更新该层中的存储，结果存储在 layer-with-updated-storage 中。
最后，我们必须更新索引。这意味着，对于每个索引（通过 add-entity 函数中 reduce 和 partial 化的 add-entity-to-index 的组合完成）：
- 找到应该被索引的属性（见
add-entity-to-index中filter与索引的usage-pred对属性进行操作的组合） - 从实体的 ID 构建一个索引路径（见
update-attr-in-index函数中partial化的update-entry-in-index与from-eav的组合） - 将该路径添加到索引中（见
update-entry-in-index函数）
clojure
(defn- add-entity-to-index [ent layer ind-name]
(let [ent-id (:id ent)
index (ind-name layer)
all-attrs (vals (:attrs ent))
relevant-attrs (filter #((usage-pred index) %) all-attrs)
add-in-index-fn (fn [ind attr]
(update-attr-in-index ind ent-id (:name attr)
(:value attr)
:db/add))]
(assoc layer ind-name (reduce add-in-index-fn index relevant-attrs))))
(defn- update-attr-in-index [index ent-id attr-name target-val operation]
(let [colled-target-val (collify target-val)
update-entry-fn (fn [ind vl]
(update-entry-in-index
ind
((from-eav index) ent-id attr-name vl)
operation))]
(reduce update-entry-fn index colled-target-val)))
(defn- update-entry-in-index [index path operation]
(let [update-path (butlast path)
update-value (last path)
to-be-updated-set (get-in index update-path #{})]
(assoc-in index update-path (conj to-be-updated-set update-value))))所有这些组件都作为新层添加到给定的数据库中。剩下的就是更新数据库的时间戳和 top-id 字段。最后一步发生在 add-entity 的最后一行，它同时返回更新后的数据库。
我们还提供了一个 add-entities 便捷函数，通过迭代应用 add-entity 在一次调用中添加多个实体。
clojure
(defn add-entities [db ents-seq] (reduce add-entity db ents-seq))删除实体
从数据库中删除一个实体意味着添加一个不包含该实体的层。为此，我们需要：
- 删除实体本身
- 更新引用该实体的其他实体的属性
- 从索引中清除该实体
这个"不包含地构建"的过程由 remove-entity 函数执行，它看起来与 add-entity 非常相似：
clojure
(defn remove-entity [db ent-id]
(let [ent (entity-at db ent-id)
layer (remove-back-refs db ent-id (last (:layers db)))
no-ref-layer (update-in layer [:VAET] dissoc ent-id)
no-ent-layer (assoc no-ref-layer :storage
(drop-entity
(:storage no-ref-layer) ent))
new-layer (reduce (partial remove-entity-from-index ent)
no-ent-layer (indexes))]
(assoc db :layers (conj (:layers db) new-layer))))引用删除通过 remove-back-refs 函数完成：
clojure
(defn- remove-back-refs [db e-id layer]
(let [reffing-datoms (reffing-to e-id layer)
remove-fn (fn[d [e a]] (update-entity db e a e-id :db/remove))
clean-db (reduce remove-fn db reffing-datoms)]
(last (:layers clean-db))))我们首先使用 reffing-datoms-to 在给定层中找到所有引用我们实体的实体；它返回一个三元组序列，包含引用实体的 ID、属性名称和被删除实体的 ID。
clojure
(defn- reffing-to [e-id layer]
(let [vaet (:VAET layer)]
(for [[attr-name reffing-set] (e-id vaet)
reffing reffing-set]
[reffing attr-name])))然后我们对每个三元组应用 update-entity 来更新引用已删除实体的属性。（我们将在下一节探讨 update-entity 的工作方式。）
remove-back-refs 的最后一步是从索引中清除引用本身，更具体地说是从 VAET 索引中清除，因为它是唯一存储引用信息的索引。
更新实体
本质上，更新是对实体的属性值的修改。修改过程本身取决于属性的基数 (cardinality)：基数为 :db/multiple 的属性持有一组值，所以我们必须允许向该集合添加或删除项目，或完全替换该集合。基数为 :db/single 的属性持有单个值，因此只允许替换。
由于我们还有提供直接在属性和值上进行查找的索引，这些索引也必须被更新。
与 add-entity 和 remove-entity 一样，我们不会真正就地修改实体，而是添加一个包含更新实体的新层。
clojure
(defn update-entity
([db ent-id attr-name new-val]
(update-entity db ent-id attr-name new-val :db/reset-to))
([db ent-id attr-name new-val operation]
(let [update-ts (next-ts db)
layer (last (:layers db))
attr (attr-at db ent-id attr-name)
updated-attr (update-attr attr new-val update-ts operation)
fully-updated-layer (update-layer layer ent-id
attr updated-attr
new-val operation)]
(update-in db [:layers] conj fully-updated-layer))))要更新属性，我们用 attr-at 定位它，然后使用 update-attr 执行实际更新。
clojure
(defn- update-attr [attr new-val new-ts operation]
{:pre [(if (single? attr)
(contains? #{:db/reset-to :db/remove} operation)
(contains? #{:db/reset-to :db/add :db/remove} operation))]}
(-> attr
(update-attr-modification-time new-ts)
(update-attr-value new-val operation)))我们使用两个辅助函数来执行更新。update-attr-modification-time 更新时间戳以反映图 10.1 中黑色箭头的创建：
clojure
(defn- update-attr-modification-time
[attr new-ts]
(assoc attr :ts new-ts :prev-ts (:ts attr)))update-attr-value 实际更新值：
clojure
(defn- update-attr-value [attr value operation]
(cond
(single? attr) (assoc attr :value #{value})
; now we're talking about an attribute of multiple values
(= :db/reset-to operation)
(assoc attr :value value)
(= :db/add operation)
(assoc attr :value (CS/union (:value attr) value))
(= :db/remove operation)
(assoc attr :value (CS/difference (:value attr) value))))剩下的就是从索引中删除旧值并将新值添加到索引中，然后用所有更新后的组件构建新层。幸运的是，我们可以利用之前为添加和删除实体编写的代码来完成此操作。
事务
我们底层 API 中的每个操作都作用于单个实体。然而，几乎所有数据库都有一种方式让用户将多个操作作为单个事务 (transaction) 执行。这意味着：
- 这批操作被视为一个单一的原子操作，因此所有操作要么一起成功，要么一起失败。
- 数据库在事务前后都处于有效状态。
- 这批更新看起来是隔离的 (isolated)；其他查询不应该看到只应用了部分操作的数据库状态。
我们可以通过一个接口来满足这些需求，该接口消费一个数据库和一组要执行的操作，并产生一个状态反映给定变更的数据库。提交的一批变更应该通过添加一个层来应用。然而，我们有一个问题：我们在底层 API 中编写的所有函数都会向数据库添加一个新层。如果我们要执行一批包含 n 个操作的操作，我们会看到 n 个新层被添加，而我们真正想要的是恰好一个新层。
关键在于我们想要的层是按顺序执行这些更新后产生的顶层。因此，解决方案是一个接一个地执行用户的操作，每个操作创建一个新层。当最后一层创建后，我们只取那个顶层并将其放在初始数据库上（让所有中间层去无用之地吧）。只有在完成所有这些之后，我们才会更新数据库的时间戳。
所有这些都在 transact-on-db 函数中完成，它接收数据库的初始值和要执行的一批操作，并返回更新后的值。
clojure
(defn transact-on-db [initial-db ops]
(loop [[op & rst-ops] ops transacted initial-db]
(if op
(recur rst-ops (apply (first op) transacted (rest op)))
(let [initial-layer (:layers initial-db)
new-layer (last (:layers transacted))]
(assoc initial-db :layers (conj initial-layer new-layer)
:curr-time (next-ts initial-db)
:top-id (:top-id transacted))))))注意这里我们使用了"值"这个术语，意味着只有这个函数的调用者接触到更新后的状态；数据库的所有其他用户都不知道这一变化（因为数据库是一个值，因此不能改变）。为了构建一个用户可以接触到其他人执行的状态变化的系统，用户不直接与数据库交互，而是通过另一层间接引用来引用它。这个附加层使用 Clojure 的 Atom（一种引用类型）来实现。这里我们利用了 Atom 的三个关键特性：
- 它引用一个值。
- 可以通过执行事务（使用 Clojure 的软件事务内存 (Software Transaction Memory) 功能）来更新
Atom的引用指向另一个值。该事务接受一个Atom和一个函数。该函数操作Atom的值并返回一个新值。事务执行后，Atom引用函数返回的值。 - 获取
Atom引用的值通过解引用 (dereferencing) 完成，它返回该时刻Atom的状态。
在 Clojure 的 Atom 和 transact-on-db 中完成的工作之间，仍然有一个需要弥合的差距；即用正确的输入调用事务。
为了拥有最简单、最清晰的 API，我们希望用户只需要提供 Atom 和操作列表，然后让数据库将用户输入转换为正确的事务。
这种转换发生在以下事务调用链中：
transact → _transact → swap! → transact-on-db
用户使用 Atom（即连接）和要执行的操作调用 transact，后者将输入转发给 _transact，并添加更新 Atom 的函数名称 (swap!)。
clojure
(defmacro transact [db-conn & txs] `(_transact ~db-conn swap! ~@txs))_transact 准备对 swap! 的调用。它通过创建一个列表来完成此操作，列表以 swap! 开始，后跟 Atom，然后是 transact-on-db 符号和一批操作。
clojure
(defmacro _transact [db op & txs]
(when txs
(loop [[frst-tx# & rst-tx#] txs res# [op db `transact-on-db] accum-txs# []]
(if frst-tx#
(recur rst-tx# res# (conj accum-txs# (vec frst-tx#)))
(list* (conj res# accum-txs#))))))swap! 在事务中调用 transact-on-db（使用之前准备好的参数），transact-on-db 创建数据库的新状态并返回它。
此时我们可以看到，通过一些小调整，我们还可以提供一种询问"假如"问题的方式。这可以通过用一个不对系统做任何更改的函数替换 swap! 来完成。这个场景通过 what-if 调用链实现：
what-if → _transact → _what-if → transact-on-db
用户使用数据库值和要执行的操作调用 what-if。然后它将这些输入转发给 _transact，并添加一个模仿 swap! API 但没有其副作用的函数（称为 _what-if）。
clojure
(defmacro what-if [db & ops] `(_transact ~db _what-if ~@ops))_transact 准备对 _what-if 的调用。它通过创建一个列表来完成此操作，列表以 _what-if 开始，后跟数据库，然后是 transact-on-db 符号和一批操作。_what-if 调用 transact-on-db，就像 swap! 在事务场景中所做的那样，但不对系统造成任何影响。
clojure
(defn- _what-if [db f txs] (f db txs))注意我们使用的不是函数而是宏 (macro)。这里使用宏的原因是宏的参数不会在调用发生时被求值；这使我们能够提供更简洁的 API 设计，用户以 Clojure 中任何函数调用的结构方式提供操作。
上述过程可以在以下示例中看到。对于事务，用户调用：
clojure
(transact db-conn (add-entity e1) (update-entity e2 atr2 val2 :db/add))变为：
clojure
(_transact db-conn swap! (add-entity e1) (update-entity e2 atr2 val2 :db/add))然后变为：
clojure
(swap! db-conn transact-on-db [[add-entity e1][update-entity e2 atr2 val2 :db/add]])对于 what-if，用户调用：
clojure
(what-if my-db (add-entity e3) (remove-entity e4))变为：
clojure
(_transact my-db _what-if (add-entity e3) (remove-entity e4))然后：
clojure
(_what-if my-db transact-on-db [[add-entity e3] [remove-entity e4]])最终：
clojure
(transact-on-db my-db [[add-entity e3] [remove-entity e4]])作为库的洞察提取
至此，我们已经具备了数据库的核心功能，是时候添加它的存在理由 (raison d'etre) 了：洞察提取。我们这里使用的架构方法是允许以库的方式添加这些功能，因为数据库的不同用途需要不同的机制。
图遍历
当实体的属性类型为 :db/ref 时，实体之间会创建引用连接，这意味着该属性的值是另一个实体的 ID。当引用实体被添加到数据库时，引用会在 VAET 索引中被索引。 VAET 索引中的信息可以被利用来提取指向某个实体的所有入链接。这在 incoming-refs 函数中完成，它收集在该索引中从实体可达的所有叶子节点：
clojure
(defn incoming-refs [db ts ent-id & ref-names]
(let [vaet (indx-at db :VAET ts)
all-attr-map (vaet ent-id)
filtered-map (if ref-names
(select-keys ref-names all-attr-map)
all-attr-map)]
(reduce into #{} (vals filtered-map))))我们也可以遍历给定实体的所有属性，收集类型为 :db/ref 的属性的所有值，从而提取该实体的所有出引用。这由 outgoing-refs 函数完成。
clojure
(defn outgoing-refs [db ts ent-id & ref-names]
(let [val-filter-fn (if ref-names #(vals (select-keys ref-names %)) vals)]
(if-not ent-id []
(->> (entity-at db ts ent-id)
(:attrs) (val-filter-fn) (filter ref?) (mapcat :value)))))这两个函数作为任何图遍历操作的基本构建块，因为它们将抽象层次从实体和属性提升到图中的节点和链接。一旦我们有了将数据库视为图的能力，我们就可以提供各种图遍历和查询 API。我们将此留作一个已解决的练习给读者；一个解决方案可以在本章的源代码中找到（见 graph.clj）。
查询数据库
我们要介绍的第二个库提供查询功能，这是本节的主要关注点。没有强大的查询机制，数据库对用户来说就不是很有用。这个功能通常通过查询语言 (query language) 暴露给用户，用于声明性地指定感兴趣的数据集。
我们的数据模型基于事实（即 datom）随时间的积累。对于这种模型，寻找合适查询语言的自然之处是逻辑编程 (logic programming)。一种受逻辑编程影响的常用查询语言是 Datalog，它除了非常适合我们的数据模型外，还有一种非常优雅的 Clojure 语法适配。我们的查询引擎将实现 Datomic 数据库 的 Datalog 语言的一个子集。
查询语言
让我们看一个使用我们提议的语言的示例查询。这个查询问的是："喜欢披萨、说英语且本月过生日的实体的姓名和生日是什么？"
clojure
{ :find [?nm ?bd ]
:where [
[?e :likes "pizza"]
[?e :name ?nm]
[?e :speak "English"]
[?e :bday (bday-mo? ?bd)]]}语法
我们直接使用 Clojure 的数据字面量语法来提供查询的基本语法。这使我们避免编写专门的解析器，同时为熟悉 Clojure 的程序员提供一种熟悉且易读的形式。
查询是一个包含两个条目的映射：
- 一个以
:where为键、以规则 (rule) 为值的条目。规则是子句 (clause) 的向量，子句是由三个谓词 (predicate) 组成的向量，每个谓词操作 datom 的不同组成部分。在上面的示例中，[?e :likes "pizza"]就是一个子句。这个:where条目定义了一个规则，作为数据库中 datom 的过滤器（类似于 SQL 的WHERE子句）。 - 一个以
:find为键、以向量为值的条目。该向量定义了所选 datom 的哪些组成部分应该被投影到结果中（类似于 SQL 的SELECT子句）。
上面的描述遗漏了一个关键需求：如何使不同的子句在一个值上同步（即在它们之间进行连接操作），以及如何在输出中构造找到的值（由 :find 部分指定）。
我们使用变量 (variable) 来满足这两个需求，变量以前导的 ? 表示。这个定义的唯一例外是"无关"变量 _（下划线）。
查询中的子句由三个谓词组成；表 10.2 定义了在我们的查询语言中什么可以作为谓词。
| 名称 | 含义 | 示例 |
|---|---|---|
| 常量 (Constant) | datom 中该项的值是否等于该常量？ | :likes |
| 变量 (Variable) | 将 datom 中该项的值绑定到变量并返回 true。 | ?e |
| 无关 (Don't-care) | 始终返回 true。 | _ |
| 一元运算符 (Unary operator) | 以变量作为操作数的一元操作。将 datom 中该项的值绑定到变量（除非它是 '_'）。用 datom 中该项的值替换变量。返回操作的应用结果。 | (bday-mo? _) |
| 二元运算符 (Binary operator) | 必须有一个变量作为操作数之一的二元操作。将 datom 中该项的值绑定到变量（除非它是 '_'）。用 datom 中该项的值替换变量。返回操作的结果。 | (> ?age 20) |
表 10.2 - 谓词
查询语言的限制
工程学完全是关于管理权衡的，设计我们的查询引擎也不例外。在我们的案例中，需要解决的主要权衡是功能丰富度与复杂度。解决这一权衡需要我们审视系统的常见用例，并从中决定哪些限制是可以接受的。
在我们的数据库中，我们决定构建一个具有以下限制的查询引擎：
- 用户不能在子句之间定义逻辑操作；它们始终通过 'AND' 连接。（这可以通过使用一元或二元谓词来解决。）
- 如果查询中有多个子句，必须有一个在该查询的所有子句中都出现的变量。这个变量充当连接变量。这个限制简化了查询优化器。
- 查询只在单个数据库上执行。
虽然这些设计决策导致查询语言不如 Datalog 丰富，但我们仍然能够支持许多类型的简单但有用的查询。
查询引擎设计
虽然我们的查询语言允许用户指定他们想要访问什么，但它隐藏了如何实现的细节。查询引擎是负责为给定查询产生数据的数据库组件。
这涉及四个步骤：
- 转换为内部表示：将查询从文本形式转换为查询计划器消费的数据结构。
- 构建查询计划：确定一个高效的计划 (plan) 来产生给定查询的结果。在我们的案例中，查询计划是一个要调用的函数。
- 执行计划：执行计划并将其结果发送到下一阶段。
- 统一和报告：仅提取需要报告的结果并按指定格式进行格式化。
阶段 1：转换
在这个阶段，我们将给定的查询从用户容易理解的表示转换为查询计划器可以高效消费的表示。
查询的 :find 部分被转换为给定变量名称的集合：
clojure
(defmacro symbol-col-to-set [coll] (set (map str coll)))查询的 :where 部分保留其嵌套向量结构。然而，每个子句中的每个术语都根据表 10.2 被替换为谓词。
clojure
(defmacro clause-term-expr [clause-term]
(cond
(variable? (str clause-term)) ;variable
#(= % %)
(not (coll? clause-term)) ;constant
`#(= % ~clause-term)
(= 2 (count clause-term)) ;unary operator
`#(~(first clause-term) %)
(variable? (str (second clause-term)));binary operator, 1st operand is variable
`#(~(first clause-term) % ~(last clause-term))
(variable? (str (last clause-term)));binary operator, 2nd operand is variable
`#(~(first clause-term) ~(second clause-term) %)))对于每个子句，一个包含该子句中使用的变量名称的向量被设置为其元数据。
clojure
(defmacro clause-term-meta [clause-term]
(cond
(coll? clause-term) (first (filter #(variable? % false) (map str clause-term)))
(variable? (str clause-term) false) (str clause-term)
:no-variable-in-clause nil))我们使用 pred-clause 来遍历每个子句中的术语：
clojure
(defmacro pred-clause [clause]
(loop [[trm# & rst-trm#] clause exprs# [] metas# []]
(if trm#
(recur rst-trm# (conj exprs# `(clause-term-expr ~ trm#))
(conj metas#`(clause-term-meta ~ trm#)))
(with-meta exprs# {:db/variable metas#}))))遍历子句本身发生在 q-clauses-to-pred-clauses 中：
clojure
(defmacro q-clauses-to-pred-clauses [clauses]
(loop [[frst# & rst#] clauses preds-vecs# []]
(if-not frst# preds-vecs#
(recur rst# `(conj ~preds-vecs# (pred-clause ~frst#))))))我们再次依赖于宏不会急切求值其参数这一事实。这使我们能够定义更简单的 API，用户以符号形式提供变量名（例如 ?name），而不是要求用户理解引擎的内部机制并以字符串形式提供变量名（例如 "?name"），或者更糟糕的是引用变量名（例如 '?name）。
在这个阶段结束时，我们的示例为 :find 部分产生以下集合：
clojure
#{"?nm" "?bd"}以及表 10.3 中 :where 部分的以下结构。（"谓词子句"列中每个单元格持有其在"元数据子句"列中邻居的元数据。）
| 查询子句 | 谓词子句 | 元数据子句 |
|---|---|---|
| [?e :likes "pizza"] | [#(= % %) #(= % :likes) #(= % "pizza")] | ["?e" nil nil] |
| [?e :name ?nm] | [#(= % %) #(= % :name) #(= % %)] | ["?e" nil "?nm"] |
| [?e :speak "English"] | [#(= % %) #(= % :speak) #(= % "English")] | ["?e" nil nil] |
| [?e :bday (bday-mo? ?bd)] | [#(= % %) #(= % :bday) #(bday-mo? %)] | ["?e" nil "?bd"] |
表 10.3 - 子句
这个结构充当在后续阶段执行的查询，一旦引擎决定了正确的执行计划。
阶段 2：制定计划
在这个阶段，我们检查查询以构建一个好的计划来产生它描述的结果。
通常，这涉及选择适当的索引（表 10.4）并以函数的形式构建计划。我们根据单一连接变量（只能操作单一类型的元素）来选择索引。
| 连接变量操作的对象 | 使用的索引 |
|---|---|
| 实体 ID | AVET |
| 属性名称 | VEAT |
| 属性值 | EAVT |
表 10.4 - 索引选择
这种映射背后的推理将在下一节实际执行计划时变得更加清晰。现在只需注意，关键是选择一个叶子节点持有连接变量所操作元素的索引。
定位连接变量的索引由 index-of-joining-variable 完成：
clojure
(defn index-of-joining-variable [query-clauses]
(let [metas-seq (map #(:db/variable (meta %)) query-clauses)
collapsing-fn (fn [accV v] (map #(when (= %1 %2) %1) accV v))
collapsed (reduce collapsing-fn metas-seq)]
(first (keep-indexed #(when (variable? %2 false) %1) collapsed))))我们首先提取查询中每个子句的元数据。提取的元数据是一个 3 元素向量；每个元素要么是变量名，要么是 nil。（注意该向量中最多只有一个变量名。）一旦向量被提取，我们从中（通过 reduce）产生一个单一的值，它要么是变量名要么是 nil。如果产生了变量名，那么它出现在所有元数据向量的相同索引位置；即这是连接变量。因此我们可以根据上述映射选择与该连接变量相关的索引。
一旦选择了索引，我们构建计划，这是一个闭包 (closure)，它关闭了查询和索引名称，并执行返回查询结果所需的操作。
clojure
(defn build-query-plan [query]
(let [term-ind (index-of-joining-variable query)
ind-to-use (case term-ind 0 :AVET 1 :VEAT 2 :EAVT)]
(partial single-index-query-plan query ind-to-use)))在我们的示例中，选择的索引是 AVET 索引，因为连接变量操作的是实体 ID。
阶段 3：执行计划
我们在上一阶段看到，查询计划最终调用 single-index-query-plan。这个函数将：
- 在索引上应用每个谓词子句（每个谓词在适当的索引层级上）。
- 对结果执行 AND 操作。
- 将结果合并为更简单的数据结构。
clojure
(defn single-index-query-plan [query indx db]
(let [q-res (query-index (indx-at db indx) query)]
(bind-variables-to-query q-res (indx-at db indx))))为了更好地解释这个过程，我们将使用示例查询来演示它，假设数据库持有表 10.5 中的实体。
| 实体 ID | 属性名称 | 属性值 |
|---|---|---|
| 1 | :name :likes :speak :bday | USA Pizza English July 4, 1776 |
| 2 | :name :likes :speak :bday | France Red wine French July 14, 1789 |
| 3 | :name :likes :speak :bday | Canada Snow English July 1, 1867 |
表 10.5 - 示例实体
现在是时候深入兔子洞，看看 query-index 函数了，我们的查询终于开始在这里产生一些结果：
clojure
(defn query-index [index pred-clauses]
(let [result-clauses (filter-index index pred-clauses)
relevant-items (items-that-answer-all-conditions (map last result-clauses)
(count pred-clauses))
cleaned-result-clauses (map (partial mask-path-leaf-with-items
relevant-items)
result-clauses)]
(filter #(not-empty (last %)) cleaned-result-clauses)))这个函数首先将谓词子句应用到之前选择的索引上。每个谓词子句在索引上的应用返回一个结果子句 (result clause)。
结果的主要特征是：
- 它由三个项目组成，每个来自索引的不同层级，每个都通过了各自的谓词。
- 项目的顺序匹配索引的层级结构。（谓词子句始终按 EAV 顺序。）重新排序是在对谓词子句应用索引的
from-eav时完成的。 - 谓词子句的元数据附加在上面。
所有这些都在 filter-index 函数中完成。
clojure
(defn filter-index [index predicate-clauses]
(for [pred-clause predicate-clauses
:let [[lvl1-prd lvl2-prd lvl3-prd] (apply (from-eav index) pred-clause)]
[k1 l2map] index ; keys and values of the first level
:when (try (lvl1-prd k1) (catch Exception e false))
[k2 l3-set] l2map ; keys and values of the second level
:when (try (lvl2-prd k2) (catch Exception e false))
:let [res (set (filter lvl3-prd l3-set))] ]
(with-meta [k1 k2 res] (meta pred-clause))))假设查询在 7 月 4 日执行，在上述数据上执行的结果如表 10.6 所示。
| 结果子句 | 结果元数据 |
|---|---|
| [:likes Pizza #{1}] | ["?e" nil nil] |
| [:name USA #{1}] | ["?e" nil "?nm"] |
| [:speak "English" #{1, 3}] | ["?e" nil nil] |
| [:bday "July 4, 1776" #{1}] | ["?e" nil "?bd"] |
| [:name France #{2}] | ["?e" nil "?nm"] |
| [:bday "July 14, 1789" #{2}] | ["?e" nil "?bd"] |
| [:name Canada #{3}] | ["?e" nil "?nm"] |
| [:bday "July 1, 1867" #{3}] | ["?e" nil "?bd"] |
表 10.6 - 查询结果
一旦我们产生了所有的结果子句，我们需要在它们之间执行 AND 操作。这通过找到通过了所有谓词子句的所有元素来完成：
clojure
(defn items-that-answer-all-conditions [items-seq num-of-conditions]
(->> items-seq ; take the items-seq
(map vec) ; make each collection (actually a set) into a vector
(reduce into []) ;reduce all the vectors into one vector
(frequencies) ;count for each item in how many collections (sets) it was in
(filter #(<= num-of-conditions (last %))) ;items that answered all conditions
(map first) ; take from the duos the items themselves
(set))) ; return it as set在我们的示例中，这一步的结果是一个持有值 1（即 USA 的实体 ID）的集合。
我们现在必须移除没有通过所有条件的项目：
clojure
(defn mask-path-leaf-with-items [relevant-items path]
(update-in path [2] CS/intersection relevant-items))最后，我们移除所有"空"的结果子句（即它们的最后一项为空）。我们在 query-index 函数的最后一行完成这个操作。我们的示例留下了表 10.7 中的项目。
| 结果子句 | 结果元数据 |
|---|---|
| [:likes Pizza #{1}] | ["?e" nil nil] |
| [:name USA #{1}] | ["?e" nil "?nm"] |
| [:bday "July 4, 1776" #{1}] | ["?e" nil "?bd"] |
| [:speak "English" #{1}] | ["?e" nil nil] |
表 10.7 - 过滤后的查询结果
我们现在准备报告结果了。结果子句的结构对于此目的来说不太方便，所以我们将其转换为类似索引的结构（映射的映射）——但有一个重要的变化。
要理解这个变化，我们必须首先引入绑定对 (binding pair) 的概念，它是将变量名与其值匹配的一对。变量名是在谓词子句中使用的那个，值是在结果子句中找到的值。
索引结构的变化在于，我们现在在索引中保存实体 ID / 属性名 / 值的位置放置了实体 ID / 属性名 / 值的绑定对：
clojure
(defn bind-variables-to-query [q-res index]
(let [seq-res-path (mapcat (partial combine-path-and-meta (from-eav index))
q-res)
res-path (map #(->> %1 (partition 2)(apply (to-eav index))) seq-res-path)]
(reduce #(assoc-in %1 (butlast %2) (last %2)) {} res-path)))
(defn combine-path-and-meta [from-eav-fn path]
(let [expanded-path [(repeat (first path)) (repeat (second path)) (last path)]
meta-of-path (apply from-eav-fn (map repeat (:db/variable (meta path))))
combined-data-and-meta-path (interleave meta-of-path expanded-path)]
(apply (partial map vector) combined-data-and-meta-path)))在示例执行的第 3 阶段结束时，我们手中有以下结构：
clojure
{[1 "?e"]{
{[:likes nil] ["Pizza" nil]}
{[:name nil] ["USA" "?nm"]}
{[:speaks nil] ["English" nil]}
{[:bday nil] ["July 4, 1776" "?bd"]}
}}阶段 4：统一和报告
此时，我们已经产生了用户最初请求的结果的超集。在这个阶段，我们将提取用户想要的值。这个过程称为统一 (unification)：我们将在这里将绑定对结构与用户在查询的 :find 子句中定义的变量名称向量进行统一。
clojure
(defn unify [binded-res-col needed-vars]
(map (partial locate-vars-in-query-res needed-vars) binded-res-col))每个统一步骤由 locate-vars-in-query-result 处理，它遍历查询结果（结构为类似索引的条目，但带有绑定对）以检测用户请求的所有变量和值。
clojure
(defn locate-vars-in-query-res [vars-set q-res]
(let [[e-pair av-map] q-res
e-res (resultify-bind-pair vars-set [] e-pair)]
(map (partial resultify-av-pair vars-set e-res) av-map)))
(defn resultify-bind-pair [vars-set accum pair]
(let [[ var-name _] pair]
(if (contains? vars-set var-name) (conj accum pair) accum)))
(defn resultify-av-pair [vars-set accum-res av-pair]
(reduce (partial resultify-bind-pair vars-set) accum-res av-pair))在这个阶段结束时，我们示例的结果是：
clojure
[("?nm" "USA") ("?bd" "July 4, 1776")]运行整个流程
我们终于构建了面向用户的查询机制所需的所有组件，即 q 宏，它接收数据库和查询作为参数。
clojure
(defmacro q
[db query]
`(let [pred-clauses# (q-clauses-to-pred-clauses ~(:where query))
needed-vars# (symbol-col-to-set ~(:find query))
query-plan# (build-query-plan pred-clauses#)
query-internal-res# (query-plan# ~db)]
(unify query-internal-res# needed-vars#)))总结
我们的旅程始于对一种不同类型数据库的构想，并以一个如下的数据库结束：
- 支持 ACI 事务（当我们决定将数据存储在内存中时，持久性就丢失了）。
- 支持"假如"交互。
- 回答与时间相关的问题。
- 处理使用索引优化的简单 Datalog 查询。
- 提供图查询的 API。
- 引入并实现了演化查询 (evolutionary query) 的概念。
还有许多可以改进的地方：我们可以为几个组件添加缓存以提高性能；支持更丰富的查询；添加真正的存储支持以提供数据持久性，仅举几例。
然而，我们的最终产品可以做很多事情，并且使用 488 行 Clojure 源代码实现，其中 73 行是空行，55 行是文档字符串。
最后，还有一件事仍然缺少：一个名字。对于一个使用 360 行 Clojure 代码实现的内存型、索引优化、支持查询、对库开发者友好、具有时间感知能力的函数式数据库，唯一合理的选择就是 CircleDB。