Read forward in time from last read message

[evanp]

One way for clients to efficiently use a reverse-chronological collection like the messages collection is to store a last-seen activity or object id.

To get the latest data, the client can get the latest page from the collection (first property), then follow the next properties of each page, until it finds a page with last-seen activity id in the items or orderedItems property. All the data that has been read is the "latest data". The client might show the latest items first, and then use scrolling to show earlier items.

The problem with this process in MLS is that the client state is very dependent on previous state. So, the client has to cache all the data in the latest pages until it finds the last-seen item, and then apply all the new activities in order, forwards in time, in order to calculate the current state. This takes time and memory.

One way to improve this process is to have a feature for jumping directly to the page with the last-seen activity, without reading all the later pages. Then, if the collection is bidirectionally navigable (it has next and prev links on each page), the client can navigate forward in time, up to the current page.

[trwnh]

this sounds like you would really want an event log for consistency

AS2-Vocab has https://www.w3.org/TR/activitystreams-vocabulary/#dfn-startindex which allows ordered collection paging to start from a certain point and go forward. i really think that MLS-relevant activities should be paginated forward-chronologically, not reverse-chronologically (in whichever resource they're exposed).

the endpoint used to retrieve MLS events/activities should probably support a cursor parameter for paginating forward. for example, if the MLS log was at /mls/, then one might request /mls/?since=134 to fetch MLS events "since" event 134. alternatively, http headers may be used, or POST with url-encoded parameters, or some other equivalent mechanism.

[mayel]

yeah cursor pagination seems ideal IMO 👍

[evanp]

I was thinking of having a specific property for the collection that would be an endpoint for jumping directly to the page with a particular item:

{
    "@context": ["https://www.w3.org/ns/activitystreams", "https://purl.archive.org/socialweb/mls"],
    "type": "OrderedCollection",
    "name": "Evan's incoming MLS messages",
    "id": "https://social.example/user/evan/messages",
    "totalItems": 30108,
    "first": "https://social.example/user/evan/messages/uSQOayNw",
    "pageWithItem": "https://social.example/findPage?collection=https://social.example/user/evan/messages"
}

You could use this endpoint to get the page that includes an item, by adding an id parameter with ID of the object you're trying to find:

GET /findPage?collection=https://social.example/user/evan/messages&id=https://other.example/activity/UuvuKpHf HTTP/1.1
Host:  social.example
Authorization: Bearer E6DSD_dbM-Sc8lHAulPoa

If it's found, it would return the page with that object as one of its items:

200 OK
Content-Type: application/activity+json
Location: https://social.example/user/evan/messages/x3cEe7gk

{
    "@context": ["https://www.w3.org/ns/activitystreams", "https://purl.archive.org/socialweb/mls"],
    "type": "OrderedCollectionPage",
    "name": "A page of Evan's incoming MLS messages",
    "id": "https://social.example/user/evan/messages/x3cEe7gk",
    "partOf": "https://social.example/user/evan/messages",
    "next": "https://social.example/user/evan/messages/RN-mCSCX",
    "prev": "https://social.example/user/evan/messages/aYXrTl9A",
    "items": [
        "https://third.example/activity/tXWDPWDx",
        "https://other.example/activity/UuvuKpHf",
        "https://social.example/activity/8GZ3w_sY",
        "https://photo.example/activity/MsTM-AsF"
    ]
}

If it's not found (the id is not a member of the collection), it returns a 404.

404 Not Found
Content-Type: application/problem+json

{
    "status": 404,
    "type": "about:blank",
    "description": "The id is not found in this collection"
}

This is only useful if it's a paged collection and the pages are bidirectionally navigable (both forward and back).

[benpate]

I'll vote for using a standard GET with URL parameters. We're not changing any data on the server, so this is better than a POST. The same goes for HTTP headers: this is a less common, and more difficult way of sending parameters like this.

Could we just specify something like this? https://my.server.social/collection?startIndex=123

