九章精品求職直播課程之系統(tǒng)設(shè)計(jì)班課件url

1、一致性算法與短系統(tǒng)Consistent Hashing & Design Tiny Url課程版本 v5.1本節(jié)主講人 東邪/掃描關(guān)注獲取最新面試題及權(quán)威解答: ninechapter:知乎:官網(wǎng):法律責(zé)任和本由償社區(qū)用戶整理第1頁與，否則將九章的所有課程均受法律保護(hù)，不與損失一經(jīng)發(fā)現(xiàn)，將被法律責(zé)任和賠償法律責(zé)任本賠由社區(qū)用戶整理第2頁與，否則將今日課程大綱Consistent Hashing 簡(jiǎn)單的Consistent Hashing方法的回顧及缺陷分析 一個(gè)更優(yōu)的 Consistent Hashing 方法RepliaSQL 通常如何進(jìn)行備份NoSQL 通常如何進(jìn)行備份？系統(tǒng) De

2、sign Tiny Url設(shè)計(jì)一個(gè)短 4S 分析法 No Hire / Weak Hire / Hire / Strong Hire附錄（供大家自學(xué)）：當(dāng)你的時(shí)候法律責(zé)任和本由償社區(qū)用戶整理第3頁與，否則將一致性算法Consistent HashingHorizontal Sharding 的法律責(zé)任和本由償社區(qū)用戶整理第4頁與，否則將Consistent Hashing我們先來說說為什么要做 “一致性”Hash% n 的方法是一種最簡(jiǎn)單的 Hash 算法但是這種方法在 n 變成 n+1 的時(shí)候，每個(gè) key % n和 % (n+1) 結(jié)果基本上都不一樣所以這個(gè) Hash 算法可以稱之為：不一

3、致 hashWeb Server0 3 6 93 7 112 6 10DB0DB1DB2DB0DB1DB2DB3法律責(zé)任本賠由社區(qū)用戶整理第5頁與，否則將Consistent Hashing一個(gè)簡(jiǎn)單的一致性Hash算法將 key 模一個(gè)很大的數(shù)，比如 360將 360 分配給 n 臺(tái)，每個(gè)負(fù)責(zé)一段區(qū)間Web Server 上區(qū)間分配信息為一張表新加一臺(tái)的時(shí)候，在表中選擇一個(gè)位置，勻走相鄰兩臺(tái)的一部分?jǐn)?shù)據(jù)比如 n 從 2 變化到 3，只有 1/3 的數(shù)據(jù)移動(dòng)DB1: 240359DB0: 0119DB1: 180359DB0: 0179DB2: 120239法律責(zé)任本賠由社區(qū)用戶整理第6頁與，否

4、則將3臺(tái)變4臺(tái)的例子法律責(zé)任本賠由社區(qū)用戶整理第7頁與，否則將Consistent Hashing每一次加入一臺(tái)新只有1臺(tái)或者2臺(tái)數(shù)據(jù)庫的數(shù)據(jù)會(huì)被遷移 因?yàn)橐紦?jù)環(huán)上的一段區(qū)間這是一個(gè)比較簡(jiǎn)單的 Consistent Hashing 的算法提問：這種簡(jiǎn)單方法中，有什么缺陷？法律責(zé)任本賠由社區(qū)用戶整理第8頁與，否則將缺陷1 數(shù)據(jù)分布不均勻因?yàn)樗惴ㄊ恰皩?shù)據(jù)最多的相鄰兩臺(tái)均勻分為三臺(tái)”比如，3臺(tái)變4臺(tái)時(shí)，無法做到4臺(tái)均勻分布法律責(zé)任本賠由社區(qū)用戶整理第9頁與，否則將缺陷2 遷移大上獲取新的數(shù)據(jù)只從兩臺(tái)老導(dǎo)致這兩臺(tái)老負(fù)載過大法律責(zé)任本賠由社區(qū)用戶整理第10頁與，否則將Consistent Hashi

