构建您自己的数据库

nam1234567

4.91/5 (101投票s)

2015年9月14日

CPOL

12分钟阅读

235337

3089

使用 C# 构建您自己的数据库类库

下载源代码 - 4.5 MB

1. 引言

我遇到了一个问题，我需要存储数百万条任意数据记录，范围从 1KB 到 8KB，以便我能像访问本地磁盘一样快速地查找、搜索、读取、遍历我的数据。

虽然 Sqlite 最初速度很快，但我讨厌使用它，因为它空间利用效率低，并且随着大量数据写入和/或删除，它的速度会随着时间推移而显著下降。Sqlite 还会将数据和索引混合在同一个文件中，这使得线性遍历体验非常糟糕，尤其是当记录被删除时，它会留下永远不会被填满的空隙，直到你调用 vacuum() 命令。在这篇 Mozilla 文章中了解更多关于 sqlite 的问题。

所以，我想做一个像 Sqlite 一样快，但不会随着时间推移而变慢，更好地重复利用已删除空间，并且不需要 vacuum() 的数据库。

完整的实现源代码可以在 GitHub 上下载（不过，我建议你先阅读文章再看代码。

目标

我设定了一个非常具体的目标来简化事情：我做了一个存储牛的数据库，其中定义了 CowModel
```
    public class CowModel
    {
        public Guid Id { get; set; }
        public string Breed { get; set; }
        public int Age { get; set; }
        public string Name { get; set; }
        public byte[] DnaData { get; set; }
    }
```
正如你所见，Breed、Name 和 DnaData 属性的大小是未知的，这使得这个项目更具挑战性，因为数据库需要处理可变长度的数据。

交付物将是一个单一的 C# DLL，我们可以直接集成到任何主项目中，它具有允许我们与数据库交互的以下接口。

请注意，所有读取/搜索/删除操作都是 ad-hoc 的（即，使用索引）

    public interface ICowDatabase
    {
        void Insert (CowModel cow);
        void Delete (CowModel cow);
        void Update (CowModel cow);
        CowModel Find (Guid id);  // Adhoc
        IEnumerable<CowModel> FindBy (string breed, int age); // Adhoc
    }

范围

这是一个简单的数据库，只需要 24-32 小时的工作量，主要目标是性能和学习数据库的工作原理，以便你可以自己动手创建一个。

像 ACID 兼容、事务/原子写入、多用户等功能都不包含在内，但设计上可以实现这些功能。

2. 设计

A. 块存储

我们将把数据存储在一个文件中。索引分开存储，每个索引一个文件。

为了让数据库能够重复利用已删除数据的空间，我们不将数据库文件视为一个流，而是将数据视为固定大小的独立块。这保证了最小的尺寸，以便未使用的空间可以被重复利用。

块的大小由你选择，但典型的文件系统块大小是 4KB，操作系统以 4KB 的块进行读写，所以你的块大小可以是 256B、512B、1024B 等，以确保你的数据库与底层文件系统块大小对齐。

我们将这个称为 BlockStorage。我将选择 4KB 作为我的块大小，因为我的牛 DNA 数据量相当大。

块的内容可以是任何东西，一个块不关心它存储什么。它还支持元数据头，这样我们以后可以存储诸如对其他块的引用、实际使用的块内容大小等等信息。

我们将使用以下接口访问块存储

    public interface IBlockStorage
    {
        /// <summary>
        /// Number of bytes of custom data per block that this storage can handle.
        /// </summary>
        int BlockContentSize {
            get;
        }

        /// <summary>
        /// Total number of bytes in header
        /// </summary>
        int BlockHeaderSize {
            get;
        }

        /// <summary>
        /// Total block size, equal to content size + header size, should be a multiple of 128B
        /// </summary>
        int BlockSize {
            get;
        }

        /// <summary>
        /// Find a block by its id
        /// </summary>
        IBlock Find (uint blockId);

        /// <summary>
        /// Allocate new block, extend the length of underlying storage
        /// </summary>
        IBlock CreateNew ();
    }

    public interface IBlock : IDisposable
    {
        /// <summary>
        /// Id of the block, must be unique
        /// </summary>
        uint Id {
            get;
        }

        /// <summary>
        /// A block may contain one ore more header metadata, 
        /// each header identified by a number and 8 bytes value.
        /// </summary>
        long GetHeader (int field);

        /// <summary>
        /// Change the value of specified header.
        /// Data must not be written to disk until the block is disposed.
        /// </summary>
        void SetHeader (int field, long value);

        /// <summary>
        /// Read content of this block (src) into given buffer (dst)
        /// </summary>
        void Read (byte[] dst, int dstOffset, int srcOffset, int count);

        /// <summary>
        /// Write content of given buffer (src) into this (dst)
        /// </summary>
        void Write (byte[] src, int srcOffset, int dstOffset, int count);
    }

