Graviton数据库：用于键值存储的ZFS

Graviton数据库是一个简单、快速、版本化、经过身份验证、可嵌入纯GOLANG的密钥值存储数据库。简而言之，Graviton数据库类似于密钥值存储的ZFS，其中的每一次写入都使用密码证明进行跟踪、版本控制和身份验证。此外，还可以拍摄数据库的快照。此外，即使在实时更新期间也可以使用简单的copy、rsync命令进行数据库备份，而不会出现任何数据库损坏的可能性。

引力子目前是阿尔法软件。使用几乎全单元测试复盖率和随机黑盒测试来确保数据库一致性和线程安全。该项目已经拥有100%的代码覆盖率。许多决策，如更改、重命名API、处理错误、散列算法等正在评估中，并公开征求改进和建议。

在单个数据存储中支持2^64个树(理论上)。树可以命名，因此可以用作水桶。

支持值版本跟踪。所有提交的更改都已版本化，能够在任何时间点访问它们。

快照(单个版本中的多树提交导致多存储桶同步，可以访问、追加和进一步修改每个快照、删除键、修改值等、存储新键、值。)。

能够在线性时间内在2个树之间进行差异，并报告所有插入、删除、修改的更改。)。

能够生成可以证明密钥存在或不存在的密码证明(密码证明大约为1KB。)。

区分(对2个树进行区分，以检测版本之间的更改或在线性时间内比较2个任意树。)

Graviton中的顶级对象是Store。它表示为服务器磁盘上包含多个文件的目录，并且始终代表数据的一致快照。

