Skiplist và Skiptree: Khi cấu trúc dữ liệu "ngách" cứu rỗi bài toán BigQuery

Skiplist và Skiptree: Khi cấu trúc dữ liệu "ngách" cứu rỗi bài toán BigQuery

Trong một lần tham gia câu lạc bộ sách về "Nghệ thuật Lập trình Đa bộ xử lý" (The Art of Multiprocessor Programming), chủ đề về Skiplist đã được đưa ra thảo luận. Trong suốt sự nghiệp của mình, Skiplist dường như luôn là một cấu trúc dữ liệu ngách, với một nhóm người hâm mộ cuồng nhiệt nhưng không có nhiều ứng dụng thực tế đối với tôi. Tuy nhiên, khoảng sáu năm trước, chúng tôi đã gặp phải một vấn đề tại Antithesis tưởng chừng như không thể giải quyết, cho đến khi nhận ra rằng một sự mở rộng của Skiplist chính là câu trả lời chúng tôi cần.

Trước khi đi sâu vào giải pháp đó, hãy cùng tìm hiểu Skiplist là gì.

Cấu trúc Skiplist

Skiplist là gì?

Skiplist là một cấu trúc dữ liệu ngẫu nhiên, về cơ bản là một sự thay thế trực tiếp cho cây tìm kiếm nhị phân (binary search tree) với cùng giao diện và cùng độ phức tạp tiệm cận cho các thao tác. Nhiều người thích sử dụng nó vì có thể triển khai các phiên bản đồng thời không khóa (lock-free) tương đối đơn giản và dễ hiểu, hoặc đơn giản là vì sở thích cá nhân.

Về mặt triển khai, bạn có thể hình dung Skiplist giống như một danh sách liên kết (linked list) kết hợp với các "làn đường nhanh" (express lanes). Bạn bắt đầu với một danh sách liên kết cơ bản, sau đó thêm một hệ thống phân cấp các danh sách liên kết khác với số lượng nút dần ít đi. Trong ví dụ trên, các nút ở các danh sách cấp cao hơn được chọn theo xác suất, với mỗi nút có 50% cơ hội được thăng cấp lên tầng tiếp theo.

Điều này giúp tăng tốc độ tìm kiếm vì bạn có thể sử dụng các danh sách cấp cao hơn để "nhảy" nhanh đến nút bạn muốn tìm. Trong một danh sách liên kết thông thường với n nút, việc tìm kiếm một nút sẽ mất thời gian O(n). Skiplist cho phép bạn nhảy cấp độ, với mỗi cấp độ giảm một nửa số lượng nút cần kiểm tra, giúp bạn tìm thấy nút trong thời gian O(log n).

Tuy nhiên, sau khi đọc về cấu trúc dữ liệu này, tôi thực sự chưa bao giờ nghĩ đến nó nữa, cho đến một ngày nọ chúng tôi gặp phải vấn đề sau tại Antithesis...

Bài toán tại Antithesis

Antithesis chạy phần mềm của khách hàng nhiều lần để tìm lỗi. Mỗi lần chạy, công cụ fuzzing của chúng tôi sẽ chèn các lỗi khác nhau và yêu cầu mã kiểm thử đưa ra các quyết định ngẫu nhiên khác nhau. Theo thời gian, những lựa chọn này tạo ra một cây phân nhánh của các dòng thời gian: mỗi đường đi từ gốc đến lá đại diện cho một chuỗi các lựa chọn mà công cụ fuzzing đã thực hiện và kết quả diễn ra sau đó.

Chúng tôi có rất nhiều truy vấn cần thực hiện, về cơ bản là các thao tác gấp (fold operations) lên hoặc xuống cây này. Ví dụ, với một thông báo nhật ký cụ thể, lịch sử duy nhất của các sự kiện dẫn đến nó là gì? (Đi lên theo các con trỏ cha từ nút đó về gốc).

Vấn đề là lượng dữ liệu đầu ra từ phần mềm đang thử nghiệm quá lớn, chúng tôi phải đưa tất cả vào một cơ sở dữ liệu phân tích, và tại thời điểm đó chúng tôi đang sử dụng Google BigQuery. Các cơ sở dữ liệu phân tích được tối ưu hóa để quét song song một lượng dữ liệu khổng lồ để tính toán kết quả tổng hợp. Sự đánh đổi là chúng rất chậm trong các truy vấn điểm (point lookups), nơi bạn lấy một hàng cụ thể theo ID của nó.

Điều này rất quan trọng, bởi vì cách tự nhiên để biểu diễn một cây trong cơ sở dữ liệu là sử dụng các con trỏ cha — mỗi nút là một hàng trong bảng, với một cột parent_id trỏ đến cha của nó. Để trả lời câu hỏi như "cho tôi xem lịch sử dẫn đến thông báo nhật ký này", bạn sẽ cần đi lên cây từng nút một: tra cứu nút, lấy ID cha, tra cứu nút cha, v.v. Mỗi bước là một truy vấn điểm. Trong một cơ sở dữ liệu OLTP được thiết kế cho truy vấn điểm, điều này ổn. Nhưng trong BigQuery, về cơ bản mọi thao tác đều dẫn đến việc quét toàn bộ bảng, điều này có nghĩa là ngay cả những truy vấn cơ bản nhất cũng sẽ thực hiện O(depth) lần đọc trên toàn bộ tập dữ liệu. Thật khủng khiếp!

