第六章節：學習要點

[JimmyFUFU]

我沒準備 kahoot 會不會破壞傳統 Q

---

• Partitioning

  • 當資料量超過一台機器的負荷時，就會需要用到 partition 去將資料分割放到不同的機器(節點)上，也可以稱之為 sharding
  • 目標：將 data 和 query load 平衡的分配每個 node 上，如果 partitioning 是不平衡的，會導致某個 node 會有過多的 data，我們稱之為偏斜(skew)，而這個 node 稱之為熱點(hot spot)

• Partitioning by Key Range key 可以是資料中單詞的開頭字母，也可以是時間，用時間的話可以很輕鬆地獲取某日或某月的資料 缺點： hot spot => 幫 key 加上一些 prefix 來讓資料還是能分佈在不同的 partition 上

• Partitioning by Hash of Key 為了要避免偏斜和熱點，可以用簡單的雜湊讓相似的原始資料們被平均且隨機分配在不同的 partition 缺點：導致範圍查詢會比 key-range 做 partition 來的要慢，需要將所有 query 都丟到各個 partition 上面去搜尋

• Partitioning and Secondary Indexes

  • Document-based 每個 partition 維護自己的次級索引，所以也被稱為本地索引 local index query 時需要做 分散 / 聚集（scatter/gather）
  • Term-based
    • 全域型索引 global index
    • 優點：讀取比較快，可以去包含關鍵字的 partition 拿資料就好，不需要 scatter/gather
    • 缺點：寫入比較複雜，寫入單一文件可能會影響到多個 partition
    • 非同步的更新

• Rebalancing Partitioning

  • Query 吞吐量增加 → 需要新增節點
  • 資料量變大 → 需要新增節點
  • 某個節點出現故障 → 將資料給節點保管
  • 最低要求
    • Rebalance 之後，負載（資料儲存，讀取和寫入請求）應該節點之間公平地共享。
    • Rebalance 時，資料庫應該繼續接受讀取和寫入 ⇒ zero downtime
    • 節點之間只移動必須的資料，減少網路和磁碟 I/O 負擔

• Request Routing

  • client 可以 access 每個節點，可以利用迴圈或是隨機的方式找到資料
  • 會有一個 routing tier 來將 client 端的 query 導向正確的節點
  • client 端知道 partition 的分配方式和情況，可以直接去正確的節點拿到資料

[0x171-0]

• 分區與複製

  • 分區：將大數據集劃分為較小數據集 ，增加可伸縮性，目標是將請求均勻發送到不同節點上
  • How？
  • 與複製結合，達到多節點儲存
  • 分區主庫與分區從庫可以在不同節點上，每個節點既可以是某分區的主庫、其他分區的從庫

• 鍵值資料的分區

  • 分區不良可能造成的問題？熱點、偏斜

  • 3種分區方法

    • 1.根據鍵的範圍分區
      • 作法:為每個分區指定一塊連續的鍵範圍，鍵是有序的，並且分區擁有從某個最小值到某個最大值的所有鍵。
      • 優點:排序的優勢在於可以進行有效的範圍查詢
      • 缺點:若應用經常訪問相鄰的鍵，存在熱點風險
    • 2.散列分區（hash partitioning）
      • 作法: 散列函數應用於每個鍵，分區擁有一定範圍的散列
      • 優點: 好的散列函數可以讓偏斜的數據均勻分佈，減少熱點
      • 缺點:
        • 破壞了鍵的排序，使得範圍查詢效率低下，但可以更均勻地分配負載。
        • 解法：複合主鍵/組合索引方法
    • 3.兩種方法合併

  • 負載偏斜與熱點消除

    • 散列分區可以減少，但是無法消除熱點
    • 目前數據系統無法自動檢測和補償偏斜的工作負載，所以需要自己在應用層實作
      • 解法例子：主鍵的開始或結尾加上隨機數，作法可能造成額外紀錄、計算

• 次級索引分區方法

  • document-based

    • 作法: 每個分區完全獨立，各自維護自己的次級索引。
    • 缺點: 讀取沒效率
      • 分散 / 聚集搜索法導致 導致尾部延遲放大

  • term-based

    • 作法：關鍵詞分區 term-partitioned，構建覆蓋所有分區的全局索引
    • 優點：讀取有效率，可以從單個分區中進行讀取。
    • 缺點
      • 寫入慢、複雜，需要更新多個分區中的次級索引
      • 索引異步更新會有延遲

• 分區再平衡

  • 數據庫可能的瓶頸
  • 吞吐量增加: 增加 CPU 來處理負載
  • 數據集增加: 添加磁盤、RAM 儲存
  • 機器故障: 其他機器替補

• 再平衡應達成的事情

  • 負載均衡
  • 0 downtime
  • 只移動必須數據

• 再平衡策略

  • 反面教材 hash mod N：節點變動時會移動太多不必要移動的數據
  • 固定數量的分區
  • 動態分區
  • 按節點比例分區

