lichtenberger

One of the best introductions I've found :-)

Why would it make more sense? You'd first have to sort the keys, then pretty print, then diff:

https://www.jvt.me/posts/2020/08/24/pretty-print-json-diff/

I'm also using a JSON-diff format in my data store[1], which is accumulated during insertions/updates/deletes in-memory and serialized during a commit, admittedly for large JSON instances (a few Gb and much more).

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

Oh that's what you described in your first reply.

Give it a try ;)

There's a new variant called the HOT (height optimized trie) to improve over ART :) but really nice, didn't know of SIP or highway hash, but I wanted to prevent collisions as There's also a diff algorithm, which compares revisions (that said we now also store the type of change, plus the context nodes and the root of the change in a simple JSON file -- so changes are tracked, too).

The data in SirixDB is always indexed by a 64bit int whereas the upper 10 bits denote the position of the node in the page. I've also used different node sizes as in an ART and I'm using a bitset, too in a new node type.

Don't you have to join the data stored in the ART itself? Trying to understand why and how you join index pages :-)

Basically JSONiq, with a few minor syntax differences.

Our query engine/compiler is and can be used by other data stores as well:

http://brackit.io

I'm using a rolling hash with SHA265 but only take 128 bits, as it should be enough to avoid collisions. Leaf node hashes are computed on demand, only inner node hashes are stored persistently.

Can you elaborate a bit more? You mean bitset indexes?

We're also storing a similar hash tree (a hash is stored in each node -- an insert/update/delete triggers a recomputation of the hash in all ancestor nodes) to verify if a subtree has changed in SirixDB[1]. However, only pointers to neighbour nodes as well as the content is used for recomputation of the ancestor hashes instead of all children during updates. Furthermore checksums of child page-fragments are stored in parent references.

The hashes are used for fast diff calculations along with an optional DeweyID node scheme to quickly get diffs in a resource in preorder or to check if a subtree has changed without fetching all ancestor nodes (due to the stored DeweyIDs).

For instance you can simply check for updates of a node in a JSON structure with the following query:

    let $node := jn:doc('mycol.jn','mydoc.jn')=>fieldName[[1]]
    let $result := for $node-in-rev in jn:all-times($node)
                   return
                     if ((not(exists(jn:previous($node-in-rev))))
                          or (sdb:hash($node-in-rev) ne sdb:hash(jn:previous($node-in-rev)))) then
                       $node-in-rev
                     else
                       ()
    return [
      for $jsonItem in $result
      return { "node": $jsonItem, "revision": sdb:revision($jsonItem) }
    ]

It iterates through all revisions of a node and returns the node and the revision (and we could also add the author) when it has been updated.

To make this even easier I could write a native Java function for use in the query.

[1] https://sirix.io

Does anyone know how it compares to Akka?

That's one of the main steps forward for Brackit, a retargetable JSONiq query engine/compiler (http://brackit.io) and the append-only data store SirixDB (https://sirix.io) and a new web frontend. My vision is not only to explore the most recent revision but also any other older revisions, to display the diffs, to display the results of time travel queries... help is highly welcome as I'm myself a backend engineer and working on the query engine and the data store itself :-)

Detect changes of a specific node and the whole subtree/subtree:

    let $node := jn:doc('mycol.jn','mydoc.jn')=>fieldName[[1]]
    let $result := for $node-in-rev in jn:all-times($node)
                   return
                     if ((not(exists(jn:previous($node-in-rev))))
                          or (sdb:hash($node-in-rev) ne sdb:hash(jn:previous($node-in-rev)))) then
                       $node-in-rev
                     else
                       ()
    return [
      for $jsonItem in $result
      return { "node": $jsonItem, "revision": sdb:revision($jsonItem) }
    ]

Get all diffs between all revisions and serialize the output in an array:

    let $maxRevision := sdb:revision(jn:doc('mycol.jn','mydoc.jn'))
    let $result := for $i in (1 to $maxRevision)
                   return
                     if ($i > 1) then
                       jn:diff('mycol.jn','mydoc.jn',$i - 1, $i)
                     else
                       ()
    return [
      for $diff at $pos in $result
      return {"diffRev" || $pos || "toRev" || $pos + 1: jn:parse($diff)=>diffs}
    ]

