[[407855]]

前言

LSM-Tree 是很多 NoSQL 數據庫引擎的底層實現，例如 LevelDB，Hbase 等。本文基于《數據密集型應用系統設計》中對 LSM-Tree 數據庫的設計思路，結合代碼實現完整地闡述了一個迷你數據庫，核心代碼 500 行左右，通過理論結合實踐來更好地理解數據庫的原理。

一  SSTable（排序字符串表）

之前基于哈希索引實現了一個數據庫，它的局限性是哈希表需要整個放入到內存，并且區間查詢效率不高。

在哈希索引數據庫的日志中，key 的存儲順序就是它的寫入順序，并且對于同一個 key 后出現的 key 優先于之前的 key，因此日志中的 key 順序并不重要。這樣的好處是寫入很簡單，但沒有控制 key 重復帶來的問題是浪費了存儲空間，初始化加載的耗時會增加。

現在簡單地改變一下日志的寫入要求：要求寫入的 key 有序，并且同一個 key 在一個日志中只能出現一次。這種日志就叫做 SSTable，相比哈希索引的日志有以下優點：

1）合并多個日志文件更加簡單高效。

因為日志是有序的，所以可以用文件歸并排序算法，即并發讀取多個輸入文件，比較每個文件的第一個 key，按照順序拷貝到輸出文件。如果有重復的 key，那就只保留最新的日志中的 key 的值，老的丟棄。

2）查詢 key 時，不需要在內存中保存所有 key 的索引。

如下圖所示，假設需要查找 handiwork，且內存中沒有記錄該 key 的位置，但因為 SSTable 是有序的，所以我們可以知道 handiwork 如果存在一定是在 handbag 和 handsome 的中間，然后從 handbag 開始掃描日志一直到 handsome 結束。這樣的好處是有三個：

• 內存中只需要記錄稀疏索引，減少了內存索引的大小。

• 查詢操作不需要讀取整個日志，減少了文件 IO。

• 可以支持區間查詢。

二  構建和維護 SSTable

我們知道寫入時 key 會按照任意順序出現，那么如何保證 SSTable 中的 key 是有序的呢？一個簡單方便的方式就是先保存到內存的紅黑樹中，紅黑樹是有序的，然后再寫入到日志文件里面。

存儲引擎的基本工作流程如下：

• 當寫入時，先將其添加到內存的紅黑樹中，這個內存中的樹稱為內存表。

• 當內存表大于某個閾值時，將其作為 SSTable 文件寫入到磁盤，因為樹是有序的，所以寫磁盤的時候直接按順序寫入就行。

• 為了避免內存表未寫入文件時數據庫崩潰，可以在保存到內存表的同時將數據也寫入到另一個日志中（WAL），這樣即使數據庫崩潰也能從 WAL 中恢復。這個日志寫入就類似哈希索引的日志，不需要保證順序，因為是用來恢復數據的。

• 處理讀請求時，首先嘗試在內存表中查找 key，然后從新到舊依次查詢 SSTable 日志，直到找到數據或者為空。

• 后臺進程周期性地執行日志合并與壓縮過程，丟棄掉已經被覆蓋或刪除的值。

以上的算法就是 LSM-Tree（基于日志結構的合并樹 Log-Structured Merge-Tree） 的實現，基于合并和壓縮排序文件原理的存儲引擎通常就被稱為 LSM 存儲引擎，這也是 Hbase、LevelDB 等數據庫的底層原理。

三  實現一個基于 LSM 的數據庫

前面我們已經知道了 LSM-Tree 的實現算法，在具體實現的時候還有很多設計的問題需要考慮，下面我挑一些關鍵設計進行分析。

1  內存表存儲結構

內存表的 value 存儲什么？直接存儲原始數據嗎？還是存儲寫命令（包括 set 和 rm ）？這是我們面臨的第一個設計問題。這里我們先不做判斷，先看下一個問題。

內存表達到一定大小之后就要寫入到日志文件中持久化。這個過程如果直接禁寫處理起來就很簡單。但如果要保證內存表在寫入文件的同時，還能正常處理讀寫請求呢？

一個解決思路是：在持久化內存表 A 的同時，可以將當前的內存表指針切換到新的內存表實例 B，此時我們要保證切換之后 A 是只讀，只有 B 是可寫的，否則我們無法保證內存表 A 持久化的過程是原子操作。

• get 請求：先查詢 B，再查詢 A，最后查 SSTable。

