5 ms·

What always fascinated me is they built the simulator for the database first(ish) and relied on it as a first class citizen while building the DB: https://www.

What always fascinated me is they built the simulator for the database first(ish) and relied on it as a first class citizen while building the DB: https://www.youtube.com/watch?v=4fFDFbi3toc https://www.youtube.com/watch?v=4fFDFbi3toc > 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. https://pierrezemb.fr/posts/notes-about-foundationdb/ https://pierrezemb.fr/posts/notes-about-foundationdb/

ajmurmann 3y ago
Working on a distributed key/value store myself, I couldn't agree more and think what FoundationDB did for testing from the start is absolutely the way to go. Testing distributed system is very tricky and tests can be incredibly time consuming and bring everything to a halt.
falsandtru 3y ago
I'm loving this point. The unfortunate thing is those tests are closed source (I saw a maintainer says so probably in an issue before). It seems testable but still seems to be closed source. So we cannot fork the project even if FDB becomes totally closed source again.
- aseipp 3y ago
  No, the simulation harness and tests are open source and you can run them. It would be impossible for anyone to contribute anyway without it, for example, Snowflake, which heavily depends on it. It's built into the server binary directly, so the same code is always used, and it's simply a different operational mode when compared to the real server. I used to have a project to do lots of simulation runs on my big 32 core server and then aggregate the logs into clickhouse for analysis. It wasn't that hard. However, they (at least at the time most of the developers were at Apple, many have now moved to Snowflake and the Apple team has grown a little I think) haven't released or integrated their nightly cluster and performance testing systems into open, nor have they integrated them with GitHub Actions or Nightly runs or anything. My understanding is that this is "just" a lot of compute cluster/platform orchestration code on top of the tests that exist in the repository. So, while Apple or Snowflake integrates changes across hundreds of concurrent fuzzing simulations on whatever platforms they have, if you write patches yourself, you're stuck with long simulation runs. Maybe that's changed; I haven't kept up since the 7.0 series. In practice if you write patches and they accept them, they will just do the testing in their runs for you, on a cluster far larger than what you could have. Failures reports will tell you how to reproduce them from the test files. As a contributor, testing the system on your own is mostly a matter of how much money or how many CPU cores you can personally stand to set on fire. Someone could probably integrate this functionality into a Kubernetes operator or something so that outside engineers could run large scale simulations reliably. But it is really expensive and CPU/compute intense, no matter how you go about it. [1] https://forums.foundationdb.org/t/how-to-use-foundationdb-unit-test/3077 https://forums.foundationdb.org/t/how-to-use-foundationdb-un... [2] https://github.com/apple/foundationdb/tree/main/tests https://github.com/apple/foundationdb/tree/main/tests
  - falsandtru 3y ago
    Those tests are not the implementations of the tests, just specifying the test case and the few options. But I found the implementations. I am not sure if this is all of the simulation tests, but it seems to cover the basic cases. https://github.com/apple/foundationdb/tree/main/fdbserver/workloads https://github.com/apple/foundationdb/tree/main/fdbserver/wo... > Someone could probably integrate this functionality into a Kubernetes operator or something so that outside engineers could run large scale simulations reliably. But it is really expensive and CPU/compute intense, no matter how you go about it. Maybe this. https://github.com/FoundationDB/fdb-joshua https://github.com/FoundationDB/fdb-joshua
