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

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

• 同步
• 網(wǎng)絡(luò)
• 數(shù)據(jù)庫(kù)
• 分布式
• 性能
• 估算
• 面向?qū)ο?/li>
• 案例
  • 社交網(wǎng)站信息流
  • 日志統(tǒng)計(jì)
  • 網(wǎng)絡(luò)爬蟲(chóng)
  • 電商產(chǎn)品頁(yè)面

1）Concurrency （并發(fā)）

• Thread vs. Process
  • 一個(gè)進(jìn)程擁有獨(dú)立的內(nèi)存單位，而線程是共享內(nèi)存的
  • 一個(gè)進(jìn)程擁有一個(gè)主線程
  • 進(jìn)程是系統(tǒng)進(jìn)行獨(dú)立資源調(diào)度分配的單位
  • 線程是真正的CPU分片時(shí)間
• Consumer and Producer
  • 兩個(gè)線程，兩個(gè)線程共同訪問(wèn)一個(gè)緩沖區(qū)
  • 一個(gè)線程是生產(chǎn)者，將數(shù)據(jù)放入緩沖區(qū)，另一個(gè)線程是消費(fèi)者，消費(fèi)緩沖區(qū)中的數(shù)據(jù)
  • 如何保證生產(chǎn)者不會(huì)再緩沖區(qū)滿(mǎn)的時(shí)候放入數(shù)據(jù)，消費(fèi)者不會(huì)再緩沖區(qū)空的時(shí)候訪問(wèn)緩沖區(qū)
  • Blocking Queue是一種典型的這種容器。
• Tracking:
  • Synchronized 同步方式
  • Asynchronized 異步方式

2）Network 網(wǎng)絡(luò)模型

• The Seven Layers of OSI

  • Application Layer HTTP協(xié)議
  • Presentation Layer
  • Session Layer
  • Transport Layer TCP/UDP
  • Network Layer
  • Data Link Layer
  • Physical Layer

• Visit URL

  • What happens after you typed a URL in your browser and pressed return key?
  • 需要連接遠(yuǎn)端服務(wù)器
    • 需要服務(wù)器的IP和端口
    • 如果沒(méi)有IP和端口，則需要進(jìn)行尋址，訪問(wèn)DNS(domain naming service)服務(wù)器，通過(guò)分層可以找到相應(yīng)DNS
    • DNS返回服務(wù)器的IP
    • 和遠(yuǎn)端服務(wù)器進(jìn)行TCP連接，沒(méi)有指定端口時(shí)，默認(rèn)80端口
    • 和服務(wù)器建立HTTP會(huì)話
    • 遠(yuǎn)端服務(wù)器返回?cái)?shù)據(jù)，瀏覽器解析數(shù)據(jù)，本渲染出網(wǎng)頁(yè)。
  • 發(fā)送請(qǐng)求到服務(wù)器

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

• Relational DB vs. KV Store
  • KV在需求簡(jiǎn)單，數(shù)據(jù)量又較大，沒(méi)有太多關(guān)聯(lián)關(guān)系時(shí)使用。
• Sharding vs. Clustering
  • 一般認(rèn)為單表數(shù)據(jù)量控制在1000w以?xún)?nèi)，如果超過(guò)這個(gè)量，則需要進(jìn)行拆表
  • 通過(guò)協(xié)調(diào)器，來(lái)均衡各個(gè)服務(wù)器的負(fù)載。內(nèi)部智能動(dòng)態(tài)調(diào)度。

4）Distribute System 分布式

How to scale Tiny URL service?

