Fennel: TwoQVictimPolicy< PageT > Class Template Reference (original) (raw)

TwoQVictimPolicy implements the 2Q page victimization policy as described in the VLDB '94 paper "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm" by Johnson and Shasha. More...

#include <[TwoQVictimPolicy.h](TwoQVictimPolicy%5F8h-source.html)>

List of all members.

Public Types
typedef TwoQPageListIter< PageT >	PageIterator
	All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.
typedef TwoQDirtyPageListIter< PageT >	DirtyPageIterator
	All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.
typedef SXMutexSharedGuard	SharedGuard
	All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.
typedef SXMutexExclusiveGuard	ExclusiveGuard
	Guard for write access to mutex.
Public Member Functions
	TwoQVictimPolicy ()
	All models for VictimPolicy must have a default constructor.
	TwoQVictimPolicy (const CacheParams &params)
void	setAllocatedPageCount (uint nCachePagesInit)
	Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.
void	registerPage (PageT &page)
	Receives notification from CacheImpl when a page is allocated, giving the VictimPolicy a chance to initialize its own data structures for this page.
void	unregisterPage (PageT &page)
	Receives notification from CacheImpl when a page is freed, giving the VictimPolicy a chance to deinitialize its own data structures for this page.
void	notifyPageAccess (PageT &page, bool pin)
	Receives notification from CacheImpl when a page is accessed.
void	notifyPageNice (PageT &page)
	Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.
void	notifyPageMap (PageT &page, bool pin)
	Receives notification from CacheImpl just after a page is mapped.
void	notifyPageUnmap (PageT &page, bool discard)
	Receives notification from CacheImpl just before a page is unmapped.
void	notifyPageUnpin (PageT &page)
	Receives notification from CacheImpl that a page no longer needs to be pinned.
void	notifyPageDirty (PageT &page)
	Receives notification from CacheImpl that a page has been marked as dirty.
void	notifyPageClean (PageT &page)
	Receives notification from CacheImpl that a page is no longer dirty.
void	notifyPageDiscard (BlockId blockId)
	Receives notification from CacheImpl that a page has been discarded from the cache.
SXMutex &	getMutex ()
	Provides an SXMutex to CacheImpl to be acquired before calling getVictimRange().
std::pair< PageIterator, PageIterator >	getVictimRange ()
	Provides a range of candidate victims to CacheImpl.
std::pair< DirtyPageIterator, DirtyPageIterator >	getDirtyVictimRange ()
	Provides a range of candidate victims for flushing to CacheImpl.
Private Member Functions
void	init ()
	Initializes various queue variables.
bool	isPageClean (PageT &page)
	Returns:true if a page's state is non-dirty and its dirty state is clean
void	notifyPopularPageAccess (PageT &page, bool pin)
	Notifies the policy that a page that's being accessed needs to be put into the popular queue.
Private Attributes
SXMutex	mutex
	SXMutex protecting the queues.
TwoQPageQueue	popularPinnedQueue
	FIFO queue of popular, pinned pages.
TwoQPageQueue	popularUnpinnedQueue
	LRU queue of popular, unpinned pages.
TwoQPageQueue	freshmenQueue
	FIFO queue of freshmen pages.
TwoQPageQueue	dirtyPopularUnpinnedQueue
	Companion queue to popularUnpinnedQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.
TwoQPageQueue	dirtyFreshmenQueue
	Companion queue to freshmenQueue, except it only includes dirty pages and contains pointers to TwoQDirtyPage objects.
std::vector< BlockId >	historyQueue
	FIFO history queue.
uint	historyQueueStart
	Index corresponding to the first element in the historyQueue.
uint	currHistoryQueueLen
	Current length of the historyQueue.
boost::dynamic_bitset	historyBitmap
	Bitmap used to quickly approximate whether a page exists in the history queue based on the page's BlockId.
uint	nCachePages
	Total number of buffer pages in the cache.
uint	maxFreshmenQueueLen
	Maximum number of pages in the freshmen queue.
uint	maxHistoryQueueLen
	Maximum number of pages in the history queue.
uint	freshmenQueuePercentage
	Percentage of the total cache set aside for the freshmen queue.
uint	pageHistoryQueuePercentage
	The percentage of the total number of cache pages that dictates the number of pages in this history queue.

Detailed Description

template

class TwoQVictimPolicy< PageT >

TwoQVictimPolicy implements the 2Q page victimization policy as described in the VLDB '94 paper "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm" by Johnson and Shasha.

