Small file aggregation in a parallel computing system

[0001] This invention was made under a Cooperative Research and Development Agreement between EMC Corporation and Los Alamos National Security, LLC. The United States government has rights in this invention pursuant to Contract No. DE-AC52-06NA25396 between the United States Department of Energy and Los Alamos National Security, LLC for the operation of Los Alamos National Laboratory.

[0002] The present invention relates to parallel storage in high performance computing environments.

[0003] Parallel storage systems are widely used in many computing environments. Parallel storage systems provide high degrees of concurrency in which many distributed processes within a parallel application simultaneously access a shared file namespace.

[0004] Parallel computing techniques are used in many industries and applications for implementing computationally intensive models or simulations. For example, the Department of Energy uses a large number of distributed compute nodes tightly coupled into a supercomputer to model physics experiments. In the oil and gas industry, parallel computing techniques are often used for computing geological models that help predict the location of natural resources. One particular parallel computing application models the flow of electrons within a cube of virtual space by dividing the cube into smaller sub-cubes and then assigning each sub-cube to a corresponding process executing on a compute node.

[0005] Distributed parallel computing, however, is prone to failure as a failure of an individual compute node will interrupt the entire computation. Thus, fault tolerance techniques, such as checkpoint techniques, are often employed to store the current state of each process to persistent storage. After a failure, the application can then restart from the most recent checkpoint. The checkpoints are typically performed synchronously in time for each process.

[0006] There are a number of ways to organize the data streams when multiple processes simultaneously save data to a shared parallel storage system. For example, each process can create a single file across a set of different directories and then sequentially write a large amount of data to the single file. In a further implementation, a single process can create a shared file, and then all the processes write to the shared file in large segments that are aligned with block boundaries within the parallel file system.

[0007] When multiple processes create multiple small files concurrently, however, the performance of the parallel storage system will be impaired. Serialization can cause significant performance degradation as the parallel processes must remain idle while they wait for one another. Serialization is incurred when the parallel file system locks a shared object (such as a file or a directory) in order to maintain the consistency of the shared object. When multiple processes simultaneously try to create files in a shared directory, the directory must be locked so that multiple create operations on the directory do not collide.

[0008] Non-sequential access to the physical disk drives in the parallel storage system can also impair access pattern performance. When multiple small files are concurrently written, it is very challenging for the parallel file system to place the data into sequential regions of the disk. This type of access pattern can cause the disk to frequently switch the write position in a seek disk operation. Disk access patterns that incur many seek operations tend to perform an order of magnitude more poorly than patterns that do not incur seek operations.

[0009] A need therefore exists for improved techniques for storing multiple small files from a large number of clients concurrently accessing a shared storage system.

[0010] Embodiments of the present invention provide improved techniques for small file aggregation in a parallel computing system. In one embodiment, a method for storing a plurality of files generated by a plurality of processes in a parallel computing system comprises the steps of aggregating the plurality of files into a single aggregated file; and generating metadata for the single aggregated file, wherein the metadata comprises an offset and a length of each of the plurality of files in the single aggregated file.

[0011] The plurality of processes can be running, for example, on a plurality of compute nodes. The single aggregated file is optionally provided to a middleware virtual file system and/or one or more hard disk drives for storage. According to another aspect of the invention, the metadata can be used to unpack one or more of the files from the single aggregated file. Generally, the metadata characterizes a layout of the files within the single aggregated file.

[0012] Advantageously, illustrative embodiments of the invention provide small file aggregation using a parallel log file system. Small file aggregation reduces data processing and transfer bandwidth costs, and preserves valuable disk space.

[0013] These and other features and advantages of the present invention will become more readily apparent from the accompanying drawings and the following detailed description.

[0024] The present invention provides improved techniques for storing multiple small files from a large number of clients concurrently accessing a shared storage system. Embodiments of the present invention will be described herein with reference to exemplary computing systems and data storage systems and associated servers, computers, storage units and devices and other processing devices. It is to be appreciated, however, that embodiments of the invention are not restricted to use with the particular illustrative system and device configurations shown. Moreover, the phrases “computing system” and “data storage system” as used herein are intended to be broadly construed, so as to encompass, for example, private or public cloud computing or storage systems, as well as other types of systems comprising distributed virtual infrastructure. However, a given embodiment may more generally comprise any arrangement of one or more processing devices.

