F4 - Photo Storage at Facebook

https://www.youtube.com/watch?v=34e_g-Ji_30

F4 - Photo Storage at Facebook



F4 - photo storage at Facebook

world's largest photo storage


BLOB "hotness" 

Haystack: 2008

Hot storage design goals

HIgh throughput
- in memory index
- single I/o per request!
- Multiple copies


Failure tolerant

RAIDS
Multiple copies

RAID 6
2 Redudant drivers
2 of 12 = 1.2x replication
Over 3 arrays = 3.6x


RAID 2, RAID 3, RAID 4, RAID 6 explained with diagram

https://www.thegeekstuff.com/2011/11/raid2-raid3-raid4-raid6/

Haystack   warm storage

- Redundancy = replcation 
Read throughput = replication

Total replication = 3.6x

Warm storage

Redundancy still required
Read throughput the ...


RS Encoding:

Reduundancy 


upload request -> web server -> Storage router -> haystack

                                                   F4

haystack -> Migration -> F4



Read request -> CDN -> Storage router -> F4 


f4: What are we solving

Warm storage problem:
- Need to store (warm) data efficiently
- Storage must be highly fault tolerant
- Read latency should be comparable to haystack
- Load is NOT primary concern

Solution: f4
- 2.x replication factor compared to haystack's 3.6x
- yet more fault tolerant than haystack(!!)

f4: Data splitting RS(5,2)

10G Haystack volume

1G Data blocks

Data blocks
Parity blocks

f4: RS Rebuild

RS decoding 

Data blocks   parity blocks

f4: Block placement policy

Blocks of each stripe is placed in different racks(=> hosts)
RS(10,4) is used in practice (1.4x)
Tolerant 4 racks(-> 4 disks/hosts) failures

f4 Cell anatomy

f4 storage consists of a set of cells.
One cell resides completely in one data center
Cell consists of 3 kind of nodes: storage, compute, coordinator
The index is distributed across storage needs

f4 Reads

user request -> router -> index read (1), storage nodes, compute, cell

  Data read (2)

REads with datacenter failures (2.1X)

Router1, router2, router3

Datacenter1
Datacenter2
Datacenter3

Volume1
volume2
xorVolume

Messaging at Scale at Instagram

Messaging at Scale at Instagram

https://www.youtube.com/watch?v=E708csv4XgY

Chaines tasks

Batch of 10,000 followers per task
Tasks yield successive tasks
much finer-grained load balancing
Failure/Reload penalty low

Other Async tasks

Cross-posting to other networks
search indexing
spam analysis
account deletion
API hook



Gearman framework  - load balancer

Gearman in production

persistence horrifically slow, complex
So we ran out of memory and crashed, no recovery
Single core, didn't scale well;
60ms mean submission time for us
Probably should have just used Redis

(Gearman vs Redis)

Celery

Distributed task framework
Highly extensible, pluggable
Mature, Feature rich
Great tooling
Excellent Django support
celeryd

Which broker?

Redis

We already use it
Very fast, eifficient
Polling for task distribution
Messy Non-Synchronous replication
Memory limits task capacity


Beanstalk

Purpose-built task queue
Very fast, efficient
Pushes to Consumers
Spills to disk
No replication
Useless for anything else


RabbitMQ

Reasonablely fast, efficient
Spill-to-disk
Low-maintenance synchronous replication
Excellent celery compatibility
Supports other use cases
We don't know Erlang


Out RabbitMQ Setup

Rabbit MQ 3.0
Clusters of two brokers nodes, Mirrowed
Scale out by adding broker clusters
EC2 c1.xlarge, RAID instance storage
Way overprovisioned


Alerting

We use Sensu
Monitors & alerts on queue length threshold
Uses rabbitmqctl list_queues


Scaling out

