  Large scale graph processing using distributed computing frameworks is
becoming pervasive and efficient in the industry. In this work, we present a
highly scalable and configurable distributed algorithm for building connected
components, called Union Find Shuffle (UFS) with Path Compression. The scale
and complexity of the algorithm are a function of the number of partitions into
which the data is initially partitioned, and the size of the connected
components. We discuss the complexity and the benchmarks compared to similar
approaches. We also present current benchmarks of our production system,
running on commodity out-of-the-box cloud Hadoop infrastructure, where the
algorithm was deployed over a year ago, scaled to around 75 Billion nodes and
60 Billions linkages (and growing). We highlight the key aspects of our
algorithm which enable seamless scaling and performance even in the presence of
skewed data with large connected components in the size of 10 Billion nodes
each.
