Subject: Re: Feedback on Tombstones -04

From: "Mark Stahl" <[email-masked]>
Date: Wed, 7 May 2008 12:19:25 -0400

One issue that we've encountered with tombtones is that most services don't
keep them forever.     (Otherwise, the list of tombstones only ever grows.)

This leads to problems with clients that periodically poll for changes -
they don't know if the set of tombstones is complete since the last time
they polled.

I'd suggest adding an element at:deleted-since, so the server can let the
client know the tomebstone window in effect.  Building on the proposal for
at;deleted-entries, I'd suggest something like this:

<at:deleted-entries>
  <at:deleted-since>2003-12-13T18:30:02.25Z</at:deleted-since>
  <at:deleted-entry .../>
  <at:deleted-entry .../>
  <at:deleted-entry .../>
</at:deleted-entries>

Another useful piece of information to the client trying to sync is a hint
as to the typical tomebstone lifetime.  But I'm not sure if it belongs in
this spec. (Perhaps it's more appropriate in a service document?)

-- mark

On Tue, Apr 22, 2008 at 5:15 PM, Eric Scheid <[email-masked]>
wrote:

>
> On 23/4/08 3:46 AM, "Brian Smith" <[email-masked]> wrote:
>
> > Why not have at:deleted-entry contain app:edited and/or atom:updated
> > instead of @when? Then say that timestamps should be compared using the
> > same date construct (compare only app:edited to app:edited, and
> > atom:updated to atom:updated). AtomPub collections would use app:edited
> > and most other collections would use atom:updated, just like they do
> > with atom:entry already today.
>
> +1 : elegant, simple
>
> > This would allow a feed to indicate that it supports this feature, even
> > when no entries have been deleted:
> >
> >   <at:deleted-entries/>
> >
> > Knowing that the collection provides these tombstones would all clients
> > to skip crawling the collection to look for deleted entries.
>
> +1 also
>
> e.
>
>

-- 
Test driving http://five.sentenc.es/

---

From: "Brian Smith" <[email-masked]>
Date: Wed, 7 May 2008 11:19:06 -0700

> keep them forever.     (Otherwise, the list of tombstones only ever 

For most systems, keeping track of deleted items on the back end is not a 
problem. The only problem is that you don't want the feeds to be bloated 
with an ever-increasing number of tombstones, right?

> client know the tomebstone window in effect.

To solve this problem, I implemented a simple feed paging extension. The 
first page of the collection feed (at the collection URI) contains a 
"feed-changes" link. The feed-changes link points to a feed that is only 
guaranteed to contain all the information (e.g. entries and tombstones) that 
was changed since the first page of the collection feed was fetched. The 
clients can use this to answer the question "what are all the changes that 
occurred since the last time I synced with the server?"

The first page of the "feed-changes" feed contains another "feed-changes" 
link that works in an analogous fashion. Clients can keep in sync with the 
collection by chasing the "feed-changes" links. The "feed-changes" feeds can 
also use RFC 5005 paging; to get a complete sync, one has to page through 
all the pages (using "next") before chasing the "feed-changes" link from the 
first page.

My suggestion is to finish up the at:deleted-entry mechanism that is as 
simple as possible, and then define a separate AtomPub synchronization 
protocol on top of it, based on the "feed-changes" mechanism I just 
described, where the at:deleted-entry mechanism would be a required element 
of the "feed-changes" feeds. What do you think?

> this spec. (Perhaps it's more appropriate in a service document?)

It is a good idea to keep this information in the feed, because this is 
useful in Atom feeds that are not AtomPub feeds.

Regards,
Brian

---

From: "James Holderness" <[email-masked]>
Date: Wed, 7 May 2008 19:40:50 +0100

Mark Stahl wrote:
> This leads to problems with clients that periodically poll for
> changes - they don't know if the set of tombstones is complete
> since the last time they polled.
>
> I'd suggest adding an element at:deleted-since, so the server
> can let the client know the tomebstone window in effect.

Assuming you did know whether the set of tombstones was complete or not, how 
would this effect your behaviour as a client? In other words, what would you 
do differently if you knew the set of tombstones was incomplete?

Regards
James

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 8 May 2008 10:45:04 +1000

In a paged feed, I just put the tombstones on the page that's  
appropriate; e.g., if the entries are sorted by date (and most are),  
the tombstone goes on the relevant page (i.e., using the time of  
deletion).

On 08/05/2008, at 2:19 AM, Mark Stahl wrote:

> One issue that we've encountered with tombtones is that most  
> services don't keep them forever.     (Otherwise, the list of  
> tombstones only ever grows.)
>
> changes - they don't know if the set of tombstones is complete since  
> the last time they polled.
>
> I'd suggest adding an element at:deleted-since, so the server can  
> let the client know the tomebstone window in effect.  Building on  
> the proposal for at;deleted-entries, I'd suggest something like this:
>
> <at:deleted-entries>
> Another useful piece of information to the client trying to sync is  
> a hint as to the typical tomebstone lifetime.  But I'm not sure if  
> it belongs in this spec. (Perhaps it's more appropriate in a service  
> document?)
>
> -- mark
>
>
> On Tue, Apr 22, 2008 at 5:15 PM, Eric Scheid <[email-masked] 
> > wrote:
>

--
Mark Nottingham     http://www.mnot.net/

---

From: "Mark Stahl" <[email-masked]>
Date: Thu, 8 May 2008 08:28:54 -0400

On Wed, May 7, 2008 at 2:40 PM, James Holderness <[email-masked]>
wrote:

>  Assuming you did know whether the set of tombstones was complete or not,
> how would this effect your behaviour as a client? In other words, what would
> you do differently if you knew the set of tombstones was incomplete?
>

James,

The issue is sync, and the diffrence is between incremental and full sync.

Assume a client has previously downloaded a complete copy of a collection at
time T1.  Some time later, T2, the client retrieves the updated feed.
Assume entries and tombstones are both in app:edited order, as suggested by
Mark Nottingham.  If the client knows that the server is still holding
tombstones of all entries deleted since T1, then it can correctly update
it's local copy of the collection to be in sync with the server. Otherwise,
it must retrieve the full collection and manually calculate the missing
deletes in order to sync.

-- m

---

From: "Mark Stahl" <[email-masked]>
Date: Thu, 8 May 2008 10:09:04 -0400

On Thu, May 8, 2008 at 8:28 AM, Mark Stahl <[email-masked]> wrote:

> >  Assuming you did know whether the set of tombstones was complete or
> > not, how would this effect your behaviour as a client? In other words, what
> > would you do differently if you knew the set of tombstones was incomplete?
> >
>
> James,
>
> Assume a client has previously downloaded a complete copy of a collection
> at time T1.  Some time later, T2, the client retrieves the updated feed.

But just to reiterate my reasons for suggesting this, it's *not* my goal to
write a sync algorithm into the at:delete-entries spec.

I'm just suggesting that we should provide a way for a service to indicate
there may be deleted entries it has forgotten about.  The at:deleted-since
extension seems to me the simplest way to fill that need.

 -- mark

---

From: James M Snell <[email-masked]>
Date: Thu, 08 May 2008 07:47:49 -0700

The time-window issue is relevant to more than just deleted entries.  A 
relying party may also need to know the timeframe for a given set of 
edits and posts.  What I had originally imagined is that the time window 
would be handled by a higher level sync specification and not 
specifically by the tombstones draft.

- James

Mark Stahl wrote:
> 
> 
> On Wed, May 7, 2008 at 2:40 PM, James Holderness <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
> 
>     Mark Stahl wrote:
> 
>     not, how would this effect your behaviour as a client? In other
>     words, what would you do differently if you knew the set of
>     tombstones was incomplete?
> 
> 
> James,
> 
> Assume a client has previously downloaded a complete copy of a 
> collection at time T1.  Some time later, T2, the client retrieves the 
> updated feed.  Assume entries and tombstones are both in app:edited 
> order, as suggested by Mark Nottingham.  If the client knows that the 
> server is still holding tombstones of all entries deleted since T1, then 
> it can correctly update it's local copy of the collection to be in sync 
> with the server. Otherwise, it must retrieve the full collection and 
> manually calculate the missing deletes in order to sync. 
> 
> -- m
> 
> --

---

From: "Brian Smith" <[email-masked]>
Date: Thu, 8 May 2008 07:43:07 -0700

Mark Stahl wrote:
> The idea of interleving entries and deleted-entries in edited order sounds
> like a good pattern.  It's particularly useful  for clients attempting to
> retrieve the most recent changes.

Earlier in the thread James Snell pointed out that RFC4287 doesn't seem to 
allow any elements between or after the <atom:entry> elements in a 
<atom:feed> element.

Also, It would only be useful if the deleted-entries elements were required 
to be in order along with the entries; otherwise, the client would have to 
parse the whole feed anyway for out-of-order tombstones.

- Brian

---

From: "Mark Stahl" <[email-masked]>
Date: Thu, 8 May 2008 09:55:58 -0400

MarkN,

The idea of interleving entries and deleted-entries in edited order sounds
like a good pattern.  It's particularly useful  for clients attempting to
retrieve the most recent changes.  Combining this idea with the idea of a
tombstone "lifetime", then, one could construct a feed that looks something
like this:

<feed>
   <entry> ... updated at T ... </entry>
*   <at:deleted-entry> ... deleted at T-1... </at:deleted-entry>
   <at:deleted-entry> ... deleted at T-2... </at:deleted-entry>
*   <entry> ... updated at T-3 ... </entry>
*    <at:deleted-since>T-4</at:deleted-since>
*   <entry> ... updated at T-5 ... </entry>
   <entry> ... updated at T-6 ... </entry>
   ...
</feed>

I would not recommend this order be required.  But it would be very useful
for clients attempting to learn of changes to the feed since the last time
they accessed it.

-- m

On Wed, May 7, 2008 at 8:45 PM, Mark Nottingham <[email-masked]> wrote:

> In a paged feed, I just put the tombstones on the page that's appropriate;
> e.g., if the entries are sorted by date (and most are), the tombstone goes
> on the relevant page (i.e., using the time of deletion).
>
>
>
>  One issue that we've encountered with tombtones is that most services
> > don't keep them forever.     (Otherwise, the list of tombstones only ever
> > grows.)
> >
> > I'd suggest adding an element at:deleted-since, so the server can let
> > the client know the tomebstone window in effect.  Building on the proposal
> > for at;deleted-entries, I'd suggest something like this:
> >
> > <at:deleted-entries>
> > Another useful piece of information to the client trying to sync is a
> > hint as to the typical tomebstone lifetime.  But I'm not sure if it belongs
> > in this spec. (Perhaps it's more appropriate in a service document?)
> >
> > -- mark
> >
> >
> > On Tue, Apr 22, 2008 at 5:15 PM, Eric Scheid <
> > [email-masked]> wrote:
> >

---

From: "Brian Smith" <[email-masked]>
Date: Thu, 8 May 2008 07:35:17 -0700

> extension seems to me the simplest way to fill that need.

I don't have any objection to the at:deleted-since idea, but it seems 
impossible to describe in a useful way without describing part of a 
synchronization protocol.

Besides expiration, there is another reason that a feed may not contain 
tombstones for all deleted entries. If any information is encoded in that 
atom:id (e.g. the title of the entry), then the feed producer may provide a 
mechanism for a user to delete an entry without producing a tombstone, to 
prevent information leaking via the atom:id. So, even if you sync within the 
time frame suggested by the at:deleted-since element, you might not get all 
of the tombstones.

- Brian

---

From: "Mark Stahl" <[email-masked]>
Date: Thu, 8 May 2008 08:19:46 -0400

On Wed, May 7, 2008 at 2:19 PM, Brian Smith <[email-masked]> wrote:

> > don't

Typically, the limitation on the number of tombstones reflects a limitation
in the amount of storage available in a backend service.  If tombstone
lifetimes are infinite, the storage required for an atom pub collection can
grow to an ever increasing size, even if the number of elements allowed in
that collection is bounded.   Most services I talk about doing AtomPub purge
tombstones after some time (for example, 30 days.)   So I'm faced with the
problem today.  Advertising the tombstone window would solve a lot of
problems.

> all the pages (using "next") before chasing the "feed-changes" link from the

This addresses the large feed document issue, but is still premised on the
idea that you store all tombstones indefinitely, so it doesn't solve the
problem I'm attempting to solve.

> of the "feed-changes" feeds. What do you think?

I'm willing to separate the problem of a sync spec from tombstones, so I
guess it depends on whether you consider it important that the tombstone
spec have the capability to indicate that the set of tombstones provided may
not be complete.  I tend towards thinking that it's important enough to be
included in the main spec, but YMMV, and I'd be happy to have
at:deleted-entry today so we can build on it.

> > hint

The reason I hesitate to mention this is it seems to be heading more and
more towards a sync spec.  And I'm not trying to solve the whole sync
problem with this spec, but create tools that will be used to solve sync.

Regards,

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 9 May 2008 09:47:02 +1000

...and that's not exactly what I was suggesting; I only meant that the  
at:deleted-entry should appear in the same feed document (i.e., page)  
as its contemporary atom:entry's.

Cheers,

On 09/05/2008, at 12:43 AM, Brian Smith wrote:

> Earlier in the thread James Snell pointed out that RFC4287 doesn't  
> seem to allow any elements between or after the <atom:entry>  
> elements in a <atom:feed> element.
>
> Also, It would only be useful if the deleted-entries elements were  
> required to be in order along with the entries; otherwise, the  
> client would have to parse the whole feed anyway for out-of-order  
> tombstones.
>
> - Brian

---

From: "Mark Stahl" <[email-masked]>
Date: Mon, 12 May 2008 12:02:47 -0400

Sounds like there's no momentum for adding an at:deleted-since feature to
this draft, and that it's better added to a further on sync draft.   (We
will end up doing something similar in the interim.)  Any other opinions?
-- m

On Thu, May 8, 2008 at 7:47 PM, Mark Nottingham <[email-masked]> wrote:

> at:deleted-entry should appear in the same feed document (i.e., page) as its
> contemporary atom:entry's.
>
> Cheers,
>
>
>
> > Earlier in the thread James Snell pointed out that RFC4287 doesn't seem
> > to allow any elements between or after the <atom:entry> elements in a
> > <atom:feed> element.
> >
> > required to be in order along with the entries; otherwise, the client would
> > have to parse the whole feed anyway for out-of-order tombstones.
> >
> > - Brian
> >
>
>
> --

---

From: "Brian Smith" <[email-masked]>
Date: Mon, 12 May 2008 12:34:32 -0700

> will end up doing something similar in the interim.)  Any other opinions?

What is the exact specification text that you are proposing? I think if you 
submitted the text, it would be easier to see if it belongs in the 
at:deleted-entry spec. or a sync. spec. My guess is it cannot be described 
adaquately without describing a complete synchronization protocol.

Are you guys (Google) going to propose an interoperable syncing protocol?

- Brian

---

From: "Brian Smith" <[email-masked]>
Date: Mon, 12 May 2008 12:52:03 -0700

- Brian