39 DosWriter
Uses a worker thread that wakes up every 10 seconds in order to serialise all dirty objects (i.e. objects in the Dirty Object Set) to the end of the LSS.
It is not a good idea to process the Dirty Object Set every time a CSpace lock is released because the
user may be doing something like dragging an item around on a board, and so the board is marked
as dirty at around 50 times per second. Writing an object to disk this often will lead to
thousands of obsolete versions in the LSS - a significant source of inefficiency. By only
processing the Dirty Object Set every 10 seconds we avoid a proliferation of obsolete versions of
objects, without risking excessive data loss if there is a system failure like loss of power.
Note that the log is not flushed after writing the objects. When the system is I/O bound (i.e. its throughput is limited by the lazy writer of the LSS), it is not a good idea to flush the log because writing partially full segments will only impede the lazy writer.
Writing dirty objects
For a given PersistStore a single thread is responsible for writing all dirty objects to the LSS. There is no point in using more threads because LSS transactions are serialised anyway.
Therefore this thread is hosted by the PersistStore, not a PSpace.
Cloning persistent objects
If the framework is aware of the difference between strong and weak references then it should be able to clone a tree of objects, and wire up the redundant back pointers etc correctly as well. It would be nice if huge (gigabyte) trees of objects can be asynchronously cloned.
We would like the GUI to be fast and responsive. Eg can copy and paste 1GB from one location to another. Note that a copy-on-write approach may solve this problem rather elegantly.
PROBLEM: How do we avoid needing a single very long shared read lock in order to reliably clone the tree? Clearly we can't, even if we work out how the GC can evict nodes correctly.
Note that users are aware that when they copy huge directories of files, they shouldn't try to modify any files at the same time. Nevertheless they still do it sometimes. So it really is a valid use case.
Perhaps we can get the best of both worlds by making use of the history buffer. This could be used to undo changes that have been occuring to the objects as they are being copied. This is complex but clearly quite useful.
Note that the repository offers a very elegant solution for asynchronously cloning huge trees of objects, because a repository is able to provide versions of objects for a given vector time, despite continued check-ins into the repository. This suggests that maybe we shouldn't be too worried about providing an asynchronous clone function for working set objects. I.e. it is ok to hold an extended shared read lock because most data will reside in a repository on a given HDD and working sets won't be too large.
In a working set, to copy a very large tree it is necessary to get a prolonged shared read lock. To allow for eviction we will need a concept of cooperative shared readers that call a function that allows the GC thread to safely complete the trace without getting an exclusive lock.
The shared reader making a copy should use an anonymnous PSpace to store the result of the copy.
This is only transferred to the destination PSpace later using a short lived exclusive lock.
Solution 1
This assumes that back pointers only exist up to the immediate parent. This is suitable for document trees.
Let x,y be given where x is the parent of tree y to be cloned. The task is to clone y to y' and make y' the child of x.
We use an OID to OID map to provide OID translation as we visit prefs. The entry x --> x' is added to the map. We have a stack of objects to copy. y is pushed.
Given: x --> y, x' --> ???, newOid to be applied to new y (called y').
void AsyncClone(x,x',y,newOid)
{
stack2.push(x,x',y,newOid);
while(!stack2.empty());
{
(x,x',y,newOid) = stack2.Pop();
map<OID,OID> map;
map[x->oid] = x'->oid;
map[y->oid] = newOid;
stack.push(y, newOid);
while(!stack.empty())
{
(p,oid) = stack.Pop();
assert( map[p.oid] = oid );
// Make a shallow copy p'. Note that p,p' will have same OID values for all pref members.
{
serialise p to a PagedBuffer.
Create p' of same type as p.
Deserialise PagedBuffer into p'.
Make p' persist with 'oid'.
}
for each pref member m in p'
{
if (m)
{
if (map.find(m.oid))
{
// Use the map for OID translation
m.oid = map[m.oid];
}
else
{
// Eagerly allocate oids and add map entry, to make sure we don't create two
// objects for the same oid.
IPersistable* q = *m;
assert(q);
newOid = allocate oid, affilated with 'oid' (i.e. oid assigned to p')
map[m.oid] = newOid;
m.oid = newOid;
if (q->IsTreeNode()) stack2.push(p,p',q,newOid);
else stack.push(q,newOid);
}
}
}
}
}
}More analysis
It would appear that solution 1 is too restrictive in its assumptions about the weak pointers.
For example, consider a PDeque containing a double linked list of pages, with pointers to the first and last pages.
PDeque
/ \
---<----/ \--->---
/ \
(first) / \ (last)
/ \
Page -->-- Page ... -->-- Page
--<-- --<--
We can think of this structure as forming a tree as follows
- the first page is regarded as an immediate child of the PDeque.
- each successor page is regarded as a child of its predecessor
PDeque
\
Page (first page)
\
...
\
Page (last page)
The 'prev' ptr in each Page looks like a back pointer to its parent. However the PDeque's pointer to the last page breaks the assumptions made by solution 1. It is a "downwards" weak pointer (meaning that it points at a descendent).
Evidently when cloning the PDeque it will be necessary to fill in the pointer to the last page later.
A more complex example is a B+Tree
B+Tree
/ | \
/ | \
/ Node \
/ / | \ \
/ ... \
/ Node \
/ / | \ \
/ ... \
/ \
Page -->-- Page ... -->-- Page
--<-- --<--
Let's assume that the tree structure (i.e. strong pointers) is dictated by the internal nodes. Then the weak pointers are
- ptrs to the first and last page in the B+Tree. These are "downwards" weak pointers
- ptrs to the prev and next page in each page. These are "sideways" weak pointers.
Alternatively if we structure the tree using the linked list of pages then the ptrs in the internal nodes at height 1 represent "sideways" weak pointers.
The conclusion is that we can't avoid "sideways" weak pointers.
Solution 2
We use an OID-OID map to keep track of the relationship between the source and destination trees. Where possible, weak pointers are set correctly when we first copy an object (by looking up the map). This will cause all back pointers, half the side pointers but none of the down pointers to be fixed as we go. We will need to record at set of unresolved weak pointers and come back to them later - possibly before actually completing the copy of the entire tree!
Note that within a single node of the tree there can be a local graph of "GraphElement" objects known to be isolated from the rest of the world. This can be copied with its own independent OID-OID map.
Consider that an object can be asked what type it is, and the following types are supported
1. World
Used at a course granularity where the only valid form of weak pointer is a back pointer
from child to parent. Note that the document tree is composed from "world" objects.
2. Master
A node that has a tree of slave nodes that contain arbitrary weak pointers amongst
themselves (and the master).
Used for a B+Tree object.
3. Slave
Subordinate to a master. Used for the nodes of a B+Tree.
4. GraphElement
Any of the above three can host a private graph of subordinate objects that are reconnected
in isomorphic fashion when the graph is shallow cloned.
It is assumed that the entire graph can fit in memory.
The recursive clone function can introduce separate OID-OID maps at each master node during the depth first cloning. These OID maps are reclaimed as the stack unwinds, reducing the storage space requirements of the algorithm.
Solution 3 [preferred]
We simplify the framework at the expense of complicating the interface to the application programmer. The justification is increased performance and greater overall simplicity.
Each IPersistable can indicate whether it is a Master/Slave/GraphElement. Private graphs of a node of the tree are copied using a short lived OID-OID map as described above.
However no OID-OID maps are used to fix weak pointers between nodes of the tree. Instead each tree node has the following method called just after it is cloned
void FixWeakPtrs(xdeque<ptr<IPersistable> >& path, int masterIndex);The deque of IPersistables represent the path taken during the recursive clone function. This is pushed and popped during the cloning.
The masterIndex provides the index position within the deque of the nearest Master ancestor.
It is assumed that this allows the given object to set weak pointers as required.
The B+Tree will fix weak pointers as follows: When FixWeakPtrs() is called on a leaf page the following is done:-
void BTreeLeaf::FixWeakPtrs(xdeque<ptr<IPersistable> >& path, int masterIndex)
{
master = path[masterIndex];
if (master->first == NULL)
{
// This leaf must be the first page
master->first = this;
}
// When the clone has finished this will equal the last visited leaf page.
master->last = this;
p = < use parents to navigate up then down as required to find prev leaf page >
this->prev = p;
p->next = this;
}todo
DosWriter uses an IoContextPool rather than its own std::thread.
DosWriter.h
Source: Ceda/cxPersistStore/src/DosWriter.h
DosWriter.cpp
Source: Ceda/cxPersistStore/src/DosWriter.cpp