lichtenberger

I think with modern hardware as for instance the now available first byte-addressable NVM variable sized pages and buffers should in theory get more widespread use and the reading/writing granularity gets more fine granular in the next years. I think as of now the Intel Optane memory however still has to fetch 256 Bytes at the minimum.

However, variable sized pages also allow page compression.

Can you give us some links to the mentioned issues and techniques that achieve high cache and storage bandwith efficiency without VSBs?

In my particular case it was also a design decision made back in 2006 or 2007 already. It's designed for fast random reads from the ground up due to the versioning focus (reading page-fragments from different revisions, as it just stores fragments of record-pages). I'll change the algorithm slightly to fetch the fragments in parallel (should be fast on modern hardware, that is even SSDs and in the future for instance with byte-addressable non-volatile memory).

Yeah, in the advent of byte-addressable NVM... I think we have to rethink a lot of stuff and I'm sure we can get rid of a lot of stuff, which isn't needed anymore or should be replaced with light weight components. I'm trying to achieve some of this with https://sirix.io. However, I hope more and more people will get involved over time as it's of course completely Open Source.

Great work and very interesting ideas. I'm working on a versioned database system[1] which offers similar features and benefits:

    - storage engine written from scratch
    - completely isolated read-only transactions and one read/write transaction concurrently with a single lock to guard the writer. Readers will never be blocked by the single read/write transaction and execute without any latches/locks.
    - variable sized pages
    - lightweight buffer management with a "kind of" pointer swizzling
    - dropping the need for a write ahead log due to atomic switching of an UberPage
    - rolling merkle hash tree of all nodes built during updates optionally
    - ID-based diff-algorithm to determine differences between revisions taking the (secure) hashes optionally into account
    - non-blocking REST-API, which also takes the hashes into account to throw an error if a subtree has been modified in the meantime concurrently during updates
    - versioning through a huge persistent and durable, variable sized page tree using copy-on-write
    - storing delta page-fragments using a patented sliding snapshot algorithm
    - using a special trie, which is especially good for storing records sith numerical dense, monotonically increasing 64 Bit integer IDs. We make heavy use of bit shifting to calculate the path to fetch a record
    - time or modification counter based auto commit
    - versioned, user-defined secondary index structures
    - a versioned path summary
    - indexing every revision, such that a timestamp is only stored once in a RevisionRootPage. The resources stored in SirixDB are based on a huge, persistent (functional) and durable tree 
    - sophisticated time travel queries

As I'm spending a lot of my spare time on the project and would love to spend even more time, give it a try :-)

Any help is more than welcome.

Kind regards Johannes

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

Hi all,

the system has its roots in a university project, for which Marc Kramis had already predicted in 2008 that fast random, very fine granular reads are the key to efficient persistent, durable data structures, which retain its previous versions. We drastically shrink the data to write due to the asymmetry between reads and writes. Batched, sequential writes without in-place updates are also beneficial for nowadays common "traditional" SSDs.

http://kops.uni-konstanz.de/bitstream/handle/123456789/5914/...

Kind regards and happy holidays Johannes

Disclaimer: Author here.

Thank you for posting :-) While the storage system is based on a system called Treetank with a longer history it turns out that Marc Kramis, who came up with the first ideas and a first implementation for his Ph.D. had a tremendous vision about the future of persistent storage (for instance fast random reads in conjunction with fine grained access to storage) and that we can shift our focus from clustering constraints of traditional B+-trees to a storage engines which stores a dense distribution of unique, dense strictly sequential 64bit integers in a keyed persistent, durable trie.

His report "Growing Persistent Trees into the 21st Century" is from 2008:

http://kops.uni-konstanz.de/bitstream/handle/123456789/5914/...

SirixDB strictly drops the requirement of a predefined block-size as well as clustering. It even versions data pages, which are stored in small sized variable-length byte arrays. The whole tree of a revision is based on many tries and revisions are indexed as well as AVL trees for secondary indexes.

The system is also heavily inspired by ZFS and some of their design decitions put to test on a sub-file level.

Any help in putting forward the vision of a versioned, persistent (in the functional data structure sense) data store would be amazing :-)

