Designing data-intensive applications: the big ideas behind reliable, scalable, and maintainable systems

Foundations of Data Systems

Data Models

• SQL：关系型，key-value 对，关联程度一般
• 文档型：自包含文档，少关联
• 图数据库：数据大量关联

Storage and Retrival

• OLTP 数据存储系统
  • 日志结构：追加
    • hash-map：key 对应数据文件当中的位置偏移，只要 key 表能装入内存
      • 高性能读写
      • 对大量 key 不友好
      • 区间查询不友好
    • SSTables：排序字符串表：按顺序合并存储 k-v
      • 可以稀疏存储 key
      • 内存维护表，大于表的写进磁盘文件，一个 log 用来数据恢复
  • 原地更新
    • B-Tree：固定大小的段/页组合
      • 页大小和底层磁盘契合
      • 覆盖而不是追加
      • 大于页大小时候分裂页
• OLAP 数据分析系统
  • 数据仓库：专门用于数据分析的数据库，是工作用数据库的副本，面向查询
    • 事实表：记录事件事实的主表，大，列多
    • 列存储：列太多，一行拆开，每列单独存
    • 列压缩：None值可以被压缩
    • 聚合：面对常见操作预处理

Encoding

向前兼容

旧版本可读新版本的数据，一般通过忽略实现

向后兼容

新版本可读旧版本数据

• 语言自带：性能、通用性差、安全问题（代码生成）
• 文本文件（XML，JSON，CSV）：大，各种数据格式支持弱
• 二进制编码：小，带有更好的兼容检查支持，自带类型，自带注释

Dataflow

• 基于数据库：数据比代码长久，旧版本更新需要忽略新的项
• 基于服务（web 服务 和 RPC）
  • web 服务：通过 HTTP 向服务器公开的 API 调用服务
  • RPC：远程调用有网络自身带来新问题，大跨度有兼容性问题
• 基于消息传递：加入一个消息代理/Actor

Distributed Data

Replication

• 主从复制
  • 分主节点（可读可写）和从节点（只读）
  • 新节点建立：快照+基础上的变更 log
  • 恢复：选举+重新配置
  • 方法
    • 基于语句：非确定性语句改为传结果（VM-FT）
    • 基于预写日志 Write-ahead log (WAL)：磁盘字节改变的日志
    • 基于行的逻辑日志：按照修改的逻辑
    • 基于触发器：应用层控制
  • 复制滞后和一致性
    • 写后读：个人能读到自己之前的写
    • 单调读：多次读取的版本号不减
    • 前缀一致读：读的顺序取绝于当时写的顺序
• 多主节点复制
  • 场景：多中心、离线工作、协作编辑
  • 需要解决/规避同时写冲突
• 无主节点复制
  • 失效节点修复：
    • 读修复：检测到过期的值，适合频繁读取情形
    • 反熵过程：不断检测差异并复制缺失数据，不保证顺序，可能严重滞后
  • quorum 一致：
    • 一次写入、读取需要确认的节点数目有要求，可以保证读到最新值 $w+r>n$
    • 由于：同时读写，回滚错误、宽松 quorum 等原因，该 quorum 一致性不是确定性保证
    • 宽松 quorum：不满足条件时，先缓存等网络重连后继续写入
  • 检测并发写
    • 每个 key 对应一个 version 号，每次写递增 version 号
    • 读 key 时候返回所有未覆盖的值和 version 号，写之前必须读
    • 写时必须包含之前读的 version 号，并手动 merge 读到的结果
    • 可以覆盖低 version 号的结果，高版本不动
    • 注意，删除需要特殊的 remove 标记（简单移除会被误认为未更新）

partition

• $hash\mod N$，但是丧失顺序
  • 不能避免攻击/单 key 高流量
  • 单 key 加盐
  • 对比 node 数目，多建分区防止 mod 抖动
• service discovery：找到划分所在 node
  1. 随机找一个节点，节点之间协调
  2. 路由表连接到节点
  3. 客户端知道划分，自己找到对应节点