5、ng 更實(shí)用的方法將整個(gè) Hash 區(qū)間看做環(huán)這個(gè)環(huán)的大小從 0359 變?yōu)?0264-1將和數(shù)據(jù)都看做環(huán)上的點(diǎn)引入 Micro shards / Virtual nodes 的概念 一臺(tái)實(shí)體對(duì)應(yīng) 1000 個(gè) Micro shards / Virtual nodes每個(gè) virtual node 對(duì)應(yīng) Hash 環(huán)上的一個(gè)點(diǎn)，就在環(huán)上隨機(jī)撒 1000 個(gè)點(diǎn)作為 virtual nodes每新加入一臺(tái)需要計(jì)算某個(gè) key 所在服務(wù)器時(shí) 計(jì)算該key的hash值得到0264-1的一個(gè)數(shù)，對(duì)應(yīng)環(huán)上一個(gè)點(diǎn) 順時(shí)針找到第一個(gè)virtual node 該virtual node 所在就是該key所在的數(shù)

6、據(jù)庫服務(wù)器新加入一臺(tái)做數(shù)據(jù)遷移時(shí) 1000 個(gè) virtual nodes 各自向順時(shí)針的一個(gè) virtual node 要數(shù)據(jù) 例子：法律責(zé)任本賠由社區(qū)用戶整理第11頁與，否則將Consistent Hashing法律責(zé)任本賠由社區(qū)用戶整理第12頁與，否則將Replica 數(shù)據(jù)備份問：Backup 和 Replica 有什么區(qū)別？法律責(zé)任本賠由社區(qū)用戶整理第13頁與，否則將Backup vs ReplicaBackup一般是周期性的，比如每天晚上進(jìn)行一次備份當(dāng)數(shù)據(jù)丟失的時(shí)候，通常只能恢復(fù)到之前的某個(gè)時(shí)間點(diǎn)Backup 不用作的數(shù)據(jù)服務(wù)，不分?jǐn)傋xReplica是實(shí)時(shí)的， 在數(shù)據(jù)寫入的時(shí)候，就會(huì)

7、以當(dāng)數(shù)據(jù)丟失的時(shí)候，可以馬上通過其他的品的形式存為多份品恢復(fù)Replica 用作的數(shù)據(jù)服務(wù)，分?jǐn)傋x思考：既然 Replica 更牛，那么還需要 Backup么？法律責(zé)任本賠由社區(qū)用戶整理第14頁與，否則將MySQL Replica以MySQL為代表SQL型數(shù)據(jù)庫，通常“自帶” Master Slave 的Replica 方法Master 負(fù)責(zé)寫，Slave 負(fù)責(zé)讀Slave 從 Master 中同步數(shù)據(jù)法律責(zé)任本賠由社區(qū)用戶整理第15頁與，否則將Master - Slave原理 Write Ahead LogSQL 數(shù)據(jù)庫的任何操作，都會(huì)以 Log 的形式做一份比如數(shù)據(jù)A在B時(shí)刻從C改到了DS

8、lave 被激活后，告訴master我在了Master每次有任何操作就通知 slave 來讀log 因此Slave上的數(shù)據(jù)是有“延遲”的masterMaster 掛了怎么辦？slave1slave2將一臺(tái) Slave 升級(jí) (promote) 為 Master，接受讀+寫可能會(huì)造成一定程度的數(shù)據(jù)丟失和不一致法律責(zé)任本賠由社區(qū)用戶整理第16頁與，否則將NoSQL Replica以 Cassandra 為代表的 NoSQL 數(shù)據(jù)庫通常將數(shù)據(jù)“順時(shí)針”在 Consistent hashing 環(huán)上的三個(gè) virtual nodes 中法律責(zé)任本賠由社區(qū)用戶整理第17頁與，否則將SQL vs NoSQ