Open a specific revision

By datetime:

    jn:open('mycol.jn','mydoc.jn',xs:dateTime('2022-03-01T00:00:00Z'))

By revision number:

    jn:doc('mycol.jn','mydoc.jn',5)

And a view of an outdated frontend:

https://github.com/sirixdb/sirix/raw/master/Screenshot%20fro...

The difference might be that Brackit uses sophisticated join algorithms for these kinds of implicit joins as known from relational query processing.

I'm working on a JSONiq based implementation to jointly process JSON data and XML. The compiler uses set-oriented processing (and thus uses hash joins for instance wherever applicable) and is meant to provide a base for JSON based database systems with shared common optimizations (but can also be used as a standalone in-memory query processor):

http://brackit.io

The language itself borrows a lot of concepts from functional languages as higher order functions, closures... you can also develop modules with functions for easy reuse...

A simple join for instance looks like this:

        let $stores :=
        [
          { "store number" : 1, "state" : "MA" },
          { "store number" : 2, "state" : "MA" },
          { "store number" : 3, "state" : "CA" },
          { "store number" : 4, "state" : "CA" }
        ]
        let $sales := [
           { "product" : "broiler", "store number" : 1, "quantity" : 20  },
           { "product" : "toaster", "store number" : 2, "quantity" : 100 },
           { "product" : "toaster", "store number" : 2, "quantity" : 50 },
           { "product" : "toaster", "store number" : 3, "quantity" : 50 },
           { "product" : "blender", "store number" : 3, "quantity" : 100 },
           { "product" : "blender", "store number" : 3, "quantity" : 150 },
           { "product" : "socks", "store number" : 1, "quantity" : 500 },
           { "product" : "socks", "store number" : 2, "quantity" : 10 },
           { "product" : "shirt", "store number" : 3, "quantity" : 10 }
        ]
        let $join :=
          for $store in $stores, $sale in $sales
          where $store=>"store number" = $sale=>"store number"
          return {
            "nb" : $store=>"store number",
            "state" : $store=>state,
            "sold" : $sale=>product
          }
        return [$join]

Of course you can also group by, count, order by, nest FLWOR clauses...

It is bascially about

- What hopes and promises stand behind the technology and which problems they are supposed to solve.

- An accessible introduction of the inner workings of the actual technology and their possibilities and limitations.

- Are blockchain-based solution the only possibility to address the problem? If not, what are alternatives and substitutes?

- What is the reality behind the promises? A subjective evaluation of the technology based on the items above.

- A list of questions to ask yourself or an expert, before investing (financially or technologically) into that particular layer.

That's precisely what I did in the beginning of my career. To test every method and mock all the dependencies. This had the impact, because we usually don't use a dependency injection framework, that I had to add an interface for almost every class, adding factories with interfaces almost everywhere and then write tests which expect certain method calls and to basically debug the tests while writing them until all calls have been mocked. Thus, whenever I changed the production code I had to change the test as well.

IMHO in my own projects I tend to write tests which test certain parts of a system as well as some dependencies. So usually I'd say they are integration tests instead of unit tests. But I can refactor stuff and once I break something it's usually detected by one of the tests. Maybe unit tests should test for certain cases border cases, which are hard to test with integration tests.

Yes,the new memory model for instance for "immutable classes" for instance will be one of the biggest improvements for some applications as you can finally build cache line optimized data structures, which are for instance nowadays common in in-memory database systems. I think first considerations regarding this have been made already 10 years ago.

The new upcoming (or even already in preview) language and platform features also support each other very well. I think they are heading in a clear direction with the different projects.

I'll have to check how to call `madvise` to set MADV_RANDOM as index accesses in my use case are rather random, though. But the 2Gb chunks at most have been a really big issue. Luckily, the Foreign Memory API is getting to it's final version I think. The latest changes aren't that big IMHO :-)

They'll move the classes to the final packages in Java 19 :-)

I think the main point is accessing the foreign memory safely.

Really interesting that you played the soundtracks and liked them even without watching the movies. Did it change after watching the movies? Did you like it even more?

