6

这个问题在 StackOverflow 上经常出现，但是我已经阅读了之前所有的相关答案，并且对这个问题有轻微的扭曲。

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

我有一个传入的哈希码流——总共有数十亿个——对于每个传入的哈希码，我需要找到它并打印出相应的标识符。这项工作虽然很大，但只需要完成一次。

该文件太大，我无法读入内存，因此我一直在尝试通过以下方式使用 mmap：

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

然后我只是根据代码中的地址使用地址算法进行二进制搜索。

这似乎开始工作得很好，并在几秒钟内产生了几百万个标识符，使用了 100% 的 cpu，但是在经过一些看似随机的时间后，它会减速到爬行。当我使用 ps 查看进程时，它已从使用 100% 的 cpu 的状态“R”变为使用 1% 的 cpu 的状态“D”（磁盘绑定）。

这是不可重复的——我可以在相同的数据上再次启动该过程，并且它可能会在“爬行缓慢”发生之前运行 5 秒或 10 秒。昨晚有一次，在这件事发生之前我花了将近一分钟的时间。

一切都是只读的，我没有尝试对文件进行任何写入，并且我已经停止了机器上的所有其他进程（我控制的）。它是现代 Red Hat Enterprise Linux 64 位机器。

有谁知道为什么该进程成为磁盘绑定以及如何停止它？

更新：

感谢大家的回答和您的想法；我以前没有尝试过所有各种改进，因为我想知道我是否以某种方式错误地使用了 mmap。但答案的要点似乎是，除非我能将所有内容都挤进内存，否则我将不可避免地遇到问题。所以我将散列码的大小压缩到不产生任何重复的前导前缀的大小——前 15 个字符就足够了。然后我将生成的文件拉入内存，并以大约 20 亿个批次运行传入的哈希码。

4

5 回答 5

3

首先要做的是拆分文件。

用哈希码制作一个文件，用整数 id 制作另一个文件。由于行相同，因此在找到结果后它将很好地排列。您也可以尝试将每个第 n 个哈希放入另一个文件然后存储索引的方法。

例如，每 1000 个哈希键放入一个带有索引的新文件，然后将其加载到内存中。然后二进制扫描它。这将告诉您需要在文件中进一步扫描的 1000 个条目的范围。是的，那会做得很好！但可能远不止于此。可能每 20 条左右的记录就会将该文件大小除以 20 +- 如果我想得好的话。

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

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

于 2013-02-14T02:45:33.517 回答
2

您是否考虑过破解 PATRICIA trie 算法？在我看来，如果您可以构建数据文件的 PATRICIA 树表示，它指的是哈希和整数值的文件，那么您可能能够将每个项目减少为节点指针（2 * 64 位？），位测试偏移量（在这种情况下为 1 个字节）和文件偏移量（uint64_t，可能需要对应多个 fseek()s）。

于 2013-02-14T04:15:06.100 回答
2

有谁知道为什么该进程成为磁盘绑定以及如何停止它？

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

处理这个问题的最好方法是减少/防止大搜索并使页面缓存为您工作。

给你三个想法：

如果您可以对输入流进行排序，则可以使用类似于以下算法的方法分块搜索文件：

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

不要将所有记录存储在此表中 - 仅存储每个 Kth 记录。选择一个大的 K，但要足够小以适应内存。

要在大文件中搜索给定的目标哈希，请在内存表中进行二进制搜索，以找到table小于目标哈希的最大哈希。说这是table[h]。然后，对从 开始table[h].offset和结束的段进行 mmap table[h+1].offset，并进行最终的二进制搜索。这将大大减少磁盘寻道次数。

如果这还不够，您可以拥有多层索引：

 record_hash, offset into index where the next index starts

当然，您需要提前知道有多少层索引。

最后，如果您有多余的钱可用，您总是可以购买超过 23 GB 的 RAM，这又是一个内存限制问题（我刚刚查看了戴尔的网站 - 您购买了一个具有 32 GB RAM 的新低端工作站不到 1,400 澳元）。当然，从磁盘中读取这么多数据需要一段时间，但是一旦它在那里，你就会被设置。

于 2013-02-14T04:32:38.187 回答
1

不要使用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;
}

然后像往常一样进行二进制搜索。它可能会慢一点，但它不会开始占用您的虚拟内存。

于 2013-02-14T04:59:22.210 回答
1

我们不知道背后的故事。所以很难给你明确的建议。你有多少内存？你的硬盘有多复杂？这是一个学习项目吗？谁为你的时间买单？与每小时 50 美元的两天工作相比，32GB 的内存似乎并不昂贵。这需要运行多快？你愿意走出多远？您的解决方案是否需要使用高级操作系统概念？你嫁给了 C 语言的程序吗？让 Postgres 处理这个怎么样？

这是一个低风险的替代方案。此选项在智力上不像其他建议那样吸引人，但有可能为您带来显着收益。将文件分成 3 个 8GB 块或 6 个 4GB 块（取决于您周围的机器，它需要舒适地放入内存中）。在每台机器上运行相同的软件，但在内存中并在每个机器周围放置一个 RPC 存根。为 3 或 6 个工作人员中的每个工作人员编写一个 RPC 调用程序，以确定与给定哈希码关联的整数。

于 2013-02-14T06:28:39.507 回答