Day CRX by default stores the data in tar files, using the Tar PM (Tar Persistence Manager). This is quite different from Jackrabbit (the JCR reference implementation), which uses a SQL database. What is the Tar PM, and why does it use the old tar file format?
The Tar PM is a transactional storage engine that is specially made for JCR content. Like relational databases, it supports ACID (atomicity, consistency, isolation, durability), but it doesn't know SQL, or relational integrity, and stores the data in another way.
The biggest difference to a regular database is: the Tar PM is append-only. It doesn't do any in-place updates. Whenever there is a change, the Tar PM appends an entry to the newest file. Even when deleting content, an (empty) entry is appended. While this seems wasteful, it is actually faster than a regular database, because each change results in only one write operation. A database first stores a change in the log file (in many cases the old data and then the new data), and then writes the data again, this time in the main area. The Tar PM only writes the data once. Unused, old data is removed in a separate optimize process during off-peak hours, for example at night.
A regular database appends changes in a log file first (>>>), and then stores it again in the main data file using in-place updates (+-). The Tar PM only appends changes to the latest data file.
Linear Multi-Segment Index
Searching for a particular record in an append-only storage is tricky if you don't know where the record is stored. Scanning all tar files would take too long. For quick access, you need to have an index. Regular databases usually use a B-tree index for this. The problem is: B-trees are not append-only.
The Tar PM uses a special append-only index. Keys are stored in one or multiple index segments. Each segment is a sorted list, and each persistent segment is a file (a tar file of course!). Modifications to the index are kept in-memory until this structure grows too large, then sorted and written to a new file. There could be multiple persisted index segments, but index segments are later merged, ultimately into one large list.
A key lookup goes like this: First, the Tar PM looks in the in-memory index segment, which is implemented as a hash table. If the key is not found, then a lookup in the cache is made, which is also just a hash table. Afterwards, the Tar PM checks the persistent index segments, newest segment first.
Entries are sorted by key (131-903) in the index segment. The index contains pointers (-) where the actual content is stored in the data file.
As the index segments are sorted by key, you could do a binary search. But there is a faster way: the expected position of the key in the list is calculated directly from the key. This is possible because Jackrabbit generates keys (UUIDs) randomly, so entries are distributed almost evenly. In the example above, if you know there are entries 131-903, you can guess where the key 211 is stored, even if there are many keys. To further improve the accuracy of the lookup, the list is split into a number of groups, and the item count of each group is taken into account. If the expected position is off, the file is scanned similar to binary search, but in reality that is very seldom.
Like the data area, the index is append-only, that means data is never overwritten. Old, unused index segments are removed once they are no longer needed.
Why the Tar File Format
The file format of most database systems is proprietary, which makes it hard or impossible to read. The Tar PM uses the standard tar file format. If you are interested, you can inspect the files using one of the many tools that support this format. The tar format is future proof, and has a number of other advantages. One example is point-in-time recovery: while not directly implemented in the Tar PM yet, it is actually quite simple to do manually - just truncate the tar file at a given entry.
Another advantage of the append-only nature is 'backup-ability': Files are never modified after they are written, so backing up the repository is very simple - just copy all files.