Isn’t cache invalidation the hardest part of the feed? Once a user with millions of followers tweets, doesn’t that essentially invalidate millions of caches? That doesn’t sound like a trivial problem.

Because you can't edit tweets, the database is monotonically increasing (append-only) so scaling it isn't that hard. Cache invalidation basically just adds a new item. Deleting a tweet actually would be the harder/more expensive operation, but it's also less common.

Editing a tweet is also easy because the feeds would only store its id. You'd only need to invalidate one cache where the tweet object itself is stored.