区块链数据库。

设计考虑因素

API

数据库是一个支持事务的通用键值存储。它不支持迭代或基于前缀的检索。

状态优化

90% 的区块链数据和 IO 是 trie 节点。数据库应首先允许高效存储和检索状态数据。

单写者

数据库应能够支持多个并发读取者。允许单个并发写者就足够了。

无缓存

低级别 LRU 缓存区块链数据（如单个 trie 节点）已被证明效率低下。应在更高层次上完成缓存。即存储项或区块标题。

事务隔离

事务是原子应用的。查询不能检索部分提交的数据。

持久性

如果在任何点上 IO 被中断，数据库应恢复到一致状态。

实现

数据结构

数据组织到列中。每列服务于特定类型的数据，例如状态或标题。列由索引和一组 16 个用于不同值大小的值表组成。

索引

索引是一个基于 mmap 的动态大小探测哈希表。每个条目是一个包含 64 个 8 字节条目的页面，总共 512 字节。每个 64 位条目包含 32 位值地址、4 位值表索引和 28 位从 k 推导出的 c 值。 c 是通过跳过 n 个高位 k 并取下一个 28 位来计算的。 k 是从原始键推导出的 256 位键，并且是均匀分布的。 n 是当前索引位大小。数据库开始时 n = 16，这允许将 240 位的 k 放入值表中。

值表

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

• 填充条目，包含240位k，16位数据值大小和实际值
• 墓碑条目。这包含一个指向前一个墓碑的索引，形成可用条目的链表。
• 多部分条目。这与填充类似，另外还持有下一个条目的地址，该条目包含数据的延续。

只有16个值表中的15个允许值达到条目大小。一个额外的表，条目大小为8kb，专门用于大值，并允许多部分条目。

操作

查找

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

插入

如果尝试将条目插入到满的索引页面，则触发重新索引。64个索引条目的页面大小在负载因子达到约50%时触发重新索引。

重新索引

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

事务流水线

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

启动时，如果存在日志文件，则对其进行验证并应用于表。

潜在问题

• 一旦索引增长到2GB，内存映射I/O将无法支持32位系统。
• 大小放大。索引增长到大约50%的容量后，才会触发重新平衡。这意味着大约50%的分配空间实际上用于占用的索引条目。此外，每个值表条目只部分填充了实际数据。