在大内存映射文件中搜索

Question

我有一个大型数据结构存储在内存映射文件中.数据结构非常简单:

struct Header {
    ...some metadata...
    uint32_t index_size;
    uint64_t index[]
};

这个头部放在文件的开头,它使用了一个结构hack - 可变大小的结构,最后一个元素的大小不是一成不变的,可以改变.

char* mmaped_region = ...;  // This memory comes from memory mapped file!
Header* pheader = reinterpret_cast<Header*>(mmaped_region);

内存映射区域以HeaderHeader :: index_size 开头,Header :: index_size包含Header :: index数组的正确长度.这个数组包含数据元素的偏移量,我们可以这样做:

uint64_t offset = pheader->index[x];
DataItem* item = reinterpret_cast<DataItem*>(mmaped_region + offset);
// At this point, variable item contains pointer to data element
// if variable x contains correct index value (less than pheader->index_size)

对所有数据元素进行排序(少于为数据元素定义的关系).它们存储在与Header相同的内存映射区域中,但从结尾开始.数据元素无法移动,因为它们的大小可变,而不是 - 在排序过程中会移动标题中的索引.这与现代数据库中的B-tree页面非常相似,索引数组通常称为间接向量.

搜索

使用插值搜索算法(具有有限的步骤量)并且使用二进制搜索来搜索该数据结构.首先,我有一个完整的index数组要搜索,我正在尝试计算 - 如果分布是统一的,搜索元素可以存储在哪里.我得到一些计算索引 - 看看这个索引处的元素,它通常不匹配.比我缩小搜索范围并重复.插值搜索步骤的数量受一些小数量的限制.之后,使用二进制搜索搜索数据结构.这对于小数据集非常有用,因为分布通常是一致的.几乎没有插值搜索的迭代,我们就完成了.

问题定义. 实际上,存储器映射区域可能非常大.为了测试,我使用32Gb文件支持的存储并搜索一些随机密钥.这非常慢,因为这种模式会导致大量随机磁盘读取(所有数据都无法缓存在内存中).

这可以做什么？我认为用madvisesyscall 设置MADV_RANDOM 可能有所帮助,但可能不是很多.我希望与B树搜索速度相提并论.也许有可能使用mincore系统调用来检查在插值搜索期间可以轻松检查哪些数据元素？也许我可以使用某种预取？

Answer 1

插值搜索似乎是一个好主意.它通常有一个小的好处,但在这种情况下,即使少量的迭代保存也有很大帮助,因为它们很慢(磁盘I/O).

但是,真实数据库会复制其索引中的实际键值.在性能改进方面,空间开销完全合理.Btree是一个进一步的改进,因为它们在一个连续的内存块中打包多个相关节点,进一步减少了磁盘搜索.

对您而言,这可能是正确的解决方案.您应该复制密钥以避免磁盘I/O. 如果您无法更改现有标头,则可以通过在单独的结构中复制密钥并将其完全保留在内存中来逃避.

折衷是可能的,您只需缓存前N级二进制搜索的顶部(2 ^ N)-1键.这意味着你必须放弃对搜索部分进行插值,但正如前所述,插值并不是一个巨大的胜利.磁盘搜索保存将很容易得到回报.即使只缓存中值键(N = 1)也会为每个查找节省一次磁盘搜索.一旦用完了缓存,你仍然可以使用插值.

相比之下,任何调整内存映射参数的尝试都可以让您最多提高速度."与B树相提并论" 不会发生.如果你的算法需要那些物理搜索,你就输了.没有神奇的小精灵粉尘会修复糟糕的算法或糟糕的数据结构.