TL;DR
This paper introduces SDAFT, a novel framework that significantly speeds up parallel sequence search applications like BLAST by optimizing data access. By leveraging distributed file systems (like HDFS) and a smart scheduler, SDAFT reduces data movement bottlenecks, leading to up to a 10x reduction in I/O costs and doubling overall performance.
What Problem Does This Paper Address?
Modern scientific applications, particularly in computational biology, deal with massive datasets. Tools like BLAST, which compare query sequences against large databases, are computationally intensive. Existing parallel implementations often rely on a "compute-centric" model where data is moved from shared storage to individual compute nodes. As databases grow exponentially, this data movement becomes a major bottleneck, limiting scalability and performance. The challenge is to enable these MPI-based applications to efficiently access data stored in distributed file systems (DFS) while retaining their flexibility and performance.
Methods
SDAFT tackles this problem with two core components:
- Data-Centric Load-Balanced Scheduler (DC-scheduler): This component shifts the paradigm from moving data to compute nodes to moving computation to where the data resides. It intelligently schedules tasks to nodes that already have the required data fragments locally, minimizing network transfer. It also ensures load balance by assigning tasks to nodes based on their current load and data availability.
- SDAFT-IO Translation Layer: This layer acts as a bridge, allowing existing MPI-based applications that use standard I/O interfaces (like MPI_File_read()) to transparently interact with distributed file systems like HDFS. It translates conventional I/O operations into HDFS-compatible calls, resolving compatibility issues and enabling applications to run on HDFS without significant code modification.
The framework uses a master-slave architecture where the master process (DC-scheduler) manages task assignment and the slave processes execute the search using the SDAFT-IO layer to access data from HDFS.
Datasets
The primary dataset used for evaluation was the nt (nucleotide) database from NCBI. At the time of the experiments, this database contained approximately 17.6 million sequences, totaling about 45 GB. The authors also generated query sequences by randomly selecting and modifying sequences from the nt database to ensure close matches were found.
Key Insights and Ideas
- Compute-to-Data vs. Data-to-Compute: The paper strongly advocates for a "compute-to-data" approach, demonstrating its significant benefits over the traditional "data-to-compute" model for large-scale data-intensive applications.
- HDFS for Scientific Applications: By developing a translation layer, SDAFT shows that distributed file systems like HDFS, often associated with MapReduce, can be effectively leveraged by traditional MPI-based scientific applications.
- Data Locality is King: The experiments highlight that maximizing data locality (accessing data from local disks) is crucial for achieving scalability and high performance in data-intensive parallel computing.
- SDAFT-IO's Non-Intrusiveness: The translation layer's ability to work with existing MPI applications with minimal modification is a key enabler for widespread adoption.
Key Results
- Significant I/O Cost Reduction: SDAFT reduced I/O costs by a factor of 4-10 compared to existing schemes.
- Doubled Overall Performance: The framework doubled the overall execution performance of parallel BLAST applications, especially in I/O-intensive scenarios.
- Scalability: SDAFT demonstrated excellent scalability, with I/O bandwidth scaling linearly with the number of nodes, unlike NFS and PVFS which plateaued.
- Reduced I/O Latency: SDAFT achieved significantly lower I/O latency, often five times lower than PVFS-based BLAST.
- High Data Locality: Experiments showed that over 95% of data fragments were read from local storage when using SDAFT.
- Comparison with Hadoop-Blast: SDAFT-based BLAST was found to be significantly faster (568.664s vs. 1427.389s on 25 nodes) than a Hadoop-Blast implementation, attributed to better I/O optimization and MPI's inherent efficiency.
Limitations and Future Work
- HDFS "Append" Write Limitation: The paper notes that HDFS primarily supports "append" writes, which posed a challenge for handling concurrent writes from parallel applications. SDAFT addressed this by implementing a "concurrent write to multiple files" strategy.
- FUSE Overhead: While SDAFT-IO uses FUSE for its prototype, the authors acknowledge the potential overhead of FUSE-based implementations. However, their experiments showed negligible overhead for parallel BLAST, and in some cases, SDAFT-IO even outperformed direct libhdfs.
- Future Work: The authors suggest that SDAFT is orthogonal to existing techniques and can be adopted by other MPI-based applications that benefit from data locality. They also mention that the improvement from I/O reduction is more pronounced with larger databases and smaller query sizes. Further exploration into optimizing for different data access patterns and file system configurations could be beneficial.
Summary updated