動機

之前面試莫名其妙被system design電到翻過去， 之後看了，system design primer，但還是出事，以為只要把system design的觀念記熟就好，之後要我計算有的沒的就起飛。

目前發現這個，看完發現，原來我之前只有準備一半啊

system design的面試其實有一定的程序要走，不是單純的QA 這個沒做過相關的分析，基本上應該很難當場想出來，我當初是能想到設計，但沒辦法證明(do some math)這是可行的

所以這篇，是要補完這點。

過程

  1. 需求
  • 功能
  • output
    • 格式
  • Input的量
    • 每秒多少資料
    • 每秒多少request
  • throughput
    • Queries Per Second, QPS
    • 預期希望處理多少資料
  • latency
  1. 限制
  • 有什麼機器，spec
    • core
    • RAM
  • CAP
    • CA
      • 一致性(總是能拿到最新的) + 可用性(拿得到資料)
      • 單一DB
    • AP & CP
      • 分區容錯性(能不能分區，只有一部份是好的)
      • 有P就是兩個case
        • -總是拿到*資料，但是可能是舊的: AP
        • 可能拿不到資料，但是一定是新的: CP
    • 最終一致性
  1. 算需要多少資源
  • Daily Active User & QPS & storage & 幾台機器
    • creation QPS
    • reading QPS
    • storage for a day & many years(10years)
  • 需求+spec不能超過物理限制
    • spec
      • ram
      • ssd/hdd
      • network(RTT)
      • cores
    • 需求
      • throughput(qps)
      • input
      • latency
  • 常見物理限制的平均值
    • ram
      • 250us
    • ssd
      • 1000us
    • compress
      • 3us
    • network
      • same data center
        • 500us
      • CA<->Netherlands
        • 150000us
    • 1us = 10^-6secs
    • 1ns = 10^-9secs
    • 1ms = 10^-3secs
  1. 畫架構(API -> prog) <-> 加強 (loop)
  • CDN, DNS
  • message queue
  • concurreny/parallel design
  • Load Balancer
    • 分配方式: random, 最少負載
    • layer 4 or layer 7
  • cache
    • write around
    • write through
    • write back
  • multi-server
    • 多master or master-slave
      • 容錯轉移(failover) or 複寫(Replication)
    • auto scale
      • container orchestration platform
    • 讀寫分離
      • total = R+W，分配R與W的數量
  • DB
    • schema
      • 反正規化
      • design
        • one to one
        • one to many
        • many to many
    • multi-server
      • 依功能分成多DB (federative database)
      • 把資料分散到多DB (sharding)
    • SQL/noSQL
      • SQL: 強一致性, transaction, 複雜結構(join,index)
      • SQL: 最終一致性, 高throughput, 巨量資料

需要多少機器

要想辦法讓需求在物理限制之中

用這裡的快取做例子，來算一下

這裡是設計快取，所以記憶體的速度是物理限制

之後，需求給qps與input總量，求大概幾台幾core多少ram的機器

# 從會算的開始，要幾台
host = total_input/ram
# 每個core每秒要處理多少req
req_per_core_per_sec = qps/(host*core)
# 頻率就是時間的倒數
latency = 1/req_per_core_per_sec = (host*core)/qps
# 展開host
latency = (total_input*core)/(ram*qps)
# 把給定的數字分出來
latency = (total_input/qps) * (core/ram)
# 因為是物理限制，所以求出來的數字，不能超過latency
latency <= (total_input/qps) * (core/ram)
# 因此，要不是core變多，就是ram變小
# 台數可以透過 host = total_input/ram 算

上面推導完來帶數字

  • qps: 10m
  • total_input: 30tb

這裡有個小訣竅，在算時把單位換成統一的比較好用，看要消的單位來看要換成或不會換 像，與大小有關都是gb，時間都是sec

查表會發現，從mem讀1MB要250us(10^-6 secs)

先換算，250*10^-6

250*10^-6 <= (30*1000)/10*10^6 * (core/ram)
# 化簡
1 <= 12 * (core/ram)
# 4cores
ram <= 12*core = 48

所以4cores，一台最多只能48gb 8cores，一台最多只能96gb

照原本這裡第一次給的spec，4cores與72gb會爆，但是4cores與32gb不會爆

那總共要幾台，以4cores與32gb來看，要30*1000gb/32gb=940台

要在設計之前要知道

  • Daily Active User
    • read的頻率 => read的total_input
    • write的頻率 => write的total_input
  • user產生的資料大小 (post, short url)
    • 有可能是根據自己設計的去算(short url)
  • latency for read & write
  • Consistency or Availability
  • read-heavy or write-heavy or half-half

之後要求出，下面的東西才能繼續做設計

  • read QPS
  • write QPS
  • storage comsumption

如果需要求需要多少台機器 latency <= (total_input/qps) * (core/ram) 配合 host = total_input/ram

例子

這裡 這裡2

一些技巧

  • API設計
    • 放api_dev_key
      • 做bandwidth controll
  • Implement
    • online / offline
      • online: 一來算一筆
      • offline: 預先生成資料 (short url的碼)
    • Sharding 的 hash key
      • foreign key
      • primary key+timestamp(create time)
      • primary key+counter (zookeeper)
    • 要多長 (short url)
      • 要放多久*每天產生多少 <= (possible chars)^長度
      • 有長度就可以算storage

interviewBit

Sharding a Database

  • Can we have a fixed number of shards?
  • map to shard function: H % S
    • number of shards is S
    • a numeric hash H
    • When adding a new machine,
      • need to relocate each and every key
      • extremely expensive and highly undesirable
  • Consistent Hashing
    • 把shard列序
    • 將data或user map 到 其中一個shard
    • 如果出事或是加新機器
      • 把資料往下一台移(因為已經有順序了)

Highly Available Database

  • Master Slave
  • Multi Master
  • peer to peer
    • Consistent Hashing
      • Read and Write consistency
        • 設有P份copy
        • 要讀或寫，就對所有shard發req，拿到一定數量的ack才成功
          • R是回傳read成功的次數，W是回傳write成功的次數
        • 要維持C(總是拿到最新的write)
          • W + R > P
            • W = P: 強C(每台都要回)
              • R = 1: for fast read
            • W < P: 最終一致
              • W = 1: for fast write
              • 要處理data conflict
                • 先寫先贏
                • 留標記

Highly Consistent Database

  • 為了C與處理單點錯誤
    • 資料要write到多台DB
  • 如果每一台都write很費時，只要寫到一定數量就好
    • 需要master追蹤寫到哪些機器
  • master只有一台? 單點錯誤
    • 多一台做standby