Vì sao Elasticsearch search nhanh: inverted index, Lucene

Câu "vì có inverted index" mới đúng một phần. Elasticsearch nhanh vì nó xếp sẵn dữ liệu theo đúng hình dạng của câu hỏi tìm kiếm, ở nhiều tầng: từ điển term trong RAM, danh sách docId đã sort và nén, segment bất biến dễ cache, cột riêng cho sort/facet, cây riêng cho range, và chia shard chạy song song. Ở bài 6.11 ta đã biết dùng ES (analyzer, mapping, bool query). Bài này mở nắp xem bên trong.

1. Bài toán

shop-app giờ có 5 triệu sản phẩm. Khách gõ:

q        = "áo thun nam cotton"
category = thoi-trang-nam
price    = 100.000 – 300.000
facet    = đếm theo brand, theo size
sort     = độ liên quan, trả 20 kết quả, mong muốn < 50 ms

2. Vấn đề: vì sao B-tree của PostgreSQL không cứu được

Ở bài 6.4, B-tree sắp xếp theo giá trị đầy đủ của cột, đọc từ trái sang. Nó trả lời tốt "name bắt đầu bằng 'Áo thun'" nhưng không trả lời được "name chứa chữ 'cotton' ở đâu đó":

B-tree trên name (sắp theo chuỗi đầy đủ):
  "Áo khoác..." | "Áo sơ mi..." | "Áo thun cotton nam" | "Quần cotton..."
                                          ▲                     ▲
                    "cotton" nằm rải rác giữa chuỗi → không có điểm bắt đầu để seek

WHERE name ILIKE '%cotton%'
→ Seq Scan 5.000.000 dòng × so khớp chuỗi
→ ~5 triệu × ~300 byte ≈ 1,5 GB phải đọc (nếu không nằm hết trong cache)
→ hàng giây, và mỗi request search lại làm lại từ đầu

Kể cả quét xong, SQL chỉ trả lời có/không. Không có khái niệm "sản phẩm này khớp tốt hơn sản phẩm kia" (relevance). Muốn có phải tự viết công thức trong ORDER BY, tính trên mọi dòng khớp.

3. Giải pháp: lật ngược dữ liệu

Thay vì "document → các từ", ta lưu "từ → các document". Đó là inverted index. Elasticsearch (và OpenSearch) là lớp phân tán bọc quanh Apache Lucene; mọi cấu trúc dưới đây là của Lucene.

Bước A. Analyze 3 sản phẩm mẫu (analyzer vi_folding ở bài 6.11):

doc 1: "Áo thun nam Cotton cổ tròn"
doc 2: "Áo thun nữ cotton"
doc 3: "Áo sơ mi nam, áo công sở"

tokenize    → [Áo][thun][nam][Cotton][cổ][tròn]
lowercase   → [áo][thun][nam][cotton][cổ][tròn]
asciifolding→ [ao][thun][nam][cotton][co][tron]
               pos:0   1    2     3     4    5

doc 3 → [ao][so][mi][nam][ao][cong][so]   (pos 0..6)

Bước B. Gom thành term → posting list (docId, term frequency, positions):

term     posting list  (docId : tf : [positions])
───────  ─────────────────────────────────────────
ao     → 1:1:[0]   2:1:[0]   3:2:[0,4]
co     → 1:1:[4]
cong   → 3:1:[5]
cotton → 1:1:[3]   2:1:[3]
mi     → 3:1:[2]
nam    → 1:1:[2]   3:1:[3]
nu     → 2:1:[2]
so     → 3:2:[1,6]
thun   → 1:1:[1]   2:1:[1]
tron   → 1:1:[5]
         ▲
         docId luôn được SORT tăng dần — đây là chìa khóa của mọi thứ phía sau

• tf dùng để chấm điểm (BM25).
• positions dùng cho phrase query: "thun nam" phải có pos(nam) = pos(thun) + 1.
• Với 5 triệu sản phẩm: số term khác nhau chỉ vài trăm nghìn tới vài triệu, mỗi term trỏ tới danh sách docId.

Bước C. Term dictionary + FST: tìm term trong micro-giây

Danh sách term được sort và lưu trên đĩa theo block (term dictionary). Để biết term "cotton" nằm ở block nào mà không đọc đĩa, Lucene giữ trong RAM một term index dạng FST (finite state transducer): một automaton chia sẻ cả tiền tố lẫn hậu tố, rất nhỏ.

FST (rút gọn) cho: co, cong, cotton, mi, nam, nu
          ┌─ n ─▶(g)───────────▶ cong   → block 2
 (start)─c─o─┼─ t ─ t ─ o ─ n ───▶ cotton → block 2
          │  └─ (kết thúc) ─────▶ co     → block 1
          ├─ m ─ i ─────────────▶ mi     → block 3
          └─ n ─┬─ a ─ m ───────▶ nam    → block 3
                └─ u ───────────▶ nu     → block 3
Đi theo từng ký tự: O(độ dài term), không phụ thuộc 5 triệu doc

• Prefix ("cot*"): đi tới nút "c-o-t" rồi liệt kê nhánh con.
• Fuzzy ("coton", 1 lỗi): Lucene dựng một Levenshtein automaton cho "coton" và chạy giao với FST, chỉ đi các nhánh có thể khớp, không thử từng term.
• Regex/wildcard cũng là automaton. Nhưng wildcard đầu (*ton) vẫn phải duyệt nhiều nhánh → chậm, nên dùng n-gram thay vào.

Bước D. Giao posting list cho truy vấn nhiều từ

"ao thun nam cotton" với operator AND = giao 4 danh sách đã sort. Bắt đầu từ danh sách ngắn nhất, nhảy (advance) trên các danh sách còn lại:

Trên 5 triệu doc (số liệu minh họa):
  ao     → 1.800.000 docs
  nam    →   900.000
  thun   →   400.000
  cotton →    60.000   ← dẫn đường

cotton: 12, 87, 305, 1201, ...
thun  : advance(12) → 12 ✓   advance(87) → 90 ✗ (bỏ 87)  ...
nam   : advance(12) → 12 ✓ ...
ao    : advance(12) → 12 ✓ → doc 12 khớp cả 4

Skip list trên posting list:
  level 1:  0 ───────────── 1024 ─────────── 2048 ───▶
  level 0:  0,3,7,12,...   1024,1030,...     2048,...
  advance(1500): nhảy thẳng tới block 1024, không đọc từng phần tử

Kết quả: chi phí tỉ lệ với danh sách hiếm nhất (~60k), không phải 5 triệu.

Nén posting list: docId đã sort nên lưu khoảng cách (delta) thay vì số tuyệt đối:

docIds : 73, 300, 302, 332, 343, 372
delta  : 73, 227,   2,  30,  11,  29     ← số nhỏ
Frame of Reference: chia block 128 số, mỗi block dùng đúng số bit cần
  (max delta 227 → 8 bit/số thay vì 32 bit) → nhỏ ~4 lần, đọc tuần tự, CPU giải nén cực nhanh (SIMD)

Roaring bitmap (cho kết quả filter được cache):
  chia docId theo khối 65.536; khối thưa → mảng short; khối dày → bitmap 8 KB
  AND/OR giữa hai bitmap = phép bit trên CPU

Bước E. Segment: index nhỏ, bất biến

Một Lucene index không phải một file lớn mà là nhiều segment. Mỗi segment là một inverted index hoàn chỉnh, ghi một lần, không bao giờ sửa.

index sản phẩm (doc mới)
     │
     ▼
in-memory buffer  + ghi translog (để không mất khi crash)
     │  refresh (mặc định mỗi 1s)
     ▼
segment mới (trong OS page cache) → TỪ LÚC NÀY MỚI SEARCH THẤY   ← near real-time
     │  flush/commit (định kỳ) → fsync xuống đĩa, translog được cắt
     ▼
seg_1 [big] seg_2 seg_3 seg_4 [nhỏ]   ── merge nền ──▶  seg_5 [big]

UPDATE doc 2  = đánh dấu xóa doc 2 cũ (tombstone, file .liv) + index bản mới vào segment mới
DELETE doc 2  = chỉ đánh dấu; dữ liệu thật biến mất khi merge

Vì sao bất biến lại nhanh:

• Không cần lock khi đọc: segment không đổi, nhiều thread search song song thoải mái.
• Cache bền: OS page cache, filter cache theo segment không bao giờ bị "dơ"; chỉ segment mới cần tính lại.
• Nén mạnh được vì không phải chừa chỗ để sửa tại chỗ (khác B-tree phải split page).
• Cái giá: cập nhật = xóa + thêm, và phải merge.

Bước F. Doc values và BKD tree: phần không phải chữ

Inverted index trả lời "term → doc". Nhưng sort theo giá và đếm facet cần chiều ngược lại "doc → giá trị". Lucene lưu thêm doc values: lưu theo cột trên đĩa (giống columnar DB).

