GroveDB

分支	测试	覆盖率
master

具有高效二级索引查询的层次化认证数据结构

GroveDB 是一个专为高效二级索引查询、证明、速度和可靠性而设计的数据库系统。它专为在 Dash 平台 上使用而构建，但也可以轻松集成到其他类似用途的应用程序中。

动机

二级索引对于任何数据库管理系统都至关重要。所有先前的解决方案都根据它们试图解决的问题有一定的权衡。

考虑一个认证数据结构，例如建立在餐厅数据库上的 Merkle 树。每个餐厅都有一些属性，例如价格和类型

struct Restaurant{
	ID uint32;
	name: String;
	type: String;
	isVegan: bool;
};

如果我们有四家餐厅，我们可能会像下面这样将它们提交到 Merkle 树中

graph TD;
root-->A[" "];
root-->B[" "];
A-->AA["id:0"];
A-->AB["id:1"];
B-->AC["id:2"];
B-->AD["id:3"];

按主键查询既简单又高效。如果我们有一个查询，如 SELECT * WHERE ID <= 2; ，我们可以返回相应的元素，同时构建一个高效的区间证明。然而，通过二级索引进行查询并不高效；你很可能会不得不迭代整个结构。考虑以下查询 SELECT * WHERE isVegan=true;。当按主键排序时，素食餐厅不会连续。这不仅证明是非平凡的，而且查找这些元素所需的时间也会很长。

GroveDB 是一种经典的时间-空间权衡。它通过预计算和提交来实现了在二级索引上的高效查询。构建并提交了每个可能的可查询二级索引的子树（上限）。这是一个子树集合；一个森林。对于相同的数据，类似的 GroveDB 结构可能看起来像这样

graph TD;
root-->A["\'Restaurant\'"];
root-->B["..."];
A-->Q["ID"];
A-->W["name"];
A-->E["kind"];
A-->R["isVegan"];
Q-->Z["..."];
W-->X["..."];
E-->C["..."];
R-->Y["id:2"];
R-->U["id:1"];
R-->I["id:0"];
R-->O["id:3"];

从这里，对二级索引 isVegan 的查询将遍历为该二级索引构建的子树。项目可能不一定是复制的，而是引用的。

特性

• 高效的二级索引查询 - 特地为二级索引查询设计和定制。
• 证明 - 支持成员资格证明、非成员资格证明和范围证明。
• 运行在任何地方 - 由于是用 Rust 编写的，它支持所有编译目标。x86、树莓派（AArch64）和 Wasm。还有 Node.js 绑定。

架构

插入和删除操作如你所预期，更新相应的子树并返回适当的成员资格/非成员资格证明。

树结构

我们选择了一个统一的结构，而不是不相交的认证数据结构；一个基于具有分层认证数据结构的数据库外包的分层认证数据结构。元素是最基本的组件，可以以几种方式表示。它们可以是项目、项目引用、树、带有项目的树，甚至是带有项目引用的树。一个元素包含一个项目、对象的引用或子树。

这些树基于我们对 Merk 的分支，并应用了针对 GroveDB 使用的自定义补丁。Merk 的独特之处在于它是一个 AVL 树，所以中间节点也包含一个键/值对。每个节点包含一个第三哈希，即 kv_hash，除了其左右子节点的哈希之外。kv_hash 简单地计算为 kv_hash=H(key,value)。然后计算节点哈希为 H(kv_hash,left_child_hash,right_child_hash)。Merk 使用 Blake2B，而 rs-merkle 使用 SHA256。

存储

RocksDB 是一个键值存储，源自 LevelDB，由 Facebook 开发。我们选择它是因为其高性能、成熟度以及与我们的堆栈的兼容性。Merk 本身是基于 RocksDB 构建的。

我们有三类存储：辅助存储、元数据存储和树根存储。辅助存储用于存储不用于共识的纯键值数据。元数据用于存储 GroveDB 使用范围之外的东西。它没有前缀，因此与子树无关。它存在于更高的层面。树根存储用于存储子树。

GroveDB 中的数据库事务是围绕 RocksDB 的 OptimisticTransactionDB 基本原语的一个包装。乐观事务希望平均只有少数冲突，这些冲突在提交阶段被检测到。这与使用锁的悲观模型相比。

查询

要查询 GroveDB，必须提供路径和查询项目。路径指定子树，而查询项目确定从子树中选择哪些节点。

GroveDB 目前支持 10 种查询项目类型

• 键(key_name)
• 范围(start..end)
• 范围（包含）(start..=end)
• 范围（全部）(..)
• 范围从(start..)
• 范围到(..end)
• 范围到（包含）(..=end)
• 范围之后(prev..)
• 范围之后到(prev..end)
• 范围之后到（包含）(prev..=end)

这描述了一个基本的查询系统：选择一个子树然后从该子树中选择节点。可能需要创建更复杂的查询或对结果集添加限制，这导致我们转向 PathQuery。

PathQuery

PathQuery 允许进行更复杂的查询，并可以对结果集进行可选限制，即限制和偏移量。

    PathQuery
        path: [k1, k2, ..]
        sized_query: SizedQuery
            limit: Optional<number>
            offset: Optional<number>
            query: Query
                items: [query_item_1, query_item_2, ...],
                default_subquery_branch: SubqueryBranch
                    subquery_path: Optional<key>
                    subquery_value: Optional<Query>
                conditional_subquery_branches: Map<QueryItem, SubqueryBranch>
                        

