Self-tuning buffer management

Details Self-tuning buffer management Self-tuning buffer management

2000-10-26

2003-10-07

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S133000, C711S159000

Reexamination Certificate

active

06631446

ABSTRACT:

BACKGROUND
The invention relates to self-tuning buffer management.
Computer systems have limited memory storage for the information they process, and in some cases, the amount of information to be processed may exceed the amount of available storage. Buffering systems, such as caches, allow only a subset of the information to be stored in memory at any given time. Information stored in the buffers typically can be retrieved more quickly than information stored, for example, on a magnetic or optical disk.
A buffer manager is responsible for managing the buffers. For example, to store new data in the cache when the cache is full, at least some data already residing in the cache must be replaced. Various replacement strategies are known including replacing the least recently used (LRU) data. In general, such strategies also involve rearranging the relative positions of the buffers within the pool. For example, one implementation of the LUR technique maintains the list of buffers according to the time at which the data in each buffer is accessed. At one end (the “hot” end) of the list is a buffer containing the most recently used data, and at the other end (the “cold” end) is a buffer containing the least recently used data. When data in a given buffer is accessed, the buffer containing the data is moved from its current location in the list to the hot end of the list. When new data is brought into the cache, it is placed in the buffer at the cold end of the list, and the buffer then is moved to the hot end of the list.
A considerable amount of overhead is required to rearrange the buffers each time data is accessed. This rearranging also can lead to contention for buffer data structures, limiting the amount of parallelism that can be achieved in the buffer manager. Reducing contention is an important way to enable a multi-CPU (central processing unit) system to run faster, so that the CPUs do not have to wait for each other as much. Therefore, it would desirable to improve management of the buffers.
SUMMARY
In general, a method of managing memory buffers includes maintaining a pool of buffers and assigning the buffers to buffer classes based on the frequency with which information stored in the buffers is accessed. Different algorithms can be used to manage buffers assigned to the different classes.
Various implementations can include one or more of the following features. A determination can be made as to whether a particular buffer qualifies for entry into a particular one of the buffer classes based on a comparison between a threshold value and the frequency with which information stored in the particular buffer was accessed during a specified time interval.
The threshold value can be adjusted dynamically. For example, if it is determined that too many buffers have qualified for entry into the particular buffer class, the threshold value can be increased. If it is determined that too few buffers have qualified for entry into the particular buffer class, the threshold value can be decreased. The particular buffer class can have a target size, and the threshold value can be adjusted based on the number of attempts to assign buffers to the particular buffer class that would cause the target size to be exceeded. In some cases, the target size represents a maximum permissible size for the particular buffer class. In general, the technique can include periodically checking the extent of any disparity between a target size for the particular buffer class and the number of buffers that qualified for the particular buffer class during a previous time interval and adjusting the threshold value based on the extent of the disparity.
In some situations, a user can designate particular information as a candidate for storage in a particular buffer class. The techniques then can include determining whether requested information was previously designated by a user as a candidate for storage in a particular buffer class and comparing the frequency with which the requested information was accessed during a specified time interval to a threshold value. If the requested information was previously designated by a user as a candidate for storage in the particular buffer class and the frequency with which the information was accessed during the specified time interval is greater than the threshold value, then the requested information is stored in a buffer in the particular buffer class.
A system that includes first and second memories, a bus and a processor configured to execute the foregoing techniques also is disclosed. Furthermore, an article that includes a computer-readable medium that stores computer-executable instructions for causing a computer system to execute the foregoing techniques is disclosed.
Some implementations include one or more of the following advantages. The techniques can allow buffers to be assigned to a buffer class based on how frequently the buffers are accessed. The techniques can help ensure that buffers that previously were accessed frequently but are no longer being accessed frequently are moved to lower priority classes. Thus, buffers can be prevented from becoming permanently labeled as containing frequently-accessed data when the data no longer is being accessed frequently.
Adjustments to the thresholds can be made dynamically to take account, for example, of the current load on the system. The adjustments can be implemented automatically by the system without user intervention and can increase the overall efficiency and cost-effectiveness of the system.
Other features and advantages will be readily apparent from the following detailed description, the accompanying drawings and the claims.


REFERENCES:
patent: 5432919 (1995-07-01), Falcone et al.
patent: 5584015 (1996-12-01), Villette et al.
patent: 5640604 (1997-06-01), Hirano
patent: 5680573 (1997-10-01), Rubin et al.
patent: 5778442 (1998-07-01), Ezzat et al.
patent: 5915104 (1999-06-01), Miller
patent: 6003101 (1999-12-01), Williams
patent: 6088767 (2000-07-01), Dan et al.
patent: 6317427 (2001-11-01), Augusta et al.
patent: 6378043 (2002-04-01), Girkar et al.
patent: 6397274 (2002-05-01), Miller
Hallnor et al. A Fully Associative Software-Managed Cache Design, ISCA 2000, pp. 107-116.*
Riley et al., “The Design of Multimedia Object Support in DEC Rdb”, Digital Technical Journal, vol. 5, No. 2, pp. 50-64, Spring 1993.
Ozden et al., “Buffer Replacement Algorithms for Multimedia Storage Systems”, Proceedings of the International Conference on Multimedia Computing and Systems, pp. 172-180, Jun. 1996.
Scheuermann et al., “A case for delay-conscious caching of Web documents”, Computer Networks and ISDN Systems, vol. 29, Nos. 8-13 (Sep. 1997), pp. 997-1005.
Bridge et al., “The Oracle Universal Server Buffer Manager”, Proc. Of the 23rdVLDB Conference (1997), pp. 590-593.
Chou et al., “An Evaluation of Buffer Management Strategies for Relational Database Systems”, Relational Implementation Techniques, VLDB (1985), pp. 174-188.
“MS SQL Server 7.0 Storage Engine”, http://www.microsoft.com/technet/SQL/Technote/sq17stor.asp, Oct. 5, 2000.
Chen et al., “Adaptive Database Buffer Allocation Using Query Feedback”, 1993 VLDB., http://www.cs.umd.edu/~nick/papers/vldb93.ps.gz.

Affiliated with

Also associated with

Rating

Self-tuning buffer management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Self-tuning buffer management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-tuning buffer management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3142676