jstimps

jstimps OP

The FDB knobs are tuned with the 8GB per process assumption. Changing these knobs is generally reserved for advanced deployments. ref

Without key clears or inserts I don’t believe the btrees will need to rebalance in any significant manner. Unless I am missing something?

Yes, this is very much in line with my thinking, taking inspiration from Erlang’s atom table, but making it a permanent part of the metadata in the DB. However, there is likely a challenge with coordinating changes to Ecto Schemas across a distributed app. As you deploy a new app release, some clients will be on one Ecto.Schema and others on the new Ecto.Schema. It is during these transition periods that I believe something more must be done to prevent wires being crossed. For example, a naive approach would cause a node on the old Ecto.Schema to start getting nils for a field that has been remapped in the symbol table. This is probably all surmountable, but it’s a significant amount of work.

EctoFDB already does what you describe in each transaction. I’m not familiar with \xFF/metadataVersion; I will have to look into it, thanks for the tip!

1
Post #31
garrison

garrison

Do they actually statically allocate all that cache memory at startup? If so that’s a shame if it’s not configurable. There is nothing in FDB that would consume so much RAM for a small DB. Those knobs are probably pretty safe, though, I would think.

Tigerbeetle for example allocates all of their memory at startup, which is really cool. But it has to be configurable.

When you rewrite a key you are still writing the page to disk. There would be no splits or joins, but you are still wearing out your SSD with the writes. They can only take so many.

Database b+trees are not balanced like a binary tree, they are very wide and they just split the root instead. There is a lot of write amplification if you write a single key in a page because you have to rewrite the whole page. 100b k/v with 4k page size is 40x write amplification, for example. For a cow tree you then have to rewrite each parent page too, so if it’s 3 levels deep that’s 120x. Redwood uses a really weird versioned page table because they were trying to do MVCC at the storage level (but I get the feeling they gave up), so it’s not so simple. Also obviously batching saves a lot here.

Btrees do not like random inserts because they fragment the tree. If a node splits at >100% and joins at <50% then over time you would expect the average node to be 75% full, so there is 25% wasted space (“slack”). To reduce the slack you can rewrite the btree with sequential insertions. FDB data movement requests keys, in order, and writes them back into the “destination” btree, which conveniently compacts it. Users were abusing this property to keep their btrees in good shape by constantly excluding and re-adding nodes one at a time to compact the btrees. So they added that as a feature (“perpetual storage wiggle”).

Which brings me to an amusing point: since the storage wiggle rebuilds the btrees from scratch every so often anyway, Redwood does not merge nodes at all!

1
Post #32
garrison

garrison

The database schema (which comes from migrations) is stored statefully and transactionally in the database. FDB’s consistency guarantees will ensure the data is never corrupted (assuming my design has no mistakes!), so you don’t need to worry about that.

The Ecto schemas of course would, ideally, match up with the database state - but Ecto is specifically designed so that this is the user’s problem. Your guarantees here are the same guarantees that, say, Postgres, provides: there is a schema where “these fields” have “these names”. The user is responsible for ensuring their Ecto schemas are compatible with that. If not you throw an error! (or Ecto does).

There are situations where a user might have to break out those “safe Ecto migration” strategies to handle their own nodes’ inconsistencies. But you don’t have to worry about that - your job is just to ensure migrations execute quickly without rewriting the table!

BTW, my comment had grown long but there are a number of enhancements you can make to the schema:

You can store a type along with each “field” and raise on a mismatch like Postgres would.

You can store a “default” value with each field so that new columns can default to something other than nil. If the field is missing from a row use the default. Note that you have to be careful never to update the default value once the field is created or you would corrupt old rows.

You could even do foreign keys, which would be pretty cool.

0
Post #33
jstimps

jstimps OP

v0.5.0

Notable Enhancements

  • Index Metadata [doc] now makes use of FoundationDB’s \xff/metadataVersion key,
    which allows the client to cache metadata and maintain transactional isolation
    without having to wait on any keys. Thanks @garrison for pointing this out!
  • Versionstamp [doc]: Added the ability to insert objects with a monotonically increasing integer id, via FoundationDB’s versionstamp.
  • SchemaMetadata [doc]: This is a new built-in Indexer that allows your app to watch and sync a collection of objects in a tenant. (Demo: Sync Engine Part II - Collections)

