54 Initial state

Sending the initial state of an object

A delta (sent between a pair of sites) records the initial state of objects that need to be created.

It is assumed that all the persistent state of a datasource is defined by its reflected data model members. i.e. there is no additional persistent state that needs to be sent in a delta.

For a given datasource, we send initial states of the fields in an order derived from the schema, and associated with a recursive descent algorithm through the fields. The initial state is written to an archive, which is assumed to be associated with IPC to another site.

It is assumed that the receiving site will use the same schema to deserialise the initial state of the datasource.

This approach avoids the need to send paths to identify fields. Also, values of fields are sent with an implicit format - i.e. without type information. For example, the initial state of an int16 field only involves writing two bytes to the archive. This makes the transmission of the initial state of objects very space efficient.

We avoid the need to use explicit auxilliary data structures to record the initial states of objects, because we work directly with the objects themselves by making use of the reflection information.

Sending OidHigh OidSpaceGuid pairs

The sender doesn't need to translate OIDs as they're sent. (i.e. the need to translate OIDs is imposed on the receiver). However the sender needs to first send OidHigh/OidSpaceGuid pairs. Unfortunately it means it needs to know what OIDs are to be sent in a delta before sending the delta, because the OidHigh/OidSpaceGuid pairs are sent in a separate stub/scion message.

There are various approaches. E.g.

  • Write a special function to first calculate the set of oidHighs to be sent
  • First write to a null archive, allowing the writer barrier for writing oidHighs to be called.
  • Write to a buffer in memory before writing to the IPC channel. The write barrier allows for recording the OIDs to be sent. We then invoke the stub message to send the relevant OidHigh/OidSpaceGuid pairs, then we can simply send the buffer in a separate stub message.

Initial state of fields

Note that OIDs are allocated eagerly, so there is never a need to allocate OIDs at the time of sending a delta.

  • For small assignable fields it is reasonable to send the current value of the field even if there has been a reassignment to the field (so the new value is being sent separately with a vdom anyway).
  • For large assignable fields it may be appropriate to use a marker to avoid needing to send the initial state, when reassignment has occurred. This can be determined by testing whether there is an entry in the LocVdomMap for that FieldId.
  • the initial state of a vector field is deduced by comparing the current state with the recorded insertion operations. Any gaps correspond to the initial state! So we can *calculate* this initial state at the time we send the operation. This only requires a left to right scan through the insertion intervals so it is very efficient.
  • The initial state of a set field is assumed to consist only of the oids which have not yet undergone reassignments to their location. i.e. the oids for which no vdom has yet been defined. Note that for oids that have been reassigned to the set field, we will send information about the reassignment in the delta in the normal way. In that sense, the oid is not regarded as part of the initial value of the set field.
  • the initial state of a vector field is recorded using
    • int32 n : The number of elements to insert into q-space
    • set<q,oid> : The oids to insert as a function of q-position, where q in [0,n) These oids are the oids that currently appear in the field as a function of q-position, and also have no Vdom entry, so these oids have never been reassigned from this their original location.
  • similarly we should be able to work out the initial state of set fields, delta field, bag fields etc.

When a delta is received

The receiver should only create objects for (s,t) that it doesn't already have. It should be found that

  • no object with the given OID already exists in the LSS
  • no VDom is defined for the OID
  • no location is recorded for the given OID

