Consider applying fan-out pattern to timelines

[tesaguri]

Currently, the timeline service runs a complex query every time a timeline is fetched:

https://github.com/kitsune-soc/kitsune/blob/8a88fb32468ec89f349db17c2b19155c58adbb40/kitsune/src/service/timeline.rs#L67-L100

Since fetching the timeline is a frequently performed task, you can imagine how much cost this will incur at scale.

You can make the fetching cost O(1) by computing the content of timelines when the posts are made instead of when the timeline is fetched: when a local post is made or a remote post is pushed, the server would look up all the followers of the author of the post and push ("fan-out") the post ID to their "timelines" (list of post IDs stored in Redis), and when fetching the timeline, the server simply pulls the stored post IDs and queries the database by the post IDs to get the contents ("hydrate"), which is far cheaper operation than the complex query.

Things get more complicated when you consider timelines of inactive users and posts from celebrities with millions of followers, but I think that explains the basics of the idea.

The approach is essentially the same as what Twitter does (as explained in a presentation by its employee, Timelines at Scale, which has quite interesting insights on its own). Mastodon also employs this pattern (Relevant code: app/lib/feed_manager.rb, app/models/feed.rb, app/services/fan_out_on_write_service.rb). Misskey is considering adopting this pattern (misskey-dev/misskey#9325).

This approach incurs more cost on the write time, but it pays well by the reduction of read-time cost. Also, you may well end up implementing a similar logic anyway if you are going to implement push notifications or a streaming API.

Another trade-off is that the approach caps the number of posts that can be fetched from the timeline. The length of home timeline of Twitter and Mastodon is limited to 800 for this reason.

The implementation would arguably be more complicated and the design choice would involve certain trade-offs, so I don't suggest that this should be implemented (at least, not immediately). But I think it is still worth considering, so that, for example, Kitsune can avoid making architectual decisions incompatible to the design without even thinking about it.

[aumetra]

Thanks for putting the idea here. I thought about using this pattern for the reasons you mentioned, making timeline computation cheaper.

But yeah, as you said, there are a lot of factors to be considered before adapting this pattern. I don't think we made any decisions yet that would make this approach incompatible yet, we also sealed the fetching of the actual timelines behind a service method, so we could swap out the underlying fetch logic without changing any other code.

[aumetra]

We could probably prototype a generic fan-out mechanism as a crate that just lives inside the crates directory for now, without enabling it by default (or make this a compile-time feature?)

Because we have a lot of the necessary architecture set-up to implement this. We already emit events on post creation and deletion, meaning we could define an event-driven service that adds/removes the posts to/from the timelines

[tesaguri]

Well, it's not that I'm very interested in seeing this implemented in the short term. I intended this issue to be something like a placeholder in case someday Kitsune went viral and some instances actually became in need of it (like Misskey did).

That being said, starting with a prototype with which we can experiment sounds reasonable to me. Perhaps it might not result in significant impact for home timelines while the user base is small, but, come to think of it, the public timeline for example might benefit from it even for small and medium instances.

[aumetra]

I generally agree with this sentimemnt, but even on small instances that are very well federated, the home timeline computation could take a while when done on-demand since, even with indices, the query time will increase with more posts.

But yeah, some prototyping and experimentation inside a seperate crate would probably be interesting and fun.