從0開始：500行代碼實作 LSM 資料庫

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

作者 | 蕭恺

來源 | 阿裡技術公衆号

前言

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

一 SSTable（排序字元串表）

之前基于哈希索引實作了一個資料庫，它的局限性是哈希表需要整個放入到記憶體，并且區間查詢效率不高。

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

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

1）合并多個日志檔案更加簡單高效。

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

從0開始：500行代碼實作 LSM 資料庫

2）查詢 key 時，不需要在記憶體中儲存所有 key 的索引。

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

記憶體中隻需要記錄稀疏索引，減少了記憶體索引的大小。
查詢操作不需要讀取整個日志，減少了檔案 IO。
可以支援區間查詢。

從0開始：500行代碼實作 LSM 資料庫

二建構和維護 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 日志格式：

從0開始：500行代碼實作 LSM 資料庫

資料區：資料區主要是存儲寫入的指令，同時為了友善分段讀取，是按照一定的數量大小分段的。
稀疏索引區：稀疏索引儲存的是資料段每一段在檔案中的位置索引，讀取 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();
    }
}

總結

知行合一，方得真知。如果我們不動手實作一個資料庫，就很難了解為什麼這麼設計。例如日志格式為什麼這樣設計，為什麼資料庫儲存的是資料操作而不是資料本身等等。

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

參考資料

《資料密集型應用系統設計》

原文連結

本文為阿裡雲原創内容，未經允許不得轉載。

從0開始：500行代碼實作 LSM 資料庫

前言

一 SSTable（排序字元串表）

二建構和維護 SSTable

三實作一個基于 LSM 的資料庫

四代碼實作分析

總結

繼續閱讀

Testlink安裝部署之XAMPP

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述

從0開始：500行代碼實作 LSM 資料庫

前言

一 SSTable（排序字元串表）

二 建構和維護 SSTable

三 實作一個基于 LSM 的資料庫

四 代碼實作分析

總結

繼續閱讀

二建構和維護 SSTable

三實作一個基于 LSM 的資料庫

四代碼實作分析