跳到主要內容
Jasonmel Online

系統設計

把資料結構放大到好幾台機器

主題 · 分割與分片

分割與分片

垂直切分把欄位或功能拆到不同的表和資料庫，讓常用的資料更小、更容易進快取；水平分片則依某個鍵把列切到好幾台機器。切法決定了查詢要問幾台，也決定了會不會有一台特別忙。

水平分片：把「列」分到不同機器

切法
寫入
4
已存的 ID（0 到 99,999），依所在分片著色；括號是「最新 1%」查詢的範圍
099,999
20,000 筆新寫入落在哪一片
  • S1
    0
  • S2
    0
  • S3
    0
  • S4
    20,000

虛線：完全平均時每片該分到的量。

最忙／平均
4.00×
「最新 1%」要問幾片
1
連續 1,000 個 ID 要問幾片
2
上次加一片：搬動
—

每個新 ID 都比已存的大，所以 20,000 筆寫入全部落在第 4 片：一台扛 100%，其他台閒著。但「最新 1%」的查詢只要問 1 片。

亮起來的是這一步執行的程式碼
function fnv1a(key: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < key.length; i++) {
    h = Math.imul(h ^ key.charCodeAt(i), 0x01000193);
  }
  return h >>> 0;
}
 
class ShardRouter {
  // bounds[i] is the first key of shard i + 1, sorted.
  constructor(private shards: number, private bounds: number[]) {}
 
  rangeShard(key: number): number {
    let lo = 0, hi = this.bounds.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.bounds[mid] <= key) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
 
  hashShard(key: number): number {
    return fnv1a(String(key)) % this.shards;
  }
 
  // Which shards a query for keys in [lo, hi] must ask.
  shardsForRange(lo: number, hi: number, scheme: string): number[] {
    if (scheme === "hash") {
      return [...Array(this.shards).keys()];
    }
    const first = this.rangeShard(lo);
    const last = this.rangeShard(hi);
    const out: number[] = [];
    for (let s = first; s <= last; s++) out.push(s);
    return out;
  }
}
// Vertical partitioning: hot columns in one table, cold ones in another.
const HOT_COLUMNS = ["id", "email", "password_hash", "display_name", "last_login"];
 
function splitRow(row: Record<string, unknown>) {
  const hot: Record<string, unknown> = {};
  const cold: Record<string, unknown> = { id: row.id };
  for (const [column, value] of Object.entries(row)) {
    (HOT_COLUMNS.includes(column) ? hot : cold)[column] = value;
  }
  return { hot, cold };
}
 
// A database reads whole pages: narrow rows pack more to a page.
function pagesToScan(rows: number, rowBytes: number, pageBytes = 8192): number {
  const perPage = Math.max(1, Math.floor(pageBytes / rowBytes));
  return Math.ceil(rows / perPage);
}
 
// Functional partitioning: each table lives in its domain's database.
const DATABASE_FOR: Record<string, string> = {
  users: "users-db", orders: "orders-db", order_items: "orders-db", events: "analytics-db",
};
 
function databasesFor(tables: string[]): string[] {
  return [...new Set(tables.map((t) => DATABASE_FOR[t]))].sort();
}

垂直切分：把「欄」或「功能」分開

使用者表
查詢
  • 熱id8 B
  • 熱email48 B
  • 熱password_hash60 B
  • 熱display_name32 B
  • 熱last_login8 B
  • 冷bio1,200 B
  • 冷settings_json1,800 B
  • 冷avatar_thumb4,000 B
每頁 8 KiB 放 1 列
查詢次數
1
讀了幾頁
1,000
讀進來／用到
7.8 MiB / 39 KiB
快取放得下幾人的登入資料
8,192 / 100,000

列出 1,000 位使用者只需要名字和最後登入時間，共 39 KiB。一張寬表裡每列 7,156 bytes、一列就塞滿一頁，資料庫要讀 1,000 頁（7.8 MiB），真正用到的只有 0.5%。

依功能切：每個領域一個資料庫

資料庫
  • 結帳：寫訂單和明細orders-db1 次往返
  • 登入：查使用者users-db1 次往返
  • 每日活躍人數：掃事件analytics-db1 次往返
  • 各國營收：使用者 × 訂單orders-dbusers-db2 次往返，在應用程式裡 JOIN

每個資料庫可以依自己的負載挑規格、調參數、擴充，分析的大量掃描也不再和結帳搶同一顆磁碟。代價是跨領域的問題要查兩次、在程式裡 JOIN，也沒有一個交易能同時涵蓋兩邊。

亮起來的是這一步執行的程式碼
function fnv1a(key: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < key.length; i++) {
    h = Math.imul(h ^ key.charCodeAt(i), 0x01000193);
  }
  return h >>> 0;
}
 
class ShardRouter {
  // bounds[i] is the first key of shard i + 1, sorted.
  constructor(private shards: number, private bounds: number[]) {}
 
  rangeShard(key: number): number {
    let lo = 0, hi = this.bounds.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.bounds[mid] <= key) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
 
  hashShard(key: number): number {
    return fnv1a(String(key)) % this.shards;
  }
 
  // Which shards a query for keys in [lo, hi] must ask.
  shardsForRange(lo: number, hi: number, scheme: string): number[] {
    if (scheme === "hash") {
      return [...Array(this.shards).keys()];
    }
    const first = this.rangeShard(lo);
    const last = this.rangeShard(hi);
    const out: number[] = [];
    for (let s = first; s <= last; s++) out.push(s);
    return out;
  }
}
// Vertical partitioning: hot columns in one table, cold ones in another.
const HOT_COLUMNS = ["id", "email", "password_hash", "display_name", "last_login"];
 
function splitRow(row: Record<string, unknown>) {
  const hot: Record<string, unknown> = {};
  const cold: Record<string, unknown> = { id: row.id };
  for (const [column, value] of Object.entries(row)) {
    (HOT_COLUMNS.includes(column) ? hot : cold)[column] = value;
  }
  return { hot, cold };
}
 
// A database reads whole pages: narrow rows pack more to a page.
function pagesToScan(rows: number, rowBytes: number, pageBytes = 8192): number {
  const perPage = Math.max(1, Math.floor(pageBytes / rowBytes));
  return Math.ceil(rows / perPage);
}
 
// Functional partitioning: each table lives in its domain's database.
const DATABASE_FOR: Record<string, string> = {
  users: "users-db", orders: "orders-db", order_items: "orders-db", events: "analytics-db",
};
 
function databasesFor(tables: string[]): string[] {
  return [...new Set(tables.map((t) => DATABASE_FOR[t]))].sort();
}

模型假設與範圍

  • 這是可重現的教學模型；延遲、容量、故障率與工作負載是設定或樣本，不能直接當作正式系統的效能承諾。
  • 範圍或雜湊把鍵分配到固定分片；比較查詢觸及的分片和負載。未模擬線上搬遷、跨分片交易與故障選主。

什麼時候用

  • 資料或寫入量大到一台機器放不下或扛不住：先試過加記憶體、讀取副本和快取，真的不夠才切。
  • 常常查一段連續的鍵（時間範圍、字母順序）時用範圍切；只做單筆查找、最怕熱點時用雜湊切。
  • 切的鍵要選大部分查詢都會帶的欄位（例如使用者 ID），這樣一次查詢只需要問一片。
  • 垂直切分通常比水平分片早用到：少數大欄位（文章內容、圖片、JSON 設定）拖慢常用查詢時，先把它們搬出去；不同業務互相搶資源時，再依功能拆成不同資料庫。

和其他主題的關係

出現在這些架構裡

時間與空間複雜度（Big O）