需要一个路径来定义查询的起始上下文。

大小查询

代码sized_query决定结果集的限制方式。它包含可选的限制和偏移量。代码limit决定结果集的最大大小，而代码offset指定在添加到结果集之前需要跳过的元素数量。

查询

代码query对象是一个递归结构 - 它指定如何从当前子树中选择节点，并且可以选择递归地将另一个查询应用到前一个查询得到的结果集上。

项目

代码items是一组查询项目，用于决定从当前上下文中选择哪些节点（这构建了一个结果集）。

在描述default_subquery_branch和conditional_subquery_branches之前，我们需要定义它们的构建块，即子查询分支

子查询分支

    subquery_path: Optional<Key>
    subquery_value: Optional<Query>

情况

• subquery_path: true，subquery_value: false
  选择带有子查询路径的节点，并将其作为结果集返回。

• subquery_path: false，subquery_value: true
  直接将子查询_value中的查询应用到子树上，并将结果作为结果集返回。

• subquery_path: true，subquery_value: true首先选择带有子查询路径的节点并将其设置为新的上下文。
  然后，将子查询值应用到这个新的上下文中，并将结果作为结果集返回。

子查询分支用于单个节点，但可以使用default_subquery_branch和conditional_subquery_branches将其应用到前一个查询的结果集上。

默认子查询分支

如果存在，则将指定的子查询分支应用于前一个查询结果集中的每个节点。

条件子查询分支

而不是将子查询分支应用到结果集中的每个节点，您可能只想将其应用到结果集的一个子集。在这种情况下，我们使用条件子查询。

条件子查询包含查询项目到子查询分支的映射。

    Map<QueryItem, SubqueryBranch>

对于结果集中的每个节点，我们检查是否存在匹配该节点的查询项目。如果存在，则将关联的子查询分支应用到该节点。请注意，一旦条件子查询被应用到节点，默认子查询就不在该节点上运行。

合并路径查询

本节描述GroveDB如何处理路径查询的合并。

可合并的路径查询允许将执行不同操作的单独路径查询组合成单个等效路径查询。

路径查询可以表示为一组键（子树路径）和应用于该子树的查询（查询可以有未知深度）。

p_i = [k₁，k₂，..，k_n，Query]

非常重要的一点是，路径查询链可以在任何点压缩，即您可以将键序列转换为一个单一查询。

考虑p₁ = [k₁，k₂，k₃]。这可以读作

• 从根树中选择键为k1的节点
• 将上下文更改为k1，然后选择键为k2的节点
• 将上下文更改为k2，最后选择键为k3的节点

我们可以创建一个等效查询来表示这一点，它可以看起来像这样

    Query
        query k1
        cond on k1
            query k2
            cond on k2
                query k3
                cond on k3

[\(k₁, k₂, k₃\)] => Q₁，其中 Q₁ 等同于路径数组。

这也可以在任何路径数组点上执行，因此我们可以有

[\(k₁, k₂, k₃\)] => [\(\(k₁, Q₂\)]
[\(k₁, k₂, k₃\)] => [K₁, K₂ Q₃]

路径合并算法变为

• 在路径查询中找到公共路径
• 将每个路径数组压缩到公共路径索引之后的查询
• 将压缩查询合并为单个查询
• 返回新的路径查询，公共路径作为路径，组合查询作为查询

示例
p₁ = [\(\(k₁, k₂, k₃, Qₐ\)]
p₂ = [\(\(k₁, k₂, k₄, Qₐ₅\)]

公共路径 = [\(\(k₁, k₂\)]

在公共路径之后压缩每个路径数组
p₁ = [\(\(k₁, k₂, Qₐ₆\)]
p₂ = [\(\(k₁, k₂, Qₐ₇\)]

合并压缩查询
Qₚ = Qₐ₆ + Qₐ₇

返回最终的 PathQuery
pₙ = [\(\(k₁, k₂, Qₚ\)]

用法

GroveDB 是为与 Dash 平台一起使用而构建的，但可以轻松集成到其他应用程序中进行类似使用。请参阅其在 rs-drive（示例）中的使用。

我们目前还有 Node.js 的绑定。请参阅 node-grove。

构建

首先，使用您首选的方法安装 rustup。

构建需要 Rust 夜间版本，因此请确保您正在使用正确的版本。

rustup安装夜间版本

克隆仓库并导航到主目录

gitclone https://github.com/dashevo/grovedb.git && cdgrovedb

从这里我们可以构建

cargobuild

grovedbg

有一个正在进行的 GroveDB 调试器层实现。要使用具有这些功能启用的库，需要设置具有 grovedbg 特性的依赖项。

然后，要启动可视化工具以在端口（例如 10000）上观察浏览器中的数据库结构，以下代码片段应执行

    let db = Arc::new(GroveDb::open("db").unwrap());
    db.start_visualzier(10000);

只需记住使用 Arc，因为 HTTP 服务器可能会超过 GroveDB 实例的生命周期。

性能

使用 cargo test