6 ms·

> You can also say what you think would be the number of followers (millions+), what would be the time needed for a write you a database (~millisecond each) and

> You can also say what you think would be the number of followers (millions+), what would be the time needed for a write you a database (~millisecond each) and why that won't match 3 seconds, so you know how much time you have per follower. While we are on the topic I am really curious to know how they solve it actually.

varunsaini 6y ago
Twitter has changed this approach few times I guess, earlier it used to be simply insert tweet into a collection of tweets, and then when you load use timeline, look up the people they follow and find/merge those tweets. But it's going to create a lots of load on systems. Another approach is to maintain a cache of user's timeline(mailbox of tweets), when user posts a tweet, lookup all the people who follow that user, and insert the tweet into each or their timeline cache. results have be pre-computed, so less load. Both approaches fails when you have folks with lots of followers, so may be they use a hybrid of these approaches. this is Discussed in detail in "Designing Data-Intensive applications" book.
- jsjohnst 6y ago
  > Both approaches fails when you have folks with lots of followers The traditional mailbox architectural model can be improved via a few methods though to increase scale. 1. The entire tweet doesn’t need to be duplicated for each follower, only a lookup reference (“ID”) to the tweet. 2. Unlike in a traditional mailbox sense, each user’s timeline is a bounded collection. So rather than maintaining every tweet for every followed user in the timeline, it’s capped to the X most recent.
viraptor 6y ago
My guess would be lots of distributed queues, some resources dedicated to heavy lifting of few vs random noise of everyone else, and storage layer which allows lots of append traffic without blocking. Maybe some storage special casing like "randos get their tweets serialised on your timeline, but because you're following Taylor Swift we'll just query that common feed in parallel rather than copying it". They've got lots of engineering blog content, there may be a better answer here https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale.html https://blog.twitter.com/engineering/en_us/topics/infrastruc...
asdfasgasdgasdg 6y ago
I don't work at twitter, but one thing you can know for sure is that the tweet needs to be distributed to multiple machines to meet this performance requirement. A single machine probably could probably send three million trivial messages in three seconds, but if you mix in any business logic it's not gonna happen. What I'd do is have a shared highfanout queue. Once you have more than say 10k followers your tweets go to the high fanout cluster. You'd have hundreds or low thousands of machines, each of which serves a slice of consumers. When the tweet is sent, you write it to this queue. Each consumer is pulling from one of the shards. If you have a thousand workers that means each worker only needs to send a thousand messages in three seconds, which is very doable. Only about 180k twitter users have more than 20k followers. If each users tweets every 200 seconds, which seems like a high estimate, then that implies a load of about 1kwps for this system, which seems doable, especially if you have a small intermediate layer of distributors which consolidates the write load. That's just my sketch.
- brianwawok 6y ago
  Right. Seems very doable to verbally sketch it if you have ever seen something like a fan out. If you only worked in single Wordpress servers, I could see it a big leap.
  - asdfasgasdgasdg 6y ago
    To be fair, having worked in a twitter-like domain is a valid selection criterion for any internet company planning to handle lots of traffic. It is possible that working on wordpress servers would not prepare you very well for such a job. Being unable to even articulate a basic strategy for handling a problem like this would be something I would consider a yellow flag for a potential teammate. It would make me question whether the person would be able to help me in my work.
    - alexbanks 6y ago
      If someone's resume was only wordpress sites, and they somehow made it into a technical interview for a team that managed twitter-like systems, I'd consider that a critical failure of the selection process. As an interviewer, I would try and make that experience as painless as possible for the candidate, and if not totally shocked by their abilities, have very direct conversations about the shortcomings of the selection process with whoever brought them in in the first place.
zackbloom 6y ago
I can’t speak to how it’s actually solved, but I can give a sketch from my experience. The game is generally to (1) consider denormalizing data and (2) rethink when you have the computer do work. Denormalizing data refers to moving away from a model where you store one and only one copy of each ‘tweet’ in something like a relational database, to a model where you might actually store a separate copy of each tweet for each follower. That is kind of an extreme example of denormalization, but it’s a good way to illustrate how you could make it near-instant for any user to load their twitter homepage. If you stored the interesting tweets of every person I follow in a table just for me, you would make ‘reads’ (loading my homepage) incredibly cheap, but writes (someone with a lot of followers tweeting) very expensive. Those trade offs exist everywhere in a system like this, which is (2), you get to decide when you do work. If celebrities with a million followers tweet an average of once a second, but people load their feeds a hundred thousand times a second, it is entirely acceptable to do 10000x more work for a celebrity tweet posting. This is actually the same concept behind using indexes in relational databases, but done more explicitly. My personal answer to this question would probably start somewhat space-innefficient. I would take each tweet and put it into an event processing queue which writes a reference to it into each followers feed. This sounds nasty, but it scales with the number of writes, not reads, and we have less writes, and it scales linearly with the follower count of the writer. I would then improve efficiency by thinking about dormant accounts, caching, and maybe doing a bit more work on read.
- gonzo41 6y ago
  The other requirement worth thinking about is the 3 seconds. How many followers are going to be watching for that 3 seconds to matter. And how much slack can be in that? Could 1.5 million followers be sleeping and not need the tweet for a few hours or only when they next sync.
  - alexbanks 6y ago
    If it's a pub/sub model, you wouldn't care at all about how many were watching right? You'd just publish. And for something like Twitter, you'd probably Publish but then also log to some kind of "Notifications" store, so if a user did care but was not actively watching, on their next subscription they'd receive the messages they'd missed.
dehrmann 6y ago
One trick to problems like this is to solve it differently for celebrities, head queries, etc., than for less commonly accessed data. Essentially have two different systems and combine the data because designing a single system that meets both scale requirements is harder.
ahpearce 6y ago
As of 2017, pretty sure Redis is a large part of it: https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale.html https://blog.twitter.com/engineering/en_us/topics/infrastruc...

