《数据密集型应用系统设计》
2022-11-07 14:08:30 25 举报AI智能生成
《数据密集型应用系统设计》是一本关于如何设计、构建和管理大型、高性能、高可用性的数据处理系统的指南。本书详细介绍了在处理大量数据时，如何有效地利用硬件资源、优化算法和架构，以及如何处理数据的存储、查询和分析等方面的问题。书中还探讨了如何确保系统的稳定性、可扩展性和安全性，以及如何应对不断变化的业务需求和技术挑战。无论你是数据科学家、软件工程师还是IT管理者，本书都将为你提供宝贵的指导和实践经验，帮助你在数据驱动的时代取得成功。
作者其他创作
大纲/内容
可靠、可扩展与可维护的应用系统
可靠性
即使发生了某些错误，系统人可以继续正常工作
故障来源：硬件故障、软件错误、人为失误
可扩展性
响应时间没增加100ms销售额会下降1%，1s的延迟增加等价于客户满意度下降16%
可维护性
运维简单：运维更轻松
可演化性 ： 易于改变
简单性：简化复杂
消除意外复杂性最好的手段是抽象
一个应用必须完成预期的多种需求
功能需求：该做什么
非功能性需求：安全性、可靠性、合规性、可伸缩性、兼容性
数据模型与查询语言
数据模型
关系型
文档型
图模型
查询语言
SQL
MapREDUCE
MongoDB聚合管道
Cypher
SPARQL
Datalog
数据存储与检索
数据库值需要做两件事：向它插入数据时，它就保存数据；之后查询时，它应该返回那些数据
两种存储引擎：日志结构的存储引擎、面向页的存储引擎
数据的核心： 数据结构
索引背后的基本思路都是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据
哈希索引
SSTables：要求key-value对的顺序案件排序，这种格式称为排序字符串表(SSTable)
LSM-Tree : 基于合并和压缩排序文件原理的存储引擎通常称为LSM存储引擎
B-tree
几乎是有关系型数据库中的标准引擎实现，许多非关系型数据也用到
B-tree将数据库分解成固定大小的块、页(传统上是4k)，页是内存读/写的最小单元
每个页都可以使用地址/位置标识，这样可以让一个页引用另一个页，类似指针，不过指向的是磁盘地址，而不是内存。
某一页被指定为B-tree的根，每当查找索引中的一个键时，总是从这里开始，改业包含了若干个键和子页的引用，每个子页都负责一个连续范围内的键，相邻引用质检的键可以指示这些范围质检的边界
B-tree可靠性机制：预写日志(write-ahead log,WAL),也称重做日志：一个仅支持追加修改的文件，每个B-tree的修改必须先更新WAL然后再修改树本身的页。当数据库崩溃时，可以基于WAL恢复到最近一致的状态。
B-tree优化机制
不使用WAL，而是写时复制
保存键的缩略信息，而不是完整键，这样可以节省页空间
基于LSM-tree让连续的键再磁盘上相互靠近
添加额外的指针到树中，可以顺序扫描，而不用跳回父页
分型树
其他索引
多列索引
全文索引
模糊索引
在线事务处理(online transaction processing OLTP)
通常面向用户，这意味着它可能收到大量请求，为了在线负载，应用程序通常再每个查询中只涉及少量记录
在线分析处理(online analytic procession OLAP)
数据仓库
星型与雪花型分析模式
列式存储
列压缩
位图：一个位图对应每个不同的值，一个位对应一行，如果行具有该值，该位置为1，否则为0
内存带宽和矢量化处理
列存储中的排序
列存储的写操作
聚合：数据立方体与物化视图
物化视图是查询结果的实际副本，并存入磁盘，而虚拟试图只是用于编写查询的快捷方式
大多数数据仓库都保留尽可能多的原始数据，仅当数据立方体可以对待特定查询显著提升性能时，才会采用多维数据聚合
数据编码与演化
关系型数据库通常假设数据库中的所有数据都符合一种模式，尽管该模式可以改变，这样在任何一个给定时间点都只有一个有效模式
REST: Representational State Transfer ，具象状态传输
RPC：remote procedure calls ,远程过程调用
数据编码格式
编码需要面临的问题
多语言
安全隐患
兼容性
效率
JSON
XML
二进制
Thrift
protobuf
Avro
第一种模式语言 Avro IDL 用于人工编辑
第二种模式语言 基于JSON 易于机器读取
Avro的关键思想是：写模式与读模式不必须往期一模一样，他们只需要保持兼容
数据流模式
进程间数据流动的方式
通过数据库
通过服务调用
通过异步消息传递
基于数据库的流动
不同的时间写入不同的值
归档存储
基于服务的数据流动
面向服务/微服务体系结构的 一个关键设计目标是：通过使服务可独立部署、进化，让应用程序更易于更改和维护
网络请求与本地请求的不同
本地函数调用时可预测的
本地函数调用要么有结果返回，要么抛异常
网络调用需要考虑幂等性
网络调用影响的时间不可预测
网络调用基于内存、指针等更高效
网络调用需要考虑，两方编码不一样的情况
REST
RPC
基于消息传递的数据流
消息代理的几个优势
如果接收方不可用或过载，它可以充当缓冲区，从而提供系统的可靠性
它可以主动将消息重新发送到之前崩溃的进程，从而防止消息丢失
避免发送方需要知道接收方的IP、端口等
支持将一个消息发送到多个接收方
将发送方与接收方分离，解耦
消息代理
MQ、kafka
分布式Actor框架
分布式数据系统
成功的技术应首先处理好现实问题，因为现实无法被愚弄
分布式数据库出现的目的
扩展性
容错与高可用性
延迟考虑
数据分布在多个节点时又两种常见方式：复制、分区
数据复制
复制的目的
使用数据在地理位置上更接近用户，从而降低访问延迟
当部分组件出现故障时，系统仍然可以继续工作，从而提高系统可用性
扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量
三种流行的复制方法
主从复制
多主复制
无主复制
主从复制
工作原理
指定某一个副本为主副本，写请求必须由主副本节点先处理完毕
其他副本接收主副本的同步日志，并按顺序写入到本节点
客户端可以从主副本或从副本查询数据，但是写请求只能到主副本
复制方式可以是同步复制或异步复制
节点恢复追赶
在某个时间点，对数据的主节点生成一个一致性快照
将此快照发送至，刚恢复的新节点
新节点连接到主节点请求快照之后发生的数据更改日志
获取日志后，新节点基于日志应用这些数据变更，这个过程也叫"追赶"
节点失效处理
从节点失效，恢复后追赶主节点
主机诶点失效，节点切换
确认主节点失效
选举新的主节点
重新配置系统使新主节点生效
复制日志的实现
基于语句复制
做法：将每个insert/update/delete记录到日志，复制的时候基于日志记录去做同步
存在的问题
任何调用非确定性函数的语句，如now()获取当前时间等，会导致在不同副本上得到的结果不同
如果语句中使用了自增列，或依赖数据库的实现自增，则所有副本必须按照完全相同的顺序执行，否则可能会带来不同的结果
有副作用的语句(触发器、存储过程、用户定义的函数)，可能会在不同的副本上产生不同的副作用
MySQL5.1之前基于语句复制，之后的版本，若存在不确定性的操作，则MySQL切换到基于行的复制
基于预写日志(WAL)传输
做法：每次数据涉及修改都先写入日志，这个日志可以用于崩溃恢复，和同步
缺陷：日志描述的数据结果非常底层:一个WAL把喊了那些磁盘快的哪些字节发生变化，诸如此类细节，这使得复制方案和存储引擎紧密耦合
基于行的逻辑日志复制
复制的日志和存储引擎采用不同的日志格式，这样复制与存储逻辑剥离，这种复制日志称之为逻辑日志
行级别记录描述
对于行插入，记录包含所有相关列的新值
对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键，若无主见则记录所有列的旧值
对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值
MySQL的binlog，若配置的是基于行复制，则是基于行级别的方式
基于触发器的复制
复制滞后问题
写后读一致：保证用户总能看到自己所提交的最新数据
单调读：用户在某个时间点读到数据之后，保证此后不会出现比该时间更早的数据
前缀一致读：保证数据之间的因果关系，如：总是以正确的顺序先读取问题，再看到答案。
一个解决的方法是确保任何具有因果顺序关系的写入都提交到同一个分区来完成
一个解决的方法是确保任何具有因果顺序关系的写入都提交到同一个分区来完成
多主节点复制
适用场景
多数据中心
离线客户端端操作
协作编辑
与单主节的区别
性能更优
容忍数据中心失效
容忍网络问题
处理写冲突
同步与异步冲突检测
避免冲突
收敛于一致性状态
每个写入都分配一个ID，ID大者写入生效，这种也叫后写入者获胜。这种很流程但是会导致数据丢失
每个副本分配一个ID，并制定规则。最终ID大者生效。这种也会导致数据丢失
以某种方式将这些值合并在一起
利用预先定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突。方式最有效但是最低效
自定义冲突解决逻辑
在写入时执行：质押数据库系统在复制变更日志时候检测到冲突，就会调用应用层的冲突处理程序来解决。
在读取时执行：当检测到冲突时，所有冲突写入值都暂时保留下来，下一次读取数据时，会将数据的多版本读返回给应用。应用可能会提醒用户冲突已经解决。
注意点：冲突解决通常用于单个行或文档，而不是整个事务。因此如果有一个原子事务包含了多个不同的请求写，每个请求仍然需要考虑冲突问题
多主节点的拓扑模型
环形拓扑
每个节点接收来自前序节点的写入
星型拓扑
一个指定的根节点奖写入转发给所有其他节点
全部-至-全部拓扑
可能存在某些网络链路比其他链路更快的情况，导致复制日志之间的覆盖
无主节点复制
读修复
当客户端并行读取多个副本时，可以检测到过期的返回值，然后将新值写到过期的节点。这种主要适用于哪些被频繁读取的场景
反熵过程
一些数据存储有后台程序不断查找副本之间数据的差异，将任何缺少的数据做不同节点之间的复制
读写quuorum
如果有n个副本，写入至少需要w个节点确认，读取必须至少查询r个节点，则只需要w+r>n，读取的节点中一定会包含新值
如果可用节点数小于w或r，则写入、读取就会返回错误
之所以这样，是因为成功写入的节点集合和读取 的节点集合必然会有交集
数据分区
我们必须首先定义清楚关系，然后才是执行步骤
分区通常是这样定义的：每一条数据只属于某个特定分区。实际上，每个分区都可以视为一个完整的小型数据库
目的
提供可扩展性
将数据和查询负载均匀分布在所有节点上
数据分区与数据复制
分区通常与复制结合使用，每个分区在多个节点存在副本，需要节点间复制
一个节点可能即是某些分区的主副本，又是其他分区的从副本
键-值数据的分区
需要考虑系统热点问题
基于关键字区间分区：为每个分区分配一段连续的关键字或关键字区间
基于关键字哈希值分区
JAVA与Ruby的哈希，同一个键在不同的进程中可能返回不同的哈希值
负载倾斜与热点
基于哈希的分区方法可以减轻热点，但是没法完全避免
通常对少了的热点关键字附加随机数才能有意义，而对写入吞吐量低的绝大多数关键字，这些都意味着不必要的开销
分区与二级索引
基于文档分区的二级索引(本地索引)
每个分区完全独立，各自维护自己的二级索引
查询时候需要考虑分散、聚集
基于词条的二级索引分区(全局索引)
优点：读取效率更高 缺点：写入速度慢
分区再平衡
需要满足点
平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀的分布
再平衡过程中，数据库应该可以正常继续提供读写服务
避免不必要的负载迁移，以加快动态再平衡，并尽量减少网络和磁盘I/O yingxiang
动态再平衡策略
不该使用取模方式
固定数量的分区
创建远超于实际节点数的分区数，然后为每个节点分配多少个分区。若后续有新加入的节点，则新节点可以从每隔个现有节点匀走几个分区，知道分区再次达到全局平衡
动态分区
当分区的数据增加超过一个可配置的阈值，它就拆分为两个分区，每个分区承担一半的数量，相反，若大量数据被删除则分区缩小到某个阈值以下
按节点比例分区
分区与集群节点数成正比关系，若节点不变，每个分区的大小与数据集大小保持正比增长关系；当节点增加，分区则会调整变得更小
手动再平衡和自动再平衡
请求路由
策略
允许客户端连接任意的节点，若某节点恰好存在请求的数据，则处理并返回。否则将请求转发到下一个合适的节点，接受答复，并将结果返回给客户端
将所有请求都统一发到一个路由层，由路由层负责将请求转发到对应的分区节点上，路由层本身不处理任何请求，它充当一个分区感知的负载均衡器
客户端感知分区和节点分配关系。此时客户端可以直接连接到目标节点，二部需要任何中介
许多分布式数据库系统依靠独立的协调服务(ZooKeeper)跟踪集群范围内的元数据
一些数据库系统基于gossip协议来同步集群状态变化
大规模并发处理(massively parallel procession MPP)
事务
ACID:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)
原子性、隔离性、持久性是数据库自身的属性，而一致性更多的是应用层的属性
弱隔离级别
读-提交
保证
读数据库时，只能看到已成功提交的数据，防止脏读
写数据库时，只会覆盖已成功提交的数据，防止脏写
实现
防止脏写：当事务想修改某个对象时，它必须首先获得该对象的锁，然后一直持有锁知道事务提交或终止
防止脏读：对于每个待更新的对象，数据库都会维护其旧值与当前持锁事务将要设置的新值两个版本。在事务提交之前，其他所有读操作都读取旧值，仅当些事务提交后，才切换到读新值
快照级别隔离(可重复读)
不可重复度(nonrepeatable read) = 读倾斜(read skew)
思路：每个事务都从数据库的一致性快照中读取，事务一开始所看到是最近提交的数据，即使数据库随后可能被另一个事务修改，但保证每个事务都是只看到该特定时间点的旧数据
多版本并发控制(Multi-Version Concurrency Control ,MVCC)
一致性快照可见性规则
每笔事务开始时，数据库列出所有当时尚在进行中的其他事务，然后忽略这些事务完成的部分写入，即不可见
所有中止事务所做的修改全部不可见
较晚事务ID所做的任何修改不可见，不管这些事务是否完成提交
除此之外，其他所有的写入都对应用查询可见
索引与快照级别隔离
一种方案是索引直接指向对象的所有版本，然后想办法过滤当前事务不可见的那些版本
另一种是没修事务都会创建一个新的B-tree root 代表该时刻数据的一致性快照
防止更新丢失(read-modify-write)
原子写操作
独占锁
所有原子性操作都在单线程操作
显式加锁
自动检测更新丢失
原子比较与设置
冲突解决与复制
写倾斜与幻读
这种在一个事务中的写入改变了另一个事务查询结果的现象，叫幻读
这种方法称为实体化冲突，它把幻读问题转变为针对数据库中一组具体行的锁冲突问题
串行化
最强的隔离级别
串行化技术
严格按照串行顺序执行
两阶段锁定(two-phase locking 2PL)
乐观并发控制技术
两阶段锁定(two-phase locking 2PL)
实现
多个事务同事获取一个对象的共享锁，但是如果某个事物已获取得了对象的独占锁，则所有其他事务必须等待
如果事务要修改对象，必须获取独占锁
如果事务先读取对象，再尝试写入对象，则需要将共享锁升级为独占锁
获得锁后，一直持有锁直到事务结束
谓词锁
索引区间锁
可串行化的快照隔离(Serializable Snapshot Isolation SSI)
悲观锁与乐观锁并发控制
基于过期的条件做决定
检测是否读取了过期的MVCC对象
检测写是否影响了之前的读
分布式系统的挑战
故障与部分失效
云计算与超算
不可靠的网络
网络故障
检测故障
超时与无限期的延迟
网络阻塞与排队
同步与异步网络
不可靠的时钟
单调时钟与墙上时钟
时钟同步与准确性
时间戳与事件顺序
时钟的置信区间
全局快照的同步时钟
进程暂停
响应时间保证
调整垃圾回收的影响
主节点与锁
Fencing令牌
拜占庭故障
弱的谎言形式
理论模型与现实
关于时钟，有三种系统模型
同步模型
部分同步模型
异步模型
节点系统失效模型
崩溃-中止模型
崩溃-恢复模型
拜占庭(任意)失效模型
算法的正确性
唯一性(安全性)
单调递增(安全性)
可用性(活性)
一致性与共识
可线性化:原子一致性，强一致性
线性化的依赖条件
加锁与主节点选举
约束与唯一性保证
夸通道的时间依赖
实现线性化系统
主从复制(部分支持可线性化)
共识算法(可线性化)
多主复制(不可线性化)
无主复制(可能不可线性化)
之所以泛起线性化的原因是性能，二不是为了容错
CAP理论
不要求线性化的应用更能容忍网络故障，这种思路通常被称为CAP定理
CAP有时也代表一致性、可用性，分区容错性，系统只支持其中两个特性，不过这种理解存在误导性，网络分区是一直故障，不管喜不喜欢，它都会发生，所以无法选择或逃避网络分区问题。因此更准确的称呼应该是“网络分区情况下选择可用性还是一致性”
顺序保证
因果关系
非因果序列发生器
每个节点都独立产生自己的一组序列号
可以报墙上时间戳附加到每个操作上
可以预先分配序列号的区间范围
Lamport时间戳
每个节点都有一个唯一的标识，且每个节点都有一个计数器来记录各自自己处理的请求总数。Lamport时间戳是一个值对(计数器,节点ID)。两个节点可能会有相同的计数器，但时间戳中包含节点ID信息，因此可以确保每个时间戳是唯一的
Lamport时间戳主要用于确保全序关系
全序广播
可靠发送，没有消息丢失，如果消息发送到了某个节点，则它一定要发送到所有节点
严格有序，消息总是以相同的顺序发送给每个节点
分布式事物与共识
共识场景
主节点选举
原子事务提交
二阶段提交(2PC)
当应用启动一个分布式事务时，它首先向协调者请求事务ID，改ID全局唯一
应用程序在每个参与节点上执行单节点事务，并将全局ID附加到事务上。如果在这个阶段发生问题，则安全终止
当应用程序准备提交时，协调者向所有参与者发生准备请求，并附加全局事务ID，如果有任意一个失败或超时则安全中止，放弃事务
参与者收到准备请求后，确保在任何情况下都可以提交事务，包括安全的将事务数据写入磁盘，并检测师傅存在冲突或约束违规，一旦向协调者回答“是”，节点就承诺会提交事务。
当协调者收到所有准备请求的答复时，就是否提交事务要做个明确决定。协调者吧最后的决定写入到磁盘事务日志中，防止系统崩溃后恢复。
协调者向所有参与者发生提交(回滚)事务请求。如果请求发生失败或超时，则必须一直重试，直到成功为止
实践中的分布式事务
Exactly-once消息处理
XA交易
支持容错的共识
共识算法必须满足的性质
协商一致性，所有的节点都接受想给他的决议
诚实性，所有节点都不能反悔，即对一项决议不能有两次决定
合法性，如果决定了值v,则v一定是由某个节点所提议的
可终止性，节点如果不崩溃则最终一定可以达成决议
如果遇到的问题最终归结为共识，且有容错的需求，则建议采用ZooKeeper
派生数据
批处理系统
三种不同类型的系统
在线服务(在线系统)
批处理系统(离线系统)
流处理系统(近实时系统)
批处理输出哲学：一个程序读取输入并写回输出。这个过程中，输入保持不变，任何以前的输出都被新输出完全替换，并没有其他副作用。
MapReduce作业的输出处理遵循相同原理：将输入视为不可变，避免副作用。
数据流引擎有个共同点：他们吧整个工作流作为一个作业来处理，而不是把它分解成独立的子作业
Flink是围绕流水线执行的思想而建立起来的，也就是将运算的输出递增的传递给其他运算符，且在开始处理之前不等待输入完成
数据流对MapReduce的改进是：不需要自己将所有中间状态写入文件系统
设计原则：输入是不可变的，输出是为了成为另一个程序的输入，而复杂的问题通过编写"做好一件事"的小工具来解决
分布式处理框架需要解决的问题：
分区：在MapReduce中，mapper根据输入文件块进行分区
容错：MapReduce需要频繁写入磁盘，使得可以从单个失败任务中轻松恢复，而无需重新启动整个作业，但在无故障情况下则会减慢执行速度。
排序-合并join
广播哈希join:两个join输入中的某一个数据集比较小，所以不需要分区，完全加载到哈希表中。
分区哈希join
流处理系统
在流处理的上下文中，记录通常被称为事件，但它本质上是一回事：一个小的、独立的、不可变的对象，该对象包含某个时间点发生事情的细节。每个事件通常包含一个时间戳，用于指示事件发生的墙上事件
webhooks背后思路：一个服务的回调URL被注册到另一个服务中，并且每当事情发生时都会向该URL发出请求
消息传递模式
负载均衡式：每条消息都只被传递给其中一个消费者，所以消费者可以共享主题中处理消息的进度，代理可以任意分配消息给消费者。
扇出式：每条此消息都被传递给所有的消费者。扇出允许几个独立的消费者各自“收听”相同的广播消息，而不相互影响。
消息消费者无法跟上生产者发送消息的速度时，有三种选择：丢弃消息、缓冲消息、应用背压
变更数据捕获(Change Data Capture,CDC)
日志压缩：存储引擎定期查找具有相同key的日志记录，丢弃所有的重复项，并只保留每个key的最新的更。每个压缩和合并的过程是在后台运行。
将数据写入形式与读取形式分开，并允许多个不同的读取视图，可以获得很大的灵活性。这个想法有时被称为命令查询职责分离(Command Query Responsibility Segregation,CQRS)
复杂事件处理(Complex Event Procession CEP)
为了调整不正确的设备时钟，一种方法是记录三个时间戳
根据设备的时钟，记录事件发生的时间
根据设备时钟，记录将事件发送到服务器的时间
根据服务器时钟，记录服务器收到事件的时间
窗口类型
轮转窗口，翻滚窗口的长度是固定的，每个时间都属于一个窗口。如10:30:00-10:30:59是第一个窗口，10:31:00-10:31:59是第二个窗口
跳跃窗口，跳跃窗口的时间也是固定的，但是允许相联的窗口，时间范围有重叠，以达到平滑的目的
滑动窗口，滑动窗口包含在彼此的某个间隔内发生的所有事件。
会话窗口，与其他窗口类型不同，会话窗口没有固定的持续时间。
流式join
流与流
流与表
表与表
容错：基于微批处理、检查点、事务或幂等性写入等，可以实现更细粒度的恢复机制
数据库系统的未来
考虑到好的分布式事务协议尚未得到广泛支持，我认为基于日志的派生数据是集成不同数据系统的最有前途的方法
决定是文件的全序关系称为全序关系广播，它等价于共识。大多数共识算法是针对单节点吞吐量足于处理整个事件流而设计的，并且这些算法不提供支持多节点共享时间排序的机制。
如果有一种技术可以满足你的所有需求，那么最好使用该产品，而不是试图使用基础组件来重新实现一遍。当没有单一的软件能满足所有需求时，分离和组合的优势才会显现出来。
最快和最可靠的网络请求就是根本没有网络请求
达成共识的最常见方式是将单一节点作为主节点，并负责做出所有决定。
一致性
时效性：时效性意味着确保用户观察到系统的最新状态
完整性：完整性意味着避免数据损坏，即没有数据丢失，也没有互相矛盾或成为的数据
只执行一次是保证完整性的机制
没有一种工具可以有效的服务于所有可能的场景，所以应用程序必须编排多个不同的软件来王畅他们的目标
0 条评论
下一页