You can also implement a hash map as a tree ;-)

For densely packed IDs (32 or 64 bit integers...) I think it's even faster to use a keyed trie structure, as it can use fast bit-shifting operations in contrast to using standard B+-trees.

Also, this can be used as a persistent, on-disk / flash drive data structure or as a hash array mapped trie for HashMap implementations in-memory (Scala or Closure for instance).

For a persistent (both in the sense of functional programming as well as storing on non-volatile disk), this is for instance implemented in SirixDB (https://sirix.io), a temporal data store prototype I'm maintaining and developing :-)

Pretty nice tool :-)

But what if the data store would do all of that already?

  - retaining the history of your data:
    - free deduplication through copy on write and sharing unchanged structures
    - further store space savings through page-level versioning (not all records in a page have to be written: just the changed/inserted/deleted ones plus depending on the algorithm a few more to fast track it's reconstruction)
    - read and write performance is balanced using a sliding snapshot algorithm: This avoids having to read long chains of incremental page changes and it avoids write peaks from intermittant full page snapshots. Instead they get trailed over a few (usually three or four revisions).
    - the sorage manager stores timestamps for all revision in a RevisionRootPage, which itself is indexed

  - Optional commit author and message
  - Reverting to and committing a past "good" revision is just adding a few bytes to index a new RevisionRootPage which references the past revision data (simple pointer)
  - You can diff taking rolling hashes into account
  - Currently I'm working on a diffing JSON format and a web front-end to display these in special space filling approaches
  - Sophisticated time travel queries
  - typed, user-defined and versioned secondary index structures (based on AVL trees)
  - a path summary kept up to date always
  - a lot of metadata stored and kept up to date for each record/node

It's already implemented in https://sirix.io / https://github.com/sirixdb/sirix

I'm working on getting it stable, but help from you, the Open Source community is always needed :-)

For sure you'd have to add rolling hashes, but that's probably more natural in a tree based data store.

I've added these to https://sirix.io, which fastens diffing considerably, especially with deep trees. Otherwise indexing changes could be done :-)

I'm working on a temporal document store in my spare time. If done right and you have an index structure which let's say indexes each revision of a table (in my case binary XML or JSON as of now) as in Git for instance you simply append a new RevisionRootPage. This page is indexed of course and points to the former revision-data. Should be super fast, so you don't have to replay changes made in the meantime. Even if I'd write to a distributed log for instance and would read from it the changes since revision n. I think that way you can also version the whole database easily.

https://sirix.io / https://github.com/sirixdb/sirix

Great lecture so far. Haven't had the time to watch the whole lecture, but one thing I want to mention is that there are techniques to improve the buffer manager performance as for instance described here by Goetz Graefe: http://www.vldb.org/pvldb/vol8/p37-graefe.pdf

I've implemented an even simpler solution for my Open Source Data Store (https://sirix.io) in that each page stores a number of references, which are itself lightweight pointer objects (in Java) and it simply stores an in-memory reference as well as a pointer to the location to fetch it from disk/a flash drive. If the buffer manager has these Objects as keys on eviction we can simply null the reference to the in-memory page instance.

Eroll Garner is one of my most favorite pianists. Plus, as a Lindy Hop dancer it's super great to hear his music and dance to it.

Nowadays, I love Gordon Webster and of course... Stephanie Trick and Paolo Alderighi.

I also don't know why duplicating timestamps for each row to store the transaction times is needed for a kind of history table.

Other data models with schema after write semantics (for instance trees or graphs) don't have this problem of having to store schema changes.

As I'm working myself on a temporal storage system in my spare time (as well as during my student times at the University of Konstanz), I'd say that you should index each revision instead, storing the timestamp of the transaction commit in a RevisionRootPage for instance, which is the root and main entry to deserialize a revision. Unchanged pages should be shared amongst the different revisions.

Furthermore due to fast random access of flash drives and even parallel I/O with PCIe SSDs you can store page-fragments instead of whole pages. The SSD might fetch too much information due to misalignments, but I'd say that access to persistent storage also gets more fine granular in the future (byte level granularity instead of block-level or the blocks are smaller-sized -- I think even 512 bytes is not that unusual nowadays).

Not only storing the incremental or differential changes from a database page, but changes which fall out of a sliding window doesn't make intermediate full dumps of pages necessary, such that write and read peaks don't occur and a predictable number of page fragments can be read to reconstruct a page in-memory, preferably fetching the fragments if possible in parallel.

I'm working on storing data in a log-structure persistently without the overhead of a transaction log in my spare time (Open Source[1]). Instead, an UberPage which guarantees consistency is atomically swapped during a transaction commit (inspired by ZFS). It should be used for data, which doesn't fit into main memory. Revisions are always appended, whereas almost only changed data plus some metadata is written to a file during commits.

You can easily retain the full version history in a log structure, but you need fast random access (option of parallel "real" access would be best) on a flash drive -- PCIe SSDs for instance.

Basically in order to balance read and write performance only a fraction of each database page (with changed records) needs to be written sequentially in batches to the end of a file.

Each revision is indexed under a RevisionRootPage and these are indexed under the UberPage with keyed tries.

This opens up a lot of opportunities for analysing data and its history.

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

Just wanted to add that tree and graph structures of course can be stored sequentially on disk or a flash drive (log-structured). For instance with a really fast random access storage and some additional space you can even save the history, that is lightweight snapshots of your data. That is you always append data.

This way you can also use clever versioning algorithms to predict the performance (no read or write peaks) and to lower the space consumption.

Yes, I saw them. Also his book is one of the best computer science books I've read and he gave me a really good advise for my own Open Source project, regarding the use of BookKeeper as a distributed log (instead of Kafka) :-)

I think Automerge from Martin Kleppmann is super interesting :-)

