Author: NoraCodes

During this Google Summer of Code, I built visn, a testing framework designed specifically to integration-test Rust projects that rely on eventual consistency.

Originally, I imagined that a full network simulator was needed to thoroughly exercise the qaul.net API, as I discussed in my initial blog post. While sketching out designs for the libqaul API, as seen in this pull request (which influenced the actual service API), I discovered that it made much more sense to simply simulate the events coming into an individual instance. This is simpler to design, easier for developers to use, and less computationally complex.

That insight lead to the idea of a generic, easy-to-extend testing framework which could be used to test qaul at multiple levels at once. This framework, discussed in more detail in my second blog post, essential boils down to a mechanism for writing tests in an easy-to-read format which is transformed into calls into the system under test.

While working on this idea, I was also involved in several pull requests which added various capabilities to the libqaul API, including adding the Message struct and designing security and consistency validation steps for messages.

Eventually, my first pull request for visn itself came along. I got a lot of useful feedback and decided that the easiest way to make sure I was writing the right kind of test framework was to actually use it, by implementing features in libqaul and testing them at the same time as I implemented features in visn. This lead to my third blog post, on the value of this approach to what I call “conceptual” testing and my first PR that actually implemented and tested some libqaul features, along with the PR that fixed the issues I mentioned in that blog post.

Around this time, the project moved to a GitLab instance, so my PRs were somewhat split. In addition to a first stab at a contacts book API, which I later revised, I added the most recent visn feature, and in my opinion, one of the most useful: permutation testing.

In essence, rather than simply testing a single order of events, visn now allows testing all possible orderings of a set of events. This is, of course, and O(n!) algorithm, since there are n! orderings of n events, but I was able to do it pretty efficiently with the use of what eventually became the permute crate.

permute uses a data structure, called an ArbitraryTandemControlIterator, that stores both a reference to an array (a “slice”) and an iterator over indices to that array and transparently iterates over references to elements in that array. This way, copying of the array’s elements is kept to an absolute minimum, reducing both computational and memory footprint.

For example, reversing the elements of a vector using an ATCI:

let data = vec![
    String::from("red"),
    String::from("orange"),
    String::from("yellow"),
    String::from("green"),
    String::from("blue"),
    String::from("indigo"),
    String::from("violet"),
];

let control = vec![6, 5, 4, 3, 2, 1];

let atci = ArbitraryTandemControlIterator::new(&data, control.clone().into_iter());

for (atci_val, rev_val) in atci.zip(data.iter().rev()) {
       // Critically, these are both &std::string::String. No copying occurred.
       assert_eq!(atci_val, rev_val);
}

Of course, control could just as easily be vec![6, 5, 6, 4, 4, 3, 2, 1] or any other combination of valid indices.

Combined with an implementation of Heap’s algorithm for permuting lists, permute can provide an efficient method of generating all possible orderings in a deterministic way.

With that done, I was able to add a sample all-orders test for some aspects of the libqaul API, and tidy up the internal testing crate so that others can use this work. Once these two merge requests are reviewed and accepted, the visn testing framework and the service_sim crate in the qaul.net tree will be fully able to support ongoing libqual development.

Google Summer of Code with Freifunk has been a wonderful experience during which I’ve worked with cool technologies, amazing peers, and extremely helpful mentors. Overall, I think it’s made me a much better technologist and programmer, and I’d like to wholeheartedly thank Google, Freifunk, and my mentors for the amazing opportunity.

While working on the visn eventual consistency testing framework for the qaul.net project, I’ve run into an excellent example of one of the most important reasons to test software, in some ways more important than the discovery of regressions, design defects, or other functional issues. Specifically, the ability to determine problems in the conceptual model around which the software is built.

Conceptual Testing

Unit, integration, and acceptance tests are well known for their value in detecting regressions, ensuring that functions, classes, and other units are written in a self-contained and composable style, and ensuring that design goals are met throughout the lifecycle of the project.

