Tìm kiếm Vector ở quy mô lớn: So sánh Chỉ mục HNSW và IVFFlat trong pgvector và SQLite-vec

Pipeline RAG của bạn đã hoạt động. Tính năng tìm kiếm ngữ nghĩa đã được triển khai. Nhưng độ trễ đang dần tăng lên, và phản hồi của người dùng cho thấy kết quả không phải lúc nào cũng liên quan. Nguyên nhân gốc rễ thường không nằm ở LLM hay mô hình embedding, mà ở một lựa chọn cơ bản hơn sâu trong tầng cơ sở hạ tầng: thuật toán chỉ mục vector. Việc lựa chọn giữa các thuật toán Tìm kiếm Láng giềng Gần đúng (Approximate Nearest Neighbor - ANN) như Hierarchical Navigable Small World (HNSW) và Inverted File with Flat Compression (IVFFlat) là một quyết định có ảnh hưởng sâu sắc đến recall, độ trễ, mức sử dụng bộ nhớ và sự phức tạp trong vận hành.

Đây không phải là một bài tập lý thuyết suông. Đối với một kỹ sư senior, việc chọn đúng chỉ mục là để kiểm soát sự đánh đổi giữa độ chính xác (recall) và hiệu năng (số truy vấn mỗi giây, QPS). Một lựa chọn sai lầm có thể dẫn đến một hệ thống quá chậm, quá thiếu chính xác, hoặc quá tốn kém để vận hành. Chúng ta sẽ mổ xẻ hai thuật toán nổi trội này, không chỉ trên lý thuyết mà còn qua các triển khai thực tế trong hai công cụ ngày càng phổ biến và sẵn sàng cho production: pgvector cho PostgreSQL và sqlite-vec dạng nhúng. Đây là cẩm nang giúp bạn đưa ra quyết định sáng suốt và có cơ sở vững chắc cho hạ tầng AI của mình.

Các đối thủ: Câu chuyện về hai thuật toán ANN

Tìm kiếm K-Láng giềng Gần nhất (K-Nearest Neighbor - KNN) chính xác là bất khả thi về mặt tính toán ở quy mô lớn. "Lời nguyền của số chiều" (curse of dimensionality) có nghĩa là khi số chiều trong vector embedding của bạn tăng lên (ví dụ: 768 cho all-MiniLM-L6-v2, 1536 cho text-embedding-ada-002 của OpenAI), không gian tìm kiếm sẽ mở rộng theo cấp số nhân. Một lượt quét tuần tự (linear scan) hàng triệu vector cho mỗi truy vấn sẽ khiến bất kỳ hệ thống production nào cũng phải sụp đổ.

Các thuật toán ANN giải quyết vấn đề này bằng cách đánh đổi độ chính xác hoàn hảo để lấy tốc độ tăng vọt. Thay vì đảm bảo tìm ra các láng giềng gần nhất tuyệt đối, chúng cung cấp một tập hợp các láng giềng gần có xác suất rất cao.

IVFFlat: Chỉ mục lượng tử hóa

Chỉ mục Tệp Nghịch đảo (Inverted File - IVF) có khái niệm đơn giản và mượn ý tưởng cốt lõi từ việc lập chỉ mục của các công cụ tìm kiếm truyền thống. Biến thể "Flat" đề cập đến cách các vector được lưu trữ trong chỉ mục.

Cách IVFFlat hoạt động:

1. Phân vùng (Training): Trong quá trình tạo chỉ mục, IVFFlat sử dụng một thuật toán phân cụm (thường là k-means) để chia toàn bộ không gian vector thành nlist cụm (cluster). Tâm của mỗi cụm được gọi là "centroid". Chỉ mục lưu trữ danh sách các vector thuộc về mỗi cụm.
2. Tìm kiếm: Khi một vector truy vấn đến:
   • Nó được so sánh trước tiên với nlist centroid để tìm các cụm gần nhất.
   • Việc tìm kiếm sau đó được giới hạn trong các vector thuộc nprobe cụm gần nhất, trong đó nprobe là một tham số lúc truy vấn.
   • Bên trong nprobe cụm này, một cuộc tìm kiếm vét cạn, chính xác được thực hiện trên tất cả các vector thành viên.

