Guys, we’re doing pagination wrong…

These are the words that I had to mut­ter quite a few times in my career, at the dis­sat­is­fac­tion of how pag­i­na­tion had been imple­ment­ed on sev­er­al projects.

Still, that dis­sat­is­fac­tion is noth­ing com­pared to how I feel when I occa­sion­al­ly had to ask “why is this API not pag­i­nat­ed..?”

So, tak­ing a break from my usu­al Server­less ram­blings, let’s talk about pag­i­na­tion :-)

Unidirectional and Bidirectional Pagination

Gen­er­al­ly speak­ing, I see two com­mon types of pag­i­na­tions:

  • sim­ple, uni­di­rec­tion­al, pag­ing through a sta­t­ic set of results that are too long or inef­fi­cient to return in one go — e.g. list of twit­ter fol­low­ers, or list of Google search results
  • bidi­rec­tion­al pag­ing through a feed or stream of some sorts where new results can be added after you received the first page of results — e.g. your twit­ter time­line, or noti­fi­ca­tions

Avoid leaky abstraction

A com­mon mis­take I see is that the pag­i­nat­ed API requires the caller to pro­vide the “key” it uses to sort through the results, which cre­ates a leaky abstrac­tion. The caller must then under­stand the under­ly­ing mech­a­nism the ser­vice uses to page its results — e.g. by time­stamp, or alpha­bet­i­cal order.

DynamoDB’s Query API is a good exam­ple of this. To page through the query results, the caller must spec­i­fy the Exclu­siveS­tartKey in sub­se­quent requests. How­ev­er, the ser­vice does return the LastE­val­u­at­ed­Key in the response too.

So, in prac­tice, you can almost treat the LastE­val­u­at­ed­Key as a token, or cur­sor, which you sim­ply pass on in the next request. Except, it’s not just a token, it’s an actu­al sort key in the DynamoDB table, and the attribute names already gave the imple­men­ta­tion details away any­way.

On its own, this is not a big deal. How­ev­er, it often has the unfor­tu­nate­ly knock-on effect of encour­ag­ing appli­ca­tion devel­op­ers to build their appli­ca­tion lev­el pag­i­na­tions on top of this imple­men­ta­tion detail. Except this time around, they’re not return­ing the LastE­val­u­at­ed­Key in the response and the client is now respon­si­ble for track­ing that piece of infor­ma­tion.

Con­grat­u­la­tions, the under­ly­ing mechan­ic your data­base uses to sup­port pag­i­na­tion has now leaked all the way to your front end!

Make paging intent explicit and consistent

Anoth­er com­mon trend I see is that you have to send the same request para­me­ters to the pag­i­nat­ed API over and over, for exam­ple:

  • max no. of results per page
  • the direc­tion of pag­i­na­tion (if bidi­rec­tion­al)
  • the orig­i­nal query (in DynamoDB’s case, this includes a no. of attrib­ut­es such as Fil­ter­Ex­pres­sionKey­Con­di­tion­Ex­pres­sionPro­jec­tion­Ex­pres­sion and Index­Name)

I won’t call this one a mis­take as it is some­times by design, but more often than not it strikes me as a con­se­quence of lack of design instead.

In all the pag­i­nat­ed APIs I have encoun­tered, the intend­ed behav­iour is always to fetch the next set of results for a query, not to start a dif­fer­ent query mid­way through. That just wouldn’t make sense, and you prob­a­bly can’t even call that pag­i­na­tion, more like nav­i­ga­tion! I mean, when was the last time you start a DynamoDB query, and then have to change any of the request para­me­ters mid­way through pag­i­nat­ing through the results?

That said, there are legit­i­mate rea­sons for chang­ing the direc­tion of pag­i­na­tion from a pre­vi­ous­ly received page. More on this when we dis­cuss bidi­rec­tion­al pag­ing fur­ther down the arti­cle.

Unidirectional paging with cursor

For uni­di­rec­tion­al pag­i­na­tion, my pre­ferred approach is to use a sim­ple cur­sor. The impor­tant detail here is to make the cursor mean­ing­less.

As far as the client is con­cerned, it’s just a blob the serv­er returns in the response when there are more results to fetch. The client shouldn’t be able to derive any imple­men­ta­tion details from it, and the only thing it can afford to do with this cursor is to send it along in the next request.

fig. 1 — flow of request & respons­es for a series of pag­i­nat­ed requests

But how does the API know where to start fetch­ing the next page from?

A sim­ple way to do this is:

  1. cre­ate a JSON object to cap­ture the data need­ed to fetch next page — e.g. if you’re using DynamoDB, then this can be the request object for the next page (includ­ing the ExclusiveStartKey)
  2. base64 encode the JSON string
  3. return the base64 blob as cursor

When we receive the request to fetch the next page, we can apply the reverse process to get back the request object we cre­at­ed ear­li­er.

Isn’t that gonna leak even more infor­ma­tion — e.g. that you’re using DynamoDB, the table name, the schema, etc. — if some­one just base64 decode your blob?

Absolute­ly, which is why you might also choose to encrypt the JSON first. You also don’t have to use the DynamoDB query request as base.

Notice in both fig. 1 and fig. 2 the client only sends the cursor in the sub­se­quent requests?

This is by design.

As I men­tioned ear­li­er, the client has already told us the query in the first request, the pag­i­na­tion mech­a­nism should only pro­vide a way for fetch­ing sub­se­quent pages of the results.

Which, to me, means it should not afford any oth­er behav­iour (there is that word again, read here to see how the idea of affor­dance applies to API design) and there­fore do not require any oth­er infor­ma­tion besides the cursor from the pre­vi­ous response.

