sdi 3

Question 1

fb messenger - the avg msg is how large?

Answer 1

100 bytes

Question 2

messenger high level design

Answer 2

we will need a chat server that will be the central piece. When a user wants to send a message to another user, they will connect
to the chat server and send the message to the server; the server then passes that message to the other user and also stores it in the database.

Question 3

pull model

Answer 3

Users periodically ask the server if there are any new messages for them. Server keeps track of undelivered msgs; when user connects to the server, server returns all the pending msgs. To minimize latency, users have to check the server quite frequently, and a lot of the time they’ll be getting an empty response. This will waste a lot of resources.

Question 4

push model

Answer 4

Users can keep a connection open with the server and can depend upon the server to notify them whenever there are new messages. The server does not need to keep track of the pending messages, and we will have minimum latency.

Question 5

How can the central chat server keep track of all opened connections to redirect messages to users efficiently?

Answer 5

The server can maintain a hash table, where “key” would be the UserID and “value” would
be the connection object. So whenever the server receives a message for a user, it looks up that user in the ht.

Question 6

What will happen when the central chat server receives a message for a user who has gone offline?

Answer 6

If the
receiver has disconnected, the server can notify the sender about the delivery failure. If it is a
temporary disconnect, e.g., the receiver’s long-poll request just timed out, we can ask the sender to retry sending. This retry
could be embedded in the client’s logic so that users don’t have to retype the message. The server can also store the message for a while and retry sending it once the receiver reconnects.

Question 7

How should the central chat server process a ‘deliver message’ request?

Answer 7

upon receiving a new message:
1) Store msg in db
2) Send msg to receiver
3) Send acknowledgment to sender

The chat server will first find the server that holds the connection for the receiver and pass the message
to that server

Question 8

How can we maintain sequencing of the messages?

Answer 8

Storing timestamps won’t ensure correct ordering of messages for clients.
we need to keep a sequence number for every message for each client. This number will determine the ordering of messages for EACH user. Both clients will see a different view of the message sequence, but this view will be consistent for them on all devices.

Question 9

messenger - what storage system CAN’T we use?

Answer 9

We cannot use RDBMS like MySQL or NoSQL like MongoDB because we cannot afford to read/write
a row from the database every time a user receives/sends a message. This will not only make the basic
operations of our service run with high latency, but also create a huge load on databases.

Question 10

messenger - what storage system should we use?

Answer 10

• must support very high rate of
  small updates and also fetch a range of msgs quickly
• solution: wide-column database solution like HBase. HBase is a column-oriented key-value NoSQL db.
• HBase groups data together to store new data in a memory buffer and, once the buffer is full, it dumps the data to the disk.
• HBase is also an efficient database to store variably sized data.

Question 11

pagination

Answer 11

Clients should paginate while fetching
data from the server. Page size could be different for different clients, e.g., cell phones have smaller
screens, so we need a fewer number of message/conversations in the viewport.

Question 12

messenger data partitioning

Answer 12

Partitioning based on MessageID: If we store different msgs of a user on separate shards, fetching a range of msgs would be very slow, so bad idea.

Partitioning based on UserID: find shard number by “hash(UserID) % (num of shards)” and then store/retrieve the data from there. very quick to fetch chat history

Question 13

messenger caching

Answer 13

We can cache a few recent messages (say last 15) in a few recent conversations that are visible in a
user’s viewport (say last 5). Since we decided to store all of the user’s messages on one shard, cache for
a user should entirely reside on one machine too.

Question 14

What will happen when a chat server fails?

Answer 14

It’s extremely hard to failover TCP connections to other servers; an easier approach can be to
have clients automatically reconnect if the connection is lost.

Question 15

Should we store multiple copies of user messages?

Answer 15

We cannot have only one copy of the user’s data, because if the server holding the data crashes or is down permanently, we can’t recover that data. Either we have to store multiple copies of the data on different servers or use techniques like Reed-Solomon encoding to distribute and replicate it.

Question 16

how to implement group chat?

Answer 16

