40 DeletionQueue

The DeletionQueue is concerned with permanently deleting persistent objects in a given PSpace.

Asynchronous deletion of huge trees

Deleting an object requires deletion of all its descendents. This could represent many Gigabytes of data. Therefore it should be performed asynchronously. Furthermore it would be preferable to not require exclusive write access, except for making the changes to the (objects) that previously referenced the object(s) to be deleted.

Each PSpace stores a persistent DeletionQueue (DQ) of OIDs for objects registered for asynchronous deletion.

A transaction with exclusive write access to the PSpace that creates orphans commits an instruction to delete whole sub-trees of objects (by pushing orphans onto a transient delta-DQ which is later added to the persistent DQ). This allows the transaction to run very quickly because it doesn't actually delete the objects. The orphan subtrees are removed asynchronously in the background.

An incremental deletion involves popping an OID from the DQ, loading the object from disk (if not memory resident), then pushing all its children back onto the DQ. This is repeated for a time slice then the accumulated changes are quickly written to the LSS using a single LSS transaction.

The DosWriter thread takes on the responsibility to delete objects in the store asynchronously.

Thread-safety of the DQ

The DQ, delta-DQ and the oss_objflags member within each persistable object may only be accessed by a thread with an exclusive write lock on the CSpace, or else the DOS Writer thread, after getting a shared read lock on the CSpace.

Note therefore that access requires a lock on the CSpace. Furthermore the only thread with just a shared read lock that gains access is the DosWriter thread. This implies that only a single thread gains access at a time.

The delta-DQ

Consider a thread with an exclusive write lock on the PSpace that makes changes causing orphaned sub-trees. If we put the OID of an orphan directly into the DQ then we risk the asynchronous processing of the DQ causing the orphan to be deleted on disk before we have committed to the changes that caused it to be orphaned in the first place. That could be disasterous.

We need to delay deletion of an OID until the associated PSpace has first had its DOS processed.

That will guarantee that

• No object is written to disk after the associated serial element has been deleted from the LSS [that would represent a persistent memory leak]
• We commit to deleting an orphan at the same time that we commit to the changes that caused it to become orphaned.

Let each PSpace have its own independent, persistent DQ. Let a transient delta-DQ be stored in each PSpace and represents a delta to be applied to the DQ.

A thread with an exclusive write lock on the PSpace can make changes that orphans one or more objects in the PSpace. As part of the transaction it registers the orphaned objects in the PSpace delta-DQ.

Consider that the DosWriter gets a shared read lock on the PSpace then processes the DOS. At this time there can't be any thread with an exclusive lock on the PSpace. Therefore no thread is adding entries to the delta-DQ. After processing the DOS, but still within the scope of the shared read lock the contents of the delta-DQ are transferred to the DQ, and the delta-DQ is emptied. If the DQ is dirty then it is also written to the LSS as part of the same LSS transaction.

Trying to optimise by not writing objects that are to be deleted

It could be imagined that a useful optimisation is to avoid writing objects that were marked as dirty (and have been added to the DOS) but have subsequently been marked for permanent deletion.

However, there are some subtle problems with such an approach. For example, consider that changes are made to the PSpace by a mutative thread, and later when we process the DOS we avoid writing objects that are deemed to have been deleted. A problem is that the asynchronous deletion process requires that the *latest* (i.e. most up to date) rendition of objects be traced in order to correctly delete sub-trees. Therefore it could easily be a problem if dirty objects are not rewritten.

Comparison to a more layered design

A more layered design would be to only support synchronous, manual deletion of serial elements in the PersistStore layer. A higher level layer adds support for the deletion queue - adding a PSpace root named something like "SystemDeletionQueue". We can imagine that some PSpaces don't even need an asynchronous deletion queue.

This approach is quite reasonable, except there are some penalties

• The current design allows for deletion to be done with only a shared read lock. The more layered approach would require an exclusive write lock.
• The framework is able to use a bit in the oss_objflags member to properly perform tracing in order to delete graphs of objects.

Persisting the DQ

For each PSpace the DQ persists in its own serial element. A more sophisticated implementation could use daisy chained pages to allow the queue to grow very large efficiently.

It should be possible to use the ROT and prefs for the DQ! The DQ can even be marked as dirty and added to the DOS! So when the DOS is processed, the new DQ is written if dirty as required.

The PSpace can store a pref to the DQ. This persists in the same serial element that stores the PSpace roots.

The DQ is loaded on demand and may be evicted like any other persistent object.

Dealing with back pointers

Nodes of the tree are allowed to store "back pointers" to their parent nodes. This can cause problems for asynchronous deletion of trees. The issue is that a child can be processed after the parent has been deleted from the LSS. Therefore it is important to ignore the back pointer in the child.

One approach could be to provide a means to zero back pointers. However this is far from ideal because during the deletion objects would be marked as dirty and therefore rewritten to the LSS.

Our solution is to provide a separate function on the IPrefVisitor to visit the back pointers.

DeletionQueue.h

Source: Ceda/cxPersistStore/src/DeletionQueue.h

DeletionQueue.cpp

Source: Ceda/cxPersistStore/src/DeletionQueue.cpp