ThinkerQAQ

NOTE

1.5 数据模型

1. 什么是数据模型 - 计算机和现实世界之间的抽象层，描述了数据的特征 2. 为什么需要数据模型 - 计算机不能直接处理现实的事物，所以，人们只有将现实事物转成数字化的数据，才能让计算机识别处理 3. 数据模型有哪些 - 概念模型：描述现实世界的信息 - 逻辑模型：内存中或磁盘中的数据结构 - 物

系统设计创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 什么是数据模型

  • 计算机和现实世界之间的抽象层，描述了数据的特征

2. 为什么需要数据模型

  • 计算机不能直接处理现实的事物，所以，人们只有将现实事物转成数字化的数据，才能让计算机识别处理

3. 数据模型有哪些

  • 概念模型：描述现实世界的信息
  • 逻辑模型：内存中或磁盘中的数据结构
  • 物理模型：序列化到磁盘或网络中的字节流

4. 概念模型

4.1. 关系模型

  • 数据被组织成关系（表），其中每个关系是元组（行）的无序集合
  • 关系有一对一、一对多、多对多
  • 适用于连接操作

4.2. 文档模型

  • 以一个文档为单位进行存储，支持数组和文档嵌套。可以简单得理解为就是json
  • 不会为存储的数据强制一个模式
  • 适用于一对多且大多数记录之间不存在关系

4.3. 图模型

  • 一个图由两种对象组成：顶点+边
  • 不会为存储的数据强制一个模式
  • 适用于多对多关系，任意事物都可能与任何事物相关联

5. 逻辑模型

  • 根据使用场景可以分为OLAP和OLTP
属性 事务处理 OLTP 分析处理 OLAP
面向的用户 终端的Web用户 内部的数据分析师
实时性读写要求 高 低
事务性要求 高 低
分析要求 低、简单 高、复杂
处理的数据 当前时间点的数据 随时间推移的历史事件
主要读取模式 查询少量记录，按键读取 在大批量记录上聚合
主要写入模式 随机访问，写入要求低延时 批量导入（ETL），事件流
数据集尺寸 GB ~ TB TB ~ PB
数据结构分类 根据读多还是写多分为log-structured和page-oriented 列存储
  • 数据存储在磁盘还是内存
    • 由于数据量大和磁盘 vs 内存（原链接已失效）可知，必须使用磁盘
  • 选用哪种数据结构呢？
    • 根据使用场景而定

5.1. log-structured

5.1.1. 使用场景

  • 事务处理
  • 写多读少

5.1.2. 是什么

  • 日志：也就是一个 仅追加（append-only） 的数据文件
  • 可以看作K-V对数据库
  • 顺序写磁盘效率高
  • 为了避免磁盘空间用完，将日志分为特定大小的segment。在一定时机对segment进行压缩，合并相同的key，对齐旧的key
  • 如何解决大量写
    • 磁盘顺序IO
  • 同一条数据占用多份空间
    • 后台定时合并压缩数据
  • 单个文件还是多个文件
    • 单个文件。固定大小基于阈值划分如何合并数据
  • 把文件加载到内存中排序在合并效率低
    • 保证文件内的数据有序
  • 如何保证文件有序
    • 插入时即排好序
  • 如何排序
    • 红黑树、跳表、B树
  • 磁盘顺序写还是慢
    • 在内存中缓存一段时间，在批量写入磁盘
  • 如何保证内存数据不丢
    • redo log
  • 怎么读取数据
    • 按照倒序读取最新数据,一旦读取到数据，则停止读取逻辑
  • 读优化方案
    • 每个 SSTablel中添加布隆过滤器,用来快速判断读取的数据是否存在,加速读效果
    • 采用分区存储 SSTable,除了L0层外,每层之间的数据不重叠,层内数据有序存储
    • 压缩优化,提升压缩效率,防止压缩过程阻塞读逻辑
  • 三大问题
    • 读放大：读操作需要从新值到旧值依次读取,再此过程中会涉及不止一次IO。特别是范围查询时,导致影响很明显
    • 空间放大：在 LSM Tree中,所有的写都是通过 append的方式来记录因此导致所有过期或者删除的数据不会立即清理掉,仍然LSM读写、空间放大会占据空间,所以称为空间放大
    • 写放大：在上述过程中,为了减少读放大和空间放大。通常采用后台合并数据的方式来解决。但该过程也引入了写放大。实际写入磁盘的据大小和程序要求写入的数据大小之比。正常情况下,压缩合并的过程中对一条数据会涉及多次写,所以称为写放大

5.1.3. 实现

  • LSM.md（关联笔记尚未公开）

5.2. page-oriented

5.2.1. 使用场景

  • 事务处理
  • 读多写少

5.2.2. 是什么

  • 磁盘如何快速读写
    • 顺序IO
  • 每条数据顺序追加后怎么快速读
    • 每条记录维护一个索引
  • 每条记录维护一个索引太大了
    • 这里之所以每条记录需要一个索引是因为每条记录是变长的
      • 那么改成定长的就好了，比如磁盘划分成固定大小的block
      • Block内的每条记录维护索引，Block之间使用no
    • Block大小：操作系统page
    • Block索引存不存：存，聚簇（数据和索引放一块）或者非聚簇
  • 如何支持排序、范围查询
    • 写入时对数据排序
  • B+树 vs B树
    • B Tree.md（关联笔记尚未公开）
  • 结论
    • 找到了一种在磁盘上和内存中都可以维护的数据结构:b+树。内存中采用b+树实现数据的存储,磁盘上的任何一页对应內存中的b+树-个节点(索引页映射成片孑节点。数据页映射成叶孑节点。最后直观思路得以实现
    • 核心原因:树高度低、每次磁盘IO相对较少、不同请求时间复杂度比较平均

5.2.3. 实现

5.3. 列存储

5.3.1. 使用场景

  • 分析处理的场景经常读取大量行但取少量字段，因此适合用列存储结构

5.3.2. 是什么

  • 不要将所有值从一行存储在一起，而是将每个列中的所有值存储在一起
  • 同样的列会更加易于压缩存储，这样就可以减少大量的工作

6. 物理模型

  • 序列化：将内存中的数据结构转换成磁盘中存储或网络中传输的字节序列
  • 反序列化：将磁盘中存储或网络中传输的字节序列转换成内存中的数据结构

6.1. 文本格式

6.1.1. JSON

  • JSON区分字符串和数字，但它不区分整数和浮点数，也不能确认精度
  • 不支持二进制字符串

6.1.2. XML

  • 不能区分恰好由数字组成的数字和字符串
  • 不支持二进制字符串

6.1.3. CSV

  • 不能区分恰好由数字组成的数字和字符串

6.2. 二进制格式

6.2.1. Thrift

6.2.2. ProtocolBuf

6.2.3. Avro

6.3. 文本 vs 二进制

文本 二进制
优点 可读性高并且自描述 消息紧凑；解析开销小
缺点 消息冗余；解析开销大 可读性差

7. 数据查询语言

7.1. 命令式查询

  • 详细的命令机器怎么（How）去处理一件事情以达到你想要的结果（What）

7.2. 声明式查询

  • 只告诉你想要的结果（What），机器自己摸索过程（How）

7.3. Map-Reduce查询

  • 将大批量的数据拆分执行（Map），然后再将结果合并成最终结果（Reduce）

8. 参考