research-article

Public Access

External-memory Dictionaries in the Affine and PDAM Models

Authors:

Michael A. Bender,

Alex Conway,

Martín Farach-Colton,

Yang ZhanAuthors Info & Claims

ACM Transactions on Parallel Computing, Volume 8, Issue 3

Article No.: 15, Pages 1 - 20

https://doi.org/10.1145/3470635

Published: 20 September 2021 Publication History

All formats PDF

Abstract

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, then the DAM approximates the IO cost on any hardware to within a factor of 2.

Furthermore, the DAM model explains the popularity of B-trees in the 1970s 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 article, 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 B-trees are 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.

References

[1]

mkfs.btrfs. [n.d.]. Manual page. Retrieved from https://btrfs.wiki.kernel.org/index.php/Manpage/mkfs.btrfs.

Abstract

References

Cited By

Index Terms

Recommendations

BetrFS: a compleat file system for commodity SSDs

Copy-on-Abundant-Write for Nimble File System Clones

Efficient Directory Mutations in a Full-Path-Indexed File System

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

HTML Format

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations