Manufacturing Twitter on One Machine? 100Gbps NICs and NVMe are quick

On this publish I’ll try the enjoyable stunt of designing a system that might serve the complete manufacturing load of Twitter with a lot of the options intact on a single (very highly effective) machine. I’ll begin by exhibiting off a Rust prototype of the core tweet distribution information construction dealing with 35x full load by becoming the recent set in RAM and parallelizing with atomics, after which do math round how fashionable high-performance storage and networking would possibly allow you to serve a close-to-fully-featured Twitter on one machine.

I wish to be clear that is meant as academic enjoyable, and never as a good suggestion, no less than going all the best way to 1 machine. In the midst of the publish I discuss all of the alternate-universe infrastructure that would want to exist earlier than doing this is able to be sensible. There’s additionally some options which may’t match, and lots of methods I’m probably not assured in my estimates.

I’ve now spent a few week of evenings and a 3 weekends doing analysis, math and prototypes, step by step determining the best way to match increasingly options (photographs?! ML?!!) than I initially thought I may match. We’ll begin with the very fundamentals of Twitter after which undergo step by step increasingly options, in what I hope can be an enchanting tour of another world of methods design the place net apps are constructed like excessive efficiency buying and selling methods. I’ll additionally analyze the minimal price configuration utilizing a number of extra sensible machines, and discuss in regards to the sensible disadvantages and benefits of such a design.

Right here’s an summary of the options I’ll discuss and whether or not I believe they may match:

• Timeline and tweet distribution logic: Primarily based on a prototype, matches simply on a handful of cores once you pack latest tweets in RAM supplemented with NVMe.
• HTTP(S) request serving: Sure. HTTP matches, HTTPS matches solely due to session resumption.
• Picture serving: A detailed match with tough estimates, however perhaps doable with a number of 100Gbit/s networking playing cards. You want effort to keep away from excessive bandwidth prices.
• Video, search, adverts, notifications: Most likely these wouldn’t match, and it’s actually tough to estimate whether or not they would possibly.
• Historic tweet and picture storage: Tweets match on a specialised server, however photographs don’t, you could possibly match perhaps 4 months of photographs with a 48x HDD storage pod.
• ML-based timeline: A100 GPUs are insane and might run an honest LM in opposition to each tweet and dot-product the embeddings with each consumer.

Let’s get this unhinged reply to a common systems design interview question began!

Core Tweet Distribution

Let’s begin with the unique core of Twitter: Customers posting text-based tweets to feeds which others observe with a chronological timeline. There’s mainly two methods you could possibly do that:

1. The timeline web page pulls tweets in reverse-chronological order from every observe till sufficient tweets are discovered, utilizing a heap to merge them. This requires retrieving lots of tweets from totally different feeds, the problem is making that quick sufficient.
2. Every tweet will get pushed into cached timelines. Pushing tweets may be quicker than retrieving them in some designs, and so this may be well worth the storage. However movie star tweets have large fanout so both want background processing or to be individually merged in, however you want a backup merge in any case in case a spread of timeline isn’t cached.

The systems design interview answers I can discover take the second method as a result of merging from the database on pageload could be too gradual with typical DBs. They use some type of background queue to do the tweet fanout writing right into a sharded timeline cache like a Redis cluster.

I’m undecided how actual Twitter works however I believe based mostly on Elon’s whiteboard photo and a few tweets I’ve seen by Twitter (ex-)workers it appears to be principally the primary method utilizing quick customized caches/databases and perhaps parallelization to make the merge retrievals quick sufficient.

How huge is Twitter?

While you’re not designing your methods to scale to arbitrary ranges by including extra machines, it turns into vital what order of magnitude the numbers are, so let’s attempt to get good numbers.

So, what number of tweets do we have to retailer? This Twitter blog post from 2013 offers figures for each day and peak charges, however these numbers are fairly previous.

By intense digging I discovered a researcher who left a pocket book public together with tweet counts from a few years of Twitter’s 10% sampled “Decahose” API and found the shocking undeniable fact that tweet price as we speak is across the identical as or decrease than 2013! Tweet price peaked in 2014 after which declined earlier than reaching new peaks within the pandemic. Elon just lately tweeted the same 500M/day quantity which matches the Decahose pocket book and 2013 weblog publish, so this appears to be true! Twitter’s lively customers grew the entire time so I believe this displays a shift from a “posting about your life to your folks” platform to an algorithmic content-consumption platform.

I did all my calculations for this undertaking utilizing Calca (which is nice though buggy, laggy and unmaintained. I’d swap to Soulver) and I’ll be together with all calculations as snippets from my calculation pocket book.

each day lively customers = 250e6 => 250,000,000
  

avg tweet price = 500e6/day in 1/s => 5,787.037/s
  

site visitors surge ratio = 535e6 / 340e6 => 1.5735
  

max sustained tweet price = avg tweet price * site visitors surge ratio  => 9,106.073/s
  

max tweet price = 150,000/second => 150,000/second
  

tweet content material max dimension = 560 byte
  

