7 ms·

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

• felixhuttmann 6y ago
  A few thoughts: 1) AWS dynamodb has a parallel scanning functionality for this exact use case. https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/Scan.html#Scan.ParallelScan 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-paginate/ 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.
  • ComodoHacker 6y ago
    >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.
• ppeetteerr 6y ago
  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.
  • simonw 6y ago
    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.
    • ppeetteerr 6y ago
      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
      • the_arun 6y ago
        For dynamic usecase, DynamoDB has implemented pagination with something called lastEvaluatedKey - https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/Query.Pagination.html 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?
        • ppeetteerr 6y ago
          That's one way, for sure. You can do this with IDs, dates, etc.
• arcbyte 6y ago
  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.
• jasonhansel 6y ago
  It's important here that "created" is an immutable attribute. Otherwise you could get issues where the same item appears on multiple lists (or doesn't appear at all) because its attributes changed during the scanning process.
• draw_down 6y ago
  > 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 list. Clicking “next page” 10 times instead of clicking to page 10 is bullshit, and users know it.
  • alexchamberlain 6y ago
    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.
    • juancn 6y ago
      This is the best one I've been able to come up with: https://engineering.medallia.com/blog/posts/sorting-and-paging-on-distributed-data/ https://engineering.medallia.com/blog/posts/sorting-and-pagi...
  • juancn 6y ago
    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-paging-on-distributed-data/ https://engineering.medallia.com/blog/posts/sorting-and-pagi... ). You can at most save some transfer over the network.
  • yxhuvud 6y ago
    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.
• adontz 6y ago
  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.
  • eyelidlessness 6y ago
    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.
    • adontz 6y ago
      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.
      • eyelidlessness 6y ago
        How would a separate API solve the consistency problem? Because it doesn’t paginate? A different accept/content-type can deliver the same thing without multiplying the location of a resource. As far as consistency with pagination, it’s fairly trivial if you always have a snapshot, eg with simple historical data (which has a zillion other benefits as well).
• gampleman 6y ago
  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.
  • sb8244 6y ago
    > 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).
    • alexchamberlain 6y ago
      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.
      • sb8244 6y ago
        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 dump into a spreadsheet. Our professional services team is in love with it, so I bet they'd love generic data export capability.
        • jerf 6y ago
          "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.
• eyelidlessness 6y ago
  I think keeping temporal history and restricting paginated results to the data at the point in time where the first page was retrieved would be a pretty decent way to solve offset based interfaces (regardless of the complexity of making the query implementation efficient). Data with a lot of churn could churn on, but clients would see a consistent view until they return to the point of entry. Obviously this has some potential caveats if that churn is also likely to quickly invalidate data, or revoke sensitive information. Time limits for historical data retrieval can be imposed to help mitigate this. And individual records can be revised (eg with bitemporal modeling) without altering the set of referenced records.
  • ako 6y ago
    I think for most use cases, as a user i'd rather see the newest items in a list, then consistency of pagination. If i forget to manually refresh, i might miss out on important new items. Why do you think it is important for users to have temporal consistency?
    • eyelidlessness 6y ago
      Well I’ll use a recent example I encountered that was actually very frustrating. I was looking for a font to use for a logo for a personal project. The site I was using (won’t name and shame, and I can’t recall the site now anyway) had no sorting options, items were ordered by whatever “popularity” formula they use. As I paginated, many of the fonts I’d previously viewed would appear on subsequent pages, often in a different order. It was frustrating not just because I could tell that I was probably missing fonts that were being bumped up to previous pages, but also because it made me doubt my mental model of my own browsing history: “Did I navigate back too far? Did I forget a tangential click and end up on a different search path?” It’s not a great UX. And in some ways I suspect that my own views were at least partially causing it, which made me more hesitant to even click on anything unless I was sure it was worth the disruption.
      • ako 6y ago
        This doesn't sound like a "temporal consistency" problem, rather an inconsistent and untransparent ordering issue.
• gigatexal 6y ago
  From the code sample in the article I didn’t know you could append to a slice from within a go func
  • mssundaram 6y ago
    As long as you use the mutex locks
    • gigatexal 6y ago
      Of course. I see that now it’s so obvious not sure why I didn’t see that earlier.