Scala中的磁盘持久化延迟缓存列表 ™

Question

Scala中的磁盘持久化延迟缓存列表 ™

scaladata-structuresdata-stream

15

我需要在Scala中拥有一个非常非常长的(X,Y)对列表。它非常大，无法放入内存（但可以很好地放在磁盘上）。

所有更新操作都是cons（头部追加）。
所有读取访问都从头部开始，并有序地遍历列表，直到找到预定的一对。
缓存会很棒，因为大多数读取访问将一遍又一遍地保留相同的数据。

因此，这基本上是一个“磁盘持久化的惰性可缓存列表”™

在我开始自己编写之前，您有什么想法如何获得一个？

附加说明：是的，MongoDB或任何其他不可嵌入资源都是过度杀伤力的。如果您对此有特定用例感兴趣，请参见类Timeline 这里。基本上，我希望拥有一个非常非常大的时间轴（数百万个月内的配对），尽管我的匹配只需要涉及最近几个小时。

- Hugo Sereno Ferreira

3

如果您最终选择自行开发，您可能需要实现基于页面的内容。头部附加的要求使事情变得有趣，因为文件是可追加的，但只能在末尾追加，并且您可能不想读取整个文件以读取最新的值。 - Chris Shain

2

所以为了明确起见，您正在寻找基于Scala的解决方案，而不是基于操作系统的解决方案？处理磁盘和内存之间的页面和交换通常被视为操作系统服务。 - Dan Burton

所有读取访问都从头开始，一个非常非常长的成对列表...你确定要O(n)查找吗？ - Nicholas White

@Chris Shain：该文件应以相反的顺序存储列表，因此将前缀添加到列表即将其附加到文件中。 - Nicholas White

我不需要对集合进行随机访问，因此我期望能够在O(1)时间内访问头部，并在前n个元素中以O(n)的时间访问。 - Hugo Sereno Ferreira

显示剩余4条评论

4个回答

4

你写道：

mongodb，或者其他不可嵌入的资源，都是过度杀伤力

你知道吗，有些可嵌入的数据库引擎非常小巧？如果你知道，我不确定你的确切需求和为什么不使用它们。

你确定Hibernate +一个可嵌入的DB（比如SQLite）不够用吗？另外，BerkeleyDB Java Edition，HSQLDB，或其他嵌入式数据库也是一种选择。

如果您不对对象本身执行查询（并且确实听起来您不这样做），也许序列化比复杂对象的对象关系映射更简单，但我从未尝试过，也不知道哪个更快。但是，在类型上完全通用的情况下，序列化可能是唯一的方法，假设您选择的框架提供了适当的接口来编写。如果没有，您可以在创建自己的“类型类”MySerializable[T]（例如Scala标准库中的Ordering[T]）之后编写。

然而，您不想为此任务使用标准Java序列化。“任何可序列化的东西”听起来是一个糟糕的要求，因为它建议使用序列化，但我猜您可以放松到“使用我选择的框架可序列化的任何东西”。序列化在时间和空间上极其低效，而且不是设计用于序列化单个对象，而是返回带有特殊头文件的完整文件。我建议使用一些不同的序列化框架-在这里查看比较。

定制实现的其他原因不去采取这条路。

此外，似乎您将基本上倒序读取文件，这是一种相当糟糕的访问模式，对非固态硬盘的性能来说如此：在读取一个扇区后，需要几乎完整的磁盘旋转才能访问前一个扇区。此外，正如Chris Shain在上面的评论中指出的那样，您需要使用基于页面的解决方案，并且需要处理可变大小的对象。

- Blaisorblade

3

这些Java库可能包含您所需的内容。它们旨在比标准Java集合更有效地存储条目。

github.com/OpenHFT/Chronicle-Queue
github.com/OpenHFT/Chronicle-Map

- Rich

2

快进5年，这个项目现在已经在https://github.com/OpenHFT/Chronicle-Queue和https://github.com/OpenHFT/Chronicle-Map中开发。 - leventov

感谢您添加评论。有趣的是，我的当前项目使用ChronicleMap来存储数据的MD5摘要以检测重复项！ - Rich

@leventov 快进5年，这似乎是对这个问题最好的答案。你想把它推荐上去，让我接受吗？ :) - Hugo Sereno Ferreira

3

如果您不想使用可嵌入的数据库之一，那么考虑使用内存映射文件堆栈呢？

栈似乎符合您所需的访问特征。（将一堆数据推入并经常迭代最近推入的数据）
您可以直接从Scala使用Java的MappedByteBuffer。您可以像处理内存一样处理文件，而无需尝试将文件实际加载到内存中。
这种方式会从操作系统中免费获得一些缓存，因为映射的文件将像虚拟内存一样运行。最近写入/访问的页面将保留在操作系统的文件缓存中，直到操作系统决定将它们刷新回磁盘（或您手动刷新它们）。
如果您担心顺序读取性能，可以从文件的任一端构建堆栈，但是如果通常读取您刚刚写入的数据，则不认为这将是一个问题，因为它仍将在内存中。（但是，如果您跨页面写入数小时/天的数据然后读取数据，则可能会出现问题）
以这种方式寻址的文件在64位JVM上的大小限制为2GB，但是您可以使用多个文件来克服此限制。

- framed

1

缓存点很好，我也考虑过，但是我没有想出如何以高效的方式将对象数组转换为字节数组。与C语言不同，你不能轻松地使用内存映射文件作为堆，因为你仍然需要实现一个内存分配器。即使在C语言中，这也并不是那么简单的事情。 - Blaisorblade

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel C. Sobral · Accepted Answer

做这样的事情最简单的方法是扩展 Traversable 。您只需要定义 foreach ，并完全控制遍历，因此可以执行打开和关闭文件等操作。

您还可以扩展 Iterable ，它需要定义 iterator ，并且当然要返回某种类型的 Iterator 。在这种情况下，您可能会为磁盘数据创建一个 Iterator ，但是要控制像打开文件这样的事情就会更加困难。

以下是由Josh Suereth编写的 Traversable 示例：

class FileLinesTraversable(file: java.io.File) extends Traversable[String] {
  override def foreach[U](f: String => U): Unit = {
     val in = new java.io.BufferedReader(new java.io.FileReader(file))
     try {
       def loop(): Unit = in.readLine match {
          case null => ()
          case line => f(line); loop()
       }
       loop()
     } finally {
       in.close()
     }
  }
}