FoundationDB

Talk: FoundationDB - NoSQL and ACID

Link

NoSQL's motivation:

• Ease of scaling & operation
• Fault tolerance
• ...

but no ACID transactions!

Why ACID?

• Bugs don't appear under concurrency!
• Reason locally rather than globally. Think about the invariants, and check if xact maintains them.

Remove/decouple data models:

• We have a db with ACID
• ... which provides polyglot data models & APIs
  • Key-Value,
  • Graph
  • column-oriented
  • relational
  • ...
• Without requiring separate physical dbs
• Pull the data-structures out of the engine

Werner Vogles on data inconsistency:

Data inconsistency in large-scale reliable distributed systems has to be tolerated ... [for performance and to handle faults]

CAP_2008 conclusions?

• Scaling requires distributed design
• Distributed requires high availibility
• Availability requires no C

CAP availability != High availability

Werner Vogles 2013

Achieving strict consistency can come at a cost in update or read latency, and may result in lower throughput...

Plan

• Maintain both scalability and fault tolerance
• CP system with global ACID transactions
• Enable abstractions and many data models
• Deliver high per-node performance

Decomposition into Stages

• Accept client transactions
• Apply concurrency control
• Write to transaction logs
• Update persistent data representation

FoundationDB has done a lot of engineering work to make each of the stages scalable & fault tolerant. With high performance.

Talk: Testing Distributed Systems with Deterministic Simulation

• Youtube Link
• Example Test

FDB:

• Distributed kv store
• Strong guarantees:
  • Serializable transactions across whole keyspace
  • Causal reads (never re-order a read-transaction)
• Mix of OCC & snapshot isolation

Snowflake uses FDB for metadata storage

Edsger W. Dijkstra

Program testing can be used to show the presence of bugs, but never to show their absence!

Difficulties in testing Distributed Systems:

• Slow Network vs. Dead Machine
• Message Reordering
• Randomness: Reproduction is very difficult, changing timing changes behaviour

Deterministic Simulation

• Control randomness
  1. Single-threaded concurrency
  2. Simulated implementation of all external communication
  3. Determinism

With its own programming language FLOW

• Extension to C++
  • Implementes stackless coroutines
  • Adds a few keywords (ACTOR, wait, waitNext, ...)
  • Similar to async/await in C#, Python, ...
• ActorCompiler compiles flow files to C++ files

Use interfaces for system calls so we can simulate them:

• INetwork -> Net2 vs SimNetwork
• IConnection -> FlowConnection vs SimConnection
• IAsyncFile -> AsyncFileKAIO vs SimFile

For randomness, use a deterministic random number generator

Difficulties

• ...
• CPU cycles
• Free space on disk
• Memory footprint of program
• Disk latencies
• System status
• The value of uninitialized memory
• ...

Output random seed at the end of test, so if someone introduces non-determinism, we catch it.

Dave Scherer on FoundationDB

I wanted a house, but I got a pile of drywall and 2x4 framing studs.

"C" in ACID:

• Your program brings the database from one valid state to another valid state.

The Paper

FoundationDB: A Distributed Key Value Store

• Initially, all NoSQL databases gave up consistency. Now, Cassandra, MongoDB, Couchbase support some form of ACID
• Most databases bundle storage engine, data model, and query language. FDB takes a modular approach: A highly scalable, minimal storage engine, with minimal chosen set of features.
• No structured semantics, no query language, no data model or schema management, no secondary indexes. Uses layers to provide extra abstractions:
  • Record Layer: relational
  • JanusGraph
  • CouchDB is being rebuilt on top of FDB

Record Layer Paper

FoundationDB Record Layer: A Multi-Tenant Structured Datastore