数据密集型应用系统设计
2023-06-09 14:07:54 3 举报AI智能生成
数据密集型应用系统设计读书笔记
作者其他创作
大纲/内容
事务
事务的原理
ACID 的含义
原子性（Atomicity）
隔离性（Isolation）
持久性（Durability）
一致性（Consistency）
单对象与多对象事务操作
单对象写入
多对象事务的必要性
处理错误与中止
弱隔离级别
读写竞争
脏写 -> 读-未提交
脏读 -> 读-提交
防止脏读
防止脏写
存在问题
不可重复读 -> 可重复读
实现快照级别隔离
一致性快照的可见性规则
不可见
可见
索引与快照级别隔离
写写竞争
更新丢失
原子写操作
显式加锁
自动检测更新丢失
原子比较和设置
冲突解决与复制
多对象冲突
写倾斜
幻读
实体化冲突
强隔离级别
悲观并发控制
实际串行执行
存储过程封装
优势与劣势
分区
两阶段加锁（2PL）
实现方式
性能分析
谓词锁
索引区间锁
乐观并发控制
可串行化快照隔离（SSI）
基于过期的条件做决定
检测是否读取过期的 MVCC 对象
检测写是否影响了之前的读
可串行化快照隔离的性能
跟踪事务读写的粒度
与实际串行执行相比
与两阶段加锁相比
分布式系统的挑战
故障与部分失效
云计算与超算
不可靠网络
网络故障
网络分区
故障检测
超时与无限期延迟
网络拥塞与排队
同步和异步网络
延迟与资源利用率
不可靠时钟
单调时钟与墙上时钟
墙上时钟
单调时钟
时钟同步与准确性
依赖同步的时钟
时间戳与事件顺序
时钟的置信区间
全局快照的同步时钟
进程暂停
响应时间保证
调整垃圾回收的影响
授时方案
TrueTime
去中心化授时（TSO）
分布式授时（HLC）
多层级中心化授时（STP）
知识，真相与谎言
真相由多数决定
主节点与锁
Fencing 令牌
拜占庭故障
弱的谎言形式
理论系统与现时
算法的正确性
安全与活性
将理论系统映射到现实世界
一致性与共识
一致性保证
数据一致性
最终一致性
线性一致性
因果一致性
顺序一致性
其他
事务一致性
事务 ACID
隔离性
ANSI SQL-92
未提交读（RU）
已提交读（RC）
可重复读（RR）
可串行化（Serializable）
Critique
访问异常
幻读
写倾斜
隔离级别
快照隔离（SI）
技术实现
多版本并发控制（MVCC）
产品实现
可串行化
两阶段封锁（2PL）
单进程
可串行化快照隔离（SSI）
可线性化
达成条件
可线性化与可串行化
依赖条件
加锁与主节点选举
约束与唯一性保证
跨通道的时间依赖
实现方式
主从复制（部分支持可线性化）
共识算法（可线性化）
多主复制（不可线性化）
无主复制（可能不可线性化）
线性化代价
CAP 理论
非线性系统
网络延迟
顺序保证
顺序与因果关系
因果顺序并非全序
可线性化强于因果一致性
捕获因果依赖关系
序列号排序
非因果序列发生器
Lamport 时间戳
局限性
全序关系广播
使用全序关系广播
全序关系广播 -> 线性化存储
原子比较设置
追加日志
线性化读取
线性化存储 -> 全序关系广播
共识问题
共识问题
原子提交与两阶段提交：停止服务/人工介入
事务原子提交
两阶段提交（2PC）
系统的承诺
协调者发生故障
三阶段提交（3PC）
实践中的分布式事务
Exactly-Once 消息处理
XA 交易
停顿时仍持有锁
从协调者故障中恢复
局限性
单点故障
有状态
高复杂度
低容错
支持容错的共识：自动切换
共识算法与全序广播
主从复制与共识
Epoch 和 Quorum
局限性
同步复制
故障误判
多数节点
静态成员组成
网络问题敏感
成员与协调服务
节点任务分配
服务发现
成员服务
* 批处理系统
UNIX 工具
简单日志分析
命令链与自定义程序
排序与内存中聚合
UNIX 设计哲学
统一接口
逻辑与布线分离
透明与测试
MapReduce 与分布式文件系统
MapReduce 作业
分布式执行
工作流
Reduce 端的 join 与分组
分析用户活动事件
排序-合并 join
将相关数据放在一起
分组
数据倾斜
Map 端的 join
广播哈希 join
具有 Map 端 join 的工作流
批处理工作流的输出
生成搜索索引
批处理输出键值
批处理输出的哲学
对比 Hadoop 与分布式数据库
存储多样性
处理模型多样性
针对频繁故障的设计
超越 MapReduce
中间过程实体化
数据流引擎
容错
实体化
图与迭代处理
Pregel 处理模型
容错
并行执行
高级 API 和语言
声明式查询语言
不同领域的专业化
* 流处理系统
发送事件流
消息系统
直接消息传递
消息代理
与数据库对比
多个消费者
确认和重新传递
分区日志
基于日志的消息存储
与传统消息系统对比
消费者偏移量
磁盘空间使用
当消费者跟不上生产者
重新处理消息
数据库与流
保持系统同步
变更数据捕获
实现变更数据捕获
初始快照
日志压缩
对变更流的 API 支持
事件溯源
从事件日志导出当前状态
命令和事件
状态，流与不可变性
不变事件的优势
相同的事件日志派生多个视图
并发控制
不变性的限制
流处理
适用场景
复杂事件处理
流分析
维护物化视图
在流上搜索
消息传递和 RPC
流的时间问题
事件事件与处理时间
准备就绪
谁的时钟
窗口类型
流式 join
流和流 join（窗口 join）
流和表 join
表和表 join（物化视图维护）
join 的时间依赖性
流处理的容错
微批处理和校验点
重新审视原子提交
幂等性
故障后重建状态
* 数据系统的未来
数据集成
采用派生数据来组合工具
为何需要数据流
派生数据与分布式事务
全序的局限
排序事件以捕获因果关系
批处理和流处理集成
保持派生状态
为应用演化而重新处理数据
Lambda 架构
统一批处理和流处理
分拆数据库
端到端的正确性
做正确的事
分拆数据库
编排多种数据存储技术
创建索引
元数据库
分离式与集成式系统
围绕数据流设计应用系统
应用程序代码作为派生函数
应用程序代码与状态分离
数据流：状态变化和应用程序代码之间相互影响
流式处理与服务
观察派生状态
实体化视图和缓存
有状态，可离线客户端
状态更改推送至客户端
端与端的事件流
读也是事件
多分区数据处理
端到端的正确性
数据库的端到端争论
Exactly-once 执行操作
重复消除
操作标识符
端到端的争论
在数据系统中采用端到端的思路
强制约束
唯一性约束需要达成共识
基于日志的消息传递唯一性
多分区请求处理
时效性与完整性
数据流系统的正确性
宽松的约束
无需协调的数据系统
信任，但要确认
软件缺陷时的完整性
不要盲目信任承诺
验证的文化
可审计性的设计
端到端的再讨论
审计数据系统的工具
做正确的事
预测性分析
偏见与歧视
责任与问责
反馈环路
数据隐私与追踪
监控
赞成与选择的自由
数据隐私和使用
数据作为资产和权力
记住工业革命
立法与自律
数据分区
键值数据的分区
基于关键字区间
基于关键字哈希值
一致性哈希
组合索引
数据倾斜与热点
分区与二级索引
基于文档（本地）
基于词条（全局）
分区再平衡
动态再平衡策略
避免取模
固定数量
动态分区
按节点比例
自动与手动再平衡
请求路由
分布式协调
并行查询执行
分区架构
PGXC
Hash 分片
普通哈希
一致性哈希
Range 静态分片
Set
NewSQL
Range 动态分片
Group
可靠、可扩展与可维护的应用系统
可靠性（Reliability）
硬件故障
软件故障
人为失误
可扩展性（Scalability）
描述负载
描述性能
系统扩展
自动与手动
水平与垂直
有状态与无状态
可维护性（Maintainability）
可运维性
简单性
复杂系统
设计抽象
可演化性
应对需求变化
敏捷开发模式
简单与抽象
数据模型与查询语言
数据模型
关系模型：严格关联
数据访问
局限性
多对一关系
多对多关系
非关系模型
文档模型：弱关联
灵活性
局限性
数据局部性
图模型：复杂关联
图模型
属性图模型
三元存储模型
图处理框架
Pregel
......
数据查询语言
声明式语言
MapReduce
图查询语言
声明式
Cypher
SPARQL
Datalog
SQL
命令式
Gremlin
数据存储与检索
数据结构
哈希索引
追加写入
偏移量
分段压缩
文件格式
删除记录
崩溃恢复
部分写入
并发控制
局限性
哈希表必须全部放入内存
区间访问效率不高
LSM-Tree
构建和维护 SSTables
处理写请求
处理读请求
合并和压缩
崩溃恢复
LSM 存储引擎
性能优化
布隆过滤器
压缩合并策略
优势与劣势
写放大
写入较快
读取较慢
更好的压缩
写入带宽开销
B-Tree
分页设计
查找
更新
插入
可靠性
预写日志
并发控制
性能优化
写时复制
键略缩信息
相邻布局
添加额外指针
分形树
优势与劣势
读取较快
写入较慢
并发控制
其他索引结构
在索引中存储值
堆文件
聚簇索引
多列索引
级联索引
全文搜索和模糊索引
内存保存所有内容
应用实例
反缓存架构
事务处理与分析处理
事务处理系统（OLTP）
日志结构
原地更新
分析系统（OLAP）
数据仓库
星型与雪花型模式
列式存储
列压缩
列与列簇
矢量化处理
排序操作
写操作
聚合：数据立方体与物化视图
* 数据编码与演化
编码格式
语言特定格式
JSON、XML 与二进制变体
二进制编码
Thrift 与 Protocol Buffers
字段标签和模式演化
数据类型和模式演化
Avro
写模式与读模式
模式演化规则
动态生成模式
模式的优点
数据流模式
基于数据库的数据流
不同的时间写入不同的值
归档存储
基于服务的数据流：REST 和 RPC
网络服务
远程过程调用
存在问题
发展方向
数据编码和演化
基于消息传递的数据流
消息代理
分布式 Actor 框架
数据复制
复制模型
单主节点复制
同步与异步
同步复制
异步复制
半同步复制
配置新从节点
处理节点失效
从节点失效：追赶式恢复
主节点失效：节点切换
处理步骤
确认主节点失效
选举新的主节点
使新主节点生效
存在问题
数据丢失
数据不一致
脑裂
超时
复制日志的实现
基于语句
基于预写日志
基于行逻辑日志
基于触发器
复制滞后问题
一致性模型
写后读
主节点处理
更新时间戳
多数据中心
单调读
前缀读
解决方案
应用层保障
事务
多主节点复制
使用场景
多数据中心
离线客户端
协作编辑
处理写冲突
同步/异步检测
避免冲突
状态收敛
写时/读时冲突解决
自动解决冲突
无冲突数据类型
可合并的持久数据结构
操作转换
拓扑结构
环型
星型
全链接
存在问题
无主节点复制
节点失效时写入数据库
读修复与反熵
读写 Quorum
Quorum 一致性的局限
监控旧值
sloppy quorum 与数据回传
多数据中心
检测并发写
最后写入者获胜（丢弃）
happens-before 关系和并发
确定前后关系
合并同时写入的值
版本矢量
元数据存储
静态分片存储
哈希
多节点
无变更
无状态服务
心跳
PD 被动接收
持久化
去中心化
PSP 架构
Gossip 协议
0 条评论
下一页