Phép loại suy: Hãy tưởng tượng một thư viện khổng lồ với hàng triệu cuốn sách (vector). IVFFlat sắp xếp chúng lên nlist kệ sách (cụm). Để tìm một cuốn sách về chủ đề cụ thể (query vector), trước tiên bạn xác định nprobe kệ sách liên quan nhất và sau đó tỉ mỉ quét từng cuốn sách chỉ trên những kệ đó.

Các tham số tinh chỉnh chính:

• lists (nlist): Số lượng cụm cần tạo. nlist cao hơn sẽ tạo ra một phân vùng không gian chi tiết hơn, có khả năng cải thiện tốc độ tìm kiếm nếu nprobe thấp, nhưng đòi hỏi nhiều bộ nhớ hơn cho các centroid. Một kinh nghiệm phổ biến là nlist = N / 1000 cho tối đa 1 triệu vector, và nlist = sqrt(N) cho các bộ dữ liệu lớn hơn.
• ivfflat.probes (nprobe): Số lượng cụm cần tìm kiếm tại thời điểm truy vấn. Đây là nút vặn chính để điều chỉnh sự đánh đổi giữa tốc độ và độ chính xác. nprobe cao hơn làm tăng recall nhưng cũng làm tăng độ trễ vì có nhiều vector được quét hơn.

HNSW: Duyệt đồ thị có hướng dẫn

Hierarchical Navigable Small World (HNSW) là một thuật toán dựa trên đồ thị đã trở thành một thế lực thống trị trong lĩnh vực tìm kiếm vector nhờ hiệu năng vượt trội, đặc biệt ở các mức recall cao.

Cách HNSW hoạt động:

1. Xây dựng đồ thị phân tầng: HNSW xây dựng một đồ thị nhiều lớp trong đó mỗi nút là một vector. Các lớp trên cùng là những "đường cao tốc" thưa thớt nối các điểm xa nhau trong không gian vector, trong khi các lớp dưới cùng là những "đường nội bộ" dày đặc nối các láng giềng gần nhau. Trong quá trình chèn, một vector mới được thêm vào đồ thị, tạo ra các kết nối đến các láng giềng gần nhất của nó ở các lớp khác nhau.
2. Tìm kiếm tham lam (Greedy Search): Một cuộc tìm kiếm bắt đầu tại một điểm vào được xác định trước ở lớp trên cùng, thưa thớt nhất. Thuật toán duyệt đồ thị một cách tham lam, luôn di chuyển về phía nút gần nhất với vector truy vấn. Khi không thể tìm thấy nút nào gần hơn ở lớp hiện tại, nó sẽ đi xuống lớp tiếp theo, dày đặc hơn và tiếp tục tìm kiếm. Quá trình này lặp lại cho đến khi đến lớp dưới cùng, nơi nó thực hiện một cuộc tìm kiếm cục bộ tinh chỉnh.

Phép loại suy: Giống như việc di chuyển trong một thành phố bằng bản đồ đa tầng. Bạn bắt đầu trên hệ thống đường cao tốc liên bang (tầng trên cùng) để nhanh chóng vượt qua những khoảng cách lớn, sau đó đi vào các xa lộ chính (tầng giữa), và cuối cùng sử dụng các con đường nội bộ (tầng dưới cùng) để tìm địa chỉ chính xác.

Các tham số tinh chỉnh chính:

