Cấu trúc dữ liệu cho các ứng dụng dữ liệu chuyên sâu [PDF]
(cs-people.bu.edu)- Cấu trúc dữ liệu key-value là thành phần cốt lõi của các hệ thống dựa trên dữ liệu, và hiệu năng có thể chênh lệch rất lớn tùy theo workload và điều kiện phần cứng
- Cấu trúc vật lý được chia thành bố cục dữ liệu, metadata phục vụ tra cứu, và thuật toán lưu trữ/truy xuất; chúng cũng được gọi là access methods, data containers, hoặc search structures
- Workload được biểu diễn bằng tổ hợp của point query, range query, chèn, xóa và cập nhật; dung lượng và chi phí của bộ nhớ/lưu trữ bền vững cũng là yêu cầu thiết kế
- B+-tree mạnh về đọc và range query, nhưng khi số lần chèn/cập nhật tăng lên thì việc tái tổ chức các nút lá trở thành gánh nặng; LSM-tree xử lý lượng lớn thao tác chèn bằng cơ chế buffering và merge
- Trong môi trường mà việc di chuyển dữ liệu là nút thắt cổ chai, cần chọn cấu trúc hiện có hoặc thiết kế cấu trúc mới phù hợp với ứng dụng mới, thay đổi phần cứng và sự gia tăng dữ liệu
Vấn đề mà cấu trúc dữ liệu key-value giải quyết
- Cấu trúc dữ liệu key-value được dùng rộng rãi trong các ứng dụng dữ liệu chuyên sâu, và nhờ tính tổng quát của mô hình key-value, nó trở thành nền tảng của nhiều hệ thống
- Một key ánh xạ tới một value, nhưng cùng một value có thể liên kết với nhiều key
- Ý nghĩa của value thay đổi tùy theo ứng dụng
- Có thể là bản ghi của cơ sở dữ liệu quan hệ
- Có thể là Pandas DataFrame
- Có thể là một tập các field trong hệ thống NoSQL mà ứng dụng sẽ parse và sử dụng
- Trong hệ thống xử lý dữ liệu mạng xã hội, có thể bao gồm tham chiếu tới các đối tượng lớn như ảnh hoặc video
Cấu thành vật lý và phạm vi áp dụng
- Về mặt vật lý, cấu trúc dữ liệu key-value gồm ba thành phần
- Dữ liệu được lưu theo một layout cụ thể
- Metadata tùy chọn giúp việc tìm kiếm dữ liệu
- Thuật toán hỗ trợ các phép toán lưu trữ và truy xuất
- Cấu trúc dữ liệu được sử dụng dưới nhiều hình thức trong hệ thống dữ liệu, hệ điều hành, hệ thống file, compiler và hệ thống mạng
- Các ví dụ trong tài liệu chủ yếu xoay quanh hệ thống dữ liệu quy mô lớn và thiết bị lưu trữ thứ cấp, nhưng cách phân tích và thiết kế cũng áp dụng được cho hệ thống in-memory
- Phân tích này được xây dựng cho môi trường có từ hai tầng bộ nhớ/lưu trữ trở lên
Workload và chi phí quyết định thiết kế
- Ứng dụng hoặc workload có thể được biểu diễn bằng tổ hợp các phép toán key-value
-
Point query
-
Range query
- Chèn
- Xóa
- Cập nhật
- Dung lượng cần thiết và chi phí của bộ nhớ cùng lưu trữ bền vững cũng cấu thành yêu cầu của ứng dụng
- Tùy theo loại hệ thống mà cấu trúc dữ liệu cần tối ưu sẽ khác nhau
- Hệ thống file quản lý metadata và nội dung file bằng các cấu trúc dữ liệu được tối ưu cho cập nhật thường xuyên
- Compiler quản lý biến bằng hash map trong suốt vòng đời của biến, và biểu diễn toàn bộ hình dạng của chương trình bằng abstract syntax tree
- Thiết bị mạng cần các cấu trúc dữ liệu chuyên biệt để lưu trữ và truy cập bảng định tuyến một cách hiệu quả
-
Sự đối lập trong lựa chọn giữa B+-tree và LSM-tree
- B+-tree được dùng nhiều để cân bằng chi phí đọc và ghi trong các workload có ít thao tác chèn/cập nhật nhưng nhiều point query và range query
- Fanout lớn của nút giúp giảm số lần truy cập bộ nhớ phụ cần thiết khi đi từ root tới leaf, và các level phía trên được cache ở tầng bộ nhớ nhanh hơn
- Nó duy trì mọi key được sắp xếp trong các nút lá và nối các nút lá bằng linked list để hỗ trợ range query
- Khi số lần chèn và cập nhật tăng lên, việc tái tổ chức hoặc tách các nút lá trở nên cần thiết và có thể trở thành nút thắt hiệu năng
- LSM-tree dùng một cách tiếp cận khác cho workload có nhiều thao tác chèn
- Đưa mọi cập nhật vào một bộ đệm bộ nhớ chung
- Khi bộ đệm đầy thì flush xuống đĩa
- Khi các bộ đệm tích lũy lại thì merge thành các tập dữ liệu đã sắp xếp lớn hơn
- Việc cập nhật được xử lý theo chính sách out-of-place, nên nhiều cặp key-value có cùng key có thể cùng tồn tại trong cấu trúc
- Giá trị hiện tại của một key là cặp key-value được chèn gần nhất
Cấu trúc dữ liệu thích ứng
- Tài liệu không chỉ đề cập cách thiết kế cấu trúc dữ liệu dựa trên dự báo workload từ trước, mà còn nói tới các cấu trúc có thể dần tiến tới trạng thái lý tưởng trong quá trình chạy
- B+-tree và LSM-tree trong thiết kế ban đầu đều áp đặt thứ tự sắp xếp trong các nút thường trú trên đĩa để trả lời mọi point query hoặc range query
- Cấu trúc dữ liệu thích ứng có thể bắt đầu từ một hoặc nhiều nút chưa được sắp xếp, rồi dần sắp xếp khi có cơ hội
- Database cracking sử dụng mẫu truy cập của các truy vấn đến để tái tổ chức vật lý dữ liệu nền tảng theo cách liên tục và tăng dần
- Mục tiêu là cải thiện hiệu năng của các truy vấn trong tương lai
Phân cấp phần cứng và bức tường bộ nhớ
- Sự phát triển của phần cứng tạo ra những thách thức và cơ hội mới cho thiết kế cấu trúc dữ liệu
- Ở phân cấp lưu trữ, các tầng thấp hơn cung cấp nhiều dung lượng hơn với chi phí thấp hơn nhưng độ trễ truy cập lớn hơn, còn các tầng phía trên gần bộ xử lý hơn thì nhanh hơn nhưng nhỏ hơn và có chi phí trên mỗi byte cao hơn
- Tầng trở thành nút thắt của một ứng dụng cụ thể sẽ thay đổi tùy theo kích thước dữ liệu của ứng dụng và dung lượng lưu trữ của từng tầng
- B+-tree ban đầu được thiết kế để tối đa hóa fanout nhằm giảm truy cập đĩa, nhưng khi bộ nhớ lớn hơn và dữ liệu nằm trong RAM hoặc bộ nhớ phụ không bay hơi thì trade-off đã thay đổi đáng kể
- B+-tree in-memory cho hiệu năng tốt nhất ở fanout nhỏ
- Bức tường bộ nhớ (memory wall) chỉ xu hướng khoảng cách giữa tốc độ bộ xử lý và tốc độ bộ nhớ ngoài chip ngày càng lớn
- Từ đầu những năm 2000, hệ điều hành và hệ thống quản lý dữ liệu đã được thiết kế lại để tối ưu việc sử dụng bộ nhớ đệm cache
Không gian thiết kế và các guideline
- Tài liệu hệ thống hóa không gian các lựa chọn thiết kế cấu trúc dữ liệu và cách chọn cấu trúc phù hợp với mục tiêu ứng dụng và workload
- Do phần cứng và đặc tính dữ liệu liên tục thay đổi, thiết kế cấu trúc dữ liệu cũng cần được đổi mới liên tục
- Không gian thiết kế và các guideline đã được hệ thống hóa này có thể dùng để chọn cấu trúc dữ liệu hiện có phù hợp nhất, hoặc thiết kế cấu trúc dữ liệu mới cho workload cụ thể
1 bình luận
Các ý kiến trên Hacker News
Tôi mới chỉ đọc lướt qua, nhưng bài viết này là một tài liệu khảo sát cực kỳ xuất sắc bao quát một phạm vi rất rộng
Nó không chỉ dừng ở việc liệt kê các cấu trúc dữ liệu, mà còn giúp hệ thống hóa trong đầu những yếu tố cần cân nhắc khi tạo hoặc sử dụng cấu trúc dữ liệu trong ứng dụng
Một trong các tác giả của cuốn sách này đang điều hành một phòng thí nghiệm trong lĩnh vực này
Cũng có một công cụ thú vị giúp thiết kế cấu trúc dữ liệu tối ưu: http://daslab.seas.harvard.edu/datacalculator/
Tôi muốn biết thêm các tài liệu được khuyến nghị về chủ đề này
Bài báo rất hay, và tôi cũng biết Designing Data-Intensive Applications của Martin Klepmann, nhưng cuốn đó thiên về cơ sở dữ liệu hơn là cấu trúc dữ liệu
Nếu thiết kế một cấu trúc để chứa một loại dữ liệu phân tích nào đó, phần đối chiếu rất quan trọng giữa mảng cấu trúc và cấu trúc mảng lại bị thiếu
Vì vậy nội dung đó có được thảo luận, chỉ là không giải thích bằng các thuật ngữ mảng cấu trúc/cấu trúc mảng mà thôi
Tôi muốn mua một cuốn, nhưng trên Amazon giá 100 đô la
Đây là một cấu trúc méo mó khiến cả tác giả lẫn độc giả đều thiệt
Cần có mục lục
Ngay cả khi bảo nó bỏ qua phần đầu trang và chân trang cũng vậy; tôi cứ nghĩ trình độ mới nhất đã tốt hơn nhiều rồi