这个问题经常在StackOverflow上重复出现，但是我已经阅读了所有以前的相关答案，并且在这个问题上略有转折。
我有一个23Gb文件，其中包含4.75亿行相同大小的行，每行包含一个40个字符的散列码，后跟一个标识符（整数）。
我有一个传入哈希代码stream – 总计数十亿 – 每个传入的哈希代码我需要find它并打印出相应的标识符。 这项工作，虽然大，只需要做一次。
该文件太大，我不能读入内存，所以我一直在试图以下面的方式使用mmap：
codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0); 然后，我只是使用基于代码中的地址的地址算术来进行二进制search。
这似乎开始精美的工作，并在几秒钟内产生几百万个标识符，使用100％的CPU，但后来看起来随机的一些时间，它放慢了爬行。 当我使用ps查看进程时，使用100％的cpu将状态“R”更改为使用1％cpu的状态“D”（磁盘绑定）。
这是不可重复的 – 我可以在相同的数据上再次启动进程，并且在“慢速爬行”发生之前可能运行5秒或10秒。 昨天晚上，在发生这种事之前，我已经有一分钟的时间了。
一切都是只读的，我没有试图写入文件，我已经停止了所有其他进程（我控制）在机器上。 这是一个现代的红帽企业Linux 64位机器。
有谁知道为什么这个过程变成了磁盘绑定，以及如何阻止它？
更新：
感谢大家回答，并为你的想法; 我以前没有尝试过所有的各种改进，因为我想知道如果我不正确地使用mmap。 但是答案的要点似乎是，除非我能把所有东西都记在脑后，否则我将不可避免地陷入困境。 所以我把散列码的大小压缩到了不会造成任何重复的开头前缀的大小 – 前15个字符就足够了。 然后，我把结果文件存入内存，并分别以大约20亿次的批量运行哈希代码。
第一件事是分割文件。
使用散列码创建一个文件，使用整数标识创建另一个文件。 由于行是相同的，那么在找到结果之后它会排队。 您也可以尝试一种方法，将每个第n个散列放入另一个文件，然后存储索引。
例如，每1000个散列键与索引一起放入一个新文件，然后将其加载到内存中。 然后二进制扫描，而不是。 这将告诉你需要在文件中进一步扫描的1000个条目的范围。 是的，这将做得很好！ 但可能比这少得多。 就像大概每隔20个记录一样，将文件大小减少20 + – 如果我想的很好。
换句话说，在扫描之后，只需要触摸磁盘上几千字节的文件即可。
另一个选择是拆分文件并将其放在多台机器的内存中。 然后只是二进制扫描每个文件。 这将产生绝对最快的可能的搜索零磁盘访问…
你有没有考虑过盗用PATRICIA trie算法？ 在我看来，如果你可以建立你的数据文件的PATRICIA树形表示，它指的是散列和整数值的文件，那么你可能能够将每个项目减少到节点指针（2 * 64位？）， （在这种情况下是1字节）和文件偏移量（uint64_t，这可能需要对应于多个fseek（））。
有谁知道为什么这个过程变成了磁盘绑定，以及如何阻止它？
二进制搜索需要在文件中寻找很多。 在整个文件不适合内存的情况下，页面缓存不能很好地处理大的搜索，从而导致您看到的行为。
处理这个问题的最好方法是减少/阻止大的寻找并使页面缓存为你工作。
给你三个想法：
如果可以对输入流进行排序 ，则可以使用类似以下算法的方式来搜索文件：
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
当然，你需要提前知道有多少层索引。
最后， 如果你有额外的钱，你总是可以购买超过23GB的内存，并再次成为一个内存绑定的问题（我只是看着戴尔的网站 – 你拿起一个新的低端工作站32 GB的RAM不到$ 1,400澳元）。 当然，从磁盘读取大量数据需要一段时间，但是一旦存在，就会被设置。
不要使用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; }
那么就照常进行二进制搜索。 它可能会慢一点，但它不会开始咀嚼你的虚拟内存。
我们不知道后面的故事。 所以很难给你明确的建议。 你有多少内存？ 你的硬盘有多复杂？ 这是一个学习项目吗？ 谁在为你付出代价？ 32GB的RAM相比两天的工作价格不到50美元/小时。 这需要多快运行？ 你愿意走多远？ 您的解决方案是否需要使用高级操作系统概念 你嫁给了一个C程序吗？ 如何使Postgres处理这个？
这是一个低风险的选择。 这种选择不像其他建议那样具有智力上的吸引力，但有可能给你带来显着的收益。 将文件分成3个8GB的块或4个4GB的块（取决于你周围的机器，它需要适应内存）。 在每台机器上运行相同的软件，但是在内存中并在每个机器上放置一个RPC存根。 写一个RPC调用者给你的3或6个工人，以确定与给定散列码相关的整数。