What's good about offset pagination; designing parallel cursor-based web APIs • Hacker News Board

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#21

Post by corty » Sun, Jan 03, 2021, 9:40 PM UTC

eyelidlessness wrote: post #8

gampleman wrote: post #5

To point out the obvious: generally API providers don’t particularly want you to pararelize your request (they even implement rate limiting to make it harder on purpose). If they wanted to make it easy to get all the results, they would allow you to access the data without pagination - just download all the data in one go.

A certain level of parallelism is generally within the realm of good API citizenship. Even naive rate limiting schemes tend to permit a certain number of concurrent requests (as they well should, since even browsers may perform concurrent requests without any developer intervention). Rate limiting and pagination aren’t (necessarily) about making full data consumption more difficult. They’re more often about optimizin…

One thing that frequently bugs me is APIs limiting number of items per page for reasons of efficiency. I can perfectly understand low limits for other reasons, like not helping people scrape your data.

But limiting for efficiency is usually done in a way that I would call a cargo cult: First, the number of items per "page" is usually a number one would pick per displayed page, in the range of 10 to 20. This is inefficient for the general case, the amount of data transmitted is usually just the same size as the request plus response headers. So if the API isn't strictly for display purposes, pick a number of items per page that gives a useful balance between not transmitting too much useless data, but keeping query and response overhead low. Paginate in chunks of 100kB or more.

In terms of computation and backend load, pagination can be as expensive for a 1-page-query as for a full query. Usually this occurs when the query doesn't directly hit an index or similar data structure where a full sweep over all the data cannot be avoided. So think and benchmark before you paginate, and maybe add an index here and there.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#22

Post by ako » Sun, Jan 03, 2021, 10:03 PM UTC

eyelidlessness wrote: post #20

ako wrote: post #15

Earlier quoted context omitted.

This doesn't sound like a "temporal consistency" problem, rather an inconsistent and untransparent ordering issue.

Huh? It’s absolutely a temporal consistency problem. The ordering was absolutely clear and consistent (most->least popular at time of request). But the popularity scores were changing so rapidly that “at time of request” makes the ordering unstable . If the ordering was determined by popularity at the time I accessed page 1, the ordering would have been stable. Sure, that popularity score would be stale. But who care…

Ok, thanks for the explanation. I hadn't expected the popularity score to be so unstable. Means that a lot of users are concurrently scoring the fonts, and that the averages are continuously being recalculated. Unexpected.

But you're right, if the dataset is continuously changing at high frequency, pagination makes no sense.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#23

Post by ppeetteerr » Sun, Jan 03, 2021, 10:04 PM UTC

Pagination of an immutable collection is one thing and can be parallelized. Pagination of a mutable collection (e.g. a database table), on the other hand, is risky since two requests might return intersecting data if new data was added between the requests being executed.

True result sets require relative page tokens and a synchronization mechanism if the software demands it.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#24

Post by simonw » Sun, Jan 03, 2021, 10:20 PM UTC

ppeetteerr wrote: post #23

Pagination of an immutable collection is one thing and can be parallelized. Pagination of a mutable collection (e.g. a database table), on the other hand, is risky since two requests might return intersecting data if new data was added between the requests being executed. True result sets require relative page tokens and a synchronization mechanism if the software demands it.

Intersecting data is fine provided there's a unique ID for each result that can be used to de-duplicate them.

Ideally I'd want a system that guarantees at-least-once delivery of every item. I can handle duplicates just fine, what I want to avoid is an item being missed out entirely due to the way I break up the data.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#25

Post by arcbyte » Sun, Jan 03, 2021, 10:21 PM UTC

I think you could accomplish something similar with token pagination by requesting a number of items that will result in multiple "pages" for your user interface. Then as the user iterates through you can request additional items. This isn't parallelizing, but provides the same low-latency user experience.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#26

Post by ppeetteerr » Sun, Jan 03, 2021, 10:43 PM UTC

simonw wrote: post #24

ppeetteerr wrote: post #23

