资源共享吧系统设计与实践课件中七剑客

1、系统设计中七剑客大纲同步 网络 数据库分布式性能 估算面向对象案例 社交网站信息流 日志统计-网络爬虫 电商产品页面IntroductionSystem design:1-3 rounds in interviewsFor new-grad: not required/simpleFor experienced: important to show your knowledge and thoughtful ideasKnowledge, Design, Communication!ConcurrencyThvs. ProcessConsumer and ProducerBlockingque

2、ueTracking:Synchronized, AsynchronizedNetworkVisit URLWhat happens after you typed a URL in your browser and pressed return key?DatabaseRelational DB vs. KV StoreSharding vs. ClusteringTinyURL:Store the map document:from shortlink code to full URL. The record/code: varchar(8)url: varchar(1000) creat

3、ed_at: timestampWe also need to store the reverse mapfrom URL back to code.Distribute SystemHow to scale Tiny URL service?Stateless frontend serversa load balancerSharded/replicated database (on shortlink code)Memcached to scaletrafficSpwrite loadLocally buffered event tracking + async flush to high

4、-throughput message queueUse a distributed unique ID generator (64-bit)PerformanceCache is KEY!EstimationHow many piano tuners are there in the entire world?Tiny URL: How much is total storage? URL Length 10 - 1000 chars.Total accumulated URL number 100 MNew URL registrations are on the order 100,00

5、0/day (1/ sec)Redirect requests are on the order of 100M/day (1000/sec)Design Pattern23 patterns: MVCSingleton Factory Iterator Decorator Facade案例News FeedsStats ServerWeb CrawlerAmazon Product PageNews feedDefine feedOrganizeaggregate dedup sortLevel 1.0Database Schema: User Friendship NewsGet News

6、feed: merge news Newsfeed vs NewsNewsIdAuthorIdContent12“Hehe”21“Lala”FriendshipIdSourceIdTargetId112221UserIdNameAge1Jason252Michael26Why bad?100+ friends1 Query -> Get friends list 1 Query ->SELECT news WHERE timestamp>AND sourceid IN friend list LIMIT 1000IN is slowEither Sequential scan

7、 or 100+ index queriesLevel 2.0Pull vs PushPull: Get news from each friend, merge them together. (NewsFeed generated when user request)Push: NewsFeed generated when news generated. (we have another table to store newsfeed, may cause duplicate news)Push:1 Query to select latest 1000 newsfeed. 100+ in

8、sert queries (Async)Disadvantage: News Delay.Level 3.0Popular star (Justin Bieber) Flowers 13M +Async Push may cause over 30 minutes (13M+ insertions, delay too long)Push + Pullfor popular star, dont push news to flowersfor every newsfeed request, merge non-popular user newsfeed (push) and popular u

9、sers newsfeed (pull)Level 4.0Push disadvantage: RealtimeStorage (Duplicate) EditGo back to PULL:Cache users latest (14 days) newsBroadcast multiple request to multiple servers (Shard by userId). Merge & sort newsfeedCache newsfeeds for this user with timestampClick Stats ServerHow are click stat

10、s stored?A poor candidate will suggest write-back to a data store on every clickA good candidate will suggest some form of aggregation tier that accepts clickstream data, aggregates it, and writes back a persistent data store periodicallyA great candidate will suggest a low-latency messaging system

11、to buffer the click data and transfer it to the aggregation tier.If daily, storing in hdfs and running map/reduce jobs to compute stats is a reasonable approachIf near real-time, the aggregation logic should compute statsCache Requirementa When a reqomes look it up in the cache and if it hits thenre

12、turn the response from here and do not pass the request to the systemb If the request is not found in the cache then pass it on to the systemc Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cachedDesign one cache su

13、ch that all operations can be done in O(1) lookup, delete and insert.Web CrawlerAmazon Product PageThe product page includes information such asa) product informationb) user informationc) recommended products (what do other customers buy after viewing this item, recommendations for you like this product, etc)ReferenceThe Log: What every software engineer should know about real-time da