The 2Q refers to the fact that the algorithm separates the pages in the cache into two separate queues -- a LRU popular queue for frequently accessed pages and a FIFO freshmen queue for less frequently accessed pages. There is also a FIFO history queue that keeps track of pages that have been victimized from the freshmen queue. That history queue is what's used to determine whether a page is a popular one. In other words, when a page is first added to the cache, it's added to the freshmen queue. Once it's victimized from the freshmen queue, it's added to the history queue. If a page is re-referenced while it's in the history queue, it's added to the popular queue. By keeping two separate queues, the algorithm is scan resistant. Therefore, if you are doing large sequential scans, the scan resistant property prevents the scan pages from flooding the cache, paging out index pages that are more commonly referenced, particularly, index root pages. Ideally, you want to keep index root pages cached and page out the scan pages instead, even if the latter was more recently referenced.

Note that the naming of the queues is different from the less intuitive terms used in the original Johnson/Shasha paper -- Am (popular), A1in (freshmen), and A1out (history). Also, the popular queue is divided into two separate queues -- pinned vs unpinned pages. This makes locating a page for victimization more efficient.

One other extension in our implementation is we maintain separate queues of dirty pages for pages currently in the freshmen and popular-unpinned queues. These queues are subsets of their "parent" queues. By separating out dirty pages, this makes locating candidate pages for flushing more efficient when you have a large number of cache pages, many of which aren't dirty.

Any realization for PageT must inherit both CachePage and TwoQVictim as bases.

Definition at line 474 of file TwoQVictimPolicy.h.

Member Typedef Documentation

All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.

This type must be a model for a standard forward iterator. For TwoQVictimPolicy, this is accomplished by iterating over two doubly-linked list of pages corresponding to queues, one after the other.

Definition at line 656 of file TwoQVictimPolicy.h.

All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.

In the case of TwoQVictimPolicy, this iterator only returns dirty pages, avoiding clean pages.

Definition at line 665 of file TwoQVictimPolicy.h.

All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.

This guard must provide any synchronization required to protect the iteration against concurrent modifications. The guard will be initialized with the result of getMutex(). For TwoQVictimPolicy, the guard is a read guard protecting the various queues, meaning notifications are blocked during iteration since they have to modify the chain.

Definition at line 677 of file TwoQVictimPolicy.h.

Constructor & Destructor Documentation

Member Function Documentation

template

| void TwoQVictimPolicy< PageT >::init | ( | | ) | [inline, private] | | ------------------------------------------------------------------ | - | | - | ------------------- |

template

bool TwoQVictimPolicy< PageT >::isPageClean	(	PageT &	page	)	[inline, private]

template

void TwoQVictimPolicy< PageT >::notifyPopularPageAccess	(	PageT &	page,
bool	pin
)	[inline, private]

Notifies the policy that a page that's being accessed needs to be put into the popular queue.

Depending on the "pin" parameter, it's either put into the popular-pinned queue or the popular-unpinned queue.

Parameters:

page	the page being accessed
pin	whether the page is being pinned

