Implementing Pagination for ActivityPub Collections

The ActivityPub specification defines a number of collections for each ActivityPub actor – an inbox and an outbox, followers and following and liked. Each ActivityPub object can also have shares, likes, thread and replies collections. I want to talk about how to best implement these collections. I'll talk about the requirements for collections, some general principles, and then some specific suggestions for different paging strategies.

Requirements

• A collection is represented by a top-level Collection or OrderedCollection object, plus a singly- or doubly-linked list of CollectionPage objects or OrderedCollectionPage objects. For this discussion, I'm going to stick just with OrderedCollection and OrderedCollectionPage, which are the best representation. (This is a correctness requirement; implementations that don't meet it are incorrect.)
• The OrderedCollection should include a totalItems property, with the total item count, plus either an orderedItems property with all the items in it, or a first property with the id for the first OrderedCollectionPage in the list. It can also have a last property with the id of the last OrderedCollectionPage in the list if the list is doubly-linked, but I'm going to concentrate on singly-linked lists in this discussion. (correctness)
• The OrderedCollectionPage should include a partOf property with the id of the OrderedCollection. It should have an orderedItems property with zero or more items, either as ids or as embedded objects. It should have a next property with the id of the next page, except for the last page. (correctness)
• Items in the collection should be in reverse chronological order by insertion time. A new item added to the collection should be the first item in the first page. Items should be sorted within pages and across pages. (correctness)
• The paging should be continuous. The last item in one page should be immediately newer than the first item in the next page. There should be no gaps between pages. There should be no overlap between pages. (correctness)
• An item can be added to the front of a collection; the new item is always the first item in the first page or the first item in the collection if it doesn't have pages. (correctness)
• Any arbitrary item can be removed from a collection; any item on any page can be removed. (correctness)
• Each HTTP request should be less than about 100-200ms. This is a rule of thumb based on people's patience with interactive API use. (This is a performance requirement. Implementations that don't meet this requirement are slow, or take up unnecessary client or server resources.)
• Collection implementations should be structured to minimise the number of HTTP requests. This is especially true if the server enforces request rate limits. (performance)
• Collection implementations should keep the responses of HTTP requests under about 100KiB. This is a rough rule of thumb for any API payload sizes; if you're trying to keep API requests under about 100ms, this makes sure that bandwidth is not your limiting factor. (performance)
• To the extent possible, the results should be cacheable with HTTP caching. In practice, this means that you should isolate volatility into fewer parts of the collection, and leave the other parts stable. (performance)
• ActivityPub object ids are opaque. Clients can't add or change or remove query parameters to get different results. (robustness)

General best practices

• Include on the order of 100 items in each page. Reading a full collection requires 1 + (total size/page size) HTTP requests. If you have only a few items per page, that will require a lot of pages. If you have many items per page, it requires fewer pages, so that's fewer total HTTP requests. If each item is represented by an URL, and your URLs are about 128-256 bytes each, you can fit 256 URLs into a payload of 32KiB to 64KiB – well under the 100KiB guideline. If you include embedded nodes for your items, you might want to halve that to 128 objects.
• Inline small collections. If the total number of items in the collection is less than your page size, include the items in the OrderedCollection object's orderedItems property. If your page size is ~128-256 items, most real-world collections – like shares, replies, likes, and even followers and following – are going to fit in this boundary. Inlining reduces the number of HTTP requests for each collection by 1, but for all collections by about half. That's a good savings!

Pagination strategies

I know of three pagination strategies you can use for implementing ActivityPub collections. They differ in the structure of the ID URLs that are used to fetch collections and pages, and in the database structure that backs up the storage of the items.

Strategy 1: Offset Pagination

In this strategy, there is a fixed page size. The URL includes a page number for the page to be retrieved:

https://social.example/collection/{collection_id}?page={page_number}

The page number is used to calculate an offset for the first item in the page from the newest item in the collection. The offset is usually calculated like (page_number - 1) * (page_size) for 1-based page numbers.

