OFADB设计文档

元数据管理模块设计

​ 设计理念上，我们采用数据表的形式对元数据进行了持久化，可通过文件持久化保存元数据，并能根据文件在内存中重建元数据在内存中的表示。我们支持的功能包括

• 元数据的持久化
• 库、表、索引、字段的元数据查询
• 数据索引的创建和删除
• 数据表的创建和删除
• 数据库的创建、加载、切换和删除

元数据持久化

​ 我们使用数据表的方式管理元数据。我们将所有的元数据都存在数据表中，所有的元数据表构成了一个系统数据库（System）。具体来说，我们将元数据分为三张表——数据库元数据表、表元数据表、索引源数据表，分别存储数据库、表、索引相关的元数据信息。对于这三张表的元数据信息，因为这三张表的结构的不变性，我们采用类成员变量的形式，将这几张表的字段信息等元数据内嵌在代码中，以此维护元数据数据库。

三张表存储的元数据实际内容和类型如下。

元数据存储结构

数据库元数据表

字段名	内容说明	字段类型
name	数据库名	String

表元数据表

字段名	内容说明	字段类型
tableName	表名	String
databaseName	数据库名	String
fields	字段信息	String
pkIndex	主键索引在索引list中的位置	Int

索引元数据表

字段名	内容说明	字段类型
tableName	表名	String
databaseName	数据库名	String
columnsInfo	索引用到的字段信息	String
isUnique	索引是否是unique	Bool

部分字段的详细介绍

• fields：是描述数据库表字段信息的字符串（filed）的列表，field存储的信息包括
  • 字段名
  • 字段类型
  • 字段是否可空
  • 字段是否为自增字段
  • 当前自增起点
• columnsInfo：当前索引所用到的表的字段信息列表，由字段在字段列表中的索引组成

元数据变更操作

​ 由于元数据以数据表的形式存储，所以对于元数据的直接操作就是对于普通数据表的增删改查操作。

元数据的查询操作

​ 我们支持了各层次元数据的查询接口，包括对于数据库元数据的查询、数据表元数据的查询、和字段元数据的查询，每个种类的元数据的查询都提供了存在性查询（待查询对象是否存在于现有数据库中）和数据获取查询（待查询对象的实际值）。所有的元数据查询结果都包含了该指向该对象本身的指针，例如表元数据查询得到的查询结果中包含了指向该表本身的指针。各类元数据查询详细说明如下：

数据库元数据查询

存在性查询

• 查询描述：输入数据库名，查询数据库是否存在。
• 查询实现：通过在数据库元数据表中查找是否存在包含该数据库名的行数据，判断数据库是否存在

数据库元数据内容查询：

• 查询描述：输入数据库名，获取数据库的实际元数据信息
  • 获取的元数据信息包括：
    • 数据库名
    • 数据库中所有的表的元数据
• 查询实现：首先使用存在性查询验证数据库存在，如果不存在，则返回空，否则在表源数据表中找到所有隶属于该数据库的表，获取这些表的元数据和数据库名一同作为结果返回。

数据表元数据查询

存在性查询

• 查询描述：输入数据库名、数据表名，查询该数据库中是否存在该表
• 查询实现：在表元数据表中查询是否存在库名等于输入数据库名、表名等于输入数据表明的项

数据表元数据内容查询

• 查询描述：输入数据库名、数据表名，获取该数据表的实际元数据信息
  • 数据表元数据内容：
    • 数据表名
    • 所属数据库
    • 表的字段元数据（所属数据表，字段名、字段类型、非空、自增）
    • 表的行数
    • 表的所有索引的元数据
• 查询实现：首先执行存在性查询，验证表存在（不存在则返回空），然后在表元数据表中查询获得除索引信息以外的所有元数据，然后在索引元数据表中查找所有隶属于此表的索引项，获取其元数据后和表的其他元数据一起返回。

字段元数据查询

存在性查询

• 查询描述：输入数据库名、数据表名、列名，查询指定数据库中的指定表是否存在字段名为输入字段名的字段。
• 查询实现：使用表元数据的内容查询获得表的元数据，在表的元数据中查找是否存在名为输入字段名的列

数据字段内容查询

• 查询描述：输入数据库名、数据表名、列名，获取指定数据库中的指定表指定字段的字段元数据。
  • 字段元数据信息内容：
    • 所属数据表
    • 字段名
    • 是否是自增属性，自增起点
    • 是否可以是空值
    • 字段类型
• 查询实现：首先执行存在性查询，验证字段存在（不存在返回空），使用表元数据的内容查询获得表的元数据，在表的元数据中查找该列元数据信息返回。

数据索引元数据查询

数据索引元数据内容查询

• 查询描述：输入数据库名、数据表名，获取该数据表的所有索引的元数据信息
  • 单个数据索引元数据信息包括：
    • 所属数据表
    • 使用到的列的序列号
    • 使用到的列的类型
    • 索引是否是unique
• 查询实现：首先使用表元数据的存在性查询确认表的存在性，然后在索引元数据表中查询属于该表的索引行，将行数据中的元数据信息返回。

涉及元数据变动的数据库操作

​ 涉及数据库元数据变动的操作包括对于数据库、表、索引的增加和删除操作。这些操作通过在对应的源数据表中插入或删除对应的元数据表项，来完成数据库中对应元数据的更新。

主要涉及的代码文件及说明

