Cái giá của thao tác ghi rẻ: RocksDB đọc như thế nào?

RocksDB đọc một khóa như thế nào?

Một thao tác đọc trong RocksDB đi từ dữ liệu mới nhất đến cũ nhất và dừng ở phiên bản đầu tiên của khóa mà nó tìm thấy. Chỉ có vậy; mọi thứ còn lại đều nhằm tăng tốc quá trình này.

Thứ tự tìm kiếm là cố định và phản chiếu ngược đường dẫn ghi được mô tả trong bài trước: nó lần lượt đi qua memtable đang hoạt động, các memtable bất biến, các tệp SST ở cấp 0 và các tệp SST đã sắp xếp từ cấp 1 trở xuống.

RocksDB kiểm tra memtable đang hoạt động trước vì nó chứa các thao tác ghi gần đây nhất, nằm trong bộ nhớ và sử dụng skiplist. Do đó, tra cứu là một phép tìm kiếm đã sắp xếp trong bộ nhớ, gần như không tốn I/O. Quá trình tìm kiếm dừng ngay khi tìm thấy khóa.

Sau memtable đang hoạt động, RocksDB kiểm tra mọi memtable bất biến đã đầy nhưng chưa được flush xuống đĩa. Nó kiểm tra chúng tiếp theo, từ mới nhất đến cũ nhất.

Sau đó, đĩa được kiểm tra. Từng tệp cấp 0 phải được kiểm tra riêng, từ mới nhất đến cũ nhất, vì các phạm vi khóa của chúng chồng lấn. Nguyên nhân là mỗi tệp là một ảnh chụp của bất kỳ dữ liệu nào mà một memtable đã tiếp nhận, nên cùng một khóa có thể đồng thời xuất hiện trong hai tệp cấp 0.

Mỗi tệp cấp 0 là một nơi riêng biệt mà khóa có thể ẩn náu. Đây chính là lý do số lượng tệp cấp 0 làm tăng chi phí đọc và RocksDB phải tạm dừng thao tác ghi để giữ con số này trong giới hạn.

Từ cấp 1 trở xuống, các tệp SST trong cùng một cấp được sắp xếp và không chồng lấn, nên nhiều nhất chỉ một tệp ở mỗi cấp có thể chứa khóa. Tệp đó được tìm bằng phép tìm kiếm nhị phân trên metadata của tệp, sau đó quá trình tìm kiếm đi sâu vào chính tệp này. Khối chỉ mục xác định đúng khối dữ liệu, còn khối dữ liệu sẽ chứa khóa hoặc cho thấy cấp này không có khóa.

Số thứ tự rất quan trọng với đường dẫn đọc của RocksDB vì chúng cho phép dừng tìm kiếm ở phiên bản đầu tiên tìm thấy. Điều này đảm bảo đó là phiên bản mới nhất. Ví dụ, nếu thao tác đọc tìm thấy một tombstone, nó hoàn tất và trả về rằng khóa đã bị xóa. Vì vậy, quá trình tìm kiếm kết thúc tại tombstone và để lại giá trị cũ hơn trên đĩa.

RocksDB cung cấp những thao tác đọc nào?

RocksDB cung cấp bốn cách đọc, mỗi cách sử dụng đường dẫn đọc theo cách khác nhau: Get, MultiGet, Iterators và Snapshots.

Get

Get là phép tra cứu điểm mà chúng ta đã lần theo ở phần trước. Nói cách khác, đó là tìm một khóa theo thứ tự từ mới nhất đến cũ nhất, trong đó phiên bản đầu tiên sẽ được chọn.

MultiGet

MultiGet gom các phép tra cứu điểm thành lô. Một thao tác đọc có thể cung cấp cho RocksDB một tập hợp khóa; RocksDB sẽ sắp xếp và nhóm chúng theo những tệp mà chúng có thể truy cập.

Trên thực tế, điều này giúp RocksDB mở một SST duy nhất, chỉ tham chiếu các khối chỉ mục và bộ lọc của nó một lần, đồng thời xử lý I/O theo lô. Đây vẫn là đường dẫn đọc giống Get, nhưng chi phí được cố định và phân bổ trên toàn bộ lô.

Iterator

