Meta-Data Structure and Handling

The present invention relates generally to data processing systems and, more particularly, to storage of data on disk by a file system.

Conventional file systems have had difficulty in storing file data on disk in an efficient manner. Many conventional systems have adopted an approach wherein all data is stored in a single-sized storage unit on disk. Unfortunately, this approach does not efficiently store file data on disk. In particular, file data may vary in size and, thus, may not be well-matched for the predetermined storage unit size. Other conventional systems have provided a user with an option of adopting one of numerous different formats. The decision as to which format to adopt must be made before the file data is available to the user. As a result, the choice of format by the user is merely speculative and often does not correspond well with the actual file data. As a result, the file data is often inefficiently stored.

In conventional operating systems, each file is allocated a fixed number of blocks of disk space for storing file data and control information about the file. The blocks are fixed-sized so that the units may be quickly allocated and deallocated. The control information for the files and the file data are often variable-sized, which poses at least two problems. First, when the file data and/or control information is not large enough to fill a block, disk space within the allocation unit is wasted. Second, when the file data and/or control information is too large to be stored in a single block, it must be stored in multiple blocks and multiple pointers are maintained to specify where the data is stored. Maintaining and using such pointers is often quite cumbersome.

In conventional file systems, data and meta-data (i.e., data that describes the storage of other data) have been treated as distinct entities. In particular, data and meta-data have been stored in different formats in conventional file systems. Moreover, separate tools have been provided for acting on data and meta-data. This fragmented view of data and meta-data has resulted in added overhead and complexity.

In accordance with the first aspect of the present invention, a method is practiced in a data processing system having disk storage and a processing means for running an operating system. In this method, the data is stored in the disk storage in a first variable-sized stream data structure. Meta-data is stored in the disk storage in a second variable-sized stream data structure. A stream descriptor is stored for each of the stream data structures. The stream descriptor includes a type identifier that identifies how the stream data structure is stored on disk in disk storage.

In accordance with another aspect of the present invention, streams of data are stored in stream data structures in the disk storage. The streams of data are formed from logically contiguous bytes of data. A stream descriptor is stored for each stream data structure in the disk storage. Each stream descriptor includes a type identifier that describes how the stream data structure is stored in the disk storage. The stream data structures which store related data are stored in a first variable-sized data structure along with their associated stream descriptors.

In accordance with yet another aspect of the present invention, streams of data are stored in the disk storage in stream data structures. A stream descriptor is stored for each stream data structure on the disk storage. Each stream descriptor includes a type identified that describes how the stream data structures are stored in the disk storage. Stream data structures which store related data are stored in the disk storage along with their associated stream descriptors in a variable-sized data structure. Groups of the variable-sized data structures which store related data are stored in a catalog data structure.

In accordance with yet another aspect of the present invention, a method is practiced in a data processing system having disk storage. In this method, streams of data are stored in the disk storage in stream data structures. The streams are formed by logically contiguous bytes of data. A stream descriptor is stored for each stream data structure in the disk storage. The stream data structures which store related data are stored along with their associated stream descriptors in respective variable-sized data structures in the disk storage. Each variable-sized data structure has an associated identifier. The variable-sized data structures are stored in an array of fixed-sized identifiable buckets of disk space in the disk storage. A mapping structure holding entries that specify a bucket identifier for a bucket in the array is stored in the disk storage. The entries are indexed by the identifiers of the variable-sized data structures. The mapping structure is used to locate one of the variable-sized data structures in the array, given its identifier.

FIG. 1 is a block diagram of a data processing system for practicing a preferred embodiment of the present invention.

FIG. 2 is a diagram of the format for a stream descriptor that is used in the preferred embodiment of the present invention.

FIG. 3 is a diagram of a stream descriptor for a tiny stream in accordance with the preferred embodiment of the present invention.

FIG. 4 is a diagram of a stream descriptor for a small stream in accordance with the preferred embodiment of the present invention.

FIG. 5 is a diagram of a stream descriptor for a large stream in accordance with the preferred embodiment of the present invention.

FIG. 6 is a diagram of a stream descriptor for a compressed stream in accordance with the preferred embodiment of the present invention.