[0025] According to one aspect of the invention, small file aggregation is employed to reduce the overhead involved in the creation of small files. Generally, the small file data for many small files is buffered, for example, in a middleware file system located on the compute client. The aggregated small files are then sequentially written to disk in a much smaller number of physical objects. In this manner, the random creation of small files is transformed into sequential write operations to a large file by buffering the small files in memory and then writing relatively fewer files in large chunks.

[0026] In one exemplary embodiment, the middleware file system that aggregates the small files is implemented using the Parallel Log-Structured File System (PLFS), as modified herein to provide the features and functions of the present invention. See, for example, John Bent et al., “PLFS: A Checkpoint Filesystem for Parallel Applications,” Intl Conf. for High Performance Computing, Networking, Storage and Analysis 2009 (SC09) (November 2009), incorporated by reference herein. Generally, conventional PLFS improves the efficiency of checkpoint techniques for parallel applications by inserting an interposition layer into the existing storage stack to rearrange the problematic access pattern associated with checkpoints.

[0027] In addition, due to the placement of PLFS as a middleware file system on the client, PLFS can aggregate the large number of small files into a smaller number of large files.

[0028] Small File Aggregation

[0029] FIG. 1 illustrates an exemplary compute node 100 within a parallel computing system. As shown in FIG. 1, the exemplary node 100 comprises an application 110 that generates a plurality of files 120-1 through 120-N (collectively referred to herein as files 120). The application 110 provides the files 120 to a middleware virtual file system 130, such as PLFS. The middleware virtual file system 130 then stores the files 120 in an actual file system 140, comprised of one or more hard disk drives. The middleware virtual file system 130 may comprise, for example, a burst buffer (e.g., flash memory) to aggregate the small files.

[0030] In the exemplary embodiment, a daemon of the PLFS middleware virtual file system 130 runs on each node 100 to intercept each request by each process (or application) on the node 100. The PLFS middleware virtual file system 130 then captures the data for each write operation and packages (i.e., aggregates) multiple write operations into a single write operation of an aggregate file.

[0031] The rate of metadata creation for each individual file 120 is significant and imposes latency between the creation of each small file. The present invention recognizes that many file systems perform better for large sequential writes to a single file as opposed to many small writes to many small files. This is typically because writes to small files 120 may cause physical “seeks” of the disk head media. These seeks can take, for example, 10 milliseconds. Sequential access, however, can operate at rotational speeds that are an order of magnitude faster.

[0032] FIG. 2 illustrates the exemplary node 100 of FIG. 1 in accordance with an aspect of the present invention. As shown in FIG. 2, the middleware virtual file system 130 aggregates the files 120 by sequentially writing the files 120 into an aggregated file 210. The aggregated file 210 is then written to the actual file system 140, together with metadata 220. The metadata 220 is generated, for example, by the middleware virtual file system 130 and may be comprised of, for example, an offset and a length of each small file 120 in the aggregated file 210. The offset and length of each small file 120 provides an index that subsequently allows each small file 120 to be found in the aggregate file 210. The index optionally also comprises a timestamp that provides two functions: resolution in case of subsequent overwrites as well as a modification timestamp provided to the user when the user asks for the file access history. Finally, the index comprises an identifier (id) of each small file, which id can be looked up in the name file (discussed below) to find the file name. These lookups, which could otherwise result in disks seeks, can optionally be avoided by caching the index and name files, which are small and will fit in memory.

[0033] Note that typical file systems also will write to multiple physical locations on disk for the creation of a small file. The directory entry must be modified; the file needs an inode which may or may not fit in the directory entry; and the file data may go to a third block.

[0034] In this manner, the present invention improves file system performance for workloads comprised of the sequential creation of multiple small files 120. The virtual file system layer 130 rearranges the logical workload (multiple small files 120) into a physical workload more amenable to the performance characteristics of the backing file system. The logical file system view that the user expects is preserved so that the performance improvement is gained in a manner that is transparent to the user. In the exemplary embodiment, file data and associated metadata for a large number of files 120 are stored in three actual files 210, 220 (plus the name file). The smaller files in the aggregate file 210 are unpacked as necessary (as discussed below) to satisfy read and lookup operations.

