Additional indirection was always there for indexes, be it database managed or application managed.
If the database is running embedded in your application, then there is very little extra cost involved.
If one is using the database as a separate process, you incur additional latency for the network round-trip + the payload of the matched index items.
That is the cost you pay.
But in return you get natural parallel fanout, reduced locks/contention bottleneck, etc.
You also get to have your indexes in dedicated shards on dedicated nvme hardware. With batching, you can reduce the contention on indexes even further.
You also get a simpler mental model, simpler queries, more deterministic and predictable latency. The list goes on.
Application-managed indexes are ideal for extreme scaling.
What industries is It common to have data small enough that running an embedded databases makes sense but also the data is so large that the indices that database provides aren't sufficient and you need to roll your own and they will perform better than the ones built with coordination with the storage engine and everything else? This seems a very unusual set of circumstances so I'm very curious on the use case.
There are many more and most may not be documented online.
Our usecase is offline first mobile ERP (roll-out hopefully soon) with online-sync capabilities doing invoice/coupon processing, etc. in a network of regional shops - with a focus on minimizing latency and aggressive reduction of costs at scale.
Once we measured the reduction in latency due to parallel fanout (over index shards - not just data shards) for range scan, there is no going back ever again.
When you need the same database to be running on mobiles and servers alike, you need embedded database for mobile and standalone executable for server.
> they will perform better than the ones built with coordination with the storage engine and everything else?
No amount of coordination with the storage engine can override the physics of lock contention in distributed systems.
> This seems a very unusual set of circumstances so I'm very curious on the use case.
That’s interesting. My spare time tinkering is around offline first embedded querying/storage with more of a focus on operational data (in particular spatial/spatiotemporal). Most of the big offline use cases I’ve seen are aerospace/drones or logistics or robotics where they want to juggle a lot of things at once concurrently (normally by stringing together a few different things currently). Most of the time I mention it people just terminate the conversation at SQLite or DuckDB when they don’t really fit for the hot path of any of most operational use cases or jump straight to the big cloud DBMS du jour.
> When you need the same database to be running on mobiles and servers alike, you need embedded database for mobile and standalone executable for server.
Most of the people I’ve run into just want some sort of replication system that’s a bit richer than MQTT et al.
> No amount of coordination with the storage engine can override the physics of lock contention in distributed systems.
Carrying on from the previous point. Distributed querying may still just be a workaround rather than something anyone actualy wants to do as a first option.
> Distributed querying may still just be a workaround rather than something anyone actualy wants to do as a first option.
That is not the case. Even on a single machine with multiple shards (think hundreds or even thousands of kv engine say LMDB envs), a distributed query parallelizes efficiently. Additionally it can also saturate the SSD/NVMe with multiple write transactions concurrently.
It definitely is the first option and not a workaround. Even replication benefits from this write saturation and reduced latency and parallelism. Naturally, multiple writes involving the same logical unit of work can go through a durable execution framework (think ordered-log/kafka) as one insert and the client dismissed only for the consumer later attempting multiple idempotent writes (logical work with retry on failure) - achieving maximum SSD saturation. The client is later informed of the status.
> Most of the big offline use cases I’ve seen are aerospace/drones or logistics or robotics ...
Our previous ERP (built almost over a decade) for a large enterprise client, required disbursing customers as the absolute paramount priority regardless of internet availability - which is where offline first became the only choice. They wanted data to seamlessly move across thousands of offline systems - which is where we wrestled with replication/conflict resolution, etc. Our new Slyp and SlypBusiness is a reincarnation/re-imagining of this old ERP with added goodies but as mobile first applications.
There is only up to a point where we tolerate other databases, and beyond which the conventional wisdom starts to be a net negative and we realized we are better off building one for ourselves.
You also now have to manage your own ACID guarantees, and what amounts to cache invalidation. Not sure how this is “a simpler mental model.”
Same with locks / contention: non-locking reads don’t cause contention, or at least, none that wouldn’t also occur with a separate table acting as the index.
Do you have any examples of this being used at scale, preferably with an accompanying blog post or other form of documentation?
> You also now have to manage your own ACID guarantees and what amounts to cache invalidation ...
Hint: Extreme scale. You anyway have no full ACID guarantees at scale and one has to implement their own relevant guarantees and cache invalidation at extreme scale. You either have to implement your guarantees or pay the cost of bottleneck and latency.
They are achieved via idempotency, durable execution, etc.
There is sufficient reason for me to think that either you may not have read my comments attentively enough or you may lack the experience of building reliable systems at scale.
A developer need not be hand-held with this reasoning on the topic of scaling. I have given ample reasoning to reconstruct.
What is extreme scale here? Like you've been able to fit over 1 PB of NVMe in 1U for years now (and before the AI inflation, prices were low enough that you could do it for like $100k IIRC). Are we talking 10s+ of PB? Who actually needs this scale?
At mere 100s of TB of data, I think you'll find that a normal database is far more likely to scale better. Most developers are... not as good as database developers at maintaining a database, and will not do a good job of it when they write their own inside of their application. They're often not even that good at using a database.
e.g.
> You also get to have your indexes in dedicated shards on dedicated nvme hardware. With batching, you can reduce the contention on indexes even further
You can just do this with postgres. It works great. Most people don't even get that right. And they're going to suddenly get it right and implement efficient indexes?
Not just data, but concurrent operations per second for writes and reads involving seperate transactions. Eg: Scaling concurrent write transactions on different shards with minimal write lock contention.
You seem to have missed the final sentence beginning with "Note:" in my original comment. Nobody said you can't do this with postgres.
> Most people don't even get that right. And they're going to suddenly get it right and implement efficient indexes?
What most people get right is not my concern. If you find building a thin wrapper layer for your application as hard, clearly this may not be applicable to you.
Okay, again, what kind of scale are we talking about here? 100ks of writes/second? Millions? For data that can't do reads from a replica (presumably not since you're saying use eventual consistency)? Always absent from these kinds of blogs are concrete numbers for what kind of volume they're discussing, making them completely useless drivel. Also that blog is saying they were running into trouble in early 2014 and started this project; okay, the first NVMe drive was mid 2013. Did they do that first? They totally could've been using racks of 10k RPM disks around that time with maybe SSDs for the indexes. You'd be way better off going all NVMe today as your first step to "scaling" (in fact you are insane if you are using anything else for an OLTP database), and just that is likely to immediately solve whatever problem you have already.
If postgres can already do partitioning, batching, different tablespaces on different disks, etc. except do it correctly with ACID, then what exactly is the benefit of manually implementing what it already does well?
Also how does going "schemaless" help with scaling at all? That's just asking for data integrity issues for no benefit. Peak mid-2010s money-furnace resume-driven "engineering."
> Okay, again, what kind of scale are we talking about here? 100ks of writes/second
You seem to be confusing writes/second with concurrent write transactions/second. Nvme won't rescue you if Postgres locks up only allowing each write txn to proceed sequentially when what you need is SSD write saturation on separate write transactions on multiple shards in a single machine.
> You'd be way better off going all NVMe today as your first step to "scaling" (in fact you are insane if you are using anything else for an OLTP database), and just that is likely to immediately solve whatever problem you have already.
This is hilarious. So we should all start building based on your prescription.
> what exactly is the benefit of manually implementing what it already does well?
Really? Is that a serious argument. Postgres is not a magic database that does everything that everybody wants very well.
In systems engineering, the trade offs are obvious. But if it is not clear at this point, I don't think I can offer much help.
I will offer one last advice.
Just write a snippet of code inserting 100M small keys and values into, say 1k chunks/shards of separate kv engine (LMDB, whatever). Do normal hashing for shard selection. Now store secondary indexes likewise. Now do parallel fanout for secondary indexes for selecting some 100k data. Collect the index data and do another parallel fanout and fetch the final data.
Now go see the latency results (excluding lmdb env setup time). Additionally observe the latency for writes :-)
Rich index metadata is just icing on the cake. Cheers.
The point of batching is that high requests/business "transactions" don't necessitate high concurrent database transactions. The thing that matters here is actual workload. How that turns into transactions is something you can tweak. And once you have a decent workload, you can build batches with dozens of items in a couple milliseconds, so you can still keep single digit millisecond latency with batching.
Yes, if you're architecting around slow disks instead of just using fast ones (which cost a fraction of the development cost of what you're saying), and if you do things like give up ACID in service to that, you're crazy and incompetent.
It's not magic, but for 99.999% of people, magic is not required. So again, like I asked twice, what is "extreme scale"? Weirdly, no one who brags about "scale" is ever willing to say what that means, and everyone saying they've never encountered this "scale" is willing to put concrete numbers behind it like 100s of TB at ~1M QPS or whatever.
At 100M rows in a table pg can do just fine with single digit ms latency with 5 digit request rates. Is that your "scale"?
I have operated a BDR Postgres cluster spread across five global regions with hundreds of TB of data, with multiple reader nodes attached to each primary, each on instances with node-local NVMe drives; the entire cluster saw over 1 million QPS. I will grant you that there are much larger examples of scale, but they typically exist on DBs designed for that, like Spanner, Vitess, etc.
I am not asking for hand-holding, I’m asking for one single publicly-available example of this being done, because I cannot fathom it being necessary or beneficial, and you have not provided concrete proof.
Usually first principles architectures and systems engineering doesn't require you to be validated by big players. You can always spin up and do your own measurements.
Yet since you asked, assuming good faith, here is what you are looking for.
< The indexes are eventually consistent; whenever we write a cell we also update the index entries, but it does not happen in the same transaction. The cells and the index entries typically do not belong to the same shard. So if we were to offer consistent indexes, we would need to introduce 2PC in the writes, which would incur significant overhead. With eventually consistent indexes we avoid the overhead, but Schemaless users may see stale data in the indexes. Most of the time the lag is well below 20ms between cell changes and the corresponding index changes >
Disclaimer: I have never worked at Uber. This is all armchair speculation, and I could of course be wrong.
IMO, if you read the later post on Docstore [0], you can see that they spent an enormous amount of time building back everything that they gave up with Schemaless - the enforcement of a schema (the irony...), transactions, serializability, etc.
They needed to create secondary indices as tables because they were storing everything in JSON blobs, which is difficult to directly index now, let alone in the 2010s. You can of course argue that they needed to use JSON blobs because they kept needing schema changes, and online DDL back then was difficult. I would counter that if you keep needing schema changes, you haven't done a good job modeling.
Everywhere I have worked that has DBs they claim are too large, I have been able to prove (typically by cloning one and remodeling it) that the reason they're suffering from performance issues is because they've made a series of decisions which were fighting against their RDBMS: UUIDv4 PKs, strings for low-cardinality data, excessive secondary indices, poor query plans from the ORM, massive JSON blobs that's duplicating already-present data, etc. At my last job, I showed a 30% speedup purely from changing to a PK that made sense for the table's usage.
> Everywhere I have worked that has DBs they claim are too large, I have been able to prove (typically by cloning one and remodeling it) that the reason they're suffering from performance issues is because they've made a series of decisions which were fighting against their RDBMS
Some are just physics. Say if you want SSD write saturation and multiple parallell write transactions, the traditional RDBMS model itself may not suffice. Its not just data size but concurrent write transactions, lock contention, etc. Additionally, think resource constrained devices like mobile phones. Or an aggressive cost reduction mentality where each cpu cycle shouldn't be unnecessarily wasted without feeling guilty. If you come from a systems engineering background like that, you wouldn't be much impressed with many traditional databases at all. I am generally not much interested in SQL databases anyway.
> They needed to create secondary indices as tables because they were storing everything in JSON blobs, which is difficult to directly index
Our database Dip stores raw binary as well as json as first class citizens. Can't speak for Docstore, but as far as I see, it is just an evolved form of its earlier self with different tradeoff according to their workload. Note the lack of mention of the removal of secondary indexes as separate data.
> I would counter that if you keep needing schema changes, you haven't done a good job modeling.
Disagree. Schema stabilizes - yes. But doesn't mean they don't go through cycles of change occasionally.
Postgres can absolutely saturate an NVMe drive on its own.
> Additionally, think resource constrained devices like mobile phones.
SQLite will saturate the phone’s I/O before you saturate SQLite.
> Or an aggressive cost reduction mentality where each cpu cycle shouldn't be unnecessarily wasted without feeling guilty.
> Our database Dip stores raw binary as well as json as first class citizens.
These two statements are in conflict. If you want to minimize CPU cycles, parsing JSON is a terrible idea, and you should be pushing everything into bitfields, operating on it with bitwise manipulations.
> If you come from a systems engineering background like that, you wouldn't be much impressed with many traditional databases at all. I am generally not much interested in SQL databases anyway.
I would love to see a Jepsen analysis of your DB. Then a benchmark of it vs. Postgres, or MySQL, or SQLite.
I love how you first confused application managed indexes with B+trees in code. Then you moved to how you could not see how "this could be faster", asserting there is an additional indirection layer.
When pointed out that the indirection also exists in database managed indexes, you wanted examples of usage at scale with a blog post. You also mentioned you have operated 1M QPS, yet you couldn't fathom while being oblivious to lock contention. You were persistent in demanding one public link.
When the Uber blog link was provided with exact scenario in the excerpt, you pivoted to how their new version has schema enforcement. You claimed you were able to prove all inefficiencies you encountered were due to bad data modeling or bad decisions which went against RDBMS.
When pointed out that the newer blog post doesn't mention removing the secondary indexes which was the whole issue, you digressed to the grand finale of absurdly claiming Sqlite will saturate phone's I/O before one saturates Sqlite, which is so false that it is not even funny. And finally demanding our Dip's benchmarks (which will come in due time, if? we ever release it to the public).
All of this when more than enough hand-holding was made to help you understand. Even when the underlying physics was easy to understand. Enough pivoting.
Let our conversation stand and be of help to anyone curious enough to learn the tradeoffs discussed. Best wishes.
I too would like to know concretely what sort of industry or scenario you are involved in, because in general “it’s simpler to roll your own than use mature, industry standard tooling” is bad advice. “Just build your own index with another table” is either hyper-specific to a niche scenario or flat out a terrible idea.
As another commenter pointed out, this means if nothing else you pay an extra round trip to the DB. Allowing the DB to own the index moves that computation to the data and eliminate a round trip network cost. In general fetching some data from the DB to tell you what other data to fetch from the same DB is a poor design. SQL exists to solve this exact problem.
There are absolutely scenarios where scale is so large that you need a partition lookup service. But this is different from not using indices.
If the database is running embedded in your application, then there is very little extra cost involved.
If one is using the database as a separate process, you incur additional latency for the network round-trip + the payload of the matched index items.
That is the cost you pay.
But in return you get natural parallel fanout, reduced locks/contention bottleneck, etc.
You also get to have your indexes in dedicated shards on dedicated nvme hardware. With batching, you can reduce the contention on indexes even further.
You also get a simpler mental model, simpler queries, more deterministic and predictable latency. The list goes on.
Application-managed indexes are ideal for extreme scaling.