Database design
This design document describes the requirements, use cases and the design of the data store into which Kyua will keep the data it generates, and the kind of reports we want to extract out of this data store.
As we shall see soon, the data stored in the database obviously includes test results, but will eventually include build logs and other miscellaneous test results as well.
Please note that this is pretty much a draft. In particular, the design of the database is still incomplete (there is no formal definition of the schema). I still have to perform some experiments to cover the missing points. That said, the current contents already represent a pretty accurate idea of how I want things to move forward.
The user and developer has to be able to obtain a detailed report of the execution of a collection of tests right after they have been executed. In general, the user will build a piece of software, run the tests and, at this point, want to inspect what happened if there was any failure. This is, by far, the most basic and common use case.
This is the only functionality provided by atf-report, which we are trying to replace.
Generate a report with the results of the execution of a test suite in multiple platforms and/or operating systems.
A possible user-friendly representation for this would be a matrix where the columns are the platforms, the rows are the test cases and each cell holds the history of the test results. Platforms and tests can come and go at any particular execution, so "nulls" in any given cell are expected.
This is a problem that arises from the previous requirement: when we run a collection of tests in different platforms or environments, the test suite may be located in different points of the file system (e.g. /home/jmmv/local/tests in NetBSD vs. /Users/jmmv/local/tests in Mac OS X). The database has to provide a mechanism to recognize that different paths at different points in time actually represent the same collection of tests for reporting purposes.
Reports should include as much information as possible to allow for "post-mortem" debugging. Some test failures may be hard to reproduce, specially if the failure condition is not repeatable, so gathering the information when the crash happens (instead of at debugging time) helps in this situation.
Among other things, we can collect the following:
- The output (stdout, stderr) of the program.
- The stack trace leading to the failure.
- The listing of the work directory and, maybe, its contents.
Keeping the contents of the work directory around may be useful to investigate the values of particular temporary files, but this data may grow out of control size-wise. The user should be able to choose what data is recorded per test case and, specially in the case of the contents of the work directory, specify how long such data should be kept for.
Extract the history of a particular test case. This history needs to include the properties of the test case and its results and logs over time.
Not all test suite executions will deliver a result for a given test case. For example, if we have run a test suite 10 times and a test case disappeared after the 5th time (because it was removed from the test suite), it is perfectly fine to return only 5 results.
One of the "hidden" goals of Kyua is to become a "Q.A. framework", not just a testing framework. By this I mean that Kyua needs to provide mechanisms to assess the correctness of many different parts of the release engineering process, and these include building the software and generating the release itself.
Therefore, we need to be able to bundle build results and other arbitrary test (such as distribution-file tests) into the report. For example: in a continuous integration system, a build failure is as common as a test failure. Both should be reported to the user in the same final report so that the user does not need to look at different data sources to get information about "failures" in the code.
While Kyua has no knowledge of build results at the moment, the database design needs to leave room for these requests.
The initial database that will come out of this design will by no means be perfectly designed and, therefore, will need changes to its schema over time. This is expected and acceptable. Therefore, Kyua needs to provide a mechanism to transparently upgrade from a database using an old schema to a new schema. I particularly like how Monotone does this with its mtn db migrate command.
Kyua has to be able to identify what schema version a given database is using so it can determine how to migrate it to a more modern schema.
Let's start by analyzing what the obvious and naive solution to the requirements above would be, in the form of a database to store all the information required. As we shall see, this approach might work but it does not really suit the current model of Kyua.
The obvious approach would be to define these concepts:
- Test case: an individual unit of execution that yields results. Identified by a name and the test program it belongs to.
- Test program: an collection of test cases, supposedly with some semantic relation. Identified by the name and the test suite it belongs to.
- Test suite: a collection of test programs that belong to a particular program, library or system. Identified by the name recorded in the
Kyuafileor by the location of theKyuafileon disk.
With these concepts, the obvious test case identifier would be a triplet of the test suite identifier plus the test program identifier plus the test case identifier. Unfortunately, this identifier relies on the way we define the identifiers of the test suite and test program, and this is a tricky thing to do due to the way Kyua represents test suites as hierarchies on the file system.
Let's see what the problems are and the possible solutions we have.
There is no strict definition of a test suite in Kyua: a "test suite" is defined by a directory containing a Kyuafile, but no directory is more special than any other. In particular, we can observe the following facts:
- Each directory in the file system is potentially a test suite, and they are all equally important.
- Corollary: no directory can be said to be the "root" of the test suite. The "root" is only a conceptual concept, but has no effects on the execution of the tests themselves.
-
Kyuafiles define a "test-suite" property, but this has no correlation to the file system layout. This property is used to define the set of configuration variables that apply to the test programs in that test suite. Because this property belongs in theKyuafiles, and because noKyuafilecan affect the behavior of another, nested directories may belong to different test suites even if they are all executed in the same run; even disjoint directories can be part of the same test suite by means of the value listed in theKyuafile.
Consider the following example which assumes that the open source packages GLib and pkg-config provide Kyua-based tests (this is purely fictitious):
-
/usr/tests/Kyuafile: defines no test suite. -
/usr/tests/glib/Kyuafile: defines aglibtest suite. -
/usr/tests/pkg-config/Kyuafile: defines apkg-configtest suite. -
/usr/tests/pkg-config/glib/Kyuafile: also defines aglibtest suite. Thisglibis a subdirectory ofpkg-configbecausepkg-configships (or used to ship) with its own copy ofglib. Thepkg-configpackage does not modify the test suite definition in itsglib/Kyuafilesubfile because it has no control over such files.
In this scenario, you may note that we have two directories claiming to belong to the glib test suite, yet they are disconnected on the file system. This is fine, but we can make no assumptions regarding the connection of the pkg-config/glib subtree with the top-level glib tree. Furthermore, these two subtrees could belong to two vastly different versions of the same package, yielding to two very different versions of the test suite: joining their results into the same report could be very confusing.
The above example also has implications on the way we identify our test programs. Consider these problems:
- If we run the tests from
/usr/tests/gliband later from/usr/tests/pkg-config/glib, should we detect that they belong to the same test suite and, if so, attempt to interleave their results in the same report? Even if we could detect this fact, mixing the test results from the two hierarchies on the same report might be the wrong thing to do, because the two test suites may be completely different and thus any matches in the identifiers would be misleading. - If we run the tests from
/usr/tests(the top-level tree) and later from within/usr/tests/pkg-config, should we reconcile the results of both executions? The answer should be yes because, as mentioned before, no directory is more special than any other. However, because there is no concept of a "top" directory, we cannot easily do this.
Another problem arises when/if we rename tests or directories. For example, what would happen if we renamed /usr/tests to /mnt/usr/tests? (Note that I chose /mnt on purpose; you could imagine a system network-mounting tests from another and thus putting them in a different path.) Could we continue to recognize the test programs inside the new directory as matching the old one, so that we could maintain a single historical record of every test case?
If we find a way to represent the test suites that is disconnected from the location on the hard disk, we could achieve this. But if we did that, the representation would not match reality, and then we could have problems reconciling test programs as mentioned in the previous section.
Lastly, why are we putting so much emphasis on the concept of a "test suite"? Storing the results of a "test suite" should be no more special than storing the build logs of the code that generated that test suite, or validating that the distribution file created afterwards fulfills some quality criteria.
In other words, the fact that Kyua does not have a strong test suite definition mixes well with the requirement of being able to store arbitrary "results" that do not come from the execution of tests themselves. We need to figure out a way to intermix all kind of data and results under a single identifier, and this should not be tied to the concept of a test suite definition.
The main problem we are facing in how to identify a test case in the context of the database and how this identifier carries on across different executions of it. With all the above in mind, we can propose the following alternative design ideas. Note that not all of them will play well with the problems described so far, but it is good to consider them nonetheless.
Identify tests by their relative path to the top of the test suite.
- The "top" is defined by the upmost directory containing a
Kyuafilein a test suite tree. This assumes that aKyuafilecan only include sub-Kyuafiles from directories immediately one level below, which is the current implementation in Kyua but may not be later on. - For reporting purposes (i.e. to report "what" was run), the test suite of these tests is the value of the test suite property in the top
Kyuafile. -
/usr/testswould have to be changed to define its test suite as "global" or similar so that running the tests from this directory would provide a meaningful name to the report and to act as an identifier.
The way to determine the system-wide top directory would be to walk up the directory tree looking for the upmost Kyuafile that indirectly includes the current directory. E.g. any test in the /usr/tests hierarchy belongs to the /usr/tests test suite regardless of where it is executed from. The root is the test suite identifier of the top Kyuafile (which in this case would be "global"). Reports can only be generated from a root only.
This design permits to differentiate ~/local/tests/kyua-cli/t_foo from /usr/tests/kyua-cli/t_foo, because the roots would be ~/local/tests and /usr/tests respectively. It is OK to consider these two programs as different because the name match may be just a coincidence. However, this design does not permit to reconcile ~/local/tests/foo/kyua-cli/t_foo with ~/local/tests/kyua-cli/t_foo even if both t_foo belong to the kyua-cli test suite because their relative paths to the root are different.
Identify tests by their test suite name and their relative path to the test suite-specific top directory. This is similar to the previous case, but in order to determine the top directory of the test suite, we would walk the tree upwards until we reach the upmost Kyuafile that contains the same test suite name as the one in the current directory.
This design does permit to reconcile ~/local/tests/foo/kyua-cli/t_foo with ~/local/tests/kyua-cli/t_foo because the search upwards for the root would stop at kyua-cli in both cases and yield the same relative paths. It also simplifies reconciling test results for a particular test suite when run under different environments. However, this has the potential of generating false reconciliations.
Identify tests by a unique checksum that allows us to identify test cases across test suites and test programs without collisions. This is an idea that comes from the way distributed version control systems generate identifiers for revisions and other artifacts of the system.
The obvious approach would be to checksum the binary and use that as the identifier. This works for any given version of the test suite, but a simple rebuild of the code will cause all checksums to be different and thus we would not able to keep track of the history of a particular test case at all across system upgrades.
Another approach would be to generate a checksum based on the test case name, test program name, and the metadata properties of the test. This would generate a pretty unique identifier for a test no matter where it was located. However, the identifier would not work across updates to the test that change the metadata: a simple update on the test case description would yield two different test cases without any possibility of reconciliation.
Represent test programs directly by their absolute path and later represent test cases by their name plus the identifier of the test program. Don't attempt to determine roots of any kind and forget about the concept of test suites.
Reports are generated by scanning the list of results that correspond to a given subtree (i.e. generate a report for the whole of /usr/tests).
Because we can run tests from within any point of the file system, we get a sparse tree of results. The fact that we generate a report from within /usr/tests does not mean that we will get up-to-date results for all of the test cases in /usr/tests: we will only get the most recent results for every particular invocation of a test, and no result if a test has never been run. (For example, if we run the tests in /usr/tests/a but not the tests in /usr/tests/b, generating a report from within /usr/tests would show no traces of b; this is expected.)
In order to group the execution of tests, their build logs and any other kind of information, we define the concept of a session. The session is just a simplified way to refer to particular executions. Each session has a user-defined identifier and any test results are attached to that session.
This approach is extremely simple: there is no need to apply heuristics (which can lead to non-deterministic values) to determine the tests root. And this approach is very versatile because the user is in control of explicitly stating what ends up in a particular report. Furthermore, the user could intermix results from different sessions into the same report, thus providing the ability to merge data from different platforms.
However, the major problem of this solution appears when we move a tree (imagine executing tests in a destdir), or when we want to reconcile tests run under different platforms. A machine may be storing the tests in /usr/tests while another is storing them in /usr/local/tests, yet we know that such tests are exactly the same and we want them to be reported together. This problem can be fixed by giving the user the option of remapping directory trees on his own during report generation.
Consider this scenario: our NetBSD system stores its tests in /usr/tests and our FreeBSD system has its tests in /usr/local/tests. We run the tests on the former and assign a session name of netbsd; we run the tests on the latter and assign a session name of freebsd. During report generation, we tell Kyua to strip out the /usr/tests prefix from the netbsd session and to strip out the /usr/local/tests prefix from the freebsd session. By doing this, we end up with relative paths that can be reconciled; the user is the one who defined how this reconciliation happens, so he is the one responsible for defining a mapping that makes the most sense.
The approach that best suits the needs of Kyua is the last one (Absolute paths and sessions section). The rest of this document describes how to represent such design as a database and how Kyua will manage it.
This section describes the design of the Kyua database. This design should be independent on the backend data store.
In order to support seamless migrations from one database schema to another, we need to store metadata in the database to be able to recognize which version it is at. To do so, each schema is assigned a version number (a single integer) and the database records such schema version. Migrations only need to look at the current version of the database to determine what schema delta needs to be applied.
We define a metadata table that includes the following fields. Having this as a table allows for future extensibility:
- Schema version (integer).
A session is a collection of database entities (e.g. test results and build logs) grouped by the semantics of a high-level task. For example, the logs of a particular build and the results of running the tests of such build form part of the same session.
A session also includes information of the environment in which it is created. Running the same test suite in two different machines will yield two different sessions because the environment in which these run are different.
The following properties for part of the session:
- Identifier.
- Start and end timestamps.
- Hostname.
- Operating system identifier. This is the equivalent of
uname -a. - Current directory.
- Environment variables.
- User (and potentially other user privileges such as group memberships).
- Configuration variables (as printed by
kyua config). - Free-form tags to easily select sessions.
From the above we deduce that sessions are used to tag runs of a test suite and relate such runs to a single system configuration. Therefore, in order to generate reports that include results from different system configurations (platforms), we need to be able to merge different sessions into a single report.
As an example, we could choose to select the newest sessions for every different operating system in the database and generate a report out of these. The report would have a column for every operating system name and a row for every test case.
Before discussing what session identifiers should be, let's take a look at the free-form tags. The way tags behave has a direct influence on the way sessions are identified.
Tags are just arbitrary textual labels assigned to sessions. The user decides what (if any) tags are applied to a given session, and they are not unique (different sessions can hold the same tags)
Tags can be seen as user-friendly names for the sessions. While the session definition itself includes a good deal of typed information, there are things that the user may want to represent but that are not covered by the session schema. The user can therefore define tags to attach extra semantics to the sessions, and to allow him to query such sessions later.
We can consider different session identifiers:
- Sequential numbers. New sessions automatically get a new identifier and the user has no control over them (though he does not need to have such control).
- A combination of different fields of the data. The triplet timestamp, hostname and current directory should be enough to generate a unique key, as one is unlikely to run two Kyua commands from the same directory on the same machine simultaneously. However, from the user's perspective, such identifiers are long and hard to type.
- Hash of a subset of the session data. This is just a hash over the triplet described on the previous point. The only benefit of this approach is that it is easier to type than the previous if the hashes can be shortened when no collisions are detected.
- User-assigned names. Sessions only exist as long as a user requests them, and when he does so he manually gives them a name.
We want to attach a sessions to every single invocation of Kyua because we want to be able to track all executions of all test case. In general, the sessions can be automatically created on-the-fly for read/write operations, but the user needs to be able to create sessions manually to later attach multiple disconnected operations to the same session (think about build plus test). Because of this, we can rule out the user-assigned names choice for identifiers.
Also, because sessions can be selected using any of their fields including the user-friendly names, having descriptive identifiers provides no much value. Actually, such identifiers hinder usability because they would become rather long and hard to type.
Therefore, identifiers are simply sequential numbers. They can be automatically assigned and are easier to type. The user will usually not have to use the identifier because he has other means of selecting sessions.
We store the following information about a test case:
- Test program path.
- Test case name.
- The session this test case belongs to. This is required because the properties below are not stable across runs, so we need to keep their history.
- Test suite name (the value that comes from the
Kyuafile). Has no relation to the location on the file system. - Metadata properties of the test case.
The identifier of the test case is the triplet of the test program path with the test case name with the session identifier.
Test case results can be represented by storing this information:
- Test case identifier.
- Start and end timestamps.
- Result state.
- Result reason.
- stdout, stderr and potentially any other files in the work directory.
The identifier of a result is just the identifier of its test case. Within a session, a particular test case can only have one result, and the test case itself already encodes the session the result belongs to.
All of the concepts described in the design section above can be very easily represented in a relational database. A relational database provides us the mechanism to describe tables, their keys, how they relate to each other and an excellent way to query the data in a variety of ways.
We could implement our own data store by saving each major data entity in a separate file, and the defining our own language to perform queries on such data. However, this is a major amount of work that can be simplified by using SQLite.
SQLite provides us the best of both worlds: it implements a relational database on top of a flat file, and the database engine itself is extremely lightweight.
As part of the requirements, we need to be able to multiplex results from different machines into the same database so that we can generate unified reports of results. This would be simplified if we used a full-featured, network-aware database server such as PostreSQL. However, Kyua should not depend on any such server due to its size, difficulty in configuration and the inability to import it into the NetBSD base system.
SQLite is not a network-aware. We cannot run a SQLite server to which different instances of Kyua from different machines talk to. However, we can get around this problem by providing a proxy server that acts as a gateway to a local SQLite database. We can then make any Kyua instances talk to this server to store their results.
As a first iteration of this design, there will be no separate database server. This simplifies the implementation and lets us implement a replacement for atf-report fairly easily. However, implementing this server in the future should be possible. Or, alternatively, we need to provide an easy way to swap database servers easily so, for the cases where network operation is permitted, we can plug PostgreSQL (or similar) without major issues.
This document has presented in good detail all of the major requirements that Kyua has regarding the generation of reports. In order to implement such requirements, the document has discussed possible alternative solutions and has settled on a particular design and database system that can fulfill such requirements.
The decision is to incorporate the use of SQLite into Kyua. As a first iteration, the main Kyua binary will talk to SQLite directly so no networked operation is possible. We will later provide means to make different machines running Kyua store their output in a single database by exposing the SQLite database through a server.