系統(tǒng)設(shè)計(jì)與實(shí)踐

系統(tǒng)設(shè)計(jì)介紹

短URL設(shè)計(jì)

設(shè)計(jì)一個(gè)系統(tǒng)把用戶提供的URL轉(zhuǎn)換為短的URL，訪問的時(shí)候要跳回到原始的URL关炼，在系統(tǒng)設(shè)計(jì)的面試?yán)锍谈梗绾卧u(píng)價(jià)一個(gè)系統(tǒng)設(shè)計(jì)，一分到四分

第一級(jí)：

設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)來(lái)映射關(guān)系儒拂，從短URL到原始的URL寸潦。

有哪些不好的地方？

從原始的URL返回一個(gè)5位的編碼社痛，不是五位的用0補(bǔ)充见转。

能不能擴(kuò)充，返回的ID為什么都是0到9蒜哀？

在Cache里面搜索斩箫，Read/Write rate LRU和LFU

第二級(jí)：

Key-Value DB

MySQL is slow

Key-Value模型做了很多簡(jiǎn)化，提升了性能，是MySQL的10倍以上

有沒有其他辦法產(chǎn)生呢乘客？

URL->md5(128bits)

Base64->6bits

Truncate(md5(URL), 5)

第三級(jí)：

考慮到擴(kuò)展性和可靠性

Multiple Servers(Memcache/DB)

Sharding: hash(URL) % N = Server ID

Standby

Reliability

Replica(cross region, master slave)

Recovery(master: checkpoints, slave:recreate)

Consistency：一致性赊抖，在分布式當(dāng)中，某一個(gè)節(jié)點(diǎn)還沒有同步完成寨典，從A和B中讀出來(lái)有誤差

第四級(jí)：

從chunk中分到一個(gè)cluster氛雪，id generator（zookeeper）

怎么避免URL被重復(fù)地訪問和爬蟲(有些網(wǎng)站不想要被爬取)，可以在內(nèi)部把字符串打亂

怎么限制單一用戶RPS耸成，strategy?

流量控制

怎么實(shí)現(xiàn)重定向的思路报亩？

速率限制：可以用memcache,key是IP，Username/Email, UserId(logged in)

Reak key in memcache: key+timestamp(inminute)

Value:counter

Expiration:/m,/h,/d

Memcache內(nèi)存

Redis內(nèi)存+磁盤井氢，定時(shí)從內(nèi)存flush

Nosqul database

Sql database

Ratelimit

使用cache帶上過期銷毀信息弦追，一個(gè)小時(shí)后銷毀，但算法會(huì)出錯(cuò)

系統(tǒng)設(shè)計(jì)七劍客：

同步

網(wǎng)絡(luò)

數(shù)據(jù)庫(kù)

分布式

性能

估算

面向?qū)ο?/p>

案例-社交網(wǎng)絡(luò)信息流

日志統(tǒng)計(jì)

網(wǎng)絡(luò)爬蟲

電商產(chǎn)品頁(yè)面

concurrency

thread vs. process

consumer and producer

blockingqueue

tracking:

synchronized, asynchronized

操作系統(tǒng)里面程序運(yùn)行的系統(tǒng)單位花竞，一個(gè)程序至少有一個(gè)進(jìn)程劲件，一個(gè)進(jìn)程至少有一個(gè)線程，進(jìn)程的劃分比較小约急，一個(gè)進(jìn)程有獨(dú)立的內(nèi)存單位零远，但多個(gè)線程可以共享內(nèi)存，每一個(gè)獨(dú)立的線程有入口厌蔽，序列和程序的出口牵辣，操作系統(tǒng)會(huì)用進(jìn)程的調(diào)度管理來(lái)分配，進(jìn)程是數(shù)據(jù)集合上的活動(dòng)奴饮，是系統(tǒng)實(shí)現(xiàn)調(diào)度的單位

生產(chǎn)者和消費(fèi)者：

有限的緩沖問題纬向，多線程同步問題的案例，主要描述了兩個(gè)共享緩沖區(qū)的線程戴卜，一個(gè)叫consumer,一個(gè)叫producer逾条，生產(chǎn)者生產(chǎn)一定數(shù)據(jù)到緩沖區(qū)，消費(fèi)者負(fù)責(zé)消費(fèi)投剥，生產(chǎn)者不會(huì)在緩沖區(qū)滿的時(shí)候加入师脂，消費(fèi)者不會(huì)在空的時(shí)候的消費(fèi)

blockingqueue

給定了一個(gè)queue的結(jié)構(gòu)，普通的queue先入先出薇缅，但空的時(shí)候要等待危彩，滿的時(shí)候不能push，queue的基本操作泳桦，有move和add汤徽，有maxSize,，如果有兩個(gè)同時(shí)去操作的話灸撰，有保護(hù)谒府，在函數(shù)起始位置有l(wèi)ock,末尾有unlock.當(dāng)queue是空的時(shí)候拼坎，que就一直在等待，

tracking相關(guān)的完疫，記錄一個(gè)事件是不是被記錄下來(lái)枢步，

兩種做法一種是同步的近弟，一種是異步的腌乡，當(dāng)你去訪問一個(gè)服務(wù)的時(shí)候是一個(gè)get請(qǐng)求斩启，異步的方式，放入緩沖區(qū)芳誓，做一種積累余舶，log aggregator，每隔一段時(shí)間去刷新到磁盤上面锹淌，好處是一方面降低系統(tǒng)復(fù)雜度匿值，另一方面可以加一些實(shí)時(shí)的分析系統(tǒng)。

