Hi, it seems to me that your approach relies heavily on synchronized clocks in the server cluster. The three components in the time stamp are only useful to resolve a conflict in case two deltas have been generated on two machines in the cluster at the very same time. So the tmestamps are unique but they are not ordered correctly IMHO.
If the machines have no synchronized clocks I cannot see (currently) how your protocol should work. Let's say so far all deltas received by a client came from server 1 of the cluster and therefore the client received timestamps as follows (t1, 0, id1), (t1, 1, id1), (t2, 0, id1), (t3, 0, id1) with t1 < t2 < t3. Now the client logs off and in again. It request all changes that happened after (t3, 0, id1) because this is the latest time stamp it has seen. It could have happened that server 2 has created a delta that the client has not yet seen but which has the timestamp (x, 0, id2) with t2 < x < t3. This happened because clocks are not perfectly synchronized. The client will not get this delta because (x, 0, id2) < (t3, 0, id1), i.e. it seems to be older but it is not. I think you need vector clocks since these allow you to define a consistent cut across a distributed systems. To me this seems to be your intention. However, vector clocks grow in size with the number of servers involved, which renders them next to useless in very large settings. ... and I fully agree that such things will be much easier to discuss at the summit :-) Greetings Torben 2010/10/26 Tad Glines <[email protected]> > When I designed the global sequence I was aware of the potential > scalability issue. I dealt with this by including three components in the > sequence. Timestamp, sequence, and server id. > The timestamp is the same as the one currently included in deltas. The > sequence is only non-zero if more than one delta are generated on the server > in a very short time frame where the timestamp ends up being the same. In my > implementation I just used an atomic integer. The server id is unique to > each instance in a back end cluster and helps provide that last bit if > ordering in the case where on some large set of servers the timestamp and > sequence happen to to be the same. This method of sequence number generation > requires no run-time coordination, just startup/configuration time > coordination for the server ids. > > This summit should be fun. A lot can be resolved in 5 minutes that takes > days over e-mail. > > -Tad > > > On Mon, Oct 25, 2010 at 8:22 PM, Alex North <[email protected]> wrote: > >> Re: a global delta ordering. We considered this for a while as a >> simplification to aid some client, but ultimately rejected it. The core >> reason we decided against it is that it severely limits scalability (in our >> system, anyway) to require global coordination between many wave servers to >> agree on a clock/sequence. It depends on the scope of the sequence, but it >> pretty much forces everything that knows about the sequence to be homed on >> the same machine. We tried to design a protocol that would not constrain the >> implementation in that way (not that we necessarily succeeded). >> >> We built all our clients to not rely on cross-wavelet ordering, though a >> weak form can be gained from timestamps. >> >> However, it's still something we could consider again. I hope at the >> summit we'll be able to talk a bit more about our lessons from scaling >> Google Wave - it's a bit difficult to communicate everything over email. >> >> A. >> >> >> On 26 October 2010 11:42, Tad Glines <[email protected]> wrote: >> >>> Yes, participant removal does complicate things. I had to deal with it in >>> a bunch of places when I was implementing changes for my last project. >>> >>> There was one change to the protocol I had to make that I'd like to >>> discuss at some point. When dealing with a thick client that has a lot of >>> waves state stored locally and the need to operate disconnected for long >>> periods of time, there's a need to sync with the server quickly. Having the >>> client open or make history requests for ALL the waves doesn't scale well. >>> Also if the client is using wave for things other than conversations it may >>> become important to be able to order deltas global and not just within a >>> wavelet. to that end I had to add a global sequence number to the deltas.In >>> this case it was global with the server. The client could then ask for all >>> deltas that occurred after sequence number X. This plus a threading change >>> in the server to ensure deterministic ordering of deltas sent to other >>> connected clients, allows reliable cross wavelet references (i.e. the >>> referenced item would always arrive before the reference). >>> >>> Any thoughts. >>> >>> -Tad >>> >>> >>> On Mon, Oct 25, 2010 at 5:10 PM, Alex North <[email protected]> wrote: >>> >>>> Thanks for these great questions, Tad, and apologies for the slow >>>> response. I lost focus on this amongst a pile of refactorings necessary >>>> before I could make a real start. >>>> >>>> I intend to respond to your questions in detail and update the proposal >>>> soon. I will just point out though that the remove participant mechanism >>>> (losing all access) was just a stop-gap, so that we could implement a >>>> simple >>>> version of the protocol and then iterate to address tricky problems like >>>> that. We have experience from implementing participant removal in Google >>>> Wave and it turned out to be even more complex than you might think. >>>> >>>> Cheers, >>>> Alex >>>> >>>> On 16 October 2010 01:13, Tad Glines <[email protected]> wrote: >>>> >>>>> I'd like to see the semantics for participant removal more explicitly >>>>> documented. In places it's implied that the user looses all access to a >>>>> wavelet once removed from the participant list, where as in other places >>>>> it's implied that the user retains access to the wavelet history up to the >>>>> delta where the participant is removed. It seems pointless to remove all >>>>> access to the wavelet since the user has already seen (and may have >>>>> cached) >>>>> the previous contents. So it seems more reasonable that the participant >>>>> retains access to all deltas up to and including the delta where the >>>>> participant is removed. If the participant is removed, added then removed >>>>> again. the participant should retain access to all deltas up to and >>>>> including the last delta in which the participant is removed. >>>>> >>>>> Having implemented my own client side OT I can say that the logic will >>>>> more complicated if the delta associated with a client submit is >>>>> completely >>>>> omitted. it's easier to match against a version than it is to identify the >>>>> gap between deltas. Perhaps we could make the delta in WaveletUpdate >>>>> optional and omit it for deltas that correspond to the clients submit. >>>>> However, omitting the delta is only valid if the delta stream and submit >>>>> can >>>>> be associated with the same client instance by the server. This is simple >>>>> in >>>>> the case where the client connects to the server with a single WebSocket, >>>>> but is more difficult if the client sends the submit via a separate >>>>> communication channel from the delta stream. >>>>> >>>>> If the channelId found in SubmitDeltaRequest is intended as a means to >>>>> associate a submit with a delta stream then it should be made optional or >>>>> the description needs to be modified so that it states that the delta >>>>> channel must be opened before a submit can be made. >>>>> >>>>> If we add an optional endVersion to the OpenWaveletChannelRequest, then >>>>> it can serve as an open-ended subscription or as a closed-ended history >>>>> request. >>>>> >>>>> What would the server return in the version zero snapshot? It's a >>>>> little hard to tell from the description whether or not the server would >>>>> be >>>>> creating the root conversation or if it would only be including metadata. >>>>> I'm assuming that the only reason you have the wavelet creation service >>>>> seperated from the delta submit service is so that the server can include >>>>> initial metadata in the wave/wavelet. If so, what metadata would the >>>>> server >>>>> be including? >>>>> >>>>> -Tad >>>>> >>>>> On Thu, Oct 14, 2010 at 4:23 PM, Alex North <[email protected]> wrote: >>>>> >>>>>> Hi all, >>>>>> >>>>>> The Google Wave client/server protocol is rather complex and we had >>>>>> trouble documenting it well. It was never fully implemented in FedOne >>>>>> (now >>>>>> WIAB). We've recently developed a design for a new, simpler protocol >>>>>> which >>>>>> I'd like to share with you here. >>>>>> >>>>>> >>>>>> https://sites.google.com/a/waveprotocol.org/wave-protocol/protocol/design-proposals/clientserver-protocol >>>>>> >>>>>> Questions and feedback are most welcome. In particular please let me >>>>>> know if the documentation is unclear. I intend to implement this >>>>>> protocol in >>>>>> Wave in a Box over the coming week or so. >>>>>> >>>>>> Cheers, >>>>>> Alex >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Wave Protocol" group. >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]<wave-protocol%[email protected]> >>>>>> . >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/wave-protocol?hl=en. >>>>>> >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Wave Protocol" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]<wave-protocol%[email protected]> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/wave-protocol?hl=en. >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Wave Protocol" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<wave-protocol%[email protected]> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/wave-protocol?hl=en. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Wave Protocol" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<wave-protocol%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/wave-protocol?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Wave Protocol" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<wave-protocol%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/wave-protocol?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Wave Protocol" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<wave-protocol%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/wave-protocol?hl=en. > -- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
