Cây LSM là gì? Giải thích về cây hợp nhất có cấu trúc nhật ký

Cây LSM là gì?

Cây hợp nhất có cấu trúc nhật ký (LSM) là một cấu trúc dữ liệu lưu đệm các thao tác ghi đến trong bộ nhớ rồi hợp nhất chúng xuống đĩa thành những lô bất biến đã được sắp xếp. Nó không bao giờ sửa đổi dữ liệu tại chỗ. Thay vào đó, nó tích lũy thay đổi và trì hoãn việc tổ chức dữ liệu, đánh đổi sự đơn giản ở phía đọc để lấy thông lượng ghi.

Cây LSM được chính thức hóa trong một bài báo năm 1996 của Patrick O’Neil, Edward Cheng, Dieter Gawlick và Elizabeth O’Neil mang tên Cây hợp nhất có cấu trúc nhật ký (LSM-tree). Trong khoảng một thập kỷ, nó vẫn là một cấu trúc học thuật tương đối ít được biết đến, cho đến khi Bigtable của Google xây dựng lớp lưu trữ dựa trên khái niệm này. Thiết kế của Bigtable tạo tiền đề cho LevelDB, LevelDB tạo tiền đề cho RocksDB, và một biến thể nào đó của cây LSM hiện nằm bên dưới phần lớn các hệ thống được xây dựng để tiếp nhận lượng dữ liệu lớn.

Tên gọi gợi ý rằng đây là một cây duy nhất, nhưng điều đó rất dễ gây hiểu lầm.

Hiểu chính xác hơn, cây LSM là sự phối hợp của ba thành phần:

• Một memtable: bộ đệm trong bộ nhớ lưu các thao tác ghi gần nhất
• Một write-ahead log (WAL): tệp chỉ cho phép nối thêm trên đĩa, giúp các thao tác ghi đó được lưu bền vững
• Một tập hợp ngày càng lớn các tệp sorted string table (SST): các tệp bất biến, đã sắp xếp, lưu toàn bộ dữ liệu cũ hơn

Gần như mọi đặc điểm đáng chú ý trong hành vi của LSM đều bắt nguồn từ cách dữ liệu di chuyển giữa ba thành phần này. Tất cả quá trình di chuyển đó bắt đầu bằng một lệnh gọi hàm duy nhất, có vẻ đơn giản đến mức dễ đánh lừa, thường được gọi là một thao tác put.

Put là gì?

Put là một lớp bao tiện ích. Ở bên trong, nó tạo một WriteBatch chứa đúng một bản ghi rồi chuyển lô đó cho Write(), hàm xử lý các thay đổi.

Điểm bắt đầu tự nhiên là Put(key, value), nhưng nói chính xác thì RocksDB không có thao tác như vậy. Mọi thao tác ghi đều là một lô, còn một put riêng lẻ đơn giản chỉ là lô gồm một phần tử. RocksDB hỗ trợ sẵn các thao tác ghi nguyên tử trên nhiều khóa vì đây là thao tác gốc của hệ thống.

Một WriteBatch là chuỗi byte nhỏ gọn với cấu trúc cố định. Cụ thể, phần đầu dài 12 byte chứa số thứ tự dài 8 byte và số lượng bản ghi dài 4 byte, theo sau là các bản ghi. Mỗi bản ghi gồm một thẻ loại dài một byte, một khóa có tiền tố độ dài và, đối với thao tác ghi, một giá trị có tiền tố độ dài.

Khẳng định trong bài viết đầu tiên của loạt bài này—khóa và giá trị là các mảng byte tùy ý—trở nên hoàn toàn đúng theo nghĩa đen. Cách mã hóa lô không biết và cũng không quan tâm các byte có ý nghĩa gì. Cấu trúc duy nhất được áp đặt là các tiền tố độ dài.

Mỗi lô được đóng dấu bằng một bộ đếm tăng đơn điệu gọi là số thứ tự. Nó thiết lập thứ tự toàn phần cho mọi thao tác ghi mà cơ sở dữ liệu từng chấp nhận. Số thứ tự là nền tảng giúp snapshot, thao tác đọc nhất quán và khôi phục sau sự cố trở nên khả thi. WAL có thể được phát lại vì mỗi bản ghi trong đó đều biết vị trí của mình trong hàng đợi.

