设计数据密集型应用(一)，DDIA

零、开篇词

欢迎各位，给大家分享一下自己最近读的书，ddia ,全名叫做：design data-intensive application 直译为：设计数据密集型应用；或者叫做，数据密集型应用的设计

🎈为什么分享这本书🎈

我相信在场的各位一定历经过这样的场景：春节档档期一下子上映了很多场电影，一场电影要不要去看，你是如何决策的？对于我来说呢，通常都是先看一下豆瓣评分，如果高的话，就买票入场，对吧，所以为什么选择分享这本书，那就不得不说下这本书

0.1-关于ddia的溢美之词

可以看到，这本书的评价惊人的高，居然达到了 9.7分的高分，有的同学可能觉得9,7分并不是一个很高的分数，来看下面这部是个码农都知道的书《算法导论》，这本书的评分是多少呢？ 9.2分，当然这是一个很高的分数，但是ddia 比这个高度还要高 0.5分；有的同学可能还是不能很直接的get到这本书的魅力，OK，我们来和豆瓣电影评分类比一下，要知道豆瓣中电影评分最高的也就是9.7分，也就是大名鼎鼎的，我相信各位应该都看过《肖申克的救赎》

甚至ByteDance 这家公司将这本书写进入interview doc。所以结论来了，DDIA , 你值得拥有

0.2-关于作者

接下来，我们一起来看下这本书的作者，上图中的靓仔就是了

一 、整书大纲

下面是整书的一个脉络：分为3个部分12个章节，

1.1-3部分12章节

1️⃣数据系统的基石

主要讲述了数据系统底层的一些概念，无论是单机上的单点数据系统，还是分布在多机器上的分布式系统。这个讨论的范围是 单机或者多机器，区别于第二部分仅谈论多机器上的分布式系统

• 1：可靠性、可扩展性、可维护性 在开发一个应用的时候，必须要满足各种功能需求才能称之为有用，除了功能需求（也就是能够实现什么功能）还需要一些非功能需求，也就是通用属性，比如说可靠性1，可扩展性2，可维护性3> [1] 意味着即使发生故障，系统也能正常工作> > [2] 意味着即使在负载增加的情况下也有保持性能的策略> > [3] 有许多方面，但实质上是关于工程师和运维团队的生活质量的
• 2：数据模型与查询语言 这个是从使用者的角度出发，⚠️注意这个视角很重要 描述数据录入数据系统的格式，已及如何将存入的数据取出来。涉及关系模型，文档模型，图模型。比如说对于关系型数据库来说，数据模型 = DML ；查询语言 = DSL(一种声明式的查询语句) 。阐述了关系模型的各个挑战者挑战关系模型的霸主地位最终落败的过程，数据模型发展至今关系模型依然王者
• 3：存储与检索 这个是从数据系统的角度出发，描述数据系统如何存储我们录入的数据，以及在我们需要这部分数据，存储系统如何精准、快速的定位到目标数据。这里注意区分2章节和3章节的角度
• 4：编码与演化 随着时间推移，数据系统由于功能的迭代，需要对初始涉及的数据模型(schema)进行更改，那么如何处理数据模型的前后兼容问题，就是这个章节要讨论的问题

2️⃣分布式数据

多台机器参与数据的存储和检索，数据系统所面临的一些挑战

• 5：复制 ： 同一份数据，多个拷贝/副本
• 6：分区 ： 同一份数据，分割成多块
• 7：事务 ： 主要介绍 事务，ACID，隔离级别等内容，个人觉得这部分内容是重点也是难点
• 8：分布式系统的麻烦 ： 在极端情况下，分布式系统黑暗的诸多问题，看完这一章节，你会觉得你所处于的环境真的是太幸福了
• 9：一致性与共识 ：分布式数据系统如何去实现一致性和达成共识，从而避免类似于 brain split 的问题，这一章节会讨论在构建容错分布式系统的时候使用到的 算法和协议(比如Raft、Paxos、ZAB)，一定会让你有所收货

3️⃣派生数据

主要讨论衍生(派生)数据：所谓衍生数据 是以输入数据输出新的数据，输出是衍生数据（derived data）的一种形式 ，流处理和批处理都会产生衍生数据

• 10：批处理 ： 有界数据的处理
• 11：流处理 ： 无界数据的处理
• 12：数据系统的未来 🤣

🎈过度🎈：以上呢，就是整本书的一个简短的概括，下面的内容就是我基于书中的内容做的一些总结，已及自己的一些启发

1.2-计算密集与数据密集型应用区分

下图是应用程序的简要分类：

