In-memory thread cache

[novacrazy]

Due to the performance limitations of recursive queries, it would be very useful in the future to create an in-memory thread structure to cache the last/top N messages to a certain depth, for query-less rapid access. Treat it like an LRU cache based on room/thread accesses, so the most in-demand rooms/threads can avoid a large chunk of work. For the purpose of this, an entire room is a top-level thread. This has the added benefit of the listing of posts in a user-board room also being cached.

This is partially inspired by https://slack.engineering/real-time-messaging/

However, I want to extend this to user-board rooms and posts, with the full tree structure. As of writing this I'm unsure what the tree should look like, as it might need to support varying traversal conditions and filtering.

type MsgId = Snowflake;
type RoomOrParentId = Snowflake;

// 16 bytes
struct CachedMessage {
    msg_id: MsgId,
    parent_id: RoomOrParentId,
}

struct Cache {
    threads: scc::HashCache<RoomOrParentId, Tree<CachedMessage>>,
    messages: scc::HashMap<MsgId, Message>,
}

perhaps key by (RoomOrParentId, SortMethod) where SortMethod could be Top/New/etc., so those get their own sorted trees.

Furthermore, we'll need to track some kind of threshold for cache insertion, such that we aren't constantly thrashing it with small posts. The cache should only be used when the time spent doing repeated work becomes significant for a single post.

[novacrazy]

Forgot to mention that per-message access is so Messages can be updated without invalidating the entire tree. Things such as reactions and voting will cause frequent updates that don't change the layout of the tree. Perhaps the exception to that would be if it changes the sort order of siblings in the tree.