9、L in ReplicaSQL“自帶” 的 Replica 方式是 Master Slave“手動(dòng)” 的 Replica 方式也可以在 Consistent Hashing 環(huán)上順時(shí)針存三份NoSQL“自帶” 的 Replica 方式就是 Consistent Hashing 環(huán)上順時(shí)針存三份“手動(dòng)” 的 Replica 方式：就不需要手動(dòng)了，NoSQL就是在 Sharding 和 Replica 上幫你偷懶用的！法律責(zé)任本賠由社區(qū)用戶整理第18頁與，否則將設(shè)計(jì)短系統(tǒng)Design Tiny URL法律責(zé)任和本由償社區(qū)用戶整理第19頁與，否則將法律責(zé)任和本由償社區(qū)用戶整理第20頁與，否則將回顧系

10、統(tǒng)設(shè)計(jì)的常見誤區(qū)流量一定巨大無比那必須是要用NoSQL了那必須是分布式系統(tǒng)了某同學(xué)：先來個(gè)Load Balancer，后面一堆Web Server，然后memcached，最底層NoSQL，搞定！法律責(zé)任和本由償社區(qū)用戶整理第21頁與，否則將系統(tǒng)設(shè)計(jì)問題的基本步驟4S 分析法1.提問：分析功能/需求/QPS/容量Scenario2. 畫圖：根據(jù)分析結(jié)果設(shè)計(jì)“可行解” Service+Storage3. 進(jìn)化：研究可能遇到的問題，優(yōu)化系統(tǒng) Scale法律責(zé)任和本由償社區(qū)用戶整理第22頁與，否則將Scenario 場(chǎng)景分析動(dòng)起手來試試看法律責(zé)任和本由償社區(qū)用戶整理第23頁與，否則將Scenario

11、 場(chǎng)景 我要設(shè)計(jì)啥根據(jù) Long URL 生成一個(gè) Short URL=>法律責(zé)任和本由償社區(qū)用戶整理第24頁與，否則將Scenario 場(chǎng)景 我要設(shè)計(jì)啥根據(jù) Short URL 還原 Long URL，并跳轉(zhuǎn)=>法律責(zé)任和本由償社區(qū)用戶整理第25頁與，否則將QPS動(dòng)起手來試試看，分析QPS和法律責(zé)任和本由償社區(qū)用戶整理第26頁與，否則將Scenario 需求 QPS + Storage1. 詢問面試官 約100M2. 推算產(chǎn)生一條Tiny URL的QPS日活躍用戶假設(shè)每個(gè)用戶平均每天發(fā) 0.1 條帶 URL 的Average Write QPS = 100M * 0.1 / 86

12、400 100 Peak Write QPS = 100 * 2 = 2002k QPS一臺(tái) SSD支持 的MySQL完全可以搞定3. 推算點(diǎn)擊一條Tiny URL的QPS假設(shè)每個(gè)用戶平均點(diǎn)1個(gè)Tiny URLAverage Read QPS = 100M * 1 / 86400 1k Peak Read QPS = 2k4. 推算每天產(chǎn)生的新的 URL 所占100M * 0.1 10M 條每一條 URL 長(zhǎng)度平均 100 算，一共1G 1T 的硬盤可以用 3 年法律責(zé)任和本由償社區(qū)用戶整理第27頁與，否則將Service 服務(wù)該系統(tǒng)比較簡(jiǎn)單，只有一個(gè) ServiceURL Service法律

13、責(zé)任和本由償社區(qū)用戶整理第28頁與，否則將Service 服務(wù) 邏輯塊聚類與接口設(shè)計(jì)TinyUrl只有一個(gè)UrlService 本身就是一個(gè)小Application 無需關(guān)心其他的函數(shù)設(shè)計(jì)UrlService.encong_url)UrlService.decode(short_url)端口設(shè)計(jì)GET /<short_url> return a Http redirect responsePOST /data/shorten/Data = url:Return short url法律責(zé)任和本由償社區(qū)用戶整理第29頁與，否則將Tiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：Q