• 請求路由

  • 將請求路由到正確節點的三種不同方式
    • 聯系任何節點
    • 發送到路由層
    • 客戶端知道分區和節點的分配
  • 分配解法
    • 中介協調服務, ex: ZooKeeper
    • 流言協議（gossip protocol）
    • 配置路由層

[at7211]

• partition 主要的關鍵在於如何有效地將資料做分區，可能會遇到的 issue 就有如 hot spot/skew 等資料分區不均勻的狀況
• 對應自己的資料特性以及業務需求，去應對該如何將資料做分區。可以依照資料的傾斜程度、資料同步、寫入速度去做衡量
• partition 後查詢時就會變得比單機查詢更複雜，通常會依賴如 zookeeper 去 track 分區的資料 metadata

[samwu4166]

現在主要的兩種分割槽方法:

• Range Partition
• Hash Partition

固定配置分割槽:

例如，執行在 10 個節點的叢集上的資料庫可能會從一開始就被拆分為 1,000 個分割槽，因此大約有 100 個分割槽被分配給每個節點。

這樣當節點變多的時候，可以從『每個節點』把多的分割槽讓給新的節點即可

Ex. Riak 【15】、Elasticsearch 【24】、Couchbase 【10】和 Voldemort 【25】

動態配置分割槽:

例如 HBase，一開始指會有一個分割槽，且上限是 10GB，如果資料超過了，就會動態配置一個，並且讓兩個分割槽儲存差不多量的資料。並且會依據分割槽容量的減少來一併縮減分割槽。

Ex. RethinkDB, MongoDB(2.4後支援)

Cassandra 和 Ketama 使用的第三種方法是使分割槽數與節點數成正比 。在這種情況下，每個分割槽的大小與資料集大小成比例地增長，而節點數量保持不變，但是當增加節點數時，分割槽將再次變小。當一個新節點加入叢集時，它隨機選擇固定數量的現有分割槽進行拆分，然後佔有這些拆分分割槽中每個分割槽的一半，同時將每個分割槽的另一半留在原地。

再平衡的觸發方法:

• 手動 - 雖然有系統可以幫忙提出分割建議讓使用者提交，可是可能發現就來不及
• 自動 - 再平衡是一個昂貴的操作，因為它需要重新路由請求並將大量資料從一個節點移動到另一個節點。如果沒有做好，這個過程可能會使網路或節點負載過重，降低其他請求的效能。

服務發現（service discovery）

• 迴圈策略的負載均衡 即 Round-Robin Load Balancer）。如果該節點恰巧擁有請求的分割槽，則它可以直接處理該請求；否則，它將請求轉發到適當的節點，接收回復並傳遞給客戶端。
• 主要就是看要把 routing 表放到哪一個層級使用
  • 現代分散式系統都會有一個獨立出來的調配中介，如 Zookeeper
    • 每個節點在 ZooKeeper 中註冊自己，ZooKeeper 維護分割槽到節點的可靠對映。 其他參與者（如路由層或分割槽感知客戶端）可以在 ZooKeeper 中訂閱此資訊。

[AK4codee]

分區類型

• RANGE分區：基於屬於一個給定連續區間的列值，把多行分配給分區。

  CREATE TABLE tbl_test (
  　　uuid INT NOT NULL,
  　　title VARCHAR(20)
  )
  PARTITION BY RANGE (uuid) (
  PARTITION p0 VALUES LESS THAN (5),
  PARTITION p1 VALUES LESS THAN (10),
  PARTITION p2 VALUES LESS THAN (15),
  PARTITION p3 VALUES LESS THAN MAXVALUE
  );

• LIST分區：類似於RANGE分區，LIST是列值匹配一個離散值集合中的某個值來進行選擇。

  CREATE TABLE tbl_test (
  uuid INT NOT NULL,
  title VARCHAR(20)
  )
  PARTITION BY List (uuid) (
  PARTITION p0 VALUES in (1,2,3,5),
  PARTITION p1 VALUES in (7,9,10),
  PARTITION p2 VALUES in (11,15)
  );

• HASH分區：基於用戶定義的表達式的返回值來進行選擇分區，該表達式使用將要插入到表中的這些行的列值來進行計算，這個函數必須產生非負整數值。

  CREATE TABLE tbl_test (
  uuid INT NOT NULL,
  title VARCHAR(20)
  )
  PARTITION BY HASH (uuid) (
  PARTITIONS 3
  );

  分區再平衡

  需求

• 要盡量平均分散
• 不能中斷請求
• 只移動必要的資料

  方式

• 固定區數
• 固定區長
• 固定個節點區數

[Parkerhiphop]

Why Partitioning? → Scalability

1. 過大的資料集 or 過高的吞吐量
2. Replication 會產生極高的延遲
3. 需要將資料分成 Partition（分割） or Sharding（分片）

