[0.6.0][develop] Olivine routes new maximum keys to page 0 after a split, causing missing reads

[mikehostetler]

Summary

Olivine can make committed keys unreadable after its index has split into multiple pages.

Index.Tree.page_for_key/2 returns page 0 when the requested key is above every stored page boundary. Page 0 is the leftmost page after a split. A new maximum key must go to the actual rightmost page.

Repeated increasing writes therefore extend page 0 across later pages. This creates overlapping page ranges and an invalid page chain. Point reads can return :not_found, and range reads can omit committed keys.

The value data remains in the data file. The index no longer routes reads to it.

Affected versions

Confirmed on:

• Bedrock 0.6.0, tag commit a22a1516dddb879627c4174b98235077c11a64d0
• Current develop, commit 306c55bb7bd6c5546dbab65b58cb617a8b69bbd7
• Elixir 1.20.2
• Erlang/OTP 29.0.2

The affected source and test files have the same Git blob IDs in 0.6.0 and current develop.

Root cause

The current fallback is:

case :gb_trees.next(iter) do
  {_last_key, page_id, _next_iter} -> page_id
  _none -> 0
end

Page 0 starts as the only page, so this is correct before the first split.

After a split, page 0 remains the leftmost page. The fallback must return the page ID stored at the largest boundary in the tree. Returning 0 sends new maximum keys back to the left edge.

The existing unit test currently encodes the incorrect rule:

assert Tree.page_for_key(tree, "z") == 0

Affected source:

bedrock/lib/bedrock/data_plane/materializer/olivine/index/tree.ex

Lines 45 to 62 in 306c55b

	@doc """
	Finds the page that contains a specific key. With no gaps, every key
	maps to exactly one page. Uses gb_trees iterator for efficiency.
	Tree structure: key = last_key, value = page_id
	When a key is beyond all pages in the tree, returns page 0 (which acts as
	the catch-all page extending to infinity).
	"""
	@spec page_for_key(t(), Bedrock.key()) :: page_id()
	def page_for_key(tree, key) do
	iter = :gb_trees.iterator_from(key, tree)
	case :gb_trees.next(iter) do
	{_last_key, page_id, _next_iter} -> page_id
	_none -> 0
	end
	end

Affected test:

bedrock/test/bedrock/data_plane/materializer/olivine/index_tree_test.exs

Lines 7 to 28 in 306c55b

	describe "page_for_key/2" do
	test "returns correct page for key insertion" do
	page1_kvs = [{"a", <<1::64>>}, {"f", <<2::64>>}]
	page2_kvs = [{"g", <<3::64>>}, {"m", <<4::64>>}]
	page1 = Page.new(1, page1_kvs)
	page2 = Page.new(2, page2_kvs)
	tree =
	:gb_trees.empty()
	|> Tree.add_page_to_tree(page1)
	|> Tree.add_page_to_tree(page2)
	# Key "c" should go to page 1 (contains "a" to "f")
	assert Tree.page_for_key(tree, "c") == 1
	# Key "j" should go to page 2 (contains "g" to "m")
	assert Tree.page_for_key(tree, "j") == 2
	# Key "z" (beyond all pages) should go to rightmost page (always 0)
	assert Tree.page_for_key(tree, "z") == 0
	end

Clean reproduction

I added 600 increasing keys as 600 separate transactions. This matches metadata-style workloads where keys are created over time.

A standalone regression test is here:

https://github.com/mikehostetler/bedrock/blob/e07fdc2d4ed4b44cfc4258ff59c0fcdbeabcbf02/test/bedrock/data_plane/materializer/olivine/page_chain_recovery_bug_test.exs#L243-L265

Against clean upstream develop, the test reports:

range read returned 129 of 600 keys;
128 point lookups returned :not_found

No Hancho code is used in this reproduction.

Production observation

The failure was first found in a repository-local Bedrock cluster used by Hancho.

The recovered index contained four pages. Each page was internally sorted, but the complete page chain was not sorted. Page 0 overlapped later pages. Two keys were duplicated across pages.

A queue record was present in the data and index files, but the rebuilt tree routed its lookup to a different page and returned :not_found.

Expected behavior

• New keys above the current maximum extend the actual rightmost page.
• Page ranges remain ordered and do not overlap.
• Every committed key remains available through point and range reads.
• Recovery detects an invalid global page order instead of accepting it.

Suggested correction

1. When iterator_from/2 has no result, return the page ID from :gb_trees.largest/1.
2. Add a regression with more than one page and many increasing, single-key transactions.
3. During recovery, validate:
   • the complete page chain;
   • global key order across pages;
   • duplicate keys;
   • page count against the reachable chain.
4. Existing damaged stores need either:
   • a canonical page-map repair; or
   • an explicit corruption error with a repair tool.

A tested reference implementation is available in the mikehostetler/bedrock branch hancho/bedrock-next.

The prevention and recovery implementation is commit:

mikehostetler@84e7cd3