• set 請求：直接寫入 A。

• rm 請求：假設 rm 的 key1 只在 A 里面出現了，B 里面沒有。這里如果內存表存儲的是原始數據，那么 rm 請求是沒法處理的，因為 A 是只讀的，會導致 rm 失敗。如果我們在內存表里面存儲的是命令的話，這個問題就是可解的，在 B 里面寫入 rm 命令，這樣查詢 key1 的時候在 B 里面就能查到 key1 已經被刪除了。

因此，假設我們持久化內存表時做禁寫，那么 value 是可以直接存儲原始數據的，但是如果我們希望持久化內存表時不禁寫，那么 value 值就必須要存儲命令。我們肯定是要追求高性能不禁寫的，所以 value 值需要保存的是命令， Hbase 也是這樣設計的，背后的原因也是這個。

另外，當內存表已經超過閾值要持久化的時候，發現前一次持久化還沒有做完，那么就需要等待前一次持久化完成才能進行本次持久化。換句話說，內存表持久化只能串行進行。

2  SSTable 的文件格式

為了實現高效的文件讀取，我們需要好好設計一下文件格式。

以下是我設計的 SSTable 日志格式：

• 數據區： 數據區 主要是存儲寫入的命令，同時為了方便分段讀取，是按照一定的數量大小分段的。

• 稀疏索引區： 稀疏索引保存的是數據段每一段在文件中的位置索引，讀取 SSTable 時候只會加載稀疏索引到內存，查詢的時候根據稀疏索引加載對應數據段進行查詢。

• 文件索引區： 存 儲數據區域的位置。

以上的日志格式是迷你的實現，相比 Hbase 的日志格式是比較簡單的，這樣方便理解原理。同時我也使用了 JSON 格式寫入文件，目的是方便閱讀。而生產實現是效率優先的，為了節省存儲會做壓縮。

四  代碼實現分析

我寫的代碼實現在：TinyKvStore，下面分析一下關鍵的代碼。代碼比較多，也比較細碎，如果只關心原理的話可以跳過這部分，如果想了解代碼實現可以繼續往下讀。

1  SSTable

內存表持久化

內存表持久化到 SSTable 就是把內存表的數據按照前面我們提到的日志格式寫入到文件。對于 SSTable 來說，寫入的數據就是數據命令，包括 set 和 rm，只要我們能知道 key 的最新命令是什么，就能知道 key 在數據庫中的狀態。

/** 
 * 從內存表轉化為ssTable 
 * @param index 
 */ 
  private void initFromIndex(TreeMap<String, Command> index) { 
    try { 
        JSONObject partData = new JSONObject(true); 
        tableMetaInfo.setDataStart(tableFile.getFilePointer()); 
        for (Command command : index.values()) { 
            //處理set命令 
            if (command instanceof SetCommand) { 
                SetCommand set = (SetCommand) command; 
                partData.put(set.getKey(), set); 
            } 
            //處理RM命令 
            if (command instanceof RmCommand) { 
                RmCommand rm = (RmCommand) command; 
                partData.put(rm.getKey(), rm); 
             } 
 
 
            //達到分段數量，開始寫入數據段 
            if (partData.size() >= tableMetaInfo.getPartSize()) { 
                writeDataPart(partData); 
            } 
        } 
        //遍歷完之后如果有剩余的數據（尾部數據不一定達到分段條件）寫入文件 
        if (partData.size() > 0) { 
             writeDataPart(partData); 
        } 
        long dataPartLen = tableFile.getFilePointer() - tableMetaInfo.getDataStart(); 
        tableMetaInfo.setDataLen(dataPartLen); 
        //保存稀疏索引 
        byte[] indexBytes = JSONObject.toJSONString(sparseIndex).getBytes(StandardCharsets.UTF_8); 
        tableMetaInfo.setIndexStart(tableFile.getFilePointer()); 
        tableFile.write(indexBytes); 
        tableMetaInfo.setIndexLen(indexBytes.length); 
        LoggerUtil.debug(LOGGER, "[SsTable][initFromIndex][sparseIndex]: {}", sparseIndex); 
 
 
      //保存文件索引 
      tableMetaInfo.writeToFile(tableFile); 
      LoggerUtil.info(LOGGER, "[SsTable][initFromIndex]: {},{}", filePath, tableMetaInfo); 
 
 
    } catch (Throwable t) { 
         throw new RuntimeException(t); 
    } 
} 

