Facebook Architecture

https://www.facebook.com/atscaleevents/videos/1732398473699916/
http://highscalability.com/blog/2016/6/27/how-facebook-live-streams-to-800000-simultaneous-viewers.html

This began a year of product improvement and protocol iteration.

• They started with HLS, HTTP Live Streaming. It’s supported by the iPhone and allowed them to use their existing CDN architecture.
• Simultaneously began investigating RTMP (Real-Time Messaging Protocol), a TCP based protocol. There’s a stream of video and a stream of audio that is sent from the phone to the Live Stream servers.
  • Advantage: RTMP has lower end-end latency between the broadcaster and viewers. This really makes a difference an interactive broadcast where people are interacting with each other. Then lowering latency and having a few seconds less delay makes all the difference in the experience.
  • Disadvantage: requires a whole now architecture because it’s not HTTP based. A new RTMP proxy need to be developed to make it scale.
• Also investigating MPEG-DASH (Dynamic Adaptive Streaming over HTTP).
  • Advantage: compared to HLS it is 15% more space efficient.
  • Advantage: it allows adaptive bit rates. The encoding quality can be varied based on the network throughput.

• Live video is different than normal videos: it causes spiky traffic patterns.
  • Live videos are more engaging so tend to get watched 3x more than normal videos.
  • Live videos appear at the top of the news feed so have a higher probability of being watched.
  • Notifications are sent to all the fans of each page so that’s another group of people who might watch the video.
• Spiky traffic cause problems in the caching system and the load balancing system.
• Caching Problems
  • A lot of people may want to watch a live video at the same time. This is your classic Thundering Herd problem.
  • The spiky traffic pattern puts pressure on the caching system.
  • Video is segmented into one second files. Servers that cache these segments may overload when traffic spikes.
• Global Load Balancing Problem
  • Facebook has points of presence (PoPs) distributed around the world. Facebook traffic is globally distributed.
  • The challenge is preventing a spike from overloading a PoP.

This is how a live stream goes from one broadcaster to millions of viewers.

• A broadcaster starts a live video on their phone.
• The phone sends a RTMP stream to a Live Stream server.
• The Live Stream server decodes the video and transcodes to multiple bit rates.
• For each bit rate a set of one-second MPEG-DASH segments is continuously produced.
• Segments are stored in a datacenter cache.
• From the datacenter cache segments are sent to caches located in the points of presence (a PoP cache).
• On the view side the viewer receives a Live Story.
• The player on their device starts fetching segments from a PoP cache at a rate of one per second.

• There is one point of multiplication between the datacenter cache and the many PoP caches. Users access PoP caches, not the datacenter, and there are many PoP caches distributed around the world.
• Another multiplication factor is within each PoP.
  • Within the PoP there are two layers: a layer of HTTP proxies and a layer of cache.
  • Viewers request the segment from a HTTP proxy. The proxy checks if the segment is in cache. If it’s in cache the segment is returned. If it’s not in cache a request for the segment is sent to the datacenter.
  • Different segments are stored in different caches so that helps with load balancing across different caching hosts.

Protecting The Datacenter From The Thundering Herd

• What happens when all the viewers are requesting the same segment at the same time?
• If the segment is not in cache one request will be sent to the datacenter for each viewer.
• Request Coalescing. The number of requests is reduced by adding request coalescing to the PoP cache. Only the first request is sent to the datacenter. The other requests are held until the first response arrives and the data is sent to all the viewers.
• New caching layer is added to the proxy to avoid the Hot Server problem.
  • All the viewers are sent to one cache host to wait for the segment, which could overload the host.
  • The proxy adds a caching layer. Only the first request to the proxy actually makes a request to the cache. All the following requests are served directly from the proxy.

PoPs Are Still At Risk - Global Load Balancing To The Rescue

• So the datacenter is protected from the Thundering Herd problem, but the PoPs are still at risk. The problem with Live is the spikes are so huge that a PoP could be overloaded before the load measure for a PoP reaches the load balancer.
• Each PoP has a limited number of servers and connectivity. How can a spike be prevented from overloading a PoP?
• A system called Cartographer maps Internet subnetworks to PoPs. It measure the delay between each subnet and each PoP. This is the latency measurement.
• The load for each PoP is measured and each user is sent to the closest PoP that has enough capacity. There are counters in the proxies that measure how much load they are receiving. Those counters are aggregated so we know the load for each PoP.
• Now there’s an optimization problem that respects capacity constraints and minimizes latency.  
• With control systems there’s a delay to measure and a delay to react.
• They changed the load measurement window from 1.5 minutes to 3 seconds, but there’s still that 3 second window.
• The solution is to predict the load before it actually happens.
• A capacity estimator was implemented that extrapolates the previous load and the current load of each PoP to the future load.
  • How can a predictor predict the load will decrease if the load is currently increasing?
  • Cubic splines are used for the interpolation function.
  • The first and second derivative are taken. If the speed is positive the load is increasing. If the acceleration is negative that means the speed is decreasing and it will eventually be zero and start decreasing.
  • Cubic splines predict more complex traffic patterns than linear interpolation.
  • Avoiding oscillations. This interpolation function also solves the oscillation problem.
  • The delay to measure and react means decisions are made on stale data. The interpolation reduces error, predicting more accurately, and reduces oscillations. So the load can be closer to the capacity target
  • Currently prediction is based on the last three intervals where each interval is 30 seconds. Almost instantaneous load.

