乐趣区

关于数据库:CMU-15445-数据库课程第四课文字版-存储2

jiezi

熟肉视频地址：

  • [CMU 数据库管理系统课程[熟肉]4. 数据库存储构造 2(上)](https://www.bilibili.com/vide…)
  • [CMU 数据库管理系统课程[熟肉]4. 数据库存储构造 2(下)](https://www.bilibili.com/vide…)

1. 面向日志的存储

上节课咱们讲完了面向元组的存储，这节课从面向日志的存储设计开始。

在这里，页中不存储元组数据，只会存储日志记录，即通过日志记录咱们插入的数据以及咱们如何更新零碎中的数据，包含：插入元组的语句日志，删除元组的语句日志，更新元组的语句日志。
这种设计 写得很快，因为不必在一个页里寻找并更新单个元组，就是在开端追加写，这样写起来十分快，对于磁盘 I/O 也很好。

然而对于 读取，就很麻烦了。为了读取一条记录，咱们要做的就是从后向前扫描这个日志，以便从新创立咱们想要查问的元组。

当然咱们能够做一些优化，比方咱们能够 建设一个索引，用来找到利用于每个元组的不同日志记录，这样咱们就不须要对所有的日志记录进行残缺的扫描。然而这带来了而外的元数据存储耗费。

另一种优化形式就是 定期压缩这些日志，基本上只是把所有的日志记录压缩成单个值，过程是：获取页的锁并锁定，而后执行压缩，而后开释锁。让咱们更深刻地讨论一下压缩是如何进行的：

首先是 层级压缩 (level compaction) 的：从顶层开始是第 0 级，咱们有这个依照执行程序排好序的日志文件，它在一直积攒，随着工夫积攒了所有这些页。咱们要做的是做一个周期性的压缩，即当第 0 级有两页被填满的时候，将它们外面的记录做归并排序，并压缩到一个更大的文件中并放到下一级，即第 1 级。之后更多的日志文件会在顶层第 0 级建设，咱们只是一直反复这个过程，第 1 级有两页满了的就归并排序压缩成为一个新的放入第 2 级，顺次类推。
另一种是 整体压缩 (universal compaction) 的：即没有等级概念，只是合并归并压缩相邻的页文件。

数据格式（Data Representation）

如果咱们在页面中有一个独自的元组，咱们如何存储它，如何解释存储在外面的数据，以及 DBMS 的其余层如何利用或从元组存储中提取它们须要的数据。

元组实质上就是一个字节序列，DBMS 目录中会蕴含表的模式信息，通过这个模式信息能够解析出元组中的数据。


元组内的数据属性能够有不同的类型，个别常见的类型包含：

  • 整数类型：有不同的大小的整数，在 SQL 规范中是基于它们反对的值范畴定义的，个别有 BIGINT/SMALLINT/TINYINT/INTEGER 等等
  • 浮点数类型或者小数类型：一种是基于 IEEE-754 规范定义的近似浮点值，还有就是固定小数点的小数，个别有 FLOAT/REAL，以及 NUMERIC/DECIMAL 等等。
  • 变长类型：这种数据类型并非固定长度，所以带有头部标识数据长度，之后跟着理论数据，比方 VARCHAR/VARBINARY/TEXT/BLOB
  • 工夫类型：个别通过计算与 Unix Epoch（1970-01-01 00:00:00 UTC）工夫通过的工夫长度（单位为毫秒或者秒），保留在一个 32 位或者 64 为的整数类型中存储。

这里最辣手的是 浮点小数或者任意精度的小数的解决。

对于 小数精度不确认的小数，例如不限度计算结果的数字的小数位数这种状况，因为精度是不确认的，所以很难通过一些计算机构造示意进去，例如 C/C++ 中对应的 FLOAT 和 DOUBLE/REAL 等类型，他们是通过 IEEE-754 规范去近似迫近理论存储的小数：

  • 最高位 bit 示意符号位（0x8000000000000000）
  • 第二到第十二的 bit 示意指数（0x7ff0000000000000）
  • 剩下的 bit 示意浮点数真正的数字（0x000fffffffffffffL）

举个例子，78.5 这个数字，对于 double，理论存储的就是：40 53 a0 00 00 00 00 00，转换成二进制：01000000 01010011 10100000 00000000 00000000 00000000 00000000 00000000，符号位：0，指数位 10000000101 = 1029，减去阶数 1023 = 理论指数 6，小数局部 0.0011101000000000000000000000000000000000000000000000，转换为十进制为 0.125 + 0.0625 + 0.03125 + 0.0078125 = 0.2265625，加上隐含数字 1 为 1.2265625，之后乘以 2 的 6 次方就是 1.2265625 * 64 = 78.5

double 应用的位数比拟多，所以迫近的误差更小一些，float 应用的位数比拟少，可能的误差就会大一些。

这里应用一个指定精度显示的程序展现了这种 IEEE-754 规范迫近带来的可能的误差。

如果你是在不须要那么准确的场景，那么能够应用这种 IEEE-754 规范迫近的近似小数，如果你须要很准确的场景，那么就不要用这种了。你就须要应用固定精度的 数字类型（Numeric Type）

能够在给数字类型设置一个任意的精度和位数，这些货色在理论零碎中如何工作有很多不同的实现。一般来说，商业版的数据库要简单得多，因为他们晓得商业利用对固定精度的数值有很大的需要。然而这里须要衡量，因为你须要的精确度越高会在你的处理过程中须要更多的开销。

postgres 是这样实现其数字数据类型：

这个构造体包含：

  • int ndigits: 蕴含数字的个数
  • int weight：第一个数字的权重，理论的数字由第一个数字乘以这个权重组成
  • int scale：放大系数
  • int sign：符号，是正是负还是空
  • NumericDigit *digits：是一个字符数组，保留所有的数字

MySQL 的存储构造也是相似的：

这个构造体包含：

  • int intg: 小数点前的数字个数
  • int frac：小数点前面的数字个数
  • int len：数字占用字节长度
  • bool sign：符号，是正是负
  • decimal_digit_t *buf：是一个 int32 数组，保留所有的数字

大多数零碎不容许元组超过单个页的大小，所以它要么受列的大小限度要么受列的个数限度，或者两者都受限制，所以根本不能指定一个大于一页大小的元组。然而如果元组的某个值大于一页大小怎么办？例如一个某个元组有个值是 VARCHAR 类型，保留了很长的字符串，那么咱们不会把所有数据和元组其余数据放在一起，而是把它存储在 溢出页 中。

假如元组的 c 属性是一个 VARCHAR 类型并且保留的值很大，那么元组外在 c 的地位会保留一个指针，它会指向存储在 溢出页 中的 varchar 数据。溢出页可能一页存不下，不止一页大小，所以会是一个页链表。这在不同的零碎中有不同的叫法：

  • postgres 称它为 toast，如果大于 2KB，溢出页就会呈现
  • MySQL：大于页大小的一半就会呈现溢出页
  • SQL Server：大于页大小才会呈现溢出页

除了 溢出页 还有另一种形式即 存储为内部文件

某些 DBMS 容许你将这种大值存储到内部的文件中，以 BLOB 的形式解决这个数据，例如：

  • Oracle：BFILE 数据类型
  • Microsoft：FILESTREAM 数据类型

咱们个别不不适宜存储进数据库的大数据放入内部文件存储，例如视频、图片等等。咱们只是存储了一个指向数据的指针，理论指向的数据位于文件系统的其余中央，咱们能够在须要的时候援用它。

然而这样就丢失了 DBMS 对其的治理个性，例如不能保障内部是否有批改或者删除这个内部文件，不能保障事务性批改等等。

对于非不适宜放入数据库存储的那种大数据，比方大 JSON 等等，Jim Gray 已经有一篇论文钻研，评估数据大小对于是间接在溢出页面内存储 blob 好，还是在内部存储 blob 更好的影响，这是一篇 15 年前的论文，这篇论文得出的论断是，他们得出的论断是 256KB 的大小在内部存储更无利，当初这个数字可能变得更大了。然而咱们要记住，如果它存储在 DBMS 中，咱们每次都要把这些微小的对象通过很多页写入和从磁盘中读取，这是咱们要思考的衡量。

3. 系统目录（System Catalog）


咱们接下来要讲的是零碎级别的目录，DBMS 须要在外部保留所有对于数据库的元数据以便于他能须要晓得如何编码和解码存储在代表元组的字节中的数据。个别存储 对于表，列，索引，视图的构造信息 ，诸如此类的构造信息。DBMS 通常还存储无关 用户和权限的信息 ，就像拜访权限，即用户应该可能查看或批改哪些数据。最初，DBMS 还存储了 大量的外部统计数据，比方不同值的数量，或者连贯基数，或者数据范畴之类的，这些是构建查问打算，查问执行中十分重要的。

大部分的 DBMS 都将数据库存储为目录类型的构造，后面咱们说过，在这个系统目录中也会存储对于表，列，索引，视图的构造信息，这些构造信息也像一般的表一样存储 。那么当初就有了鸡生蛋蛋生鸡的问题，咱们须要这些构造信息解析读取表数据，然而这些信息也以表的模式存储。所以个别的设计是 它们有这些非凡的元数据对象包装器，零碎能够用来间接编码和解码存储在系统目录中的值。

用户能够查问 DBMS 的这个外部目录，它通常存储在这个 INFORMATION_SCHEMA 中，以获取对于数据库的信息以及各种统计信息等等。这被 ANSI 规范定义为只读视图的汇合，在它标准化之前，这已经很凌乱，每个零碎都有本人的形式来裸露这些元数据。当初有了这个规范，大家都能够通过拜访 INFORMATION_SCHEMA 来拜访这些信息。不过不同的零碎还是裸露了其余的一些等价的快捷方式命令拜访这些信息，比方：

这是列出某个数据库中所有表的命令：

  • SQL-92 规范中是：select * from information_schema.tables
  • Postgres 中是：\d
  • MySQL 中是：show tables
  • sqlite 中是：.tables


这是查看某个表的详细信息的命令：

  • SQL-92 规范中是：select * from information_schema.tables where table_name = 'student'
  • Postgres 中是：\d student
  • MySQL 中是：DESCRIBE student
  • sqlite 中是：.schema student

4. 数据库工作负载类型（Database Workload）

咱们次要有三种不同类型的数据库工作负载：

  • 第一个是 在线事务处理，简称 OLTP（Online Transaction Processing）：这意味着你有很多疾速短小的运行操作，即每次只读取或更新一小部分数据。例如你的银行账户场景，比方你想要失去你银行账户的余额，你只是读取一个值，或者如果你想做一笔交易，比方贷款，这是一笔相当短的交易。还有就是像亚马逊这样的网上商店，你浏览不同的产品把它们加到你的购物车结账付运费，你拜访的数据量绝对于亚马逊提供的所有产品来说是绝对较小的，然而如果你思考下世界上有很多同时购物的人，这就千里之行; 始于足下了，即各个事务拜访或批改的数据量千里之行; 始于足下了。
  • 第二个是 在线剖析解决，简称 OLAP（Online Analytical Processing）：这些有点像剖析查问，读取大量的数据，扫描表的大部分，会产生聚合，有很多表之间的连贯，通常用于决策反对或商业智能。同样是亚马逊的例子，比方亚马逊想晓得在过来的一个月里，CMU 学生购买最多的五个商品是什么。这种查问须要扫描一个大的样本，而不仅仅是更新单个或读取单个记录。
  • 最初一个是最近越来越风行的 混合事务和剖析解决，简称 HTAP（Hybrid Transaction and Analytical Processing）：指标是可能把 OLTP 和 OLAP 放在同一个数据库实例上，事务处理和剖析同时运行，这样可能失去对于交易数据更快或更实时的见解。

这个坐标图可能更直观些，X 轴是从写多读少到读多写少，Y 轴是申请复杂度，从简答到简单。OLTP 的工作负载更多的是写多一些并且比较简单的申请，OLAP 的工作负载更多的是读多一些并且比较复杂的申请，HTAP 介于两者之间。

在理论应用中，个别公司会建设 OLAP 与 OLTP 独立的环境：因而，在 一端你通常会有多个 OLTP 数据筒仓 ，这里做所有的在线业务申请； 另一端十分大的 OLAP 数据仓库 ，你要在数据仓库转储所有的数据筒仓的数据以供剖析。咱们须要 从数据筒仓到数据仓库的数据传输，次要通过这个 ETL（Extract Transform Load，提取、转换、加载）过程 ：咱们从这些不同的数据筒仓中 提取 所有的数据，这些数据格式可能与咱们最终须要的数据格式有差别，所以咱们须要 转换 这些数据，并且对数据做一些解决，比方合并，删除反复等等，最初 加载 到数据仓库中。还有一些 数据分析的后果须要从数据仓库传回数据筒仓中，例如一些产品举荐信息，在你拜访商品网页时为你举荐的产品。HTAP 的思维就是让这些事务工作与查问工作一起并发执行，并省略很多两头的同步操作。

为什么辨别不同类型的工作负载很重要？回顾一下关系模型，它为咱们对数据进行不同操作提供了肯定的规定和要求，但它 并没有通知咱们在物理上咱们须要如何存储数据 。咱们须要依据咱们的业务即工作负载的类型，来决定咱们的数据如何存储。咱们后面次要讲的次要是 基于行 的存储，即 某一个元组的所有属性的数据都严密的保留在一起。然而这种设计并不实用所有的场景，咱们来看一个维基百科的例子：


咱们有有一个 useracct 表，也就是维基百科的用户，它蕴含 userId 和 userName；而后有 pages 表，存储了维基百科数据；而后有 revisions 表，它阐明哪个用户对哪个页面进行了哪些编辑或订正。同时，userId 指向 useracct 表，pageId 指向 pages 表，其中 pages 表的 revId 指向 revisions 表。

对于维基百科 OLTP 业务场景举几个例子，这些场景都只会批改或者查问表中很少的数据：

  • 查问某一个维基百科词条，这样就是查问 pages 以及 revisions 表。
  • 比方可能是用户每次登陆的时候更新用户记录
  • 获取用户上次登录时更新的词条数据
  • 批改词条，即批改 pages 表以及增加一个新的记录到 revisions 表中。这些是运行工夫很短的简略操作，只在数据库中读取或写入一些值。

对于维基百科 OLAP 业务场景的一个例子是查看上个月来自于 .gov 的用户不同登陆次数，这种就会扫描表中的大部分数据。

咱们引入存储模型的概念，第一种是 基于行的存储模型 ，这就是所谓的 n 元存储模型（N-ary Storage Model），在一个页中存储基于行的数据，所有货色都像一个字节数组，所有货色都是间断存储的。这种格局对于 OLTP 业务申请更加敌对，因为查问偏向于操作单个记录或者行这个行的所有数据是存储在一起的，如果不思考溢出页的话就都在一页，也就是 大部分申请每个都只会操作一页。


应用后面维基百科的 OLTP 例子，例如用户登录须要查问单个用户，这个申请会走索引（索引在前面的课堂中会讲到，在第七讲），索引会通知咱们去哪个页的哪个槽去获取这个用户元组的地位，读取槽获取到用户元组位与页中的地位，而后就能读取到这个用户元组的所有信息。同时注册新用户须要插入记录，这个插入也只会放在一页上，并且用户所有值都在一起。

然而这种存储不太适宜 OLAP 的场景，还是用后面提到的维基百科的例子，查看上个月来自于 .gov 的用户不同登陆次数，这个查问不能走索引，咱们须要遍历这个表的所有页，过滤 hostname 是.gov 的以及 lastlogin 是上个月的，而后统计 lastlogin 字段，也就是咱们其实只须要 hostname 和 lastlogin 这两个字段的值，然而理论咱们却 加载并解析了整个元组的所有属性值。这些带来了首先是磁盘 I/O 的节约，以及对于解析整个元组数据带来的额定的内存与 CPU 耗费。


咱们总结下 n 元存储模型的优缺点：

  • 长处：

    • 元组的增删改查很快
    • 适宜须要查问整个元组数据的查问

  • 毛病：

    • 很不适宜要扫描表中大部分数据，并且查问的只是元组属性的子集的场景


第二种是 基于列的存储模型 ，这就是所谓的 合成存储模型或 DSM（Decomposition Storage Model），行将一个元组的 繁多属性的值于一个页面中间断存储 ，而不是间断地存储单个元组的所有不同属性值。咱们将提取所有的元组这个列值并将他们间断存储，这也是 ” 列存储 ” 这个名字的起源。这对于有很多只读查问的 OLAP 工作负载十分现实，个别这种查问须要剖析大部分行的某些属性值，如果咱们把同一属性的值放在一起，咱们就不必扫描查问中用不到的属性，并且同一属性的值在一起这样对于某个属性运行聚合函数窗口函数就会效率更高。

咱们回到后面提到的维基百科的 OLAP 例子，查看上个月来自于 .gov 的用户不同登陆次数，这个查问咱们只须要 hostname 和 lastLogin，咱们不须要表格中的任何其余属性，所以咱们当初就能够找到对应于这两个列的页，缩小了要扫描的数据耗费。

然而对于那种须要返回元组所有属性的申请，比方要查问某一个元组的所有属性，须要查问每个属性的所在的页，而后汇总返回。那么如何从每个属性所在的页找到这个元组对应的数据呢？

能够有两种形式：

  • 固定长度的偏移量 ：因为每个列值都是雷同的类型， 对于固定长度字段，咱们间接通过长度乘以个数就能失去对应数据的地位偏移 。然而如果对于可变长度的字段，例如 可变长度的字符串 ， 能够通过一些形式转换成固定长度的字段，例如将字符串填充拉长到特定的长度，或者进行编码应用长度的整数代码替换字符串，这个在之后的课程会具体探讨。这种形式尽管占用空间小实现简略，然而对于变长字段实现比拟麻烦并且会有空间节约等问题。
  • 另一种抉择是存储 元组的 id 间接嵌入到列中：个别这些列还是通过某种排序规定排序的，咱们能够通过二分查找来找到对应 id 的数据。

咱们总结下 DSM 存储模型的优缺点：

  • 长处：

    • 缩小了 I / O 节约，因为只读取查问所需的列中的数据
    • 对于理论存储的列，您能够失去更好的查询处理和压缩（前面课程还会具体探讨这个，同一种类型的数据放在一起更好压缩，例如咱们存储的是日期，那么咱们不必每一个值都存储日期，而是第一个存储日期，之后的存储与第一个日期的绝对日期）

  • 毛病：

    • 如果你想去重建一个独自的元组的所有数据，那么就比较慢
    • 要做插入更新之类的事件要艰难得多，因为你当初须要在多列多页中增加值而不是一次写完


DSM 零碎并不是新的设计，它们曾经存在了一段时间，第一个是在 20 世纪 70 年代公布的 Cantor，它实际上不像 DBMS，而是像一个文件系统。在 20 世纪 80 年代，有了第一个对于 DSM 存储的实践根底或提议。在 20 世纪 90 年代，有一种产品叫做 SybaseIQ，它就像 Sybase 这个行存储的内存加速器，惋惜并不风行。他们所做的是将数据以列存储模式在内存中，以减速某些类型的查问。在 21 世纪初到中期，这三个零碎开始风行，Vertica, VectorWise 和 MonetDB，他们是第一个受欢迎的，商业上胜利的列存储，为很多目前很常见的列存储技术铺平了路线。从 2010 当前，根本所有人都会用到基于 DSM 的零碎了。

总结一下，尽管课程开始的时候始终在说 DBMS 是由这些独立的局部组成的技术栈，但其实并不是齐全独立的，比方这里，为指标工作负载抉择正确的存储模型十分重要，对于 OLTP 你想要行存储，OLAP 须要列存储。

微信搜寻“干货满满张哈希”关注公众号，加作者微信，每日一刷，轻松晋升技术，斩获各种 offer：

我会常常发一些很好的各种框架的官网社区的新闻视频材料并加上集体翻译字幕到如下地址（也包含下面的公众号），欢送关注：

  • 知乎：https://www.zhihu.com/people/…
  • B 站：https://space.bilibili.com/31…
退出移动版