Caching, Search, OLTP vs OLAP

1. Vì sao caching?

Latency hierarchy (đại khái 2026):

Đọc Postgres qua mạng đã ~1ms (network + parse + plan + exec). Cùng query cache vào Redis: ~50µs. Cache vào RAM app (in-memory): ~10ns.

Cache giảm latency và giảm tải DB — nếu cache hit 95%, DB chỉ phải xử lý 5% traffic.

1.1. Cache đặt ở đâu?

Mỗi tầng đều có cache: browser HTTP cache (Cache-Control), CDN edge cache, reverse proxy cache (nginx proxy_cache), app in-memory (Map/LRU), distributed cache (Redis/Memcached).

2. Cache Patterns — 4 chiến lược

2.1. Cache-Aside (Lazy Loading)

Phổ biến nhất. App quản lý cache, DB không biết về cache.

async function getUser(id: number) {
  const key = `user:${id}`;
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached);

  const user = await db.query('SELECT * FROM users WHERE id=$1', [id]);
  await redis.set(key, JSON.stringify(user), 'EX', 600);  // TTL 10 phút
  return user;
}

async function updateUser(id: number, data: any) {
  await db.query('UPDATE users SET ... WHERE id=$1', [id]);
  await redis.del(`user:${id}`);   // invalidate
}

Ưu: đơn giản, fail-open (cache chết app vẫn chạy). Nhược: data có thể stale (giữa write và invalidate).

2.2. Write-Through

Cache là "front" của DB. App ghi cache, cache ghi DB đồng bộ.

Ưu: read luôn fresh. Nhược: latency write tăng (chờ cả 2 ghi). Cache miss đầu vẫn phải đọc DB.

2.3. Write-Behind (Write-Back)

App ghi cache, cache async flush DB sau.

Ưu: write rất nhanh. Nhược: nguy cơ mất data nếu cache crash trước khi flush. Phức tạp với consistency.

Dùng cho counter, log, analytics — chấp nhận mất 1-vài giây cuối.

2.4. Refresh-Ahead

Trước khi key sắp expire, cache tự refresh từ DB. Người dùng không bao giờ thấy cache miss.

Phức tạp triển khai, ít dùng. Cloudflare và một số CDN làm dạng này.

3. Cache Invalidation — vấn đề khó nhất

"There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton

3.1. Khi nào invalidate?

• TTL (Time-to-Live) — set TTL khi cache, key tự xóa. Đơn giản nhất, an toàn nhất. Nhược: data có thể stale đến TTL.
• Event-based — khi UPDATE/DELETE → DEL key. Cần biết tất cả key liên quan.
• Versioning — key có version: user:5:v123. Update → tăng version → key cũ bị orphan, tự expire qua TTL.

3.2. Cascade invalidation

1 record có thể được cache ở nhiều key/view:

user:5
user:5:profile
home_feed:user:5
search_result:term:"alice"   ← chứa user 5
team:42:members              ← chứa user 5

Update user 5 → phải invalidate cả 5 key. Cách:

• Set TTL ngắn (chấp nhận stale).
• Pattern key + scan + del (chậm).
• Tag system (Redis 7+ hash tags) hoặc Memcached "cache groups".
• Pub/Sub event → mọi cache subscriber tự invalidate.

3.3. Stale-while-revalidate

Khi cache miss, trả ngay stale value, đồng thời trigger background refresh. User không phải chờ.

async function get(key: string) {
  const cached = await redis.get(key);
  if (cached) {
    const { value, expires_at } = JSON.parse(cached);
    if (Date.now() > expires_at - 30_000) {
      // sắp hết hạn, trigger refresh background:
      void refresh(key);
    }
    return value;
  }
  return await refresh(key);  // miss thật, blocking
}

4. Cache Stampede / Thundering Herd

Khi 1 hot key expire cùng lúc 1000 request đến → 1000 request đồng thời đập vào DB.

4.1. Giải pháp

• Lock / single-flight — chỉ 1 request rebuild cache, các request khác chờ kết quả.
• Stale-while-revalidate — trả stale, background refresh.
• Probabilistic early expiration — refresh trước khi expire, theo xác suất tăng dần khi gần expire.
• TTL jitter — TTL không phải con số cố định mà ± 10% random → tránh expire đồng loạt.

// Single-flight pattern với Redis SETNX:
async function get(key: string) {
  const cached = await redis.get(key);
  if (cached) return cached;

  const lockKey = `lock:${key}`;
  const acquired = await redis.set(lockKey, '1', 'NX', 'EX', 5);
  if (!acquired) {
    await sleep(50);
    return get(key);  // request khác đang rebuild, chờ rồi đọc
  }

  try {
    const value = await fetchFromDb();
    await redis.set(key, value, 'EX', 600);
    return value;
  } finally {
    await redis.del(lockKey);
  }
}

5. Redis làm cache — best practice

5.1. TTL chiến lược

# Hot data, đổi nhanh: 1-5 phút
SET user:5:online 1 EX 300

