IntersectMBO / IntersectMBO/lsm-tree
Refactor page/run tests that use the reference implementation
- 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
Assessment
This issue has not been assessed yet.