External-Memory Dictionaries in the Affine and PDAM Models
External-Memory Dictionaries in the Affine and PDAM Models
复制标题
Affine 和 PDAM 模型中的外部存储器字典
DOI：
10.1145/3323165.3323210
复制
发表时间：
2021
影响因子：
1.6
通讯作者：
Pandey, Prashant
中科院分区：
文献类型：
--
作者：
Bender, Michael;Conway, Alex;Farach-Colton, Martin;Jannen, William;Jiao, Yizheng;Johnson, Rob;Knorr, Eric;McAllister, Sara;Mukherjee, Nirjhar;Pandey, Prashant
存储设备具有复杂的性能配置文件，包括启动IO的成本（例如，硬盘驱动器中的寻道时间）、并行性和存储体冲突（SSD中）、传输数据的成本以及固件内部操作。数据访问机（DAM）模型通过假设存储设备以大小为B的块传输数据并且所有传输都具有单位成本来简化现实。尽管它的简化，DAM模型是相当准确的。事实上，如果将B设置为半带宽点（此时硬件的延迟和带宽相等），则DAM会将任何硬件上的IO成本近似为2倍。此外，DAM解释了70年代B树的流行以及B树和日志结构合并树当前的流行。但它无法解释为什么有些B树使用小节点，而所有B树都使用大节点。在DAM中，所有IO以及所有节点都是相同的大小。在本文中，我们证明了仿射和PDAM模型，这是DAM模型的小改进，在不牺牲易用性的情况下，在可预测性方面产生了令人惊讶的巨大改善。我们提出了一个大型的存储设备的集合上的基准测试表明，仿射和PDAM模型给出了很好的近似的硬盘驱动器和SSD的性能特性，分别。我们表明，仿射模型解释了B-树和B +-树的节点大小的选择。此外，模型预测B树对节点大小的变化非常敏感，而B树则不那么敏感。这些预测是根据经验得出的。最后，我们表明，在仿射和PDAM模型，它支付组织数据结构，利用不同的IO大小。在仿射模型中，B-树可以被优化，使得所有操作都是同时最优的，甚至直到低阶项。在PDAM模型中，可以组织B树（或B+树），以便有效地处理顺序和并发工作负载。我们的结论是，DAM模型是有用的第一次切割时，设计或分析的算法或数据结构，但仿射和PDAM模型使算法设计人员能够优化参数的选择，并填写在设计细节。
Storage devices have complex performance profiles, including costs to initiate IOs (e.g., seek times in hard drives), parallelism and bank conflicts (in SSDs), costs to transfer data, and firmware-internal operations. The Disk-Access Machine (DAM) model simplifies reality by assuming that storage devices transfer data in blocks of size B and that all transfers have unit cost. Despite its simplifications, the DAM model is reasonably accurate. In fact, if B is set to the half-bandwidth point, where the latency and bandwidth of the hardware are equal, the DAM approximates the IO cost on any hardware to within a factor of 2. Furthermore, the DAM explains the popularity of B-trees in the 70s and the current popularity of B-trees and log-structured merge trees. But it fails to explain why some B-trees use small nodes, whereas all B-trees use large nodes. In a DAM, all IOs, and hence all nodes, are the same size. In this paper, we show that the affine and PDAM models, which are small refinements of the DAM model, yield a surprisingly large improvement in predictability without sacrificing ease of use. We present benchmarks on a large collection of storage devices showing that the affine and PDAM models give good approximations of the performance characteristics of hard drives and SSDs, respectively. We show that the affine model explains node-size choices in B-trees and B+-trees. Furthermore, the models predict that the B-tree is highly sensitive to variations in the node size whereas B-trees are much less sensitive. These predictions are born out empirically. Finally, we show that in both the affine and PDAM models, it pays to organize data structures to exploit varying IO size. In the affine model, B-trees can be optimized so that all operations are simultaneously optimal, even up to lower order terms. In the PDAM model, B-trees (or B+-trees) can be organized so that both sequential and concurrent workloads are handled efficiently. We conclude that the DAM model is useful as a first cut when designing or analyzing an algorithm or data structure but the affine and PDAM models enable the algorithm designer to optimize parameter choices and fill in design details.