Iterators quét các phạm vi, nghĩa là chúng tìm đến một khóa rồi di chuyển tiến hoặc lùi theo thứ tự đã sắp xếp.

Về bản chất, iterator là một phép hợp nhất k chiều (tức là kết hợp k danh sách đã sắp xếp khác nhau thành một chuỗi duy nhất được sắp xếp hoàn chỉnh). Mọi nguồn dữ liệu còn hiệu lực—memtable, mọi memtable bất biến, từng tệp L0 và một tệp ở mỗi cấp sâu hơn—đều đóng góp con trỏ đã sắp xếp riêng; một heap liên tục trả về con trỏ đang giữ khóa nhỏ nhất tiếp theo.

Quy tắc ưu tiên phiên bản mới nhất này được áp dụng ở mọi bước. Vì vậy, nếu nhiều nguồn cung cấp cùng một khóa, phiên bản mới nhất sẽ được chọn và phần còn lại bị loại bỏ.

Các giá trị bị che khuất và tombstone được bỏ qua khi iterator tiến lên. Điều đó có nghĩa một phạm vi đầy các khóa đã xóa là phạm vi mà iterator phải âm thầm đi qua mà không trả về gì. Một không gian khóa bị xóa nhiều sẽ khiến các phép quét chậm theo cách mà phép tra cứu điểm không bao giờ nhận thấy.

Snapshot

Một Snapshot là số thứ tự được ghi lại tại một thời điểm. Bất kỳ thao tác đọc nào mang theo nó chỉ cần bỏ qua các phiên bản mới hơn số đó và trả về phiên bản mới nhất có số bằng hoặc nhỏ hơn. Cách này cho phép đọc nhất quán tại một thời điểm cụ thể, được triển khai bằng một phép so sánh số nguyên.

Tạo snapshot gần như miễn phí vì chi phí chỉ phát sinh về sau; một snapshot còn hiệu lực vẫn có thể nhìn thấy các phiên bản không thể được thu hồi, bất kể chúng cũ đến đâu.

Cả Get và MultiGet đều biết chính xác khóa cần tìm. Vì vậy, quá trình tìm kiếm có thể đặt ra một câu hỏi rẻ hơn “khóa này ở đâu?”. Cụ thể là “những tệp nào chắc chắn không có khóa này?”. Iterators không bao giờ có được lối tắt đó. Trả lời câu hỏi rẻ hơn này là toàn bộ nhiệm vụ của bộ lọc Bloom.

Bộ lọc Bloom là gì?

Bộ lọc Bloom trả lời một câu hỏi về một tập hợp: phần tử này chắc chắn không có trong đó phải không? Câu trả lời là chắc chắn không hoặc có thể, chứ không bao giờ là một lời khẳng định chắc chắn rằng có. Nếu một tệp chắc chắn không có khóa, quá trình tìm kiếm sẽ không bao giờ mở tệp đó, nhờ vậy tiết kiệm I/O.

Khi một SST được tạo, nó đưa từng khóa qua một số hàm băm và mỗi giá trị băm sẽ đặt một bit trong mảng bit nhỏ gọn (khối bộ lọc).

Tại thời điểm đọc, phép tra cứu băm khóa cần tìm theo cùng cách rồi kiểm tra các bit đó. Nếu bất kỳ bit nào chưa được đặt, khóa chưa từng được chèn, nghĩa là khóa chắc chắn không ở đây.

Nếu tất cả các bit đều được đặt, khóa có thể hiện diện—chỉ là có thể vì giá trị băm của các khóa khác có thể tình cờ phủ lên cùng các bit.

Điều này có nghĩa có thể xảy ra dương tính giả—quá trình tìm kiếm mở tệp, kiểm tra nhưng không tìm thấy gì, làm lãng phí chính lượng I/O mà bộ lọc được thiết kế để tiết kiệm.

Với cấu hình thông thường của RocksDB là mười bit cho mỗi khóa, tỷ lệ dương tính giả xấp xỉ một phần trăm. Mười bit mang lại 99% khả năng bỏ qua một tệp không có khóa. Bộ lọc cho một SST có một triệu khóa chỉ lớn hơn một megabyte đôi chút, nằm trong bộ nhớ cùng với chỉ mục và được tham chiếu mà không cần chạm vào đĩa mà nó bảo vệ. Rất ít cấu trúc trong kỹ thuật hệ thống mang lại nhiều lợi ích hơn với chi phí thấp như vậy.

