Caching in a data processing system using the pigeon hole principle

• US 6,094,706 A
• Filed: 03/02/1998
• Issued: 07/25/2000
• Est. Priority Date: 03/02/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation, Minimed, Inc. (Medtronic Plc)
• Original Assignee: International Business Machines Corporation
• Inventors: Farchi, Eitan Daniel, Factor, Michael Edward
• Primary Examiner(s): Peikari, Behzad James
• Assistant Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US09/033,326
• Time in Patent Office: 876 Days
• Field of Search: 711/113, 711/118, 711/158, 711/703, 711/202, 711/112, 707/6, 707/200
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Methods and apparatus for resolving access patterns in a data processing system using the pigeon hole principle are disclosed herein. The data processing system has a directed graph G of access patterns including a vertices set V representing cache items. Each cache item v has an access pattern defined by a path of vertices (v₁ → , . . . , →v_n), v₁ representing the start of the path and v_n representing the end of the path at cache item v. The method includes defining a prefix cache for directed graph G which contains a map between an access pattern (v₁ → , . . . , →v_k) and vertex v_k for a kth level L in graph G, storing the prefix cache in a memory and, for a given access pattern (v₁ → , . . . , →v_n), searching the prefix cache for a prefix (v₁ → , . . . , →v_k) of the given access pattern that reaches the kth level L. If the search is successful, the method includes outputting vertex v_k by reference to the stored prefix cache and calling an access pattern resolution primitive which accepts access pattern (v_k+1 → , . . . , →v_n) as an input and generates vertex v_n as an output. If the search is unsuccessful, the method includes setting the input to the resolution primitive to the given access pattern (v₁ → , . . . , →v_n) to generate vertex v_n as the output. In either case, the given access pattern (v₁ → , . . . , →v_n) is fully resolved. Apparatus for performing this method is also disclosed. A particular use of the pigeon hole principle for caching in a data processing system involves the resolution of hierarchical file pathnames into in-core representations of the files named by the paths (i.e., namespace resolution) using prefix caching.

Claims

1. In a computer including a hierarchical file structure having a namespace including a pathname associated with each of a plurality of files, the pathname for each file including at least one prefix component and at least one lower-level component, an apparatus for resolving hierarchical file pathnames into representations of the files named by the paths, comprising:

a memory storing a prefix cache for the hierarchical file structure which includes a representation of an upper-level portion of the namespace for the file structure, the upper-level portion of the namespace including the at least one prefix component of the pathname for each of the files;

means for translating the at least one prefix pathname component for the given file into the representation of the upper-level portion of the namespace for the given file by searching the prefix cache for the at least one prefix pathname component; and

means for completing resolution of the pathname for the given file when the translation succeeds by using the at least one lower-level pathname component for the given file as an input to an access pattern resolution primitive which outputs a representation of the given file.

2. The apparatus of claim 1 further comprising means for resolving the pathname for the given file when the translation does not succeed by using the entire pathname of the given file, including its prefix and lower-level components, as an input to the access pattern resolution primitive which outputs the representation of the given file.

3. The apparatus of claim 2 further comprising means for counting each time a prefix pathname component stored in the prefix cache is reached.

4. The apparatus of claim 3 further comprising means for adding new pathnames to the prefix cache that contain the particular pathname component when the respective counter for a particular prefix pathname component reaches a predetermined threshold.

5. A method for resolving access patterns in a data processing system having a directed graph G of access patterns, directed graph G including a vertices set V representing a plurality of cache items, each cache item v having at least one access pattern defined by a path of vertices (v₁ →

, . . . , →

v_n), vertex v₁ being a start vertex representing the start of the path and vertex v_n being an end vertex representing the end of the path, wherein end vertex v_n is equal to the cache item v, the method comprising the steps of;

defining a prefix cache for directed graph G, the prefix cache containing a map between an access pattern (v₁ →

, . . . , →

v_k) and vertex v_k for a kth level L in graph G, wherein vertex v_k is a vertex in the kth level L in graph G which is reached by the access pattern (v₁ →

, . . . , →

v_k) and L is an independent set of vertices in G which does not include any start vertices;

storing the prefix cache in a memory; and

for a given access pattern (v₁ →

, . . . , →

v_n), searching the stored prefix cache for a prefix (v₁ →

, . . . , →

v_k) of the given access pattern that reaches the kth level L and, if the search is successful, outputting vertex v_k by reference to the stored prefix cache and calling an access pattern resolution primitive which accepts access pattern (v_k >

, . . . →

v_n) as an input and generates vertex v_n as an output to fully resolve the given access pattern.

6. The method of claim 5 wherein, if the search was not successful, the method comprises setting the input to the access pattern resolution primitive to the given access pattern (v₁ →

, . . . →

v_n) to generate vertex v_n as the output, wherein the given access pattern (v₁ →

, . . . , →

v_n) is fully resolved.

7. A method for namespace resolution of a given file in a data processing system having a hierarchical file structure, the file structure having a namespace including a pathname associated with each of a plurality of files, the pathname for each file including at least one prefix component and at least one lower-level component, the method comprising the steps of:

defining a prefix cache for the hierarchical file structure, the prefix cache including a representation of an upper-level portion of the namespace for the file structure, the upper-level portion of the namespace including the at least one prefix component of the pathname for each of the files;

storing the prefix cache in a memory;

translating the at least one prefix pathname component for the given file into the representation of the upper-level portion of the namespace for the given file by searching the prefix cache for the at least one prefix pathname component; and

when the translation succeeds, completing resolution of the pathname for the given file by using the at least one lower-level pathname component for the given file as an input to an access pattern resolution primitive which outputs a representation of the given file named by the pathname.

8. The method of claim 7 wherein, when the translation does not succeed, the method comprises resolving the pathname for the given file by using the entire pathname of the given file, including its prefix and lower-level components, as an input to the access pattern resolution primitive which outputs the representation of the given file named by the pathname.

9. The method of claim 8 wherein the prefix cache stores a subset of pathnames that start at a root directory and have a limited length such that the upper-level portion of the namespace starts at the root directory.

10. The method of claim 9 wherein the prefix cache further stores a representation of the file or directory named by each pathname in the subset of pathnames which is stored in the prefix cache.

11. The method of claim 10 wherein the representation of each file or directory stored in the prefix cache is its in-core representation (i.e., vnode).

12. The method of claim 11 wherein the translation of the at least one prefix pathname component for the given file generates the vnode of the file or directory named by the at least one prefix pathname component.

13. The method of claim 12 further comprising the step of tuning the prefix cache by adjusting the number of pathname components stored therein.

14. The method of claim 13 wherein the tuning step includes adjusting the number of characters stored at each level of the prefix cache.

15. The method of claim 8 wherein the translation starts at a root directory of the namespace and the pathname is absolute.

16. The method of claim 8 wherein the translation starts at a current working directory in the namespace and the pathname is relative.

17. The method of claim 8 wherein, when the translation succeeds, at least a portion of the pathname is resolved without accessing an on-disk representation of the pathname.

18. The method of claim 8 further comprising the step of updating a respective counter each time a prefix pathname component stored in the prefix cache is reached.

19. The method of claim 18 wherein, when the respective counter for a particular prefix pathname component reaches a predetermined threshold, the method further comprises the step of adding new pathnames to the prefix cache that contain the particular pathname component.

20. The method of claim 8 wherein a portion of the namespace resides on a remote data processing system such that the namespace is a distributed namespace.