[Spread-users] Lamport timestamps?
John Schultz
jschultz at spreadconcepts.com
Fri Aug 24 11:49:24 EDT 2007
Spread currently implements causal ordering as a total ordering that is
causal. Rather than a lamport timestamp, each Spread daemon updates a
shared sequence number that defines the IDs and total order of messages.
Only one daemon can update this sequence number at a time (within a given
membership) when it holds the token and sends messages.
Exposing this counter would buy users very little, as they can easily
reconstruct the counter upon delivery. The first delivered message is #1,
the second is #2 and so on. Simply reset the counter to zero on any
membership change (and associate it with the membership ID). The only
tricky thing would be after transitional messages where there can be holes
in the total order. Anyway, let us know if this helps with your problem
or not.
Because total order is a stronger service than causal order, this
implementation can cause higher latencies, both in message origination and
in delivery dependencies, than if causal ordering was directly
implemented.
If one were to implement causal ordering directly in Spread, then we most
likely would use a Directed Acyclic Graph (DAG) of causal dependency
rather than vector timestamps. Essentially, the DAG is an optimized
version of vector timestamps where only the minimum necessary causality
information is attached to each message.
For example, if a daemon were to send two messages with no intervening
receives, then the first one might have several dependencies listed but
the second message would simply say it depends on the first message it
just sent. When you have losses you may need to recover some of the
messages in the dependency chain, but this is true for either
implementation.
Cheers!
---
John Schultz
Spread Concepts
Phn: 443 838 2200
On Thu, 23 Aug 2007, Peter A. Friend wrote:
> On Aug 23, 2007, at 1:50 PM, Alaric Snell-Pym wrote:
>>
>> Hi there,
>>
>> Implementing a replicated data storage system using Spread, I've had
>> to implement my own Lamport timestamps for various reasons, but it
>> occurs to me that there's probably one ticking away inside my local
>> Spread daemon anyway. I've not yet looked in the source, but I'm
>> considering the feasibility of exposing that time to the users of the
>> daemon.
>
> And this is also related to a question I posted earlier about how causal
> orders are currently implemented. From the book by Birman it seems you can
> use a logical timestamp but it takes a lot of messages to support a causal
> order. With vector timestamps there is more per-message overhead but fewer
> messages are needed to provide a causal order.
More information about the Spread-users
mailing list