FIG. 7 is a diagram of a stream descriptor for an encrypted stream in accordance with the preferred embodiment of the present invention.

FIG. 8 is a diagram of a stream descriptor for a small scale transaction in accordance with the preferred embodiment of the present invention.

FIG. 9 is a diagram of a stream descriptor for replicated data in accordance with the preferred embodiment of the present invention.

FIG. 10 is a diagram of a field descriptor in accordance with the preferred embodiment of the present invention.

FIG. 11 is a diagram of an onode in accordance with the preferred embodiment of the present invention.

FIG. 12 is a diagram of streams that hold property information about the onode of FIG. 12.

FIG. 13 is a diagram of a bucket array in accordance with the preferred embodiment of the present invention.

FIG. 14 is a diagram of a work ID mapping array and an onode bucket array in accordance with the preferred embodiment of the present invention.

FIG. 15 is a diagram of an object store catalog in accordance with the preferred embodiment of the present invention.

The preferred embodiment of the present invention provides a file system that stores both data and meta-data on disk as groups of "streams." A "stream" is a logically contiguous, randomly addressable, variable-sized array of bytes of data that serves as the logical unit of storage on the disk. Most programmatic access to data in files is made through streams. Each stream may be stored on the disk in one of a number of different representations. Each of the different representations is well suited for a particular size and use of the stream. Accordingly, each stream is stored in a representation on disk that is best suited for its size.

Each stream has a stream descriptor associated with it and which is stored in a file system control structure. The stream descriptor is used to access the stream and to obtain information about the stream. The stream descriptor provides a description of the representation in which the data of the streams is stored. Streams of data that hold related data are encapsulated into data structures known as onodes. An onode is a variable-sized structure that is roughly analogous to a file, a directory or a subdirectory. Groups of related onodes are, in turn, stored in data structures known as object store catalogs or object stores. Thus, data and meta-data (such as the object store catalogs) are described in a like fashion in a hierarchy which will be described in more detail below.

FIG. 1 is a block diagram of a data processing system 10 for practicing the preferred embodiment of the present invention. Although the system 10 of FIG. 1 is a single processor system, those skilled in the art will appreciate that the present invention may also be practiced in a multiple processor system, such as a distributed system. The data processing system 10 includes a central processing unit (CPU) 12, a memory 14, disk storage 16, a keyboard 18, a mouse 20, and a video display 22. The disk storage 16 may include hard disks and other types of disk storage devices. The keyboard 18, mouse 20, and video display 22 are conventional input/output devices.

The memory 14 holds a copy of an operating system 24, including a file system manager 26 for managing files stored in the system. The operating system 24 may be an object-oriented operating system. The preferred embodiment of the present invention described herein is implemented as part of the operating system 24. Although the preferred embodiment of the present invention is described as being part of the operating system 24, those skilled in the art will appreciate that the present invention may alternatively be implemented in other types of code that are separate from the operating system.

As mentioned above, streams are available in a number of different representations in the preferred embodiment of the present invention. In order to understand the different representations of streams, it is helpful to review the format of the stream descriptors that are provided for the streams. FIG. 2 is a diagram of the format of a stream descriptor 28. The stream descriptor 28 is capable of describing each of the different representations of streams that are available in the preferred embodiment of the present invention. The stream descriptor 28 includes three fields: a size field 30, a type field 32 and a description field 34. The size field 30 holds a value that specifies the size of the stream in bytes. The type field 32 specifies the type of the stream, and the description field 34 holds a description of the stream (i.e., the form of the description field 34). The values held in fields 30, 32 and 34 vary with the representation of the associated stream (as will be described in more detail below).

A "tiny stream" is a first representation of a stream that is available in the preferred embodiment of the present invention. The tiny stream is used to store data that is very small in size relative to the allocation unit of the storage medium (i.e., a disk in the disk storage 16). The "allocation unit" of the storage medium refers to the basic unit of disk memory space in disk storage 16 that is allocated for storing files. For instance, in FAT-based file systems, the minimum allocation unit is a sector. Unfortunately, a sector is often much larger than stream data produced in the system 10. FIG. 3 depicts the format of the stream descriptor 28 for the tiny stream. The size field 30 holds a value that specifies the size of the stream, and the type field 32 specifies that the stream is a tiny stream. The description field 34 holds the data of the stream and, thus, provides an immediate representation of the data of the stream. This immediate representation provides a very efficient means for storing small amounts of data. In particular, the data is integrated directly into the stream descriptor so that it may be easily and quickly accessed.

