Skip to main content
Using Deno in production at your company? Earn free Deno merch.
Give us feedback
Module

x/velo/src/policy/tiny_lfu/frequency_sketch.ts>FrequencySketch

A high-performance caching library for Deno. Supports LRU, LFU, ARC, and TinyLFU.
velo-org/velo
Latest
class FrequencySketch
import { FrequencySketch } from "https://deno.land/x/velo@1.0.0/src/policy/tiny_lfu/frequency_sketch.ts";

A probabilistic set for estimating the frequency of elements within a time window to use as freshness metric for the TinyLFU [1] admission policy. Employing a Count-Min Sketch[2] where the counter matrix is represented by an array with length=width*depth. Width is at least the given capacity of the cache for accuracy, but is increased to the next power of two. The depth is 4 by default.

The frequency of all entries is aged periodically using a sampling window based on the maximum number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps the sketch fresh by dividing all counters by two.

Constructors

new
FrequencySketch(capacity: number, depth?: number)

Properties

private
depth: number
private
maxFrequency: number
private
resetSize: number
private
size: number
private
table: Uint8Array

The widthXdepth matrix of counters represented as an array.

private
width: number

Methods

private
rehash(a0: number)
private
reset()

Halves every counter and sets new size

private
tableIndex(
hash: number,
cHash: number,
depthIndex: number,
)

Returns the table index associated with the given hash and depth index.

private
tryIncrementCounterAt(
hash: number,
cHash: number,
depthIndex: number,
)

Increments counter if it is not already at maximum. Returns true if the counter was incremented, false otherwise.

contains(hash: number)
frequency(hash: number)

Returns the estimated frequency of the given item. Up to a maximum.

hash(item: T)
increment(hash: number)

Increments popularity of given item up to a maximum. Downsamples popularity if a certain threshold is reached.