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