Design Data Intensive Applicat

何為SHARDING:

將大數據集分為多個塊，存儲在不同的服務器上

目的：

可擴展性: 不同的分片可以放在不同的服務器上，分散讀請求
復雜查詢可以并行的在不同的分片上執行
寫請求分散到各個服務器上

問題1: 怎么分？

每個服務器上數據保持均勻,避免數據傾斜

• 隨機分配:
  優點: 數據均勻
  缺點: 無法知道數據在哪個節點
• 每個分片保存主鍵一個范圍內連續鍵值 (partition by key range)
  優點: 容易算出主鍵在哪個節點. 主鍵可有序存儲，方便范圍搜索
  缺點: 每個分片數據可能不均勻，需要調節分片邊界 --> 手動或自動. 主鍵前綴解決分布問題
• 按主鍵HASH值分片: （riak, couchbase, voldemort）
  優點: 理論上數據均勻，取決于HASH算法. 容易算出數據在哪個節點
  缺點: 難以進行范圍搜索
• 混合模式: 聯合主鍵，先按主鍵第一個屬性HASH，再按其他屬性有序排列 (cassandra)
  適合處理一對多數據
  處理數據傾斜和熱點鍵讀寫:
  需要應用層解決: 如對鍵值增加隨機前后綴. 缺點: 同一個鍵值的數據分散在不同分片內，增加讀取復雜度

  問題2: 如何查詢數據?

  分片策略解決了寫和主鍵查詢的問題，但是如何解決其他查詢條件查詢？如何在數據分片的情況下建立二級索引?

• 本地索引: 每個分片單獨維護二級查詢條件到主鍵列表的字典映射
  優點：寫數據時更新索引時容易
  缺點：查詢必須在每個分片的二級索引中查找，再合并結果
• 全局索引: 一個獨立的索引結構覆蓋所有分片，索引本身也分片，按照索引對應的查詢條件 （term partitioned)
  優點：查詢索引落到單個分片,效率高，如果采用RANGE分片也支持范圍查詢
  缺點: 寫入數據復雜，寫操作會影響多個分片(數據分片和索引分片未必在同一個節點), 需要分布式事務支持, 或者采用異步方式，犧牲一致性,新寫入的數據未必立刻在索引中可見.

  問題3: 集群擴容或者有宕機節點分片數據如何處理?

  分片數據需要從一個節點遷移到另一個節點 (partition rebalancing)

  數據重平衡需求:

  1. 遷移后負載必須保持均勻 (集群擴容)
  2. 遷移中集群必須可用，讀寫無影響
  3. 遷移必須最小化不必要的數據移動，減少集群IO開銷

     數據重平衡策略:

• hash取模會導致擴容后大量分片所處節點發生變化, 不滿足上述需求3
• 不直接把key映射到node，而是先把key映射到partition, 再把partition映射到node. partition的數量遠大于node的數量, 這樣新增node獲取部分partition數據, 同時保持key到partition的映射不變 （riak, elasticsearch, couchbase, voldemort)
  優點: 最小化擴容過程中的數據移動
  缺點: partition數量是永遠固定的，不可增減, 決定partition的數量很難，每個partition的數據量過大或者過小都會帶來額外開銷
• 動態主鍵范圍分片: 數據分片按照主鍵排序, 當分片超過配置大小后自動分裂為兩個分片, 當分片由于數據刪除過小后和相鄰的分片做合并. (hbase, rethinkDB)
  優點: 分片大小自動適配集群數據量
  缺點: 數據庫剛初始化時僅有一個分片, 讀寫負載不能有效分散. 解決方案: 配置預分片.
  動態分片也可應用于HASH分片
• 分片數同比例于節點數: 即每個節點上分片數固定. 新節點加入時，隨機選取一定數量的分片做等分，把一半數據移動到新節點. (cassandra, ketama)
  缺點：只支持HASH分片. 隨機選取可能導致數據不均勻

  人工或自動平衡:

  自動重平衡
  優點：不需要人工干預
  缺點：分片數據移動是昂貴的操作，會對集群性能產生不可知影響，并容易引起雪崩效應
  人工重平衡
  優點：可控性強
  缺點：響應速度慢

請求路由：

重平衡之后客戶端需要知道連接到哪個節點

• 客戶端可連接到任何節點，如果分區存在則處理請求，否則由節點負責將請求發往分片所在節點
  優點：客戶端不需要存儲分片METADATA，
  缺點：請求roundtrip時間可能變長
• 單獨的路由層負責接收客戶端請求并轉發，路由層需要了解分片存儲METADATA
  優點：客戶端不需要存儲分片METADATA，
  缺點：請求roundtrip時間可能變長

• 客戶端存儲分片METADATA并直接路由到新節點
  優點：直接路由, 速度快
  缺點：客戶端需要感知分片topology變化

  客戶端感知路由變化是一個挑戰性的問題. (網絡延遲/分區等), 需要分布式一致性協議，或者用集中式路由METADATA存儲如zookeeper等

并行QUERY執行:

分析型數據庫需要將復雜的QUERY分解成可多個并發執行的分片和階段，構成一個有向無環圖

其他：

一般SHARDING和REPLICATION會一起使用，一個分片會保存在多個服務器上
一致性HASH: 主要解決CDN網絡隨機選擇分片邊界而不需要一個集中式的一致性協議，一般不太適合使用于數據庫