[0035] The virtual file system preserves the expected view of the created files 120. Physically, however, the data is rearranged into a single large file 210, which was written sequentially. The smaller metadata file 220 describes the layout of the data within the large file 210, so that the data can be reconstructed for read and lookup operations. This reorganization, transparent to the application 110, allows the underlying storage system 140 to achieve the full potential bandwidth of the disk storage due to the sequential nature of the workload. It is noted, however, that two files are written: the data file 210 and the metadata file 220. Read access will first consult the metadata file to discover the appropriate location within the data file for a particular region of data. This lookup can be avoided with a small buffer for the metadata 220, which can be a small amount of data.

[0036] FIG. 3 illustrates an exemplary conventional PLFS logical file system 300. As shown in FIG. 3, the exemplary PLFS logical file system 300 comprises six files 310-1 through 310-6 and one directory 320.

[0037] FIG. 4 illustrates the aggregation of the exemplary PLFS logical file system 300 of FIG. 3 in accordance with the present invention. As shown in FIG. 4, the small files in the same directory are aggregated into a small file aggregated container structure 430. In particular, small files 310-1 through 310-3 under the directory PLFS mount point 300 are aggregated into a first small file aggregated container 430-1. Similarly, small files 310-4 through 310-6 under the directory 320 are aggregated into a second small file aggregated container 430-2. As discussed hereinafter, the small file aggregated container structures 430 are directories with a similar structure to PLFS container files.

[0038] FIG. 5 illustrates an exemplary internal structure 500 of the small file aggregated containers 430 of FIG. 4. As shown in FIG. 5, the exemplary internal structure 500 comprises a top level directory 510 and for each small file i in the aggregated small file, a name list file 530-i, a data file 540-i, and an index file 550-i. The name list file 530 identifies the associated small file by name, the data file 540 contains the actual data of the associated small file and the index file 550 comprises a pointer (i.e., an offset into the data file) to the actual data. An exemplary format for the name list file 530 is discussed further below in a section entitled “Physical Layout of Name List File.”

[0039] Consider P processes running on H compute nodes, F small files are written to the PLFS file systems, and the PLFS systems have B backends. Then, with small file aggregation in accordance with the present invention, the small file aggregated container will be created on every backend (B), every compute node may have a hostdir.x in each backend (B*H), every process will create three files in the hostdir.x directory it hashed to (2*P), so the total number of files or directories that will be created can be expressed as follows:
T=B+B*H+3*P

[0040] Each backend will contain (1+H+3P/B) files.

[0041] In all instances in which the number of files per process is greater than three, the total number of files in each backend will be less than a regular file system. In addition, every process could write the filename and index to the index file and write the data to data file. Thus, there is no need to share a file between processes.

[0042] Physical Layout of Name List File

[0043] In one exemplary embodiment, the name list files 530 record all operations on file names. In this manner, the list of files in this directory could be restored later. In addition, the name list file 530 must support create, rename and remove operations. A list of records will be appended to the name list file 530 when a new file is created or an old file is deleted or renamed. All records in the name list file 530 have the following exemplary format:

[0044]

	operation	length	time stamp	file name

where the exemplary operation field comprises 4 bytes enumeration (CREATE, DELETE, OPEN, OPEN_TRUNC, RENAME); the exemplary length field comprises 4 bytes to indicate the length of the file name without the ending zero; the exemplary time stamp comprises 8 bytes that records the time stamp of the operation to resolve potential conflicts; and the exemplary file name comprises a variable length indicating the name of the associated file.

[0045] Thus, after checking all the records in the name list file 530, the list of file names in this name list file 530 can be constructed. In addition, all of the files in a directory can be listed after reading and parsing all name list files 530. The name list files 530 and the index files 550 correspond to the metadata 220 of FIG. 2.

[0046] Small File Aggregated Container Data Structure

