DB From Zero

Projects | Blog | Code

In initial DB From Zero projects, I developed few if any unit tests for correctness. Tests were only developed to expedite debugging issues that were encountered in benchmarking. I simply didn't feel tests were necessary for these exploratory and educational projects.

In doing so, I've been remiss in my duties as a software engineer. After all, what is the point in doing all this work to develop and benchmark database components if the end result is buggy. Is it even useful to benchmark incorrect code?

Further, I find that including unit tests in development encourages a developer to create better software interface with more thought around how components are composed so as to facilitate testing. And this ultimately leads to components that are more re-usable. Therefore, going forward, I aspire to write more tests for the projects that we develop in DB From Zero.

To facilitate the testing of the disk-based storage engines we're developing, I've introduced abstractions for all file and directory operations. This allows for the use of in-memory stand-ins for use in running tests with faster execution times. Further, this alleviates the need to setup and configure a writable file system in our CI environment. I generally try to take this approach in my professional work and am excited to fully apply this approach in all DB From Zero projects.

public interface ReadOnlyFileOperations {

  boolean exists();

  long length();

  InputStream createInputStream() throws IOException;
}

public interface FileOperations<T extends OutputStream> extends ReadOnlyFileOperations {

  T createAppendOutputStream() throws IOException;

  void sync(T outputStream) throws IOException;

  void delete() throws IOException;

  OverWriter<T> createOverWriter() throws IOException;

  interface OverWriter<T extends OutputStream> {
    T getOutputStream();

    void commit() throws IOException;

    void abort();
  }
}

public interface FileDirectoryOperations<S extends OutputStream> {

  boolean exists();

  List<String> list() throws IOException;

  void mkdirs() throws IOException;

  void clear() throws IOException;

  FileOperations<S> file(String name);
}

Additionally, I've been working on a general-purpose ReadWriteStorageTester<K, V> that performs a random sequence of 'put', 'get', and 'delete' operations on a ReadWriteStorage<K, V> instance. It also performs these operations on a companion Map<K, V> and compares the results of the tested storage engine against the companion map, asserting for correctness. Here's an example of using the ReadWriteStorageTester<K, V> in testing.

  @Test public void testSingleThreaded() throws IOException {
    var create = createTree(1000);
    var operations = create.getLeft();
    var tree = create.getRight();
    var builder = ReadWriteStorageTester.builderForBytes(tree, RandomSeed.CAFE.random(), 16, 4096)
        .debug(true)
        .checkDeleteReturnValue(false)
        .checkSize(false);
    var count = new AtomicInteger(0);
    builder.iterationCallback((ignored) -> {
      if (count.incrementAndGet() % 1000 == 0) {
        LOGGER.info("iteration " + count.get() + " size " + 
          Dbf0Util.formatBytes(getDirectorySize(operations)));
      }
    });
    var tester = builder.build();
    tester.testPutDeleteGet(10 * 1000, PutDeleteGet.BALANCED, KnownKeyRate.MID);
  }

With debugging enable, it logs the operations performed to assist in debugging any issues.

05:55:50.880 FINE get a0828cd6d947fed0b3c1e6aecc82067f
05:55:50.880 FINE get ByteArrayWrapper{prefix=daa54e6614deed58, length=17, hash=1637135279}
05:55:50.880 FINE put 17d4ccd9d558a56f59a1bc33d7eea218=ByteArrayWrapper{prefix=38e69f568b4c1299, length=4096, hash=1958503476}
05:55:50.880 FINE get 7b4a0c30329fefb83d4b554499198b90
05:55:50.880 FINE put 2288c3abeceaee37d465c59bd979ce42=ByteArrayWrapper{prefix=160cf9011a7c01f5, length=4096, hash=445556146}
05:55:50.880 FINE get 17d4ccd9d558a56f59a1bc33d7eea218
05:55:50.880 FINE del 7b4a0c30329fefb83d4b554499198b90
05:55:50.880 FINE del 9901bf4e373f7db9a6987b2103a2356c
05:55:50.880 FINE del ByteArrayWrapper{prefix=2329cee83ab3dc61, length=17, hash=-876173019}

Using the newly developed file abstractions and ReadWriteStorageTester, quite a few tests have been added to the project.

I must admit that I didn't manually write 5070 different test cases. The high number of tests cases result from using the burst library to automatically generates tests using all combinations of defined parameters. Here's an example of using burst.

@RunWith(BurstJUnit4.class)
public class BlockBTreeTest extends BaseBTreeTest {

  @Burst Capacity capacity;

  @Test public void testAddDeleteMany(RandomSeed seed, Count count, KeySetSize keySetSize) {
    var btree = bTree();
    ReadWriteStorageTester.builderForIntegers(btree, seed, keySetSize)
        .debug(isDebug())
        .build()
        .testAddDeleteMany(count.count);
  }

  ...

A testAddDeleteMany test case is generated for every combination of Capacity, RandomSeed, Count, and KeySetSize. This allows us to easily test a large number of different scenarios and discover infrequently encountered bugs in testing.

I'm pleased with the addition of these unit tests for correctness. Please hold me accountable for continuing to develop unit tests in future projects.