mstar.engine.resources.kv.prefix_index

The prefix index: which cached page holds which key, and which to drop first.

Inserting makes the index a page’s second owner, so evicting releases that one reference and the page reaches the free list only once no live request holds it too. Leaves are ordered by a clock that ticks on every insert and every matching lookup. A hit re-stamps a page without pushing it again, so a leaf keeps one heap entry however often it is read, and an entry that surfaces under an older stamp is pushed back under the page’s own.

Every caller holds the manager’s lock, so none of this takes one of its own.

Classes

PrefixIndex(arena)

class mstar.engine.resources.kv.prefix_index.PrefixIndex(arena)

Bases: object

Parameters:

arena (PageArena)

evict(n)

Drop the oldest leaves the index alone holds, until n are free.

A leaf a request or a lease also holds is passed over and put back: dropping it would free nothing and lose an entry that is still good. Returns how many pages reached the free list.

Parameters:

n (int)

Return type:

int

insert(key, page, parent=None)

Name page by key under parent; the first writer wins.

Parameters:

• key (bytes)

• page (int)

• parent (int | None)

Return type:

bool

lookup(keys)

Walk keys from the root and stop at the first one not indexed.

Parameters:

keys (Sequence[bytes])

Return type:

list[int]

num_pages()

How many pages the index holds a reference to (len(pages())).

Return type:

int

num_sole_owned()

Indexed pages nothing else holds: an upper bound on what evict can free.

Return type:

int

page_for(key)

Parameters:

key (bytes)

Return type:

int | None

pages()

Every page the index is holding a reference to.

Return type:

list[int]