Upvote for Syncable & Embeddable. It will take a massive amount of time to build from ground up, so I wonder if it's sensible for you to build SQL on top of RocksDB like CockroachDB did: https://www.cockroachlabs.com/blog/cockroachdb-on-rocksd/
Especially an immutable database (like Git's index) sounds like a very powerful concept. No more need for modification dates (they would be in the change record) and no need at all for separate log tables and all that guff. Every CRUD system ends up with some sort of audit log tacked on, costing heaps in terms of both maintenance, storage and extra processing for every change. In addition I would want there to be a command analogous to `vacuum` to truncate this history while the database is online, similar to Git's rebase or filter-branch.
> An embedded, immutable, syncable relational database.
Sounds like he wants a blockchain?
A blockchain probably isn't really what OP wants. But funnily enough it does meet all those criteria.
> what I’m after is a database to be embedded on client-side applications itself, be it desktop, browser, mobile, etc.
Thats how most Blockchain clients work - on the client side, with APIs (usually RPCs) to chat with other programs
> Being immutable means that only new information is added, no in-place update ever happens, and nothing is ever deleted.
Immutability is exactly what blockchains were designed for.
> Syncable
Since blockchains are decentralized by nature, this also comes out of the box.
Of course if you choose a blockchain you have to deal with a host of other issues... performance, no SQL (in most clients), harder to debug, etc. But still a fun thought experiment
Blockchains are meant as a data store. Archival, verifiable. But not easily searchable. There is no design on blockchain for advanced query languages/logic.
It seems like the OP is going after something like blockchain that adds querying. But I don't think blockchain syncing is designed well enough for client-side use, and the OP seems to want to use this database client-side in JavaScript. I think it would be possible to implement blockchain syncing with WebRTC, but WebRTC has some security risks for users (IP leakage mostly) so I am not sure I would start off with that as a primary communication channel.
Hyperledger fabric gets around this by storing a copy of the data up to the last block in some other db, like couchDB. That way, you get (supposedly) the best of both worlds
Most blockchain clients have a DB with a cached version of the chain. This is typically done with a typical, off the shelf DB. For example Bitcoin Core uses LevelDB, but other implementations use SQL lite.
As I said at the end, blockchain isn't really what OP wants. It meets his requirements mostly via technicalities.
I have to question the "relational" part. SQL is an absolutely massive language, to the point where "we support SQL" is almost an empty statement because there's no single SQL to support.
While revamping the database, consider a smaller query language. I built a GraphQL-based database query language in my GraphQL compiler project[1], and it's been a huge success at my company so far[2][3]. Here's a demo of cross-database querying with it, if you're curious [4].
I'm not really an expert on the field. But, have you considered that maybe SQL is massive for good reasons?
The subset of SQL that covers majority of use cases is actually small and probably mostly covered by the standard.
All the rest of SQL which makes it a massive beast is for all those cases where adding the logic to the database would've been the most efficient for all those who need that extra bit of efficiency.
It's slightly more likely that modern SQL is the byproduct of several query language specifications accelerated to ludicrous speeds and set to collide with each other. Out one end of the apparatus, SQL-86 emerged.
A little known fact about this experiment: the residue splattered along the interior of the apparatus was recovered and named LDAP.
I think SQL is massive because of two major reasons:
1. It has a highly inconsistent, non-generalized syntax
2. It tries to reuse the language for everything -- from schema specification, to querying, to administration, to query engine hints, to procedural language definitions
The RDBMS in total is a highly complex system, but SQL adds a lot of accidental complexity on top of it.
Also for a new DB, you hardly need to support the whole suite of features to produce a useful system -- you just need to constrain the recommended usecases. See SQLite for the quintessential example -- they dropped MVCC and a lot of management/multi-tenancy features as they targetted a surprisingly large niche.
As it turns out, there's a wide variety of data management needs -- SQL is often a beast because most RDBMS's have a goal of targetting all of them.
I'm building a relational lang (http://tablam.org) so this is close to my interests.
SQL is not just massive, it have grown past it actual capabilities and original purposes without fix or clean it, then ALSO need to be the interface for some of the most complex piece of software (rdbms) and support the needs of a multitude of features, frameworks and languages. Is like html/css/js.
Going to basics, the relational model is fairly simple, and you can spice it with functional and/or procedural features to round it and still keep it very small.
So yes, I think it can be done MUCH better than SQL and still do MUCH more than it can right now...
P.D: My language TablaM (will!)is basically this plus a little of array programming. You can fit very well the relational model in a lisp/tcl/datalog like environment with a small core that is very expressive...
In fact "TablaM" come to sound like "Kablam!" https://www.youtube.com/watch?v=9glnVMq1xrE, a nickelodeon weird program of the past (when it do a lot of cool things). I have a habit of put weird names to my projects...
Then I morph into tablam, and later in the game I create a pseudo-plausible rationalization where "Tabla (spanish)" == "Table" and M is for "Multi-paradigm, -platform, -dimension, etc" that is the one explanation I will use in case get serious people asking me :)
Why is it 'massive'? I don't think it is. Compared to say C++, or programming in python where the language is smallish but the libraries considerable, I can't see why you say that.
I'm not sure what you mean by not as flexible as relational model. I'll address SSB, as I'm more familiar with it, as I've built a CRDT system on top of it in clojurescript.
Each message can be linked by its content addressable hash. The engine allows for Map/Filter/Reduce queries which are not much different in capabilities from SQL queries, these can even be indexed to speed up views. The only real difference is that no schema is enforced on each message type, but it's not that difficult to enforce something like that on a higher layer when publishing entries.
If you think about it, storing JSON entries is a lot more flexible than table rows. Also, the content stored need not be JSON, but EDN, transit or reference to binary blobs.
> Each message can be linked by its content addressable hash.
What I had in mind is, while as you well said, you can link the data in a pub in any way you need, the distribution model is fixed. The only way to change that is creating more pubs.
I think the distribution model is an integral part of the data structure in a general p2p setting and needs to be customizable, within reason.
Thanks for your response, I find this stuff super interesting to watch evolve.
I think I understand a bit of your concern, although note that the pubs aren't necessarily required for replication in SSB, one can use onion routing, physical devices (sneaker nets), local area connections, etc. But I agree, that there are more areas to improve, such as changing the network/capabilities keys on the fly from within a message to ratchet the distribution, making reference to content hashes within different network keys, etc. I'm curious if your work takes any of this into account? Thanks again.
Gotta figure out what your needs are. For example, if browser and node is a requirement than you can look at RxDb which uses Pouch and either Indexeddb or various file options.
If you want everything, it’s going to be big and not appropriate for web or mobile unless part of browsers or the OS.
Immutability is an interesting property, but reality is messy. Depending on the use case you envision for the database, data that needs to be scrubbed will accidentally be added to the system. This could be an important private key, or something legally dubious. In an append only/sync system there isn't really a good way to scrub that data. (Replay the entire history, filter bad data, then delete all remotes and resync from clean copy is not good). Again depends entirely on the use case of the database you envision, but if you wish to make it general purpose it is something to consider.
It’s interesting because it reflects the reality of modern computing — for many use cases storage capacity is not a meaningful constraint.
I ran pretty important systems as a DBA years ago that we’re significant but would never, ever require a meaningful constraint on growth. (Performance, different story)
Sometimes looking at a problem like a database with a new set of constraints leads to interesting and novel things.
I've been working on personal and professional projects where growth isn't a truly restricting constraint but is still an actual constraint. What do you mean by "meaningful"? Once I get into the 10's of terabytes there's no storage system where copying a TiB of data is "instant" or ignorable.
Professionaly I work on a financial reporting system where there are around 1.5 million accounts with trading activity. Things like moving a month of data around and checksumming still take on the order of 1 hour. If the size of that monthly dataset doubled, we'd be OKAY but it it grew 10x we'd have to start restructuring things both on the software side and the hardware side.
For personal work I am working with searching video frame substrings regardless of codec, resolution etc within videos in a ~50 TiB video set. Having to re-encode hundrends of GiB of video at a time is some thing that takes a huge amount of time and nothing something I can just "throw into an S3 bucket". The growth of said working set is not truly constrained but is actually constrained. I can only afford so many 8-10 TiB HDDs at a time! They also fail and have to be mirrored/backedup with rsycn at the very least which adds to the cost for me.
I mean that it’s not a technical constraint or limit. Not that its trivial to do! If there is an ROI in keeping stuff forever, you can.
Think about what you’re saying about your personal project. What you’re talking about wasn’t financially achievable for TV companies just 20 years ago. Hell, anything older than a few days would be stored offline in some tape silo, or in a shelf. (And 10-12 people to attend to it!) Now you as an individual could afford to do all sorts of stuff with that video data, albeit for some significant $.
I really don’t get why GDPR gets dragged up every time someone mentions immutable data stores; was everyone really building append-only systems before 2018?
It has been a legal requirement in the UK that databases must be able to delete personal data since the data protection act 1984 - https://www.legislation.gov.uk/ukpga/1984/35/enacted - in particular see the data protection principles in schedule 1: the 6th principle requires that data is retained no longer than necessary. There are provisions elsewhere in the act that can require a data holder to delete data.
Most of GDPR is not really new. There was a significant amount of teaching about data protection when I was at university in 1994-1997 and it wasn’t even new then.
Database immutability does not mean it's impossible to delete content.
It means you separate two use cases: retracting information (I remove an item from my shopping cart because I want another item) and purging data (I delete my account and all my shopping history because I don't want the shop to store my data anymore).
You can still purge data easily in Datomic, for example.
This article[1] from 2015 has stuck with me for years, talking about the same approach. The interesting thing about transactional/bitemporal databases is really the effect on how we consume them with our applications. The schema can be separated from the transaction data, schema migrations become easy, tables become cached materialized views (with the cache updated concurrently at write time), reduced need for application-level cache, no cache cold start, and pub/sub becomes the norm.
I’m the same regarding that article. I always thought of that article as a kind of “deconstruction” or “decoupling” and “rearrangement” of traditional DBMS architecture.
The end result you speak of is a more flexible data platform, which can handle more use cases, including applying decoupled parts to different things.
A good example, in my mind, is Apache Spark - which is like taking a compute and SQL query engine, making it distributed and decoupling it from the underlying storage. Now, suddenly SQL or code can be used on anything you can fit into a data frame, even streams - wow!
Pulling out the transaction log - and wow, suddenly we have durable, potentially immutable queues we can use for even long term storage.
I was so excited by the line of thinking in that article. :)
The problem of deleting stuff from a history of changes is challenging. But I think Darcs, the distributed version control system written in Haskell, does this rather neatly.
Darcs is different from git in that a "commit" (called a "patch" in Darcs lingo) does not depend upon the entire history of what has come before. Rather it has specified dependencies, which Darcs can infer itself – or you can specify if you want more semantic content in the patch structure.
A repository is a collection of patches, which are merged using something called patch algebra. So, if you want to delete a patch, you just issue the command "darcs obliterate" and it will remove the patch, and anything which depends on it. Then working directory is reconstructed by merging together any loose ends using patch algebra.
With careful administration of dependencies, this approach makes deleting specific things very slick.
> Immutability is an interesting property, but reality is messy.
Words have fuzzy boundaries - immutable obviously doesn't mean actually immutable. It means immutable like how git is immutable - you're not meant to change history. It'll fight like a tiger to stop you easily changing history. It'll give you two different ways to get what you want while preserving history. But if you want to change history you can.
SQL is said to be declarative but if you get hit dealing with the wrong sort of workload in SQL then the implementation details can start to matter extremely quickly.
In practice, the author probably only means 'much more immutable' rather than 'illegal to use with European data' level immutability.
True. And what makes it easy is it's immutability. When you change history in Git, you rewrite it (rebase). But re-writing is only possible if you know every bit of the journey up to now. When you have actual updates, history is lost.
the way git changes history is a stretch on the word change, rebasing creates a parallel history and then promotes it to be the true one. the reflog still remembers the previous history.
Let me disagree. I'm working on a transactional OS [1] with an immutable filesystem, it's primarily a website builder. Every request creates a new snapshot of your website. It's append-only for the duration of the transaction. That's the only way to provide robust rollback and also provides version snapshots for free - but it doesn't mean snapshot's can't later be removed.
My solution was to provide an undo-chain of a fixed given length. Versions older than that simply "fall off the chain" and will be picked up by GC eventually. You can also make snapshots long-lived snapshots if you want.
(Of course removing a snapshot is an append-only operation :P but GC will go after non-referenced snapshots eventually.)
I just want a database that takes no configuration options except for a list of peers and a disk partition to write to and provides strictly serializable transactions 100% of the time (modulo partitions).
I'd rather start with slow and correct, and implement hacks to improve performance once slow becomes "too slow". But instead, database engines are sold on benchmark performance, so out of the box they lose transactions they told you they committed, or read uncommitted writes, or all sorts of other crazy things. I don't want this unless I write code myself to do those things. (If I go through the API, it must be completely consistent. If I clone the drive of the database server and pick around at random disk blocks, sure, maybe I'll see some uncommitted writes.)
I really like FoundationDB. It still feels like that system where if it breaks you will be blamed aggressively for picking a weird thing, so I'd like to see some more success stories, I guess. But if I really care, maybe I should be the success story.
The Go API is also kind of weird, and conflicts with my general thought on Go code that every I/O operation should be cancelable with a context -- they really don't subscribe to that point of view.
Those are the main reasons why I don't use it... but I guess they have the fundamentals down (the "foundation" if you will), so it's probably worth powering through those nits and start using it.
Firebase (whether it be Firestore or realtime database) has almost none of the desired properties in the article. The only one it does have, as far as I can tell, is "syncable".
Indeed, Irmin is a library to implement data stores which can be freely cloned, updated and merged along a model similar to git.
It separates the content from the actual store. So it can run as well on a file-system, on a git repository, in memory or in the browser (See for instance https://github.com/talex5/irmin-js).
I think what's even better than relational may be directly using OOP objects, using the system prevalence pattern.
If you're willing to model your "DB updates" using event sourcing, you could fork something like Prevayler to achieve your immutability needs while being able to serve as source of truth across multiple nodes.
It's very difficult to have traditional OOP with pervasive immutability, because it almost entirely removes the idea of a stable instance of an object. There is no single instance that you call methods on or send messages to. Every method call or message processing must produce a new instance.
More generally, encapsulation fails here. Immutability cannot be encapsulated behind the same interface as mutability. An immutable interface by necessity will look different from a mutable interface (at the very least methods that would normally return `void` in a mutable interface cannot ever exist in an immutable interface).
Scala is mostly immutable and OOP+FP works very well with it.
Also, just because an object is immutable doesn't mean that every method is going to return a new instance of that object. For an example, a 'sum' method on a list of integers object would return an integer, not a list.
As a general rule of thumb Scala is precisely OOP when it's mutable and FP when it's immutable. The fusion occurs exactly at the boundary between mutable and immutable code.
Yes if you have only read-only methods then immutable and mutable methods coincide, but that's precisely the place where mutability doesn't matter to begin with.
Eventually somewhere in your code you have to write something and that's where mutability both matters and results in different APIs.
However, you're right that my initial statement "Every method call or message processing must produce a new instance." is way too strong. I should've meant every write-based call (or message processing).
Good points. There's also the minority notion that you can use OOP where it design-wise makes sense, and procedural/functional/whatever where that makes sense. Of course, if code becomes too esoteric, you risk making a special snowflake noone else is willing to look at.. So probably kind of explains why people take an all-or-nothing approach is most general cases.
My point then is to fully utilize OOP where applicable, to gain the advantages of orthogonal design. This special effort in design may take many attempts to get right, in order to provide more flexibility and power than in initial iterations.
It's a super interesting set of requirements - and I've been mentally trying to wrestle with an extra ones on top of that - selectively syncing data.
Let's say I've got three users of my bookkeeping app. Person A and Person B are in different companies, totally separate data. Person C is a bookkeeper and wants to work with both their sets of data.
It's a trivial example where you can just say "well you just keep Person A's and Person B's data separate and switch what the bookkeeper gets to see when they want to reconcile separate accounts".
I don't have any good solutions for it yet, but I'm enjoying exploring them.
Noms has gone pretty quiet since the acquisition. Dolt is based on noms (not sure how much is has diverged) and much more active: https://github.com/liquidata-inc/dolt
Also have wanted this. Operating on data locally means it can be fast and low latency (on device, not between devices).
I think the secret lies in using CRDTs to sync data in a way that allows it to be processed into another system. E.g. Postgres on a server and SQLite on a phone.
I'm not sure what exactly Scuttlebutt covers or does not cover, but an example real problematic situation that I have seen is like this:
1. The system among other things stores user-entered content;
2. User A has published sensitive personal data about person B (perhaps in a doxxing-like post, perhaps by making a fake profile with their name and data, perhaps including interesting images), and to make things interesting also regarding other laws in other countries, let's assume that person B is underage (which is also realistic and common, school kids do things like that to each another).
3. Person B requests that user A removes that content, and A refuses.
4. Person B escalates (the specific process does not matter much) finally resulting in you getting a legally binding request to remove that information about person B from your system/product.
So the key tech requirements include both breaking immutability and full centralised control; you can do decentralised systems for e.g. performance and bandwidth reasons, but fully decentralised, user-controlled censorship-resistant technologies can't be used because then you can't implement censorship, and you need that ability.
There doesn't even have to be a person B. Under the terms of the GDPR you have the right to an erasure request, which means the party holding your data must erase your data, whatever that may be, and it must be erased from backup systems too.
I think DuckDB checks a number of these boxes! It is embedded and written in C so compilable to WASM. It is also 10x faster than SQLite and interoperable with Apache Arrow! It might be a good place to start anyway!
Have you ever used a flat file database? I envision the perfect database having a file system API that automatically sorts and can be edited using standard files, but stores data using like JSON or YAML. That way it can be versioned and queried using the standard file system tools, or those that implement the Unix Philosophy.
I tried this for a small project once about 10 years ago, using svn as version control and putting a GUI around it. It was clunky, with no good way of doing uniqueness or foreign key constraints, and slowed way down after ~1000 records. I ended up moving to a regular database and implemented the versioning logic manually, which was pretty straightforward.
At first this irked be because the final solution didn't retain the full power of a VCS. No merges, no branches, etc. But what I finally came to terms with was that it didn't need to (YAGNI): it just needed historical records and that was pretty easy. It ended up being much cleaner and faster that way.
I think that you'd have to also implement indexes to make that work, just like SQL databases do. Even with SQL, I ran into plenty of cases that indexes were necessary for decent speed. Flatfiles would just amplify that.
And, if you're trying to use the VCS to do merges, the indexes will constantly get messed up, so they'd have to be reindexed after every merge to be sure they were legit, and it still wouldn't ensure uniqueness... Ouch.
I'm longing and has the need for this type of database, and the time is ripe now for someone to implement it. It should be a local first and networked/distributed second, since IMHO the latter feature should be the sync problems not database problem per se.
The closest to this idea is SQLite (open source and mentioned in the article) and SQL Anywhere from SAP (commercial and not mentioned in the article). But as the article pointed out most of the current solutions rely on SQL.
I'd love to have the new database system to be open source and uses modern open data format for examples TileDB, Arrow and Parquet. The computation part should be language agnostic and independent of the programming languages such as JuliaDB or personally I'd prefer D programming language.
Coincidentally, around seven years ago Bryan from Joyent (Joyent's presentation is mentioned as the main motivation early in the article) has blogged about this similar effort targeting POSIX systems (specifically ZFS) that eventually becomes Manta and now part of Triton a.k.a SmartDataCenter [1]. For details implementation please refer to the original paper [2].
That depends on the programming language, for example C# with LINQ and functional programming languages are pretty good at expressing queries. SQL has no capability for abstraction and so only the simplest queries will be succint, if you want to e.g. union two similar queries then you'll have to copy and paste.
With Common Table Expressions you can process the shared data in one set ("temporary table" is a good mental model for it), compute the unique parts in subsequent sets and use the results for the UNION in a single query.
C# LINQ is basically very roundabout way of doing what SQL was made for. What SQL does, and does really well, is operate on sets of data (aka tables) using set theory. You can get succinct expression with C# and functional languages, but they are not really possible to optimize the same way SQL is because it's not bound by set theory the same way.
SQL by default operates on multisets instead of sets; iIt has no syntax for a set (aka table) literal, SELECT 1, "a" FROM DUAL UNION SELECT 2, "b" UNION ... doesn't count; sub-queries (using another SELECT in a FROM clause) are a pretty recent addition; and the list goes on. It's not based on a set theory, or on the first-order logic, or the relational model, not really. If it were, it would be be Prolog.
Regarding table literals, some products support using
VALUES (1, 'a'), (2, 'b'), ...
as a table constructor in general, not just in INSERT, and looking at SQL:92, SQL:99, and SQL:2003 it looks to me like this should be standard SQL. Derived tables, aka subqueries, exist in SQL:92 at least as well, so whether or not that is considered recent depends on how you look at it, I think.
I am not trying to defend SQL with this, and all in all this does not take away from the points you raised, but the above were something that stood out.
They were in SQL:92, but IIRC adoption was somewhat slow and patchy, and has generally finished somewhen in the early 2000s.
My point is, the parent's claim that SQL "operate[s] on sets of data (aka tables) using set theory", and does it "really well" but when you actually look at SQL, you realise that sets/tables aren't really first-class ― derived tables were added in later versions of SQL, and literal tables still don't exist, but those are things you expect a language focused on table manipulations to have. Nope, it's a language for building very specific kinds of queries which was then patched and extended into something more general.
I find most strongly typed functional languages get too hung up on the structure of the rows. E.g. what happens to SELECT user_name, price FROM orders JOIN users ON user_id? You might end up with something like this:
But that will quickly get messy if you have multiple tables, and you have to explicitly say how to order joins (which you don’t do in sql), and something which just analyses the function calls (ie can’t look inside the lambdas) can’t really know that it only needs to look at a few columns of the tables. So maybe instead you need special values to represent the columns of your tables but then how can you represent the necessary renaming when you join one table multiple times? And how will you describe computations with those fields?
Ultimately I think this is a problem largely involving bindings and sets of things and that these are difficult (if not impossible) to move to the type level while providing a nice api. So you could either get a risky api that can throw runtime errors for queries that could never be valid or you get issues like the ones I described above.
Datasets there work like [(column_name, value)] heterogenous lists would work on Haskell. It does really not get that problematic. (All the problems go away in Haskell if you decide to use maps too.)
But yes, it throws runtime errors. The nature of retrieving data from a foreign service is that it will throw runtime errors. There is some verification you can do, but a strong typed database layer just makes promises it can not fullfill.
Linq can be used in a declarative way such that the AST is available and can be rewritten for optimization or transformation say to SQL [1].
Not that this is easy but many project utilize it and the relinq project tries to give you a more usable starting point [2].
After having done SQL for years then Linq, I actually prefer the more explicit operation of Linq by default, I know the order of execution is the one I specify. Also being able to use a full rich imperative language in the query is so very useful.
I can’t help but be extremely pessimistic. This is an insanely challenging project. Looking at the author’s other side projects: https://euandre.org/about.html
I’d guess this project is about 10,000x-100,000x as challenging as the Songbooks one. And the author has no obvious experience writing DBs, that I can see?
This project seems at least as ambitious as CockroachDB. Development started on CockroachDB 6.5 years ago, was founded by a group of Google alums with relevant distributed systems experience (working on GFS), and it since became well funded and has had a sizeable team working on it full time for years. This project would be almost impossible to make significant progress against without a strong, well funded team working on it for years, but the author speaks about it as a side project.
You are assuming that one needs to build a new database to achieve the requirements. That is unlikely. This sounds more like a glue-code project, where you combine different existing solutions, like Git, local SQL and probably a SQL server to form a whole, pre-made solution. What the author wants is implemented essentially by many many teams. Each time from scratch. All we need is someone baking this into a re-usable framework. That is STILL ambitious for a side project, but far from impossible.
I don't think so. For one, he wants it to run in the browser, and SQLite doesn't run in the browser. In his "embedded" section, he makes it pretty clear that he doesn't want to build on SQLite:
> SQLite is a great example of that: it is a very powerful relational database that runs almost anywhere. What I miss from it that SQLite doesn’t provide is the ability to run it on the browser
> Mentat was an interesting project, but its reliance on SQLite makes it inherit most of the downsides (and benefits too) of SQLite itself.
Also, I'm sceptical you could make SQLite efficient for an immutable DB, IF you want to support full SQL. A DB like Datomic has to do some pretty crazy stuff to be remotely efficient, and it doesn't even try to support full SQL - a great read on Datomic internals: https://tonsky.me/blog/unofficial-guide-to-datomic-internals
Mentat, the DB he links to, is much less ambitious than this proposal, and had a couple years of work by a number of devs before eventually being shuttered/abandoned. It's about 35K lines of Rust, despite being built on top of SQLite, isn't remotely done, doesn't run in the browser, etc.
Even if you did build this proposed DB on top of another DB, to make it efficient, and have all of the features discussed, I strongly suspect that it would be an absolutely massive amount of work.
What does "10,000x-100,000x as challenging" mean? If the songbook cost him one week, this will cost him at least 200 years? I love a good hyperbole, but this is just disparaging.
Most databases that we use are written by hundreds to thousands of people and take years to become reliable and mostly bug-free. It can easily take much more than 200 programmer-years.
By that yardstick nobody should ever attempt to write an OS or programming language or game engine from scratch. I am glad there are plenty of individuals who try.
ye but be realistic. If you're just one dude that has no experience in creating operating systems then you shouldn't seriously try to write one from scratch.
For giggles, sure go into the project with the idea that it will fail, that's not an issue. However if you're serious then what the poster is saying is that its over a lifetime's worth of work.
The Linux that was created by one person is far from the Linux that exists today. The Linux that exists today was created by hundreds (thousands?) of people over the span of decades.
Time to plug the osdev wiki, a very cool read even if you're not planning to write your own OS. Here's the beginner mistakes page: https://wiki.osdev.org/Beginner_Mistakes
> you will never have enough time to write something comparable to modern Linux or Unreal alone
That is only true if you're retaining their respective requirements and architecture. Not necessarily a good idea.
Linux supports tons of devices and architectures very few people are using: people are only paid to add stuff, no one is paid to remove it once no longer needed, so it tends to accumulate. Writing an OS in C is not necessarily a good idea in 2020, if I would be interested in writing a new OS I would do it in .NET.
Unreal engine is not that complicated in comparison to modern Linux. I think when people are watching modern video games or technical demos and saying "wow", they overestimate complexity of code, and underestimate complexity of assets.
But they're usually started by one or a few people. If they get somewhere promising more resources can be added over time to make it more than a cool PoC.
Fair enough, pulled those numbers out of my a, and they are indeed too high. ~1,000x seems like a better incredibly rough guess. i.e. if the Songbook project is 1 dev, 1-2 weeks, this would be more like (extremely roughly 2-4 years for a team of 10 devs).
CockroachDB sounds like it has a target market of a couple of hundred to low thousands companies though. How many people are in the market for a "[A] SQL database for building global, scalable cloud services that survive disasters." [0]? It sounds like a pretty good product, lots of potential, etc. But there are not that many people who need to run their own cloud and maintain uptime in the event of a data centre being taken out. If I ever use CockroachDB it is probably because some cloud provider decided to offer it and not Postgres. Those core features are targeted at problems that only a very small subset of people have.
Compare that to embedded/immutable/syncable/relational. Everybody in software has dealt with software where that would be a compelling feature set in a database. These are solutions to problems any developer has encountered. It is, in that sense, a much easier project for people to understand and get behind.
OP probably doesn't have useful opinions on how his software should handle a direct nuclear strike on his production machine. He probably does have useful opinions on when he should cheat and let a little bit of mutability into the otherwise 'immutable' system.
I am yet to see any GB/TB project that cannot be handled by traditional RDMS systems, so I don't wish for new databases other than when I have to work without either Oracle or SQL Server and wish to have their productivity tooling around.
> test_onefile.c - This file implements a demonstration VFS named "fs" that shows how SQLite can be used on an embedded device that lacks a filesystem.
About a couple years ago I used sql.js [1] in an internal tool to provide the user the ability to execute SQL queries against the data they had loaded. It worked just fine.
Maybe one can learn from and avoid the biggest mistake of sql: mixed commands and date. Maybe one can separate the command from the data in the control.
234 comments
[ 2.9 ms ] story [ 233 ms ] threadSounds like he wants a blockchain?
A blockchain probably isn't really what OP wants. But funnily enough it does meet all those criteria.
> what I’m after is a database to be embedded on client-side applications itself, be it desktop, browser, mobile, etc. Thats how most Blockchain clients work - on the client side, with APIs (usually RPCs) to chat with other programs
> Being immutable means that only new information is added, no in-place update ever happens, and nothing is ever deleted.
Immutability is exactly what blockchains were designed for.
> Syncable
Since blockchains are decentralized by nature, this also comes out of the box.
Of course if you choose a blockchain you have to deal with a host of other issues... performance, no SQL (in most clients), harder to debug, etc. But still a fun thought experiment
Blockchains are meant as a data store. Archival, verifiable. But not easily searchable. There is no design on blockchain for advanced query languages/logic.
It seems like the OP is going after something like blockchain that adds querying. But I don't think blockchain syncing is designed well enough for client-side use, and the OP seems to want to use this database client-side in JavaScript. I think it would be possible to implement blockchain syncing with WebRTC, but WebRTC has some security risks for users (IP leakage mostly) so I am not sure I would start off with that as a primary communication channel.
As I said at the end, blockchain isn't really what OP wants. It meets his requirements mostly via technicalities.
While revamping the database, consider a smaller query language. I built a GraphQL-based database query language in my GraphQL compiler project[1], and it's been a huge success at my company so far[2][3]. Here's a demo of cross-database querying with it, if you're curious [4].
[1]: https://github.com/kensho-technologies/graphql-compiler
[2]: https://blog.kensho.com/compiled-graphql-as-a-database-query...
[3]: https://blog.kensho.com/database-agnostic-querying-is-unavoi...
[4]: https://github.com/obi1kenobi/graphql-compiler-cross-db-exam...
SQL is not the same thing as relational. Relational is a model, SQL is a language which (arguably, quite loosely) fits that model.
The subset of SQL that covers majority of use cases is actually small and probably mostly covered by the standard.
All the rest of SQL which makes it a massive beast is for all those cases where adding the logic to the database would've been the most efficient for all those who need that extra bit of efficiency.
A little known fact about this experiment: the residue splattered along the interior of the apparatus was recovered and named LDAP.
I thought SQL descended relatively straightforwardly from SEQUEL.
1. It has a highly inconsistent, non-generalized syntax
2. It tries to reuse the language for everything -- from schema specification, to querying, to administration, to query engine hints, to procedural language definitions
The RDBMS in total is a highly complex system, but SQL adds a lot of accidental complexity on top of it.
Also for a new DB, you hardly need to support the whole suite of features to produce a useful system -- you just need to constrain the recommended usecases. See SQLite for the quintessential example -- they dropped MVCC and a lot of management/multi-tenancy features as they targetted a surprisingly large niche.
As it turns out, there's a wide variety of data management needs -- SQL is often a beast because most RDBMS's have a goal of targetting all of them.
SQL is not just massive, it have grown past it actual capabilities and original purposes without fix or clean it, then ALSO need to be the interface for some of the most complex piece of software (rdbms) and support the needs of a multitude of features, frameworks and languages. Is like html/css/js.
Going to basics, the relational model is fairly simple, and you can spice it with functional and/or procedural features to round it and still keep it very small. So yes, I think it can be done MUCH better than SQL and still do MUCH more than it can right now...
P.D: My language TablaM (will!)is basically this plus a little of array programming. You can fit very well the relational model in a lisp/tcl/datalog like environment with a small core that is very expressive...
1: https://www.youtube.com/watch?v=8ktYyme_sUw
In fact "TablaM" come to sound like "Kablam!" https://www.youtube.com/watch?v=9glnVMq1xrE, a nickelodeon weird program of the past (when it do a lot of cool things). I have a habit of put weird names to my projects...
Then I morph into tablam, and later in the game I create a pseudo-plausible rationalization where "Tabla (spanish)" == "Table" and M is for "Multi-paradigm, -platform, -dimension, etc" that is the one explanation I will use in case get serious people asking me :)
P.D: I have a video for this at https://www.youtube.com/watch?v=Qs6byLBqyR4
https://wiki.tcl-lang.org/page/TclRAL
interestingOnes = Pokemons.queryAll() .whereColor(P.equals(“grass”)) .queryWorstEnemy() .whereColor(P.notEquals(“fire”)) .get();
I'm building something like this, with one extra requirement: permissionless / trustless p2p operation. It works in the browser, here's the README:
https://github.com/hyperhyperspace/hyperhyperspace-core
Each message can be linked by its content addressable hash. The engine allows for Map/Filter/Reduce queries which are not much different in capabilities from SQL queries, these can even be indexed to speed up views. The only real difference is that no schema is enforced on each message type, but it's not that difficult to enforce something like that on a higher layer when publishing entries.
If you think about it, storing JSON entries is a lot more flexible than table rows. Also, the content stored need not be JSON, but EDN, transit or reference to binary blobs.
What I had in mind is, while as you well said, you can link the data in a pub in any way you need, the distribution model is fixed. The only way to change that is creating more pubs.
I think the distribution model is an integral part of the data structure in a general p2p setting and needs to be customizable, within reason.
Cheers!
I think I understand a bit of your concern, although note that the pubs aren't necessarily required for replication in SSB, one can use onion routing, physical devices (sneaker nets), local area connections, etc. But I agree, that there are more areas to improve, such as changing the network/capabilities keys on the fly from within a message to ratchet the distribution, making reference to content hashes within different network keys, etc. I'm curious if your work takes any of this into account? Thanks again.
If you want everything, it’s going to be big and not appropriate for web or mobile unless part of browsers or the OS.
I ran pretty important systems as a DBA years ago that we’re significant but would never, ever require a meaningful constraint on growth. (Performance, different story)
Sometimes looking at a problem like a database with a new set of constraints leads to interesting and novel things.
unsure whether to laugh or cry
Professionaly I work on a financial reporting system where there are around 1.5 million accounts with trading activity. Things like moving a month of data around and checksumming still take on the order of 1 hour. If the size of that monthly dataset doubled, we'd be OKAY but it it grew 10x we'd have to start restructuring things both on the software side and the hardware side.
For personal work I am working with searching video frame substrings regardless of codec, resolution etc within videos in a ~50 TiB video set. Having to re-encode hundrends of GiB of video at a time is some thing that takes a huge amount of time and nothing something I can just "throw into an S3 bucket". The growth of said working set is not truly constrained but is actually constrained. I can only afford so many 8-10 TiB HDDs at a time! They also fail and have to be mirrored/backedup with rsycn at the very least which adds to the cost for me.
Think about what you’re saying about your personal project. What you’re talking about wasn’t financially achievable for TV companies just 20 years ago. Hell, anything older than a few days would be stored offline in some tape silo, or in a shelf. (And 10-12 people to attend to it!) Now you as an individual could afford to do all sorts of stuff with that video data, albeit for some significant $.
Most of GDPR is not really new. There was a significant amount of teaching about data protection when I was at university in 1994-1997 and it wasn’t even new then.
It means you separate two use cases: retracting information (I remove an item from my shopping cart because I want another item) and purging data (I delete my account and all my shopping history because I don't want the shop to store my data anymore).
You can still purge data easily in Datomic, for example.
Something the original post reminds me of a little is Crux [1].
[1] https://opencrux.com/main/index.html
[1] https://www.confluent.io/blog/turning-the-database-inside-ou...
(Nice to see it's still relevant – the article is linked at the very top of the crux about page: https://opencrux.com/about/what-is-crux.html)
The end result you speak of is a more flexible data platform, which can handle more use cases, including applying decoupled parts to different things.
A good example, in my mind, is Apache Spark - which is like taking a compute and SQL query engine, making it distributed and decoupling it from the underlying storage. Now, suddenly SQL or code can be used on anything you can fit into a data frame, even streams - wow!
Pulling out the transaction log - and wow, suddenly we have durable, potentially immutable queues we can use for even long term storage.
I was so excited by the line of thinking in that article. :)
Darcs is different from git in that a "commit" (called a "patch" in Darcs lingo) does not depend upon the entire history of what has come before. Rather it has specified dependencies, which Darcs can infer itself – or you can specify if you want more semantic content in the patch structure.
A repository is a collection of patches, which are merged using something called patch algebra. So, if you want to delete a patch, you just issue the command "darcs obliterate" and it will remove the patch, and anything which depends on it. Then working directory is reconstructed by merging together any loose ends using patch algebra.
With careful administration of dependencies, this approach makes deleting specific things very slick.
That is so backwards I can't take the guy seriously.
Words have fuzzy boundaries - immutable obviously doesn't mean actually immutable. It means immutable like how git is immutable - you're not meant to change history. It'll fight like a tiger to stop you easily changing history. It'll give you two different ways to get what you want while preserving history. But if you want to change history you can.
SQL is said to be declarative but if you get hit dealing with the wrong sort of workload in SQL then the implementation details can start to matter extremely quickly.
In practice, the author probably only means 'much more immutable' rather than 'illegal to use with European data' level immutability.
My solution was to provide an undo-chain of a fixed given length. Versions older than that simply "fall off the chain" and will be picked up by GC eventually. You can also make snapshots long-lived snapshots if you want.
(Of course removing a snapshot is an append-only operation :P but GC will go after non-referenced snapshots eventually.)
[1] https://boomla.com/
I'd rather start with slow and correct, and implement hacks to improve performance once slow becomes "too slow". But instead, database engines are sold on benchmark performance, so out of the box they lose transactions they told you they committed, or read uncommitted writes, or all sorts of other crazy things. I don't want this unless I write code myself to do those things. (If I go through the API, it must be completely consistent. If I clone the drive of the database server and pick around at random disk blocks, sure, maybe I'll see some uncommitted writes.)
The Go API is also kind of weird, and conflicts with my general thought on Go code that every I/O operation should be cancelable with a context -- they really don't subscribe to that point of view.
Those are the main reasons why I don't use it... but I guess they have the fundamentals down (the "foundation" if you will), so it's probably worth powering through those nits and start using it.
It separates the content from the actual store. So it can run as well on a file-system, on a git repository, in memory or in the browser (See for instance https://github.com/talex5/irmin-js).
As git, Irmin uses 3-way merge but applied to arbitrary values and not only files. As described here http://gazagnaire.org/pub/FGM15.pdf and generalized here https://kcsrk.info/papers/oopsla19-mrdt.pdf
If you're willing to model your "DB updates" using event sourcing, you could fork something like Prevayler to achieve your immutability needs while being able to serve as source of truth across multiple nodes.
My point is that you can achieve all the OP's needs without representing your model in SQL.
More generally, encapsulation fails here. Immutability cannot be encapsulated behind the same interface as mutability. An immutable interface by necessity will look different from a mutable interface (at the very least methods that would normally return `void` in a mutable interface cannot ever exist in an immutable interface).
Also, just because an object is immutable doesn't mean that every method is going to return a new instance of that object. For an example, a 'sum' method on a list of integers object would return an integer, not a list.
Yes if you have only read-only methods then immutable and mutable methods coincide, but that's precisely the place where mutability doesn't matter to begin with.
Eventually somewhere in your code you have to write something and that's where mutability both matters and results in different APIs.
However, you're right that my initial statement "Every method call or message processing must produce a new instance." is way too strong. I should've meant every write-based call (or message processing).
My point then is to fully utilize OOP where applicable, to gain the advantages of orthogonal design. This special effort in design may take many attempts to get right, in order to provide more flexibility and power than in initial iterations.
Let's say I've got three users of my bookkeeping app. Person A and Person B are in different companies, totally separate data. Person C is a bookkeeper and wants to work with both their sets of data.
It's a trivial example where you can just say "well you just keep Person A's and Person B's data separate and switch what the bookkeeper gets to see when they want to reconcile separate accounts".
I don't have any good solutions for it yet, but I'm enjoying exploring them.
Not sure what the status of that is since Attic Labs was acquired by Salesforce.
> Status > Nobody is working on this right now. You shouldn't rely on it unless you're willing to take over development yourself.
I think the secret lies in using CRDTs to sync data in a way that allows it to be processed into another system. E.g. Postgres on a server and SQLite on a phone.
1. The system among other things stores user-entered content;
2. User A has published sensitive personal data about person B (perhaps in a doxxing-like post, perhaps by making a fake profile with their name and data, perhaps including interesting images), and to make things interesting also regarding other laws in other countries, let's assume that person B is underage (which is also realistic and common, school kids do things like that to each another).
3. Person B requests that user A removes that content, and A refuses.
4. Person B escalates (the specific process does not matter much) finally resulting in you getting a legally binding request to remove that information about person B from your system/product.
So the key tech requirements include both breaking immutability and full centralised control; you can do decentralised systems for e.g. performance and bandwidth reasons, but fully decentralised, user-controlled censorship-resistant technologies can't be used because then you can't implement censorship, and you need that ability.
At first this irked be because the final solution didn't retain the full power of a VCS. No merges, no branches, etc. But what I finally came to terms with was that it didn't need to (YAGNI): it just needed historical records and that was pretty easy. It ended up being much cleaner and faster that way.
And, if you're trying to use the VCS to do merges, the indexes will constantly get messed up, so they'd have to be reindexed after every merge to be sure they were legit, and it still wouldn't ensure uniqueness... Ouch.
The closest to this idea is SQLite (open source and mentioned in the article) and SQL Anywhere from SAP (commercial and not mentioned in the article). But as the article pointed out most of the current solutions rely on SQL.
I'd love to have the new database system to be open source and uses modern open data format for examples TileDB, Arrow and Parquet. The computation part should be language agnostic and independent of the programming languages such as JuliaDB or personally I'd prefer D programming language.
Coincidentally, around seven years ago Bryan from Joyent (Joyent's presentation is mentioned as the main motivation early in the article) has blogged about this similar effort targeting POSIX systems (specifically ZFS) that eventually becomes Manta and now part of Triton a.k.a SmartDataCenter [1]. For details implementation please refer to the original paper [2].
[1]http://dtrace.org/blogs/brendan/2013/06/25/manta-unix-meets-...
[2]https://queue.acm.org/detail.cfm?id=2645649
SQL by default operates on multisets instead of sets; iIt has no syntax for a set (aka table) literal, SELECT 1, "a" FROM DUAL UNION SELECT 2, "b" UNION ... doesn't count; sub-queries (using another SELECT in a FROM clause) are a pretty recent addition; and the list goes on. It's not based on a set theory, or on the first-order logic, or the relational model, not really. If it were, it would be be Prolog.
I am not trying to defend SQL with this, and all in all this does not take away from the points you raised, but the above were something that stood out.
My point is, the parent's claim that SQL "operate[s] on sets of data (aka tables) using set theory", and does it "really well" but when you actually look at SQL, you realise that sets/tables aren't really first-class ― derived tables were added in later versions of SQL, and literal tables still don't exist, but those are things you expect a language focused on table manipulations to have. Nope, it's a language for building very specific kinds of queries which was then patched and extended into something more general.
Ultimately I think this is a problem largely involving bindings and sets of things and that these are difficult (if not impossible) to move to the type level while providing a nice api. So you could either get a risky api that can throw runtime errors for queries that could never be valid or you get issues like the ones I described above.
Datasets there work like [(column_name, value)] heterogenous lists would work on Haskell. It does really not get that problematic. (All the problems go away in Haskell if you decide to use maps too.)
But yes, it throws runtime errors. The nature of retrieving data from a foreign service is that it will throw runtime errors. There is some verification you can do, but a strong typed database layer just makes promises it can not fullfill.
By contrast, SQL is more constrained about what it can do. It's declarative and you rely on the database engine to optimize the procedure.
Neither is perfect.
Not that this is easy but many project utilize it and the relinq project tries to give you a more usable starting point [2].
After having done SQL for years then Linq, I actually prefer the more explicit operation of Linq by default, I know the order of execution is the one I specify. Also being able to use a full rich imperative language in the query is so very useful.
[1] https://docs.microsoft.com/en-us/dotnet/api/system.linq.ique...
[2] https://github.com/re-motion/Relinq
I can’t help but be extremely pessimistic. This is an insanely challenging project. Looking at the author’s other side projects: https://euandre.org/about.html
I’d guess this project is about 10,000x-100,000x as challenging as the Songbooks one. And the author has no obvious experience writing DBs, that I can see?
This project seems at least as ambitious as CockroachDB. Development started on CockroachDB 6.5 years ago, was founded by a group of Google alums with relevant distributed systems experience (working on GFS), and it since became well funded and has had a sizeable team working on it full time for years. This project would be almost impossible to make significant progress against without a strong, well funded team working on it for years, but the author speaks about it as a side project.
> SQLite is a great example of that: it is a very powerful relational database that runs almost anywhere. What I miss from it that SQLite doesn’t provide is the ability to run it on the browser
> Mentat was an interesting project, but its reliance on SQLite makes it inherit most of the downsides (and benefits too) of SQLite itself.
Also, I'm sceptical you could make SQLite efficient for an immutable DB, IF you want to support full SQL. A DB like Datomic has to do some pretty crazy stuff to be remotely efficient, and it doesn't even try to support full SQL - a great read on Datomic internals: https://tonsky.me/blog/unofficial-guide-to-datomic-internals
Mentat, the DB he links to, is much less ambitious than this proposal, and had a couple years of work by a number of devs before eventually being shuttered/abandoned. It's about 35K lines of Rust, despite being built on top of SQLite, isn't remotely done, doesn't run in the browser, etc.
Even if you did build this proposed DB on top of another DB, to make it efficient, and have all of the features discussed, I strongly suspect that it would be an absolutely massive amount of work.
For giggles, sure go into the project with the idea that it will fail, that's not an issue. However if you're serious then what the poster is saying is that its over a lifetime's worth of work.
In the alternate reality following your dictum, Linux does not exist.
But you will never have enough time to write something comparable to modern Linux or Unreal alone.
That is only true if you're retaining their respective requirements and architecture. Not necessarily a good idea.
Linux supports tons of devices and architectures very few people are using: people are only paid to add stuff, no one is paid to remove it once no longer needed, so it tends to accumulate. Writing an OS in C is not necessarily a good idea in 2020, if I would be interested in writing a new OS I would do it in .NET.
Unreal engine is not that complicated in comparison to modern Linux. I think when people are watching modern video games or technical demos and saying "wow", they overestimate complexity of code, and underestimate complexity of assets.
Compare that to embedded/immutable/syncable/relational. Everybody in software has dealt with software where that would be a compelling feature set in a database. These are solutions to problems any developer has encountered. It is, in that sense, a much easier project for people to understand and get behind.
OP probably doesn't have useful opinions on how his software should handle a direct nuclear strike on his production machine. He probably does have useful opinions on when he should cheat and let a little bit of mutability into the otherwise 'immutable' system.
[0] https://www.cockroachlabs.com/docs/stable/
No it does not. It has a pluggable storage interface that makes no such assumption: https://www.sqlite.org/vfs.html
> test_onefile.c - This file implements a demonstration VFS named "fs" that shows how SQLite can be used on an embedded device that lacks a filesystem.
[1] https://github.com/sql-js/sql.js
https://euandre.org/2020/08/31/the-database-i-wish-i-had.htm...