乐趣区

关于数据库:从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 的值,老的抛弃。

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();}
}

总结

知行合一,方得真知。如果咱们不入手实现一个数据库,就很难了解为什么这么设计。例如日志格局为什么这样设计,为什么数据库保留的是数据操作而不是数据自身等等。

本文实现的数据库性能比较简单,有很多中央能够优化,例如数据长久化异步化,日志文件压缩,查问应用布隆过滤器先过滤一下。有趣味的读者能够持续深入研究。

参考资料
《数据密集型利用零碎设计》

原文链接
本文为阿里云原创内容,未经容许不得转载。

退出移动版