我需要将大量数据存储在大约 1k 个块中。我将以一种难以预测但可能存在模式的方式访问这些对象。
是否有一种算法或启发式方法可以根据我的访问模式重新排列磁盘上的对象，以尝试最大化顺序访问，从而最小化磁盘寻道时间？
sanity
问问题
1123 次
5 回答
5
在现代操作系统（Windows、Linux 等）上，您绝对无法优化寻道时间！原因如下：
- 你处于一个先发制人的多任务系统中。您的应用程序及其所有数据可以随时刷新到磁盘 - 用户切换任务、屏幕保护程序启动、电池电量耗尽等。
- 您不能保证该文件在磁盘上是连续的。执行 Aaron 的第一个要点并不能确保文件完整无缺。当您开始写入文件时，操作系统不知道文件将有多大，因此它可以将其放在一个小空间中，并在您向其写入更多数据时将其分段。
- 仅当文件大小小于应用程序中的可用地址范围时，内存映射文件才有效。在 Win32 上，可用的地址空间量约为 2Gb - 应用程序使用的内存。映射较大的文件通常涉及取消映射和重新映射文件的部分，这不是最好的事情。
- 将数据放在文件的中心没有任何帮助，因为据您所知，文件的中心部分可能是最碎片化的部分。
套用Raymond Chen的话说，如果您必须询问操作系统限制，您可能做错了什么。将您的文件系统视为一个不可变的黑匣子，它就是它本来的样子（我知道，您可以使用 RAID 等来提供帮助）。
您必须采取的第一步（并且必须在您进行优化时采取）是衡量您目前拥有的东西。永远不要假设任何事情。用硬数据验证一切。
从您的帖子中，听起来您实际上还没有编写任何代码，或者，如果您有，目前没有性能问题。
唯一真正的解决方案是着眼于全局并开发方法以在不停止应用程序的情况下从磁盘中获取数据。这通常是通过异步访问和推测加载。如果您的应用程序总是访问磁盘并处理数据的一小部分，您可能需要考虑重新组织数据以将所有有用的东西放在一个地方，而将其他数据放在其他地方。如果不了解完整的问题域，就不可能真正有帮助。
于 2008-12-08T11:13:02.717 回答
2
使用内存映射文件访问而不是通常的 open-seek-read/write 模式。该技术适用于 Windows 和 Unix 平台。
这样，操作系统的虚拟内存系统将为您处理缓存。访问已经在内存中的块将不会导致磁盘寻道或读取时间。从内存回写到磁盘会被自动且高效地处理，并且不会阻塞您的应用程序。
Aaron 的笔记也很好，因为它们会影响不在内存中的块的初始加载时间。将其与内存映射技术相结合——毕竟使用重新排序块memcpy()比从磁盘读取/写入和尝试交换等更容易。
于 2008-12-05T15:12:41.423 回答
1
解决这个问题的最简单方法是使用一个操作系统，它可以在后台为你解决这个问题，比如 Linux。给它足够的 RAM 以在 RAM 中保存 10% 的对象，它会尝试将尽可能多的对象保留在缓存中，将加载时间减少到 0。Windows 的最新服务器版本也可能工作（其中一些没有'不适合我，这就是我提到这个的原因）。
如果这是不行的，试试这个算法：
在硬盘上创建一个非常大的文件。一口气写完这个非常重要，这样操作系统就会在磁盘上分配一个连续的空间。
将所有对象写入该文件。确保每个对象的大小相同（或在文件中给每个对象相同的空间，并注意每个块的前几个字节的长度）。使用空硬盘或刚刚进行碎片整理的磁盘。
在数据结构中，保留每个数据块的偏移量以及访问频率。当它被频繁访问时，将其在文件中的位置与更接近文件开头且访问次数较少的块交换。
[编辑] 使用操作系统的内存映射 API 访问此文件，以允许操作系统有效缓存最常用的部分以获得最佳性能，直到您下次可以优化文件布局。
随着时间的推移，频繁访问的块将冒泡到顶部。请注意，您可以在一段时间内收集访问模式，分析它们并在您的机器上几乎没有负载的情况下在夜间重新排序。或者您可以在完全不同的机器上进行重新排序，并在完成后交换文件（和偏移表）。
也就是说，你真的应该依赖一个现代操作系统，许多聪明人一直在努力为你解决这些问题。
于 2008-12-05T15:08:00.340 回答
-1
这是一个有趣的挑战。不幸的是，我也不知道如何开箱即用地解决这个问题。Corbin 的方法对我来说听起来很合理。
至少这里有一点优化建议：将最常访问的项目放在磁盘（或未碎片化文件）的中心，而不是放在末尾。这样，平均而言，寻求较少使用的数据将更接近。呃，不过，这很明显。
如果您自己找到解决方案，请告诉我们。
于 2008-12-08T09:54:11.877 回答