Cây dữ liệu lớn trong IndexedDB với RxDB: index, tìm kiếm trigram và tải lười

Personal OS, app quản lý thời gian của mình, có một thư viện block: các hoạt động dùng lại được và lồng vào nhau ("Học sâu cuối tuần" chứa "Phiên tập trung 1", "Nghỉ", "Đọc sách", và "Đọc sách" lại có các chương riêng). Mọi thứ nằm trong trình duyệt, trong IndexedDB qua RxDB, và thư viện có thể phình ra không giới hạn. Bài này kể điều gì khiến một cây dữ liệu trong IndexedDB chậm, và những thay đổi giúp việc đọc, tìm kiếm và vẽ cây phụ thuộc vào thứ đang hiện trên màn hình thay vì kích thước cả bảng: một index mà RxDB không dựng được, tìm kiếm trigram bỏ qua dấu tiếng Việt, tải lười, virtualize, và những bài test đếm số truy vấn thay vì đếm mili giây.

Một truy vấn mất 19,6 giây cho 61 node

Mỗi block lưu block cha trong parent_id, có giá trị null với block gốc. Tải một cây con nghĩa là hỏi con của từng tầng một:

db.snapshot_nodes.find({ selector: { parent_id: { $in: parentIds } } })

Trông như một lần tra index. Nhưng không phải. Kế hoạch của một ngày gồm hai tầng, 61 node, trong một bảng 2.061 node, mất 19,6 giây để tải, vì mỗi tầng là một lần quét toàn bảng.

Lý do nằm trong quy tắc schema của RxDB: index chỉ được phép trên trường kiểu string, integer hoặc number. Một trường nullable được khai là ["string", "null"], không thuộc kiểu nào trong đó, nên parent_id không bao giờ được index. Không có index, $in quay về đọc từng document một.

Một cột "bóng" không null, do hook điền

Cách sửa dễ nghĩ nhất là lưu một giá trị đánh dấu như "" vào parent_id thay cho null. Nhưng làm vậy sẽ phá hàng chục chỗ đang kiểm if (!block.parent_id) với nghĩa "đây là block gốc". Nên cách sửa là thêm một cột thứ hai:

parent_key là bản sao không null của parent_id: bằng nó, hoặc "" với block gốc. Cột này chỉ tồn tại để được index; parent_id giữ nguyên ý nghĩa ở mọi chỗ khác.
Hook preInsert và preSave điền nó ở mọi lần ghi (lời gọi repository, chèn hàng loạt, upsert, migration), nên không đường ghi nào quên được.
Một migration schema điền bù cho các block đã có sẵn trên máy người dùng.

Từ đó, tải một cây con là một lần tra index cho mỗi tầng, và số lượt đi về bằng độ sâu của cây (thực tế hai, ba tầng) chứ không phải số node.

Mẹo này sau đó còn phải dùng lại cho category_id, cùng một lý do. Một cột bóng cũng kéo theo hệ quả cho việc đồng bộ, chuyện đó được kể riêng trong bài bốn lỗi làm RxDB sync hỏng trong im lặng.

Đọc từng nhánh một, không đọc cả bảng

Dù đã có index, trang thư viện ban đầu vẫn theo dõi cả bảng rồi dựng cây bằng JavaScript: lập map, nhóm theo cha, đếm con. Mọi thứ trên trang tốn thời gian tỉ lệ với tổng số block.

Giờ cây được tải lười:

Block gốc và con của từng nhánh đang mở là các truy vấn reactive riêng trên parent_key. Thu gọn một nhánh là bỏ subscription của nó.
Breadcrumb và panel chi tiết leo ngược lên bằng findById thay vì tìm trong một bản sao cả bảng trong bộ nhớ.
Xoá hay nhân bản một cây con duyệt theo chiều rộng qua index.

Một bài test kiểm tra đúng tính chất quan trọng. Nó đọc 20 con của một nhánh trong bảng 120 block, rồi đọc lại trong bảng 2.020 block (lớn gấp 16,8 lần), và so thời gian. Nếu trang vẫn theo dõi cả bảng thì tỉ lệ sẽ xấp xỉ 16,8; với index, kết quả là khoảng 0,95 lần, tức là không đổi. Test sẽ đỏ nếu tỉ lệ vượt 6, một biên rộng vì nó chạy trên fake-indexeddb trong CI.

Tìm chuỗi con mà không có full-text index

Tìm kiếm khó hơn. Người dùng muốn tìm kiểu "có chứa": gõ "họp" phải ra "Cuộc họp nhóm". Index trên title chỉ giúp được tiền tố, và RxDB không có tìm kiếm full-text, nên bản đầu tiên nạp mọi block rồi lọc bằng JavaScript.

Cách sửa là một inverted index nhỏ theo kiểu máy tìm kiếm, nằm trong một collection riêng chỉ ở máy, không bao giờ đồng bộ:

Chuẩn hoá chữ: bỏ dấu tiếng Việt, chuyển về chữ thường, gộp khoảng trắng. Phân rã NFD gỡ được hầu hết dấu, nhưng đ là một chữ cái riêng trong Unicode chứ không phải d cộng dấu, nên cần một quy tắc riêng.
Tách thành trigram, các mẩu ba ký tự chồng lên nhau: "cuoc hop" cho ra cuo, uoc, oc , c h, ho, hop.
Lưu một hàng cho mỗi cặp (block, trigram), có index trên trigram.
Khi tìm, tách câu truy vấn theo cùng cách, lấy các hàng khớp bất kỳ trigram nào bằng một lần $in có index, rồi xác minh từng ứng viên bằng cách kiểm tra title đã chuẩn hoá có thật sự chứa câu truy vấn đã chuẩn hoá không. Kết quả xếp theo số trigram khớp.