Another representation that is available in the preferred embodiment of the present invention is a small stream. The "small stream" is a stream that is stored in a single extent of data. An extent is a variable-sized contiguous run of allocation units. The stream data is stored in an extent because it is too large to store directly in the stream descriptor 28. The format of the stream descriptor 28 for the small stream is shown in FIG. 4. The type field 32 specifies that the associated stream is a small stream, and the description field 34 holds an extent descriptor 36 that describes an extent 42 in which the data of the stream is stored. The extent 42 is stored on a disk in the disk storage 16. The extent descriptor 36 includes two subfields 38 and 40. Subfield 38 holds a value that specifies the length of the extent 42, and subfield 40 holds the disk address of the extent (i.e., where the extent is located in the logical address space of the disk).

A third representation that is available in the preferred embodiment of the present invention is a "large stream." The large stream is a stream stored in multiple extents. The large stream is appropriate for storing a stream having a large amount of data. FIG. 5 depicts the format of the stream descriptor 28 for such a large stream. Type field 32 specifies that the stream is a large stream. The description field 34 holds a second stream descriptor 43 that describes a stream 44 holding extent descriptors. This second stream descriptor 43 describes a tiny stream and includes a description field 34' that holds the stream 44 of extent descriptors. The extent descriptors 36', 36" and 36'" have the same format as the extent descriptor 36 that was described with reference to FIG. 4. As a result, multiple extents 42', 42" and 42'" are described by a single stream 34'. If the number of extent descriptors becomes too large, the second stream descriptor 43 may describe a small stream rather than a tiny stream. Moreover, if the number of extent descriptors becomes too large for a small stream, the second stream descriptor 43 may describe a large stream. Large streams are generally used where large contiguous blocks of disk space are not available. The large stream facilitates the storage of large amounts of data as a single stream in extents that may be dispersed about the disk. As a result, large streams scale well as disks become more fragmented and the stream grows.

As the size of a stream grows, the representation of the stream is promoted up a hierarchy of stream representations to facilitate efficient storage of the stream. The hierarchy includes the tiny stream, the small stream and the large stream. A stream may be promoted from a tiny stream to a small stream and then to a large stream. In general, as was mentioned above, the most appropriate representation is chosen for a stream based upon the amount of data and the amount of fragmentation that are included in the stream.

The above description has described the four basic types of streams available in the preferred embodiment of the present invention. The type field 34 of stream descriptor 28 may also be utilized to specify special descriptions of data stored within a stream. FIG. 6 is an example of the format of the stream descriptor 28 when a stream holds compressed data. The type field 32 holds a value specifying that the data of the stream is compressed, whereas the description field 34 holds a stream descriptor for the compressed data. The stream descriptor held in the description field 34 may be a tiny stream, a small stream, or a large stream, depending upon the amount of data included in the stream.

FIG. 7 depicts the format of a stream descriptor 28 when the stream descriptor describes a stream of encrypted data. Type field 32 holds a value which specifies that the stream holds encrypted data. The description field 34 holds a stream descriptor for the encrypted data. The stream descriptor also includes an encryption key value 50. The encryption key value 50 may be used to decrypt the data stored in the stream. The stream descriptor for the encrypted data that is held in the description field 34 may be a tiny stream, a small stream, or a large stream.

Another example of the use of the type field 32 to specify special descriptions of data is shown in FIG. 8. FIG. 8 shows the stream descriptor 28 for a small scale transaction. A small scale transaction refers to an instance wherein changes to data in a database are recorded without directly changing the data until a sufficient number of other changes have occurred to warrant incurrence of the overhead associated with changing all of the affected data. The type field 32 specifies that the description field 34 holds data for a small scale transaction. The description field 34 holds a first stream descriptor 52 and a second stream descriptor 54. The first stream descriptor 52 describes an original stream of data. The second stream descriptor 54 describes a stream that specifies the changes that have been made to the original stream. The original stream of data is updated by implementing the changes held in the second stream.

