Subject: Re: Tools that make use of previous/next/first/last links?

From: James M Snell <[email-masked]>
Date: Sun, 30 Apr 2006 21:25:58 -0700

Mark,

While I'm sure the other James may have his own particular set of
issues, the one pain point for me with the history spec is the use of
the "previous" link to point back in time.  This runs counter to the use
of the previous link in both OpenSearch, APP and Gdata.  It would be
excellent if rather than using previous, feed history would look at the
set of feeds as a list of pages ordered in reverse chronological order,
where "next" pointed to the next oldest set of entries.

e.g.

current=/feed.xml
first=/2006/04/feed.xml
next=/2006/03/feed.xml
next=/2006/02/feed.xml
next=/2006/01/feed.xml
...

- James

Mark Nottingham wrote:
> 
> Did you find that algorithm wrong, too hard to understand/implement, or
> did you just do a different take on it? Does the approach that you took
> end up having the same result?
> 
> Any suggestions on how to better document it appreciated.
> 
> Cheers,
> 
> 
> On 2006/04/26, at 8:35 PM, James Holderness wrote:
> 
>>
>> We added support for next/prev/previous links in version 0.3.0 of
>> Snarfer [1]. We don't use the reconstruction algorithm suggested in
>> the Feed History draft, but your example feed seems to work ok for an
>> initial retrieval. There may be problems with subsequent updates,
>> though, depending on how you handle items falling out the bottom of
>> the main feed.
>>
>> Regards
>> James
>>
>> [1] http://www.snarfware.com/
>>
>> John Panzer wrote:
>>> We just deployed support for link@rel="previous" et al. for
>>> AOL Journals.  If anyone has a client that makes use of these
>>> links, please let me know, I'd love to see if there are any
>>> interoperability problems.
>>
>>
> 
> 
> -- 
> Mark Nottingham     http://www.mnot.net/
> 
>

---

From: Eric Scheid <[email-masked]>
Date: Mon, 01 May 2006 17:04:36 +1000

On 1/5/06 2:25 PM, "James M Snell" <[email-masked]> wrote:

> of the previous link in both OpenSearch, APP and Gdata.

I thought OpenSearch results are not sorted by chronological age at all, but
instead by relevance? Using "next" with OpenSearch makes sense in that
context. Using "previous" for stepping back thru time in a data store
arranged chronologically makes sense.

I'm not familiar with how Gdata arranges it's data, but briefly scanning the
API docs it's modelled on OpenSearch, and furthermore it says "Result
ordering is up to the implementation" ... thus I would think it would be
right for it to use 'next' to get the next page, but wrong to assume that
this would imply stepping backwards chronologically.

e.

---

From: James M Snell <[email-masked]>
Date: Mon, 01 May 2006 00:55:44 -0700

> arranged chronologically makes sense.

My apologies, I did not mean to imply that OS used chronological
ordering.  Quite the opposite, in fact; that is, opensearch defines no
meaning to the ordering of pages at all.  Previous just means the
previous page in a set.

> this would imply stepping backwards chronologically.

I'm generally against making any assumptions about whether or not
next/previous points to anything but some other page of entries; if you
want to know whether they're newer or older, just look at the updated
timestamp and sort accordingly.  That said, however, we end up with a
problem when we have one spec that says next points backwards in time
(APP), one spec that says next points forwards in time (feed history)
and one spec that says next is just another page of entries that match
some criteria (opensearch). No matter what the various link types point
to, there needs to be consistency. As it stands now, a single feed
cannot implement APP, OpenSearch AND Feed History.

- James

---

From: Eric Scheid <[email-masked]>
Date: Mon, 01 May 2006 19:18:35 +1000

On 1/5/06 5:55 PM, "James M Snell" <[email-masked]> wrote:

> That said, however, we end up with a

I just reviewed the relevant example in the APP spec and it's worrisome.
Reading between the lines it suggests that the subscription uri is
"http://example.org/entries/go", with the rest of the collection available
via rel="next" through to "http://example.org/entries/10".

The worrisome thing is that once that collection gains another 10 entries,
then the resource "http://example.org/entries/11" will now contain the
entries which were previously contained by resource
"http://example.org/entries/10". Every page of the collection needs to be
updated and have the entries shuffled along.