Changelog

:heart:

3
Post #34
garrison

garrison

Very nice work!

Versionstamps for auto increment are something I have actually thought about a lot. I’m not so sure it’s a good idea most of the time, for a number of reasons. The Record Layer IIRC uses UUID keys (probably v4?) for records, though that is not always a good idea either.

For one, they are a bit wasteful: 96 bits because they need to encode the 64 bit version plus a transaction and operation index (2 bytes each). And then if you want to ship tenants around like CloudKit you need another few bytes for a generation index because FDB versions are not correlated across clusters (which is actually a design mistake in FDB IMO, it could be fixed). But most of the bits in all three parts of the versionstamp are wasted (nobody is doing 2^16 * 2^16 * 1,000,000 writes/second).

And then for all of those wasted bits you don’t get global uniqueness guarantees because the ids chosen will be highly correlated (they count from zero). With a 96 bit versionstamp plus, say, 32 bits for the tenant move counter you literally have a 128 bit UUID except without the UU. Obviously in most cases you don’t need globally unique ids across clusters, but if we’re going to burn the bits anyway it sure would be nice

But the bigger problem is that they harm transaction composition. You cannot read versionstamp keys from the RYW cache because it would violate strict serializability. * It is also annoying to work with primary keys which are only known after commit in Elixir because structs are immutable (I see you discovered this as well), so you have to make the API ugly, which I am not a big fan of.

I think most of the time you are better off using UUID keys (v4 or v7 depending on the use case) or a 64 bit autoincrement key via the old high-contention allocator trick (it always amused me that this blog post uses Elixir syntax for seemingly no reason).

There are a few cases, though, where versionstamp keys are useful. In particular, a high-contention queue where you want atomic appends which are strict-serializable. This was the use-case they were created for: CloudKit does a lot of syncing between sometimes-offline devices (naturally) and so they need a good way to grab “all changes since X version”. I know you’ve seen the talk so you’re aware of this :slight_smile:

* Incidentally I’m not sure this is actually true, but usually when that happens the FDB devs have simply thought of something I didn’t, so I put the burden of proof on myself for the time being.

1
Post #35
jstimps

jstimps OP

You’re right about the weaknesses of Versionstamps (really autoincrementing keys in general). I should probably make that more clear in the docs.

Another missing feature of FDB Versionstamps: you can’t set the versionstamp on both the key and value at the same time. This makes maintaining an index key while supporting GetMappedRange awkward, but still doable by constructing a more complex mapper tuple:

  defp mapper(tenant, idx_len) do
    offset_fun = fn offset ->
      [
        "{V[#{offset}]}",     # prefix
        "{V[#{offset + 1}]}", # source
        "{V[#{offset + 2}]}", # namespace

        # pk: get it from the index_key because the versionstamp lives there, not in the value
        "{K[#{offset + 5 + idx_len}]}",

        "{...}" # rest
      ]
    end

If you allow me to speculate a bit, I suspect this stems from the “set versionstamp” ops being atomic ops. It seems unnatural to allow keys related to atomic ops on the RYW tx to be readable from the cache (for example, an “add” operation on a key does not have a meaningful RYW cached value). In the case of set_versionstamp_key, I suppose it could be feasible and useful, but your transaction logic would still have to understand that portions of that cached key are not in their final form. And if your transaction needs to code around this defensively anyway, I figure you’re better off doing your own in-transaction cache.

Your point still stands about versionstamps making transaction composition harder - they sure do!

Guilty as charged, but the API I landed on is acceptable, IMO. I may yet propose a postprocess callback in Ecto to allow the adapter to participate in the struct creation, if time allows.

Confession: I’m finding myself having to deviate from the standard Ecto API more often as the implementation increases in scope. (all the async/await functions, transaction vs transact vs transactional). FDB is unique in a lot of ways, though, so I don’t presume that a lot of these ideas are generalizable to other DB clients - yet :grin:.

Agreed, this is the most / compelling use case for Versionstamps :smile: . I’ll update the docs to reflect this, too.

I’d like to explore this area a little bit myself. My undeveloped idea is to use the modules from riak_dt as Ecto.Type fields and implement the Ecto Adapter to perform merging upon an update. That is, to allow 2 FDB clusters to evolve separately and then have them merge at a later time.