14、PS和Storage應(yīng)用服務(wù)：UrlService法律責(zé)任和本由償社區(qū)用戶整理第30頁與，否則將Storage 數(shù)據(jù)存取數(shù)據(jù)如何與第一步：Select 選結(jié)構(gòu)第二步：Schema 細(xì)化數(shù)據(jù)表法律責(zé)任和本由償社區(qū)用戶整理第31頁與，否則將SQL or NoSQL選什么？標(biāo)準(zhǔn)是什么？法律責(zé)任和本由償社區(qū)用戶整理第32頁與，否則將SQL vs NoSQL 到底怎么選？是否需要支持 Transaction？ NoSQL不支持Transaction是否需要豐富的 SQL Query？ NoSQL的SQL Query不是太豐富 也有一些NoSQL的數(shù)據(jù)庫提供簡(jiǎn)單的SQL Query支持是否想偷懶？ 大多數(shù)

15、 Web Framework 與 SQL 數(shù)據(jù)庫兼容得很好 用SQL比用NoSQL少寫很多代碼是否需要Sequential ID？SQL 為你提供了 auto-increment 的 Sequential ID也就是1,2,3,4,5 NoSQL的ID并不是 Sequential 的法律責(zé)任和本由償社區(qū)用戶整理第33頁與，否則將SQL vs NoSQL 到底怎么選？對(duì)QPS的要求有多高？ NoSQL 的性能更高對(duì)Scalability的要求有多高？SQL 需要碼農(nóng)寫代碼來 Scale 還記得Db那節(jié)課中怎么做 Sharding，Replica 的么？NoSQL 這些都幫你做了所以Tiny UR

16、L用什么比較合適？法律責(zé)任和本由償社區(qū)用戶整理第34頁與，否則將Storage 數(shù)據(jù)如何與是否需要支持 Transaction？不需要。NoSQL +1是否需要豐富的 SQL Query？不需要。NoSQL +1是否想偷懶？Tiny URL 需要寫的代碼并不復(fù)雜。NoSQL+1對(duì)QPS的要求有多高？ 經(jīng)計(jì)算，2k QPS并不高，而且2k讀可以用Cache，寫很少。SQL +1對(duì)Scalability的要求有多高？和QPS要求都不高，單機(jī)都可以搞定。SQL+1是否需要Sequential ID？ 取決于你的算法是什么法律責(zé)任和本由償社區(qū)用戶整理第35頁與，否則將算法是什么？如何將 Long Ur

17、l 轉(zhuǎn)換為一個(gè) 6位的 Short Url？法律責(zé)任和本由償社區(qū)用戶整理第36頁與，否則將算法1 使用函數(shù) Hash Function（不可行）比如取 Long Url 的 MD5 的最后 6 位只是打個(gè)比方，這個(gè)方法肯定是有問題的啦優(yōu)點(diǎn)：快缺點(diǎn)：難以設(shè)計(jì)一個(gè)沒有的算法法律責(zé)任和本由償社區(qū)用戶整理第37頁與，否則將算法2 隨機(jī)生成ShortURL + 數(shù)據(jù)庫去重隨機(jī)一個(gè) 6 位的 ShortURL，如果沒有被用過，就綁定到該 LongURL偽代碼如下：優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：生成短的速度隨著短越來越多變得越來越慢法律責(zé)任和本由償社區(qū)用戶整理第38頁與，否則將算法3 進(jìn)制轉(zhuǎn)換 Base62Base6

18、2將 6 位的short url看做一個(gè)62進(jìn)制數(shù)（0-9, a-z, A-Z)每個(gè)short url 對(duì)應(yīng)到一個(gè)整數(shù)該整數(shù)對(duì)應(yīng)數(shù)據(jù)庫表的Primary Key Sequential ID6 位可以表示的不同 URL 有多少？ 5 位 = 625 = 0.9B = 9 億 6 位 = 626 = 57 B = 570 億 7 位 = 627 = 3.5 T = 35000 億優(yōu)點(diǎn)：效率高缺點(diǎn)：依賴于全局的自增ID法律責(zé)任和本由償社區(qū)用戶整理第39頁與，否則將隨機(jī)生成 vs 進(jìn)制轉(zhuǎn)換幸福二選一法律責(zé)任和本由償社區(qū)用戶整理第40頁與，否則將基于隨機(jī)生成的方法需要根據(jù) LongShort，也需要根據(jù)

