KV数据库一直让我着迷，我一直梦想着建立一个简单的、业余爱好的数据库来取乐。我读过几篇关于构建 redis、git、编译器和解释器的博文，但没有一篇是关于构建数据库的。这篇文章是对有关制作数据库并最终遇到Bitcask 论文的帖子进行了长期而危险的搜索的结果。

BitCask介绍

Bitcask是一种本地键/值存储，数据保存在文件中。一个操作系统进程将随时打开文件进行写入。当文件大小达到相当大的理论阈值时，我们关闭文件并打开一个新文件。

目标

每个项目的低延迟，读取或写入。
高吞吐量，尤其是在写入随机项目的传入流时。
处理数据集的能力比 RAM 没有降级更重要。
崩溃友好性，无论是在快速恢复还是在不丢失数据方面。
易于备份和恢复。
一种相对简单易懂的代码结构和数据格式。

数据格式

让我们开始分解它。

Key
Value

如果游标位于文件中数据的位置，您能否读取数据？

答案是不！

让我解释

由于键和值是可变长度的。我们需要弄清楚要阅读多少。所以我们需要存储键的大小和它的值。

现在我们已经在文件中写入了键和值的大小。给定一个指向数据位置的文件游标。我们知道前 8 个字节代表键和值的大小。一旦我们读取它，我们就会看到实际键的大小和要读取的值。

存储原始数据类型

虽然我们的 kv 数据库是 MVP-ready。假设我们要存储整数、浮点数和字符串等数据类型。一旦数据写入文件，数据类型就会丢失，所有内容都将被视为字符串，因为我们没有存储任何信息。

为了保留类型信息，让我们再存储两个字段，keytype和valuetype，代表存储的数据类型。

审计与安全

为了审计和安全，bitcask 建议分别存储 32 位纪元时间戳和CRC（循环冗余校验）。这些值是在数据写入文件时生成的。

最终的数据格式如下所示。我们将为每个键和值存储 20 个字节的附加数据。

第 4 个字节是一个 32 位整数，表示 CRC。
接下来的 4 个字节是一个 32 位整数，表示纪元时间戳。
接下来的 8 个字节是两个 32 位整数，分别代表keysize和valuesize。
接下来的 4 个字节是两个 16 位整数，分别表示keytype和valuetype。
剩下的字节是我们的键和值。

数据存储格式

计算机以二进制数字集表示数据。该表示包括分组为更广泛集合的位，例如字节。如果您注意到我们的数据格式，前 24 个字节是无符号整数。默认情况下，当将整数写入文件时，它们不会以二进制形式存储。

让我解释

假设我们运行下面的代码。写入文件的数据大小是多少？

File.open('sample.txt', 'w') do |file|
    [1, 12, 123, 1234, 12345, 123456, 1234567, 12345678].each do |num|
        file.write(num)
    end
end

它是36 个字节，因为默认情况下，它们被写为每个字符为 1 个字节的字符串。

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 字节

但这可能更有效率。在我们的数据格式中，我们讨论过对于任何键和值，我们将存储 20 个字节的元数据。所以我们不能将它们保留为字符串，因为它会导致可变长度字段。解决方案是对其进行编码并以二进制格式存储。

如果我们将它们编码为 4 字节整数并以二进制格式存储它们。文件的大小为32字节。

4 * 8 = 32 字节

最大键值大小

文件中存储的最大key或分别是或value的整数类型的函数。keysizevaluesize

因为我们的keysizeorvaluesize是 4 字节（32 位）无符号整数。我们可以存储的键或值的最大值是

整合

让我们创建一个Serializer封装序列化和反序列化逻辑的模块。我们需要将数据编码成二进制序列。Ruby 有Array.pack，它根据指令将数据打包成二进制序列。指令告知数据应如何以二进制序列编码。下面是我们将使用的指令列表。

L< : 32 位无符号整数，小端 (uint32_t)
S< : 16 位无符号整数，小端 (uint16_t)
q< : 64 位有符号整数，小端 (int64_t)
E ：双精度，小端

我们所有的指令都采用小端字节顺序。这没有任何性能优势。您也可以按大端顺序对它们进行编码。我们指定字节顺序以确保我们的数据库文件是跨平台兼容的。

module Bitcask
  module Serializer

    HEADER_FORMAT = 'L<L<L<S<S<'
    HEADER_SIZE = 16

    CRC32_FORMAT = 'L<'
    CRC32_SIZE = 4

    DATA_TYPE = {
      Integer: 1,
      Float: 2,
      String: 3
    }.freeze

    DATA_TYPE_LOOK_UP = {
      DATA_TYPE[:Integer] => :Integer,
      DATA_TYPE[:Float] => :Float,
      DATA_TYPE[:String] => :String
    }.freeze

    DATA_TYPE_DIRECTIVE = {
      DATA_TYPE[:Integer] => 'q<',
      DATA_TYPE[:Float] => 'E'
    }.freeze

  end
