System and method for chunk-based indexing of file system content

• US 7,487,138 B2
• Filed: 08/25/2004
• Issued: 02/03/2009
• Est. Priority Date: 08/25/2004
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Borthakur, Dhrubajyoti, Pashenkov, Serge
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Saeed; Usmaan
• Application Number:
  US10/926,432
• Publication Number:
  US 20060059171A1
• Time in Patent Office: 1,623 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A system and method for chunk-based indexing of file system content. In one embodiment, the system may include a storage device configured to store data and a file system configured to manage access to the storage device and to store file system content including a plurality of files. The system may further include a search engine configured to construct an index of the file system content. The file system may be further configured to partition a given one of the plurality of files into a plurality of logical chunks, and constructing an index may include generating respective index information associated with each of the plurality of logical chunks.

Claims

1. A system, comprising:

a storage device configured to store data; and

a file system configured to manage access to said storage device and to store file system content including a plurality of files to said storage device; and

a search engine configured to construct an index of said file system content;

wherein said file system is further configured to partition a given one of said plurality of files into a plurality of logical chunks, wherein given ones of said logical chunks include structured data records formatted according to a self-describing data format, wherein each of said structured data records includes one or more data elements delimited by respective tag fields, wherein said tag fields are defined according to said self-describing data format;

wherein to partition said given file, said file system is further configured to adjust a chunk boundary between two adjacent given ones of said logical chunks such that said chunk boundary falls between boundaries of said structured data records;

wherein to construct said index, said search engine is further configured to generate respective index information associated with each of said plurality of logical chunks, such that boundaries of said respective index information correspond to boundaries of said logical chunks;

wherein for each given one of said plurality of logical chunks, said respective index information is indicative of one or more data patterns occurring within said given logical chunk of said given file; and

wherein in response to detecting an operation to modify said given file, said file system is further configured to identify one or more modified logical chunks of said given file, and wherein said search engine is further configured to regenerate respective index information associated with each of said one or more modified logical chunks without regenerating respective index information for one or more logical chunks of said given file that are unmodified by said operation.

2. The system as recited in claim 1, wherein said file system is further configured to associate a respective modification identifier with each of said logical chunks and to assert said respective modification identifier in response to modifying a corresponding logical chunk of said given file, and wherein said search engine is further configured to regenerate respective index information associated with a given logical chunk dependent upon said respective modification identifier.

3. The system as recited in claim 1, wherein said file system is further configured to associate a respective last modification time with each of said logical chunks and to update said respective last modification time in response to modifying a corresponding logical chunk of said given file, and wherein said search engine is further configured to regenerate respective index information associated with a given logical chunk dependent upon said last modification time.

4. The system as recited in claim 3, wherein for said given logical chunk, said search engine is further configured to compare a last modification time included in said respective index information associated with said given logical chunk with said respective last modification time provided by said file system, and to regenerate said respective index information in response to determining that said respective last modification time provided by said file system is more recent than said last modification time included in said respective index information.

5. The system as recited in claim 1, wherein each of said logical chunks is of a fixed and uniform size.

6. The system as recited in claim 1, wherein said logical chunks vary in size.

19. The system as recited in claim 1, wherein to adjust said chunk boundary between said two adjacent given ones of said logical chunks, said file system is further configured to adjust said chunk boundary such that said chunk boundary falls between instances of said tag fields.

20. The system as recited in claim 1, wherein said self-describing data format comprises Extensible Markup Language (XML).

7. A computer implemented method, comprising:

a file system storing file system content including a plurality of files to a storage device, wherein said file system is configured to manage access to said storage device;

said file system partitioning a given one of said plurality of files into a plurality of logical chunks, wherein given ones of said logical chunks include structured data records formatted according to a self-describing data format, wherein each of said structured data records includes one or more data elements delimited by respective tag fields, wherein said tag fields are defined according to said self-describing data format;

wherein said file system partitioning said given file comprises said file system adjusting a chunk boundary between two adjacent given ones of said logical chunks such that said chunk boundary falls between boundaries of said structured data records;

a search engine constructing an index of said file system content, wherein said constructing includes generating respective index information associated with each of said plurality of logical chunks such that boundaries of said respective index information correspond to boundaries of said logical chunks, and wherein for each given one of said plurality of logical chunks, said respective index information is indicative of one or more data patterns occurring within said given logical chunk of said given file;

