Build a Simple Database

Writing a simple database from scratch with Node.js!

View on GitHub

索引和二进制格式存储

接下来我们就开始实现一个最简单的保存在内存内的哈希索引，这在 Node 环境中非常简单，只需要用一个 Map 就能实现了。但这个 Map 内的值存什么还需要多考虑一点。我们需要先设计好如何以二进制格式来存储我们的数据。

TIP

Node.js 提供了三种风格的接口，分别是异步调用返回一个 promise，同步调用，以及传入回调函数的 callback 形式，为了方便，只要有同步调用的我们都统一采用同步调用的方式。

对于写入，我们还是使用之前的 fs.appendFileSync 接口，除了字符串数据以外，它也支持传入一个 buffer。而读取的话，我们需要使用到 fs.readSync 接口，它的签名是下面这样的，你可以在指定的位置，读取指定 length 长度的数据块，将其复制到你所传入的 buffer 对象中，同时可以指定从 buffer 对象 offset 的偏移量位置开始写入：

export function readSync(
  fd: number,
  buffer: NodeJS.ArrayBufferView,
  offset: number,
  length: number,
  position: ReadPosition | null
): number;

export function readSync(
  fd: number,
  buffer: NodeJS.ArrayBufferView,
  offset: number,
  length: number,
  position: ReadPosition | null
): number;

对于其中的 fd，我们可以通过 fs.openSync 来获取文件的描述符。

这意味着在读取数据时我们不光要知道从那个地方开始读，最好还能知道读取多大的数据块出来，那么为了方便，我们写入前就干脆也把需要写入的大小也记录到索引里面：

type Offset = number;
type Size = number; // how many bytes
type Index = [Offset, Size];

type Offset = number;
type Size = number; // how many bytes
type Index = [Offset, Size];

同时，这次我们也提供对数据类型的支持，对于提交过来的不同的数据类型，我们针对性的将其转换成二进制格式，为了简单一点，这里我们只支持三种类型，分别是数字，布尔值和字符串：

const enum DataType {
  Boolean,
  Number,
  String,
}

const enum DataType {
  Boolean,
  Number,
  String,
}

这里使用到了 const enum，他们在编译后会被完全抹去，三种类型分别会用 0，1，2 代替：

// before
const a = DataType.Boolean;

// after
const a = 0; /* Boolean */

// before
const a = DataType.Boolean;

// after
const a = 0; /* Boolean */

然后我们可以针对这三个类型编写一个序列化的函数，同时，为了在读取时针对性的进行反序列化，我们还需要将它的类型信息也存进去，规则是下面这样的：

  • 每一个数据都用第一个字节来存储它的类型信息，0，1，2 分别对应布尔值，数字和字符串；
  • 布尔值，用一个字节来表示（主要是 Node 最少得分配一个字节），1 为 true，0 为 false；
  • 数字，因为 Node 中的普通数字实际上都是双精度浮点数，我们就将其都作为 double 处理，占用 8 个字节（64 位），对于可能溢出的大数字先不管；
  • 除了布尔和数字，其他都当做字符串处理，采用 UTF-8 编码。
const serialize = (val: boolean | number | string): Buffer => {
  let buf: Buffer;
  let type: Buffer;
  let data: Buffer;

  switch (typeof val) {
    case 'boolean': {
      type = Buffer.alloc(1, DataType.Boolean);
      data = Buffer.alloc(1, val ? 1 : 0);
      break;
    }
    case 'number': {
      type = Buffer.alloc(1, DataType.Number);
      data = Buffer.allocUnsafe(8);
      data.writeDoubleBE(val);
      break;
    }
    case 'string': {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
      break;
    }
    default: {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
    }
  }

  buf = Buffer.concat([type, data]);
  return buf;
};

const serialize = (val: boolean | number | string): Buffer => {
  let buf: Buffer;
  let type: Buffer;
  let data: Buffer;

  switch (typeof val) {
    case 'boolean': {
      type = Buffer.alloc(1, DataType.Boolean);
      data = Buffer.alloc(1, val ? 1 : 0);
      break;
    }
    case 'number': {
      type = Buffer.alloc(1, DataType.Number);
      data = Buffer.allocUnsafe(8);
      data.writeDoubleBE(val);
      break;
    }
    case 'string': {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
      break;
    }
    default: {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
    }
  }

  buf = Buffer.concat([type, data]);
  return buf;
};

注意数字的部分用到了 buffer.writeDoubleBE，BE 的意思是 Big-Endian，中文叫大端序，还有一种叫小端序，对于字节序这里不赘述，可以自行搜索。具体使用什么样的字节序这里没什么讲究，但最重要的是在序列化和反序列化的时候一定要使用相同的字节序，这里我们默认全部使用大端序。

这样呢反序列化也很简单：