Đây cũng là lý do bài trước trong loạt bài này ghi nhận kích thước khối bộ lọc bằng 0. Bộ lọc Bloom là tính năng phải chủ động bật, được cấu hình qua filter_policy với số bit trên mỗi khóa do ứng dụng lựa chọn, còn mặc định không thiết lập bộ lọc nào.

Mặc định này có thể chấp nhận được đối với một thư viện không thể biết workload của mình, nhưng không thể chấp nhận trong môi trường production, nơi bộ lọc tạo ra sự khác biệt giữa việc một khóa không tồn tại chỉ tốn một lần kiểm tra bộ nhớ cho mỗi tệp và việc phải đọc khối chỉ mục của từng tệp.

Một hạn chế là bộ lọc Bloom chỉ hữu ích khi quá trình tìm kiếm biết chính xác khóa. Bộ lọc Bloom có thể trả lời liệu key:0301 có trong tệp này hay không, nhưng không thể trả lời liệu tệp có chứa bất kỳ thứ gì giữa key:0090 và key:0110 hay không vì phép băm phá hủy thứ tự.

Iterators không bao giờ biết trước khóa tiếp theo nên không nhận được sự hỗ trợ nào từ cấu trúc này. Bộ lọc Bloom là công nghệ dành cho tra cứu điểm; các workload tập trung vào phạm vi phải tìm cách khác để giảm tải.

Còn tìm kiếm theo tiền tố trong RocksDB thì sao?

Giải pháp một phần của RocksDB cho vấn đề quét là thay đổi dữ liệu được băm. Một bộ trích xuất tiền tố cho RocksDB biết rằng khóa có cấu trúc mang ý nghĩa (chẳng hạn tám byte đầu tiên hoặc mọi thứ trước một dấu phân cách). Khi biết tiền tố là gì, RocksDB có thể tạo bộ lọc Bloom trên tiền tố thay vì, hoặc song song với, toàn bộ khóa. Một bộ lọc có thể trả lời liệu tệp có chứa khóa bắt đầu bằng một tiền tố nhất định hay không sẽ hỗ trợ iterator.

Tuy nhiên, lối tắt này chỉ hoạt động với một tiền tố.

Phép quét cho một tiền tố nhất định có thể bỏ qua tệp và khối giống như phép tra cứu điểm. Phép quét đi từ tiền tố này sang tiền tố tiếp theo không nhận được cùng lợi ích. Cách duy trì đảm bảo về thứ tự lặp giữa các tiền tố xứng đáng có một bài phân tích chuyên sâu riêng về các chi tiết cấu hình giúp điều đó khả thi.

Nhìn chung, tìm kiếm theo tiền tố không làm cho các phép quét phạm vi trở nên rẻ.

Thay vào đó, nó làm cho một dạng quét phạm vi cụ thể và cực kỳ phổ biến trở nên rẻ đối với một tiền tố nhất định.

Bộ nhớ đệm khối của RocksDB là gì?

Bộ nhớ đệm khối là bộ nhớ đệm trong RAM dành cho các khối chưa nén. Khi một khối dữ liệu được đọc từ SST, nó được giải nén và giữ lại để lần đọc tiếp theo cần cùng khối có thể tìm thấy mà không phải chạm vào đĩa. Điều này có nghĩa các khóa nóng tập trung trong các khối nóng, còn các khối nóng không tiếp tục gây tốn I/O.

Vì vậy, bộ lọc Bloom cố gắng giữ quá trình tìm kiếm ở ngoài các tệp, còn bộ nhớ đệm khối giúp việc truy cập lại những tệp bắt buộc phải mở trở nên rẻ.

Một điểm tinh tế là có hai bộ nhớ đệm.

