Binary Index Tree trong Cơ sở dữ liệu

Một trong những điểm thú vị nhất khi phát triển các hệ thống Business là lập báo cáo doanh thu.

Mình đã từng maintain hệ thống cảnh báo sớm của Cục quản lý cạnh tranh, hệ thống do đối tác nào đó viết không phải mình. Trong bài viết này mình sẽ lấy hệ thống trên làm ví dụ và cách xử lý của mình để đảm bảo tốc độ truy xuất báo cáo.

Demonstration

Dữ liệu gồm mấy trăm triệu dòng có kiểu định dạng như sau: quốc gia, loại mặt hàng, loại nhóm hàng, tổng nhập khẩu, tổng xuất khẩu, thời gian (định dạng yyyy-mm)

Để đánh giá thị trường nhập khẩu chẳng hạn thì cần so sánh tổng nhập khẩu của quốc gia này với quốc gia kia trong cùng quý, cùng tháng. Thậm chí còn cần gom lại theo cả mặt hàng và nhóm hàng nữa.

Các yêu cầu khác thì như sau:

• Người dùng được phép tùy chọn gom lại theo cái gì bằng thao tác trên Website của hệ thống.
• Dữ liệu của những năm/tháng cũ có thể được cập nhật lại vào bất kì thời điểm nào. Ví dụ dữ liệu năm 2012 có thể có thay đổi về mặt doanh thu.

Các bạn có thể thấy với chỉ 5 6 trường dữ liệu, chúng ta có rất nhiều chiều để tính tổng và so sánh.

Câu chuyện cũ

Giải pháp ban đầu tiên của đối tác kia là sử dụng nó nhiều pivot table (bạn hình dung nó là một temporary table), thực hiện full table scan cả trăm triệu dòng để lấy ra các thông tin aggregation xác định.

Ví dụ: Table X thì gom theo quý 1 - 2015 và theo quốc gia. Table Y thì gom theo quý 1 2015 là theo nhóm hàng, theo quốc gia.

Chưa nói tới số lượng table phải quản lý là khá nhiều, bản thân cách lưu trữ này đòi hỏi phải tính lại nếu có có sự thay đổi về dữ liệu. Mỗi lần tính toán hoặc cập nhật như vậy hệ thống chạy gần 3 ngày mới xong (hệ thống DB gồm 3 máy chủ oracle database, master-slave).

Ý tưởng xử lý ban đầu

Thường thì chúng ta nghĩ ngay tới là sử dụng các hệ thống BigData. Tuy nhiên:

• Bạn cần deploy thêm máy chủ và thay đổi toàn bộ cấu trúc dữ liệu.
• Vẫn phải lưu các pivot data vì query data là động từ phía người dùng. Không thể mỗi lần người dùng query lại đi chạy Map Reduce để tính toán được :D
• Vẫn không giải quyết được triệt để độ linh động về thời gian. Chẳng han không phải tính theo quý mà chỉ từ tháng 12 năm trước tới tháng 1 năm nay mà thôi.
• Khi cập nhật dữ liệu, vẫn cần tính toán lại rất rất nhiều. Thông thường một lần cập nhật là cập nhật luôn cả mấy chục triệu dòng. Cập nhật tháng 10 năm 2014 thì đồng nghĩa với dữ liệu tổng từ năm 2012 đến bây giờ cũng phải cập nhật theo.

TL;DR

Thời điểm đó mình quyết định phải xử lý bài toán này bằng algorithm. Và một thuật toán kinh điển rất phù hợp cho bài toán này là binary index tree. Tuy nhiên việc đưa nó cơ sở dữ liệu lại không dễ dàng, mặc dù hết sức thú vị.

Đầu tiên bạn có thể tìm hiểu về thuật toán trong link này: TopCoder - Binary Index Tree và GeeksforGeeks - Binary Index Tree

Mình sẽ nói ngắn gọn ở đây

• Giả sử mình có một mảng gồm N số nguyên
• Mình có 2 yêu cầu là: cập nhật bất kì số nguyên nào của mảng và tính tổng các số trong một khoảng bất kì nào đó (từ phần tử mảng ở vị trí A tới vị trí B chẳng hạn)
• Binary index tree hoạt động như sau: một node có index là K1 sẽ quản lý tổng (hoặc chỉ số nào đó khác tùy bài toán của bạn) của các phần tử từ K1 tới K2 = K1 - lowbit(K1) = K1 - (K1 & -K1).
• Tổng các phần tử từ 1 đến K1 sẽ được tính bằng S(K1) = F[K1] + F[K2 = K1 - (K1 & -K1)] + F[K3 = K2 - (K2 & -K2)] + ... + F[1]. Tổng số bước nhảy của phép tính trên không quá là log(N)
• Để tính tổng các phần tử từ vị trí A tới B thì: tính tổng từ 1 tới B và từ 1 tới A - 1 rồi trừ cho nhau là xong: S[A,B] = S(B) - S(A-1)
• Thao tác thay đổi giá trị tại bất kì thời điểm nào cũng diễn ra trong logN

