Systems and methods for caching with file-level granularity

[0002] The present invention relates to implementing improved disk caching strategies in a computer. In particular, the present invention relates to a method for designating files as memory-resident, transient, or neither memory resident nor transient and appropriately caching the disk blocks associated with a designated file.

[0003] When operating, computers typically utilize three types of memory. Persistent memories that are not based on optical or magnetic media, e.g., EEPROM or Flash ROM, store the Basic Input/Output System (BIOS), boot parameters, and other startup routines. A volatile memory such as RAMBUS dynamic RAM (RDRAM) or synchronous dynamic RAM (SDRAM) stores data and programs presently in use, e.g., the operating system. A persistent memory typically using optical or magnetic media stores data and programs that are not presently in use.

[0004] The differences between the technologies implementing the different memory types offer advantages and disadvantages. Memories based on optical or magnetic media retain information in the absence of electrical power. Volatile memories like SDRAM require electrical power to retain information, but typically offer faster access times. Persistent ROM memories offer faster access times and retain information in the absence of electrical power, but have limited storage capacity and operate mostly as read-only devices.

[0005] Recognizing the different advantages offered by different memory types, operating system designers have developed various techniques to permit software applications to achieve fast access to data while maintaining copies of the data that will survive the removal of electrical power. One family of techniques is called “disk caching.” Disk caching attempts to retain certain selected data in volatile memory while storing other data in a persistent storage device. Since volatile memory for caching is typically limited in size relative to the memory available in a persistent storage device, designers of disk caching algorithms must decide which data to cache and which data to store in slower, persistent memory.

[0006] Some prior art computer systems address this problem by implementing RAM disk functionality. Referring to FIG. 1, a typical prior art computer system 10 includes a microprocessor 12, a-memory 14, and an input/output (I/O) controller 16 connected by a system bus 18. The system bus 18 permits one or more of these interconnected components to communicate through the exchange of data. For example, the microprocessor 12 may send read or write requests to the memory 14 or the I/O controller 16.

[0007] The memory 14 in a prior art computer 10 itself typically includes three types of memory. RAM 20 stores data and programs presently in use. Programs can be a user application 36, an operating system 26, or a device driver such as a disk driver 28. ROM 22 stores the BIOS 30 and other boot routines. The mass storage device 32 provides a persistent memory typically using optical or magnetic media.

[0008] Performance-critical applications using large amounts of data, such as database systems, store data on mass storage device 32. However, mass storage device 32 typically has slower access times than RAM 20. Therefore, a performance-critical application should use as much RAM 20 storage as possible. Purchasing and installing a solid-state mass storage device (not shown) will also result in a performance gain, but these devices tend to be expensive and have access times inferior to RAM 20 storage.

[0009] Typically, a performance-critical application is designed and coded to use RAM 20 storage. However, an operating system 26 using a virtual memory system to redirect memory operations from RAM 20 to mass storage 32 will redirect the read and write transactions from the application, hindering its performance. A virtual memory system can be bypassed by using a RAM disk scheme, setting aside a portion of RAM 20 for use as a virtual disk volume. User applications 36 interact with the RAM disk 34 as if it were a disk volume on a mass storage device 32, but having significantly improved access times. Using a RAM disk scheme ensures that performance-critical applications access RAM 20 without undertaking special programming measures.

[0010] The RAM disk approach has drawbacks. For example, in some RAM disk implementations, disk blocks stored in the RAM disk 34 are duplicated in the disk cache 24. This unnecessary duplication wastes space in RAM 20 and potentially saturates cache 24, further hindering accesses to files in mass-storage 32. Moreover, RAM disks have volume-level granularity: all the files on the virtual volume must be stored in RAM disk 34. It is generally not possible to set the attributes of individual files to ensure they stay in RAM 20, while marking other files for storage in mass storage 32. Therefore, it is desirable to provide functionality to designate individual files to ensure that they are encached in RAM 20 or stored in mass storage 32.