Bộ nhớ đệm khối thuộc về RocksDB và chứa các khối chưa nén mà RocksDB quản lý trực tiếp. Bên dưới nó là bộ nhớ đệm trang của hệ điều hành, nơi giữ các trang tệp thô đã nén mà RocksDB vừa đọc gần đây. Cùng một dữ liệu có thể đồng thời chiếm chỗ ở cả hai nơi (tức là chưa nén trong bộ nhớ đệm khối và đã nén trong bộ nhớ đệm trang). Đây là lý do mức sử dụng bộ nhớ thực tế của RocksDB thường xuyên bị đánh giá thấp và các cuộc thảo luận về kích thước bộ nhớ đệm mà bỏ qua bộ nhớ đệm trang chỉ đang xem xét một nửa hệ thống.

Các khối chỉ mục và bộ lọc được xử lý đặc biệt. Chúng nhỏ, được tham chiếu trong gần như mọi thao tác đọc chạm đến tệp tương ứng và việc không tìm thấy chúng trong bộ nhớ đệm gây chi phí cực lớn. Vì vậy, giữ chúng thường trú trong bộ nhớ gần như là điều bắt buộc.

Việc chúng nằm trong ngân sách của bộ nhớ đệm khối hay nằm ngoài ngân sách đó, trong bộ nhớ riêng của các trình đọc bảng, là một lựa chọn cấu hình (tức là cache_index_and_filter_blocks).

Tombstone và chuỗi hợp nhất khiến thao tác đọc tốn bao nhiêu chi phí?

Tombstone và chuỗi hợp nhất là các loại bản ghi từ đường dẫn ghi có ảnh hưởng đến đường dẫn đọc, nhưng chỉ có thể được xử lý dứt điểm bằng compaction. Tombstone tích lũy cho đến khi compaction loại bỏ chúng cùng những xác dữ liệu mà chúng che khuất; chuỗi hợp nhất dài ra cho đến khi compaction gộp chúng thành các giá trị hoàn chỉnh.

Tombstone không tốn nhiều chi phí cho phép tra cứu điểm tìm thấy nó. Cụ thể, quá trình tìm kiếm dừng lại và trả kết quả vì “đã xóa” là một kết quả hợp lệ. Tuy nhiên, iterator không thể dừng ở tombstone. Thay vào đó, nó phải xử lý tombstone, bỏ qua các phiên bản bị che khuất và tiếp tục tiến cho đến khi tìm thấy khóa còn hiệu lực tiếp theo. Một không gian khóa bị xóa nhiều giống như bãi mìn gồm các mục phải được duyệt qua rồi loại bỏ mà không trả về gì; việc quét qua đó có thể thực hiện rất nhiều công việc tùy ý nhưng chỉ tạo ra rất ít kết quả. Phép tra cứu điểm không bao giờ nhận thấy điều này, còn phép quét phạm vi hoàn toàn không có khả năng chống lại nó.

Các toán hạng hợp nhất tạo ra cùng loại chi phí nhưng theo hướng ngược lại. Thao tác đọc một khóa đã hợp nhất không thể dừng ở bản ghi mới nhất vì toán hạng là một mô tả về thay đổi chứ không phải giá trị. Vì vậy, quá trình tìm kiếm phải tiếp tục thu thập toán hạng cho đến khi gặp một giá trị đầy đủ, một tombstone hoặc đáy cây, rồi gộp chuỗi thông qua toán tử hợp nhất.

Phần hướng dẫn trong bài trước đã gộp một chuỗi gồm ba phần tử, nhưng cần lưu ý rằng thiết kế không giới hạn chuỗi ở ba. Một bộ đếm được hợp nhất mười nghìn lần giữa các lần compaction sẽ tạo ra thao tác đọc phải thu thập và gộp mười nghìn toán hạng, trong khi đường dẫn ghi không làm gì để ngăn điều đó.

Tam giác Khuếch đại

Tam giác khuếch đại là sự đánh đổi ba chiều chi phối mọi cây LSM: khuếch đại ghi, khuếch đại đọc và khuếch đại không gian. Cải thiện bất kỳ hai yếu tố nào cũng làm yếu tố thứ ba tệ đi.

Athanassoulis và cộng sự đã chính thức hóa các đánh đổi này thành phỏng đoán RUM (2016). Phỏng đoán này cho rằng một phương thức truy cập chỉ có thể giảm thiểu nhiều nhất hai trong ba loại chi phí: chi phí đọc, chi phí cập nhật và chi phí bộ nhớ hoặc không gian; loại thứ ba sẽ phải gánh phần chi phí còn lại. Cây B nằm ở một vị trí (tức là đọc rẻ, cập nhật đắt), còn cây LSM nằm ở vị trí khác (tức là cập nhật rẻ, đọc đắt), và tam giác mô tả vùng đánh đổi ở giữa.