end

序列化和反序列化

serialize将数据序列化为我们的数据格式。它识别数据类型，生成标头并计算 crc。它返回数据的长度和二进制编码数据。
deserialize与相反serialize。它验证 crc，解码二进制编码数据并返回纪元、key和val。

module Bitcask
  module Serializer

    def serialize(epoch:, key:, value:)
      key_type = type(key)
      value_type = type(value)

      key_bytes = pack(key, key_type)
      value_bytes = pack(value, value_type)

      header = serialize_header(epoch: epoch, keysz: key_bytes.length, key_type: key_type, value_type: value_type,
                                valuesz: value_bytes.length)
      data = key_bytes + value_bytes

      [crc32_header_offset + data.length, crc32(header + data) + header + data]
    end

    def deserialize(data)
      return 0, '', '' unless crc32_valid?(desearlize_crc32(data[..crc32_offset - 1]), data[crc32_offset..])

      epoch, keysz, valuesz, key_type, value_type = deserialize_header(data[crc32_offset..crc32_header_offset - 1])
      key_bytes = data[crc32_header_offset..crc32_header_offset + keysz - 1]
      value_bytes = data[crc32_header_offset + keysz..]

      [epoch, unpack(key_bytes, key_type), unpack(value_bytes, value_type)]
    end

    def serialize_header(epoch:, key_type:, keysz:, value_type:, valuesz:)
      [epoch, keysz, valuesz, DATA_TYPE[key_type], DATA_TYPE[value_type]].pack(HEADER_FORMAT)
    end

    def deserialize_header(header_data)
      header = header_data.unpack(HEADER_FORMAT)

      [header[0], header[1], header[2], DATA_TYPE_LOOK_UP[header[3]], DATA_TYPE_LOOK_UP[header[4]]]
    end

  end
end

下面是一些用于打包、解包和生成 crc 的辅助函数。

module Bitcask
  module Serializer

    def crc32_offset
      CRC32_SIZE
    end

    def header_offset
      HEADER_SIZE
    end

    def crc32_header_offset
      crc32_offset + header_offset
    end

    def crc32(data_bytes)
      [Zlib.crc32(data_bytes)].pack(CRC32_FORMAT)
    end

    def desearlize_crc32(crc)
      crc.unpack1(CRC32_FORMAT)
    end

    def crc32_valid?(digest, data_bytes)
      digest == Zlib.crc32(data_bytes)
    end

    def pack(attribute, attribute_type)
      case attribute_type
      when :Integer, :Float
        [attribute].pack(directive(attribute_type))
      when :String
        attribute.encode('utf-8')
      else
        raise StandardError, 'Invalid attribute_type for pack'
      end
    end

    def unpack(attribute, attribute_type)
      case attribute_type
      when :Integer, :Float
        attribute.unpack1(directive(attribute_type))
      when :String
        attribute
      else
        raise StandardError, 'Invalid attribute_type for unpack'
      end
    end

    private

    def directive(attribute_type)
      DATA_TYPE_DIRECTIVE[DATA_TYPE[attribute_type]]
    end

    def type(attribute)
      attribute.class.to_s.to_sym
    end

  end
end

磁盘存储

最后，让我们创建一个名为的类DiskStore，我们的持久键值存储。它有以下方法。

Get：从存储返回给定键的值。

2 Put：将键值写入。

module Bitcask
  class DiskStore

    include Serializer

    def initialize(db_file = 'bitcask.db')
      @db_fh = File.open(db_file, 'a+b')
      @write_pos = 0
      @key_dir = {}
    end

    def get(key)
      key_struct = @key_dir[key]
      return '' if key_struct.nil?

      @db_fh.seek(key_struct[:write_pos])
      epoch, key, value = deserialize(@db_fh.read(key_struct[:log_size]))

      value
    end

    def put(key, value)
      log_size, data = serialize(epoch: Time.now.to_i, key: key, value: value)

      @key_dir[key] = key_struct(@write_pos, log_size, key)
      persist(data)
      incr_write_pos(log_size)

      nil
    end

    def flush
      @db_fh.flush
    end

    private

    def persist(data)
      @db_fh.write(data)
      @db_fh.flush
    end

    def incr_write_pos(pos)
      @write_pos += pos
    end

    def key_struct(write_pos, log_size, key)
      { write_pos: write_pos, log_size: log_size, key: key }
    end

  end
end

结语

为避免给你们带来太多数据，我从文章中遗漏了一些内容。您应该考虑的下一个改进是如何使用预先存在的数据文件初始化 DiskStore？

您可以使用您选择的语言来实现它。如果您在任何地方被阻止，请在https://github.com/dineshgowda24/bitcask-rb查看完整的工作代码。DiskStore如果您对其中任何一个感兴趣，它具有使用预先存在的数据文件和基准进行初始化的实现。

很高兴实施您自己的 KV 存储！

基于bitcask论文建立自己的快速、持久的 KV 存储