Put, Delete, Merge

Một điểm quan trọng cần lưu ý là Put tương ứng với kTypeValue, còn Delete tương ứng với kTypeDeletion. Điều này có nghĩa thao tác xóa không thực sự loại bỏ dữ liệu. Thay vào đó, nó là một thao tác ghi—một tombstone—ghi nhận việc xóa, còn quá trình thu hồi dữ liệu thực tế được trì hoãn đến lúc compaction.

Put và Delete dùng chung định dạng WriteBatch với kTypeMerge, được ghi bởi thao tác Merge. Merge tồn tại vì quy trình đọc-sửa-ghi gây bất lợi nghiêm trọng cho một kho lưu trữ tối ưu cho ghi. Việc tăng một bộ đếm bằng Put đòi hỏi đọc giá trị hiện tại, cộng thêm một rồi ghi kết quả trở lại. Như vậy cần hai lần duyệt cơ sở dữ liệu chỉ để thay đổi một con số, trong đó thao tác đọc phải chịu toàn bộ chi phí của luồng đọc.

Merge bỏ qua hoàn toàn thao tác đọc.

Thay vào đó, nó nối thêm một toán hạng (tức phần mô tả thay đổi, chẳng hạn như “cộng một”) rồi trả về. Không có phép tính nào được thực hiện tại thời điểm ghi. Sau đó, cơ sở dữ liệu kết hợp các toán hạng thành giá trị cuối cùng bằng toán tử hợp nhất do ứng dụng cung cấp, khi khóa được đọc lần tiếp theo hoặc khi compaction gặp chuỗi này.

Delete trì hoãn việc thu hồi, còn Merge trì hoãn việc tính toán.

Toàn bộ đặc tính của cây LSM thể hiện rõ qua ba thẻ loại này: mọi thay đổi, kể cả những thay đổi phụ thuộc về mặt logic vào trạng thái hiện có, đều trở thành thao tác nối thêm mà không cần đọc trước. Trong cây LSM, mọi thứ đều là thao tác nối thêm.

Giải thích luồng ghi của cây LSM

Cách rõ ràng nhất để hiểu cây LSM là theo dõi một Put(key, value) từ lúc gọi hàm cho đến khi dữ liệu được ghi xuống đĩa.

Bước một: Write-Ahead Log

Thao tác ghi trước tiên được nối vào WAL. Việc nối thêm này diễn ra trước khi memtable được cập nhật, và thứ tự đó tạo thành cam kết về độ bền dữ liệu. Cụ thể, sau khi thao tác nối vào WAL hoàn tất, dữ liệu ghi đã tồn tại trên đĩa ở dạng có thể sống sót qua sự cố, dù chưa được tổ chức để phục vụ việc đọc.

Nối thêm vào nhật ký là thao tác đĩa rẻ nhất có thể, và đó chính là mục tiêu. Độ bền dữ liệu được đảm bảo với chi phí của thao tác ghi tuần tự.

RocksDB gộp các thao tác ghi đồng thời vào những group commit để tiếp tục phân bổ chi phí, còn tùy chọn sync kiểm soát việc dữ liệu nối thêm có được đẩy qua bộ nhớ đệm trang của hệ điều hành xuống bộ nhớ ổn định trước khi lệnh gọi trả về hay không.

Bước hai: Memtable

Sau khi độ bền dữ liệu được đảm bảo, thao tác ghi được chèn vào memtable. Theo mặc định, memtable của RocksDB là một skiplist. RocksDB dùng skiplist vì memtable cần tiếp nhận các thao tác ghi đồng thời và trả về nội dung theo thứ tự khóa đã sắp xếp, phục vụ cả thao tác đọc lẫn quá trình flush sau đó.