• m: Số lượng kết nối hai chiều (cạnh) tối đa mà một nút có thể có trong đồ thị. m cao hơn tạo ra một đồ thị dày đặc hơn, mạnh mẽ hơn, dẫn đến recall tốt hơn và xây dựng nhanh hơn nhưng làm tăng đáng kể kích thước chỉ mục và dung lượng bộ nhớ.
• ef_construction: Một tham số lúc xây dựng chỉ mục, kiểm soát kích thước của danh sách ứng viên động khi tìm kiếm láng giềng cho một nút mới. Giá trị cao hơn dẫn đến một đồ thị chất lượng tốt hơn (recall tiềm năng cao hơn) với chi phí là thời gian xây dựng chỉ mục chậm hơn nhiều.
• hnsw.ef_search: Một tham số lúc truy vấn, xác định kích thước của danh sách ứng viên động trong quá trình tìm kiếm. Đây là nút vặn quan trọng cho sự đánh đổi recall/độ trễ. ef_search cao hơn làm tăng khả năng tìm thấy các láng giềng gần nhất thực sự (recall cao hơn) nhưng làm tăng độ trễ truy vấn.

Tìm hiểu sâu về triển khai: pgvector trong PostgreSQL

pgvector là một extension của PostgreSQL mang lại khả năng tìm kiếm vector hiện đại cho cơ sở dữ liệu quan hệ mã nguồn mở tiên tiến nhất thế giới. Điều này cho phép bạn kết hợp dữ liệu có cấu trúc và tìm kiếm vector trong cùng một transaction, một khả năng mạnh mẽ cho các ứng dụng production.

Đầu tiên, hãy đảm bảo extension đã được kích hoạt trong cơ sở dữ liệu của bạn:

CREATE EXTENSION IF NOT EXISTS vector;

Giả sử chúng ta có một bảng để lưu trữ các đoạn tài liệu:

CREATE TABLE documents (
    id SERIAL PRIMARY KEY,
    content TEXT,
    embedding VECTOR(768)
);
-- Populate with data...

IVFFlat trong pgvector

Tạo một chỉ mục IVFFlat khá đơn giản. Quyết định chính là số lượng lists. Đối với một bảng có 1 triệu vector, giá trị từ 1000 đến 4000 là một điểm khởi đầu hợp lý.

-- Tạo chỉ mục IVFFlat với 1000 lists
-- Phải thực hiện sau khi bảng đã được điền dữ liệu.
CREATE INDEX ON documents
USING ivfflat (embedding vector_l2_ops)
WITH (lists = 1000);

Lưu ý quan trọng trong môi trường production: Chỉ mục IVFFlat không được xây dựng tăng dần (incrementally). Bạn phải điền dữ liệu vào bảng trước, sau đó mới chạy CREATE INDEX. Nếu bạn thêm một lượng lớn vector mới, chỉ mục sẽ trở nên mất cân bằng và hiệu suất sẽ giảm sút. Bạn phải xây dựng lại toàn bộ chỉ mục (REINDEX INDEX my_ivfflat_index;), việc này có thể gây ra downtime hoặc đòi hỏi một chiến lược chỉ mục blue-green phức tạp.

Tại thời điểm truy vấn, bạn kiểm soát độ chính xác bằng ivfflat.probes. Đây là một tham số ở cấp session.

-- Thiết lập số lượng probes cho session/transaction hiện tại
SET ivfflat.probes = 10;

-- Thực thi truy vấn
SELECT id, content FROM documents
ORDER BY embedding <-> (SELECT embedding FROM documents WHERE id = 123)
LIMIT 10;

HNSW trong pgvector

HNSW cung cấp một giải pháp thay thế linh hoạt hơn và thường có hiệu năng cao hơn.

-- Tạo chỉ mục HNSW
-- Có thể thực hiện trên bảng rỗng hoặc đã có dữ liệu.
CREATE INDEX ON documents
USING hnsw (embedding vector_l2_ops)
WITH (m = 16, ef_construction = 64);

