Space allocation in a write anywhere file system

• US 7,930,326 B2
• Filed: 10/03/2007
• Issued: 04/19/2011
• Est. Priority Date: 08/18/2000
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Lewis, Blake, Doucette, Douglas P., Edwards, John K.
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US11/866,957
• Publication Number:
  US 20080028011A1
• Time in Patent Office: 1,294 Days
• Field of Search: 707200-205, 707/822, 707/823, 707/824, 711/114
• US Class Current: 707/822
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A file system determines the relative vacancy of a collection of storage blocks, i.e., an “allocation area”. This is accomplished by recording an array of numbers, each of which describes the vacancy of a collection of storage blocks. The file system examines these numbers when attempting to record file blocks in relatively contiguous areas on a storage medium, such as a disk. When a request to write to disk occurs, the system determines the average vacancy of all of the allocation areas and queries the allocation areas for individual vacancy rates. The system preferably writes file blocks to the allocation areas that are above a threshold related to the average storage block vacancy of the file system.

Claims

1. A method comprising:

identifying a multi-block storage region as satisfying a block vacancy criterion, the multi-block storage region being one of a plurality of multi-block storage regions of a file system in a data storage system, each multi-block storage region comprising a plurality of mass storage devices, by

computing a value that represents an amount of block vacancy in said multi-block storage region based on identifying, using a block vacancy map of a current state of the file system and a block vacancy map of at least one past state of the file system, each block allocated on a mass storage device in said multi-block storage region during the current state and each block allocated on the mass storage device in said multi-block storage region during the at least one past state, and

determining that the value has a particular relationship to an allocation threshold; and

in response to identifying the multi-block storage region as satisfying the block vacancy criterion, selecting the multi-block storage region as a destination for data to be written.

2. A method as recited in claim 1, further comprising:

writing data into the selected multi-block storage region in response to the multi-block storage region being selected.

3. A method as recited in claim 1, further comprising setting the allocation threshold based on how many storage blocks are available for writing data in the file system.

4. A method as recited in claim 3, wherein the value corresponds to a number of free blocks in said multi-block storage region in the file system according to the current state and a snapshot of the file system at a past point in time.

5. A method as recited in claim 4, wherein said selecting comprises selecting the multi-block region because the value corresponding to said region exceeds the allocation threshold.

6. A method as recited in claim 1, further comprising:

performing said computing, for each of a plurality of different multi-block storage regions of the file system, to generate a different value for each said multi-block storage region.

7. A method as recited in claim 6, comprising linearly searching the plurality of multi-block storage regions of the file system to select a first region with the corresponding value exceeding the threshold.

8. A method comprising:

mapping storage blocks of a mass storage system into a plurality of multi-block storage regions of a file system, each multi-block storage region comprising a plurality of mass storage devices;

for each of the plurality of multi-block storage regions of the file system, computing a value that represents an amount of block vacancy in said multi-block storage region to produce a plurality of values, each value corresponding to a different one of the plurality of multi-block storage regions, said computing based on identifying, using a block vacancy map of a current state of the file system and a block vacancy map of at least one past state of the file system, each block allocated on a mass storage device in said multi-block storage region during the current state and each block allocated on the mass storage device in said multi-block storage region during the at least one past state;

identify a multi-block storage region, of the plurality of multi-block regions, as satisfying a block vacancy criterion, by determining that the value corresponding to said region exceeds an allocation threshold;

in response to identifying the multi-block storage region as satisfying the block vacancy criterion, selecting the multi-block storage region as a destination for data to be written; and

writing data into the selected multi-block storage region after said multi-block storage region is selected.

9. A method as recited in claim 8, further comprising:

setting the allocation threshold based on how many storage blocks of the file system are available for writing data.

10. A method as recited in claim 9, wherein the value corresponds to a number of free blocks in said multi-block storage region in the file system according to the current state and a snapshot of the file system at a past point in time.

11. A method as recited in claim 10, wherein said selecting comprises selecting the multi-block region because the value corresponding to said region exceeds the allocation threshold.

12. A method as recited in claim 11, comprising linearly searching the plurality of multi-block storage regions of the file system to select a first region with the corresponding value exceeding the threshold.

13. An apparatus comprising:

a mass storage system to store data; and

a file system that manages a plurality of storage blocks stored in the mass storage system, the file system being configured to

for each of a plurality of multi-block storage regions of the file system, wherein each multi-block storage region comprises a plurality of mass storage devices, compute a value that represents an amount of block vacancy in said multi-block storage region to produce a plurality of values, each corresponding to a different one of the plurality of multi-block storage regions, said computing based on identifying, using a block vacancy map of a current state of the file system and a block vacancy map of at least one past state of the file system, each block allocated on a mass storage device in said multi-block storage region during the current state and each block allocated on the mass storage device in said multi-block storage region during the at least one past state;

identify a multi-block storage region, of the plurality of multi-block regions, as satisfying a block vacancy criterion, by determining that the value corresponding to said region has a particular relationship to an allocation threshold; and

in response to identifying the multi-block storage region as satisfying the block vacancy criterion, select the multi-block storage region as a destination for data to be written.

14. An apparatus as recited in claim 13, wherein the file system is further configured to write data into the selected multi-block storage region in response to the multi-block storage region being selected.

15. An apparatus as recited in claim 13, wherein the file system is further configured to set the allocation threshold based on how many storage blocks are available for writing data in the file system.

16. An apparatus as recited in claim 15, wherein the value corresponds to a number of free blocks in said multi-block storage region in the file system according to the current state and a snapshot of the file system at a past point in time.

17. An apparatus as recited in claim 16, wherein said selection comprises selecting the multi-block region because the value corresponding to said region exceeds the allocation threshold.

18. An apparatus as recited in claim 15, wherein the file system is configured to linearly search the plurality of multi-block storage regions of the file system to select a first region with the corresponding value exceeding the threshold.