引言

本文为《数据密集型利用零碎设计》的读书笔记第一局部第三章的笔记整顿，也是集体认为的这本书第一局部最重要的内容。本文将会针对目前数据库系统两个次要营垒进行开展，别离是采纳日志型存储构造高速读写的 LSM-Tree 和面向 OLTP 的事务数据库 BTree 两种数据结构比照。

次要内容

本文的次要内容介绍如下：

• 最简略 key/value 数据库考量和拓展，从零开始理解日志型存储构造。
• 索引对于数据库的重要性，哈希索引如何优化 key/value 数据库。
• Btree 数据结构的简略介绍，数据结构和特点等。
• LSM-Tree 日志存储构造 VS Btree 存储引擎，两大阵营的优劣比照。
• OLTP 到 OLAP 的比照，行存储到列式存储构造演进，以及数据仓库呈现和数据分析的演进。

数据库底层设计考量

• 底层存储模式：记录存储的根本设计格局，尽管格局会有不同的设计，然而最终都是以文件的模式存储。
• 查问 / 新增 / 读取 / 批改形式：在内部来看也就是在数据库概念中的 DML 操作，这种操作面对的是客户端，属于对外接口的局部。而从外部来看则是存储数据结构，操作数据结构和并发性能的考量。
• 操作日志：出于持久性的考量，操作日志是不可或缺的因素，也是意外之后数据修复的保障。
• 数据类型：比方 Key/value 存储还是针对行列的存储构造。

key/value 存储构造和哈希索引

要害：#key/value 存储构造解决 #哈希索引优化

从零开始设计一个数据库的存储模式，能够从上面的几个点思考，从存储构造登程咱们看日志存储构造数据库是如何呈现的。

首先是 key/value 数据库数据结构设计第一版，从最简略的 k / v 存储数据库开始理解由此引申出哈希索引的构造：

下面构造有如下的特点：

存储模式 ：次要以 key/value 存储模式，key/value 能够是任何内容。底层应用 纯文本 的模式存储，应用追加形式更新数据，雷同 key 应用最初一次读到的 key 为基准。

读写形式 ：db_set xx 设置数据，db_get xx读取数据，批改一个 key 通过最初一行追加模式，意味着更新和删除操作没有任何的开销，无需关注并发的问题。

查问性能：查找数据的开销为 O(n)，新增和批改的性能都是 O(1)。

追加式解决长处

• 程序写比随机写好很多
• 段文件是追加不可变的，意味着并发拜访和解体复原比拟容易
• 压缩和合并分段能够避免数据文件碎片化问题

最简略的 k / v 模式的数据库造成有哪些毛病？

• 追加对于存储空间的节约，尽管追加对于更新和新增非常方面并且保护老本较低，然而有个显著的问题是存储空间的节约，同时咱们发现其实并不需要存储原始文本的模式，同时数据自身能够通过压缩更加紧凑。
• 查问效率随着数据的收缩而升高，所以须要对于查问速度进行优化，对于查问最简略的形式是引入索引，而对于 key/value 存储模式设计索引最为常见的是哈希索引

对于 Key/value 存储引擎来说哈希是罕用的索引类型，哈希索引应用内存中的哈希表进行实现，键值对的键存储数据须要索引的数值，而值存储偏移量，偏移量通过计算获取存储地位，在原始数据中间接找到相干地位的数据间接读取。

上面是哈希索引对于 key/value 构造数据进行索引优化。

纯文本存储数据收缩如何避免性能变差？

• 分段数据：当追加到肯定水平之后则写入一个新的文件。
• 压缩段：将最新的数据进行压缩存储，因为应用追加新增形式，能够间接抛弃旧数据。
• 段压缩和多段合并：压缩与合并的过程没有特定布局，取决于数据结构和存储构造的抉择。

如何避免性能变差：

哈希表和段进行绑定，一个段对应一个哈希表，同时执行段压缩和多端合并，保障脏数据及时清理，最初肯定在内存中引入哈希表进行保护。

理解了大抵思路之后，如何进行具体优化？

