News for hackers. Stuff that matters.
Re:FoundationDB: A Distributed Key-Value Store by leetrout on Monday July 03, 2023 @11:04AM (#36573928)
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

> 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/

Re:FoundationDB: A Distributed Key-Value Store by ajmurmann on Monday July 03, 2023 @12:08PM (#36574965)
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.
Re:FoundationDB: A Distributed Key-Value Store by falsandtru on Monday July 03, 2023 @12:18PM (#36575120)
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.
Re:FoundationDB: A Distributed Key-Value Store by aseipp on Monday July 03, 2023 @01:41PM (#36576357)
No, the simulation harness and tests are open source and you can run them. 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. 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.

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 intensive no matter how you go about it.

[1] https://forums.foundationdb.org/t/how-to-use-foundationdb-un...

[2] https://github.com/apple/foundationdb/tree/main/tests

Re:FoundationDB: A Distributed Key-Value Store by falsandtru on Monday July 03, 2023 @02:24PM (#36576946)
Those tests are not the implementations of the tests, just specifying the test case. But I found the implementations. I am not sure if this is all of the simulation tests, but it seems to cover the major cases.

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

Re:FoundationDB: A Distributed Key-Value Store by aseipp on Monday July 03, 2023 @02:47PM (#36577261)
Yeah, that's basically an actually good implementation of the pile of crap that I threw together several years ago while writing a few patches. :)

And yes, I linked to the spec files because there actually isn't that much test code written in Flow I feel; the high-level specs in the .txt files can be mixed and matched so much to create a lot of variety from some small number of primitives, so that's really where all the good stuff is. Implementation vs interface, and all that.

Re:FoundationDB: A Distributed Key-Value Store by pavlov on Monday July 03, 2023 @12:51PM (#36575622)
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.

Re:FoundationDB: A Distributed Key-Value Store by rockwotj on Monday July 03, 2023 @01:03PM (#36575820)
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.
Re:FoundationDB: A Distributed Key-Value Store by aseipp on Monday July 03, 2023 @01:58PM (#36576570)
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...

Re:FoundationDB: A Distributed Key-Value Store by bigfish24 on Monday July 03, 2023 @03:28PM (#36577704)
Do you know the paper for Atlas?
Re:FoundationDB: A Distributed Key-Value Store by aseipp on Monday July 03, 2023 @05:53PM (#36579302)
Yes, I managed to find it: "eXtreme Modeling in Practice" https://arxiv.org/pdf/2006.00915.pdf

Unfortunately I got the product wrong; it was not Atlas, it was Realm Sync. All of the test-case generation stuff is in Section 5.

Re:FoundationDB: A Distributed Key-Value Store by pavlov on Monday July 03, 2023 @02:00PM (#36576589)
Yes, the model is more like an executable form of documentation. There’s no guarantee that code comments match what the code actually does; similarly there’s no guarantee that the TLA+ model matches what the system does.

Documentation is still generally useful, and so is a model. You have to be committed to keeping both up to date as the code evolves.

Re:FoundationDB: A Distributed Key-Value Store by gamegoblin on Monday July 03, 2023 @08:32PM (#36580658)
This is what we did for our KV store at S3: https://www.amazon.science/publications/using-lightweight-fo...

Using https://github.com/awslabs/shuttle which works on our real Rust code.

Re:FoundationDB: A Distributed Key-Value Store by samsquire on Monday July 03, 2023 @02:27PM (#36576996)
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.

Re:FoundationDB: A Distributed Key-Value Store by AaronFriel on Monday July 03, 2023 @03:21PM (#36577624)
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/Hy...

Alas, I think Hyperdex development paused a few years later. It's a shame that it stopped then.

Re:FoundationDB: A Distributed Key-Value Store by riwsky on Monday July 03, 2023 @04:45PM (#36578560)
“The Jepsen is coming… from INSIDE THE HOUSE!”
Re:FoundationDB: A Distributed Key-Value Store by innerzeal on Wednesday July 05, 2023 @08:08PM (#36609088)
They founded a company around the simulator called http://antithesis.ai/