Space allocation in a write anywhere file system

• US 6,636,879 B1
• Filed: 08/18/2000
• Issued: 10/21/2003
• Est. Priority Date: 08/18/2000
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Lewis, Blake, Edwards, John K., Doucette, Douglas P.
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Mofiz, Apu M
• Application Number:
  US09/642,065
• Time in Patent Office: 1,159 Days
• Field of Search: 707/201, 707/202, 707/203, 707/204, 707/205, 360/48, 369/30.09, 711/165, 711/173, 714/4, 714/6
• US Class Current: 707/690
• 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 method and system for improving data access of a reliable file system is provided. In a first aspect of the invention, the file system determines the relative vacancy of a collection of storage blocks, herein called an “allocation area”. This is accomplished by recording an array of binary numbers. Each binary number in the array describes the vacancy of a collection of storage blocks. The file system examines these binary numbers when attempting to record file blocks in relatively contiguous areas on a storage medium, such as a hard disk. When a request to write to disk occurs, the system determines the average vacancy of all the allocation areas and queries the allocation areas for individual vacancy rates such as sequentially. 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. If the file in the request to write is larger than the selected allocation area, the next allocation area above the threshold is preferably used to write the remaining blocks of the file.

Claims

1. A method for improved space allocation in a write anywhere file system, including a file system having a set of storage blocks in a mass storage system, including

maintaining an active map of said storage blocks not available for writing data;

recording a consistency point in said file system including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time;

determining, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to said active map and a summary map; and

selecting at least one of said plurality of regions in response to said spacemap.

2. A method as in claim 1, wherein said corresponding value is responsive to a numerical comparison between a number of storage blocks available for writing data in said region and a number of storage blocks available for writing data in said mass storage system.

3. A method as in claim 1, wherein said active map is a bit map.

4. A method as in claim 1, wherein said corresponding value is responsive to an average of the number of storage blocks available for writing data, in response to said active map and at least one said copy of active map at a previous time.

5. A method as in claim 1, wherein said selecting is performed on a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

6. A method as in claim 1, wherein said corresponding value responsive to a number of storage blocks is a binary number.

7. A method as in claim 6, wherein said corresponding value determined for one of said regions is a binary number stored in a data block containing one or more of said binary numbers each corresponding to a unique region.

8. A method for improved space allocation in a write anywhere file system, including a file system having a set of storage blocks in a mass storage system, including

maintaining a collection of bit maps responsive to the set of storage blocks available for writing data;

determining, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to at least two bitmaps included in said collection of bitmaps;

selecting at least one of said plurality of regions in response to said spacemap; and

writing at least part of a file composed of a collection of file blocks to the selected one of said plurality of regions.

9. A method as in claim 8, wherein writing said collection of file blocks is to at least one of said plurality of regions.

10. A method as in claim 8, wherein said selecting is performed on a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

11. A method as in claim 8, wherein said writing is to a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

12. A method as in claim 8, including additional selecting when said writing does not contain an entire said collection of file blocks.

13. A method as in claim 8, wherein said corresponding value is responsive to an average of the number of storage blocks available for writing data, in response to said bit map.

14. An apparatus for improved space allocation in a write anywhere file system, including a file system that has a set of storage blocks in a mass storage system;

wherein

said file system maintains an active map of one of said storage blocks not available to write data;

said file system records a consistency point which includes a consistent version of said file system at a previous time, said consistency point includes a copy of said active map at said previous time;

said file system determines, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to said active map and a summary map; and

said file system selects at least one of said plurality of regions in response to said spacemap.

15. An apparatus as in claim 14, wherein said value that corresponds to said plurality of regions is responsive to a numerical comparison between a number of storage blocks available to write data in said region and a number of storage blocks available to write data in said mass storage system.

16. An apparatus as in claim 14, wherein said active map is a bit map.

17. An apparatus as in claim 14, wherein said value that corresponds to said plurality of regions is responsive to an average of the number of storage blocks available to write data, in response to said active map and at least one said copy of active map at a previous time.

18. An apparatus as in claim 14, wherein said file system selects a first of said plurality of regions that satisfies said value in a linear search of said plurality of regions.

19. An apparatus for improved space allocation in a write anywhere file system, including a file system having a set of storage blocks in a mass storage system including

means for maintaining an active map of said storage blocks not available for writing data;

means for recording a consistency point including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time;

means for determining, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to said active map and a summary map; and

means for selecting at least one of said plurality of regions in response to said spacemap.

20. An apparatus as in claim 19, wherein said corresponding value is responsive to a numerical comparison between a number of storage blocks available for writing data in said region and a number of storage blocks available for writing data in said mass storage system.

21. An apparatus as in claim 19, wherein said active map is a bit map.

22. An apparatus as in claim 19, wherein said corresponding value is responsive to an average of the number of storage blocks available for writing data, in response to said active map and at least one said copy of active map at a previous time.

23. An apparatus as in claim 19, wherein said selecting is performed on a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

24. An apparatus as in claim 19, wherein said corresponding value responsive to a number of storage blocks is a binary number.

25. An apparatus as in claim 19, wherein said corresponding value determined for one of said regions is a binary number stored in a data block containing one or more of said binary numbers each corresponding to a unique region.

26. An apparatus as in claim 19, wherein a collection of said corresponding value is stored in one or more of said data storage blocks.

27. A memory storing information including instruction, the instructions for improved space allocation in a write anywhere file system, including a file system having a set of storage blocks in a mass storage system, the instructions including the steps of

maintaining an active map of said storage blocks not available for writing data;

recording a consistency point in said file system including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time;

determining, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to said active map and a summary map; and

selecting at least one of said plurality of regions in response to said spacemap.

28. A memory as in claim 27, wherein said corresponding value is responsive to a numerical comparison between a number of storage blocks available for writing data in said region and a number of storage blocks available for writing data in said mass storage system.

29. A memory as in claim 27, wherein said active map is a bit map.

30. A memory as in claim 27, wherein said corresponding value is responsive to an average of the number of storage blocks available for writing data, in response to said active map and at least one said copy of active map at a previous time.

31. A memory as in claim 27, wherein said selecting is performed on a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

32. A memory as in claim 27, wherein said corresponding value responsive to a number of storage blocks is a binary number.

33. A memory as in claim 27, wherein said corresponding value determined for one of said regions is a binary number stored in a data block containing one or more of said binary numbers each corresponding to a unique region.

34. A memory storing information including instruction, the instructions for improved space allocation in a write anywhere file system, including a file system having a set of storage blocks in a mass storage system, the instructions including the steps of

maintaining a collection of bit maps responsive to the set of storage blocks available for writing data;

determining, for each one of a plurality of regions of said storage blocks in said mass storage system, a spacemap including an array of binary numbers, each said binary number being count related to a number of blocks available or not available for writing data in one of said regions, wherein said spacemap is responsive to at least two bitmaps included in said collection of bitmaps;

selecting at least one of said plurality of regions in response to said spacemap; and

writing at least part of a file composed of a collection of file blocks to the selected one of said plurality of regions.

35. A memory as in claim 34, wherein writing said collection of file blocks is to at least one of said plurality of regions.

36. A memory as in claim 34, wherein said selecting is performed on a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

37. A memory as in claim 34, wherein said writing is to a first of said plurality of regions satisfying said value in a linear search of said plurality of regions.

38. A memory as in claim 34, wherein said instructions include additional selecting when said writing does not contain an entire said collection of file blocks.

39. A memory as in claim 34, wherein said corresponding value is responsive to an average of the number of storage blocks available for writing data, in response to said bit map.