在C中的大型磁盘文件上进行二进制搜索 - 问题

Question

这个问题在*上经常出现，但我已经阅读了所有以前的相关答案，并且对这个问题略有改动。

我有一个23Gb文件，其中包含4.75亿行的大小相等，每行由40个字符的哈希代码后跟一个标识符（整数）组成。

我有一个传入哈希代码流 - 总计数十亿 - 我需要找到每个传入哈希代码并打印出相应的标识符。这项工作虽然很大，但只需要进行一次。

文件太大，我读入内存，所以我一直在尝试通过以下方式来usemmap：

codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0); 

然后我使用基于地址的地址算术做一个二进制搜索码。

这似乎开始工作美丽，并在几秒钟内使用100％的cpu产生几百万个标识符，但后来一些，看似随机的时间量减缓到爬行。当我使用ps查看进程时，使用100％的cpu将状态“R”更改为使用1％cpu的状态“D”（磁盘绑定）。

这是不可重复的 - 我可以在相同的数据上再次启动进程，并且在“慢速爬行”发生之前它可能运行5秒或10秒。昨晚一次，在发生这种情况之前，我花了将近一分钟时间。

一切都是只读的，我没有试图对文件进行任何写操作，并且我已经停止了机器上的所有其他进程（我控制的）。它是一个现代化的红帽企业Linux 64位机器。

有谁知道为什么这个过程变成了磁盘绑定以及如何阻止它？

UPDATE：

感谢大家的回答，和你的想法;之前我以前没有尝试过所有的各种改进，因为我想知道我是否以某种方式错误地使用了mmap。但答案的要点似乎是，除非我能把所有东西都记在脑海中，否则我将不可避免地遇到问题。所以我将散列码的大小压缩到了不会产生任何重复的前缀前缀的大小 - 前15个字符就足够了。然后我将结果文件拖入内存，并分别以大约20亿次的批量运行传入的哈希代码。

Answer 1

要做的第一件事是分割文件。

用散列码和另一个整数ID构成一个文件。由于行是相同的，所以在找到结果后它会排队。您也可以尝试一种方法，将每个第n个散列放入另一个文件，然后存储索引。

例如，每1000个散列键放入带有索引的新文件中，然后将其加载到内存中。然后进行二进制扫描。这将告诉您需要在文件中进一步扫描的1000个条目的范围。是的，这将做得很好！但可能比这少得多。就像大概每隔20个记录一样，将文件大小减少20 + - 如果我想的很好。

换句话说，扫描后只需触摸磁盘上几千字节的文件即可。

另一种选择是拆分文件并将其放入多台机器的内存中。然后只是二进制扫描每个文件。这将产生绝对最快的可能的搜索零磁盘访问...

Answer 2

你有没有考虑黑客一个PATRICIA特里算法？在我看来，如果你可以为数据文件建立一个PATRICIA树形表示，它指向散列和整数值的文件，那么你可能能够将每个项目减少到节点指针（2 * 64位？）， （这种情况下1字节）和文件偏移量（uint64_t，它可能需要对应多个fseek（））。

Answer 3

有谁知道为什么这个过程变成磁盘绑定，以及如何阻止它？

二进制搜索需要在文件中寻找很多。在整个文件不适合内存的情况下，页面缓存不能很好地处理大的搜索，从而导致您看到的行为。

处理这个问题的最好方法是减少/阻止大的寻找并使页面缓存为你工作。你

三个想法：

如果可以排序的输入流，您可以搜索在块的文件，使用类似下面的算法：

code_block <- mmap the first N entries of the file, where N entries fit in memory 
max_code <- code_block[N - 1] 
while(input codes remain) { 
    input_code <- next input code 
    while(input_code > max_code) { 
    code_block <- mmap the next N entries of the file 
    max_code <- code_block[N - 1] 
    } 
    binary search for input code in code_block 
} 

---

如果您无法对输入流进行排序，您可以通过构建数据的内存中索引来减少您的磁盘搜索量。越过大文件，并进行了table是：

record_hash, offset into file where this record starts 

所有记录不要存放在此表 - 商店只有每第K个记录。选择一个大K，但足够小，这适合内存。

要在大文件中搜索给定的目标散列，请在内存中的表中执行二进制搜索以查找table中比目标散列小的最大散列。说这是table[h]。然后，mmap从table[h].offset开始并在table[h+1].offset结束的段，并进行最终的二分查找。这将大大减少磁盘搜索的数量。

如果这还不够，你可以有索引的多层：

record_hash, offset into index where the next index starts 

当然，你需要提前知道时间指数的多层次怎么有。

---

最后，如果你有多余的钱可你总是可以再次购买的RAM超过23 GB，并且使这个内存约束问题（我只是看着戴尔公司的网站 - 你拿起新低带32 GB内存的工作站，价格不到$ 1,400澳元）。当然，从磁盘读取大量数据需要一段时间，但一旦存在，就会被设置。

Answer 4

而不是使用mmap，可以考虑只使用普通的旧lseek + read。您可以定义一些辅助功能来读取哈希值及与其对应的整数：

void read_hash(int line, char *hashbuf) { 
    lseek64(fd, ((uint64_t)line) * line_len, SEEK_SET); 
    read(fd, hashbuf, 40); 
} 

int read_int(int line) { 
    lseek64(fd, ((uint64_t)line) * line_len + 40, SEEK_SET); 
    int ret; 
    read(fd, &ret, sizeof(int)); 
    return ret; 
} 

那么就做你的二进制搜索如常。它可能会慢一点，但它不会开始咀嚼你的虚拟内存。

Answer 5

我们不知道背后的故事。所以很难给你明确的建议。你有多少内存？你的硬盘有多复杂？这是一个学习项目吗？谁在为你的时间付钱？与价格为50美元/小时的人员的两天工作相比，32GB的RAM似乎不那么昂贵。这需要多快运行？你愿意走多远？您的解决方案需要使用高级操作系统概念吗？你嫁给了一个C程序吗？如何使Postgres处理这个问题？

这是一个低风险的选择。这种选择不像其他建议那样具有智力上的吸引力，但有可能为您带来重大收益。将文件分成3个8GB块或6个4GB块（取决于你周围的机器，它需要适合内存）。在每台机器上运行相同的软件，但在内存中并在每个机器上放置一个RPC存根。为每个3或6个工人编写一个RPC调用者，以确定与给定散列码关联的整数。