Replication via FoundationDB | FlowG

Skip to main content<br>🎉<br>FlowG v0.61.0<br>has been released, and with it one of the two big projects we announced on the<br>road to 1.0: replication is now<br>generally available.

It is powered by a brand new storage backend, built on top of<br>FoundationDB.

A little bit of history​

Historically, FlowG stored everything in BadgerDB,<br>an embedded key/value store. It served us well, but it is a single-node<br>database, and our first attempt at replication was an experimental layer on top<br>of it, synchronizing storages via the "TCP Push/Pull" mechanism of the<br>SWIM Protocol.

The idea was to let every node accept writes and reconcile them in the<br>background, converging towards<br>eventual consistency. Node<br>discovery was handled by<br>Hashicorp's memberlist, which we<br>ran over HTTP instead of its default TCP/UDP transport, so it could sit behind a<br>reverse proxy and reuse the same TLS and authentication as the rest of FlowG .

For the data synchronization itself, we leaned on a happy accident of BadgerDB:<br>it versions every key/value pair and exposes an incremental backup that streams<br>every pair newer than a given version and hands back the new high-water mark.<br>Each of our three storages already behaved like a<br>CRDT anyway<br>(last-write-wins for auth and config, append-only for log), so we did not<br>even need the operation log we had originally designed. Once per second, riding<br>on the SWIM "TCP Push/Pull", each node advertised the last version it had seen<br>from every peer; the peer streamed back everything newer over HTTP (abusing<br>HTTP trailers<br>to send the new version after the body), and the receiver merged it straight<br>into its local storage.

As I said back then, this implementation was "buggy, costly in terms of<br>performance, and wrong on many levels".

Making it correct would have meant piling on ever more machinery (snapshots<br>to keep the sync affordable, real conflict resolution, a story for network<br>partitions and node failures) until we had, slowly but surely, reimplemented a<br>distributed database. Badly.

So we did the reasonable thing: instead of writing our own, we stood on the<br>shoulders of giants and plugged FlowG into<br>FoundationDB, a distributed, transactional<br>key/value store that gives us replication, fault-tolerance and strict<br>serializability for free.

To understand how we got there, we first need to talk about how FlowG models<br>its data.

The data model of FlowG​

At the highest level, FlowG manipulates a handful of entities: users, roles<br>and their tokens for authentication; transformers, pipelines and forwarders for<br>processing; and streams of log records for storage.

Here is how they relate to each other, grouped by the store they live in:

Those are the logical entities, the ones you manipulate through the API and<br>the UI. But under the hood, FlowG does not know about "users" or "streams".<br>It only knows about key/value pairs .

From entities to key/value pairs​

Every entity is decomposed into a set of key/value pairs, spread across three<br>independent, ordered stores: the auth, config and log namespaces. A single<br>logical entity is not one row, it lives in several keys that share a common<br>prefix. Its attributes become key suffixes, and its relationships become keys of<br>their own: the key user:alice:role:admin simply means "alice has the role<br>admin". When a key's mere presence already carries the information, it stores no<br>value at all (we write those ∅).

auth (users, roles, tokens)​

config (transformers, pipelines, forwarders)​

log (streams and their records)​

The ordering of the keys is not incidental, it is load-bearing. Everything under<br>the user:alice: prefix sits contiguously, so reading a user back is a single<br>prefix scan. The same property is what lets us store each log entry under a<br>timestamped key and scan a whole stream in chronological order, and keep an<br>inverted index of field values right beside the entries it points to.

Operations as ACID transactions​

Because a single entity spans several keys, any operation on it has to touch<br>several keys at once, and they must all take effect together or not at all. That<br>is exactly what a transaction gives us.

Saving the user alice above, for instance, is not a single write. It stores her<br>password, adds the roles she should have, and removes the ones she should no<br>longer have, all inside one read-write transaction.

If any of these writes fails, the whole transaction is rolled back as if it never<br>happened: alice never ends up with only half of her roles, and a concurrent<br>reader sees either her old state or her new one, never something in between.<br>Reads work the same way, running in read-only transactions over a consistent<br>snapshot.

This is the important takeaway: FlowG only ever needs two primitives from its<br>storage layer (a read-only transaction and a read-write transaction, both<br>providing get, set, delete, and ordered prefix iteration over key/value pairs).

Anything that can provide that, with ACID guarantees, can be a backend...