Basically the initial state is used to initialise the value of a new object. This includes the initialisation of fields of type set and vector. However in these cases it is also necessary to set the location of each oid in the oid location map. There is no need to try to remove the object from an existing location (because it won't exist). Also there is no need to insert an entry into the Vdom map. That must wait until the oid location is reassigned from its initial location.

Non-models

OIDs of non-models are recorded separately. Their initial state is simply sent as serialised state.

Optimisation : Absorbing operations into the initial values

An interesting idea for optimisation is whether we can avoid recording operations on an object that hasn't yet been sent over the wire to another site. In that case it should be possible to accumulate further changes as though they were part of its initial state. This even includes operations on vectors.

This optimisation obviously has enormous ramification for a site that has not connected to any other site - it basically means that no operations will be recorded against new objects at all. The potential efficiency gain is enormous in that case.

To implement this optimisation we need to be able to efficiently determine whether a given object is known to be local, meaning that it cannot be present on another site. It is assumed that all objects that existed in the state corresponding to the base vector time are regarded as not local because they are available in the repository. i.e. local objects are objects that have been allocated after the base vector time, and have never been sent in a session. This information needs to persist. Furthermore the database transaction that marks an object as not local should be made durable before the object is sent in a session.

Approach 1
class WorkingSet
{
    // Returns true if the object with the given oid is only local - i.e. it cannot be present
    // on another site
    bool OidIsLocal(oid) const
    {
        return m_localOids.find(oid);
    }

    void OnCreateObject(oid)
    {
        m_localOids.insert(oid);
    }

    void OnSendObjectInASession(oid)
    {
        m_localOids.erase(oid);
    }

    void OnSetNewBaseVectorTime()
    {
        m_localOids.clear();
    }

    // A working set persists a set of OIDs for the objects that have been created since
    // the base vector time and have not been sent to another site.  These objects are called
    // local because they cannot be present on another site.
    // This set will typically be fairly small during a normal interactive session. However
    // it would be very large if there have never been any sessions.
    set<OID> m_localOids;
};
Approach 2

The working set already persists the OIDs that have been allocated to new objects since the base vector time, as a function of (s,t). Consider that the working set also persists a vector time 'vsent' that represents the union over all operations (s,t) that have ever been sent or received. This is initialised to the base vector time. It is possible to determine whether a given OID has been sent. Unfortunately this is expensive without an efficient mapping from OID to the (s,t) of its original creation. 

class WorkingSet
{

    // For each SiteId records a vector of (t,oid) ordered by t for objects that have been
    // created since the base vector time
    std::map<SiteId, xvector<t_oid> > m_createdOidsMap;

    // The working set persists a vector time vsent that represents the union over all
    // operations (s,t) that have ever been sent or received.  This is initialised to the
    // base vector time
    VectorTime m_vsent;
};

For efficiency we choose approach 1

IDEA: We can increase efficiency in an amortised sense by caching look ups within transient state within an object. We have a whole lot of bits in each IObject! We only need two bits for 3 states: 

enum
{
    UNKNOWN,        // means have to find out whether local or no local
    LOCAL,          // last time we looked was found to be local
    NOT_LOCAL       // last time we looked was found to not be local
};

When an object is sent, it is necessary to change the status from LOCAL to NOT_LOCAL.

Ramification of optimisation for fields of type vector<pref>

Consider that an object is created after the base vector time, and it contains a field of type vector. The field is initialised with prefs that point at either

  1. new objects
  2. objects that already existed in the UT before the base vector time.

At present, the prepare prefs code will either

  1. allocate an oid
    update oid location map
  2. remove oid from old locations
    update vdom
    update oid location map

Note that no interval is recorded to represent an insertion - even for oids that already exist in the UT.

Consider that we generate intervals for the oids that were moved from other parts of the UT. Then the problem is that all subsequent insertions into the interval are going to need to cause intervals to be shifted. The result is that we end up recording changes after all. This ruins the main idea of the optimisation.

The conclusion is that we won't create insertion intervals until operation recording is activated for the object. It follows that we need the initial state to cater for the case that it acts like a reassignment of oids!

More on optimisation for vector fields

It may be useful to for an empty list of intervals in the PtoQ map to signify the condition that there is no distinction between p and q coords. This is a very common case, and this would avoid the heap allocation and reduce the overhead on disk as well. Currently the PtoQMap records a single interval, with dp = dq = n where n is the current size of the field. The number of tombstones is dq-dp = 0 as required.

Until such time as operation recording is enabled, there is no need to create a distinction between p and q coordsinates. In particular delete or move operations could avoid the creation of tombstones!

Efficient use of paths

We want a path to be able to grow and shrink efficiently in the manner of a stack during the recurse. It is a good idea to allocate a reasonable size for the path up front to avoid repeated heap allocations.

A mutable FieldId must be passed in order for the path to be modified! However by design each function reinstate the previous value of the path.

To grow and shrink a path, it would be convenient to pass an archive? That way bytes written to the archive can be forwarded onto the path?

Alternatively: 

ssize_t n = path.Append_ssize_t(x);
< use new path >
path.EraseTail(n);

Sending initial state of a vector field

Consider that we are sending the initial state of an xvector<T> field within an object that was created after the base vector time.

Most generally the xvector<T> field

  • has state that was prepared in a model constructor (say) and wasn't recorded as an insertion operation. Let this be called "prehistoric state".
  • has had insertions and deletions recorded, and deletions may have deleted elements of the prehistoric state. It follows that it is not generally possible to calculate the prehistoric state.

Over time this object may need to be sent to numerous peers. One approach could be to treat the prehistoric state as the initial state of the xvector<T> field to be sent to a site whenever the initial state of the object is sent to a peer. Unfortunately it is not possible in general to calculate the prehistoric state - because it may have been deleted by subsequent deletion operations.

In any case it seems silly for a site to calculate an earlier state and then have the receiving state have to apply the insertions/deletions to that state in order to recreate the current state of the field already on the sender. Why not simply send the current state of the field and be done with it?

So the approach is to simply send:

  • the current value of the field
  • the recored insertions
  • the recorded deletions

(i.e. everything that we've got - and assume the receiver simply initialises the corresponding variables with these values).

This approach has the advantage of

  1. Simplicity
  2. Optimal CPU usage (since there are no difficult calculations to be performed at all)
  3. Optimal network utilisation (since we only send the information that needs to be sent

Unfortunately there is a problem: The receiver has a concept of ignoring (just "scanning") over the initial state of objects that are already present on the receiver. In such cases it is necessary for the receiver to process the insertions/deletions as a delta in the normal fashion (this involves taking RFactors with respect to a vectortime describing what operations it has already applied).

For the initial state of a xvector<T> field we always simply send the current state (and nothing more). If there are insertion/deletion intervals then that information is necessarily sent as well, but later in the same delta when the changes to the xvector are processed. In that case we should find that the sender sends the entire insertion/deletion intervals.

On the receiver two things can happen:

  1. The object didn't aready exist. The object is created with the current state. The receiver later processes the insertions/deletions specially - i.e. it simply copies the insertion and deletion intervals and makes no changes to the xvector<T> field.
  2. The object already exists. The initial state is scanned over and ignored. In that case the insertion/deletion intervals are processed in the normal way to bring the receiver up to date.