Managing partitioned cache

Details Managing partitioned cache Managing partitioned cache

1998-06-22

2002-04-09

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S133000

Reexamination Certificate

active

06370619

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to computer systems and, more specifically, to a method for partitioning a buffer cache.
BACKGROUND OF THE INVENTION
Most data processing systems include both volatile and nonvolatile memory devices. In general, volatile memory devices, such as random access memory, provide faster access times than nonvolatile memory devices, such as magnetic or optical disks. However, nonvolatile memory is generally less expensive and less susceptible to data loss.
To take advantage of the persistent nature of nonvolatile memory, an object, such as a data item in a database system, is typically stored on nonvolatile memory (e.g. in a data block on a disk) until the data item is required by a particular process of the database system. To take advantage of the speed of volatile memory, a copy of the data block that contains the data item is loaded into volatile memory when the data item is required by a particular process of the database system. Once the data block is loaded into volatile memory, the process can quickly access and make changes to the copy of the data item. At some later point in time, the copy of the updated data item is written back to the database in order to reflect the changes that were made by the process.
For example, in a database system, a section of volatile memory known as a buffer cache is generally used by processes for accessing and manipulating information contained within the database. In order for a process to access or change data that is stored in the database, a copy of the data block that contains the data item is first loaded from the database into the buffer cache. After the data block is loaded in the buffer cache the process can then quickly access and manipulate the copied data version. At some later point in time, the contents of the buffer cache is written back to the database in order to reflect any changes that were previously made to the copied data version.
Typically, the buffer cache includes multiple buffers that are shared among one or more processes that are executing on a database server. When a process executes a transaction that requires a change to a data item within a data block, that is not already present within the buffer cache, the data block that contains the data w item is loaded into a buffer in the buffer cache. Any changes are then made to the data within the buffer.
Because the buffer cache contains a fixed amount of memory, a limited number of buffers are available for processing information. Often the amount of information to be processed exceeds the capacity of the buffers available to hold the information (i.e. data blocks). Once the buffer cache is full, storing new data in the buffer cache requires replacing data that already resides in the buffers within the buffer cache with the new data. In order to manage the limited number of available buffers, several replacement strategies have been developed. These replacement strategies determine which of the buffers currently residing in the buffer cache are to be overwritten with the new data (i.e. cached out).
Over the years, many different replacement strategies have been developed to increase efficiency. The most common of these strategies include replacing the least recently used (LRU) data, replacing the data that has been in the buffer the longest (First-In/First-Out, or FIFO), or replacing the newest data in the buffer (Last-In/First-Out, or LIFO). Each of these methods has both advantages and disadvantages that greatly depend on the amount of data being processed, the size of the buffer cache and the usage pattern which corresponds to how the data is being accessed.
Most database servers employ a single buffer cache. A drawback with using a single buffer cache is that only a single replacement strategy can be used for the entire set of buffers within the buffer cache. Using a single replacement strategy in a database system can be very inefficient when differently sized tables are accessed using different usage patterns. This inefficiency occurs because different usage patterns and differently sized tables can require distinct replacement strategies for efficient caching.
For example,
FIG. 1
depicts a database system
100
in which an order table
104
, an employee table
106
, and a stock table
108
are accessed through a single buffer cache
102
. Order table
104
contains a record of each order and contains more data blocks than can fit within the buffers of buffer cache
102
at any one time. Order records are constantly being added to the end of order table
104
. Therefore, it would be efficient to only keep in the buffer cache
102
the buffers that contain information from data blocks that are currently at the end of the order table
104
.
Conversely, stock table
108
comprises all of the stock items for sale and is small enough to fit within the number of buffers contained in buffer cache
102
. As stock items are retrieved on a frequent basis, it would be efficient to keep all data blocks of the entire stock table
108
within the buffers of buffer cache
102
at all times.
On the other hand, employee table
106
contains the address of each employee and is referenced very infrequently. Once an employee record is accessed it is normally not accessed again for a very long period of time. Therefore, it would be efficient to swap-out these buffers soon after an access completes so that another operation can use the buffer.
Because the tables of database system
100
have different caching requirements, a single replacement scheme cannot efficiently manage the replacement requirements associated with each of the tables. However, because data base system
100
contains only a single buffer cache
102
, the single replacement strategy for the buffer pool must be applied to all tables within database system
100
regardless of their size and usage patterns.
To address the inefficiencies associated with a single buffer cache, database servers can divide the buffer cache into multiple sub-cache areas. By using multiple sub-cache areas, each sub-cache can maintain its own individual replacement strategy that may differ from the replacement strategies associated with other sub-cache areas. Therefore, different replacement strategies can be used for different table based upon the memory disk address of the data blocks that are associated with a particular table. However, by using multiple sub-cache areas, data blocks, based on their nonvolatile memory disk address, are statically assigned to a particular sub-cache area and therefore can only be cached into buffers that are located within the particular sub-cache area.
Therefore, in such a database system, although multiple sub-cache areas provide for individual replacement strategies, a particular replacement strategy must be used for all data blocks that are assigned to a particular sub-cache area. This mapping restricts a particular table to a particular replacement strategy based on where its associated data blocks are located on disk. Thus, because data blocks are statically assigned to a specific sub-cache area based on its nonvolatile memory disk address, a particular sub-cache area or specific replacement strategy cannot be dynamically chosen for a particular table based on its access or usage pattern.
Therefore, based on the foregoing, it is clearly desirable to provide a mechanism for dynamically mapping data blocks to replacement strategies based on the associated table's access or usage patterns.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for partitioning a buffer cache for dynamically mapping data blocks with a particular replacement strategy based on the associated table's access and/or usage patterns.
According to the method, a buffer cache in a computer system is managed by dividing the buffer cache into multiple buffer pools. In managing the buffer cache, when a data item is requested, it is first determined whether the requested data item is stored in a buffer within the buffer cache. If the requested d

Affiliated with

Also associated with

Rating

Managing partitioned cache does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Managing partitioned cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Managing partitioned cache will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2843211