Mọi nội dung trong bài viết này đều là một góc của tam giác đang tự bảo vệ mình.

Khuếch đại ghi là tỷ lệ giữa số byte thực tế được ghi xuống đĩa và số byte mà ứng dụng ghi về mặt logic. Một Put được ghi một lần vào WAL, một lần khi flush xuống L0 và thêm một lần mỗi khi compaction đưa nó xuống một cấp. Điều này có nghĩa một thao tác ghi logic có thể thường xuyên biến thành mười đến ba mươi thao tác ghi vật lý trong suốt vòng đời của nó trong một LSM phân cấp với hàng chục cấp. Trong khi bài trước ca ngợi việc mọi thao tác ghi đó đều diễn ra tuần tự, bài này lại than phiền về chúng.

Khuếch đại đọc là số nơi mà một truy vấn phải kiểm tra để tìm câu trả lời. Với phép tra cứu điểm, trường hợp xấu nhất là mọi memtable, tệp L0 và một tệp ở mỗi cấp sâu hơn (tức là quá trình tìm kiếm được lần theo ở đầu bài viết này); chi phí thực tế là mọi phần còn sót lại sau bộ lọc Bloom và bộ nhớ đệm khối. Với phép quét phạm vi, đó là phép hợp nhất k chiều giữ mọi nguồn mở cùng lúc. Khuếch đại đọc phần lớn là nội dung của bài viết này: các bộ lọc, bộ nhớ đệm và bộ trích xuất tiền tố đóng vai trò là cơ chế giúp giảm chi phí đó.

Khuếch đại không gian là tỷ lệ giữa dung lượng đĩa đã dùng và dữ liệu logic được lưu trữ. Các phiên bản cũ đang chờ compaction, tombstone cùng những xác dữ liệu mà chúng che khuất, chuỗi hợp nhất chưa được gộp và mọi phiên bản bị một snapshot còn hiệu lực ghim lại đều chiếm dung lượng đĩa cho dữ liệu mà ứng dụng không còn có thể đọc hoặc không còn cần. Compaction phân cấp được tinh chỉnh tốt giữ tỷ lệ này gần 1,1 lần, trong khi các cách bố trí khác đánh đổi nhiều hơn đáng kể.

Tam giác cho thấy cải thiện hai góc bất kỳ sẽ khiến góc thứ ba tệ đi. Cụ thể:

• Compaction tích cực: thao tác đọc nhanh hơn và không gian chặt chẽ hơn, nhưng mọi khóa liên tục bị ghi lại và khuếch đại ghi tăng lên
• Compaction thưa: thao tác ghi diễn ra trơn tru, nhưng tệp chồng chất để thao tác đọc phải kiểm tra và dữ liệu chết lưu lại trên đĩa
• Dành bộ nhớ cho bộ lọc: bộ nhớ đệm và hiệu năng đọc phục hồi, nhưng bộ nhớ là tài nguyên thứ tư thầm lặng mà cả ba góc của tam giác đều cạnh tranh

Không có cài đặt nào mang nhãn “nhanh”. Chỉ có những vị trí trên tam giác phù hợp hoặc không phù hợp với một workload nhất định.

Lần theo Đường dẫn Đọc

Phần sau sử dụng lại dự án từ phần hướng dẫn của bài trước, với tính năng thống kê được bật.

Thay nội dung của src/main.rs bằng:

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