寫入的格式是基于讀取倒推的，主要是為了方便讀取。例如 tableMetaInfo 寫入是從前往后寫的，那么讀取的時候就要從后往前讀。這也是為什么 version 要放到最后寫入，因為讀取的時候是第一個讀取到的，方便對日志格式做升級。這些 trick 如果沒有動手嘗試，光看是很難理解為什么這么干的。

/** 
 * 把數據寫入到文件中 
* @param file 
*/ 
public void writeToFile(RandomAccessFile file) { 
    try { 
        file.writeLong(partSize); 
        file.writeLong(dataStart); 
        file.writeLong(dataLen); 
        file.writeLong(indexStart); 
        file.writeLong(indexLen); 
        file.writeLong(version); 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } 
} 
 
 
/** 
* 從文件中讀取元信息，按照寫入的順序倒著讀取出來 
* @param file 
* @return 
*/ 
public static TableMetaInfo readFromFile(RandomAccessFile file) { 
    try { 
        TableMetaInfo tableMetaInfo = new TableMetaInfo(); 
        long fileLen = file.length(); 
 
 
        file.seek(fileLen - 8); 
        tableMetaInfo.setVersion(file.readLong()); 
 
 
        file.seek(fileLen - 8 * 2); 
        tableMetaInfo.setIndexLen(file.readLong()); 
 
 
        file.seek(fileLen - 8 * 3); 
        tableMetaInfo.setIndexStart(file.readLong()); 
 
 
        file.seek(fileLen - 8 * 4); 
        tableMetaInfo.setDataLen(file.readLong()); 
 
 
        file.seek(fileLen - 8 * 5); 
        tableMetaInfo.setDataStart(file.readLong()); 
 
 
        file.seek(fileLen - 8 * 6); 
        tableMetaInfo.setPartSize(file.readLong()); 
 
 
        return tableMetaInfo; 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } 
} 

從文件中加載 SSTable

從文件中加載 SSTable 時只需要加載稀疏索引，這樣能節省內存。數據區等查詢的時候按需讀取就行。

/** 
     * 從文件中恢復ssTable到內存 
     */ 
    private void restoreFromFile() { 
        try { 
            //先讀取索引 
            TableMetaInfo tableMetaInfo = TableMetaInfo.readFromFile(tableFile); 
            LoggerUtil.debug(LOGGER, "[SsTable][restoreFromFile][tableMetaInfo]: {}", tableMetaInfo); 
            //讀取稀疏索引 
            byte[] indexBytes = new byte[(int) tableMetaInfo.getIndexLen()]; 
            tableFile.seek(tableMetaInfo.getIndexStart()); 
            tableFile.read(indexBytes); 
            String indexStr = new String(indexBytes, StandardCharsets.UTF_8); 
            LoggerUtil.debug(LOGGER, "[SsTable][restoreFromFile][indexStr]: {}", indexStr); 
            sparseIndex = JSONObject.parseObject(indexStr, 
                    new TypeReference<TreeMap<String, Position>>() { 
                    }); 
            this.tableMetaInfo = tableMetaInfo; 
            LoggerUtil.debug(LOGGER, "[SsTable][restoreFromFile][sparseIndex]: {}", sparseIndex); 
        } catch (Throwable t) { 
            throw new RuntimeException(t); 
        } 
    } 

SSTable 查詢

從 SSTable 查詢數據首先是要從稀疏索引中找到 key 所在的區間，找到區間之后根據索引記錄的位置讀取區間的數據，然后進行查詢，如果有數據就返回，沒有就返回 null。

/** 
 * 從ssTable中查詢數據 
 * @param key 
 * @return 
 */ 