1. 压缩合并存储：为了让存储数据更加紧凑同时没有节约，定期对于追加数据进行合并压缩是必要的，同时数据分段也能够进步线程并发读写性能。
2. 数据分段：留神数据分段是联合压缩合并一起解决的，当压缩合并存储的数据达到一定量的时候须要对于数据进行分段解决，目标是避免单文件过大同时能够进步索引的搜寻效率。
3. 哈希表：引入哈希表构造，在数据行上加一层索引目录，能够放慢查问性能，索引的 key 存储的是键须要保障惟一，而 value 则存储了 行记录的指针，这实用于分段的数据结构找到数据存储的地位，通过一次遍历分段间接通过偏移指针查指定数据是否符合要求即可。

下面探讨的存储构造其实存在理论的实现形式，此数据库存储引擎便是：Bitcast。

哈希索引：

哈希索引设计特点

• 文件格式：并没有应用纯文本存储而是应用二进制，应用字节来记录字符串长度，前面存储实在数据。（二进制也有利于压缩）

  • 解体复原：最大的问题是重启之后 哈希表会被开释，如果须要从新建设哈希表须要从新读取段，所以最大的性能开销在扫描段上，有一种优化形式是将哈希表的快照存储磁盘上间接读取。
  • 局部写入记录：应用 SHA 盐值和操作日志对于局部写入记录进行复原，操作日志绝对于数据存储日志更为简略，只须要做增量操作，因为目标仅仅用于存储引擎解体之后能够保证数据的持久性。
  • 并发管制：Bitcast 实际上是一个写线程和多个读线程，数据应用追加形式能够保障多个线程读取，然而只能保障一个线程写入，然而因为数据分段，能够多线程同时改写不同数据段。

通过下面哈希构造的介绍，咱们能够总结出 哈希索引 的几个特点：

• 哈希索引实用于 查问多，增删少 的状况，尽管压缩和分段合并能够解决数据存储效率低的问题，然而对于频繁的增删须要额定的开销从新保护改变哈希表。
• 哈希表 须要在内存 中进行应用，所以受限于内存的大小，当然并不是说磁盘无奈存储哈希表，而是哈希表在磁盘中难以保护和存储。

哈希的索引模式也存在 局限性：

• 尽管哈希表不肯定必须放入内存，实践能够在磁盘上保护哈希表，然而这样做须要大量的 IO，同时哈希抵触须要更简单的解决逻辑。
• 区间查问效率不高，对于范畴查问的解决能力较弱，此时工夫复杂度会进化为 O(n)。

以上是哈希构造对于 key/value 存储的构造的优化。

哈希索引通常的实用场景：

• 点击数：对于数据的准确性要求并不是非常高，然而对于效率要求非常高
• 大量数据的惟一记录查找，留神是大量数据，因为哈希表空间无限。

小结：

咱们能够看到，从一个最简略的 k / v 数据库到哈希索引的构造引入，数据的存储和读取构造逐步变简单，能够看到哈希索引非常适合 key/value 的存储引擎，然而显然它存在比拟显著的缺点，比方只能保护哈希表到内存，并且频繁的更新插入 key/value 对于索引的保护开销也不小，最初最为致命的是范畴查问对于哈希索引是硬伤。

总结：索引特点

• 放慢原始数据的查问速度
• 空间换工夫，须要更多的存储空间以及更长写数据工夫
• 索引很多时候被视为和原始数据离开的构造

通过下面的设计有毛病，针对哈希索引有了第一层进化，那就是 SSTable 和 LSM-Tree。

SSTable 和 LSM-Tree 构造

SSTable #LSM-Tree

概念

在具体的内容介绍之前，咱们须要弄清楚 SSTable 和 LSM-Tree 有什么区别，简略来说 LSM-Tree 是对 SSTable 概念和思维的一个继承。另外须要留神这个构造特点正好解决了 哈希索引局限性 问题，同时 SSTable 并没有摈弃 key/value 这样的存储构造，而是在索引构造上进一步降级。

SSTable 概念

SSTable 起源自谷歌在 2006 年公布的一篇轰动世界的论文，外面的 BigTable 就是 SSTable 和 LSM-Tree 的前身：Bigtable: A Distributed Storage System for Structured Data。如果感觉论文难以了解，能够参考这篇文章了解：

https://blog.csdn.net/OpenNai…

这里挑了其中一些和 SSTable 无关的内容，惋惜的是这篇论文并没有具体的介绍 SSTable 的外部数据结构，在论文第六个大节中介绍了 SSTable 的作用：

