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绑定。

架构

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

树结构（s）

我们选择统一的而不是不相交的认证数据结构；一个基于 Database Outsourcing with Hierarchical Authenticated Data Structures 的分层认证数据结构。元素是最原子的组件，可以用几种方式表示。它们可以是项目、项目引用、树、带项目的树，甚至是带项目引用的树。一个元素包含一个项目、一个对象的引用或一个子树。

这些树基于我们对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>
                        

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

SizedQuery

sized_query确定如何限制结果集。它包含可选的限制和偏移值。其中，limit确定结果集的最大大小，而offset指定在添加到结果集之前要跳过的元素数量。

Query

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

Items

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
  将保存在子查询值中的查询直接应用于子树，并将结果作为结果集返回。

• 首先，选择具有子查询路径的节点，并将其设置为新的上下文。
  然后，将子查询值应用于此新上下文，并将结果作为结果集返回。

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

default_subquery_branch

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

conditional_subquery_branch

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

条件子查询包含一个从QueryItem到SubqueryBranch的映射。

    Map<QueryItem, SubqueryBranch>

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

路径查询合并

本节介绍了GroveDB如何处理路径查询的合并。

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

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

p_i = [k₁, k₂, .., k_n, 查询]

以下内容非常重要：路径查询链可以在任何点进行压缩，即可以将一系列键转换为一个查询。

考虑 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₁，其中 Q1 等价于路径数组。

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

[k₁, k₂, k₃] => [k₁, Q₂]
[k₁, k₂, k₃] => [K₁, K₂ Q₃]

路径合并算法变为

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

示例
p₁ = [k₁, k₂, k₃, Q_a]
p₂ = [k₁, k₂, k₄, Q_b]

公共路径 = [k1, k2]

压缩公共路径后的每个路径数组
p₁ = [k₁, k₂, Q_c]
p₂ = [k₁, k₂, Q_d]

合并压缩查询
Q_p = Q_c + Q_d

返回最终的 PathQuery
p_f = [k₁, k₂, Q_p]

用法

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

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

构建

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

构建需要Rust nightly版本，因此请确保您使用的是正确的版本。

rustup安装nightly

克隆仓库并导航到主目录

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

lib.rs:

GroveDB的存储抽象。