public Command query(String key) { 
    try { 
        LinkedList<Position> sparseKeyPositionList = new LinkedList<>(); 
 
 
        Position lastSmallPosition = null; 
        Position firstBigPosition = null; 
 
 
        //從稀疏索引中找到最后一個小于key的位置，以及第一個大于key的位置 
        for (String k : sparseIndex.keySet()) { 
            if (k.compareTo(key) <= 0) { 
                lastSmallPosition = sparseIndex.get(k); 
            } else { 
                firstBigPosition = sparseIndex.get(k); 
                break; 
            } 
        } 
        if (lastSmallPosition != null) { 
            sparseKeyPositionList.add(lastSmallPosition); 
        } 
        if (firstBigPosition != null) { 
            sparseKeyPositionList.add(firstBigPosition); 
        } 
        if (sparseKeyPositionList.size() == 0) { 
            return null; 
        } 
        LoggerUtil.debug(LOGGER, "[SsTable][restoreFromFile][sparseKeyPositionList]: {}", sparseKeyPositionList); 
        Position firstKeyPosition = sparseKeyPositionList.getFirst(); 
        Position lastKeyPosition = sparseKeyPositionList.getLast(); 
        long start = 0; 
        long len = 0; 
        start = firstKeyPosition.getStart(); 
        if (firstKeyPosition.equals(lastKeyPosition)) { 
            len = firstKeyPosition.getLen(); 
        } else { 
            len = lastKeyPosition.getStart() + lastKeyPosition.getLen() - start; 
        } 
        //key如果存在必定位于區間內，所以只需要讀取區間內的數據，減少io 
        byte[] dataPart = new byte[(int) len]; 
        tableFile.seek(start); 
        tableFile.read(dataPart); 
        int pStart = 0; 
        //讀取分區數據 
        for (Position position : sparseKeyPositionList) { 
            JSONObject dataPartJson = JSONObject.parseObject(new String(dataPart, pStart, (int) position.getLen())); 
            LoggerUtil.debug(LOGGER, "[SsTable][restoreFromFile][dataPartJson]: {}", dataPartJson); 
            if (dataPartJson.containsKey(key)) { 
                JSONObject value = dataPartJson.getJSONObject(key); 
                return ConvertUtil.jsonToCommand(value); 
            } 
            pStart += (int) position.getLen(); 
        } 
        return null; 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } 
} 

2  LsmKvStore

初始化加載

• dataDir：數據目錄存儲了日志數據，所以啟動的時候需要從目錄中讀取之前的持久化數據。

• storeThreshold：持久化閾值，當內存表超過一定大小之后要進行持久化。

• partSize：SSTable 的數據分區閾值。

• indexLock：內存表的讀寫鎖。

• ssTables：SSTable 的有序列表，按照從新到舊排序。

• wal：順序寫入日志，用于保存內存表的數據，用作數據恢復。

啟動的過程很簡單，就是加載數據配置，初始化內容，如果需要做數據恢復就將數據恢復到內存表。

/** 
 * 初始化 
 * @param dataDir 數據目錄 
 * @param storeThreshold 持久化閾值 
 * @param partSize 數據分區大小 
*/ 
public LsmKvStore(String dataDir, int storeThreshold, int partSize) { 
    try { 
        this.dataDir = dataDir; 
        this.storeThreshold = storeThreshold; 
        this.partSize = partSize; 
        this.indexLock = new ReentrantReadWriteLock(); 
        File dir = new File(dataDir); 
        File[] files = dir.listFiles(); 
        ssTables = new LinkedList<>(); 
        index = new TreeMap<>(); 
        //目錄為空無需加載ssTable 
        if (files == null || files.length == 0) { 
            walFile = new File(dataDir + WAL); 
            wal = new RandomAccessFile(walFile, RW_MODE); 
            return; 
        } 
 
 
        //從大到小加載ssTable 
        TreeMap<Long, SsTable> ssTableTreeMap = new TreeMap<>(Comparator.reverseOrder()); 
        for (File file : files) { 
            String fileName = file.getName(); 
            //從暫存的WAL中恢復數據，一般是持久化ssTable過程中異常才會留下walTmp 
            if (file.isFile() && fileName.equals(WAL_TMP)) { 
                restoreFromWal(new RandomAccessFile(file, RW_MODE)); 
            } 
            //加載ssTable 
            if (file.isFile() && fileName.endsWith(TABLE)) { 
                int dotIndex = fileName.indexOf("."); 
                Long time = Long.parseLong(fileName.substring(0, dotIndex)); 
                ssTableTreeMap.put(time, SsTable.createFromFile(file.getAbsolutePath())); 
            } else if (file.isFile() && fileName.equals(WAL)) { 
                //加載WAL 
                walFile = file; 
                wal = new RandomAccessFile(file, RW_MODE); 
                restoreFromWal(wal); 
            } 
        } 
        ssTables.addAll(ssTableTreeMap.values()); 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } 
} 

寫入操作

寫入操作先加寫鎖，然后把數據保存到內存表以及 WAL 中，另外還要做判斷：如果超過閾值進行持久化。這里為了簡單起見我直接串行執行了，沒有使用線程池執行，但不影響整體邏輯。set 和 rm 的代碼是類似，這里就不重復了。