In this strategy, collection items are stored in a relational database table like collection_members with a collection_id, item_id, and some kind of ordering factor. This can be insertion datetime or an auto-incrementing integer or other data types. For the outbox collection, if you're using ULIDs or Snowflake IDs, you can even use the ID itself for sorting. I'm going to used inserted_at in this example, but the principle is the same.

To get the items in page page_number with size page_size, you'd do a SQL query like this:

SELECT item_id
FROM collection_members
WHERE collection_id = {collection_id}
ORDER BY inserted_at DESC
OFFSET {(page_number - 1) * (page_size)}
LIMIT {page_size}

Having an index on (collection_id, inserted_at) can really help here.

Determining if the OrderedCollectionPage should have a next property is a little tricky with this strategy. If the query returns fewer than page_size items, you know there are no more. But what if it returns exactly page_size items? That could mean either that there are more items, or that the total count of items lines up right on the page boundary. An old trick is to request page_size + 1 items, and throw away the last item, just to see if there are more items in next pages.

This is the most common strategy I see for pagination on the Fediverse today; it's the one that Mastodon uses, and a lot of other ActivityPub implementations copy it. It's also the worst pagination strategy I'll discuss here, by a long shot.

The first problem is that it's not correct. Or, rather, it's not robust to changes in the collection. The continuity constraint is broken. If you load page 1, get its next property (page 2), and an item is added before you fetch page 2, the last item in the old page 1 will now be the first item in the new page 2. Similarly, if an item is removed from page 1, the first item of the old page 2 becomes the last item of the new page 1 – and when you fetch page 2, you'll never see that item!

The second problem is that it's absurdly inefficient – it's O(N) for a single page request, and O(N^2) to traverse the whole collection. Yuck! To execute the query with that OFFSET ... LIMIT ... stanza, the database engine has to get all {(page_number - 1) * (page_size)} items from the table, throw them away, and then take the next page_size items. So, when you load page 100 with a 100-item page size with this strategy, you have to fetch and order the first 9900 items, discard them, and return the next 100. On average, you have to fetch and discard N/2 items, so it's O(N).

To read a whole collection, you need to do this N/page_size times, so an O(N) procedure repeated ~N times is going to be O(N^2). This is a strategy that will get you a solid C- in your algorithms and data structures CS class, just on this problem alone.

Mastodon deals with this problem by setting a special rate limit only on collection pages – you can only request 300 every 15 minutes, or about 1 every 3 seconds. That keeps the brutal cost to the server down, at the expense of making clients extremely slow.

A last problem is that this strategy is almost uncacheable. Every page is volatile. If a new item is added to the collection, the first page of the collection is changed – as well as every other page in the collection! And if an item is removed from the collection, whichever page the item was in, every page after that is also changed. Objects usually get removed from collections like likes relatively soon after they are inserted, because people change their mind about likes, follows, shares, and so on relatively soon after they do them. So, the problem with removes is pronounced.

Strategy 2: Cursor Pagination

A better strategy, which is implemented by a number of servers, is cursor pagination. In this strategy, rather than keeping track of a page number, and incrementing it to get the next page, the server passes a marker for the end of the current page. The next page_size items are the next page.

URLs in this strategy look something like this:

https://social.example/collection/{collection_id}?older_than={last_item_inserted_at}

The database structure can be identical to the one used for offset paging: collection_id, item_id, and an ordering factor like inserted_at. There's a requirement for strict ordering here, though – no two items can have the same inserted_at timestamp. Usually if you track timestamps to milliseconds, this isn't a problem, but you can throw in a random number for a few additional digits to make sure if you want. Or, you can include the item_id in the cursor and use that for a tie-breaker. I'm going to assume unique inserted_at to make this easier, though.

So, your query now looks like:

SELECT item_id
FROM collection_members
WHERE collection_id = {collection_id}
AND inserted_at < {last_item_inserted_at}
ORDER BY inserted_at DESC
LIMIT {page_size}

In terms of performance, the change in the WHERE clause here makes a world of difference. Instead of O(N), this query is O(log N), as long as you have an index on inserted_at. And traversing the whole collection is O(N log N). A much better step!

Determining if the OrderedCollectionPage should have a next property is the same as with offset pagination. Just ask for page_size + 1 items, and see if you get what you ask for. Throw away the last one.