Celery only supported 1 broker host last year when we started
Created kombu-multbroker "shim"
Multiple brokers used in a round-robin fashion
Breaks some Celery management tools :(

Concurrency models

multiprocessing (pre-fork)
eventlet
gevent
threads

Problem:

Network-bound tasks sometimes need to take some action


Ruun higer concurrency?
Inefficient :(

Lower batch (prefetch) size?
Min is concurrency count, inefficient :(

Separate slow & fast tasks :)

OUr concurrency levels

fast (14)
feed (12)
default (6)

Problem
Task fails sometimes


Work crashes still lost task






Problem:
Slow tasks monopolize workers


NLP proof gives us choices: to retry or not to retry

problem

Early on, drop task

Publishers confirms

Confirm tasks

Avoid using async tasks as a "backup" mechanism only during failures. It'll probably break.



Better grip on RabbitMQ performance
Utilize result storage
Single cluster for control queues
Eliminate kombu-multibroker





-- study topics --


Sensu

https://docs.sensu.io/sensu-core/1.4/reference/checks/#what-is-a-sensu-check




----------------------------------

Study one more topic

AWS Elastic Beanstalk
https://aws.amazon.com/elasticbeanstalk/

AWS Elastic Beanstalk

Load balancing, provisioning, Application health monitoring, Auto scaling


capacity provisioning, load balancing, auto-scaling, and application health monitoring.

Manageing and configuring servers, databases, load balancers, firewalls, and networks.

Attachments area

Preview YouTube video Messaging at Scale at Instagram

Scaling databases

https://www.youtube.com/watch?v=dkhOZOmV7Fo

Scaling databases

too much load 

master - slave1, slave2,  replicate 

master  handles write, slave handles read, a lot of read compared to write. 

Downsides

- doesn't increase with speed
- replication log

Too much data in one machine 

Master - does not fit into one machine, one computer memory

Too much data

Shard

Hash to multiple machines

1-100   101-200  201-300

downsides

- complex queries 

- range query - hit all the machines - merge the result -> sort them in the memory - join becomes difficult 



replicate and sharding 

One setup for replicate 

another setup for sharding 

How do I overcome the nervous and anxiety issue?

August 7, 2019

Introduction

It is my short research. When I am nervous, I tend to look up wechat and then continuously waste a few minutes to get some update. What  I really look for is the personal connection. As a single person and also sometime introvert, I like to figure out ways to break those bad habits, and then focus on my own study to prepare most important onsite interview experience.

One idea

I just spent a few minutes to watch one of Facebook instagram video provided by Lisa Guo. I quickly understand that I should watch a few videos, every video I will set up a role model for me to follow. So I can calm down and really learn as a senior engineer.

How to make good learning experience during preparation?

August 7, 2019

Introduction

It is my curiosity research. I like to learn as many topics related to Amazon and Facebook during my system design and product design preparation. If I cannot understand the topics, I can quickly go back to those system design tutorial video, and learn the basics first.

Amazon AWS

I like to learn a few areas related to Amazon AWS.

Vacation from August 12 to August 20, 2019

August 7, 2019

Introduction

It is the important for me to prepare and schedule a vacation from August 12 to August 20, 2019. I like to spend time to learn system design, and also work on algorithm and data structure during the break.

Scaling Instagram Infrastructure

Here is the link.

Scaling Instagram Infrastructure

https://www.youtube.com/watch?v=hnpzNAPiC0E

Instagram stack

Cassandra
PostgreSQL               Django             other services

memcache

RabbitMQ

Celery  


-----
Data centers - different data centers
storage vs computing

storage: need to be consistent across data centers
computing: driven by user traffic, as needed basis

Scale out: storage

PostgreSQL  user, media, friendship etc. 

Django -> read  -> replica   DC1
       -> write -> master    DC2
                   replica   DC3

Latency - 

Cassandra user freeds, activities etc. 

   replica  - replica - replica

consistency 2, read as 1

Write - 2
Read - 1 

Computing 

   django RbbitMQ, global balancer -> asynchronous task 

DC1  CD2

memcache  

- high performance key-value store in memory
millions of reads/writes per second
sensistive to network condition

cross region operation is prohibitive 

 NO global consistency 

Let see what problems came out


Counters

select count(*) from user_like_media where media_id = 12345;

100s ms

memcache - database 


select count from media_likes where media_id = 12345

10s us


Cache invalidated 

All djangos 

Memcache lease 


 time   d1   d2   memcache   db


lease-get -> fill
lease-get -> wait or use state

read from dB

lease-set

lease-get

  DC1        DC2

Scaling out 

capacity
reliability 

scaling out - challenges, opportunities

Beyond North America
More localized social network

17:00 
CPU impact: -12 to 10 %
Regression -> a real problem 

CPU   monitor   analyze  optimize
CPU - analyze
continuous profiling 

generate_profile explore --start <start-time> --duration <minutes>

Caller 
Callee 

Optimize - 
reload instagram feed - each url 

variety of mobile - best user experience - 
multiple url to mobile device, size of media 
do less 
300x300
150x150
400x600
200x200

C is really faster
Candidate functions:
Used extensively
Stable


Cython or C/C++ 

Scale up 

Use as few CPU instructions as possible
Use as few servers as possible

One web server 
process 1 ... N
Reduce code 
Run in optimized mode (-O)
Remove dead code 
CProfile - code never executed - remove those code
Share more - 

scale up: memory

Move configuration to shared memory
matrix to measure tradeoff
Disable garbage collection 
20+% capacity increase

Scale up: network latency

Synchronous processing model with long latency

Shared memory / private memory 


Django -> async IO (Feed, news, friends suggestion) - not sequential 

Faster python run-time 
Debugging friendly - Python is better than C/ C++
Async web framework 
- extra service
Better memory analysis
etc etc

Scale dev team

Scaling team 

30% engineers joined in last 6 months
Intern - 12 weeks
hack-A-Month - 4 weeks
Bootcampers - 1 week

ramp up time ? 

32:00/ 51:11
Features
Saved posts
comment filtering 
Multiple media in one post
First story notification
windows App
Instagram Live
Video View notification
Self-hard prevention

Product engineer asks those questions:

Which server?
NewTable or New column?
What index?
Should I cache it?
Will I lock up DB?

Heavy process 
Will I bring down instagram?

Infrastructure engineer baby sit ...

What we want
- automatically handle cache
Define relations, not worry about implementation 


Tao - Data model and API

Source control

with branches 
Context switching 
Code sync/merge overhead
Surprise
Refactor/major upgrade
Performance tracking harder

Adopt one master approach 
No branches
- continuous integration
Collaborate easily
Fast bisect and revert
continuous performance monitoring

Feature launch 


36:56/ 51:11
Engineers
Dogfooder
Employees
Some demographics
World


Feature load test 

how many user uses the feature - feature load test 
Ship it live? Once a week? One a day? Once a diff !!
40-60 rollouts a day

Checks and balances

Code review/ unittest -> code accepted committed -> Canary -> To the wild 

Alert system - Do the needful and revert 

Scale up
Scale dev team
Scale out

40:00 
Takeaways
Scaling is continuous effort
Scaling is multi-dimensional
Scaling is everybody's responsibilities

41:00 
Questions

The Storage Technologies Behind Facebook Messages

I like to watch 10 videos related to Facebook technologies.

This one is the first one. It is called the storage technologies behind Facebook messages.

674. Longest Continuous Increasing Subsequence

621. Task Scheduler

Patience sorting

Here is the wiki article.

Coach Swap- Simona Halep and Darren Cahill

Here is the link.

Nick Bollettieri, Tennis Legend: Talks at GS Session Highlights

Here is the link.

I want to be the best. We will win.

I want to be the best coach in the world. You are responsible for the result.

What continues to motivate you?

Be able to read people. You have to have chance to be success. How to relate to them?

All those players are in common?

They do not care what it takes. Sharapova came to school when she was 9 years old. She refused to lose.

Be a winner, you sleep on it, eat it. You are willing to do uncomfortable things.

How do you spot talent? Thousand students attends the academy.

What makes a good coach?

What is wrong, son? Do not you ever say that you cannot.

I took the chance. Success comes with team work. Thank you. One person cannot do it.

The Mindset of a Champion with Legendary Tennis Coach Nick Bollettieri

Here is the link.

I like to conduct some research how to prepare for most important onsite interviews from Amazon and Facebook in August, 2019. How should I perform best I can? I experienced a few issues when I met a computer science Ph.D., we worked together to give each other interview for 2 hours. I just could not believe how good he is in our mock interview. I felt so nervous since I like to work for Amazon and Facebook as well.

It is time for me to search some coach advice.


Enter the race

Quit, do not think they can win.

Without a team, a plan and a place to develop the talent. Along the way, you should develop the talent.

Champion find ways to make it happen. No matter how long it takes.

It is not I did. We did. I do not care who you are. All teams have values. The value can be ...

Core value - Team work.

Nick is the best coach in the world.

Find ways to get away the nervous.

60 years a coach

What I learn from my best students - Sharapova, etc. each of them.
Make impact for people's life - go on generations.

Learn a lot in little time, you lost it.
Learn a little over long time, you keep it.

You judge people by efforts you put in. Not score you have.

When you go out to do the job. You go out to win. It is not good "You play the best you can".

My last mark, it is all about winning.

How load balancers work - System Design Interview knowledge [Beyond the interview]

Here is the link.


Knowing about how a load balancer works is important for most software engineers. Load balancing algorithms and techniques can be useful for your next system design interview too. Besides that, it quite interesting! This video covers load balancing algorithms, how Google uses load balancing and traffic routing, a real word load balancing example for a web application, stateful load balancing and consistent hashing for load balancing.

Enumerate a few load balancers.

Enumerate a few benefits of load balancers.

IP range -

Transport layer - IP range -
Application layer  - conent header - Level 7 header
DNS load balancer - Uber heavy use on this


Two http server, one backend server

System Design Interviews - Communicate effectively [Part 3]

Here is the link.

System Design Knowledge - How to improve [Part 2]

Here is the link.

System Design Shopify eCommerce platform Interview Question for software engineers

Here is the link.

Keywords:
- Customers
- Products
- Orders
- Payment methods
- Shop owner
- Isolation
- Plugins
- Store front vs backend API


Second step, 3 key features

1. Customated store creation
2. Backend
3. Hosting/Networking

Brokers -> Shopify website -> store orchestrator

How HTML5 Web Sockets Interact With Proxy Servers

Here is the article for me to read.

I like to put this article on the waiting list to be scheduled to read.

Consistent Hashing

Here is the link.

Database Sharding

Here is the article.

Understanding Database Sharding

Here is the article. I plan to read it again.

System design blog - My system design notes

August 4, 2019

Introduction

It is important for me to understand the basics of system design. I am open to all kinds of technology, even though I do not have time to play with each technology, but learning is so important as a programmer who has invested over 4 years on algorithm and data structure.

One system design blog

Here is the blog I like to read this weekend.

Long Polling vs WebSockets vs Server-Sent Events

Here is the article.

Case study: two hours mock interview with a friend

August 4, 2019

Introduction

I had a two hour mock interview with a friend met on interviewing.io. I like to write down some notes and help me track how many things I should work on next two weeks.

Case study

I am preparing Amazon and Facebook onsite interviews in August. He is preparing Google and Amazon onsite interviews in August.

We met on pramp.com. I gave him the algorithm to work on for warmup. The algorithm is called is graph bipartite. Here is his code with my review, I added all comments.

He told me that he always using graph algorithm pseudo code as a template.

He likes to give me an algorithm to work on after we spent 30 minutes. I chose to give him a hard level algorithm to work on since I like to learn KMP algorithm from him.

We had discussion about KMP algorithm, he showed me his code to use longest prefix suffix array to solve the problem.

Next he gave me the algorithm to work on. Find if there are increasing subsequence with length three in the array. I did not come out the correct answer, I came out partial solution to see if maximum length of any continuous increasing subarray is bigger than two.

He showed me that it is special case of longest increasing subsequence. He then showed me O(nlogn) solution using binary search.

He also showed me his solution for hard level algorithm Leetcode 214: shortest palindrome. He told me that he submitted the code while I coded my solution.

Actionable Items

The mock interview partner learns things quickly. He showed me two solutions, one is binary search to solve longest increasing subsequence, and then second one is hard level 214 shortest palindrome using same function used for KMP algorithm - longest prefix suffix array.

What I did is to show him how I can write a simple while loop algorithm and test the code using pramp.com, and then he showed me a failed test case. I explained the idea to use extra space to help and using linear time to solve the algorithm, he explained to me to work on the idea to use binary search.

Five hours on tennis court

August 4, 2019

Introduction

It is my personal health research. I like to push myself hard to spend more hours on tennis court in order to lose weight and also get some benefit to enjoy the sunshine, stay healthy.

How I spent 5 hours on tennis court?

I spent five hours on tennis court in central park of Burnaby.

Here are things I did on tennis court:

1. Warm up using stripe band starting from 12:30 PM
2. Play tennis against wall 20 - 30 minutes
3. Chat with friends on tennis court, watch BC 14 years champion - a young chinese training with the coach and other young players.
4. Practice serve on tennis court, at least 5 * 30 tennis ball
5. Rally with a friend on tennis court from 3:00 PM - 5:00 PM

Code study: Rabin Karp algorithm

August 4, 2019

Introduction

I had two hours mock interview with a friend met on interviewing.io. He shared his Rabin Karp algorithm.

Here is the gist.

Case study: KMP algorithm to study

August 4, 2019

I had two hours mock interview with the engineer who prepares Google onsite from 10:00 PM to 12:00 PM today. I asked him to solve hard level algorithm 214. Shortest Palindrome. We had discussion about the algorithm can be solved using KMP algorithm. He shared with me his C# code for KMP algorithm. 


Here is C# code. 

Case study: Is graph bipartite

August 4, 2019

I gave out the algorithm for the interviewee to work on, he wrote C# solution. Here is the gist. I also went over the code and add some comment, here is the gist.

300. Longest Increasing Subsequence

Here is the link.

I have a mock interview and worked on the algorithm to find if there are three increasing subsequence in the array on August 4, 2019 10:00 PM. I found out that I solved the partial solution and then the interviewer told me that it is special case of longest increasing subsequence. And also he explained to me how to use binary search to solve it using O(nlogn) time.

I have to work hard to review the algorithm. The first step is to share my last submission back in 2017. And then I plan to study more on various solutions on the algorithm.

public class Solution {
    public int LengthOfLIS(int[] nums) {
        int size = nums.Length;

            if (size == 0) { 
                return 0; 
            } 

            var subsequence = new int[size];

            int length = 1;
            for (int i = 0; i < size; ++i) 
            {
                var current = nums[i];
                subsequence[i] = 1; 

                // get maximum value from all options
                for (int j = 0; j < i; ++j) 
                {
                    var visit = nums[j];
                    if (visit < current)
                    {
                        subsequence[i] = Math.Max(subsequence[i], subsequence[j] + 1);
                    }
                }

                // update the length if need
                length = Math.Max(length, subsequence[i]);
            }

            return length;
        }    
}

A list to prepare

August 3, 2019

Introduction

It is my short research. I like to figure out why it is so important for me to learn and think about as a system designer. I am preparing for Amazon and Facebook onsite interview in August, I just could not believe that I have to learn how to be a passionate presenter to work on white board presentation like those youtube.com I like, and also I need to thank those authors to share the ideas through medium.com.

First one to say thanks

Here is the article I like to read and I really think about how I should keep reading and expand my knowledge.

HTTP and Websockets: Understanding the capabilities of today’s web communication technologies

Here is the article. I like to spend 10 minutes to read first.

Here are my notes.

Two API types:
Web service APIs (e.g. SOAP, JSON-RPC, XML-RPC, REST
Websocket APIs

HTTP

Http functions as a request-response protocol in the client-server computing model.

HTTP polling
Http short polling
Http long polling
Http periodic polling

HTTP Streaming

Alternative to websockets

SSE (Server sent events/ EventSource)

Sample applications: Twitter updates, stock quotes, cricket scores, notification to browser

Websockets

WebSocket solves a few issues with HTTP:

• Bi-directional protocol
• Full-duplex communication
• Single TCP connection

Sample applications: IM/ Chat apps, Games, Admin frontends

Websockets problems to go through proxies/firewalls -> Secured WebSockets

If you hold the stock market, you will grow with America, says Jack Bogle

Here is the link.

50% loss, a lot of people act on emotions.

Act on emotions and move out the stock market. Emotion will defeat you totally.

Long term correction with GDP, stock market is 95%, the annual correlation is 20%. You make good long term bet, short bet is not way to go.

Liquid crisis -> ...

Market structure -> liquid

Volatility strike ...

10 years after crisis 

Vanguard CEO Tim Buckley: Investors Should Be Very Conservative Around Return Assumptions | CNBC

Here is the link.

We tend to stay away asset from bitcoin etc., no cashflow, where is long term ... except speculation.