tweet content material avg dimension = 140 byte
  

metadata dimension = 2*8 byte + 5 * 4 byte => 36 byte
  

tweet avg dimension = tweet content material avg dimension + metadata dimension => 176 byte
  

tweet storage price = avg tweet price * tweet avg dimension in GB/day => 88 GB/day
  

tweet storage price * 1 12 months in TB => 32.1413 TB
  

tweet content material fastened dimension = 284 byte
  

tweet cache price = (tweet content material fastened dimension + metadata dimension) * max sustained tweet price in GB/day => 251.7647 GB/day
  

tweet cache dimension = tweet cache price * 2 day in GB => 503.5294 GB
  

avg following = 400
  

graph dimension = avg following * each day lively customers * 4 byte in GB => 400 GB
  

I believe the primary takeaway taking a look at these calculations is that many of those numbers are small numbers on the dimensions of contemporary computer systems!

Scorching set in RAM, relaxation on NVMe

Given these numbers, I’ll be utilizing the “your dataset fits in RAM” paradigm of methods design. Nonetheless it’s a bit extra sophisticated since our dataset doesn’t really slot in RAM.

Storing all of the historic tweets takes many terabytes of storage. However in all probability 99% of tweets considered are from the previous couple of days. This implies we are able to use a hybrid of RAM+NVMe+HDDs hooked up to our machine in a tiered cache:

• RAM will retailer our sizzling set cache and serve virtually all requests, so most of our efficiency will solely rely upon the RAM cache. It’s frequent to suit 512GB-1TB of RAM in a contemporary machine.
• Fashionable NVMe drives can retailer >8TB and do over 1 million 4KB IO operations per second per drive with latencies close to 100us, and you may connect dozens of them to a machine. That’s sufficient to serve all tweets, however we are able to decrease CPU overhead and add headroom by simply utilizing them for lengthy tail tweets and doubtless the follower graph (because it solely wants one IO op per timeline request).
• Some further 20TB HDDs can retailer the very previous very chilly tweets which can be mainly by no means accessed, particularly on the 2x compression I noticed with zstd on tweet textual content from a Kaggle dataset.

Nonetheless, tremendous excessive efficiency tiering RAM+NVMe buffer managers which may entry the RAM-cached pages virtually as quick as a standard reminiscence entry are principally solely detailed and benchmarked in academic papers. I don’t know of any good well-maintained open-source ones, LeanStore is the closest. You don’t simply want tiering logic, but in addition an NVMe write-ahead-log and checkpointing to make sure persistence of all adjustments like new tweets. This is without doubt one of the areas the place working Twitter on one machine is extra of a theoretical chance than a practical one.

So I simply prototyped a RAM-only implementation and I’ll handwave away the issue of the buffer supervisor (and issues like schema migrations) by saying it isn’t that related as to if the efficiency targets are doable as a result of most requests simply hit RAM and this paper shows that you can implement what is basically mmap with much more efficient page faults for under a ten% latency hit on non-faulting RAM reads plus some TLB misses from not having the ability to use hugepages. Though the true overhead is on the writes and faulting reads and from the handful of cores taken up for logging writes and managing checkpointing, cache reads and evictions.

My Prototype

I made a prototype (source on Github) in Rust to benchmark the in-memory efficiency of timeline merging and present that I may get it quick sufficient to serve the complete load. At it’s core is a minimalist pooling-and-indices type illustration of Twitter’s information, optimized to be pretty memory-efficient:

/// Go away room for a full 280 English character plus slop for accents or emoji.
/// An actual implementation would have an escape hatch for longer tweets.
pub const TWEET_BYTES: usize = 286;

// non-zero so choices together with a timestamp do not take any more room
// u32 since that is 100+ years of second-level precision and it lets us pack atomics
pub sort Timestamp = NonZeroU32;
pub sort TweetIdx = u32;

pub struct Tweet {
    pub content material: [u8; TWEET_BYTES],
    pub ts: Timestamp,
    pub likes: u32, pub quotes: u32, pub retweets: u32,
}

/// linked listing of tweets to make appending quick and keep away from house overhead
/// a linked listing of chunks of tweets would in all probability be quicker due to
/// cache locality of fetches, however I have never applied that
pub struct NextLink {
    pub ts: Timestamp, // so we all know whether or not to observe additional
    pub tweet_idx: TweetIdx,
}

/// High degree feeds use an atomic hyperlink so we are able to mutate concurrently
/// This successfully works by casting NextLink to a u64
pub struct AtomicChain(AtomicU64);

/// Since that is most of our RAM and cache misses we be sure it is
/// aligned to cache traces for type factors
#[repr(align(64))]
pub struct ChainedTweet {
    pub tweet: Tweet,
    pub prev_tweet: Choice<NextLink>,
}
assert_eq_size!([u8; 320], ChainedTweet); // 5 cache traces

/// We retailer the Graph in a format we are able to mmap from a pre-baked file
/// in order that our checks can load an actual graph quicker
pub struct Graph<'a> {
    pub customers: &'a [User],
    pub follows: &'a [UserIdx],
}