1
Post #36
garrison

garrison

This is part of it but versionstamp is substantially weirder. With an atomic add you know the key but not the value. With a versionstamp key you know the value but not the key. Which means that you need to block any gets or scans within the range where the key could be (mercifully bounded to the read version plus 5s) because you don’t know where exactly the key is supposed to be in that range, even though you know the value!

If you think about the actual use-case here (primary key), you would want to be able to use it (and compose with it) as a foreign key. So function #1 creates a struct with a relation, and function #2 can look up the foreign key from the RYW cache without knowing that it actually only exists in the RYW cache. Even though we don’t know the real versionstamp key this entire pattern can be implemented on top of a placeholder key without violating correctness. I mean, I think it can anyway. This stuff is hard.

Weirdly, even a range scan should be correct. There can’t be any versionstamp keys in our snapshot above the read version anyway (obvious invariant), so there are no other keys in that range to read and therefore the only key in a range scan of [read_version, read_version + 5000000) should be our key! Of course if any other keys get inserted then we abort anyway so reading that range is a terrible idea but it’s correct, which is the important part.

So the only case where you would actually run into problems is if a previous transaction lied and inserted a versionstamp key into the range (keys are just bytes after all). Then we don’t know where our key lines up compared to that key, so a read of that range violates correctness.

But, why would you do that?! If we’re storing structured data we know this situation will never arise, so a strict serializability violation shouldn’t happen, ever. So it’s a weird case, I think, where the safety mechanism is only needed because FDB has to support unstructured keys for a use case where the data will only ever be structured in practice. The tyranny of key value stores, I guess.

But I still feel like I might be missing something, so I could just be totally wrong.

1
Post #37
garrison

garrison

For me the underlying problem here isn’t Ecto, it’s immutability. I see you’ve gone with a promise/await style API to batch updates but I’m not a big fan of that style. I want something which looks closer to how Ecto works now, like:

%User{} = user = transaction(fn ->
  user = Repo.insert! %User{name: "foo"}
  token = Repo.insert! %UserToken{user: user, token: generate_token()}
  {:ok, user}
end)

With Ecto we do this all the time, and since the User gets its id at insert time with e.g. Postgres we can just return it. But with FDB of course this is not so easy. We need to populate the versionstamp after commit, so then we need to run every struct we want to return through some function again, which is ugly and error-prone.

Actually I was going to continue making this point but I think I’ve just had an epiphany: you can use the transaction() barrier to deep-search the return value and populate any missing versionstamps.

I can’t believe I never thought of this before LOL, that’s actually a beautiful solution. Never mind, I guess!

Yeah, I’ve already accepted that my own work is going to necessitate throwing Ecto out with the bathwater. It’s a shame because Ecto is probably my favorite library of all time, but at the end of the day it’s evolved to be an SQL client more than anything else and I don’t think that is something that can or should be changed at this point.

0
Post #38
jstimps

jstimps OP

I have considered this approach, but I think it can be slow and error-prone. The caller may choose to store their output in a data structure that cannot be inspected (such as a NIF resource of some kind), or it may be so deeply nested that traversing again it is an unacceptable use of time post-commit. These are edge cases, but would be the source for confusion, and for that reason I’ve avoided it.

I wonder if your work can continue to use Ecto Changesets? The changeset integration with Phoenix is strong. I’m interested in hearing more about it!

1
Post #39
jstimps

jstimps OP

This is still possible with EctoFDB, just not with Versionstamps. Using :binary_id works the same as traditional Ecto.

The async is only there to match libfdb_c’s futures, allowing the caller to only wait on network when they deem necessary.

Repo.transaction(fn ->
  f1 = Repo.async_get_by!(User, name: "Alice")
  f2 = Repo.async_get_by!(User, name: "Bob")
  [alice, bob] = Repo.await([f1, f2])

  Repo.insert!(%Team{members: [alice.id, bob.id]})
end,
prefix: tenant)

Functionally equivalent, but now with 2 network waits:

Repo.transaction(fn ->
  alice = Repo.get_by!(User, name: "Alice")
  bob = Repo.get_by!(User, name: "Bob")

  Repo.insert!(%Team{members: [alice.id, bob.id]})
end,
prefix: tenant)
1
Post #40