RockDB: Embedded Key-Value Store for Flash and RAM

Nam Bui

Jan 15, 2022 • 13 min read

1. Tổng Quan RocksDB

RocksDB là công cụ lưu trữ sử dụng key/value. Nó được phát triển bởi Facebook dựa trên LevelDB và cung cấp backwards-compatible hỗ trợ cho LevelDB APIs. RocksDB hỗ trợ lưu trữ trên nhiều phần cứng khác nhau, ban đầu tập trung phát triển lưu trữ trên fast flash. Nó sử dụng cơ sở dữ liệu có cấu trúc Log cho việc lưu trữ, được viết bằng C++, và có thể được gọi bởi Java bằng cách sử dụng RocksJava. Nó hỗ trợ cả tìm kiếm điểm,range scans và nó cũng cung cấp một số kiểu truy vấn ACID khác nhau.

RocksDB có các cấu hình cài đặt linh động thể hiện ở chỗ có thể tùy chỉnh để chạy trên nhiều môi trường khác nhau như SSDs, Hard disks, Ramfs hoặc remote storage. Nó hỗ trợ các thuật toán nén khác nhau và các công cụ để hỗ trợ xây dựng và gỡ lỗi. RocksDB sử dụng mã nguồn mở của LevelDB và ý tưởng từ Apache Hbase. Mã nguồn của RocksDB bắt đầu được tách ra từ LevelDB bản 1.5. Trước khi hình thành RocksDB, nó cũng đã được xây dựng dựa trên mã và ý tưởng đã được phát triển trước đó tại Facebook.

2.Kiến trúc của RocksDB

Kiến trúc của RocksDB gồm 3 phần cơ bản là Memtable, sstfile và logfile.

Quy trình xử lý của RocksDB được tiến hành như sau:

Luồng Writes

Đầu tiên khi có request (Writes) gửi đến RocksDB. Dữ liệu mới sẽ được tiến hành ghi vào trong Memtable và có thể được tùy chọn ghi vào Write-Ahead Log (WAL - logfile). Trong đó logfile là tệp được ghi tuần tự trên bộ nhớ. Khi Memtable đầy thì nó sẽ được tiến hành ghi vào trong sstfile trên bộ nhớ và dữ liệu trên logfile khi đó cũng sẽ được xoá một cách an toàn. Dữ liệu trong sstfile sẽ được sắp xếp để dễ dàng tra cứu các từ khoá.

Luồng Read

Khi có request (Read) gửi đến RocksDB. Nó sẽ tiến hành tìm kiếm trong Memtable trước. Nếu trong Memtable không có thì nó sẽ tiến hành tìm kiếm trên sstfile.

2.1. Memtable

Memtable là một cấu trúc lưu trữ dữ liệu trong bộ nhớ trước khi tiến hành đẩy vào trong sstfile. Nó cung cấp cả 2 dịch vụ đọc và ghi, dữ liệu luôn được chèn vào memtable, và việc đọc sẽ luôn được tiến hành ở memtable đầu tiên do dữ liệu trong memtable luôn là dữ liệu mới nhất. Khi memtable đầy bộ nhớ nó sẽ lock memtable lại và được thay thế bởi một memtable mới. Memtable cũ khi đã đầy sẽ được tiến hành đẩy dữ liệu vào sstfile, sau khi quá trình đẩy dữ liệu hoàn tất bảng memtable đó sẽ có thể bị xóa.

Một số cấu trúc dữ liệu thường sử dụng trong memtable

2.1.1 Skip list

Hình 2.1.1: Hình ảnh mô tả cách tìm kiếm một phần tử sử dụng Skiplist

Trường hợp xấu nhất là chúng ta phải mất O(n) thời gian cho trường hợp tìm kiếm tuần tự trong một danh sách đã được sắp xếp mà không thể skip qua các node trong quá trình tìm kiếm . Ý tưởng của Skiplist là tiến hành xây dựng nhiều tầng trong danh sách đã được sắp xếp. Các để tìm tìm kiếm một phần tử sử dụng Skiplist được thể hiện ở hình 2.1.1

Memtable sử dụng cấu trúc Skiplist này nhằm tối ưu việc đọc, ghi, truy cập và quét tuần tự trong memtable. Bên cạnh đó, nó cũng cung cấp một số tính năng hữu ích khác mà các cấu trúc khác của memtable không hỗ trợ như là Concurrent Insert và Insert with Hint.