🅰️ 首先是计算密集型应用，这类应用的瓶颈是算力，比如进行气象预测，对于这类应用我们处理的方式就是不断的提升计算机的算力，比如增加CPU的核数，增加内存等

🅱️ 再有就是数据密集型，这类应用的瓶颈是：

• 数据量，Volume
• 数据的复杂性，Variety
• 数据的变更速度，Velocity

对于数据密集型应用，我们通常会使用标准的组件来处理：

1️⃣ 存储数据，以便自己或其他应用程序之后能再次找到(数据库 database)

2️⃣ 记住开销昂贵操作的结果，加快读取速度(缓存 cache)

3️⃣ 允许用户按关键字搜索数据，或以各种方式对数据进行过滤(搜索索引 search indexes)

4️⃣ 向其他进程发送消息，进行异步处理(流处理 stream processing)

5️⃣ 定期处理累积的大批量数据(批处理 batch processing)

二、第3章节-存储与检索

那么在第一部分，第三章节，是存储与检索的内容，也就是说：数据库在最基础的层次上完成的2件事情：

🅰️ 当你把数据交付给它的时候，它如何将数据存储起来

🅱️ 当你向数据库索要数据时，它如何将数据返回给你

由于事务性负载和分析性负载的存储引擎之间存在着很大的差异，这两类的存储引擎我们分开来描述

在事务处理方面：

• 日志结构存储引擎 ；从最简单的数据库实现append-log(无索引日志)到 LSM(日志结构合并树) 树的演化历程
• 面向页面的存储引擎 ，典型的比如B-Tree

在分析性存储引擎方面，我们谈谈

• 数据仓库
• 星型模型&雪花模型
• 列存储

2.1-无索引日志

我们来看下 世界上最简单的数据库 是如何实现的

• 首先来一个插入操作
• 再来一个更新操作
• 最后，来一个get 操作

那么这个最简单的数据库底层是如何进行数据的摆放的呢？可以看到

db_set()

就是一个非常简单的追加4，这简直不是简单，甚至可以说是简陋但正是由于这种设计使得写入变的非常的高效，代价就查找的开销是 O(n) ，O(n)的复杂度，这意味着如果数据量增加一倍，查询响应时间将会增加一倍。也就是说查询时间和数据量之间的关系是线性相关的。所以我们需要更快的得到目标结果，那么如何去提升数据的查找效率？

[4] 追加是顺序写，顺序写入速度>>随机写入

2.2-如何提升查找效率？

当我们还在上小学的时候，可能也面临过类似的问题，假设说现在有2个小学生，忘记了囧字怎么写，想要用新华字典查询一下：

• @冰雨 同学使用的是一本没有目录的字典(比如说康熙字典)
• @流川同学 使用的是一本有目录的字典(现代新华字典)那么谁最后能更快的获知 jiong 字的写法呢？直觉告诉我们流川同学有较大的概率最快获取到 joing字的写法。

可以发现现代字典的特征就是都会有一个目录，这个目录是在原始数据之外维护的额外的数据，正是由于目录的存在，使得@流川同学能够更快的获取到目标数据。其实这个目录，其实就相当于英文中的 index , 而 index英译就是索引，至此我们可以得到一个结论：

索引 是在原始数据之外维护的额外的数据，索引 可以加速数据访问

🎈Post Script🎈

由于需要在原始数据之外额外维护一份数据，这就无形增加了空间复杂度，在计算机领域中，时间和空间就像鱼和熊掌一样，不可兼得，降低时间复杂度的方式就用空间换取时间； 可以说这个问题在计算机领域是一个绕不开的话题，如何去提升查找效率这个问题的另外一种问法是：给我一个更低的时间复杂度的实现，那么常见的比O(n) 还低的时间复杂度就是 O(1)，O (log_n) 两个，O(1)的时间复杂度，我们很容易就会想到哈希表，因为哈希表的时间复杂度默认是O(1)$，接下来我们尝试构建哈希索引来提升查询效率

2.3-内存中构建hash索引

那么对于存储于磁盘中的数据，我们在内存中维护一个HashMap，维护key和value 的偏移量，这样一来，我们就能够迅速的定位到目标数据，比如我们想要find key = 42 的数据，通过查询内存中的HashMap表，获得偏移量64 ，所以可以直接定位到数据，而不在需要从头开始遍历

随着我们不断的在文件末尾追加文件，磁盘中的单个文件也会越来越大，甚至单个文件可能吃掉整个磁盘的存储。所以，如何用有限的存储存储更多的数据？ 也就是说如何避免磁盘的空间的消耗？

2.4-压缩与分段合并 & hash索引的局限性

我们解决的方案是：

