#232 - Cải thiện tốc độ tìm kiếm text trong Postgres

Grokking Vietnam

Sep 01, 2022

Trong số này, chúng ta cùng tìm hiểu về:

Cách giám sát một hệ thống phân tán phức tạp
Cách cải thiện tốc độ tìm kiếm text trong Postgres của CharityAPI
Lịch sử của Macintosh Portable
Lời giải bài Time Based Key-Value Store

Ngoài ra các bạn vẫn có thể tiếp tục đặt mua ấn phẩm Dijkstra tập 2 tại đây.

Những bài viết hay

Distributed Tracing: The Why, What, and How?

(by steven.do)

Bài viết nêu lên những thách thức gặp phải, một số nguyên nhân khi cần giám sát một hệ thống phân tán phức tạp, bên cạnh đó, tác giả cũng gợi ý một vài ý tưởng và các khối chức năng cần thiết để giải quyết được các thách thức đặt ra.

Theo quan điểm của tác giả, trong một hệ thống phân tán phức tạp, một nghiệp vụ logic cần có sự tham gia của hàng trăm, hàng ngàn thành phần khác. Khi một sự cố xảy ra hoặc một xử lý bị delay, điều đầu tiên chúng ta cần làm là tìm được một lời giải thích hợp lý về chuyện gì đang xảy ra đối với hệ thống? Các thành phần tham gia gồm những thành phần nào? Vấn đề xuất phát từ đâu? Những vấn đề xảy ra tiêu tốn nhiều thời gian xử lý thường có đặc điểm gì? Xu hướng ảnh hưởng đến hiệu suất của hệ thống ra sao? Xu hướng về mức độ ổn định của hệ thống theo thời gian ra sao?

Quá trình phát triển của các hệ thống từ đơn giản đến phức tạp đã trải qua các mô hình như sau: No Concurrency > Basic Concurrency > Asynchronous Concurrency > Distributed Concurrency

Ở mỗi mô hình độ phức tạp trong việc giám sát cũng khác nhau và có sự gia tăng khi độ phức tạp của hệ thống tăng lên, và với mô hình Distributed Concurrency việc xác định và hiểu được nguyên nhân của vấn đề xảy ra tại một thành phần trong hệ thống cũng như việc đặt các câu hỏi về tổng thể hoạt động đang diễn ra trong hệ thống càng trở nên khó khăn và thử thách.

Từ đó, tác giả gợi ý một vài khối chức năng cần thiết để liên kết, định danh và chia sẻ định danh các thông tin của các xử lý cùng tham gia một tác vụ trên một hệ thống phân tán phức tạp. Tuy nhiên chỉ với việc có thêm thông tin về hoạt động và định danh của các thành phần cùng tham gia xử lý trong hệ thống vẫn chưa đủ thông tin để chúng ta xác định được nguyên nhân vấn đề, vì vấn đề có thể xuất phát từ các thư viện được cung cấp từ các nhà cung cấp khác và chúng không cung cấp được các thông tin cần thiết hoặc không tương thích với giải pháp vì không có cùng format thống nhất hoặc giới hạn thông tin.

Do vậy, tác giả cho rằng cần thêm một khối chức năng xử lý khả năng tương tác (interoperability) để liên kết với các thành phần được cung cấp từ các bên thứ 3 khác vốn không tương thích với giải pháp và hệ thống. Để làm được điều này, chúng ta cần một bộ chuẩn chung cho toàn hệ thống, và tác giả đã đề xuất dựa theo bộ chuẩn the W3C TraceContext specification.

Sau khi đã có một bộ chuẩn chung, chúng ta đã có cách thức để có thể cộng tác trên cùng một ngữ cảnh (context propagation). Nhưng lại cần có một công cụ thu thập dữ liệu tracing theo một tiêu chuẩn mở và tiêu chuẩn công nghiệp (open and industry standard). Tác giả đã đề xuất sử dụng OpenTelemetry, một bộ công cụ dùng để đo đạc, generate, thu thập và export telemetry data (bao gồm metrics, logs, và traces).

