Hadoop Perfect File: A fast access container for small files with direct in disc metadata access

Jude Tchaye-Kondi, Yanlong Zhai, Kwei-Jay Lin, Wenjun Tao, Kai Yang

TL;DR

This paper introduces Hadoop Perfect File (HPF), a novel archive file format designed to efficiently store and access massive numbers of small files in HDFS. HPF achieves significantly faster metadata lookup and file access by using a two-tiered hashing system and direct access to index files, overcoming the performance bottlenecks of existing HDFS solutions.

What Problem Does This Paper Address?

The Hadoop Distributed File System (HDFS) is excellent for storing and processing large files. However, it struggles with a large volume of small files. This "small file problem" arises because HDFS's NameNode (NN) stores all file metadata in its main memory. With millions of small files, the metadata size can overwhelm the NN's memory, leading to performance degradation, overload, and even system instability. Existing solutions like HAR, SequenceFile, and MapFile attempt to mitigate this by merging small files into larger archives, but they often introduce their own performance issues, particularly in accessing individual small files within these archives. These methods can require reading entire index files or rely heavily on client-side caching, which can be problematic for clients with limited memory.

Methods

HPF tackles the small file problem by creating an archive file that merges small files into larger "part" files. The core innovation lies in its metadata management and access strategy:

  • Two-Tiered Hashing for Metadata: HPF uses a combination of two hash functions to locate a small file's metadata:
  • Extensible Hash Function (EHF): This function dynamically distributes metadata across multiple index files, preventing any single index file from becoming too large and ensuring efficient distribution.
  • Monotone Minimal Perfect Hash Function (MMPHF): For each index file, an MMPHF is built. This function allows for direct, O(1) lookup of a specific file's metadata within that index file, eliminating the need to scan the entire index.
  • Direct Index File Access: Unlike other archive formats that might require reading entire index files, HPF's MMPHF allows it to calculate the exact offset and size of the metadata for a specific file. This enables direct seeking and reading of only the necessary metadata.
  • Centralized Caching: To further reduce I/O operations, HPF leverages HDFS's Centralized Cache Management system to keep its index files in the DataNodes' off-heap memory. This means metadata lookups are primarily in-memory operations.
  • File Appending: HPF supports adding new files to an archive after its creation, a feature lacking in some other archive formats like HAR.
  • Lazy Persist Writes: During the creation of HPF files, the paper utilizes HDFS's Lazy Persist write policy to speed up the writing of data to DataNodes by using off-heap memory.

Datasets

The paper uses log text files from various servers as its dataset. They employ multiple file sets with varying numbers of files: 100,000, 200,000, 300,000, and 400,000 files. The total size of these datasets ranges from 1.44 GB to 4.23 GB, with individual file sizes varying from 1 KB to 10 MB. No new benchmarks were introduced; instead, they compared HPF against native HDFS, HAR, and MapFile.

Key Insights and Ideas

  • Metadata is the Bottleneck: The paper strongly emphasizes that the primary challenge with small files in HDFS is not the storage of the data itself, but the sheer volume of metadata and its management by the NameNode.
  • Direct Metadata Access is Key: The core insight is that by using perfect hashing and distributing metadata across multiple index files, it's possible to achieve near-instantaneous metadata retrieval without needing to load entire index files into memory.
  • Decentralizing Metadata Management: While HDFS centralizes metadata in the NN, HPF effectively decentralizes the access to metadata by leveraging DataNode caching and its own index structure, reducing the NN's burden.
  • Trade-offs in Archive Design: The paper highlights how different archive formats make trade-offs. HAR is slow but simple; MapFile offers compression but has limitations with random access and appending; HPF aims for a balance of speed, appendability, and efficient metadata access.

Key Results

The experimental results demonstrate HPF's significant performance advantages:

  • Access Performance (Without Caching): HPF was up to 40% faster than native HDFS, 179% faster than MapFile, and an astonishing 11294% faster than HAR.
  • Access Performance (With Caching): Even with caching enabled for HAR and MapFile, HPF remained faster, showing a 48% improvement over HDFS, 35% over MapFile, and 105% over HAR.
  • Creation Time: HPF exhibited the fastest creation time among the archive formats, significantly outperforming HAR.
  • NameNode Memory Usage: HPF, HAR, and MapFile all showed substantially lower NameNode memory usage compared to storing files directly in HDFS. HPF and HAR were slightly more memory-efficient than MapFile due to using a larger block size (512MB vs. 128MB).
  • Archive File Size: HPF and MapFile achieved significant space savings (over 42% for MapFile and 11% for HPF) due to compression, while HAR offered little to no compression.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while HPF moves metadata load from the NN to DNs, it still requires client-side processing for initial metadata hashing and index building.
  • The recovery mechanism for client-side failures relies on a temporary index file, which could potentially lead to data loss if not managed carefully.
  • The current HPF prototype applies compression at the record level, which is less efficient than MapFile's block-level compression.
  • Future Work:
    • Investigate the memory footprint of HPF's two hash functions (EHF and MMPHF) in client memory.
  • Explore implementing block-level compression, similar to MapFile, for potentially better storage efficiency.
  • Develop functionality for deleting files from HPF archives.
  • Consider moving the index system construction to the NameNode side to leverage its high availability, though this would increase NN resource usage.

Summary updated

BibTeX
@article{tchayekondi2021hadoop,
  author = {Jude Tchaye-Kondi and Yanlong Zhai and Kwei-Jay Lin and Wenjun Tao and Kai Yang},
  title = {{Hadoop Perfect File: A fast access container for small files with direct in disc metadata access}},
  journal = {J. Parallel Distributed Comput.},
  year = {2021},
  doi = {10.1016/j.jpdc.2021.05.011},
}
Figure