66 LSS - old documentation from 2005

Status: historical. This chapter preserves documentation written in 2005. Terminology, interfaces and implementation choices may have changed.

Log structured store (LSS)

Summary

Ceda uses a Log Structured Store (LSS) as the underlying persistence mechanism. Advantages are

• The store is simpler that the classical page based systems, like ARIES.
• No particular hardware or OS support is required --> platform independence
• Write performance is optimised – because all objects are written to the end of the log
• Space utilisation is excellent because objects of all sizes are written “crunched up” to the end of the log
• Recovery is simple because the log is self describing. A simple scan of the log allows for recovery of indexing information.
• Because recovery is fast and efficient, check points can be done infrequently. This greatly reduces the amount of indexing information that is written to disk
• It is easy to see how compacting + cleaning algorithms can be devised that recover space and recluster the segments to optimise read performance.
• Cleaning eliminates fragmentation.
• The persistent store has been decoupled from concurrency, simplifying the design. Rather than all of ACID, it only promises atomicity.

Ceda uses a persistent history buffer to represent all changes to persistent objects – even individual character insertions and deletions in a text document, or resizing of a slider control. This reflects the capability for synchronous editing. Therefore, good write performance is important. A log structured store seems ideal for this purpose.

Overview

A Log-Structured Store (LSS) unifies the object database with the log. ie objects are written to the log, not to a separate area.

As new versions of objects are written to the end of the log, previous versions are rendered obsolete. Therefore the log requires periodic garbage collection (called cleaning). This occurs in parallel with the normal operation of the store.

The log is stored as a linked list of segments. A segment is fairly large to reduce the impact of disk seek operations. Over time, more and more objects within a previously written segment become obsolete. Cleaning involves the relocation of live objects, providing an opportunity to re-cluster objects. It also facilitates application level garbage collection.

The LSS is a persistent heap, and only manages opaque blobs of binary data. These are called serial elements. A layer above the LSS called the Persistent Object Store (POS) associates a serial element with the serialised state of a persistent object. There is no size limit on a serial element. A serial element is identified by a 64 bit Object Identifier (OID). This is assigned when the serial element is first created, and kept for life.

Internally the LSS breaks up large serial elements into smaller pieces called packets. Clients of the store are insulated from this implementation detail.

A client of the LSS reads or writes a serial element as a stream of bytes (through the IFile interface). Neither the LSS nor clients of the LSS need to store a serial element as a single contiguous block in main memory.

Object Identifiers (OIDs)

An OID is a 64 bit number that uniquely identifies a packet or serial element on a given LSS. It is composed from two 32 bit values called OIDhigh and OIDlow.

Note that an OID doesn’t point directly at a serial element in the log. An OID is assigned to a serial element forever, even though the serial element may be written to the end of the log many times. The OID is like a handle and the Recoverable Packet Map (RPM) maps the OID to the current position of the serial element in the log, providing the extra level of indirection to allow the serial element to move around and yet still be found using the same OID.

No steal policy

A steal policy is where dirty objects or pages are written to a data store even though they have not been committed yet. This could be important for long running transactions that modify many objects, or for page based systems where a page always contains uncommitted updates due to fine-granularity locking and overlapping transactions’ updates to that page. 

However, it is assumed that in Ceda transactions are short lived, and will only modify a small number of objects. Therefore we assume a no-steal policy, so objects will only be written to disk when a transaction commits. This implies that no undo work is required on recovery.

External interface provided by the LSS

The ILSS interface contains the following functions

All changes (ie mutative work) done on an LSS must be done by a thread that has opened a commit phase. A commit phase is intended for a single thread. Only the thread that called CreateCommitPhase() on the LSS is permitted to call the functions in this interface, or delete the commit phase. A commit phase must be deleted after it has been used.

The Persistent Object Store (POS)

The Persistent Object Store (POS) is the client of the LSS. The implementation of the POS is described in detail later in this documentation. To help understand the LSS it is useful to have an overview of the POS.

The LSS is responsible for managing persistent serial elements, keyed by OID. The POS is responsible for managing the deserialised form of those serial elements - ie the IPersistable objects in memory. For this purpose the POS makes use of the following data structures

• A Resident Object Table (ROT) which is a map from OID to pointer location in memory, to keep track of the set of the IPersistable objects that are reachable from the persistent store root and are currently resident in memory
• A Dirty Object Set (DOS) which keeps track of the persistent objects that have been marked as dirty and need to be written back to the LSS.