• 分段存储：也就是说当追加文件的size达到了一定的阈值之后，我们重新写入新的文件
• 压缩：丢弃重复的键，保留每个键的最新值

如上图中原本12个键 压缩之后之后3个键，整个文件的size降低。如何进一步改进？

在执行压缩的同时，可以将压缩之后的段合并。如 Data file segment 1 和 Data file Segment 2 在压缩了之后，进行了一个合并操作，得到了 Merged Segment(比如mew 这个键压缩合并的过程)。压缩和合并对用户是没有感知的，由后台进程完成，在合并的时候由旧的段文件提供读写请求，在合并完成之后，读写请求转化为新的合并后的段

那么由于hash表本身的特性，也会导致我们构建的哈希索引有一定的局限性，比如：

🅰️ 哈希表是存在于内存中的

🅱️ 范围查询是软肋

那么如何突破哈希表的局限性，寻找更好的索引结构？

2.5-SSTable 排序字符串表

这个问题的答案是：排序字符串表，也就是SSTable5, 也就是：在段文件中，对键值对的序列排序。比如上图中，对于已经排好序段文件1，段文件2 ，段文件3 ，进行压缩和合并，而且，在合并之后，仍然需要保证合并之后的段文件有序，所以我们需要一个合适的排序算法：那么这个排序算法是什么呢？ 是冯诺依曼发明的归并排序算法；merge sort 的优势就在于：内存在小于被排序文件大小的时候，仍然可以将排序完成

[5] SSTable : Sort String Table

使用SSTable可以有效的突破内存限制和解决范围查询的问题。如下图中我们查找，handiwork 的过程，可以发现不是在内存中保存所有键的索引，由于SSTable维护了顺序关系，我们的索引以稀疏索引的方式存在于内存中。同时，可以支持范围查询

2.6-LSM 日志结构合并树

在前面的讲述中，我们默认了落盘段文件是有序的，在落盘写入段文件之前，如何按键排序？考虑到效率问题，最初的的写入一定是在内存中的，到达一定的时间阈值或者是内存阈值的时候，在进行落盘形成 SSTable，那么内存中选择什么样的数据结构？

1️⃣ 内存表，为什么是AVL-Tree ？

• 首先平衡二叉树本身就是二叉搜索树，而二叉搜索树中序遍历就是顺序结构，可以直接落盘形成SSTable
• 由于平衡特性，可以保持树的结构，而不是退化成链表，使得查询的时间复杂度维持在 O(logN), 而且对于新加入的数据，平衡二叉树通过左旋或者右旋的方式保持平衡性

2️⃣ 落盘，也就是平衡二叉树的中序遍历方式落盘

3️⃣ 读取请求，先请求内存，然后查询磁盘段

4️⃣ 压缩和合并： 后台压缩合并段文件，并丢弃覆盖/删除旧值

5️⃣ 防止数据库崩溃：磁盘保留一份单独的日志，每个写入都附加到磁盘上，防止数据库崩溃，内存数据丢失

那么使用这种结构的组件有哪些呢？

Cassandra6、Bigtable、HBase、Elasticsearch、Solr7、Hologres

[6] 卡桑德拉，Apache Cassandra是一套开源分布式NoSQL数据库系统。它最初由Facebook开发，用于改善电子邮件系统的搜索性能的简单格式数据，集Google BigTable的数据模型与Amazon Dynamo的完全分布式架构于一身

[7] 和ES一样是一个企业级的搜索索引

这种先内存排序，再落盘排序的结构，就是LSM(Log-Structure Merge Tree 日志结构合并树)结构

2.7-面向页存储引擎

接下来我们介绍另外一种存储引擎：面向页面的存储引擎，比如B 树，B树会将数据库分解为固定大小的块或者是页面，传统大小为4K而且一次只能读取或者写入一个页面，和LSM对比一下

下图展示了面向页面的存储引擎是如何查询数据的

分支因子：在B树中一个页面中对子页面的引用数量。面向页面的存储引擎发展至今已经非常成熟了，伴随着上世纪70年代关系型数据库的发展至今

2.8-向页面添加元素

如何向B树中增加一个数据，如下图：

2.9-比对LSM树 和 B树

最后我们来一起对比一下LSM树和B树，也即面向日志的存储引擎和面向B树的存储引擎的优劣势

2.10-OLTP&OLAP 和 数据仓库

数据库在历史中主要为两种系统提供支持

🅰️ 在线事务处理系统，即OLTP

🅱️ 在线分析系统，即OLAP

下表中对比了两者之间的区别