In statically typed languages like Rust, however, it can often be tempting to eschew the fine-grained level of unit testing used in dynamic languages, since the compiler checks many of the constraints unit tests are designed to impose. Rust, for example, permits encoding a lot of detail about the presence, or absence, of values with the type system.

In qaul.net’s libqaul, we provide a model for metadata about a user in the UserData struct (from libqaul/src/users/mod.rs):

/// A public representation of user information
///
/// This struct is used for both the local user (identified
/// by `UserAuth`) as well as remote users from the contacts book.
#[derive(Default, Debug, PartialEq, Clone)]
pub struct UserData {
    /// A human readable display-name (like @foobar)
    pub display_name: Option<String>,
    /// A human's preferred call-sign ("Friends call me foo")
    pub real_name: Option<String>,
    /// A key-value list of things the user deems interesting
    /// about themselves. This could be stuff like "gender",
    /// "preferred languages" or whatever.
    pub bio: BTreeMap<String, String>,
    /// The set of services this user runs (should never be empty!)
    pub services: BTreeSet<String>,
    /// A users profile picture (some people like selfies)
    pub avatar: Option<Vec<u8>>,
}

This struct provides Optional types for every field, except for those fields which can contain nothing (like the BTreeMap or BTreeSet), since by design, a user may not have set any of these fields. This works really well for user storage, which was the original purpose of the data structure, but does not work well for user information transmission, as I found out.

Conceptual Problems in the User Model

Initially, libqaul was designed to use the UserData struct for all user data needs, including transmission. Some of the UserData related API surface was the first that I implemented during the initial deployment of visn, and therefore the first API surface to be tested. During that process, I mapped the function Qaul::user_update() to a visn synthetic event, UserUpdate, which carried a UserData to be passed to user_update().

While writing these tests, I encountered a problem: what happens in the case that a user wants to clear a field in their UserData? Do they issue a UserData in which there is an Option::None value in that field (like a null), which is interpreted to mean that the field should be cleared?

This made the user_update() function very easy to implement, since it could simply assign the newly received UserData as the new canonical UserData for that user. That, however, leads to a problem when it comes to data transmission over the actual network. When, for example, a user has set a profile photo or a lot biography fields, the UserData could be pretty large, and retransmitting that on every subsequent update is not very practical.

The act of writing these tests, which were primarily designed to prevent regressions, lead me to implement a delta-based UserData update scheme, wherein the UserData is updated incrementally with small changes. This provides other advantages, too, such as allowing more orderings of those events’ arrivals to result in a valid state for the UserData.

Conceptual Problems in visn

In addition to uncovering problems in the design of libqaul, this process helped me refine my ideas for the visn testing framework. Initially, visn assumed that all operations modelled by synthetic events were infallible, or at least that failure to perform an action should lead to test failure. In fact, a critical component of eventually consistent systems is their ability to reject invalid states, in order to remain robust in the face of serious network problems or malicious input.

Originally, the resolve function took the state of the system under test and an event, and returned the new state (Fn(Event, System) -> System).

To address this problem, visn‘s type model became even more complex, incorporating a separate return type rather than requiring that the function which resolves events always return a successfully transformed state (Fn(Event, System) -> Return), and the infallible variant now simply sets Return to System.

In addition, rather than taking a singular System argument when resolving events, visn now takes a function returning a System, laying the groundwork for supporting multiple permutations of the ordering of queued events.

Conclusion

Testing is important for both compiled and dynamic languages to prevent defects and enforce good factorization, but the benefits to compiled languages can, like many design processes, be moved “left”, into the pre-execution step. As seen here, the simple act of writing tests often leads to conflict with the type system and compiler that can reveal conceptual and design defects in the system being tested.

As I wrote in my prior blog post, I am working on qaul.net for this GSoC. Specifically, I’m working on simulating various components of the system so that other parts can be tested and developed independently, reducing the overall coupling between various elements.

