import { Cache } from '../cache' ; import { CacheSPI } from '../cache-spi' ; import { Metrics } from '../metrics/metrics' ; import { CountMinSketch } from './sketch' ; import { ON_REMOVE , ON_MAINTENANCE , TRIGGER_REMOVE , MAINTENANCE } from '../symbols' ; import { RemovalReason } from '../removal-reason' ; import { CacheNode } from '../cache-node' ; import { Weigher } from '../weigher' ; import { KeyType } from '../key-type' ; import { AbstractCache } from '../abstract' ; import { RemovalListener } from '../removal-listener' ; const percentInMain = 0.99 ; const percentProtected = 0.8 ; const percentOverflow = 0.01 ; const adaptiveRestartThreshold = 0.05 ; const adaptiveStepPercent = 0.0625 ; const adaptiveStepDecayRate = 0.98 ; const DATA = Symbol ( 'boundedData' ) ; /**
 * Options usable with a BoundedCache.
 */ export interface BoundedCacheOptions < K extends KeyType , V > { /**
     * The maximum size of the cache. For unweighed caches this is the maximum
     * number of entries in the cache, for weighed caches this is the maximum
     * weight of the cache.
     */ maxSize : number ; /**
     * Weigher function to use. If this is specified the cache turns into
     * a weighted cache and the function is called when cached data is stored
     * to determine its weight.
     */ weigher ? : Weigher < K , V > | null ; /**
     * Listener to call whenever something is removed from the cache.
     */ removalListener ? : RemovalListener < K , V > | null ; } /**
 * Data as used by the bounded cache.
 */ interface BoundedCacheData < K extends KeyType , V > { /**
     * Values within the cache.
     */ values : Map < K , BoundedNode < K , V > > ; /**
     * The maximum size of the cache or -1 if the cache uses weighing.
     */ maxSize : number ; /**
     * Weigher being used for this cache. Invoked to determine the weight of
     * an item being cached.
     */ weigher : Weigher < K , V > | null ; /**
     * Maximum size of the cache as a weight.
     */ weightedMaxSize : number ; /**
     * The current weight of all items in the cache.
     */ weightedSize : number ; /**
     * Listener to invoke when removals occur.
     */ removalListener : RemovalListener < K , V > | null ; /**
     * Sketch used to keep track of the frequency of which items are used.
     */ sketch : CountMinSketch ; /**
     * The limit at which to grow the sketch.
     */ sketchGrowLimit : number ; /**
     * Timeout holder for performing maintenance. When this is set it means
     * that a maintenance is queued for later.
     */ maintenanceTimeout : any ; /**
     * The maximum size the cache can grow without an eviction being applied
     * directly.
     */ forceEvictionLimit : number ; /**
     * The time in milliseconds to delay maintenance.
     */ maintenanceInterval : number ; /**
     * Adaptive data used to adjust the size of the window.
     */ adaptiveData : AdaptiveData ; /**
     * Tracking of the window cache, starts at around 1% of the total cache.
     */ window : CacheSection < K , V > ; /**
     * SLRU protected segment, 80% * (100% - windowSize) of the total cache
     */ protected : CacheSection < K , V > ; /**
     * SLRU probation segment, 20% * (100% - windowSize) of the total cache
     */ probation : ProbationSection < K , V > ; } /**
 * Node in a double-linked list used for the segments within the cache.
 */ class BoundedNode < K extends KeyType , V > extends CacheNode < K , V > { public readonly hashCode : number ; public weight : number ; public location : Location ; constructor ( key , value ) { super ( key , value ) ; this . hashCode = key == null ? 0 : CountMinSketch . hash ( key ) ; this . weight = 1 ; this . location = Location . WINDOW ; } } /**
 * Location of a node within the caches segments.
 */ const enum Location { WINDOW = 0 , PROTECTED = 1 , PROBATION = 2 } /**
 * Segment within the cache including a tracker for the current size and
 * the maximum size it can be.
 */ interface CacheSection < K extends KeyType , V > { /**
     * Head of the linked list containing nodes for this segment.
     */ head : BoundedNode < K , V > ; /**
     * Current size of the segment. Updated whenever something is added or
     * removed from the segment.
     */ size : number ; /**
     * The maximum size of the segment. Set on creation and can then be moved
     * around using the adaptive adjustment.
     */ maxSize : number ; } /**
 * Special type for the probation segment that doesn't track its size.
 */ interface ProbationSection < K extends KeyType , V > { /**
     * Head of the linked list containing nodes for this segment.
     */ head : BoundedNode < K , V > ; } /**
 * Data used for adaptive adjustment of the window segment.
 */ interface AdaptiveData { /**
     * The adjustment left to perform, a positive number indicates that the
     * window size should be increased.
     */ adjustment : any ; /**
     * The current step size for the hill climbing.
     */ stepSize : any ; /**
     * The hit rate of the previous sample.
     */ previousHitRate : number ; /**
     * The number of this in the current sample.
     */ misses : number ; /**
     * The number of misses in the current sample.
     */ hits : number ; } /**
 * Bounded cache implementation using W-TinyLFU to keep track of data.
 *
 * See https://arxiv.org/pdf/1512.00727.pdf for details about TinyLFU and
 * the W-TinyLFU optimization.
 */ export class BoundedCache < K extends KeyType , V > extends AbstractCache < K , V > implements Cache < K , V > , CacheSPI < K , V > { private [ DATA ] : BoundedCacheData < K , V > ; public [ ON_REMOVE ] ? : RemovalListener < K , V > ; public [ ON_MAINTENANCE ] ? : ( ) => void ; constructor ( options ) { super ( ) ; const maxMain = Math . floor ( percentInMain * options . maxSize ) ; const sketchWidth = options . weigher ? 256 : Math . max ( options . maxSize , 128 ) ; this [ MAINTENANCE ] = this [ MAINTENANCE ] . bind ( this ) ; this [ DATA ] = { maxSize : options . weigher ? - 1 : options . maxSize , removalListener : options . removalListener || null , weigher : options . weigher || null , weightedMaxSize : options . maxSize , weightedSize : 0 , sketch : CountMinSketch . uint8 ( sketchWidth , 4 ) , sketchGrowLimit : sketchWidth , values : new Map ( ) , adaptiveData : { hits : 0 , misses : 0 , adjustment : 0 , previousHitRate : 0 , stepSize : - adaptiveStepPercent * options . maxSize } , window : { head : new BoundedNode < K , V > ( null , null ) , size : 0 , maxSize : options . maxSize - maxMain } , protected : { head : new BoundedNode < K , V > ( null , null ) , size : 0 , maxSize : Math . floor ( maxMain * percentProtected ) } , probation : { head : new BoundedNode < K , V > ( null , null ) , } , maintenanceTimeout : null , forceEvictionLimit : options . maxSize + Math . max ( Math . floor ( options . maxSize * percentOverflow ) , 5 ) , maintenanceInterval : 5000 } ; } /**
     * Get the maximum size this cache can be.
     */ get maxSize ( ) { return this [ DATA ] . maxSize ; } /**
     * Get the current size of the cache.
     */ get size ( ) { return this [ DATA ] . values . size ; } /**
     * Get the weighted size of all items in the cache.
     */ get weightedSize ( ) { return this [ DATA ] . weightedSize ; } /**
     * Cache and associate a value with the given key.
     */ public set ( key , value ) { const data = this [ DATA ] ; const old = data . values . get ( key ) ; const node = new BoundedNode ( key , value ) ; data . values . set ( key , node ) ; if ( data . weigher ) { node . weight = data . weigher ( key , value ) ; } data . weightedSize += node . weight ; if ( old ) { old . remove ( ) ; data . weightedSize -= old . weight ; switch ( old . location ) { case Location . PROTECTED : data . protected . size -= old . weight ; break ; case Location . WINDOW : data . window . size -= old . weight ; break ; } } if ( data . weigher && data . values . size >= data . sketchGrowLimit ) { const sketchWidth = data . values . size * 2 ; data . sketch = CountMinSketch . uint8 ( sketchWidth , 4 ) ; data . sketchGrowLimit = sketchWidth ; } node . appendToTail ( data . window . head ) ; data . window . size += node . weight ; data . sketch . update ( node . hashCode ) ; if ( data . weightedSize >= data . forceEvictionLimit ) { this [ MAINTENANCE ] ( ) ; } else if ( ! data . maintenanceTimeout ) { data . maintenanceTimeout = setTimeout ( this [ MAINTENANCE ] , data . maintenanceInterval ) ; } if ( old ) { this [ TRIGGER_REMOVE ] ( key , old . value , RemovalReason . REPLACED ) ; return old . value ; } else { return null ; } } /**
     * Get a previously cached value.
     */ public getIfPresent ( key ) { const data = this [ DATA ] ; const node = data . values . get ( key ) ; if ( ! node ) { data . adaptiveData . misses ++ ; return null ; } data . adaptiveData . hits ++ ; data . sketch . update ( node . hashCode ) ; switch ( node . location ) { case Location . WINDOW : node . moveToTail ( data . window . head ) ; break ; case Location . PROBATION : node . location = Location . PROTECTED ; node . moveToTail ( data . protected . head ) ; data . protected . size += node . weight ; while ( data . protected . size > data . protected . maxSize ) { const lru = data . protected . head . next ; lru . location = Location . PROBATION ; lru . moveToTail ( data . probation . head ) ; data . protected . size -= lru . weight ; } break ; case Location . PROTECTED : node . moveToTail ( data . protected . head ) ; break ; } return node . value ; } public peek ( key ) { const data = this [ DATA ] ; const node = data . values . get ( key ) ; return node ? node . value : null ; } /**
     * Delete any value associated with the given key from the cache.
     */ public delete ( key ) { const data = this [ DATA ] ; const node = data . values . get ( key ) ; if ( node ) { node . remove ( ) ; switch ( node . location ) { case Location . PROTECTED : data . protected . size -= node . weight ; break ; case Location . WINDOW : data . window . size -= node . weight ; break ; } data . weightedSize -= node . weight ; data . values . delete ( key ) ; this [ TRIGGER_REMOVE ] ( key , node . value , RemovalReason . EXPLICIT ) ; if ( ! data . maintenanceTimeout ) { data . maintenanceTimeout = setTimeout ( this [ MAINTENANCE ] , data . maintenanceInterval ) ; } return node . value ; } return null ; } /**
     * Check if a certain value exists in the cache.
     */ public has ( key ) { const data = this [ DATA ] ; return data . values . has ( key ) ; } public clear ( ) { const data = this [ DATA ] ; const oldValues = data . values ; data . values = new Map ( ) ; for ( const [ key , node ] of oldValues ) { this [ TRIGGER_REMOVE ] ( key , node . value , RemovalReason . EXPLICIT ) ; } data . weightedSize = 0 ; data . window . head . remove ( ) ; data . window . size = 0 ; data . probation . head . remove ( ) ; data . protected . head . remove ( ) ; data . protected . size = 0 ; if ( data . maintenanceTimeout ) { clearTimeout ( data . maintenanceTimeout ) ; data . maintenanceTimeout = null ; } } public keys ( ) { this [ MAINTENANCE ] ( ) ; return Array . from ( this [ DATA ] . values . keys ( ) ) ; } public cleanUp ( ) { this [ MAINTENANCE ] ( ) ; } get metrics ( ) : Metrics { throw new Error ( 'Metrics are not supported by this cache' ) ; } private [ TRIGGER_REMOVE ] ( key , value , cause ) { const data = this [ DATA ] ; const onRemove = this [ ON_REMOVE ] ; if ( onRemove ) { onRemove ( key , value , cause ) ; } if ( data . removalListener ) { data . removalListener ( key , value , cause ) ; } } private [ MAINTENANCE ] ( ) { const onMaintenance = this [ ON_MAINTENANCE ] ; if ( onMaintenance ) { onMaintenance ( ) ; } const data = this [ DATA ] ; let evictedToProbation = 0 ; while ( data . window . size > data . window . maxSize ) { const first = data . window . head . next ; first . moveToTail ( data . probation . head ) ; first . location = Location . PROBATION ; data . window . size -= first . weight ; evictedToProbation ++ ; } while ( data . weightedSize > data . weightedMaxSize ) { const probation = data . probation . head . next ; const evictedCandidate = evictedToProbation === 0 ? data . probation . head : data . probation . head . previous ; const hasProbation = probation !== data . probation . head ; const hasEvicted = evictedCandidate !== data . probation . head ; let toRemove ; if ( ! hasProbation && ! hasEvicted ) { break ; } else if ( ! hasEvicted ) { toRemove = probation ; } else if ( ! hasProbation ) { toRemove = evictedCandidate ; evictedToProbation -- ; } else { let removeCandidate ; const freqEvictedCandidate = data . sketch . estimate ( evictedCandidate . hashCode ) ; const freqProbation = data . sketch . estimate ( probation . hashCode ) ; if ( freqEvictedCandidate > freqProbation ) { removeCandidate = false ; } else if ( freqEvictedCandidate < data . sketch . slightlyLessThanHalfMaxSize ) { removeCandidate = true ; } else { removeCandidate = Math . floor ( Math . random ( ) * 1000 ) >= 1 ; } toRemove = removeCandidate ? evictedCandidate : probation ; evictedToProbation -- ; } if ( toRemove . key === null ) { throw new Error ( 'Cache issue, problem with removal' ) ; } data . values . delete ( toRemove . key ) ; toRemove . remove ( ) ; data . weightedSize -= toRemove . weight ; this [ TRIGGER_REMOVE ] ( toRemove . key , toRemove . value , RemovalReason . SIZE ) ; } adaptiveAdjustment ( data ) ; if ( data . maintenanceTimeout ) { clearTimeout ( data . maintenanceTimeout ) ; data . maintenanceTimeout = null ; } } } param data function adaptiveAdjustment < K extends KeyType , V > ( data ) { calculateAdaptiveAdjustment ( data ) ; const a = data . adaptiveData . adjustment ; if ( a > 0 ) { increaseWindowSegmentSize ( data ) ; } else if ( a < 0 ) { decreaseWindowSegmentSize ( data ) ; } } param data function evictProtectedToProbation < K extends KeyType , V > ( data ) { let i = 0 ; while ( i ++ < 1000 && data . protected . size > data . protected . maxSize ) { const lru = data . protected . head . next ; if ( lru === data . protected . head ) break ; lru . location = Location . PROBATION ; lru . moveToTail ( data . probation . head ) ; data . protected . size -= lru . weight ; } } returns function calculateAdaptiveAdjustment < K extends KeyType , V > ( data ) { const adaptiveData = data . adaptiveData ; const requestCount = adaptiveData . hits + adaptiveData . misses ; if ( requestCount < data . sketch . resetAfter ) { return false ; } const hitRate = adaptiveData . hits / requestCount ; const hitRateDiff = hitRate - adaptiveData . previousHitRate ; const amount = hitRateDiff >= 0 ? adaptiveData . stepSize : - adaptiveData . stepSize ; let nextStep ; if ( Math . abs ( hitRateDiff ) >= adaptiveRestartThreshold ) { nextStep = adaptiveStepPercent * data . weightedMaxSize * ( amount >= 0 ? 1 : - 1 ) ; } else { nextStep = adaptiveStepDecayRate * amount ; } adaptiveData . adjustment = Math . floor ( amount ) ; adaptiveData . stepSize = nextStep ; adaptiveData . previousHitRate = hitRate ; adaptiveData . misses = 0 ; adaptiveData . hits = 0 ; return true ; } param data function increaseWindowSegmentSize < K extends KeyType , V > ( data ) { if ( data . protected . maxSize === 0 ) { return ; } let amountLeftToAdjust = Math . min ( data . adaptiveData . adjustment , data . protected . maxSize ) ; data . protected . maxSize -= amountLeftToAdjust ; data . window . maxSize += amountLeftToAdjust ; evictProtectedToProbation ( data ) ; for ( let i = 0 ; i < 1000 ; i ++ ) { let lru = data . probation . head . next ; if ( lru === data . probation . head || lru . weight > amountLeftToAdjust ) { lru = data . protected . head . next ; if ( lru === data . protected . head ) { break ; } } if ( lru . weight > amountLeftToAdjust ) { break ; } amountLeftToAdjust -= lru . weight ; if ( lru . location === Location . PROTECTED ) { data . protected . size -= lru . weight ; } lru . moveToTail ( data . window . head ) ; data . window . size += lru . weight ; lru . location = Location . WINDOW ; } data . protected . maxSize += amountLeftToAdjust ; data . window . maxSize -= amountLeftToAdjust ; data . adaptiveData . adjustment = amountLeftToAdjust ; } param data function decreaseWindowSegmentSize < K extends KeyType , V > ( data ) { if ( data . window . maxSize <= 1 ) { return ; } let amountLeftToAdjust = Math . min ( - data . adaptiveData . adjustment , Math . max ( data . window . maxSize - 1 , 0 ) ) ; data . window . maxSize -= amountLeftToAdjust ; data . protected . maxSize += amountLeftToAdjust ; for ( let i = 0 ; i < 1000 ; i ++ ) { const lru = data . window . head . next ; if ( lru === data . window . head ) { break ; } if ( lru . weight > amountLeftToAdjust ) { break ; } amountLeftToAdjust -= lru . weight ; lru . moveToTail ( data . probation . head ) ; lru . location = Location . PROBATION ; data . window . size -= lru . weight ; } data . window . maxSize += amountLeftToAdjust ; data . protected . maxSize -= amountLeftToAdjust ; data . adaptiveData . adjustment = - amountLeftToAdjust ; }