@Override 
public void set(String key, String value) { 
    try { 
        SetCommand command = new SetCommand(key, value); 
        byte[] commandBytes = JSONObject.toJSONBytes(command); 
        indexLock.writeLock().lock(); 
        //先保存數據到WAL中 
        wal.writeInt(commandBytes.length); 
        wal.write(commandBytes); 
        index.put(key, command); 
 
 
        //內存表大小超過閾值進行持久化 
        if (index.size() > storeThreshold) { 
            switchIndex(); 
            storeToSsTable(); 
        } 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } finally { 
        indexLock.writeLock().unlock(); 
    } 
} 

內存表持久化過程

切換內存表及其關聯的 WAL：先對內存表加鎖，然后新建一個內存表和 WAL，把老的內存表和 WAL 暫存起來，釋放鎖。這樣新的內存表就可以開始寫入，老的內存表變成只讀。

執行持久化過程：把老內存表有序寫入到一個新的 ssTable 中，然后刪除暫存內存表和臨時保存的 WAL。

/** 
  * 切換內存表，新建一個內存表，老的暫存起來 
  */ 
  private void switchIndex() { 
     try { 
         indexLock.writeLock().lock(); 
         //切換內存表 
         immutableIndex = index; 
         index = new TreeMap<>(); 
         wal.close(); 
         //切換內存表后也要切換WAL 
         File tmpWal = new File(dataDir + WAL_TMP); 
         if (tmpWal.exists()) { 
             if (!tmpWal.delete()) { 
                 throw new RuntimeException("刪除文件失敗: walTmp"); 
             } 
         } 
         if (!walFile.renameTo(tmpWal)) { 
             throw new RuntimeException("重命名文件失敗: walTmp"); 
         } 
         walFile = new File(dataDir + WAL); 
         wal = new RandomAccessFile(walFile, RW_MODE); 
     } catch (Throwable t) { 
         throw new RuntimeException(t); 
     } finally { 
         indexLock.writeLock().unlock(); 
     } 
 } 
 
 
/** 
 * 保存數據到ssTable 
 */ 
private void storeToSsTable() { 
    try { 
        //ssTable按照時間命名，這樣可以保證名稱遞增 
        SsTable ssTable = SsTable.createFromIndex(dataDir + System.currentTimeMillis() + TABLE, partSize, immutableIndex); 
        ssTables.addFirst(ssTable); 
        //持久化完成刪除暫存的內存表和WAL_TMP 
        immutableIndex = null; 
        File tmpWal = new File(dataDir + WAL_TMP); 
        if (tmpWal.exists()) { 
             if (!tmpWal.delete()) { 
                 throw new RuntimeException("刪除文件失敗: walTmp"); 
            } 
        } 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } 
 } 

查詢操作

查詢的操作就跟算法中描述的一樣：

• 先從內存表中取，如果取不到并且存在不可變內存表就從不可變內存表中取。

• 內存表中查詢不到就從新到舊的 SSTable 中依次查詢。

@Override 
public String get(String key) { 
    try { 
        indexLock.readLock().lock(); 
        //先從索引中取 
        Command command = index.get(key); 
        //再嘗試從不可變索引中取，此時可能處于持久化sstable的過程中 
        if (command == null && immutableIndex != null) { 
            command = immutableIndex.get(key); 
        } 
        if (command == null) { 
            //索引中沒有嘗試從ssTable中獲取，從新的ssTable找到老的 
            for (SsTable ssTable : ssTables) { 
                command = ssTable.query(key); 
                if (command != null) { 
                    break; 
                } 
            } 
        } 
        if (command instanceof SetCommand) { 
            return ((SetCommand) command).getValue(); 
        } 
        if (command instanceof RmCommand) { 
            return null; 
        } 
        //找不到說明不存在 
        return null; 
    } catch (Throwable t) { 
        throw new RuntimeException(t); 
    } finally { 
        indexLock.readLock().unlock(); 
    } 
} 

總結

知行合一，方得真知。如果我們不動手實現一個數據庫，就很難理解為什么這么設計。 例如日志格式為什么這樣設計，為什么數據庫保存的是數據操作而不是數據本身等等。

本文實現的數據庫功能比較簡單，有很多地方可以優化，例如數據持久化異步化，日志文件壓縮，查詢使用布隆過濾器先過濾一下。有興趣的讀者可以繼續深入研究。