B. 记录存储

块存储无法满足我们的数据是可变长度的要求。

为了支持可变长度记录，例如 CowModel，其中 Breed、Name、DnaData 属性的长度是未知的，我们在块存储之上添加了另一个层，称为记录存储。

在这里，一条记录由一个或多个块组成，并按顺序排列。换句话说，一个 Record 是块的链表。

一条记录可能使用一个完整的块来存储其数据，或者只使用块的一部分，这在块元数据头的 `length` 字段中定义（我们稍后会讨论实现）。

一条记录还有一个 ID，即组成它的第一个块的 ID。

可以通过块的元数据头字段之一，在逻辑上将一个块标记为已删除。此外，我们将使用一个特殊记录，即记录 #0（第一个记录），来存储已删除块 ID 的**堆栈**。删除一条记录是通过在逻辑上将其块标记为已删除，然后将这些块的 ID "**推**"到记录 #0 来完成的。这使得在创建新记录时可以通过读取记录 #0 并 " **弹出**"一个空闲 ID（如果存在）并重复使用它来回收未使用块的空间。

记录存储的用法如下

    public interface IRecordStorage
    {
        /// <summary>
        /// Effectively update an record
        /// </summary>
        void Update (uint recordId, byte[] data);

        /// <summary>
        /// Grab a record's data
        /// </summary>
        byte[] Find (uint recordId);

        /// <summary>
        /// This creates new empty record
        /// </summary>
        uint Create ();

        /// <summary>
        /// This creates new record with given data and returns its ID
        /// </summary>
        uint Create (byte[] data);

        /// <summary>
        /// Similar to Create(byte[] data), but with dataGenerator which generates
        /// data after a record is allocated
        /// </summary>
        uint Create (Func<uint, byte[]> dataGenerator);

        /// <summary>
        /// This deletes a record by its id
        /// </summary>
        void Delete (uint recordId);
    }

C. 索引

索引允许根据记录的属性搜索记录（例如，按 Id 查找牛，按 breed 查找牛）；当然，你可以遍历记录来查找你想要的内容，但在记录超过一百条时会非常低效。

B-Tree 是在数据库中构建索引最常用的数据结构。如果你不熟悉 B-tree 或树结构，你可以将其优点想象成一个 List<Tuple<K, V>>，按 K 排序，其中 K 是索引键（例如 Cow 的 ID 或 Breed），V 是 RecordStorage 中记录的 ID。这使你能够对键 K 进行 BinarySearch 并立即返回 V 的位置，无论列表有多大。

有关 B-Tree 或树结构的更多信息，我推荐阅读二叉树、二叉搜索树、自平衡二叉搜索树、红黑树、B-Tree。

目前，我们只需要知道索引存储键值对，其中 Key 是我们的 CowModel 的属性，Value 是我们数据的记录 ID。它不仅允许通过 Key 瞬间查找 Value（类似于 Dictionary），还可以找到任意键 K 的位置，并以升序或降序遍历从 K 到所有其他键。

B-Tree 由单个节点组成，每个节点保存对其他节点的引用。我们通过将每个节点序列化为一条记录来存储索引，利用上面设计的 RecordStorage。每个索引单独存储在一个文件中。

当我们访问一个 Node 时，我们读取其二进制内容并反序列化为一个 Node，对其进行更改，然后将其序列化回字节数组，并将其保存回一条记录中。

为了获得最佳性能，一个 Node 应该完美地放入一个 4KB 的块中。我们可以调整每个 Node 中的条目数量，使其能够适应。