pub struct Consumer {
    pub follows_idx: usize, // index into graph follows
    pub num_follows: u32,
    pub num_followers: u32,
}

impl<'a> Graph<'a> {
    // We will use zero-cost abstractions to make our swimming pools extra ergonomic
    pub fn user_follows(&'a self, consumer: &Consumer) -> &'a [UserIdx] {
        &self.follows[user.follows_idx..][..user.num_follows as usize]
    }
}

pub struct Datastore<'a> {
    pub graph: Graph<'a>,
    // It is a tiny customized pool which mmaps an unlimited quantity of un-paged digital
    // tackle house. It is like a Vec which by no means strikes and allows you to append concurrently
    // with solely an immutable reference by utilizing an inside append lock.
    pub tweets: SharedPool<ChainedTweet>,
    pub feeds: Vec<AtomicChain>,
}

Then the code to compose a timeline is an easy utilization of Rust’s built-in heap:

/// Re-use these allocations so fetching might be malloc-free
pub struct TimelineFetcher {
    tweets: Vec<Tweet>,
    heap: BinaryHeap<NextLink>,
}

impl TimelineFetcher {
    fn push_after(&mut self, hyperlink: Choice<NextLink>, after: Timestamp) l

    pub fn for_user<'a>(&'a mut self, information: &Datastore,
      user_idx: UserIdx, max_len: usize, after: Timestamp
    ) -> Timeline<'a> {
        self.heap.clear(); self.tweets.clear();
        let consumer = &information.graph.customers[user_idx as usize];
        // seed heap with hyperlinks for all follows
        for observe in information.graph.user_follows(consumer) {
            self.push_after(information.feeds[*follow as usize].fetch(), after);
        }
        // compose timeline by popping chronologically subsequent tweet
        whereas let Some(NextLink { ts: _, tweet_idx }) = self.heap.pop() {
            let chain = &information.tweets[tweet_idx as usize];
            self.tweets.push(chain.tweet.clone());
            if self.tweets.len() >= max_len { break }
            self.push_after(chain.prev_tweet, after);
        }
        Timeline {tweets: &self.tweets[..]}
    }
}

I wrote a bunch of support code to load an old Twitter follower graph dump from 2010, which is about 7GB in-memory. I used a dump in order that I may seize a sensible distribution form of follower counts and overlaps, whereas becoming on my laptop computer. I then wrote a load-generator which selects each consumer with greater than 20 followers (round 7M) to tweet and each consumer with greater than 20 follows (round 9M) to view. I then generate 30 million recent tweets after which benchmark how lengthy it takes to compose timelines with them on all 8 cores of my laptop computer and get the next outcomes:

Initially added 15000000 tweets in 5.46230697s: 2746092.463 tweets/s.
Benchmarked including 15000000 tweets in 5.456315988s: 2749107.646 tweets/s.
Beginning fetches from 8 threads
Carried out 16714668 in 5.054423792s at 3306938.375 tweets/s. Avg timeline dimension 167.15 -> growth 100.63
Carried out 16723580 in 5.072738523s at 3296755.771 tweets/s. Avg timeline dimension 167.24 -> growth 100.69
Carried out 16724418 in 5.077739414s at 3293673.944 tweets/s. Avg timeline dimension 167.24 -> growth 100.69
Carried out 16752863 in 5.079175123s at 3298343.253 tweets/s. Avg timeline dimension 167.53 -> growth 100.86
Carried out 16715614 in 5.081238053s at 3289673.467 tweets/s. Avg timeline dimension 167.16 -> growth 100.64
Carried out 16741876 in 5.083800824s at 3293180.945 tweets/s. Avg timeline dimension 167.42 -> growth 100.80
Carried out 16729038 in 5.090990804s at 3286008.293 tweets/s. Avg timeline dimension 167.29 -> growth 100.72
Carried out 16748782 in 5.096817055s at 3286125.796 tweets/s. Avg timeline dimension 167.49 -> growth 100.84

So about 3.3M tweets distributed per core-second, when retrieved with a median timeline chunk of 167. And since it’s principally cache misses, per-core efficiency solely goes right down to 2.5M/sec when utilizing all 16 hyperthreads, permitting me to succeed in 40M tweets fetched per second on my laptop computer. Now I’m totally conscious my benchmark just isn’t the complete information dimension of Twitter nor essentially the most practical load I may create, however I’m simply making an attempt to get an estimate of what the complete scale efficiency would appear like and I believe this offers an inexpensive estimate. My take a look at information is manner bigger than my laptop computer cache and totally random so mainly each load ought to be a cache miss, and profiling appears to align with this. So whereas I believe reminiscence entry is marginally slower when you have got extra of it, the throughput ought to be related on a server that had sufficient RAM on one NUMA node to suit the full-sized tweet cache. Extra realistically non-uniform load distributions I imagine would simply make it extra possible that the L3 cache really made issues quicker.