BigTable 和 GFS 是什么关系呢？在论文中咱们能够看到一个相似树的构造，其中根节点为主服务器，主服务器负责承受申请，通过治理分片服务器将申请分片到不同的片服务器中，所以从外层看最终干活的是片服务器，实际上片服务器自身只是负责管理本人分片 SSTable，通过非凡索引晓得数据在那个 SSTable 分片中，而后从 GFS 中读取 SSTable 文件的数据，而 GFS 则可能要从多个 chuncker server 外面搜寻数据。

而图中的 metatable 原数据表能够看作是和 SSTable 绑定的相似索引的关系，元数据表的数据是不能被外界拜访的，外界拜访的是元数据对应的 SSTable 分片，这和前面介绍的 LSM-Tree 有着非常相熟的符合关系。

改良与比照

关键点：数据存储形式，索引查找形式改良

SSTable 通常如何工作？

• 写入的时候不写入磁盘而是先写入内存表的数据结构，同时在内存将数据进行排序。
• 当数据结构内存占用超过肯定的阈值就能够间接写入到磁盘文件因为曾经是排好序的状态，所以能够对于旧构造笼罩，写入效率比拟高。并且写入和数据结构改变能够同时进行。
• 读写程序依照 内存 -> 磁盘 -> 上一次写入文件 -> 未找到这样的程序进行查找和搜寻。
• 后盾定时线程定时合并和压缩排序分段，将废除值给笼罩或者抛弃。

SStable 的改良点

上面是 SSTable 绝对于哈希构造的特点：

• 高效合并：合并段的过程更加高效，每一个段都是依照特定程序排序，当呈现多个反复数值的时候能够合并到最新的段，对于旧数据则能够间接舍弃后面的内容。
• 范畴索引优化：内存中哈希表也是有序存储，能够将多个 kv 对应的数据条目一起压缩存储，这样索引条目只须要结尾局部的键值即可，因为后续所有的记录都是有序的。
• 索引优化：比起哈希较为涣散随便的构造，这样的解决就义肯定的读写开销换来更加高效的存储和索引构造，并且能够反对范畴索引扫描。
• 程序读写：数据顺序存储的益处是能够程序读写，防止磁盘的随机读写能够大幅度晋升读写性能

上面是改良过后的压缩过程图：

最大的改变点：压缩合并的根底上对于 SSTable 根底内容进行合并操作。

如何保护 sstable?
首先是数据如何在内存中排序，能够应用红黑树和 AVL 树的构造也能够是任意构造，重点是在内存中实现数据压缩合并和排序的操作。

为什么数据集远远大于内存仍然能够高效？
因为应用排序以及分段合并压缩分段的数据，所以一次加在到内存的数据不须要太多，其实只须要把内存索引表查找某个区间段的数据，而后进行程序查找，因为是依照排序的形式顺序存储的，在段上查找数据集通常能够依据键间接偏移或者依照特定规定二分查找的形式搜寻。

SSTable 和哈希索引的比照：

能够看到 SSTable 在哈希索引的根底上进行优化，应用排序的伎俩尽管会损耗肯定的写入耗费，然而换来的是更高效率的范畴查问以及更高效率的压缩存储模式。

哈希索引：

• 索引查问效率非常高
• 内存中保护，磁盘 IO 开销很小
• 十分实用于 Key 频繁更新的场景

SSTable：

• 利于磁盘保护索引和程序读写，
• 优化范畴查问。
• 将范畴搜寻的查问效率优化至 O(logN)的程度

理论案例和利用

全文索引：

全文索引尽管比 key/value 简单很多，然而实质都是相似的，某些数据保护仍然基于 key/value 形式存储，比方词条的映射关系应用的 SS Table 进行存储，在内存中排好序存储，并且须要的时候进行合并。

LevelDB 和 RockDB：

LevelDB 和 RockDB 是最为典型的 LSM-Tree 实际案例，尤其是 LSM-Tree 作者刚好又是谷歌的工程师，深刻理解这两款经典 LSM-Tree 实现案例能够对于 SSTable 的设计和利用有更深的理解。

LSM-Tree 的代码非常简单易懂，难懂的中央作者也给了正文，对于我这种 JAVA 开发者也能理解大略。