Whew!

Quay lại bài toán ban đầu, điểm đáng lưu ý nhất của chúng ta là trường thời gian. Nó biến thiên, đóng vai trò là xương sống của các phép tính aggregation.

Nếu bạn hình dung thời gian đóng vai trò index giống mấy cái K1 hoặc K2 ở trên; còn giá trị cần tính là tổng nhập khẩu hoặc tổng xuất khẩu; chiều cần tính là quốc gia, mặt hàng, loại mặt hàng!! Tưởng tượng chút nhỉ.

Thiết kế và cập nhật dữ liệu

Mình sẽ thiết kế một table như sau:

CREATE TABLE pivot_nhap_khau (
    Index bigint, # index ở đây chính là chiều thời gian, chính là k1 k2 ... của chúng ta
    Nation int,
    ProductType int,
    ProductID bigint,
    Value float,
    Primary Key (Index, Nation, ProductType, ProductID)
)

Với mỗi dữ liệu được cập nhật hoặc thêm mới từ cái table cỡ bự phía trên, ta cũng đồng thời cập nhật vào table này, tác động tới một loạt các dòng dữ liệu, tuy nhiên không quá log(N) trong đó N chính là tổng số tháng.

Ví dụ thời điểm bắt đầu dữ liệu là tháng 1 năm 2012, và chúng ta muốn hệ thống này hoạt động 100 năm, tức là chúng ta có 12 * 100 = 1200 tháng. Vậy một thao tác cập nhật sẽ tác động không quá log(1200), cỡ 12 dòng gì đó.

Điểm thú vị lớn nhất là chiều dữ liệu. Ví dụ:

• Để gom theo ProductType và ProductID mà không quan tâm tới quốc gia, ta ghi nhận thêm một dòng dữ liệu đặc biệt nữa là (index, 0, ProductType, ProductID) trong đó 0 chính là đại diện cho việc gom của chúng ta.
• Ta sẽ cập nhật cho các điểm: (index1, 0, 34, 12) rồi (index2, 0, 34, 12) and so on. Trong đó index2 = index1 + (index1 & -index1), cứ như thế cho tới khi cái index của chúng ta vượt quá 1200 (lưu ý ở đây: giá trị 34 là id của loại hàng thủy hải sản, còn 12 là id của mặt hàng cá ngừ)

Tương tự, nếu muốn gom theo nation mà không quan tâm tới product thì ta cập nhật theo (index, Nation, 0, 0)

Select dữ liệu

Để tính tổng giá trị nhập khẩu của các ngừ trên toàn thế giới từ tháng 1 2012 tới tháng 7 năm 2015 thì ta tính như sau:

• Tổng cá ngừ toàn thế giới từ điểm start point tới tháng 1 - 2012: index1 = tháng 1 2012, tính sum của các row sau: (index1, 0, 34, 12) + (index2, 0, 34, 12) + ... trong đó index2 = index1 - (index1 & -index1) (khác với ở trên nhé, ở trên là update nên ta cộng với lowbit, ở đây là trừ)
• Tương tự với tháng 7 2015
• Trừ hai kết quả cho nhau là xong
• Tổng số row cần lấy ra không quá 2 * log(N), cỡ 24 row gì đó.

Kết quả thu được

• Cập nhật lại dữ liệu của một tháng diễn ra trong vài tiếng thay vì vài ngày như trước.
• Select sum cực nhanh, đáp ứng yêu cầu nhiều lượt truy cập cùng lúc của người dùng.
• Có thể tính toán tại bất kì range nào thay vì chỉ theo quý. Ở ví dụ trên ta tính toán dữ liệu của nhiều năm liền, nhiều tháng liền nhau.

Bonus point

Điểm lý thú khác chính là khả năng sharding của dữ liệu thời gian, bài toán trên mình giới hạn 100 năm, muốn thêm 100 năm nữa thì mình sẽ thêm một table như vậy, lưu điểm mốc từ năm thứ 100 tới năm thứ 200. And so on.

PS: mình đã và đang sharding cho dự án hiện tại đang làm. Advantage là khả năng scale và tăng tốc độ xử lý cả update lẫn select.

Conclusion

Trên đây là một kĩ thuật mình đã đưa vào khá nhiều production. Các bạn có thể trao đổi bằng comment bên dưới, mình rất mong có thể học hỏi các kĩ thuật xử lý khác :D

Have fun!