Method and system for persistently cached, copy-on-write view of revision control trees

• US 9,069,792 B1
• Filed: 08/22/2008
• Issued: 06/30/2015
• Est. Priority Date: 08/22/2008
• Status: Active Grant

• Current Assignee: Conifer Systems LLC
• Original Assignee: Conifer Systems LLC
• Inventors: Craighead, Matthew J.
• Primary Examiner(s): Richardson, James E
• Application Number:
  US12/196,937
• Time in Patent Office: 2,503 Days
• Field of Search: 707/653, 707/657, 707/829, 707/638, 707/793
• US Class Current: 1/1
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files

Abstract

A method and system for efficient usage of revision control system resources by providing a client-based file system tree based on managed cache resources is provided. The managed cache resources include both a persistent, disk-based cache that maintains copies of requested file data from a repository server and an ordered tree data structure-based metadata cache for tracking file metadata across revisions. Embodiments of the present invention further maintain in the data cache data related only to specifically requested files. Embodiments of the present invention further track a range of versions of the file system tree for which particular file versions are applicable, so that unnecessary downloading to the client of unchanged files is avoided. Thus, file data and metadata are only requested from a repository server when needed and only a single version of a file is maintained until a modification to that file is made.

Claims

1. A method comprising:

receiving, from a version repository client, a first request for requested information stored in a repository of a revision control system, wherein the repository comprises a plurality of historical copies of information;

if the requested information is stored in local storage of the version repository client, providing the requested information from the local storage of the version repository client, wherein the local storage comprises a cache, a metadata cache, and non-cache storage, wherein the cache stores original file data received from the repository, and wherein the non-cache storage stores only modified copies of the file data stored in the cache; and

if the requested information is not stored in the local storage of the version repository client,

transmitting, from the version repository client, a second request for the requested information to a remote repository server coupled to the repository,

receiving the requested information from the remote repository server in response to the second request, and

in response to said receiving the requested information, providing the requested information and storing the requested information in the local storage of the version repository client, wherein storing the requested information comprises adding an added node to an ordered tree data structure in the metadata cache, wherein adding the added node to the ordered tree data structure in the metadata cache comprises removing a node from the ordered tree data structure to prevent the ordered tree data structure from exceeding a certain number of nodes, wherein nodes in the ordered tree data structure are ordered based upon how recently each node was used, wherein files in the cache are subject to eviction to make room for new files in the cache, and wherein modified versions of files in the non-cached storage are not subject to eviction from the non-cached storage.

2. The method of claim 1 wherein the requested information is metadata associated with a file.

3. The method of claim 2 further comprising:

if the requested information is stored in the metadata cache, retrieving the requested information from the metadata cache.

4. The method of claim 3 wherein said retrieving the requested information further comprises:

searching the ordered tree data structure, wherein the metadata cache is structured as the ordered tree data structure.

5. The method of claim 4 further comprising:

performing said searching using a revision number associated with the file, wherein

the first request comprises the revision number, and

the ordered tree data structure uses a range of revision numbers as keys associated with nodes of the ordered tree data structure.

6. The method of claim 3 wherein the metadata cache is stored in one of persistent memory or non-persistent memory.

7. The method of claim 2 wherein said receiving the requested information from the remote repository server further comprises:

receiving additional file information associated with one or more files in a same directory as the requested file information, wherein

the second request comprises a request for file information related to the requested information.

8. The method of claim 7 further comprising:

storing the additional file information in the local storage.

9. The method of claim 1 wherein

the added node has an associated node key that comprises a revision number associated with the file, and

the requested information is associated with the added node;

and

said storing the requested information in the metadata cache comprises;

examining nodes in the ordered tree data structure adjacent to the added node to determine if the metadata associated with one of the adjacent nodes is the same as the requested information associated with the added node; and

if the metadata associated with one of the adjacent nodes is the same as the requested information, extending a range of revision numbers in the node key of the adjacent node to include the revision number of the added node, and deleting the added node.

10. The method of claim 1 wherein

the added node has an associated key that comprises a range of revision numbers associated with the file, and

the requested information is associated with the added node;

and

said storing the requested information in the metadata cache comprises;

examining a node in the ordered tree data structure to determine if a key associated with the examined node is within the range of revision numbers associated with the added node; and

if the key associated with the examined node is within the range of revision numbers of the added node, deleting the examined node.

11. The method of claim 1 wherein

the added node has an associated key that comprises a range of revision numbers associated with the file, and

the requested information is associated with the added node;

and

said storing the requested information in the metadata cache comprises;

examining a node in the ordered tree data structure to determine if a key associated with the examined node is a range of revision numbers that overlaps with the range of revision numbers associated with the added node; and

if the key associated with the examined node overlaps the range of revision numbers associated with the added node, extending the range of revision numbers of the key of the examined node to include the range of revision numbers associated with the key of the added node, and deleting the added node.

12. The method of claim 1 wherein the requested information is data associated with a file.

13. The method of claim 12 further comprising:

retrieving the requested information from a persistent storage cache.

