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

[David MENTRE]

Hello,

I'm currently trying to design the protocol, data structures and
algorithms needed to imlement caching in the client.

The main idea is quite simple: 

  To each object in the server (participant, question or tag) associate
  a 64 bits timestamp (following the scheme suggested by Félix). Each
  time an object is modified, its timestamp is updated with latest
  modification real time.

  When the client needs to know whether its cache is synchronized or not
  with the server, it only needs to check the object timestamp on the
  server. If the client's local value is the same, it has latest
  version, otherwise it needs to fetch the latest one from server.


My only concern is regarding timestamp fetching. How to optimize it in
such a way that the client won't request timestamp of *all* objects on
the server?

I'm thinking at the following solution:

 - the server keeps the highest timestamp for groups of 10, 100, 1000,
   ... objects in a tree, the bigger the group, higher it is in the
   tree. 

   For example, highest timestamps for questions from 0 to 9, 10 to 19,
   ..., highest timestamp for questions from 0 to 99, etc.;

 - the client keeps the same data structure for its cache;

 - when the client needs to check its local cache validity, it requests
   the highest timestamp for questions from 0 to the maximum number of
   questions. For example, highest timestamp for questions from 0 to
   99. 

   If the timestamp given by server does not match the highest timestamp
   localy stored, the client requests the 10 sub-timestamps. For
   example, timestamps for questions from 0 to 9, 10 to 19, ..., 90 to
   99. For each one of them, the client check if it has the same value.

   If not, get individual question info for unmatching timestamp.


On the server or client side, when an object is modified, e.g. question
18, it is only needed to update a limited amount of timestamps,
e.g. from 10 to 19, from 0 to 99, from 0 to 999, ...

Obviously, the algorithm has an logarithmic complexity and is scalable
to a large amount of objects.

What do you think of it?

Any suggestion of suitable data structures? Any pitfalls to avoid?

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