title: K-way merge sort divided on multiple hosts
body: <p>I have ~8000 files, with ~6TB data on disk. Each file contains a list of key value pairs, and I wish to consolidate those values into a single list of sorted key-value pairs (e.g. so if key A occurs in two files, the consolidated file contains the key A once and that key contains all values from the two files).</p>
  
  <p>I have implemented this <a href="https://en.wikipedia.org/wiki/K-way_merge_algorithm" rel="nofollow noreferrer">k-way merge</a> for a single core on a single host in Python [<a href="https://gist.github.com/duhaime/30251966f56e243a4f04740840ed2f3d" rel="nofollow noreferrer">gist</a> -- see <a href="https://stackoverflow.com/questions/50614732/divide-key-value-pairs-into-equal-lists-without-access-to-key-value-counts">this thread</a> for a nice intuitive overview of the procedure]. I now wish to distribute the work over multiple hosts that do not have shared memory but can have shared network access.</p>
  
  <p>The key space that I need to sort is absolutely enormous, roughly 26^24, but the vast majority of keys are not present in the data (so it doesn't make sense to give each worker a set of keys with which to concern themselves).</p>
  
  <p>Do others have any ideas how one could go about implementing a distributed k-way merge algorithm? This strikes me as entirely non-trivial, but there may be low hanging fruit that I'm not seeing. Any pointers others can offer would be greatly appreciated.</p>
  
  <hr>
  
  <p><strong>Notes</strong></p>
  
  <p>The compute setup is parameterizable. I'm working on two compute clusters, each will allow me to use ~10-1000 nodes concurrently, each with 12-24 cores and ~120GB RAM. The machines come online at some indeterminant time after they're requested. Network communication happens over TCP. Disks are SSD with an AFS filesystem and storage is abundant.</p>
  
  <p>Additionally, I'm using a simple Python package <a href="https://github.com/duhaime/big-read" rel="nofollow noreferrer">big-read</a> to read only <code>n</code> lines from each of the 8,000 files into RAM at any given time, so RAM management for an "external sort" is already tractable...</p>
  
  <p>Highly related: K-way merge with <a href="https://stxxl.org/tags/1.4.1/design_algo_sorting.html" rel="nofollow noreferrer">stxxl</a>.</p>