19、 ShortLong。如果選擇用 SQL 型數(shù)據(jù)庫，表結(jié)構(gòu)如下：并且需要對(duì) shortKey 和 longURL 分別建索引（index）。什么是索引？索引的原理？法律責(zé)任和本由償社區(qū)用戶整理第41頁與，否則將shortKeylongUrla0B4LbDf523Pdao80FQFD8oq基于隨機(jī)生成的方法也可以選用 NoSQL 數(shù)據(jù)庫，但是需要建立兩張表（大多數(shù)NoSQL數(shù)據(jù)庫不支持以 Cassandra 為例子索引）第一張表：根據(jù) LongShortrow_key=longURL, column_key=ShortURL, value=null or timestamp第二張表：根據(jù) Sho

20、rtLongrow_key=shortURL, column_key=LongURL, value=null or timestamp法律責(zé)任和本由償社區(qū)用戶整理第42頁與，否則將基于隨機(jī)生成方法的 Work Solution1. check long urlshortentrue/false2. insert new urlWeb ServerURL Tablereturn short urlget1. check short urlWeb ServerURL Tablelong urlreturn http 301 redirect法律責(zé)任和本由償社區(qū)用戶整理第43頁與，否則將基于進(jìn)制轉(zhuǎn)換

21、的方法因?yàn)樾枰玫阶栽鯥D（Sequential ID），因此只能選擇使用 SQL 型數(shù)據(jù)庫。表單結(jié)構(gòu)如下，shortURL 可以不在表單里，因?yàn)榭梢愿鶕?jù) id 來進(jìn)行換算法律責(zé)任和本由償社區(qū)用戶整理第44頁與，否則將idlongUrl (index=true)1234基于進(jìn)制轉(zhuǎn)換方法的Work Solution1. check long urlshortentrue/false2. insert new urlWeb ServerURL Tablereturn idget1. check short urlWeb ServerURL Tablelong urlreturn http 301

22、redirect法律責(zé)任和本由償社區(qū)用戶整理第45頁與，否則將Tiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：QPS和Storage應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution法律責(zé)任和本由償社區(qū)用戶整理第46頁與，否則將先休息5分鐘，然后下半節(jié)的內(nèi)容，你基本要開始教大家彈指神通了不到期中問卷法律責(zé)任和本由償社區(qū)用戶整理第47頁與，否則將Scale 進(jìn)化Tiny URL 有什么可以優(yōu)化的地方？法律責(zé)任和本由償社區(qū)用戶整理第48頁與，否則將Interviewer: How to reduce response t

23、ime?如何提高響應(yīng)速度？說說看有哪些地方可以？提高讀的速度還是寫的速度？法律責(zé)任和本由償社區(qū)用戶整理第49頁與，否則將Scale 如何提速利用緩存提速（Cache Aside）緩存里需要存兩類數(shù)據(jù)：long to short（生成新 short url 時(shí)需要）short to long（short url 時(shí)需要）畫一下生成新URL時(shí)的流程圖小練習(xí)：getWeb Serverreturn http 301 redirectURL Table (MySQL)法律責(zé)任和本由償社區(qū)用戶整理第50頁與，否則將MemcachedTiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：QPS和Stor

