IntersectMBO / IntersectMBO/lsm-tree

Refactor page/run tests that use the reference implementation

Open
#199 1 comment 0 reactions 0 assignees View on GitHub
enhancement lsm-tree priority: low
Dominant language
Haskell
Stars
53
Forks
17
Avg merge
2d 3h
Merged PRs (30d)
4

Description

Many of the existing tests use the `FormatPage.hs` reference implementation of the page binary format, the type `PageLogical` and its QC generator.

Prior to PR #195 the `PageLogical` representation was always valid, for all possible values of the representation (at least for the purpose of serialisation, which doesn't care about key sort order). That's because the reference implementation used an unbounded approach to serialisation, rather than insisting that the binary format fit within a fixed disk page size (like 4k).

In PR #195 we introduce fixed disk page sizes, to make the reference implementation and real implementation closer and thus give us an opportunity to simplify tests using the reference impl. A consequence is that `PageLogical` now represents a superset of valid pages, rather than exactly all valid pages, and so the `encodePage` now has to be partial.

Furthermore, the tests for the real implementation need (or could be simpler) with a few variations on key/value sequences.

## Existing tests

We review what existing tests do, or could do, to help us decide what set of types and QC generators would help us simplify and/or improve the tests. We go in rough order from low to higher level.

### RawPage

The `RawPage` module is for decoding.

Existing tests:
* a range of unit tests
* a range of focused property tests for each aspect of the page format, or part of the size distribution, comparing against the reference impl

Missing tests:
* A general test against the reference impl for the whole page content

The property tests want a type that represents a valid page (with total serialisation) with its logical content. This would make `toRawPage` total.

### PageAcc

This covers a single page, with many key/ops in it, but not the single page case with overflow.

Existing tests:
* general `prototype` test which compares the reference and real impls for a sequence of key/ops, including checking the sequences end at the same point.
* several specific instances of `prototype` providing guaranteed coverage (could perhaps be replaced by labels & coverage conditions)

The existing `prototype` comparison test could be simplified if we could turn it into a bulk comparison test. Would need a reference impl page construction that returns the suffix that didn't fit.

These tests want a sequence of key/ops that may or may not fit within a page. The generator should cover:
* single page, all operations
* more than will fit in a page
* probably wants a range of sizes: small, near page size

These tests need to exclude single value pages that overflow. This is covered by PageAcc1.

### PageAcc1

This covers a single page, with a single key/op in it, including the single page case with overflow.

Existing tests:
* two property test covering equal serialised pages between real and reference impl for single key with inserts or upsert
* instances of the two above for specific cases (could be replaced by labels and coverage conditions)

These tests want a generator for single key/operation pairs, wants a range of (single value) sizes: small, near page size, overflow, multiple overflow pages.

### IndexCompact

The tests here use their own page summary types for test case generation and it's unclear that they would benefit from improved types or generators for pages.

### RunAcc

This now covers a whole run, including the bloom filter and compact index.

Existing tests:
* now-redundant test about page size == 4k
* general test about page matches prototype
- currently uses only nearly full pages but unclear why
- generates keys that are >= 6 bytes, for compact index
- can probably just use the full range of sizes: small, nealy full, overflow, multi-overflow
* existing RunAcc tests are a bit of a mess after prior changes, they still talk about old PageAcc.

Missing tests:
* Need to test multi-page RFP partitioning
* Need general test for run consisting of multiple pages

These tests want a generator for key/op sequences that need not fit one page, and should cover multiple pages.

Need a RFP sequence partitioning, using reference impl within each partition. Reference impl does not need to be taught about RFP. But could provide a simple run construction using unfoldr + concat, in terms of a page construction returning the suffix.

### Run

This is like RunAcc but now does file I/O. Much the same tests should still work at this level though.

Existing tests:
* some unit tests
* round trip write then read, for real impl with itself
* property comparing write and open, for real impl with itself

Missing tests:
* comparison of serialised run against reference impl
* comparison of key/ops decoded from real run, vs original key/ops serialised by reference impl

The extra tests should mirror the RunAcc ones and so need the same types and generators.

## Proposal

1. key/op pair sequences corresponding to a valid page (thus fitting)
2. key/op pair sequences that may or may not fit into a page
3. single key/op pair for the single-value page case
4. key/op pair sequences corresponding to runs of multiple pages (with keys >= 6 bytes)

What would each test use:
* RawPage would use 1
* PageAcc would use 2
* PageAcc1 would use 3
* RunAcc and Run would use 4

Extend reference impl to provide a construction function that returns the unconsumed suffix.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.