Re: [Demexp-dev] A protocol proposal to track modifications on server

[David MENTRE]

Hi Félix,

Many thanks for the feedback. Overall, I find your approach quite
interesting. From a programming point of view, it is quite simple to
implement, except that it will add once more new dependencies to the
code (zlib) and I need to find suitable binding. And I need to figure
how to handle endianness in OCaml.

I'll go for your approach.


Some comments on your comments:

address@hidden writes:

> 1/ Concerning your proposed approach
> -I think that it is probably most efficient in terms of bandwidth.
> I would recommend using a binary tree (instead of 10-tree you seemed
> to suggest in your mail) because I would intuitively
> guess it is optimal in terms of bandwidth needed to check the
> timestamps (but not optimal in terms of server workload, see below).
> -I may put some heavy worldload on the server because each time an
> object is modified (mainly questions and tags), all timestamps
> hierarchically "above" the said object are to be modified. In this
> case a non-binary tree is better because the larger the order of the
> tree, the less parents to update.

If I would keep my algorithm, I would implement it with the tree width
defined as a constant that could be changed. And I would probably keep
the 10-tree approach.

> -I may be complex to implement (as compared to brute method, see below)
> because of the recursive nature of the algorithm and because the server
> and client trees do not have the same shape (there are always more
> objects on the server due to new questions etc.)

OCaml helps a lot when one need to encode algorithms. But that's true
that this is more complex than your approach.

> 2/ Possible other approach: brute force

> That's 2100000 timestamps. Now, obviously, the time resolution of
> the timestamps should not be higher than the time resolution of the
> file update on the server. With 24 bits for a timestamp,
> your system can last for 2^24=16777216 and 16666216/(30*24*365)=63,8 years.
> The uncompressed file would be:
> 2100000 timestamps * 24 bits /(8*1024)=6 MB

I prefer a 32 bits timestamp (easier to code). With 31 bits (signed
integer), starting from 2005-01-01, it will allow timestamp until about
2068 if we keep the 1s resolution and until about 10000 if we keep the
2mn resolution. I'll probably use 2s resolution (until about 2130).

At 32 bits, it gives about 8 MB uncompressed.

> You would need a file format to be able to assign each timestamp to its
> corresponding object but that should be easy.

Proposed format:

32 bits int: number of questions (Q)
32 bits int: number of tags (T)
32 bits int: number of participants (P)
32 bits int: question timestamp * N
32 bits int: tags timestamp * T
32 bits int: participant timestamp * P

All integers encoded in big endian format.

The tree first integers could be encoded in the XDR format separately.

Do you think it is an issue if the three timestamp zones (for questions,
tags and participants) are gzipped separately?

> Let me know what you thing.

I like it. :-) So I'm going to implement it.


Yours,
d.
-- 
pub  1024D/A3AD7A2A 2004-10-03 David MENTRE <address@hidden>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A