区块链数据库。

ParityDb 是一个针对区块链应用的嵌入型持久化键值存储，进行了优化。

设计考虑

• 数据库旨在高效存储编码到Patricia-Merkle trie中的区块链状态。这意味着大多数键的大小固定且均匀分布。大多数值都很小。超过16 kbytes的值很少。Trie节点可能被多个Trie和/或分支共享，因此需要引用计数。
• 读取性能比写入性能对区块链交易吞吐量更重要。写入通常在导入新块时以大批次进行。在区块链客户端空闲或执行块之间通常会有一些时间间隔。

无缓存

API

数据库是一个支持事务的通用键值存储。API 允许将数据分区为列。建议每个列包含与单一数据类型对应的条目。例如，状态Trie节点、区块头部、区块链交易等。支持两种类型的列索引：哈希和B树。

事务

数据库支持多个并发读取者。所有写入都是序列化的。写入以批次形式执行，也称为事务。事务原子性地应用。要么全部写入事务数据，要么全部不写。查询不能检索部分提交的数据。

数据库不实现任何自定义数据缓存。相反，它依赖于操作系统页面缓存。因此，大型数据库的性能取决于可用于操作系统页面缓存的系统内存量。

持久性

如果在任何点上中断I/O，数据库将恢复到一致状态。请注意，此状态可能不是中断前的最新状态。由后台线程提交但尚未保存到磁盘的写入将丢失。

实现细节

数据结构

每个列将数据存储在一组256个值表中，其中255个表包含大小范围为32kbytes的条目。最后一个256个值表的大小存储超过32k的条目，这些条目被分成多个部分。哈希列还包括一个哈希索引文件。

元数据

元数据文件包含数据库定义。这包括一组列，并为每个列指定了配置。

哈希索引

哈希索引是一个基于mmap的动态大小探测哈希表。对于每个键，索引计算一个均匀分布的256位哈希值'k'。对于大小为n的索引，k的前n位映射到512字节的索引页面。每个页面是无序的64个8字节条目的列表。每个8字节条目包含一个值地址和一些额外的k位。一个空条目用零值表示。一个空数据库从n = 16开始。值地址包括一个8位值表索引和该表中条目的索引。每个索引文件的前16kbytes用于存储列的统计数据。

值表

值表是一个可按需增长的固定大小条目的线性数组。每个条目可能包含以下之一

• 填充条目，包含240位k，15位数据值大小，压缩标志，可选引用计数器和实际值。
• 墓碑条目。这包含一个先前墓碑的索引，形成一个空条目的链接列表。
• 多部分条目。这与填充类似，此外还包含一个指向下一个包含数据续集的条目的地址。

哈希索引操作

哈希索引查找

计算k，使用前n位找到索引页面。搜索具有匹配键位的匹配条目。使用条目中的地址从值表中查询部分k和值。确认k与预期值匹配。

哈希索引插入

如果尝试将条目插入到满索引页面，则触发重新索引。当加载因子达到约0.52时，64个索引条目的页面大小触发一次重新索引。

重新索引

当无法解决冲突时，会创建一个新的索引表，其容量是原来的两倍。立即继续将条目插入新表。启动一个后台进程，将条目从旧表移动到新表。在此过程中，所有查询都检查两个表。

BTree索引操作。

待办事项

事务管道

在commit时，所有数据都移动到内存覆盖中，使其可用于查询。然后，这些数据被添加到提交队列中。这允许commit函数尽可能早地返回。提交队列由提交工作者处理，该工作者收集将修改索引或值表的条目，并将其作为一系列命令写入二进制日志文件。所有修改的索引和值表页面都放置在内存覆盖中。然后，文件由另一个后台线程处理，将其刷新到磁盘并添加到最终化队列。最后，另一个线程处理最终化队列。它读取二进制日志文件并应用所有更改到表中，清除页面覆盖。

启动时，如果存在任何日志文件，它们将被验证是否损坏，并在表上执行操作。

许可证

ParityDb 主要根据 MIT 许可证和 Apache 许可证（版本 2.0）的条款进行分发，您可选择其中之一。

有关详细信息，请参阅 LICENSE-APACHE 和 LICENSE-MIT。

贡献

除非您明确声明，否则您有意提交以供 ParityDb 包含的贡献，根据 Apache 2.0 许可证定义，应按上述方式双重许可，不附加任何额外条款或条件。