Live data from Hacker News

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

brandur.org

41–50 of 51 posts

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

#41
post #18

Earlier quoted context omitted.

We provide (internal) access to data where we provide interactive access via GraphQL-based APIs and bulk access via CSV or RDF dumps - I feel like dump files are grossly undervalued these days.

I agree. I am going to reflect on this and see if there's a way to support dump files long term in our app. We sorta support it today but it's ad hoc implementation since an export can range from a few hundred of a thing to tens of millions of a thing. Is there any good literature or patterns on supporting dumps in the tens of millions or larger? I wrote a sheets plug-in that uses our cursor API to provide a full dum…

"Is there any good literature or patterns on supporting dumps in the tens of millions or larger?"

The two main things you need are: 1. HTTP is a streaming protocol. You don't need to fully manifest a response in memory before you send it. If your framework forces that, bypass it for this particular call. (If you can't bypass it... your framework choice is now a problem for you.)

2. You presumably have some sort of JSON encoder in your language. As long as it doesn't have some sort of hard-coded "close the stream once we send this JSON" behavior (and if so, file a bug because a JSON encoder has no business doing that), all you have to do is ensure that the right bytes go out on the wire. You, again, don't have to fully manifest the reply in memory before you encode it. Something like:

    stream.Write("[")
    needComma = False
    for item in toBeSerialized:
        if needComma:
            stream.Write(",")
        json.Write(stream, item)
        needComma = True
    stream.Write("]")
A lot of times when you're emitting gigabytes of JSON it's still in lots of little chunks where each individual chunk isn't a memory problem on its own, so doing something like this can be very memory-efficient, especially if "toBeSerialized" is itself something like a cursor coming out of a DB where it itself is not manifesting in memory. (Newlines are also a good idea if your JSON encoder isn't naturally doing it already; helps debugging a lot for very little cost.)

JSON objects can be more annoying; you may need to manually deserialize one and that's more annoying. Protip: Whenever possible, use the JSON encoder in your language; there is no shame or anything in using the JSON encoder to emit strings corresponding to the keys of your object. Much like HTML, you need to be very careful writing things directly to the stream; it really always should go through the encoder. I even send constant strings through the encoder just to make the code look right.

The last little tidbit is that the HTTP software stack will tend to fight you on the matter of keeping long-lived connections open. There can be a lot of places that have timeouts you may want to extend. If this gets too big you may need to do something other than HTTP. You may also need to consider detecting failures (hashing or something) and the ability to restart. (Although don't underestimate modern bandwidth and the speed you can iterate through SELECT -type queries; definitely check into the virtues of just retrying. 10GB/year of extra bandwidth and processing power is still cheaper than a developer even designing* a solution to that problem, let alone implementing and testing it.)

Oh, and if you can use HTTP, be sure you're gzip'ing. It's dirt cheap nowadays on the CPU; only in extreme situations of bandwidth abundance and CPU shortage can it be worth skipping. My rule-of-thumb on JSON shrinking is about 15:1. CSVs don't quite shrink that much but they still shrink down pretty well.

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

#42

Earlier quoted context omitted.

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?

That's one way, for sure. You can do this with IDs, dates, etc.

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

#43
post #41
post #18

Earlier quoted context omitted.

I agree. I am going to reflect on this and see if there's a way to support dump files long term in our app. We sorta support it today but it's ad hoc implementation since an export can range from a few hundred of a thing to tens of millions of a thing. Is there any good literature or patterns on supporting dumps in the tens of millions or larger? I wrote a sheets plug-in that uses our cursor API to provide a full dum…

"Is there any good literature or patterns on supporting dumps in the tens of millions or larger?" The two main things you need are: 1. HTTP is a streaming protocol. You don't need to fully manifest a response in memory before you send it. If your framework forces that, bypass it for this particular call. (If you can't bypass it... your framework choice is now a problem for you.) 2. You presumably have some sort of JS…

Thanks for this. It seems obvious reading it but I haven't thought about it this way before. I'm definitely going to explore these concepts!

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

#44
post #21

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…

Pagination for a one-page-query is rarely the same cost in my experience, in real-world scenarios.

In very simple cases, like a single table sql query, absolutely - databases effectively have to compute the full result, sort it, and return a window. There's almost no reason to paginate here, at an API level, unless the consumer wants only a subset (say, bandwidth limitations). Sending it all at once can be a huge benefit for those that will use it all, it's both simpler and faster for all parties.

But in most real-world cases, there are at least two additional details that can add significant response time: joins (when not involved in sorting) and additional data-gathering needed to fully build the response (e.g. getting data from other systems, internal or external). Joined data is not typically loaded prior to computing limit/offset since it may be a massive waste, and external data is effectively the same issue but with far higher latency.

And that's before getting into other practical issues, e.g. systems that can't process the response stream as it comes in - a subset will load-and-return faster than the whole content in all cases, so e.g. a website loading some json can show initial UI faster while loading more in the background. Streaming is often possible and that'll negate a lot of the downsides, but it's far less common than processing a request only after it completes.

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

#45
post #21

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 disagree. I've seen too many cases of api users that are overfetchting for no reason. I don't mind providing a bulk api, but that is a very different use case that regular endpoints shouldn't have to support.

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

#46

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

No, what is bullshit is having the option to go to page 10 in the first place. If the user does that then the UI is already broken. What is needed is good filter abilities.

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

#47
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…

I hardly imagine consistent integral paginated data view without creating a snapshot. I would be manual MVCC implementation or something. Separate API seems a much simpler solution to me.

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

#48

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…

>a way where this information could be obtained in a query

There's no standard way because index implementation details are hidden for a reason.

>in e.g. postgres

You can query pg_stats view (histogram_bounds column in particular) after statistics are collected.

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

#49
post #46

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

No, what is bullshit is having the option to go to page 10 in the first place. If the user does that then the UI is already broken. What is needed is good filter abilities.

Filtering is an orthogonal concern to this, I'm not advocating against filtering. Sometimes you don't know what you're looking for, and you will go insane if you're not sure if the thing you want is on page 8 or 12 if you have to keep clicking "next/prev" to get between them.

Another way to put what you're saying is essentially that the user should never have more than one page of results. Putting it that way kind of shows that it's not really a solution

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

#50
post #41
post #18

Earlier quoted context omitted.

I agree. I am going to reflect on this and see if there's a way to support dump files long term in our app. We sorta support it today but it's ad hoc implementation since an export can range from a few hundred of a thing to tens of millions of a thing. Is there any good literature or patterns on supporting dumps in the tens of millions or larger? I wrote a sheets plug-in that uses our cursor API to provide a full dum…

"Is there any good literature or patterns on supporting dumps in the tens of millions or larger?" The two main things you need are: 1. HTTP is a streaming protocol. You don't need to fully manifest a response in memory before you send it. If your framework forces that, bypass it for this particular call. (If you can't bypass it... your framework choice is now a problem for you.) 2. You presumably have some sort of JS…

IMO it's better to use JSONL[1].

Also back in the day IBM had XML for Logging format, where every separate line was an XML fragment [2].

Most markup languages suffering of having a root element, which prevents efficient logging or steaming.

[1] https://jsonlines.org/

[2] https://en.wikipedia.org/wiki/XML_log

Post reply on HN