[benpate]

Also: is there any mechanism for us to specify straight chronological ordering? I don't know of any examples in other ActivityPub collections, but it would be really useful for us to define it that way here.

@trwnh - is there any prior art on this?

[TallTed]

If I understand the prior art question correctly, you might look to the codebase of DreamWidth, which forked from LiveJournal after Russia closed its previously open source. Readers are able to choose to read the comments on a post as purely chronological, or as fully threaded. They can also choose to treat any comment as a temporary root, such they can the comments on that comment as purely chronological, or as fully threaded. Etc.

[benpate]

Thanks, @TallTed. Yeah, I do something similar in my own UX. I’m mostly looking for something similar at the JSON level.

I think ActivityPub OrderedCollections are supposed to be sorted in reverse chronological order — though I can’t find that reference in the spec to confirm.

I’d love to define our MLS messages collection as ascending chronological order, but I don’t know how much that would run counter to standard ActivityPub conventions.

[trwnh]

re: query parameters see https://datatracker.ietf.org/doc/html/rfc8820#name-uri-queries for potential pitfalls of defining them, although in this case it should probably be fine as long as the web server knows to send query parameters to the same resource in its configuration (think nginx location blocks) and the parameters don't conflict with any future extensions.

re: prior art on forward chronological ordering, i think the only reason reverse-chron was specified in activitypub was out of a desire to have reverse-chronological timelines. reverse-chron means that fetching the first page should return the newest results, which are generally considered "most relevant" by the activitypub authors and anyone with a bias toward recency. but in MLS (and any other event log structure, really), you MUST process every event in-order, or else you will arrive at an inconsistent state. the way to do this without making it unnecessarily harder on yourself and everyone is to present MLS events (or their enveloped forms) in forward-chronological order (because that is how you will be generally processing them). a client/consumer then only needs to keep track of what was the last seen/processed event, and request any events in-order that arrived after that cursor (so that they can apply each event as a progressive update or state change).

in practice you can split messages into "cryptographic state" messages and "framed content" messages, but you cannot decrypt contentful messages without knowing which epoch they came from (determined by the cryptographic state). it is possible to store the decrypted messages and present them in any order, but this should only be done at the client which is the final "end" of the e2ee communication channel.

another advantage of forward-chron when it comes to paging is that it allows you to have more stable paging. if "page 1" is the most recent 10 items, then inserting 1 item will invalidate the cache of every page. in general, inserting an item at a certain position will shift every item after that position. if you use forward-chron, you simply append the new item at the end, and all previous pages before that are unchanged and unaffected. removing an item still affects the items and pages after that point, but this can be mitigated by using cursor pagination instead of standard paging.

some other resources regarding this:

• Musings on paginating chronological content https://css-tricks.com/musings-on-paginating-chronological-content/
• When Next Means Previous and Forward is Back https://osiatynska.com/blog/2013/06/02/disambiguation
  • "Opting for older / newer is one clear solution that is both necessary and sufficient for unambiguous navigation."

[trwnh]

@benpate wrote:

I think ActivityPub OrderedCollections are supposed to be sorted in reverse chronological order — though I can’t find that reference in the spec to confirm.

I’d love to define our MLS messages collection as ascending chronological order, but I don’t know how much that would run counter to standard ActivityPub conventions.

see w3c/activitypub#376 for that issue, raised 2.5 years ago and accepted as an errata a little over a year ago. the requirement only applies to the inbox/outbox in practice (and the other collections defined in activitypub, only if they are ordered). it does not apply to all as:OrderedCollections, and the MLS work is not part of the ActivityPub spec (rather, it is adjacent to it).

[trwnh]

@benpate wrote:

Also: is there any mechanism for us to specify straight chronological ordering? [...] is there any prior art on this?

Ah, I think I understand the question a bit better now... you mean a property to signal that the collection is ordered forward-chron instead of reverse-chron, right?