That was one of the first algorithms I learned at the university, thanks for posting :-)

I'd say dancing 3 times a week for instance is a real guarantee to lose weight if you simply drink water at the dance locations for instance. Once I mostly quit dancing 2 years ago because of Covid-19 I gained more than 10kg weight :-/

This is precisely what https://github.com/sirixdb/sirix does. A resource in a database is stored in a huge persistent structure of index pages.

The main index is a trie, which indexes revision numbers. The leaf nodes of this trie are "RevisionRootPages". Under each RevisionRootPage another trie indexes the main data. Data is addressed through dense unique and stable 64bit int nodeKeys. Furthermore, the user-defined secondary indexes currently are also stored as further tries under a RevisionRootPage.

The last layer of inner pages in a trie adds references to a predefined maximum number of data page fragments. The copy-on-write architecture does not simply copy whole data pages, but it depends on the versioning algorithm. The default is a sliding snapshot algorithm, which copies changed/inserted/deleted nodes plus nodes, which fall out of a predefined window (usually the size is low, as the page fragments have to be read from random locations in parallel to reconstruct a full page). This reduces the amount of data to store for each new revision. The inner pages of the trie (as well as the data pages) are not page-aligned, thus they might be small. Furthermore, they are compressed before writing to persistent storage.

Currently, it offers a single read-write transaction on a resource plus read-only transactions without any locks.

As posted in another comment that's basically what https://github.com/sirixdb/sirix supports along with easily reconstructing former revisions of a JSON document (or any node therein), sophisticated secondary (also versioned) indexes, querying with JSONiq and optimizations at query compile time as for joins and aggregates....

In our case we opted for three types of secondary user-defined indexes (besides the main document trie index to find unique, stable nodes by their 64bit ID), namely

1. field indexes

2. path indexes

3. content-and-structure indexes which index paths and their typed values

Furthermore a path summary keeps track of all distinct paths in the JSON resource.

Very interesting, thanks for pointing out :-)

True. In general I could add storing relational data as well, but currently I'm entirely focusing on JSON and auto-indexing for secondary indexes as well higher order function support in Brackit.

Of course we'd need more man-power as I'm more or less the only one working on the core in my spare time (since 2012).

Moshe mainly works on the clients and a frontend. A new frontend based on SolidJS is in the works showing the history and diffs as in

https://raw.githubusercontent.com/sirixdb/sirix/master/Scree...

However, we're of course looking forward to suggestions, bug reports, real world use cases and contributions :-)

It's in our case the tree root of the index, which is always written after all the descendant pages have been written as a new revision is committed (during a postorder traversal of the new pages).

In ZFS the UberPage is called UberBlock. We borrowed some of the concepts as to add checksums in the parent pages instead of the pages itself. In ZFS they are blocks :-)

Thanks for asking.

In order to provide fast audits of subtrees, the system stores optionally a merkle hash tree (a hash in each node) and updates the hashes for all ancestors automatically during updates.

I'd argue that's still a lot of work to manually do. However, great work and detail, thanks a lot :-)

I'm working on a database system[1] in my spare time, which automatically retains all revisions and assignes revision timestamps during commits (single timestamp in the RevisionRootPage). Furthermore, it is tamper proof and the whole storage can be verified by comparing a single UberPage hash as in ZFS.

Basically it is a persistent trie-based revision index (plus document and secondary indexes) mapped to durable storage, a simple log-structured append-only file. A second file tracks revision offsets to provide binary search on an in-memory map of timestamps. As the root of the tree is atomically swapped it does not need a WAL, which basically is another data file and can be omitted in this case.

Besides versioning the data itself in a binary encoding similar to BSON it tracks changes and writes simple JSON diff files for each new revision.

The data pages are furthermore not simply copied on write, but a sliding snapshot algorithm makes sure, that only changed records mainly have to be written. Before the page fragments are written on durable storage they are furthermore compressed and in the future might be encrypted.

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

It is nice, but I wonder if it's also a full-fledged query compiler?

Also IMHO modules with user-defined (higher order?) functions are a big plus of a query language.

JSON loading boilerplate? Is it also a compiler with sophisticated optimizations during compile time? :)