Improving Postgres Text Search Speed 7x On Millions of Records

(by quangle)

CharityAPI ra đời phục vụ cho việc tra cứu dữ liệu của các tổ chức từ thiện và phi lợi nhuận. Vào tháng 5, đội ngũ kỹ sư tại đây nhận được phản hồi từ khách hàng bởi việc tìm kiếm dữ liệu diễn ra rất chậm đối với một số truy vấn. Cụ thể với kho lưu trữ khoảng 1,5 triệu dữ liệu trong bảng organizations trên Postgres, sau khi kiểm tra, họ chọn cách tiếp cận cải thiện hiệu suất bằng việc tối ưu truy vấn mà không cần dùng đến các search engine như Elasticsearch. Và họ đã thành công khi tăng tốc độ search nhanh hơn 760% so với phiên bản cũ bằng những phương pháp như sau.

Thứ nhất: thêm và truy vấn trên trường có kiểu tsvector của bảng organizations.

Postgres cung cấp giải pháp tìm kiếm dựa trên tsvector (cho phép chuyển đổi từ kiểu text sang tokenized vector để tối ưu tìm kiếm). Vì vậy họ đã vận dụng phương pháp trên để tối ưu tìm kiếm cho bảng organizations, hướng triển khai sẽ đi lấy kết quả từ trường searchable_fields, sau đó liên kết với tập dữ liệu được lưu ở cột mới có tên searchable_document dạng tsvector. Song họ cũng tiến hành đánh index cho chính trường tsvector này.

Thứ hai: thực hiện 2 truy vấn lần lượt bao gồm tìm kiếm tập IDs và lấy thông tin organizations dựa trên tập IDs đó.

Chính vì việc join dữ liệu của tập organizations làm chậm tốc độ truy vấn, nhóm kỹ sư chọn cách tiếp cận bằng việc sử dụng 2 câu truy vấn. Qua báo cáo kiểm tra, họ đã chỉ ra việc dùng join dữ liệu tập organizations làm chậm tốc độ truy vấn tới 76%. Vì vậy, nhóm tiến hành tổ chức lại logic cho việc tìm kiếm thông qua 2 việc: thu thập danh sách IDs, sau đó sẽ truy vấn thông tin tổ chức thông qua ID đã được sắp xếp theo thứ tự. Khi đọc tới đây, mình cũng có chút hoài nghi về ý tưởng này của tác giả, còn bạn thì sao?

Để tìm hiểu kĩ hơn các phương pháp được vận dụng, mời bạn đọc cùng tham khảo bài viết.

Góc Lập Trình

Đề ra tuần này: Snapshot Array

(by ndaadn)

Cài đặt cấu trúc dữ liệu SnapshotArray hỗ trợ những hàm sau:

Hàm khởi tạo SnapshotArray(int length): khởi tạo một cấu trúc dữ liệu tương tự mảng, với độ dài là "length". Ban đầu, tất cả các giá trị đều là 0.
Hàm set(index, val): gán giá trị "val" tại vị trí "index".
Hàm snap(): lưu lại các giá trị hiện tại của mảng và trả lại "snap_id" - số lần gọi hàm snap() - 1.
Hàm get(index, snap_id): trả lại giá trị tại vị trí "index" tại thời điểm "snap_id".

Lời giải đề bài tuần trước: Time Based Key-Value Store

(by phucnh)

Với dạng bài yêu cầu lưu trữ và tìm kiếm theo khóa, ta có thể nghĩ ngay tới cấu trúc dữ liệu bảng băm (hashtable). Tuy nhiên trong bài này, ta còn cần lưu trữ và tìm kiếm theo giá trị tuyến tính: thời gian dữ liệu được cập nhật. Để tìm kiếm nhanh giá trị có thời gian cập nhật gần nhất với biến timestamp của hàm get, ta có thể sử dụng cây tìm kiếm nhị phân (Binary Search Tree).