If so, then there is https://w3id.org/fep/1985 which I wrote up a year ago based on an earlier SocialHub thread from 2020 regarding how to evolve collections to be more useful: https://socialhub.activitypub.rocks/t/pre-fep-evolving-orderedcollection-to-be-more-useful/4608

Currently, I don't entirely know if FEP-1985 is the ideal solution, although it works as written. The shortcomings I haven't had time to deal with yet are how to differentiate between ordered collections and sorted collections, i.e., how do we know when the ordering is by simple insertion order vs. by some other criteria, and will the server enforce this sorting for you or do you need to be really careful about issuing your Add/Remove/etc activities? Right now the difference between as:OrderedCollection and as:Collection is basically only the difference between html:ol and html:ul -- one is ordered, the other is unordered. But in the case of sorted collections, you would want more information. In a way, all OrderedCollections are implicitly sorted by insertion time, but that insertion time isn't generally exposed. In HTML, this is where html:li would come in as a "list item", and you can imagine a similar abstraction for as:OrderedCollection? say something like _:CollectionItem which wraps the item in the item in the collection and can be used to make further statements about, say, position in the collection, or indicating the datetime that an activity arrived rather than the datetime it was published. See also http://schema.org/ListItem and http://schema.org/ItemList for that kind of abstraction.

Well... I guess if you take that as "prior art", then we can also for example look at what html:ol does: https://developer.mozilla.org/en-US/docs/Web/HTML/Reference/Elements/ol

• <ol reversed> indicates the order is "reversed", which in this context means "high to low" or "greater values first" or "descending order". This is because the specified default in HTML (or most user agents, rather) is "ascending order". Something like this could work, I guess, if you defined a property like _:reversed and say that the default value is true. Then you would need to know what the default ordering is, I suppose... ActivityPub is kind of the outlier here because most other systems I can think of generally assume "reversed" would match HTML's expectation, not ActivityPub's expectation.
  • <ol type=> indicates the "type" of the ordering. You can instruct user-agents to order the list numerically (1), or to use alphabetical letters (A for uppercase, a for lowercase), or to use roman numerals (I for uppercase, i for lowercase). This allows making sublists where the counter can indicate item 2.i or 1.a.iii, for example.
  • <ol start=> indicates where the list should start counting up (or down) from. You can instruct user-agents to start at 98, for example, then render 3 ordered items as "98.", "99.", "100." (or equivalent, depending on type). You can sort of think of this like as:startIndex, I guess?

[evanp]

I’d love to define our MLS messages collection as ascending chronological order, but I don’t know how much that would run counter to standard ActivityPub conventions.

I don't think that's what you want, Ben.

Ordering the messages chronologically would mean that the first page would always be the oldest messages, and you'd have to read forward in time to the very last page, which has the newest messages. This would mean that as messages are added to the end, every time you load messages, it takes longer and longer and longer to load them.

It also means that, on the server side, you are keeping the least relevant messages, sent months or years ago, at the top of your cache, getting reloaded over and over.

Of the three options (straight reverse chron, reverse chron with a quick finder endpoint as proposed in this issue, and straight chron), straight chron seems like the worst structure.

[trwnh]

@evanp wrote:

you'd have to read forward in time to the very last page, which has the newest messages

No? You can load the last page and read backward in time through previous pages.

[benpate]

Sorry, I left out a detail. I think what I mean is sorting things chronologically AND having a standard index to use as a starting point.

As a placeholder, I'm using URLs that look like: https://server.socal/@user/pub/mlsInbox?after=[URL of last-retrieved value]. This is working great for me right now, and I think it's what you're suggesting as well.

If that's all true, then I think we should define that parameter so that clients can use this inbox with as little fuss as possible.

[evanp]

@evanp wrote:

you'd have to read forward in time to the very last page, which has the newest messages

No? You can load the last page and read backward in time through previous pages.

Yes, if the collection is bidirectional/doubly-linked.