從0開始：500行代碼實現(xiàn) LSM 數(shù)據(jù)庫
前言
LSM-Tree 是很多 NoSQL 數(shù)據(jù)庫引擎的底層實現(xiàn)，例如 LevelDB，Hbase 等。本文基于《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計》中對 LSM-Tree 數(shù)據(jù)庫的設(shè)計思路，結(jié)合代碼實現(xiàn)完整地闡述了一個迷你數(shù)據(jù)庫，核心代碼 500 行左右，通過理論結(jié)合實踐來更好地理解數(shù)據(jù)庫的原理。
一 SSTable（排序字符串表）
之前基于哈希索引實現(xiàn)了一個數(shù)據(jù)庫，它的局限性是哈希表需要整個放入到內(nèi)存，并且區(qū)間查詢效率不高。
在哈希索引數(shù)據(jù)庫的日志中，key 的存儲順序就是它的寫入順序，并且對于同一個 key 后出現(xiàn)的 key 優(yōu)先于之前的 key，因此日志中的 key 順序并不重要。這樣的好處是寫入很簡單，但沒有控制 key 重復(fù)帶來的問題是浪費了存儲空間，初始化加載的耗時會增加。
現(xiàn)在簡單地改變一下日志的寫入要求：要求寫入的 key 有序，并且同一個 key 在一個日志中只能出現(xiàn)一次。這種日志就叫做 SSTable，相比哈希索引的日志有以下優(yōu)點：
1）合并多個日志文件更加簡單高效。
因為日志是有序的，所以可以用文件歸并排序算法，即并發(fā)讀取多個輸入文件，比較每個文件的第一個 key，按照順序拷貝到輸出文件。如果有重復(fù)的 key，那就只保留最新的日志中的 key 的值，老的丟棄。
2）查詢 key 時，不需要在內(nèi)存中保存所有 key 的索引。
如下圖所示，假設(shè)需要查找 handiwork，且內(nèi)存中沒有記錄該 key 的位置，但因為 SSTable 是有序的，所以我們可以知道 handiwork 如果存在一定是在 handbag 和 handsome 的中間，然后從 handbag 開始掃描日志一直到 handsome 結(jié)束。這樣的好處是有三個：
-
內(nèi)存中只需要記錄稀疏索引，減少了內(nèi)存索引的大小。
-
查詢操作不需要讀取整個日志，減少了文件 IO。
-
可以支持區(qū)間查詢。
二 構(gòu)建和維護 SSTable
我們知道寫入時 key 會按照任意順序出現(xiàn)，那么如何保證 SSTable 中的 key 是有序的呢？一個簡單方便的方式就是先保存到內(nèi)存的紅黑樹中，紅黑樹是有序的，然后再寫入到日志文件里面。
存儲引擎的基本工作流程如下：
-
當(dāng)寫入時，先將其添加到內(nèi)存的紅黑樹中，這個內(nèi)存中的樹稱為內(nèi)存表。
-
當(dāng)內(nèi)存表大于某個閾值時，將其作為 SSTable 文件寫入到磁盤，因為樹是有序的，所以寫磁盤的時候直接按順序?qū)懭刖托小?/p>
-
為了避免內(nèi)存表未寫入文件時數(shù)據(jù)庫崩潰，可以在保存到內(nèi)存表的同時將數(shù)據(jù)也寫入到另一個日志中（WAL），這樣即使數(shù)據(jù)庫崩潰也能從 WAL 中恢復(fù)。這個日志寫入就類似哈希索引的日志，不需要保證順序，因為是用來恢復(fù)數(shù)據(jù)的。
-
處理讀請求時，首先嘗試在內(nèi)存表中查找 key，然后從新到舊依次查詢 SSTable 日志，直到找到數(shù)據(jù)或者為空。
-
后臺進程周期性地執(zhí)行日志合并與壓縮過程，丟棄掉已經(jīng)被覆蓋或刪除的值。
以上的算法就是 LSM-Tree（基于日志結(jié)構(gòu)的合并樹 Log-Structured Merge-Tree） 的實現(xiàn)，基于合并和壓縮排序文件原理的存儲引擎通常就被稱為 LSM 存儲引擎，這也是 Hbase、LevelDB 等數(shù)據(jù)庫的底層原理。
三 實現(xiàn)一個基于 LSM 的數(shù)據(jù)庫
前面我們已經(jīng)知道了 LSM-Tree 的實現(xiàn)算法，在具體實現(xiàn)的時候還有很多設(shè)計的問題需要考慮，下面我挑一些關(guān)鍵設(shè)計進行分析。
1 內(nèi)存表存儲結(jié)構(gòu)
內(nèi)存表的 value 存儲什么？直接存儲原始數(shù)據(jù)嗎？還是存儲寫命令（包括 set 和 rm ）？這是我們面臨的第一個設(shè)計問題。這里我們先不做判斷，先看下一個問題。
內(nèi)存表達到一定大小之后就要寫入到日志文件中持久化。這個過程如果直接禁寫處理起來就很簡單。但如果要保證內(nèi)存表在寫入文件的同時，還能正常處理讀寫請求呢？
一個解決思路是：在持久化內(nèi)存表 A 的同時，可以將當(dāng)前的內(nèi)存表指針切換到新的內(nèi)存表實例 B，此時我們要保證切換之后 A 是只讀，只有 B 是可寫的，否則我們無法保證內(nèi)存表 A 持久化的過程是原子操作。
-
get 請求：先查詢 B，再查詢 A，最后查 SSTable。
-
set 請求：直接寫入 A。
-
rm 請求：假設(shè) rm 的 key1 只在 A 里面出現(xiàn)了，B 里面沒有。這里如果內(nèi)存表存儲的是原始數(shù)據(jù)，那么 rm 請求是沒法處理的，因為 A 是只讀的，會導(dǎo)致 rm 失敗。如果我們在內(nèi)存表里面存儲的是命令的話，這個問題就是可解的，在 B 里面寫入 rm 命令，這樣查詢 key1 的時候在 B 里面就能查到 key1 已經(jīng)被刪除了。
因此，假設(shè)我們持久化內(nèi)存表時做禁寫，那么 value 是可以直接存儲原始數(shù)據(jù)的，但是如果我們希望持久化內(nèi)存表時不禁寫，那么 value 值就必須要存儲命令。我們肯定是要追求高性能不禁寫的，所以 value 值需要保存的是命令， Hbase 也是這樣設(shè)計的，背后的原因也是這個。
另外，當(dāng)內(nèi)存表已經(jīng)超過閾值要持久化的時候，發(fā)現(xiàn)前一次持久化還沒有做完，那么就需要等待前一次持久化完成才能進行本次持久化。換句話說，內(nèi)存表持久化只能串行進行。
2 SSTable 的文件格式
為了實現(xiàn)高效的文件讀取，我們需要好好設(shè)計一下文件格式。
以下是我設(shè)計的 SSTable 日志格式：
-
數(shù)據(jù)區(qū)： 數(shù)據(jù)區(qū) 主要是存儲寫入的命令，同時為了方便分段讀取，是按照一定的數(shù)量大小分段的。
-
稀疏索引區(qū)： 稀疏索引保存的是數(shù)據(jù)段每一段在文件中的位置索引，讀取 SSTable 時候只會加載稀疏索引到內(nèi)存，查詢的時候根據(jù)稀疏索引加載對應(yīng)數(shù)據(jù)段進行查詢。
-
文件索引區(qū)： 存 儲數(shù)據(jù)區(qū)域的位置。
以上的日志格式是迷你的實現(xiàn)，相比 Hbase 的日志格式是比較簡單的，這樣方便理解原理。同時我也使用了 JSON 格式寫入文件，目的是方便閱讀。而生產(chǎn)實現(xiàn)是效率優(yōu)先的，為了節(jié)省存儲會做壓縮。
四 代碼實現(xiàn)分析
我寫的代碼實現(xiàn)在：TinyKvStore，下面分析一下關(guān)鍵的代碼。代碼比較多，也比較細碎，如果只關(guān)心原理的話可以跳過這部分，如果想了解代碼實現(xiàn)可以繼續(xù)往下讀。
1 SSTable
內(nèi)存表持久化
內(nèi)存表持久化到 SSTable 就是把內(nèi)存表的數(shù)據(jù)按照前面我們提到的日志格式寫入到文件。對于 SSTable 來說，寫入的數(shù)據(jù)就是數(shù)據(jù)命令，包括 set 和 rm，只要我們能知道 key 的最新命令是什么，就能知道 key 在數(shù)據(jù)庫中的狀態(tài)。
- /**
- * 從內(nèi)存表轉(zhuǎn)化為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);
- }
- //達到分段數(shù)量，開始寫入數(shù)據(jù)段
- if (partData.size() >= tableMetaInfo.getPartSize()) {
- writeDataPart(partData);
- }
- }
- //遍歷完之后如果有剩余的數(shù)據(jù)（尾部數(shù)據(jù)不一定達到分段條件）寫入文件
- 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 如果沒有動手嘗試，光看是很難理解為什么這么干的。
- /**
- * 把數(shù)據(jù)寫入到文件中
- * @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 時只需要加載稀疏索引，這樣能節(jié)省內(nèi)存。數(shù)據(jù)區(qū)等查詢的時候按需讀取就行。
- /**
- * 從文件中恢復(fù)ssTable到內(nèi)存
- */
- 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 查詢數(shù)據(jù)首先是要從稀疏索引中找到 key 所在的區(qū)間，找到區(qū)間之后根據(jù)索引記錄的位置讀取區(qū)間的數(shù)據(jù)，然后進行查詢，如果有數(shù)據(jù)就返回，沒有就返回 null。
- /**
- * 從ssTable中查詢數(shù)據(jù)
- * @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如果存在必定位于區(qū)間內(nèi)，所以只需要讀取區(qū)間內(nèi)的數(shù)據(jù)，減少io
- byte[] dataPart = new byte[(int) len];
- tableFile.seek(start);
- tableFile.read(dataPart);
- int pStart = 0;
- //讀取分區(qū)數(shù)據(jù)
- 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：數(shù)據(jù)目錄存儲了日志數(shù)據(jù)，所以啟動的時候需要從目錄中讀取之前的持久化數(shù)據(jù)。
-
storeThreshold：持久化閾值，當(dāng)內(nèi)存表超過一定大小之后要進行持久化。
-
partSize：SSTable 的數(shù)據(jù)分區(qū)閾值。
-
indexLock：內(nèi)存表的讀寫鎖。
-
ssTables：SSTable 的有序列表，按照從新到舊排序。
-
wal：順序?qū)懭肴罩?，用于保存?nèi)存表的數(shù)據(jù)，用作數(shù)據(jù)恢復(fù)。
啟動的過程很簡單，就是加載數(shù)據(jù)配置，初始化內(nèi)容，如果需要做數(shù)據(jù)恢復(fù)就將數(shù)據(jù)恢復(fù)到內(nèi)存表。
- /**
- * 初始化
- * @param dataDir 數(shù)據(jù)目錄
- * @param storeThreshold 持久化閾值
- * @param partSize 數(shù)據(jù)分區(qū)大小
- */
- 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中恢復(fù)數(shù)據(jù)，一般是持久化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);
- }
- }
寫入操作
寫入操作先加寫鎖，然后把數(shù)據(jù)保存到內(nèi)存表以及 WAL 中，另外還要做判斷：如果超過閾值進行持久化。這里為了簡單起見我直接串行執(zhí)行了，沒有使用線程池執(zhí)行，但不影響整體邏輯。set 和 rm 的代碼是類似，這里就不重復(fù)了。
- @Override
- public void set(String key, String value) {
- try {
- SetCommand command = new SetCommand(key, value);
- byte[] commandBytes = JSONObject.toJSONBytes(command);
- indexLock.writeLock().lock();
- //先保存數(shù)據(jù)到WAL中
- wal.writeInt(commandBytes.length);
- wal.write(commandBytes);
- index.put(key, command);
- //內(nèi)存表大小超過閾值進行持久化
- if (index.size() > storeThreshold) {
- switchIndex();
- storeToSsTable();
- }
- } catch (Throwable t) {
- throw new RuntimeException(t);
- } finally {
- indexLock.writeLock().unlock();
- }
- }
內(nèi)存表持久化過程
切換內(nèi)存表及其關(guān)聯(lián)的 WAL：先對內(nèi)存表加鎖，然后新建一個內(nèi)存表和 WAL，把老的內(nèi)存表和 WAL 暫存起來，釋放鎖。這樣新的內(nèi)存表就可以開始寫入，老的內(nèi)存表變成只讀。
執(zhí)行持久化過程：把老內(nèi)存表有序?qū)懭氲揭粋€新的 ssTable 中，然后刪除暫存內(nèi)存表和臨時保存的 WAL。
- /**
- * 切換內(nèi)存表，新建一個內(nèi)存表，老的暫存起來
- */
- private void switchIndex() {
- try {
- indexLock.writeLock().lock();
- //切換內(nèi)存表
- immutableIndex = index;
- index = new TreeMap<>();
- wal.close();
- //切換內(nèi)存表后也要切換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();
- }
- }
- /**
- * 保存數(shù)據(jù)到ssTable
- */
- private void storeToSsTable() {
- try {
- //ssTable按照時間命名，這樣可以保證名稱遞增
- SsTable ssTable = SsTable.createFromIndex(dataDir + System.currentTimeMillis() + TABLE, partSize, immutableIndex);
- ssTables.addFirst(ssTable);
- //持久化完成刪除暫存的內(nèi)存表和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);
- }
- }
查詢操作
查詢的操作就跟算法中描述的一樣：
-
先從內(nèi)存表中取，如果取不到并且存在不可變內(nèi)存表就從不可變內(nèi)存表中取。
-
內(nèi)存表中查詢不到就從新到舊的 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();
- }
- }
總結(jié)
知行合一，方得真知。如果我們不動手實現(xiàn)一個數(shù)據(jù)庫，就很難理解為什么這么設(shè)計。 例如日志格式為什么這樣設(shè)計，為什么數(shù)據(jù)庫保存的是數(shù)據(jù)操作而不是數(shù)據(jù)本身等等。
本文實現(xiàn)的數(shù)據(jù)庫功能比較簡單，有很多地方可以優(yōu)化，例如數(shù)據(jù)持久化異步化，日志文件壓縮，查詢使用布隆過濾器先過濾一下。有興趣的讀者可以繼續(xù)深入研究。
