Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

brandur.org

Post reply on HN
Print view View original

31–40 of 51 posts

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

#31

Post by eyelidlessness »

ako wrote: post #22
eyelidlessness wrote: post #20

Earlier quoted context omitted.

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.

I think we’re almost on the same page (heh). Pagination may still make sense for a variety of reasons. Even if there’s no meaningful sever optimization gain, clients may benefit from a reduced response size (mobile, expensive data plans, low power devices). That sort of thing is where ensuring consistency (for the sake of brevity I’ll repeat, at a point in time, but there are other ways to allow clients to negotiate this) at the request level over multiple requests is useful, even if the underlying data is changing much faster than the client is consuming it.

It’s worth noting here that this isn’t just applicable to paginated lists. It can also be used where you want to let the client optionally, concurrently access related resources. It can be used for client-side concurrent transactional writes. It’s a barrel of monkeys.

For what it’s worth, I wouldn’t assume their volume of traffic was necessarily the reason the data was in such flux. It could be (and I strongly suspect) that their popularity algorithm just stinks (eg weighting 100% of 1 view over 90% of 100 views). Even so, a snapshot in time is probably a much easier lift/gain for a flailing algorithm than really digging into the data and analytics to get an optimal stable sort without it:

1. Take a snapshot of the query and throw it in a dumb cache.

2. Rate limit cache key creation rather than cache hit requests.

3. Throw the caches out (and repopulate if reasonable) every [vaguely not gonna break the bank age duration].

4. Forget about any further optimization unless you reallllly need it.

5. Document the problems with the suboptimal solution, have a retro so your junior devs can develop better instincts, get them onto the next user story.

6. Put a “should we improve this” on the backlog of backlogs.

7. Profit.

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

#32

Post by eyelidlessness »

tshaddox wrote: post #7
sb8244 wrote: post #6

Earlier quoted context omitted.

> If they wanted to make it easy to get all the results Speaking from experience...we want to make it easy but also want to keep it performant. Getting the data all in one go is generally not performant and is easy to abuse as an API consumer. For example, always asking for all of the data rather than maintaining a cursor and secondary index (which is so much more performant for everyone involved).

That’s the point. Running multiple paginated queries in parallel is essentially circumventing the API provider’s intent to limit the number of items requested at one time.

If your API doesn’t support a single client making ~6 concurrent requests, let me tell you about browsers since the last millennium.

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

#33

Post by juancn »

draw_down wrote: post #3

> it uses offsets for pagination... understood to be bad practice by today’s standards. Although convenient to use, offsets are difficult to keep performant in the backend This is funny. Using offsets is known to be bad practice because.... it’s hard to do. Look I’m just a UI guy so what do I know. But this argument gets old because I’m sorry, but people want a paginated list and to know how many pages are in the lis…

The hardest part is to be able to parallelize the sorts in the backend and keep the working sets reasonably sized.