pavlov 3y ago
For some types of distributed systems, you can do this kind of simulated testing in advance by building a TLA+ model. It’s not a full-blown simulator (because generally the application code doesn’t even exist yet when you’re building the TLA+ model). But it can let you collect data and validate assumptions about your design before writing a single line of code.
- rockwotj 3y ago
  My beef with TLA+ is that it's not the same code, so while you're testing the design yes, you aren't testing the implementation of the design, which is just as important (if not harder too) to get right.
  - aseipp 3y ago
    Yes, but there really aren't too many good solutions to that that aren't either extremely language or domain specific. And if you're careful you can get a lot of direct mileage out of it. For example, MongoDB (yes, that one!) used it in the development of their Atlas system and has a paper about using TLA+ to model the system, characterize behaviors, then generate compilable-code test cases from those minimal set of behaviors -- which are then directly linked against the core internals of the Atlas codebase as a client library. They then run those tests and re-generate them when the model changes. "Model based test case generation" is the strategy here. So you can characterize what happens in split brain scenarios, state machine transition failures (conflicting transactions), etc. In reality the design stage is a pretty critical phase so you need all the help you can get, so even if you don't like TLA+ you're way better off than not modeling at all. As an example of the language specific thing, though, there's a library for Haskell I like that's very cool, called Spectacle, which also implements the temporal logic of TLA+ along with a model checker, but as a Haskell DSL. An interesting benefit of this is that you can model check actual real Haskell code that runs e.g. in your services, but I haven't taken this very far. There are also alternative solutions like Stateright for Rust. But again, not everyone has the benefit of these...
    - bigfish24 3y ago
samsquire 3y ago
Thanks for sharing that and quoting an incredibly useful snippet. This is such an interesting topic! Some thoughts: * I wonder if the approach could be used to implement debuggable replayability, with accurate tracing and profiling. A bit like what verdagon is doing with Vale. * It could be used to integrate the event loop with tracing (rather than instrumentation with Jaegar) * I really like the idea that "every object" is an event loop, which reminds me of Microsoft Orleans with its actor model for its grains. * I am interested with actor and lightweight thread architectures. * I am interested in the scalabiliy of nodejs event loop architecture and Win32 desktop application programming. * I think this approach could be used to test and simulate microservices. * Approach could be used to test GUIs with React Redux reducer style.
AaronFriel 3y ago
When I was writing a Haskell client library for Hyperdex, another distributed kv store, I found it incredibly helpful to implement a simulator for correctness. This helped me identify which behavior was unspecified (arithmetic overflow: should error) or where my simulator deviated. https://github.com/AaronFriel/hyhac/blob/master/test/Test/HyperDex/Pool.hs#L449-L460 https://github.com/AaronFriel/hyhac/blob/master/test/Test/Hy... Alas, I think Hyperdex development paused a few years later. It's a shame that it stopped then.
riwsky 3y ago
“The Jepsen is coming… from INSIDE THE HOUSE!”
innerzeal 3y ago
They founded a company around the simulator called http://antithesis.ai/ http://antithesis.ai/

ajmurmann 3y ago

Working on a distributed key/value store myself, I couldn't agree more and think what FoundationDB did for testing from the start is absolutely the way to go. Testing distributed system is very tricky and tests can be incredibly time consuming and bring everything to a halt.

falsandtru 3y ago

I'm loving this point. The unfortunate thing is those tests are closed source (I saw a maintainer says so probably in an issue before). It seems testable but still seems to be closed source. So we cannot fork the project even if FDB becomes totally closed source again.

aseipp 3y ago
No, the simulation harness and tests are open source and you can run them. It would be impossible for anyone to contribute anyway without it, for example, Snowflake, which heavily depends on it. It's built into the server binary directly, so the same code is always used, and it's simply a different operational mode when compared to the real server. I used to have a project to do lots of simulation runs on my big 32 core server and then aggregate the logs into clickhouse for analysis. It wasn't that hard. However, they (at least at the time most of the developers were at Apple, many have now moved to Snowflake and the Apple team has grown a little I think) haven't released or integrated their nightly cluster and performance testing systems into open, nor have they integrated them with GitHub Actions or Nightly runs or anything. My understanding is that this is "just" a lot of compute cluster/platform orchestration code on top of the tests that exist in the repository. So, while Apple or Snowflake integrates changes across hundreds of concurrent fuzzing simulations on whatever platforms they have, if you write patches yourself, you're stuck with long simulation runs. Maybe that's changed; I haven't kept up since the 7.0 series. In practice if you write patches and they accept them, they will just do the testing in their runs for you, on a cluster far larger than what you could have. Failures reports will tell you how to reproduce them from the test files. As a contributor, testing the system on your own is mostly a matter of how much money or how many CPU cores you can personally stand to set on fire. Someone could probably integrate this functionality into a Kubernetes operator or something so that outside engineers could run large scale simulations reliably. But it is really expensive and CPU/compute intense, no matter how you go about it. [1] https://forums.foundationdb.org/t/how-to-use-foundationdb-unit-test/3077 https://forums.foundationdb.org/t/how-to-use-foundationdb-un... [2] https://github.com/apple/foundationdb/tree/main/tests https://github.com/apple/foundationdb/tree/main/tests
- falsandtru 3y ago
  Those tests are not the implementations of the tests, just specifying the test case and the few options. But I found the implementations. I am not sure if this is all of the simulation tests, but it seems to cover the basic cases. https://github.com/apple/foundationdb/tree/main/fdbserver/workloads https://github.com/apple/foundationdb/tree/main/fdbserver/wo... > Someone could probably integrate this functionality into a Kubernetes operator or something so that outside engineers could run large scale simulations reliably. But it is really expensive and CPU/compute intense, no matter how you go about it. Maybe this. https://github.com/FoundationDB/fdb-joshua https://github.com/FoundationDB/fdb-joshua

