簡介：?LSM-Tree 是很多 NoSQL 數(shù)據(jù)庫引擎的底層實(shí)現(xiàn)，例如 LevelDB，Hbase 等。本文基于《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計》中對 LSM-Tree 數(shù)據(jù)庫的設(shè)計思路，結(jié)合代碼實(shí)現(xiàn)完整地闡述了一個迷你數(shù)據(jù)庫，核心代碼 500 行左右，通過理論結(jié)合實(shí)踐來更好地理解數(shù)據(jù)庫的原理。

作者 | 蕭愷
來源 | 阿里技術(shù)公眾號

前言

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

一 SSTable（排序字符串表）

之前基于哈希索引實(shí)現(xiàn)了一個數(shù)據(jù)庫，它的局限性是哈希表需要整個放入到內(nèi)存，并且區(qū)間查詢效率不高。

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

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

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

因?yàn)槿罩臼怯行虻?#xff0c;所以可以用文件歸并排序算法，即并發(fā)讀取多個輸入文件，比較每個文件的第一個 key，按照順序拷貝到輸出文件。如果有重復(fù)的 key，那就只保留最新的日志中的 key 的值，老的丟棄。

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

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

• 內(nèi)存中只需要記錄稀疏索引，減少了內(nèi)存索引的大小。
• 查詢操作不需要讀取整個日志，減少了文件 IO。
• 可以支持區(qū)間查詢。

二 構(gòu)建和維護(hù) SSTable

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

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

• 當(dāng)寫入時，先將其添加到內(nèi)存的紅黑樹中，這個內(nèi)存中的樹稱為內(nèi)存表。

• 當(dāng)內(nèi)存表大于某個閾值時，將其作為 SSTable 文件寫入到磁盤，因?yàn)闃涫怯行虻?#xff0c;所以寫磁盤的時候直接按順序?qū)懭刖托小?/p>

  • 為了避免內(nèi)存表未寫入文件時數(shù)據(jù)庫崩潰，可以在保存到內(nèi)存表的同時將數(shù)據(jù)也寫入到另一個日志中（WAL），這樣即使數(shù)據(jù)庫崩潰也能從 WAL 中恢復(fù)。這個日志寫入就類似哈希索引的日志，不需要保證順序，因?yàn)槭怯脕砘謴?fù)數(shù)據(jù)的。
• 處理讀請求時，首先嘗試在內(nèi)存表中查找 key，然后從新到舊依次查詢 SSTable 日志，直到找到數(shù)據(jù)或者為空。
• 后臺進(jìn)程周期性地執(zhí)行日志合并與壓縮過程，丟棄掉已經(jīng)被覆蓋或刪除的值。

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

三 實(shí)現(xiàn)一個基于 LSM 的數(shù)據(jù)庫

前面我們已經(jīng)知道了 LSM-Tree 的實(shí)現(xiàn)算法，在具體實(shí)現(xiàn)的時候還有很多設(shè)計的問題需要考慮，下面我挑一些關(guān)鍵設(shè)計進(jìn)行分析。

1 內(nèi)存表存儲結(jié)構(gòu)

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

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

一個解決思路是：在持久化內(nèi)存表 A 的同時，可以將當(dāng)前的內(nèi)存表指針切換到新的內(nèi)存表實(shí)例 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 請求是沒法處理的，因?yàn)?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)前一次持久化還沒有做完，那么就需要等待前一次持久化完成才能進(jìn)行本次持久化。換句話說，內(nèi)存表持久化只能串行進(jìn)行。

2 SSTable 的文件格式

為了實(shí)現(xiàn)高效的文件讀取，我們需要好好設(shè)計一下文件格式。

以下是我設(shè)計的 SSTable 日志格式：

• 數(shù)據(jù)區(qū)：數(shù)據(jù)區(qū)主要是存儲寫入的命令，同時為了方便分段讀取，是按照一定的數(shù)量大小分段的。
• 稀疏索引區(qū)：稀疏索引保存的是數(shù)據(jù)段每一段在文件中的位置索引，讀取 SSTable 時候只會加載稀疏索引到內(nèi)存，查詢的時候根據(jù)稀疏索引加載對應(yīng)數(shù)據(jù)段進(jìn)行查詢。
• 文件索引區(qū)：存儲數(shù)據(jù)區(qū)域的位置。

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

四 代碼實(shí)現(xiàn)分析

我寫的代碼實(shí)現(xiàn)在：TinyKvStore，下面分析一下關(guān)鍵的代碼。代碼比較多，也比較細(xì)碎，如果只關(guān)心原理的話可以跳過這部分，如果想了解代碼實(shí)現(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);}//達(dá)到分段數(shù)量，開始寫入數(shù)據(jù)段if (partData.size() >= tableMetaInfo.getPartSize()) {writeDataPart(partData);}}//遍歷完之后如果有剩余的數(shù)據(jù)（尾部數(shù)據(jù)不一定達(dá)到分段條件）寫入文件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 要放到最后寫入，因?yàn)樽x取的時候是第一個讀取到的，方便對日志格式做升級。這些 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ù)，然后進(jìn)行查詢，如果有數(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ù)，減少iobyte[] 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)存表超過一定大小之后要進(jìn)行持久化。
• partSize：SSTable 的數(shù)據(jù)分區(qū)閾值。
• indexLock：內(nèi)存表的讀寫鎖。
• ssTables：SSTable 的有序列表，按照從新到舊排序。
• wal：順序?qū)懭肴罩?#xff0c;用于保存內(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<>();//目錄為空無需加載ssTableif (files == null || files.length == 0) {walFile = new File(dataDir + WAL);wal = new RandomAccessFile(walFile, RW_MODE);return;}//從大到小加載ssTableTreeMap< Long, SsTable> ssTableTreeMap = new TreeMap<>(Comparator.reverseOrder());for (File file : files) {String fileName = file.getName();//從暫存的WAL中恢復(fù)數(shù)據(jù)，一般是持久化ssTable過程中異常才會留下walTmpif (file.isFile() && fileName.equals(WAL_TMP)) {restoreFromWal(new RandomAccessFile(file, RW_MODE));}//加載ssTableif (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)) {//加載WALwalFile = 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 中，另外還要做判斷：如果超過閾值進(jìn)行持久化。這里為了簡單起見我直接串行執(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)存表大小超過閾值進(jìn)行持久化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)存表后也要切換WALFile 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_TMPimmutableIndex = 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é)

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

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

參考資料
《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計》

原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的从0开始：500行代码实现 LSM 数据库的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。