24、age應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution提高Web服務(wù)器與數(shù)據(jù)服務(wù)器之間的效率：利用緩存提高讀請(qǐng)求的效率法律責(zé)任和本由償社區(qū)用戶整理第51頁與，否則將Scale 如何提速利用地理位置信息提速優(yōu)化服務(wù)器速度 不同的地區(qū)，使用不同的 Web 服務(wù)器 通過DNS不同地區(qū)的用戶到不同的服務(wù)器優(yōu)化數(shù)據(jù)速度使用Centralized MySQL+Distributed Memcached一個(gè)MySQL配多個(gè)Memcached，Memcached跨地區(qū)分布法律責(zé)任和本由償社區(qū)用戶整理第52頁與，否則將Scale 如何提速S

25、hared DB法律責(zé)任和本由償社區(qū)用戶整理第53頁與，否則將CNDNSWeb ServerMemcachedUSADNSWeb ServerMemcachedTiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：QPS和Storage應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution提高Web服務(wù)器與數(shù)據(jù)服務(wù)器之間的效率：利用緩存提高讀請(qǐng)求的效率提高用戶與服務(wù)器之間的效率：解決了中國用戶美國服務(wù)器慢的問題法律責(zé)任和本由償社區(qū)用戶整理第54頁與，否則將* Interviewer: How to scale?假如我們一開始估

26、算錯(cuò)了，一臺(tái)MySQL搞不定了法律責(zé)任和本由償社區(qū)用戶整理第55頁與，否則將Scale 如何擴(kuò)展？什么時(shí)候需要多臺(tái)數(shù)據(jù)庫服務(wù)器？Cache不夠DB 0寫操作越來越多越來越多的請(qǐng)求無法通過 Cache 滿足Web Server增加多臺(tái)數(shù)據(jù)庫服務(wù)器可以優(yōu)化什么？解決“存不下”的問題 Storage的角度解決“忙不過”的問題 QPS的角度Tiny URL 主要是什么問題？DB 1Web ServerDB 2如何將數(shù)據(jù)分配到多臺(tái)？DB 3法律責(zé)任和本由償社區(qū)用戶整理第56頁與，否則將Scale 如何擴(kuò)展？Vertical Sharding 將多張數(shù)據(jù)表分別分配給多臺(tái) Tiny URL 并不適用DB 0

27、Horizontal ShardingWeb Server用什么做Sharding Key?如果用 ID，如何Long Url?DB 1如果用Long Url，如何ID？用什么做 Sharding Key?Web ServerDB 2DB 3法律責(zé)任和本由償社區(qū)用戶整理第57頁與，否則將Scale 如何擴(kuò)展？用 Long URL 做 shard key的時(shí)候，只能廣播給N臺(tái)數(shù)據(jù)庫QPS的問題并不解決降低每臺(tái)用 ID 做 shard key按照 ID % N（N為數(shù)據(jù)服務(wù)器個(gè)數(shù)），來分配Short url to long url將 short url 轉(zhuǎn)換為 ID根據(jù) ID 找到數(shù)據(jù)庫到 lon

28、g url在該數(shù)據(jù)庫中Long url to short url先：廣播給 N 臺(tái)數(shù)據(jù)庫，是否看起來有點(diǎn)耗，不過也是可行的，因?yàn)閿?shù)據(jù)庫服務(wù)器太多對(duì)應(yīng)數(shù)據(jù)庫的話，獲得下一個(gè)自增 ID 的值，再：如果不法律責(zé)任和本由償社區(qū)用戶整理第58頁與，否則將Scale 全局自增ID如何獲得在N臺(tái)服務(wù)器中全局共享的一個(gè)自增ID是一個(gè)難點(diǎn)一種解決辦法是，專門用一臺(tái)數(shù)據(jù)庫來做自增ID服務(wù)Read more: 該數(shù)據(jù)庫不真實(shí)數(shù)據(jù)，也不負(fù)責(zé)其他 為了避免單點(diǎn)失效（Single Point Failure) 可能需要多臺(tái)數(shù)據(jù)庫另外一種解決辦法是用 Zookeeper使用全局自增ID的方法并不是解決 Tiny URL 的

