design challenge

Good programmers like to solve interesting problems. Here is an interesting problem, and we'd love to see how you would tackle it.

the problem

You are an engineer at a purely hypothetical startup - lets call it Facebook. Your hypothetical boss - lets call him 'Mark' - comes over and says "I'd like you to build a feature called 'Newsfeed' that displays changes from your friends from all the various activities they are doing on the site." You agree, and now have to design said system.

the requirements

  • Ability to display the last 100 friend updates for a given user (news-feed)
  • Ability to retrieve the last 20 updates from a given person (mini-feed)
  • Ability to easily add any type of item to a persons feed
  • Scalable to tens of millions of users
  • Scalable for users with up to 10,000 friends
  • All data must be returned in under a second

the deliverables

We're not asking you to build this, but rather to explain how you would design it. What database tables would be involved? Application servers? Caching? There is no right answer per se - we just want to see how you think. Please submit your response using whatever tools you deem appropriate (MS Word, Ruby on Rails, pseudo-code, etc).