Index 的用法如下

    public interface IIndex<K, V>
    {
        /// <summary>
        /// Create new entry in this index that maps key K to value V
        /// </summary>
        /// <param name="key">Key.</param>
        /// <param name="value">Value.</param>
        void Insert (K key, V value);

        /// <summary>
        /// Find an entry by key
        /// </summary>
        /// <param name="key">Key.</param>
        Tuple<K, V> Get (K key);

        /// <summary>
        /// Find all entries that contain a key larger than or equal to specified key
        /// </summary>
        IEnumerable<Tuple<K, V>> LargerThanOrEqualTo (K key);

        /// <summary>
        /// Find all entries that contain a key larger than specified key
        /// </summary>
        IEnumerable<Tuple<K, V>> LargerThan (K key);

        /// <summary>
        /// Find all entries that contain a key less than or equal specified key
        /// </summary>
        IEnumerable<Tuple<K, V>> LessThanOrEqualTo (K key);

        /// <summary>
        /// Find all entries that contain a key less than specified key
        /// </summary>
        IEnumerable<Tuple<K, V>> LessThan (K key);

        /// <summary>
        /// Delete an entry from this index, optionally use specified IComparer to compare values
        /// </summary>
        /// <param name="key">Key.</param>
        /// <param name="value">Value.</param>
        /// <param name="valueComparer">Value comparer; Default value is Comparer[k].Default</param>
        bool Delete (K key, V value, IComparer<V> valueComparer = null);

        /// <summary>
        /// Delete all entries of given key
        /// </summary>
        /// <param name="key">Key.</param>
        bool Delete (K key);
    }

D. 整合

我们将 IRecordStorage 和一个或多个 IIndex 组合起来构成一个完整的数据库。由于这两个接口都已实现，剩下的工作不多了。

将一条记录插入数据库是通过在 IRecordStorage.Create() 中创建一条记录来完成的，它返回一个 uint ID，然后使用这个 ID 和 IIndex 进行索引。
更新一条记录也会更新相关的 IIndex。
删除一条记录也会从 IIndex 中删除其条目。
搜索记录将尽可能使用 IIndex。当没有索引可以使用时，我们将遍历所有主索引条目（完整索引扫描）。

实现

源代码已附上。你也可以在 GitHub 上找到我的实现。

我们将数据库命名为 "FooDB"，其中主源代码位于 FooCore，并附带其单元测试 FooTest，以及使用 FooDB 构建其 CowDatabase 的 Cow 应用程序是 FooApplication。

A. BlockStorage 实现

值得关注的类

由于 BlockStorage 没有依赖项，因此实现起来简单直接。

创建新块

BlockStorage 初始化时，其唯一的依赖项是 Stream。
BlockStorage 在初始化时会维护 stream 的长度，使其成为指定 blockSize 的倍数。当客户端请求创建一个新块时，它只需扩展底层 Stream 的长度。

查找块

每个块都由一个唯一的 ID 标识，该 ID 也是它在 Stream 中的位置。例如，如果 Stream 的长度为 4096B，blockSize 为 1024B，那么就有 4 个块：0、1、2、3。
你可以通过将 stream 位置设置为 3*1024B = 3072 来轻松跳转到块 #3。

读写块

Block 实现提供了 Read() 和 Write() 方法来处理块内容。它们只是简单的包装器，用于从底层 Stream 读取或写入字节数组。
每个块的前几个字节都预留给头部。头部只是一个 LONG 值（8 字节），它可以是任何内容，一个块不关心其头部，除了允许客户端对其进行读写。
当客户端完成使用一个块时，必须调用 Dispose 以便所有缓存都被刷新。

注释

在此实现中，我缓存了前 4KB，通常包含头部和部分主体内容，以优化性能，因为文件系统通常以 4KB 的块进行读写，这样可以减少一些写入调用。但是，对于大于 4KB 的块，这会导致非线性写入（因为缓存的前 4KB 数据最后写入）。

对于写敏感的程序，这应该通过更智能的缓存刷新或将整个块缓存在内存中，然后在块被 Dispose 时按顺序写入来解决。

B. RecordStorage 实现

值得关注的类

FooCore/RecordStorage.cs

正如你所见，RecordStorage 初始化时以 IBlockStorage 作为依赖项，因为我们设计 RecordStorage 是建立在 BlockStorage 之上的。

创建记录

