從零開始寫KV資料庫：基于哈希索引

前言

新的KV資料庫層出不窮，我們經常聽說的KV資料庫如RocksDb、Hbase等都是基于日志結構的存儲引擎。最近我在看《資料密集型應用系統設計》，裡面有一章專門在講日志結構的存儲引擎的演進過程，純看理論不過瘾，是以我決定根據書裡的理論動手自己實作一個KV資料庫。同時，為了能順便學習Rust，是以我使用了Rust來實作資料庫。

除了參考《資料密集型應用系統設計》，我還參考了《

pingcap/talent-plan

》中使用Rust實作KV資料庫的源碼，恰好它的實作就是基于哈希索引和日志壓縮的原理，跟書中的描述不謀而合。通過實作一個迷你資料庫來學習和了解資料庫的原理是一種學以緻用的方式，能夠幫助我們更加深入了解資料庫原理。閑話不多說，開始正文。

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%9C%80%E7%AE%80%E5%8D%95%E7%9A%84%E6%95%B0%E6%8D%AE%E5%BA%93 最簡單的資料庫

在上正菜之前先來一道甜點，你知道最簡單的資料庫隻需要幾行代碼嗎？隻需要兩行，一行讀取，一行寫入。

#!/bin/bash

db_set() {
        echo "$1,$2" >> database
}

