时间：   |   分类：     |   阅读： 6232 字 ~13分钟

去年就看到总有人推荐这本书(简称DDIA),最初手里只有英文版,缓慢的读了个开头后来就忙别的去了.

今年偶然看到网上有中译版,惭愧的是到了年底,最近几个月才读来.

书的信息量很大,对数据库和分布式系统感兴趣的尤其值得一读.

暂时还剩第三部分没读完,先记些凌乱的笔记.

数据密集型:

  • 数据是主要挑战,涉及数据量,数据复杂度和数据变化速度.
  • 于此对应的是计算密集型.

第一部分:数据系统基础

数据系统设计的基本思想

第一章: 可靠性,可扩展性,可维护性

可靠性:

  • 要设计具有容错/韧性的系统以应对各种故障.
  • 常见的故障种类:
  • 硬件故障
  • 软件错误
  • 人为错误

可扩展性: 用负载参数描述负载

描述性能:

  • Throughout
  • Response Time(客户端感受时间,区别于Latency). 响应时间重视时间分布,即使用百分位而不是平均数

软件系统的三个设计原则

  • 可操作性(运维友好)
  • 简单性(好的抽象)
  • 可演化性/可扩展性/可修改性/可塑性

第二章:数据模型和查询语言

数据模型: 数据的存储和查询等

  • 关系模型: 事务处理和批处理
  • 文档模型: 对多对多和连接(记录之间存在关系)支持较差
  • 图模型

关系模型

存储ID还是文本字符串是个副本(duplication)问题,去除冗余副本是数据库规范化的关键思想.

声明式查询语言(SQL)相对命令式的优势:

  • 比命令式API更简洁和容易
  • 隐藏了数据引擎的实现细节

文档数据库

适用于大多数关系都是一对多关系(树状结构化数据)

文档数据库的应用场景是：数据通常是自我包含的，而且文档之间的关系非常稀少。

准确的说文档数据库 并不是无模式(schemaless),应该是schema-on-read(隐含的数据结构).

JSON表示比多表模式具有更好的局部性(locality).

第三章

主流的两大类存储引擎：

  • 日志结构（log-structured）的存储引擎
  • 面向页面（page-oriented）的存储引擎（例如B树）

日志结构学派

日志/log:仅追加的数据文件. (只允许附加到文件和删除过时的文件，但不会更新已经写入的文件)

哈希索引: Bitcask(Riak默认存储引擎)

SSTables(排序字符串表（Sorted String Table）)制作LSM树/日志结构合并树

Bloom过滤器/布隆过滤器是用于近似集合内容的内存高效数据结构，它可以告诉您数据库中是否出现键，从而为不存在的键节省许多不必要的磁盘读取操作.

LSM树性能优势:

由于数据按排序顺序存储，因此可以高效地执行范围查询（扫描所有高于某些最小值和最高值的所有键），并且因为磁盘写入是连续的，所以LSM树可以支持非常高的写入吞吐量。

就地更新学派

将磁盘视为一组可以覆盖的固定大小的页面。例子:B树.

日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。相比之下，B树将数据库分解成固定大小的块或页面.

为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）/ 重做日志(redo log)

并发控制使用锁存器（latches）（轻量级锁）保护树的数据结构来完成.

根据经验，通常LSM树的写入速度更快，而B树的读取速度更快。 LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。

内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。

数据仓库

数据仓库是一个独立的数据库，分析人员可以查询需要的内容，而不影响OLTP操作。 数据仓库包含公司所有各种OLTP系统中的只读数据副本。 从OLTP数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为"抽取-转换-加载（ETL）"

  • 在线事务处理（OLTP, OnLine Transaction Processing）
  • 在线分析处理（OLAP, OnLine Analytice Processing）

星型模式/维度建模

由事实表和维度表组成.

列存储

第四章:编码与演化

将数据结构转换为网络中的字节或磁盘上的字节的几种方法。我们看到了这些编码的细节不仅影响其效率，更重要的是应用程序的体系结构和部署它们的选项。

服务支持滚动升级需要提供向后兼容性（新代码可以读取旧数据）和向前兼容性（旧代码可以读取新数据）的方式进行编码.

  • 编程语言特定的编码
  • JSON，XML和CSV等文本格式
  • 二进制模式驱动格式

二进制模式驱动格式允许使用清晰定义的前向和后向兼容性语义进行紧凑，高效的编码。

对于静态类型编程语言的用户来说，从模式生成代码的能力是有用的，因为它可以在编译时进行类型检查。

  • Thrift
  • Protocol Buffers
  • Avro

数据流的几种模式

  • 数据库
  • RPC和REST API
  • 异步消息传递(消息代理或Actor模型)

REST似乎是公共API的主要风格。 RPC框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。