fn main() {
	let with_bloom = std::env::args().nth(1).as_deref() == Some("bloom");
	let path = if with_bloom { "/tmp/read-bloom" } else { "/tmp/read-nobloom" };

	let mut opts = Options::default();
	opts.create_if_missing(true);
	opts.enable_statistics();

	if with_bloom {
		let mut bbt = BlockBasedOptions::default();

		bbt.set_bloom_filter(10.0, false);
		opts.set_block_based_table_factory(&bbt);
	}

	let db = DB::open(&opts, path).unwrap();

	// Three L0 SSTs with fully overlapping ranges: file b holds keys where
	// key % 4 == b, all spanning 0..600. Keys where key % 4 == 3 exist nowhere
	for batch in 0..3u64 {
		let mut k = batch;

		while k < 600 {
			let key = format!("key:{:04}", k);
			db.put(key.as_bytes(), b"value").unwrap();
			k += 4;
		}

		db.flush().unwrap();
	}

	// key:0404 lives only in the oldest file, meaning the search must get past
	// the two newer files to reach it
	let hit = db.get(b"key:0404").unwrap();
	println!("get(key:0404) = {:?}", hit.map(|b| String::from_utf8(b).unwrap()));

	// key:0303 is inside every file's range and inside no file
	let miss = db.get(b"key:0303").unwrap();
	println!("get(key:0303) = {:?}", miss);

	if let Some(stats) = db.property_value("rocksdb.options-statistics").unwrap() {
		for line in stats.lines() {
			if line.contains("bloom.filter.useful")
				|| line.contains("bloom.filter.full.positive")
				|| line.contains("block.cache.data") {
				println!("{}", line);
			}
		}
	}
}

Ở trên, chúng ta có ba tệp L0 đã được flush với các phạm vi khóa chồng lấn hoàn toàn. Vì vậy, không thể loại trừ tệp nào chỉ dựa trên metadata phạm vi, bởi mỗi tệp đều là nơi mà cả hai khóa có thể ẩn náu.

Kết quả trúng (tức là key:0404) chỉ nằm trong tệp cũ nhất, buộc quá trình tìm kiếm từ mới nhất đến cũ nhất phải xử lý hai tệp không có khóa trước khi đến được tệp có khóa.

Kết quả trượt (tức là key:0303) nằm trong phạm vi của mọi tệp nhưng không nằm trong tệp nào, nghĩa là chỉ bộ lọc Bloom mới có thể tiết kiệm chi phí cho thao tác đọc đó.

Chạy nguyên trạng, sau đó chạy với đối số bloom.

Khi không có bộ lọc, đầu ra là:

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 3
rocksdb.block.cache.data.hit COUNT : 3
rocksdb.bloom.filter.useful COUNT : 0

Chúng ta có sáu lần truy cập khối dữ liệu để trả lời hai phép tra cứu. Lần trúng đọc một khối dữ liệu từ mỗi tệp trong ba tệp, trong đó hai tệp không hữu ích, dẫn đến ba lần đọc đĩa. Lần trượt sau đó kiểm tra lại cùng ba tệp; ba lần truy cập khối dữ liệu của nó chỉ trúng bộ nhớ đệm vì phép tra cứu đầu tiên vừa làm nóng bộ nhớ đệm. Bộ nhớ đệm khối đã hoàn thành nhiệm vụ và đó là thứ duy nhất làm được việc.

Khi có bộ lọc, đầu ra là:

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 1
rocksdb.block.cache.data.hit COUNT : 0
rocksdb.bloom.filter.useful COUNT : 5
rocksdb.bloom.filter.full.positive COUNT : 1

Tổng cộng chúng ta chỉ có một lần truy cập khối dữ liệu. Ta có thể tự kiểm chứng phép tính cho việc useful bằng 5:

• Lần trúng tham chiếu bộ lọc của tệp mới nhất và bộ lọc của tệp thứ hai; cả hai đều trả về không. Bộ lọc của tệp cũ nhất trả về một full.positive, được chứng minh là dương tính thật. Như vậy, chúng ta có hai lần bỏ qua
• Lần trượt tham chiếu cả ba bộ lọc và nhận ba kết quả không, nghĩa là có ba lần bỏ qua và không tệp nào được mở

Cộng lần trúng và lần trượt, chúng ta có năm lần kiểm tra tệp. Năm lần kiểm tra tệp mà bộ lọc trả lời từ bộ nhớ chính là năm lần đọc khối dữ liệu mà lượt chạy không có bộ lọc phải thực hiện. Như vậy, mười bit cho mỗi khóa đã biến sáu lần truy cập khối thành một.