If you ask for "first 50 items after key X", you just need to keep a priority queue of size 50 on each BE node and merge them before returning them (I'm assuming a distributed backend). It doesn't matter on which page you are.

But if you specify "first 50 items after element N" it gets really tricky, each BE shard needs to sort the first N elements, and it can use some trickery to avoid doing a naive merge (see: https://engineering.medallia.com/blog/posts/sorting-and-pagi... ).

You can at most save some transfer over the network.

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

#34

Post by juancn »

alexchamberlain wrote: post #17
draw_down wrote: post #3

> it uses offsets for pagination... understood to be bad practice by today’s standards. Although convenient to use, offsets are difficult to keep performant in the backend This is funny. Using offsets is known to be bad practice because.... it’s hard to do. Look I’m just a UI guy so what do I know. But this argument gets old because I’m sorry, but people want a paginated list and to know how many pages are in the lis…

I can't find one right now, but I feel like there must be an algorithm that can identify the key that can be used for each page, yet cheaper than a full sort (ie cheaper than offset pagination in generality). Of course, a skip list would work for a secondary index.

This is the best one I've been able to come up with: https://engineering.medallia.com/blog/posts/sorting-and-pagi...

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

#35

Post by cunac »

corty wrote: post #21
eyelidlessness wrote: post #8

Earlier quoted context omitted.

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 ineffi…

my intent with pagination is always to prevent problems with open ended size of data set. 1000 at once is usually not a problem but 10x , 100x etc.. is a big problem for transferring over the wire.

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

#36

Post by tshaddox »

eyelidlessness wrote: post #32
tshaddox wrote: post #7

Earlier quoted context omitted.

That’s the point. Running multiple paginated queries in parallel is essentially circumventing the API provider’s intent to limit the number of items requested at one time.

If your API doesn’t support a single client making ~6 concurrent requests, let me tell you about browsers since the last millennium.

It’s not about what the API provider can physically support, it’s just about being a polite client. They probably can support 6 concurrent requests without it causing a problem. The point is that if they use offset or page number pagination with a maximum limit of 100, that’s probably a clue that you shouldn’t preemptively grab the first 100 pages in parallel.

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

#37

Post by gkop »

tshaddox wrote: post #36
eyelidlessness wrote: post #32

Earlier quoted context omitted.

If your API doesn’t support a single client making ~6 concurrent requests, let me tell you about browsers since the last millennium.

It’s not about what the API provider can physically support, it’s just about being a polite client. They probably can support 6 concurrent requests without it causing a problem. The point is that if they use offset or page number pagination with a maximum limit of 100, that’s probably a clue that you shouldn’t preemptively grab the first 100 pages in parallel.

It’s not hard to imagine scenarios where an API provider might reasonably prefer n concurrent requests of m batch size over a single request of n * m batch size.

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

#38

Post by eyelidlessness »

tshaddox wrote: post #36
eyelidlessness wrote: post #32

Earlier quoted context omitted.

If your API doesn’t support a single client making ~6 concurrent requests, let me tell you about browsers since the last millennium.

It’s not about what the API provider can physically support, it’s just about being a polite client. They probably can support 6 concurrent requests without it causing a problem. The point is that if they use offset or page number pagination with a maximum limit of 100, that’s probably a clue that you shouldn’t preemptively grab the first 100 pages in parallel.

Right, that’s my point. Don’t be overzealous obviously. But some concurrency should be expected (and in my opinion designed for and encouraged). There’s a huge gulf between grabbing 100 pages and grabbing the number of resources a browser grabs by default.

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

#39

Post by eyelidlessness »

gkop wrote: post #37
tshaddox wrote: post #36

Earlier quoted context omitted.

It’s not about what the API provider can physically support, it’s just about being a polite client. They probably can support 6 concurrent requests without it causing a problem. The point is that if they use offset or page number pagination with a maximum limit of 100, that’s probably a clue that you shouldn’t preemptively grab the first 100 pages in parallel.

It’s not hard to imagine scenarios where an API provider might reasonably prefer n concurrent requests of m batch size over a single request of n * m batch size.

I can more than imagine it, I design for it. Concurrent all the things. The vast majority of GET workloads are either embarrassingly parallel or so badly designed that they fall over with even the gentlest touch (which I’m sad to say I’ve encountered; services falling over from sequential requests!).

Edit to add: this isn’t some wild idea, recent network and web standards have made increasing concurrency both automatic (HTTP/2 and beyond) and tunable (various prefetch APIs).

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

#40

Post by jerf »

corty wrote: post #21
eyelidlessness wrote: post #8

Earlier quoted context omitted.

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 ineffi…

Strongly agree. I have an API I work on where if you ask for a couple of gigabytes of data, it'll send it to you, because if you're asking for it, that's what you want. It gets streamed out, and the docs warn you that you will get exactly what you asked for, so you may want to chunk up on your side (for this particular API there is a trivial way for clients to do that), or if you can handle a full stream, go nuts.

Pagination would just complicate things. I think with most APIs, intended as APIs (i.e., not just an endpoint primarily meant to feed a front-end page), you're better off thinking of your default as "I'm going to just stream everything they ask for", and look for reasons why that won't work, rather than start from the presumption that everything must be paginated from the beginning.

Don't get me wrong; there are plenty of solid reasons to paginate. You may discover one applies to your API. But if you can leave it out, it's often simpler for both the producer and the consumer. Wait until you find the need for it. Plus, if that happens, you'll have a better understanding of the actual problem you need to solve and better solutions may reveal themselves.

Post reply on HN