[0011] The present invention relates to the problem of disk caching for improved access to data files. One object of the invention is to provide methods for caching disk blocks on a per-file basis. Another object of the invention is to permit individual users or software applications to designate files as memory-resident or transient. Yet another object of the invention is to provide a programmed computer that can cache disk blocks on a per-file basis.

[0012] In one aspect, the present invention is a method for improved access to data files. First, a portion of volatile memory is designated for use as a cache memory. After the cache is established, files are designated as memory-resident. Data blocks and index blocks associated with memory-resident files are maintained in the cache memory. In one embodiment, a file can be designated memory-resident while it is in use by a software application. In another embodiment, the memory-resident state of the file can be set by a user or by a software application. In yet another embodiment, maintaining blocks associated with memory-resident files in cache memory includes the steps of accessing a data block or an index block associated with a memory-resident file and storing the contents of the block in the cache memory. In one embodiment, the volatile memory for the cache is random-access memory (RAM). In another embodiment, the memory-resident cache is a sub-cache of a designated cache memory. In yet another embodiment, users or software applications can modify the size of the memory-resident cache. In one embodiment, it is possible to set a maximum size for the memory-resident cache, and disk blocks are removed from the cache when the maximum size is exceeded. In another embodiment, it is possible to designate a memory-resident file as not memory-resident, and data blocks and index blocks associated with the file are subsequently subject to default caching methods, making them more likely to be removed from cache memory when demand exceeds capacity.

[0013] In another aspect, the present invention is a method for improved access to data files. First, a portion of volatile memory is designated for use as a cache memory. After the cache is established, files are designated transient. Data blocks and index blocks corresponding to transient files are maintained in cache memory for a nominal duration. In one embodiment, blocks associated with transient files are not written to mass storage until the passage of the nominal period of time, whereupon they are written and subsequently removed from cache memory. In another embodiment, a file can be designated transient while being accessed by a software application. In yet another embodiment, a user or software application can designate a file as transient. In one embodiment, the volatile memory for the cache is random-access memory (RAM). In another embodiment, it is possible to designate a transient file as not transient, and data blocks and index blocks associated with the file are subsequently subject to default caching methods, making them less likely to be removed from cache memory when demand exceeds capacity.

[0014] In still another aspect, the present invention is a programmed computer with an improved caching system. The computer includes a non-volatile memory having a file. The file has at least one disk block and an attribute field corresponding to the state of the file as memory-resident or transient. The computer also includes a volatile memory having a cache containing disk blocks associated with memory-resident files. The volatile memory also has queue structures containing data structures that correspond to the data blocks stored in the cache. These data structures are only removed from the queue when required by size limits imposed on the cache. In one embodiment, the size limits imposed on the cache may be increased or decreased. In another embodiment, the disk block is an index block or a data block associated with the file. In another embodiment, the queue is a first queue composed of data structures corresponding to disk blocks associated with memory resident files, and a second queue composed of data structures corresponding to disk blocks associated with transient files.

[0015] These and other advantages of the invention may be more clearly understood with reference to the specification and the drawings, in which:

[0016] FIG. 1 is a block diagram of a prior art system with RAM disk functionality;

[0017] FIG. 2 is a block diagram of a prior art system with a disk cache with block-level granularity;

[0018] FIG. 3 is a block diagram of an embodiment of a computer constructed in accord with the present invention;

[0019] FIG. 4 is a diagram depicting the bits for a parameter value passed with an opcode used to control the treatment of individual files as memory-resident or transient;

[0020] FIG. 5 is a block diagram of a computer embodying the present invention with two phy queues to support memory-resident and transient file caching;

[0021] FIGS. 6 and 6A are a flowchart describing an embodiment whereby a user designates a file memory-resident;

[0022] FIG. 7 is a flowchart describing a transaction relating to a memory-resident file; and

[0023] FIG. 8 is a flowchart describing the queue management techniques periodically executed by the cache manager 50.

[0024] In the drawings, like reference characters generally refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