• m = 16: Một điểm khởi đầu tiêu chuẩn. Tăng lên 24 hoặc 32 để có recall cao hơn với chi phí là bộ nhớ.
• ef_construction = 64: Một sự đánh đổi hợp lý giữa chất lượng xây dựng và thời gian xây dựng. Tăng lên 128 để có đồ thị tốt hơn nếu bạn có thể chấp nhận thời gian xây dựng lâu hơn.

Ưu điểm Lớn: Chỉ mục HNSW trong pgvector được xây dựng tăng dần! Bạn có thể thêm chỉ mục vào một bảng rỗng và nó sẽ được cập nhật hiệu quả khi bạn INSERT các hàng mới. Đây là một thay đổi cuộc chơi (game-changer) đối với các bộ dữ liệu động.

Truy vấn cũng tương tự, sử dụng một tham số ở cấp session cho chất lượng tìm kiếm.

-- Thiết lập tham số chất lượng tìm kiếm cho session hiện tại
SET hnsw.ef_search = 100;

-- Thực thi truy vấn
SELECT id, content FROM documents
ORDER BY embedding <-> (SELECT embedding FROM documents WHERE id = 123)
LIMIT 10;

So sánh luồng truy vấn trong pgvector

Sơ đồ sau minh họa các đường đi khác nhau mà một truy vấn thực hiện trong runtime tùy thuộc vào loại chỉ mục và các tham số session.

Lợi thế nhúng: sqlite-vec

Nếu một instance PostgreSQL đầy đủ là quá mức cần thiết thì sao? Đối với các thiết bị biên, hàm serverless, hoặc các ứng dụng local-first, sqlite-vec cung cấp một giải pháp cực kỳ mạnh mẽ. Nó là một extension của SQLite nhúng một công cụ tìm kiếm vector hiệu năng cao trực tiếp vào tệp cơ sở dữ liệu của ứng dụng bạn.

sqlite-vec chủ yếu tận dụng hnswlib, một trong những triển khai HNSW nguyên bản và được tối ưu hóa nhất. Điều này đơn giản hóa sự lựa chọn: bạn sẽ có HNSW ngay từ đầu.

Sức mạnh nằm ở sự đơn giản và không có chi phí mạng. Dưới đây là một ví dụ bằng Python:

import sqlite_vec
import numpy as np

# Kết nối đến (hoặc tạo) tệp cơ sở dữ liệu
db = sqlite_vec.connect('my_app_data.db')

# Định nghĩa một bảng với cột vector 768 chiều sử dụng HNSW
# Chỉ định 'hnsw' là ngầm định trong các phiên bản mới hơn nhưng nên ghi rõ cho tường minh
db.create_table(
    'articles',
    {
        'embedding': (768, 'f32', {'m': 16, 'ef_construction': 64})
    }
)

# Chèn một số dữ liệu
vectors = np.random.rand(1000, 768).astype('f32')
db.insert('articles', ['embedding'], vectors)

# Thực hiện tìm kiếm
query_vector = np.random.rand(768).astype('f32')
results = db.search(
    'articles',
    'embedding',
    query_vector,
    k=10,
    # ef_search được truyền vào như một tham số ở đây
    params={'ef': 100}
)

print(f"Found {len(results)} results.")
for rowid, distance in results:
    print(f"RowID: {rowid}, Distance: {distance}")

db.close()

Mô hình rất rõ ràng: các đặc tính hiệu năng vượt trội của HNSW đã khiến nó trở thành lựa chọn mặc định cho các triển khai tìm kiếm vector hiện đại, gọn nhẹ như sqlite-vec.

Cuộc đối đầu benchmark: Một so sánh thực tế

Lý thuyết là một chuyện, nhưng hiệu năng production mới là điều quan trọng. Chúng tôi đã benchmark các triển khai IVFFlat và HNSW của pgvector trên một bộ dữ liệu gồm 1 triệu vector 768 chiều (các embedding all-MiniLM-L6-v2).

