Efficient storage of objects in a file system

• US 5,613,105 A
• Filed: 06/30/1993
• Issued: 03/18/1997
• Est. Priority Date: 06/30/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Berkowitz, Brian T., Zbikowski, Mark, Ferguson, Robert I.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lewis, Cheryl
• Application Number:
  US08/086,344
• Time in Patent Office: 1,357 Days
• Field of Search: 395/600, 395/425, 395/575, 395/700, 395/275, 395/400
• US Class Current: 1/1
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 20/1252 for discontinuous data, e.g. digital information signals, computer programme data
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 27/329 on a disc [VTOC]

Abstract

A file system provides a hierarchical approach to storage of file data. Logically contiguous bytes of file data are stored in stream data structures, and streams which hold related file data are stored in a variable sized onode data structures on disk. The variable-sized onode data structures are stored in fixed sized buckets, and the buckets are organized into a variable sized array. Thus, the file system provides a combination of variable-sized storage with fixed-sized storage to provide a very efficient approach to storing file data. In addition, indexes may be provided within the structures to allow quick access to onodes and streams.

Claims

1. In a file system in a data processing system having secondary storage divided into sectors, a method of storing contents of files in the secondary storage, comprising the steps of:

providing a sequence of fixed-sized file system data structures of a data type that is specifically designed for storing contents of the files on the secondary storage wherein said fixed-sized file system data structures are distinct from the sectors of the secondary storage;

storing a first set of contents of files that are logically related of a first size in a first variable-sized file system data structure of a given structure type on the secondary storage; and

storing the first variable-sized file system data structure of the given structure type in which the first set of contents of files that are logically related are stored in at least one of the fixed-sized file system data structures on the secondary storage.

2. The method recited in claim 1, further comprising the steps of:

storing a second set of contents of files that are logically related of a second size in a second variable-sized file system data structure of the given structure type; and

storing the second variable-sized file system data structure of the given structure type in which the second set of contents of files that are logically related are stored in the fixed-sized file system data structure in which the first set of contents of files that are logically related are stored.

3. The method recited in claim 1 wherein the step of providing the sequence of fixed-sized file system data structures further comprises the step of providing a variable-sized array of the fixed-sized file system data structures.

4. The method recited in claim 1 wherein the secondary storage is disk storage.

5. The method recited in claim 1, further comprising the step of storing property information about the first variable-sized file system data structure of the given structure type in the secondary storage.

6. The method recited in claim 5, further comprising the step of querying the first variable-sized file system data structure of the given structure type to obtain the property information stored therein.

7. The method recited in claim 1, further comprising the step of storing an identification in the variable-sized file system data structure of the given structure type that uniquely identifies the first variable-sized file system data structure of the given type stored in the fixed-sized file system data structure.

8. A data processing system, comprising:

internal memory;

secondary storage divided into sectors;

a file system for managing files;

a sequence of fixed-sized file system data structures for storing contents of files wherein said fixed-sized file system data structures are distinct from the sectors of the secondary storage;

means for storing a first set of contents of files that are logically related in a first variable-sized file system data structure of a given structure type; and

means for storing the first variable-sized file system data structure in which the first set of contents of files that are logically related are stored in at least one of the fixed-sized file system data structures.

9. A data processing system as recited in claim 8, further comprising:

means for storing a second set of contents of files that are logically related in a second variable-sized file system data structure of the given structure type; and

means for storing the second variable-sized file system data structure of the given structure type in which the second set of contents of files that are logically related are stored in the fixed-sized file system data structure in which the first set of contents of files that are logically related are stored.

10. The data processing system of claim 8 wherein the secondary storage is disk storage.

11. The data processing system of claim 8, further comprising means for storing property information about the first variable-sized file system data structure of the given structure type in the secondary storage.

12. The data processing system of claim 11, further comprising means for querying the first variable-sized file system data structure of the given structure type to obtain the property information stored therein.

13. In a file system in a data processing system having secondary storage divided into sectors, a method comprising the steps of:

storing logically contiguous bytes of files in variable-sized data structures of a first type;

storing sets of the variable-sized data structures of the first type in which are stored related files in a variable-sized data structure of a second type; and

storing the variable-sized data structure of the second type in a fixed-sized data structure wherein the fixed-sized data structure is independent of the sectors of the secondary storage.

14. The method recited in claim 13 wherein the step of storing logically contiguous bytes of files in variable-sized data structures of the first type further comprises the step of storing an identifier in each data structure of the first type to uniquely identify the logically contiguous bytes stored in the variable-sized structure of the first type among the variable-sized data structures of the first type held in a same one of the variable-sized data structure of the second type.

15. The method recited in claim 13 wherein the secondary storage is disk storage and the step of storing the variable-sized data structures of the second type in a fixed-sized data structures further comprises the step of storing the variable-sized data structures of the second type in fixed-sized data structures in the disk storage.

16. The method recited in claim 13, further comprising the step of storing property information in the secondary storage for each of the variable-sized data structures of the second type.

17. The method recited in claim 16, further comprising the step of querying one of the variable-sized data structures of the second type to obtain the property information contained therein.