[0025] In brief overview, Applicant's invention provides systems and methods for implementing improved disk caching in a programmed computer. Improved disk caching is achieved through apparatus and methods that permit the designation of files as memory-resident, transient, or normal (i.e., neither memory-resident nor transient). The disk blocks associated with a memory-resident file are loaded immediately into cache memory in whole or in part, or are loaded on a block-by-block basis as they are accessed. The blocks of a memory-resident file remain in cache until the file is designated not memory-resident, whereupon the blocks become purgeable, or until cache size limits force the removal of blocks from the cache. The blocks are purged immediately in whole or in part, or displaced gradually as blocks from memory-resident files displace them. Disk blocks associated with a transient file that have been encached remain in the cache for a short, predetermined period of time before they are expired, removing them from the cache. If the contents of the block have changed while encached, then expiration is followed by writing the updated contents of the block to mass storage. Disk blocks associated with a file that is neither memory resident nor transient (i.e., a normal file), are cached and expired in accord with the default caching scheme used by the computer.

[0026] A file or type of file is designated memory-resident or transient at any time, even when it is in use by another software application. The disk blocks encached are data blocks, index blocks, or both. The cache for memory-resident files is a standard disk cache or a sub-cache within a standard disk cache. The size of the cache may change during operation, freeing RAM for use by other applications. If the cache is a sub-cache, then the remaining cache memory is used by other applications until needed for the caching of memory-resident files. When the total blocks stored from memory-resident files exceed the size of the memory-resident cache, the excess blocks are subject to expiration by the default caching algorithm, rendering them more likely to be removed when demand exceeds capacity.

[0027] FIG. 2 depicts a prior art computer with normal disk cache functionality. Disk blocks likely to be accessed again are retained in a cache memory, thereby reducing read/write transactions to mass storage. In one embodiment, a cache manager 50 in the operating system 12 maintains multiple queues in RAM memory 20 containing data structures called “phys.” In this embodiment, cache manager 50 uses phys to track the states of disk blocks stored in cache memory. The cache manager 50 includes subprograms that traverse the queues at regular intervals, moving phys between queues to indicate their current state. Parameters defining the cache are stored in a cache data structure (not shown), which in turn affects the behavior of the cache manager 50. Editing these parameters permits a user or software application to indirectly affect file caching behavior.

[0028] In one embodiment, individual phys are numbered and associated with 4 KB cache entries, wherein each cache entry represents the contents of a disk block. In this embodiment, each numbered phy contains information describing the disk block associated with the cache entry, the state of the cache entry (e.g., modified or unmodified), the caching mode of the entry, and other information required to maintain a disk caching system. As a phy grows old or its state changes, the cache manager 50 moves the phy between queues, implementing cache functionality. A phy is always associated with at least one queue; there are no unassociated phys.

[0029] In one embodiment, cache manager 50 maintains five queue structures. First queue 52 contains phys that point to disk blocks that are currently referenced, i.e., blocks that are presently in use by one or more software applications and have virtual addresses. Second queue 54 contains phys that point to disk blocks that are not presently in use by at least one software application and therefore are not currently referenced, but have virtual addresses. The third queue 56 contains phys that point to disk blocks that are not currently referenced and do not have virtual addresses. The fourth queue 58 contains phys for reuse with virtual addresses. The fifth queue 60 contains phys for reuse that lack virtual addresses. In some embodiments, referenced and unreferenced phys are maintained in the same queue, using the reference count value to distinguish between them.

[0030] A transaction directed to a disk block not currently encached associates a phy in the first queue 52 with the disk block after it has been accessed. In some instances, e.g., when a disk block is preread, the phy is unreferenced and is placed in the second queue 54 or the third queue 56 depending on the presence or absence of a virtual address. Phys move between the referenced queue 52 and the unreferenced queues 54 and 56 as they are referenced and then not referenced.

