alluxio.worker.block.evictor

Class LRFUEvictor

java.lang.Object

alluxio.worker.block.AbstractBlockStoreEventListener

alluxio.worker.block.evictor.AbstractEvictor

alluxio.worker.block.evictor.LRFUEvictor

All Implemented Interfaces:

BlockStoreEventListener, Evictor

@NotThreadSafe
public final class LRFUEvictor
extends AbstractEvictor

This class is used to evict blocks by LRFU. LRFU evict blocks with minimum CRF, where CRF of a block is the sum of F(t) = pow(1.0 / mAttenuationFactor, t * mStepFactor). Each access to a block has a F(t) value and t is the time interval since that access to current. As the formula of F(t) shows, when (1.0 / mStepFactor) time units passed, F(t) will cut to the (1.0 / mAttenuationFactor) of the old value. So mStepFactor controls the step and mAttenuationFactor controls the attenuation. Actually, LRFU combines LRU and LFU, it evicts blocks with small frequency or large recency. When mStepFactor is close to 0, LRFU is close to LFU. Conversely, LRFU is close to LRU when mStepFactor is close to 1.

Nested Class Summary

Nested classes/interfaces inherited from interface alluxio.worker.block.evictor.Evictor

Evictor.Factory, Evictor.Mode

Field Summary

Fields inherited from class alluxio.worker.block.evictor.AbstractEvictor

mAllocator, mMetadataView

Constructor Summary

Constructors

Constructor and Description
LRFUEvictor(BlockMetadataEvictorView view, Allocator allocator) Creates a new instance of LRFUEvictor.

Method Summary

Modifier and Type	Method and Description
EvictionPlan	freeSpaceWithView(long bytesToBeAvailable, BlockStoreLocation location, BlockMetadataEvictorView view, Evictor.Mode mode) Frees space in the given block store location and with the given view.
protected Iterator<Long>	getBlockIterator() Returns an iterator for evictor cache blocks.
void	onAccessBlock(long userId, long blockId) Actions when accessing a block.
void	onBlockLost(long blockId) Actions when a block is lost.
void	onCommitBlock(long userId, long blockId, BlockStoreLocation location) Actions when committing a temporary block to a BlockStoreLocation.
void	onRemoveBlockByClient(long userId, long blockId) Actions when removing an existing block.
void	onRemoveBlockByWorker(long userId, long blockId) Actions when removing an existing block by worker.
protected void	onRemoveBlockFromIterator(long blockId) Performs additional cleanup when a block is removed from the iterator returned by AbstractEvictor.getBlockIterator().

Methods inherited from class alluxio.worker.block.evictor.AbstractEvictor

cascadingEvict, freeSpaceWithView, updateBlockStoreLocation

Methods inherited from class alluxio.worker.block.AbstractBlockStoreEventListener

onAbortBlock, onMoveBlockByClient, onMoveBlockByWorker, onStorageLost

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LRFUEvictor

public LRFUEvictor(BlockMetadataEvictorView view,
                   Allocator allocator)

Creates a new instance of LRFUEvictor.

Parameters:

view - a view of block metadata information

allocator - an allocation policy

Method Detail

freeSpaceWithView

@Nullable
public EvictionPlan freeSpaceWithView(long bytesToBeAvailable,
                                                BlockStoreLocation location,
                                                BlockMetadataEvictorView view,
                                                Evictor.Mode mode)

Description copied from interface: Evictor

Frees space in the given block store location and with the given view. With the GUARANTEED mode, after eviction at least one StorageDir in the location has the specific amount of free space after eviction. The location can be a specific StorageDir, or BlockStoreLocation.anyTier() or BlockStoreLocation.anyDirInTier(String). The view is generated and passed by the calling BlockStore. This method returns null if Evictor fails to propose a feasible plan to meet the requirement.

With the BEST_EFFORT mode, the evictor always returns an eviction plan with toMove and toEvict fields to indicate how to free space. Even if the tier does not have the amount of free space, the evictor returns the plan to free the max space.

If both toMove and toEvict of the plan are empty, it indicates that Evictor has no actions to take and the requirement is already met.

Throws an IllegalArgumentException if the given block location is invalid.

Specified by:

freeSpaceWithView in interface Evictor

Overrides:

freeSpaceWithView in class AbstractEvictor

Parameters:

bytesToBeAvailable - the amount of free space in bytes to be ensured after eviction

location - the location in block store

view - generated and passed by block store

mode - the eviction mode

Returns:

an EvictionPlan (possibly with empty fields) to get the free space, or null if no plan is feasible

getBlockIterator

protected Iterator<Long> getBlockIterator()

Description copied from class: AbstractEvictor

Returns an iterator for evictor cache blocks. The evictor is responsible for specifying the iteration order using its own strategy. For example, LRUEvictor returns an iterator that iterates through the block ids in LRU order.

Specified by:

getBlockIterator in class AbstractEvictor

Returns:

an iterator over the ids of the blocks in the evictor cache

onAccessBlock

public void onAccessBlock(long userId,
                          long blockId)

Description copied from interface: BlockStoreEventListener

Actions when accessing a block.

Specified by:

onAccessBlock in interface BlockStoreEventListener

Overrides:

onAccessBlock in class AbstractBlockStoreEventListener

Parameters:

userId - the id of the session to access this block

blockId - the id of the block to access

onCommitBlock

public void onCommitBlock(long userId,
                          long blockId,
                          BlockStoreLocation location)

Description copied from interface: BlockStoreEventListener

Actions when committing a temporary block to a BlockStoreLocation.

Specified by:

onCommitBlock in interface BlockStoreEventListener

Overrides:

onCommitBlock in class AbstractBlockStoreEventListener

Parameters:

userId - the id of the session to commit to this block

blockId - the id of the block to commit

location - the location of the block to be committed

onRemoveBlockByClient

public void onRemoveBlockByClient(long userId,
                                  long blockId)

Description copied from interface: BlockStoreEventListener

Actions when removing an existing block.

Specified by:

onRemoveBlockByClient in interface BlockStoreEventListener

Overrides:

onRemoveBlockByClient in class AbstractBlockStoreEventListener

Parameters:

userId - the id of the session to remove this block

blockId - the id of the block to be removed

onRemoveBlockByWorker

public void onRemoveBlockByWorker(long userId,
                                  long blockId)

Description copied from interface: BlockStoreEventListener

Actions when removing an existing block by worker.

Specified by:

onRemoveBlockByWorker in interface BlockStoreEventListener

Overrides:

onRemoveBlockByWorker in class AbstractBlockStoreEventListener

Parameters:

userId - the id of the session to remove this block

blockId - the id of the block to be removed

onBlockLost

public void onBlockLost(long blockId)

Description copied from interface: BlockStoreEventListener

Actions when a block is lost.

Specified by:

onBlockLost in interface BlockStoreEventListener

Overrides:

onBlockLost in class AbstractBlockStoreEventListener

Parameters:

blockId - the id of the lost block

onRemoveBlockFromIterator

protected void onRemoveBlockFromIterator(long blockId)

Description copied from class: AbstractEvictor

Performs additional cleanup when a block is removed from the iterator returned by AbstractEvictor.getBlockIterator().

Overrides:

onRemoveBlockFromIterator in class AbstractEvictor