search

carrotdata / carrot-cache

In-Out-Process Java cache (L1/L2 off-heap, scalable, ZeroGC) with full SSD support
Other
3 stars 0 forks source link

[CODE] Eviction policy refactoring #201

Open VladRodionov opened 1 year ago

VladRodionov commented 1 year ago

To support dynamically calculated promotion index. Currently, the API provides only current item index and total number of items in the index block. This won't allow complex eviction algorithms, such as window LFU or Dual Gready Size Frequency.

VladRodionov commented 1 year ago

This may require refactoring of index format as well.

Add

public double score(long ibPtr, long ptr, int index) to IndexFormat.

VladRodionov commented 1 year ago

Score is the positive real number. The lower the score - the higher the item priority. Examples of score functions

  1. Identity (default): (ibPtr, ptr, index) -> index
  2. kind of window LFU: (currentTime - lastAccessTime) / numberOfAccesses

  3. W-LFU with inverse weight: (currentTime - lastAccessTime) * inverseWeight / numberOfAccesses.

    InverseWeight examples:

iw = size / cost - size of a cached item and cost of cold generation

VladRodionov commented 1 year ago

Better score functions:

score = A T/(T1 N1)

This function preserves ordering between any pair of objects without hits as time goes by.