[0031] Cache manager 50 periodically reviews the referenced queue 52 for phy entries older than a predetermined time value. In one embodiment, this time value is 30 seconds. If the age of a phy exceeds this time value, cache manager 50 cancels the references to the block associated with the phy, releases the block associated with the phy, decrements the phy reference count to zero, and moves the phy to unreferenced queue 54 because all phys on the referenced list have virtual addresses. This type of phy expiration is rare, given that phys are typically requested and then subsequently released, causing the phy reference count to be non-zero only for a short period of time. A notable exception involves the reading of a sequential file. In this case, disk blocks are read but often not immediately released. Therefore, phys associated with these blocks may be expired for time reasons.

[0032] Next, cache manager 50 reviews both unreferenced queues 54 and 56 for phy entries older than a predetermined time limit. In one embodiment, this time limit is 5 minutes. The unreferenced phys are expired if they are older than this time limit. Upon expiration, a phy is moved to one of the free queues 58 and 60 (depending on whether the phy has a virtual address) and becomes available to track another disk block as described above.

[0033] Lastly, cache manager 50 reviews the free queues 58 and 60 for phy entries older than a predetermined time limit. If a phy is older than the predetermined time limit and the current cache size exceeds a minimum predetermined value, then the buffer associated with the phy is freed. The memory allocated for the phy structure itself is never freed, but is queued and used again, being reallocated when a phy is needed and the free lists have no available phys with a buffer.

[0034] Thus, by using data structures associated with disk block contents in memory and a series of queues to hold these data structures, the prior art computer system of FIG. 2 implements a disk caching system that keeps recently-accessed disk blocks in cache and expires older unaccessed blocks from the cache.

[0035] FIG. 3 depicts a computer representing one embodiment of the present invention. In typical operation, a user application 70 executes a system call to designate a file or type of file memory-resident or transient. In some embodiments, the user operating the application 70 must have special system privileges. In one embodiment using the VOS operating system from Stratus Computer of Maynard, MA, the system call s$control passes a new control opcode SET₁₃FILE_CACHE_MODES to the VOS operating system 12.

[0036] Referring to FIG. 4, in this embodiment the SET_FILE_CACHE_MODES opcode for the s$control command is a 32-bit integer. If the low order bit 80 is set, the cache manager 50 treats the designated file as memory-resident and persistently caches data blocks associated with the file. If the next low-order bit 82 is set, the cache manager 50 treats the file as memory-resident and persistently caches index blocks associated with the file. If high-order bit 84 is set, the cache manager 50 treats the data blocks of the file as transient. Similarly, setting high-order bit 86 causes the cache manager 50 to treat the file's index blocks as transient. As discussed below, valid opcodes cannot simultaneously have bits 80 and 84 set, or bits 82 and 86 set.

[0037] Referring to FIG. 5, in one embodiment the addition of two new phy queues to the system of FIG. 2 enables memory-resident and transient caching. The first queue 90 caches phys that point to data and index blocks associated with memory-resident files. When an application initially accesses a disk block associated with a file, the attributes of the file are examined to determine if its data or index blocks are memory-resident, as discussed above. If so, the phys associated with the blocks are added to memory-resident queue 90. In one embodiment, the first queue 90 is actually two queues: one containing phys with virtual addresses and one containing phys without virtual addresses.

[0038] The second queue 92 caches phys that point to data and index blocks associated with transient files. If the attributes of a file whose blocks are being accessed indicate the file is transient, as discussed above, then the phys associated with the blocks associated with the file are added to transient queue 92. In one embodiment, the phys queued on the second queue 92 are also present on one of the other queues maintained by cache manager 50′.

[0039] Memory-resident behavior occurs through modifications to the cache manager 50 so that it never expires phys in memory-resident queue 90 merely because of their age. That is, in the prior art system of FIG. 2 the cached data associated with a phy may eventually be expired because the phy is older than a predetermined time limit. In contrast, the cache manager 50 in the present invention does not expire phys in queue 90 because they are older than a predetermined time limit. Ideally, the cached data associated with memory-resident files remains encached indefinitely, unless the file is subsequently designated non-memory resident, the file is no longer used by any applications, or the capacity of the memory resident cache is exceeded.