doc values (column-oriented, theo segment)
docId :   0      1      2      3     ...
brand : [coolm][yody ][coolm][owen ]   ← lưu ordinal số + từ điển
price : [199k ][149k ][259k ][399k ]

Facet "đếm theo brand" trên 6.000 doc khớp:
  for docId in matches: count[brand_ord[docId]]++     ← đọc tuần tự 1 cột, không đụng _source

Số và geo (price, location) được index bằng BKD tree (k-d tree theo block): range price 100k–300k đi xuống cây, lấy nguyên các block nằm trọn trong khoảng mà không cần xét từng doc.

                [0 ─────────── 2.000k]
           [0 ── 250k]        [250k ── 2.000k]
     [0─120k]   [120k─250k]   [250k─400k] ...
        ▲ một phần    ▲ nằm trọn → lấy cả block    ▲ một phần → kiểm từng doc

Filter context và filter cache: điều kiện trong filter (category, price, inStock) chỉ trả lời có/không. Lucene cache kết quả thành bitset theo từng segment; lần sau cùng filter chỉ là phép AND bit. Segment bất biến nên cache không bao giờ sai.

bitset category=thoi-trang-nam : 0110 1101 0011 ...
bitset price 100k–300k         : 1110 0101 0111 ...
AND                            : 0110 0101 0011 ...  → rồi mới giao với posting list chữ

Bước G. BM25: thứ SQL không có

Với mỗi doc khớp, cộng điểm của từng term (chỉ ý tưởng, không cần thuộc công thức):

score(doc) = Σ  IDF(term) × tf_saturation(tf) × length_norm(field)

IDF    : "cotton" (60k doc) hiếm hơn "ao" (1,8 triệu) → cotton nặng điểm hơn nhiều
tf     : xuất hiện 2 lần tốt hơn 1 lần, nhưng 20 lần không hơn bao nhiêu (bão hòa, k1)
length : "Áo thun nam cotton" (4 từ) thắng mô tả 300 từ có chứa cotton (b)

Tất cả số liệu cần (df của term, tf, độ dài field đã nén thành 1 byte "norm") đều tính sẵn lúc index. Lúc search chỉ cộng nhân. Thêm nữa, Lucene dùng WAND/block-max: mỗi block posting lưu điểm tối đa có thể đạt, block nào không thể lọt top 20 thì bỏ qua luôn.

Bước H. Phân tán: shard và replica

index "products" = 5 primary shard × 1 replica (mỗi shard = 1 Lucene index ~1 triệu doc)

        client
          │
          ▼
  coordinating node
    │  QUERY phase: gửi song song tới 1 bản (primary HOẶC replica) của mỗi shard
    ├──▶ shard0 ──▶ top 20 (docId, score)
    ├──▶ shard1 ──▶ top 20
    ├──▶ ...    ──▶ ...           + facet count từng phần
    │  merge → top 20 toàn cục, cộng facet
    │  FETCH phase: chỉ lấy _source của 20 doc thắng
    ▼
  response

• Mỗi shard chỉ xử lý 1/5 dữ liệu, chạy cùng lúc → latency ≈ shard chậm nhất.
• Replica nhận read → nhiều traffic thì thêm replica/node (scale ngang).
• Số primary shard cố định khi tạo index (đổi phải reindex/split), nên chọn từ đầu theo kích thước dự kiến (thường 10–50 GB/shard).

4. Ghép lại: đường đi của "áo thun nam cotton"

1. analyze      "áo thun nam cotton" → [ao, thun, nam, cotton]
2. mỗi shard, mỗi segment:
   a. FST tìm 4 term → con trỏ tới 4 posting list           (RAM, µs)
   b. filter: bitset category ∧ bitset price (cache) ∧ inStock  (phép bit)
   c. giao posting list, dẫn bởi "cotton", skip list         (~60k → ~6k doc)
   d. BM25 + block-max bỏ block yếu → giữ top 20
   e. facet brand/size: đọc doc values của ~6k doc
3. coordinating node merge 5 × top 20 → top 20, cộng facet
4. fetch _source 20 doc → JSON
Không bước nào quét 5 triệu doc.

Thử nhanh bằng curl để thấy segment và profile:

curl -s -u "$SEARCH_USER:$SEARCH_PASSWORD" "$SEARCH_URL/_cat/segments/products?v&h=shard,segment,docs.count,docs.deleted,size"
curl -s -u "$SEARCH_USER:$SEARCH_PASSWORD" "$SEARCH_URL/products/_search" \
  -H 'Content-Type: application/json' \
  -d '{"profile":true,"query":{"match":{"name":{"query":"ao thun nam cotton","operator":"and"}}}}'