What?

• Partitioning 是有意將大型資料庫分解成小型資料庫的方式

兩種主要的 Partitioning Approach

1. Key Range：查詢快，但也有熱點風險
2. Hash：查詢曼，但較均衡附載
3. **使用複合 Primary Key 並行

• Skewed & Hot Spot 仍然棘手

Partitioning & Secondary Index

1. Document-based (Local Index): 寫入單個，讀取時要多個
2. Term-based(Global Index): 寫入在多個，讀取時可單個

Request Routing 的三種做法

1. 讓 Client 自由聯絡任何節點：用迴圈策略的負載平衡
2. 做一個 Router Layer
3. Client 本身就知道 Partition 和 Node 要打哪個

如何知道要打哪個？

1. 統一的協調服務，如 ZooKeeper
2. Gossip Protocol，運用做法 1

[jxiu0129]

1. key-value partition
   • 鍵值範圍
   • hash map
     2. partition rebalance
   • （固定）建立比節點更多的分割槽，併為每個節點分配多個分割槽
   • （動態）當分割槽增長到超過配置的大小時，會被分成兩個分割槽，每個分割槽約佔一半的資料。與之相反，如果大量資料被刪除並且分割槽縮小到某個閾值以下，則可以將其與相鄰分割槽合併
   • （按節點比例）每個節點具有固定數量的分割槽。在這種情況下，每個分割槽的大小與資料集大小成比例地增長，而節點數量保持不變，但是當增加節點數時，分割槽將再次變小
2. 請求路由 - zookeeper

[taco0929]

分區

將儲存分散在（多個）硬碟並分散查詢的處理器 範圍分區： 以鍵的最大、最小值分配分區範圍 散列分區： 以鍵（如哈希值或散射函數）平均分配

• 平衡偏斜 可為熱點分區建立副本
• 使用次級索引
  • 全局索引可能導致尾部延遲放大
  • 以次級索引分區可能導致索引更新延遲 分區再平衡
• 負載應於各節點平均分配
• 再平衡發生時，資料庫仍能進行讀寫
• 只移動必須的數據
• examples:
  • 固定數量分區
  • 動態分區
  • 按結點比例分區 路由請求
• 允許用戶查詢任何節點，若該分區無資料可將請求轉發
• 以路由層決定將請求發送給哪個節點
• 客戶於查詢時須先知道分區與節點的分配

[Jay0328]

Partition

Why

• 過大的數據量
• 過大的 throughput
• Replication 會產生極高的 latency

How

將大 database 切分為較小 database，增加 scalability，並可以放在不同 nodes 中

Term

• 偏斜(skew) - 如果分區是不公平的，一些分區比其他分區有更多的數據或查詢
• 熱點(hot spot) - 不均衡導致的高負載分區
• 分散 / 聚集（scatter/gather）- 查詢分區 database 的方法

Partition Method/Strategy

• Key Range
  • props
  • range scan 簡單，相近的資料都在同個分區
  • cons
  • 如果使用 timestamp 之類的可能會造成 hot spot，可以組合多個 columns 當作 key 來解決
• Hash of Key
  • props
  • 較 range 方法平均隨機
  • cons
  • range scan cost 較大，需要 scan 較多的分區

Hot Spot 消除

目前 database 無法自動檢測和補償高度 skew 的情況，需要在 application layer 額外實作

Ex: 社群網站上一個有百萬追蹤者的名人在做某事時

解法: 在 index 的開始或結尾加上隨機數

• cons
  • 可能造成額外紀錄的開銷
  • Query 時也需要額外的處理

Secondary Index

• Document Based
  • Local Index - 每個分區完全獨立，各自維護自己的 index
  • cons
  • query 效率差
    • 因 scatter，容易有 tail latencies
• Term Based
  • Global Index
  • props
  • range scan 簡單，term 中的資料都在同個分區
  • cons
  • 寫入速度慢且複雜
  • 需要更新多個分區，index 異步更新會有延遲

Rebalancing

• 固定，建立比 node 更多的分區，並為每個 node 分配多個分區，node 變多時把多的分區分給新的 node
• 動態，根據資料量動態 分割/合併 分區
• 按 node 比例，每個分區大小與資料大小成比例而 node 數量不變，當增加 node 時分區將再次變小
  • 分區大小較為穩定

Manual or Auto

• Manual
  • 較保險
  • 雖然有系統會幫忙計算好只需要人工 approve，但是可能錯過時機點
• Auto
  • 較方便
  • 如有 node 過載而響應的很慢，其他 nodes 會認為該 node 已死亡，有造成級聯失效的可能性

Routing

• 讓 client 自由聯絡任何 node，循环策略的負載均衡 - Round-Robin Load Balancer
• 做一個 Routing Layer 的 middleware
• Client 本身就知道 partition 和 node 在哪
  • cons
  • 需依賴於 service discovery 之類的機制