RecordStorage 通过将指定数据分割成多个块（像链表一样）来为任意数据字节数组创建一条记录。
它使用元数据头部（字段 #0 kNextBlockId 和 #3 kPreviousBlockId）将一个块链接到另一个块，以识别构成单个记录的块之前和之后的块。
它使用块头部（字段 #2 kBlockContentLength）来标记块的实际可用数据。这使得记录可以有任意大小，而不是仅仅是某个特定块大小的倍数。
通过重用已删除的块（例如，从记录 #0 "弹出"一个 uint）或请求底层 BlockStorage 分配块来分配新记录。

查找记录

查找记录很简单，因为记录的 ID 也是它组成块的第一个块的 ID。
如果第一个记录有下一个块，则获取下一个块，并继续，直到到达最后一个块。

删除记录

删除记录是通过将记录及其所有块标记为已删除（字段 #4 kIsDeleted）来完成的。
它使用一个特殊记录，即记录 #0，来跟踪已删除的块。这个记录就像一个 uint 堆栈。当一条记录被删除时，一个 uint 数字被"推"到堆栈中。

更新记录

如果新记录数据使用的块数与旧数据相同，则 RecordStorage 更新现有块的内容。
如果新记录数据使用的块数多于旧数据，则 RecordStorage 分配（或重用）更多所需的块。
如果新记录数据使用的块数少于旧数据，则未使用的块将被标记为已删除。

C. B-Tree（磁盘上的）实现

值得关注的类如下

B-Tree 实现已经被其他人完成了，我们只需要将他们的算法转化为代码。我遵循了这些文章来实现 B-Tree - 这篇、这篇和这篇。（不管怎样，我花了超过 18 个小时）。

棘手的部分是树必须能够从硬盘访问，而不是内存。当我们访问树的一部分时，只有那一部分会从硬盘加载到内存，而不是整棵树。

要做到这一点，我们只需要确保 2 件事

TreeNode 是可序列化的（可以转换为/从字节数组构造）。由于 Tree 由多个 TreeNodes 组成，如果其节点可序列化，则 Tree 也是可序列化的。
任何 TreeNode 的访问都必须通过 ITreeNodeManager 的实例来完成，也就是说，TreeNode 不应该保持对另一个 TreeNode 的直接内存引用，而是保持它们的 ID。

为了开发和单元测试，我模拟了一个 ITreeNodeManager 的实现，即 TreeMemoryNodeManager。之后，我编写了 TreeDiskNodeManager 用于生产使用，以及 TreeDiskNodeSerializer 助手来序列化 TreeNode。

D. CowDatabase 实现

此时创建 CowDatabase 将会非常简单快捷，因为我们已经完成了 RecordStorage 和索引的构建。

请查看我的 CowDatabase 实现如下

初始化

FooDatabase 初始化时，其参数为数据库路径，并使用命名约定来定位另外两个索引（cow Guid 的主索引，Breed 和 Age 的次级索引）。

然后它构建一个主索引，一个 Tree<Guid, uint>（将 cow 的 GUID 映射到其记录 ID），以及一个次级索引 Tree<Tuple<string, int>, uint>（将 cow 的 Breed 和 Age 映射到其记录 ID）。

插入、删除和更新牛

CowDatabase 使用 RecordStorage 实例来存储牛的序列化数据，并借助 CowSerializer。每当插入、删除或更新牛时，它会分别调用 RecordStorage 的 Create()、Remove()、Update()，并创建和修改所需的索引。

搜索牛

搜索 cow/cows 是通过查看主索引或次级索引来获取实际的记录 ID，然后使用这些 ID 和 RecordStorage 来读取 cow 数据。

现在，我们可以开始存储和查询我们的 cows 了，就像在 FooApplication/Program.cs 中一样；享受你定制的数据库吧！

兴趣点

我使用 Mac 上的 mono 编写了这个演示，性能非常好，但是，我发现 30-40% 的 CPU 时间花在运行 C# 代码而不是实际执行 IO 上（我期望的是 10-20%）。不过，我认为 C# 在 Windows 上运行效果更好。

我还遇到一个问题，我的 Mac 将所有写入调用缓存到内存中，我无法刷新它，即使使用 FileStream.Flush(bool true)。我认为这是 mono 的一个 bug？

总之，这是一个有趣的周末项目，希望大家喜欢。