FIG. 9 shows an example of the stream descriptor 28 for a stream that holds replicated data. Data often must be replicated so that loss of the data will not be catastrophic. Specifically, there are selected data structures for which the system maintains multiple copies on disk. In such instances, the structures are copied to two different locations on the disk. The stream descriptor 28 includes a first stream descriptor 56 and a second stream descriptor 58 in its description field 34. The first stream descriptor 56 describes a first stream holding a first copy of the data, and the second stream descriptor 58 describes a second stream holding another copy of the data. The type field 32 holds a value specifying that the stream includes replicated data.

The preferred embodiment of the present invention stores information about streams in a field descriptor 60 like that shown in FIG. 10. The field descriptor 60 includes a stream ID field 62 that holds a stream ID. The stream ID is a four-byte long identification number that uniquely identifies the stream within an onode (onodes will be described in more detail below). The field descriptor 60 further includes a flags field 64 that holds flag bits. The final field of the field descriptor 60 is the stream descriptor 28 for the stream.

Streams are grouped according to related functionality into "onodes". An onode corresponds with the logical notion of an object and typically holds all of the streams that constitute a file, a directory or a subdirectory. Each onode includes information necessary to describe the variable-sized collection of streams that it includes.

FIG. 11 is a diagram that illustrates the format of an onode 66. Each onode 66 holds streams of related functionality. Each onode 66 includes the following fields: a length field 68, a work ID field 70, a flags field 72, a class ID field 73 and a field 76 that holds an array of field descriptors 60 (such as depicted in FIG. 10). The length field 68 holds a value that specifies the length of the onode, whereas the work ID field 70 holds an index into a work ID mapping array 104 (FIG. 14), as will be described in more detail below. The work ID is four bytes in length. The flags field 72 (FIG. 11) holds flag bits, and the class ID field 73 holds a class ID for the onode. Field 76 holds a packed array of field descriptors 60, that includes a field descriptor 60 for each of the streams held with the onode 66. The number of streams included in the array of field descriptors of field 76 may vary. Moreover, the length of each stream in the array of field descriptors of field 76 may vary. Accordingly, the onode 66 is a variable-sized structure. The variable-sized nature of onodes 66 helps to minimize internal fragmentation in allocation units on disk in disk storage 16.

Certain data about onodes 66 is not incorporated directly into the onode. Instead, this data is stored in separate streams as shown in FIG. 12. Stream 78 holds a number of different types of status information regarding its associated onode 66 (FIG. 11). The status information includes a time stamp held in field 86 that specifies the time that the onode 66 was created. Field 88 holds a time stamp that specifies the last time that the onode 66 was modified. Similarly, field 90 holds a time stamp that specifies the last time that the onode 66 was accessed. Field 92 holds a value that specifies the size of the onode 66, and field 94 holds a security descriptor for the owner of the onode. All of the information held in stream 78 is useful in administration of file data held in the associated onode 66.

A second stream 80 of status information is also shown in FIG. 12. This stream 80 includes three fields 96, 98 and 100. Each onode 66 is visible in the global name space of the data processing system 10, and the global name space is a logical tree structure in which each onode other than the root onode has a parent node. Field 96 holds the work ID of the parent onode. Field 98 holds a universally unique ID (UUID) for the onode 66. Lastly, field 100 holds a class ID that specifies the class of the onode 66. Each onode 66 has a unique class associated with it. In particular, each onode 66 is an instance of an object of a particular class.

Two additional streams 82 and 84 of status information are also stored. Stream 82 holds the name of the onode 66 relative to its parent, and stream 84 holds access control lists (used in security) for the onode.

Streams 78, 80, 82 and 84 are stored separately for at least two reasons. First, storing this information separately reduces the average size of the onodes 66. Streams 78, 80, 82 and 84 are not stored for each onode. As a result, the average size of the onodes decreases. Second, storing this information separately allows programmatic access to related groups of information without requiring complex code to retrieve the code from each onode 66.