Về bản chất, đây là tam giác khuếch đại ở quy mô nhỏ hơn. Lượt chạy không có bộ lọc trả toàn bộ chi phí khuếch đại đọc; lượt chạy có bộ lọc trả chi phí đó bằng bộ nhớ (tức là vài trăm byte bộ lọc cho mỗi tệp); còn đường dẫn ghi không phải trả gì trong cả hai trường hợp. Mọi quyết định tinh chỉnh trong RocksDB đều là sự đánh đổi này ở quy mô lớn hơn.

Solana gây áp lực lên đường dẫn đọc như thế nào?

Bài trước xem validator là bài kiểm tra sức chịu tải của đường dẫn ghi. Cụ thể, shred liên tục đổ vào ở tốc độ đường truyền. Phía đọc là nửa còn lại của thỏa thuận, bởi một ledger không ai có thể đọc lại chỉ là một cách đắt đỏ để làm nóng trung tâm dữ liệu.

Mọi nhận định trong bài viết này về thứ tự tìm kiếm, bộ lọc và thiết kế khóa đều xuất hiện trong cách dữ liệu của Solana thực sự được truy vấn.

Bên trong validator, các thao tác đọc của Blockstore có hai dạng khác nhau: phục vụ yêu cầu sửa chữa và phát lại hoặc stream một block.

Phục vụ yêu cầu sửa chữa nghĩa là các validator khác đang yêu cầu những shred mà chúng đã bỏ lỡ. Đây là phép tra cứu điểm theo (slot, index). Phát lại hoặc stream lượng ledger tương ứng với một block là phép quét phạm vi trên một slot nhất định.

Vì khóa shred bắt đầu bằng số slot, mọi shred của một slot nằm liền kề nhau trên đĩa. Do đó, “đưa cho tôi slot n” là một lượt duyệt iterator tuần tự, chặt chẽ thay vì nhiều phép đọc điểm rải rác.

Thiết kế khóa từ đường dẫn ghi chính là tối ưu hóa cho đường dẫn đọc. Cụ thể, cùng một bố cục ưu tiên slot giúp các lần flush tạo ra các tệp L0 gần như không chồng lấn cũng biến thao tác đọc block thành một lượt quét liền mạch duy nhất.

Lớp RPC đặt ra những câu hỏi khó hơn. getTransaction là phép tra cứu điểm theo chữ ký trong dữ liệu trạng thái giao dịch. Đây chính là trường hợp mà bộ lọc Bloom được tạo ra để xử lý, vì một chữ ký không có trong SST nhất định chỉ nên tốn một lần kiểm tra bộ nhớ để loại trừ, thay vì phải đọc chỉ mục.

getSignaturesForAddress là phép quét theo tiền tố được đề cập trước đó trong bài—chỉ mục từ địa chỉ đến chữ ký bắt đầu bằng địa chỉ, nên toàn bộ lịch sử của một tài khoản chiếm một phạm vi khóa liền mạch và toàn bộ hoạt động của một địa chỉ trở thành dạng quét phạm vi mà cấu trúc này xử lý tốt.

Tuy nhiên, những câu hỏi mà ứng dụng thực sự đặt ra nằm trên cả hai cơ chế. Không có primitive nào cho “Đưa cho tôi tất cả giao dịch của địa chỉ này.” Loại câu hỏi này trở thành một phép quét tiền tố để lấy chữ ký, sau đó là một phép tra cứu điểm cho mỗi chữ ký để lấy giao dịch.

Trên thực tế, một truy vấn phạm vi được phân nhánh thành hàng trăm hoặc hàng nghìn Get. Đây chính xác là workload mà cơ chế gom lô của MultiGet được tạo ra để xử lý. Cụ thể: sắp xếp các chữ ký, nhóm chúng theo những tệp được truy cập, rồi chỉ tham chiếu chỉ mục và bộ lọc của mỗi tệp một lần.

Một truy vấn nhìn từ bên ngoài giống như một lệnh gọi API duy nhất thực chất kích hoạt tuần tự mọi cơ chế mà bài viết này đã mô tả trên đường dẫn đọc: iterator, sắp xếp theo tiền tố, bộ lọc Bloom, phân bổ chi phí theo lô và bộ nhớ đệm khối.

Chúng tôi đã xây dựng lệnh gọi API đó.