29、最佳方法故不展開討論全局自增ID的細(xì)節(jié)，那到底怎么做？法律責(zé)任和本由償社區(qū)用戶整理第59頁與，否則將Scale 擴(kuò)展SHORT KEY如果最開始，short key 為6位，下面為short key增加 1 位前置位 AB1234 0AB1234 還有一種做法是把第1位單獨(dú)留出來做 sharding key，總共還是6位該前置位的值由 Hash(long_url) % 62 得到該前置位則為 sharding keyConsistent Hashing 相關(guān)練習(xí)將環(huán)分為62個(gè)區(qū)間每臺(tái)在環(huán)上負(fù)責(zé)一段區(qū)間這樣我們就可以同時(shí)通過 short_url 和 long_url 得到 Sharding Ke

30、y無需廣播無論是short2long還是long2short 都可以直接找到數(shù)據(jù)所在服務(wù)器Read more:Read more:法律責(zé)任和本由償社區(qū)用戶整理第60頁與，否則將Scale 目前的架構(gòu)Consistent Hashing 的Mapping 表存于每臺(tái) Web Server 上，hard code在代碼里法律責(zé)任和本由償社區(qū)用戶整理第61頁與，否則將CNDNSWeb ServerMemcachedShared DBShared DBShared DBShared DB 0123USADNSWeb ServerMemcachedTiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：

31、QPS和Storage應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution提高Web服務(wù)器與數(shù)據(jù)服務(wù)器之間的效率：利用緩存提高讀請(qǐng)求的效率提高用戶與服務(wù)器之間的效率：解決了中國用戶美國服務(wù)器慢的問題解決流量繼續(xù)增大一臺(tái)數(shù)據(jù)庫服務(wù)器的問題：將數(shù)據(jù)分配到多臺(tái)服務(wù)器法律責(zé)任和本由償社區(qū)用戶整理第62頁與，否則將* Interviewer: 還有可以優(yōu)化的么？法律責(zé)任和本由償社區(qū)用戶整理第63頁與，否則將Scale Multi Region 的進(jìn)一步優(yōu)化優(yōu)化空間的地方是 上圖的架構(gòu)中，還服務(wù)器 (Web Server) 與 數(shù)據(jù)庫服務(wù)

32、器 (Database) 之間的通信 中心化的服務(wù)器集群（Centralized DB set）與 跨地域的 Web Server 之間通信較慢 比如中國的服務(wù)器需要那么何不讓中國的服務(wù)器美國的數(shù)據(jù)庫中國的數(shù)據(jù)庫？如果數(shù)據(jù)是重復(fù)寫到中國的數(shù)據(jù)庫，那么如何解決一致性問題？ 很難解決用戶習(xí)慣想時(shí)，會(huì)被DNS分配中國的服務(wù)器中國的用戶中國的用戶的一般都是中國的的地域信息進(jìn)行 Sharding所以我們可以按照 如何獲得中國的用戶的地域信息？只需要將用戶比較常的弄一張表就好了美國的怎么辦？美國的數(shù)據(jù)好了，反正也那就讓中國的服務(wù)器慢多少中國中國是主流需求，優(yōu)化系統(tǒng)就是要優(yōu)化主要的需求法律責(zé)任和本由償社區(qū)用

33、戶整理第64頁與，否則將Scale 最終的架構(gòu)法律責(zé)任和本由償社區(qū)用戶整理第65頁與，否則將CNDB CNDNSWeb ServerMemcachedUSADNSWeb ServerDB USAMemcachedTiny URL 里程碑場(chǎng)景分析：要做什么功能需求分析：QPS和Storage應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution提高Web服務(wù)器與數(shù)據(jù)服務(wù)器之間的效率：利用緩存提高讀請(qǐng)求的效率提高用戶與服務(wù)器之間的效率：解決了中國用戶美國服務(wù)器慢的問題提高QPS，將數(shù)據(jù)分配到多臺(tái)服務(wù)器：解決流量繼續(xù)增大一臺(tái)數(shù)據(jù)庫服務(wù)