Skiplist hỗ trợ chèn đồng thời không khóa trong khi luôn duy trì thứ tự sắp xếp. Nó tương đương với việc phân loại giấy tờ ngay khi chúng đến, thay vì để chúng chất thành đống.

Bước ba: Memtable đầy

Memtable tăng kích thước cho đến khi chạm ngưỡng đã cấu hình (tức write_buffer_size), mặc định là 64 MB. Lúc này, nó được đánh dấu là bất biến, một memtable mới trống được thay vào và các thao tác ghi đến tiếp tục diễn ra không gián đoạn. Memtable đầy đã bị đóng băng sẽ chờ đến lượt được flush trong nền.

Các thao tác ghi không bao giờ bị chặn bởi chính quá trình flush.

Bước bốn: Flush

Một luồng nền ghi memtable bất biến ra đĩa dưới dạng tệp SST ở level 0 (L0) của cây. Vì skiplist đã được sắp xếp, quá trình flush chỉ cần một lượt tuần tự để duyệt các mục theo thứ tự và ghi chúng ra.

Nhiệm vụ của memtable đã hoàn thành và các mục WAL tương ứng cuối cùng có thể bị loại bỏ. Dữ liệu giờ đây tồn tại bền vững trên đĩa ở dạng cố định, có thể đọc được.

Bên trong tệp SST có gì?

Tệp SST là nơi dữ liệu tồn tại trong suốt phần đời còn lại. Nó được tổ chức thành ba loại block và một footer:

• Data block: chính các mục đã sắp xếp, mỗi block có kích thước vài kilobyte và được nén riêng
• Index block: ánh xạ phạm vi khóa tới offset của block để thao tác tra cứu có thể chuyển thẳng đến đúng block
• Bloom filter block tùy chọn: bản tóm tắt xác suất nhỏ gọn có thể trả lời “khóa này chắc chắn không nằm trong tệp này” mà không cần đọc thêm bất kỳ dữ liệu nào
• Footer: xác định vị trí của tất cả thành phần trên

Mọi thành phần trong bố cục này đều nhằm giúp các thao tác đọc sau này truy cập ít byte nhất có thể, đặc biệt là index và bloom filter.

Theo dõi luồng ghi

Mọi nội dung giải thích ở trên đều có thể được quan sát trực tiếp. Phần này sẽ nhanh chóng theo dõi một Put đi qua cơ sở dữ liệu bằng ldb và sst_dump, các công cụ kiểm tra đi kèm RocksDB. Ví dụ sử dụng Rust và crate rocksdb, nhưng binding nào cũng phù hợp.

Điều kiện tiên quyết

Để làm theo, hãy cài đặt các công cụ dòng lệnh RocksDB và bộ công cụ Rust.

Trên macOS, brew install rocksdb cung cấp cả ldb và sst_dump. Trên Debian/Ubuntu, gói cần cài là rocksdb-tools.

Sau khi cài đặt, hãy tạo một dự án mới:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

Crate rocksdb biên dịch thư viện RocksDB C++ từ mã nguồn trong lần build đầu tiên, vì vậy lần chạy cargo run ban đầu có thể mất vài phút.

Bước một: Ghi và dừng

Thay nội dung của src/main.rs bằng đoạn mã sau:

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Chạy một lần bằng cargo run, sau đó liệt kê thư mục cơ sở dữ liệu vừa được tạo:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT và tệp MANIFEST theo dõi danh mục tệp của cơ sở dữ liệu, còn OPTIONS ghi lại cấu hình được dùng khi mở cơ sở dữ liệu. LOG, không có số đi kèm, là nhật ký văn bản mà con người có thể đọc để gỡ lỗi; đừng nhầm nó với 000004.log, chính là write-ahead log.

Số hiệu tệp cụ thể sẽ khác nhau giữa các lần chạy, nhưng cấu trúc thì không đổi.

Lưu ý rằng thư mục chưa có một tệp .sst nào. Thao tác ghi đã bền vững vì vẫn tồn tại sau khi tiến trình thoát, nhưng hiện chỉ có dưới dạng một bản ghi WAL. Đây chính là sự tách biệt giữa độ bền và việc tổ chức dữ liệu.