This in turn, means we need to cap­ture the orig­i­nal query, or intent, in the cursor so we can con­struct the cor­re­spond­ing DynamoDB request. Or, we could just cap­ture the actu­al DynamoDB request in the cursor which seems like a sim­ple, prac­ti­cal solu­tion here.

fig. 2 — inter­ac­tion between client, API and DynamoDB

Bidirectional paging with cursor(s)

With bidi­rec­tion­al pag­ing, you need to be able to page for­ward in time (when new tweets are added to your time­line) as well as back­ward (to fetch old­er tweets). So a sim­ple string cursor would no longer suf­fice, instead we need 2 cur­sors, one for each direc­tion, for exam­ple…

  "before": "ThlNjc5MjUwNDMzMA...",
  "after": "ADfaU5ODFmMWRiYQ..." 

Addi­tion­al­ly, when pag­ing for­ward, even when there are no more results right now we still have to return a cur­sor as new results can be added to the feed lat­er. So we should also include a pair of boolean flags in the response.

  "before": "ThlNjc5MjUwNDMzMA...",
  "hasBefore": true,
  "after": "ADfaU5ODFmMWRiYQ...",
  "hasAfter": true

When the client pages for­ward in time and receives hasAfter as false then it knows there are no more results avail­able right now. It can there­fore stop active­ly fetch the next page of results, and be more pas­sive and only poll for new results peri­od­i­cal­ly.

Let’s run through a sim­ple exam­ple, imag­ine if you’re fetch­ing the tweets in your time­line where the API would return the lat­est tweets first.

fig. 3 — pag­i­nate back­ward in time to fetch old­er data
  1. the client makes a first request
  2. API responds with a cursor object, hasAfter is false because the API has respond­ed with the lat­est results, but hasBefore is true as there are old­er results avail­able
  3. the client makes a sec­ond request and pass­es only the before cur­sor in the request, mak­ing its inten­tion clear and unam­bigu­ous
  4. API responds with anoth­er cursor object where this time both hasBeforeand hasAfter are true giv­en that we’re right in the mid­dle of this stream of results
  5. the client makes a third and last request, again pass­ing only the beforecur­sor received from the pre­vi­ous response
  6. API responds with a cursor object where hasBefore is false because we have now received the old­est result avail­able

Ok, now let’s run through anoth­er exam­ple, this time we’ll page for­ward in time instead.

fig. 4 — pag­i­nate for­ward in time to fetch new­er data
  1. the client makes a first request
  2. API responds with a cursor object, hasAfter is false because the API has respond­ed with the lat­est results, but hasBefore is true as there are old­er results avail­able
  3. some time has passed, and more results have become avail­able
  4. the client makes a sec­ond request, and pass­es only the after cur­sor in the request, mak­ing its inten­tion clear and unam­bigu­ous
  5. API responds with only the new­er results that the client has not received already, and cursor.hasAfter is false as these are the lat­est results avail­able at this moment in time; should the client page back­ward (in time) from this response then it’ll receive the same results as the first response from the API

Now, let’s cir­cle back to what I men­tioned ear­li­er regard­ing the occa­sion­al need to change direc­tion mid­way through pag­i­na­tion.

The rea­son we need pag­i­na­tion is because it’s often imprac­ti­cal, inef­fi­cient and in some cas­es impos­si­ble to return all avail­able results for a query — e.g. at the time of writ­ing Katy Per­ry has 108M Twit­ter fol­low­ers, try­ing to retrieve all her fol­low­ers in one request-response cycle would have crashed both the serv­er and the client app.

Besides lim­it­ing how much data can be returned in one request-response cycle, we also need to place a upper bound on how much data the client app would cache in order to pro­tect the user expe­ri­ence and pre­vent the client app from crash­ing.

That means, at some point, as the user keeps scrolling through old­er tweets, the client would need to start drop­ping data it has already fetched or risk run­ning out of mem­o­ry. Which means, when the user scrolls back up to see the lat­est tweets, the client would need to re-fetch pages that had been dropped and hence revers­ing the orig­i­nal direc­tion of the pag­i­na­tion.

For­tu­nate­ly, the scheme out­lined above is flex­i­ble enough and allows you to do just that. Every page of results has an asso­ci­at­ed cursor that allows you to fetch the next page in either direc­tion. So, in the case where you need to re-fetch a dropped page, it’s as sim­ple as mak­ing a pag­i­nat­ed request with the after cur­sor of the lat­est page you have cached.

Dealing with “gaps”

Stay­ing with the Twit­ter exam­ple. If you open up the Twit­ter mobile app after some time, you’ll see the tweets that has already been cached but the app also rec­og­nizes that a lot of time has passed that it’s not fea­si­ble to pag­i­nate from the cached data all the way to the lat­est.

Instead, the client would fetch the lat­est tweets with a non-pag­i­nat­ed request. As you scroll down, the client can auto­mat­i­cal­ly fetch old­er pages as per fig. 3 and grad­u­al­ly fill in the gap until it joins up with the cached data.

The behav­iour of the Twit­ter mobile app has changed over time, and anoth­er tac­tic I have seen is to place a visu­al (click­able) mark­er for the miss­ing tweets in the time­line. This makes it an explic­it action by the user to start pag­ing through old­er tweets to fill in the gap.

So there you have it, a sim­ple and effec­tive way to imple­ment both uni­di­rec­tion­al and bidi­rec­tion­al pag­i­nat­ed APIs, hope you have found it use­ful!