Definition at line 594 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), SXMutex::isLocked(), TwoQVictimPolicy< PageT >::isPageClean(), LOCKMODE_X, TwoQPageQueue::moveToTail(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQVictimPolicy< PageT >::popularPinnedQueue, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

Referenced by TwoQVictimPolicy< PageT >::notifyPageAccess().

template

void TwoQVictimPolicy< PageT >::setAllocatedPageCount	(	uint	nCachePagesInit	)	[inline]

Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.

Parameters:

nCachePagesInit	number of buffer pages in the cache

Definition at line 708 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::currHistoryQueueLen, TwoQVictimPolicy< PageT >::freshmenQueuePercentage, TwoQVictimPolicy< PageT >::historyBitmap, TwoQVictimPolicy< PageT >::historyQueue, TwoQVictimPolicy< PageT >::historyQueueStart, TwoQVictimPolicy< PageT >::maxFreshmenQueueLen, TwoQVictimPolicy< PageT >::maxHistoryQueueLen, TwoQVictimPolicy< PageT >::mutex, TwoQVictimPolicy< PageT >::nCachePages, NULL_BLOCK_ID, opaqueToInt(), and TwoQVictimPolicy< PageT >::pageHistoryQueuePercentage.

template

void TwoQVictimPolicy< PageT >::registerPage	(	PageT &	page	)	[inline]

template

void TwoQVictimPolicy< PageT >::unregisterPage	(	PageT &	page	)	[inline]

template

void TwoQVictimPolicy< PageT >::notifyPageAccess	(	PageT &	page,
bool	pin
)	[inline]

Receives notification from CacheImpl when a page is accessed.

On entry, the page's mutex is held by the calling thread, so the state of the page (e.g. its mapped BlockId) is guaranteed to remain stable. This is true for all other notify methods as well. For TwoQVictimPolicy, depending on the current state of the page, that determines what happens to the page.

If the page is currently either in the freshmen or popular-pinned queues, then the page remains in its current position in the queue.
If the page is currently in the popular-unpinned queue and it's being pinned, then it's added to the popular-pinned queue. Otherwise, if it's not being pinned, it's added to the tail of the popular-unpinned queue.
If the page is not currently in the cache and it's in the history queue, it's added to one of the popular queues, depending on whether it's being pinned. Otherwise, if it's not in the history queue, then it's added to the tail of the freshmen queue.

Parameters:

page	the page being accessed
pin	if true, the page being accessed will be pinned in the cache

Definition at line 834 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::freshmenQueue, TwoQVictimPolicy< PageT >::historyBitmap, TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQVictimPolicy< PageT >::mutex, TwoQVictimPolicy< PageT >::notifyPopularPageAccess(), opaqueToInt(), TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, and TwoQVictim::PAGE_STATE_POPULAR_UNPINNED.

Referenced by TwoQVictimPolicy< PageT >::notifyPageMap().

template

void TwoQVictimPolicy< PageT >::notifyPageNice	(	PageT &	page	)	[inline]

Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.

For TwoQVictimPolicy, this results in the page being moved to the head of the queue if the page is in either the popular-unpinned or freshmen queues.

Parameters:

page	the page to which the hint pertains

Definition at line 872 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQVictimPolicy< PageT >::freshmenQueue, TwoQDirtyPage::getDirtyState(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQPageQueue::moveToHead(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, and TwoQVictimPolicy< PageT >::popularUnpinnedQueue.

template

void TwoQVictimPolicy< PageT >::notifyPageMap	(	PageT &	page,
bool	pin
)	[inline]

Receives notification from CacheImpl just after a page is mapped.

This implies an access as well, so for efficiency, no corresponding notifyPageAccess notification is received.

Parameters:

page	the page being mapped
pin	if true, the page being mapped will be pinned in the cache

Definition at line 909 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::notifyPageAccess().

template

void TwoQVictimPolicy< PageT >::notifyPageUnmap	(	PageT &	page,
bool	discard
)	[inline]

Receives notification from CacheImpl just before a page is unmapped.

The Page object still has the ID being unmapped.

Parameters:

page	the page being unmapped
discard	if true, page is being discarded from the cache

Definition at line 924 of file TwoQVictimPolicy.h.

template

void TwoQVictimPolicy< PageT >::notifyPageUnpin	(	PageT &	page	)	[inline]

Receives notification from CacheImpl that a page no longer needs to be pinned.

Parameters:

Definition at line 1001 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::isPageClean(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQVictimPolicy< PageT >::popularPinnedQueue, TwoQVictimPolicy< PageT >::popularUnpinnedQueue, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

template

void TwoQVictimPolicy< PageT >::notifyPageDirty	(	PageT &	page	)	[inline]

Receives notification from CacheImpl that a page has been marked as dirty.

Parameters:

Definition at line 1035 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQPageQueue::insertAtTail(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_CLEAN, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, and TwoQDirtyPage::setDirtyState().

template

void TwoQVictimPolicy< PageT >::notifyPageClean	(	PageT &	page	)	[inline]

Receives notification from CacheImpl that a page is no longer dirty.

Parameters:

Definition at line 1071 of file TwoQVictimPolicy.h.

References TwoQVictimPolicy< PageT >::dirtyFreshmenQueue, TwoQVictimPolicy< PageT >::dirtyPopularUnpinnedQueue, TwoQDirtyPage::getDirtyState(), TwoQVictimPolicy< PageT >::mutex, TwoQDirtyPage::PAGE_CLEAN, TwoQDirtyPage::PAGE_DIRTY_FRESHMAN, TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED, TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED, TwoQVictim::PAGE_STATE_FREE, TwoQVictim::PAGE_STATE_FRESHMAN, TwoQVictim::PAGE_STATE_POPULAR_PINNED, TwoQVictim::PAGE_STATE_POPULAR_UNPINNED, TwoQPageQueue::remove(), and TwoQDirtyPage::setDirtyState().

template

void TwoQVictimPolicy< PageT >::notifyPageDiscard	(	BlockId	blockId	)	[inline]

Member Data Documentation

The documentation for this class was generated from the following file:

/home/pub/open/dev/fennel/cache/TwoQVictimPolicy.h

Generated on Mon Jun 22 04:00:48 2009 for Fennel by 1.5.1