There is, however, some inevitable coupling. My original design called for three phases of implementation: quickly simulating a network of hosts, accurately portraying a qaul.net network, and providing a HTTP API mirroring the real qaul.net service, in that order. As it turns out, the API is not well enough defined at the moment to work from the ground up on the simulator, so I’ve focused my efforts onto the API itself and the second step of the process.

visn

visn, meaning “knowledge” in Yiddish, is the testing framework I’ve created to bypass some of the initial effort of building a real simulation of the eventually-consistent real world network. Instead, visn uses synthetic event streaming to simulate incoming messages, which are translated into actual mutations of the state of a node through a resolution function.

For example, we could define some synthetic events such as MessageReceived and FileUpdate. Our node under test, A, receives two FileUpdate events for some file (say,hello.txt), one creating the file and then one changing its contents, and a MessageReceived whose message refers to hello.txt.

It’s desirable to have the final displayed message show the updated contents of the file. To test this, we define the mapping from synthetic events to real state changes, and then write tests for each possible arrival order case.

Without visn, managing these changes becomes rather challenging. With a framework in place to manage the state and order of arrival, however, all synthetic event translation can be done in a single function, and each test is decoupled from the rest of the software, so true unit tests can be used.

The Big Picture

Now that visn is in a working state, I can use it to help build out the libqaul API and start testing its components. This will help make future development faster, as well as providing a target for more detailed network simulation in the future.

qaul.net allows spontaneous, ad-hoc networks to form between any wireless-enabled devices over whatever medium is available. Currently, the project is undergoing a Rust rewrite, which will provide enhanced security, modularity, and performance.

As with any rewrite, testing is a major component of the process. In the case of qaul.net, that requires a fairly sophisticated model of the underlying network protocols in use and even some of the physics behind them (like jitter, also known as “lag spikes”, which has the potential to foul up any routing protocol).

Project Overview

The problem of building a simulator is a common one, but in this case it is somewhat complicated by its dual use here, in both automated testing and as a way to quickly provide (fake) data to new applications, UIs, and other software components.

The simulator needs to be able to quickly simulate a network of hosts communicating over various media, accurately portray a qaul.net network complete with cryptographic identity management, and finally provide a HTTP API mirroring that of the real qaul.net service, so applications can develop against a known-good testing state.

Quickly simulating a network of hosts is relatively easy. Using an existing graph datastructure library (petgraph), along with ancillary data structures, the simulator will build a world state model representing hosts as vertices and connections (over Wi-Fi, Bluetooth, and even Internet overlay connections) as edges. Then, the simulator will provide a “tick”-based simulation model in which messages are passed from host to host via each medium in a simulated timestep.

Accurately portraying a qaul.net network is a little harder, but not much more so. With the network simulator built up, each host needs only to be given a small amount of behavior and a cryptographic identity to begin to act like a real qaul.net network. This behavior will be parametric, so testing all kinds of scenarios (including adversarial ones) will be possible.

Providing a HTTP API mirroring the real qaul.net service is the final step, and will probably mean wrapping the simulator in an asynchronous shell so that a Futures-based HTTP library can run alongside it. Once this is complete, the webserver can be spun up and applications can be pointed to it as though it were a real network!

Progress So Far

Up to now, I’ve spent my time getting comfortable in the qaul.net Zulip chat and evaluating the fundamental abstractions that I’ll use to build the simulator core. I currently have about a hundred lines of code written, in addition to a few “spike” components that I wrote just to test out various concepts. Starting today, though, the real code is happening!

About Me

I’m Leonora, a computer science student at Beloit College. I’ve written a lot of Rust and really like the language, but I’ve spent most of the last two years working on data analysis applications like the Open Energy Dashboard and CancerIQ. I’m super excited to be working on the next generation of qaul.net and the open, decentralized internet!