bedrock-kv / bedrock / abc99faa38a80b963c0a9f07a9c5aabb15b9a104

82%

Build Type

push

github

Committed by web-flow

Commit Message

Prevent missing Olivine reads after right-edge page splits (#229)

## Why

Olivine routes a key through a tree whose boundaries are the last key on
each index page. Page 0 begins as the only page, but after the first
split it becomes the **leftmost** page.

When a key sorted beyond every stored boundary, the old fallback still
returned page 0. That sent new maximum keys back to the left edge,
creating overlapping page ranges and an out-of-order page chain. The
value bytes were written successfully, but point reads could route to
the wrong page and range reads could omit committed keys.

For example, after a split:

```text
page 0: a..f
page 1: g..m
```

A write for `z` must extend page 1. Sending it to page 0 produces
`a..f,z` before `g..m`, so the global index is no longer ordered.

The regression test reproduces this with 600 increasing keys written as
600 separate transactions, matching append-heavy metadata workloads.

## What changed

- Keys beyond the largest boundary now route to the page stored at
`:gb_trees.largest/1`, which is the actual rightmost page.
- Unit and property expectations now require routing to an existing
rightmost page rather than assuming page 0.
- Recovery validates the reconstructed index before accepting it:
  - page 0 exists;
  - map keys agree with embedded page IDs;
  - the page chain has no missing links or cycles;
  - every recovered page is reachable from page 0;
  - keys are globally ordered and unique across page boundaries;
- required version records exist and predecessor versions descend
correctly.
- Complete snapshots are validated before selective loading can hide
orphan pages.
- `IndexManager` restores the recovered data-file offset, and the index
analyzer reports structured corruption errors.

## How it works

### Routing new maximum keys

Normal lookups still choose the first page boundary greater than or
equal to the key. Only the no-boundary case changes:

```text
key e  -> boundary f -> page 0
key k  -> ... (continued)

Coverage Stats

63 of 68 new or added lines in 4 files covered. (92.65%)

3 existing lines in 2 files now uncovered.

7021 of 8731 relevant lines covered (80.41%)

1175.23 hits per line