2.1.2 HashSkipList

HashSkipList là cấu trúc mà ở đó dữ liệu được lưu trữ thành các mảng băm, trong mỗi mảng băm là dữ liệu sẽ được lưu trữ dưới dạng skiplist .

Trường hợp sử dụng HashSkiplist tốt nhất là kết hợp giữa PainTable SST format và lưu trữ chúng trong RAMFS.

Khi thêm hoặc tìm kiếm, RocksDB sẽ sử dụng key’s prefix bằng cách sử dụng Options.prefix_extractor, để tìm kiếm nhóm băm. Trong nhóm băm, việc tìm kiếm sẽ được tiến hành bằng cách sử dụng key’s data.

HashSkipList có một hạn chế đó là việc quét qua nhiều prefix yêu cầu sao chép và sắp xếp, việc này sẽ gây chậm và tốn kém bộ nhớ.

Một số opions quan trọng khi cấu hình Memtable

AdvancedColumnFamily::memtable_factory: Tùy chỉnh việc thay đổi triển khai cơ bản của memtable và cung cấp các tùy chọn triển khai cụ thể (Mặc định sử dụng SkipListFactory)
ColumnFamilyOptions::write_buffer_size: Kích thước của một memtable (Mặc định: 64MB)
DBOptions::db_write_buffer_size: Tổng dung lượng của memtable trên các column family. Giúp quản lý tổng bộ nhớ được sử dụng bởi memtables. (Mặc định:0 (Tắt))
DBOptions::write_buffer_manager: Thay vì chỉ định tổng kích thước của memtables, người dùng có thể sử dụng một trình quản lý để giám sát việc sử dụng bộ nhớ của memtables. (Mặc định là: nullptr)
AdvancedColumnFamilyOptions::max_write_buffer_number: Số lượng memtable tồn tại trong bộ nhớ, trước khi đẩy vào SST files (Mặc định: 2)
AdvancedColumnFamilyOptions::max_write_buffer_size_to_mantain: Số lượng dữ liệu được lưu trữ trong bộ nhớ (được tính bằng byte). Nó bao gồm tổng dung lượng các memtable đang tồn tại trong bộ nhớ. RocksDB sẽ cố gắng lưu trữ nhiều dữ liệu nhất trong bộ nhớ - nếu mà việc xoá bỏ một memtable đã được đẩy vào sstfiles dẫn đến bộ nhớ giảm xuống dưới ngưỡng này thì, memtable đó sẽ không bị xoá. (Mặc định: 0)

Cơ chế Flush của memtable

Ba trường hợp Memtable sẽ tiến hành flush vào SSTfiles bao gồm:

Kích thước dữ liệu vượt quá kích thước của memtable được cài đặt sau khi tiến hành ghi.
Tổng dung lượng của memtable trên tất cả các column families vượt qua tổng dung lượng được cài đặt hoặc DBOptions::write_buffer_manager đưa ra cảnh báo. Thì bảng memtable có dung lượng lớn nhất sẽ được tiến hành flush vào SSTfiles.
Dung lượng của file WAL vượt quá kích thước tối đa mà file được cài đặt để lưu trữ. Khi đó thì memtable có data cũ nhất sẽ được tiến hành đẩy vào sstfiles.

Từ ba trường hợp trên có thể thấy rằng, trước khi memtable đầy nó cũng có thể bị đẩy vào sstfile. Do đó sẽ có một số trường hợp mà sstfile có dung lượng nhỏ hơn so với memtable.

2.2 Write-Ahead Log(WAL)

Mỗi khi có update đến RocksDB thì dữ liệu sẽ được ghi vào 2 nơi. Đầu tiền dữ liệu sẽ được tiến hành ghi vào trong Memtable, sau đó sẽ được đẩy vào SStfile. Thứ 2, dữ liệu sẽ được tiến hành ghi vào trong WAL ở trên đĩa. Trong trường hợp khi mà xảy ra lỗi trong quá trình đẩy từ memtable vào trong SSTfile thì WAL sẽ được sử dụng để tiến hành khôi phục hoàn toàn dữ liệu trong memtable. Trong cấu hình mặc định, RocksDB đảm bảo tính nhất quán của quá trình khi gặp sự cố bằng cách xoá WAL sau mỗi lần người dùng viết.