Onodes 66 (FIG. 11) are stored in onode bucket arrays 102 (FIG. 13). The onode bucket array 102 is a variable-sized data structure that is composed of an array of fixed-sized buckets. The size of the buckets (e.g., 4K) depends on the architecture of the data processing system 10 but may match the page size of the system 10. The buckets are numbered 1 through N in the example of FIG. 13. Each bucket in the array 102 contains a packed set of onodes 66. In the example of FIG. 13, it can be seen that bucket 2 includes only a single onode, whereas bucket 1 includes two onodes and bucket 3 includes three onodes.

The onode bucket array 102 is used to minimize the amount of data that must be shuffled when file data is moved, deleted or inserted. The granularity of allocation and deallocation of blocks of disk space is fixed. In other words, memory blocks are allocated and deallocated in fixed-sizedd buckets. If, instead, a variable-sized structure was employed for storing file data, the granularity of allocation would not be fixed, and the granularity of allocation could become excessively large.

For efficiency, the operating system 24 (FIG. 1) stores related onodes 66 (FIG. 11) in the same buckets in the array 102 (FIG. 14) or in buckets that are in close proximity to each other on disk in disk storage 16. This storage strategy minimizes seek time in finding onodes 66 on disk. In general, files that are typically accessed together are placed into the same bucket. Examples of files that are accessed together include files in a common subdirectory or directory.

The onode bucket array 102 (FIG. 13) is accessed as a stream. The system 10 typically stores multiple onode bucket arrays 102 and, thus, stores multiple streams holding the onode bucket arrays. Internally, all references between onodes are based on work IDs. Locating an onode 66 (FIG. 11) within the bucket of an array 102 requires looking for a work ID for the onode. The work ID mapping array 104 (FIG. 14) maps from a work ID to a bucket number of the onode bucket array 102. The numbered bucket is then searched for an onode with a matching work ID. In particular, the work ID of a particular onode 66 serves an index into the work ID mapping array 104. The entry at the specified index identifies the bucket number that holds the onode 66. For example, as shown in FIG. 14, entries 106 and 108 of the work ID mapping array 104 hold values specifying that the onodes 66 having the associated work IDs are held in bucket 1.

Each onode 66 (FIG. 11) includes a name index stream that is stored among the streams held in the array of field descriptor 76. The name index stream holds a B-tree index for the stream descriptors contained within the onode 66. The name index stream uses the stream ID of a stream as a key for locating the stream descriptor held within the onode 66. The B-tree index is described in more detail in co-pending application entitled "Efficient Storage of Objects in a File System", Ser. No. 08/086,344 now U.S. Pat. No. 5,613,105, which was filed on even date herewith and is assigned to a common assignee. The disclosure of that co-pending application is explicitly incorporated by reference herein.

Just as related collection of streams are collected into onodes 66 (FIG. 11), related collections of onodes are collected into data structures known as object store catalogs. The work ID of an onode 66 serves as a basis for identifying any onode within an object store catalog. An object store catalog is described by an object store catalog onode 110, such as shown in FIG. 15. The object store catalog onode 110 includes the length field 68, the work ID field 70, flags field 72 and an array of field descriptors 76 as are found in other onodes 66. The array of field descriptors 76 includes field descriptors in which are stored stream descriptors 112, 114 and 116.

Stream descriptor 112 describes the work ID mapping array stream 104. Stream descriptor 114 describes the onode bucket array stream 102, and stream descriptor 116 describes the name index stream 117. Since the work ID mapping array stream 104 and the onode bucket array stream 102 store related data, they are stored in a common onode (i.e., the object store catalog onode 110). As such, the object store catalog onode 110 provides a vehicle for relating the work ID mapping array stream 104, the onode bucket array stream 102 and the name index stream 117. The object store catalog onode 110 is stored within the group of onodes that constitute the catalog at work ID 0. Work ID 0 is, by definition, always located in the first element of the onode bucket array stream 102. The first bucket at work ID 0 is a distinguished bucket having a known location. The data structures stored within the bucket are, thus, easily and simply accessed.

While the present invention has been described with reference to a preferred embodiment thereof, those skilled in the art will appreciate that various changes in detail and form may be made without departing from the present invention as defined in the appended claims.