14. The method of claim 13 wherein said retrieving the requested information comprises:

providing a cache key associated with the file to a manager of the persistent storage cache, wherein

the cache key is generated using metadata associated with the file;

receiving the requested information if the data associated with the file is stored in the persistent storage cache; and

receiving an indication that the data associated with the file is not stored in the persistent storage cache if the data associated with the file is not stored in the persistent storage cache.

15. The method of claim 14 further comprising:

performing said transmitting the second request in response to said receiving an indication that the data associated with the file is not stored in the persistent storage cache.

16. The method of claim 12 wherein said storing the requested information in the local storage further comprises:

compressing the requested information; and

storing the compressed requested information in the local storage.

17. The method of claim 1 further comprising:

recording an identifier of the requested information in a list of accessed file information.

18. The method of claim 1, wherein the version repository client maintains a single copy of a file received from the repository in the local storage, if the file has not been modified by the version repository client subsequent to being received from the repository.

19. A system comprising:

a local storage configured to store information, wherein the local storage is a computer readable storage medium coupled to a version repository client, wherein the local storage comprises a cache, a metadata cache, and non-cache storage, wherein the cache stores original file data received from a repository of a revision control system, and wherein the non-cache storage stores only modified copies of the file data stored in the cache;

a processing device configured to implement a cache manager for the version repository client, coupled to the local storage, the cache manager comprising a cache manager processor module coupled to an interface module and a query interface module, wherein

the interface module is configured to receive a first request, from the version repository client, for requested information stored in the repository, wherein the repository comprises a plurality of historical copies of information,

the cache manager processor module is configured to

provide the requested information from the local storage if the requested information is stored in the local storage, and

if the requested information is not stored in the local storage,

transmit a second request, from the version repository client, for the requested information to a remote repository server, coupled to the repository, using the query interface module,

receive the requested information from the remote repository server using the query interface module in response to the second request, and

in response to said receiving the requested information, provide the requested information and store the requested information in the local storage, wherein storing the requested information comprises adding an added node to an ordered tree data structure in the metadata cache, wherein adding the added node to the ordered tree data structure in the metadata cache comprises removing a node from the ordered tree data structure to prevent the ordered tree data structure from exceeding a certain number of nodes, wherein nodes in the ordered tree data structure are ordered based upon how recently each node was used, wherein files in the cache are subject to eviction to make room for new files in the cache, and wherein modified versions of files in the non-cached storage are not subject to eviction from the non-cached storage, and

the query interface module is configured to transmit the second request to the remote repository server and receive the requested information from the remote repository server.

20. The system of claim 19 wherein the cache manager processor module is further configured to:

retrieve the requested information from the metadata cache, if the requested information is stored in the metadata cache, wherein

the requested information is metadata associated with a file.

21. The system of claim 20 wherein the cache manager processor module is further configured to:

search an ordered tree data structure to retrieve the requested information, wherein

the metadata cache is structured as the ordered tree data structure,

said searching is performed using a revision number associated with the file,

the first request comprises the revision number, and

the ordered tree data structure uses a range of revision numbers as keys associated with nodes of the ordered tree data structure.

22. The system of claim 20 wherein the metadata cache is stored in one of persistent memory or non-persistent memory.

23. The system of claim 20 wherein the cache manager processor module is configured to receive the requested information from the remote repository server by being further configured to:

receive additional file information associated with one or more files in a same directory as the requested file information, wherein

the second request comprises a request for file information related to the requested information; and

store the additional file information in the local storage.

24. The system of claim 19 wherein

the added node has an associated key that comprises a revision number associated with the file, and

the requested information is associated with the added node;

and

the cache manager processor module is configured to store the requested information in the metadata cache by being further configured to;

examine nodes in the ordered tree data structure adjacent to the added node to determine if the metadata associated with one of the adjacent nodes is the same as the requested information associated with the added node; and

if the metadata associated with one of the adjacent nodes is the same as the requested information, extend a range of revision numbers in the key of the adjacent node to include the revision number of the added node, and delete the added node.

25. The system of claim 19 wherein

the added node has an associated key that comprises a range of revision numbers associated with the file, and

the requested information is associated with the added node;

and

the cache manager processor module is configured to store the requested information in the metadata cache by being further configured to;

examine a node in the ordered tree data structure to determine if a key associated with the examined node is within the range of revision numbers associated with the added node; and

if the key associated with the examined node is within the range of revision numbers of the added node, delete the examined node.

26. The system of claim 19 wherein the cache manager processor module is further configured to:

retrieve the requested information from a persistent storage cache, wherein the requested information is data associated with a file, and

the local storage is the persistent storage cache.

27. The system of claim 26 wherein the cache manager processor module is further configured to:

provide a cache key associated with the file to a manager of the persistent storage cache, wherein

the cache key is generated using metadata associated with the file;

receive the requested information if the data associated with the file is stored in the persistent storage cache; and

receive an indication that the data associated with the file is not stored in the persistent storage cache if the data associated with the file is not stored in the persistent storage cache.