2.2.1 Vòng đời của WAL

Khi tạo mới một DB, WAL sẽ được tạo ra để tiến hành lưu trữ tất cả những dữ liệu được ghi vào trong DB.
Khi có dữ liệu mới được tạo, WAL sẽ tiến hành lưu trữ toàn bộ các dữ liệu mới này. WAL sẽ giữ chúng cho đến khi dung lượng lưu trữ đạt đến giá trị DBOptions::max_total_wal_size
Khi người dùng đẩy một số data từ column family vào trong SSTfiles. WAL mới sẽ được tạo và tất cả những lần ghi tới sẽ được tiến hành ghi vào trong WAL mới này. WAL cũ sẽ không chấp nhận những lần ghi sau việc xóa WAL cũ có thể được tiến hành trì hoãn.
Tại thời điểm này WAL sẽ có số lượng là 2. WAL mới chứa dữ liệu mới, và WAL cũ chứa giá trị là của những column family khác mà chưa được chuyển vào SSTfile. WAL chỉ bị xoá khi toàn bộ các column family của WAL được chuyển hết vào SSTfile.

2.2.2 Cấu hình của WAL

DBOption::wal_dir : cấu hình địa chỉ thư mục lưu trữ WAL, thư mục này có thể nằm riêng biệt với dữ liệu thực.
DBOption::WAL_ttl_seconds, DBOptions::WAL_size_limit_MB: hai trường này ảnh hưởng đến tốc độ xóa WAL đã lưu trữ. Giá của chúng cho biết ngưỡng thời gian và dung lượng ổ cứng để tiến hành kích hoạt WAL đã lưu trữ.
DBOptions::max_total_wal_size: Dùng để giới hạn kích thước của WAL.
DBOptions::manual_wal_flush: dùng để xác định người dùng sẽ tiến hành xóa WAL thủ công hay tự động (nếu tiến hành xóa thủ công thì sẽ tiến hành gọi hàm FushWAL)
DBoptions::wal_filter, người dùng có thể cung cấp một đối tượng bộ lọc khi xử lý WAL trong quá trình khôi phục. Lưu ý không được hỗ trợ trong chế độ RocksDB_Lite
WriteOptions::disableWAL: được sử dụng để tắt WAL nếu có một log khác lưu trữ dữ liệu backup.

2.3 SSTFiles

SSTFile trong đó SST là viết tắt của từ Sorted Sequence Table. Ở trong SSTFiles tất cả các key đều được tiến hành sắp xếp. SSTFiles sử dụng một số format như BlockBasedTable, PainTable Format, CuckooTable Format. Trong đó BlockBasedTable là kiến trúc được sử dụng mặc định trong RocksDb.

BlockBasedTable

BlockBaseTable gồm 5 phần chính bao gồm Datablock, Meta Block, Metaindex Block, Index Block, Footer

DataBlock

Shared key length

Unshared key length

Value length

Unshared key content

Value

Khối dữ liệu lưu trữ khóa / giá trị theo tuần tự và 5 giá trị được lưu trữ cho một khối duy nhất

Mỗi cặp entry được lưu trữ với cấu trúc bao gồm 5 phần:

Độ dài của phần được chia sẻ với khóa bản ghi trước đó, 0 có nghĩa là Mục nhập là điểm khởi động lại;
Độ dài của phần không được chia sẻ với khóa bản ghi trước đó;
chiều dài giá trị;
Nội dung không được chia sẻ với khóa bản ghi trước đó;
giá trị nội dung

restart_interval=2

entry one : key=deck,value=v1

entry two : key=dock,value=v2

entry three: key=duck,value=v3

Restart_interval = 2 tức là số lượng của các restart là 2. Các restart các nhau một offset mặc định là 16. Mục đích của điểm Khởi động lại là để tăng tốc quá trình tìm kiếm khi đọc nội dung sstable.

MetaBlock

Cấu trúc BlockHandle bao gồm:

offset: varint64

size: varint64

Bloom Filter

Bloom Filter giúp xác định xem key cần tìm có tồn tại trong SSTfiles hay không mà không cần phải truy cập vào trong SSTfiles.

Khi một file SSTfiles được tạo thì Bloom Filter cũng sẽ được tạo ở mỗi một tệp SSTfiles theo cùng một cách khác nhau.