It additionally seems to be like including tweets to the information construction shouldn’t be a bottleneck, given it provides tweets at over 1M/core-sec when the best peak Twitter had was 150k/sec.

Can the prototype meet the true load? Very sure!

My prototype’s efficiency ought to primarily scale based mostly on variety of tweets retrieved (due to cache misses retrieving them) and the scale of retrieved chunks (bigger chunks dilute the overhead of establishing the observe chain heap). The fastened overhead additionally scales with common observe rely and variable with log observe rely, which has in all probability grown since 2010 however I sadly don’t have numbers on, and more often than not is spent within the variable section anyhow. So let’s see how these numbers stack as much as calculations of actual Twitter load!

avg timeline price = 400/day
  

supply price = each day lively customers * avg timeline price => 100,000,000,000/day
  

supply price in 1/s => 1,157,407.4074/s
  

avg growth = supply price / avg tweet price in 1 => 200
  

supply bandwidth = tweet avg dimension * supply price in Gbit/s => 1.6296 Gbit/s
  

supply bandwidth in TB/month => 535.689 TB/month
  

per core = 2.5e6/(thread*second) * 2 thread => 5,000,000/second
  

peak supply price = max tweet price * avg growth => 30,000,000/second
  

peak cores wanted = peak supply price / per core => 6
  

peak bandwidth = tweet avg dimension * peak supply price in Gbit/s => 42.24 Gbit/s
  

avg new connection price = 3/day * each day lively customers in 1/s => 8,680.5556/s
  

tweets per request = supply price / avg new connection price in 1 => 133.3333
  

Appears like my estimate of the complete common tweet supply price of Twitter is 35x lower than what my 8 core laptop computer can fetch! I additionally had chosen the common timeline dimension within the benchmark based mostly on the estimate of regular timeline request sizes. It additionally seems to be like serving all of the timeline RPCs is a reasonably small quantity of bandwidth throughout common load.

There’s numerous room for this to underestimate load or overestimate efficiency: Peak hundreds may burst a lot greater, I may get common timeline sizes or supply charges improper, and a sensible implementation would have extra overheads. My estimates may very well be improper in numerous methods, however there’s simply a lot efficiency margin it ought to be high quality. My implementation even appears to scale linearly with cores, and there’s one other 10x left earlier than it will begin hitting reminiscence bandwidth limitations. Proper now it could actually solely add tweets from one thread, which I solely have a 20x efficiency margin on (however from a recognized peak load), however with a bit bit extra effort with atomics that may very well be multi-core too.

This maybe 350x security margin, plus the truth that high-performance batched kernel-bypass RPC systems can obtain overheads low sufficient to do 10M requests/core-s, means I’m assured an RPC service which acted because the core database of simplified manufacturing Twitter may match on one huge machine. It is a very restricted sense of working “Twitter” on one machine, you’d nonetheless produce other stateless machines to behave as net servers and API frontends to the high-performance binary RPC protocol, and naturally that is solely the very most simple options of Twitter.

There’s a bunch of different primary options of Twitter like consumer timelines, DMs, likes and replies to a tweet, which I’m not investigating as a result of I’m guessing they received’t be the bottlenecks. Replies do add barely to the load when writing a tweet, as a result of they’d have to be added to a secondary chain or one thing to make retrieving them quick. Some in style tweets have tons of replies, however customers solely can see a subset, and the identical subset might be cached to serve to each consumer.

To make my hedged confidence quantitative, I’m 80% positive that if I had a dialog with a (maybe former) Twitter efficiency engineer they wouldn’t persuade me of any elements I missed about Twitter load (on a much-simplified Twitter) or what machines can do, which might change my estimates sufficient to persuade me a centralized RPC server couldn’t serve all of the simplified timelines. I’m solely 70% positive for a model that additionally does DMs, replies and likes, as a result of these may be used far more than I think, and would possibly pose challenges I haven’t considered.

Conclusion-ish: It’s not sensible to construct this manner, however perhaps it may very well be

I don’t really assume individuals ought to construct net apps this manner. Right here’s all of the issues I believe would go improper with making an attempt to implement a Twitter-scale firm on one machine, and the alternate universe system that must exist to keep away from that downside:

• Your one machine can die: Methods can have remarkable uptime when there’s only one machine, however that’s nonetheless risking everlasting information loss and extended outages. You’d use at variety of machines in numerous buildings in any actual deployment. The framework may deal with this semi-transparently with some further cores and bandwidth per-machine utilizing state machine replication and Paxos/Raft for failover.
• RAM constructions are straightforward however disks are tough: You’d want the type of NVMe virtual memory buffer manager I’ve talked about attached with a transaction log so you may simply write a Rust state machine such as you would in RAM.
• Dangerous code can expend all of the assets: You’d want a bunch of enforcement infrastructure round this. Your activity system would want preemption and subsystem reminiscence/community/cpu budgets. You’d have to seize busy day manufacturing traces and replay them in pre-deploy CI.
• A bug in a single half can carry down the whole lot: Usually community boundaries implement design round failure dealing with and gracefully degrading. You’d want instruments for in-system circuit breakers and failure dealing with logic, and static evaluation to implement this on the firm degree.
• Zero-downtime deploys and schema evolution are tough: You’d want tooling to do one thing like generate getters that examine model tags in your information constructions and dispatch. Evolveable usually conflicts with constructions being fixed-size, which implies an additional random learn for a lot of operations, or having to do deploys by way of rewriting the entire database and having one other system catch as much as the current incrementally earlier than slicing over.
• Kernel-bypass binary protocol networking is tough to debug: It will take tons of tooling effort to catch as much as the ecosystem of linux networking and textual content codecs earlier than debugging and observability could be as clean.
• What if you wish to do one thing that doesn’t match on the machine?: You’d need a system which may scale to a number of machines by way of some type of state machine replication, distant paging and RPCs. In order for you safety boundaries between the machines that provides numerous entry management complexity. Databases and multicore CPUs have already got this type of expertise, but it surely’s not obtainable exterior them.

It’s doable to construct methods this manner proper now, it simply requires actually deep data and carefulness, and is setting your self up for both catastrophe or tons of infrastructure work as your organization scales. There’s a suggestions loop the place few corporations within the net house scale this manner, so the obtainable open-source tooling for it’s abysmal, which makes it actually onerous to scale this manner. I consider scaling this manner as a result of I used to work for a trading company, the place scaling methods to deal with hundreds of thousands of requests per second per machine with microsecond latency kernel-bypass networking is a common way to do things and there’s numerous infrastructure for it. However they nonetheless use numerous machines for many issues, and in some ways have a less complicated downside (e.g. usually no state persists between market days and there’s downtime between).

I do type of yearn for this alternate-universe open supply infrastructure to exist although. Extra hardware-efficient methods are cheaper, however I believe the primary profit is avoiding the traditional distributed methods and asynchrony issues each try to separate issues between machines runs into (which I’ve written a pseudo-manifesto on before), which implies there’s potential for it to be manner less complicated too. It will additionally allow magic powers like time-travel debugging any manufacturing request so long as you mark the state for snapshotting. However there’s a lot momentum behind the present paradigm, not solely by way of what code exists, however what abilities readily hireable individuals have.

Edit: A good friend factors out that IBM Z mainframes have a bunch of the resiliency software and hardware infrastructure I mention, like lockstep redundancy between mainframes separated by kilometers. In addition they scale to large machines. I don’t know a lot about them and am positively inquisitive about studying extra, and if it weren’t for the insane price I wouldn’t be shocked if I really ended up liking fashionable mainframes as a platform for writing resilient and scalable software program in a simple manner.

That’s all I initially deliberate for this publish, to point out with affordable confidence that you could possibly match the core tweet distribution of simplified Twitter on one machine utilizing a prototype. However then it turned out I had tons of cores and bandwidth left over to tack on different issues, so let’s forge forward and attempt to estimate which different options would possibly match utilizing all the additional CPU!

Straight serving net requests

The above simplified Twitter structure doesn’t serve the entire simplified Twitter from one machine, and depends on stateless frontend machines to serve the buyer API and net pages. Can we additionally try this on the primary machine? Let’s begin by imagining we’ll serve up a perhaps 64KB static web page with a protracted cache timeout, and makes use of some minimized JS to fetch the binary tweet timeline and switch it into DOM.

A benchmark for fast HTTP servers reveals a single machine dealing with 7M easy requests per second. That’s manner above our average-case estimate of 15k/s from above, so there’s snug room to deal with peaks and estimation error. Browser caches and other people leaving tabs open on our static most important web page will in all probability additionally save us bandwidth serving it too. Nonetheless HTTP is virtually deprecated for offering no safety.

dwelling web page price on a small connection = 10Gbit/s / 64KB in 1/s => 19,073.4863/s
  

I spent a bunch of time Googling for good benchmarks on HTTPS server efficiency. Nearly the whole lot I discovered was articles claiming the performance penalty over HTTP is negligible by giving CPU overhead numbers within the realm of 1% which embrace utility CPU. The symmetric encryption for established connections with AES-ni instructions is definitely quick at gigabytes per core-s, but it surely’s the general public key crypto to ascertain periods that’s worrying. After they do give out uncooked overhead numbers they say numbers like 3.5ms to do session creation crypto as if it’s tiny, which it’s for most individuals, however we’re not being most individuals! That’s solely 300 periods/core-s! I can discover some HTTPS benchmarks, however they often simulate a small variety of shoppers so don’t take a look at connection institution.

What possible saves us is session resumption and tickets, the place browsers cache established crypto periods to allow them to be resumed in future requests. This implies we could solely have to deal with 1 session negotiation per user-week as a substitute of a number of per day, and thus it’s in all probability doable for an HTTPS server to hit 100k requests/core-s below practical hundreds (earlier than app and bandwidth overhead). So though I can’t discover any really good high-performance HTTPS server benchmarks, I’m going to say The machine can in all probability straight serve the online requests too.

