The Log Structured Store

The log structured store (LSS) exports an abstraction of a record-oriented repository. Records can be variable sized and indexed by record number (remember VSAM anyone?). The LSS also supports compression of the record payload.

In this description of the LSS, we will often talk about the application level. That refers to the abstraction exported by the LSS module, and in this context the application is usually the pstore. However, because LSS is defined as it's own module, rs.db.lss , user programs can be built directly on top of the LSS.

A data segment record summarizes the records written since the previous data segment or EOF record. The length field is the total number of bytes in the data segment including the DSEG record.

The DSEG record was originally designed to support traversing the LSS in the backwards direction, in case a commit record was not found at the EOF. This works because a GAP record is inserted just before a DSEG to ensure that the DSEG appears in the last granule of a 512-byte IO block. Hence, in the backwards direction, you see a sequence of *EOF and DSEG records. However, this is not currently done because it was found to be unreliable (probably because since a DSEG spans multiple IO blocks, we could not be sure that the last IO block would reliably contain a DSEG . It could be the middle of some payload that happens to look like a DSEG . Of course, that could be true for *EOF , too...)

A data record stores the payload of an application-level record (e.g., a heap page from the pstore or an indirect page descriptor). The low 4 bits of the space word identifies the compression algorithm used to compress the payload. The high 28 bits is the number of granules occupied by the data record, not counting the record header (which, note, is 1 granule in size).

A GAP record is used to provide padding so that DSEG and *EOF records can appear in the last granule of an IO block.

A VOLF record contains the path to other volumes. Although a VOLF is present to describe the volume in which it appears, it is not used.

A ZIPA record contains the string name of a compression algorithm.

An *EOF record marks the end of the file. An *EOF record always appears at the end of an IO block that also contains a commit record ( COMM ).

The presence of an *EOF record at the end of the last IO block in a volume is how the LSS quickly finds the most recent commit record in a volume. If the EOF record is not present, then the fallback is to scan forward from the last known commit record (as recorded in the volume header, \LSS ) until a new commit record is found.

An INDX record is a bucket in the hash table which maps (application level) record numbers to LSS record pointers. These records are loaded lazily into IndexEntry structures in memory, where it is called a cache line.

A MIDX record contains the contents of a hash table pointing to INDX records.

A \LSS record appears only at the beginning of a volume file, and describes the volume as a whole. The payload of the \LSS record corresponds to the LSSVolumeHeader structure, and is mostly constant except for the last_cr_at and last_cr_generation fields which are updated occasionally to point to a recent commit record.

All the goodies... Metadata (generation #, version#, timestamp), bookmarks, diff list, midx pointer, prev CR ptr, VH fuel

How we find a commit record... how we find... (1) the last, if no gen# is specified, (2) a bookmarked one, (3) some other one (if gen# is specified), (4) one if EOF is messed up, (5) if there are multiple volumes

The LSS supports a concept of bookmarking particular checkpoints. The commit record maintains direct pointers to each of the bookmarked commit records in addition to the previous commit record.

Bookmarks are intended to support being able to easily roll back to particular significant points in history. For example, bookmark #1 is used by the pstore's online garbage collector to represent the snapshot against which the persistent traversal is taking place (since it employs a snapshot-at-beginning strategy, and multiple commits may happen between when the garbage collection cycle starts and when it completes).

The payload of data records are compressed using one of 16 defined compression algorithms. The commit record contains a table of 15 pointers to the compression algorithm descriptors, which are ZIPA records. Algorithm 0 is always the null algorith which denotes no compression.

lssctl

The persistent store stores three kinds of records in the underlying LSS.

1. Root. The root record, which is always record number 0 (zero), stores information about the pstore as a whole. The contents correspond to the structure RStoreCommitInfo .

2. Indirect Page Data. Certain kinds of indirect pages can contain information used to elaborate the actual objects at runtime. These record numbers are in the range #x100 - #xFFFFFF .

3. Heap Page Data. The contents of each page of the persistent heap are stored in records. Each record corresponds to one page, starting at record #x2000000 .

Currently, for example, symbols that are referenced by the store use indirect page data to store the string repr of the symbol. When a indirect page is referenced by a page that is being loaded,

The contents of the root record (record number 0) correspond to the structure RStoreCommitInfo in rstoret.h and it basically just stores a pointer to the default, or "main", allocation area.

Each page of data in the persistent heap is stored in it's own record in the underlying LSS. Record numbers for heap pages start at #x2000000 (actually, in older versions of RScheme they started at #x1000000 [XXX which versions]).