Trước đây, các nhà phát triển phải chạy một vòng lặp phía client gồm getSignaturesForAddress và n lệnh gọi getTransaction, cùng logic thử lại mà các mẫu n+1 luôn cần đến.

getTransactionsForAddress thu gọn vòng lặp đó thành một phương thức duy nhất với nhiều tính năng phù hợp với cơ chế đường dẫn đọc được thảo luận trong bài viết này.

Thứ tự sắp xếp tăng dần và giảm dần là hai hướng của iterator. Phân trang dựa trên con trỏ trả về một token có dạng slot:position, tức là một vị trí khóa. Vì vậy, tiếp tục truy vấn phân trang chính là tìm lại vị trí trong phép quét nơi lần trước đã dừng. Bộ lọc slot và thời gian giới hạn công việc ngay từ đầu thay vì loại bỏ kết quả sau đó.

Hệ thống lưu trữ dài hạn phục vụ phương thức đó giữ toàn bộ lịch sử giao dịch của Solana trong RocksDB—hàng trăm terabyte. Chúng tôi đã di chuyển hệ thống từ ClickHouse sang RocksDB, và đó là lý do loạt bài này ra đời: công cụ lưu trữ được mô tả xuyên suốt các bài viết là hệ thống mà chúng tôi đã tinh chỉnh theo từng column family để biến toàn bộ vòng đời của một tài khoản thành một phép quét liền mạch và phép tra cứu chữ ký thành một lần kiểm tra bộ nhớ duy nhất. Đây là lý do chúng tôi có hệ thống lưu trữ dài hạn hiệu năng cao nhất trên toàn Solana.

Kết luận

Đường dẫn đọc là lịch hoàn trả của cây LSM và bài viết này trình bày nó như một hóa đơn chi tiết. Một phép tra cứu đi từ mới nhất đến cũ nhất, qua memtable, L0 và mọi cấp đã sắp xếp, rồi dừng ở phiên bản đầu tiên tìm thấy. Mọi tính năng và công cụ khác đều tồn tại để giảm thiểu số lần truy cập mà quá trình tìm kiếm cần thực hiện: bộ lọc Bloom trả lời từ bộ nhớ liệu một khóa có chắc chắn không nằm trong tệp hay không để tệp đó luôn đóng; bộ nhớ đệm khối giúp việc mở lại những tệp bắt buộc phải mở trở nên rẻ; còn thiết kế tiền tố biến dạng quét phạm vi duy nhất có chi phí phải chăng thành đúng dạng mà ứng dụng thực sự cần.

Tam giác khuếch đại là sổ cái ghi lại tất cả điều này: chi phí đọc được thanh toán bằng bộ nhớ, chi phí ghi được trả sớm hơn qua các đợt tuần tự. Chi phí không gian âm thầm tích lũy trong từng tombstone và phiên bản bị che khuất mà quá trình tìm kiếm bước qua.

Cần lưu ý rằng mọi cấu trúc trong bài viết này chỉ quản lý chi phí của các tệp tích lũy, phiên bản chết và chuỗi hợp nhất chưa được gộp. Không nội dung nào trong bài thực sự loại bỏ chi phí đó. Cơ chế loại bỏ nó chạy liên tục trong nền, và quyết định mức độ tích cực của cơ chế này là lựa chọn tinh chỉnh có ảnh hưởng lớn nhất trong RocksDB. Bài tiếp theo trong loạt bài sẽ nói về compaction: nó làm gì, ba kiểu mà RocksDB cung cấp và vì sao Blockstore của Solana từng nổi tiếng vì chuyển kiểu rồi lại chuyển về.

Nếu dành cả buổi chiều để đọc một bài hướng dẫn về đường dẫn đọc của cơ sở dữ liệu là điều bạn yêu thích, hãy cùng xây dựng với chúng tôi. Đường dẫn đọc được mô tả ở đây là đường dẫn chúng tôi vận hành trên toàn bộ lịch sử của Solana, nơi khác biệt giữa việc tham chiếu một bộ lọc Bloom và mở một tệp được đo bằng phần cứng thật và tiền thật. Chúng tôi đang tuyển dụng cho toàn bộ đội ngũ kỹ thuật. Xem tất cả vị trí đang tuyển tại helius.dev/careers