• Stateless frontend servers behind a load balancr 前段服務(wù)做負(fù)載均衡，Stateless 沒(méi)有狀態(tài)，當(dāng)用戶(hù)操作時(shí)，當(dāng)工作做了一般，轉(zhuǎn)換服務(wù)器之后，還可以繼續(xù)，而不是仍然要使用原有的服務(wù)器。
• Sharded/replicated database(on shortlink code)
• Memcached to scale read traffic 通過(guò)緩存，緩解數(shù)據(jù)庫(kù)讀取壓力
• Spread write load 可以通過(guò)先定位，再寫(xiě)入的方式
• Locally buffered event tracking + async flush to high-throughput message queue(kafka)
• Use a distributed unique ID generator(64-bit)

5) Performance 性能

CPU -> L1 -> L2 -> L3 -> SSD -> HD -> Network 速度越來(lái)越慢

6) Estimation 估算

How many piano tuners are there in the entire world?

• 考察思維邏輯推理
• 對(duì)估算是否有考慮

Tiny URL:How much is total storage?

• URL 的平均長(zhǎng)度 10-1000 字節(jié)
• 假設(shè)目前已經(jīng)存了一億個(gè)
• 新增的URL大概是一天100000條（1秒增加一條）
• 一天大概需要查詢(xún)一億次，每秒1000次

7）Design Patten 設(shè)計(jì)模式

23 patterns:

• MVC
• Singleton
• Factory
• Iterator
• Decorator
• Facade

3.案例

News Feeds

• Define feed
  • 首先要定義feed的內(nèi)容，可以是一個(gè)新聞的片段，應(yīng)該包含內(nèi)容，發(fā)布人，發(fā)布時(shí)間
• Organize
  • aggregate 同一個(gè)人發(fā)布多條信息，是否需要?dú)w類(lèi)
  • dedup 如果同一條信息多人發(fā)布，能否去重
  • sort 更具發(fā)布時(shí)間，或內(nèi)容的重要新（親密度，高級(jí)用戶(hù)）
  • Level 1.0
    • Database Schema：
      • User
      • Friendship
      • News
    • Get Newsfeed
      • merge news
    • Newsfeed vs. News
      • Newsfeed是一個(gè)集合，我的主頁(yè)需要顯示的，我的好友圈
      • News僅僅是一個(gè)新聞。
    • Why bad?
    • 100+ friends
      • 1 Query --> Get friends list
      • 1 Query --> SELECT news WHERE timestamp>xxx AND sourceid IN friend list LIMIT 1000
    • IN 非常慢
    • Sequential scan or 100+ index queries
  • Level 2.0
  • Pull vs. Push
    • Pull：Get news from each frined,merge them together.
    • Push: NewsFeed generated when news generated.
  • Level 3.0
    • Popular star
      • Flowers 13M + 人數(shù)太多
      • Async Push may cause over 30 minutes
    • Push + Pull
      • 對(duì)于明星人群，不要push news 給 flowers
      • 對(duì)于普通人，兩者結(jié)合
  • Level 4.0
    • Push disadbantage:
      • Realtime
      • Storage(Duplicate)
      • Edit
    • Go back to PULL:
      • Cache user's latest news
      • Broadcast multiple request to multiple servers(Shard by userID)
      • Merge & Sort
      • Cache newsfeeds for this user with timestamp

Stats Server

How are click stats stored?

• 每次點(diǎn)擊就會(huì)將寫(xiě)入數(shù)據(jù)庫(kù)
• 增加中間層，再根據(jù)某種策略，將中間層寫(xiě)入數(shù)據(jù)庫(kù)
• 設(shè)計(jì)出一個(gè) low-latency messaging，能夠緩存數(shù)據(jù)，還能夠存入數(shù)據(jù)庫(kù)

Cache Requirement

• 當(dāng)收到request，首先在cache中尋找，如果找到則直接返回
• 如果沒(méi)有找到則傳入系統(tǒng)
• 設(shè)計(jì)cache只能存儲(chǔ)一定量的request，如果超過(guò)，則刪除最早的request。
• 查找，刪除，插入 O(1)

Web Crawler

Amazon Product Page

• The product page includes information such as
  • a) product information
  • b) user information
  • c) recommended products