"Caching does not work if the data is different for everyone."
I think caching can work, but at a different level of granularity. Rather than cache a person's full timeline, which is composed of multiple sub-feeds (each of which requires a database query), cache the data from the sub-feeds themselves, then recombine them on every page load. This would significantly lower the number of database queries, as each cache element would be invalidated only when its "owner" sends a tweet. This solution would be much more CPU intensive on the application servers, though, and Ruby may not be the best tool for the job if that were the case.
"Traditional page caching does not work" would have been a better way for me to phrase that. I don't mean to suggest that no caching anywhere in the stack (machine or software) will be used--that would be absurd. I only mean that the cheap and easy page caching used to scale most web apps where you keep pages or chunks of pages in a cache goes out the window for twitter.
I think caching can work, but at a different level of granularity. Rather than cache a person's full timeline, which is composed of multiple sub-feeds (each of which requires a database query), cache the data from the sub-feeds themselves, then recombine them on every page load. This would significantly lower the number of database queries, as each cache element would be invalidated only when its "owner" sends a tweet. This solution would be much more CPU intensive on the application servers, though, and Ruby may not be the best tool for the job if that were the case.