使用辅助存储器的低RAM空间、高吞吐量的持久键值存储

摘要

本发明涉及使用辅助存储器的低RAM空间、高吞吐量的持久键值存储。所描述地是使用闪存(或其他辅助存储)、基于RAM的数据结构和机制，仅用低的RAM空间占用量来访问存储在该闪存中的键值对。映射(例如，散列)函数将键值对映射至基于RAM的索引中的槽。槽包括指向闪存上各记录的桶的指针，这些记录各自都具有映射至该槽的键。例如用从最新近写入记录到最早写入记录的各指针来将各记录的桶安排成经线性链接的链表。还描述了将桶中的非连续记录压缩在单个闪存页面上，以及无用信息收集。另外描述了可减少桶大小的变化的负载平衡，该负载平衡使用每槽一个布隆过滤器来避免不必要的搜索，并且描述了将槽拆分成子槽。

主权项

一种计算环境中的系统，该系统包括维护在主存储(102)中的索引(108)以及映射机制(110)，所述索引(108)用于索引辅助存储(104)中持久存储的数据，所述映射机制(110)用于将记录的键映射至基于该键的索引的槽，在所述映射机制(110)中存在比槽更多的可能键，所述索引中的每一槽都被配置来维护指向所述辅助存储(104)中的一个或多个记录的相应链表的指针，在所述辅助存储(104)中该槽的相应链表中的每一记录都具有映射至该槽的键，并且在存在任何在先记录时，链表中的每一记录与该链表中的在先记录相链接；还包括用于基于所述记录的键来向所述辅助存储添加输入记录的插入操作，所述插入操作被配置来：确定所述输入记录的键所映射至的槽；将维护在所述槽中的在先指针与要写入到辅助存储中的所述输入记录相关联，以将所述输入记录链接至所述在先指针所指向的在先记录；以及，将所述在先指针改变成新指针，该新指针指向所述输入记录写入到所述辅助存储中的位置。