Môi trường thử nghiệm:

• Bộ dữ liệu: 1 triệu vector, 768 chiều.
• Phần cứng: AWS db.m6g.xlarge (4 vCPU, 16 GiB RAM)
• PostgreSQL: v15 với pgvector v0.5.1

Phân tích kết quả

1. Recall & Độ trễ: HNSW là người chiến thắng rõ ràng để đạt được recall cao. Với ef_search=100, nó đạt được recall gần như hoàn hảo 98% ở độ trễ (15ms) mà IVFFlat chỉ đạt được ở recall 85%. Để đưa recall của IVFFlat lên trên 90%, nprobe phải được đẩy lên cao đến mức độ trễ của nó trở nên không cạnh tranh được.
2. Thời gian xây dựng: IVFFlat xây dựng nhanh hơn đáng kể (5 phút so với 45+ phút cho HNSW). Đây là ưu điểm chính của nó. Nếu bộ dữ liệu của bạn tĩnh và bạn cần xây dựng chỉ mục nhanh chóng, IVFFlat rất hấp dẫn.
3. Bộ nhớ & Kích thước: Chỉ mục HNSW lớn hơn và tiêu tốn nhiều bộ nhớ hơn. Các cạnh của đồ thị (kết nối m cho mỗi nút) làm tăng đáng kể chi phí so với cấu trúc danh sách-vector đơn giản hơn của IVFFlat.
4. Đường cong đánh đổi: Đối với cả hai chỉ mục, việc tăng tham số lúc tìm kiếm (probes hoặc ef_search) sẽ cải thiện recall nhưng làm tăng độ trễ. Điểm mấu chốt là đường cong của HNSW thuận lợi hơn: nó mang lại cho bạn nhiều recall hơn cho mỗi mili giây độ trễ mà bạn sẵn sàng trả giá.

Ước tính bộ nhớ và tinh chỉnh Production

Cung cấp bộ nhớ không chính xác là lý do số 1 gây ra hiệu năng tìm kiếm vector kém. Nếu chỉ mục không vừa trong RAM (shared_buffers cho PostgreSQL), cơ sở dữ liệu sẽ phải đọc/ghi liên tục từ đĩa, và độ trễ sẽ tăng vọt từ mili giây lên giây.

Công thức bộ nhớ HNSW

Dung lượng bộ nhớ của một chỉ mục HNSW chủ yếu do việc lưu trữ các vector và các kết nối đồ thị. Tổng bộ nhớ ≈ (dim * 4 + m * 2 * 4) * num_vectors

• dim * 4: Kích thước của một vector tính bằng byte (giả sử số thực 32-bit).
• m * 2 * 4: Kích thước các kết nối cho một nút. m kết nối đi ra, * 2 cho các liên kết hai chiều, * 4 byte cho mỗi con trỏ (giả sử số nguyên 32-bit cho ID nút).
• Đối với ví dụ 1 triệu vector, 768 chiều, m=16 của chúng ta: (768 * 4 + 16 * 2 * 4) * 1,000,000 ≈ (3072 + 128) * 1e6 ≈ 3.2 GB. Thêm chi phí cho chính dữ liệu vector và kích thước chỉ mục đầy đủ là khoảng 4.2 GB, khớp với benchmark của chúng tôi.

Công thức bộ nhớ IVFFlat

Bộ nhớ IVFFlat được chia cho các centroid và dữ liệu được tải trong một truy vấn. Bộ nhớ Centroid = nlist * dim * 4

Tại thời điểm truy vấn, hệ thống phải tải tất cả các vector từ nprobe cụm vào bộ nhớ. Bộ nhớ truy vấn ≈ nprobe * (num_vectors / nlist) * dim * 4

