4

我需要读取一组文件并将其分解为键值对，并将它们保存为磁盘上该键的（键，值列表），就像 map-reduce 范例一样。一切都在一台计算机上。例如，我可以在不同的文件上编写不同的列表并用密钥命名文件。这似乎是一种非常糟糕的做事方式。首先，如果你有十亿个密钥，你最终会得到十亿个文件。所以很明显那是行不通的，我需要某种内存映射。我还必须让不同的线程来完成映射工作，所以如果它们要写入同一个缓冲区，它们之间就必须进行某种同步。如果我有一个键值缓冲区映射，并在缓冲区上同步，那么线程不应该互相踩踏，所以我认为这部分应该可以工作。问题是如何将值映射到光盘。如何在同一个文件中写入对应于不同键的缓冲区？如果有人能指出我正确的方向，将不胜感激。我对这方面的了解非常可悲。再次感谢。

4

4 回答 4

6

正如 Lirik 建议的那样，从实际的角度来看，使用 BerkeleyDB 很容易做到这一点。

如果您对理论比对实践更感兴趣，我建议您将其视为“外部排序”操作。也就是说，将尽可能多的输入读入内存，然后按键排序。将已排序的块写为单个文件。然后可以轻松地将排序的文件合并到一个文件中。

在其他应用程序中，这是 Lucene 用来构建“倒排索引”以搜索文本的方法。“键”是文档中的单词，“值”是出现该单词的文档列表。Lucene 读取文档，并为每个单词在内存中创建一个术语到文档的条目。当内存已满时，它将索引段写入磁盘。当磁盘上有很多索引段时，将它们合并为一个段。事实上，您也可以根据您的任务调整 Lucene 的索引编写器。

可以将工作划分为多个线程。但是，您必须对磁盘争用敏感。跳过同时读取和写入许多文件会大大降低传统驱动器的速度。可能有机会同时安排一些活动。当您将前一个已排序的块写入磁盘时，您可能会从一个文件中读取新数据，尤其是在机器有两个磁盘驱动器的情况下。当然，使用 SSD 临时存储一些已排序的段会很有帮助。

于 2011-08-03T20:08:06.940 回答
4

我认为Oracle 的 Berkeley DB可能正适合您：

伯克利数据库

Berkeley DB 旨在将数据存储为键/值对中的不透明字节数据数组，该键/值对以可用访问方法之一为索引，如上所示。

Berkeley 非常健壮、成熟且快速，但如果您想采用更轻量级的方法，请使用SQLite。

另一种选择是使用 Google 的 LevelDB；它是用 C++ 编写的，但它周围有Java 包装器。LevelDB 速度快得令人麻木，而且非常轻量级！

如果没有关于您的项目的更多详细信息，我只能说：

  • 使用所有这些解决方案，键/值对将存储在同一个文件中（如有必要，多个实例可以存储到单独的文件中，但我不明白为什么会这样）。
  • BerkeleyDB 和 LevelDB 具有非常好的缓存和映射能力。
  • BDB 和 LDB 也允许压缩（不确定 SQLite 是否也可以）。
  • 根据您的密钥分布（例如，如果您使用像 Google 的CityHash这样的良好散列函数），您可能会获得非常好的数据局部性，从而减少表扫描。
  • 您可能应该编写自己的线程安全缓冲区，并且应该避免让多个线程写入 BDB/LDB，因为这些解决方案是基于磁盘的，并且您通常不想要多线程磁盘 I/O 操作。

批评：-我不确定您所说的“键值缓冲区映射”是什么意思……您是否将缓冲区映射到每个键？你为什么需要那个？

于 2011-08-03T19:23:30.173 回答
1

Chronicle Map应该是解决这个问题的好方法。

一般来说，它在操作速度和消耗内存方面都非常有效，即它比之前建议的 BerkeleyDB快得多。

Chronicle Map 是一种分段存储，允许并行处理分段，例如。G：

for (int i = 0; i < chronicleMap.segments(); i++) {
  int segmentIndex = i;
  executor.submit(() -> {
    chronicleMap.segmentContext(segmentIndex).forEachSegmentEntry(entry -> {
      // do processing with entry.key() and entry.value(),
      // value() could be a List or some Iterator-like abstraction
    });
  });
}

请参阅MapSegmentContextJavadocs。

但是，使用 Chronicle Map 并不总是有效地处理每个键（逻辑上）多个值。但是在您的情况下，如果您只需要处理每个键的静态值集，而不是添加/删除值，那么它可以很好地工作。

于 2017-03-18T23:20:09.163 回答
0

你看过使用Hadoop吗？

于 2011-08-04T20:05:51.507 回答