18. A data processing system comprising:

internal storage;

secondary storage having memory space divided into logical partitions of multiple bytes;

a file system for managing files;

means for storing logically contiguous bytes of files in variable-sized file system data structures of a first type in the internal storage;

means for storing sets of the variable-sized file system data structures of the first type that hold related files in variable-sized file system data structures of a second type in the internal storage; and

means for storing the variable-sized file system data structures of the second type in fixed-sized data structures in the internal storage.

19. In a data processing system having secondary storage and a file system for managing files, a method comprising the steps of:

storing sets of logically contiguous bytes of file data in respective variable-sized file system data structures of a first type;

storing variable-sized file system data structures of the first type which store related files in a variable-sized file system data structure of a second type in the secondary storage; and

storing a B-tree index to the variable-sized data structures of the first type in the variable-sized file system data structure of the second type in the secondary storage.

20. The method recited in claim 19, further comprising the step of locating logically contiguous bytes of files in the variable-sized file system data structure of the second type in the secondary storage by accessing the B-tree index.

21. The method recited in claim 19 wherein the step of storing the B-tree index to the variable-sized file system data structures of the first type in the variable-sized file system data structure of the second type in the secondary storage further comprises the step of storing the B-tree index to the variable-sized file system data structures of the first type in the variable-sized file system data structure of the second type in the secondary storage as a variable-sized file system data structure of the first type.

22. In a data processing system having secondary storage and a file system for managing files, a method comprising the steps of:

storing logically contiguous bytes of files in variable-sized file system data structures of a first type;

storing variable-sized file system data structures of a second type in the secondary storage wherein each variable-sized file system data structure of the second type stores a set of the variable-sized file system data structures of the first type that store files; and

in each variable-sized file system data structure of the second type, storing a B-tree index to the variable-sized file system data structures of the first type stored in the variable-sized file system data structure of the second type.

23. In a data processing system having a file system for managing files, secondary storage that includes memory space divided into sectors which holds an array of fixed-size buckets file system data structures that are distinct from the sectors and one of the buckets holds an object, a method of allocating additional memory space in the secondary storage to fulfill growing requirements of the object, comprising the steps of:

determining whether the bucket that currently holds the object has sufficient free memory space to fulfill the growing requirements of the object;

when the bucket that currently holds the object has sufficient free memory space, allocating additional space in the bucket to the object to fulfill the growing requirements of the object; and

otherwise, finding a bucket that has sufficient memory space to fulfill the growing requirements of the object and moving the object to the found bucket.

24. The method of claim 23 wherein the step of finding a bucket that has sufficient memory space to fulfill the growing requirements of the object further comprises finding a bucket that has sufficient memory space to fulfill the growing requirements of the object that is in closest proximity in the secondary storage to the bucket that currently holds the object.

25. In a data processing system having secondary storage divided into sectors and a file system for managing files, a method comprising the steps of:

storing files in an array of fixed-sized buckets of storage space in the secondary storage wherein the buckets are defined by the file system and are distinct from the sector and wherein at least one of the fixed-sized buckets of storage space has more than one file stored in it;

providing an identifier for each file that identifies the file among those stored in the array;

storing a map in the secondary storage that maps each identifier for a file into the fixed-sized bucket in which the file is stored;

locating one of the files having a selected identifier in the array by using the map to locate the fixed-sized bucket in which the file is stored and searching the fixed-sized bucket to locate the file having the selected identifier.

26. In a data processing system having secondary storage that is divided into sectors and a file system for managing files, a method comprising the steps of:

storing files in array of fixed-sized buckets of storage space in the secondary storage wherein said buckets are defined by the file system and are distinct from the sectors and wherein each file has an identifier associated with it;

storing a file system mapping structure of multiple entries in the secondary storage, said entries including at least one entry that maps another of the identifiers to one of the buckets in the array;

storing in the file system mapping structure a free list of identifiers of cells of space in the secondary storage that are unallocated; and

using the file system mapping structure to locate a bucket from the identifier of the bucket.

27. The method recited in claim 26, further comprising the step of using the file system mapping structure to locate an identifier in the free list.

28. In a data processing system having secondary storage that is divided into sectors and a file system for managing files, a method comprising the steps of:

providing an array of fixed-sized buckets of storage space in the secondary storage wherein said buckets are defined by the file system and are distinct from the sectors and for storing files, each file having an identifier associated with it;

providing a file system mapping structure of multiple entries in the secondary storage for mapping identifiers to either cells in a free list or to the fixed-sized buckets in the array;

providing the free list in the file system mapping structure, said free list including identifiers of any free cells of space in the secondary storage;

determining if the free list contains an identifier for at least one cell; and

where the free list contains an identifier for at least one cell, assigning a selected identifier of a cell from the free list to a new file and storing the new file in the cell.

29. The method recited in claim 28, further comprising the step of:

where the free list contains no cells,

adding additional entries to the file system mapping structure that map new identifiers to new free cells.

30. The method recited in claim 29, further comprising the steps of:

assigning one of the new identifiers associated with one of the new free cells to the new file; and

storing the new file in the new free cell associated with the new identifier that is assigned to the new file.