lichtenberger

Oh, and Sirix optionally already stores a rolling merkle hash over the data.

It's first and foremost a document store / so for JSON or XML currently, that's why it's not SQL compliant. I think other query languages as JSONiq are much more tailored to this, albeit a niche of course (based on XQuery).

Regarding tamper proof audit logs not much is missing. Cryptographic hashes instead of XXH3, a commit hash chain and signed commits. Actually, I think that's a great addition with minimal changes needed.

What you can audit currently is "who changed what" for instance.

Besides, documents are split into fine granular nodes, so we have "no" upper limit besides running out of 48bit nodeKeys/node identifiers at some point maybe.

Furthermore, a (versioned, as always) path summary keeps track of all distinct paths, which is a key ingredient for the optional secondary indexes, which can index paths or paths and content among other stuff as simply indexing fields. Optionally you can also add indexes to speed up aggregate queries (which are basically column projections).

Furthermore, the whole storage can self-validate through checksums stored in parent pages up to the root as in ZFS for instance.

DeweyIDs can be optionally stored for each node, which can speed up the comparison of subtrees between revisions (in order to detect simply which changesets belong to a certain subtree without having to traverse ancestor chains). They lend themselves well for compression.

We even have importers which can identify based on heuristics minimal edit operations to import existing revisions of XML or JSON documents and to commit these with hopefully a minimal or close to minimal set of update operations, but it depends heavily on the data.

I'm working on a side-project in my spare time since the end of 2012 (before at the university) with some gaps, which is an append-only DBS with time travel capabilities using a custom storage engine based on COW tries and a (still I think) novel page versioning strategy called Sliding Snapshot. Recently I began work on pooling pages for reuse and a custom allocator for variable page sizes. Before, I had created new instances whenever a page was read from disk instead of reusing instances, so the allocation rate was really high for parallel transactions.

https://sirix.io | https://github.com/sirixdb/sirix | http://brackit.io

Yes, in the Valhalla builds of course :-) That said I hope we'll see the value classes at least in Java 25.

Seems, that we already have value classes in the EA builds :-)

I once implemented the backend of a calendar and resource control for a low code platform.

The control is highly customizable, with a lot of views to chose from, daily, monthly, yearly... but also resource views (you can book resources with custom groupings, by plugin, by the resource-ID, whatever...), define "plugins" on the data sources, what's the from- and to- columns, the title column, what's the resource (may be from a foreign key / 1:1 relationship or 1:N if it's from a "child" data source or from the same data source/table).

Furthermore I've implemented different appointment series, to chose from (monthly, weekly (which weekdays), daily...), which column values should be copied. Also appointment conflicts (or only conflicts if they book the same resource). You could also configure buffers before and after appointments where no other appointment can be.

That was a lot of fun and also challenge sometimes regarding time zones and summer/winter time in Europe and so on :-)

