Paginating with Riak

The question of pagination comes up from time to time on the Riak mailing list and in #riak on, most recently a few days ago. In reply, I always say something along the lines of "No. Riak does not do pagination." Let's take a look at what pagination is and why Riak has a hard time doing it. Pagination is generally defined as the ordered numbering of pages in a publication, usually a book. Now let's take that book and make it a Hot 100 list of super cool things that we want to put on a website. As far as we are concerned pagination is the ability to select a subset of information, in sequence, from a larger set of information.

Let's work with the numbers 1 through 100, in order. We could interest ourselves with the numbers one at a time or, perhaps, 10 at a time. If we were to page through those numbers we would have to know primarily two things: where are we starting and how much do we want. In addition, any meaningful pagination would require the larger set to be sorted. Working with our earlier definition and our example, Riak presents one chief complaint: sorting.

Riak at its core is a distributed key/value persisted data store that also happens to do a lot of other things. Now break that down. Looking at those words individually we have "distributed", meaning that your data lives on a number of different machines in your cluster. Good thing, right? Yes. However it also means that no single machine is the canonical reference for all your data. Which in turn means that you need to ask multiple machines for your data and those machines will return data to you when they see fit, ie. not in order. Moving on, we have "key/value". In regards to the topic at hand, this means that Riak has no insight into any data held within your keys, ie. Riak does not care if your stored json object has an age value in it. Next, we have "persisted". Riak has no native internal index, meaning Riak will not store on disk the data you send it in any useful way - useful to you at least. Lastly, we have "happens to do a lot of other things." Thankfully for us, one of those other things is Map/Reduce.

Map/Reduce is where all those previous sorting problems, uh, sort themselves out. Map/Reduce is basically the way for you to marshal your data in Riak. Basically, Map/Reduce takes your unsorted heaping mess of data and whips it into shape. I'll be using the riak-js module for nodejs to talk to Riak and walk through our example. Using a stock Riak install we will populate 100 keys, named 1 through 100, with a simple json object and select a subset of those keys using m/r. This example expounds on a brief mention of the subject in a Basho blog post from the summer of 2010. We will be taking advantage of a number of built-in javascript functions that come bundled with Riak. See you after the code.

Basically run populate-riak to populate a bucket, then run paginate-riak to get a "page" of that data back. All this works off the command line. Cool, right? Well, ya. Except... if you are contemplating running a site with any meaningful scale this will not function that well for you. Hmm, why is that? Well, on its face this method will work but what it is doing is pulling all records in your bucket and sorting your result set on the fly - every time you call it. This will fall down as the number of records in your system grows, aka. the number of records you need to sort grows. You really need to employ caching at different layers of your application to make this work better. Allowing your users to run the above every time they want to paginate a set of records is just a recipe for disaster. As an ad-hoc query run once in a while it should work fine, ie. perhaps run on a frequency to build a paginated cache that your user facing application hits directly.

Bear in mind that this is not a knock on Riak. It is simply a limitation that is inherent in the design of Riak. When evaluating a persistent data store you should take into account the good, of which Riak has a fair amount of, and the not so good. This is just one area where your application will have to accomodate the shortcomings by making judicious usage of pre-emptive caching. Now, when asked in the future whether or not Riak supports pagination I'll simply give a qualified "Sort of."

4 responses
Isn't RiakSearch supposed to solve this problem? The solr interface documentation says it supports sort by index key, start val and num rows, but they have been bugged for 7 months.

Nobody wants to comb over their disk just to sort a bunch of values that are already in memory. If this bug were fixed your pagination post would be much more succinct.

Thank you for your comment, KevBurnsJr. This post is specific to implementing pagination via MapReduce as implemented in Riak. The above code indicates using a bucket as the input of your m/r although in a production system you would be advised to replace that with a list of keys. At present, RiakSearch and Riak are two different downloads, although the two products will likely merge[0]. If you are using RiakSearch, then there are better mechanisms available to you to facilitate pagination, as you noted.



There are a couple of other problems with this approach:

1. Because the records in the reduce phase are process as we get them from the map phase, the number of records return can change from call to call even with the same params. Check

2. If you're values are complex enough, you can end up with an error like this:
{"lineno":465,"message":"InternalError: script stack space quota is exhausted","source":"unknown"}. A way to solve this is to increase the values of js_thread_stack and js_thread_stack (Check for more info). I think also you can just write you're own reduceSlice in erlang that I would assume its more efficient (if it happens that you're using erlang). I'm working on this right, will post back if I get this working

Thanks for the comment, Manuel.

1. Later on in that thread,, there is a solution given. Has to do with how/when the reduce is run.

2. Doing your m/r in erlang will result in a non-trivial performance boost. The error you got can be mitigated by tuning the jv thread/memory allocations but if you can do an m/r erlang you probably should.