DDIA reading note
DDIA reading note
存储结构
Q 高吞吐量
TODO: 重看
append only
SSTables(Sorted String Table)
- 分制(归并)的思想，合并有序段
- 有序 => 快找
- append only => 磁盘顺序写入
LSM tree(日志结构合并树)
- 保存一系列在后台合并的SSTables
- 顺序写 => 写入更快
- 考虑写放大问题：日志中通用记录了过时操作 => 日志压缩
- 考虑压缩速率和写入速率的问题
B tree
- 分段成固定大小的页面，顺序，分级
- 非append only, 但读取更快
- 需要考虑增/删后再平衡的问题，开大了浪费空间，开小了多平衡
内存中存储
内存数据库性能优势不散因为不需要从磁盘读取，操作系统会缓存最近使用的磁盘块。基于磁盘存储的数据库也不慢。关键在于省去了内存数据结构和磁盘数据结构编码的开销
- 面向列存储：将同一列的值存储在一起。扫描更快
- TODO…
编码演化
- 直接使用字符型是比较浪费吞吐量的 => 二进制json, xml等
- rpc
- …
分布式数据
垂直伸缩：购买更强大的机器
- 共享内存架构
- 共享磁盘架构
水平伸缩: 加节点
- 无共享架构
复制
分片
事务
一致性与共识
复制
冗余容错，负载均衡
单领导
多领导
无领导
全同步
半同步(大多数ok)
同步问题，如何同步
- 单纯使用时间戳似乎不行，因为每个节点的计时器多少存在差别，可做参考
简单的复制是不行的，因为数据会不断的变化无法一致 => 定义快照
- 故障切换(abs)
- 确认失效
- 使用超时等策略，超时时间长意味着恢复时间长，反之又会频繁切换 => 运维团队愿意手动管理
- 选择新主
- 重新配置系统
- 确认失效
- 挑战
- 异步复制可能导致记录丢失
- 数据库与外部存储的协调
- 多主节点导致脑裂(split brain)
复制日志的实现
- 基于语句
- 非确定性函数问题：如集函数
count()等不同时刻值还不一样 => 预处理常量替换 - 必须完全顺序
- 触发器等副作用
- 非确定性函数问题：如集函数
- 预写式日志(WAL Write Ahead Log) =>
- 逻辑日志复制(基于行)
- 复制和存储引起使用独立的日志格式，方便向后兼容
- 一操作生成多个日志描述
复制延迟问题
更新不能立刻同步到其他节点，所以如果从延迟较大的节点读取时会得到过时的数据。但是从节点最终会一致的，所有称为最终一致性
- 读己之写(read-after-write consistency或read-your-writes consistency): “更新的同步”
- 防止用户写入后从过时副本中读取
- 简单实现: 写入时记录时间戳，读取时比对时间戳是否够新
- 但时钟同步至关重要（不可靠的时钟）
- 考虑跨设备的一致性问题
- 单调读: “查询的同步”
- 防止从不同节点查到不同的数据
- 同样比对时间戳，更新的才能接受。即滤除旧数据
- 一致前缀读
- 有因果顺序的两条记录，传递到第三者的延迟不同，导致顺序不合理
- 一种方法是，任何因果相关的写入都写入同一个分区 => 不存在不同的延迟
多主复制
无主复制
git
客户端直接写入多个副本
使用一个协调者代替客户端写入
读修复
- 根据返回值判断陈旧副本
反熵
- 使用后台进程不断查找副本之间的数据差异
|———-|
| |
|———-|
p541
一致性共识
线性一致性
- 相当于只有一个副本, 且操作是原子的
是全序(total order)的, 全序的意思的序列中的任意两个数都是可比较的。
因果一致性
区别于线性一致性, 因果一致性只要求存在因果的事件顺序唯一, 不存在因果的事件可以任意。比如同时发生的互不相关的事件, 再比如git的两个分支
是偏序(partial order)的, 如集合类型就是不可比较的, 如{1, 4}, {2, 3}怎么比