Item — HN Reader

Interesting read.

Relatedly, FoundationDB has a distributed testing framework called “Simulation”, which can simulate distributed failures on a single machine (thread!). Quoting from https://pierrezemb.fr/posts/notes-about-foundationdb/ :

> We wanted FoundationDB to survive failures of machines, networks, disks, clocks, racks, data centers, file systems, etc., so we created a simulation framework closely tied to Flow. By replacing physical interfaces with shims, replacing the main epoll-based run loop with a time-based simulation, and running multiple logical processes as concurrent Flow Actors, Simulation is able to conduct a deterministic simulation of an entire FoundationDB cluster within a single-thread! Even better, we are able to execute this simulation in a deterministic way, enabling us to reproduce problems and add instrumentation ex post facto. This incredible capability enabled us to build FoundationDB exclusively in simulation for the first 18 months and ensure exceptional fault tolerance long before it sent its first real network packet. For a database with as strong a contract as the FoundationDB, testing is crucial, and over the years we have run the equivalent of a trillion CPU-hours of simulated stress testing.

3 comments

Testing a distributed system using a single machine may look like an unorthodox approach. From our experience, however, when building a test framework for a distributed system, everyone would be automatically led to think about building it using a single machine for many benefits, especially saving a lot time. So, I would find it very inefficient to develop a distributed system using only system tests utilizing a cluster of machines, without exploiting integration tests.

Nevertheless using just a single thread to simulate everything seems like a great approach.

>simulation of an entire FoundationDB cluster within a single-thread!

Reminds me of an InfoQ post about simulating robot swarms in a single thread: https://www.infoq.com/articles/java-robot-swarms/ (links to Java libraries for that in the comments)

Being able to run everything in a single thread allows to:

1) Do a lot of tests quickly (with virtual time flowing as fast as possible), or arbitrarily slowly if you prefer slow-motion in some contexts.

2) Have determinism. Great for debugging: can reproduce bugs at will, even with full logs on (one trick is to enable them just some time before the bug occurs, when the bug is far from start time).

3) More easily figure out whether a bug is in domain code or a threading issue.

4) Use single-threaded execution as a bench of domain code, and see how much multi-threading/distribution can make them faster or do make them slower.

One constraint is that it rules out some programming styles, since the code must never use waiting constructs, like futures (if the single thread starts to wait, it will wait forever since nothing happens outside of it).

This is an excellent example of having time being a first class input to the evolution of a system. I believe this is fairly common in CEP [1] systems. Similar techniques can be used to handle randomness. I think anytime one writes code that is tied to the wall clock, that a mistake has been made.

[1] https://en.wikipedia.org/wiki/Complex_event_processing

> One constraint is that it rules out some programming styles, since the code must never use waiting constructs

The constraint here is for testing/simulation to be able to supply their own implementation of waiting constructs, not that waiting constructs cannot be used, of course they can.

I meant rules out for the domain code that you want to be able to run in a single thread, which should be by far most of the code (unless you ensure that whatever your code wants to wait for, has then necessarily already happened, but that seems brittle to me).

Inside of the technical layers you use to run it in multiple threads, there are of course wait/notify mechanisms (or similar).

Maybe you thought about wait implementations that would not wait but that would "help", and go on with other computations while the condition is not yet met? If not then I would like you to expand on what you mean, ideally with a few lines of code as a sample to make it clear.

I mean wait implementation doesn't have to actually wait, it just has to register an event handler and store some context to continue with. In the simplest case if we assume there is nothing else to process the condition will be met right in the next iteration and will call back that event handler and continue from that point all without any waiting.

Ok, I was talking about actually waiting (like in "while(!condition)yield();") with more code to execute at the _same_ (*) virtual time after the wait, not taking care of having some code executed _later_, which is indeed a proper approach in our case, and what "waiting" could mean in some informal specification.

(*) When doing deterministic virtual time scheduling, computations are scheduled to take place at given times, and are processed exactly at the time they are supposed to be. The time can only change once everything that had to be computed at current time has been computed (if in "as fast as possible" mode, the scheduler then just jumps the clock to the next time something is scheduled to happen) (if you want to read more about that, see "time advance request" and "time advance grant" in the HLA norm).

There is a great talk about this testing, it goes all the way to deterministic seeds and other basics. The level of determinism is admirable. https://youtu.be/4fFDFbi3toc