Testing

• You need to be able to overload a PoP.
• A load testing service was built that is globally distributed across the PoPs that simulates live traffic.
• Able to simulate 10x production load.
• Can simulate a viewer that is requesting one segment at a time.
• This system helped reveal and fix problems in the capacity estimator, to tune parameters, and to verify the caching layer solves the Thundering Herd problem.

Upload Reliability

• Uploading a video in real-time is challenging.
• Take, for an example, an upload that has between 100 and 300 Kbps of available bandwidth.
• Audio requires 64 Kbps of throughput.
• Standard definition video require 500 Kbps of throughput.
• Adaptive encoding on the phone is used to adjust for the throughput deficit of video + audio. The encoding bit-rate of the video is adjusted based on the available network bandwidth.
• The decision for the upload bitrate is done in the phone by measuring uploaded bytes on the RTMP connection and it does a weighted average of the last intervals.

• Investigating a push mechanism rather than the request-pull mechanism, leveraging HTTP/2 to push to the PoPs before segments have been requested.

http://www.chepoo.com/facebook-platform-architecture-design-1.html

特别是第2点它扩大了传播范围，在Facebook认为，第2点比1更为重要，Facebook平台的意义就是在这里。”we build the platform optimize for build apps for social graph”，开放平台的意义就是让扩展应用将social graph发扬光大。

“在Facebook开放平台以前，social network封闭式平台，但是今天这种情况结束了”

Facebook Platform的三大目标

1. Apps深度整合到Facebook平台(Deep Integration Into Facebook Website)
app可以集成到用户profile
app拥有独立的首页(canvas page)，首页完全是应用自己控制的，可放任何内容，包括广告。
app可以以用户身份发布feed
app可以发送消息，邀请，提醒等
一个应用只要被用户授权访问他的profile之后，应用就可以调用api获取到比如user/friend/application/privacy information，Facebook API接口也值得各种平台设计者学习。比如用户API接口

2. 病毒式的传播(Mass Distribution through the Social Graph)
传播的核心是feed体系(从09年的眼光来看，Twitter的feed可能比它做得更出色，甚至造成了威胁，并进一步引发它最近的homepage改版)。App可以发布3种不同类型的Feed

application story，相当与应用添加提醒，比如A添加了某应用。
simple story, feed里面表现为一行文本。
full story, 详细，可以预览图片，视频等。
关于feed可参看另外一篇技术分析文章：Facebook的feed格式设计

App可以发送notification(提醒)，request(邀请)。Facebook还提供平台级别的工具如friend selector供app使用。Facebook还通过应用嵌入到Profile通过exposure让更多的用户来使用，比如用户看到好友Profile某个应用有趣也会立即add。

通过以上途径，促进应用的传播，促进信息的传播，促进人的社会化交流。

3. 商业机会(New Business Opportunity)
canvas page可以放任何广告，也可以进行电子商务进行销售，app可以获得所有收入。对于这两种方式，Facebook都是持支持态度。

http://www.chepoo.com/facebook-platform-architecture-design-2.html

一、Facebook Connect

Facebook开放平台之后围墙的问题依然存在，所有的用户所有的内容都在facebook网站的内部。facebook connect可以将facebook的用户，好友，feed和第三方网站作深度整合。将social graph扩大到所有的Web领域。到目前为止Facebook Connect的应用已经非常广泛，比如6月27号的Facebook Developer Garage Shanghai介绍了不少基于Facebook Connect的网站，如提供给外国人分享在上海活动图片的citymoments就非常不错。

二、Facebook新的设计

Mark介绍了很多Facebook新的设计, 比如应用可以不再局限在profile box里面，可以作为一个独立的profile tab, 相当一个独立的页面，应用开发商有更多独立的发挥空间。
另外facebook开放了翻译工具, facebook的翻译工具可以让全球的用户帮助将第三方开发的应用翻译成各种本地语言，并由用户投票每个条目最合适的翻译结果。这个本来用于facebook平台自身的国际化，此次开放给第三方开发者