[0040] The maximum size of the cache limits the number of disk blocks that can be cached, which limits the number of phys associated with memory-resident files maintained in phy queue 90. Specifically, when the cache manager 50 periodically scans the phy queues, it also computes the maximum number of phys that can be stored based on the number of blocks that fit within the current maximum size of the cache memory. When that maximum number is exceeded, the cache manager 50 uses the default caching algorithms to determine the best candidate phys for expiration and removes the data associated with the best candidate phys until the cache size falls below the set limit. Similarly, if a user or a software application alters the size of the disk cache, changing the maximum number of memory-resident phys, then the size of the queues will be adjusted, removing the data associated with otherwise memory-resident phys.

[0041] In some embodiments, the size of the memory-resident cache can be altered by changing a system parameter specifying its size. In an embodiment where the memory-resident cache is a subcache of a normal cache memory, this parameter specifies a ratio between the size of the cache and the size of the subcache. Decreasing this ratio immediately reduces the size of the subcache, resulting in the expiration of disk blocks in excess of the size limit. Subsequently increasing the size of the disk cache permits flushed blocks to reenter the queue normally, as discussed above. If the memory-resident status of a file is changed, blocks associated with phys associated with the file are removed or added, as appropriate.

[0042] Attempts to disable memory-resident caching have no effect until the next time the cache manager 50 traverses the queues. In contrast, enabling memory-resident caching immediately affects phys associated with disk blocks at the next access of the block, assuming the blocks are not already encached. Blocks already encached are affected by the change in state the next time they are referenced.

[0043] In many ways the operation of the transient phy queue 92 is similar to that of the memory-resident phy queue 90. Like phys not in the memory-resident queue 90, phys in the transient queue 92 older than a predetermined time limit are expired. However, the predetermined time limit for transient phys is typically nominal, for example zero seconds, resulting in their immediate expiration from cache after being referenced. Designating files or certain types of files as transient reduces the amount of time that their associated blocks typically remain in cache, making resources available to cache other memory-resident or normal files.

[0044] For example, computers typically use log files to record transactions or other behavior for later review. Because a log file is frequently written to and infrequently read from, there is no benefit to caching the disk blocks associated with the log file. Designating a log file transient and setting the predetermined transient time limit to zero would in effect eliminate the blocks associated with the file from the cache, making resources available to cache other files.

[0045] It is sometimes desirable to expire the phys for blocks associated with transient files after a short, non-zero time period. For example, if a log file has a trailing one-time reader to subsequently reprocess written blocks, then setting the predetermined transient time limit to a small non-zero value facilitates this behavior by temporarily retaining the blocks associated with the file. Until the age of the transient phy exceeds the predetermined time limit, zero or non-zero, the block contents associated with a transient phy are not immediately written to mass storage. Once the block contents associated with a transient phy are written to mass storage, the block contents are eliminated from the cache.

[0046] FIGS. 6 and 6A depict a flowchart illustrating how a file is designated memory-resident or transient. First, a cache for disk blocks associated with memory-resident files is created in random-access memory (Step 8). Next, a user either directly designates a file or type of file as memory-resident or transient, or indirectly does so by running a software application, for example, a file manager (Step 10). In some embodiments, the user must be a privileged user or an error condition is returned and the designation is rejected. In other embodiments, any user may make this designation. A software application receives the designation from the user (Step 12). The application invokes a system routine that designates a file or type of file as memory-resident or transient (Step 14). In one embodiment using the VOS operating system, this routine is the system command “s$control” with a 32-bit argument “SET_FILE_CACHE_MODES.” The routine examines the value of the bits set in the passed argument (Step 16).

[0047] First, only the four lowest-order bits of the passed argument may be set (Step 18). Otherwise, an error condition is returned and the designation is rejected (Step 20). Next, referring to FIG. 4, bit 80 and bit 84 are examined (Step 22). The low-order bit 80 designates the data blocks of the file as memory-resident and the high-order bit 84 designates the data blocks of the file as transient. Since these conditions are mutually exclusive, a properly-formed argument cannot have both bits set. If both bit 80 and bit 84 are set, then an error condition is returned and the designation is rejected (Step 20).

