Search

Contemporary frameworks for data analytics, such as Hadoop, Spark, and Flink seek to allow applications to scale performance flexibly by adding hardware nodes. However, we find that when the computation on each individual node is optimized, peripheral activities such as creating data partitions, messaging and synchronizing between nodes diminish the speedup obtainable from adding more hardware. We analyze workloads which distribute operations on correlated data—such as joins and aggregation found in SQL, text similarity searches, and image disparity computations. After optimizing computation on efficient, custom processors, we discover challenges in scaling the applications to hundreds of nodes on a high-bandwidth network. We then describe techniques to overcome these challenges towards prototyping a 512-node system which is able to execute SQL queries offloaded from a commercial database, and outperform SQL-on-hadoop and traditional parallel RDBMS executions by 173x and 7x respectively.

Modern InfiniBand interconnects offer link speeds of several gigabytes per second and a remote direct memory access (RDMA) paradigm for zero-copy network communication. Both are crucial for parallel database systems to achieve scalable distributed query processing where adding a server to the cluster increases performance. However, the scalability of distributed joins is threatened by unexpected data characteristics: Skew can cause a severe load imbalance such that a single server has to process a much larger part of the input than its fair share and by this slows down the entire distributed query. We introduce Flow-Join, a novel distributed join algorithm that handles attribute value skew with minimal overhead. Flow-Join detects heavy hitters at runtime using small approximate histograms and adapts the redistribution scheme to resolve load imbalances before they impact the join performance. Previous approaches often involve expensive analysis phases, which slow down distributed join processing for non-skewed workloads. This is especially the case for modern high-speed interconnects, which are too fast to hide the extra computation. Other skew handling approaches require detailed statistics, which are often not available or overly inaccurate for intermediate results. In contrast, Flow-Join uses our novel lightweight skew handling scheme to execute at the full network speed of more than 6 GB/s for InfiniBand 4×FDR, joining a skewed input at 11.5 billion tuples/s with 32 servers. This is 6.8× faster than a standard distributed hash join using the same hardware. At the same time, Flow-Join does not compromise the join performance for non-skewed workloads.