Cài đặt Key-Value Storage bằng Go và C++ - Phần 1
1. Giới thiệu
Để nối tiếp bài blog trước về Key-Value Store sử dụng B-Tree. Bài blog lần này ta sẽ cài đặt thêm một Key-Value (KV) storage bằng cấu trúc dữ liệu khác là B+Tree. Dựa vào 2 storage đã có, ta xây dựng một service bằng Golang có sử dụng gRPC để gọi đến 2 storage này.
Project được đặt tên là GodBee. GodBee chỉ mang tính thử nghiệm sự kết hợp giữa Go và C++. Trong thực tế, các IO heavy sẽ được đẩy xuống tầng sâu nhất thường sử dụng C/C++, trong khi Golang thích hợp cho kiến trúc micro service.
Bài blog được chia làm 2 phần. Trong phần 1 này, ta sẽ tìm hiểu cụ thể về B+Tree và cách nhóm đã xây dựng một KV store bằng cấu trúc này. Các method được cung cấp bởi store bao gồm: Set, Get, Remove, Exist. Ở phần 2, ta sẽ đi sâu về về cách xây dựng service, làm thế nào có thể kết nối từ Golang sang C++.
2. B+Tree
B+Tree là một biến thể của B-Tree. B+Tree tuân theo các quy ước của B-Tree (về số lượng key trong node, cách cây tự cân bằng, v.v) do đó các bạn nên hiểu trước về cấu trúc và mục đích của B-Tree để tiếp cận cấu trúc B+Tree này và các ưu điểm của nó.
Để tìm hiểu B+Tree, đầu tiên hãy xem qua 2 cấu trúc node của B-Tree và B+Tree khi lưu trữ các cặp KV.
Có 2 điểm khác biệt chính của B+Tree node và B-Tree node:
- Value trong B+tree chỉ được lưu trữ ở leaf node. Do đó ta có thể bỏ đi trường Data pointer (value pointer) ở internal node.
- Leaf node trong B+tree không có pointer trỏ đến node con. Ngoài ra, ta đặt thêm một pointer trỏ đến leaf node tiếp theo.
Dựa vào 2 điểm khác biệt này, và B+Tree đem lại những ưu điểm:
- Do giảm đi một giá trị value pointer ở internal node và tree pointer ở leaf node, nên tăng số lượng key có thể lưu trong một node từ đó tăng độ phân nhánh và giảm độ cao của cây. Vì vậy, số lần truy cập đĩa của B+Tree giảm hơn so với B-Tree.
- Các node lá liên kết với nhau làm cho việc tìm kiếm trên khoảng hiệu quả hơn. Ví dụ ta muốn tìm các cặp KV có key trong khoảng từ 35–100. Công việc này sẽ dễ dàng hơn vì ta chỉ cần tìm key nhỏ nhất thỏa điều kiện trên, và duyệt tiếp cho đến khi key >100.
3. Implement Key-Value Storage with B+Tree
Mình sẽ không đi sâu vào thuật toán của các method mà sẽ trình bày về cách lưu trữ file và xử lí đụng độ. Các bạn có thể xem repo trên Github của nhóm để rõ hơn phần thuật toán nhóm mình đã implement B+Tree.
3.1 Cấu trúc file lưu trữ
Mình sử dụng tổng cộng 3 file lưu trữ:
- File Database: lưu các cặp Key-Value.
- File DeletedNodes: lưu offset các node bị xóa.
- File DeletedValues: lưu offset của các value bị xóa.
Để config các thông số của B+Tree KV Storage ta có file config như sau:
Trong đó:
- PAGE_SIZE: kích thước của một page (byte) (xem thêm phần cấu trúc tổng quát phía dưới)
- KEY_SIZE: kích thước tối đa của một key
- VALUE_SIZE: kích thước tối đa của một một value
- DEL_NODE_FILE_NAME, DEL_VALUE_FILE_NAME, DB_FILE_NAME: lần lượt là tên của các file DeletedNodes, DeletedValues, Database.
Cấu trúc tổng quá của file Database:
- Header: lưu trữ metadata của B+Tree như PAGE_SIZE, KEY_SIZE, VALUE_SIZE, vị trí của Root, tên của các file DeletedNodes, DeletedValues
- Ngay sau header là các Page, có 2 loại Page: Node page — lưu 1 B+Tree node, và Value page lưu các value. 2 page này cùng kích thước được lưu trong biến PAGE_SIZE của config (mặc định là 4096 bytes).
- Trong một Value page có thể lưu nhiều value, tùy theo kích thước tối đa của value và kích thước của page (mặc định là 1024 bytes)
- Các page được đánh ID tăng dần, dựa vào ID này ta sẽ xác định được vị trí cụ thể của một node trong file.
Cấu trúc Node page:
- Childs Offset: đối với internal node chứa các offset của các node con, đối với leaf node chứa offset của các value và offset của leaf node tiếp theo.
- Keys: Chứa giá trị các key thuộc node này.
- Flag: có 3 loại INTERNAL|LEAF|REMOVED. Cờ REMOVED đánh dấu node đã xóa.
- Size: số lượng key hiện có trong node.
- Dựa vào các kích thước đã config sẵn, ta có thể tính được tham số MaxDegree (độ phân nhánh) của cây.
Cấu trúc Value Page:
Một value page có thể chứa nhiều vào value tùy vào kích thước tối đa của value - VALUE_SIZE và PAGE_SIZE.
Cách đánh Offset:
Nếu dùng hẳn offset chính xác vị trí bắt đầu của một node hay value thì sẽ lãng phí kha khá các giá trị, và số lượng offset có thể sử dụng sẽ ít đi khá nhiều. Nếu ta chỉ dùng ID của page như đã nói ở phần cấu trúc tổng quan của file database thì ta không thể biết được bị trí chính xác của value, vì trong một page có thể tồn tại nhiều value. Vì vậy để xác định vị trí của một page, mình dùng một giá trị 8 bytes hay 64 bits.
64 bit này chia ra làm 2 phần, phần đầu lưu ID của page đó, phần cuối sẽ lưu vị trí của value trong value page (với node page mặc định là 0). Số lượng bit cụ thể của mỗi phần do PAGE_SIZE và VALUE_SIZE quyết định.
Ví dụ với PAGE_SIZE là 4096 bytes, VALUE_SIZE là 1024 bytes. Vậy một value page có thể lưu tối đa 4 value. Với 4 value này, ta cần 2 bit cuối để đánh vị trí của một value, và 62 bit còn lại để lưu ID. Cụ thể hơn, nếu một value nằm vị trí thứ 2 trong page, và page này có ID là 5 thì offset của nó là 010110. Nếu một node page có ID là 6 thì ID là 011000.
3.2 Xử lí đụng độ
Do có nhiều threads cùng truy cập vào storage nên ta quan tâm đến việc xử lí đụng độ.
Vấn đề:
- Reader write problem: với cùng một dữ liệu, tại một thời điểm, nhiều thread có thể cùng đọc một lúc tuy nhiên không được tồn tại thread đang ghi vào dữ liệu này. Mặt khác, tại một thời điểm, chỉ có duy nhất 1 thread được ghi vào dữ liệu và không có thread đọc hay ghi khác được truy cập trong thời gian này.
- Khi thực hiện lời gọi từ Go service xuống C++ storage, ta không kiểm soát được số lượng threads tạo ra. Do đó, việc phục vụ riêng một con trỏ FILE cho từng thread làm tốn memory, chưa kể việc mở đóng file nhiều sẽ gây giảm hiệu năng. Nếu ta chỉ có một con trỏ FILE xài chung cho tất cả các thread, điều này làm giảm hiệu năng của storage vì các thread không thể đồng thời truy cập file.
Để giải quyết vấn đề đầu tiên, nhóm mình sử dụng read lock và write lock.
Request cần lấy được read lock nếu nó muốn thực hiện Get và Exist. Đối với request cần thực hiện Set và Remove, nó cần đạt được write lock.
Với vấn đề thứ 2, ta tạo một pool các con trỏ FILE để có thể tái sử dụng các con trỏ FILE (FILE*) hiệu quả hơn. Pool này có thể implement bằng queue/stack. Tất nhiên, số lượng FILE* trong pool là hạn chế nên ta phải đặt lock trên pool này. Khi một thread muốn làm việc trên file, nó sẽ xem trong pool có FILE* nào đang có sẵn không. Nếu có, chỉ đơn tuần là pop 1 FILE* trong pool ra xài, còn nếu pool trống thì thread đó phải chờ đến khi một thread khác push lại FILE* vào pool. Đoạn code trên mô tả việc lấy FILE* từ pool và trả FILE* vào lại pool:
4. Những điểm cần cải thiện
Với cấu trúc file này, việc lưu trữ key và value trong page gây ra những hạn chế như:
- Giảm kích thước key và value có thể lưu trữ,
- Việc cấp phát sẵn một vùng nhớ cố định cho value và key có thể gây lãng phí tài nguyên với những key và value kích thước nhỏ.
Ta có thể cải thiện bằng cách tách riêng file lưu trữ value và tìm cách để xác định vị trí value này. Nếu key kích thước quá lớn, ta có thể suy nghĩ việc ứng dụng hash vào để xử lí.
5. Kết luận
Ở bài blog này, ta đã tìm hiểu cách để xây dựng storage của GodBee sử dụng B+tree. Các bạn có thể tham khảo repo của nhóm để hiểu hơn cách nhóm mình đã xây dựng storage. Ở phần tiếp theo, nhóm mình sẽ trình bày về cách xây dựng service bằng Go để có thể gọi đến Storage này.
Slide: B+Tree, KV-Store Service
Link repo github: https://github.com/zalopay-oss/godbee
Cám ơn anh AJ Pham đã hỗ trợ nhóm em thực hiện project này.