起初的数据库，能够同时应对以上两种查询的情况，无论是OLTP类型的查询，还是OLAP类型的查询，单一的数据库的表现的都很好，也就是说：也就是说两者是一家的。 OLAP通常会要求 高可用与低延迟，为了保证业务系统的稳定运行，所以DBA会密切关注他们的OLTP数据库，他们通常不愿意让业务分析人员在OLTP数据库上运行临时分析查询，因为这些查询通常开销巨大，会扫描大部分数据集，这会损害同时执行的事务的性能。可以见得，OALP和OLTP 这对亲兄弟发生了矛盾，矛盾会最佳解决方案就是分家。在二十世纪八十年代末和九十年代初期，渐渐地很多公司有停止使用OLTP系统进行分析，而是在单独的数据库上运行分析。这个单独的数据库被称为数据仓库(data warehouse)。因为最初的数据仓库是从关系型数据库中独立出来，只存储关系数据，而且是面向数据分析，BI(商业智能)的，只是到了后来随着大数据时代的到来，数据仓库才慢慢变的越来越像数据湖8 (就是各种数据都跑往数据仓库里面塞)

[8] 数据湖：是指使用大型二进制对象或文件这样的自然格式储存数据的系统[1] ，数据湖可以包括关系数据库的结构化数据(行与列)、半结构化的数据(CSV，日志，XML, JSON)，非结构化数据 (电子邮件、文件、PDF)和 二进制数据(图像、音频、视频)

数据沼泽：数据沼泽 是一个劣化的数据湖，用户无法访问，或是没什么价值

又或者说，数据湖是下一代数据仓库，从OLTP数据库中提取数据，转换成适合分析的模式，清理并加载到数据仓库中，因此数据仓库包含公司各种OLTP系统中所有的只读数据副本。下图是一个简要的示意图：

2.11-数据仓库系统组件

我们来看一些比较出名的商业数据仓库系统，尽管他们是冠以出名的商业数据仓库系统，但是其中"商业"两个字可能是太贵，导致我们大多数从事数据仓库相关工作的人，其实并不知道：

• SQL - Server 使用两套不同的存储和查询引擎来应对OALP和OLTP环境
• Teradata 天睿
• Vertica 维蒂卡
• SAP HANA SAP 汉那
• ParAccel 帕加速

相对而言，我们更喜欢免费的开源产品，下面是一些SQL-on-Hadoop 项目：

Hive-SQL、Spark-SQL、Flink-SQL、Presto、Druid、Kylin、Impala

2.12-雪花模型

在OLTP系统中，可用的数据模型很丰富，比如大类上分为

🅰️ 关系模型

🅱️ 新的非关系模型，No-SQL模型

• 文档数据库模型
• 图形数据库模型

相对于OATP系统来说，OLAP系统的数据模型多样性就少的多，数据仓库大多使用一样的公式化模型：星型模式|星型模型(也叫维度建模) 如下图：

1️⃣ 模式的中心是一个所谓的事实表，事实表的每一行代表在特定时间发生的事件(这里，每一行代表客户购买的产品)

2️⃣ 事实表中的一些列是属性，例如产品销售的价格和从供应商那里购买的成本(允许计算利润余额)，通常是数字等可统计指标

3️⃣ 事实表中的其他列是对其他表(称为维表)的外键引用，由于事实表中的每一行都表示一个事件，因此这些维度代表事件的发生地点，时间，方式和原因

4️⃣ 事实表格有100列以上，有时甚至有数百列，快手宽表列长达1000+列

5️⃣ 星型模型进一步的扩展是雪花模型，也就是基于维度表进一步拆分

当表关系可视化时，事实表在中间，由维表包围；与这些表的连接就像星星的光芒，所以这模式被命名为：“星型模式”

2.13-列式存储

在前面的存储结构中，我们介绍了

🅰️ 基于日志的存储：日志结构学派

🅱️ 基于页面的存储：就地更新学派

然而，典型的数据仓库查询一次只访问较少的列，如果使用行存储的话，面向行的存储引擎仍然需要将所有这些行(每个包含超过100个属性)从磁盘加载到内存中，解析它们，并过滤掉那些不符合要求的条件。这可能需要很长时间。面向列的存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如下图

可以观察到红色框选出来的值序列，他们是重复数据，而重复数据是压缩的好兆头。我们根据列中的数据，可以使用不同的压缩技术来进一步降低对磁盘吞吐量的需求，在数据仓库中特别有效的一种技术是位图编码(类似哈夫曼编码)，如下图：

🤣以上是《设计数据密集型应用》读书笔记的第1部分，欢迎吐槽，欢迎关注

更多精彩内容，欢迎关注作者的微信公众号：stackoverflow