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.

US security

Here is the link for me to read.

美国的退休政策分三个层次

美国的退休制度设计具有一定弹性，不少老人选择延迟退休，只要你还干得动，老板也愿意雇你。如果你在美国旅行，留心观察一下就会发现，旅游、餐饮等各类服务行业中都有不少老年人在工作。

1.提前退休

年满62岁就可以开始领退休金，但要打7折，每推迟一个月领取，打的折扣就少一些。

2.正常退休

根据出生日期的不同，美国社会保障局设定了不同的正常退休年龄，比如1937年和1937年以前出生者，退休年龄是65岁，1943年到1954年间出生者，退休年龄是66岁，1960年和1960年后出生的人，退休年龄是67岁。在正常退休年龄内退休的人，可以领取全额退休金。

3.延迟退休

选择延迟退休的人在原有的退休金基础上还能获得奖励性的收益(Delayed　retirement　Credits)。如果你的正常退休年龄是66岁，你选择在67岁退休，那么你每个月能拿到108%的退休金，如果你选择在70岁或70岁以后退休，那么你每个月能拿到132%的退休金。

这种以自愿为原则、渐进式的退休制度设计，让人们可以根据自身情况进行选择，而拉开档次的退休金获得比例，特别是对于延迟退休的奖励性收益，一定程度上鼓励了美国人延迟退休。

美国的双轨制

联邦雇员和地方政府雇员一般不参加社保，他们有自己的退休金计划（pension），一般是按工作年限，一年累计1%到2%。 退休金按最高收入3年或5年平均为基准，乘以累计值。如果工作35年，累计了70%，最高收入平均是6000每月，那么退休金就是4200，远大于社保的退休金。

美国政府雇员总数是两千多万，占劳动力人口的15%，加上政府雇员中高薪的比例不少，造成退休金巨大的差距，一直被社会舆论批评。最近几年由于政府退休金开支越来越大，已经入不敷出，有些部门如邮局放弃退休金计划而加入联邦的社保计划。

中美两国的退休储备

美国人退休后的经济来源有三个支柱：第一支柱指的是政府主导的基本养老金，第二支柱指的是雇主主导的企业年金，第三支柱指的是完全靠个人积累的个人税延养老金。其中公共养老只是最弱的一部分。

而中国则严重依赖社保养老，第二支柱、第三支柱完全不给力。所以为啥美国人不用存钱？因为养老的问题人家已经做好准备了。

在美国，退休金主要由四部分组成

1.社会安全福利（Social Security Benifit）

只要你领工资，就必须将税前收入的一定比例交给政府，在缴满一定的期限（40个季度）后，便能在退休后领取相应的福利。

这部分钱有多少？自然是很少了...而且关于社安金即将倒闭的消息这些年一直没有消停过，等你退休还有没有承诺的那个数...谁也不能保证。曾经有人给过这样一个数字对比，虽然算法不是很准确，但是基本上符合实际，各位对号入座！

1）底薪如售货员，饭店服务员等，时薪8到10元，假如平均月收入1400：工作10年的话，退休金是360；工作20年的话，退休金是701；工作35年以上，退休金是892。

2）一般收入如办事员等，月薪2000到3000，假如平均月收入2500：工作10年的话，退休金是643；工作20年的话，退休金是902；工作35年以上，退休金是1245。

3）全职工作中位数收入如小学教师，记者等，年薪四万到五万，假如平均月收入3500：工作10年的话，退休金是765；工作20年的话，退休金是1084；工作35年以上，退休金是1565。

4）高薪工作如职业白领等，年薪6万到10万，假如平均月收入6000：工作10年的话，退休金是993；工作20年的话，退休金是1542；工作35年以上，退休金是2131。

5）顶薪如管理层等，超过11万社保最高限，即平均月收入9166：工作10年的话，退休金是1283；工作20年的话，退休金是2017；工作35年以上，退休金是2605。

2.部分公司和政府的退休金（Pension Plan），不需要雇员缴费

