mstar.engine.resources.kv.prefix_index

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)[source]#

Bases: object

Parameters:

arena (PageArena)

assert_evictable()[source]#

Check that evict, run on a copy of the index and the owner counts, frees every page in the evictable set.

Return type:

None

evict(n, spare=None)[source]#

Drop the oldest leaves the index alone holds, until n are free. When spare accepts a leaf’s key, that leaf is dropped only once no other leaf is left.

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 the keys of the pages that reached the free list.

Parameters:
Return type:

list[bytes]

evictable()[source]#

Return the live set of pages evict could free. Callers read it and don’t keep it.

A page only the index holds is out of reach while a page below it is held, since eviction takes leaves only.

Return type:

set[int]

holds(page)[source]#
Parameters:

page (int)

Return type:

bool

insert(key, page, parent=None)[source]#

Name page by key under parent; the first writer wins. When the arena reports to this index and the index alone holds parent, page is filed with no parent. Filed under parent, a held page would keep evict from freeing parent, which the pool counts as evictable.

Parameters:
Return type:

bool

insert_run(keys, pages, parent)[source]#

Name pages by keys, each under the one before and the first under parent. A key already indexed keeps its page, and the next key goes under that page. Returns how many pages were inserted.

Parameters:
Return type:

int

key_of(page)[source]#
Parameters:

page (int)

Return type:

bytes | None

lookup(keys)[source]#

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

Parameters:

keys (Sequence[bytes])

Return type:

list[int]

num_pages()[source]#

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

Return type:

int

page_for(key)[source]#
Parameters:

key (bytes)

Return type:

int | None

pages()[source]#

Every page the index is holding a reference to.

Return type:

list[int]

pages_for(keys)[source]#

lookup without the stamp, for a walk that is not a hit.

Parameters:

keys (Sequence[bytes])

Return type:

list[int]

parent_key(page)[source]#
Parameters:

page (int)

Return type:

bytes | None

set_shared(page, shared)[source]#

Called when page gains or loses its one owner besides the index.

Parameters:
Return type:

None

touch(pages)[source]#
Parameters:

pages (Sequence[int])

Return type:

None