Bước hai: Kết xuất WAL

Trỏ ldb đến bất kỳ tệp .log nào có trong thư mục:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

Chúng ta có một lô: số thứ tự 1, chứa 1 bản ghi (29 byte), là một PUT với khóa là dạng mã hóa hex của slot:0001.

Kích thước khớp với cách mã hóa đã nêu trước đó: phần đầu 12 byte cộng với bản ghi 17 byte, bao gồm một thẻ loại, hai tiền tố độ dài, khóa dài 9 byte và giá trị dài 5 byte.

Bước ba: Flush và kết xuất SST

Trước tiên, hãy xóa thư mục cơ sở dữ liệu (tức rm -rf /tmp/lsm-trace) để lần chạy này bắt đầu từ trạng thái sạch.

Thêm một dòng vào main.rs sau thao tác put:

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

Việc gọi db.flush().unwrap(); buộc memtable được ghi ra dưới dạng tệp SST thay vì chờ đến khi đầy.

Chạy lại tệp rồi liệt kê thư mục.

Giờ đây, chúng ta có thể thấy một tệp .sst mới trong đầu ra. Có thể kiểm tra tệp này bằng cả hai chế độ hữu ích của sst_dump, thay tên tệp thực tế vào lệnh:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Lưu ý rằng sst_dump in một vài dòng mở đầu về định dạng tệp trước kết quả quét; chúng đã được lược bỏ ở đây và trong các đầu ra bên dưới.

Đây là cặp khóa-giá trị tại nơi lưu trữ cố định mới, vẫn mang theo số thứ tự của nó.

Sau đó, chúng ta có thể xem các thuộc tính bằng lệnh sau:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

Đầu ra thuộc tính liệt kê chi tiết cấu trúc SST đã trình bày trước đó trong bài: số lượng và kích thước data block, kích thước index block, sự hiện diện của filter, thuật toán nén và số lượng mục.

Dù chỉ có một khóa, mọi thành phần cấu trúc đều được liệt kê, với một ngoại lệ đáng chú ý. Kích thước filter block bằng 0 và filter policy là N/A vì bloom filter là tính năng tùy chọn trong RocksDB, được cấu hình qua filter_policy, còn các tùy chọn mặc định không thiết lập chính sách này.

Bài viết tiếp theo trong loạt bài sẽ giải thích vì sao các hệ thống production gần như luôn bật tính năng này.

Bước bốn: Mở lại và kiểm tra nhật ký

Hãy biến các dòng put và flush thành chú thích, chỉ giữ lại dòng DB::open, rồi chạy thêm một lần nữa. Khi liệt kê thư mục, bạn sẽ thấy 000004.log cũ đã biến mất và được thay bằng một nhật ký mới gần như trống với số hiệu cao hơn. Nội dung của nhật ký cũ đã được flush vào SST ở bước ba, vì vậy các bản ghi trở nên lỗi thời và RocksDB loại bỏ tệp khi mở lại.

Đó là toàn bộ mối liên kết trong vòng đời WAL-memtable.

Để đi sâu thêm một lớp, trên Linux, chúng ta có thể chạy tệp nhị phân ở bước một bằng strace -e trace=write,fdatasync nhằm quan sát cam kết về độ bền tại ranh giới syscall. Cụ thể, các lệnh gọi write tuần tự nối dữ liệu vào tệp .log, còn fdatasync chỉ xuất hiện khi WriteOptions.sync được thiết lập.

Bước năm: Xóa khóa và xem lại phần còn lại

Khẳng định trước đó rằng thao tác xóa là một thao tác ghi có thể được quan sát trực tiếp.

Sửa main.rs để xóa khóa và buộc thực hiện thêm một lần flush:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Chạy chương trình rồi liệt kê thư mục.

Giờ sẽ có hai tệp .sst. Tệp cũ hơn không thay đổi vì nó bất biến, nghĩa là vẫn chứa khóa và giá trị tương ứng. Chúng ta có thể xác minh điều này bằng cách quét:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Bây giờ hãy quét tệp mới hơn:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