varunsaini 6y ago

Twitter has changed this approach few times I guess, earlier it used to be simply insert tweet into a collection of tweets, and then when you load use timeline, look up the people they follow and find/merge those tweets. But it's going to create a lots of load on systems. Another approach is to maintain a cache of user's timeline(mailbox of tweets), when user posts a tweet, lookup all the people who follow that user, and insert the tweet into each or their timeline cache. results have be pre-computed, so less load. Both approaches fails when you have folks with lots of followers, so may be they use a hybrid of these approaches. this is Discussed in detail in "Designing Data-Intensive applications" book.

jsjohnst 6y ago
> Both approaches fails when you have folks with lots of followers The traditional mailbox architectural model can be improved via a few methods though to increase scale. 1. The entire tweet doesn’t need to be duplicated for each follower, only a lookup reference (“ID”) to the tweet. 2. Unlike in a traditional mailbox sense, each user’s timeline is a bounded collection. So rather than maintaining every tweet for every followed user in the timeline, it’s capped to the X most recent.

viraptor 6y ago

My guess would be lots of distributed queues, some resources dedicated to heavy lifting of few vs random noise of everyone else, and storage layer which allows lots of append traffic without blocking. Maybe some storage special casing like "randos get their tweets serialised on your timeline, but because you're following Taylor Swift we'll just query that common feed in parallel rather than copying it". They've got lots of engineering blog content, there may be a better answer here https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale.html https://blog.twitter.com/engineering/en_us/topics/infrastruc...

asdfasgasdgasdg 6y ago

I don't work at twitter, but one thing you can know for sure is that the tweet needs to be distributed to multiple machines to meet this performance requirement. A single machine probably could probably send three million trivial messages in three seconds, but if you mix in any business logic it's not gonna happen. What I'd do is have a shared highfanout queue. Once you have more than say 10k followers your tweets go to the high fanout cluster. You'd have hundreds or low thousands of machines, each of which serves a slice of consumers. When the tweet is sent, you write it to this queue. Each consumer is pulling from one of the shards. If you have a thousand workers that means each worker only needs to send a thousand messages in three seconds, which is very doable. Only about 180k twitter users have more than 20k followers. If each users tweets every 200 seconds, which seems like a high estimate, then that implies a load of about 1kwps for this system, which seems doable, especially if you have a small intermediate layer of distributors which consolidates the write load. That's just my sketch.

brianwawok 6y ago
Right. Seems very doable to verbally sketch it if you have ever seen something like a fan out. If you only worked in single Wordpress servers, I could see it a big leap.
- asdfasgasdgasdg 6y ago
  To be fair, having worked in a twitter-like domain is a valid selection criterion for any internet company planning to handle lots of traffic. It is possible that working on wordpress servers would not prepare you very well for such a job. Being unable to even articulate a basic strategy for handling a problem like this would be something I would consider a yellow flag for a potential teammate. It would make me question whether the person would be able to help me in my work.
  - alexbanks 6y ago
    If someone's resume was only wordpress sites, and they somehow made it into a technical interview for a team that managed twitter-like systems, I'd consider that a critical failure of the selection process. As an interviewer, I would try and make that experience as painless as possible for the candidate, and if not totally shocked by their abilities, have very direct conversations about the shortcomings of the selection process with whoever brought them in in the first place.

zackbloom 6y ago

I can’t speak to how it’s actually solved, but I can give a sketch from my experience. The game is generally to (1) consider denormalizing data and (2) rethink when you have the computer do work. Denormalizing data refers to moving away from a model where you store one and only one copy of each ‘tweet’ in something like a relational database, to a model where you might actually store a separate copy of each tweet for each follower. That is kind of an extreme example of denormalization, but it’s a good way to illustrate how you could make it near-instant for any user to load their twitter homepage. If you stored the interesting tweets of every person I follow in a table just for me, you would make ‘reads’ (loading my homepage) incredibly cheap, but writes (someone with a lot of followers tweeting) very expensive. Those trade offs exist everywhere in a system like this, which is (2), you get to decide when you do work. If celebrities with a million followers tweet an average of once a second, but people load their feeds a hundred thousand times a second, it is entirely acceptable to do 10000x more work for a celebrity tweet posting. This is actually the same concept behind using indexes in relational databases, but done more explicitly. My personal answer to this question would probably start somewhat space-innefficient. I would take each tweet and put it into an event processing queue which writes a reference to it into each followers feed. This sounds nasty, but it scales with the number of writes, not reads, and we have less writes, and it scales linearly with the follower count of the writer. I would then improve efficiency by thinking about dormant accounts, caching, and maybe doing a bit more work on read.

gonzo41 6y ago
The other requirement worth thinking about is the 3 seconds. How many followers are going to be watching for that 3 seconds to matter. And how much slack can be in that? Could 1.5 million followers be sleeping and not need the tweet for a few hours or only when they next sync.
- alexbanks 6y ago
  If it's a pub/sub model, you wouldn't care at all about how many were watching right? You'd just publish. And for something like Twitter, you'd probably Publish but then also log to some kind of "Notifications" store, so if a user did care but was not actively watching, on their next subscription they'd receive the messages they'd missed.

dehrmann 6y ago

One trick to problems like this is to solve it differently for celebrities, head queries, etc., than for less commonly accessed data. Essentially have two different systems and combine the data because designing a single system that meets both scale requirements is harder.

ahpearce 6y ago

As of 2017, pretty sure Redis is a large part of it: https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale.html https://blog.twitter.com/engineering/en_us/topics/infrastruc...