Terabyte Sort on FPGA-Accelerated Flash Storage

摘要

Sorting is one of the most fundamental and useful applications in computer science, and continues to be an important tool in analyzing large datasets. An important and challenging subclass of sorting problems involves sorting terabyte scale datasets with hundreds of billions of records. The conventional method of sorting such large amounts of data is to distribute the data and computation over a cluster of machines. Such solutions can be fast but are often expensive and power-hungry. In this paper, we propose a solution based on flash storage connected to a collection of FPGA-based sorting accelerators that perform large-scale merge-sort in storage. The accelerators include highly efficient sorting networks and merge trees that use bitonic sorting to emit multiple sorted values every cycle. We show that by appropriate use of accelerators we can remove all the computation bottlenecks so that the end-to-end sorting performance is limited only by the flash storage bandwidth. We demonstrate that our flash-based system matches the performance of existing distributed-cluster solutions of much larger scale. More importantly, our prototype is able to show almost twice the power efficiency compared to the existing Joulesort record holder. An optimized system with less wasteful components is projected to be four times more efficient compared to the current record holder, sorting over 200,000 records per joule of energy.