WiscSort: External Sorting for Byte-Addressable Storage

Vinay Banakar, Kan Wu, Yuvraj Patel, Kimberly Keeton, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We present WiscSort, a new approach to high-performance concurrent sorting for existing and future byte-addressable storage (BAS) devices. WiscSort carefully reduces writes, exploits random reads by splitting keys and values during sorting, and performs interference-aware scheduling with thread pool sizing to avoid I/O bandwidth degradation. We introduce the BRAID model which encompasses the unique characteristics of BAS devices. Many state-of-the-art sorting systems do not comply with the BRAID model and deliver sub-optimal performance, whereas WiscSort demonstrates the effectiveness of complying with BRAID. We show that WiscSort is 2-7x faster than competing approaches on a standard sort benchmark. We evaluate the effectiveness of key-value separation on different key-value sizes and compare our concurrency optimizations with various other concurrency models. Finally, we emulate generic BAS devices and show how our techniques perform well with various combinations of hardware properties.
Original languageEnglish
Pages (from-to)2103-2116
JournalProceedings of the VLDB Endowment
Issue number9
Publication statusPublished - 10 Jul 2023


Dive into the research topics of 'WiscSort: External Sorting for Byte-Addressable Storage'. Together they form a unique fingerprint.

Cite this