A simplified example:

    /entries/go contains entries Q,R,S,T
    /entries/2 contains entries M,N,O,P
    /entries/3 contains entries I,J,K,L
    /entries/4 contains entries E,F,G,H
    /entries/5 contains entries A,B,C,D

which then gets another 4 entries added (ie. U,V,W,X) and the collection now
looks like this:

    /entries/go contains entries U,V,W,X
    /entries/1 contains entries Q,R,S,T
    /entries/2 contains entries M,N,O,P
    /entries/3 contains entries I,J,K,L
    /entries/4 contains entries E,F,G,H
    /entries/5 contains entries A,B,C,D

This is just smells bad in so many ways. Pity the blog package that
publishes static files and will have to rebuild every collection page. Pity
the poor server that gets asked if /entries/3 has been modified and if so
hand it over. Pity the google bot that does all that asking.

Of course, this sentence doesn't parse into English real well either:

    "next" and "prev" link elements reference the
    preceding and subsequent feed documents in the set.

ie. "next" references the *preceding* feed document, and "prev" references
the *subsequent* feed document. It doesn't even make sense when read Down
Under ;-)

e.

---

From: [email-masked] (Peter Robinson)
Date: Mon, 1 May 2006 11:16:41 +0100

> of the previous link in both OpenSearch, APP and Gdata.

Yes it does.  (Though as was later clarified it's not that OpenSearch
specifies any chronological ordering as such, but it is true that anyone
who wants to implement OpenSearch in a conventional time-ordered feed
will have to have "next" pointing back in time.)

I thought it was agreed when we were discussing registering the link
relations for prev/next etc. that the registration would not specify
whether next meant backwards or forwards in time, but that specs making
use of them would be written to be 'sign independent'.

E.g. the history spec (or something else) would define an element
<nextIsBackwardsInTime value="yes" /> or whatever, that publishers could
set and consumers would be required to check.

Regards,

Peter
-- 
Peter Robinson
<http://www.ticketswitch.com/> Concerts, sport and theatre tickets

---

From: James M Snell <[email-masked]>
Date: Mon, 01 May 2006 08:50:45 -0700

Yes, the paging in APP is a problem (one I've been largely ignoring up
to this point in our own implementation). There is no way of reliably
and efficiently reconstructing the entire feed history.

- James

---

From: James M Snell <[email-masked]>
Date: Mon, 01 May 2006 10:36:14 -0700

Mark,

Right now, the subscription feed uses "previous" to point to the archive
feeds.  Perhaps a better approach would be to to have an "archive" link
relation that points to the first of a distinct set of archive feeds.
Also, remove the temporal semantics from the the previous link and
require that each archive page contain the entries from a fixed period
of time (that is, each archive feed document is "complete" within a
given time period)

  <!-- Subscription feed -->
  <feed>
    ...
    <link rel="self" href="/feed.xml" />
    <link rel="archive" href="/2006/04/feed.xml" />
  </feed>

  <!-- /2006/04/feed.xml -->
  <feed>
    ...
    <link rel="self" href="/2006/04/feed.xml" />
    <link rel="current" href="/feed.xml" />
    <link rel="next" href="/2006/03/feed.xml" />
    <link rel="first" href="/2006/04/feed.xml" />
    <link rel="last" href="/2006/01/feed.xml" />
  </feed>

  <!-- /2006/03/feed.xml -->
  <feed>
    ...
    <link rel="self" href="/2006/04/feed.xml" />
    <link rel="current" href="/feed.xml" />
    <link rel="previous" href="/2006/04/feed.xml" />
    <link rel="next" href="/2006/02/feed.xml" />
    <link rel="first" href="/2006/04/feed.xml" />
    <link rel="last" href="/2006/01/feed.xml" />
  </feed>

This completely removes the current subscription feed from the history
reconstruction and eliminates the sliding window effect.

Reconstructing the feed history becomes a simple matter of locating the
archive link and iterating over a set of fixed pages.

- James

---

From: "James Holderness" <[email-masked]>
Date: Mon, 1 May 2006 21:30:54 +0100

> relation that points to the first of a distinct set of archive feeds.

If I have to add yet another algorithm for paging support in addition to the 
ones that are already there, I'd be inclined to just dump the whole thing.

> and efficiently reconstructing the entire feed history.

I would have thought a combination of RFC3229/feed with paging would be 
adequate. Something like that should work perfectly well with any client 
that already supports those features. It doesn't require the invention of a 
whole new system.

Regards
James

---

From: Andreas Sewe <[email-masked]>
Date: Tue, 02 May 2006 18:01:57 +0200

Eric Scheid wrote:
> I just reviewed the relevant example in the APP spec and it's 
> worrisome. Reading between the lines it suggests that the 
> subscription uri is "http://example.org/entries/go", with the rest of
> the collection available via rel="next" through to 
> "http://example.org/entries/10".
> 
> The worrisome thing is that once that collection gains another 10 
> entries, then the resource "http://example.org/entries/11" will now 
> contain the entries which were previously contained by resource 
> "http://example.org/entries/10". Every page of the collection needs 
> to be updated and have the entries shuffled along.

Yes, I have noticed this problem some time ago as well. See
"Directionality of "next"/"previous": Incompatibility with Feed-History
I-D (long)" [1] for some more discussion on this very subject, which led
in turn to PaceReverseLinks [2], which hasn't received much support,
however. :-(

Andreas Sewe

[1] <http://www.imc.org/atom-protocol/mail-archive/msg04645.html>
[2] <http://www.imc.org/atom-protocol/mail-archive/msg04718.html>

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 2 May 2006 20:23:44 -0700

>> arranged chronologically makes sense.

What Eric said.

> As it stands now, a single feed

Please describe the scenario where you'd want that to happen -- show  
the feed.

---

From: James M Snell <[email-masked]>
Date: Tue, 02 May 2006 21:14:54 -0700

Mark Nottingham wrote:
>[snip]
> Please describe the scenario where you'd want that to happen -- show the
> feed.
> 
> 

The feed(s) are part of our open activities implementation and are
available via our APP interop endpoint [1].  Our APP collection feeds
are also the feeds people subscribe to and search with (e.g. any of our
feeds accept querystring parameters to filter the feed results).
Requesters can set the page size as a querystring, if the result set is
larger than the page size, the feed is automatically paged using
first/last/next/previous.  The fact that our entries are sorted in
reverse chronological order makes us compliant with APP, but makes it
impossible for clients to use the Feed History algorithm  (current has a
next but no previous).

- James

[1] http://www.imc.org/atom-protocol/mail-archive/msg04795.html

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 2 May 2006 22:48:55 -0700

If you use URIs like
   http://example.com/feed?start=5&num=10
changing the directionality of "next" and "previous" will not make  
what you're doing compatible with feed history.

Such URIs have a much more fundamental problem -- they don't refer to  
a stable set of entries, and therefore only act as a snapshot of the  
*current* feed, chopped up into chunks. If the feed changes between  
accesses, the client will be in an inconsistent state. The client  
also has to walk through all of the pages every time it fetches the  
feed; it can't cache them -- which is a primary requirement for feed  
history.

What are the requirements that drove you to this type of paging  
solution?

---

From: David Powell <[email-masked]>
Date: Wed, 3 May 2006 10:07:37 +0100

> feed; it can't cache them -- which is a primary requirement for feed  

I think it would be worth recommending the use of stable URIs in the
draft.

-- 
Dave

---

From: "A. Pagaltzis" <[email-masked]>
Date: Wed, 3 May 2006 11:26:35 +0200

* David Powell <[email-masked]> [2006-05-03 11:20]:
> > Such URIs have a much more fundamental problem -- they don't
> > refer to a stable set of entries, and therefore only act as a
> > snapshot of the  *current* feed, chopped up into chunks. If
> > the feed changes between  accesses, the client will be in an
> > inconsistent state. The client  also has to walk through all
> > of the pages every time it fetches the  feed; it can't cache
> > them -- which is a primary requirement for feed  history.
> 
> I think it would be worth recommending the use of stable URIs
> in the draft.

Considering how fundamental stable URIs are to the FH extension
and how much of the previous discussion has revolved around them,
I’m surprised there isn’t already language to that effect in the
text. In fact, I would have expected a SHOULD or two on this
subject.

Regards,
-- 
Aristotle Pagaltzis // <http://plasmasturm.org/>

---

From: Bill de hÓra <[email-masked]>
Date: Wed, 03 May 2006 11:42:41 +0100

(ot for the last thread)

Hi Mark,

I've just specced out an app that uses FH and this idea of an archived 
feed hadn't quite come across to me as "safe" - I had some what ifs 
about server resets that affected the feed.

However, the URL:

nails that concern for me and thus your point about "chunky URLs" which 
dynamically generated feeds rings true. Would you consider calling this 
out thing directly in a future rev? I think it might be helpful for 
robust server designs if some guidance were given.

cheers
Bill

Mark Nottingham wrote:
> changing the directionality of "next" and "previous" will not make what 
> you're doing compatible with feed history.
> 
> Such URIs have a much more fundamental problem -- they don't refer to a 
> stable set of entries, and therefore only act as a snapshot of the 
> accesses, the client will be in an inconsistent state. The client also 
> has to walk through all of the pages every time it fetches the feed; it 
> can't cache them -- which is a primary requirement for feed history.
> 
> What are the requirements that drove you to this type of paging solution?
> 
>

---

From: James M Snell <[email-masked]>
Date: Wed, 03 May 2006 08:43:50 -0700

+1, I'd also highly recommend introducing an "archive" link relation
that can be used to cleanly separate paged feed documents used for state
reconstruction from paged feed documents used for other purposes (e.g.
searching)

  ===
  Attribute Value: archive

  Description: A URI that, when dereferenced, returns a feed document
  containing a fixed set of entries that does not change over time.

  Expected display characteristics: The archive relation may be used
  for background processing without displaying its value, or, a user
  agent may support displaying a hyperlink, button or other GUI element
  for accessing or subscribing to the linked feed document.

  Security Considerations: Automated agents should take care when this
  relation crossed administrative domains (e.g. the URI has a different
  authority than the current document)
  ===

Example;

  <link rel="archive" href="http://example.org/archive?when=2006/04" />

- James

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 3 May 2006 09:43:22 -0700

I had this already:
    "Archive document" refers to a feed document that is archived; i.e.,
    the set of entries inside it does not change over time.  Entries
    within an archive MAY themselves change, however.

but if this is catching people by surprise, it obviously isn't  
prominent enough. I'll hammer it home with some examples, SHOULDs, etc.

Thanks!

On 2006/05/03, at 3:42 AM, Bill de hÓra wrote:

> (ot for the last thread)
>
> Hi Mark,
>
> I've just specced out an app that uses FH and this idea of an  
> archived feed hadn't quite come across to me as "safe" - I had some  
> what ifs about server resets that affected the feed.
>
> However, the URL:
>
> nails that concern for me and thus your point about "chunky URLs"  
> which dynamically generated feeds rings true. Would you consider  
> calling this out thing directly in a future rev? I think it might  
> be helpful for robust server designs if some guidance were given.
>
> cheers
> Bill
>
> Mark Nottingham wrote:
>> If you use URIs like
>> Such URIs have a much more fundamental problem -- they don't refer  
>> to a stable set of entries, and therefore only act as a snapshot  
>> of the *current* feed, chopped up into chunks. If the feed changes  
>> between accesses, the client will be in an inconsistent state. The  
>> client also has to walk through all of the pages every time it  
>> fetches the feed; it can't cache them -- which is a primary  
>> requirement for feed history.

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 3 May 2006 09:52:33 -0700

Any extension that uses "previous" and "next" has to account for the  
stablity of the underlying resources; if you use *any* paging  
application and the set of entries in "previous" and "next" changes  
over time, you're going to potentially end up with a reconstructed  
feed in inconsistent state. Or do you have use cases where it's OK to  
have sloppy feed reconstruction?

On 2006/05/03, at 8:43 AM, James M Snell wrote:

>>> refer to

---

From: [email-masked] (Peter Robinson)
Date: Wed, 3 May 2006 23:26:45 +0100

> Please describe the scenario where you'd want that to happen -- show

I don't use APP, but this feed implements OpenSearch and would like to
allow clients to maintain a history:
<http://www.ticketswitch.com/cgi-bin/atom_feed.exe>

The OpenSearch description is here:
<http://www.ticketswitch.com/cgi-bin/rss_open_search_desc.exe>
(The name is a holdover from when OpenSearch was rss-only.)

Regards,

Peter