14 ms·
HC-tree is an experimental high-concurrency database back end for SQLite
- conaclos 4y agoSQLite is a great database engine. I often wonder if it could even be better without extreme backward compatibility. It could be nice to have Foreign Keys enabled by default, and make all tables strict by default. A new binary format that reduces the size of database by leveraging table strictness and type info could also be great.
- ngrilly 4y agoAgreed, but priorities: I think that new high concurrency backend is a more important improvement.
- ngrilly 4y agoWondering what the HC in HC-tree is for?
- otoolep 4y agorqlite[1] author here. It's very interesting see this. Not sure whether it can bring more functionality to rqlite, but it's definitely cool to see the SQLite database evolve with more client-server applications in mind. I will say that one misconception people often have about rqlite is that it's a drop-in replacement for SQLite. You see that a bit even in the comments section here. That was never its goal. Its goal is a lightweight and super-simple to use distributed relational database. Using SQLite as the database engine was the perfect way to meet that requirement. [1] https://www.rqlite.io https://www.rqlite.io
- otoolep 4y agoI will say the promise of "improved concurrency" is very interesting to me. If nothing else, I would definitely pull that into rqlite (probably as an option). That said, working with Raft log has always been the real bottleneck, not SQLite.
- yread 4y agoit's still pretty amazing that their "stock" (actually a tuned branch) can do 75k updates/s. That's enough for a lot of people
- TOP-HACKER 4y ago[flagged]
- simonw 4y agoConcurrent writes and replication! See also this thread on the SQLite forum: https://sqlite.org/forum/forumpost/d9b3605d7ff40cf4 https://sqlite.org/forum/forumpost/d9b3605d7ff40cf4
- metadat 4y agoThe linked performance graphs look remarkably promising, indicating hctree with 25% smaller pages scales to 1 million transactions per second: https://sqlite.org/hctree/doc/hctree/doc/hctree/threadtest.wiki https://sqlite.org/hctree/doc/hctree/doc/hctree/threadtest.w...
- freeqaz 4y agoNit: 1kb pages vs 4kb pages, so 75% smaller (25% of the size).
- michaelcampbell 4y agoThank you. One of my (granted, OCD driven) peeves is the recent ubiquity of framing that sort of comparison as "3 times smaller!". Ohmygod, no.
- metadat 4y agoOops, yes thank you for the correction!
- jimnotgym 4y agoIt makes me wonder why I would use anything else?
- stefanos82 4y agoExactly what I was thinking!
- metadat 4y agoPerhaps because as of today: > The prototype is still missing features and contains many bugs. But it works well enough to test.
- Jarred 4y agoAre there benchmarks comparing it against postgres/mysql/mariadb?
- stefanos82 4y agoI hope this gets stable enough so I can test it with an e-commerce demo just for fun!
- pbreit 4y agoDo we have any idea what the timing might be?
- hinkley 4y agoWhat does it mean for SQLite to use something as a backend? How much of it is still SQLite at that point?
- andrewf 4y agoMy guess would be the b-tree layer down based on "the database backend module that it uses to store b-tree structures in its database file" and the architecture diagram at https://www.sqlite.org/arch.html https://www.sqlite.org/arch.html
- simonw 4y agoThis feels to me a little bit similar to MyISAM v.s. InnoDB in MySQL - two different "backends" that are low level details about how the data is actually stored and accessed.
- Falell 4y agoBloomberg's comdb2 does something similar, using the SQL grammar and query planner but swapping out the storage layer. To quote from their paper: "In SQLite a query plan is compiled into a bytecode program that is executed by a virtual machine, named Virtual DataBase En-gine (VDBE)... In the original SQLite implementation the VDBE operates on the real B-trees of the database... In contrast the Comdb2 VDBE operates on the cdb2 abstraction of a table during the OCC phase of transaction execution..." http://www.vldb.org/pvldb/vol9/p1377-scotti.pdf http://www.vldb.org/pvldb/vol9/p1377-scotti.pdf
- hot_gril 4y ago> How much of it is still SQLite at that point? I'm guessing just the interface. If there are any well-understood quirks of the regular implementation, maybe they'd want to replicate them too, idk.
- t3estabc 4y ago[dead]
- samsquire 4y agoThis is very interesting. Thank you for submitting this and thank you for working on this. I am highly interested in parallelism and high concurrency. I implemented multiversion concurrency control in Java. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... I am curious how to handle replication with high concurrency. I'm not sure how you detect dangerous reads+writes to the same key (tuples/fields) across different replica machines. In other words, multiple master. I am aware Google uses truetime and some form of timestamp ordering and detection of interfering timestamps. But I'm not sure how to replicate that. I began working on an algorithm to synchronize database records, do a sort, then a hash for each row where hash(row) = hash(previous_row.hash + row.data) Then do a binary search on hashes matching/not matching. This is a synchronization algorithm I'm designing that requires minimal data transfer but multiple round trips. The binary search would check the end of the data set for hash(replica_a.row[last]) == hash(replica_b.row[last]) then split the hash list in half and check the middle item, this shall tell you which row and which columns are different.
- irq-1 4y agoCheck out: Living without atomic clocks: Where CockroachDB and Spanner diverge https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ https://www.cockroachlabs.com/blog/living-without-atomic-clo...
- simonw 4y agoMy assumption here is that the replication model described is one leader, multiple replicas - so all writes are applied to the leader and the followers are only used for reads. This is a pattern commonly used with other databases such as PostgreSQL and MySQL which avoids a huge amount of complexity involved in multi-leader setups.
- hot_gril 4y agoThere's also the hot standby leader configuration that the higher Heroku Postgres tiers do. The standby leader receives writes asynchronously, so during failover you can actually suffer a little permanent data loss. Really should have a bigger warning label. I only ever do single leader, multi follower like you describe.
- hot_gril 4y agoThis sounds a lot like Postgres or MySQL. Is the point of this to have compatibility with the huge number of existing SQLite applications?
- simonw 4y agoThe SQLite team are good at listening to the people who use the software. People who use SQLite want to be able to scale it to handle higher concurrent write loads, including from multiple processes.
- hot_gril 4y agoYeah, that's what I was thinking. If you're already using SQlite, here's a faster version of it.
- pbreit 4y agoSQLite is MUCH easier to deploy.
- hot_gril 4y agoBut HC-tree sounds like it's a full-on server like Postgres, and unlike regular SQLite. Maybe I'm mistaken. Edit: I was wrong, this makes more sense now. This isn't comparable to Postgres.
- deleted 4y ago[deleted]
- BulgarianIdiot 4y agoApple powers iCloud Core Data with SQLite. This way it uses the same DB engine locally on your Mac and iPhone, and the server backend in their data centers. I don't know if they've swapped the backend, or just use it as-is. SQLite can scale vastly if you use it for file IO and do sharding/replication on top of it as a separate concern. I've done ad-hoc (extremely crude) versions of that in some apps.
- hot_gril 4y agoIsn't each cloud CoreData store just for a single user, so high concurrency isn't needed?
- BulgarianIdiot 4y agoYes, we have natural sharding by user. However Core Data also can create shares which multiple users can access. I don't think this typically causes high concurrency, it's more like a Dropbox file share or a Google docs file share for a few users at a time. This definitely helped them make the choice to run SQLite on the server. But I still think it's super cool. We're talking 1.8 billion devices with data stored as SQLite files in the cloud.
- T-Winsnes 4y agoI would assume single account but multiple devices, so you could have multiple connections syncing at once.
- hot_gril 4y agoDoing that serially wouldn't be particularly slow. Most likely 4 devices at most.
- deleted 4y ago[deleted]
- senderista 4y agoUnbounded spinning is absolutely disastrous when cores are oversubscribed. If their spin locks are really unbounded, this does not belong in production.
- MobiusHorizons 4y agoAt the bottom of the linked article: > In all cases above, "spin-lock" actually means invoke the SQLite xBusy callback if one is registered, or to literally spin-lock otherwise. Seems the wait behavior is user configurable.
- eyegor 4y agoThat seems to only be true for the BEGIN EXCLUSIVE statement, which sounds like it's the entire point. Sqlite is generally a bit more bring your own batteries by design, so if you care you would add timeouts at the writer. Unless I'm missing something.
- didip 4y agoOnce this becomes the default, next is networking code.
- randomdata 4y agoThere was a time where desktop client software connecting to the RDBMS server directly was all the rage, necessitating that the RDBMSes of the era have networking capabilities to listen for those clients. But is there any point in a modern database providing that when we've all but completely moved the client->server networking into the application layer? As cyclical as tech can be, I find it difficult to think that we'll go back to that style of architecture. There are just so many benefits to having an application server sit in between the client and the database. Going back to green screen terminals hanging off a central computer seems more likely, and that model doesn't need its database networked either.
- filleokus 4y agoWhile that's true, I also think that the current rage is stateless applications, outsourcing state to centralised database/cache/object storage layers over a network connection. That allows you to easily spin up/down e.g containers, migrate the application between nodes etc without having to maintain a high performance network file system. Using sqlite in such an environment requires you to either solve the persistence layer in general (≈ rook/ceph) or specialised for sqlite (≈ litestream/litefs/rqlite depending on your need). I think one probably could argue that rqlite is essentially a network protocol for sqlite.
- dagss 4y agoThis really depends on what you mean with "application". It is very popular to have the "backend" stateless, yes, but it is also popular that each service has their own dedicated database, and to consider the service/application to be the combination of the stateless backend and the dedicated stateful database. The application is stateful even if the backend is stateless.
- 4y ago
- LAC-Tech 4y agoI always thought it would be awesome if SQLite got something like this. The decision to use SQLite for small web apps would become a lot more compelling if there was no "I have to migrate to postgres when I scale" anxiety.
- throwaway892238 4y agoCan someone explain why you would want a database larger than 16 TiB? Imagine there's database corruption, or you need to change the schema or something... why would you want to deal with that on an insane scale like hundreds of TiB? If you split your data up into smaller databases or shard, there's less chance of a problem affecting all of your data, and it being so gigantic that it takes forever to fix it.
- oakwhiz 4y agoSometimes I don't mind waiting for the query to finish. Makes for a good coffee break.
- EGreg 4y agoJohn Titor told me that this isn't an insane scale at all. You know, on the IBM 5100 computer they could only run like 1000 KB.
- ddlutz 4y agoI guess it really depends on your use case? Something like GMail it probably makes sense to have a database more than 16 TiB.
- wyager 4y ago16TiB is not a problem. I have admin'd postgres databases larger than that. If you use good hardware (ECC RAM) and an error-correcting filesystem (ZFS) you are generally good to go. Typically for postgres, DB corruption issues are isolated to single tables/indices, not the entire database. Sqlite's architecture might be a bit less "resilient" in this sense (I'm not sure, just guessing), but it also might have a lower chance of introducing corruption in the first place.
- jandrewrogers 4y agoYou want high-density storage to minimize the number of servers required when data models get large. If you limited yourself to 16 TiB, then it would not be uncommon to require thousands of servers for large data models. If your database supports high-density storage then you could fit this in a single rack. For somewhat smaller data models you could fit this on a single server. It doesn't just save a lot of money, some edge environments -- essentially single servers -- are already PiB+. Storage bandwidth is typically greater than network bandwidth these days so many workloads scale well this way. Quantity has a quality all its own. Fragmenting your database over thousands of servers introduces new classes of failure and greatly increases the risks of other types of failures that you don't have to deal with when you only have dozens of servers or a single server. High-density storage does require strategies for recovery that reflect the bandwidth-to-storage ratios. Designers are usually aware of the implications and architect appropriately.
- cryptonector 4y agoAh, SQLite3 grows up! That is, with this (and external projects like rqlite), SQLite3 really begins to break out of the embedded RDBMS space. The SQLite4 stuff I guess didn't just get completely abandoned. I guess it was a good experiment.
- gigatexal 4y agoHere’s an odd ball question: why did K8s devs go with etcd and not SQLite?
- remram 4y agoThere are distributions of Kubernetes that use SQLite instead of etcd, for example k3s: https://docs.k3s.io/architecture https://docs.k3s.io/architecture The drawback is that it's not replicated. With etcd, you set up multiple control-plane nodes (ex: 5) and you can tolerate a minority of them being down without any effect (ex: 2/3 down). With SQLite, you can only have one control-plane node, and if it's down your control-plane is unavailable. This is fine for small clusters where you don't want to run multiple control-plane nodes, or you don't think it will go down, or you don't mind fixing it.
- ddorian43 4y agoBecause they are different things.
- vkazanov 4y agoEtcd is a key-value storage based on a distributed consensus algorithm. This (sort of) means that you can have a source of cluster truth in the db and make sure it lives through certain distributed system bad scenarios. Sqlite is a (relatively) simple in-process sql rdbms. You get a proper reliable sql on a single computer, which is practically useful for many more cases. It is possible to build distributed dbs on top of a bunch of sqlite instances but one would need to solve these very distributed system problems that etcd solves. In fact, some of the popular distributed dbs use etcd or zookeeper or custom implementations of the same algos o top of traditional rdmss. K8s is a distributed system that needs to have a reliable view of its nodes. Clearly, a concensus-based db is necessary.
- gigatexal 4y agoSo that would make etcd consistent and available (CP of the CAP)? edit: almost -- available and partition tolerant at least in the default config: https://github.com/cloudfoundry-attic/etcd-release/blob/master/README.md#fault-tolerance-and-data-durability https://github.com/cloudfoundry-attic/etcd-release/blob/mast...
- adius 4y agoFor all SQLite fans here: We are currently working on a full-fledged SQLite hosting platform. Check it out at https://airsequel.com https://airsequel.com. So far we provide an instant GraphQL API, an SQLite workbench, a spreadsheet UI, and dashboards.
- MobiusHorizons 4y agoWhy would you ever want to put a network between SQLite and the application logic. That is SQLite’s one cool trick as it were. At that point the db seems like an implementation detail rather than a selling point.
- deleted 4y ago[deleted]
- college_physics 4y agoSqlite is maybe the most extreme success example of a real MVP: solving efficiently a narrow problem and adding complexity incrementally as needed. While not without limitations (eg it is conceivable that the concurrency backend is made more difficult by earlier choices) overall it is a remarkable pattern which has produced gems like spatialite. Is there anything else like this out there?