# Static-ish: 1 giờ
SET product:1 "{...}" EX 3600

# Reference data hiếm đổi: 1 ngày
SET country:VN "Việt Nam" EX 86400

5.2. Eviction policies

Khi Redis hết RAM (vượt maxmemory), eviction policy quyết định xóa key nào:

• noeviction — báo lỗi khi full (default).
• allkeys-lru — least recently used trên mọi key. Phổ biến nhất cho cache.
• allkeys-lfu — least frequently used.
• volatile-lru — LRU chỉ trên key có TTL.
• allkeys-random — xóa ngẫu nhiên.

# redis.conf:
maxmemory 4gb
maxmemory-policy allkeys-lru

5.3. Cache key naming

{namespace}:{type}:{id}:{detail}

user:profile:5
user:settings:5
post:42:comments:page:1
search:result:hash(query)
session:abc123

5.4. Pipeline & batch

// ❌ N round-trip:
for (const id of ids) {
  await redis.get(`user:${id}`);
}

// ✓ 1 round-trip với MGET:
const values = await redis.mget(ids.map(id => `user:${id}`));

// ✓ Pipeline cho mixed commands:
const pipe = redis.pipeline();
for (const id of ids) pipe.get(`user:${id}`);
const results = await pipe.exec();

6. Search & Inverted Index

"Tìm bài viết có từ 'database'" — không thể quét toàn bộ với LIKE '%database%' trên TB content.

6.1. Inverted Index

"Inverted" = ngược: từ → các document chứa từ đó (như index sách giáo khoa).

6.2. Pipeline xử lý text

1. Tokenization — chia chuỗi thành từ.
2. Lowercasing — "Database" = "database".
3. Stop words removal — bỏ "the", "is", "a"...
4. Stemming / Lemmatization — "running" → "run", "ran" → "run".
5. Synonyms — "PG" = "Postgres".
6. N-gram — cho fuzzy / typo (xem 6.3).

6.3. Fuzzy / typo search — Trigram

Chia từ thành n-gram (vd: 3-gram):

"database" → "dat", "ata", "tab", "aba", "bas", "ase"
"databse"  → "dat", "ata", "tab", "abs", "bse"
                ↑↑↑   ↑↑↑   ↑↑↑    chung 3 trigram → similar

Postgres extension pg_trgm dùng trigram cho fuzzy search.

6.4. Ranking — TF-IDF, BM25

Khi 1 query match nhiều document, làm sao xếp hạng độ liên quan?

• TF (Term Frequency) — từ xuất hiện nhiều = liên quan hơn.
• IDF (Inverse Document Frequency) — từ ở ít doc = mang nhiều thông tin hơn.
• TF-IDF = TF × IDF.
• BM25 — cải tiến TF-IDF, mặc định ở Elasticsearch.

7. Elasticsearch / OpenSearch

Search engine mặc định cho web modern. Built trên Apache Lucene (Java). Distributed bằng cách shard inverted index.

7.1. Cấu trúc cơ bản

• Index — tương đương "table" — lưu một loại document.
• Document — JSON.
• Field — column trong document, có type (text, keyword, date, geo, ...).
• Mapping — schema cho field (kiểu, analyzer).
• Shard — index chia thành shard, replicate.

7.2. text vs keyword

{
  "mappings": {
    "properties": {
      "title": { "type": "text" },         // analyze → tokens, dùng full-text search
      "tags":  { "type": "keyword" },      // không analyze, exact match (filter)
      "name":  {
        "type": "text",
        "fields": { "raw": { "type": "keyword" } }   // dual: search + sort
      }
    }
  }
}

7.3. Query DSL

// Index document:
PUT /posts/_doc/1
{ "title": "Postgres database tutorial", "tags": ["sql","db"] }

// Full-text:
POST /posts/_search
{
  "query": {
    "match": { "title": "database" }
  }
}

// Multi-field + filter:
POST /posts/_search
{
  "query": {
    "bool": {
      "must":   [{ "match": { "title": "tutorial" }}],
      "filter": [{ "term":  { "tags": "sql" }}]
    }
  },
  "sort": [{ "_score": "desc" }],
  "from": 0, "size": 20
}

7.4. Khi nào dùng Elasticsearch?

• Full-text search yêu cầu cao (relevance, ranking, highlighting).
• Log aggregation (Elastic Stack: Logstash, Kibana).
• Geo search.
• Analytics realtime.

Sync với primary DB qua CDC (Debezium đọc Postgres WAL → Kafka → Elastic) hoặc app tự index khi write.

8. Postgres tsvector + GIN — search nhẹ

Khi search là feature phụ, không cần Elastic riêng:

-- Cột generated tự cập nhật search vector:
ALTER TABLE posts ADD COLUMN search tsvector
  GENERATED ALWAYS AS (
    setweight(to_tsvector('simple', coalesce(title, '')), 'A') ||
    setweight(to_tsvector('simple', coalesce(body,  '')), 'B')
  ) STORED;