[0047] FIG. 6 illustrates an exemplary aggregated small file data structure 600 for the small file aggregated containers 430 of FIG. 4. The exemplary aggregated small file data structure 600 supports read and write operations to small files in the small file aggregated containers 430. The exemplary aggregated small file data structure 600 comprises a dropping files field 610, a names field 620, a small file container index field 630 and a writers field 640. The dropping files field 610 identifies any physical files (or sub-files) stored by the underlying file system, such as PLFS, in a known manner.

[0048] The names field 620 corresponds to the name lists 530 of FIG. 5 and is used for lookup and read operations. The lookup operation is important to the small file aggregated containers 430. Each time a file is opened, created, renamed or removed, the existence of the file should initially be checked in the small file aggregated containers 430. Thus, once the small file aggregated container 430 is created, all the name list files 530 in backend file systems will be loaded to memory so that the name list can be created. In addition, the name list can optionally be cached in memory so that later lookups do not require disk access.

[0049] As shown in FIG. 6, the name list 620 in memory is a mapping from each file name to its index and data files (did) and its file identifier (fid) in that index file, so that the data can be restored based on those index and data files.

[0050] The small file container index field 630 corresponds to the index files 550 of FIG. 5. As shown in FIG. 6, the writers field 640 identifies the writer process associated with each process (identified by a process identifier (pid)). The information in the writers field 640 is used to identify the writer for write operations and other modifications.

[0051] The writer is the data structure for making modifications to this aggregated small file data structure 600. The writer will be created when the process wants to make modifications to the aggregated small file data structure 600 (such as create a new file, open an existing file for write, rename or remove a file). The writer remains in memory as long as possible and it will not be deleted until the aggregated small file data structure 600 is deleted.

[0052] The aggregated small file data structure 600 must exist before modifications are made to this directory or regular files are accessed.

[0053] FIG. 7 is a flow chart describing an exemplary creation process 700 for obtaining an aggregated small file data structure 600. As shown in FIG. 7, the creation process 700 begins during step 710 once a file /path/to/dir1/file1 is accessed or modified.

[0054] A test is performed during step 720 to determine if the AggregatedFS->cache[“/path/to/dir1”] exists. If it is determined during step 720 that AggregatedFS->cache[“/path/to/dir1”] exists, then modifications continue during step 730, as discussed below. If, however, it is determined during step 720 that AggregatedFS->cache[“/path/to/dir1”] does not exist, then “/path/to/dir1” is expanded to “/backend1/path/to/dir1”, “/backend2/path/to/dir2” . . . during step 740.

[0055] A test is performed during step 750 to determine if the small files container directory is in these backends. If it is determined during step 750 that the small files container directory exists in these backends, then all name files are read during step 760 and the aggregated small file data structure 600 is created.

[0056] If, however, it is determined during step 750 that the small files container directory does not exist in these backends, then a further test is performed during step 770 to determine if the operation creates a new file.

[0057] If it is determined during step 770 that the operation does not create a new file, then—ENOENT (No such file or directory) is returned during step 780 and the process 700 stops (a file in an empty directory is being accessed). If, however, it is determined during step 770 that the operation creates a new file, then make the top level directory for small file container 430 on the appropriate backend during step 790 and create a new aggregated small file data structure 600 in memory.

[0058] Thus, the process generates an aggregated small file data structure 600 for the operations discussed below.

[0059] Modification Procedures

[0060] As indicated above, whenever a process P writes into a logical directory Y, the process P creates three files: Z/data.X, Z/index.X, and Z/names.X where Z is the physical directory as returned by expandPath( ) and X is a unique identifier (e.g., timestamp plus hostname plus pid). The names files 530, 630 will contain a set of filenames that P wrote in directory Y.

[0061] When a new Writer is added to PLFS, the Writer 640 will create three files and record the following modifications to these three files.

[0062] FIGS. 8A through 8C, collectively, illustrate exemplary pseudo code 800 for the Writer 640. As shown in FIG. 8B, the exemplary pseudo code 800 comprises a create function 810 to open a new file and a remove function 820 to remove a file.

[0063] As shown in FIG. 8C, the exemplary pseudo code 800 comprises a rename function 830 to rename an existing file. Section 840 creates and replaces a file while section 850 adds a new file after determining it does not already exist.

[0064] Loading and Merging Name List Files

[0065] When the PLFS is trying to load the small file aggregated containers 430 to memory, the PLFS will read all dropping files in the backend file systems. In addition, the PLFS will obtain a list of dropping files 610, such as dropping.data.X, dropping.index.X and dropping.names.X, where X is a unique identifier.

[0066] First, a vector of these dropping files 610 is created. The vector contains all the dropping files 610 in the backends containers 430. The vector will be referred as “Droppings” below. Then, all name list files 530, 620 will be read to obtain a list of operation records. The exemplary list of operation records contains:

[0067] dropping_id: If it is read from Droppings[i], then the dropping_id is ‘i’;

[0068] operation: CREATE, REMOVE, OPEN, OPEN_TRUNC, RENAME_FROM or RENAME_TO;

[0069] filename: The name of the file operated on;

[0070] timestamp: The timestamp stored in this name list file; and

[0071] file_id: Its id in this name list file.

[0072] In order to resolve potential conflicts, all of these lists of operation records will be sorted based on the timestamp. In addition, based on these lists of operation records, the Names mapping 620 in the small file container structure 600 could be constructed as shown in FIG. 9.

[0073] FIG. 9 illustrates exemplary pseudo code 900 for a names mapping construction process 900. After load_and_merge( ) during line 910, the Names mapping 620 can be constructed and the regular files in this directory can find all the index files that contain its data and its file id in those index files by investigating the result of SmallFileContainer.Names[filename].

[0074] File Descriptor and Related Operations

[0075] The file descriptor AggregatedFD has an Index for reading, and it will use the SmallFileContainer.Writers[pid] to perform modifications. The Index for reading is constructed from a list of index and data files and the file identifiers in each of them. The list can be obtained from SmallFileContainer.Names[its filename].

[0076] The data of this file can be constructed in a similar manner as the container mode of the PLFS, all index entries of it will be read from its index files and then those entries will be merged together to get the latest view of its data.

[0077] FIG. 10 illustrates the pseudo code 1000 for AggregatedFD. When the AggregatedFD is created, its member variables (except index) are setup in section 1010.

[0078] File Truncation

[0079] The truncation operation in small file aggregation is similar to container mode in a conventional PLFS with some minor changes.

[0080] Even if a file is truncated to zero, the corresponding dropping files 610 cannot be deleted or truncated to zero, because the dropping files 610 may contain some index entries of other logical files. The dropping files 610 may be shared between different logical files and cannot be deleted when one of the logical file is truncated to zero. Otherwise, another file may be corrupted.

[0081] There are no metadata files for aggregated small files. As a result, there is no place to store the latest size of a file. Thus, every time when the size of a file is needed, all of its index files need to be read.

[0082] If two or more logical files in the same directory are truncated concurrently by different processes, a locking mechanism should be deployed to prevent concurrently writing the index files, which may lead to data corruption.

[0083] While many existing file systems use a minimum of 4,000 bytes to store each file, the disclosed small file aggregation approach can use significantly less memory. The disclosed small file aggregation approach uses a small constant number of bytes (e.g., less than 100 bytes) for the necessary small file metadata 220 plus the small file data itself. In the extreme case of a 0 byte file, for example, the exemplary disclosed small file aggregation approach will use no more than 100 bytes as compared to 4096 bytes in typical file systems.

[0084] Numerous other arrangements of servers, computers, storage devices or other components are possible. Such components can communicate with other elements over any type of network, such as a wide area network (WAN), a local area network (LAN), a satellite network, a telephone or cable network, or various portions or combinations of these and other types of networks.

[0085] It should again be emphasized that the above-described embodiments of the invention are presented for purposes of illustration only. Many variations may be made in the particular arrangements shown. For example, although described in the context of particular system and device configurations, the techniques are applicable to a wide variety of other types of information processing systems, data storage systems, processing devices and distributed virtual infrastructure arrangements. In addition, any simplifying assumptions made above in the course of describing the illustrative embodiments should also be viewed as exemplary rather than as requirements or limitations of the invention. Numerous other alternative embodiments within the scope of the appended claims will be readily apparent to those skilled in the art.