[2009 WSDM] Những thách thức trong việc xây dựng hệ thống truy hồi thông tin quy mô lớn

Các chiều chính và trade-off của hệ thống truy hồi thông tin

• Khi thiết kế hệ thống, cần cân nhắc cân bằng các trade-off kỹ thuật giữa những yếu tố sau.
  • Số lượng tài liệu được lập chỉ mục
  • Số truy vấn xử lý mỗi giây (QPS)
  • Độ mới của chỉ mục / tốc độ cập nhật
  • Độ trễ truy vấn (Latency)
  • Lượng thông tin được lưu cho mỗi tài liệu
  • Độ phức tạp / chi phí của việc tính điểm và thuật toán tìm kiếm
• Độ khó về mặt kỹ thuật có xu hướng tỷ lệ với tích của các tham số này.
• Tất cả các yếu tố này đều ảnh hưởng đến hiệu năng tổng thể và hiệu năng trên chi phí (hiệu năng trên mỗi đô la).

Sự thay đổi về quy mô hệ thống (1999 vs 2009)

• Trong 10 năm qua, quy mô hệ thống và yêu cầu hiệu năng đã thay đổi một cách mạnh mẽ.
  • # tài liệu: ~70 triệu → hàng tỷ (~tăng 100 lần)
  • số truy vấn xử lý mỗi ngày: (~tăng 1000 lần)
  • thông tin chỉ mục trên mỗi tài liệu: (~tăng 3 lần)
  • độ trễ cập nhật: vài tháng → vài phút (~giảm 10000 lần)
  • độ trễ truy vấn trung bình: <1 giây → <0.2 giây (~giảm 5 lần)
  • tài nguyên hệ thống: nhiều máy hơn * máy nhanh hơn (~tăng 1000 lần)
• Vì các tham số này liên tục thay đổi, đôi khi theo nhiều bậc độ lớn, thiết kế hệ thống phải không ngừng tiến hóa.
  • Một thiết kế phù hợp ở thời điểm cụ thể (X) có thể trở thành thiết kế rất sai lầm ở quy mô gấp 10 hay 100 lần. (Vì vậy nên thiết kế với mức tăng trưởng khoảng 10 lần trong đầu, nhưng cần lên kế hoạch viết lại trước khi chạm mốc 100 lần)
  • Trong 10 năm qua đã có 7 lần cải tổ lớn.

Kiến trúc hệ thống ban đầu (1997-1999)

• Giai đoạn dự án nghiên cứu (1997):
  • Web server frontend nhận truy vấn và phân tán yêu cầu xử lý tới các index server và document server
  • Index server: sharding theo ID tài liệu (docid)
  • Document server: sharding theo ID tài liệu (docid)