CREATE INDEX idx_posts_search ON posts USING GIN(search);

-- Query:
SELECT id, title, ts_rank(search, query) AS rank
FROM posts, to_tsquery('simple', 'postgres & tutorial') AS query
WHERE search @@ query
ORDER BY rank DESC LIMIT 20;

-- Highlight:
SELECT ts_headline('simple', body, query) FROM posts ...;

-- Trigram fuzzy:
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_posts_title_trgm ON posts USING GIN(title gin_trgm_ops);
SELECT * FROM posts WHERE title % 'databse'   -- typo OK
ORDER BY similarity(title, 'databse') DESC;

Ưu: cùng DB, không cần sync. Nhược: ít feature hơn Elastic (synonyms, multi-language pluggable, advanced ranking).

Quy tắc thực dụng: search là feature phụ → Postgres tsvector. Search là core (e-commerce, content site) → Elastic.

9. OLTP vs OLAP — hai thế giới khác nhau

9.1. Row vs Column storage

9.2. Vì sao columnar nén tốt?

Cùng cột → giá trị tương tự (toàn bộ là email format, age từ 18-100, ...). Run-length encoding, dictionary encoding, delta encoding đạt 10-50× compression. Disk đọc ít → query nhanh.

10. Data Warehouse vs Data Lake vs Lakehouse

10.1. Data Warehouse

DB chuyên cho analytics. Schema chặt, ETL trước khi load.

• BigQuery (GCP) — serverless, columnar, query-as-a-service.
• Snowflake — multi-cloud, separation of compute and storage.
• Redshift (AWS) — cluster-based.
• ClickHouse — open-source, cực nhanh, dùng nội bộ Yandex.
• DuckDB — embedded OLAP "SQLite cho analytics".

10.2. Data Lake

Lưu raw file (CSV, JSON, Parquet) trên S3/GCS. Query qua Spark, Trino, Athena. Linh hoạt nhưng query không nhanh bằng warehouse.

10.3. Lakehouse

Kết hợp: lưu Parquet trên object storage + thêm metadata layer (Delta Lake, Apache Iceberg, Hudi) để có ACID, schema, time-travel.

Databricks, Snowflake Iceberg là các sản phẩm Lakehouse phổ biến.

11. Star Schema & Snowflake Schema

11.1. Fact table & Dimension table

OLAP schema có 2 loại bảng:

• Fact table — sự kiện đo được. Mỗi row = 1 sự kiện. Cột = (foreign keys to dimensions, measures).
• Dimension table — đối tượng mô tả: thời gian, khách hàng, sản phẩm, địa lý.

Hình như ngôi sao → "Star schema". Fact ở giữa, dimension xung quanh.

11.2. Star vs Snowflake

• Star — dimension flat (denormalized). Đơn giản, query nhanh.
• Snowflake — dimension được normalize tiếp (vd: city là bảng riêng, FK tới dim_geography). Đỡ trùng nhưng query chậm hơn.

Đa số chọn Star — vì OLAP thiên về read, denormalized OK.

11.3. Slowly Changing Dimensions (SCD)

Thuộc tính dimension thay đổi theo thời gian (customer đổi địa chỉ). Cách handle:

• SCD Type 1 — overwrite, mất history.
• SCD Type 2 — thêm row mới với valid_from/valid_to. Giữ history đầy đủ.
• SCD Type 3 — thêm cột "previous_value".

SCD Type 2 phổ biến nhất cho fact-based analytics — báo cáo phải reflect state tại thời điểm sự kiện.

12. ETL vs ELT — đưa data vào warehouse

ELT hiện đại hơn — warehouse như BigQuery, Snowflake compute mạnh, transform bằng SQL dễ debug, version qua git.

12.1. CDC — Change Data Capture

Streaming thay batch. Đọc Postgres WAL (logical replication) → Kafka → consumer (Elastic, Snowflake, Redshift).

• Debezium — open-source CDC từ Postgres/MySQL/Oracle.
• AWS DMS — managed.
• Fivetran, Airbyte — SaaS connector.

Pattern hiện đại: source DB (Postgres OLTP) → CDC → Kafka → analytics warehouse + search engine + cache. Cùng 1 source-of-truth, nhiều consumer.

13. Bài tập

1. Implement cache-aside cho endpoint GET /user/:id với Redis. Đo cache hit rate và latency.
2. Mô phỏng cache stampede: tắt key hot, gửi 1000 request đồng thời. Quan sát DB. Áp dụng single-flight, đo lại.
3. Tạo bảng posts trong Postgres + tsvector + GIN. Test full-text search vs LIKE '%term%' trên 1M dòng.
4. Thiết kế star schema cho analytics e-commerce: fact_orders + dim_customer + dim_product + dim_date.
5. Phân biệt: khi nào dùng Postgres tsvector, khi nào cần Elasticsearch riêng?
6. So sánh row vs column storage qua ví dụ SELECT AVG(price) FROM products với 100M dòng — tại sao columnar nhanh hơn 50×?

14. Quiz