Rust實作高效Key-Value儲存與索引機制

– 10 分鐘閱讀

Rust 的 HashMap 與 BTreeMap 提供了不同的特性，適用於不同場景。HashMap 效率更高，適合無序的鍵值對應關係，而 BTreeMap 則能維護鍵的排序，適用於需要排序的場景。ActionKV 是一個根據 Rust 的鍵值儲存系統，透過索引機制提升資料存取效率。索引以 BTreeMap 的形式儲存，並在系統啟動時載入到記憶體中，以便快速定位鍵值對應的磁碟位置。ActionKV 的設計包含磁碟儲存和記憶體儲存兩種模式，分別對應 akv_disk 和 akv_mem 模組，並使用 bincode 函式庫進行序列化和反序列化，以實作索引的持久化。為了最佳化啟動速度，ActionKV 將索引資料儲存在與應用程式資料相同的檔案中，避免每次啟動都重建索引。程式碼範例展示瞭如何使用 HashMap 和 BTreeMap 進行資料儲存和查詢，以及如何使用 bincode 進行序列化和反序列化操作，並說明瞭 ActionKV 如何讀取、更新和儲存索引資料。

HashMap和BTreeMap的選擇

在選擇HashMap和BTreeMap時，需要根據具體的情況進行選擇。一般而言，如果需要維護鍵值對應關係的順序，BTreeMap是一個更好的選擇。否則，HashMap是一個更高效的選擇。

示例：荷蘭東印度公司的投資

以下是一個示例，展示瞭如何使用libactionkv函式庫儲存和查詢荷蘭東印度公司的投資資料：

use std::collections::HashMap;

fn main() {
    let mut investments = HashMap::new();

    investments.insert("Rotterdam", 173000);
    investments.insert("Hoorn", 266868);
    investments.insert("Delft", 469400);
    investments.insert("Enkhuizen", 540000);
    investments.insert("Middelburg", 1300405);
    investments.insert("Amsterdam", 3697915);

    for (city, investment) in &investments {
        println!("{} invested {}", city, investment);
    }
}

這個示例建立了一個HashMap，儲存了荷蘭東印度公司各個城市的投資資料。然後，它遍歷了HashMap，列印預出了每個城市的投資資料。

處理集合資料：BTreeMap 的應用

在 Rust 中，BTreeMap 是一個有序的對映（Map），它能夠將鍵值對儲存於樹狀結構中。這使得它非常適合需要維護鍵的排序順序的應用場景。下面，我們將展示如何使用 BTreeMap 來儲存和處理一些城市及其對應的人口資料。

建立 BTreeMap

首先，讓我們建立一個 BTreeMap 例項，並向其中插入一些資料。這些資料代表著荷蘭一些城市及其人口資料。

use std::collections::BTreeMap;

fn main() {
    let mut population_map = BTreeMap::new();
    
    population_map.insert(3_697_915, "Amsterdam");
    population_map.insert(1_300_405, "Middelburg");
    population_map.insert(540_000, "Enkhuizen");
    population_map.insert(469_400, "Delft");
    population_map.insert(266_868, "Hoorn");
    population_map.insert(173_000, "Rotterdam");
}

迭代和顯示資料

接下來，我們將迭代這個 BTreeMap 中的所有元素，並列印預出每個城市及其人口資料。

for (population, city) in &population_map {
    println!("{} 人口居住在 {}", population, city);
}

這段程式碼將會輸出每個城市及其對應的人口資料，按照人口資料的順序排列。

內容解密：

  • BTreeMap::new() 用於建立一個新的空 BTreeMap 例項。
  • insert() 方法用於向 BTreeMap 中新增新的鍵值對。在這裡，鍵是城市的人口資料，值是城市的名稱。
  • for 迴圈用於迭代 BTreeMap 中的所有元素。迴圈變數 population 和 city 分別對應於每個鍵值對中的鍵（人口資料）和值（城市名稱）。
  • println! 宏用於列印預出每個城市及其人口資料。

圖表翻譯：

以下是使用 Mermaid 語法繪製的流程圖，描述瞭如何建立和使用 BTreeMap：

  flowchart TD
    A[建立 BTreeMap] --> B[插入資料]
    B --> C[迭代和顯示資料]
    C --> D[列印結果]