I believe there’s a 75% probability, conditional on an RPC backend becoming, that you could possibly additionally serve net requests. Particularly with a customized HTTP3 stack that used DPDK and really optimized static cached pages for a minimalist Twitter, with most uncertainty being perhaps session resumption or caches can’t hit that usually.

Put up-prediction edit: Somebody who labored at Twitter confirmed their precise request charges are decrease than a quick HTTPS server may deal with, however famous that crawlers imply a portion of the requests have to have the HTML generated server-side. I’m going to say crawlers are a separate characteristic, which I believe would possibly match with cautious web page dimension consideration and optimization, however would possibly pose bandwidth and CPU points.

The above is all assuming that folks or a JS script refreshes with the newest tweets every time a consumer visits a couple of occasions a day. However actual Twitter gives reside updates and infinite scrolling, can we try this?

avg session period = 20 minutes
  

reside connection rely = avg session period * avg new connection price in 1 => 10,416,666.6667
  

ballot request price = 1/minute * reside connection rely in 1/s => 173,611.1111/s
  

avg tweets per ballot = supply price / ballot request price in 1 => 6.6667
  

frenzy push price = avg growth * max tweet price => 30,000,000/second
  

tls websocket state = 41.7 GB / 4.9e6 in byte => 8,510.2041 byte
  

reside connection rely * tls websocket state in GB => 88.648 GB
  

The request price is completely high quality, however the primary situation is the scale of every ballot request has gone down, which raises our fastened overhead. We in all probability have sufficient headroom that it’s high quality, however we are able to do higher both by caching the heap we use for iterating timelines and updating it with new tweets or straight pushing new tweets to open connections. This may require following the tweet stream and intersecting a B-Tree set construction of reside connections with sorted follower lists from new tweets, or perhaps checking a bitset for reside customers. This may be sharded trivially throughout cores and the common tweet supply price is low sufficient, if peaks are an excessive amount of we are able to simply slip on reside supply.

Infinite scrolling additionally performs higher if we are able to cache a cursor on the finish for every open connection, let’s examine how a lot every cached connection-cursor prices:

cached cursor dimension = 8 byte * avg following => 3,200 byte
  

reside connection rely * cached cursor dimension in GB => 33.3333 GB
  

We will simply match one firstly and one on the finish in RAM! Given they are often loaded with one IO op it wouldn’t even actually gradual issues down in the event that they spilled to NVMe.

Photographs: Kinda!?

Photographs are one thing I initially thought positively wouldn’t match, however I used to be on a roll so I checked! Let’s begin by taking a look at whether or not we are able to serve the pictures in individuals’s timelines.

served tweets with photographs price = 1/5
  

avg served picture dimension = 70 KB
  

picture bandwidth = supply price * served tweets with photographs price * avg served picture dimension in Gbit/s => 132.7407 Gbit/s
  

complete bandwidth = picture bandwidth + supply bandwidth => 134.3704 Gbit/s
  

complete bandwidth * 1 month in TB => 44,169.993 TB
  

That appears surprisingly doable! I work with machines with tons of of gigabits/s of networking day-after-day and Netflix can serve static content at 800Gb/s. This does require aggressive picture compression and resizing, which is fairly CPU-intensive, however we are able to really get our customers to do this! We will have our shoppers add each a big and a small model of every picture once they publish them after which we received’t contact them besides perhaps to validate. Then we are able to discard the small model as soon as the picture drops out of the recent set.

Nonetheless there’s tons that may very well be improper about this estimate, and there’s lower than 8x overhead from my common case to essentially the most a single machine can serve. So site visitors peaks could trigger our system to need to throttle serving photographs. I believe there’s perhaps a 40% probability I’d say it will match with out dropping photographs at peaks, upon a lot deeper investigation with Twitter inside numbers, conditional on the fundamentals becoming.

However what wouldn’t it take to retailer all of the historic giant variations?

saved picture fraction = 1/10
  

avg saved picture dimension = 150 KB
  

picture price = avg tweet price * saved picture fraction in 1/s => 578.7037/s
  

picture storage price = picture price * avg saved picture dimension in GB/day => 7,680 GB/day
  

complete storage price = tweet storage price + picture storage price in GB/day => 7,768 GB/day
  

complete storage price * 1 12 months in TB => 2,837.2037 TB
  

picture replication bandwidth = picture storage price * $0.01/GB in $/month => $2,337.552/month
  

backblaze b2 price = $0.005 / GB / month
  

price per 12 months of photographs = (picture storage price * 1 12 months in GB) * backblaze b2 price in $/month => $14,025.312/month
  

So if we needed to stay strictly to 1 server we’d have to make Twitter like SnapChat the place your photographs dissapear after some time, perhaps make our cache right into a enjoyable mechanic the place your tweets maintain their photographs solely so long as individuals maintain taking a look at them!

Options that in all probability don’t match and are onerous to estimate

Video

