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