Đó vẫn là cùng một khóa nhưng có số thứ tự cao hơn, mang type:0 thay vì type:1 và không chứa giá trị. Đây là một tombstone: bản ghi kTypeDeletion từ phần WriteBatch đã được flush vào SST riêng. Cơ sở dữ liệu giờ chứa cả giá trị lẫn bản ghi xóa giá trị đó, nằm cạnh nhau trong các tệp riêng biệt.

Khi đọc khóa, mâu thuẫn sẽ được giải quyết theo hướng ưu tiên tombstone.

Chúng ta có thể xác minh điều này bằng cách thêm thao tác tra cứu vào chương trình:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Chương trình sẽ in not found vì luồng đọc kiểm tra dữ liệu mới hơn trước, và số thứ tự 2 có ưu tiên cao hơn số thứ tự 1. Theo góc nhìn của cơ sở dữ liệu, giá trị đã biến mất, nhưng nó vẫn nằm trên đĩa trong tệp SST cũ hơn.

Chưa có gì được thu hồi, nghĩa là thao tác xóa mới chỉ được ghi nhận và tombstone sẽ tiếp tục che khuất giá trị cho đến khi compaction hợp nhất hai tệp, rồi loại bỏ cả tombstone lẫn giá trị bị che khuất.

Bước sáu: Xóa khóa và xem lại phần còn lại

Loại bản ghi Merge cũng có thể được quan sát. Nó yêu cầu cấu hình một toán tử hợp nhất vì RocksDB không thể biết một toán hạng có ý nghĩa gì nếu không có toán tử.

Xóa thư mục cơ sở dữ liệu một lần nữa và thay main.rs bằng đoạn mã sau:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

Kết xuất WAL cho thấy ba bản ghi MERGE riêng biệt. Tức là có ba thao tác nối thêm thay vì một thao tác đọc duy nhất:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

Toán tử hợp nhất đã kết hợp chuỗi tại thời điểm đọc, với kết quả ở dạng byte thô. Chương trình in Some([51]) vì 51 là mã ASCII của ký tự 3. Một lần nữa, nguyên nhân là khóa và giá trị đều là các mảng byte tùy ý.

Chúng ta cũng có thể thêm db.flush().unwrap(); trước thao tác tra cứu, xóa thư mục rồi chạy lại chương trình. Kết quả quét SST hiển thị một bản ghi duy nhất:

'counter' seq:3, type:2 => 3

Quá trình flush đã áp dụng toán tử và thu gọn chúng thành một toán hạng duy nhất.

Vì sao level 0 đặc biệt?

Các tệp SST mới được đưa vào level 0. Chúng là snapshot trực tiếp của memtable, mỗi tệp bao phủ bất kỳ phạm vi khóa nào mà memtable tương ứng đã tiếp nhận, vì vậy các tệp L0 có thể và thường xuyên chồng lấn nhau. Điều này khác với mọi level sâu hơn, nơi các tệp không chồng lấn; mỗi tệp sở hữu một phạm vi khóa riêng biệt, nên một khóa nhất định chỉ có thể nằm trong tối đa một tệp ở mỗi level.

Hệ quả là mỗi tệp L0 trở thành một vị trí riêng mà khóa có thể ẩn trong đó, khiến số lượng tệp L0 trực tiếp làm giảm hiệu năng đọc. Vì vậy, RocksDB theo dõi chặt chẽ số lượng tệp L0 và bắt đầu điều tiết, thậm chí đình trệ các thao tác ghi khi số lượng tăng quá cao.

Giữ L0 ở quy mô nhỏ là một trong những nhiệm vụ chính của compaction.

Vì sao cây LSM vượt trội hơn B-tree khi ghi?

B-tree trả chi phí tổ chức dữ liệu tại thời điểm ghi để thao tác đọc có thể tìm thấy mọi thứ chính xác ở vị trí cần thiết, còn cây LSM trì hoãn việc tổ chức sang compaction chạy nền, nơi chi phí được thanh toán sau theo lô lớn.