However, as he told me a more sophisticated persistence layer is needed. Looking forward how it's emerging

Shouldn't clean code always be maintainable? Or maybe if setting everything up is too cumbersome or the build system is crappy it's not maintainable, hmm.

I think it's doable (I'm also a backend dev and started a frontend a few days ago). But I guess it would be great if you also get some help to begin.

However, maybe we should use https://www.npmjs.com/package/@vue/composition-api instead of giving Vue.js 3 a try if some things are simply not implemented as of now.

Probably better, hm. But as SirixDB itself is in a kind of pre alpha state I think if we encounter a few bugs it would be okay or even slight API changes.

If we get some documentation I'd love to use it for a brand new front-end (idea) for https://sirix.io:

https://github.com/sirixdb/sirix-web-frontend

https://dev.to/johanneslichtenberger/working-on-a-versioned-...

https://dev.to/johanneslichtenberger/building-a-web-frontend...

However, I'm in need of some help, as I'm completely new to web front-end development :-)

Great work on Dolt and seeing temporal data stores emerging :-)

Regarding XML and JSON SirixDB[1] already provides full blown time-travel queries using a fork of Brackit[2], that is basically XQuery to process and query both the XML as well JSON documents. That said SirixDB in principal could also store relational data or graph data. The storage engine has been built from scratch to offer the best possible versioning capabilities. However I've never implemented branching/merging as I didn't come up with good use cases. It seems it's then always more of a versioning system like Git, but more fine granular.

I always struggled to implement this as SirixDB currently only allows a single read-write transaction on a resource. Thus, if it would support branching and merging users would have to manually handling conflicts when merging (or automatically -- using a merge-strategy which is often case not good).

There's however plently of optimization potential, as SirixDB optionally stores a lot of metadata for each node (number of descendants, a rolling hash, Dewey-IDs, number of children... as well as user-defined, typed secondary index-structures). I'll have to look how to build AST rewrite rules and implement a lot of optimizations into my Brackit binding in the future, so it's just the starting point (but everything should at least work already) :-)

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

[2] http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

I'm not really sure how Noms versions stuff. It seems they use a variant of a B-tree index. Or maybe only for secondary indexes?

I think if you can use a simple monotonically increasing sequence number SirixDB has indexing advantages as for instance when storing XML and JSON documents or graph data.

The cool thing also is that SirixDB not only copies changed database pages but it implements a sliding window algorithm for versioning the database pages itself along with well known backup versioning strategies. Furthermore user-specified, typed secondary index structures are also naturally versioned.