34、器的問題提高中國的Web服務(wù)器與美國的數(shù)據(jù)庫服務(wù)器通信較慢的問題：按照地域信息進(jìn)行Sharding法律責(zé)任和本由償社區(qū)用戶整理第66頁與，否則將* Interviewer: How to provide custom url?=>=>法律責(zé)任和本由償社區(qū)用戶整理第67頁與，否則將Scale 自定義的短自定義URL新建一張表CustomURLTable長(zhǎng)先再CustomURLTable URLTable創(chuàng)建普通短CustomURLTable是否根據(jù)長(zhǎng)先再在URLTable中和創(chuàng)新自定義短錯(cuò)誤的想法：是否已經(jīng)在URLTable中在URLTable中加一個(gè)column 大部分?jǐn)?shù)據(jù)這一項(xiàng)都

35、會(huì)是空 再在CustomURLTable中和課后練習(xí)：法律責(zé)任和本由償社區(qū)用戶整理第68頁與，否則將custom_urllong_url (index=true)ggfbjzTiny URL 設(shè)計(jì)總結(jié)場(chǎng)景分析：要做什么功能需求分析：QPS和Storage應(yīng)用服務(wù)：UrlService數(shù)據(jù)分析：選SQL還是NoSQL 數(shù)據(jù)分析：細(xì)化數(shù)據(jù)庫表得到一個(gè)Work Solution提高Web服務(wù)器與數(shù)據(jù)服務(wù)器之間的 利用緩存提高讀請(qǐng)求的效率Scenario: 各種問面試官問題，搞清楚要干嘛Service + Storage:根據(jù)問到的內(nèi)容進(jìn)行分析得到一個(gè)基本可以work的方案效率提高用戶與服務(wù)器之間的效

36、率 解決了中國用戶美國服務(wù)器慢的問題提高QPS，將數(shù)據(jù)分配到多臺(tái)服務(wù)器 解決流量繼續(xù)增大一臺(tái)數(shù)據(jù)庫服務(wù)器Scale的問題提高中國的Web服務(wù)器與美國的數(shù)據(jù)庫服務(wù)器通信較慢的問題 按照地域信息進(jìn)行Sharding提供 Custom URL 的功能follow up法律責(zé)任和本由償社區(qū)用戶整理第69頁與，否則將重要的事情說N遍系統(tǒng)設(shè)計(jì)沒有標(biāo)準(zhǔn)，言之有理即可設(shè)計(jì)一個(gè)可行解比拋出Fancy的概念更有用法律責(zé)任和本由償社區(qū)用戶整理第70頁與，否則將課后作業(yè)思考題：請(qǐng)基于隨機(jī)生成的算法，設(shè)計(jì)一整套系統(tǒng)假如同一個(gè) Long URL 可以對(duì)應(yīng)到不用的 Short URL，請(qǐng)根據(jù)這個(gè)特性優(yōu)化你的系統(tǒng)架構(gòu)。是否需

37、要長(zhǎng)久保存 ShortURL？好處是什么，壞處是什么？如果一個(gè) short URL 被瘋狂和點(diǎn)擊，會(huì)出現(xiàn)什么情況？以及如何避免這種情況帶來的麻煩？編程題：法律責(zé)任和本由償社區(qū)用戶整理第71頁與，否則將今天我們學(xué)會(huì)了什么？?jī)蓚€(gè)系統(tǒng)設(shè)計(jì)的 General Questions How to sharding? How to replica?一個(gè)超高頻的系統(tǒng)設(shè)計(jì)面試題 Design Tiny URL從題目之中我們學(xué)會(huì)的：SQL 和 NoSQL 的選擇標(biāo)準(zhǔn)讀比較多的話，可以用 Memcached 來優(yōu)化寫比較多的話，可以拆分?jǐn)?shù)據(jù)庫 Vertical Sharding / Horizontal Sharding Consistent HashingMulti Region知道了不同區(qū)域之