const deserialize = (buf: Buffer): boolean | number | string => {
  const type = buf[0];

  switch (type) {
    case DataType.Boolean: {
      return buf[1] === 1;
    }
    case DataType.Number: {
      return buf.readDoubleBE(1);
    }
    case DataType.String: {
      return buf.slice(1).toString();
    }
    default:
      return buf.slice(1).toString();
  }
};

const deserialize = (buf: Buffer): boolean | number | string => {
  const type = buf[0];

  switch (type) {
    case DataType.Boolean: {
      return buf[1] === 1;
    }
    case DataType.Number: {
      return buf.readDoubleBE(1);
    }
    case DataType.String: {
      return buf.slice(1).toString();
    }
    default:
      return buf.slice(1).toString();
  }
};

这样整体的思路就确定了：

  • 启动时先获取数据库文件 fd，开启 repl 环境；
  • 对于 set 命令把 key/value 交给 set 函数，进行序列化，先更新索引，再写入文件；
  • 对于 get 命令解析出 key，交给 get 函数，先从索引中查找，如果有的话根据偏移位置和数据大小，然后直接读取出来并进行反序列化然后返回。

我们据此可以重构一下之前的 get 和 set 函数：

const get = (key: string) => {
  const index = map.get(key);

  if (index) {
    const [offset, size] = index;
    const buffer = Buffer.alloc(size);
    fs.readSync(fd, buffer, 0, size, offset);
    return deserialize(buffer);
  }

  return null;
};

const set = (key: string, value: string) => {
  let buffer: Buffer;
  if (value === 'true' || value === 'false') {
    // boolean
    buffer = serialize(JSON.parse(value));
  } else if (/^-?\d+$/.test(value)) {
    // number
    buffer = serialize(parseFloat(value));
  } else {
    buffer = serialize(value);
  }

  const size = buffer.byteLength;
  const offset = fs.statSync(dbFile).size;
  map.set(key, [offset, size]);
  fs.appendFileSync(dbFile, buffer);
};

const get = (key: string) => {
  const index = map.get(key);

  if (index) {
    const [offset, size] = index;
    const buffer = Buffer.alloc(size);
    fs.readSync(fd, buffer, 0, size, offset);
    return deserialize(buffer);
  }

  return null;
};

const set = (key: string, value: string) => {
  let buffer: Buffer;
  if (value === 'true' || value === 'false') {
    // boolean
    buffer = serialize(JSON.parse(value));
  } else if (/^-?\d+$/.test(value)) {
    // number
    buffer = serialize(parseFloat(value));
  } else {
    buffer = serialize(value);
  }

  const size = buffer.byteLength;
  const offset = fs.statSync(dbFile).size;
  map.set(key, [offset, size]);
  fs.appendFileSync(dbFile, buffer);
};

可以使用 ts-node db.ts 来直接启动并进行测试。

问题

目前来看这个简单的方案似乎还是可行的，现实中某些数据库其实也是这么做的，但要求所有的键必须都可以放入内存中，而数据值可以使用比可用内存更多的空间，因为可以在硬盘上通过一次硬盘查找操作来加载所需的部分。我们甚至还可以加入缓存功能，对于同一个 key 被反复读取的话将其缓存在内存里，这样下一次请求过来就可以从缓存中查找到并返回，就完全不需要再来一次磁盘 I/O 了。但它还存在几个问题：

  • 如果有海量多的键，那就很麻烦了。虽然可以在硬盘上维护一个映射，但很可惜硬盘上的映射很难表现优秀。它需要大量的随机访问 I/O，并且哈希冲突的处理也需要很烦琐的逻辑；
  • 范围查询效率很低，只能一个一个单独查找每一个键；
  • 内存中的映射会在进程退出时丢失，或许可以在退出时先写入到硬盘，下次启动时再恢复，不过总之服务的重启可能比较痛苦；
  • 每次 append 虽然快，但是会造成很多的存储空间浪费，尤其是在一个键多次写入的时候，我们或许可以用新值覆盖旧值？实际上追加属于顺序写入操作，通常会比随机写入快得多，另外我们还可以通过合并压缩等方案来优化存储，但这个问题我们以后再细说；
  • 因为存储的数据大小是未知的，我们在索引中还需要维护这个数据，总感觉不太优雅，应该还有更好的解决方案。

之后我们就讲一讲怎么一步步解决上面这些问题的。

最后附上完整的代码：

点击展开 
import repl from 'repl';
import fs from 'fs';

const dbFile = './data.db';

const map = new Map<string, Index>();
const fd = fs.openSync(dbFile, 'a+'); // `a+` flag means open file for reading and appending.

type Offset = number;
type Size = number; // how many bytes
type Index = [Offset, Size];

const enum DataType {
  Boolean,
  Number,
  String,
}

const get = (key: string) => {
  const index = map.get(key);

  if (index) {
    const [offset, size] = index;
    const buffer = Buffer.alloc(size);
    fs.readSync(fd, buffer, 0, size, offset);
    return deserialize(buffer);
  }

  return null;
};

