Data Intensive Application

应用设计的三个目标？

  • 可靠性 （应用可以容许部分软硬件异常以及人为操作异常
  • 可维护性（设计便于维护，
  • 可扩展性（在负载甚至需求变化时，可以有效保持系统的稳定运行

应用设计初期需要确定具体的性能（指标要求）。

相对于平均响应时间，百分位（或者中位数）更能满足系统的性能评估，例如 RT 的中位数为 200ms，说明50%的用户 RT 小于200ms，更能体现用户使用情况。

关系模型、文档模型、图模型

关系模型是指类似 MySQL 这类的 RBDMS。

该模型将数据以关系为维度聚合，在 SQL 种称为表，每个关系元组称为行。

文档模型类似于 MongoDB，将一系列相关的数据以 JSON 或者 XML 的形式保存在一起。

文档模型具有更好的局部性，例如一份简历，文档模型可以很快的查出完整的简历数据（不管是 JSON 还是 XMl），但是关系模型往往需要链接多个表产生完整的数据。

但是文档模型联结能力不强，这往往需要在业务中模拟链接的过程。

（关系模型的范式基本不需要考虑，在特定的场景下，数据冗余往往能带来更好的性能。

文档模型不会对数据强制执行模式，也就是无模式（MongoDB 中可以指定 Document 中某些 required 的字段，但是大部分字段都是可以为空的）。

这会带来一定的误导性，但是在需要修改数据格式的时候会更加方便。

（例如 MySQL 如果执行 MDL 语句会直接锁表重造，所以速度会非常感人，而 MongoDB 如果需要改，直接改就好了，应用中可以覆盖旧数据。

如果数据大多是一对多的关系（树型结构）甚至于说记录之间没有关系，那么文档模型是最合适跌。

但多对多的情况下，文档模型不占任何优势，但是某些只关心一对多甚至一对一的系统中，文档模型也不是不能用。

文档模型的数据应该尽量小。

（跳过了图模型。

数据存储与检索

数据库可以分为日志结构和面向页的两种，工作类型可以分为事务型和分析型。

索引是为了加速数据的查找过程，另外索引也会拖慢查询的性能（你需要额外去维护这部分数据。

Hash 索引

通过 Hash 算法找到数据在文件的偏移量，并直接提取。

Hash 的问题有以下几个：

  1. Hash 数组需要完全放入内存（针对磁盘的 Hash 会存在大量的随机 IO，并且难以处理冲突。
  2. 对于区间查询效率非常低。

（这里又扯到了单文件追加写的记录形式，这样子写的好处有以下几个：

  1. 追加写的性能更好（尤其在磁盘中。
  2. 不会存在修改到一半的旧值（可以完整保存旧值，方便新值奔溃后造成丢失。

为了避免日志占用大量的磁盘，可以将日志分为多个段（日志段，每段日志表示一部分数据，参考 Kafka。

每段文件在达到一定的大小之后关闭，并且对旧段可以进行合并，以节省磁盘空间，也降低崩溃后的恢复时间。

SSTable（排序字符串表，它要求 k-v 的数据对按照 key 的顺序排列，当然保证 key 的唯一。

相对于追加写（乱序写），SST 有如下几个优点：

  1. 更加方便压缩（相同的 Key 保存在同个段，即使跨段，从新段开始遍历，旧段肯定是旧值
  2. 文件的头尾字符串就形成了索引，不需要保存所有的 Key 到内存中
  3. 提高范围查询性能

为了维护 Key 的有序性可以使用类似 R-B Tree（红黑树） 或者 AVL树的数据结构。

以 SSTable 为基础的存储引擎的工作流程：

  1. 写入时，先添加到内存表中（保存在内存中的平衡树。
  2. 当内存表大于某个阈值的时候，将其落盘。
  3. 查找时，先查询内存表，然后按照段的新旧顺序往后查询（后段肯定更新，查到为止。
  4. 后台进程周期性的合并和压缩段文件，并删除旧文件。

为了避免奔溃的时候内存表中的数据丢失，可以使用部分的乱序写来备份（乱序指的是 Key 乱序，写文件还是按照请求顺序。

（这里的逻辑就是 WAL，内存表中的数据以日志的形式先落盘，内存表落盘的时候可以清除这部分日志。

以上的描述基本就是 LSM（Log-Structured Merge-Tree，日志结构合并树？

Lucene 使用了该种方式保存词典（词典就是单词和对应文档的映射关系，也算是 k-v 结构。

B-Tree 结构

B-Tree 将数据库分解成固定大小的块或者页（传统上 4K），页是内部读写的最小单元，并且每个页面都可使用地址标识。

查找的时候总是从 B-Tree 的根节点出发，B-Tree 的每个节点都包含若干个键以及对子页的引用，每个节点都负责一部分，每个节点所包含的子页数量称为分支因子。

更新 B-Tree 的时候，首先找到现有键所在的数据页，并且更新该页的值，如果此时该页不够容纳新数据，就会出现页分裂（MySQL 中主键递增的原因，页分裂很拉效率。

和 LSM-Tree 相比，B-Tree 是在旧值上修改，因此更新操作不会改变任何原有的引用（LSM-Tree 是追加写，旧值失效了。

B-Tree 的 crash-safe 通常通过额外 WAL（write-ahead log，预写日志）来实现，这是一个仅支持追加修改的文件，每个 B-Tree 的修改操作都必须先更新 WAL 然后再更新树本身，奔溃后根据 WAL 恢复。

