Regarding vector Index, my interest is mostly a hope at this point. Also I don’t have the time to fully invest at the moment. 
I’ve captured my initial idea in a new discussion here. I would be interested in hearing your thoughts.
I’d like to continue collaborating on your other ideas too. It’s clear you have experience in this area and a bold vision. I enabled Discussions which may be a more convenient place to follow up on some of these conversation threads on an individual basis.
Hi! Your fdb project was very helpful in me getting the erlfdb binding tester back up and running in GitHub CI, so thank you!
One thing that’s unique about developing on top of FDB is that many flowers can bloom, so-to-speak. Love seeing others with interest in the tech. 
I don’t use gh but I will reply here if you don’t mind.
The only prior art I’m aware of for vector indexes on FDB is this project, which was posted on the FDB forums but as far as I can tell they never actually ported it to FDB before abandoning it. It’s not clear to me from the README what type of index they used, but the same org is a maintainer of a very popular SIMD vector search implementation (usearch) so it’s possible they were taking the approach I considered above.
SPANN is interesting, I haven’t read the paper.
The main reason I’m tempted by the quantize+brute-force approach is that it’s enticingly simple, and I am (naturally, as a programmer) very lazy 
The complexity of HNSW and co make me very uncomfortable, especially since it doesn’t really seem like they perform that well. Contrast with a BTree, for instance, which is much easier to understand and yet has excellent performance (for a different use-case, of course).
It could very well turn out that vector search is a problem best solved by brute-force in parallel (like most of OLAP). I don’t think anyone knows for sure yet.
@a3kov A quick update on your question.
erlfdb: The erlfdb 0.2.2 release is in a real production app, working well, with a significant workload. I will consider a 1.0 release, if that is meaningful to anyone.
ecto_foundationdb: EctoFDB is still experimental, but it is now driving a small and low-stakes production app at https://livesecret.link (GitHub)
Cheers!
The inability to rename a field without rewriting the whole DB is a bit worrying… I’m not sure how much of an issue it may become, but it’s exactly the type of things that may block wider adoption of ecto_fdb.
That’s a fair take. However, I believe it glosses over the difficulty in safely renaming a column in other dbs as well, as detailed in safe-ecto-migrations | Renaming a Column.
Certainly the ecto_fdb project has a long way to go – deleting a field is table stakes, for example, and it’s not there yet. Thanks for your interest!
From the linked article:
There is a shortcut: Don’t rename the database column, and instead rename the schema’s field name and configure it to point to the database column.
Ecto_fdb could do the same trick I believe ? But yeah, I totally forgot about this. In 99% of cases we care about the model (schema) field names, and not about the DB column names.
Keep in mind the context in which I brought this up: FDB is designed to operate as a large, distributed system with a potentially enormous amount of data. The “database” layer (here, ecto_fdb) is designed to be stateless.
In this context, you have to take special care to use indirection for schema changes without breaking the consistency guarantees of the database and without rewriting the entire table (because, again, the table could be 100TB).
This is not easy, but it’s not impossible or anything. I don’t think it’s substantially more difficult than, for example, building indexes online (which was already implemented).
This “trick” is essentially doing the indirection in the application layer. It’s inelegant because, ideally, the schema should be stored along with the data it represents. But it would work, I suppose.
I actually believe the FDB design decisions work quite well for small and moderately sized databases as well. For me, it’s more about the kind of workload and the operations story. I wouldn’t want people to come away thinking that they need 100TB of data in order to use it – LiveSecret is essentially a 0-Byte database running on a couple GB of memory (please don’t try to DOS it though 
). I’m pretending FDB is an embedded database by using ex_fdbmonitor , instead of SQLite, even though I am a big fan. Of course, please check FDB’s system requirements for a production app. Running with low system memory does go against the grain of a recommended FDB deployment. (8GB per fdbserver process recommended)
To date, the largest value add for me is never having to write DDL and never having to worry about migrations while I’m doing additive changes (new schemas, new fields, new indexes), which is 99% of development anyway IME.
We wouldn’t know until we tried it, to be honest. Some Ecto features come for free, and some require the adapter to meet specific contractual details. But if it doesn’t work, I imagine it would be possible to add support. Let me know if you find out!
Happy to report there is progress on the main branch, not yet in a release. Specifically, there is a new CLI module, a guide, and a test for deleting or renaming a field safely, in the spirit of Safe Ecto Migrations. Renaming a field in this way actually requires 2 full table rewrites, which you may find unfortunate, but at least now it’s possible to do it 
.
Other progress on the main branch includes refactoring the IndexInventory into a general purpose metadata store. This paves the way for richer metadata such as a schema field map (like an atom table) that could allow for table operations without rewrites, similar to what’s been described in this thread. That may come in future work – I’m still considering the implications.
100% agree. Even for a smaller database you get high availability/durability out of the box and very strong correctness and consistency guarantees (much better than Postgres, for example). Plus if you ever do need to scale, you know it won’t be a problem.
What I was getting at is that any solution for schema operations needs to be able to scale to 100TB+ scale in order to get full value out of FDB. Rewriting a table is fine for a (very) small DB, but not so much as you grow. Especially since FDB encourages a multitenant approach, and that complicates things further.
I have never actually operated FDB, but I struggle to think of anything in the architecture which would necessitate 8GB per process for a small DB. I would imagine this requirement is for operating at scale.
If the DB is small then everything is small: shard map/txnstatestore, byte sample, serverdbinfo, mutations in memory on the tlogs and in the storage ptree, etc will all be small.
Another thing to keep in mind is that for a large DB rewriting a table, even in the background, is actually physically expensive. FDB is a huge distributed btree, and btrees have a lot of write amplification. Rewriting the rows in order will reduce that amplification considerably (because FDB naturally batches disk updates due to the in-memory MVCC design) but even then rewriting every key is naturally going to wear out your SSDs, which is not free. On the cloud they will charge you iops instead, so same problem.
After some thought I think this design would work:
To create a field: add a new field key with a new (monotonic) integer id. It is easy to allocate ids transactionally because migrations are rare so there is no contention. You can store the next_id in the schema.
To rename a field: simply point the new name to the id previously used by the old name, and then delete the old name.
To delete a field: well, delete the field! The id will remain “allocated” because they are monotonic.
So, to run a migration, we perform the above operations and then update the “schema version” to whatever Ecto provides, similar to how it works with Postgres. There should be no problem submitting this as a single transaction to FDB, as it won’t be large.
Naturally, you can then store rows with integer keys instead of string keys, where the integers are the above ids. You could even encode them as varints for even more space savings since there are only as many ids as fields have existed (i.e. not many).
Finally, for correctness you would have to read the “schema version” in every transaction to ensure it matches what the client expects. This would create a bottleneck for a large DB, but you could use the \xFF/metadataVersion key for cache invalidation (increment it on every migration). That key was specifically designed to do exactly this.
You can cache the %{field => id} and vice-versa mappings in an ets table (or persistent_term, perhaps, would be better) along with the Ecto version and the metadataVersion.
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!
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!
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.
\xff/metadataVersion key,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)
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 
* 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.
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 
.
Agreed, this is the most / compelling use case for Versionstamps 
. 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.
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.
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.
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!
© Copyright Elixir Forum | Terms | Privacy & Cookies
