4 ms·

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

Have a look into my DB project: https://sirix.io https://sirix.io | https://github.com/sirixdb/sirix https://github.com/sirixdb/sirix https://sirix.io/docs/concepts.html https://sirix.io/docs/concepts.html and in progress tutorial https://sirix.io/docs/jsoniq-tutorial.html 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 :-)

derefr 3y ago
How does Sirix compare to LMDB (esp. MDBX)? (I ask because AFAIK LMDB derivatives do a similar-sounding thing: it updates pages within a write-transaction by first allocating freelist pages to use to write out new copies of those pages with the changes included; these changes recurse upward because the pages are storing a B-tree, until a modified copy of the root page is made; a commit-log pointer is updated to point to the new root page; and then the old rewritten pages are put into the freelist.)
- lichtenberger 3y ago
  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 https://sirix.io/docs/concepts.html and https://sirix.io/docs/jsoniq-tutorial.html 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
- senderista 3y ago
  Note that if your updates are much smaller than a page, you're gonna have a bad time with LMDB. Optimizations like WAL and group commit exist for a reason.
  - lichtenberger 3y ago
    Because it has to copy and write entire pages instead of only force a flush of log records due to a WAL?
    - lichtenberger 3y ago
      Oh, seems also because of random in-place writes of the B-tree.
  - hyc_symas 3y ago
    For a 4KB pagesize, the breakeven point in write amplification vs WALs is around 768 bytes. http://www.lmdb.tech/bench/ondisk/ http://www.lmdb.tech/bench/ondisk/ Above that record size, LMDB is more efficient. For OpenLDAP, with LDAP entries typically being at least 1KB, the LMDB design is ideal. If it's not ideal for other applications, oh well.

derefr 3y ago

How does Sirix compare to LMDB (esp. MDBX)? (I ask because AFAIK LMDB derivatives do a similar-sounding thing: it updates pages within a write-transaction by first allocating freelist pages to use to write out new copies of those pages with the changes included; these changes recurse upward because the pages are storing a B-tree, until a modified copy of the root page is made; a commit-log pointer is updated to point to the new root page; and then the old rewritten pages are put into the freelist.)

lichtenberger 3y ago
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 https://sirix.io/docs/concepts.html and https://sirix.io/docs/jsoniq-tutorial.html 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
senderista 3y ago
Note that if your updates are much smaller than a page, you're gonna have a bad time with LMDB. Optimizations like WAL and group commit exist for a reason.
- lichtenberger 3y ago
  Because it has to copy and write entire pages instead of only force a flush of log records due to a WAL?
  - lichtenberger 3y ago
    Oh, seems also because of random in-place writes of the B-tree.
- hyc_symas 3y ago
  For a 4KB pagesize, the breakeven point in write amplification vs WALs is around 768 bytes. http://www.lmdb.tech/bench/ondisk/ http://www.lmdb.tech/bench/ondisk/ Above that record size, LMDB is more efficient. For OpenLDAP, with LDAP entries typically being at least 1KB, the LMDB design is ideal. If it's not ideal for other applications, oh well.