System Design Mock Interview: Design Facebook Messenger
Вставка
- Опубліковано 25 чер 2024
- Don't leave your career to chance. Sign up for Exponent's system design interview course today: bit.ly/48OhSV7
In this interview, Jacob (Dropbox Software Engineer) answers a system design interview question of designing Facebook Messenger, commonly asked in software engineering and technical program management (TPM) interviews.
Chapters -
00:00:00 Introduction
00:00:09 Question
00:00:15 Answer
00:00:39 Requirements
00:01:55 Design
00:09:05 Data types
00:11:46 Scale
👉 Subscribe to our channel: bit.ly/exponentyt
🕊️ Follow us on Twitter: bit.ly/exptweet
💙 Like us on Facebook for special discounts: bit.ly/exponentfb
📷 Check us out on Instagram: bit.ly/exponentig
📹 Watch us on TikTok: bit.ly/exponenttikttok
ABOUT US:
Did you enjoy this video? Want to land your dream career? Exponent is an online community, course, and coaching platform to help you ace your upcoming interview. Exponent has helped people land their dream careers at companies like Google, Microsoft, Amazon, and high-growth startups. Exponent is currently licensed by Stanford, Yale, UW, and others.
Our courses include interview lessons, questions, and complete answers with video walkthroughs. Access hours of real interview videos, where we analyze what went right or wrong, and our 1000+ community of expert coaches and industry professionals, to help you get your dream job and more!
#softwareengineer #systemdesign #mockinterview #technicalprogrammanagement #tpminterview #tech #technicalprogrammanager #coding #programming #systemdesign #entrepreneurship #exponent #softwareengineering #facebook - Наука та технологія
Don't leave your career to chance. Sign up for Exponent's system design interview course today: bit.ly/48OhSV7
What tool is it?
Although I point out several places that I think not proper, this is the most helpful system design interview walking-through on whole UA-cam. Why? Instead of laying out these components names and introduce their usage directly, you start from comparing connection protocols and pick the right one(web-socket), then build up the very basic backbone in very natural way. Then find bottle neck of single API server, introduce load balancer. Then pub/sub message queue. Then you analysis the high volume request and pick up NoSql. Then introduce cache, cdn and S3 to solve low latency bottleneck! THIS IS very helpful, amazing sharp. THANK YOU SO MUCH.
👋 Have a question or suggestion? Let us know in the comments here! And don't forget to check out the full course System Design Interview course here: bit.ly/2XduSkJ
A socket is defined by (source IP, source port, destination IP, destination port). Different sockets CANNOT have the same exact bindings, but you can create the socket as long as the port or client IP is different. So, you can handle 65536 (the number of technically possible port ids) concurrent connections PER client.
Of course, if you use other ports in your server, then you have many more possible connections.
Let me know if I'm missing something! Always up to learn something new :)
Yeah, that's exactly what I wanted to say right after I heard this guy said the server can have at most about 65000 connections.
Nice, i think this has the right amount of complexity without going into too much details like some others. Seems like a realistic amount of info to spit out in 30-45 minutes of an interview.
I believe a media attachment can be big enough, so we don't want to send it through our API server. Instead, client can request a pre-signed link to object storage from the server to upload the file using that link. These links are valid for some short amount of time for security.
Nice addition, S3 does support a feature called pre-signed URL.
That's a great point!
This was a good demo of managing details i.e. staying at a consistent high level. It's easy to dive too deep into in one area while neglecting some major components of the system. You can then leave it open for the interviewer to choose one area to get deeper on.
Looking at the database schema, it suits sql database but Cassandra being a no sql, I wanted to find out how the fields are defined. Also how does the message get distributed to the user from message queue is not very clear to me
Exaclty I was gonna to write the same. In no sql you wanna avoid the joins.
I think this is a great example interview and the end design is spot on, one thing i'd simply say to anyone watching this is also ensure to check up on terms and technologies as they always change (this video is 2 years before this comment). In particular modern web connections would probably motivate long-polling as the ideal solution. This is because HTTP2 is universally supported now, and it supports streaming and multiple server responses for a single request - so you can treat it like a one-directional WebSocket - however with faster connection handshakes and better compression support. Although from a client API standpoint you would issue multiple 'requests' for sending message it would be on the singular TCP underlying connection.
Hey NickCooperWasHere! Appreciate the kind words. Thanks for letting others know the importance of keeping their knowledge up-to-date before going for an interview!
Thanks so much for your video, it was really concise and explanatory. I'm studying for an Architecture and System Design interview and your video was the first I watched because if was the shortest one.
this is much better than the other mock system design interviews videos
1. How does a messaging Service (e.g. kafka) write to a DB directly? Wouldn't you have individual services writing to a DB?
2. If we're using a NoSQL DB, why are there ER diagrams in the Data Types section?
3. Does a conversation contain messages? Doesn't there need to be some linkage between the two entities?
These are exactly what just came to my mind
1. Yes
2. -
3. each message has a coversation_id so they are linked
Also my question is how we are going to create topics for such huge load. Million of user are sending messages per second will single topic will be able to handle it, also if each service consumes millions of messages and filter out for one user . I don’t think it’s scalable approach
Simple and elegant. Great presentation as well. Thank you.
I learned a lot just listening to this. Thank you!
The statement at 5:20 is incorrect. A server can have up to 65k connections *for every client*. This comes from the fact that we are filling in the ports into a standard connection 4-tuple: (source ip, source port, destination ip, destination port). Different clients have different IPs, which allows the server to have another 16bits/65k connection per client. Otherwise a great video, thanks!
We can't say that the limitation of connection for a server is 65535. limitation for a server doesn't depend on the number of ports. Instead, it depends on the maximum open files of the server process, memory, and connection tracking (conntrack) limitation, etc. Of course, here I'm talking about a Linux server.
These videos are so helpful in learning to work through these system design questions. THANK YOU.
The 65536 Port limitations is actually for the client machines not for the servers. In fact, the server uses the same port for all sockts.
On Server side, server creates socket with ephemeral port. 65K limit might be for ephemeral ports ?
@@giridhar510 the limit is per client's IP.
on server side, it look like this:
ipA:80
ipB:80
@@songjo3506 Websocket uses TCP protocol and so is HTTP. Server sees them same way. So when an request for new connection comes in, it is always ported to an ephemeral port.
@@Kriishna47 the ephemeral ports are assigned to each peer IP.
Scenario where
If users are 1K users,
It means the connections the server can handle is
1K IP x # of ephemeral ports.
Access Linux console and trigger ss -tlap to see how the connection is established.
So what would be the limit for number of web sockets on each server?
this was most perfect PM mockup ever, other vids are like 40 mins long. can you please make more, pleaaaaasseeeeeee
On one side you talked about using Cassandra or HBase and on the other your ERD actually drove towards a relational design.
I also think that the design related to Notification service was incomplete, because it assumes a connection possibility with the client.
A key part of a system design may be a back of the envelope estimation, which I found missing in your presentation.
Over requirement of Size/growth of the data was missing.
1) Notifications works in a different way, there need not be any persistent connection at all. You generally push notifications through 3rd parties in case of SMS. Or you can in house have an integration FCM like setup to do the same.
2) IMO the DB schema wasn't really ERD. It was simply actor ids and their corresponding values
it's ok to have different schemas for NoSQL as well. You can put them in the same table to avoid joins. There is a pattern called adjacency list for many-to-many or one-to-many relationships. I agree that the bridge table for conversation-id and user-id is not needed.
Great video. One quick thing to point out. Web Socket server mux's the connection and would listen on a single Port so not subject to the 65kish limitation. Its a limitation in the client-side typically and mostly becomes a burden if you are running a load test to a TCP server.
Good point!
how does websocket looks up connection based on user-id? I wonder if there is a need to bookkeeping connection-user information at application level.
@@meow-mi333 Yes, that needs to be done at the application level
As somebody else in the comments said, I don't think its correct to say that the server can only handle 65536 concurrent connections. The server websocket port (80) should be able to share multiple TCP/websocket connections. The limitations would probably come from your application code or hardware (i.e. CPU/memory/network bandwidth)
I agree server sockets are different than clent sockets.
yes, WhatsApp had an article about 2M tcp connections on a single machine
I mean even if that were the case, wouldn't the load balancer have that limitation too?
@@dustinkftw Put a L3 load-balancer that distributes IP packets based on source-IP-port hash to your WebSocket server farm. Since the L3 balancer maintains no state (using hashed source-IP-port) it will scale to wire speed on low-end hardware (say 10GbE). Since the distribution is deterministic (using hashed source-IP-port), it will work with TCP (and hence WebSocket).
Yeah, the 65536 is only a limit on the number of applications that can be listening for the initial connection on the API server.
We technically only need 1 of those ports to be listening to new WS connections.
Awesome tutorial! Thank you so much!
Compared to other videos, this is the correct design.
Thank you for this design. It is so useful.
Excellent and very clear explanation of the system design. Encourage you to upload more system design videos
This system design talking points will give a lot of hard hitting questions from the interviewer!
Limitations of 65k is per client.
On the TCP level the tuple (source ip, source port, destination ip, destination port) must be unique for each simultaneous connection. That means a single client cannot open more than 65535 simultaneous connections to a single server. But a server can (theoretically) serve 65535 simultaneous connections per client
a socket connection is (client ip:port, socket ip:port), client can be any different ip:port combination, so a server with one port can serve as many clients as needed
With HTTP/2 you have PUSH. Then, even though the connection needs to be established beforehand, the server can push information which is indeed much more scalable than pulling
Agree. Surprised about this too.
Really Great Video. Looking forward to more such content related to system design.
More to come! Be sure to subscribe and like for more!
Really great and informed video with correct reasoning and justification
Thank you!
12:00 I believe you want to put cache between message service and database.
This one and the instagram design is way better than the Facebook feed. But could have spanned to about 30 min of info in terms of coverage.
When you mention tables, are you meaning SQL database having earlier mentioned NoSQL?
Hi Jacob - This is very interesting video , I am trying to draw along with you and would like to ask you which platform are you using for flowcharts. You drew it very smoothly
Hey @Ankit! I'm using a great tool called Whimsical (whimsical.com)
@@tryexponent scrolled down for this comment. 😅
I don't have Facebook Messenger. I only had it for a few weeks in the beginning of 2016. I didn't use it prior to that time, now have I used it since then.
@8:14, You said "We know we gonna support large volume of request and save lots of data". That's the reason you pick nosql over sql. And cap theorem's universal tradeoffs only apply for nosql db. And in chat system, we prefer availability and partition tolerance.
Just curious why sql can't afford large volume of data. And besides, I believe consistency should be the priority, you just don't want to miss any messages.
@@niceperson6412 I don't think that consistency is about not loosing messages, it's about handling multi-step transactions. Which I can't imagine in a chat service.
5:24 The TCP protocol does have 16 bits for the port number. The total number of Ports available to an IP address are 65,536 (from 0 to 65,535). The WebSocket Server uses one of the 65,535 Ports (in case of secure Sockets that would be Port # 443). The rest of the ports are managed by the OS for various other purposes (Well-known ports: 0 to 1023, Registered ports: 1024 to 49151 and Dynamic ports: 49152 to 65535.)
The maximum number of connections a WebSocket server could have with clients would depend on (i) the specs of the server hardware, (ii) capabilities of WebSocket server (e.g. employing techniques like Connection Pooling) and the capabilities of employed WebSocket library and (iii) OS environment settings.
Many credible sources on the Internet claim to easily achieve 1 Million or more simultaneous connections on WebSocket server. (Of course the actual number of simultaneous connections would depend on the use case and there would be all kinds of nuances).
Consistency is more important than availability.
Your videos are great. Easy to understand. Loved your video for Instagram as well :)
Thanks! Glad you like them!
Thanks!
Hey Jacob. Interesting video.
I was wondering why can’t we use concept of SNS topic where user B will subscribe to a topic and as soon as user A sends message he will receives it.
I’m new to backend programming so was curious ?
Great video! Question about the data model - the tables are defined with schemas that fit a relational model, e.g. the "user" columns in "messages" and "conversation_users" tables are foreign keys pointing to "users" table's records. However, if we use Cassandra as you mentioned, we can't do join-queries directly in the database. (I'm not familiar with HBase, so can't say about that.) Is your intention perhaps to use a hybrid approach, e.g. a relational db for users, conversations, and conversation_users, and nosql for message?
+1 If this was a real interview, the interviewer would dig into this and the candidate would have to explain how Cassandra works. Candidates can't just throw out the names of databases and not know how they work. Exponent should go into more depth there
@@bengillman1123 I Don't think you need to do any kind of join here, you can just filter each conversation when fetching it (aka when the user clicks it), you shouldn't need to fetch all the conversations at once if the user is not reading them. Maybe you query like 5-6 conversations if the system gets extended to remember your last conversations. And anyways, even if you needed to query all the conversations of a user, it shouldn't be so many and you can do that by just filtering (kind of in predicate).
this is good. one question why is database directly connected to message bus? shouldnt there be an application server which reads from the message bus and stores in the database?
I don't really get what there is to cache. Chat messages are all unique right, not public and getting heavy reads.
Memory access is exponentially faster than going to the database for a read. If I were designing this messaging service, I could cache conversations that were going on *right now* between two online users, and allow cached messages to automatically expire with time.
Think about it. That messaging service in his architecture diagram is servicing *millions* of users, potentially at the same time. You do *not* want to bottleneck on the database, but at the same time you need a way to persist messages for when they need to be delivered later to offline users, so you can't do without it. Or maybe users want to be able to log into a different device and see the history of their conversations, so they would need to be downloaded from the server. His design offers a way to provide both without sacrificing too much with regards to latency.
hi cool tutorial thx, small question how u loadbalnceing WebSocket's?
one question, you have added a load balancer between the APIs and the clients. so are the clients keep the WebSocket connection with the load balancer? if it is, then again the 65k limitation can occur?
This man is incredibly well informed and his presentation was incredibly well explained!
The Messaging service appeared to be a monolith in your diagram, vs the API servers. Is this intentional or is the messaging service also intended to be horizontally scalable and clustered? If so, what is the need to separate it out?
I would add a timestamp for each message. You'll need that to determine ordering when displaying messages.
Partition in CAP theorem does not mean sharding, it means systems are partitioned and cannot talk to each other
If we use a CDN and it sits side by side with the load balancer, would we say that objects stored in the CDN must be public objects not secured? For example, giphy type images or something ?
What editor your use to design systems?
For the messages table - shouldn't we consider adding a timestamp for when the message was sent?
I think consistency and sharding are more important. I will sacrifice availability
Could someone help me understand why we need the message queue service and how that will work in detail? It is going to be something like SQS and SNS setup?
How about Scaling the solution. is cloud providers scaling solution like Autoscaling group(AWS) or scale set(Azure)after load balancer will be appropriate?
what diagramming tool are you using in these videos?
what tool are you using to create that diagram?
Thanks for the video. Can you elaborate on messaging service that is support to deliver a message from user A connected to API server 1 to user B connected to API server 2 ? You said messaging service is build for that purpose. But when there are millions users connected to hundreds even thousands API server. What's the best messaging component? what would be the topic that API server 1 post so that API server 2 picks but not others?
Instead of an ID for messages table, would it be better for a primary composite key such as (from_user_id, to_user_id, timestamp)? It's not physically possible for a user to send 2 exactly-simultaneous messages.
Which application are you using for desing on the go??
How are you using the messaging queue to serve data to the api service
Great video
I have a small question, what's the tool being used here to display the architecture design ?
Whimsical
Why didn’t you talk about consistency for this problem. I felt it was quite important
What about created at on the messages table? How will we know when messages were sent?
Does Cassandra support foreign keys? The DB schema looks more like a Relational one.
What is the name of tool he used to designed the diagram?
This is the absolute best video explanation that I have ever seen for the system. I follow Exponent channel on youtube but being a student and financing myself, I am not able to get the subscription. However, I would suggest, along with mock interviews that Exponent have been uploading on YT, these pattern following videos on System Design are better suited for a quick but detailed explanation of the system. Please upload more of such videos and if there is any discount for students please help me.
should we use api server to interact with DB, not MQ?
Bro whats the app you using for this designing ?
Which whiteboarding app are you using?
Hi! I had one confusion. You said we will be needing NoSQL database but then you are doing data model exactly like a SQL database and these tables would have to have a lot of joins to get data from. Could you please explain that?
Did you figure out answer to this? am curious also
What applications do they use to create these designs in?
Thank you for sharing. Which whiteboarding tool is being used here to draw the components?
Whimsical!
Great explanation. Though the data model part is still not clear to me. Maybe some visuals could help here to understand which key corresponds to what visual data.
Thanks for the feedback @Milan! Anything else you would want to see in future videos?
Is there a mobile app version of this system design mock interview?
Using a CDN for a chat application might not be worth it, as most Media is consumed just by one user or users from a Group.
Might need it if some content got viral and everyone one is sharing and viewing it.
still confuse what's the message service in the middle
Great video!
So what happens if the S3 bucket that the CDN directed me to does not have my media asset? Or does every S3 bucket from the CDN have the same data? What if my location one day is New York and then the next Melbourne, I would be hitting different S3 buckets correct?
S3 is a managed service by AWS. So you don’t have to set up multiple buckets for faster reads, that all happens in the background. Maybe the confusion is in the fact the I believe you should only have one CDN per S3 Bucket. If you have a url for the S3 bucket in your database metadata row then the object should be there. If the object can not be returned there should be some error handling. Maybe the file was corrupted on the AWS server or maybe it was deleted and the url was not updated on the messages url field.
What software used to make block diagram ?
whats the difference between the message service and the api?
Messaging service and how the server process these messages is unclear. Also when we write to db, what we write to db and how we use cache is not explained. Also we might have to maintain a sticky session with load balancer otherwise it's not gonna reach the same server instance.
Thanks! May i ask what is the platform you are using now to display those notes when recording the videos?
whimsical
what whiteboard app are they using ?
Do we need a timestamp for "messages" table?
What’s the need for cache?
what's this whiteboard app they are using?
what's the whiteboarding tool you're using in the video? looks pretty nice and smooth. thx
Whimsical
@@roycrxtw thank you!
This is really well done, thanks! A request - please try to go a little deeper to have at least 30 mins of content.
Hey @Pokri Poki, thanks! What areas would you like to see us go deeper in?
@@tryexponent couple things You could either go WIDE or go DEEP. Go WIDE - talk about some more features (which of my buddies are online? or 'abc is typing' , etc). Go DEEP - a) how do you tie your technology choices to the initial non functional goals you set up, what are the trade-offs of your chosen tech stack? b) describe the core systems a little more (the pub-sub system) or the notification system c) What kind of high level metrics / monitoring you will have in place to ensure the system works as it was designed to? What would be your tech stack choices for the data analytics part?
I actually liked this video so much because it was short and concise.
The messages data model definitely needs a timestamp.
Best certifications for System Designer jobs?
i believe your Hbase suggestion sacrifices Availability instead of the Consistency you are aiming to sacrifice under CAP
Hey @Chisomo! Good correction. Both HBase and Cassandra have been used by Facebook Messenger but you're right that their consistency models are not as similar as suggested here - we'll try to fix this in a future video!
@@tryexponent also, I'm new to Cassandra, but you're showing relational tables, and Cassandra isn't relational, right? So it should all be denormalized.
Does Facebook Messenger still use WebRTC (in lieu of websockets)?
I would've wanted to see more detail on how the servers interact with the pubsub system (assuming something like Apache Kafka). Would you just have two servers publish and subscribe to each other? That sounds expensive, both in terms of money, space, and latency. If multiple servers get hashed to the same pub-sub connections, that'd be better, but you'd have to skip a lot of messages.
In my shallow opinion, Kafka is more messaging model than pub/sub model, which means the machine don't have to subscribe to each other but rather listens to the message in the queue. The message would contain some identifiers like 'sender_id' and 'receiver_id', especially the latter that allows particular server to respond.
How would the Message Service map onto AWS ?
Great video, what software are you using for drawing the charts please?
Hey alfellati, the whiteboard being used here is called "Whimsical"!
how do you invalidate or update the cache?
DB will be SPOF based on this design
I was really confused by the data schema section, so looked for more details. For in depth Cassandra data modeling for a messaging app, I found this video to be very helpful: ua-cam.com/video/gTiwfpCgtoI/v-deo.html. TL;DR: The NoSQL column data modeling is a lot more complex as the idea is to store everything you need into one table and define partition keys and clustering columns which make up the primary key.
Shouldn't the API actually talk to the notification service if the user is not online?