说到这部分就更是欲哭无泪了，目前绝大部分公司都不在提供Pension Plan，很多公司也在实施老人老办法，新人新办法。当然政府雇员还有此计划，主要适用于公务员，此外，某些工会也提供企业养老金。

3.企业退休金计划 (401K)

由企业主导，雇主和雇员共同出资的企业补充养老保险制度，适用于在公司有提供该福利者。多数公司都提供401K计划，只是计划补偿不同。

4.个人退休金计划 (又分IRA、Roth IRA)

由个人负责，自愿参加的个人储蓄养老保险制度。

注：这里只讲“工薪阶层”，低收入者或者多套住房投资者不在讨论范围。

美国华人养老需注意

1.如果移民去了美国，只要符合条件，还可以领中国的退休金

根据《中华人民共和国社会保险法》、《实施〈中华人民共和国社会保险法〉若干规定》以及《关于获准出国定居的退休人员加入外国籍后仍可享受退休待遇的规定》等中国法律和规范性文件，退休人员加入外籍后可继续享受相关退休待遇。

也就是说，只要符合在中国领取退休金的基本条件，退休人员加入外国国籍后，仍可继续领取养老金。所以，不管你是移民去了美国，还是移民去了加拿大、澳大利亚等国家，只要符合条件，都是可以领取退休金的。

对于美国华人华侨来说，退休之后如果不在美国居住，假定已经拥有起码四十季度点数，是否可以继续领取社会安全退休金，要分以下情况：

假如您是美国公民，只要不是定居在古巴或朝鲜，即使长期在海外居住，都可以要求政府，按月将退休金寄到国外的地址；如果银行账户设在香港或日本，政府更可以将退休金，以自动转账方式送到户口内，但设在其他亚洲国家的银行账户则不能自动转账。

假如您不是美国公民，便有可能无法在海外取得社安退休金。这个条例有一些例外的情况。有一些国家的公民，长期居住在海外也可以领取社安退休金，但中国大陆、香港、澳门、台湾公民不包括在内。因此，中国大陆、香港、澳门和台湾公民即使有美国永久居留权(绿卡)，也在美国工作十年以上，离开美国超过六个月社安退休金便会停止。其实只要您连续离开美国国境30天，便已经算是离开美国了，将来回到美国后要连续居住起码30天才算回到美国。

也就是说，如果您是美国公民，长期离境并不会对您的养老金领取带来影响。但请注意，养老金银行自动转账需符合一定条件，具体可咨询美国相关机构。如果您持有美国绿卡，那么请务必谨记，最好不要一次离境美国超过半年，否则可能会被停发养老金。

System Design: How to design Twitter? Interview question at Facebook, Google, Microsoft

Here is the link.

Core features - focus on them first


1. Tweeting
2. Timeline
Two things: your own timeline
- User
- Home
3. Following

Naive solution first

Relational database:
User table, tweets table

Tweets table with three columns:

ID
Content
user

User table

ID
Name

We care about more availability, little less about consistency in small time frame.

Optimized solution

System Design: Messenger service like Whatsapp or WeChat - Interview Question

Here is the link.

1. One one text
2. Sent/ Delivered/ Read
3. Push notifications

Offline, the messages are sent in wrong order.

Second feature:

Dive deep:

Multicast messaging, like cache, database replication, sharding, store of message, usage limit, premium service, load balancing,

Features -> Architecture

Simple feature first, and then grow architecture, the interviewer will tell you what he likes you to talk about.

Online games system design frontend PART 1 | online game software architecture

Here is the link.

Three different functionality

check_input()
update_game_state()

214. Shortest Palindrome

August 2, 2019

I have fun to read the article, I spent more than 30 minutes to read. I like the writing as well. This should be the first time I read the article!

10 minutes reading:

Read KMP algorithm through KMP algorithm

Here is the wiki article.


Spend 30 minutes to learn how to build KMP prefix table

Read the discussion post here.

Here is C# code I like to study.