# profile cho biết thời gian từng bước: build_scorer, next_doc, advance, score

5. So sánh

6. Khi nào ES là tốt nhất / khi nào KHÔNG

• Tốt nhất: search là tính năng chính, dữ liệu lớn, cần relevance, typo, autocomplete, facet, lọc kết hợp; đọc nhiều hơn ghi rất nhiều; chấp nhận trễ vài giây.
• Không phải source of truth: không transaction nhiều doc, không foreign key, có thể mất ghi gần nhất khi sự cố.
• Không cho strong consistency: vừa trừ tồn kho mà đọc từ ES để quyết định bán thì sai.
• Dataset nhỏ (vài trăm nghìn dòng, search phụ): PostgreSQL FTS đủ, không cần thêm cluster.
• Cùng một doc cập nhật liên tục (view count mỗi giây): mỗi update = xóa + thêm + merge, tốn kém. Tách field đó ra hoặc gộp cập nhật.

Vì ES là bản sao eventually consistent, phải có pipeline đưa thay đổi từ PostgreSQL sang: đó là bài 6.13.

Bạn hiểu gần đúng, chỉ cần chỉnh một điểm: phần lớn index nằm trên đĩa, không nằm trong heap. Lucene đọc qua mmap, để OS page cache giữ phần nóng.

Ước lượng thô, 5 triệu sản phẩm, name + description ngắn + vài field keyword/số:
  _source (JSON nén)        ~ 2–3 GB   đĩa, chỉ đọc lúc fetch 20 doc
  inverted index + positions~ 1–2 GB   đĩa → page cache
  doc values (brand, price) ~ 200–400 MB đĩa → page cache
  FST term index            ~ vài chục MB  (off-heap ở bản mới)
  ─────────────────────────
  tổng index ~ 4–6 GB

RAM 8 GB node:
  heap JVM   : 4 GB   (≤ 50% RAM, và < ~31 GB để giữ compressed oops)
  page cache : ~4 GB  ← phần này mới làm search nhanh

• Heap dùng cho request, aggregation, cache. Đừng cho heap ăn hết RAM, vì page cache mới là thứ giữ posting list và doc values "nóng".
• Thứ hay gây hết heap: aggregation terms trên field text với fielddata=true. Facet luôn dùng field keyword (doc values).
• Giảm dung lượng: tắt positions cho field không cần phrase (index_options: docs), "index": false cho field chỉ hiển thị, "doc_values": false cho field không sort/facet.

Vậy 5 triệu sản phẩm là cỡ nhỏ với ES. Production nên 3 node để có replica và master quorum, không phải vì thiếu RAM.

Đúng rồi, đó là near real-time, đúng như sơ đồ segment ở trên:

t=0     PUT /products/_doc/p-1001     → vào buffer + translog → trả 200 OK (đã bền)
t=0..1s search                        → chưa thấy (chưa có segment)
t≈1s    refresh                       → segment mới mở cho reader → thấy
GET /products/_doc/p-1001 (theo id)   → thấy ngay (realtime get đọc translog/refresh riêng)

Tại sao không refresh sau mỗi doc? Mỗi refresh tạo một segment nhỏ. Nhiều segment nhỏ → mỗi search phải duyệt nhiều segment, merge liên tục, cache bị xóa. 1 giây là điểm cân bằng.

• Màn hình admin "lưu xong thấy luôn": gửi ?refresh=wait_for cho request đó (chờ tới lần refresh kế, không ép tạo segment). Tránh refresh=true cho mọi request.
• Bulk import 5 triệu doc: đặt refresh_interval: -1 và number_of_replicas: 0 khi nạp, xong bật lại → nhanh hơn nhiều.
• Index ít đọc: tăng refresh_interval lên 30s để giảm tải.

Ngoài 1 giây này, còn độ trễ từ PostgreSQL sang ES qua pipeline đồng bộ, đo và xử lý ở bài 6.13.

Ý tưởng hấp dẫn, nhưng chính những thứ làm ES nhanh lại làm nó dở khi làm DB:

Kết luận: PostgreSQL giữ sự thật (giá, kho, đơn), ES giữ bản sao được sắp xếp để tìm. Đồng bộ hai nơi là chi phí có chủ đích, và index ES luôn build lại được từ DB.

Q1. Tại sao làm chức năng search thì dùng Elasticsearch?

🇻🇳 Tiếng Việt:

Vì database quan hệ index theo giá trị cả cột bằng B-tree, nên tìm "chứa từ" với LIKE '%x%' phải quét toàn bảng và không có relevance. Elasticsearch dựa trên Lucene, lưu inverted index: term trỏ tới danh sách docId đã sort và nén, tra term qua FST trong RAM, giao các danh sách bằng skip list nên chi phí theo term hiếm nhất chứ không theo số dòng. Nó có sẵn BM25, typo, autocomplete, facet trên doc values, và chia shard chạy song song để scale ngang. Đổi lại nó là near real-time và không phải source of truth, nên em vẫn giữ dữ liệu gốc ở PostgreSQL và đồng bộ sang. Nếu dữ liệu nhỏ, em dùng full-text của PostgreSQL trước.

🇬🇧 English:

A relational database indexes whole column values with a B-tree, so a "contains word" search with LIKE '%x%' scans the whole table and has no relevance. Elasticsearch is built on Lucene and stores an inverted index: each term points to a sorted, compressed list of doc IDs, terms are found through an in-memory FST, and lists are intersected with skip lists, so cost depends on the rarest term rather than the row count. It gives BM25 ranking, typo tolerance, autocomplete and facets on doc values out of the box, and shards run in parallel so it scales horizontally. The trade-off is that it is near real-time and not a source of truth, so I keep the original data in PostgreSQL and sync it over. For small datasets I would start with PostgreSQL full-text search.

Q2. Lucene segment là gì, vì sao bất biến?

🇻🇳 Tiếng Việt:

Một shard là một Lucene index gồm nhiều segment, mỗi segment là một inverted index nhỏ ghi một lần. Doc mới vào buffer và translog, mỗi giây refresh thành segment mới nên mới search thấy, gọi là near real-time. Update và delete chỉ đánh dấu xóa, dữ liệu thật bị bỏ khi merge. Bất biến giúp đọc không cần lock, cache theo segment luôn đúng và nén được mạnh; cái giá là update tốn kém và cần merge nền.

🇬🇧 English:

A shard is a Lucene index made of many segments, and each segment is a small write-once inverted index. New documents go to a buffer and the translog, and a refresh every second turns them into a new searchable segment, which is why it is near real-time. Updates and deletes only mark documents as deleted, and the data is dropped during merges. Immutability means reads need no locks, per-segment caches never go stale and data compresses well; the cost is expensive updates and background merging.

Q3. Elasticsearch làm sort và facet nhanh thế nào khi inverted index là term → doc?

🇻🇳 Tiếng Việt:

Sort và aggregation cần chiều doc → giá trị, nên Lucene lưu thêm doc values theo cột trên đĩa, chỉ đọc đúng cột cần cho các doc khớp. Range trên số như giá dùng BKD tree, lấy cả block nằm trọn trong khoảng. Điều kiện trong filter context không tính điểm và được cache thành bitset theo segment, nên lọc lặp lại chỉ là phép AND bit.

🇬🇧 English:

Sorting and aggregations need the doc-to-value direction, so Lucene also stores doc values, a columnar on-disk format, and reads only the needed column for matching docs. Numeric ranges such as price use a BKD tree that takes whole blocks lying inside the range. Clauses in filter context are not scored and are cached as per-segment bitsets, so repeated filters become bitwise ANDs.

Q4. Một search request chạy qua cluster như thế nào?

🇻🇳 Tiếng Việt:

Node nhận request làm coordinating node, gửi song song tới một bản primary hoặc replica của mỗi shard. Query phase: mỗi shard trả top N docId và điểm cùng facet từng phần. Coordinating node merge ra top N toàn cục, rồi fetch phase chỉ lấy _source của N doc đó. Thêm replica giúp tăng throughput đọc, thêm shard và node giúp chia dữ liệu.

🇬🇧 English:

The receiving node acts as coordinator and sends the query in parallel to one copy, primary or replica, of each shard. In the query phase each shard returns its top N doc IDs with scores and partial facets. The coordinator merges them into the global top N, then the fetch phase loads _source only for those N documents. Replicas add read throughput, while more shards and nodes spread the data.

Cách nhớ ngắn gọn

• B-tree sort theo cả chuỗi → không tìm "chứa từ"; inverted index lật ngược: term → docId đã sort.
• FST tìm term trong RAM; giao posting list từ term hiếm nhất, skip list + nén delta.
• Segment bất biến: refresh 1s → near real-time; update = tombstone + merge; cache an toàn.
• Doc values cho sort/facet, BKD cho range, filter = bitset cache, BM25 cho relevance.
• Shard song song, query then fetch; ES là bản sao, PostgreSQL là sự thật.