這個流程圖展示了從建立 BTreeMap、插入資料、迭代和顯示資料，到最終列印結果的整個過程。

新增資料函式庫索引到 actionkv v2.0

資料函式庫和檔案系統比單個檔案更複雜，涉及大量的設計空間和儲存與檢索系統。這就是為什麼新系統一直在被開發的原因。然而，這些系統都有一個共同的元件，那就是真正的智慧之後的資料函式庫。

在 7.5.2 節中建立的 actionkv v1 存在一個重大問題，導致它無法在合理的時間內啟動。每次執行時，它都需要重建其索引以查詢儲存的金鑰。現在，我們將新增 actionkv 儲存其自身索引資料的能力，該索引位於與應用程式資料相同的檔案中。這比你想象的要容易，並且不需要對 libactionkv 進行任何修改。前端程式碼只需要進行少量修改。專案目錄現在具有新的結構，並包含一個額外的檔案（如下所示）。

###範例 7.20：展示範圍查詢和有序迭代的 BTreeMap

實作說明
std::collections::HashMap (預設雜湊函式，稱為 SipHash)密碼學上安全，對拒絕服務攻擊具有抵禦能力，但比其他雜湊函式慢
std::collections::BTreeMap對於具有內在順序的金鑰很有用，快取一致性可以提供速度上的提升；按排序順序列印

BTreeMap 可以讓你選擇金鑰的一部分。

實作索引

為了實作索引，我們需要對 actionkv 的儲存機制進行修改，以便它可以儲存索引資料。這涉及到修改儲存格式和讀寫邏輯。

修改儲存格式

我們將在儲存檔案中新增一個新的部分，用於儲存索引資料。這個部分將包含一個 BTreeMap，該對映將金鑰對映到其對應的值。

修改讀寫邏輯

當 actionkv 啟動時，它將讀取索引資料並建立 BTreeMap。當有新的金鑰-值對被新增或刪除時，actionkv 將更新索引資料。

###範例程式碼

use std::collections::BTreeMap;
use std::fs::File;
use std::io::{Read, Write};

struct ActionKV {
    //...
    index: BTreeMap<String, String>,
}

impl ActionKV {
    fn new() -> Self {
        //...
        let mut index = BTreeMap::new();
        //...
        ActionKV { index, /*... */ }
    }

    fn insert(&mut self, key: String, value: String) {
        //...
        self.index.insert(key.clone(), value.clone());
        //...
    }

    fn remove(&mut self, key: String) {
        //...
        self.index.remove(&key);
        //...
    }

    fn save_index(&self) -> Result<(), std::io::Error> {
        let mut file = File::create("index.dat")?;
        let mut index_data = Vec::new();
        for (key, value) in &self.index {
            index_data.push(key.as_bytes());
            index_data.push(value.as_bytes());
        }
        file.write_all(&index_data)?;
        Ok(())
    }

    fn load_index(&mut self) -> Result<(), std::io::Error> {
        let mut file = File::open("index.dat")?;
        let mut index_data = Vec::new();
        file.read_to_end(&mut index_data)?;
        let mut index = BTreeMap::new();
        for chunk in index_data.chunks(2) {
            let key = String::from_utf8_lossy(&chunk[0]).into_owned();
            let value = String::from_utf8_lossy(&chunk[1]).into_owned();
            index.insert(key, value);
        }
        self.index = index;
        Ok(())
    }
}

瞭解 ActionKV 核心：libactionkv 函式庫

ActionKV 是一個根據 Rust 的資料函式庫實作，旨在提供高效的鍵值儲存和查詢功能。下面是 ActionKV 專案結構的概覽：

actionkv
├── src
│   ├── akv_disk.rs
│   ├── akv_mem.rs
│   └── lib.rs
└── Cargo.toml

在 Cargo.toml 檔案中，我們增加了一些新的依賴項和一個二進位制入口。以下是 Cargo.toml 檔案的相關內容：

[package]
name = "actionkv"
version = "2.0.0"
edition = "2018"

[dependencies]
bincode = "1"
byteorder = "1"
crc = "1"
serde = "1"
serde_derive = "1"

這些依賴項包括 bincode、byteorder、crc 和 serde，它們分別用於二進位制編碼、位元組順序、迴圈冗餘校驗和序列化。其中，serde 和 serde_derive 用於實作序列化和反序列化功能。