So, I think in my local bubble noone is for instance as excited about DB systems as I am, so in essence I thought I could even spend some money to get some expert opinions or rather insights I'm struggling with (currently for instance with bad throughput of my immutable OSS DBS). That said I think noone so far wanted money and some even offered help, but so far I think they didn't have time, thus didn't answer any "pings". So, as I can't spend too much time (and of course not too much money) either on profiling and debugging right now it's kind of a dilemma, as it would IMHO be very interesting to know what's slowing down N read-only trxs in my system :-) that said a couple of years ago I also asked about help with a frontend without much luck. I guess it has to have some value of course, so maybe at least spending some money (even if it's a non profit spare time project since 11 or even more years) should be OK :-)

Guess I just felt a bit frustrated...

Throughput. The code can be "suspended" on a blocking call (I/O, where the platform thread usually is wasted, as the CPU has nothing to do during this time). So, the platform thread can do other work in the meantime.

https://kotlinlang.org/docs/whatsnew20.html

See also https://github.com/JetBrains/kotlin/releases

We're using a similar trie structure as the main document (node) index in SirixDB[1]. Lately, I got some inspiration for different page-sizes based on the ART and HAMT basically for the rightmost inner pages (as the node-IDs are generated by a simple sequence generator and thus also all inner pages (we call them IndirectPage) except for the rightmost are fully occupied (the tree height is adapted dynamically depending on the size of the stored data. Currently, always 1024 references are stored to indirect child pages, but I'll experiment with smaller sized, as the inner nodes are simply copied for each new revision, whereas the leaf pages storing the actual data are versioned themselfes with a novel sliding snapshot algorithm.

You can simply compute from a unique nodeId each data is assigned (64bit) the page and reference to traverse on each level in the trie through some bit shifting.

[1] https://github.com/sirixdb/sirix

The technique is also described in the awesome book "Crafting Interpreters" by Robert Nystrom.

Super interesting read about COW, log-structures and a mix thereof (CObW -- copy on bounded writes).

I think it depends, but I wonder if anything can be done about the problem with checked exceptions in lambdas / for instance the streams. I think the enhanced switch with handling failure is only part of the solution, but I'm also a proponent of having only unchecked exceptions.

At least they are already discussing the next version.

Oh, seems also because of random in-place writes of the B-tree.

Because it has to copy and write entire pages instead of only force a flush of log records due to a WAL?

What about storing the data and thus, the indexes in Kafka. Would it make sense? Let's say currently, I'm storing SirixDB resources in files. However, instead of offsets into a file the index pages could be stored in Kafka optionally (or Pulsar...). Is Kafka too slow for this or only for specific row-tuples? We could make a combined storage caching the pages locally or also storing in the file system and asynchronous storing in Kafk, S3 or whatever.

Well, it may be a B-tree, or an LSM-tree, a trie or whatever index structure suits...

Also, of course you may have covering indexes.

"Database Design and Implementation" by Edward Sciore is also a very great read with a lot of examples written in Java (actually a small DBS).

For actual research I'd recommend all stuff from Andy (Pavlo), Viktor Leis, Thorsten Grust, Thomas Neumann...

It's fundamentally how SirixDB approaches this (basically also storing checksums) as also written in another reply :-)

Every commit directly syncs the binary data to the durable storage (currently a file) and incrementally adds data. Furthermore, it stores optionally the changes (type of change/ctx node/updatePosition... in JSON files). For instance, lately I've implemented a simple copy mechanism based on this. Copy a given revision and optionally apply all changes with intermediate commits to also copy the full history up to the most recent revision). However, the main idea is to use the change tracking also for diff visualizations... maybe even stream these via web sockets.

A production ready system BTW may be Datomic.

And it also reminds me of this paper: https://dl.acm.org/doi/abs/10.5555/3275366.3284969

Basically, it retains all revisions. Furthermore, the main document index is a keyed trie, much like hash array mapped tries. That is storing an array as a tree and using compact page layouts (bitmaps, 4 references pages, full pages) to reduce the page sizes if they are not full. However, Sirix assigns monotonically increasing, immutable, unique node identifiers, thus most inner pages are full with references to the next level pages (also checksums of the child pages are stored along with the references as in ZFS). The height of the tree increases dynamically. Currently every inner page stores at most 1024 references, thus it's a very wide tree, but we should experiment with other sizes.

The leaf pages of the trie store either the data itself/the nodes or nodes of the path summary, nodes of the secondary indexes...

Thus, we have the main document index, but a RevisionRootPage also has references to the tries, which store the secondary indexes. The secondary indexes are read into main memory / are reconstructed from the leaf pages of the tries (usually small), also a small path summary.

The data pages are not simply copied... only nodes, which changed or fall out of a sliding window. Thus, a page may have to be reconstructed in-memory from at most a small number N of page fragments in the worst case. Thus, it needs a device, which is suitable for fast random, small sized parallel reads and sequential writes.

Currently you have to copy a resource starting from a given revision and applying all updates up to the most recent revision with intermediate commits in order to get rid of old revisions, as it only uses one data file per resource (a resource is equivalent to a table in a relational system). Thus, the data files are basically logs. Another file simply stores offsets and timestamps read into memory to retrieve a given revision.

https://sirix.io/docs/concepts.html

and

https://sirix.io/docs/jsoniq-tutorial.html

Should probably help to get a further understanding.

HTH and let me know if you're interested in more details :-)

Thanks for asking

Have a look into my DB project: https://sirix.io | https://github.com/sirixdb/sirix

https://sirix.io/docs/concepts.html and in progress tutorial https://sirix.io/docs/jsoniq-tutorial.html may be especially helpful.

It basically turns updates into appends and is based on a persistent tree structure (the header with a reference to the (revision) root page has to be swapped atomically. Other than that the revision indexes for new data are always appended. In order to reduce copy-on-write overhead for updated page (fragments) a sliding snapshot for the data pages is applied.

Naturally, unchanged pages are simply referenced (e.g. through offsets into the file, thus sharing unchanged pages between revisions).

What's also special is a path summary of all unordered paths in a resource, which enables user-defined smaller tailored secondary indexes and other query rewrites :-)

This thread is also a good short summary of the key points: https://twitter.com/jensdittrich/status/1734142079012323480?...

Here's the project website: https://www.tornadovm.org/

I think one of the main problems was, that the marketing was especially terrible as they branded both consumer SSDs with an Optane cache as Optane as well as the "real" Optane DC persistent memory, which is put into the appropriate DIMM slots.

Another issue may be that Optane DC persistent memory simply was not fast enough to replace non persistent RAM.

Still, I hope that another technology will arise, which is byte-addressable and persistent/durable. I think it could radically change the design of database systems again. You wouldn't have to have a page cache / buffer manager, which retrieves same sized blocks (or multiples of blocks) for instance. You probably wouldn't even need serialization/deserialization to disk.

It would be great if it'd be possible to for instance read 512byte blocks from disk with current SSDs, but I guess the block overhead for meta data might be too big.

What I'm missing the most is byte granular reading (in case of Optane it was 256 bytes, because of checksums, but that's fine granular enough).

It means it would be possible to read/write data in much more fine granular chunks (potentially saving a lot of storage space in some cases).

I'm working on something similar for the JVM, however with no document semantics, but on a much more fine granular level.

JSON is shredded during an initial import into a tree structure with fine granular nodes. Thus, an import can be done with very low memory consumption (permitted that auto-commit issues a sync to disk before RAM space is exceeded). Furthermore, it doesn't require a WAL for consistency. Instead the indexes are stored in a log-structure using a persistent tree (as in every commit creates a new tree root). A sliding snapshot algorithm makes sure, that only a fragment of a page has to be copied on a write.

As thus, it's also a perfect candidate for an event store, storing both the (lightweight) snapshots and tracking the changes optionally.

https://github.com/sirixdb/sirix

The architecture is described over here:

https://sirix.io/docs/concepts.html

Furthermore I'm working on a tutorial for a local client usage (work in progress):

https://sirix.io/docs/jsoniq-tutorial.html

Kind regards

Johannes

Yes, basically :)