In response to my recent post about Twitter's architectural woes, Robert Scoble penned a missive entitled Should services charge “super users”? where he writes

First of all, Twitter doesn’t store my Tweets 25,000 times. It stores them once and then it remixes them. This is like saying that Exchange stores each email once for each user. That’s totally not true and shows a lack of understanding how these things work internally.

Second of all, why can FriendFeed keep up with the ever increasing load? I have 10,945 friends on FriendFeed (all added in the past three months, which is MUCH faster growth than Twitter had) and it’s staying up just fine.

My original post excerpted a post by Isreal L'Heureux where he pointed out that there are two naive design choices one could make while designing a system like Twitter. When Robert Scoble posts a tweet you could either

    1. PUSH the message to the queue’s of each of his 6,864 24,875 followers, or
    2. Wait for the 6,864 24,875 followers to log in, then PULL the message.

Isreal assumed it was #1 which has its set of pros and cons. The pro is that fetching a users inbox is fast and the inbox can easily be cached. The con is that the write I/O is ridiculous. Robert Scoble's post excerpted above argues that Twitter must be using #2 since that is what messaging systems like Microsoft Exchange do.

The feature of Exchange that Robert is talking about is called Single Instance Storage and is described in a Microsoft knowledge base article 175706 as follows

If a message is sent to one recipient, and if the message is copied to 20 other recipients who reside in the same mailbox store, Exchange Server maintains only one copy of the message in its database. Exchange Server then creates pointers.
...
For example, assume the following configuration:
Server 1 Mailbox Store 1: Users A, B, and C
Server 2 Mailbox Store 1: User D

When User A sends the same message to User B, User C, and User D, Exchange Server creates a single instance of the message on server 1 for all three users, because User A, User B, and User C are on the same server. Even the message that is in User A's Sent Items folder is a single instance of the messages that is in the Inboxes of User B and User C. Because User D is on a different server, Exchange Server sends a message to server 2 that will be stored on that server.

So now we know how Exchange's single instance storage works we can talk about how it helps or hinders the model where users pull messages from all the people they are following when they log-in. A pull model assumes that you have a single instance of each message sent by a Twitter user and then when Robert Scoble logs in you execute a query of the form

SELECT TOP 20 messages.author_id, messages.body, messages.publish_date
FROM  messages
WHERE messages.author_id  in (SELECT following.id from following where user_id=$scoble_id)
ORDER BY messages.publish_date DESC;

in this model there's only ever one instance of a message and it lives in the messages table. Where does this break down? Well, what happens when you have more than one database per server or more than one set of database servers or more than one data center?  This is why Exchange still has multiple message instances per mailbox store even if they do have single instances shared by all recipients of the message in each mailbox store on a single server.

How much does having multiple databases or multiple DB servers affect the benefits of single instancing of messages? I'll let the Exchange team answer that with their blog post from earlier this year titled Single Instance Storage in Exchange 2007 

Over the years, the importance of single instance storage (SIS) in Exchange environments has gradually declined. Ten years ago, Exchange supported about 1000 users per server, with all users on a single database. Today, a typical mailbox server might have 5000 users spread over 50 databases. With one-tenth as many users per database (100 users vs. 1000 users), the potential space savings from single-instancing is reduced by 10x. The move to multiple databases per server, along with the reduction in space savings due to items being deleted over time, means that the space savings from SIS are quite small for most customers. Because of this, we've long recommend that customers ignore SIS when planning their storage requirements for Exchange.
...
Looking forward
Given current trends, we expect the value of single instance storage to continue to decline over time. It's too early for us to say whether SIS will be around in future versions of Exchange. However, we want everyone to understand that it is being deemphasized and should not be a primary factor in today's deployment or migration plans.

At the end of the day, the cost of a naive implementation of single instancing in a situation like Twitter's is latency and ridiculous read I/O. You will have to query data from tens of thousands of users across multiple database every time Robert Scoble logs in.

Exchange gets around the latency problem with the optimization of always having an instance of the message in each database. So you end up with a mix of both a pull & push model. If Scoble blasts a message out to 25,000 recipients on an Exchange system such as the one described in the blog post by the Exchange team, it will end up being written 250 times across 5 servers (100 users per database, 5000 users per server) instead of 25,000 times as would happen in a naive implementation of the PUSH model. Then when each person logs-in to view their message it is assembled on demand from the single instance store local to their mail server instead of trying to read from 250 databases across 5 servers as would happen in a naive implementation of the PULL model.

Scaling a service infrastructure is all about optimizations and trade offs. My original post wasn't meant to imply that Twitter's scaling problems are unsolvable since similar problems have obviously been solved by other online services and Enterprise products in the messaging space. It was meant to inject some perspective in the silly claims that Ruby on Rails is to blame and give readers some perspective on the kind of architectural problems that have to be solved.

Now Playing: Lil Wayne - Got Money (feat. T-Pain)


 

Tuesday, May 27, 2008 6:46:17 AM (GMT Daylight Time, UTC+01:00)
Does anyone have any actual knowledge about how Twitter is architected? Anyone who says it's "definitely this" or "definitely not that" is definitely wrong. The 140 char limit would seem to make Twitter rather "doable".

I actually think Ruby and Rails could be a culprit because it's not very well suited to the optimizations that would be necessary to make Twitter work well.
pwb
Tuesday, May 27, 2008 8:25:56 AM (GMT Daylight Time, UTC+01:00)
The point of Dare’s original post (and the post it quoted) was to say that there were only a couple ways they could be doing it. The one thing you can count on from tech companies is that they are eager to self promote when they’ve done something revolutionary so since Twitter has never mentioned any magic bullet to solve this problem you can pretty much guarantee they are using one of the two options given.

As far as Ruby on Rails, I’m not a fan but I doubt it could be the root of their problems. In the end, what Twitter does is not really a complicated programming task. It really is basically a data front end so while Rails might hurt them on code optimization I doubt it’s responsible for the wholesale system collapses.

What I think is a much more likely culprit, and what I think Dare’s post alludes to, is Twitter’s infrastructure. Again, Twitter is basically just a database front end but its pulling/writing massive amounts of data which makes it one of the toughest architecture jobs out there. Companies like Google and Amazon have gone to the trouble of architecting their own data systems (Bigtable and Dynamo respectively) to deal with problems that are equal in size.

I doubt Twitter with its 16 person workforce has come anywhere near building an infrastructure capable of dealing with the issues their system will require to scale.
Monday, June 2, 2008 2:15:38 PM (GMT Daylight Time, UTC+01:00)
I know nothing about how Twitter is actually built, and I'd like to see far more stats before making any guesses on a better design, but the service appears to be read intensive. Having been in similar situations before with critical DB bottlenecks, my gut says ditch the DB.

I blogged my thoughts here

Comments are closed.