[0048] Similarly, bits 82 and 86 are examined (Step 24). Again, referring to FIG. 4, bit 82 designates the index blocks of the file as memory-resident and bit 86 designates the index block of the file as transient. Since these conditions are mutually exclusive, a properly-formed argument cannot have both bits set. If both bits 82 and bits 86 are set, then an error condition is returned and the designation is rejected (Step 20).

[0049] The file is examined for associated index information (Step 26). If no index information is present but bits 82 or 86 are set (Step 28), then the argument passed is in error and a message is returned to the application indicating that no index information is associated with the file (Step 30). If no index information is present and neither the low-order bit 82 or the high-order bit 86 is set (Step 28), then system information is updated to reflect the desired caching state of the data blocks associated with the file (Step 34) before the process repeats itself (Step 36). If index information is present then system information is updated to reflect the desired caching state of the index blocks associated with the file (Step 32) and the desired caching state of the data blocks associated with the file (Step 34) before the process repeats itself (Step 36).

[0050] FIG. 7 depicts one embodiment of a transaction involving a data block or index block associated with a file or type of file that has been designated memory-resident. First, a block associated with a file or type of file is accessed, stored in memory, and associated with a phy structure (Step 48). The appropriate memory structures are examined for information that would indicate that the data block or index block requested has been designated memory-resident (Step 50). If the file is not designated memory-resident (Step 52), or if the file is designated memory-resident but no memory-resident cache exists (Step 56), then the file blocks are processed in accord with the normal caching algorithm (Step 54). If the file is designated memory-resident and a cache for memory-resident files exists, then the cache manager 50 conditionally sets the condition of the phy to memory-resident (Step 58).

[0051] Before this condition can be confirmed, the cache manager 50 checks the maximum size limit of the cache (Step 60). In some embodiments, this can be a number; in others, a percentage of an existing cache. If the number of phys queued equals or exceeds the maximum number of phys that could be held in the specified maximum size (Step 62), then the oldest phy in the appropriate memory-resident queue is moved to the free phy queue for reuse (Step 64). If there are no phys in the memory-resident queues, then the oldest phy in the appropriate unreferenced phy queue is moved to the free phy queue for reuse (Step 64). Assuming there is no issue with the size of the cache, the phy is placed in the appropriate queue (Step 66).

[0052] FIG. 8 depicts one embodiment of the queue management techniques periodically executed by the cache manager. As discussed above, at periodic intervals the cache manager 50 sweeps the phy queues, looking for phys with changed attributes (Step 68). If no phys have changed attributes (Step 70), the cache manager 50 periodically repeats its sweep of the queues (Step 68). If a phy with a changed attribute is located (Step 68), then the phy is moved to the queue matching its changed attributes. For example, if a memory-resident file is designated not memory resident, all of the phys associated with cached blocks from the file will have their attributes changed from memory-resident to normal (i.e., neither memory resident or transient). These phys are removed from the memory-resident queues, removing their blocks from the memory-resident cache (Step 72).

[0053] If a user adjusts the size of the memory-resident cache, it is necessary to recompute the number of phys whose blocks can be stored in memory-resident cache (Step 74). If the new number of permitted phys is less than the number of phys currently enqueued (Step 76), it will become necessary for the cache manager to expire phys from the queue as discussed above (Step 80). If the new number of permitted phys exceeds the number of phys already enqueued this adjustment is unnecessary (Step 78).

[0054] Many alterations and modifications may be made by those having ordinary skill in the art without departing from the spirit and scope of the invention. Therefore, it must be expressly understood that the illustrated embodiment has been shown only for the purposes of example and should not be taken as limiting the invention, which is defined by the following claims. The following claims are thus to be read as not only literally including what is set forth by the claims but also to include all equivalent elements for performing substantially the same function in substantially the same way to obtain substantially the same result, even though not identical in other respects to what is shown and described in the above illustrations.