Time based pagination

Abstract: How to paginate ordered list that grow quickly over time (chats, logs, messages, emails, etc)

Recently, while I was working on Meet4tea, I had to find a way to paginate a chat conversation. The classic approach to pagination wasn’t working and we had to find a better way.

Classic pagination

The classic approach to pagination is something like this:

//Client
messages = server.getChatMessages(page)

//Server
getChatMessages(page) ->
  perPage = 5
  from = (page-1) * perPage
  to = from + perPage
  return queryDatabase(from, to)

Now let’s see what happens when a user request the first page and then move to the second page

The first request retrieve the most recent 5 elements

The second request retrieve the second group of 5 elements

Classic pagination – the problems

1) A message arrive after user requested page 1

The first request retrieve the most recent 5 elements

“6” will be duplicated (in case of on scroll loading the client need to identify duplicates and the user will see one item less then expected)

2) It’s hard to request for new messages (sockets or server events would fix the problem too)

• The client has to request the first page once in a while and check if it contains new messages
• If there are new messages it should check if all of them arrived (in case 6 messages arrived between the 2 requests) and it should keep requesting messages unless one known message is found

TimeBased pagination

Requisites:

• Every message has a timestamp (or an index of sort)
• Insertion in the middle are not possible, new messages can only be pushed at the end

Let’s go back to our example

//Client
//Get the most recent messages
messages = server.getChatMessages()

//Server
//Default time to now and direction to backward - the first request gets the newest messages
getChatMessages(time = Date.now(), direction = 'backwards') ->
  limit = direction == 'backwards' ? 5 : 100
  return queryDatabase(orderByTime, timeIfBackwards, limit)

If the client need older messages

//Client
messages = server.getChatMessages(6, backwards)

We will retrieve:

If the client need to check for newer message

//Client
messages = server.getChatMessages(10, onwards)

Nothing to retrieve

//Client
messages = server.getChatMessages(10, onwards)

If a new element arrive we can retrieve only the new one

Why not limiting on new messages?
If the user receive 20 new messages in the current chat we are sure they are all relevant to him, so we want to retrieve all of them