B-tree là cấu trúc nền tảng của phần lớn cơ sở dữ liệu truyền thống. Nó cập nhật dữ liệu tại chỗ, nghĩa là mỗi thao tác ghi phải tìm trang chứa khóa, đọc trang, sửa đổi rồi ghi lại. Các trang liên quan nằm rải rác trên đĩa, vì vậy một luồng thao tác ghi ngẫu nhiên về mặt logic trở thành một luồng I/O ngẫu nhiên về mặt vật lý.

Cây LSM từ chối trả chi phí tại thời điểm ghi. Nó nối thêm (vào WAL), lưu đệm (trong memtable) và xử lý theo lô (flush). Mọi thao tác ghi xuống đĩa đều tuần tự, còn khoản nợ tổ chức dữ liệu được trì hoãn sang compaction. Công việc không biến mất. Thay vào đó, chi phí được thanh toán sau theo lô lớn, hợp nhất thành dạng mà ổ đĩa xử lý rất hiệu quả.

Điều này đặc biệt quan trọng trên SSD vì chúng hoàn toàn không thể ghi đè dữ liệu tại chỗ.

Bộ nhớ flash được xóa theo các block lớn, từ hàng trăm kilobyte đến megabyte, và được ghi theo các trang nhỏ hơn. Điều này có nghĩa mỗi thao tác ghi đè ngẫu nhiên nhỏ đều buộc lớp ánh xạ flash (FTL) của ổ đĩa di chuyển dữ liệu còn hiệu lực và xóa các block ở hậu trường.

Các thao tác ghi trang ngẫu nhiên của B-tree buộc FTL phải liên tục thực hiện việc này. Write amplification do thiết bị áp đặt được cộng dồn lên mức phát sinh từ chính cấu trúc dữ liệu, gây tổn thất cả về thông lượng lẫn tuổi thọ ổ đĩa. Các thao tác ghi tuần tự lớn của cây LSM gần với trường hợp lý tưởng nhất dành cho phần cứng flash.

Cách tốt nhất để hình dung điều này là một khoản vay. Việc trì hoãn tổ chức dữ liệu sẽ đến hạn dưới dạng I/O compaction, còn thao tác đọc phải kiểm tra nhiều vị trí hơn so với B-tree. Vì vậy, cây LSM mua thông lượng ghi ở hiện tại và hoàn trả sau dưới dạng read amplification và space amplification.

Để tìm hiểu sâu hơn về cách cây LSM so sánh với B-tree xét theo read amplification, write amplification và space amplification, hãy xem B-Tree và LSM-Tree.

Điều gì xảy ra sau khi RocksDB gặp sự cố?

Memtable là bộ nhớ khả biến, nghĩa là sự cố sẽ xóa sạch nó. Đây chính là lý do WAL tồn tại.

Khi khởi động lại, RocksDB phát lại mọi thao tác ghi đã được xác nhận nhưng chưa được flush vào SST. Nó chèn chúng vào một memtable mới để tái tạo trạng thái trước sự cố. Chi phí khôi phục tỷ lệ thuận với lượng dữ liệu chưa được flush, đó là lý do vòng đời WAL và memtable được liên kết với nhau. Sau khi nội dung của memtable được flush an toàn vào SST, các mục nhật ký tương ứng trở nên lỗi thời và WAL có thể được cắt bớt.

Một thao tác ghi trở nên bền vững ngay khi dữ liệu nối thêm được lưu vào nhật ký. Sau đó, nó trở nên dễ đọc với chi phí thấp khi quá trình flush tổ chức lại dữ liệu. B-tree gắn liền hai bước này, trong khi cây LSM tách chúng ra, và phần lớn đặc tính của cấu trúc bắt nguồn từ sự phân tách đó.

Solana tạo áp lực lên luồng ghi như thế nào?

Bài viết đầu tiên trong loạt bài này đã mô tả cách Agave lưu trữ sổ cái của Solana trong RocksDB. Xét từ góc độ luồng ghi, workload đó gần như một bài kiểm thử áp lực được thiết kế riêng. Cụ thể, các shred (tức các đơn vị dữ liệu thô của sổ cái) liên tục đến qua mạng ở tốc độ đường truyền, và mỗi shred đều phải đi qua luồng nối vào WAL và chèn vào memtable trước khi lớp lưu trữ của validator hoàn thành nhiệm vụ.

