Database Partitioning Strategies

Difficulty: Advanced

Question

Explain database partitioning strategies. When would you use range-based vs hash-based partitioning?

Answer

Database partitioning splits a large table across multiple storage units to improve performance and manageability.

Types: 1. Horizontal Partitioning (Sharding): Split rows across databases. Row with id=1 on Shard A, id=2 on Shard B. 2. Vertical Partitioning: Split columns across tables. Frequently accessed columns in one table, large/rarely-used columns in another.

Sharding strategies: - Range-based: Shard by value range (users A-M on Shard 1, N-Z on Shard 2). Simple but prone to hotspots. - Hash-based: hash(key) % num_shards. Even distribution but range queries require scatter-gather. - Directory-based: Lookup table maps each key to a shard. Flexible but the directory is a bottleneck. - Geographic: Data stored in the region closest to the user. Good for compliance and latency.

Key challenges: cross-shard queries, distributed joins, rebalancing, maintaining uniqueness across shards.

Code examples

Sharding Strategies Compared

// RANGE-BASED sharding
// Shard 1: user_id 1 - 1,000,000
// Shard 2: user_id 1,000,001 - 2,000,000
// Shard 3: user_id 2,000,001 - 3,000,000

function getRangeShard(userId) {
  if (userId <= 1_000_000) return 'shard-1';
  if (userId <= 2_000_000) return 'shard-2';
  return 'shard-3';
}

// Pros: Range queries stay on one shard
//        SELECT * FROM users WHERE id BETWEEN 500 AND 600
// Cons: Newest users all on one shard (hotspot)
//        Uneven data distribution over time

// HASH-BASED sharding
function getHashShard(userId, numShards) {
  const hash = murmurHash(String(userId));
  return `shard-${hash % numShards}`;
}

// Pros: Even data distribution
// Cons: Range queries need scatter-gather across ALL shards
//        Adding shards requires rehashing (use consistent hashing)

// DIRECTORY-BASED sharding
// Lookup table: userId -> shardId
// Stored in a fast cache (Redis)
async function getDirectoryShard(userId) {
  let shard = await redis.get(`shard_map:${userId}`);
  if (!shard) {
    shard = assignShard(userId);  // Logic to pick shard
    await redis.set(`shard_map:${userId}`, shard);
  }
  return shard;
}

// Pros: Flexible, can move individual users between shards
// Cons: Directory is a single point of failure and bottleneck

Each strategy has different trade-offs. Range-based is good for ordered queries. Hash-based ensures even distribution. Directory-based offers maximum flexibility at the cost of an extra lookup.

Vertical Partitioning Example

-- BEFORE: One large users table
CREATE TABLE users (
  id SERIAL PRIMARY KEY,
  name VARCHAR(100),
  email VARCHAR(255),
  password_hash VARCHAR(255),
  -- Frequently accessed above, rarely accessed below
  bio TEXT,
  avatar_url VARCHAR(500),
  resume BYTEA,           -- Large binary data
  settings JSONB,
  login_history JSONB,    -- Can grow very large
  created_at TIMESTAMP
);

-- AFTER: Vertical partitioning
-- Hot table: frequently queried, small rows
CREATE TABLE users (
  id SERIAL PRIMARY KEY,
  name VARCHAR(100),
  email VARCHAR(255),
  password_hash VARCHAR(255),
  created_at TIMESTAMP
);

-- Warm table: occasionally accessed
CREATE TABLE user_profiles (
  user_id INT PRIMARY KEY REFERENCES users(id),
  bio TEXT,
  avatar_url VARCHAR(500),
  settings JSONB
);

-- Cold table: rarely accessed, large data
CREATE TABLE user_documents (
  user_id INT PRIMARY KEY REFERENCES users(id),
  resume BYTEA,
  login_history JSONB
);

-- Benefits:
-- 1. users table fits more rows in memory (smaller row size)
-- 2. Most queries only hit the small users table
-- 3. Large BLOBs don't slow down simple lookups
-- 4. Can store cold data on cheaper/slower storage

Vertical partitioning separates frequently accessed columns from large, rarely accessed ones. This improves cache efficiency since more hot rows fit in memory, and allows different storage tiers for hot and cold data.

Cross-Shard Query Pattern

// Challenge: queries that span multiple shards

// Scatter-gather pattern for cross-shard search
async function searchUsersAcrossShards(query, limit = 20) {
  const shards = getAllShards(); // ['shard-1', 'shard-2', 'shard-3']

  // Scatter: send query to all shards in parallel
  const results = await Promise.all(
    shards.map(shard =>
      queryOnShard(shard, {
        sql: 'SELECT * FROM users WHERE name ILIKE $1 ORDER BY created_at DESC LIMIT $2',
        params: [`%${query}%`, limit]
      })
    )
  );

  // Gather: merge results from all shards
  const merged = results
    .flat()
    .sort((a, b) => b.createdAt - a.createdAt)
    .slice(0, limit);

  return merged;
}

// Challenge: unique IDs across shards
// Solution 1: UUID (no coordination needed)
// Solution 2: Snowflake ID (timestamp + machine + sequence)
function generateSnowflakeId(machineId) {
  const timestamp = Date.now() - EPOCH;  // Custom epoch
  const sequence = getNextSequence();     // Per-machine counter
  // 41 bits timestamp | 10 bits machine | 12 bits sequence
  return (BigInt(timestamp) << 22n)
    | (BigInt(machineId) << 12n)
    | BigInt(sequence);
}

// Snowflake IDs are:
// - Globally unique without coordination
// - Sortable by time (timestamp is the high bits)
// - Used by Twitter, Discord, Instagram

Cross-shard queries use the scatter-gather pattern: send the query to all shards, merge results locally. Snowflake IDs generate globally unique, time-sortable IDs without coordination between shards.

Key points

Concepts covered

Sharding, Horizontal Partitioning, Vertical Partitioning, Range Partitioning, Hash Partitioning