4 ms·

Key features are: - log-structured storage system with copy-on-write semantics especially well suited for SSDs (random reads, writes are batched and synced to

Key features are: - log-structured storage system with copy-on-write semantics especially well suited for SSDs (random reads, writes are batched and synced to disk when a commit is issued) - implements a novel versioning algorithm called sliding snapshot, which balances read/write-performance and has other beneficial characteristics. We also implement full, incremental and differential versioning at the page-level - stores hashes of the page-fragments in parent pointers in our main hash array based trie structure in the indirect pages as in ZFS. In the future these can be used to validate the integrity of the whole resource - compression of each page, as well as encryption in the future - for each XDM/XML-node in our on-disk structure we optionally store the descendant-count, the child-count as well as a hash of the content - a diff algorithm, which uses our stable node-identifiers and optionally hashes for comparisons of node-pairs in different revisions - a RESTful, asynchronous, temporal API written with Vert.x in Kotlin - several temporal XPath axis extensions, which could also be used for JSON in the future - several XQuery functions to open, diff, commit... a resource - opening revisions of resources either by an ID or via a given timestamp. In case of the given timestamp the revision is searched by binary search and either the revision is found or the revision, which is closest to the given point in time is opened

platform 8y ago
could you describe major differences and overlaps between your solution and Datomics, MarkLogic temporal documents (https://docs.marklogic.com/guide/temporal/intro https://docs.marklogic.com/guide/temporal/intro). Some compare with any other database 'time travel' feature would be helpful as well. Thank you
- lichtenberger 8y ago
  Thanks so much for asking. I'm not sure how they are actually storing their bitemporal documents, but I think it must be some kind of a huge B(+)-tree maybe. I think the cool thing is that we have revision root pages and are able to reconstruct each revision in merely the same time. We currently have a tree, very similar to how ZFS stores the objects on-disk. It's more or less a form of a hash array based trie. The number of levels of the indirect pages currently is static, but I'll change this and only create a new level once it's really needed as in ZFS. During every change to the resources in Sirix never in-place changes occur, instead it does a copy-on-write of the involved page and a pointer to the former version is created. This is necessary for our versioning algorithms as it has to fetch at most N former versions of the page, depending on if the page has been modified (usually N should be between 2 and 5 or something like that). The index structures currently are AVL-trees (thus also versioned), simply stored as data records in the leafes, but it would be best to plug in a B-tree in the future. On a higher level I have added many operations, which are usually not found in XML databases, for instance as our internal tree structure is a kind of persistent DOM firstChild/rightSibling/leftSibling/parent encoding I added move operations to move subtree. A path summary stores all paths in the resource and is kept updated at all times as are optional indexes on paths, elements, attributes or content-and-structure. The interesting thing is with the help of extensions to Brackit(.org), which also has some basic JSON navigation primitives already built in I was able to add temporal axis. I added several XPath axis to navigate in time, for instance first::, last::, all-time::, next::, previous::, future::, past::*... we also allow diffing, opening a resource in a specific revision...
  - platform 8y ago
    interesting. last:: -- I assume, means 'most-recent'. maintaining pre-calculated 'most recent' is very useful (as long as I can ask 'what was most recent, say, yesterday at 1pm'). Most of the 'hand-made' append-only data schema design suffer from not being able to return 'joined' most-recent datums, quickly. Because a 'usual' implementation requires doing join with select max on business or system (or both) time stamp My understanding that both DBs I mentioned previously do copy of write for temporal data, but I am not sure if they do any document level-diffs.
    - lichtenberger 8y ago
      Yes, the revisions can be reconstructed in merely the same time, for instance it doesn't matter if you open the most recent revision or any past revision regarding system/transaction time. We also do not have to store the transaction time more than once (in the revision - root page). And if you do a fine granular modification, we usually do not copy and rewrite the whole page with currently 512 records (it depends on the versioning algorithm you use).
    - lichtenberger 8y ago
      I think they might store a bitemporal that is two dimensional index. However, I think this is not really efficient to reconstruct a specific revision in comparison to our approach, where we just have to follow pointers from the revision root pages.
- lichtenberger 8y ago
  Ph.D. thesis which might also help from Marc (from which the idea and everything originates) http://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/Kramis2014.pdf http://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/Kramis... From Sebastian Graf: https://kops.uni-konstanz.de/bitstream/handle/123456789/27250/Graf_272505.pdf?sequence=1&isAllowed=y https://kops.uni-konstanz.de/bitstream/handle/123456789/2725... The XQuery compiler from Sebastian Baechle: http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publications/2013/Dissertation-Baechle.pdf http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...
- lichtenberger 8y ago
  During our copy-on-write we also do not necessarily store the whole record-page (leaf page with data/records), but depending on the versioning algorithm only changed records since some past state. The sliding snapshot algorithm for instance (with a sliding window) is very clever in balancing read-/write-performance.

platform 8y ago

could you describe major differences and overlaps between your solution and Datomics, MarkLogic temporal documents (https://docs.marklogic.com/guide/temporal/intro https://docs.marklogic.com/guide/temporal/intro). Some compare with any other database 'time travel' feature would be helpful as well. Thank you

lichtenberger 8y ago
Thanks so much for asking. I'm not sure how they are actually storing their bitemporal documents, but I think it must be some kind of a huge B(+)-tree maybe. I think the cool thing is that we have revision root pages and are able to reconstruct each revision in merely the same time. We currently have a tree, very similar to how ZFS stores the objects on-disk. It's more or less a form of a hash array based trie. The number of levels of the indirect pages currently is static, but I'll change this and only create a new level once it's really needed as in ZFS. During every change to the resources in Sirix never in-place changes occur, instead it does a copy-on-write of the involved page and a pointer to the former version is created. This is necessary for our versioning algorithms as it has to fetch at most N former versions of the page, depending on if the page has been modified (usually N should be between 2 and 5 or something like that). The index structures currently are AVL-trees (thus also versioned), simply stored as data records in the leafes, but it would be best to plug in a B-tree in the future. On a higher level I have added many operations, which are usually not found in XML databases, for instance as our internal tree structure is a kind of persistent DOM firstChild/rightSibling/leftSibling/parent encoding I added move operations to move subtree. A path summary stores all paths in the resource and is kept updated at all times as are optional indexes on paths, elements, attributes or content-and-structure. The interesting thing is with the help of extensions to Brackit(.org), which also has some basic JSON navigation primitives already built in I was able to add temporal axis. I added several XPath axis to navigate in time, for instance first::, last::, all-time::, next::, previous::, future::, past::*... we also allow diffing, opening a resource in a specific revision...
- platform 8y ago
  interesting. last:: -- I assume, means 'most-recent'. maintaining pre-calculated 'most recent' is very useful (as long as I can ask 'what was most recent, say, yesterday at 1pm'). Most of the 'hand-made' append-only data schema design suffer from not being able to return 'joined' most-recent datums, quickly. Because a 'usual' implementation requires doing join with select max on business or system (or both) time stamp My understanding that both DBs I mentioned previously do copy of write for temporal data, but I am not sure if they do any document level-diffs.
  - lichtenberger 8y ago
    Yes, the revisions can be reconstructed in merely the same time, for instance it doesn't matter if you open the most recent revision or any past revision regarding system/transaction time. We also do not have to store the transaction time more than once (in the revision - root page). And if you do a fine granular modification, we usually do not copy and rewrite the whole page with currently 512 records (it depends on the versioning algorithm you use).
  - lichtenberger 8y ago
    I think they might store a bitemporal that is two dimensional index. However, I think this is not really efficient to reconstruct a specific revision in comparison to our approach, where we just have to follow pointers from the revision root pages.
lichtenberger 8y ago
Ph.D. thesis which might also help from Marc (from which the idea and everything originates) http://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/Kramis2014.pdf http://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/Kramis... From Sebastian Graf: https://kops.uni-konstanz.de/bitstream/handle/123456789/27250/Graf_272505.pdf?sequence=1&isAllowed=y https://kops.uni-konstanz.de/bitstream/handle/123456789/2725... The XQuery compiler from Sebastian Baechle: http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publications/2013/Dissertation-Baechle.pdf http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...
lichtenberger 8y ago
During our copy-on-write we also do not necessarily store the whole record-page (leaf page with data/records), but depending on the versioning algorithm only changed records since some past state. The sliding snapshot algorithm for instance (with a sliding window) is very clever in balancing read-/write-performance.