Ukeate笔记

数据密集型应用

  • data-intensive applications
  • 计算密集型应用
  • 数据处理标准件
    • 存储
    • 缓存
    • 索引
    • 流处理
      • 异步消息
    • 批处理
  • 基石
    • 描述
    • 数据模型与查询语言
      • 层次模型(hierarchical model)
        • 20世纪70、80年代
        • 类似文档数据库，擅于处理一对多关系，难处理多对多关系
        • 记录间不能链接
        • IMS使用层次模型
      • 网络模型(network model)
        • 20世纪70、80年代
        • 是层次模型的推广，每条记录可能有多个父节点
        • CODASYL上进行了标准化，也称为CODASYL模型
        • 记录间链接不是外键，是持久化的指针
          • 要从根记录起沿这些链路访问记录，称为访问路径(access path)
          • 要查询代码中记录各种访问路径
      • 关系模型
        • 曾是理论性提议，被怀疑能否有效实现
        • RDBMSes
        • NoSQL
        • 混合持久化
        • 阻抗失谐
        • 多对一和多对多关系
          • 副本(duplication)问题与数据库规范化(normalization)
        • 索引实际上是访问路径，与网络模型的区别是它们由查询优化器自动生成
          • 只需构建一次查询优化器，可所有程序中通用
          • 特定查询手动编写访问路径比通用优化器更容易
          • 从长期看通用的方案更好
      • 文档模型
        • 有更好的局部性
        • 与层次模型对比，父记录存储嵌套记录
        • 记录间引用称为文档引用，相当于外键
        • 与关系模型对比
          • 文档模型架构灵活，因局部性有更好的性能，更接近应用程序的数据结构
          • 关系模型为连接提供更好的支持
          • 容错属性
          • 处理并发性
        • 特性
          • 局限性
            • 不能直接引用文档中的嵌套项目
            • 支持不好
          • 灵活性
            • 无模式(schemaless)
              • 文档记录无模式验证，但读时有隐式模式，容易模式变更
              • 读时模式(schema-on-read)
                • 类似运行时动态类型检查
              • 写时模式(schema-on-write)
                • 类似编译时静态类型检查
                • 关系数据库是写时模式
          • 查询的数据局部性
            • 性能优势，不必查找多次
            • 即使读一小部分也加载整个文档，更新时整个重写
            • 数据局部性也存在于关系数据库中
        • 与关系数据库融合
          • 关系数据库支持XML、JSON，及在其中的索引查询功能
          • 文档数据库中支持关系
            • RethinkDB在查询语言中支持类似关系的连接
            • MongoDB驱动自动解析数据库引用
        • MongoDB的agregate重新发明了SQL
      • 查询语言
        • 类型
          • 声明式
            • SQL
            • 隐藏实现细节
            • 可以并行优化
          • 命令式
            • IMS
        • Web中
          • CSS是声明式
          • DOM是命令式
        • MapReduce
          • 声明式指定过滤器
          • 命令式调用map和reduce函数
      • 图数据库
        • 适合多对多关系常见的应用
          • 社交图谱
          • 网络图谱
          • 公路或铁路网络
        • 可运行图算法
          • 最短路径
          • PageRank
        • 顶点可表示不同模式对象
        • 实现
          • 属性图模型
            • Neo4j、Titan、InfiniteGraph
            • 顶点vertex
              • 唯一标识符
              • 一组出边，一组入边
              • 一组属性
            • 边edge
              • 唯一标识符
              • 边的起点tail vertext
              • 边的终点head vertex
              • 顶点之间关系的类型标签
              • 一组属性
            • 特点
              • 顶点间互联没有限制
              • 顶点可高效找到入边和出边
              • 可用标签区分存储不同信息
          • 三元组存储
          • 查询语言
        • SQL中查询多级关系
          • 可用递归公用表达式(WITH RECURSIVE)
    • 存储与检索
      • 存储引擎
        • 事务性负载、分析性负载
        • 类型
          • 日志结构(log-structured)
          • 面向页面(page-oriented)
            • B树
      • 索引
        • 哈希索引
          • 分段
            • 增长到特定尺寸关闭前段，写入新段
          • 压缩
            • 丢弃重复的键，只保留最近更新
          • 合并
            • 压缩后小段合并，再替换旧段
          • 实施中的问题
            • 文件格式
              • 二进制
            • 删除记录
              • 附加删除标记
              • 合并过程中放弃删除键的以前值
            • 崩溃恢复
              • 内存散列映射丢失
              • Bitcast恢复磁盘上每个段的哈希映射快照恢复
            • 部分写入记录
              • 校验和，检测和忽略日志的损坏部分
            • 并发控制
              • 写操作有严格顺序，常见的实现是只有一个写入器线程
              • 追加日志的原因
                • 追加是顺序写，在磁盘和SSD上都比随机写快
                • 崩溃恢复简单
                • 合并旧段避免数据文件随时间推移而分散的问题
          • 哈希索引的局限性
            • 必须放进内存
              • 磁盘要随机写
            • 范围查询效率不高
        • SSTables和LSM树
          • SSTableLSM Tree
          • 效率优化
            • 不存在的键遍历问题，Bloom过滤器
            • 不同策略确定SSTables如何被压缩、合并的顺序和时间
        • B Tree
        • 其它索引
          • 二级索引
          • 聚簇索引(clustered index)
            • 值存在索引中
            • 堆文件
              • 值更大时，要移动堆并更新所有索引，或在旧堆位置留转发指针
            • 包含列索引(index with included columns)、覆盖索引(covering index)
              • 部分数据在索引中
          • 多列索引
            • 连接索引
              • 简单组合多值
            • 多维索引
              • 如地理位置
              • 特殊化空间索引
                • R树
          • 全文索引
            • 模糊索引
        • 内存数据库
          • 更快的原因
            • 主要在于省去内存数据结构编码为磁盘数据结构的开销
            • 不从磁盘读取是其次
          • 可扩展到支持比内存更大的数据集
          • NVM
      • OLTP、OLAP
        • 分析模式
          • 星型
            • 事实表在中间，由维表包围
          • 雪花型
            • 星型模式，尺寸进一步分解
        • 列存储
          • 每列存储在单独文件中
        • 列压缩
          • 列值重复易于压缩
          • 位图编码
        • 列族
          • Bigtable将一行所有列与行键一起存储，不用列压缩，主要是面向行的
        • 内存带宽和失量化处理
        • 列存储排序
          • 便于压缩
          • 可多列排序
        • 写入列存储
          • 先内存排序再批量写入磁盘
        • 聚合：数据立方体和物化视图
    • 编码与演化
      • 双向兼容
      • 编码格式
      • 语言内置编码
        • 与语言深度绑定
        • 有实例化任意类的能力，有安全问题
        • 缺少数据版本控制
        • 效率低，如Java的Serializable
      • JSON,XML,二进制变体(CSV)
      • 二进制编码
    • 数据流类似
      • 数据库的数据流
      • 归档数据
      • 服务的数据流，REST与RPC
      • Web服务，HTTP
      • RPC
      • MQ
      • Actor模式
  • 分布式数据
    • 扩展
      • 垂直扩展(vertical scaling)、向上扩展(scale up)
        • 共享内存架构(shared-memory architecture)
          • 成本增长快于线性增长
        • 共享磁盘架构(shared-disk architecture)
          • 竞争锁定开销限制了可扩展性
        • 无共享架构(shared-nothing architecture)、水平扩展(horizontal scale)、向外扩展(scale out)
    • 复制(replication)
      • 处理变更
        • single leader
          • 同步复制、异步复制
            • 延迟问题处理
              • 读自己的写
              • 单调读
              • 一致前缀读
        • multi leader
        • leaderless
          • 写入仲裁
    • 分区(partition)
      • 键值分区
        • 负载倾斜、热点消除
      • 分片与次级索引
      • 分区再平衡
      • 请求路由
    • 事务
      • 棘手的问题
        • ACID
        • 多对象事务
        • 处理错误和路上
      • 弱隔离级别
      • 可序列化
    • 分布式系统的麻烦
      • 故障与部分失效
      • 不可靠的网络
      • 不可靠的时钟
    • 一致性与共识
      • 线性一致性
      • 顺序保证
      • 分布式事务共识
  • 衍生数据
    • 记录系统和衍生数据系统
    • 批处理
    • 流处理
      • 传递事件流
      • 流与数据库
      • 流处理
    • 数据系统的未来
      • 数据集成
      • 拆库

关系图谱

反向链接