The POS assumes that IPersistable objects use pref<T> smart pointers to reference other persistable objects. A pref<T> stores an OID and this is used to “fault in” persistable objects on demand (ie when the pref<T> is first dereferenced). The POS first tests whether the object is already in memory by looking up the OID in the ROT. If not then the POS makes a request for the serial element in the LSS with the given OID, allowing the IPersistable object to be created and deserialised.

It is assumed that all access to persistable objects is done in the scope of a CedaLock. Therefore there can be at most one thread that makes a read request on the LSS at a given time.

The DOS isn’t processed at the end of every CedaLock transaction. Rather, changes to the C++ objects in memory are allowed to “accumulate”. This is very important for performance. For example, when a user makes hundreds of independent changes to an image (say over a period of 2 seconds) it is likely that the image is only marked as dirty and added to the DOS once. When the DOS is eventually processed, only the final rendition of the image will be written to disk.

A worker thread is responsible for processing the DOS. It is coded as follows

class DirtyObjectSetWriter

{

void DirtyObjectSetWriter::SignalWriteDirtyObjectSet()

{

m_wakeThread.Signal();

}

void WorkerThreadFn()

{

const int PROCESS_DIRTY_OBJECT_SET_TIMEOUT_MSEC = 2000;

while(!m_requestShutDown)

{

m_wakeThread.Wait(PROCESS_DIRTY_OBJECT_SET_TIMEOUT_MSEC);

if (m_requestShutDown) return;

// Get a CedaLock, in order to be able to serialise the objects in the DirtyObjectSet

CedaLock lock(m_abortThread);

if (m_requestShutDown) return;

ASSERT(lock);

m_ps.WriteDirtyObjectsToLSS();

lock.Commit();

}

}

}

This ensures that when objects are added to the DOS, at most 2 seconds will elapse before a worker thread processes (or at least tries to process) the DOS - ie writes all the dirty objects to the LSS and clears the DOS. Note that the DOS is processed in the scope of a CedaLock to ensure that no other thread is able to make changes to the persistent objects that are being serialised to the LSS. Therefore at most one thread has read or write access to the LSS at a given time.

When the DOS is processed, we say that a commit phase is performed on the LSS. This involves the following steps

1. ILSS::CreateCommitPhase() is called to obtain an ILSSCommitPhase interface pointer.
2. ILSSCommitPhase::Write() is called for all the dirty objects
3. ILSSCommitPhase::Delete() is called for all the objects to be permanently deleted
4. The ILSSCommitPhase is deleted.

The LSS uses a large segment cache, so often a commit phase will be able to write all its data to the LSS without blocking on I/O. It is important to note that a commit phase doesn’t flush the log. A separate function ILSS::Flush() is provided for that purpose, but performance is degraded if it is called unnecessarily.

By parenthesising the changes made by a CedaLock transaction, the LSS is able to ensure atomicity, in case the system crashes part way through writing data. On recovery the LSS starts in a state where no transaction has only been partially applied.

Note that a transaction doesn’t enter its commit phase unless all fallible work has been completed. The commit phase is meant to be infallible – in the sense that it can only fail due to a hardware or power failure. For that reason there is never a need to explicitly abort the commit phase in software.

Durability

TODO for doco

• Provide a simple diagram that compares central server versus peer-peer with data replication. State the basic differences
• Explain that data replication and operational transform immediately leads to the idea that data is for only one process - dramatically easing the need for concurrency control using pessimistic locking.

Assumptions on the hard-disk

The LSS implementation goes to a number of lengths to avoid certain assumptions about the hard-disk. Many data bases assume one or more of the following

• Disk sectors (typically 512 bytes) are written atomically
• Clusters (often 4k or 8k) are written atomically
• Data is written to the platter in the same order that the write commands are issued in software
• When a file is created with the FILE_FLAG_WRITE_THROUGH option, WriteFile() doesn’t return until the data has gone to non-volatile storage.

Ceda avoids making these assumptions.

OID allocations

As a transaction runs, new objects may become reachable and therefore need to be assigned an OID. This happens when container objects are marked as dirty. The POS needs to assign OIDs to the objects that become reachable for the first time. Therefore it is necessary to support OID allocation in ILSS rather than ILSSCommitPhase. An insignificant downside is that when a transaction aborts we have some wasted OIDs.

Assumed access pattern for reading serial elements

When the Object Store reads a serial element, the stream of bytes is deserialised into a C++ object (and typically won’t be contiguous in memory). A Resident Object Table (ROT) keeps track of objects that are resident in memory, so there will rarely be a need to read the same serial element twice.

Note that the LSS typically reads a large number of serial elements at a time – because of the coarse granularity of segments. The LSS assumes that locality within a segment is good and therefore it buffers segments that have been read from disk.

Localisation