SSTable 的弊病

• 最大的隐患是在压缩合并分段的时候不能进行数据的读写，否则数据一致性会存在问题，这对于吞吐量要求高的零碎很难承受。
• 压缩另一个问题是对于带宽的占用十分高，压缩数据量越大，带宽耗费越高，容易阻塞大量的读写申请。
• 如果压缩速度跟不上写入数据，那么就会呈现大量未压缩数据沉积状况，长期累计容易造成磁盘空间有余，然而 sstable 的数据结构决定了追加写入是不受管制的，须要内部力量监控。

Btree 存储构造

简介

Btree 数据结构自 1970 年被提出之后，被宽广的数据库使用者承受 BTree 目前不太可能被新技术淘汰，而日志索引构造的 Lsm-Tree 将来前景非常可观。

Btree 特点

和 SSTable 仅仅只有一点相似：B-tree 保留按键排序的 key/value 对，这样能够实现高效的 key-value 查找和区间查问，除此之外没有其余的类似点。

上面是 Btree 的特点：

• 和日志存储构造不同的是，Btree 将数据分为固定的数据页，每一个数据页固定大小，通常为 4KB，InnoDB 一个数据页固定设置为 16KB。
• 更新数据在原构造上进行更新，也就是应用新数据页笼罩旧的数据页，所以更新的代价绝对于日志构造要大很多的。
• 数据页存在和磁盘对应的惟一标识，同时数据页之间通过链表指针串联，然而指针存储的不是内存上的地址，而是磁盘的地址，
• 新增数据如果数据页内容有余须要进行页决裂，同时父节点须要蕴含新决裂的页，而页决裂很容易造成磁盘碎片和数据的排序，同时因为外部须要维持数据排序开销不小。

为什么数据页要固定大小？
这和磁盘的读写无关，传统机械硬盘为 512b 最小单位，而 SSD 通常为 4KB 最小单位读写，所以数据页设计为和磁盘兼容的模式存储有利于 程序读写，同时能够最大化利用磁盘空间。

Btree 优化和可改良点

• 压缩存储：应用缩略的键信息，因为对于树两头一个数据行来说只有提供开始和完结的地位即可，这样能够在无限的数据页存储更多的数据。
• 数据页排序：尽管数据页能够存储在不同的磁盘空间，然而对于某些须要范畴查问的状况下须要对于磁盘进行程序查找，而此时数据页的随机查问就会呈现问题
• BTree 到 B + 树的优化，优化的形式也非常简略易懂，在各层都加链表放慢索引查找，这种甚至不能叫优化只能说是改良。
• 应用 写时复制 代替笼罩页的形式，在批改页的时候不对原数据改变，将写入新的父页并且更新旧援用。

Btree 和 LSM-Tree 比照

Btree 的读写速度快于 LSM-Tree，因为一次 IO 读写能够索引到大量的数据页，而 LSM-Tree 须要逾越多个压缩段才可能找到数据。然而 LSM-Tree 的读写速度要快于 Btree，同时存储效率要比 Btree 要高，因为压缩和合并分段之后数据间隙之间根本不存在数据间隙碎片。

所以 LSM-Tree 实用于读写多的场景，而 Btree 因为须要高效查问设计上要简单十分多所以为了服务查问性能能够容忍写入和删除的额定开销。

单纯比照数据结构可能比拟干燥，这里从老外的网站上找了一份 Mysql 和LevelDB的比照，这两款根本能够代言 Btree 和 LSM-Tree 这两种数据结构了。能够看到 LevelDB 要比 Mysql 的呈现早晨不少，这和 BigTable 有着密切关系，也和网络时代的倒退和互联网的用户量指数回升有关系。

OLTP 和 OLAP

特色

单从名字的辨别，这两个类型别离针对 事务 和针对 剖析，由此引发了不同的齐全不同的数据结构和存储模式，同时侧重点和服务范畴不同，留神这两者并不能说谁劣势谁劣势，因为 OLAP 说白了是在 OLTP 上演变而呈现的。

如果看不清，能够看看甲骨文提供的一个表格：

OLTP：在线 事务 解决。用于解决数据量较小的事务为主的业务，要求的是高吞吐高响应，个别为 web 应用程序，次要面向宽广用户群体，实用于解决生存中 80% 左右的业务和零碎问题。

OLAP：在线 剖析 解决。次要基于大数据量的数据搜寻和汇总，随着工夫变动而进行数据分析进行数据撑持。个别呈现在中大型公司的较大型我的项目中。

数据仓库

事务型号数据库这里不再赘述了，置信大家也很相熟，这里说说数据仓库是什么？

数据仓库是上世纪 90 年代被提出的放弃基于传统事务 OLTP 构造的数据库剖析，转为应用单个数据仓库进行数据分析的形式，简略了解就是讲数据和业务剥离，只保留数据局部进行存储，通常为了不便剖析会应用 [[《数据密集型零碎设计》列式存储]] 引擎和后面提到的 [[《数据密集型型零碎设计》SSTable 和 LSM-Tree]] 数据结构。

劣势

数据仓库有上面的劣势。

• 面向主题：数据仓库能够高效剖析对于特定主题或职能畛域（例如销售）的数据。
• 集成：数据仓库可在不同起源的不同数据类型之间建设一致性。
• 绝对稳固：进入数据仓库后，数据将保持稳定，不会产生扭转。
• 反映历史变动：数据仓库剖析着眼于反映历史变动。

存储模式

数据仓库个别不存在于小公司，因为基本没有那个资金撑持也没有，而是面对较大公司多达 10 几个零碎数据规模的存在模式，所以对于很多人来说可能就是围观看造火箭，看懂了如同也没啥价值。

结构图

上面是整个数仓零碎的构造

进化

数据仓库到了当初又呈现了进一步的转变，大数据也被分为了很多个方向，这些都是战将来的货色，这里简略提炼一下概念：

• 数据挖掘
• 预测和统计
• 人工智能和机器学习

数据湖

留神数据库并不是指比数据仓库大很多倍的数据仓库或者数据库集群，他是齐全不同的概念，数据仓库是曾经被整顿
数据湖次要用于存储大量大同小异并且没有进行分类筛选的数据，数据湖对于剖析人员来说是最为自在的一种，能够形象看作垃圾池掏金子，收益和代价并存，更多时候是把数据湖转为数据仓库。

利用

• 数据库 比拟风行的有：MySQL, Oracle, SqlServer 等。
• 数据仓库 比拟风行的有：AWS Redshift, Greenplum, Hive 等。

剖析模式

对于数据仓库的分析模型，现今通常有两种形式：星型模型和雪花模型。

星型模型

星型模型也别叫做纬度模型，这个模型针对的是非强依赖的数据关系剖析，比拟典型的如电商零碎和购物网站，尽管商品，订单，库存，广告等等看似没有什么关系，然而这些数据就像是星星一样扩散，有着千头万绪的间接依赖或者间接依赖关系。
星型模型的数据更像是星星和月亮的关系，外围通常位于两头，而周围分布关系模型。

雪花模型

雪花模型要比星型模型设计上标准很多，也是对于维度模型的进一步拆分，比方对于商品表引入更加细分的品牌和分类进行更进一步的细分，也相似超市的商品分类。

小结

这一节点从 OLAP 讲到数据仓库，再讲到两种支流的剖析形式，星型模型和雪花模型。
当然这些内容都是简略介绍，读者能够依据本人感兴趣的点进行深刻和相熟。

列式存储

介绍

对于传统的业务数据库并且用户量较小的公司来说，通常应用关系型数据库，而关系型数据库根本以 Btree 数据结构作为外围，这些数据库根本都是行存储，行存储比拟合乎了解思维，然而实际上对于数据分析而言，行数据往往会造成长时间的工夫期待，并且如果须要对于数据进行施行剖析作为业务决策，应用行存储剖析显然零碎开销是无奈承受的，由此引入了[[OLTP 和 OLAP]]。

之前提到的内容都是行式存储，有些状况下列存储更利于数据管理，特地是对于事务关系数据库行存储构造不利于繁多列剖析，比方咱们想要存储某一分类的价格趋势，行存储须要扫描所有行求和，而列存储间接把一整列拿进去求和即可，两者效率天然不必多说。

列存储构造特点

• 所有列值紧凑存储在一起
• 通常比行存储更有利于了解
• 可用于非关系型数据库，当然也能够用于关系型数据库。（反过来行存储就不实用这条规定了）