在 src 目錄下，我們有三個 Rust 檔案：akv_disk.rs、akv_mem.rs 和 lib.rs。這些檔案分別實作了 ActionKV 的磁碟儲存、記憶體儲存和函式庫功能。

下面是 akv_disk.rs 檔案的簡要內容：

// akv_disk.rs
use std::fs::File;
use std::io::{Read, Write};

pub struct AkvDisk {
    file: File,
}

impl AkvDisk {
    pub fn new(file_path: &str) -> Self {
        let file = File::create(file_path).unwrap();
        AkvDisk { file }
    }

    pub fn write(&mut self, key: &str, value: &str) {
        let mut buffer = Vec::new();
        buffer.extend_from_slice(key.as_bytes());
        buffer.extend_from_slice(value.as_bytes());
        self.file.write_all(&buffer).unwrap();
    }

    pub fn read(&mut self, key: &str) -> Option<String> {
        let mut buffer = Vec::new();
        self.file.read_to_end(&mut buffer).unwrap();
        let data = String::from_utf8_lossy(&buffer);
        if data.contains(key) {
            let value = data.split(key).nth(1).unwrap();
            Some(value.to_string())
        } else {
            None
        }
    }
}

這個實作提供了基本的鍵值儲存和查詢功能，使用磁碟檔案進行資料儲存。

同樣地，akv_mem.rs 檔案實作了記憶體儲存版本的 ActionKV：

// akv_mem.rs
use std::collections::HashMap;

pub struct AkvMem {
    map: HashMap<String, String>,
}

impl AkvMem {
    pub fn new() -> Self {
        AkvMem {
            map: HashMap::new(),
        }
    }

    pub fn write(&mut self, key: &str, value: &str) {
        self.map.insert(key.to_string(), value.to_string());
    }

    pub fn read(&self, key: &str) -> Option<String> {
        self.map.get(key).cloned()
    }
}

這個版本使用 HashMap 來儲存鍵值對，提供了快速的查詢和儲存功能。

最後，lib.rs 檔案提供了 ActionKV 函式庫的入口點，匯總了磁碟儲存和記憶體儲存的功能：

// lib.rs
pub mod akv_disk;
pub mod akv_mem;

使用者可以根據需要選擇使用磁碟儲存或記憶體儲存版本的 ActionKV。

圖表翻譯：

  flowchart TD
    A[ActionKV] --> B[akv_disk.rs]
    A --> C[akv_mem.rs]
    B --> D[磁碟儲存]
    C --> E[記憶體儲存]
    D --> F[write]
    D --> G[read]
    E --> H[write]
    E --> I[read]

這個圖表展示了 ActionKV 的架構和功能，包括磁碟儲存和記憶體儲存版本的鍵值儲存和查詢功能。

行動KV（ActionKV）儲存系統的索引機制

行動KV是一種簡單的鍵值儲存系統，旨在提供高效的資料存取和管理。在行動KV的設計中，索引機制扮演著關鍵角色，負責將鍵值對對映到磁碟上的物理位置。當使用者嘗試存取某個鍵的值時，系統需要先載入索引並將其轉換為記憶體中的形式，以便快速定位該鍵值對應的磁碟位置。

行動KV的索引實作

在行動KV的實作中，索引被儲存為一個特殊的鍵值對，稱為INDEX_KEY。這個鍵值對被儲存於磁碟上，並在系統啟動時載入記憶體。當使用者嘗試存取某個鍵的值時，系統會先檢查是否存在相應的索引紀錄，如果存在，則直接傳回對應的值；否則，系統會將索引紀錄寫入磁碟，並更新記憶體中的索引。

行動KV的目錄結構

行動KV的目錄結構如下所示：

lib
name = "libactionkv"
path = "src/lib.rs"

[[bin]]
name = "akv_mem"
path = "src/akv_mem.rs"

[[bin]]
name = "akv_disk"
path = "src/akv_disk.rs"

在這個目錄結構中，libactionkv是行動KV的核心函式庫，提供了基本的鍵值儲存和管理功能。akv_mem和akv_disk是兩個獨立的二進位制檔案，分別實作了行動KV的記憶體和磁碟儲存功能。

行動KV的索引載入過程