Với những phân tích trên, ta có giải thuật như sau: https://pastebin.com/76Pta6vu

Việc thêm và tìm kiếm trong bảng băm có độ phức tạp thời gian là O(1), còn trong cây tìm kiếm nhị phân là O(logn). Vì vậy, độ phức tạp về thời gian của hàm set và get đều là O(logn).

Trong bài này, ta có một rằng buộc "thời gian của hàm set là tăng dần". Như vậy, ta không cần thiết phải sử dụng cây tìm kiếm nhị phân để lưu trữ cặp "thời gian, giá trị", mà có thể sử dụng mảng. Mỗi khi thêm dữ liệu, ta chỉ cần thêm vào cuối mảng có khoá tương ứng. Với việc tìm kiếm theo giá trị thời gian, ta có thể áp dụng binary search. Bằng cách này, ta có thể tối ưu độ phức tạp về thời gian của hàm set còn O(1).

History

Vào ngày 28 tháng 8 năm 1991, trên tàu con thoi Atlantis, email đầu tiên từ không gian đã được gửi từ một máy Macintosh Portable thông qua Apple Link. Apple Link là một dịch vụ trực tuyến của Apple trước khi Internet được thương mại hóa.

Các phi hành gia Shannon Lucid và James C. Adamson đã gửi thông điệp sau:

Hello Earth! Greetings from the STS-43 Crew. This is the first AppleLink from space. Having a GREAT time, wish you were here,...send cryo and RCS! Hasta la vista, baby,...we'll be back!

Người nhận là Marcia Ivins, tại trung tâm vũ trụ Johnson

Macintosh Portable là máy tính chạy pin đầu tiên do Apple sản xuất. Mặc dù thu hút được nhiều sự chú ý vào thời điểm đó nhưng lại không thành công mấy vì pin của nó quá nặng với hơn 7kg. (source)

(by lpv)

Code & Tools

SurrealDB - một hệ thống document-graph database cho realtime web
Supabase - một phần mềm mở thay thế cho Firebase

Feedback

Bạn đánh giá nội dung số newsletter này thế nào?

(1 = Rất tệ / 5 = Rất tốt)

👎 1 —— 2 —— 3 —— 4 —— 5 👍

(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)

Grokking mang lại cho các bạn những kiến thức mới mẻ và hữu ích thông qua:

Tech Talk: Là một hoạt động thường xuyên của Grokking từ những ngày đầu thành lập. Tại đây các diễn giả chia sẻ kiến thức xoay quanh Computer Science và Software Engineer. Các buổi Tech Talk đều được record và upload lên kênh youtube của Grokking.
Grokking Knowledge Graph: Tập hợp những nguồn kiến thức phong phú với hơn 1000 bài viết chọn lọc, các đầu sách, khóa học, v.v… Các bài viết đều được gán nhãn để giúp bạn đọc dễ dàng tìm kiếm.
Webinar: Là chương trình kết nối các kỹ sư Việt Nam và các kỹ sư đang làm việc tại các công ty công nghệ hàng đầu thế giới.
Dijkstra: Một ấn phẩm được xuất bản bởi các thành viên của Grokking. Với những bài viết đào sâu vào kỹ thuật và kiến thức khoa học máy tính.
Kipalog: Nền tảng chia sẻ kiến thức dành cho các lập trình viên.
Newsletter: Những bài viết hay về công nghệ sẽ được gửi tới bạn hàng tuần qua email.

Chúc các bạn sẽ tìm được nhiều điều mới mẻ khi đến với Grokking và xin hẹn gặp lại các bạn vào tuần sau.

Quotes

A computer is like a violin. You can imagine a novice trying ﬁrst a phonograph and then a violin. The latter, he says, sounds terrible. That is the argument we have heard from our humanists and most of our computer scientists. Computer programs are good, they say, for particular purposes, but they aren’t ﬂexible. Neither is a violin, or a typewriter, until you learn how to use it.

― Marvin Minsky