Một giải pháp thay thế là chia nhỏ dữ liệu: lưu trữ chỉ cấu trúc cây (các con trỏ cha) trong một cơ sở dữ liệu tốt về truy vấn điểm, và giữ dữ liệu chính trong BigQuery. Nhưng cách tiếp cận này sẽ tạo ra các vấn đề khác. Mỗi lần chèn sẽ cần ghi vào cả hai hệ thống, và vì chúng tôi muốn phân tích dữ liệu trực tuyến (trong khi dữ liệu mới đang được ghi vào), việc giữ cho hai cơ sở dữ liệu nhất quán sẽ yêu cầu một cơ chế như cam kết hai pha (2PC). Tôi thà không tự tạo ra các vấn đề 2PC mới khi không thực sự cần thiết. Hơn nữa, vào thời điểm đó, BigQuery có ngữ nghĩa nhất quán rất lỏng lẻo, nên không rõ việc giữ hai hệ thống đồng bộ có khả thi hay không.

Skiplist đến giải cứu! Hay chính xác hơn là một thứ kỳ lạ chúng tôi gọi là "Skiptree"

Vậy Skiptree là gì? Nó giống như Skiplist, nhưng là một cây.

Cấu trúc Skiptree

Nói cách khác, bạn có một cây cấp độ 0, sau đó một hệ thống phân cấp các cây ở phía trên nó. Mỗi cây có khoảng 50% số nút của cấp độ bên dưới (các nút bị loại bỏ được hiển thị bằng các đường nét chấm xám trên sơ đồ).

Nếu bạn chọn bất kỳ đường đi nào từ gốc đến lá, các nút dọc theo đường đi đó — cùng với sự xuất hiện của chúng trong các cây cấp cao hơn — tạo thành một Skiplist. Vì vậy, Skiptree thực sự chỉ là một bunch of Skiplists chia sẻ cấu trúc, một cho mỗi đường đi từ gốc đến lá trong cây.

Để lưu trữ Skiptree, bạn tạo một bảng SQL cho mỗi cấp độ: tree0, tree1, v.v. Mỗi bảng có một hàng cho mọi nút trong cây đó. Thay vì có một cột parent_id duy nhất, nó có một cột cho nút tổ tiên gần nhất ở cây trên (chúng ta gọi là next_level_ancestor) và một cột khác (gọi là ancestors_between) chứa danh sách tất cả các nút giữa nút hiện tại và nút tổ thân cấp trên.

Các bảng cấp cao hơn hoạt động tương tự. Bạn có thể sử dụng các bảng này để tìm các tổ tiên của một nút bằng cách xâu chuỗi các JOINs, làm theo cách của bạn lên các bảng.

Ví dụ, để tìm tất cả tổ tiên của nút I, bắt đầu tại bảng tree0. Cột next_level_ancestor cho bạn biết cần JOIN trên nút C trong bảng tree1, thu thập nút G từ cột ancestors_between trên đường đi. Sau đó trong bảng tree1, bạn thấy rằng next_level_ancestor là nút A, không có nút nào khác để thu thập trên đường đi. Nút A là gốc của cây nên giờ bạn đã xong: danh sách tổ tiên tổng cộng là [G, C, A]. Trong một cây sâu hơn, bạn sẽ tiếp tục bằng cách nhìn vào tree2, tree3, v.v.

Này! Bây giờ chúng ta có thể tìm tổ tiên với một truy vấn SQL không đệ quy duy nhất với số lượng JOIN cố định. Chúng ta chỉ cần làm... khoảng 40 JOINs.

Điều tuyệt vời nhất là, vào thời điểm đó, giá cả của BigQuery tính phí dựa trên lượng dữ liệu được quét, thay vì cho sức tính toán, và sự phân bố hình học của kích thước bảng có nghĩa là mỗi truy vấn này chỉ tốn gấp đôi một lần quét bảng thông thường.

Tất nhiên, có những nhược điểm, như chính câu lệnh SQL. Kích thước văn bản của các truy vấn này thường được đo bằng kilobyte. Nhưng tôi trông giống một người hang động sao? Chúng tôi không viết SQL. Chúng tôi đã viết một trình biên dịch bằng JavaScript để tạo ra nó. Và đó là cách hầu hết các thuộc tính kiểm thử trong Antithesis được đánh giá trong sáu năm đầu của công ty, cho đến khi chúng tôi cuối cùng viết cơ sở dữ liệu phân tích của riêng mình có thể thực hiện các truy vấn dạng cây hiệu quả.

Bài học kinh nghiệm

Sau này tôi phát hiện ra rằng Skiptree có liên quan chặt chẽ đến một cấu trúc dữ liệu thực tế gọi là skip graph, một cấu trúc dữ liệu phân tán dựa trên Skiplist. Điều này chỉ cho thấy rằng không có gì mới dưới mặt trời. Bất kỳ ý tưởng điên rồ nào bạn có, khả năng cao là một người điên rồ khác đã làm rồi. Bài học rút ra là: bạn không bao giờ biết khi nào một cấu trúc dữ liệu "ngoại lai" sẽ giúp bạn tiết kiệm rất nhiều thời gian và tiền bạc.

Ngoài ra, mặc dù Andy Pavlo đúng khi nói rằng một cây được viết tốt luôn đánh bại Skiplist, điều tuyệt vời về Skiplist là một triển khai ngây thơ hoàn toàn có hiệu suất đủ tốt. Điều này rất hữu ích khi bạn viết chúng bằng, ví dụ, SQL.

"Cảm ơn Phil Eaton đã gợi ý rằng chúng tôi nên viết lại điều này."