in response to detecting an operation to modify said given file, said file system identifying one or more modified logical chunks of said given file; and

said search engine regenerating respective index information associated with each of said one or more modified logical chunks without regenerating respective index information for one or more logical chunks of said given file that are unmodified by said operation.

8. The method as recited in claim 7, further comprising:

said file system associating a respective modification identifier with each of said logical chunks;

said file system asserting said respective modification identifier in response to modifying a corresponding logical chunk of said given file; and

said search engine regenerating respective index information associated with a given logical chunk dependent upon said respective modification identifier.

9. The method as recited in claim 7, further comprising:

said file system associating a respective last modification time with each of said logical chunks;

said file system updating said respective last modification time in response to modifying a corresponding logical chunk of said given file; and

said search engine regenerating respective index information associated with a given logical chunk dependent upon said last modification time.

10. The method as recited in claim 9, further comprising:

said search engine comparing a last modification time included in said respective index information associated with said given logical chunk with said respective last modification time associated with said given logical chunk; and

said search engine regenerating said respective index information in response to determining that said respective last modification time provided by said file system is more recent than said last modification time included in said respective index information.

11. The method as recited in claim 7, wherein each of said logical chunks is of a fixed and uniform size.

12. The method as recited in claim 7, wherein said logical chunks vary in size.

21. The method as recited in claim 7, wherein said file system adjusting said chunk boundary between said two adjacent given ones of said logical chunks comprises said file system adjusting said chunk boundary such that said chunk boundary falls between instances of said tag fields.

22. The method as recited in claim 7, wherein said self-describing data format comprises Extensible Markup Language (XML).

13. A computer-accessible storage medium comprising program instructions, wherein the program instructions are executable to implement:

a file system storing file system content including a plurality of files to a storage device, wherein said file system is configured to manage access to said storage device;

said file system partitioning a given one of said plurality of files into a plurality of logical chunks, wherein given ones of said logical chunks include structured data records formatted according to a self-describing data format, wherein each of said structured data records includes one or more data elements delimited by respective tag fields, wherein said tag fields are defined according to said self-describing data format; and

wherein said file system partitioning said given file comprises said file system adjusting a chunk boundary between two adjacent given ones of said logical chunks such that said chunk boundary falls between boundaries of said structured data records;

a search engine constructing an index of said file system content, wherein said constructing includes generating respective index information associated with each of said plurality of logical chunks such that boundaries of said respective index information correspond to boundaries of said logical chunks, and wherein for each given one of said plurality of logical chunks, said respective index information is indicative of one or more data patterns occurring within said given logical chunk of said given file;

in response to detecting an operation to modify said given file, said file system identifying one or more modified logical chunks of said given file; and

said search engine regenerating respective index information associated with each of said one or more modified logical chunks without regenerating respective index information for one or more logical chunks of said given file that are unmodified by said operation.

14. The computer-accessible storage medium as recited in claim 13, wherein the program instructions are further executable to implement:

said file system associating a respective modification identifier with each of said logical chunks;

said file system asserting said respective modification identifier in response to modifying a corresponding logical chunk of said given file; and

said search engine regenerating respective index information associated with a given logical chunk dependent upon said respective modification identifier.

15. The computer-accessible storage medium as recited in claim 13, wherein the program instructions are further executable to implement:

said file system associating a respective last modification time with each of said logical chunks;

said file system updating said respective last modification time in response to modifying a corresponding logical chunk of said given file; and

said search engine regenerating respective index information associated with a given logical chunk dependent upon said last modification time.

16. The computer-accessible storage medium as recited in claim 15, wherein the program instructions are further executable to implement:

said search engine comparing a last modification time included in said respective index information associated with said given logical chunk with said respective last modification time associated with said given logical chunk; and

said search engine regenerating said respective index information in response to determining that said respective last modification time provided by said file system is more recent than said last modification time included in said respective index information.

17. The computer-accessible storage medium as recited in claim 13, wherein each of said logical chunks is of a fixed and uniform size.

18. The computer-accessible storage medium as recited in claim 13, wherein said logical chunks vary in size.

23. The computer-accessible storage medium as recited in claim 13, wherein said file system adjusting said chunk boundary between said two adjacent given ones of said logical chunks comprises said file system adjusting said chunk boundary such that said chunk boundary falls between instances of said tag fields.

24. The computer-accessible storage medium as recited in claim 13, wherein said self-describing data format comprises Extensible Markup Language (XML).