當使用者嘗試存取某個鍵的值時，行動KV會先載入索引並將其轉換為記憶體中的形式。以下是索引載入過程的簡要概述：

match action {
    "get" => {
        let index_as_bytes = a.get(&INDEX_KEY)
           .unwrap()
           .unwrap();
        //...
    }
}

在這個過程中，行動KV會先檢查是否存在相應的索引紀錄，如果存在，則直接傳回對應的值；否則，系統會將索引紀錄寫入磁碟，並更新記憶體中的索引。

更新 Cargo.toml 以新增二進位檔和相依性

為了實作將索引寫入磁碟的功能，我們需要對 Cargo.toml 進行兩項更新。首先，新增必要的相依性以協助將索引寫入磁碟。接著，定義一個新的可執行檔以實作這個功能。

新增相依性

我們需要新增的相依性包括 bincode，它是一個用於序列化和反序列化 Rust 資料結構的函式庫。這個函式庫將幫助我們將索引寫入磁碟。

[dependencies]
bincode = "1.3.3"

新增可執行檔定義

定義一個新的可執行檔，其目的是負責將索引寫入磁碟。這個過程涉及到序列化索引資料結構並將其寫入檔案。

fn main() {
    //...
}

讀取和反序列化索引

在讀取索引時，我們需要先從磁碟中讀取索引檔案的內容，然後使用 bincode 對其進行反序列化。這個過程可以使用以下程式碼實作：

let index_as_bytes = std::fs::read("index.bin").unwrap();
let index_decoded = bincode::deserialize(&index_as_bytes).unwrap();
let index: HashMap<ByteString, u64> = index_decoded;

處理索引資料

在上述程式碼中，INDEX_KEY 是索引在資料函式庫中的內部隱藏名稱。由於 a.index 是一個 HashMap，它傳回的是 Option，而值本身也存放在 Option 中，以便於未來可能的刪除操作，因此我們需要使用兩次 unwrap() 來取得索引的值。

let index_value = a.index.get(&INDEX_KEY).unwrap().unwrap();

實作索引寫入磁碟

最後，實作將索引寫入磁碟的功能。這涉及到序列化索引資料結構並將其寫入檔案。

let mut file = std::fs::File::create("index.bin").unwrap();
bincode::serialize_into(&mut file, &index).unwrap();

內容解密：

上述程式碼片段展示瞭如何更新 Cargo.toml 以新增必要的相依性和可執行檔定義，然後讀取和反序列化索引，最後實作將索引寫入磁碟。這個過程涉及到序列化和反序列化 Rust 資料結構，以及檔案輸入輸出操作。

圖表翻譯：

  flowchart TD
    A[開始] --> B[新增相依性]
    B --> C[定義可執行檔]
    C --> D[讀取和反序列化索引]
    D --> E[處理索引資料]
    E --> F[實作索引寫入磁碟]
    F --> G[完成]

圖表翻譯：

此圖表展示了實作將索引寫入磁碟的步驟。從新增必要的相依性開始，接著定義可執行檔，然後讀取和反序列化索引，處理索引資料，最後實作將索引寫入磁碟。每一步驟都對應到特定的程式碼實作，共同完成了將索引寫入磁碟的功能。

使用 Rust 實作簡單的 Key-Value Store

在這個範例中，我們將實作一個簡單的 Key-Value Store，該 Store 可以持久化其索引資料。以下是實作的 Rust 程式碼：

use libactionkv::ActionKV;
use std::collections::HashMap;

const USAGE: &str = "
Usage:
    akv_disk.exe FILE get KEY
    akv_disk.exe FILE delete KEY
    akv_disk.exe FILE insert KEY VALUE
    akv_disk.exe FILE update KEY VALUE
";

fn main() {
    //...
}

fn get_key(index: &HashMap<String, usize>, key: &str) {
    match index.get(key) {
        None => eprintln!("{:?} not found", key),
        Some(&i) => {
            let kv = a.get_at(i).unwrap();
            println!("{:?}", kv.value)
        }
    }
}

Key-Value Store 的基本操作

Key-Value Store 支援以下基本操作：

  • get: 根據給定的 key 取得對應的 value。
  • delete: 刪除給定的 key 和其對應的 value。
  • insert: 插入一個新的 key-value 對。
  • update: 更新給定的 key 的 value。

實作 Key-Value Store

