“Guys, we’re doing pagination wrong…”

These are the words that I had to mutter quite a few times in my career, at the dissatisfaction of how pagination had been implemented on several projects.

Still, that dissatisfaction is nothing compared to how I feel when I occasionally had to ask “why is this API not paginated..?”

So, taking a break from my usual Serverless ramblings, let’s talk about pagination :-)

Unidirectional and Bidirectional Pagination

Generally speaking, I see two common types of paginations:

  • simple, unidirectional, paging through a static set of results that are too long or inefficient to return in one go – e.g. list of twitter followers, or list of Google search results
  • bidirectional paging 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 twitter timeline, or notifications

Avoid leaky abstraction

A common mistake I see is that the paginated API requires the caller to provide the “key” it uses to sort through the results, which creates a leaky abstraction. The caller must then understand the underlying mechanism the service uses to page its results – e.g. by timestamp, or alphabetical order.

DynamoDB’s Query API is a good example of this. To page through the query results, the caller must specify the ExclusiveStartKey in subsequent requests. However, the service does return the LastEvaluatedKey in the response too.

So, in practice, you can almost treat the LastEvaluatedKey as a token, or cursor, which you simply pass on in the next request. Except, it’s not just a token, it’s an actual sort key in the DynamoDB table, and the attribute names already gave the implementation details away anyway.

On its own, this is not a big deal. However, it often has the unfortunately knock-on effect of encouraging application developers to build their application level paginations on top of this implementation detail. Except this time around, they’re not returning the LastEvaluatedKey in the response and the client is now responsible for tracking that piece of information.

Congratulations, the underlying mechanic your database uses to support pagination has now leaked all the way to your front end!

Make paging intent explicit and consistent

Another common trend I see is that you have to send the same request parameters to the paginated API over and over, for example:

  • max no. of results per page
  • the direction of pagination (if bidirectional)
  • the original query (in DynamoDB’s case, this includes a no. of attributes such as FilterExpressionKeyConditionExpressionProjectionExpression and IndexName)

I won’t call this one a mistake as it is sometimes by design, but more often than not it strikes me as a consequence of lack of design instead.

In all the paginated APIs I have encountered, the intended behaviour is always to fetch the next set of results for a query, not to start a different query midway through. That just wouldn’t make sense, and you probably can’t even call that pagination, more like navigation! I mean, when was the last time you start a DynamoDB query, and then have to change any of the request parameters midway through paginating through the results?

That said, there are legitimate reasons for changing the direction of pagination from a previously received page. More on this when we discuss bidirectional paging further down the article.

Unidirectional paging with cursor

For unidirectional pagination, my preferred approach is to use a simple cursor. The important detail here is to make the cursor meaningless.

As far as the client is concerned, it’s just a blob the server returns in the response when there are more results to fetch. The client shouldn’t be able to derive any implementation 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 & responses for a series of paginated requests

But how does the API know where to start fetching the next page from?