Video makes use of extra bandwidth than photographs, however alternatively video compression is nice and I believe individuals view rather a lot much less video on Twitter than photographs. I simply don’t have that information although and my estimates would have such wild error bars that I’m simply not going to try to say we in all probability can’t do video on a single machine.

Search

Search requires two issues, a search index saved in quick storage, and the CPU to look over it. Utilizing Twitter’s own posts about posting lists to get some index dimension estimates:

See Also

Zayd’s Weblog – Why is machine studying ‘onerous’?

avg phrases per tweet = tweet content material avg dimension / 4 (byte/phrase) => 35 phrase
  

posting listing dimension per tweet = 3 (byte/phrase) * avg phrases per tweet + 16 byte => 121 byte
  

index dimension per 12 months = avg tweet price * posting listing dimension per tweet * 1 12 months in TB => 22.0972 TB
  

It seems to be like an enormous NVMe machine may match a couple of years of search index, though it will additionally have to retailer the uncooked historic tweets.

Nonetheless I’ve no good thought the best way to estimate how a lot load Twitter’s search system will get, and it will take extra effort than I wish to estimate the CPU and IOPS load of doing the searches. It may be doable however search is a fairly intensive activity and I’m guessing it in all probability wouldn’t match, particularly not on the identical machine as the whole lot else.

Notifications

The trickiest a part of notifications is that computing the historic notifications listing on-the-fly may be tough for large accounts, so it in all probability must be cached per consumer. This in all probability would want to go on NVMe or HDD and be up to date with a background course of following the write stream, which additionally would ship out push notifications, and will fall behind throughout site visitors bursts. That is in all probability what Twitter does given previous notifications load slowly and really previous notifications are dropped. Estimating whether or not this is able to match could be tough, the storage and compute price range is already stretched.

Somebody who labored at Twitter famous that push notifications from celebrities and their retweets can synchronize individuals loading their timelines into large bursts. Randomly delaying movie star notifications per consumer may be a obligatory efficiency characteristic.

Adverts

An ex-Twitter engineer who learn a draft talked about {that a} substantial fraction of all compute is ad-related. How a lot compute adverts price after all depends upon precisely what sort of ML or real-time auctions go into serving the adverts. Very primary adverts could be tremendous straightforward to suit, and Twitter makes $500M/12 months on “information licensing and different”. How a lot income you might want to run a service depends upon how costly it’s! You would think about an alternate universe non-profit Twitter which simply bought their public information dumps and used that for all their funding if their prices had been pushed low sufficient.

Algorithmic Timelines / ML

Algorithmic timelines seem to be the type of factor that may’t probably match, however one factor I do know from work at Anthropic is that fashionable GPUs are completely ridiculous monsters at multiplying matrices.

I don’t understand how Twitter’s ML works, so I’ll need to give you my very own thought for a way I’d do it after which estimate that. I believe the core of my method could be having a text embedding mannequin flip every tweet right into a high-dimensional vector, after which collectively optimize it with an embedding mannequin on options a few consumer’s exercise/preferences such that tweets the consumer will favor have greater dot product, then suggest tweets which have unusually excessive dot product and type the feed based mostly on that. One thing like Collaborative Filtering would possibly work even higher, however I don’t know sufficient about that to do estimates with out an excessive amount of analysis.

BERT is a well-liked sentence embedding mannequin and intelligent individuals have managed to distill it at the same performance into a tiny model. Let’s assume we base our ML on these fashions working in bf16:

teraflop = 1e12 flop
  

tinybert flops = 1.2e9 flop in teraflop => 0.0012 teraflop
  

a100 flops = 312 teraflop/s
  

a40 flops = 150 teraflop/s
  

avg tweet price * tinybert flops in teraflop/s => 6.9444 teraflop/s
  

supply price * tinybert flops / a100 flops in 1 => 4.4516
  

embedding dim = 256
  

flops to examine tweet in opposition to all customers = each day lively customers * embedding dim * flop in teraflop => 0.064 teraflop
  

flops per tweet with p4d = 8 * a100 flops / avg tweet price in teraflop => 0.4313 teraflop
  

flops per tweet with vultr = 4 * a40 flops / avg tweet price in teraflop => 0.1037 teraflop
  

Appears just like the immense energy of contemporary GPUs is as much as the scale of our activity with room to spare! We will embed each tweet and examine it in opposition to each consumer to do issues like cache some dot merchandise for sorting their timeline, or suggest tweets from individuals they don’t observe. I’m not tied to this ML scheme being one of the best, but it surely reveals now we have numerous energy obtainable!

A method this estimate may go improper is by utilizing the theoretical flops. Usually you may method that (however not really get there) by utilizing actually giant batch sizes, fused kernels and CUDA Graphs, however I usually work with a lot greater fashions than this so it is probably not doable! There’s additionally quite a lot of issues round PCIe and HBM bandwidth I didn’t estimate, and perhaps actual Twitter makes use of greater higher fashions! Algorithmic timelines additionally add extra load on the timeline fetching, since extra tweets are candidates and the timelines want sorting, however we do have loads of headroom there.