Index chỉ thu hẹp danh sách ứng viên; bước kiểm tra trên title đã chuẩn hoá mới quyết định.

export function normalizeForSearch(text: string): string {
  return text
    .normalize('NFD')
    .replace(/[̀-ͯ]/g, '')
    .replace(/đ/g, 'd')
    .replace(/Đ/g, 'd')
    .toLowerCase()
    .replace(/\s+/g, ' ')
    .trim()
}

Vì cả hai phía đều được chuẩn hoá, gõ không dấu ("hop") vẫn ra "họp", đúng cách nhiều người Việt gõ trên laptop.

Vài chi tiết thực tế:

Index được cập nhật tường minh từ các lệnh tạo, đổi tên, nhân bản, xoá hay hoàn tác block, không qua một observer chung chung. Đổi tên thì xoá trigram cũ của block trước rồi mới chèn trigram mới, vì title ngắn đi sẽ mất bớt trigram.
Khoá chính trong RxDB không được có khoảng trắng ở đầu hay cuối, mà trigram thì hay có ("oc "), nên ID của hàng mã hoá trigram, còn trường được index giữ nguyên giá trị thật.
Thư viện có sẵn được điền index bù ở nền lúc khởi động, theo từng trang bằng con trỏ ID, nên không bao giờ nạp cả bảng vào bộ nhớ một lúc.
Trigram cần ít nhất ba ký tự. Truy vấn ngắn hơn không dùng được index, đó là giới hạn chung của kỹ thuật này và nên tính trước.

Chỉ vẽ những hàng trên màn hình

Cây từng được render đệ quy: mọi node đang mở đều nằm trong DOM. Một thư viện có hàng nghìn block đang mở nghĩa là hàng nghìn hàng.

Giờ cây được làm phẳng thành danh sách theo thứ tự trước (pre-order), chỉ đi xuống các node đang mở, nên mỗi hàng nhìn thấy được là một phần tử mảng kèm độ sâu. Danh sách đó đưa cho TanStack Virtual, thư viện chỉ mount những hàng trong khung nhìn cộng một ít hàng dư.

Có một màn hình cố ý không virtualize: trình sửa ngày. Kéo thả giữa các tầng lồng nhau ở đó cần mọi item có thể sắp xếp nằm trong DOM, và một ngày chỉ có vài chục node, nên lợi ích nhỏ mà rủi ro thì có thật.

Giới hạn độ sâu, vì trải nghiệm chứ không vì tốc độ

Block lồng nhau tối đa 8 tầng. Chi phí thật đến từ số con và tổng kích thước, những thứ các thay đổi trên đã lo; độ sâu bị giới hạn vì một cây bệnh lý thì không dùng nổi và các đường đệ quy cần có điểm dừng. Di chuyển cả một cây con sẽ kiểm tra độ sâu của cha cộng một cộng chiều cao của cây con được kéo, vì node được kéo có thể hợp lệ trong khi cháu của nó lại vượt giới hạn.

Cố ý không giới hạn số con của một block: một ngày nhiều block là cách dùng hợp lệ, và những đường tốn kém với cây rộng (render và xoá) đã được xử lý trực tiếp.

Test đếm truy vấn, không đếm mili giây

Test đo thời gian trên máy CI rất nhiễu. Phần lớn test hiệu năng trong codebase này đếm thay vì đo:

Một thao tác chạy bao nhiêu truy vấn. Sao chép tuần sang các tuần sau từng gọi count() cho mỗi ngày của mỗi tuần, khoảng 364 truy vấn cho một năm; giờ chỉ còn một truy vấn theo khoảng. Nhập một file từng gọi findOne cho mỗi dòng, giờ là một find cộng một bulkUpsert. Test khẳng định số truy vấn, nên một mẫu N+1 quay lại sẽ làm build đỏ.
Database dùng kế hoạch truy vấn nào. Ở server, test chạy EXPLAIN trên PostgreSQL thật với 50.000 hàng và khẳng định thao tác pull khi đồng bộ dùng index scan chứ không phải seq scan. Ai xoá hay đổi index thì test đỏ, bất kể máy CI nhanh hay chậm.

Tóm tắt

Vấn đề	Thay đổi
`$in` trên `parent_id` nullable quét cả bảng	Cột bóng `parent_key` không null, do hook ghi điền, có index
Trang dựng cây từ cả bảng	Truy vấn lười theo từng nhánh đang mở; chi phí mỗi nhánh không đổi
Tìm chuỗi con nạp mọi block	Index trigram chỉ ở máy, bỏ dấu, xác minh ứng viên
Hàng nghìn hàng trong DOM	Làm phẳng cây cộng virtualize; màn hình kéo thả để nguyên
Cây lồng quá sâu	Giới hạn 8 tầng, kiểm cả chiều cao cây con khi di chuyển
Hiệu năng thoái lui	Test đếm truy vấn và kiểm kế hoạch truy vấn

Những thay đổi này được làm và kiểm thử ở quy mô hàng nghìn block, với mục tiêu là không thứ gì trên màn hình phụ thuộc vào tổng kích thước. Sợi chỉ chung rất đơn giản: trong IndexedDB cũng như ở database server, hãy kiểm tra xem truy vấn mình tưởng có index có thật sự dùng index không.

Nếu bạn từng giữ cho một cây dữ liệu lớn trong IndexedDB hay RxDB chạy nhanh, mình rất muốn được trao đổi. Email của mình ở trang chủ.