关于数据库:从0开始500行代码实现-LSM-数据库

简介：LSM-Tree 是很多 NoSQL 数据库引擎的底层实现，例如 LevelDB，Hbase 等。本文基于《数据密集型利用零碎设计》中对 LSM-Tree 数据库的设计思路，联合代码实现残缺地论述了一个迷你数据库，外围代码 500 行左右，通过实践联合实际来更好地了解数据库的原理。

作者 | 萧恺
起源 | 阿里技术公众号

LSM-Tree 是很多 NoSQL 数据库引擎的底层实现，例如 LevelDB，Hbase 等。本文基于《数据密集型利用零碎设计》中对 LSM-Tree 数据库的设计思路，联合代码实现残缺地论述了一个迷你数据库，外围代码 500 行左右，通过实践联合实际来更好地了解数据库的原理。

之前基于哈希索引实现了一个数据库，它的局限性是哈希表须要整个放入到内存，并且区间查问效率不高。

在哈希索引数据库的日志中，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。
能够反对区间查问。

咱们晓得写入时 key 会依照任意程序呈现，那么如何保障 SSTable 中的 key 是有序的呢？一个简略不便的形式就是先保留到内存的红黑树中，红黑树是有序的，而后再写入到日志文件外面。

存储引擎的根本工作流程如下：

当写入时，先将其增加到内存的红黑树中，这个内存中的树称为内存表。
当内存表大于某个阈值时，将其作为 SSTable 文件写入到磁盘，因为树是有序的，所以写磁盘的时候间接按程序写入就行。
为了防止内存表未写入文件时数据库解体，能够在保留到内存表的同时将数据也写入到另一个日志中（WAL），这样即便数据库解体也能从 WAL 中复原。这个日志写入就相似哈希索引的日志，不须要保障程序，因为是用来复原数据的。
解决读申请时，首先尝试在内存表中查找 key，而后从新到旧顺次查问 SSTable 日志，直到找到数据或者为空。
后盾过程周期性地执行日志合并与压缩过程，抛弃掉曾经被笼罩或删除的值。

以上的算法就是 LSM-Tree（基于日志构造的合并树 Log-Structured Merge-Tree）的实现，基于合并和压缩排序文件原理的存储引擎通常就被称为 LSM 存储引擎，这也是 Hbase、LevelDB 等数据库的底层原理。

后面咱们曾经晓得了 LSM-Tree 的实现算法，在具体实现的时候还有很多设计的问题须要思考，上面我挑一些要害设计进行剖析。

内存表的 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 也是这样设计的，背地的起因也是这个。

另外，当内存表曾经超过阈值要长久化的时候，发现前一次长久化还没有做完，那么就须要期待前一次长久化实现能力进行本次长久化。换句话说，内存表长久化只能串行进行。

为了实现高效的文件读取，咱们须要好好设计一下文件格式。

以下是我设计的 SSTable 日志格局：

数据区：数据区次要是存储写入的命令，同时为了不便分段读取，是依照肯定的数量大小分段的。
稠密索引区：稠密索引保留的是数据段每一段在文件中的地位索引，读取 SSTable 时候只会加载稠密索引到内存，查问的时候依据稠密索引加载对应数据段进行查问。
文件索引区：存储数据区域的地位。

以上的日志格局是迷你的实现，相比 Hbase 的日志格局是比较简单的，这样不便了解原理。同时我也应用了 JSON 格局写入文件，目标是不便浏览。而生产实现是效率优先的，为了节俭存储会做压缩。

我写的代码实现在：TinyKvStore，上面剖析一下要害的代码。代码比拟多，也比拟细碎，如果只关怀原理的话能够跳过这部分，如果想理解代码实现能够持续往下读。

内存表长久化

内存表长久化到 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);
    }
}

初始化加载

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 的数据库

1 内存表存储构造

2 SSTable 的文件格式

四代码实现剖析

1 SSTable

2 LsmKvStore

总结

前言