Pagination of an immutable collection is one thing and can be parallelized. Pagination of a mutable collection (e.g. a database table), on the other hand, is risky since two requests might return intersecting data if new data was added between the requests being executed. True result sets require relative page tokens and a synchronization mechanism if the software demands it.

Intersecting data is fine provided there's a unique ID for each result that can be used to de-duplicate them. Ideally I'd want a system that guarantees at-least-once delivery of every item. I can handle duplicates just fine, what I want to avoid is an item being missed out entirely due to the way I break up the data.

It's more than just de-duplicating, tho. Imagine you query a dataset and get something like a page count and a chunk size. That page count cannot be trusted if the dataset is mutable. If an item is inserted at the beginning of the set, you're going to miss the last item.

Pagination is hard

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#27

Post by the_arun » Sun, Jan 03, 2021, 10:52 PM UTC

ppeetteerr wrote: post #26

simonw wrote: post #24

Earlier quoted context omitted.

Intersecting data is fine provided there's a unique ID for each result that can be used to de-duplicate them. Ideally I'd want a system that guarantees at-least-once delivery of every item. I can handle duplicates just fine, what I want to avoid is an item being missed out entirely due to the way I break up the data.

It's more than just de-duplicating, tho. Imagine you query a dataset and get something like a page count and a chunk size. That page count cannot be trusted if the dataset is mutable. If an item is inserted at the beginning of the set, you're going to miss the last item. Pagination is hard

For dynamic usecase, DynamoDB has implemented pagination with something called lastEvaluatedKey - https://docs.aws.amazon.com/amazondynamodb/latest/developerg...

This is different from LIMIT in RDBMS

Wouldn’t this pattern solve the complexity you are talking about?

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#28

Post by felixhuttmann » Sun, Jan 03, 2021, 10:54 PM UTC

A few thoughts:

1) AWS dynamodb has a parallel scanning functionality for this exact use case. https://docs.aws.amazon.com/amazondynamodb/latest/developerg...

2) A typical database already internally maintains an approximately balanced b-tree for every index. Therefore, it should in principal be cheap for the database to return a list of keys that approximately divide the keyrange into N similarly large ranges, even if the key distribution is very uneven. Is somebody aware of a way where this information could be obtained in a query in e.g. postgres?

3) The term 'cursor pagination' is sometimes used for different things, either referring to an in-database concept of cursor, or sometimes as an opaque pagination token. Therefore, for the concept described in the article, I have come to prefer the term keyset pagination, as described in https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin.... The term keyset pagination makes it clear that we are paginating using conditions on a set of columns that form a unique key for the table.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#29

Post by gigatexal » Sun, Jan 03, 2021, 11:21 PM UTC

mssundaram wrote: post #19

gigatexal wrote: post #11

From the code sample in the article I didn’t know you could append to a slice from within a go func

As long as you use the mutex locks

Of course. I see that now it’s so obvious not sure why I didn’t see that earlier.

Re: What's good about offset pagination; designing parallel cursor-based web APIs

#30

Post by eyelidlessness » Mon, Jan 04, 2021, 12:10 AM UTC

adontz wrote: post #4

I believe data export and/or backup should be a separate API, which is low priority and ensures consistency. Here we just see regular APIs are being abused for data export. I'm rather surprised the author did not face rate limiting.

Coming from a REST perspective, I wouldn’t implement a separate API, I would use HTTP semantics (eg headers or, if truly necessary query params) on the resource listing to indicate the export/sync intention. Likely with an Accept header. If pagination is still preferred/required, the service could return an ETag or some other continuation token which when provided in subsequent responses could be used to indicate the consistent snapshot being requested. Since this is entirely optional, clients could use this mechanism to opt into stable/parallelizable requests (as I described in less specificity in another sub thread).

At this point, it these requests are expensive you have an opportunity to use a very simple (and optimistic) cache for good faith API users, relegate rate limiting to prevent abuse of cache creation (which should be even easier to detect than just overzealous parallelism), and even use the same or similar semantics to implement deltas for subsequent export/sync.