Protocol‎ > ‎Design Documents‎ > ‎

Explicit blip timestamps design proposal

    2010-01

    Alex North (anorth@google.com), Sam Thorogood (thorogood@google.com)

    Objective

    This design proposes to replace implicit blip last-modified timestamps with a representation explicitly within wave data. This model removes the blip timestamp from the worthiness calculation and makes ops which affect the timestamp properly invertible.

    Representing timestamps explicitly introduces flexibility in these values. In general an editor or agent will be responsible for updating the blip timestamp while editing. This also introduces some risk of abuse. The blip last-modified timestamp is for display purposes only and may be set arbitrarily by clients. This design proposes that authoritative timestamp information will always be available in deltas, which will be visible to users in playback and possible elsewhere. An algorithm relying on an authoritative time must use delta timestamps.

    Background

    Blip last-modified timestamps are currently calculated by servers and clients from the server-specified timestamps on deltas containing ops applying to a blip. When an op is applied to a blip and the op is deemed "worthy" the blip's timestamp is updated to match the op's. Our ops are not invertible partly because the old timestamp of the blip is not represented in the op.

    A blip's last-modified-timestamp is displayed in the wave client. The Wave client also responds to the presence of an annotation keyed conv/contentcreationtime by displaying the value of the annotation as the blip timestamp, marked with a "*". Some robots use this mechanism to override the calculated timestamp.

    Related to this design are designs to remove or explicitly represent all other blip metadata: contributors, last modified versions, etc.

    Requirements

    Blip timestamp information should be invertible; that is, for any operation we must be able to calculate, without reference to the target of the op, an inverse operation which exactly reverses the original op's effect on a wave. Metadata that is calculated when an op is applied to a wave is not invertible because the wave state before the op is required to calculate its effect.

    The blip timestamp is used only for display and is shown in the upper-right corner of a blip. It is stored as a number of seconds since the epoch and generally should accurately reflect the time of the last meaningful change (an intentionally vague description) to a blip. In some cases it is useful for the timestamp to differ from the timestamp reflected in op metadata. For example, gateways to other systems (e.g. email, social networks) may wish to set a timestamp which reflects the time of modification of data in that system. When working offline a client should be able to specify a timestamp representing the time of composition rather than the time the changes reached wave servers. The conv/contentcreationtime annotations currently used by some robots to acheive this is undesirable for a number of reasons, details omitted here.

    For any representation, we require that authoritative modification timestamps are available within the Wave system. The deltas will always contain server-specified timestamps reflecting a delta's time of application. The deltas also contain other authoritative metadata including a blip's creation time, creator, etc.

    Design Ideas

    Timestamp in blip head

    A blip's last-modified timestamp is represented explicitly as a monotonically increasing value in the blip document. The ConversationBlip interface is extended to support updating and reading it, and the listener interfaces to notify of changes.

    interface ConversationBlip {

    // ...

    long getLastModifiedTime();

    // Uses current server time. Returns new LMT.

    long updateLastModifiedTime(int roundToNearest, TimeUnit unit);

    void setLastModifiedTimeNonMonotonic(long lmt);

    }

    interface ObservableConversationBlip {

    interface Listener {

    // ...

    void onLastModifiedTimeChanged(long oldValue, long newValue);

    }

    }

    interface ObservableConversation {

    interface Listener {

    // ...

    void onBlipLastModifiedTimeChanged(ConversationBlip blip, long oldValue, long newValue);

    }

    }


    The timestamp value is backed by an element in the <head> section of each blip document.

    <head>

    <timestamp>

    <lmt t="123456789" />

    </timestamp>

    </head>

    <body>

    <line /> ...

    </body>


    Each child element of the <timestamp> has a single attribute, the value of which is an epoch-based timestamp in seconds. If multiple elements appear, as is possible under concurrent modification, then the numerically largest entry is taken to be the timestamp and other entries may be deleted. This element representation is chosen over an attribute-based representation for extensibility (see below).

    A client is responsible for updating the timestamp when submitting meaningful changes to a blip.

    • If the existing timestamp is greater than or equal to the current time, do nothing; else
    • Insert an <lmt> element with the current time and delete all other <lmt> elements

    This mechanism ensures convergence when the value is concurrently updated and that it does not regress, even when a long-offline client returns. These semantics are already implemented by the MonotonicValue interface and implementations. A client updates the timestamp value when performing conversation-level mutations rather than when submitting any ops to a document. For example, when making cursor movements and ignoring spell suggestions a client may choose not to change a blip's timestamp.

    Monotonicity is not required by the data model, but is the default mode of update. Clients may attempt to set a timestamp to a smaller value (e.g. when performing undo or recovering from abuse). However, a concurrent or later update setting the timestamp to a higher value will always override this as clients interpret the highest value present to be the canonical value.

    The last-modified timestamp is represented in the blip headers as it forms part of what might be considered the "final state" of a blip. Being part of the per-blip "content" rather than structure, the blip document is a more appropriate and simple location than the conversation manifest.

    Client estimates of server clock

    In order that timestamps are consistently interpreted across clients, the timestamp value set is based on a client's estimate of the wave server's clock. This requirement mitigates problems associated with drifting or incorrect client clocks and time zones. Using the server clock means a client may observe a timestamp which does not match their computer's clock at the time of update, depending on the accuracy of clock estimation, but will always observe the same timestamp as other clients.

    The mechanism for estimating a server's clock is client-specific and left unspecified.

    Rounding

    The blip timestamp has resolution of one second, but this is higher accuracy than is required in most cases. At present, the Google Wave client displays the value with a resolution of only one minute. Frequent timestamp updates during an editing session are unnecessary, so the timestamp value is updated only periodically by the editing client.

    While editing, the blip timestamp is updated only if the new value rounded down to the minute is greater than the existing timestamp value. Additionally, the timestamp is updated when an editing session finishes: the user clicks "Done", focusses a different blip, closes the wave etc. Non-browser clients update the timestamp with a resolution they see fit.

    Extensibility

    The timestamp representation is extensible. This design does not propose to distinguish those timestamps imported from an external system from those set by browser clients or agents. However, either attributes or child elements may be added to the <lmt> entries to support future functionality such as identifying the external timestamp source. The conversation model must ignore all unexpected attributes or child elements.

    Authoritative timestamps

    With an explicit timestamp representation there is scope for abuse through clients setting misleading or future timestamps, accidentally or maliciously. In some cases this is desirable, such as when timestamps represent external systems, but in others it is not.

    True modification time information is always available in the the timestamps of deltas affecting a document. Clients may visually identify timestamps which differ significantly from the authoritative timestamp.

    Alternatives Considered

    Timestamps could be stored in the conversation manifest document. This would allow timestamps to be processed without inspecting blip content. However, the conversation manifest currently describes only the structure of the conversation and nothing about its content.

    The timestamp could be represented as an attribute on some element in the blip document. In order to provide appropriate behaviour under concurrent editing the timestamp value is be embedded in the attribute name. If multiple entries appear, the largest value is taken to be the timestamp.

    <timestamp t123456789="1" />

    An update is performed by clearing existing attributes and adding a new one. This mechanism ensures out-of-order offline updates don't trump earlier but higher-valued updates. The ops for this mechanism would be slightly smaller than the proposed mechanism. However this format restricts extensibility. The attribute value could be used but this could lead to serialising metadata into a string for representation there.

    Explicit timestamps could be omitted entirely, but this limits flexibility, e.g. to set a timestamp based on an external system event. Given the requirement to represent these external timestamps, using the same mechanism for timestamps generated by the all clients improves simplicity and code re-use.