操作平均最差
找到鍵在哪一片：依範圍
N 是分片數；在邊界陣列上二分搜尋
O(log N)O(log N)
找到鍵在哪一片：依雜湊O(1)O(1)
範圍查詢要問的分片：依範圍
範圍越寬跨越的片越多
O(1)O(N)
範圍查詢要問的分片：依雜湊O(N)O(N)
加一片要搬的資料（K 是總筆數）
依範圍切開一片是 K/N 的一半；依雜湊重算 mod 幾乎全部要搬
O(K / N)O(K)
垂直：只讀熱欄位、掃 m 列的頁數
h 是熱欄位寬度、P 是頁大小：熱欄位分開後一頁放 52 列；沒分開時每列都塞滿一頁，就是 O(m)
O(m·h / P)O(m)
垂直：需要全部欄位的查詢
熱表一次、冷表一次（或一次 JOIN）；依功能切開到不同資料庫時就是兩次網路往返
2×2×

空間：O(K)，水平：每片約 K/N 筆，再加上一份很小的路由表；垂直：總量不變，只是熱欄位和冷欄位分開放

Big O 實測：n 變大時步數怎麼長

數的是：n 是分片數：路由一個鍵的比較次數、查連續 10 個 ID 要問的片數

Big On = 4n = 16n = 64n = 256成長倍數：實測（理論）
依範圍：路由（二分搜尋）O(log n)2468×4.0 (×4.0)
依雜湊：路由O(1)1111×1.0 (×1.0)
依範圍：範圍查詢的扇出O(1)1111×1.0 (×1.0)
依雜湊：範圍查詢的扇出O(n)41664256×64 (×64)

依雜湊在路由上省了幾步二分搜尋，卻在範圍查詢上輸了整整 n 倍：每一片都得問。

和其他做法比

水平：依範圍對依雜湊

最忙／平均：均勻 ID最忙／平均：時間遞增 ID最忙／平均：熱門鍵「最新 1%」要問幾片4 片變 5 片搬動
依範圍1.01×4.00×1.88×112.5%
依雜湊1.02×1.00×1.89×479.7%

4 片、每種工作負載 20,000 筆寫入、已存 100,000 個 ID。依範圍加一片時只切開最後一片；依雜湊加一片時重算 mod 5。熱門鍵那一欄兩種切法都救不了：30% 的流量指向同一個鍵。

垂直：一張寬表對熱冷分開

一張寬表：查詢・頁數熱冷分開：查詢・頁數讀進來的資料
登入1 · 11 · 18.0 KiB → 8.0 KiB
最近 1,000 位使用者1 · 1,0001 · 207.8 MiB → 160 KiB
個人頁（全部欄位）1 · 12 · 28.0 KiB → 16 KiB

使用者表 100,000 列，每列 7,156 bytes，其中常用的熱欄位只有 156 bytes；每頁 8 KiB、資料存在列內。64.0 MiB 的快取在一張寬表時放得下 8,192 人的登入資料，熱冷分開後 100,000 人全部放得下。

真實世界裡的它

  • HBase、Bigtable、CockroachDB、TiDB 依範圍切，並在一片太大時自動切開。
  • Cassandra、DynamoDB 依分區鍵的雜湊切（用一致性雜湊，加機器時不用全部搬）。
  • MongoDB 兩種都支援，由建立 shard key 時選擇。
  • PostgreSQL 會自動把很大的欄位值移到另一張 TOAST（The Oversized-Attribute Storage Technique）表，是資料庫自己做的垂直切分；微服務各自擁有資料庫，則是依功能切。

取捨與陷阱

  • 用遞增的 ID 依範圍切：所有新寫入都擠在最後一片（上面的「依時間遞增的 ID」）。常見解法是在鍵前面加雜湊前綴。
  • 熱門鍵換什麼切法都沒用：一個鍵只在一片上。只能複製多份分散讀取，或把它拆成好幾個子鍵。
  • 跨分片的 JOIN 和交易很貴，要協調好幾台；分片後很多原本一行 SQL 的事要改在應用層做。
  • 用 hash(key) % N 切，N 一變幾乎全部的資料都要搬家；要能擴充就用一致性雜湊或預先切成很多個小分片。
  • 垂直切分後，需要全部欄位的查詢變成兩次查找；依功能切成不同資料庫後，跨領域的查詢要在程式裡 JOIN，也不再有同一個交易保護。