• Đối với ví dụ 1 triệu vector, nlist=1000, nprobe=10 của chúng ta:
• Bộ nhớ centroid không đáng kể: 1000 * 768 * 4 ≈ 3 MB.
• Bộ nhớ truy vấn để quét là 10 * (1,000,000 / 1000) * 768 * 4 ≈ 30 MB. Dung lượng bộ nhớ tĩnh thấp, nhưng I/O và việc sử dụng bộ nhớ tạm thời trong quá trình truy vấn có thể đáng kể. Toàn bộ 3.1 GB dữ liệu vector phải có sẵn để hệ điều hành có thể đưa vào bộ nhớ một cách hiệu quả.

Hỏi đáp tương tác

Phán quyết cuối cùng và những bài học hành động

Sự lựa chọn giữa HNSW và IVFFlat là một quyết định kỹ thuật quan trọng, không phải là vấn đề sở thích.

• Hãy chọn HNSW làm lựa chọn mặc định của bạn. Đối với đại đa số các ứng dụng hiện đại liên quan đến dữ liệu động, yêu cầu recall cao và ngân sách bộ nhớ chấp nhận được, HNSW là thuật toán vượt trội. Việc triển khai nó trong pgvector rất mạnh mẽ, xử lý các cập nhật tăng dần một cách duyên dáng và mang lại hiệu suất recall-trên-độ trễ xuất sắc. Sự thống trị của nó trong các giải pháp nhúng như sqlite-vec càng củng cố vị thế của nó như là tiêu chuẩn hiện đại.

• Chỉ sử dụng IVFFlat cho các trường hợp đặc thù, với bộ dữ liệu tĩnh. Nếu bạn có một bộ dữ liệu lớn, không thay đổi và ràng buộc chính của bạn là giảm thiểu thời gian xây dựng chỉ mục, IVFFlat vẫn là một lựa chọn khả thi. Hãy chuẩn bị để quản lý sự mong manh trong vận hành của nó và chấp nhận một mức trần hiệu suất recall thấp hơn.

• Cấp phát bộ nhớ một cách hào phóng. Cả hai thuật toán đều sống và chết bởi RAM. Sử dụng các công thức ước tính bộ nhớ được cung cấp ở đây làm cơ sở cho việc lập kế hoạch năng lực của bạn. Theo dõi tỷ lệ cache hit của bạn. Một chỉ mục không vừa trong bộ nhớ là một sự cố production đang chực chờ xảy ra.

• Benchmark, Benchmark, Benchmark. Các con số trong bài viết này là một hướng dẫn. Sự phân bố dữ liệu của riêng bạn và bản chất các truy vấn của bạn là duy nhất. Hãy thiết lập một benchmark đơn giản bằng chính các vector của bạn, tinh chỉnh các tham số chính (ef_search, probes), và vẽ đường cong recall-so-với-độ trễ của riêng bạn. Đây là cách duy nhất để đưa ra quyết định thực sự dựa trên dữ liệu.

Trong thế giới phát triển nhanh chóng của hạ tầng AI, pgvector và sqlite-vec đã dân chủ hóa quyền truy cập vào tìm kiếm vector hàng đầu. Bằng cách hiểu rõ những đánh đổi kỹ thuật sâu sắc giữa HNSW và IVFFlat, bạn có thể xây dựng các hệ thống RAG và tìm kiếm ngữ nghĩa không chỉ mạnh mẽ mà còn có khả năng mở rộng, hiệu quả và đáng tin cậy trong môi trường production.

Đọc thêm

• Bài báo gốc về HNSW: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• Thư viện FAISS (nguồn gốc của nhiều khái niệm IVFFlat): Billion-scale similarity search with GPUs
• Kho mã nguồn pgvector trên GitHub: https://github.com/pgvector/pgvector
• Kho mã nguồn sqlite-vec trên GitHub: https://github.com/asg017/sqlite-vec
• ANN-Benchmarks: Một bộ benchmark cho các thuật toán ANN khác nhau

Kiểm tra kiến thức