Apparatus and method for building a file system index

• US 7,783,615 B1
• Filed: 09/30/2005
• Issued: 08/24/2010
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Popov, Nikolay, Fridella, Stephen A., Gupta, Uday K., Compton, James T., Rago, Stephen A., Doohkan, Surrendranath R.
• Primary Examiner(s): Pardo; Thuy N
• Application Number:
  US11/241,132
• Time in Patent Office: 1,789 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/10, 707/101, 707/102, 707/202, 358/448, 709/217
• US Class Current: 707/694
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06

Abstract

An improved policy enforcement architecture includes several components that improve the performance of policy enforcement in a hierarchical storage environment. A File System Query instruction permits a richer set of queries to be expressed by a policy engine, thereby permitting more complex policies to be implemented with ease. The File System result is generated at the file server, and only files of interest are forwarded to the policy engine. The file system query advantageously may be applied against a pre-generated index having one more characterizing attributes to further reduce the processing required to retrieve policy data. An Index Build instruction, added to a programming interface, allows a policy engine generate the characterizing indices in advance of use. Index maintenance techniques maintain consistency between the index and the file system to ensure that the policy can be enforced using accurate file information.

Claims

1. A method of providing an index associated with a policy used by a policy engine to a subset of files in a file system stored on a computer readable medium, wherein each index is associated with a key attribute and wherein the method includes the steps of:

receiving, at the file server, a request by the policy engine to build the index to characterize files for the policy enforcement, the request including the key attribute associated with the index, wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system from one storage device to another to enforce the policy; and

for each file in the file system;

retrieving a file identifier and a key attribute value of the file; and

storing the file identifier in the index in order of key attribute value.

2. The method of claim 1, wherein the request includes an index order indicating one of an ascending or descending key attribute value order.

3. The method of claim 1, wherein the request includes a limit indicating a number of file identifiers to be included in the index.

4. The method of claim 1, wherein the request includes an update policy indicator.

5. The method of claim 1, wherein the identifier includes an inode number.

6. The method of claim 1, wherein the identifier includes an inode parent list.

7. The method of claim 1, wherein the index is stored as a Btree data structure, and wherein index entries are added to the index using Btree techniques.

8. The method according to claim 1, wherein the index is stored in the file system.

9. The method according to claim 1, wherein the request includes an index identifier, and wherein the method further includes the step of storing the index identifier and an identifier of the key attribute in an index list.

10. A method of providing an index associated with a policy used by a policy engine to a subset of files in a file system stored on a computer readable medium, wherein each index is associated with a key attribute and wherein the method includes the steps of:

receiving, at the file server, a request by the policy engine to build the index to characterize files for the policy enforcement, the request including the key attribute associated with the index as well as a selector which defines a shared attribute characteristic for the files of interest to the index, wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system from one storage device to another to enforce the policy; and

for each file in the file system;

retrieving a file identifier and a key attribute value of the file;

determining if the file shares the attribute characteristic defined by the selector; and

responsive to the file sharing the attribute characteristic defined by the selector, storing the file identifier in the index in order of key attribute value.

11. An application programming interface, stored in a computer readable medium of a file server, includes:

program code operable when executed in response to a build index request by a policy engine to generate an index associated with a policy used by the policy engine to characterize files for the policy enforcement to a subset of files in a file system served by the file server, wherein the index is associated with a key attribute and lists files in the file system in order of key attribute value and wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system from one storage device to another to enforce the policy.

12. The application programming interface of claim 11, wherein the build index request includes a selector defining a shared attribute characteristic for the files of interest to the index, and wherein the application programming interface includes program code operable to filter key attribute values using the selector for storage in the index.

13. A file server including:

an application programming interface for receiving policy communications from a policy engine including a build index request, wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system from one storage device to another to enforce the policy;

an index generator, coupled to application programming interface, for generating an index associated with a policy used by the policy engine to characterize files for the policy enforcement to a subset of files in a file system served by the file server in response to receipt of the build index request from the application programming interface, wherein the index is associated with a key attribute and lists files in the file system in order of key attribute value; and

storage for storing the index.

14. The file server of claim 13, wherein the build index request includes a selector which defines a shared attribute characteristic for the files of interest to the index, and wherein the index generator includes a filter for filtering key attribute values using the selector to provide filtered file identifiers for storage in the index.

15. The file server of claim 13, wherein the request includes an index order, and wherein the index generator includes means, responsive to the index order, for storing listing file identifiers in the index in one of ascending or descending key attribute value order.

16. The file server of claim 13, wherein the request includes an update policy indicator, and wherein the file server includes means for updating the index in accordance with the update policy.

17. The file server of claim 13, wherein the index includes a plurality of index entries, each index entry including an inode number.

18. The file server of claim 13, wherein the index includes a plurality of index entries, each index entry including an inode parent list.

19. The file server of claim 13, wherein the index is stored in the file system of the file server.

20. The file server of claim 13, wherein the request includes an index limit identifying a number of entries to be included in the index.

21. The file server of claim 13 further including:

means for storing an index identifier associated with the index list and key attribute.

22. A file system stored on a computer readable medium comprising:

an index data structure associated with a key attribute and at least one shared attribute characteristic of files in a file system, the index data structure including a list of files of the file system having the at least one shared attribute characteristic to characterize files according to a policy used by a policy engine, the list of files being stored in key attribute value order, wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system based on the policy from one storage device to another to enforce the policy.

23. The file system according to claim 22, wherein the at least one shared attribute characteristic is related to a migration policy associated with the file system.

24. A file server comprising a computer readable medium having program code stored thereon, the program code including:

a file system build index instruction associated with a policy used by a policy engine, the file system build index instruction comprising a command and a key attribute, the file system build index instruction operable when executed by the policy engine evaluating a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrating the files in a file system from one storage device to another to cause the file server to;

retrieve a file identifier and a key attribute value of the file; and

store the file identifier in the index in order of key attribute value.

25. A file server comprising a computer readable medium having program code stored thereon, the program code including:

a file system build index instruction associated with a policy used by a policy engine, the file system build index instruction operable when executed by the policy engine to build an index to characterize files for the policy enforcement, the build index instruction comprising a command, a key attribute and a selector which defines a shared attribute characteristic for file of interest to the index, the file system build index instruction operable when executed to cause the file server to build an index by, for each file in the file system, wherein the policy engine evaluates a metadata of the file system wherein the metadata includes attributes associated with the files in the file system and based on the evaluation with regard to the criteria associated with a policy migrates the files in a file system from one storage device to another to enforce the policy;

retrieving a file identifier and a key attribute value of the file;

determining if the file shares the attribute characteristic defined by the selector; and

responsive to the file sharing the attribute characteristic defined by the selector, storing the file identifier in the index in order of key attribute value.

26. The file server of claim 25, wherein the file server is a policy server, and the key attribute and selector are selected according to a file migration policy of the policy server.