以下是 Key-Value Store 的實作程式碼：

use std::collections::HashMap;
use std::fs::File;
use std::io::{Read, Write};

struct KeyValueStore {
    index: HashMap<String, usize>,
    data: Vec<(String, String)>,
}

impl KeyValueStore {
    fn new() -> Self {
        KeyValueStore {
            index: HashMap::new(),
            data: Vec::new(),
        }
    }

    fn get(&self, key: &str) -> Option<&str> {
        self.index.get(key).map(|&i| &self.data[i].1)
    }

    fn delete(&mut self, key: &str) -> bool {
        if let Some(&i) = self.index.get(key) {
            self.index.remove(key);
            self.data.remove(i);
            true
        } else {
            false
        }
    }

    fn insert(&mut self, key: &str, value: &str) -> bool {
        if self.index.contains_key(key) {
            false
        } else {
            self.data.push((key.to_string(), value.to_string()));
            self.index.insert(key.to_string(), self.data.len() - 1);
            true
        }
    }

    fn update(&mut self, key: &str, value: &str) -> bool {
        if let Some(&i) = self.index.get(key) {
            self.data[i].1 = value.to_string();
            true
        } else {
            false
        }
    }

    fn save(&self, file: &str) -> std::io::Result<()> {
        let mut f = File::create(file)?;
        for (key, value) in &self.data {
            writeln!(f, "{} {}", key, value)?;
        }
        Ok(())
    }

    fn load(&mut self, file: &str) -> std::io::Result<()> {
        let mut f = File::open(file)?;
        let mut contents = String::new();
        f.read_to_string(&mut contents)?;
        for line in contents.lines() {
            let mut parts = line.split_whitespace();
            let key = parts.next().unwrap();
            let value = parts.collect::<Vec<_>>().join(" ");
            self.insert(key, &value);
        }
        Ok(())
    }
}

使用 Key-Value Store

以下是使用 Key-Value Store 的範例：

fn main() {
    let mut kv = KeyValueStore::new();
    kv.insert("key1", "value1");
    kv.insert("key2", "value2");
    println!("{:?}", kv.get("key1")); // Some("value1")
    println!("{:?}", kv.get("key2")); // Some("value2")
    kv.update("key1", "new_value1");
    println!("{:?}", kv.get("key1")); // Some("new_value1")
    kv.delete("key2");
    println!("{:?}", kv.get("key2")); // None
}

圖表翻譯：

  flowchart TD
    A[開始] --> B[初始化 Key-Value Store]
    B --> C[插入 key-value 對]
    C --> D[取得 key 的 value]
    D --> E[更新 key 的 value]
    E --> F[刪除 key 和其 value]
    F --> G[儲存 Key-Value Store 到檔案]
    G --> H[載入 Key-Value Store 從檔案]

圖表翻譯：

此圖表展示了 Key-Value Store 的基本操作流程。首先，初始化 Key-Value Store。然後，插入 key-value 對。接下來，取得 key 的 value。然後，更新 key 的 value。之後，刪除 key 和其 value。最後，儲存 Key-Value Store 到檔案和載入 Key-Value Store 從檔案。

從效能最佳化視角來看，HashMap 和 BTreeMap 的選擇取決於具體應用場景的需求。HashMap 使用雜湊表實作，平均時間複雜度在插入、刪除和查詢操作上都接近 O(1)，效能表現出色，尤其適用於頻繁的讀寫操作。然而，HashMap 無法保證鍵值對的順序。BTreeMap 則根據紅黑樹實作，能夠維持鍵的有序性，在範圍查詢和有序遍歷方面具有優勢，但其操作的時間複雜度為 O(log n)，相較於 HashMap 效率略低。技術團隊需要權衡資料量、操作型別和順序性需求，選擇最合適的資料結構。對於注重讀寫效能且無需排序的場景，HashMap 是更佳選擇；而對於需要有序性或範圍查詢的應用，BTreeMap 則更為適用。從技術演進角度來看，隨著硬體效能的提升和演算法的最佳化，HashMap 和 BTreeMap 的效能差異將逐漸縮小，未來可能出現更為高效且兼具兩者優勢的混合型資料結構。對於追求極致效能的應用，建議持續關注相關技術發展趨勢，並根據實際需求進行技術選型。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。