优化算法与快速磁盘存储(SSD)的结合？

Question

考虑到固态硬盘（SSD）的价格正在降低，很快将成为系统驱动器的主流，并且考虑到它们的访问速率显著高于旋转磁介质，那么使用SSD进行本地存储会提高哪些标准算法的性能呢？例如，SSD的高随机读取速度使得基于磁盘的哈希表对于大型哈希表来说是可行的；4GB的磁盘空间是readily available的，这使得哈希到32位整数范围内变得可行（更适合于查找而不是填充，尽管填充仍需要很长时间）；而这样的哈希表大小在使用旋转介质时将因访问速度过慢而难以处理，但在SSDs上却不应该是一个问题。

除了哈希表之外，未来转向SSD是否还有其他潜在的算法性能提升领域呢？我更愿意看到关于如何工作的推理而非观点，我不希望这变得有争议。

- Paul Sonier

Answer 1

您提到的哈希表确实是一种重要的数据库结构，它可以获取SSD直接探测值而不必将整个4GB或更大的文件加载到内存中。虽然SSD仍比RAM慢很多倍，但在磁盘上拥有50GB的哈希表是相当合理的，除非您为大型机器支付大笔费用，否则它不会在RAM中。

象棋位置数据库就是一个例子。我有超过50GB的哈希位置。有复杂的代码来尝试在哈希表中将相关位置组合在一起，这样我每次只需分页10MB的表格并希望能够将其用于多个类似的位置查询。需要大量的代码和复杂性来使这个过程变得高效。

使用SSD后，我能够放弃所有聚类的复杂性，只需要使用真正愚蠢的随机哈希。我也得到了性能的提升，因为我只从磁盘中获取我需要的数据，而不是10MB的大块。虽然延迟确实较大，但净加速效果显著。而且这份超级干净的代码（20行而不是800多行）可能更好。

- SPWorley

---

很棒的例子，说得好；我没有想过国际象棋的位置，但这是一个非常有趣的案例。 - Paul Sonier

Answer 2

SSD只在随机访问方面显著快速。对于磁盘的顺序访问，它们只比主流转动驱动器快两倍。许多SSD在许多场景中性能较差，导致它们表现更差，如这里所述。

虽然SSD的性能有很大提升，但它们仍然比CPU操作和物理内存慢得多。以4GB哈希表为例，您可以通过SSD维持250+ MB/s的速度来访问随机哈希表桶。使用转动驱动器，您最好也只能达到一位数MB/s的速度。如果您可以将这个4 GB哈希表保留在内存中，您可以每秒访问几个GB - 比即使是非常迅速的SSD还要快得多。

引用的文章列出了微软在Windows 7上运行时针对SSD所做的几个更改，这可以为您提供您可以考虑进行的更改类型的想法。首先，关闭了超级预取数据硬盘缓存（SuperFetch）-它旨在解决SSD缓解的慢的随机访问时间。关闭了碎片整理，因为文件分散在磁盘上对SSD不会产生性能影响。

- Michael

---

你更多地谈论SSD的优化；我更考虑由SSD性能实现（或更可行）的算法类型。我对可能（或必要）的优化不太感兴趣，而是对那些在较慢的持久存储中根本不可能的不同类型的算法或应用程序更感兴趣。 - Paul Sonier

Answer 3

因此，任何需要大量随机磁盘I/O的算法（关键词是“随机”），都会导致局部性原理无效，从而消除了许多缓存的有用性。

不过，我能看出某些数据库系统会从中受益。例如，使用MyISAM存储引擎的MySQL（其中数据记录基本上是CSV格式）。但是，我认为非常大的哈希表将是您获得良好实例的最佳选择。

- Chris Tonkinson

---

实际上，算法本身并不使用磁盘，关键是：使用SSD的性能提升可以启用哪些标准算法？这有点类似于管理代码是由特定速度和尺寸的计算机启用的... - Paul Sonier

算法本身并不使用磁盘 - 算法的实现会使用磁盘 - 在这一点上我们可以达成共识。是的，托管代码得益于硬件改进 - 但需要多个数量级的“更好”的计算机硬件才能实现。HDD和SSD之间的跳跃并不是（请原谅表达方式）数量级的巨大变化。唯一可靠的好处是随机访问。回到我的最初回答：“...这需要大量的随机磁盘I/O...” - Chris Tonkinson

Answer 4

SSD在随机读取方面要快得多，顺序读取略快，但写入速度（无论是随机还是非随机）则会慢一些。

因此，在SSD上使用基于磁盘的哈希表可能不太实用，因为现在更新它需要显著的时间，但与普通硬盘相比，搜索磁盘变得非常便宜。

- tomjen

---

请注意，在原问题中，我提到散列表比种群对于查找更加可行，正是因为这个原因。考虑一个“预填充”的散列表的概念，它随软件一起发货，以允许哈希查找的预定义；对于现代应用程序来说，4GB的安装空间非常合理。 - Paul Sonier

Answer 5

别自欺欺人了。SSD 相对于系统内存仍然慢得多。任何选择使用系统内存而非硬盘的算法，在其他条件相同的情况下，速度都会更快。

- Kenan Banks

---

重点是，并非所有其他事物都是相等的。具体来说，例如，4GB的SSD空间相对容易找到；而4GB易于寻址的系统内存则更难找到。 - Paul Sonier

@Michael：是的，这是一个好观点，但通常RAM很宝贵；持久存储则不然。 - Paul Sonier

@McWafflestix - 我的说法有误，每GB内存的价格仍然比较昂贵。但是4 GB的内存比一个性能良好的固态硬盘便宜。 - Michael

@Michael：是的，这是一个很好的观点；但是，请考虑用户应用程序想要使用大型预计算哈希表的情况。在安装时，您可能可以期望有4GB的存储空间，并且在不久的将来，您可能可以期望它是固态的；我不知道期望用户有额外的4GB RAM来放置您的哈希表是否可行。我同意，对于服务器类型的用途，通常更容易添加更多的RAM；但请考虑Arno Setagaya上面提到的50GB哈希表的观点。 - Paul Sonier

@McWafflestix - 这让我感觉我们正在试图通过创建对旋转介质而言是病态的场景来强制使用SSD有益。一个必须具有50 MB/s以上读取带宽才能受益于SSD的50GB哈希表 - 但仅仅因为我们选择了对机械硬盘来说最糟糕的数据存储。如果数据可以重新组织成B树状布局，或者我们将索引分离并将它们保留在内存中，在内存中缓存大块表格等，我们仍然可以实现不错的性能。 - Michael