When objects are written to disk at around the same time, it is likely that they will be written to the same segment. Therefore the LSS tends to localise objects in a segment according to localisation of mutative changes in time. Objects that were previously together will be drawn apart if one object is modified but not the other.

When a user creates large sub-trees of objects in short periods of time there will be good localisation. If a user tends to make changes all over the place there will be poor localisation.

Cleaning techniques that improve localisation are discussed in the chapter on contexts.

State variables in memory to manage the LSS

The following variables are defined in main memory to manage the LSS.

Efficient serialisation of the entire LSS

It is possible to serialise the entire LSS to a single stream that is suitable for transmission between computers without the overhead of meta-data like the SUT and the RPM. This simply involves serialising all serial elements. Each serial element is serialised by writing the following

• The OID assigned to the serial element
• The size of the serial element
• The serial data of the serial element

The order in which they are sent doesn’t matter apart from maintaining locality. 

De-serialisation at the destination involves starting with an empty store and writing the serial elements to segments (breaking them up into packets) and recreating the SUT and RPM at the destination. This can be achieved using one big transaction followed by a check point.

Better performance is gained if the stream is also passed through a compression algorithm.

Excellent transaction throughput

We call information in the SUT and RPM meta-data to distinguish it from the “real” data stored in the serial elements.

Meta-data is redundant and this allows the LSS to only write meta-data during check points, and yet still recover information written to the log after the last check point. By performing fewer check points, the overhead of writing the meta-data can be reduced so that efficiency of the LSS is very high – because most of the time it is writing real data. Furthermore, data is always written to a growing log without delays from disk head seeking. This allows the LSS to support a very high transaction throughput.

Daisy chaining of segments

A check point involves writing data to the log to reduce the time taken for a recovery. A recovery involves a scan through the log records in sequence starting from the last valid check point until reaching the end of the log. There is never a need to scan log records in sequence before the last valid check point. Therefore, only the segments on or after the last check point need to be daisy chained. These segments are never freed by the cleaner (because the cleaner is only allowed to work on segments before the last check point).

We regard the segments after the last check point as forming a log in the normal sense, whereas the segments before the last check point are no longer ordered, and behave more like a read only random access data store. This simplifies the cleaner because it doesn’t need to worry about a linked list as it frees segments.

Segments are only ever added at the tail of the log.

Concurrency notes

Between check points, only free segments can be written to. Therefore we can regard segments as supporting shared read access. As such there is no need to lock segments (say to limit concurrency between a CedaLock thread and the cleaner). However we need to be careful between the cleaner and the check pointer. Perhaps the same thread should be used for both. It seems nice for the LSS to hide both of these concepts. This makes the ILSS interface small and simple.

Log Record Set (LRS)

A Log Record Set (LRS) is a set of log records that are written to the log as a unit during an LRS-op. An LRS consists of zero or more packet records followed by a snap shot record.

There are three types of LRS-op

• When the POS commits a transaction
• When one or more segments are cleaned
• When dirty RPM-sections are written to the log, prior to a check point

In all cases, an exclusive write lock is gained on the SegmentWriter, so that the LRS can be written without overlapping with another LRS.

Concurrency issues

An LRS-op gets an exclusive lock on the SegmentWriter for the life of the operation. Therefore it is not possible for these operations to overlap. 

The SUT and RPM are only modified by LRS-ops. Therefore an LRS-op can’t see intermediate states of the SUT or RPM. In particular, a check point will see a consistent SUT and RPM without locking them for an extended period. This ensures that a check point writes a coherent and up to date version of the SUT and RPM to the root block and log. Also, the cleaner will get a coherent and up to date picture of what packets are live and obsolete as it cleans a segment.

The root block and the SUT are only read or written by LRS-ops, so therefore there is no need to protect them with mutexes.

The RPM is only written by LRS-ops, but it can be interrogated outside of an LRS-op. Therefore, it uses a mutex in order to be thread-safe. Locks on the RPM are only granted for short periods.

Packets

Support for large serial elements using packet chains

The LSS supports arbitrarily large serial elements. Large serial elements are split into smaller variable size pieces called packets. A packet is written as a packet log record to a segment. A packet can’t overflow a segment.

The packets of a given serial element are daisy chained. Each packet is assigned its own OID. A packet stores the OID of the next packet in the chain, or a null OID to indicate the tail packet. No! There is a bit in the first byte of a packet log record that indicates whether there is a next packet in the chain.

The OID of a serial element matches the OID of the head packet in the chain for that serial element.

The RPM and the cleaner work at the level of packets without any regard for how they daisy chain into serial elements.

OID management

Detecting dangling references

