返回

[CMU-15-445/645] Database Storage - Part 2

这是我在学习Databases Systems CMU 15-445/645/ Fall 2019过程记录的一些笔记,这次学习的第四课,主要是关于数据库存储的第二部分,主要是分析了 tuple 的不同存储方式。

数据表现方式 Data Representation

Tuple Storage

在内部存储的时候, tuples 只是一系列的字节数组,在使用的时候 DBMS 根据其内部存储的 schema 数据去推断 tuple 的组织方式来读取它。

数据的表现形式在不同层面有不同表现:

  • C/C++ 表现方式: INTEGER/BIGINT/SMALLINT/TINYINT

  • IEEE-754 标准和定点小数(浮点 vs. 定点):

    • FLOAT/REAL vs. NUMERIC/DECMAL
  • 表头: VARCHAR/VARBINARY/TEXT/BLOB

  • 时间表现方式(Unix epoch 之后的(微)秒数):TIME/DATE/TIMESTAMP

数字的存储方式

DBMS 的用户只需要关注最后两种,前两种由开发者考虑(主要是第二个两种表现方式的区别),对于第一种而言,这种数据类型主要是用了原生的 C/C++ 的数据类型,也是符合 IEEE-754 标准的,通常来说操作会比较快(CPU 有写好的指令,不需要额外操作),但是有的时候会有 rounding 的问题,具体参考以下两段代码。

#include <stdio.h>

int main() {

    float x = 0.1;
    float y = 0.2;

    // not rounding
    printf("x + y = %f\n", x + y);
    printf("0.3 = %f\n", 0.3);

    // rounding, error occurs!
    printf("x + y = %.20f\n", x + y);
    printf("0.3 = %.20f\n", 0.3);
}

他的输出是:

x + y = 0.300000
0.3 = 0.300000
x + y = 0.30000001192092895508
0.3 = 0.29999999999999998890

出现这样问题主要是因为硬件没办法存储固定位数的小数,为了解决 rounding 的问题,我们需要考虑用定点小数去存储数据,这个时候我们考虑用一种类似VARCHAR 的方式(不过不是存成字符串)去存储一组定长的二进制表示并且有元数据(存储位数等等)说明的方式去存储。

Postgres 内部的数字存储方式如下(也是一种定点数存储方法),对于这种方式存储,数字的操作方式会需要很多额外的考虑(为什么比浮点数计算速度慢的原因):

typedef unsigned char NumbericDigit;
typedef struct {
    int ndigits; // # of digits
    int weight; // weight of 1st digit
    int scale; // scale factor
    int sign; // positive/negative/NaN
    NumericDigit *digits; // digit storage
} numeric;

大尺寸的值的存储

通常来说, DBMS 不允许单个 tuple 的尺寸超过一定值,对于 tuple 里面某些比较大的参数,有不同的处理方式:

  • 将超过规定的值存在一个单独的页面(overflow page)里,在 tuple 内部用一个指针指向它,如下图所示,这样做的原因是当 tuple 崩溃的时候不希望会影响到这个参数,通常比较大的参数大部分时候不需要 update,常用的操作是 read,常用的 DBMS 的 overflow page 有:

    • Postgres: TOAST (>2KB)

    • MySQL: Overflow (>½ size of page)

    • SQL Server: Overflow (>size of page)

  • 还有一种做法是将内容存在外部文件( BLOB 类型)里面,然后用指针指向该文件的位置,如下图所示。但是 DMBS 不能更改外部文件,只能读取,而且没办法对文件保护(如果其他进程对文件进行修改的话),用这种方法的 DBMS 有:

    • Oracle: BFILE data type

    • Microsoft: FILESTREAM data type

System Catalogs

一个 DBMS 会将与数据有关的一些元数据存储到它内部的目录里:包括表格,列,索引,用户和权限还有内部统计数据等等。同时这个目录会和数据库的内容一起存在 DBMS 里。

用户可以通过查询 DBMS 的 INFORMATION_SCHEMA 目录来获得关于该数据库的内部信息:这是 ANSI 的标准规定一个只读的方式来提供关于数据库的信息。同时,不同的 DBMS 也有自己的方式(快捷键)来获得信息,如下图所示。

关系模型没有规定我们必须将 tuple 的所有参数都存放在一个单独page上,因为在某些情况下这样未必是最好的布置方式,下面以 Wikipedia 举个例子:

下图是三个 table:

我们主要考虑两种工作模式(workload):

  • On-line Transaction Processing (OLTP): 每次查询从外部读取一小部分数据然后存入(更新)本地数据库中,通常是用户第一次搭建(安装)应用要做的步骤,对应的维基百科例子操作如下所示:
// 更新页面
SELECT P.*, R.*
    FROM pages AS P
  INNER JOIN revisions AS R
    ON P.latest = R.revID
  WHERE P.pageID = ?
// 登陆账户
UPDATE useracct
    SET lastLogin = NOW(),
        hostname = ?
    WHERE userID = ?
// 插入数据
INSERT INTO revisions
    VALUES (?,?,?)
  • 另一种工作模式是 On-line Analytical Processing (OLAP): 一次读取大量数据计算计算处理,但是不对数据进行更新,对应的维基百科例子如下:
// 计算一些统计数据
SELECT COUNT(U.lastLogin),
    EXTRACT(month FROM
        U.lastLogin) AS month
  FROM useracct AS U
 WHERE U.hostname LIKE '%.gov'
 GROUP BY
  EXTRACT(month FROM U.lastLogin)

两种工作方式和读写关系如下图,这里不讨论HTAP:

Storage Models

在了解两种工作方式,我们可以开始考虑存储模型。DBMS 针对 OLTP 或者 OLAP 工作方式可以有不同的方式去存储 tuples。目前我们假定统一用 n-ary 存储方式(行存储)。

N-ary Storage Model (NSM)

用这种模型 DBMS 连续存储 tuple 的所有参数在一页里,tuple 之间也是连续存放。这种方式对 OLTP 比较有利,因为大部分时间只需要读取/更新/插入单条信息(tuple),如下图所示。

下面是一个简单的查询过程演示,这种情况下每次只插入一个 tuple,这种存储方式比较快捷:

对于下面的例子,NSM 的存储方式比较不好,因为查询过程不得不访问(读取)所有的 tuple,哪怕我们只需要其中两个参数,效率比较低

总结一下, NSM 的优缺点分别是:

优点:

  • 快速插入,更新和删除
  • 对于需要整个 tuple 的查询指令比较友好

缺点:

  • 对于扫描某组参数的查询指令不友好(效率低)

DECOMPOSITION STORAGE MODEL (DSM)

针对上面的问题,还有第二种存储模型,这种存储模型按参数将所有值连续存放(也被称为列模型),对于 OLAP 工作模型(需要扫描(只读取)所有 tuple 的某个参数)比较友好,对应的例子如下所示:

在这种情况下,我们怎么识别哪个参数对应哪个 tuple 呢?有两种方法选择:

  • 固定长度的偏移(fixed-length offsets):每个值保存成相同的长度;
  • 嵌入 id(embedded tuple ids)每个值额外存储一个 tuple id 值用于识别,比较浪费空间。

总结一下, DSM 的优缺点分别是:

优点:

  • 减少需要的I/O数(只读取需要的数据)
  • 因为同一个page 保存的是相同的类型,所以可以有数据压缩的方法

缺点:

  • 对于查询(插入,更新,删除)单个 tuple 效率较低。

目前绝大部分系统都有 DSM 存储方式。

Built with Hugo
Theme Stack designed by Jimmy