Abstract
The Hadoop Distributed File System (HDFS) is optimized for high-throughput access to large files. However, it suffers from the "small file problem," where millions of small files exhaust the NameNode's memory and degrade access performance. This paper proposes Hadoop Perfect File (HPF), a novel archive format that leverages a two-tiered hashing strategy—combining an Extensible Hash Function with a Monotone Minimal Perfect Hash Function—to achieve $O(1)$ metadata lookup times. Experimental results demonstrate that HPF significantly outperforms existing solutions like HAR and MapFile, offering up to 40% faster access than native HDFS while drastically reducing NameNode memory pressure.
Introduction
HDFS is a cornerstone of big data processing, designed to handle massive datasets across commodity hardware. It employs a master-slave architecture where a central NameNode manages the file system namespace and metadata, while DataNodes store the actual data blocks. While efficient for large-scale streaming, this architecture faces a critical scalability bottleneck when dealing with large numbers of small files.
The Small File Problem
In HDFS, every file, directory, and block is represented as an object in the NameNode's RAM, typically consuming between 250 and 368 bytes. When a cluster stores billions of small files (e.g., logs, sensor data), the NameNode's memory can become a single point of failure or a severe performance bottleneck.
Existing workarounds like Hadoop Archives (HAR) and MapFiles attempt to mitigate this by merging small files into larger containers. However, HAR files suffer from slow access due to a two-level index and are immutable. MapFiles require data to be pre-sorted and can still impose significant memory overhead when loading index files.
Hadoop Perfect File (HPF) Architecture
HPF addresses these limitations by merging small files into "part-*" files and implementing a decentralized, high-performance indexing mechanism. The core of HPF is its two-step metadata lookup system:
- Extensible Hash Function (EHF): This function maps file names to specific "buckets" or index files. This allows the system to scale dynamically; as the number of files grows, buckets can split without requiring a full re-indexing.
- Monotone Minimal Perfect Hash Function (MMPHF): Within each index file, an MMPHF maps file names to unique offsets with zero collisions. Because the function is order-preserving, it enables direct-to-disk seeks for metadata without needing to load the entire index into memory.
By calculating the exact byte offset of metadata (position, size, etc.), HPF allows clients to bypass the NameNode for granular file lookups, effectively "unloading" the master server. Furthermore, HPF utilizes standard Java sockets for client-DataNode communication, which proved more efficient than the standard Hadoop RPC for these metadata-heavy tasks.
Evaluation and Results
The researchers evaluated HPF against native HDFS, HAR, and MapFile using datasets ranging from 100k to 400k small files (1 KB to 10 MB).
- Access Performance: HPF achieved $O(1)$ lookup complexity. Without caching, HPF was 40% faster than native HDFS, 179% faster than MapFile, and over 11,000% faster than HAR. Even with caching enabled, HPF maintained a 35% performance lead over MapFile.
- Creation Speed: Unlike HAR, which requires resource-intensive MapReduce jobs, HPF can be created in parallel using simple merging threads, making it significantly faster to generate.
- Storage Efficiency: By utilizing LZ4 record-level compression, HPF reduced the total storage footprint by approximately 11% compared to raw HDFS storage.
Conclusion
Hadoop Perfect File (HPF) provides a robust solution to the HDFS small file problem. By moving metadata lookups from the NameNode's RAM to a highly efficient disk-based perfect hashing system, HPF enables massive scalability and superior access speeds. Future work will focus on implementing block-level compression and supporting file deletions within the archive.
Summary updated