openstack team mailing list archive

[Jay Pipes <jaypipes@xxxxxxxxx>]

When a user issues a GET request for a resource collection, it's clear
that you don't want to return ALL results in the collection. Returning
hundreds of thousands of records per request isn't particularly a good
idea.

Therefore, we use the concept of "pagination" -- returning a subset of
records matching the search criteria.

In Glance's API, we've added this ability (currently in code review),
but our approach is a bit at odds with the way that the OpenStack
Compute API is structured. I'd like to explain why I think our
approach is better, both in terms of usability and in terms of
efficiency.

First, here is how Nova does its pagination in the OpenStack API.

1) Look for a "marker" query parameter in the request
2) Look for a "limit" query parameter in the request, otherwise use a
default max limit.
3) If marker parameter is found, the value of the "marker" query
parameter is assumed to be an *integer* and assumed to be the
*identifier of the last object on the previous "page" of results*
4) Request *all* results
5) In the code, find the "page" of results by looking for the object
in the set of results that matches the marker parameter
6) When found, grab the next object in the result set, plus X objects,
where X is the limit parameter

The relevant code is in /nova/api/openstack/common.py, and looks like so:

def limited_by_marker(items, request, max_limit=FLAGS.osapi_max_limit):
    """Return a slice of items according to the requested marker and limit."""

<snipped for brevity... >

    limit = min(max_limit, limit)
    start_index = 0
    if marker:
        start_index = -1
        for i, item in enumerate(items):
            if item['id'] == marker:
                start_index = i + 1
                break
        if start_index < 0:
            raise webob.exc.HTTPBadRequest(_('marker [%s] not found' % marker))
    range_end = start_index + limit
    return items[start_index:range_end]

There are three MAJOR problems with the above method of pagination:

1) Very inefficient

The Python code does the job of determining the page of results to
find. This means that the database query returns EVERY row in the
resultset, instead of only returning a small subset of the results
using the LIMIT X OFFSET Y SQL construct. With hundreds of thousands
of records in the various databases, this method is simply not
scalable.

2) There is no ordering of the results in the queries the Nova
database API makes

The only queries in the Nova database API that order results is the
instance_type_get_all() method.

Without an order to the search results, paging is almost meaningless.
A page of results depends on the order of the list of results. The
reason the existing Nova code works at all is because of the fact that
all objects have an autoincrementing integer primary key, and by
nature, this autoincrementing integer primary key increases over time.
If the identifier was switched to, say, UUID, the results ordering
would fall apart completely, and "pages" of results would get skewed
and corrupted as records were inserted over time.

For instance, assume a character primary key (like UUID keys would be
stored in hex string format). Assume the following simplified set of
instances:

PK         Created_at
ABC       2011-05-25 12:00:00
DEF       2011-05-25 12:00:01
GHJ       2011-05-25 12:00:02
KLM       2011-05-25 12:00:03

Assume you want to get a list of instances with GET /servers?limit=2.
With the existing code, you'd get this:

ABC       2011-05-25 12:00:00
DEF       2011-05-25 12:00:01

With GET /servers?limit=2?marker=DEF, you'd get this:

GHJ       2011-05-25 12:00:00
KLM       2011-05-25 12:00:03

However, let's say a new instance is added:

BCD       2011-05-25 12:00:04

Because there is no sort order specified in the database queries, the
order of results is indeterminate. Page 1 may now contain the BCD
record, or it may not. It totally depends on the implementation of the
relational database, because the SQL standard does not mandate a
default sort order when one is not specified in the ORDER BY clause.

3) The marker parameter assumes an autoincrementing primary key

Because the marker parameter assumes an autoincrementing primary key,
the paging of results currently DOES solve the problem of new records
messing up paging.

As an example, let's assume I've fixed #2 above and put a default sort
order on the primary key, descending. Also assume a simple resultset
like so:

PK         Created_at
1      2011-05-25 12:00:00
2      2011-05-25 12:00:01
3      2011-05-25 12:00:02
4      2011-05-25 12:00:03

Assume I make a request for GET /servers?limit=2. I would get:

4      2011-05-25 12:00:03
3      2011-05-25 12:00:02

The results returned would be the "last" 10 server instances created.
If I did a request for GET /servers?limit=2?marker=3, I would get the
results:

2      2011-05-25 12:00:01
1      2011-05-25 12:00:00

If I add a new instance, say:

5      2011-05-25 12:00:05

and did the request for GET /servers?limit=2?marker=3, I would still
get the same results:

2      2011-05-25 12:00:01
1      2011-05-25 12:00:00

However, the ONLY reason this works is because the primary key is
auto-incrementing, and new records always come at the "end" of the
primary key. If I change the primary key to a UUID, the call to GET
/servers?limit=2?marker=3 would no longer be guaranteed to return the
same results. The newly-added instance's UUID may come between the
values of the primary keys in the original "page 2", and therefore
messed up the consistency of the pagination of my original query.

The way to avoid this inconsistency is to ensure that you have a
consistent view of the set of results of your original query. To do
that, you must always use a WHERE condition on a temporal,
always-incrementing (timestamp) column.

In SQL, this is what is necessary to have a consistent view of pages
of a result set (assuming 10 elements to a page):

Page 1:

SELECT i.* FROM instances i
ORDER BY i.id DESC;
LIMIT 10;

SET @marker = <ID of *first* record>
SET @updated_at_marker = SELECT updated_at FROM instances WHERE id = @marker;

Page 2:

SELECT i.* FROM instances i
WHERE updated_at <= @updated_at_marker
ORDER BY i.id DESC
LIMIT 10 OFFSET 10;


SUMMARY:

My proposal is to overhaul the way that Nova does pagination so that we:

1) Pass the LIMIT and OFFSET parameters down into the database API queries
2) Add a default ORDER BY for all queries returning result sets
3) Add a "page" query parameter that would be used to calculate the
OFFSET programmatically
4) Change the concept of the "marker" parameter to refer to *the ID of
the FIRST record returned in the original query*

Thoughts?

-jay