1. meaningful/有意义
a. social(graph), e.g. Green Patch
b. useful/有用，如Carpool
c. Expressive/表达, Graffiti, draw on friend profile
d. Engaging, 比如2008/5，用户投入在playfish上的时间有9亿分钟。

2. trustworthy/信任
safe/安全, trusted
secure – 平台越提供更多的privacy控制, 用户才会产生越多内容
respectful
transparent

3. well designed/良好的设计
clean, facebook平台确实很干净，值得陈赞, 因此平台要求应用也如此。
fast, use more, 访问速度越快，用户用得越多。
robust, 强壮

原则总结起来就一句话，”keep the ecosystem safe for user, fair for developers“, 平台设计的目标是对用户安全，对开发者公平。

http://colobu.com/2015/04/20/What-is-Facebook-s-architecture/

• Web前端使用PHP. Facebook的HipHop编译器[1] 会将它们转换成C++然后使用g++编译,这样就提供了一个高性能的模版和web逻辑执行层（high performance templating and Web logic execution layer）
• 由于完全依赖静态编译的限制， Facebook已经开始开发一个HipHop的解释程序[2]和HipHop虚拟机，它会将PHP代码转换成HipHop字节码 [3].
• 业务逻辑使用Thrift包装成服务[4]. 服务可能使用PHP, C++ 或者 Java开发， 也可能有其它语言，这依赖于服务需求
• 由Java实现的服务并不使用某种企业应用服务器，而是使用Facebook自己定制的应用服务器. 看起来好像是重新发明轮子，但是这些服务通常是使用Thrift暴露或者使用，使用tomcat或者Jetty都太重了
• 持久化采用MySQL, Memcached [5], Hadoop's HBase [6]. Memcached为MySQL做通用缓存
• 离线处理使用Hadoop 和 Hive.
• logging, clicks 和 feeds数据的传输使用Scribe [7]。 这些数据集中存储在HDFS（使用Scribe-HDFS [8]）, 因此可以使用MapReduce做扩展分析
• 自有技术BigPipe [9]用来加速页面的渲染（使用pipelining logic）
• Varnish Cache [10]用作HTTP网关，由于它的高性能和效率作为他们的首选
• 数十亿的用户上传的招聘使用Haystack处理。Facebbook开发的一个特别的存储方案。提供底层的优化和append-only writes [12].
• Facebook消息系统基于自己的架构， 显著利用分片sharding和动态集群管理. 业务逻辑和持久化被封装进一个称之为'Cell'模块. 每个Cell处理一部分的用户; 当用户增加时新的Cell可以加进来[13]. 持久化使用HBase [14].
• Facebook消息搜索引擎建立在存储在HBase上的反向索引[15]
• 输入提示搜索使用一个定制的存储和检索算法 [16]
• Chat基于Epoll服务器，使用Erlang开发，通过Thrift访问 [17]
• 他们还建立了一个自动化的系统，可以对监控警报进行响应，启动一个合适的修补流程或者在无法自动修补的情况下通知人力来修补[18].

f4: Facebook's Warm BLOB Storage System

http://www.umbrant.com/blog/2014/f4_facebook_warm_blob_storage.html
Haystack is very good at what it was designed to do: fast random access to write-once blobs. In short, it writes out all these objects log-structured to large 100GB files on the local filesystem, and maintains an in-memory index of blob locations so it can serve up a blob with at most a single disk seek.

The downside of Haystack is that it's not very space efficient. Files are replicated both at the node-level because of RAID-6 and also geographically three times, leading to a total replication factor of 3.6x. f4 improves upon this by using erasure coding, which drops the replication factor to 2.1x. Considering that Facebook has 65PB of warm blobs, we're looking at tens of PBs in savings (meaning millions of dollars).

However, the downside of erasure coding is worsened request rate and failure recovery. With erasure coding, there's only a single data replica that can serve read requests. Failure recovery is more expensive since it requires reading the other data and parity blocks in the stripe. In the meanwhile, clients reads require doing online erasure coding, unless they failover to another datacenter.

Haystack is great for hot data, and f4 is great for warm data, the key is determining where a given blob belongs.

Determining hotness
Facebook's blobs tend to be accessed frequently when they're first uploaded, after which access rates drops off exponentially. There are a couple different types of blobs, e.g. photos, videos, attachments, and each had different access rates and drop offs. They chose to look at a nifty metric over time: 99th percentile IOPS/TB. Based on synthetic benchmarks, they knew f4's 4TB drives could handle handle 80 IOPS with acceptable latency. This meant a blob wamigration made sense when the IOPS/TB for a type of blob fell below 20.

Profile photos, it turned out, do not exhibit a strong drop off, and are never moved to f4. Photos ended up being hot for about 3 months, and everything else was only hot for one month.

http://blog.acolyer.org/2014/12/16/f4-facebooks-warm-blob-storage-system/
It’s the story of how Facebook implemented a tiered storage solution for BLOBs and introduced per data class (temperature) replication factor, latency, and time-to-recovery tuning.

There is a strong correlation between the age of a BLOB and its temperature. Newly created BLOBs are requested at a far higher rate than older BLOBs. For instance, the request rate for week-old BLOBs is an order of magnitude lower than for less-than-a-day old content for eight of nine examined types. In addition, there is a strong correlation between age and the deletion rate.We use these findings to inform our design…

These data access patterns support a two-tier BLOB storage solution with Haystack used for ‘hot’ blobs, and content then migrating to f4 after three months for photos, and after one month for other blob types. By reducing the replication factor for ‘warm’ blobs the average request latency goes up slightly (from 14ms to 17ms), and the time to recovery after failure is increased, but the cost of storage is significantly reduced. The effective replication factor (ratio of physical data size to logical data size) for Haystack is 3.6, for f4 this has been brought down to 2.1.

Using Reed-Solomon coding achieves reliability at lower storage overheads than full replication, at the cost of longer rebuild and recovery times under failure. A (10,4) encoding has a 1.4x expansion factor. Keeping two copies of this would give a 2.8x effective replication factor, but the XOR technique further reduces the replication factor to 2.1.

Mechanical Sympathy
Choosing a 1 GB block size for encoding reduces the number of blobs that span multiple blocks, thus requiring multiple I/O operations to read
Separating out storage-intensive tasks from computing intensive tasks in the architecture (for example, the introduction of a separate transformation tier) enables the use of appropriate hardware for each.
Candidate hard drives were benchmarked to determine maximum IOPS that could be consistently achieved at the desired latency
An important consideration in the design of f4 was keeping the hardware and software well matched. Hardware that provides capacity or IOPS that are not used by the software is wasteful; software designed with unrealistic expectations of the hardware will not work. The hardware and software components of f4 were co-designed to ensure they were well-matched by using software measurements to inform hardware choices and vice-versa.

The lower CPU requirements of the storage nodes may even enable the use of lower-powered CPUs in the future, introducing a second form of cost saving.

Self-healing
f4 is designed to handle disk failures, host failures, rack failures, and data center failures. The failure rates are interesting: drives have an annual failure rate of about 1% (so > 1 drive failure per cell per week), hosts fail ‘periodically’, and racks fail ‘multiple times per year’.

When there are failures in a cell, some data blocks will become unavailable, and serving reads for the BLOBs it holds will require online reconstruction of them from companion data blocks and parity blocks. Backoff nodes are storage-less, CPU-heavy nodes that handle the online reconstruction of request BLOBs.

This online reconstruction happens in the request path and rebuilds only the requested blob, not the full block (the blob is typically much smaller than the blob). This keeps request latency down. Full block rebuilding is then handled offline by dedicated rebuilder nodes.

Thus different components at different layers in the system architecture are continually watching, repairing, and rebalancing the system

Facebook lessons learned
Among these the importance of simplicity for operational stability, the importance of measuring underlying software for your use case’s efficiency, and the need for heterogeneity in hardware to reduce the likelihood of correlated failures stand out.

Hardware heterogeneity gives immunity against shared weaknesses in homogeneous hardware.

It all begins with a detailed understanding of the use case and usage patterns, backed up by data analysis.

The software and hardware are considered together, such that the system architecture enables the right hardware to be used for the right job (in previous version of the system compute-heavy and storage-heavy tasks were mixed on the same nodes). Finally, the multiple layers of repair and recovery create a self-sustaining, self-healing system that can survive multiple and continual failures.
http://www.theregister.co.uk/2014/10/13/facebook_codes_warm_erasure_blobs_storage/

• Erasure coding — the adding of calculated parity values (Reed-Solomon codes) to a string of bytes, such that the string can be recovered if an error deletes or distorts some of the complete string. Typically more efficient than RAID at protecting data as it uses less space.

Facebook’s special problem is that it has three main types of user data, with associated metadata, and these three types need huge amounts of storage. Its main and most-accessed datasets are the recent, less than one-week-old postings on a user’s timeline. These get accessed a lot by the user’s "Friends".

Volumes are stored in one data centre and in cells, where a cell is 14 racks of 15 hosts with 30 x 4TB drives per host. Each volume/stripe/block is paired with a buddy volume/stripe/block in a different geographic region. Facebook stores an XOR of the buddies in a third region. This scheme protects against failure of one of the three regions.

http://blog.dshr.org/2014/10/facebooks-warm-storage.html

A BLOB is a Binary Large OBject. Each type of BLOB contains a single type of immutable binary content, such as photos, videos, documents, etc. Section 3 of the paper is a detailed discussion of the behavior of BLOBs of different kinds in Facebook's storage system.

Figure 3 shows that the rate of I/O requests to BLOBs drops rapidly through time. The rates for different types of BLOB drop differently, but all 9 types have dropped by 2 orders of magnitude within 8 months, and all but 1 (profile photos) have dropped by an order of magnitude within the first week.

• That significant kinds of data should be moved from expensive, high-performance hot storage to cheaper warm and then cold storage as rapidly as feasible.
• That the I/O rate that warm storage should be designed to sustain is so different from that of hot storage, at least 2 and often many more orders of magnitude, that attempting to re-use hot storage technology for warm and even worse for cold storage is futile.

http://www.datacenterknowledge.com/archives/2015/05/08/cold-storage-the-facebook-data-centers-that-back-up-the-backup/

The storage server can power up without sending power to any of the drives. Custom software controls which drive powers on when it is needed.

This way, a cold storage facility only needs to supply enough power for six percent of all the drives it houses. Overall, the system needs one-quarter of the power traditional storage servers need.

This allowed the team to further strip down the design. Instead of three power shelves in the Open Rack, a cold storage rack has only one, and there are five power supplies per shelf instead of seven. The number of Open Rack bus bars was reduced from three to one.

Today, data from a hot data center on the West Coast is backed up in a cold storage site on the East Coast and vice versa. The next step would be to apply the Reed-Solomon technique across multiple geographically remote cold storage sites, Patiejunas said.

PDF:
http://www-bcf.usc.edu/~wyattllo/papers/f4-osdi14.pdf

Video:
https://www.usenix.org/conference/osdi14/technical-sessions/presentation/muralidhar

Design a news feed system

http://blog.gainlo.co/index.php/2016/03/29/design-news-feed-system-part-1-system-design-interview-questions/
In fact, there are a bunch of interesting details about news feed like how to rank feeds, how to optimize publishing etc.

To briefly summarize the feature, when users go to their home pages, they will see updates from their friends based on particular order. Feeds can contain images, videos or just text and a user can have a large number of friends.

it’s better to have some high-level ideas by dividing the big problem into subproblem.

For a news feed system, apparently we can divide it into front-end and backend

For backend, three subproblems seem critical to me:

• Data model. We need some schema to store user and feed object. More importantly, there are lots of trade-offs when we try to optimize the system on read/write. 
• Feed ranking. Facebook is doing more than ranking chronologically.
• Feed publishing. Publishing can be trivial when there’re only few hundreds of users. But it can be costly when there are millions or even billions of users. So there’s a scale problem here.

Data model

There are two basic objects: user and feed. For user object, we can store userID, name, registration date and so on so forth. And for feed object, there are feedId, feedType, content, metadata etc., which should support images and videos as well.

If we are using a relational database, we also need to model two relations: user-feed relation and friend relation. The former is pretty straightforward. We can create a user-feed table that stores userID and corresponding feedID. For a single user, it can contain multiple entries if he has published many feeds.

For friend relation, adjacency list is one of the most common approaches. If we see all the users as nodes in a giant graph, edges that connect nodes denote friend relation. We can use a friend table that contains two userIDs in each entry to model the edge (friend relation). By doing this, most operations are quite convenient like fetch all friends of a user, check if two people are friends.

In the design above, let’s see what happens when we fetch feeds from all friends of a user.

The system will first get all userIDs of friends from friend table. Then it fetches all feedIDs for each friend from user-feed table. Finally, feed content is fetched based on feedID from feed table. You can see that we need to perform 3 joins, which can affect performance.

A common optimization is to store feed content together with feedID in user-feed table so that we don’t need to join the feed table any more. This approach is called denormalization, which means by adding redundant data, we can optimize the read performance (reducing the number of joins).

The disadvantages are obvious:

• Data redundancy. We are storing redundant data, which occupies storage space (classic time-space trade-off).
• Data consistency. Whenever we update a feed, we need to update both feed table and user-feed table. Otherwise, there is data inconsistency. This increases the complexity of the system.

Remember that there’s no one approach always better than the other (normalization vs denormalization). It’s a matter of whether you want to optimize for read or write.

Ranking

The most straightforward way to rank feeds is by the time it was created. Obviously, Facebook is doing more than that. “Important” feeds are ranked on top.

Before jumping to the ranking algorithm, I’d usually like to ask why do we want to change the ranking? How do we evaluate whether the new ranking algorithm is better? It’s definitely impressive if candidates come up with these questions by themselves.

The reason to have better ranking is not that this seems the right thing to do. Instead, everything should happen for a reason. Let’s say there are several core metrics we care about, e.g. users stickiness, retention, ads revenue etc.. A better ranking system can significantly improve these metrics potentially, which also answers how to evaluate if we are making progress.

So back to the question – how should we rank feeds? A common strategy is to calculate a feed score based on various features and rank feeds by its score, which is one of the most common approaches for all ranking problems.

More specifically, we can select several features that are mostly relevant to the importance of the feed, e.g. share/like/comments numbers, time of the update, whether the feed has images/videos etc.. And then, a score can be computed by these features, maybe a linear combination. This is usually enough for a naive ranking system.

http://blog.gainlo.co/index.php/2016/04/05/design-news-feed-system-part-2/

The general idea of ranking is to first select features/signals that are relevant and then figure out how to combine them to calculate a final score. This approach is extremely common among lots of real-world systems.

As you can see that what matters here are two things – features and calculation algorithm. To give you a better idea of it, I’d like to briefly introduce how ranking actually works at Facebook – EdgeRank.

For each news update you have, whenever another user interacts with that feed, they’re creating what Facebook calls an Edge, which includes actions like like and comments.

First of all, let’s take a look at what features are used to evaluate the importance of an update/feed. Edge Rank basically is using three signals: affinity score, edge weight and time decay.

• Affinity score (u). For each news feed, affinity score evaluates how close you are with this user. For instance, you are more likely to care about feed from your close friends instead of someone you just met once. 
• Edge weight (e). Edge weight basically reflects importance of each edge. For instance, comments are worth more than likes.
• Time decay (d). The older the story, the less likely users find it interesting.

So how does Facebook rank feeds by these three features? The calculation algorithm is quite straightforward. For each feed you create, multiply these factors for each Edge then add the Edge scores up and you have an update’s EdgeRank. And the higher that is, the more likely your update is to appear in the user’s feed.

Affinity score

We can do exactly the same thing to evaluate affinity score.

Various factors can be used to reflect how close two people are. First of all, explicit interactions like comment, like, tag, share, click etc. are strong signals we should use. Apparently, each type of interaction should have different weight. For instance, comments should be worth much more than likes.

Secondly, we should also track the time factor. Perhaps you used to interact with a friend quite a lot, but less frequent recently. In this case, we should lower the affinity score. So for each interaction, we should also put the time decay factor.

To sum up the ranking section, I hope this common approach for ranking can be one of your takeaways. Also, EdgeRank was first published at 2010 and it can be outdated.

Feed publishing

When a user loads all the feeds from his friends, it can be an extremely costly action. Remember that a user can have thousands of friends and each of them can publish a huge amount of updates especially for high profile users. To load all feeds from friends, the system requires at least two joins (get friends list and feed list.

So how to optimize and scale the feed publishing system?

Basically there are two common approaches here – push and pull.

For a push system, once a user has published a feed, we immediately pushing this feed (actually the pointer to the feed) to all his friends. The advantage is that when fetching feed, you don’t need to go through your friends list and get feeds for each of them. It significantly reduces read operation. However, the downside is also obvious. It increases write operation especially for people with a large number of friends.

For a pull system, feeds are only fetched when users are loading their home pages. So feed data doesn’t need to be sent right after it’s created. You can see that this approach optimizes for write operation, but can be quite slow to fetch data even after using denormalization (check our previous post if you don’t understand this).

Both approaches work well at certain circumstances and it’s always better to understand their pros and cons.

Selective fanout

The process of pushing an activity to all your friends or followers is called a fanout. So the push approach is also called fanout on write, while the pull approach is fanout on load.

Here I’d like to ask if you have any approaches to further optimize the fanout process?

In fact, you can do a combination of both. Specifically, if you are mainly using push model, what you can do is to disable fanout for high profile users and other people can only load their updates during read. The idea is that push operation can be extremely costly for high profile users since they have a lot of friends to notify. By disabling fanout for them, we can save a huge number of resources. Actually Twitter has seen great improvement after adopting this approach.

By the same token, once a user publish a feed, we can also limit the fanout to only his active friends. For non-active users, most of the time the push operation is a waste since they will never come back consuming feeds.

If you follow 80-20 rule, 80% of the cost comes from 20% of features/users. As a result, optimization is really about identifying the bottleneck.

http://www.chepoo.com/feed-architecture-design-analysis.html
发布的时候push给热点用户,再把feed存入热点cache当没收到push的用户登陆后可以到cache里快速pull出相关feed；用户可以先收到push的新feed消息，当想看以前的消息时再去pull出相关的feed。

三、 如何表示feed

每个平台有各式各样的feed消息，考虑到feed消息最终会展示到平台自身、扩展应用以及客户端上，所以对feed格式统一成某种规范而不是发布者随意输出最终展示的文字。同时对图片、视频以及连接等都统一定义。Facebook的实现方式是这样的：

feed是自描述的，即它不是由生产者决定最终格式，也不是前端决定。而是通过template机制来进行。
template在平台中可以由开发者注册，注册时需要定义字段及最终展示样式，如
“{*actor*} 在***游戏中升到 {*credit*} 级”

发布的feed内容仅包含字段数据，也就是变量的值，json格式。
“{“credit”: “80″}”

前端需要显示feed时候调用feed模板，再替换字段得到feed内容
“Tim 在***游戏中升到 80 级”

模板需要定义两个，模板标题及模板内容(展示feed详细内容)，前端根据需要决定只显示标题还是全部都显示。
“target”, “actor”是系统保留字段，代表目标对象和当前用户，{*actor*}必须放在模板标题开始位置。
“images”, “flash”, “mp3″, “video” 是系统保留字段，无需在模板中定义。但这些内容只会在详细feed界面输出。即只要feed内容里面有这个字段值，界面就会自动显示。
facebook文档中没有规定feed长度限制。
每个开发者最多只能注册100个模板。

四、 有效组织feed信息

2、 去重

很多时候有些feed信息是有重复性的，比如A发表了一篇日志，他的好友B和C看后很喜欢选择分享。当这条feed如果出现在B与C的共同好友里就会出现重复feed信息。

3、 排序

Design a news feed system — Medium

First thing, the candidate should do is ask questions to the interviewer:

1. Do you mean like facebook, quora news feed?
2. So, it will fetch all feeds or lets say last 100 feeds?
3. Will the feed be sorted by created date or some important feeds will be given preferences?
4. And many more questions..

The interviewer will not expect you to design a facebook like feed which must would taken months in just 45 minutes. So the idea is ‘Keep it simple’

So lets say, we want to design a news feed system which give some weight-age to each feed.

So here, I will discuss Facebook Edge Rank Algo :

An Edge is basically everything that “happens” in Facebook. Examples of Edges would be status updates, comments, likes, and shares. There are many more Edges than the examples above—any action that happens within Facebook is an Edge.

EdgeRank ranks Edges in the News Feed. EdgeRank looks at all of the Edges that are connected to the User, then ranks each Edge based on importance to the User. Objects with the highest EdgeRank will typically go to the top of the News Feed.

Affinity is a one-way relationship between a User and an Edge. It could be understood as how close of a “relationship” a Brand and a Fan may have. Affinity is built by repeat interactions with a Brand’s Edges.
Actions such as Commenting, Liking, Sharing, Clicking, and even Messaging can influence a User’s Affinity.
Affinity can be based on number of the interactions with your friend, weight of each interaction and time since your last interaction.

Weight is a value system created by Facebook to increase/decrease the value of certain actions within Facebook. Commenting is more involved and therefore deemed more valuable than a Like. In the weighting system, Comments would have a higher value than a Like. In this system all Edges are assigned a value chosen by Facebook. As a general rule, it’s best to assume Edges that take the most time to accomplish tend to weigh more.

Time Decay refers to how long the Edge has been alive; the older it is the less valuable it is. Time Decay is the easiest of the variables to understand. Mathematically it is understood as 1/(Time Since Action). As an Edge ages, it loses value. This helps keep the News Feed fresh with interesting new content, as opposed to lingering old content.
Next is storing this activity.

Ask your interviewer about the use cases of the application.

Our schema would be like this:

id
user_id // user who created the activity
data //may be json object with metadata
edge_rank //calculated using above algo
activity_type // whether its a photo, status, video
source_id //the record that the activity is related to.
created_date //timestamp
We can index on (user_id, created_date) and then perform basic queries.

Publishing the feed

“Push” Model/Fan-out-on-write
As the activity is created publish it to all the recipients. One way is maintain a pub sub model. In which the recepients will be subscribed to the mesaaging queue. Once the activity is generated , its pushed into the queue and the subscribers gets a notification.

2. “Pull” Model/or Fan-out-on-load

This method involves keeping all recent activity data in memory and pulling in (or fanning out) that data at the time a user loads their home page.

Constraints

The push model will start breaking if we have to push the messages to a large audience. Lets say Sachin Tendulkar will have a lot of fans. If this fails there will be a backlog of feeds. An alternative strategy is using different priorities for the fan-out tasks. You simply mark fan-outs to active users as high priority and fan-outs to inactive users as low priority.

The downside of pull model is that the failure scenario is more catastrophic — instead of just delaying updates, you may potentially fail to generate a user’s feed. One workaround is to have a fallback method , e.g get the updates of 10 friends only.
You must be thinking why we chose denormalized activity rather than normalized. So it will also depend on the backend that you are using. The feed with the activities by people you follow either contains the ids of the activities (normalized) or the full activity (denormalized).

Storing id alone will reduce memory usage but add an additional overhead of getting the data based on the id. So if you are building a system in which feed will go to many users , the data will be copied many times and hence memory can be insufficient.

With Redis you need to be careful about memory usage. Cassandra on the other hand has plenty of storage space, but is quite hard to use if you normalize your data.

Interviewer may ask the usage of Redis and Cassandra. 
Redis is read-optimized and stores all data in memory. Cassandra is write-optimized data store.

So with redis the following approach can be used:

1.Create your MySQL activity record
2. For each friend of the user who created the activity, push the ID onto their activity list in Redis.
A hybrid approach of pull and push model can also be used.

TODO: http://m.oschina.net/blog/222877
http://www.quora.com/What-are-best-practices-for-building-something-like-a-News-Feed
http://stackoverflow.com/questions/1443960/how-to-implement-the-activity-stream-in-a-social-network
http://www.quora.com/Activity-Streams/What-are-the-scaling-issues-to-keep-in-mind-while-developing-a-social-network-feed
http://www.slideshare.net/nkallen/q-con-3770885/8-Original_Implementationid_userid_text_createdat20
Twitter materializes (in memory) the items in each of the followers' inboxes
http://www.infoq.com/presentations/Big-Data-in-Real-Time-at-Twitter
RELATED: http://massivetechinterview.blogspot.com/2015/12/twitter-architecture-part-2.html
Facebook aggregates the home feed on demand (from in-memory stores called "leaf servers");
http://www.infoq.com/presentations/Scale-at-Facebook

http://highscalability.com/blog/2012/1/17/paper-feeding-frenzy-selectively-materializing-users-event-f.html

This can be considered like a view materialization problem in a database. In a database a view is a virtual table defined by a query that can be accessed like a table. Materialization refers to when the data behind the view is created. If a view is a join on several tables and that join is performed when the view is accessed, then performance will be slow. If the view is precomputed access to the view will be fast, but more resources are used, especially considering that the view may never be accessed.

Your wall/inbox/stream is a view on all the people/things you follow. If you never look at your inbox then materializing the view in your inbox is a waste of resources, yet you'll be mad if displaying your inbox takes forever because all your event streams must be read, sorted, and filtered. 

The best policy is to decide whether to push or pull events on a per producer/consumer basis. This technique minimizes system cost both for workloads with a high query rate and those with a high event rate. It also exposes a knob, the push threshold, that we can tune to reduce latency in return for higher system cost.

We associate feeds with consumers and event streams with producers. We demonstrate that the best performance results from selectively materializing each consumer's feed: events from high-rate producers are retrieved at query time, while events from lower-rate producers are materialized in advance. A formal analysis of the problem shows the surprising result that we can minimize global cost by making local decisions about each producer/consumer pair, based on the ratio between a given producer's update rate (how often an event is added to the stream) and a given consumer's view rate (how often the feed is viewed). Our experimental results, using Yahoo!'s web-scale database PNUTS, shows that this hybrid strategy results in the lowest system load (and hence improves scalability) under a variety of workloads.

http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/p831-silberstein.pdf
https://www.quora.com/Software-Engineering-Best-Practices/What-are-the-best-practices-for-building-something-like-a-News-Feed
* Combination of push (events are pushed to materialized per consumer feeds) and pull (events are pulled from per producer event store) approaches. Purely push or pull model is less versatile.
* The push/pull decision is made locally on per consumer/producer basis. One size doesn't fit all.
* Global and per producer coherency - With global coherency, events are displayed in the global order of timestamp. With per-producer coherency, time sequence is maintained per producer basis.
* Feed diversity - A frequent producer of events may overshadow events from less frequent producers. Feed diversity addresses diversity in favor of absolute sequencing by timestamp alone.
* The paper describes algorithms for optimization based on various factors, such as cost optimization, optimizing query latency, and so on.
* Describes sample implementation on top of PNUTs and provides performance and other matrices.

1. Queue and prompt on new activity. Stream in (preferably in real-time) comments and likes.
2. All content is not created equal. While reverse chronological delivery is popular, in high volume situations identify signals to leverage in ranking and ordering content in a more intelligent fashion.

https://discuss.leetcode.com/topic/104/design-question-a-data-model-for-rss-feed-reader-app-like-feedly

Requirements

1. User can subscribe to many feeds.
2. Each feed(basically say espn) will keep publishing multiple posts (equivalent of an article).
3. Each post will have some meta data : url, published_date.

• Each user logs in, and HomePage is displayed.
• A HomePage has top 20 latest posts from what feeds he has subscribed.
• Upon clicking on next, the next 20 results are displayed.
• There's also feeds_page, where you click on a subscribed feed, and it'll display all the posts from that feed (again top 20, pagination)

Feed representation.
A feed is of xml form.. whenever backend polls, let's say (every 1 hour), this xml gets rewritten.
All the posts may remain same, or new posts may be appended based on how the feed_owner updates the xml (in this case espn).

Read full article from Design a news feed system — Medium