We can have separate group-chat objects in our system that can be stored on the chat servers. A group-chat object is identified by GroupChatID and will maintain list of users in the chat.
LB can direct each group chat message based on GroupChatID and the server handling that group chat can iterate through all the users of the chat to find the server handling the connection of each user to deliver the message.
In databases, we can store all the group chats in a separate table partitioned based on GroupChatID.

Question 17

how to implement push notifs?

Answer 17

Push notifications will enable our system to send messages to
offline users.
For Push notifs, each user can opt-in from their device (or a web browser). Each manufacturer maintains a set of servers that handles pushing these notifs to the user.
We need to set up a Notification server, which will take msgs for offline users and send them to the manufacturer’s push notification server, which will then send them to the user’s device.

Question 18

tweet api

Answer 18

tweet(api_dev_key, tweet_data, tweet_location, user_location, media_ids) (media ids are pics, vids, etc)

A successful post will return the URL to access that tweet. Otherwise, an appropriate HTTP error is returned.

Question 19

twitter high level design

Answer 19

• multiple application servers to serve all r/w requests (mostly r) with LBs in front of them for traffic distributions.
• efficient db that can store all new tweets and support a huge number of reads
• file storage for pics and vids

Question 20

twitter db schema

Answer 20

4 DBs: users, their tweets, their favorite tweets, and people they follow.

remember tweet should include num favorites, retweets, etc

Question 21

twitter Sharding based on UserID:

Answer 21

1. Too many queries on servers holding hot users.
2. Over time some users can end up storing a lot of tweets or having a lot of follows compared to
   others. Maintaining a uniform distribution of growing user data is quite difficult.

Question 22

Sharding based on TweetID:

Answer 22

Our hash function will map each TweetID to a random server. To search for tweets (such as for timeline generation), we have to query all servers. A centralized server will aggregate these results.

This approach solves the problem of hot users, but we have to query
all database partitions to find tweets of a user, which can result in higher latencies.

Question 23

Sharding based on Tweet creation time:

Answer 23

advantage of fetching all the top tweets quickly and we only have to query a very small set of servers.
BUT traffic load distribution will be very uneven - while writing, all new tweets will be going to one server and the other servers will be idle. Similarly, while reading, the server
holding the newest tweets will have a very high load compared to servers holding older tweets.

Question 24

twitter ideal way to shard data

Answer 24

generate universally unique TweetIDs consisting of current epoch time + auto incrementing sequence. get shard number from this TweetID.
- We can reset our auto incrementing sequence every second. For fault tolerance and better performance, we can have 2 db servers to generate auto-incrementing keys for us, 1 for even keys and 1 for odd.
- If TweetID is 64bits (8 bytes) long, we can easily store tweets for the next 100 years w/ ms granularity.

Question 25

pros/cons of using 2-part TweetID to shard

Answer 25

we still have to query all the servers for timeline generation, but r/w will be substantially quicker.
1. Since we don’t have any secondary index (on creation time) this will reduce our write latency.
2. While reading, we don’t need to filter on creation-time as our primary key has epoch time included in it.

Question 26

twitter - fault tolerance

Answer 26

Since our system is read-heavy, we can have multiple secondary database servers for each DB partition. Secondary servers will be used for read traffic only. All writes will first go to the primary server and then will be replicated to secondary servers. This scheme will also give us fault tolerance, since whenever the primary server goes down we can failover to a secondary server.

Question 27

twitter - 2 ways of caching

Answer 27

We can use an off-the-shelf solution like Memcache that can store the whole tweet objects.

1. cache 20% of daily read volume from each shard
2. Let’s say 80% of users see tweets from the past 3 days only. Even if this cache data can easily fit into 1 server, we should replicate it onto multiple servers to distribute read traffic. Whenever we generate a user’s timeline, we can ask the cache servers if they have all the recent tweets for that user. If yes, we can return; else, we query the backend server.
   Our cache is a HT - ‘key’ is ‘OwnerID’; ‘value’ is a doubly LL w/ all tweets from that user from past 3 days. Insert new tweets at head; remove old tweets from tail.