db_get() {
        grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
           

可以嘗試儲存腳本，然後在shell中試一下。

➜  ~ source db.sh
➜  ~ db_set key1 value1
➜  ~ db_set key2 value2
➜  ~ db_set key1 value1
➜  ~ db_set key1 value2
➜  ~ db_get key1
value2
➜  ~ cat database
key1,value1
key2,value2
key1,value1
key1,value2
           

是不是很神奇，其實原理很簡單，set的操作是将資料追加到檔案末尾，get的操作是先grep找到所有key的資料，然後再取最後一條資料（tail -n 1）作為結果。仔細思考一下，這個資料庫邏輯是正确的，而且還是持久化的。

這個資料庫原理雖然簡單，但是其中set使用日志追加的方式寫入資料卻是很多資料庫的常用方式，因為日志追加性能非常好。相對的，get的方式性能就比較差了，需要從頭到尾掃描整個檔案，查詢的開銷是O(n)。

為了提高讀取的性能，我們需要用到索引，基本的思路就是通過儲存額外的中繼資料，根據這些中繼資料作為路标來快速定位到想要的資料。但是天下沒有免費的午餐，維護索引需要在寫入的時候額外寫入其他資料，這會影響寫入的性能。這裡就涉及到存儲系統中重要的權衡設計：**适當的索引可以加速讀取，但是每個索引都會減慢寫入的速度。**下面我們就給我們簡單的資料庫加上最簡單的索引方式：哈希索引。

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E5%9F%BA%E4%BA%8E%E5%93%88%E5%B8%8C%E7%B4%A2%E5%BC%95%E7%9A%84%E6%95%B0%E6%8D%AE%E5%BA%93 基于哈希索引的資料庫

回想一下我們經常使用HashMap資料結構，哈希索引就是基于記憶體的HashMap來實作的，不同的是我們在記憶體裡面使用HashMap的時候value都是直接存儲原始資料的，對于資料庫來說，如果你把所有的原始資料都直接存儲到記憶體的話，這是不現實的。那怎麼辦呢？想想我們在程式設計裡面常用的指針，是不是得到啟發了？我們可以在記憶體裡面儲存原始資料的“指針”，即檔案的位元組偏移量和資料的長度。指針的占用量很小，這樣我們完全可以把整個資料庫的key的索引都放到記憶體裡面，讀取的時候直接找到key在檔案中的偏移量，直接去磁盤讀取資料。

借用書中的圖示 

https://github.com/x-hansong/mweb/blob/master/docs/media/16133547248991/16133590637325.jpg

這個哈希索引的原理聽起來很簡單，但是這可是在生産中被實際使用過的Bitcask資料庫的核心原理。隻要保證所有key都能放到記憶體裡面，Bitcask就能提供高性能的讀寫，因為它的索引結構簡單，寫入也是記憶體操作，可以說索引的代價可以忽略不計，而讀取隻需要一次記憶體尋址，在有檔案系統緩存時甚至不需要IO操作。在某些場景中這個資料庫可以完爆其他所有資料庫。

了解了基本原理之後，下面開始實操環節。

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%95%B0%E6%8D%AE%E5%91%BD%E4%BB%A4 資料指令

首先定義一下我們資料庫的基本功能：

• set：儲存KV
• get：擷取資料
• rm：删除資料

如果基于日志追加來做，我們的存儲結構要怎麼設計呢？肯定不能按照前面的簡單資料庫那樣搞，因為光把資料存進去不能支援删除資料的功能。回想一下MySQL的RedoLog，我們可以得到一些啟發。如果我們不記錄原始資料，而是記錄資料指令呢？例如，我們按照下面的格式來記錄資料。

set: key1,value1
set: key2,value2
set: key1,value1
rm: key1
           

因為寫入的操作隻有兩個：set和rm，是以我們可以定義兩個資料指令，每次都把這些資料指令記錄到日志裡面，這樣讀取的時候讀取到的就是資料指令，假設我們現在讀取key2，實際上從磁盤讀取到的資料是：

set: key2,value2

，這樣我們就知道key2現在的最新值是value2，當讀取key1的時候，從磁盤讀取到的資料是

rm: key1

，那麼意味着key1已經被删除了。

在Rust中資料指令的定義如下：

pub enum Command {
    Set { key: String, value: String },
    Remove { key: String },
}
           

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%95%B0%E6%8D%AE%E5%86%99%E5%85%A5 資料寫入

接下來定義我們的資料庫對象，成員變量隻有三個，一個讀取器、一個寫入器、一個索引。

pub struct KvStore {
    reader: BufReaderWithPos<File>,
    writer: BufWriterWithPos<File>,
    index: HashMap<String, CommandPos>,
}

struct CommandPos {
    pos: u64,
    len: u64,
}
           

• BufReaderWithPos：帶有尋址讀取功能的讀取器
• BufWriterWithPos：帶有尋址寫入功能的寫入器
• CommandPos：記錄指令的起始位置和長度

那麼寫入操作具體要做什麼呢？看一下的代碼注釋

pub fn set(&mut self, key: String, value: String) -> Result<()> {
        //構造一個寫入指令
        let cmd = Command::set(key, value);
        //擷取目前寫入句柄的位置
        let pos = self.writer.pos;
        //通過serde把set指令序列化成json寫入到檔案中
        serde_json::to_writer(&mut self.writer, &cmd)?;
        //檔案刷盤持久化
        self.writer.flush()?;
        if let Command::Set { key, .. } = cmd {
        //記錄寫入指令的開始位置和長度
            let cmd_pos = CommandPos { pos, len: self.writer.pos - pos };
            //把目前key的最新指令位置記錄到索引裡面
            self.index.insert(key, cmd_pos);
        }

        Ok(())
    }
           

删除操作也是類似的：

pub fn remove(&mut self, key: String) -> Result<()> {
        if self.index.contains_key(&key) {
            //構造删除指令
            let cmd = Command::remove(key);
            //寫入到檔案
            serde_json::to_writer(&mut self.writer, &cmd)?;
            self.writer.flush()?;
            if let Command::Remove { key } = cmd {
                //從索引中删除key，這樣就讀取不到了。
                self.index.remove(&key).expect("key not found");
            }
            Ok(())
        } else {
            Err(KvsError::KeyNotFound)
        }
    }
           

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%95%B0%E6%8D%AE%E8%AF%BB%E5%8F%96 資料讀取

資料讀取主要是從索引裡面擷取指令位置，然後從磁盤讀取指令傳回結果。

pub fn get(&mut self, key: String) -> Result<Option<String>> {
        //從索引中讀取key的指令位置，如果讀取不到說明key不存在
        if let Some(cmd_pos) = self.index.get(&key) {
            let reader = &mut self.reader;
            //把讀取器遊标設定到指令的起始位置
            reader.seek(SeekFrom::Start(cmd_pos.pos))?;
            //指定讀取的長度
            let cmd_reader = reader.take(cmd_pos.len);
            //讀取指令
            if let Command::Set {value, ..} = serde_json::from_reader(cmd_reader)? {
                Ok(Some(value))
            } else {
                Err(KvsError::UnexpectedCommandType)
            }
        } else {
            Ok(None)
        }
    }
           

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%95%B0%E6%8D%AE%E5%8A%A0%E8%BD%BD 資料加載

資料庫每次啟動都需要從檔案中指令回放一遍，然後建構出記憶體索引才能開始使用。

fn load(reader: &mut BufReaderWithPos<File>, index: &mut HashMap<String, CommandPos>) -> Result<()> {
    //設定檔案遊标到0，從開始周遊到檔案末尾
    let mut pos = reader.seek(SeekFrom::Start(0))?;
    let mut stream = Deserializer::from_reader(reader).into_iter::<Command>();
    //周遊指令
    while let Some(cmd) = stream.next() {
        let new_pos = stream.byte_offset() as u64;
        match cmd? {
            //如果是set指令就插入到索引中
            Command::Set {key, ..} => {
                index.insert(key, CommandPos{pos, len: new_pos - pos});
            },
            //如果是rm指令就從索引中删除key
            Command::Remove {key} => {
                index.remove(&key);
            }
        }
        pos = new_pos;
    }
    Ok(())
}
           

至此，一個簡單的基于哈希索引的資料庫就完成了。完整代碼可以參考：

log_base

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%97%A5%E5%BF%97%E6%96%87%E4%BB%B6%E5%8E%8B%E7%BC%A9 日志檔案壓縮

上面我們實作的資料庫有一個明細的缺陷：如果使用時間很長的情況下，日志檔案會非常大，可能把磁盤用光了。是以要想辦法對日志檔案進行壓縮，可以發現對于相同的key在日志檔案中會重複儲存，而且實際上我們隻會使用最新的指令。這部分沒用的指令是可以删除掉的。是以，一個簡單的日志壓縮方式就是把重複的key删除掉隻保留每個key最近的更新。

https://github.com/x-hansong/mweb/blob/master/docs/media/16133547248991/16133913799357.jpg

壓縮日志檔案實作會比較複雜，核心思路就是要将日志進行分段處理，當日志大小超過某個門檻值時，建立一個日志用于寫入，然後再建立一個日志将之前的全部日志周遊一遍進行壓縮，最後将原始日志删除。 由于加入了分段日志的設計，是以現在要尋找一個key在磁盤的位置，需要增加一個次元：日志檔案的序号。即指令位置的資料結構需要新增一個gen字段用于辨別檔案的序号。

struct CommandPos {
    gen: u64,
    pos: u64,
    len: u64,
}
           

資料庫的成員對象也需要修改，具體見注釋。

pub struct KvStore {
    //記錄日志檔案的目錄
    path: PathBuf,
    //從單個讀取器修改為多個日志讀取器的集合，key是日志檔案的序号
    readers: HashMap<u64, BufReaderWithPos<File>>,
    writer: BufWriterWithPos<File>,
    index: HashMap<String, CommandPos>,
    //記錄目前寫入的檔案序号，壓縮時寫入的檔案序号會自增切換到新的檔案上
    current_gen: u64,
    //記錄目前未壓縮的指令大小
    uncompacted: u64,
}
           

壓縮日志的代碼實作如下：

pub fn compact(&mut self) -> Result<()> {
        //新增一個壓縮日志序号，為目前序号+1
        let compaction_gen = self.current_gen + 1;
        //目前寫入的日志序号+2，作為新的日志寫入序号
        self.current_gen += 2;
        self.writer = self.new_log_file(self.current_gen)?;

        let mut new_pos = 0;
        //根據壓縮日志序号建立一個寫入器
        let mut compaction_writer = self.new_log_file(compaction_gen)?;
        //周遊目前索引的所有key
        for cmd_pos in &mut self.index.values_mut() {
            //擷取目前key的關聯的檔案讀取器
            let reader = self.readers.get_mut(&cmd_pos.gen)
                .expect(format!("Can't find reader: {}", &cmd_pos.gen).as_str());
            //将讀取器的遊标切換到指令的起始位置
            if reader.pos != cmd_pos.pos {
                reader.seek(SeekFrom::Start(cmd_pos.pos))?;
            }
            //設定讀取器讀取的資料長度
            let mut cmd_reader = reader.take(cmd_pos.len);
            //把指令拷貝到壓縮日志寫入器中
            let len = io::copy(&mut cmd_reader, &mut compaction_writer)?;
            //更新索引中key的指令位置資料
            *cmd_pos = CommandPos {gen: compaction_gen, pos: new_pos, len };
            new_pos += len;
        }
        compaction_writer.flush()?;

        //因為日志序号是從小到大增長的，要删除之前的日志隻需要把小于壓縮日志序号的檔案都删除掉就行
        let stale_gens: Vec<_> = self.readers.keys()
            .filter(|&&gen| gen < compaction_gen)
            .cloned().collect();
        for stale_gen in stale_gens {
            self.readers.remove(&stale_gen);
            fs::remove_file(log_path(&self.path, stale_gen))?;
        }
        self.uncompacted = 0;

        Ok(())
    }
           

看代碼可能不太好了解日志壓縮的過程，下面我們舉一個日志檔案壓縮的例子 

https://github.com/x-hansong/mweb/blob/master/docs/media/16133547248991/16133930983425.jpg

 壓縮過程中讓目前寫入切換到3.log，可以保證寫入不受影響，同時新增一個2.log作為壓縮日志進行拷貝，邊拷貝邊更新索引，可以保證讀取不受影響，等壓縮完成之後，把1.log删除，平滑切換到新的日志上面。

完整的源碼可以參考：

log_compact

，這裡的實作為了簡單起見沒有按照書裡面使用異步線程去做，是在set的時候判斷未壓縮的大小是否超過門檻值進行同步壓縮的，即會阻塞寫入操作，這是一個可優化點，在後續的更新中會優化掉，但是日志壓縮思路是一緻的。

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E5%93%88%E5%B8%8C%E7%B4%A2%E5%BC%95%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9 哈希索引的優缺點

哈希索引使用順序寫入的日志來追加式地記錄每一個指令，看起來非常浪費存儲空間：為什麼不是直接原地更新檔案，用新資料覆寫老資料呢？實際上追加式的設計是非常優秀的，主要原因有以下幾個：

• 追加式主要使用順序寫入，性能非常高，比起覆寫式的随機寫入要快得多。
• 追加式的寫入在處理并發和崩潰恢複時要簡單得多，例如不需要擔心在重寫值時發生崩潰的情況，追加式寫入時如果崩潰了，隻需要丢棄檔案末尾有問題的資料，而覆寫式更新崩潰，你都不知道哪些資料是髒資料。
• 追加式的日志寫入可以通過合并舊的日志檔案解決碎片化的問題。

說了優點之後，也要說一下缺點：

• 哈希索引的實作要求所有key都放到記憶體裡面，如果有大量的key存在，那麼就沒辦法處理了。理論上可以把索引放到磁盤上面，但是這樣讀取速度就會受到影響。
• 無法支援快速的區間查詢，隻能周遊一遍所有key。

https://github.com/x-hansong/mweb/blob/master/docs/16133547248991.md#%E6%80%BB%E7%BB%93 總結

本文主要說明了基于哈希索引的KV資料庫的實作原理，同時給出了代碼實作。基于追加式日志寫入的哈希索引非常簡單高效，同時也有一定的局限性。哈希索引隻是KV資料庫的起步，後續我們還會看到解決哈希索引缺點的新索引結構（LSM-tree），這些索引設計的思想是很多先進KV資料庫（如Hbase、Cassandra）的基石。