How to Improve Design Skills
April 26, 2019
Showing posts with label System Design. Show all posts
Showing posts with label System Design. Show all posts
When it Goes Wrong - How to Ace System Design Interview
How to Land Your Dream Job Series
The Approach
- It’s important to follow some systematic approach and drive/lead this conversation.
- SNAKE(Scenario, Needs, Application, Kilobyte(Data), Evolve)
- Requirements, constraints/estimates, high-level design, detailed design
- Talk about different approaches, pros and cons
- It’s more important to follow the approach when you don’t have (much) clue or the interviewer wants to focus on specific domain or jump to detail too early.
System design interview is very important, as it’s usually conducted by managers or senior engineers who have more power to decide to hire or not, or the level.
Different from coding interview, how the system design interview goes varies a lot. Some companies(like Facebook) follow some good process, but others are not.
Depended on the interviewer, or what the candidate says, the system design interview may go wrong pretty soon.
1. Algorithm/Coding Question as a part of System Design
- During the middle of the discussion, the interviewer may (unexpectedly) ask algorithm question.
Example: Autocomplete Service
- As a system design question, the candidate may talk about: requirement
- for a distributed prefix tree, how to shard data: consistent hash etc.
- The interviewer may also ask and focus on how to Get top x word (ranked by frequency) from a single server trie: the algorithm question.
- The candidate should be aware of the change, and approach it as an algorithm question and quickly give an optimal algorithm/pseudo code quickly.
2. The interviewer looking for specific direction/answer
Focus on detail too soon and too much
- There are a lot of things the candidate can talk, but sometimes, the interviewer is looking for some specific direction/answer.
- This is not good, as the system design is supposed to let the candidate lead the process, but you have to try your best when you are in this situation.
Example: One backend key value db server is slow, how to solve it?
The interviewer may jump to how to use cache, before you go that direction, make sure you also(still) talk about the scenario, outline other approaches first.
You may not have much time to go through those: you have to take and talk a lot about X when the interviewer is saying: let's go X approach, but still outline them in the whiteboard, at least you can resume those later.
- Make sure ask these questions first
- does the backend provide client library?
- How many client apps? How easy to update them to new code/library?
- What’s the goal? How much effort? a short term fix to just make it work? or a long term invest
- What’s the team structure? Who is responsible to fix it (what team has the resource)? DB team or client team?
- Potential solutions/discussion:
- local cache in client side or remote central cache
- request coalescing in client library
- distribute the db: shard the database and add a proxy layer which can distribute the request to the right shard
- Stability: rate limit, etc
What We Can Do?
Do Not Repeat Yourself
- When asked the same questions after you already give (some) answer about it. Don’t just repeat your previous answer or try to expand it.
- Usually, this means your answer is not what the interviewer is looking for at all.
- Talk something meaningful and useful, that shows your skills.
Know/Guess what’s the interview is looking for
How vs Why and What
In system design, how to do it in detail is usually not important, instead focus on why and what info we are trying to get.
Between approach x and y, how you can determine which approach to take?With the system is already running, how can you decide you should add local cache or centralized cache?- THIS IS NOT IMPORTANT:
how to add the log, what to log and how to analyze log - WHAT IS IMPORTANT: how to determine the cache performance: hit ratio.
- THIS IS NOT IMPORTANT:
System Design Books
- Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
- The Art of Scalability: Scalable Web Architecture, Processes, and Organizations for the Modern Enterprise, Second Edition
- Web Scalability for Startup Engineers
System Design Prep Resource
Notes on Distributed Systems
Consensus
Paxos
Roles: proposers, acceptors, learners
Practices:
Cassandra lightweight transactions, CAS
Raft
replicated state machine
strong leadership
(append-only) log replication
a term number and an index
randomized election timeout
2 Phase Commit
Vote
Commit/abort
a blocking protocol
3 Phase Commit
Vote
Prepare
Commit/abort
a non-blocking protocol
CAP
LSM
Redis
pub-sub
Only online customers can get message
No customer group, each customer gets all message
Basic
WAL - write-ahead-log
R+W>N
Scalable Stateful Services
Paxos
Roles: proposers, acceptors, learners
Practices:
Cassandra lightweight transactions, CAS
Raft
replicated state machine
strong leadership
(append-only) log replication
a term number and an index
randomized election timeout
2 Phase Commit
Vote
Commit/abort
a blocking protocol
3 Phase Commit
Vote
Prepare
Commit/abort
a non-blocking protocol
CAP
LSM
Redis
pub-sub
Only online customers can get message
No customer group, each customer gets all message
Basic
WAL - write-ahead-log
R+W>N
Scalable Stateful Services
How to Improve Design Skills
How to improve design skills from Yun Yuan
Non-function features
Unique features
Rate limit - scalable, availability, DDos
What's the bottleneck
How to scale
How to handle change - node added/removed/crashed
Better user experience
Thinking from client/user perspective
How they use it, what they would like to know
Non-function features
Unique features
Rate limit - scalable, availability, DDos
What's the bottleneck
How to scale
How to handle change - node added/removed/crashed
Better user experience
Thinking from client/user perspective
How they use it, what they would like to know
How to Review and Discuss - Software Design
Talk/Think about all related
- how do we store data,
- client api
- ui change
- back compatibility: how to handle old data/client
But focus on most important stuff (first)
Talk/think about design principles/practices
- such as idempotent, parallelization,monitoring, etc
- Check more at System Design - Summary
What's the impact of other (internal and cross-team) components?
What're the known and potential constraints/issues/flaws in current design?
Don't only talk about its advantages,
Also talk about issues, don't hide them
What are alternatives?
Think alternative and different approaches, this can help find better solution
We can't really review and compare if there is no alternatives
Welcome different approaches
- although it doesn't mean it's better, or we will use it
How do can we know when the new feature works or doesn't work
How can we know problems happen
Feature Flag
Can we enable/disable the feature at runtime
Be Prepared
Ok to have informal/impromptu discussion with one or two colleagues
But make sure everyone is prepared for the formal team design discussion
All attendees should know the topic: how they would design it
Attitude
Listen first
When you don't agree with other's approaches
Don't get too defensive
Talk about ideas not people
Be prepared
Make API/Feature easier
- to use
- to test/rollback in production (feature flag)
Related
System Design - Summary
- how do we store data,
- client api
- ui change
- back compatibility: how to handle old data/client
But focus on most important stuff (first)
Talk/think about design principles/practices
- such as idempotent, parallelization,monitoring, etc
- Check more at System Design - Summary
What's the impact of other (internal and cross-team) components?
How others components use it?
Don't only talk about its advantages,
Also talk about issues, don't hide them
What are alternatives?
Think alternative and different approaches, this can help find better solution
We can't really review and compare if there is no alternatives
Welcome different approaches
- although it doesn't mean it's better, or we will use it
Development Cost
- How difficult it takes to implement?
What may change and How to evolve
What may change in (very) near future?
Visibility/Monitoring- How difficult it takes to implement?
What may change and How to evolve
What may change in (very) near future?
How do can we know when the new feature works or doesn't work
How can we know problems happen
Feature Flag
Can we enable/disable the feature at runtime
Be Prepared
Ok to have informal/impromptu discussion with one or two colleagues
But make sure everyone is prepared for the formal team design discussion
All attendees should know the topic: how they would design it
Don't make design decision immediately - for things that really matters
Take time to reflect and develop disagreement, talk it again later
Listen first
When you don't agree with other's approaches
Don't get too defensive
Talk about ideas not people
Be prepared
Make API/Feature easier
- to use
- to test/rollback in production (feature flag)
System Design - Summary
System Design Practices
Design home page stream
Design feed
Mixed approaches - Push + Pull from
-- selectively disable push for celebrities, pull them instead.
https://engineering.pinterest.com/blog/building-scalable-and-available-home-feed
Design Decisions For Scaling Your High Traffic Feeds
Expire mp3 in cdn and generate new one after x min
pre-load
Playlist Shuffle
- Fisher-Yates shuffle
- a good, uniformly distributed mix of all the tracks, no burst
Design key-value Database(lookup service)
Design APIs for add/update/query
CA or CP?
- List main components first (meltable, sstable, index, bloom filter, WAL log)
- membership and failure detection(gossip)
- Partition (Virtual nodes, consistent hashing)
- Replication(Versioning)
- handling temporary failures
- read repair and anti-entropy using Merkle tree
- Sparse index file and loaded into memory
- compress block
Write ahead (redo) log
- Global(Local) secondary index
- Conflict resolution
- Request coordinator
- Smart client can send requests to right replica
- Cache: row cache, key cache
Merge and compaction
Advantages over B-tress
- turn random writes into sequential writes
Downside of LSM tree
- compaction will interfere with the performance (not consistency)
- more storage
- key may appear in multiple sstable,
- more storage during compaction
Design column database
How to update some fields
Design Delayed Job Scheduler
- single server or distributed
- generic or for specific tasks
- Java Delay Queue
- wheelTimer (Netty)
- qurtz
Top K Frequent Elements in Recent X mins
- data structure: hashmap + linkedlist
system design:
- approximate
- batch, update every x seconds
- 分阶段统计, bucket
- sample
- different intervals for different cache(hour, daily)
Design Ticket Master - TODO
- Analyze the requirements: QPS, SLA
- Autoscale, predicative scale based on estimated popularity of concert
- queuing and prioritizing
How to Design a Trending Algorithm - TODO
- offline pipelines
- cache, no need realtime
- candidates: hashtag
- signal: influencer, location, personalization
Make single-server datastore to peer-to-peer, linearly scalable, clustered systems
Dynomite
Design distributed priority queue service + Delayed queue
Distributed delay queues based on Dynomite + Redis
A Sorted Set containing queued elements by score.
A Hash set that contains message payload, with key as message ID.
A Sorted Set containing messages consumed by client but yet to be acknowledged. Un-ack set.
Design distributed file system
- master for meta data: where the chunk stores
- get file chunk location from master, read directly form slave
- replication, checksum
Image conversion service
- queue, asynchronously
Design feed
Mixed approaches - Push + Pull from
-- selectively disable push for celebrities, pull them instead.
https://engineering.pinterest.com/blog/building-scalable-and-available-home-feed
Design Decisions For Scaling Your High Traffic Feeds
Cassandra + Denormalize
Redis + Normalized
Selective Fanout Based On Producer/Consumer
URL shortener
https://www.youtube.com/watch?v=fMZMm_0ZhK4 - Range based
- read heavy
- separate read/write to different apps
- able to disable write functions
- id (auto increment), actual url, and shorten url
- base 62 encode the id to string(shorten url)
- generate auto-generate id
- can use sql or nosql as long as find a way to generate unique long
- rate limit, prevent abuse
Insert Long Url to db, get the primary key: long
Convert base10 to Base62[0-9a-zA-Z], other characters such as -,_+, convert long to short url
Decode short url to long number and query db to get long url.
How to make it scalable
How to analyze short url click event
301 or 302?
- custom url
Extension - popular urls in last hour/day
Generate unique ID numbers
Twitter Snowflake
- 41bit timestamp
- 10bit workerid
- 12bit sequence
Flickr Ticket Servers
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
Map many logical shards to fewer physical shards
How to assign shards when we can add/remove nodes?
User Overseer(leader) to change concurrent into serialized problem
Crawler
- politeness: rate limit
- put same host pages into same queue
- different priority for different sites - multiple queues
How to index and store in memory
How to support free text queries, phrase queries
Map<String, List<Document>>
List<Document> is sorted
Document: docId, List<Long> positionIds
List<Long> is sorted
How to save to files
How to merge small files into big files
-- When save to file, make it sorted by word
-- Use merge sort to merge multiple fields
How to make it scalable - how solr cloud works
Auto completion in search
- single node
- Trie, Topk
Design Hit Counter - how to count number of requests in last second, minute and hour - link1,
Generate Game Map
- brute force, randomly generate one, check whether it can be solved in limit time by machine
- different difficulty level
Design score/rank system for social game.
Need update score realtime?
- yes, for this user's operation, when score is small
- no, for others' operation, when score is big
Rank - realtime?
- yes, when user is ranked in X(1000),
- no, if user ranks is below Y(1M)
Average score
- rank: use sorted tree - sorted by score, node splitted by score range
- table: userid, score
- sharding
- append, not update existing data
- separate score change to different types: real time vs batchable
- batch score change
Search nearby places
- GeoHash
Design Slack
Design Chat app like messenger, what's app
https://www.youtube.com/watch?v=zKPNUMkwOJE&t=2s
Websockets
ServerA forward message to ServerB which forwards to clientB
How to manage/detect friends status - presence
- reduce message, avoid O(n^2)
- Each user subscribes to its subscription list in server
- When one user state's changed, it uses pub/sub to update all related users's subscription list in server side
- Server pushes friend status to each user in some fixed interval - if there is change (batch)
How to store messages
Typing indicators
- Only send it to users who is currently interacting with this user/group
Message status: delivered, seen
De-duplication
- url dedup: use bloom filter
Detect duplicate documents in billions of urls
- back-of-the-envelope calculations
- (30 bytes for url + int/long(4 or 8 bytes)) * 10^9(~1g) ~ 34g
- A1: Hash and split into multiple files - slow (even with multiple threads) as a lot of IOs
- A2: Parallelize in multiple machines - like map-reduce
Design log collection and analysis system
- Auxiliary service, should not affect the existing service (Monitor system memory and cpu, adjust the push rate accordingly)
Design shopping cart
addToCart,removeFromCart,changeQuantity
- monitor
- abandoned cart
guest cart
- cookie
- merged if user login later
- check items availability at some point
- call other services - stock service(price, availability), metadata service, images(cdn)
ecommerce - amazon
- nosql: wide column for product table
- concurrency for order: optimistic, pessimistic
- analytics
- abandoned cart, user behavior(click,view,add/remove from cart)
products
checkout
Payment
- two phrases: Authorization, Capture
shipping
customer service
Design rate limiter
- Separate from application
- warn/notify user before user reaches 90% limit
Algorithms:
Design Miao Sha
- Use cases: different phrases of the activity: before, available, sold out
- cache boolean available instead of the count
- Principle: fair(fifo) - but no need to 100% guarantee
Two types of queues
- one queue for each on-sale hot product, only keep x (count *1.x) requests, reject directly if more than it (ask them to retry after x mins)
- handled by one single server which reads from queue
- avoid distributed problems
- asynchronous processing
Cache activity page
- protect order page by adding a server side generated random number
- server side will generate and update a non-cached a js including activity info and the random number for the order page, the js is not cached in client side
How to update stocks - concurrency
How to send email notification, handle delivery
- asynchronous, put them into a queue
Design train ticket booking - Chunyun
Protect against from hackers
- CAPTCHA
- filter based on ipAddress, acountId
- Prevent abuse: cheating
Design email
Counter
- 1. Use count table
- 2. Use Redis
Hierarchical Data
- id, parentid
Design the data structure for large social network
Design system to store/read images
https://www.youtube.com/watch?v=fMZMm_0ZhK4 - Range based
- read heavy
- separate read/write to different apps
- able to disable write functions
- id (auto increment), actual url, and shorten url
- base 62 encode the id to string(shorten url)
- generate auto-generate id
- can use sql or nosql as long as find a way to generate unique long
- rate limit, prevent abuse
Insert Long Url to db, get the primary key: long
Convert base10 to Base62[0-9a-zA-Z], other characters such as -,_+, convert long to short url
Decode short url to long number and query db to get long url.
How to make it scalable
How to analyze short url click event
301 or 302?
- custom url
Extension - popular urls in last hour/day
Generate unique ID numbers
Twitter Snowflake
- 41bit timestamp
- 10bit workerid
- 12bit sequence
Flickr Ticket Servers
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
Map many logical shards to fewer physical shards
How to assign shards when we can add/remove nodes?
User Overseer(leader) to change concurrent into serialized problem
- politeness: rate limit
- put same host pages into same queue
- different priority for different sites - multiple queues
- normalization/canonicalization
- directed graph
- each URL: last visited time, score, fingerprint
- Use Bloom filters to remove duplicates
Re-crawling
- predict which websites are most likely to have frequent update, put those into the fetchers’ priority queue.
How to handle realtime news?
- each url: next visited time based on its score and how frequently it changes
- if page(links, content) is (mostly) not changed, increase its next visit time(cut+2t) otherwise decrease its next visit time
- begin with a seed set
- use a simple fingerprint such as a checksum
- the frontier
- normalized URL
DNS resolver
Locality
- Put data centers in different regions - machines in asian to crawl asian web sites
To crawl price histories of products
signals:
- previous price history changes
- how many reviews they have
- To detect new products: provide api so client can add or manually crawl new added pages.
Design an in-memory search engine- directed graph
- each URL: last visited time, score, fingerprint
- Use Bloom filters to remove duplicates
Re-crawling
- predict which websites are most likely to have frequent update, put those into the fetchers’ priority queue.
How to handle realtime news?
- each url: next visited time based on its score and how frequently it changes
- if page(links, content) is (mostly) not changed, increase its next visit time(cut+2t) otherwise decrease its next visit time
- begin with a seed set
- use a simple fingerprint such as a checksum
- the frontier
- normalized URL
DNS resolver
Locality
- Put data centers in different regions - machines in asian to crawl asian web sites
To crawl price histories of products
signals:
- previous price history changes
- how many reviews they have
- To detect new products: provide api so client can add or manually crawl new added pages.
How to index and store in memory
How to support free text queries, phrase queries
Map<String, List<Document>>
List<Document> is sorted
Document: docId, List<Long> positionIds
List<Long> is sorted
How to save to files
How to merge small files into big files
-- When save to file, make it sorted by word
-- Use merge sort to merge multiple fields
How to make it scalable - how solr cloud works
Auto completion in search
- single node
- Trie, Topk
Design Hit Counter - how to count number of requests in last second, minute and hour - link1,
Generate Game Map
- brute force, randomly generate one, check whether it can be solved in limit time by machine
- different difficulty level
Need update score realtime?
- yes, for this user's operation, when score is small
- no, for others' operation, when score is big
Rank - realtime?
- yes, when user is ranked in X(1000),
- no, if user ranks is below Y(1M)
Average score
- rank: use sorted tree - sorted by score, node splitted by score range
- table: userid, score
- sharding
- append, not update existing data
- separate score change to different types: real time vs batchable
- batch score change
Search nearby places
- GeoHash
Design Slack
Design Chat app like messenger, what's app
https://www.youtube.com/watch?v=zKPNUMkwOJE&t=2s
Websockets
ServerA forward message to ServerB which forwards to clientB
How to manage/detect friends status - presence
- reduce message, avoid O(n^2)
- Each user subscribes to its subscription list in server
- When one user state's changed, it uses pub/sub to update all related users's subscription list in server side
- Server pushes friend status to each user in some fixed interval - if there is change (batch)
How to store messages
Typing indicators
- Only send it to users who is currently interacting with this user/group
Message status: delivered, seen
- url dedup: use bloom filter
Detect duplicate documents in billions of urls
- back-of-the-envelope calculations
- (30 bytes for url + int/long(4 or 8 bytes)) * 10^9(~1g) ~ 34g
- A1: Hash and split into multiple files - slow (even with multiple threads) as a lot of IOs
- A2: Parallelize in multiple machines - like map-reduce
Design log collection and analysis system
- Auxiliary service, should not affect the existing service (Monitor system memory and cpu, adjust the push rate accordingly)
addToCart,removeFromCart,changeQuantity
- monitor
- abandoned cart
guest cart
- cookie
- merged if user login later
- check items availability at some point
- call other services - stock service(price, availability), metadata service, images(cdn)
ecommerce - amazon
- nosql: wide column for product table
- concurrency for order: optimistic, pessimistic
- analytics
- abandoned cart, user behavior(click,view,add/remove from cart)
products
checkout
Payment
- two phrases: Authorization, Capture
shipping
customer service
Design rate limiter
- Separate from application
- warn/notify user before user reaches 90% limit
Algorithms:
- Use cases: different phrases of the activity: before, available, sold out
- cache boolean available instead of the count
- Principle: fair(fifo) - but no need to 100% guarantee
Two types of queues
- one queue for each on-sale hot product, only keep x (count *1.x) requests, reject directly if more than it (ask them to retry after x mins)
- handled by one single server which reads from queue
- avoid distributed problems
- asynchronous processing
Cache activity page
- protect order page by adding a server side generated random number
- server side will generate and update a non-cached a js including activity info and the random number for the order page, the js is not cached in client side
How to send email notification, handle delivery
- asynchronous, put them into a queue
Design train ticket booking - Chunyun
Protect against from hackers
- CAPTCHA
- filter based on ipAddress, acountId
- Prevent abuse: cheating
Counter
- 1. Use count table
- 2. Use Redis
Hierarchical Data
- id, parentid
Design the data structure for large social network
Design system to store/read images
Expire mp3 in cdn and generate new one after x min
pre-load
Playlist Shuffle
- Fisher-Yates shuffle
- a good, uniformly distributed mix of all the tracks, no burst
Design key-value Database(lookup service)
Design APIs for add/update/query
CA or CP?
- List main components first (meltable, sstable, index, bloom filter, WAL log)
- membership and failure detection(gossip)
- Partition (Virtual nodes, consistent hashing)
- Replication(Versioning)
- handling temporary failures
- read repair and anti-entropy using Merkle tree
- Sparse index file and loaded into memory
- compress block
Write ahead (redo) log
- Global(Local) secondary index
- Conflict resolution
- Request coordinator
- Smart client can send requests to right replica
- Cache: row cache, key cache
Merge and compaction
Advantages over B-tress
- turn random writes into sequential writes
Downside of LSM tree
- compaction will interfere with the performance (not consistency)
- more storage
- key may appear in multiple sstable,
- more storage during compaction
Design column database
How to update some fields
Design Delayed Job Scheduler
- single server or distributed
- generic or for specific tasks
- Java Delay Queue
- wheelTimer (Netty)
- qurtz
Top K Frequent Elements in Recent X mins
- data structure: hashmap + linkedlist
system design:
- approximate
- batch, update every x seconds
- 分阶段统计, bucket
- sample
- different intervals for different cache(hour, daily)
- Analyze the requirements: QPS, SLA
- Autoscale, predicative scale based on estimated popularity of concert
- queuing and prioritizing
How to Design a Trending Algorithm - TODO
- offline pipelines
- cache, no need realtime
- candidates: hashtag
- signal: influencer, location, personalization
Make single-server datastore to peer-to-peer, linearly scalable, clustered systems
Dynomite
Design distributed priority queue service + Delayed queue
Distributed delay queues based on Dynomite + Redis
A Sorted Set containing queued elements by score.
A Hash set that contains message payload, with key as message ID.
A Sorted Set containing messages consumed by client but yet to be acknowledged. Un-ack set.
Design distributed file system
- master for meta data: where the chunk stores
- get file chunk location from master, read directly form slave
- replication, checksum
Image conversion service
- queue, asynchronously
System Design: Learning from Existing Products
Pinterest Home Feed
- best-first rather than newest-first
- separation of available, but unseen, content and content that’s already been presented
- fan out write pins to followers
- batch write
standby HBase cluster
- speculative execution
- make another call to the standby cluster if the first call to primary cluster fails or doesn’t return within certain time
- randomly forward x percent of calls to warm up it
smart feed worker
- score/store pins: quality and meaning to users
- repins by followers, related pins, interest Pins
- 3 priority queues(hbase tables) for each user, use key-based sorting of HBase: userid, score, pin
Smart feed content generator
- pins selected are removed from pool(hbase table)
Smart feed service
materialized feed
discover interests - Pinterest
- n-grams
- verify with search queries, public domain ontologies like Wikipedia titles
- blacklist, stop words
- implicit and explicit signals from users
related interests
- co-occurrence relationship for interests
search query
- user's demographic stats
- store and use previous queries
- adjacent queries in the same search session
- clicks afert submit query
Twitter
- users,tweets,be-followed,following
- persistent connection between client and server
Add a twitter
- Write it to the queue, return to client
- in background, save to db, push to (active) follower's queue
Cache aggressively
Vector Cache
- ids(user, tweet)
- user's followers(id)
Row Cache
- tweet
Fragment Cache
Page Cache
- separated and put into a different machine
Home Timeline - link
user's timeline vs home timeline
- precomputed and cached in redis for active users
Mixed Pull+Push
- local decisions about each producer/consumer pair
- how often producer adds a event, how ofter consumer views the event
- celebrity twitter - Pull
- normal user twitter - Push
Flock maintains the follower and followings lists.
Facebook
Separate data
Recent Activity - hot
- changes frequently, cache is frequently invalidated
- small, fast to regenerate them
Non-Recent Activity - cold
- a lot of data, slow to generate
- but don't change, cache will not be invalidated
Photo storage
- use cdn popular images
- use Haystack for other images - long tail
NFS photo infrastructure - old version
- huge metadata, most are not used(permission)
- use cdn to store images
- one(or more) to translate the filename into inode number, another to read the inode from disk, and a final one to read the file itself.
- need keep all inodes in memeory
- CDN good for hot data, but not so for cold data
long tail data
- requests for less popular (often older) content
Haystack - link
Haystack Object Store
- a log structured (append-only) object store containing needles representing the stored objects
- eliminates the metadata overhead by aggregating hundreds of thousands of images in a single haystack store file
- at most one disk operation per read, keep all metadata in main memory
- haystack store file
- index - needle's location, not critical, can be rebuilt, written asynchronously
needle is identified by Offset, Key, Alternate Key, Cookie
- Don't allow overwrite existing needle, instead: add a new version and its index
- needles with tuple: duplicate Key, Alternate Key, Cookie, the largest offset is the most recent one
Read - Pass needle offset, key, alternate key, cookie and the data size
Delete - set a deleted bit in the flags
- Fault-tolerant: replicates
Photo Store Server - http layer
- keeps a minimal in-memory index
- Google sparse hash data structure
Compaction
- reclaim the space
- copy needles while skipping any duplicate or deleted entries
Haystack Cache
- insulation if upstream CDN nodes fail and
Timeline - your story
News Feed - Multifeed
- multi-fetch and aggregate stories at read time
- aggregator(staeless) and leafs
- aggregator servers sends request to all leaf servers and ranks the results.
- all data in leafs is in memory (memcached)
- fetch recent activity from all your friends
- gather and Group into stories
- rank stories by relevance
- more flexible, manageable
- fan-out reads can be bounded. writes, often cannot
- SSD
- others's story that related to you
- rank edges(stories) by importance(relevance) - link
- content score: ∑e = ue we de, wherein ∑e is the sum of the edge's rank, ue is the affinity score with the user who created the edge, we is the weight for the content type, and de is a time decay factor
- a friend's affinity score: ∑i = li ni wi, wherein ∑i is the sum of the interactions with that friend, li is the time since your last interaction (this would need to be weighted so that 1 day > 30 days), ni is the number of interacts, and wi is the weight of those interactions
- Activity(id, user_id, source_id, activity_type, edge_rank, parent_id, parent_type, data, time)
- timeline - user's story
- newsfeed
connections and activities
"Push" Model, or Fan-out-on-write
- a lot of write, only push to active users for non-celebrity users
- use write-optimized data store such as Cassandra, HBase, or BigTable
"Pull" Model, or Fan-out-on-load
- less data, less computation
- materialized what user already viewed into a table, only pull new data
- have a fallback mechanism if fails to pull - show old materialized data
Combination of push and pull
- make decision locally on per consumer/producer basis
- a frequent producer of events may overshadow events from less frequent producers
Selective Fanout Based On Consumer
- only fan-out to active/valuable users
Selective Fanout Based On Producer
- don't fan-out for high profile users
Pull for new users
- because nothing pushed to the user
- when there is no enough data, pull from following
Make schema changes is expensive in traditional db
- such as add/remove indexes
- Users don't know what they don't know.
- All content is not created equal.
Reddit
- Treat nonlogged user as second class citizens
- Return cached content to them
- Put a limit on everything
- Provide timeout
- Expire data. Lock out old threads and create a fully rendered page and cache it.
Red Envelop
- store count, balance into redis
- use redis
- decr count, CAS to decrease balance
- ttl
Uber
Driver - Long connection
- matches drivers and riders, the supply and demand
Maps/ETA (estimated time of arrival)
Nutch2
- plugins, extensible
- fetching pages, filtering and normalizing URLs and parsing responses
Etsy - link
$choose_connection = mt_rand() < $affinity;
Pruning Same/similiar message
combine similar stories into rollups
- group similar storeis
Cache
- seperate global and unique to the person
Cache Warming - gearman
- proactively
- TTL Caching
Lazy Below the Fold
JD
数据闭环,异构,聚合
EFK - Log collection/visualization
logstash/fleuent -> kafka -> Elasticsearch -> Kibana
- best-first rather than newest-first
- separation of available, but unseen, content and content that’s already been presented
- fan out write pins to followers
- batch write
standby HBase cluster
- speculative execution
- make another call to the standby cluster if the first call to primary cluster fails or doesn’t return within certain time
- randomly forward x percent of calls to warm up it
smart feed worker
- score/store pins: quality and meaning to users
- repins by followers, related pins, interest Pins
- 3 priority queues(hbase tables) for each user, use key-based sorting of HBase: userid, score, pin
Smart feed content generator
- pins selected are removed from pool(hbase table)
Smart feed service
materialized feed
discover interests - Pinterest
- n-grams
- verify with search queries, public domain ontologies like Wikipedia titles
- blacklist, stop words
- implicit and explicit signals from users
related interests
- co-occurrence relationship for interests
search query
- user's demographic stats
- store and use previous queries
- adjacent queries in the same search session
- clicks afert submit query
- users,tweets,be-followed,following
- persistent connection between client and server
Add a twitter
- Write it to the queue, return to client
- in background, save to db, push to (active) follower's queue
Cache aggressively
Vector Cache
- ids(user, tweet)
- user's followers(id)
Row Cache
- tweet
Fragment Cache
Page Cache
- separated and put into a different machine
Home Timeline - link
user's timeline vs home timeline
- precomputed and cached in redis for active users
Mixed Pull+Push
- local decisions about each producer/consumer pair
- how often producer adds a event, how ofter consumer views the event
- celebrity twitter - Pull
- normal user twitter - Push
Flock maintains the follower and followings lists.
Search
- tweets are stored in memory Lucene
- rerank based on social proof, the number of retweets, favorites, and replies.
- so every time, a tweet is retweeted or etc, no need update
Lucene
Separate data
Recent Activity - hot
- changes frequently, cache is frequently invalidated
- small, fast to regenerate them
Non-Recent Activity - cold
- a lot of data, slow to generate
- but don't change, cache will not be invalidated
Photo storage
- use cdn popular images
- use Haystack for other images - long tail
NFS photo infrastructure - old version
- huge metadata, most are not used(permission)
- use cdn to store images
- one(or more) to translate the filename into inode number, another to read the inode from disk, and a final one to read the file itself.
- need keep all inodes in memeory
- CDN good for hot data, but not so for cold data
long tail data
- requests for less popular (often older) content
Haystack - link
Haystack Object Store
- a log structured (append-only) object store containing needles representing the stored objects
- eliminates the metadata overhead by aggregating hundreds of thousands of images in a single haystack store file
- at most one disk operation per read, keep all metadata in main memory
- haystack store file
- index - needle's location, not critical, can be rebuilt, written asynchronously
needle is identified by Offset, Key, Alternate Key, Cookie
- Don't allow overwrite existing needle, instead: add a new version and its index
- needles with tuple: duplicate Key, Alternate Key, Cookie, the largest offset is the most recent one
Read - Pass needle offset, key, alternate key, cookie and the data size
Delete - set a deleted bit in the flags
- Fault-tolerant: replicates
Photo Store Server - http layer
- keeps a minimal in-memory index
- Google sparse hash data structure
Compaction
- reclaim the space
- copy needles while skipping any duplicate or deleted entries
Haystack Cache
- insulation if upstream CDN nodes fail and
News Feed - Multifeed
- multi-fetch and aggregate stories at read time
- aggregator(staeless) and leafs
- aggregator servers sends request to all leaf servers and ranks the results.
- all data in leafs is in memory (memcached)
- fetch recent activity from all your friends
- gather and Group into stories
- rank stories by relevance
- more flexible, manageable
- fan-out reads can be bounded. writes, often cannot
- SSD
- others's story that related to you
- rank edges(stories) by importance(relevance) - link
- content score: ∑e = ue we de, wherein ∑e is the sum of the edge's rank, ue is the affinity score with the user who created the edge, we is the weight for the content type, and de is a time decay factor
- a friend's affinity score: ∑i = li ni wi, wherein ∑i is the sum of the interactions with that friend, li is the time since your last interaction (this would need to be weighted so that 1 day > 30 days), ni is the number of interacts, and wi is the weight of those interactions
- Activity(id, user_id, source_id, activity_type, edge_rank, parent_id, parent_type, data, time)
- timeline - user's story
- newsfeed
connections and activities
"Push" Model, or Fan-out-on-write
- a lot of write, only push to active users for non-celebrity users
- use write-optimized data store such as Cassandra, HBase, or BigTable
"Pull" Model, or Fan-out-on-load
- less data, less computation
- materialized what user already viewed into a table, only pull new data
- have a fallback mechanism if fails to pull - show old materialized data
Combination of push and pull
- make decision locally on per consumer/producer basis
- a frequent producer of events may overshadow events from less frequent producers
Selective Fanout Based On Consumer
- only fan-out to active/valuable users
Selective Fanout Based On Producer
- don't fan-out for high profile users
Pull for new users
- because nothing pushed to the user
- when there is no enough data, pull from following
Make schema changes is expensive in traditional db
- such as add/remove indexes
- Users don't know what they don't know.
- All content is not created equal.
- Treat nonlogged user as second class citizens
- Return cached content to them
- Put a limit on everything
- Provide timeout
- Expire data. Lock out old threads and create a fully rendered page and cache it.
Red Envelop
- store count, balance into redis
- use redis
- decr count, CAS to decrease balance
- ttl
Uber
Driver - Long connection
- matches drivers and riders, the supply and demand
Maps/ETA (estimated time of arrival)
Nutch2
- plugins, extensible
- fetching pages, filtering and normalizing URLs and parsing responses
Etsy - link
$choose_connection = mt_rand() < $affinity;
Pruning Same/similiar message
combine similar stories into rollups
- group similar storeis
Cache
- seperate global and unique to the person
Cache Warming - gearman
- proactively
- TTL Caching
Lazy Below the Fold
JD
数据闭环,异构,聚合
EFK - Log collection/visualization
logstash/fleuent -> kafka -> Elasticsearch -> Kibana
System Design - Summary
Identify the user cases, requirements, constraints, scope
- ask a lot of questions
- current requirements and requirements in near future
- talk about near-future requirements and design for it.
- who is the target audience? how it will be used?
- which features would be Pri-0 versus Pri-1?
- what are key and high traffic operations?
- how accurate it requires?
- max requests/day, QPS, storage size, latency, availability
- high level design and architecture
- main user cases/specific APIs for each component
Try multiple approaches
- high level: API, application layer, data layer then drill down
- sketch up the major components and their relationships
- draw a simple diagram
Identify bottlenecks/limitations and how to tackle them
Trade-offs
Performance, Consistency, Availability, Safety
Compare with other approaches
- performance characteristics of proposed architecture
Relax Temporal Constraints
- Alleviate temporal constraints in your system whenever possible
Keys to improve performance
- cache, partition, replicate, index
Differentiated service classes
- Different services/data need different guarantees/SLA
- ask a lot of questions
- current requirements and requirements in near future
- talk about near-future requirements and design for it.
- who is the target audience? how it will be used?
- which features would be Pri-0 versus Pri-1?
- what are key and high traffic operations?
- how accurate it requires?
- max requests/day, QPS, storage size, latency, availability
- high level design and architecture
- main user cases/specific APIs for each component
Try multiple approaches
- high level: API, application layer, data layer then drill down
- sketch up the major components and their relationships
- draw a simple diagram
Identify bottlenecks/limitations and how to tackle them
Trade-offs
Performance, Consistency, Availability, Safety
Compare with other approaches
- performance characteristics of proposed architecture
Relax Temporal Constraints
- Alleviate temporal constraints in your system whenever possible
Keys to improve performance
- cache, partition, replicate, index
Differentiated service classes
- Different services/data need different guarantees/SLA
Separation of concerns/things
- separate user-facing components from non user-facing components
- critical vs non-critical services
- different db/apps into different servers
- differentiation of different components
Separate frontend and backend
- always writable in frontend
- backend can write to queue, and asynchronously do business logic
Functional partition services
- understand who are priority customers
Services
- coarse granularity of services
- establish clear relationships between the service
- isolate problems, scale independently
- solve problems independently
- critical vs non-critical services
- different db/apps into different servers
- differentiation of different components
Separate frontend and backend
- always writable in frontend
- backend can write to queue, and asynchronously do business logic
Functional partition services
- understand who are priority customers
- coarse granularity of services
- establish clear relationships between the service
- isolate problems, scale independently
- solve problems independently
Restful Service
- cache friendly
- good for public api
- put: idempotent
- put: idempotent
Use standard timestamps - UTC only
Use downcased and dash-separated path names, downcased, underscore separators for attribute names
- actions/:action
Avoid auto-I=increment id; use UUID
Use Plural Noun
put response entity into a namespace(data), able to extend/add counts, links
flexible - client can choose which fields/sub resources to return
pagination - Define a Maximum
Don’t use integers as timestamps
Etag + If-None-Match conditional GET
Avoid auto-I=increment id; use UUID
Use Plural Noun
put response entity into a namespace(data), able to extend/add counts, links
flexible - client can choose which fields/sub resources to return
pagination - Define a Maximum
Don’t use integers as timestamps
Etag + If-None-Match conditional GET
RPC
- Protobuf, Thrift, Apache Avro
- Efficency
- But hard to debug and not flexible
Services features
- read heavy (improve latency) write heavy(save space, async,queue) or both
- user facing or not?
- delay acceptable, (write feeds)
- QPS
- SLA, performance requirement
Partitioning
- each node may be the leader for some partitions, and a follower for other partitions.
partitioning by hash of key
- lose the ability to do efficient range queries: rang query has to be sent to all partitions
- (user_id, update_timestamp); (sensor, update_timestamp)
- can perform an efficient range query if specify fixed value for the first key
- read heavy (improve latency) write heavy(save space, async,queue) or both
- user facing or not?
- delay acceptable, (write feeds)
- QPS
- SLA, performance requirement
Partitioning
- each node may be the leader for some partitions, and a follower for other partitions.
partitioning by hash of key
- lose the ability to do efficient range queries: rang query has to be sent to all partitions
- (user_id, update_timestamp); (sensor, update_timestamp)
- can perform an efficient range query if specify fixed value for the first key
CAP theorem
Consistency - all of the nodes see the same data at the same time.
Availability - any available node can serve client requests even when other nodes fail.
Partition tolerance
- system can operate even in the face of network failures where communication between nodes is impossible.
- happens when some nodes in the system cannot reach other nodes, but all can be reached by clients.
CP - HBase, Bigtable, MongoDB, RedisAP - Dynamdb, Cassandra, Voldemort, Riak, SimpleDB
CA - RMDBMs, Zookeeper
Consistency - link
Eventual consistency
Causal consistency
Monotonic read consistency - desired
- if a process has seen a particular value for the object, any subsequent accesses will never return any previous values.
- always read to same replica
Monotonic write consistency
- guarantee to serialize the writes by the same process
Causal consistency
RYW (Read-Your-Writes) consistency - desired
- read it from the leader
- read user own data from leader, read others data from replicate
- or always read/write to same replica
- or always read/write to same replica
Session consistency
- guarantee read-your-writes consistency in same sessionMonotonic read consistency - desired
- if a process has seen a particular value for the object, any subsequent accesses will never return any previous values.
- always read to same replica
Monotonic write consistency
- guarantee to serialize the writes by the same process
- vector clock + RWN
Use write version - to implement optimistic lock, or consistency
Stickiness of clients
R+W>N
- N: number of replicas
- W: number of replicas that need to acknowledge update
- R: number of replicas that are read
- Normally: N=3, W=2, R=2
- Optimize for read: R=1, W=N
- Optimize for write: W=1, R=N
Use write version - to implement optimistic lock, or consistency
Stickiness of clients
R+W>N
- N: number of replicas
- W: number of replicas that need to acknowledge update
- R: number of replicas that are read
- Normally: N=3, W=2, R=2
- Optimize for read: R=1, W=N
- Optimize for write: W=1, R=N
BASE(Basically Available, Soft State, and Eventually Consistent)
Replication
- Scale reads not writes
- Statement-based
- Write-ahead log (WAL)
- Logical log - MySQL binlog
Master-Master - lose single-source-of-truth
Single Master/Multiple Slaves
Master-Master - lose single-source-of-truth
Single Master/Multiple Slaves
Fine-Grained Dynamic Partitioning
Speeds Failure Recovery
- Many machines each recover one or a few partition
Selective Replication
- find heavily used items and make more replicas
- can be static or dynamic
Sharding
Speeds Failure Recovery
- Many machines each recover one or a few partition
Selective Replication
- find heavily used items and make more replicas
- can be static or dynamic
Sharding
Redundancy
- Kick off the same computation more than once and return the one that finishes fastest.
Design for Fault Tolerance and Graceful Failure
Graceful Degradation - reduced functionality
- degradable service
- better to give users limited functionality than an error page
- still do something reasonable even if not all is right
- read only from local cache, only from distributed cache, only return fixed data
- rate limit, throttles
Fail as Early/fast as Possible - circuit breaker
- Kick off the same computation more than once and return the one that finishes fastest.
- Use multiple vendors for same service
Throttling
- rate-limiting, remove slow servers
- Always put a limit on everything
How to reduce latency - link
Differentiated service classes
- prioritized request queues in servers
Manage expensive background activities
- defer until load is lower
remove capacity under load to improve latency
Use right image/video types
Decrease processing time
- Collocation(locality)
- Caching, Pooling
- Parallelization
- Partitioning
Cross request adaptation - balance load across set of servers
Within request adaptation
- Canary Requests
- Backup Requests (w/ Cross-Server Cancellation)
– send request to first replica
– wait 2 ms, and send to second replica
– servers cancel request on other replica when starting read
Tainted Partial Results
- mark such results as tainted in caches
Use Timeouts pattern
- default Jersey uses HttpURLConnection, its socket timeout of 0 millis, meaning that the timeout is infinite.
- tryLock, lock with timeout
Use Connection pooling
How to handle failures- rate-limiting, remove slow servers
- Always put a limit on everything
How to reduce latency - link
Differentiated service classes
- prioritized request queues in servers
Manage expensive background activities
- defer until load is lower
remove capacity under load to improve latency
Use right image/video types
Decrease processing time
- Collocation(locality)
- Caching, Pooling
- Parallelization
- Partitioning
Cross request adaptation - balance load across set of servers
Within request adaptation
- Canary Requests
- Backup Requests (w/ Cross-Server Cancellation)
– send request to first replica
– wait 2 ms, and send to second replica
– servers cancel request on other replica when starting read
Tainted Partial Results
- mark such results as tainted in caches
Use Timeouts pattern
- default Jersey uses HttpURLConnection, its socket timeout of 0 millis, meaning that the timeout is infinite.
- tryLock, lock with timeout
Use Connection pooling
Design for Fault Tolerance and Graceful Failure
Graceful Degradation - reduced functionality
- degradable service
- better to give users limited functionality than an error page
- still do something reasonable even if not all is right
- read only from local cache, only from distributed cache, only return fixed data
- rate limit, throttles
Fail as Early/fast as Possible - circuit breaker
Avoid single point of failure
- Strive for active/active
Avoid hotspot
- know your limit, and do throttle
- reject new request
- clear request queue
Lazy purge - actively purge
Approximate correctness
- do a transaction every once in awhile instead of every time
- do a transaction every once in awhile instead of every time
Laziness
- Don't do work unless it's really needed
No computation at all
Pre-computation and cache
Pre-computation and cache
DNS
Route 53 - latency-based routing
geoDNS - based on location
Browser
- Use multiple domains
Load Balancer
- SSL termination/offloading (AWS ELB)
- SSL farm
- scale lb using dns otr layered lbs
Cache aggressively
- scale lb using dns otr layered lbs
Cache aggressively
- static files, not-change-often API response
Layered Cache
Application Cache
- In-Process Caching(ehcahce)
- Distributed Caching(redis)
- Vector/row/fragment/page cache
- spring cache sync=true
Reverse proxy: NginxBrowser cache: cache header(filter, or httpd config)
- Prevent 雪崩
- separate global and unique to the person
Cache Warming - gearman
- proactively
- TTL(timeout-based) Caching
Write-through cache - link
- directs write I/O onto cache and through to underlying permanent storage
- write is slower, good for apps that writes and then re-reads data frequently
Write-around cache
- write I/O is written directly to permanent storage, bypassing the cache
Write-back cache
- write I/O is directed to cache, backed up to permanent storage only at specified intervals or under certain conditions
- good for write-intensive, non-critical app, may lose data if cache dies
- time shifting, rate limiting, conflation
Cache Aside
- read from cache, if missed, read from db then put it into cache
- update to db, and invalidate cache
Write-through cache - link
- directs write I/O onto cache and through to underlying permanent storage
- write is slower, good for apps that writes and then re-reads data frequently
Write-around cache
- write I/O is written directly to permanent storage, bypassing the cache
Write-back cache
- write I/O is directed to cache, backed up to permanent storage only at specified intervals or under certain conditions
- good for write-intensive, non-critical app, may lose data if cache dies
- time shifting, rate limiting, conflation
Cache Aside
- read from cache, if missed, read from db then put it into cache
- update to db, and invalidate cache
Queue - kafka, redis, MQ
Publish/Subscribe - Kafka, MQ
Asynchrony - asynchronous processing
- order placed successfully TO order received successfully
- queue, fire and forget calls
- avoid blocking calls, reduce contention
Retry
Feature flags
- Queue-based Load Leveling Pattern
- Concurrent request converted to sequential request
- Evening out traffic spikes, overdraft protection
- Isolating failures and self-healing
- Enabling asynchronous processing
- Decoupling
Partial message ordering
exactly-once
- one approach: at-least-once + idempotent
Multiple Queue
- different priorities, put same host into same queue - to be polite
- Concurrent request converted to sequential request
- Evening out traffic spikes, overdraft protection
- Isolating failures and self-healing
- Enabling asynchronous processing
- Decoupling
Partial message ordering
exactly-once
- one approach: at-least-once + idempotent
Multiple Queue
- different priorities, put same host into same queue - to be polite
Priority Queue pattern
- Use redis
-- or multiple queue with different priorities
Asynchrony - asynchronous processing
- order placed successfully TO order received successfully
- queue, fire and forget calls
- avoid blocking calls, reduce contention
Batch operations
Statelessness
- Share Nothing
Make API Retryable, Idempotent and Killable
- selective retry - only for transient errors that may succeed on a subsequent attempt
- don't retry permanent(unrecoverable) errors
- limit the number of retries and time spent
- use exponential backoff with random
- handle overload-related errors differently from other errors
RetryTemplate, FixedBackOffPolicy, setMaxAttempts, HttpClient
Only retry in outermost service
- don't retry permanent(unrecoverable) errors
- limit the number of retries and time spent
- use exponential backoff with random
- handle overload-related errors differently from other errors
RetryTemplate, FixedBackOffPolicy, setMaxAttempts, HttpClient
Only retry in outermost service
Parallelization
Accurate vs approximately
Availability and Reliability
- how things can fail
Learn and work on an actual system
- focus on the architecture and the tradeoffs behind each decision
- do back-of-the-envelope calculations for something you’re building
Availability and Reliability
- how things can fail
Learn and work on an actual system
- focus on the architecture and the tradeoffs behind each decision
- do back-of-the-envelope calculations for something you’re building
Feature flags
- control flag to upstream(in nginx)
Design to Clone Things (X Axis)
- clone services + load balancers
Design to Split Different Things (Y Axis)
- Separate sets of data, can scale them differently.
- Separation of distinct and different functions and data
Design to Split Similar Things (Z Axis): sharding and podding
Design to Clone Things (X Axis)
- clone services + load balancers
Design to Split Different Things (Y Axis)
- Separate sets of data, can scale them differently.
- Separation of distinct and different functions and data
Design to Split Similar Things (Z Axis): sharding and podding
Design for Rollback
Design to Be Disabled
Design to Be Monitored
- Nagios, Ganglia, Graphite, statsd
Design to Be Disabled
Design to Be Monitored
- Nagios, Ganglia, Graphite, statsd
Session
Memory-based session state with Load balancer affinity(AWS ELB)
- Cookie learning vs Cookie injection
- Cookie learning vs Cookie injection
Persist session state to a DB
Data compression - gzip header
Polyglot MicroServices
- Single-purpose
- Modular and independent
- Don't share a persistence layer, each service has its own database
- Example: Cassandra, Solr
- Single-purpose
- Modular and independent
- Don't share a persistence layer, each service has its own database
Categorize users
- less frequency ops for inactive users
- return cached content(ads) for non-logged in user
Explore locality - partition
- temporal, location
Explore locality - partition
- temporal, location
Data Store
- Choose the right database for the right service
- Know what queries are needed currently or in near-future
Read to write ratio
- it may be too large/cost to keep all in memory
- is it time series?
- row size
- how long to keep the data, policy to delete/archive old data
Hot/Cold Data
- Hot data to memory, cold data to ssd or disk(Glacier)
- Store them in different system
Separate index and content
- index for search, no need to store everything (solr).
- Write to master, read from replica
- First write to queue, then sync to master
- Use different data stores
- Know what queries are needed currently or in near-future
Read to write ratio
- read/write heavy or both
- how frequently we write/read
- how frequently we write/read
- use different db for read/write
- How much data- it may be too large/cost to keep all in memory
- is it time series?
- row size
- how long to keep the data, policy to delete/archive old data
Hot/Cold Data
- Hot data to memory, cold data to ssd or disk(Glacier)
- Store them in different system
Separate index and content
- index for search, no need to store everything (solr).
- store content in KV db
Separate read/write- Write to master, read from replica
- First write to queue, then sync to master
- Use different data stores
Store raw data to S3 or hdfs
Store Data that matters to datastore
Index
- index everything want to query on, only query on indexes
Denormalize the data
Split up large tables
Store Data that matters to datastore
Index
- index everything want to query on, only query on indexes
Denormalize the data
Split up large tables
SQL vs NOSQL
Key-Value - Riak, Dynamodb
Document-oriented - Couchbase, MongoDB
Column oriented
- store data by columns
- query by key or by key range
- BigTable, HBase and Cassandra
MySQL
Document-oriented - Couchbase, MongoDB
Column oriented
- store data by columns
- query by key or by key range
- BigTable, HBase and Cassandra
MySQL
- more read than writes
master/slave
- writes goes to master
- Related or not
- Need ACID or not
Key-value
Column-oriented
Document-oriented
Column-oriented
Document-oriented
Use multiple data centers
Break incompatible schema change into multiple database and application deployments.
- maintain a set of ready-to-use, opened TCP connections to the main cluster service
- serve nearby user requests and forward them to the main cluster service using the ready-to-use, established connections
GeoHash - link
- divide the world into a grid of 32 cells
- each cell can be further divided into another 32 cells, which can be divided into another 32 cells, and so on.
- the longer, the more accurate
- the longer the shared prefix, the closer they are
Optimistic vs Pessimistic lock
- separate big fields into different table: post/tweet body
- read by blocks, smaller rows => read more rows
- avoid joins, full table scan
PoPs servers - link- read by blocks, smaller rows => read more rows
- avoid joins, full table scan
- maintain a set of ready-to-use, opened TCP connections to the main cluster service
- serve nearby user requests and forward them to the main cluster service using the ready-to-use, established connections
GeoHash - link
- divide the world into a grid of 32 cells
- each cell can be further divided into another 32 cells, which can be divided into another 32 cells, and so on.
- the longer, the more accurate
- the longer the shared prefix, the closer they are
Prefer sequential write vs random write
Gated Launch
Jitter - Add some randomness
- avoid a thundering herd
Security - link
fail securely
least privilege
never trust any input!
Deployments/Zero downtime
- rolling deployments
Jitter - Add some randomness
- avoid a thundering herd
- Add Entropy Back into Your System
Security - link
fail securely
least privilege
never trust any input!
- rolling deployments
Autoscale
- not instantaneous
- can scale up or down
Valet Key Pattern - supported by S3
Command and Query Responsibility Segregation (CQRS) Pattern
Materialized View Pattern
Lambda Architecture - link
- all data is dispatched to both the batch layer and the speed layer
- batch layer: managing the master dataset (an immutable, append-only set of raw data), to pre-compute the batch views.
- serving layer indexes the batch views
- merging results from batch views and real-time views.
Option 1. Hadoop + Spark Streaming + Memory Storage + Columnar Storage
- write latency: 25 ms
Ecommerce
SPU - Standard Product Unit
SKU - Stock Keeping Unit
MVP - minimum viable product
Robustness Principle
Be conservative in what you send, be liberal in what you accept
Be conservative in what you do, be liberal in what you accept from others
Reactive programming
- data flows and the propagation of change
- when x changes in one location, things depend on the value of x are recalculated and updated in various other locations
CPU Bound Application
Caching precomputing values
Performing the computation in separate background job.
Most apps are IO Bound Application - db/web service calls
- all data is dispatched to both the batch layer and the speed layer
- batch layer: managing the master dataset (an immutable, append-only set of raw data), to pre-compute the batch views.
- serving layer indexes the batch views
- merging results from batch views and real-time views.
Option 1. Hadoop + Spark Streaming + Memory Storage + Columnar Storage
Metrics, Numbers, Estimation
Apache Httpd Server
- one connection, one process
- max cocurrent connections: ~4000
- yaws
HAProxy, nginx
- 20K concurrent connections
Web application server
- few thousand concurrent requests
6gb memory - 50K or 140K RPS (different bandwidth)
50gb memory - 150K or 250K with Redis clustering, throughput increases linearly as you increase the number of shards
Cassandra
- mean read latency: 13 ms- write latency: 25 ms
Kafka
- 200k messages/sec for writes and 3M messages/sec for reads
- Each broker can handle terabytes of messages
- 200k messages/sec for writes and 3M messages/sec for reads
- Each broker can handle terabytes of messages
Send 1M bytes over 1Gbps network 10ms
Read 1M sequentially from memory 0.25ms
Round trip within data center 0.5ms
Disk seek 8~10ms
Read 1MB sequentially from disk 20~25ms
Back-of-the-envelope Calculation
2^30 bytes ~~ 1GB
2^40 ~~ 1 TB
2^10 ~~ 1 KB
2^20 ~~ 1 MB
million -> 10^6
billion -> 10^9 ~ 2^30 bytes ~ 1GB
trillion -> 10^12 bytes~ 1 TB
Terms
QPS - Queries per second SLA - Service-level agreement
Resources
Subscribe to:
Posts (Atom)