// HACKER NEWS — CYBERSECURITY
Accelerated Out of Core Shuffling
Shuffling data at 1.8 TiB/s! RapidsMPF is a reusable, out-of-core shuffler that turns shuffling OOM headaches into a
spill you can budget for.
Shuffling is the crux of structured data analytics distributed or otherwise. It's a core component of key data
operations like: join, groupby, merge, sort, etc. A full distributed shuffle can move all the data from every process
to every other process, an all-to-all. This is very costly and many sophisticated techniques have been developed to
avoid this operation as much as possible. Shuffles aren't particularly computationally challenging: calculating the
hashes to route data is fairly cheap. They are nonetheless expensive in a workflow, for a variety of reasons:
Because shuffling is hard, slow, memory-intensive, and critical, it's historically where RapidsMPF started.
A quick primer on joining tables. If we have two tables: partsupp and lineitem and we want to join them, what
happens?
note: left, right, and full outer joins use the same build/probe strategy with different rules for unmatched rows
At minimum, this in-memory join holds three tables: the build table, the probe table, and the output table and the
hash table built over the build side.
In the in-memory case, all the data is already colocated within the same memory space. That's no longer true once the
tables are spread across many processes/nodes/ranks or tables are batched for "streaming" joins. A rank/process can
only join rows in resident memory. Eventually, an in-memory join will occur, but first we'll need to get all the
matching keys for the build and probe tables on the samerank.
The cartoon graphic below represents how various rows of the same color are shuffled into the same output partition, and
those partitions live on different ranks.
To execute a distributed hash-join one must do the following:
In the worst case, if every stage is fully materialized before the next one begins, a single rank is holding all of the
following at once: