写点什么

DDIA 读书笔记(2)数据模型的存储与检索

用户头像
莫黎
关注
发布于: 2020 年 10 月 22 日

大部分应用都是基于数据模型一层层封装诞生的,每一层的数据模型都是基于低一层的数据模型实现。程序员对业务模型进行抽象,构建数据模型,CRUD 的 API。并将数据模型转化为数据库 (SQL 或 NoSQL )的通用结构并存储。而数据库则将自己的通用数据模型转化为磁盘上的字节流,中间还包含着基础数据结构的封装等。



不同的数据模型有各自的优劣,有的查询很快,有的新增很快,需要根据不同的业务场景选择合适的数据模型

关系模型与文档模型

关系数据库称霸了整个行业二三十年,期间也出现过其他的竞争对手,像网络模型、层次模型之类的,但最终都消磨在历史的尘埃当中,唯有关系数据库一直在随着时代不断地发展,并应用在了各种各样的领域。



进入 21 世纪后,新的竞争者 NoSQL 诞生了,经过一段时间的传播和曲解,现在基本成了非关系数据库的统称(Not Only SQL)。NoSQL 受欢迎的原因是因为它解决了 SQL 的数据库的一些痛点,比如超大数据量或是超高吞吐量,或是具有 SQL 无法匹及的灵活性。



文档数据库可以更好的展现业务模型,就像一份简历,上面会有姓名学校公司等,就是天生的一份文档,很容易就可以用 JSON 来表示其结构以及嵌套关系,如果使用 SQL 去存储,就需要定义很多的表,还需要整理表与表之间的关联。事实上为了方便存储和查询,开发人员会尝试将非索引字段也变成 json 并存储为表中的一个字段,也算是兼顾了文档模型与关系模型。



关系模型仍然保持着自己的优势,所有的表都是字段集合,没有复杂的嵌套结构,也不会有复杂的访问路径,我们可以通过任意条件来查询任意字段。而且 SQL 是一种声明式语言,我们只需要描述自己想要获取的数据,如何查询,怎么走索引,都可以交给优化器去做,大大解放了开发人员的心智负担。查询优化器经过了多年的发展,已经变得非常复杂,同时也算是一种壁垒,是其他数据库难以超越的。



虽然文档模式的灵活性被很多人称赞,但是其本质是把数据校验的活交给了应用层去实现,应用层在写入和读取是都需要去校验数据,唯一的好处大概是加字段的0成本吧,关系型的大表想要加字段都是伤筋动骨的操作。

数据存储与检索

OLTP 与 OLAP

早期数据库只是用来处理应用在线交互流程,根据用户的输入来插入或更新记录,或是通过指定的 key 查询少量数据,这类访问模式被称为在线事务处理(online transaction processing,OLTP)。



后来,随着数据量的增大,数据库也需要用来进行数据分析,它和传统的访问方式有很大的不同,数据分析通常需要读取大量的记录(GB 甚至 TB),并取记录里少量几列进行计算并展示结果,这个结果是面向企业内部人员而不是用户,用来辅助业务决策,它对数据的时性要求没有传统方式那么高,因此新的数据通常也是批量写入。这类的模式称为在线分析处理(online analytic process,OLAP)。



早期 OLTP 和 OLAP 都是使用同一个数据库,SQL 足够灵活,可以同时胜任两种工作模式,但随着在线业务的增长,OLAP 的大量读取记录的特点很容易影响到 OLTP 业务的稳定性,因此 OLAP 业务大多都会迁移到单独的数据上进行工作,这个单独的数据库被称为数据仓库。



随着 OLTP 与 OLAP 分家,为了更好的满足业务需求,两者使用的数据模型虽然都是 SQL,但内部存储细节的实现已经完全不同,需要分开讨论。



OLTP 存储引擎

日志结构存储 SSTable 和 LSM-Tree

假设数据库的功能是简单地存取 KV 对,key 和 value 都是字节序列。



一个普通的日志结构存储方案是在写入时追加到文件末尾,读取时则扫描整个文件,取最后一个匹配的 key。这个方案有着世界最快的写入速度,毕竟除了简单的追加啥都没干,但是读取的时间复杂度是 O(n)。这种仅支持追加式更新的文件和日志非常相似,所以称之为日志结构。



接下来有两个问题



  1. 是读取效率太低不可接受。为了提高读取效率,我们需要加上索引,也是怎么简单怎么来,直接在内存保存每个 key 对应的磁盘偏移量。

  2. 追加式更新会导致文件越来越大,磁盘不够用。一个解决方案是将文件分段,当文件到达一定大小时就封存它,再开个新的文件进行写入。因为旧文件不会再有写入,我们可以再开个进程去压缩它(根据 key 去重),压缩之后代替旧文件进行读写即可。每个文件都有自己的内存索引,因此读取时也需要查询多个文件。



目前的哈希索引还有有很多限制,放内存里放不下多少,放磁盘上随机读不友好,而且不支持区间查询。让我们继续进行改造。



如果要做区间查询,就必须期望key是按照顺序排列的,这样才能顺序读取而不影响效率。在磁盘上维护排序结构会很复杂,我们把最新的文件段放在内存中,使用红黑树或者 AVL 树来保持 key 的顺序,当文件段到达一定大小或一定的时间就持久化到磁盘上。这样做的好处很明显

  • 合并压缩磁盘上的文件段会变的更加简单高效,哪怕文件段比内存大,也可以用归并排序的办法去重。

  • 索引不需要再记录每个 key 的偏移量,可以稀疏一些。(即使不知道某个 key 的确切偏移量,可以通过二分查找迅速定位)

  • 最新的文件段在持久化之前可以进行压缩,节省磁盘空间,降低 IO。



还有一个小问题,假如数据库崩溃,内存中的文件段会丢失。因此还需要保留单独的日志文件,每一个写入都需要追加日志,用于崩溃后的恢复。



最后总结一下整个工作流程:

  • 当有数据写入时,数据会被添加到内存中的平衡树(内存表)。

  • 当内存表大于某个阀值或是超过某个时长未持久化时,将其作为文件写进磁盘中,同时开新的内存表来写心得数据。

  • 处理读请求时,先查找内存表,然后按时间倒序查找磁盘段文件。

  • 后台进程周期性地执行合并和压缩工作。

-

这种有序的文件结构就是 SSTable。基于这种 SSTable 建立的索引结构称之为 LSM-Tree

原地更新的 B-Tree

B-Tree 是另一种更流行的索引结构,几乎应用于所有的关系型数据库中。



相比于 LSM-Tree 会将数据库分解成几兆大小的块,B-Tree 分的更细,一块只有数 KB 大小,称为页。页是内部读写的最小单元,这种结构与磁盘本身的结构极为相似,因此非常适合用来存储数据。

[image:FA9944AF-0D3A-45F1-BC80-44851E2D8BD7-1231-00005909E6F6EBA6/Attachment.jpeg]

在 B-Tree 中,每一个页都是一个节点,除了叶子节点外,其他节点都会包含一定数量的键,键之间会有指针指向下一层节点,即键的范围所代表的索引节点。直到叶子节点获取真正的值(这个值可以是实际的数据,也可以是其他索引的指针)。当有数据写入时,首先搜索包含对应键的叶子节点,然后更新并写回磁盘。如果是新增键,而页中空间不够,该页就会被分裂成两个半满的列。



B-Tree 通过控制一个节点的子节点数量(分支因子)来控制它的深度,因此查询操作至多遍历3到4层就能获取结果。



针对数据库崩溃的情况,B-Tree 的做法是预写日志(write-ahead log,WAL),也叫重做日志。每次数据修改都需要先写 WAL 然后再更新数据。



B-Tree 和 LSM-Tree 的对比

LSM-Tree 能够承受更高的写入吞吐量,原因在于它可以将 SSTable 压缩并顺序写入磁盘,而不必重写树中的页。这样工作模式也会具有较低的写放大,缺点则是读的开销会相对较大,而且后台运行的压缩进程会影响到主线程,需要一定的控制。



B-Tree 的深度控制决定了它的读开销相对稳定,而且数据更新是直接作用在页上,因此可以实现非常强大的事务隔离机制。缺点是写开销有时过大(分裂页,合并页),且磁盘碎片过多。



索引中的值

上面说的索引的值是一个文件的偏移量,这依赖于数据的顺序存储。而索引也可以存储其他地方行的引用,存储的具体位置被称为堆,而不是依赖于特定的顺序。使用堆的好处是更新值会非常高效,而且建立多个索引时可以避免复制数据。



有些情况下从索引到堆的额外跳转会让读开销过大,因此可以将数据直接存储在索引里,这样的索引被称为聚集索引,比如 mysql 的主键。二级索引直接聚集索引。



内存数据库

随着内存的价格下降,纯内存的数据库也发展起来了。得益于内存存储自由度,内存数据库可以实现各种各样的数据结构。反直觉的一点是,内存数据库的性能优势并不是免除了磁盘 IO,因此磁盘数据库也是有内存缓存的。内存数据库真正避免了的是用写磁盘的格式对数据进行编码的开销。



另外虽然内存是易失性存储,但也会有各种各样的手段去持久化内存中的数据以便崩溃后恢复,比如内存快照,记录日志等。

针对 OLAP 的列式存储

数据仓库的表通常会有很多列(大于 100),而每次访问通常只需要取其中的几列,按照传统的行式存储会有极大的性能浪费。反而是列式存储会很合适。



列式存储依赖于一组文件,每个文件都存储着一列的所有值,查询时指定了哪些列,就只需要单独去读取特定文件即可。而且同一列的数据通常重复度极高,有些列甚至只是枚举值,因此列式存储的压缩效率也高得可怕。



由于列示存储的特性,给数据库建立索引是需要冗余的,单独给一个文件排序没有意义,需要给所有文件一起排序,而索引存储的值就只能是包含值的列,而不能是指向别处的指针。



总结

本节讲述了数据模型的概念以及不同存储引擎的简单原理



目前主流的数据模型是关系模型和文档模型。关系模型有成熟的声明式 DDL,简单的存储模型,虽然开发时会有一定的约束,但也会解放维护人员的心智负担;文档模型有着足够的灵活度,也意味着开发复杂度更高,数据格式的校验并没有被消除,而是转移到了应用层,好处是数据模型与业务模型相似,可以灵活表达各种嵌套关系;



存储引擎分为两大类,针对事务处理(OLTP)优化的架构和针对数据分析(OLAP)优化的架构。OLTP 面向用户,对数据实时性要求高,需要承接大量请求,每次请求只读取少量数据;OLAP 面向企业内部人员,请求少,但一次请求的数据量极大,对磁盘带宽和性能是巨大的挑战。



OLTP 主要有两个流派的存储引擎:

  • 日志结构流派,它只允许追加式更新文件以及删除过是的文件,而不允许修改文件。写入效率高,读取效率低。

  • 原地更新流派,将磁盘划分为无数固定大小的页,每次更新都会更改页。B-Tree 则是典型代表。

OLAP 需要重点考虑大数量的存储和读写,因此列式存储反而更加合适。



发布于: 2020 年 10 月 22 日阅读数: 55
用户头像

莫黎

关注

还未添加个人签名 2017.11.06 加入

还未添加个人简介

评论

发布
暂无评论
DDIA 读书笔记(2)数据模型的存储与检索