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.

bumped_score(row, now) #

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

Source code in capturegraph-lib/capturegraph/recipes/scratch/store/eviction.py 
43
44
45
46
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/recipes/scratch/store/eviction.py 
49
50
51
52
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/recipes/scratch/store/eviction.py 
37
38
39
40
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/recipes/scratch/store/eviction.py 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def evict(scratch: Scratch) -> None:
    """Delete the lowest-density unheld objects until the store fits its budget."""
    now = time.time()
    evicted = 0
    with scratch.database.transaction() as db:
        release_leaked(scratch, db)
        total = objects.total_size(db)
        budget = scratch.settings.budget_bytes(available_bytes(scratch.root), total)
        exempt = names.kept_hashes(db) if total > budget else set()
        for row in sorted(objects.all_rows(db), key=lambda row: density(row, now)):
            if total <= budget:
                break
            if row.hash in exempt or _held_by_a_living_owner(scratch, db, row):
                continue
            objects.delete(db, row.hash)
            remove_tree(scratch.object_dir(row.hash))
            total -= row.size_bytes
            evicted += 1
    if evicted:
        logger.info(f"eviction: freed {evicted} objects, store now {total} bytes of {budget}")