列压缩

列式存储意味着把同类数据压缩到不同的段，这对于存储构造来说是无利的，通常列压缩在数据仓库应用位图的模式存储。

因为列存储的都是同一个数据类型的数据，所以能够针对不同的数据类型进行优化存储，这样也意味着比行存储更少的空间压缩更多的数据，比方对于一些整型数据在压缩存储的时候能够应用位模式存储。也就是间接存数字的二进制位编码，列查问的时候进行位操作即可。

上面是一个典型的列存储和压缩的例子：

存储位图可能人不是很好了解和计算，然而计算器来说就不一样了，位元算操作远远高于数学运算。

另外除开列压缩以外，列的存储还以一个 列族 的概念，列族存在于 Cassandra 和 HBase 这两个数据库，而列族这个概念继承自 BigTable。
然而咱们之前介绍 [[《数据密集型型零碎设计》SSTable 和 LSM-Tree]] 讲述根本还是行存储形式和实现。

列族：其实指的是 把一行中的所有列和行主键保留到一起，并且不应用列压缩的模式存储。其实这种用行转列根本就能够实现，所以列族严格意义上仍然是行存储的变体，和真正的列存储还是存在差别的。

列排序

绝对于行存储，列的排序其实并没有多重要，因为他不关怀数据归属而是数据的整顿，和 [[SSTable]] 一样，列排序最好的形式也是通过追加压缩合并的形式，而后利用索引和一些人造的有序数据结构实现存储。

留神列排序个别不会针对单列进行排序，因为没有多少意义，至于起因这里仍然强调单列没有方法晓得数据的归属。

列排序的第一个劣势是能够对列的反复值进行压缩，比方性别通常只有男和女，这时候反复的列存储是没有必要的。

列排序的另一个长处是多列排序能够疾速的定位某一列的极值状况和不便疾速的分组或者过滤查问。

C-Store 最早引入了 一 种改良想蓓，井被商业数据仓库 Vertica。

最初，面相列存储通常会具备多个排序程序，然而多列排序很难保护，所以更常见的状况是引入二级索引保护，和行存储的索引保护不同，行存储的二级索引通常指向数据行（或者像 InnoDB 一样指向主键，不过这种解决比拟非凡），列存储二级索引通常指向值。

视图

列存储中一个非常重要的优化个性是引入试图对于长期查问进行减速，数据仓库中的 SQL 中常常会碰到聚合函数的查问通常会想到应用缓存进行存储。
列存储的缓存被叫做规范视图，留神这个视图并不是逻辑长期构造，而是实在物理视图，列存储相比行存储对于物理存储的数据无效和可用性高很多，OLTP 零碎不实用物理视图次要起因是缓存生效很快并且须要应答低提早高响应的查问，而数据仓库因为次要做数据分析数据动态状况更多。
视图的非凡状况叫做数据立方体，数据立方体的概念相似于列存储的“行聚合”和“列聚合”穿插查问的形式：

从下面的图能够看到，数据分为多个维度进行剖析和查问，通过多维度角度能够把多个分类模型的数据放到一起进行穿插统计，这对于数据分析人员来说无疑省去大量的筹备工作，将这种数据立方物化之后的查问效率也非常高。

物化数据毫无疑问让数据查问更快，因为数据曾经事后筹备，然而数据立方的毛病和缓存的毛病一样是不能频繁改变，否则失去其自身意义。

总结

次要的内容集中在 Key/value 的数据库倒退和哈希索引，以及后续的 Btree 和 LSM-Tree 上，能够看到 BTree 呈现最早然而经验了 30 多年仍然长盛不衰，一时半会应该还没有更优良的数据结构代替，而 LSM-Tree 则比拟合乎将来和古代的倒退潮流，因为他存储模式更自在，并且非常适合用于列式存储和列压缩以及数据分析，总之这篇笔记更多的是让读者理解更广大的数据视线。

写在最初

这篇除开书本的内容之外，集体对于其余内容做了一些补充，如果有不同的认识欢送探讨，如果文中有谬误欢送批评指正。

参考资料：

• https://blog.csdn.net/OpenNai… BigTable 翻译和解读，讲的不错
• https://db-engines.com/en/sys… 文中图表起源