第二部分:分布式数据系统

  • 共享架构:
    • 共享内存架构（shared-memory architecture）: 垂直扩展（vertical scaling）或向上扩展（scale up）
    • 共享磁盘架构（shared-disk architecture）: 网络附属存储（Network Attached Storage, NAS）或存储区网络（Storage Area Network, SAN）
  • 无共享架构（shared-nothing architecture）: 水平扩展（horizontal scale） 或向外扩展（scale out）

NUMA: 非均匀内存访问（nonuniform memory access）

数据分布在多个节点上有两种常见的方式：

  • 复制（Replication）
  • 分区 (Partitioning) : 不同的分区可以指派给不同的节点（node）, 亦称分片（shard）

第五章: 复制

单主复制

半同步（semi-synchronous）配置: 在数据库上启用同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。

处理节点宕机

  • 从库失效：追赶恢复
  • 主库失效：故障转移（failover）,需要认真考虑可能的情况

复制日志的实现

  • 基于语句的复制(副作用太大,通常不使用)
  • 传输预写式日志（WAL）
  • 逻辑日志复制（基于行）: 复制和存储引擎使用不同的日志格式
  • 基于触发器的复制: 较灵活,但开销较大

多主复制

多领导者配置（也称多主、多活复制）,通常用于多数据中心.

实现: CouchDB

无主复制

leaderless

复制延迟问题(最终一致性)

  • 读己之写
  • 单调读（Monotonic reads）: 比强一致性（strong consistency）更弱，但比最终一致性（eventually consistency）更强的保证
  • 一致前缀读: 如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现

第六章: 分区/Partitions

键值数据的分区

  • 根据键的范围分区:存在偏斜和热点的问题
  • 根据键的散列分区

分片与次级索引

  • 按文档的二级索引/文档分区索引/本地索引: 分散/聚集（scatter/gather）方法
  • 根据关键词(Term)的二级索引/全局索引

分区再平衡策略

  • 固定数量的分区:创建比节点更多的分区，并为每个节点分配多个分区
  • 动态分区: 按节点比例分区

第七章: 事务

事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制

ACID代表原子性（Atomicity），一致性（Consistency），隔离性（Isolation）和持久性（Durability）

  • 原子性/可中止性（abortability）: 能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。
  • 一致性: 对数据的一组特定陈述必须始终成立。即不变量（invariants）
  • 原子性，隔离性和持久性是数据库的属性，而一致性（在ACID意义上）是应用程序的属性。
  • 隔离性: 同时执行的事务是相互隔离的

并发控制常用的隔离级别

  • 读已提交是一个非常流行的隔离级别,通过使用行锁（row-level lock） 来防止脏写
  • 快照隔离/可重复读: 通常使用多版本对象/多版本并发控制（MVCC, multi-version concurrentcy control）实现
  • 可序列化(Serializability）:通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的

一些可能遇到的问题:

脏读/脏写/读取偏差(不可重复读)/更新丢失/写偏差/幻读/字面意义上的串行执行(单核CPU)/两阶段锁定/可串行化快照隔离（SSI）

MySQL/InnoDB的可重复读并不会自动检测丢失的更新

比较并设置（CAS, Compare And Set）

幻读（phantoms）:即一个事务改变另一个事务的搜索查询的结果

记录系统和衍生数据系统之间的区别不在于工具，而在于应用程序中的使用方式。

第八章: 分布式系统的麻烦

分布式系统与运行在单台计算机上的程序的不同之处：

  • 没有共享内存，只有通过可变延迟的不可靠网络传递的消息
  • 系统可能遭受部分失效
  • 不可靠的时钟和处理暂停

物理时钟:时钟和单调钟

时钟: 根据某个日历（也称为挂钟时间（wall-clock time））返回当前日期和时间,通常程序返回自epoch（1970年1月1日 午夜 UTC，格里高利历）以来的秒数（或毫秒）.需要根据NTP服务器设置同步. 单调钟: 适用于测量持续时间（时间间隔），例如超时或服务的响应时间. 保证总是前进的事实（而时钟可以及时跳回）.单调钟不需要同步.

拜占庭将军问题: 在不信任的环境中达成共识的问题.

第九章: 一致性与共识

共识（consensus）：就是让所有的节点对某件事达成一致

事务隔离主要是为了，避免由于同时执行事务而导致的竞争状态，而分布式一致性主要关于，面对延迟和故障时，如何协调副本间的状态。

最强一致性模型之一: 线性一致性（linearizability）

线性一致性（linearizability）/ 原子一致性（atomic consistency）/ 强一致性（strong consistency）/ 立即一致性（immediate consistency）/ 外部一致性（external consistency ）

基本思想：使系统看起来好像只有一个数据副本,是读取和写入寄存器（单个对象）的新鲜度保证

依赖线性一致性的场景:

  • 锁定和领导选举
  • 约束和唯一性保证
  • 跨信道的时序依赖

CAP定理的正式定义仅限于很狭隘的范围，尽管CAP在历史上有一些影响力，但对于设计系统而言并没有实际价值.

因果一致性为我们提供了一个较弱的一致性模型

版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳(更加紧凑)总是施行一个全序。

线性一致的CAS（或自增并返回）寄存器与全序广播都都等价于共识问题

共识可以解决的问题:

  • 线性一致性的CAS寄存器
  • 原子事务提交
  • 全序广播
  • 锁和租约
  • 成员/协调服务
  • 唯一性约束

ZooKeeper这样的工具为应用提供了“外包”的共识、故障检测和成员服务。

第三部分: 派生数据

第十章: 批处理算法和框架

与Unix设计相通

Unix设计原则包括：输入是不可变的，输出是为了作为另一个（仍未知的）程序的输入，而复杂的问题是通过编写“做好一件事”的小工具来解决的.

在Unix世界中，允许程序与程序组合的统一接口是文件与管道；在MapReduce中，该接口是一个分布式文件系统。

分布式批处理/MapReduce

批处理的常见用途:
搜索,构建机器学习系统，例如分类器（比如垃圾邮件过滤器，异常检测，图像识别）与推荐系统（例如，你可能认识的人，你可能感兴趣的产品或相关的搜索)