• Nguyên tắc cơ bản:
  • Tài liệu được gán ID số nguyên (docids) (tài liệu quan trọng / chất lượng cao được gán ID nhỏ)
  • Index server: (truy vấn) → trả về danh sách đã sắp xếp gồm (điểm số, docid, ...). Sharding theo docid, replication để tăng dung lượng. Chi phí O(#truy vấn * #tài liệu trong chỉ mục).
  • Document server: (docid, truy vấn) → tạo (tiêu đề, snippet). Ánh xạ docid → toàn văn tài liệu trên đĩa. Sharding theo docid. Chi phí O(#truy vấn).
• Hệ thống serving (1999):
  • Bổ sung cache server và tích hợp hệ thống quảng cáo vào cấu trúc của dự án nghiên cứu
  • Vận hành các replica cho shard của index/document server
  • Caching: cache cả kết quả chỉ mục lẫn snippet tài liệu. Tỷ lệ cache hit 30-60%. Đóng góp lớn vào việc tăng hiệu năng và giảm độ trễ truy vấn. (Tuy nhiên cần lưu ý khả năng xuất hiện spike độ trễ lớn khi cập nhật chỉ mục / flush cache)

Chiến lược phân vùng chỉ mục

• Theo tài liệu (By doc): mỗi shard giữ chỉ mục của một phần tài liệu (Google chọn cách này)
  • Ưu điểm: xử lý truy vấn độc lập theo từng shard, dễ giữ thêm thông tin theo tài liệu, ít lưu lượng mạng hơn (request/response)
  • Nhược điểm: mọi shard đều phải xử lý truy vấn, với truy vấn gồm K từ thì cần O(K*N) lần seek đĩa trên N shard
• Theo từ (By word): mỗi shard giữ chỉ mục của một phần từ khóa trên toàn bộ tài liệu
  • Ưu điểm: truy vấn K từ chỉ cần tối đa K shard xử lý, O(K) lần seek đĩa
  • Nhược điểm: cần băng thông mạng cao hơn rất nhiều (phải gom thông tin theo từ của các tài liệu khớp về một chỗ), khó duy trì thông tin theo tài liệu

Crawling và indexing ban đầu (1998-1999)

• Crawling:
  • Hệ thống batch crawling đơn giản: danh sách URL khởi đầu → crawl trang → trích xuất liên kết và đưa vào hàng đợi → dừng khi đã thu thập đủ số trang
  • Các điểm cần cân nhắc: tránh gây quá tải cho một site cụ thể, quyết định mức ưu tiên của các trang chưa crawl (ví dụ: PageRank), quản lý hiệu quả hàng đợi URL chưa crawl, xử lý lỗi máy
• Indexing:
  • Hệ thống batch indexing đơn giản: dựa trên các công cụ Unix đơn giản
  • Vấn đề: không có checkpoint nên rất vất vả khi máy lỗi, không có checksum cho dữ liệu gốc nên gặp lỗi bit phần cứng (trầm trọng hơn do máy đời đầu không có ECC/parity, vấn đề "hầu như đã được sắp xếp"), trải nghiệm với "bộ nhớ thù địch và lập trình thù địch"
  • Giải pháp: phát triển một lớp trừu tượng file có thể lưu checksum cho các record nhỏ và bỏ qua / đồng bộ lại được khi gặp record hỏng

Cách cập nhật chỉ mục (1998-1999)

• Chu kỳ: khoảng 1 lần mỗi tháng
• Quy trình:
  1. Chờ đến khung giờ ít traffic
  2. Đưa một phần replica offline
  3. Sao chép chỉ mục mới sang các replica offline
  4. Khởi động frontend mới trỏ tới chỉ mục đã cập nhật và xử lý một phần traffic
• Chiến lược tận dụng đĩa của index server:
  • Vùng ngoài của đĩa (outer part) cho băng thông cao hơn
  1. (Trong lúc vẫn phục vụ chỉ mục cũ) sao chép chỉ mục mới vào vùng trong của đĩa (inner half)
  2. Khởi động lại để dùng chỉ mục mới
  3. Xóa chỉ mục cũ
  4. Sao chép lại chỉ mục mới sang vùng ngoài nhanh hơn (faster half)
  5. Xóa bản sao chỉ mục mới đầu tiên ở vùng trong
  6. Dùng phần không gian trống ở vùng trong để xây dựng các cấu trúc dữ liệu tăng hiệu năng (ví dụ: Pair cache - tính trước kết quả giao của posting list cho các cặp từ truy vấn thường đi cùng nhau)

Ứng phó với tăng trưởng và mở rộng (1999-2001)

• Trong '99, '00, '01, kích thước chỉ mục và traffic tăng vọt (~50 triệu → hơn 1 tỷ trang, traffic tăng 20% mỗi tháng + quan hệ đối tác với Yahoo khiến traffic tăng gấp đôi chỉ sau một đêm, v.v.)
• Hiệu năng của index server trở nên cực kỳ quan trọng: liên tục bổ sung máy + cần cải thiện hiệu năng bằng phần mềm 10-30% mỗi tháng
• Cách mở rộng: thêm nhiều shard và replica hơn
• Hàm ý:
  • Thời gian phản hồi của shard bị ảnh hưởng bởi số lần seek đĩa và lượng dữ liệu cần đọc
  • Các hướng có thể cải thiện hiệu năng: lập lịch đĩa tốt hơn, mã hóa chỉ mục tốt hơn

Sự phát triển của kỹ thuật mã hóa chỉ mục

• Mã hóa ban đầu ('97): định dạng byte-aligned rất đơn giản (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). Hit là vị trí + thuộc tính (cỡ font, tiêu đề, v.v.). Thêm skip table cho các posting list lớn. Giải mã rẻ nhưng tỷ lệ nén thấp nên cần nhiều băng thông đĩa.
• Các kỹ thuật mã hóa khác nhau:
  • Mức bit: Unary, Gamma, Rice_k (trường hợp đặc biệt của mã Golomb), Huffman-Int
  • Byte-aligned: varint (7 bit mỗi byte + bit tiếp diễn)
• Định dạng chỉ mục dựa trên block: giảm cả dung lượng lẫn mức dùng CPU (~giảm 30% kích thước), tăng tốc giải mã. Dùng block có độ dài biến đổi. Header (delta, độ dài, v.v.) + delta ID tài liệu (Rice_k) + số hit (Gamma) + thuộc tính hit (run-length Huffman) + vị trí hit (Huffman-Int).
• Định dạng chỉ mục mới (sau 2004): dùng một không gian vị trí phẳng duy nhất. Theo dõi ranh giới tài liệu bằng cấu trúc dữ liệu phụ trợ. Posting list là danh sách vị trí được mã hóa delta. Cả độ gọn và tốc độ giải mã rất nhanh đều quan trọng.

Hệ thống chỉ mục in-memory (đầu năm 2001)

• Bối cảnh: mở rộng sharding + tăng replica → tổng bộ nhớ toàn hệ thống đủ để giữ toàn bộ bản sao chỉ mục trong RAM
• Kiến trúc: frontend → load balancer (bal) → shard (mỗi shard có nhiều replica index server in-memory)
• Ưu điểm: throughput tăng mạnh, latency giảm mạnh (đặc biệt các truy vấn phức tạp trước đây cần I/O đĩa ở mức GB trở nên nhanh hơn - ví dụ: "circle of life")
• Vấn đề:
  • Độ biến thiên (Variance): dùng hàng nghìn máy thay vì vài chục → khó dự đoán hơn (ví dụ: các cron job ngẫu nhiên gây sự cố)
  • Tính sẵn sàng (Availability): số replica dữ liệu chỉ mục của mỗi tài liệu chỉ có 1 hoặc rất ít → xuất hiện "truy vấn chết chóc" (mọi backend cùng chết), vấn đề sẵn sàng của dữ liệu chỉ mục khi máy lỗi (đặc biệt tài liệu quan trọng cần được nhân bản)

Thiết kế và công nghệ hệ thống giai đoạn sau (sau 2004)

• Phần cứng: data center quy mô lớn hơn, rack tự thiết kế, bo mạch chủ cấp PC, phần cứng lưu trữ / mạng giá rẻ, Linux + phần mềm tự phát triển
• Thiết kế serving (phiên bản 2004): cấu trúc phân tầng
  • Root server → các Parent server → các Leaf server (nạp Repository Shard từ GFS qua File Loader)
  • Tích hợp cache server

Mã hóa Group Varint

• Ý tưởng: giải quyết sự kém hiệu quả của việc giải mã Varint (nhiều phép rẽ nhánh / shift / mask). Gom 4 giá trị số nguyên thành một nhóm và mã hóa trong 5~17 byte.
• Cách làm:
  • Gom 4 tag 2 bit biểu thị độ dài byte (1~4 byte) của từng giá trị để tạo thành 1 byte prefix.
  • Sau byte prefix là các byte dữ liệu thực tế.
• Giải mã: đọc byte prefix, dùng nó làm chỉ số tra bảng 256 mục đã được tính trước → lấy thông tin offset và mask để giải mã 4 giá trị cùng lúc.
• Hiệu năng: nhanh hơn rất nhiều so với các cách cũ (Group Varint: ~400M/giây, 7-bit Varint: ~180M/giây, 30-bit Varint w/ 2-bit len: ~240M/giây)

Universal Search (2007)

• Hệ thống hiển thị tích hợp không chỉ kết quả tìm kiếm web mà còn nhiều loại thông tin khác nhau (hình ảnh, thông tin địa phương, tin tức, video, blog, sách, v.v.).
• Nút super root gửi truy vấn tới nhiều hệ thống tìm kiếm chuyên biệt (vertical search engine) rồi tổng hợp kết quả.

Thách thức của crawling và indexing độ trễ thấp

• Phản ánh cập nhật trong vòng vài phút là một bài toán rất khó.
• Heuristic crawling: nên crawl trang nào?
• Hệ thống crawling: phải crawl trang nhanh.
• Hệ thống indexing: phụ thuộc vào dữ liệu toàn cục như PageRank, anchor text, v.v. → cần online approximation.
• Hệ thống serving: phải sẵn sàng chấp nhận cập nhật trong khi xử lý truy vấn (cần cấu trúc dữ liệu rất khác với hệ thống cập nhật batch).

Tầm quan trọng của thử nghiệm và hạ tầng

• Dễ thử nghiệm: cực kỳ quan trọng (chu kỳ thử nghiệm nhanh → nhiều thử nghiệm hơn → nhiều cải tiến hơn).
• Các loại thử nghiệm:
  • Thử nghiệm dễ: điều chỉnh trọng số trên dữ liệu hiện có, v.v.
  • Thử nghiệm khó: cần dữ liệu mới chưa có trong chỉ mục production. (Phải dễ tạo / tích hợp dữ liệu mới và dùng cho thử nghiệm)
• Hạ tầng cốt lõi:
  • GFS: hệ thống file phân tán quy mô lớn
  • MapReduce: giúp dễ viết / chạy các tác vụ xử lý dữ liệu lớn. (Tăng tốc tạo dữ liệu cho chỉ mục production, nhanh chóng thực hiện thử nghiệm tạm thời)
  • BigTable: hệ thống lưu trữ semi-structured. (Truy cập online / hiệu quả tới thông tin theo tài liệu, cho phép nhiều process cập nhật bất đồng bộ thông tin tài liệu - rất quan trọng để giảm chu kỳ cập nhật từ hàng giờ xuống hàng phút)

Chu kỳ thử nghiệm và phát hành

1. Lên ý tưởng và thử nghiệm offline:
   • Tạo dữ liệu bằng MapReduce, BigTable, v.v.
   • Chạy thử nghiệm offline và kiểm chứng hiệu quả (bộ truy vấn đánh giá thủ công, bộ truy vấn ngẫu nhiên, v.v.).
   • Ở giai đoạn này, độ trễ / throughput của prototype không quan trọng.
   • Lặp lại cải tiến dựa trên kết quả thử nghiệm.
2. Thử nghiệm live:
   • Nếu kết quả offline tốt, tiến hành thử nghiệm live trên một phần rất nhỏ traffic người dùng thực (tiny sliver), chủ yếu là mẫu ngẫu nhiên, đôi khi là một lớp truy vấn cụ thể.
   • Ở giai đoạn này, latency quan trọng hơn throughput! Framework thử nghiệm phải hoạt động gần với độ trễ của môi trường production.
3. Tinh chỉnh hiệu năng và phát hành:
   • Nếu kết quả live tốt, tinh chỉnh hiệu năng / hiện thực lại để có thể chạy ở toàn bộ tải (ví dụ: tiền tính toán dữ liệu thay vì tính lúc chạy, dùng xấp xỉ rẻ hơn nếu "đủ tốt").
   • Quy trình rollout rất quan trọng: liên tục cân nhắc trade-off giữa chất lượng và chi phí, cân bằng giữa phát hành nhanh với độ trễ thấp / độ ổn định của site (cần sự phối hợp tốt giữa đội chất lượng tìm kiếm và đội phụ trách hiệu năng / ổn định).

Hướng đi và thách thức trong tương lai

• Truy hồi thông tin đa ngôn ngữ (Cross-Language IR): dịch mọi tài liệu trên toàn thế giới sang mọi ngôn ngữ → kích thước chỉ mục tăng vọt, chi phí tính toán cao. (Cần tiếp tục cải thiện chất lượng dịch, và cần các hệ thống quy mô lớn để xử lý các mô hình ngôn ngữ lớn hơn, phức tạp hơn)
• Danh sách kiểm soát truy cập (ACLs) trong hệ thống truy hồi thông tin: môi trường pha trộn tài liệu riêng tư / bán riêng tư / chia sẻ rộng / công khai. (Cần xây dựng hệ thống xử lý hiệu quả các ACL có kích thước rất khác nhau - giải pháp tối ưu cho tài liệu chia sẻ cho 10 người khác với tài liệu chia sẻ cho cả thế giới, và mô hình chia sẻ có thể thay đổi theo thời gian)
• Tự động xây dựng hệ thống IR hiệu quả: hiện đang dùng nhiều hệ thống cho nhiều mục đích khác nhau (cập nhật siêu nhanh, tài liệu siêu lớn, v.v.). (Liệu có thể phát triển một hệ thống duy nhất có thể tự động xây dựng hệ thống tìm kiếm hiệu quả theo đúng yêu cầu khi nhập tham số?)
• Trích xuất thông tin từ dữ liệu semi-structured: dữ liệu có nhãn ngữ nghĩa rõ ràng là cực ít. Trong khi đó dữ liệu semi-structured như bảng, form lại rất phong phú. (Cần thuật toán / kỹ thuật tốt hơn để trích xuất thông tin có cấu trúc từ nguồn phi cấu trúc / bán cấu trúc - nhiều nhiễu nhưng có thể tận dụng tính dư thừa, khả năng liên kết / kết hợp / tổng hợp thông tin từ nhiều nguồn)

Kết luận

• Thiết kế và xây dựng hệ thống truy hồi thông tin quy mô lớn là một công việc vừa đầy thách thức vừa thú vị.
• Công nghệ tìm kiếm mới thường đòi hỏi các thiết kế hệ thống mới.