Besides the single-request and traversal performance, this strategy is correct, or rather, the continuity requirement is preserved in the face of changes to the collection. If a new item is added between the fetch of one page and its next page, the next page will still get the very next item. If an item is removed before or after the cursor, continuity is maintained. Even if the cursor item is the one that's removed!

It's even somewhat cacheable, faced with insertions. When a new item is inserted, a whole new series of pages is generated, since the last item of each page changes. But the URLs of old page will still be fetchable and should be stable. Re-traversing the same collection will just require fetching a whole new set of URLs.

The same thing applies in the face of removals. When an item is removed from a page, because it's a fixed size, the last item changes, and the whole series of page URLs changes. But the old URLs for following pages will be stable. Re-traversing will smash the cache, though.

Cursor pagination is a pretty good overall; it's worlds better than offset pagination. It's not great for retraversing the same collection after it's changed, though. One great advantage of cursor pagination is that it can be used to quickly upgrade from offset pagination for most database structures – no database changes are needed.

Strategy 3: Bucket Pagination

With bucket pagination, an item is assigned to a page at insertion time – not at query time. This means that pages stay very stable over the lifetime of the collection, making them much more cache-friendly. All of the volatility is constrained to the newest page (that's where new items go) and the collection itself (for total item count). This comes with some relatively small costs, which I'll get into below.

An URL for a page with bucket pagination would usually have a container_id and a bucket_id, or just a bucket_id if the IDs are unique:

https://social.example/bucket/{bucket_id}

The database structure is different than with cursor or offset pagination. You need to store membership in terms of buckets rather than the collection; something like bucket_id, item_id, inserted_at. Fetching the items in a bucket is just a select with a sort:

SELECT item_id
FROM bucket_members
WHERE bucket_id = {bucket_id}
ORDER BY inserted_at DESC

When returning a page, you need to know the collection_id for the partOf property, and the next bucket for the next property. These can go into another table, like collection_bucket. You can store the information about what's the first bucket in the collection either with a flag on collection_bucket or by keeping a separate collection table with a first_bucket property. (This is a great place to keep a total count of items in the collection, too – you can serve the OrderedCollection object with one hit to the database.)

Inserting an item into the collection means either adding it to the first bucket or, if the first bucket is full, creating a new bucket, making it the first bucket, setting the old first bucket as its next bucket, and then adding the item to the new first bucket. This is quick and simple, but it has the downside that most of the time the first bucket has much less than page_size items in it.

Another strategy is to let the first bucket grow up to 2 * page_size items. When the first bucket is full, make a new bucket out of its oldest page_size items, and insert that as the next page in the linked list (fixing up prevs and nexts as needed). This means that your first bucket is always min(total_items, page_size) large.

Determining if the OrderedCollectionPage should have a next property is much easier; check the next_bucket column of collection_bucket for a NULL.

This strategy is correct for the continuity requirement and robust in the face of change. Buckets aren't a shifting window onto a collection; their members never move around (except for the first bucket, as described above). The last item in one bucket is always right after the first item in the next bucket.

The performance is O(log N) and O(N log N) for the full traversal, which is fine.

Where this strategy really shines is with caching. Every bucket except the first one is immutable under insertion, and only the affected bucket is changed during removal. That means you can set very long cache lifetimes on these OrderedCollectionPage objects. Except for the first one, they're just not going to change much.

The downside is that the sizes of the buckets can vary, based on removal. If your page_size is 256, and two items are taken out of a bucket, its actual size is now 254. There's no guarantee on pages having equal sizes in ActivityPub, and with collection filtering, this is pretty common. But it's worth noting.

Another downside is that in extreme situations, the bucket's actual size can go to zero! Although unlikely, when this happens, it's possible to delete the bucket and stitch up next and prev properties to connect the preceding and following buckets.

Summary

So, what are my main tips for ActivityPub implementers? Here's a quick summary.

• Have big pages – 128 or 256 items per page.
• Inline the items for small collections.
• If you're already using offset pagination, change to cursor pagination ASAP.
• If you're implementing from scratch, consider using bucket pagination.

Thanks for reading this far!