Skip to content

eviction

eviction #

Keeping the store under budget by evicting the least valuable bytes first.

An object's value is its use rate times the compute it spares, per byte: effective_score × compute_seconds / size_bytes. The use score is a leaky integrator over accesses, so the ranking is the greedy knapsack over compute-seconds saved per second per byte. Objects a kept name holds or a living process pins are never candidates.

A pass first reads the store's size from a snapshot, which waits on no writer, and stops when the store fits. Otherwise: inside one index transaction, unindex the chosen objects and rename their directories out of objects/ into a live workspace; after it commits, delete that workspace. The index is never locked across a large delete, and a tree re-sealed in between lands in objects/ afresh, out of reach of the delete.

bumped_score(row, now) #

row's use score after one more access at now.

Source code in capturegraph-lib/capturegraph/scratch/store/eviction.py
def bumped_score(row: ObjectRow, now: float) -> float:
    """``row``'s use score after one more access at ``now``."""
    elapsed = max(now - row.last_access, 0.0)
    return effective_score(row, now) - math.expm1(-elapsed / RECHARGE_SECONDS)

density(row, now) #

Compute-seconds row saves per second, per byte it occupies.

Source code in capturegraph-lib/capturegraph/scratch/store/eviction.py
def density(row: ObjectRow, now: float) -> float:
    """Compute-seconds ``row`` saves per second, per byte it occupies."""
    compute = max(row.compute_seconds, _MIN_COMPUTE_SECONDS)
    return effective_score(row, now) * compute / max(float(row.size_bytes), _MIN_SIZE_BYTES)

effective_score(row, now) #

row's use score decayed to now.

Source code in capturegraph-lib/capturegraph/scratch/store/eviction.py
def effective_score(row: ObjectRow, now: float) -> float:
    """``row``'s use score decayed to ``now``."""
    elapsed = max(now - row.last_access, 0.0)
    return row.score * math.exp(-elapsed / DECAY_SECONDS)

evict(scratch) #

Delete the lowest-density unheld objects until the store fits its budget.

Source code in capturegraph-lib/capturegraph/scratch/store/eviction.py
def evict(scratch: Scratch) -> None:
    """Delete the lowest-density unheld objects until the store fits its budget."""
    with scratch.database.read() as db:
        total, budget = _usage(scratch, db)
    if total <= budget:
        return
    with scratch.database.transaction() as db:
        release_leaked(scratch, db)
        total, budget = _usage(scratch, db)
        if total <= budget:
            return
        trash = scratch.live_dir()
        evicted = _move_aside(
            scratch,
            db,
            trash,
            total - budget,
        )
    trash.release()
    if evicted:
        freed = sum(row.size_bytes for row in evicted)
        logger.info(
            f"eviction: freed {len(evicted)} objects, store now {total - freed} bytes of {budget}"
        )