網(wǎng)絡(luò)結(jié)構(gòu)

OSI

Application layer

Presentation layer

Session layer

Transport layer

Networklayer

Data link layer

Physical layer

在頭部會(huì)加一些mate data

應(yīng)用層有HTTP協(xié)議赂摆，1.1

傳輸層：TCP,UDP

網(wǎng)絡(luò)層IP

TCP是一個(gè)可靠的穩(wěn)定的鏈接挟憔，UDP不太可靠，到物理層會(huì)通過路由傳輸?shù)搅硗庖慌_(tái)機(jī)子上去烟号，然后會(huì)一層層往上解壓

Visit URL

當(dāng)你輸入一個(gè)URL后發(fā)生了哪些事情

先要鏈接到遠(yuǎn)端的服務(wù)器绊谭，然后發(fā)送請(qǐng)求到服務(wù)器，尋址和建立鏈接褥符，首先你要做一個(gè)尋址龙誊，如果瀏覽器中存在URL的IP抚垃，就直接訪問喷楣，否則要訪問DNS，尋址加上域名找到IP鹤树，域名是一個(gè)分層的結(jié)果铣焊，頂級(jí)域名，DNS會(huì)返回服務(wù)器的地址罕伯，第三步就是瀏覽器會(huì)建立三次握手建立TCP的鏈接曲伊，網(wǎng)頁(yè)服務(wù)默認(rèn)端口是80端口，第四部是瀏覽器和服務(wù)器的會(huì)話追他，接受數(shù)據(jù)坟募，第五步是瀏覽器解析數(shù)據(jù)并渲染展示網(wǎng)頁(yè)，瀏覽器關(guān)閉的時(shí)候會(huì)終止對(duì)話并把鏈接關(guān)閉邑狸。

數(shù)據(jù)庫(kù)Database

relational DB vs. Key value store

sharding vs. clustering

以前關(guān)聯(lián)是主流懈糯，結(jié)構(gòu)化和數(shù)據(jù)模型，交易的安全性要求非常高

KV store在很多社交網(wǎng)站单雾，發(fā)了很多信息是對(duì)象的存儲(chǔ)赚哗，是一個(gè)靜態(tài)的過程她紫，不需要做很多關(guān)聯(lián)。

分片和集群的比較屿储，一臺(tái)數(shù)據(jù)庫(kù)的容量有限贿讹，單個(gè)表的承受在一千萬(wàn)左右，超過一千萬(wàn)實(shí)現(xiàn)的性能比較差够掠，需要拿到更大的數(shù)據(jù)量需要拆表民褂，垂直拆和水平拆，取摸然后分配到不同的機(jī)器上面去疯潭，第二種是clustering,是一個(gè)自動(dòng)管理的東西助赞，會(huì)自動(dòng)維護(hù)，有協(xié)調(diào)者袁勺，知道哪個(gè)服務(wù)器的復(fù)雜量的高低雹食，每次先訪問協(xié)調(diào)者，然后返回一個(gè)服務(wù)器地址期丰。

聽起來(lái)很好群叶，加一臺(tái)數(shù)據(jù)庫(kù)會(huì)告訴你，在真正的工業(yè)中sharding更多一點(diǎn)钝荡，算法設(shè)計(jì)不好的話本來(lái)負(fù)荷就很高街立，給更多的壓力，一旦發(fā)現(xiàn)問題的話sharding能做問題的定位和處理埠通，在做tinyURL的時(shí)候也用到了數(shù)據(jù)庫(kù)的結(jié)構(gòu)赎离，怎么拿到code,url, created_at,要加一個(gè)索引。

分布式

怎么規(guī)亩巳瑁化tinyurl梁剔，一個(gè)是對(duì)于前段的服務(wù)可以用load balancer,給前端服務(wù)做均衡，當(dāng)某一臺(tái)機(jī)器做了一個(gè)轉(zhuǎn)移之后還能做

第二個(gè)是把服務(wù)器sharding化舞蔽。

第三步提高性能荣病，每一層都可以加一些cache,相當(dāng)于把讀的請(qǐng)求給緩存住，大大減輕服務(wù)器的壓力渗柿。

然后對(duì)寫的流量也要給做一個(gè)平衡化个盆。

原來(lái)只能寫到集中一臺(tái)的對(duì)象，現(xiàn)在能寫到某一個(gè)服務(wù)器上的數(shù)據(jù)庫(kù)朵栖。

如何做一個(gè)tracking可以在本地做一個(gè)緩沖颊亮，異步刷新到message queue上去。

Performance性能

Numbers evetyone should know

訪問效率陨溅，cache 0.5ns

硬盤千萬(wàn)納秒級(jí)

閃存终惑，壽命比磁盤小一些，比較適合做隨機(jī)声登，磁盤適合做順序

Estimation

全世界范圍內(nèi)有多少調(diào)音師

tinyURL總的存儲(chǔ)大小

URL長(zhǎng)度10-1000字符

設(shè)計(jì)模式

MVC狠鸳，網(wǎng)絡(luò)系統(tǒng)中揣苏，后端數(shù)據(jù)叫模型層，前段叫View,中間叫Controller

Singleton只有一個(gè)實(shí)例件舵，能使用一些方式來(lái)初始化這個(gè)實(shí)例

Factory

Iterator

Decorator

Fa?ade

案例

news feeds

stats server

web crawler

amazon product page