OIDs are never reused. ie if a serial element is destroyed then its OID may never be assigned to another serial element. This allows the LSS to reliably identify dangling references to persistent objects.

Allocating OIDs to new objects

A client that is assigned a value of OIDhigh can efficiently allocate OIDs in its private address space by simply incrementing OIDlow for each serial element that is created. The RPM stores the next available OIDlow for each value of OIDhigh 

Snapshots

The LSS moves atomically from one valid snapshot to the next. This is achieved by writing snapshot records to the log. Packet records are only committed when the subsequent snapshot record is found. If no snapshot record is found on crash recovery, the log is truncated.

A transaction gains exclusive access to the log in its commit phase

Given the no-steal policy, we may as well assume that each transaction gains exclusive access to the log in its commit phase so it can write all of its modified objects, and the commit record in one go without interleaving log records with other transactions or a check point. With sufficient write caching, a transaction will be able to quickly write data to the cache and return, and avoid being blocked by I/O. There doesn’t seem to be any benefit in having multiple transactions all writing to the log at the same time.

Advantages

• There is less risk of data loss, because a transaction is given the freedom to write all its data in consecutive log records. As an extreme example, if lots of transactions write their data in parallel and a crash occurs, it is likely that none will have succeeded in writing all the changes to the log.
• We avoid mixing the data of unrelated transactions, giving us better data localisation – which will improve read performance.
• It simplifies crash recovery. It can be assumed that log records written by a transaction never span a check point, so there is no need to scan log records before the last valid check point during recovery.

Performing a commit phase

When a transaction of the POS enters the commit phase, there is every intention of writing the snapshot record. In fact only hardware or power failure can prevent this from happening. Therefore the in-memory RPM and SUT can be updated as packets are written by the SW to the SC.

The commit phase involves the following steps

1. Get an exclusive lock on the log
2. Initialise a temporary vector X of OIDs to empty, used to keep track of the set of packets to be deleted
3. For each serial element to be written (with given OID)
   1. Use the SC to find the current chain C_prev of packets used by the serial element (if any). For each packet in C_prev
      1. Add the OID to X
      2. Subtract the size of the packet from the SUT utilisation for the segment containing the packet

• Remove the entry for the packet from the RPM.

1. Write a chain C_new of packets to the log. For each packet in C_new.
   1. Add the size of the packet to the SUT utilisation for the segment containing the packet
   2. Add an entry to the RPM
2. For each serial element to be deleted (with given OID)
   1. Use the SC to find the current chain C_prev of packets used by the serial element (if any). For each packet in C_prev
      1. Add the OID to X
      2. Subtract the size of the packet from the SUT utilisation for the segment containing the packet

• Remove the entry for the packet from the RPM

5. Write a snapshot log record. This record contains the list X of OIDs of packets to be permanently deleted as part of the snapshot.
6. Release lock on the log

Note that the log is not flushed.

Supporting overflow of the root block

Given the idea of the FSS, we can “pinch” some segments for the purpose of supporting overflow of the root block. It is important to write and flush the free segments first, then write the root block. In general we must always write the root block last of all because this is what takes us atomically from one check point to the next.

Implementation notes

The entire functionality of the LSS is implemented in the folder Ceda/Sys/LSS.

Currently we don’t support recovery scanning of the log. Instead, recovery simply involves going back to the last valid check point.

We cater for Challis algorithm in a generic way, so we get code reuse for the root block and the segment trailer.

A lower layer (RAS) represents the underlying file, and the ability to read and write parts of it. This abstraction is useful because it could be replaced by a raw disk partition. It supports a 64 bit address space to allow for more than 2Gig of data.

The next layer breaks this address space up into the two root blocks and the segments. The ability to add new segments will be provided. Read/write functions to the root block and to a given segment will be provided. Also the ability to allocate new segments by growing the underlying file.

A class to encapsulate the SUT has been written. This is implemented as a vector of records. The SUT expands when extra segments are added to the file. Note that the system allows for the SUT and the size of the file to be out of sync – typically the file could have grown then the system crashed before the SUT has grown and been written to a valid check point. Growing of the file is not logged.

The class LSS encapsulates all functionality.

IDEA: Atomic append using checksums

Rather than store a size field in the segment trailer, and need to rewrite the segment trailer every time data is flushed to the log, consider that a flush log record is always written to the log after each flush operation. When scanning the log on recovery, we only trust data that is bounded by a valid flush log record. A flush log record can’t simply store some fixed “magic” values, because segments that are reused already contain previously written flush log records and so there is a risk that data will be trusted by mistake. A flush log record can contain a sequence number and/or checksum over the data in the segment. Note that this approach requires that the recovery scan be resilient to corrupt log records.