Storage management system with file aggregation and space reclamation within aggregated files

• US 6,021,415 A
• Filed: 10/29/1997
• Issued: 02/01/2000
• Est. Priority Date: 10/29/1997
• Status: Expired due to Term

• Current Assignee: HGST Netherlands B.V. (Western Digital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Cannon, David Maxwell, Martin, Howard Newton
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/960,601
• Time in Patent Office: 825 Days
• Field of Search: 707/200, 707/205, 707/206, 707/202, 711/165
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A data storage subsystem employs managed files, each comprising one or an aggregation of multiple constituent user files, to reduce file management overhead costs. After receiving user files from a client station, the subsystem creates a contiguous managed file by aggregating selected ones of the received user files according to certain predetermined criteria. Managed file creation and use are transparent to the client stations. Eventually, unused or "deleted-file space" arises as individual user files are deleted from their respective managed files. "Reclamation" is triggered when the amount of deleted-file space in a prescribed storage area (e.g. device, volume, managed file, etc.) satisfies certain criteria, e.g. poor data storage efficiency. Reclamation is performed to regain wasted space between managed files, and also space that occurs within managed files due to deletion of some but not all constituent user files. Reclamation is applied to the prescribed storage area one managed file at a time. Each managed file is reviewed to determine whether it contains any deleted-file space. Managed files without any deleted-file space are simply copied intact to the target storage area. If a managed file contains deleted-file space, however, a "reconstruction" process is performed for that file. Reconstruction identifies any contiguous regions of user files within the managed file, then copies the contiguous regions to adjacent locations in a target storage area. Reclamation is complete after all managed files in the prescribed data storage area have been copied or reconstructed.

Claims

1. A method of reclaiming deleted-file storage space within a managed file originally created with a contiguous aggregation of user files, said deleted-file storage space arising from deletion of individual user files from the managed file, said managed file residing at a source storage area, the method comprising:

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in a target storage area.

2. The method of claim 1, the source and target storage areas having no storage space in common.

3. The method of claim 1, the source and target storage areas substantially identical.

4. The method of claim 1, where:

prior to reclaiming deleted-file storage space of the managed file, the managed file and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

5. The method of claim 1, the method further comprising:

maintaining a managed. file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

6. The method of claim 5, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

7. The method of claim 5, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

8. The method of claim 1, the method further comprising:

evaluating the managed file by applying predetermined criteria to deleted-file storage space in the managed file.

9. The method of claim 8, responsive to the deleted-file storage space failing the predetermined criteria, aborting reclamation of deleted-file storage space.

10. The method of claim 9,

the application of the predetermined criteria comprising determining a ratio between storage space occupied by non-deleted user files in the managed file and total storage space in the managed file;

the predetermined criteria being satisfied when the ratio exceeds a predetermined threshold.

11. The method of claim 8, the evaluating of the managed file being performed in response to expiration of a timer.

12. The method of claim 8, the evaluating of the managed file being performed in response to an operator request.

13. The method of claim 8, the managed file being stored in a first data storage unit, the evaluating of the managed file being performed in response to an absence of available storage space in the first data storage unit.

14. The method of claim 8, the evaluating of the managed file being performed in response to deletion of a user file in the managed file.

15. The method of claim 8,

the method further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating of the managed file being performed in response to a change in the managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.

16. A method of reclaiming a source storage area to a target storage area, said source storage area including one or more managed files, each managed file including one or more user files, said method comprising:

evaluating the source storage area by determining whether data storage efficiency therein exceeds predetermined criteria;

if the storage area fails the predetermined criteria, performing a reclamation process, said reclamation process comprising, for each managed file in the source storage area;

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in a target storage area to form a reconstructed managed file.

17. The method of claim 16, the source storage area comprising a volume of data.

18. The method of claim 16, the source storage area comprising a data storage device.

19. The method of claim 16, the reclamation process forming all reconstructed managed files in contiguous arrangement in the target storage area.

20. The method of claim 16, the source and target storage areas having no storage space in common.

21. The method of claim 16, the source and target storage areas substantially identical.

22. The method of claim 16, where:

the managed files of the source area and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

23. The method of claim 16, the method further comprising:

maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

24. The method of claim 23, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

25. The method of claim 23, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

26. The method of claim 16, responsive to the data storage efficiency passing the predetermined criteria, aborting reclamation of the source storage area.

27. The method of claim 16,

the data storage efficiency comprising a ratio between storage space occupied by non-deleted user files in the source storage area and total storage space in the source storage area;

the predetermined criteria being satisfied when the ratio surpasses a predetermined threshold.

28. The method of claim 16, the evaluating being performed in response to expiration of a timer.

29. The method of claim 16, the evaluating being performed in response to an operator request.

30. The method of claim 16, the evaluating being performed in response to an absence of available storage space in the unit.

31. The method of claim 16, the evaluating being performed in response to deletion of a user file from a managed file in the source area.

32. The method of claim 16,

further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating being performed in response to a change in a managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.

33. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for reclaiming deleted-file storage space within a managed file originally created with a contiguous aggregation of user files, said deleted-file storage space arising from deletion of individual user files from the managed file, said managed file residing at a source storage area, said method comprising:

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in a target storage area.

34. The medium of claim 33, the source and target storage areas having no storage space in common.

35. The medium of claim 33, the source and target storage areas substantially identical.

36. The medium of claim 33, where:

prior to reclaiming deleted-file storage space of the managed file, the managed file and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

37. The medium of claim 33, the method further comprising:

maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

38. The medium of claim 37, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

39. The medium of claim 37, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

40. The medium of claim 33, the method further comprising:

evaluating the managed file by applying predetermined criteria to deleted-file storage space in the managed file.

41. The medium of claim 40, responsive to the deleted-file storage space failing the predetermined criteria, aborting reclamation of deleted-file storage space.

42. The medium of claim 41,

the application of the predetermined criteria comprising determining a ratio between storage space occupied by non-deleted user files in the managed file and total storage space in the managed file;

the predetermined criteria being satisfied when the ratio exceeds a predetermined threshold.

43. The medium of claim 40, the evaluating of the managed file being performed in response to expiration of a timer.

44. The medium of claim 40, the evaluating of the managed file being performed in response to an operator request.

45. The medium of claim 40, the managed file being stored in a first data storage unit, the evaluating of the managed file being performed in response to an absence of available storage space in the first data storage unit.

46. The medium of claim 40, the evaluating of the managed file being performed in response to deletion of a user file in the managed file.

47. The medium of claim 40,

the method further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating of the managed file being performed in response to entry of a change in the managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.

48. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for consolidating a unit of stored data from a source location to a target location, said unit including multiple managed files, each managed file including one or more user files, said method comprising:

evaluating the source storage area by determining whether data storage efficiency therein exceeds predetermined criteria;

if the storage area fails the predetermined criteria, performing a reclamation process, said reclamation process comprising, for each managed file in the source storage area;

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in a target storage area to form a reconstructed managed file.

49. The medium of claim 48, the source storage area comprising a volume of data.

50. The medium of claim 48, the source storage area comprising a data storage device.

51. The medium of claim 48, the reclamation process forming all reconstructed managed files in contiguous arrangement in the target storage area.

52. The medium of claim 48, the source and target storage areas having no storage space in common.

53. The medium of claim 48, the source and target storage areas substantially identical.

54. The medium of claim 48, where:

the managed files and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

55. The medium of claim 48, the method further comprising:

maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

56. The medium of claim 48, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

57. The medium of claim 55, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

58. The medium of claim 48, responsive to the data storage efficiency passing the predetermined criteria, aborting reclamation of the source storage area.

59. The medium of claim 48,

the data storage efficiency comprising a ratio between storage space occupied by non-deleted user files in the source storage area and total storage space in the source storage area;

the predetermined criteria being satisfied when the ratio surpasses a predetermined threshold.

60. The medium of claim 48, the evaluating being performed in response to expiration of a timer.

61. The medium of claim 48, the evaluating being performed in response to an operator request.

62. The medium of claim 48, the evaluating being performed in response to an absence of available storage space in the unit.

63. The medium of claim 48, the evaluating being performed in response to deletion of a user file from a managed file in the source area.

64. The medium of claim 53,

further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating being performed in response to a change in a managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.

65. A data storage subsystem, comprising:

a storage hierarchy including a source storage area and a target storage area; and

a digital data processing apparatus coupled to the storage hierarchy;

wherein the digital data processing apparatus is programmed to perform a method for reclaiming deleted-file storage space within a managed file originally created with a contiguous aggregation of user files, said deleted-file storage space arising from deletion of individual user files from the managed file, said managed file residing in the source storage area, the method comprising;

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in the target storage area.

66. The apparatus of claim 65, the source and target storage areas having no storage space in common.

67. The apparatus of claim 65, the source and target storage areas substantially identical.

68. The apparatus of claim 65, where:

prior to reclaiming deleted-file storage space of the managed file, the managed file and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

69. The apparatus of claim 65, the method further comprising:

maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

70. The apparatus of claim 69, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

71. The apparatus of claim 69, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

72. The apparatus of claim 65, the method further comprising:

evaluating the managed file by applying predetermined criteria to deleted-file storage space in the managed file.

73. The apparatus of claim 72, responsive to the deleted-file storage space failing the predetermined criteria, aborting reclamation of deleted-file storage space.

74. The apparatus of claim 73,

the application of the predetermined criteria comprising determining a ratio between storage space occupied by non-deleted user files in the managed file and total storage space in the managed file;

the predetermined criteria being satisfied when the ratio exceeds a predetermined threshold.

75. The apparatus of claim 72, the evaluating of the managed file being performed in response to expiration of a timer.

76. The apparatus of claim 72, the evaluating of the managed file being performed in response to an operator request.

77. The apparatus of claim 72, the managed file being stored in a first data storage unit, the evaluating of the managed file being performed in response to an absence of available storage space in the first data storage unit.

78. The apparatus of claim 72, the evaluating of the managed file being performed in response to deletion of a user file in the managed file.

79. The apparatus of claim 72,

the method further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating of the managed file being performed in response to a change in the managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.

80. A data storage subsystem, comprising:

a storage hierarchy including a source location and a target location; and

a digital data processing apparatus coupled to the storage hierarchy;

wherein the digital data processing apparatus is programmed to perform a method for consolidating a unit of stored data from the source location to the target location, said unit including multiple managed files, each managed file including one or more user files, said method comprising;

evaluating the source storage area by determining whether data storage efficiency therein exceeds predetermined criteria;

if the storage area fails the predetermined criteria, performing a reclamation process, said reclamation process comprising, for each managed file in the source storage area;

determining whether the managed file contains any deleted-file storage space;

in response to finding deleted-file storage space, performing a process of reconstructing the managed file comprising;

identifying contiguous regions of non-deleted user files within the managed file; and

copying each identified contiguous region to adjacent locations in a target storage area to form a reconstructed managed file.

81. The subsystem of claim 80, the source storage area comprising a volume of data.

82. The subsystem of claim 80, the source storage area comprising a data storage device.

83. The subsystem of claim 80, the reclamation process forming all reconstructed managed files in contiguous arrangement in the target storage area.

84. The subsystem of claim 80, the source and target storage areas having no storage space in common.

85. The subsystem of claim 80, the source and target storage areas substantially identical.

86. The subsystem of claim 80, where:

the managed files of the source area and all user files therein are represented in (1) a mapping table including a first table listing, for each user file, a corresponding location of that user file within the managed file, and (2) a storage table cross-referencing each managed file with an address in the subsystem containing that managed file; and

the copying of each identified contiguous region to adjacent locations in a target storage area further includes updating the mapping table and storage table to indicate presence of the managed file and its user files in the target storage area.

87. The subsystem of claim 80, the method further comprising:

maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files.

88. The subsystem of claim 87, the method further comprising:

updating the managed file attributes table for a particular managed file in response to deletion of any user file of the particular managed file.

89. The subsystem of claim 87, the method further comprising:

updating the managed file attributes table for a particular managed file in response to the copying of the particular managed file.

90. The subsystem of claim 80, responsive to the data storage efficiency passing the predetermined criteria, aborting reclamation of the source storage area.

91. The subsystem of claim 90,

the data storage efficiency comprising a ratio between storage space occupied by non-deleted user files in the source storage area and total storage space in the source storage area;

the predetermined criteria being satisfied when the ratio surpasses a predetermined threshold.

92. The subsystem of claim 80, the evaluating being performed in response to expiration of a timer.

93. The subsystem of claim 80, the evaluating being performed in response to an operator request.

94. The subsystem of claim 80, the evaluating being performed in response to an absence of available storage space in the unit.

95. The subsystem of claim 80, the evaluating being performed in response to deletion of a user file from a managed file in the source area.

96. The subsystem of claim 80,

further comprising maintaining a managed file attributes table including a representation of each managed file along with the managed file'"'"'s total storage space and storage space occupied by non-deleted files;

the evaluating being performed in response to a change in a managed file'"'"'s storage space occupied by non-deleted files in the managed file attributes table.