I can’t put a quantity on this one as a result of I’m assured I may match some ML, but it surely additionally in all probability wouldn’t be pretty much as good as Twitter’s precise ML and I don’t know the best way to flip that right into a prediction. Some ML designs additionally place far more load on different components of the system, for instance by loading numerous tweets to contemplate for every tweet really delivered within the timeline.

Bandwidth prices: They are often tremendous costly or free!

Up to now we’ve simply checked whether or not the bandwidth can match out the community playing cards, but it surely additionally prices cash to get that bandwidth to the web. It doesn’t have an effect on the machines it matches on, however how a lot does that price?

bandwidth worth = ($717/month)/(9Gbit/s) in $/GB => $0.0002/GB
  

good friend says colo worth = $1000/(month*Gbit/s) in $/GB => $0.003/GB
  

cdn77 worth = (($1390/month)/(150 TB / 1 month)) in $/GB => $0.0093/GB
  

vultr worth = $0.01/GB
  

cloudfront 500tb worth = $0.03/GB
  

supply bandwidth price = bandwidth worth * supply bandwidth in $/month => $129.8272/month
  

supply bandwidth price(bandwidth worth = cloudfront 500tb worth) => $16,070.67/month
  

complete bandwidth price = bandwidth worth * complete bandwidth in $/month => $10,704.8395/month
  

complete bandwidth price(bandwidth worth = cdn77 worth) => $409,308.6018/month
  

I used to be shocked by the truth that typical bandwidth prices are manner far more than a server able to serving that bandwidth!

However one of the best deal is definitely Cloudflare Bandwith Alliance. So far as I can inform Cloudflare doesn’t cost for bandwidth, and a few server suppliers like Vultr don’t cost for switch to Cloudflare. Nonetheless in the event you tried to serve Twitter photographs this manner I’m wondering if Vultr would all of a sudden rethink their free Bandwidth Alliance pricing as you made up numerous their combination Cloudflare bandwidth.

How cheaply may you serve Twitter: Pricing it out

Okay lets have a look at some concrete servers and estimate how a lot it will price in complete to run Twitter in a few of these situations.

$7,079/month in $/12 months => $84,948/12 months
  

8 * 2.34$/hr + $7.4/hr in $/12 months => $228,963.2184/12 months
  

price per 12 months of photographs * 5 in $/12 months => $841,518.72/12 months
  

$20,000/month in $/12 months => $240,000/12 months
  

complete bandwidth price(bandwidth worth = $0.02/GB) in $/12 months => $10,600,798.32/12 months
  

server price = $15,245
  

ram 32GB rdimms = $132 * 24 => $3,168
  

samsung pm1733 8tb NVMe = $1200 * 6 => $7,200
  

nvidia a100 = $10,000
  

hdd 20TB = $500 * 18 => $9,000
  

complete server price = server price + ram 32GB rdimms + samsung pm1733 8tb NVMe + nvidia a100 + hdd 20TB => $44,613
  

colo price = $300/month in $/12 months => $3,600/12 months
  

colo price + complete server price/(3 12 months) => $18,471/12 months
  

complete bandwidth price(bandwidth price=good friend says colo worth) in $/12 months => $128,458.0741/12 months
  

Clearly optimizing server prices right down to this degree and under isn’t economically rational, given the price of engineers, but it surely’s enjoyable to consider. I additionally didn’t attempt to examine configuring an IBM mainframe, which stands an opportunity of being the one sort of “machine” the place you would possibly be capable of connect sufficient storage to suit historic photographs.

For reference of their 2021 annual report, Twitter doesn’t break down their $1.7BN price of income to point out what they spend on “infrastructure”, however they are saying that their infrastructure spending elevated by $166M, in order that they spend no less than that a lot and presumably considerably extra. However in all probability lots of their “infrastructure” spending is on offline analytics/CI machines, and plausibly even workplace bills are a part of that class?

Conclusion

The true conclusion is kinda up within the center, however I had lots of enjoyable researching this undertaking and I hope it conveys some appreciation for what {hardware} is able to. I had much more enjoyable spending tons of time studying papers and pacing round designing how I’d implement a system that allow you to flip a Rust/C/Zig in-memory state machine like my prototype right into a distributed fault-tolerant persistent one with web page swapping to NVMe that might run at hundreds of thousands of write transactions per second and 1,000,000 learn transactions per second per added core.

I virtually actually received’t really construct any of this infrastructure, as a result of I’ve a day job and it’d be an excessive amount of work even when I didn’t, however I clearly love doing fantasy methods design so I could properly spend lots of my free time writing notes and drawing diagrams about precisely how I’d do it:

Due to the 5 ex-Twitter engineers, a few of whom labored on efficiency, who reviewed this publish earlier than publication however after I made my predictions, and introduced up fascinating issues and led me to right and make clear a bunch of issues! Additionally to my coworker Nelson Elhage who supplied good feedback on a draft round causes you wouldn’t do that in observe.