分布式批处理框架需要解决的两个主要问题是：

  • 分区: 在MapReduce中，Mapper根据输入文件块进行分区。
  • 容错: MapReduce经常写入磁盘;数据流引擎更多地将中间状态保存在内存中，更少地物化中间状态;确定性算子减少了需要重算的数据量.

分布式批处理引擎有一个刻意限制的编程模型：回调函数（比如Mapper和Reducer）被假定是无状态的. 使得批处理作业中的代码无需操心实现容错机制.

MapReduce的连接算法

  • 排序合并连接
  • 广播散列连接
  • 分区散列连接

数据流引擎的优化

Tez是一个相当薄的库，它依赖于YARN shuffle服务来实现节点间数据的实际复制，而Spark和Flink则是包含了独立网络通信层，调度器，及用户向API的大型框架。

Hive，Spark和Flink都有基于代价的查询优化器可以做到这一点，甚至可以改变连接顺序，最小化中间状态的数量.

图批量处理

在整个图上执行某种离线处理或分析,这种需求经常出现在机器学习应用（如推荐引擎）或排序系统中,最着名的图形分析算法之一是PageRank.

使用批量同步并行（BSP）计算模型,即Pregel模型.

一些概念

事件日志: 描述登录用户在网站上做的事情（称为活动事件（activity events）或点击流数据（clickstream data）.事件日志是事实表，用户数据库是其中的一个维度。

物化（materialization）: 将中间状态写入文件的过程

算子(operators)是Map和Reduce的泛化

高级API和语言:

Mahout在MapReduce，Spark和Flink之上实现了用于机器学习的各种算法

空间算法: 如最近邻搜索（k-nearest neghbors, kNN）

第十一章: 流处理(stream processing)

消息系统的分类:

  • 直接从生产者传递给消费者
  • 消息代理(message broker) / 消息队列(message queue)
    • AMQP/JMS风格的消息代理: 适用于在消息处理代价高昂，希望逐条并行处理，顺序不重要的情况下
    • 基于日志的消息代理: 适用于消息吞吐量很高，处理迅速，顺序很重要的情况下

一个记录/事件(event)由生产者（producer）/发布者（publisher）/发送者（sender）生成一次，然后可能由多个消费者（consumer）/订阅者（subscribers）/接收者（recipients）进行处理.

许多开源分布式流处理框架的设计都是针对分析设计的：例如Apache Storm，Spark Streaming，Flink，Concord，Samza和Kafka Streams。

流处理的几种目的:

  • 搜索事件模式（复杂事件处理）
  • 计算分窗聚合（流分析)
  • 保证衍生数据系统处于最新状态（物化视图）。

流式连接
流处理中可能出现的三种连接类型：

  • 流流连接
  • 流表连接
  • 表表连接

容错

流处理中实现容错和恰好一次语义的技术: 可以使用更细粒度的恢复机制，基于微批次，存档点，事务，或幂等写入。

Spark在批处理引擎上执行流处理，将流分解为微批次（microbatches）, 而Apache Flink则在流处理引擎上执行批处理.

幂等性（idempotence）: 幂等操作是多次重复执行与单次执行效果相同的操作。

第十二章:数据系统的未来

(串联起前边章节的汇总篇)

批处理与流处理

在维护衍生数据时，批处理和流处理都是有用的。流处理允许将输入中的变化以低延迟反映在衍生视图中，而批处理允许重新处理大量累积的历史数据以便将新视图导出到现有数据集上。

Lambda架构
核心思想是通过将不可变事件附加到不断增长的数据集来记录传入数据，这类似于事件溯源。
为了从这些事件中衍生出读取优化的视图, Lambda架构建议并行运行两个不同的系统：批处理系统（如Hadoop MapReduce）和独立的流处理系统（如Storm）。
在Lambda方法中，流处理器消耗事件并快速生成对视图的近似更新；批处理器稍后将使用同一组事件并生成衍生视图的更正版本。

0%