28. The system of claim 27 wherein the cache manager processor module is further configured to:

perform said transmitting the second request in response to said receiving an indication that the data associated with the file is not stored in the persistent storage cache.

29. A non-transitory computer readable storage medium comprising:

a first set of instructions, executable by a processor, configured to receive, from a version repository client, a first request for requested information stored in a repository of a revision control system, wherein the repository comprises a plurality of historical copies of information;

a second set of instructions, executable by the processor, configured to determine whether the requested information is stored in a local storage of the version repository client, wherein the local storage comprises a cache, a metadata cache, and non-cache storage, wherein the cache stores original file data received from the repository, and wherein the non-cache storage stores only modified copies of the file data stored in the cache;

a third set of instructions, executable by the processor, responsive to determining that the requested information is stored in the local storage of the version repository client and configured to provide the requested information from the local storage of the version repository client; and

a fourth set of instructions, executable by the processor, responsive to determining that the requested information is not stored in the local storage and configured to

transmit, from the version repository client, a second request for the requested information to a remote repository server coupled to the repository, receive the requested information from the remote repository server in response to the second request, and, in response to said receiving the requested information, provide the requested information and store the requested information in the local storage of the version repository client, wherein storing the requested information comprises adding an added node to an ordered tree data structure in the metadata cache, wherein adding the added node to the ordered tree data structure in the metadata cache comprises removing a node from the ordered tree data structure to prevent the ordered tree data structure from exceeding a certain number of nodes, wherein nodes in the ordered tree data structure are ordered based upon how recently each node was used, wherein files in the cache are subject to eviction to make room for new files in the cache, and wherein modified versions of files in the non-cached storage are not subject to eviction from the non-cached storage.

30. The non-transitory computer readable storage medium of claim 29 further comprising:

a fifth set of instructions, executable by the processor, configured to retrieve the requested information from the metadata cache, wherein the requested information is metadata associated with a file.

31. The non-transitory computer readable storage medium of claim 30 wherein the fifth set of instructions further comprises:

a sixth set of instructions, executable by the processor, configured to search an ordered tree data structure, wherein

the metadata cache is structured as the ordered tree data structure,

said searching uses a revision number associated with the file,

the first request comprises the revision number, and

the ordered tree data structure uses a range of revision numbers as keys associated with nodes of the ordered tree data structure.

32. The non-transitory computer readable storage medium of claim 30 wherein the metadata cache is stored in one of persistent memory or non-persistent memory.

33. The non-transitory computer readable storage medium of claim 30 wherein the fourth set of instructions further comprises:

a sixth set of instructions, executable by the processor, configured to receive additional file information associated with one or more files in a same directory as the requested file information, wherein

the second request comprises a request for file information related to the requested information; and

a seventh set of instructions, executable by the processor, configured to store the additional file information in the local storage.

34. The non-transitory computer readable storage medium of claim 29 wherein

the added node has an associated key that comprises a revision number associated with the file, and

the requested information is associated with the added node;

and

the sixth set of instructions further comprises;

an eighth set of instructions, executable by the processor, configured to examine nodes in the ordered tree data structure adjacent to the added node to determine if the metadata associated with one of the adjacent nodes is the same as the requested information associated with the added node; and

a ninth set of instructions, executable by the processor, configured to extend a range of revision numbers in the key of the adjacent node to include the revision number of the added node and delete the added node, if the metadata associated with one of the adjacent nodes is the same as the requested information.

35. The non-transitory computer readable storage medium of claim 29 wherein

the added node has an associated key that comprises a range of revision numbers associated with the file, and

the requested information is associated with the added node;

and

the sixth set of instructions further comprises;

an eighth set of instructions, executable by the processor, configured to examine a node in the ordered tree data structure to determine if a key associated with the examined node is within the range of revision numbers associated with the added node; and

a ninth set of instructions, executable by the processor, configured to delete the examined node if the key associated with the examined node is within the range of revision numbers of the added node.

36. The non-transitory computer readable storage medium of claim 29 further comprising:

a fifth set of instructions, executable by the processor, configured to retrieve the requested information from a persistent storage cache, wherein

the requested information is data associated with a file, and

the local storage is the persistent storage cache.

37. The non-transitory computer readable storage medium of claim 36 wherein the fifth set of instructions further comprises:

a sixth set of instructions, executable by the processor, configured to provide a cache key associated with the file to a manager of the persistent storage cache, wherein

the cache key is generated using metadata associated with the file;

a seventh set of instructions, executable by the processor, configured to receive the requested information if the data associated with the file is stored in the persistent storage cache; and

an eighth set of instructions, executable by the processor, configured to receive an indication that the data associated with the file is not stored in the persistent storage cache if the data associated with the file is not stored in the persistent storage cache.

38. The non-transitory computer readable storage medium of claim 37 wherein the fifth set of instructions further comprises:

a ninth set of instructions, executable by the processor, configured to perform said transmitting the second request in response to the indication provided by the eighth set of instructions.