软件包mainimport"；fmt"；import"；github.com/deroproject/graviton"；func main(){//store，_：=graviton.NewDiskStore("；/tmp/testdb"；)//在"；/tmp/testdb"；中创建新的testdb；Store，_：=graviton.NewMemStore()//在RAM ss中新建数据库，_：=store.LoadSnapshot(0)//加载最新的快照树，_：=ss.GetTree("；root"；)//使用或创建名为"；root"；tree.Put([]byte("；key"；)，[]byte("；value"；)。))//插入一个值graviton.Commit(Tree)//提交树值，_：=tree.Get([]byte("；key"；))fmt.Printf("；value从DB\"；%s\"；，String(Value))}//注意：Linux(或其他平台)的打开文件限制为1024。//默认限制允许最大2TB的Graviton数据库。

Graviton DB中的树就像BoltDB或ZFS数据集中的桶。它是命名的，最多可以包含128个字节的名称。任何商店都可以包含无限棵树。每个树还可以包含无限的键值对。然而，实际上受到服务器或系统存储空间的限制。

使用"；GetTreeWithRootHash"；API可以通过Merkle根散列访问每个树。此外，每个树都维护自己的单独版本号，并且任何特定版本都可以使用GetTreeWithVersion。请注意，每个树也可以具有任意标记，并且可以使用标记GetTreeWithTag访问任何标记的树。另外，2个任意树可以在线性时间和检测到的相关变化方面不同。

要将键/值对保存到树(或桶)中，请使用tree.Put()函数：

树，_：=ss。GetTree("；根"；)树。Put([]byte("；Answer"；)，[]byte("；44"；))//插入一个值引力。Commit(Tree)//将树保存在后端磁盘，使其持久化。

这将在根树中将"；答案"；键的值设置为"；44"；。要检索此值，我们可以使用tree.Get()函数：

Get()函数返回一个错误，因为它的操作是有保证的(除非我们试图报告某种系统故障)。如果键存在，则它将返回其字节片值。如果它不存在，则它将返回错误。

Graviton以散列字节排序的顺序将其密钥存储在树中。这使得对这些键的顺序迭代非常快。要迭代键，GravitonDB使用游标：

//假设"；根"；树存在并且具有密钥树，_：=store。GetTree("；root"；)c：=tree。Cursor()for k，v，err：=c.first()；err==nil；k，v，err=c.Next(){fmt.。Printf("；键=%s，值=%s\n"；，k，v)}。

光标允许您移动到键列表中的特定点，并通过键向前或向后移动，一次移动一个。

First()移动到第一个关键点。Last()移动到最后一个关键点。Next()移动到下一个关键点。Prev()移动到上一个关键点。

这些函数中的每个函数都有一个返回签名(key[]byte，value[]byte，err error)。当您迭代到游标的末尾时，Next()将返回错误ErrNoMoreKeys。在调用Next()或Prev()之前，必须使用First()、Last()查找位置。如果您不寻找位置，则这些函数将返回错误。

快照是指所有存储桶+数据+历史的集合状态。每次提交(tree.Commit()或Commit(tree1，tree2.))。在存储中创建新快照。每个快照由递增的uint64数字表示，0表示最新的快照。快照可用于在任何时间点访问整个数据库的任意状态。

软件包mainimport"；fmt"；import"；github.com/deroproject/graviton"；func main(){key：=[]byte("；key1"；)//store，_：=graviton.NewDiskStore("；/tmp/testdb"；)//在"；/tmp/testdb"；中创建新的testdb；Store，_：=graviton.NewMemStore()//在RAM ss中新建一个数据库，_：=store.LoadSnapshot(0)//加载最新的快照树，_：=ss.GetTree("；root"；)//使用或创建名为"；root"；tree.Put(key，[]byte("；Commit_Value1"；)//插入值Commit1，_：=graviton.Commit(Tree)//提交树。Put(key，[]byte("；Commit_Value 2"；))//覆盖现有值Commiton.Commit(Tree)//再次提交树//在第一次提交或快照时，"；root"；tree包含"；key1：Commit_。//在第二次提交或快照时，"；root"；树包含"；key1：Commit_value2&34；//我们现在将遍历Commit1快照ss，_=store.LoadSnapshot(Commit1)树，_=ss.GetTree("；root"；)值，err：=tree.Get(Key)fmt.Printf("；快照%d键%s值%s错误%s\n&。，ss.GetVersion()，String(Key)，String(Value)，err)//我们现在将遍历Commit2快照ss，_=store.LoadSnapshot(Commit2)tree，_=ss.GetTree("；root"；)value，err=tree.Get(Key)fmt.Printf("；快照%d密钥%s值%s错误%s\n"；，ss.GetVersion()，

区分2个树以检测版本之间的更改或在线性时间内比较2个任意树。

可以在线性时间内区分两个任意树以检测变化。更改分为插入、删除和修改三种类型(键相同但值更改)。如果报告的更改应用于基树，则等同于要比较的头树。

该算法在时间上是线性变化的。例.。一棵数十亿KVS的树几乎可以瞬间与父树相异。

即使在更新Graviton数据库时，也可以使用cp、copy或rsync等简单命令来同步该数据库。但是，由于数据库可能会持续追加，备份始终会有一点延迟。请注意，在执行提交时，数据库或备份在复制期间永远不会损坏。

提供了一个进行单线程测试的迷你工具，可用于在内存或磁盘后端执行各种测试。

在内部，所有树都存储在具有折叠路径的基数-2\f25 Merkle-2中。这意味着如果树有40亿个键值对，那么它的深度只有32层，这会极大地节省存储空间，这也意味着当您修改现有的键值时，只接触到有限数量的节点。

~/Tools/gocloc--逐文件NODE_INNER.GO树.GO快照.GO校样.GO节点_叶.GO STORE.GO节点.GO散列.GO常量.GO文档.GO DIFF_TREE.GO Cursor.GO-File文件为空。注释code-node_inner.go 76 33 364商店。转69 22 250树。转75 71 250验证。转30 16 171快照。转至36 18 155 node_leaf.go 29 3 150diff_tree.go 34 33 133 cursor.go 21 15 106 node.go 5 3 35const。Go 4 0 21 hash.go 7 2 19doc.go 16 42 1-TOTAL 12 402 2581655。。

目前，我们有错误报告api来报告ROT位，但没有关于磁盘损坏的报告，如果我们应该放弃这样的错误设计并使API更简单(除了快照、树加载、提交，不再有错误)。需要对此进行更多讨论-需要硬盘故障、错误等。

以下数据库都不提供每次提交的回溯功能。GravitonDB是唯一提供回溯的数据库。另外，目前，GravitonDB是唯一一个可以在线性时间内在两棵树之间进行差异的数据库。让我们比较一下某些数据库的其他功能。

关系数据库将数据组织成行，并且只能通过使用SQL进行访问。这种方法在如何存储和查询数据方面提供了灵活性，但在解析和规划SQL语句时也会产生开销。GravitonDB通过字节片关键字访问所有数据。这使得GravitonDB可以快速地按键读写数据，但不提供将值连接在一起的内置支持。

大多数关系数据库(SQLite除外)是独立于应用程序运行的独立服务器。这为系统提供了将多个应用程序服务器连接到单个数据库服务器的灵活性，但也增加了串行化和通过网络传输数据的开销。Graviton作为一个库运行在您的应用程序中，因此所有数据都必须经过您的应用程序的进程才能访问。这使数据更接近您的应用程序，但限制了对数据的多进程访问。

LevelDB及其衍生物(RocksDB、HyperLevelDB)类似于Graviton，因为它们是绑定到应用程序中的库，但是，它们的底层结构是日志结构的合并树(LSM树)。LSM树通过使用预写日志和称为SSTables的多层排序文件来优化随机写入。引力子在内部使用基数为2的Merkle树。这两种方法都有取舍之处。

如果您需要较高的随机写入吞吐量或需要使用固定磁盘，那么LevelDB可能是一个很好的选择，除非有版本控制、验证校样或Graviton数据库的其他功能的要求。

LMDB和Bolt在架构上相似。两者都使用B+树，具有完全可序列化事务的ACID语义，并且支持使用单个写入器和多个读取器的无锁MVCC。

此外，LMDB非常注重原始性能，而BoltDB则注重简单性和易用性。例如，出于性能考虑，LMDB允许几个不安全的操作，例如直接写入。Bolt选择不允许可能使数据库处于损坏状态的操作。Bolt中唯一的例外是DB.NoSync.GravitonDB在任何时间点都不会使数据库处于损坏状态。

此外，除了LMDB，BoltDB不支持版本控制、快照、线性差异等功能，目前只有Graviton提供这些功能。