Khi mở tệp SST, Bloom Filter cũng được mở và tải vào bộ nhớ bằng cách sử dụng các thông số cấu hình ban đầu của nó ( NewBloomFilterPolicy). Khi đóng tệp SST, bộ lọc sẽ bị xoá khỏi bộ nhớ. Có thể lưu bộ lọc vào bộ nhớ đệm bằng cách sử dụng cấu BlockBaseTableOptions::cache_index_and_filter_blocks = true.

Ở phiên bản RocksDB 16.6 trở đi thì 16 bit/key có thể giảm tỷ lệ giảm xuống còn 0,1%. Bloom Filter Block có thể chiếm nhiều bộ nhớ và không có trong cấu hình bộ nhớ đệm.

Meta index Block

Thông tin của mỗi khối meta được ghi lại và mỗi bản sao cũng là một cấu trúc key/value. Khóa là tên của khối meta. Giá trị là một con trỏ của loại BlockHandle, trỏ đến vị trí thực

Index Block

Được sử dụng để tìm kiếm nhanh phạm vi của khoá tra cứu. Nó có thể là tệp chứa một index block hoặc một danh sách của partitioned index blocks.

Giá trị key của khoá được lưu trữ nằm giữa khoá của khối cuối cùng và khoá đầu tiên của khối tiếp theo. Mục đích của việc này nhằm giảm kích thước của chỉ mục.

Ví dụ: Ta có key cuối cùng của block là “apple”. Key đầu tiên của block tiếp theo là “acknowledge” thì thay vì sử dụng key chỉ mục là “apple” thì ta có thể sử dụng key chỉ mục là “ad” với apple < ad < acknowledge. Làm cho dung lượng chỉ mục giảm mà hiệu quả truy xuất là như nhau.

Giá trị value của chỉ mục là một BlockHandle, trỏ đến dữ liệu tương ứng của khối.

Cấu trúc Kv lưu trữ các thuộc tính khác nhau của tệp sst hiện tại (kích thước dữ liệu, kích thước chỉ mục, kích thước bộ lọc)

Thông tin trong Footer cho biết vị trí của metaindexblock và indexblock, sau đó là Meta Block và DataBlock.

3. Compaction

Các kiểu nén dữ liệu của RocksDB bao gồm:

Leveled Compaction
Universal Compaction
FIFO Compaction

Kiểu nén cơ bản thường được sử dụng trong RocksDb là Leveled Compaction

Leveled Compaction

Các tệp trên đĩa được tổ chức theo nhiều cấp độ. Chúng tôi gọi chúng là cấp độ 1, cấp độ 2, v.v., gọi tắt là L1, L2, v.v. Mức đặc biệt-0 (hay gọi tắt là L0) chứa các tệp vừa được xóa từ bộ đệm ghi trong bộ nhớ (ghi nhớ). Mỗi cấp độ (ngoại trừ cấp độ 0) là một lần chạy dữ liệu được sắp xếp:

Bên trong mỗi cấp (ngoại trừ cấp 0), dữ liệu được phân vùng theo phạm vi thành nhiều tệp SST:

Tất cả các cấp khác 0 đều có kích thước mục tiêu. Mục tiêu của Compaction sẽ là hạn chế kích thước dữ liệu của các cấp đó nằm dưới mục tiêu. Các mục tiêu về kích thước thường tăng lên theo cấp số nhân:

Kích hoạt nén khi số lượng tệp L0 đạt đến level0_file_num_compaction_trigger, các tệp L0 sẽ được hợp nhất thành L1. Thông thường, phải chọn tất cả các tệp L0 vì chúng thường chồng chéo:

Nén được thực hiện cho đến khi dữ liệu lưu trữ tại cấp độ nào mà không nó không bị tràn dung lượng

4. Một số use case của RocksDb

1.LinkedIn: Sử dụng RocksDB làm công cụ lưu trữ

a. Linkedln’s follow feed cho việc lưu trữ hành vi của người dùng

b. Apache Samze, open-source framework cho stream processing

2. Yahoo: sử dụng RocksDB như một storage engine cho hệ thống lưu trữ dữ liệu phân tán lớn nhất của họ Sherpa

3. Netflix: sử dụng RocksDB trên AWS EC2 instances với SSD drives để cache dữ liệu ứng dụng.

4. Apache Flink, Dgraph: sử dụng RocksDB để lưu trữ trạng thái cục bộ trên máy

5….

Nguồn tham khảo: