Subject: Feed Paging for Efficient Feed Synchronization

From: "Brian Smith" <[email-masked]>
Date: Thu, 6 Dec 2007 20:02:14 +0700

James Snell wrote at http://www.snellspace.com/wp/?p=818:

> <x:link-template rel="sync"
>   pattern="http://.../myfeed;sync?{join|&|since,until}" />

<snip>

> If the until param is omitted, it is assumed to be “now”
> as determined by the server. The server must indicate the
> until date in the response feed. If the since param is
> omitted, it is assumed to be a timestamp indicating the
> moment the collection was created.

Do "since" and "until" refer to atom:updated or app:edited?

> The URL returns a single, complete Atom feed listing ONLY
> the entries that have been modified within the window of
> time specified.

It is unreasonable to require this to be done in a single page if there are many entries that need to be sent during the sync. Consider a collection that has thousands of items and a client that always uses http://.../myfeed;sync?since=1900-01-01T00:00:00Z to constantly download the entire collection. Paging is still needed.

<snip>

> We can differentiate new and updated entries using the
> x:sync element and the existing atom:published,
> atom:updated and app:edited timestamps.

Most AtomPub applications will consider an entry to be updated if they already had a copy of the entry with an earlier app:edited, and new otherwise, without needing FeedSync at all. FeedSync is more useful for non-AtomPub feeds because many implementations do not do a good job of managing the atom:updated property of entries.

<snip>

> And Because the entire snapshot is contained within a single 
> feed document, we do not have to worry about the race
> condition that is inherent in the rolling window feed
> paging model.

The race condition is not an inherent problem in the paging model; it is an implementation issue. In my implementation, I do all the paging in my collection feed using links like:

   <link rel='prev' href='?until={END}'/>
   <link rel='next' href='?since={START}'/>

Where START is the earliest app:edited in the current page and END is the latest app:edited in the current page. By assuring that all entries with the same app:edited value are collected on the same page, and following the specification requirements about the ordering of the feed, there is no chance for a race condition.

Furthermore, the first page of the feed (the collection subscription document) contains:

    <link rel='next' href='?since={START}'/>

Where START is the latest app:edited value in the collection. As a result, any client can efficiently sync with the collection like so:

1. When initially subscribing to the collection, pull down the subscription document. Remember the value of the 'next' as SYNC and page backwards using the 'prev' link relation.

2. Whenever the client needs to re-sync with the collection, instead of retrieving the subscription feed document as usually, pull the feed document from the SYNC IRI. Then page forward using the 'next' link relation, stopping at the page that has
      <link rel='next' href=''/>
(which will be a feed document with no entries). Remember the IRI of that last page as SYNC, for subsequent re-syncs.

- Brian

---

From: James M Snell <[email-masked]>
Date: Thu, 06 Dec 2007 08:07:17 -0800

> Do "since" and "until" refer to atom:updated or app:edited?

It would be app:edited

> [snip]

Note that I specifically indicated the rolling window feed paging model.
 Yes, there are ways of doing the paging where the pages are stable, and
if we can rely on folks doing it that way consistently then paging is
fine.  The key requirement is that the snapshot has to remain stable
throughout the sync process.

That said, however, once the initial sync is completed, subsequent
incremental sync's are much more efficient if paging is not used (e.g.
give me one feed document describing just the things that have changed
over the last twelve hours, etc).

> (which will be a feed document with no entries). Remember the IRI of that last page as SYNC, for subsequent re-syncs.

Again, this would work so long as the pages remain stable; however, I
would very much like to see a comparison of how the two approaches
compare in terms of performance / efficiency.

- James

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 7 Dec 2007 00:15:17 +0700

James M Snell wrote:
> >> And Because the entire snapshot is contained within a single feed 
> >> document, we do not have to worry about the race condition that is 
> >> inherent in the rolling window feed paging model.
> > 
> > The race condition is not an inherent problem in the paging 
> > model; it is an implementation issue. In my implementation, I 
> > do all the paging in my collection feed using links like:
> 
>  Yes, there are ways of doing the paging where the pages are 
> stable, and if we can rely on folks doing it that way 
> consistently then paging is fine.  The key requirement is 
> that the snapshot has to remain stable throughout the sync process.

To be clear, I don't provide any kind of snapshot mechanism. The client needs to go back to the start of the feeds (most recently edited entries) after it has paged through all the older entries, to see if some older entry has been modified during the paging process. If some entry or entries are constantly being edited, then it is possible that the client will never see them. On the other hand, what good does it do for the client to receive an old representation of an entry that is currently being relentlessly edited? The cost of implementing snapshotting seems to nearly always outweigh any benefits it might have.

The only guarantees that I make beyond what AtomPub requires are: (1) if any entries are skipped during paging, they will appear at the start of the feed, (2) navigating to each "prev" page will always result in older entries than the ones in the current page, and (3) navigating to each "next" page will result in an empty page or in entries newer than the ones in the current page. Implementations that do paging by numbering each page ("?page=2", "?page=3") often cannot make those guarantees when entries are being added/edited faster than the client can page through the feed.

> That said, however, once the initial sync is completed, 
> subsequent incremental sync's are much more efficient if 
> paging is not used (e.g. give me one feed document describing
> just the things that have changed over the last twelve hours, etc).

On the other hand, if there were hundreds of entries updated in the last 12 hours (e.g. a server upgrade which modifies the representation of every entry, or whatever else WordPress users do that causes every entry to appear updated), the client and the server will probably both benefit from chunking that up. Especially, on mobile phones, the larger the response, the less likely the service provider's proxies will let it go through to the device.

> Again, this would work so long as the pages remain stable; 
> however, I would very much like to see a comparison of how 
> the two approaches compare in terms of performance / efficiency.

Well, obviously paging is going to require more roundtrips if there are multiple pages used for the sync. If the server decides to use one page per resync then both approaches are equivalent. In fact, disregarding snapshotting, my solution is the same as yours, except in mine the server controls the values of the "since" and "until" parameters, whereas in yours the client controls them, and mine allows the server to break up the response into multiple (cacheable) pages.

- Brian

---

From: James M Snell <[email-masked]>
Date: Thu, 06 Dec 2007 09:43:17 -0800

Comments below.

Brian Smith wrote:
> On the other hand, if there were hundreds of entries updated in 
> the last 12 hours (e.g. a server upgrade which modifies the 
> representation of every entry, or whatever else WordPress users 
> do that causes every entry to appear updated), the client and the 
> server will probably both benefit from chunking that up. Especially, 
> on mobile phones, the larger the response, the less likely the service 
> provider's proxies will let it go through to the device.
> 

Either way, it's generally the same amount of data being transferred,
only you have to deal with multiple requests and scanning through each
page to detect which items have changed.  Even with pipelining, that's
less efficient than making a single request with a single response that
you know for certain contains only items that have been modified.

Regarding mobile devices: I may just be demonstrating my ignorance of
mobile device development, but I'd be rather surprised to find a mobile
device that would want to maintain a complete, persistent local snapshot
of a collection.  What I suspect would be most common is the device
wanting only to maintain a limited listing of the 10-20 most recently
updated posts -- something that can be achieved currently without feedsync.

> Well, obviously paging is going to require more roundtrips if there 
> are multiple pages used for the sync. If the server decides to use 
> one page per resync then both approaches are equivalent. In fact, 
> disregarding snapshotting, my solution is the same as yours, except 
> in mine the server controls the values of the "since" and "until" 
> parameters, whereas in yours the client controls them, and mine allows 
> the server to break up the response into multiple (cacheable) pages.

So long as the feeds contain only the entries that were modified within
the specified period of time then yes, without paging the approaches are
equivalent.  In other words, I want to avoid having to scan through the
entries to determine which entries have or have not changed since the
last time I looked at the feed; instead, I want to know that when I'm
syncing, ALL of the entries listed in that feed document have changed
since the last time I sync'd.

- James

---

From: James M Snell <[email-masked]>
Date: Thu, 06 Dec 2007 11:06:38 -0800

A quick note on the efficiency issue.  I just ran a quick test.  I
created 20 feed pages, each with 20 entries each.  Using the feed paging
model, I grab the first feed, scan the entries to see if they have been
deleted or updated.  Deleted entries are represented by an x:deleted
element *within the entry*.  Then I grab the next page[1], scan the
entries, grab the next, scan the entries, etc until I come to an entry
whose app:edited timestamp is earlier than the cutoff I defined (which
assumes the entries are sorted according to app:edited, which is not
guaranteed)[2].  I ran the process 100 times, throwing away the first
run because of initialization overhead.  The times (ms) for each run are:

[1681, 6114, 2049, 1923, 1657, 1596, 1634, 1676, 1630, 1635, 1790, 1610,
1900, 1639, 1604, 1809, 1763, 1775, 2040, 8441, 2126, 2229, 1713, 1687,
1812, 2012, 1722, 1770, 1734, 1683, 1625, 1613, 1622, 1617, 2130, 1687,
1675, 1867, 7261, 2006, 1661, 1610, 1662, 1584, 1686, 1753, 1632, 1629,
1808, 1691, 1631, 1756, 7585, 1660, 1638, 2671, 1702, 1872, 1593, 1895,
1606, 1692, 1647, 1987, 1750, 1880, 1708, 1793, 2160, 1654, 1854, 1931,
1613, 3006, 2041, 2319, 2493, 1654, 1713, 1619, 1588, 1765, 2046, 1579,
2308, 1940, 1820, 1996, 1655, 1603, 1863, 1723, 1628, 1575, 1645, 1568,
1860, 1700, 1864]

[1]: http pipelining is enabled.
[2]: If entries are not sorted by app:edited, things get much worse.

By comparison, I created a single snapshot feed containing exactly the
same set of modified entries.  Deleted entries are represented using an
x:deleted tombstone element rather than atom:entry elements.  The feed
ONLY contains x:deleted and atom:entry elements representative of items
updated after the cutoff I selected.  I ran the process 100 times,
throwing away the first run because of initialization overhead.  The
times (ms) for each run are:

[225, 253, 415, 208, 155, 95, 104, 66, 106, 74, 102, 76, 70, 113, 64,
68, 73, 90, 64, 101, 427, 181, 177, 58, 58, 947, 50, 46, 48, 70, 83, 89,
41, 143, 74, 101, 39, 59, 38, 41, 37, 45, 269, 40, 403, 37, 38, 37, 62,
38, 36, 64, 36, 37, 57, 36, 37, 70, 36, 38, 84, 41, 34, 50, 33, 33, 53,
130, 107, 132, 55, 37, 53, 38, 39, 88, 39, 39, 168, 95, 73, 102, 62, 48,
84, 47, 45, 133, 43, 81, 367, 55, 50, 89, 45, 67, 47, 67, 57]

The test feeds and code are located at
http://www.snellspace.com/public/feeds

- James

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 7 Dec 2007 02:17:57 +0700

James M Snell wrote:
> Either way, it's generally the same amount of data being 
> transferred, only you have to deal with multiple requests and 
> scanning through each page to detect which items have 
> changed.  Even with pipelining, that's less efficient than 
> making a single request with a single response that you know 
> for certain contains only items that have been modified.

> So long as the feeds contain only the entries that were 
> modified within the specified period of time then yes, 
> without paging the approaches are equivalent.  In other 
> words, I want to avoid having to scan through the entries to 
> determine which entries have or have not changed since the 
> last time I looked at the feed; instead, I want to know that 
> when I'm syncing, ALL of the entries listed in that feed 
> document have changed since the last time I sync'd.

The subscription page of a collection feed does not usually have a "next" link, and the only way to find new entries in a collection is to poll the subscription page of the collection feed (at the collection URI). My suggestion is: (a) the server adds a "next" link to the subscription page, that links to a document that represents all entries nwerer than the currently-newest entry, (b) the client chases these "next" links and thus never has to poll the collection URI. By doing this, the client will never encounter an entry that it already has an up-to-date copy of.

- Brian

---

From: James M Snell <[email-masked]>
Date: Thu, 06 Dec 2007 12:03:49 -0800

Ok, another test.. using the paging forward in time approach (e.g.
starting from the last page I looked at, GET each subsequent "next" page
containing entries modified since the last run as you describe below...
running 100 iterations pulling the feeds from localhost, with pipelining
enabled, the times for each run (in ms) are (first run is thrown out).

400 entries over 20 pages:

[520, 364, 593, 1092, 547, 971, 628, 769, 368, 1557, 462, 293, 495, 889,
991, 457, 559, 1040, 391, 309, 296, 325, 275, 552, 397, 303, 308, 341,
360, 299, 430, 322, 308, 321, 275, 314, 318, 332, 321, 431, 400, 488,
322, 343, 271, 369, 387, 404, 324, 464, 436, 392, 392, 1108, 320, 537,
275, 330, 302, 277, 403, 348, 265, 275, 364, 637, 351, 293, 276, 268,
275, 273, 301, 298, 557, 304, 360, 468, 368, 435, 375, 354, 331, 372,
417, 335, 485, 315, 356, 292, 288, 296, 320, 292, 384, 312, 416, 257]

400 entries in a single feed:

[204, 482, 251, 191, 577, 163, 150, 186, 223, 136, 159, 168, 170, 223,
905, 186, 166, 139, 157, 145, 283, 143, 150, 397, 144, 146, 185, 167,
313, 177, 147, 177, 143, 462, 162, 158, 136, 137, 162, 115, 265, 121,
183, 319, 121, 405, 169, 545, 163, 191, 156, 535, 146, 150, 518, 118,
144, 263, 145, 152, 132, 152, 509, 123, 165, 130, 171, 139, 135, 122,
152, 121, 128, 147, 117, 168, 141, 144, 142, 464, 578, 142, 143, 139,
143, 124, 151, 181, 214, 117, 160, 176, 134, 150, 116, 150, 150, 323, 127]

- James

Brian Smith wrote:
> The subscription page of a collection feed does not usually have a 
> "next" link, and the only way to find new entries in a collection 
> is to poll the subscription page of the collection feed (at the 
> collection URI). My suggestion is: (a) the server adds a "next" link 
> to the subscription page, that links to a document that represents all 
> entries nwerer than the currently-newest entry, (b) the client chases 
> these "next" links and thus never has to poll the collection URI. By 
> doing this, the client will never encounter an entry that it already has 
> an up-to-date copy of.
> 
> - Brian
> 
>

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 7 Dec 2007 11:35:05 +0700

> 400 entries over 20 pages:
...
> 400 entries in a single feed:

If the server can rely on the client handling 400 entries per feed, then it would not need to split the feed into twenty pages; only two pages would be needed. Conversely, if the client cannot handle a response with 400 entries in it, then the single-page-result query mechanism will always fail.

To see this more clearly, we should test the performance of ten clients simultaneously syncing 10,000 10KB entries using each approach, using a reasonable page size (say 100K compressed, to stay within the limits of many mobile devices), with caching reverse proxy in front of the AtomPub servers, and a caching proxy in front of the client, with a new entry inserted in between each client request. The single-page-result mechanism would have to generate and transmit ten unique 100MB documents, that many desktop clients wouldn't even be able to handle, whereas the paging mechanism would be able to offload most of its work to the client-side caching proxy server and still interoperate with most mobile devices.

I think we could also run the paging version from my $6.00/month shared hosting account (a CGI script gets 6 seconds to run before its process gets killed). I'm pretty sure that wouldn't be possible with the single-page-result implementation.

To summarize, the single-page-result solution might have better raw performance when not resource constrained, but the paging mechanism offers better cachability and scales up and down nicely. That is why I prefer the paging mechanism.

- Brian

---

From: James M Snell <[email-masked]>
Date: Fri, 07 Dec 2007 21:15:59 -0800

Excellent points.  The primary issue for me is the fact that the set of
entries we're synchronizing has to remain stable throughout the
synchronization process or else we risk race conditions and a variety of
 possible conflicts.  If the stability of the pages can be reasonably
guaranteed then paging is acceptable.

- James

---

From: "Brian Smith" <[email-masked]>
Date: Sat, 8 Dec 2007 22:26:36 +0700

James M Snell wrote:
> Excellent points.  The primary issue for me is the fact that 
> the set of entries we're synchronizing has to remain stable 
> throughout the synchronization process or else we risk race 
> conditions and a variety of  possible conflicts.  If the 
> stability of the pages can be reasonably guaranteed then 
> paging is acceptable.

I'm pretty sure I agree with you, but please define "stable".

- Brian