One downside is that SirixDB doesn't support branching, even though it would be relatively easily possible to implement I guess, but I'm not convinced that it's needed. I don't want that anyone has to merge merge conflicts. I think automatic algorithms to do this are also not the right thing. But of course it's really interesting and I also thought about it :-) maybe someone has a really good use case? :-)

BTW: Everything in SirixDB is immutable regarding updates of resources in databases. Of course you can revert to an old revision and change stuff, but the revisions in-between will still be accessible.

Keep up the great work on Quilt :-)

So you basically store S3 Buckets in Elastic Search and you're using Git for versioning a hierarchy of buckets, right?

It's interesting that versioning now finally seems to be getting some traction in mainstream database systems (even though they are not really optimal in these systems my opinion) and for instance also in your data store. You position this as a Dropbox or Google Drive replacement, right? :-)

I'm asking all these questions, because I'm engineering a temporal, versioned Open Source storage system myself (since I studied at the University of Konstanz until 2012), possibly on a much more database oriented level -- currently for storing both XML and JSON data in a binary format.

A resource in this storage system basically stores a huge tree of database pages whereas an UberPage is the main entry point (reminiscent of ZFSs UberPage, from which SirixDB borrows some ideas and puts these to the sub-file level), consisting of various more or less hash-array based subtrees as in ZFS. Thus, levels of indirect pages are added if more data needs to be stored. I've added some optimizations from in-memory hash-array based tries.

Each revision is indexed. SirixDB stores per revision and per page deltas based on a copy-on-write log-structure.

I've thought about storing each database page fragment in a S3 storage backend as another storage option and using Apache BookKeeper directly or Apache Pulsar for distributing an in-memory intent log (it doesn't need to be persisted before committing to the data files, as the UberPage just needs to be swapped atomically for consistency).

For the interested reader:

https://sirix.io and https://github.com/sirixdb/sirix

Regarding the question if Apache Pulsar or Apache BookKeeper for me it's not so clear which of both to use. I think it adds a lot of value if you add the WAL to the public API. Forgot how it's called, I think change data types (CDTs) without searching on google!? So basically you have the stream of events and expose these for use by applications :-)

I've already written with one of the core committers to BookKeeper and yes, I think I'll use it.

That said, I'm always looking for users and contributors to https://sirix.io/ or https://github.com/sirixdb/sirix. That would be super awesome, but I'm sure you have your own ideas already for using BookKeeper.

I'm currently not sure if I first want to build a frontend (I'm a backend engineer, but would like to learn some TypeScript along with using Vue.js and D3js), to interact with SirixDB and to build interactive visualizations to compare revisions of JSON- or XML-resources in SirixDB (stored in a binary format of course highly optimized for space-efficient snapshots).

I think as I'm lacking users it might be more useful, but for sure I'm at least as eager to put forth the idea of scalable SirixDB databases :-)

So, I'd like to use BookKeeper most probably (single writer, read your own write consistency, using synchronous -- for a quorum -- and asynchronous replication for the rest, exactly once semantics...). The thing I don't like is that we also need ZooKeeper, but yeah.

BTW: Why do you think BookKeeper is better than Kafka for this purpose? :-)

I like the idea, to use Apache Kafka as the underlying log. It's in principle what Martin Kleppmann suggests.

As I also want to use a distributed log in the future: Do you know Apache Pulsar or the underlying BookKeeper, which I think was especially made for a distributed WAL?

I might either want to use Apache BookKeeper or Apache Pulsar for a distributed log for scaling my Open Source temporal database, too. Furthermore I'd like to expose the API for streaming changes into the Browser or wherever you want to :-)

By the way, not directly related, but I wonder if there are at least libraries to build type safe XQuery statements?

You can reconstruct a revision in O(n), you can search for a specific revision in O(log n) and the transaction time is stored in a revision root page (time the transaction commits). Thus, you do not have to store the time for each node (even start- and end-time).

Furthermore Sirix does not have to copy whole record pages which have changed, it depends on the chosen versioning algorithm. The whole structure is highly concurrent and allows client side parallelism. We also do not have to write in a WAL first, but the structure is always consistent (if no hardware failure occurs...).