Cơ chế liên quan hoàn toàn giống những gì bài viết này đã theo dõi, nhưng ở quy mô production. Khi các shred đến, luồng chèn của Blockstore trong Agave xác thực toàn bộ lô shred đến, cố gắng khôi phục các shred bị thiếu bằng Reed-Solomon và đưa mọi thứ (tức payload của shred, metadata của slot, metadata xóa, các bản cập nhật index) vào một WriteBatch RocksDB duy nhất trước khi commit bằng một thao tác ghi nguyên tử.

Phiên bản đơn giản hóa từ insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Chú thích đó cho thấy các kỹ sư Agave diễn đạt luận điểm của bài viết này chỉ trong chín từ: lô là đơn vị của tính nguyên tử, và sự cố validator giữa quá trình chèn không bao giờ được phép khiến sổ cái chỉ cập nhật một phần.

Lô gồm một phần tử được theo dõi trong phần hướng dẫn sẽ trở thành lô gồm hàng nghìn phần tử bên trong validator—các shred cùng metadata của chúng trải rộng trên nhiều column family, một phạm vi số thứ tự, một lần nối vào WAL và một group commit.

Tuy nhiên, điểm thuận lợi là các shred bắt đầu bằng số slot (tức tuple (slot, index) trong đoạn mã đơn giản hóa là khóa ShredData), và các slot tăng gần như đơn điệu. Vì vậy, mỗi memtable tiếp nhận một dải hẹp, gần như liên tiếp của không gian khóa, và các lần flush tạo ra những tệp L0 hầu như không chồng lấn.

Chúng tôi trực tiếp trải nghiệm luồng ghi này.

Các hệ thống lưu trữ lâu dài mà chúng tôi vận hành tại Helius tiếp nhận toàn bộ lịch sử giao dịch của Solana vào RocksDB—hàng trăm terabyte trong một workload chủ yếu nối thêm và tăng trưởng vĩnh viễn—và quá trình di chuyển tạo nên kiến trúc đó được ghi lại trong bài viết về việc chuyển từ ClickHouse sang RocksDB.

Kết luận

Cây LSM là một thỏa thuận với phần cứng. Mọi thao tác ghi đều trở thành tuần tự để đổi lấy việc trì hoãn công việc tổ chức dữ liệu. Điều này có nghĩa luồng đọc phải tìm dữ liệu ở nhiều vị trí hơn so với B-tree. Memtable tiếp nhận, WAL đảm bảo và các SST tích lũy. Trên bộ nhớ flash, nơi thao tác ghi đè ngẫu nhiên bị phạt hai lần, đây là một thỏa thuận rất có lợi.

Tuy nhiên, ghi chỉ là nửa dễ dàng. Chi phí của thiết kế này được thanh toán khi đọc, vì giá trị hiện tại của một khóa có thể nằm trong memtable, một tệp L0 hoặc bất kỳ level nào bên dưới. Cơ chế giữ chi phí đó trong giới hạn là lúc kỹ thuật LSM trở nên thực sự thú vị.

Bài viết tiếp theo trong loạt bài sẽ trình bày luồng đọc, bao gồm memtable, bloom filter, block cache và cách tam giác amplification vận hành trong thực tế.

Nếu việc theo dõi một cặp khóa-giá trị duy nhất qua bốn cấu trúc dữ liệu khác nhau nghe như cách tuyệt vời để dành một buổi chiều, hãy đến xây dựng cùng chúng tôi. Những hệ thống được mô tả trong loạt bài này chính là các hệ thống chúng tôi triển khai, vận hành và tinh chỉnh ở quy mô thị trường vốn Internet. Chúng tôi đang tuyển dụng cho nhiều vị trí trong đội ngũ kỹ thuật. Xem tất cả vị trí đang tuyển tại helius.dev/careers.