（WAL 和 SSTable 中为了防止内存表丢失的策略基本一致吧。

对 B-Tree 的优化：

  1. 不使用 WAL，而是使用 写时复制（COW，Copy On Write）来实现，修改的页面完整复制并写入不同的位置，更新之后替换父页的索引位置。
  2. 不保存完整的键信息，只保存缩略信息，使每一页具有更高的分支因子，从而降低树高度，减少 IO。
  3. 考虑到范围查询的需要，可以将相邻的叶子页以顺序保存在磁盘上。
  4. 添加额外的指针，使同级的页面可以向左右扫描，而不用跳回到父节点（也算是范围查询的需要，个人感觉优于3。

LSM-Tree 和 B-Tree 的对比：

  1. LSM Tree 的写入更快，而 B-Tree 的查询更快（通常情况下，因为 LSM-Tree 只需要一个追加写，而 B-Tree 写涉及更多，但是 B-Tree 的读最坏就是树高次 IO，而 LSM-Tree 的读取最坏需要遍历所有的段。
  2. LSM-Tree 在压缩过程有时会干扰正在进行的读写

其他索引类型

  1. 主键索引（唯一，每个索引项都能唯一指向一条行记录
  2. 二级索引（非唯一，可能存在多行相同的键值
  3. 聚集索引（索引中直接保存行数据）和非聚集索引（索引仅仅保存数据引用）

内存数据库为什么更快，根本原因不是因为不用进行磁盘的 IO，像 MySQL 和 Redis 的对比，MySQL 可以设置更大的内存池，这样也可以避免磁盘的 IO，但是速度肯定还是不如 Redis的。

主要原因还是 内存数据库避免使用写磁盘的格式对内存数据结构编码的开销，就算使用内存 MySQL 也是 B-Tree 查询的时间复杂度是 O(logN)，Redis 是接近 O(1) 的复杂度。

数据访问模式被分为 OLTP（Online Transaction Processing，在线事务处理）以及 OLAP（Online Analytic Processing，在线分析处理）两种。

相对来说 OLAP 处理的数据量更多一点，写入更倾向于批量有序写入。

数据仓库，数据仓库包含所有 OLTP 系统的只读副本。

从 OLTP 数据库中（使用周期性数据转储或连续的更新流）中提取数据，转化为友好分析的模式，执行必要的清理，然后加载到数据仓库中。

简化为 提取-转换-加载（Extract- Transfrom-Load，ETL）

为什么不使用语言原生编码库：

  1. 语言自身的编码库往往和语言深度绑定，一般情况下无法跨语言
  2. 安全性问题（？
  3. 前后兼容问题
  4. 效率问题（尤其是 Java

XML，JSON，CSV 算是比较通用的编码格式。

XML 和 CSV 中无法区分数字和字符串（碰巧由数字组成），JSON 可以区分字符串和数字，但不能区分浮点数和整数，也不包含精度。

JSON 和 XML 支持 Unicode 编码，但是不支持二进制字符串（所以会有 Base64 编码

CSV 没有任何模式，APP 中自行定义每行每列的含义。

常用的二进制编码库：Thrift，Protocol Buffers，都需要模式来编码任意的数据（都需要使用 IDL 定义模式。

// thrift
struct Person{
  1: required string userName,
  2: optional i64 favoriteNumber,
  3: optional list<string> interests
}

三种数据跨进程传递方式：

  1. 数据库
  2. 异步消息系统（MQ
  3. RPC/REST

SOA（Service-oriented architecture，面向服务的体系结构），也就是目前常说的微服务体系。

RPC（Remote Procedure Call，远程过程调用），试图使向远程网络服务发起的请求看起来与在同一进程中调用编程语言中的函数或者方法相同。

分布式数据系统

需要分布式的原因：

  1. 扩展性（单机难免有物理性能，例如内存，IO，CPU的限制
  2. 容错和高可用性（单点故障问题，节点宕机会导致服务整个不可用
  3. 延迟考虑（根据网络进行异步部署，用户就近访问降低延迟

无共享结构（水平扩展），每个节点独立使用本地的硬件系统，通过以太网协调通信对外提供统一的服务。

复制和分区（常见的数据多节点分发方式：

  1. 复制

在多个节点上面保存相同数据的副本，作为数据冗余强化数据安全性保证，也可以通过副本对外提供查询服务，提高读写性能。

  1. 分片

讲一个大数据拆分撑几个小的子集，不同子集在不同的节点。

五、 数据复制

复制就是通过网络通信的方式在多个节点上保存相同的数据副本。

三种复制方式：

  1. 主从复制

复制还可以分为同步复制和异步复制。

同步复制指的是主节点是否需要等待（所有）从节点确认复制成功，再返回客户端写入成功。

同步复制可以保证从节点数据是最新的，能有一个足够安全的数据备份，但是往往会因为从节点写入延迟而影响整体的性能。

异步复制则是完全放开，主节点写入成功就返回成功，性能最高，但是在主节点宕机后可能会丢失少量未备份的数据。

还有一种半同步复制，是指部分从节点走同步复制，而部分节点走异步，如果同步过慢可以从异步节点中挑选一个升为同步。

（Redis 是完全异步的复制，MySQL 可以选择同步，异步，半同步。

  1. 多主节点复制

无主节点复制

results matching ""

    No results matching ""