const set = (key: string, value: string) => {
  let buffer: Buffer;
  if (value === 'true' || value === 'false') {
    // boolean
    buffer = serialize(JSON.parse(value));
  } else if (/^-?\d+$/.test(value)) {
    // number
    buffer = serialize(parseFloat(value));
  } else {
    buffer = serialize(value);
  }

  const size = buffer.byteLength;
  const offset = fs.statSync(dbFile).size;
  map.set(key, [offset, size]);
  fs.appendFileSync(dbFile, buffer);
};

const deserialize = (buf: Buffer): boolean | number | string => {
  const type = buf[0];

  switch (type) {
    case DataType.Boolean: {
      return buf[1] === 1;
    }
    case DataType.Number: {
      return buf.readDoubleBE(1);
    }
    case DataType.String: {
      return buf.slice(1).toString();
    }
    default:
      return buf.slice(1).toString();
  }
};

const serialize = (val: boolean | number | string): Buffer => {
  let buf: Buffer;
  let type: Buffer;
  let data: Buffer;

  switch (typeof val) {
    case 'boolean': {
      type = Buffer.alloc(1, DataType.Boolean);
      data = Buffer.alloc(1, val ? 1 : 0);
      break;
    }
    case 'number': {
      type = Buffer.alloc(1, DataType.Number);
      data = Buffer.allocUnsafe(8);
      data.writeDoubleBE(val);
      break;
    }
    case 'string': {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
      break;
    }
    default: {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
    }
  }

  buf = Buffer.concat([type, data]);
  return buf;
};

repl.start({
  prompt: 'db.js >> ',
  eval: async (evalCmd, _, __, callback) => {
    const cmd = evalCmd.trim();
    if (cmd.startsWith('set')) {
      const [, key, value] = cmd.split(' ');
      set(key, value);
      return callback(null, value);
    }
    if (cmd.startsWith('get')) {
      const [, key] = cmd.split(' ');
      const value = get(key);
      return callback(null, value);
    }
    return callback(null, `Unrecognized command.`);
  },
});

import repl from 'repl';
import fs from 'fs';

const dbFile = './data.db';

const map = new Map<string, Index>();
const fd = fs.openSync(dbFile, 'a+'); // `a+` flag means open file for reading and appending.

type Offset = number;
type Size = number; // how many bytes
type Index = [Offset, Size];

const enum DataType {
  Boolean,
  Number,
  String,
}

const get = (key: string) => {
  const index = map.get(key);

  if (index) {
    const [offset, size] = index;
    const buffer = Buffer.alloc(size);
    fs.readSync(fd, buffer, 0, size, offset);
    return deserialize(buffer);
  }

  return null;
};

const set = (key: string, value: string) => {
  let buffer: Buffer;
  if (value === 'true' || value === 'false') {
    // boolean
    buffer = serialize(JSON.parse(value));
  } else if (/^-?\d+$/.test(value)) {
    // number
    buffer = serialize(parseFloat(value));
  } else {
    buffer = serialize(value);
  }

  const size = buffer.byteLength;
  const offset = fs.statSync(dbFile).size;
  map.set(key, [offset, size]);
  fs.appendFileSync(dbFile, buffer);
};

const deserialize = (buf: Buffer): boolean | number | string => {
  const type = buf[0];

  switch (type) {
    case DataType.Boolean: {
      return buf[1] === 1;
    }
    case DataType.Number: {
      return buf.readDoubleBE(1);
    }
    case DataType.String: {
      return buf.slice(1).toString();
    }
    default:
      return buf.slice(1).toString();
  }
};

const serialize = (val: boolean | number | string): Buffer => {
  let buf: Buffer;
  let type: Buffer;
  let data: Buffer;

  switch (typeof val) {
    case 'boolean': {
      type = Buffer.alloc(1, DataType.Boolean);
      data = Buffer.alloc(1, val ? 1 : 0);
      break;
    }
    case 'number': {
      type = Buffer.alloc(1, DataType.Number);
      data = Buffer.allocUnsafe(8);
      data.writeDoubleBE(val);
      break;
    }
    case 'string': {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
      break;
    }
    default: {
      type = Buffer.alloc(1, DataType.String);
      data = Buffer.from(val);
    }
  }

  buf = Buffer.concat([type, data]);
  return buf;
};

repl.start({
  prompt: 'db.js >> ',
  eval: async (evalCmd, _, __, callback) => {
    const cmd = evalCmd.trim();
    if (cmd.startsWith('set')) {
      const [, key, value] = cmd.split(' ');
      set(key, value);
      return callback(null, value);
    }
    if (cmd.startsWith('get')) {
      const [, key] = cmd.split(' ');
      const value = get(key);
      return callback(null, value);
    }
    return callback(null, `Unrecognized command.`);
  },
});