pavlov 3y ago

For some types of distributed systems, you can do this kind of simulated testing in advance by building a TLA+ model. It’s not a full-blown simulator (because generally the application code doesn’t even exist yet when you’re building the TLA+ model). But it can let you collect data and validate assumptions about your design before writing a single line of code.

rockwotj 3y ago
My beef with TLA+ is that it's not the same code, so while you're testing the design yes, you aren't testing the implementation of the design, which is just as important (if not harder too) to get right.
- aseipp 3y ago
  Yes, but there really aren't too many good solutions to that that aren't either extremely language or domain specific. And if you're careful you can get a lot of direct mileage out of it. For example, MongoDB (yes, that one!) used it in the development of their Atlas system and has a paper about using TLA+ to model the system, characterize behaviors, then generate compilable-code test cases from those minimal set of behaviors -- which are then directly linked against the core internals of the Atlas codebase as a client library. They then run those tests and re-generate them when the model changes. "Model based test case generation" is the strategy here. So you can characterize what happens in split brain scenarios, state machine transition failures (conflicting transactions), etc. In reality the design stage is a pretty critical phase so you need all the help you can get, so even if you don't like TLA+ you're way better off than not modeling at all. As an example of the language specific thing, though, there's a library for Haskell I like that's very cool, called Spectacle, which also implements the temporal logic of TLA+ along with a model checker, but as a Haskell DSL. An interesting benefit of this is that you can model check actual real Haskell code that runs e.g. in your services, but I haven't taken this very far. There are also alternative solutions like Stateright for Rust. But again, not everyone has the benefit of these...
  - bigfish24 3y ago

samsquire 3y ago

Thanks for sharing that and quoting an incredibly useful snippet. This is such an interesting topic! Some thoughts: * I wonder if the approach could be used to implement debuggable replayability, with accurate tracing and profiling. A bit like what verdagon is doing with Vale. * It could be used to integrate the event loop with tracing (rather than instrumentation with Jaegar) * I really like the idea that "every object" is an event loop, which reminds me of Microsoft Orleans with its actor model for its grains. * I am interested with actor and lightweight thread architectures. * I am interested in the scalabiliy of nodejs event loop architecture and Win32 desktop application programming. * I think this approach could be used to test and simulate microservices. * Approach could be used to test GUIs with React Redux reducer style.

AaronFriel 3y ago

When I was writing a Haskell client library for Hyperdex, another distributed kv store, I found it incredibly helpful to implement a simulator for correctness. This helped me identify which behavior was unspecified (arithmetic overflow: should error) or where my simulator deviated. https://github.com/AaronFriel/hyhac/blob/master/test/Test/HyperDex/Pool.hs#L449-L460 https://github.com/AaronFriel/hyhac/blob/master/test/Test/Hy... Alas, I think Hyperdex development paused a few years later. It's a shame that it stopped then.

riwsky 3y ago

“The Jepsen is coming… from INSIDE THE HOUSE!”

innerzeal 3y ago

They founded a company around the simulator called http://antithesis.ai/ http://antithesis.ai/