MilliSort is a new sorting benchmark for massively parallel computing. Since the time budget of
1 ms is extremely limited (e.g., 1 ms only allows 10000 sequential cache misses or 200 sequential
RPCs), we redesigned distributed sorting from scratch to avoid cache misses and sequential RPCs. In
addition, MilliSort adopted a newly invented distributed sorting algorithm that uses a hierarchical
form of key range partitioning, which is 200x faster than the previous systems (100 ms → 0.5 ms for
280 nodes).
Thanks to this careful redesign, MilliSort performs very efficiently even at the extreme 1 ms
timescale. MilliSort’s throughput per node reaches 63.6% of the idealized upper bound, where the
partitioning cost is zero and data is shuffled at full network bandwidth with perfect balance. This
is on par with the efficiency of running a state-of-the-art sorting system for 100 seconds.