• meta Package：meta包中保存了几种对象的元数据类和用来实施元数据查询的方法类
  • DatabaseInfo：保存数据库元数据信息的类，保存的信息见上文元数据查询的内容查询
  • TableInfo：保存数据表元数据信息的类，保存的信息见上文元数据查询的内容查询
  • ColumnInfo：保存字段元数据信息的类，保存的信息见上文元数据查询的内容查询
  • IndexInfo：保存索引元数据信息的类，保存的信息见上文元数据查询的内容查询
  • Metadata：提供了库、表、字段、索引等所有元数据查询的接口的方法类。
• disk.System：用于维护系统数据库的加载，和系统数据库在内存中的更新，向外提供的接口包括：
  • 系统数据库的加载
  • 数据库的新建、删除
  • 数据索引的新建、删除
  • 当前操作数据库的加载、移除、切换
  • 文件系统的整体保存

存储模块设计

我们将数据文件分为索引文件和数据文件两类，索引文件用于存储索引数的结构，数据文件用于存储数据库中实际的行数据. 实现的功能包括:

• 多种数据类型的持久化存储,包括int,short,long,double,float,string,bool.
• 记录数据的增删改查
• 行数据的高速缓存
• 索引树的部分更新
• 自定义的二进制文件格式存储数据,数据文件——.data, 索引文件——.ndx

数据文件组织方式

将数据存在多个大小相等并且较小的块(block)中，文件主体由block的列表构成，文件头存储文件中块的大小、块的数量。

• 块个数
• 块大小
• 块列表

记录存储格式

单条记录需要存储的内容

• 空位图（用bit表示某个属性是否为null，1为null，该属性位置上存储内容无效）
• 变长字段记录内偏移量、长度
• 定长字段的值
• 变长字段的值

例：

		空位图	变长字段偏移、长度1	变长字段偏移、长度2	定长字段1	定长字段2	变长字段1	变长字段2
值		0100	（21，2）	（23，4）	12	null	“he”	"jack"
bytes		4-4	5-8	9-12	13-16	17-20	21-22	23-26

块组织存储格式（分槽的页结构）

采用变长数据的存储方式——分槽的页结构，结构如下图所示，在块头部存储块的元数据。具体存储结构见下文：

单个块存储结构

• 块大小
• 已经存储的记录个数
• 空闲位置指针
• 空闲空间大小
• 记录条目数组（块内偏移、大小）
• 记录数组

块内数据操作

删除方式

• 如果不是最后一条条目，则将对应记录的条目置为（-1，-1），否则回收条目的空间，
• 将对应索引后的所有记录依次后移
• 更新记录个数、空闲位置指针、空闲位置大小，因为单个块的大小不大，所以移动的代价相对变小。

插入方式

• 如果条目列表中有空闲条目,则直接使用空闲条目,否则新建条目
• 将数据写入块中,并更新条目上的偏移和大小

更新方式

• 如果更新后的数据大小变小，则将其后的记录后移相应位置，并更新对应条目的值；

• 如果更新后的数据大小变大，则对原数据执行删除操作后对新数据执行插入操作；

文件数据的操作

插入方式

遍历块的数组，

• 找到第一个可以插入的块（剩余大小足够大），在空闲位置指针处新建一个对应记录，更新空闲位置指针、记录条目数组、记录个数、空闲大小

• 如果没有可以插入的块，就新建一个块，然后插入

删除方式

• 找到待删除的块
• 执行块内删除

更新方式

• 检查当块是否可以容纳更新后的记录
• 如果可以,执行块内更新
• 如果不行,先删除旧记录,后执行新的记录的插入

索引文件存储组织

将整棵树以节点为单位，随机存储在文件中。文件内的空闲空间以优先列表的形式串接起来，用以新节点的插入。

文件组织方式

• 文件头：
  • 索引是否是unique；
  • 根节点的偏移
  • 空链表的头偏移，大小；
• 索引节点列表

单个索引节点存储的内容

• 节点大小
• 节点类型：m中间节点，l叶子节点
• 左节点偏移
• 右节点偏移
• key个数
• (中间节点)子节点的关键值和子节点偏移量|（叶子节点）关键值和对应叶子的内行数据个数和对应行的快和块内索引

中间节点数据格式：

叶子节点数据格式：

索引树的操作

删除节点

将节点对应空间加入空链表：

• 将节点空间加入到空列表中,保持列表按大小升序排序

更新节点

• 如果更新后的节点大小不大于原节点的大小
  • 覆盖原有数据
• 如果更新后的节点大小大于原有节点的大小
  • 删除原有节点
  • 插入更新后的节点

插入节点

• 在空列表中找到最适合插入该节点的空间——空间不小于该节点大小的最小空间，并将节点写入。

数据文件缓存

针对频繁的文件IO可能导致的访问时间过长,我们实现了数据文件在内存中的缓存. 以块为单位,在内存中建立数据文件的缓存空间,数据文件的访问和改写都会先在缓存中操作,在必要的时候才会进行文件的读写.

缓存机制

针对缓存冲突的问题，使用FIFS策略，给每个缓存中的块添加时间戳，当出现缓存区溢出时，将时间戳最小的块移除缓存区

数据操作

加载Block

• 如果缓存未满，直接从文件中加载对应块
• 如果缓存已满，根据FIFS策略，将符合条件的块移除缓存

移除Block

• 如果当前块未被更改，则直接丢弃
• 如果当前块已经被更改，则将文件中对应的存储区域用现在的内容覆盖。