A simple way to do this is:

  1. create a JSON object to capture the data needed to fetch next page – e.g. if you’re using DynamoDB, then this can be the request object for the next page (including 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 created earlier.

Isn’t that gonna leak even more information – e.g. that you’re using DynamoDB, the table name, the schema, etc. – if someone just base64 decode your blob?

Absolutely, 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 subsequent requests?

This is by design.

As I mentioned earlier, the client has already told us the query in the first request, the pagination mechanism should only provide a way for fetching subsequent pages of the results.

Which, to me, means it should not afford any other behaviour (there is that word again, read here to see how the idea of affordance applies to API design) and therefore do not require any other information besides the cursor from the previous response.

This in turn, means we need to capture the original query, or intent, in the cursor so we can construct the corresponding DynamoDB request. Or, we could just capture the actual DynamoDB request in the cursor which seems like a simple, practical solution here.

fig. 2 – interaction between client, API and DynamoDB

Bidirectional paging with cursor(s)

With bidirectional paging, you need to be able to page forward in time (when new tweets are added to your timeline) as well as backward (to fetch older tweets). So a simple string cursor would no longer suffice, instead we need 2 cursors, one for each direction, for example…

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

Additionally, when paging forward, even when there are no more results right now we still have to return a cursor as new results can be added to the feed later. 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 forward in time and receives hasAfter as false then it knows there are no more results available right now. It can therefore stop actively fetch the next page of results, and be more passive and only poll for new results periodically.


Let’s run through a simple example, imagine if you’re fetching the tweets in your timeline where the API would return the latest tweets first.

fig. 3 – paginate backward in time to fetch older data

  1. the client makes a first request
  2. API responds with a cursor object, hasAfter is false because the API has responded with the latest results, but hasBefore is true as there are older results available
  3. the client makes a second request and passes only the before cursor in the request, making its intention clear and unambiguous
  4. API responds with another cursor object where this time both hasBeforeand hasAfter are true given that we’re right in the middle of this stream of results
  5. the client makes a third and last request, again passing only the beforecursor received from the previous response
  6. API responds with a cursor object where hasBefore is false because we have now received the oldest result available

Ok, now let’s run through another example, this time we’ll page forward in time instead.

fig. 4 – paginate forward in time to fetch newer data

  1. the client makes a first request
  2. API responds with a cursor object, hasAfter is false because the API has responded with the latest results, but hasBefore is true as there are older results available
  3. some time has passed, and more results have become available
  4. the client makes a second request, and passes only the after cursor in the request, making its intention clear and unambiguous
  5. API responds with only the newer results that the client has not received already, and cursor.hasAfter is false as these are the latest results available at this moment in time; should the client page backward (in time) from this response then it’ll receive the same results as the first response from the API

Now, let’s circle back to what I mentioned earlier regarding the occasional need to change direction midway through pagination.

The reason we need pagination is because it’s often impractical, inefficient and in some cases impossible to return all available results for a query – e.g. at the time of writing Katy Perry has 108M Twitter followers, trying to retrieve all her followers in one request-response cycle would have crashed both the server and the client app.

Besides limiting 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 protect the user experience and prevent the client app from crashing.

That means, at some point, as the user keeps scrolling through older tweets, the client would need to start dropping data it has already fetched or risk running out of memory. Which means, when the user scrolls back up to see the latest tweets, the client would need to re-fetch pages that had been dropped and hence reversing the original direction of the pagination.

Fortunately, the scheme outlined above is flexible enough and allows you to do just that. Every page of results has an associated cursor that allows you to fetch the next page in either direction. So, in the case where you need to re-fetch a dropped page, it’s as simple as making a paginated request with the after cursor of the latest page you have cached.

Dealing with “gaps”

Staying with the Twitter example. If you open up the Twitter mobile app after some time, you’ll see the tweets that has already been cached but the app also recognizes that a lot of time has passed that it’s not feasible to paginate from the cached data all the way to the latest.

Instead, the client would fetch the latest tweets with a non-paginated request. As you scroll down, the client can automatically fetch older pages as per fig. 3 and gradually fill in the gap until it joins up with the cached data.

The behaviour of the Twitter mobile app has changed over time, and another tactic I have seen is to place a visual (clickable) marker for the missing tweets in the timeline. This makes it an explicit action by the user to start paging through older tweets to fill in the gap.

So there you have it, a simple and effective way to implement both unidirectional and bidirectional paginated APIs, hope you have found it useful!

Here Be Monsters – Message broker that links all things

In our MMORPG title Here Be Monsters, we offer the players a virtual world to explore where they can visit towns and spots; forage fruits and gather insects and flowers; tend to farms and animals in their homesteads; make in-game buddies and help each other out; craft new items using things they find in their travels; catch and cure monsters corrupted by the plague; help out troubled NPCs and aid the Ministry of Monsters in its struggle against the corruption, and much more!

All and all, there are close to a hundred distinct actions that can be performed in the game and more are added as the game expands. At the very centre of everything you do in the game, is a quest and achievements system that can tap into all these actions and reward you once you’ve completed a series of requirements.

 

The Challenge

However, such a system is complicated by the snowball effect that can occur following any number of actions. The following animated GIF paints an accurate picture of a cyclic set of chain reactions that can occurred following a simple action:

Chain

In this instance,

  1. catching a Gnome awards EXP, gold and occasionally loot drops, in addition to fulfilling any requirement for catching a gnome;
  2. getting the item as loot fulfils any requirements for you to acquire that item;
  3. the EXP and gold awarded to the player can fulfil requirements for acquiring certain amounts of EXP or gold respective;
  4. the EXP can allow the player to level up;
  5. levelling up can then fulfil a requirement for reaching a certain level as well as unlocking new quests that were previously level-locked;
  6. levelling up can also award you with items and gold and the cycle continues;
  7. if all the requirements for a quest are fulfilled then the quest is complete;
  8. completing a quest will in turn yield further rewards of EXP, gold and items and restarts the cycle;
  9. completing a quest can also unlock follow-up quests as well as fulfilling quest-completion requirements.

 

The same requirements system is also in place for achievements, which represent longer term goals for players to play for (e.g. catch 500 spirit monsters). The achievement and quest systems are co-dependent and feeds into each other, many of the milestone achievements we currently have in the game depend upon quests to be completed:

image

Technically there is a ‘remote’ possibility of deadlocks but right now it exists only as a possibility since new quest/achievement contents are generally played through many many times by many people involved in the content generation process to ensure that they are fun, achievable and that at no point will the players be left in a state of limbo.

 

This cycle of chain reactions introduces some interesting implementation challenges.

For starters, the different events in the cycle (levelling up, catching a monster, completing a quest, etc.) are handled and triggered from different abstraction layers that are loosely coupled together, e.g.

  • Level controller encapsulates all logic related to awarding EXP and levelling up.
  • Trapping controller encapsulates all logic related to monster catching.
  • Quest controller encapsulates all logic related to quest triggering, progressing and completions.
  • Requirement controller encapsulates all logic related to managing the progress of requirements.
  • and many more..

Functionally, the controllers form a natural hierarchy whereby higher-order controllers (such as the trapping controller) depend upon lower-order controllers (such as level controller) because they need to be able award players with EXP and items etc. However, in order to facilitate the desired flow, theoretically all controllers will need to be able to listen and react to events triggered by all other controllers..

 

To make matter worse, there are also non-functional requirements which also requires the ability to tap into this rich and continuous stream of events, such as:

  • Analytics tracking – every action the player takes in the game is recorded along with the context in which they occurred (e.g. caught a gnome with the trap X, acquired item Z, completed quest Q, etc.)
  • 3rd party reporting – notify ad partners on key milestones to help them track and monitor the effectiveness of different ad campaigns
  • etc..

 

For the components that process this stream of events, we also wanted to make sure that our implementation is:

  1. strongly cohesive – code that are dealing with a particular feature (quests, analytics tracking, community goals, etc.) are encapsulated within the same module
  2. loosely coupled – code that deals with different features should not be directly dependent on each other and where possible they should exist completely independently

Since the events are generated and processed within the context of one HTTP request (the initial action from the user), the stream also have a lifetime that is scoped to the HTTP request itself.

 

And finally, in terms of performance, whilst it’s not a latency critical system (generally a round-trip latency of sub-1s is acceptable) we generally aim for a response time (between request reaching the server and the server sending back a response) of 50ms to ensure a good round-trip latency from the user’s perspective.

In practice though, the last-mile latency (from your ISP to you) has proven to be the most significant factor in determining the round-trip latency.

 

The Solution

After considering several approaches:

  • Vanilla .Net events
  • Reactive Extensions (Rx)
  • CEP platforms such as Esper or StreamInsight

we decided to go with a tailor-made solution for the problem at hand.

In this solution we introduced two abstractions:

  • Facts – which are special events for the purpose of this particular system, we call them facts in order to distinguish them from the events we record for analytics purpose already. A fact contains information about an action or a state change as well as the context in which it occurred, e.g. a CaughtMonster fact would contain information about the monster, the trap, the bait used, where in the world the action occurred, as well as the rewards the player received.
  • Fact Processor – a component which processes a fact.

 

As a request (e.g. to check our trap to see if we’ve caught a monster) comes in the designated request handler will first perform all the relevant game logic for that particular request, accumulating facts along the way from the different abstraction layers that have to work together to process this request.

At the end of the core game logic, the accumulated facts is then forwarded to each of the configured fact processors in turn. The fact processors might choose to process or ignore each of the facts.

In choosing to process a fact the fact processors can cause state changes or other interesting events to occur which results in follow-up facts to be added to the queue.

FactProcessing

 

The system described above has the benefits of being:

  • Simple – easy to understand and reason with, easy to modularise, no complex orchestration logic or spaghetti code.
  • Flexible – easy to change information captured by facts and processing logic in fact processors
  • Extensible – easy to add new facts and/or fact processors into the system

The one big downside being that for the system to work it requires many types of facts which means it could potentially add to your maintenance overhead and requires lots of boilerplate class setup.

 

To address these potential issues, we turned to F#’s discriminated unions over standard .Net classes for its succinctness. For a small number of facts you can have something as simple as the following:

image

However, as we mentioned earlier, there are a lot of different actions that can be performed in Here Be Monsters and therefore many facts will be required to track those actions as well as the state changes that occur during those actions. The simple approach above is not a scalable solution in this case.

Instead, you could use a combination of marker interface and pattern matching to split the facts into a number of specialized discriminated union types.

image

Update  2014/07/28 : thank you to @johnazariah for bringing this up, the reason for choosing to use a marker interface rather than a hierarchical discriminated union in this case is because it makes interop with C# easier.

In C#, you can create the StateChangeFacts.LevelUp union clause above using the compiler generated StateChangeFacts.NewLevelUp static method but it’s not as readable as the equivalent F# code.

With a hierarchical DU the code will be even less readable, e.g. Fact.NewStateChange(StateChangeFacts.NewLevelUp(…))

 

To wrap things up, once all the facts are processed and we have dealt with the request in full we need to generate a response back to the client to report all the changes to the player’s state as a result of this request. To simplify the process of tracking these state changes and to keep the codebase maintainable we make use of a Context object for the current request (similar to HttpContext.Current) and make sure that each state change (e.g. EXP, energy, etc.) occurs in only one place in the codebase and that change is tracked at the point where it occurs.

At the end of each request, all the changes that has been collected is then copied from the current Context object onto the response object if it implements the relevant interface – for example, all the quest-related state changes are copied onto a response object if it implements the IHasQuestChanges interface.

 

Related Posts

F# – use Discriminated Unions instead of Classes

F# – extending Discriminated Unions using marker interfaces

Dart – implementing the Singleton pattern with factory constructors

In Dart there is an interesting language feature called ‘Factory Constructors’, which effectively allows you to override the default behaviour when using the new keyword – instead of always creating a new instance the factory constructor is merely required to return an instance of the class, the difference is important.

Factory constructors allow you to implement a number of techniques and patterns without altering code that consumes your class. For instance,

  • Singleton pattern which we will look at more closely.
  • Object pooling, a useful technique for reducing the amount of allocations (and its associated allocation cost and consequent GC pressure) in performance critical applications.
  • Flyweight pattern which is already discussed in more detail in this Idiomatic Dart article.

These are just 3 use cases that I can think of off the top of my head, please feel free to suggest any more that I have missed.

Problems with common Singleton pattern implementations

In other languages (well, the ones that I’m familiar with anyway!), in order to implement the Singleton pattern you have to ensure that the class’s constructor is not exposed publicly and that access to the singleton instance is done via a static Singleton property. Revered C#/Java developer Jon Skeet has a very good article on the various solutions one might adopt to implement the singleton pattern in C#.

Inflexible

These implementations require code that consumes your class to be aware of its implementation of the singleton pattern and create a vast blast radius throughout your application should you one day decide that the singleton pattern is no longer necessary/applicable.

For instance, if assumptions in your application change drastically (and they often do..) and you need to switch to the flyweight or another pattern instead to cater for changing requirements and/or assumptions.

Unintentional tight coupling

In the case of C# (where static members are not allowed on interfaces and abstract classes are un-constructible) the standard singleton pattern also create tight coupling to a concrete implementation where it’s seldom necessary.

You can, to some degree, work around this issue of tight coupling by introducing an IOC container as middle man between your class and its consumers, most IOC containers provide some mechanism for controlling object lifespans (transient, singleton, pooled, etc.). However, you now have tight coupling to the IOC container instead…

Singleton pattern with Factory constructors

You can implement the singleton pattern using factory constructors like this:

the key thing here is that any consuming code is completely oblivious to the fact that we have just implemented the singleton pattern. If we were to continue our mind later or forced to adopt a different pattern because of changing requirement, there will be trivial or no change on all the consuming code!

Links

Idiomatic Dart – Factory constructors

Jon Skeet – Implementing the Singleton pattern in C#

Shlomo Swidler’s Many Cloud Design Patterns slides

This is so good I keep going back to it, so to save myself and you the hassle of searching for it every time I thought I’d share it here on my blog, enjoy! Smile

.Net Tips – Use Request and Response objects

We’ve all been there before, write a simple service with a simple method:

[ServiceContract]
public interface IService
{
    [OperationContract]
    int SimpleMethod(object param1);
}

As time goes by, the simple method gets more complicated, and the list of parameters grows and eventually simple method is overloaded to provide more variety and simple method is simple no more!

A simple solution to this is the Request-Response pattern, by encapsulating all the input and output values into request and response objects you will be able to:

  • solve the problem with growing parameters
  • have an easy way of providing multiple results
  • add input/output values incrementally

And you’ll be able to do all this without even changing the service contract!

[ServiceContract]
public interface IService
{
    [OperationContract]
    SimpleMethodResponse SimpleMethod(SimpleMethodRequest request);
}

[DataContract]
public void SimpleMethodRequest
{
    [DataMember]
    public object Param1 { get; set; }

    [DataMember]
    public string Param2 { get; set; }

    [DataMember]
    public int Param3 { get; set; }

    …
}

[DataContract]
public void SimpleMethodResponse
{
    [DataMember]
    public bool Success { get; set; }

    [DataMember]
    public int? ErrorCode { get; set; }

    [DataMember]
    public string ErrorMessage { get; set; }

    …
}

In addition, you can also create a hierarchy of request/response objects and consolidate your validation logic in validator classes or custom validation attractions (you can use PostSharp to write attributes that take care of the validation ‘aspect’ of your application).

References:

API Design Patterns – Request/Response