《数据密集型应用系统设计》读书笔记

2022年6月16日 209点热度 0人点赞 0条评论

个人读书笔记,有些地方用词不够严谨(欢迎评论指正),见谅。书籍链接

笔记是个人理解,与书籍可能有偏差,建议看书。

问题:

  • 什么样的数据适合图数据库?

    社交关系?网页数据?地图数据?

  • mysql有没有事务重试?

  • 更新数据时,是按行更新还是按页更新?
  • 更新数据时,是采用copy on write还是直接修改?

第一部分 数据系统的基石

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

可靠性

  • 硬件故障:机房断电、硬盘崩溃等
  • 软件错误:数据库异常、缓存异常等
  • 认为错误:业务bug、运维失误等

允许部分服务可不用(不影响整体系统),最后同一个服务有多个提供者(集群)

可伸缩性

  • 吞吐量:每秒可以处理的记录数量
  • 延迟:包括网络延迟、排队延迟(多个请求需要排队)
  • 响应时间:包含服务器的处理事件以及延迟,一般取中位数而不是平均数

可维护性

  • 代码尽量抽象封装
  • 运维方后续讨论

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

关系模型与文档模型

相对应的就是关系型数据库以及NoSQL(文档型MongoDB,图数据库等)

对象关系不匹配

拿简历举例:

简历包含有工作经历、教育经历

  • 在关系型数据库中,会分基本信息表、工作经历表、教育经历表等
  • 在文档数据库中,只有一张表(教育经历等用数组表示)

如果场景都是要加载全部数据,那么适合使用NoSQL

多对一和多对多的关系

  • NoSQL支持关联查询,但是性能不好
  • 多对多关系更使用关系型数据库

关系型数据库与文档数据库在今日的对比

灵活性

  • 读时模式:文档型数据库,数据的结构是隐含的(就是数据也是有结构的),只有在数据被读取时才被解释
  • 写时模式:关系型数据库,数据结构由数据库保证,写入时校验

mysql5.7开始增加对json的支持,mysql8.0进一步优化的json支持

数据查询语言

  • SQL
  • MapReduce

图数据模型

  • 顶点(vertex):表示一组属性(比如人、地址、职业等)
  • 边(edge):表示关系,有起点和终点(xxx出生在xxx,xxx的职业是xxx)

和文档型数据库一样,不会在保存时强制格式。

查询时无法确定级联层数???

第三章:存储与检索

驱动数据库的数据结构

  • 哈希索引

    优点:速度快

    缺点:全部放入内存。无序,所以对顺序范围等查询不友好

  • SSTable和LSM树

    因数据结构以及顺序写,保证的写入的性能

    MemTable:数据首先放在内存中,按key排序

    Immutable MemTable:MemTable达到一定大小后,会转化成Immutable MemTable。写操作由新的MemTable处理,Immutable转成SSTable

    SSTable:已持久化。不同SSTable可能存在相同的key,以最新的为准。SSTable达到一定层数,会触发合并,此时冗余的旧key会被去除

  • B树

    mysql使用的B+树是B树的增强版

  • 比较B树和LSM树

    B树写入慢,读取快。LSM树写入快,读取慢。

    LSM写入同等数据需要磁盘IO比B树少

    LSM压缩比B树好,因为B树的空字段、页结构等,会存在少量不被使用的空间。

    LSM需考虑压缩和写入的比

事务处理还是分析

  • 在线事务处理(OLTP)
  • 在线分析处理(OLAP)
  1. 星型模型:一个事实表(存主要数据,比如人的基本信息),多个纬度表(关联表,存关联数据,比如人的浏览历史)
  2. 雪花模型:星型模型的变体,某些纬度被进一步分解为子纬度(3层表联查)

列存储

数仓的事实表基本都是大宽表,字段较多(100列)

  • 不会采取select * 的方式查询数据
  • 可以考虑列存储,列式存储很适合压缩(数据重复率高,比如男、男、女、男、女、女)

第四章:编码与演化

  • 文本格式:JSON、XML、CSV
  • json不支持二进制字符串以及对数字类型不够友好,比如无法准确表达int和float,比如20不知道是int还是float
  • 二进制格式:Thrift、Protocol Buffers、Avro
  • 数据流:

    数据库中的数据流

    服务中的数据流:REST和RPC

    消息传递中的数据库(消息队列)

  • 注意向前和向后兼容:

    对于RESTful API,常用的方法是在URL或HTTP Accept头中使用版本号

第二部分:分布式数据

第五章:复制

主从复制

  1. 同步复制:从库写入成功,主库才能继续写入
  2. 一般是一个主库,一个同步从库,多个异步从库,称为:半同步
  3. 链式复制:更多低等级从库从高等级从库拉取数据,而不是从主库拉取
  4. 设置新从库
    1. 获取主库快照,并导入
    2. 导入从快照时刻开始的binglog
  5. 故障切换
    1. 异步复制时主库故障,从库提升为主库,
      1. 从库数据不是最新
      2. 主库从新加入时可能有冲突写入(处理:丢弃未写入从库的数据)
      3. 如果数据库有与其他外部存储(比如缓存)协调,错误参考上一条
  6. 复制日志的实现
    1. 基于sql的复制,会因为sum、now等语句产生不确定性
    2. 不确定性的语句使用基于行的复制

复制延迟的问题

保证最终一致性。一是性能方面的考虑,二是数据离用户越近,延迟越小(CDN?)

  1. 读己之写

    用户不想延迟看到自己提交的数据(写入主库,但是读取从库时还没更新)

    解决方案:

    • 只有单一用户能修改的东西(例如个人资料),可以写入主库,本地放一份到缓存(设置超时),本地读取缓存的,没有再去读从库
    • 记住写入的时间戳,从库未到达改时间戳,不返回数据
  2. 单调读

    确保每个用户总是从同一个副本读取,否则会出现两次查询,副本a有数据,副本b没有

  3. 一致前缀读

    如果一系列写入按某个顺序发生,那么任何人读取这些写入时,也会看见它们以同样的顺序出现。

    比如顺序为ab,但是读取到ba,常见于分区、分片

    解决方案:保证因果相关的写入都写入相同的分区(分区划分策略?)

  4. 复制延迟的解决方案

    事务???

多主复制

  1. 场景
    1. 对不同表的复制划分到不同主库写入?
    2. 容忍延时或者离线的写入?
  2. 处理写入冲突
    1. 冲突时,使用版本最高的数据
    2. 自定义冲突解决逻辑
  3. 多主复制拓扑

    MySQL仅支持环形拓扑,即只接收一个节点的写入和自己的写入。也类似与星型拓扑。

无主复制

  1. 当节点故障时写入数据库

    同时写入多节点,过半成功则成功。同时读取多节点,取最新版本的数据。

    • 读修复和返熵
      1. 读修复:并行读取多节点,返回最新版本数据,有副本存在旧数据的,则更新
      2. 反熵过程:轮询比较差异,补齐差异
    • 读写的法定人数

      n个副本(不是节点),写入w个节点,读取r个节点,则 w + r > n

      这样才能保证每次读取至少有一个节点是最新的

      节点可能大于副本数,有可能两个节点组成一个副本(分区)

  2. 法定人数一致性的局限性

    1. 性能问题(并发写入、读取过多节点,取时间最长的)
    2. 部分节点宕机,导致写入失败
  3. 宽松的法定人数与提示移交
    1. 宽松的法定人数:写和读仍然需要w和r成功的响应,但这些响应可能来自不在指定的n个“主”节点中的其它节点。
    2. 提示移交:一旦网络中断得到解决,代表另一个节点临时接受的一个节点的任何写入都被发送到适当的“主”节点。
  4. 运维多个数据中心

    法定人数配置只限定在本地数据中心,并异步将数据同步到其余数据中心。

检测并发写入

  1. 最后写入胜利(LWW)

    保留最后版本数据,其他版本

  2. 捕获”此前发生“关系

    就是每个连接(客户端)记录并维持自己的版本号,只修改自己版本的东西

第六章:分区

在MongoDB,Elasticsearch和Solr Cloud中被称为分片(shard),但是分区(partitioning)** 是最约定俗成的叫法。

分区与复制

一个大型数据库可以拆分成多个分区,分区也可以复制(主从、无主等)

键值数据的分区

  1. 根据键得范围分区
  2. 根据键的散列分区(hash)

    破坏了排序,使得范围查询效率低下,但可以更均匀地分配负载

  3. 负载偏斜与热点消除

    这属于设计阶段的问题,目前设计系统没有自动检测和补偿偏斜的工作负载。

分区与次级索引

  1. 基于文档的次级索引进行分区

    每个分区维护自己的索引,也叫本地索引。即分区0,分区1都可能存在color=red的索引数据

  2. 基于关键词的次级索引进行分区

    也叫全局索引。一定范围的索引数据汇聚到同一个分区,比如首字母从ar的颜色在分区0中,sz的在分区1。就是分区1的索引可能被存到分区1中。

    分区同时存数据以及索引数据。

    缺点:写入速度较慢且较为复杂

分区再平衡

就是分区的增减,节点故障等导致的数据、请求、负载转移的过程,叫再平衡。

  1. 再平衡策略
    1. 固定数量的分区

      初始创建好固定数量的分区,增加节点时,帮其他节点接管一部分分区。比如初始4个节点,20个分区,每个节点5个分区。当增加一个节点时,每个节点那管理4个分区。

      缺点:初始很难定好总分区数。分区数量不正确会影响性能。

      Riak、ES、Couchbase、Voldemort使用了此方法。

    2. 动态分区

      当分区增长到超过配置的大小时,会被分成两个分区。与之相反,分区缩小到某个阈值以下,则合并。

    3. 按节点比例分区

      每个节点具有固定数量的分区,新节点加入集群时,所以选择固定数量的现有分区拆分,一人一半。

请求路由

查询要转发到哪个节点,问题概括为服务发现

三种方案:

  1. 请求节点0,节点0说没有,知道节点1有,转发到节点1,节点1返回节点0,节点0返回客户端。
  2. 统一路由转发。客户端 → 路由 → 节点。
  3. 客户端知道分区和节点的分配,请求时直接到相应的。(Eureka?)

第七章:事务

事务的棘手概念

  1. ACID的含义
    • 原子性(atomicity)
    • 一致性(consistency)

      原子性,隔离性和持久性是数据库的属性,而一致性(在ACID意义上)是应用程序的属性。

    • 隔离性(isolation)

      同时执行的事务是相互隔离的。

      可串行化级别:事务串行执行,上一个事务没结束,下一个事务不会开始执行。

    • 持久性(durability)

  2. 对象和多对象操作

    • 处理错误和中止

      发生错误时,事务可以中止并安全地重试。

      事务重试仅在临时性错误(例如,由于死锁,异常情况,临时性网络中断和故障切换)后,永久性错误(违反约束等)重试是无意义的。

弱隔离级别

即非串行化的级别

  1. 读已提交

    解决脏读和脏写。就是只有数据在commit的一刻才全部生效。

  2. 快照隔离和可重复读

    1. 可重复读:事务a读取name=’a’ → 事务b提交name=’b’ →事务a只要未提交,读取多少次name都是a
    2. 实现快照隔离:多版本并发控制(MVVC)
  3. 防止丢失更新

    丢失更新:事务a、b同时修改同一条数据,后提交的事务会覆盖前事务修改的数据。

    自动检测丢失的更新:Oracle的可串行化隔离级别,可自动检测到丢失更新,并终止惹麻烦的事务。(mysql没有)

    解决方案:

    1. 读取时就锁定,不允许别的事务读(这样mvcc就没意义了)。比如select xxx FROM table for update;
    2. cas,写入时再比较一次
  4. 写入偏差与幻读

    写偏差:两个事务正在更新两个不同的对象。丢失更新是两个事务更新同一个对象

    举例:医院规定最少有一人值班,医生a、b同时请假,事务A、B各自修改了a、b的值班状态。最后0人值班。

    解决方案:

    1. 锁住整个表
    2. 真正的串行化

可串行化

为什么数据库默认都不使用串行化?

  • 真的串行执行

    在单个线程上按顺序依次只执行一个事务,正是可串行化的定义。

    Redis实现的就是串行执行事务(旧版redis是单线程)

    1. 在存储过程中封装事务

      传统多语句事务:

      1. select结果 → 应用程序
      2. 应用程序判断 → update

      以上经过了两次io,在不允许并发的可串行化中,吞吐量会很差。

      出于这个原因,具有单线程串行事务处理的系统不允许交互式的多语句事务。(还是redis)

    2. 分区

      将数据划分多个分区,一个事务查询一个或多个分区。只要多个事务查询的分区互不冲突,就可以并发执行事务。这种串行化比单分区事务慢。

  • 两阶段锁定

    两阶段锁定(2PL,two-phase locking),不是2PC

    • mysql的默认隔离级别为可重复读(mvcc是实现此隔离级别的技术),在此级别下,如果两个事务同时尝试写入同一个对象,则锁可确保第二个写入必须等到第一个写入完成事务(中止或提交),然后才能继续(防止脏写)。

      事务A修改了id=3的数据,不会阻塞事务B的读,但是B读的是B开启事务时的旧数据。

    • 在2PL中,写入不仅会阻塞其他写入,也会阻塞读,反之亦然。快照隔离使得读不阻塞写,写也不阻塞读。

      事务A修改了id=3的数据,事务B会被阻塞,直到事务A中止、提交或者回滚。

    1. 实现两阶段锁

      2PL用于MySQL(InnoDB)的可串行化、SQL Server的可串行化、DB2的可重复读隔离级别。

    2. 2PL的性能

      因为2PL会导致阻塞,在事务中越早获取独占锁,就阻塞越久。且容易导致死锁。

    3. 谓词锁

      2PL无法解决幻读问题,因此需要引入谓词锁。

      在2PL级别下的幻读问题如下:

      // 1.事务A读取
      select name from student where id=2;// 结果 name='jack'
      // 2.事务B修改
      update student set name='rose' where id=2;
      // 3.事务A第二次读取,id=2的数据,会被阻塞
      // 4.事务B提交,释放锁
      // 5.事务A第二次读取的结果返回 name='rose',此时出现了幻读
      

      谓词锁即共享读,排斥写

      例如:

      // 1.事务A读取(创建谓词锁)
      select name from student where id=2;// 结果 name='jack'
      // 2.事务B读取
      select name from student where id=2;// 结果 name='jack'
      // 3.事务B修改
      update student set name='rose' where id=2;// 此时会被阻塞直到事务A提交
      

      关键思想是,谓词锁甚至适用于数据库中尚不存在,但将来可能会添加的对象(幻象)。如果两阶段锁定包含谓词锁,则数据库将阻止所有形式的写入偏差和其他竞争条件,因此其隔离实现了可串行化。

    4. 索引范围锁

      谓词锁性能不佳:如果活跃事务持有很多锁,检查匹配的锁会非常耗时。因此引入索引范围锁(index-range locking,也称为next-key locking)

      通过使谓词匹配到一个更大的集合来简化谓词锁是安全的。

      例如:如果有在12:00 ~ 13:00预定123号的房间,则锁定123号房间的所有时间段或者锁定12:00 ~ 13:00的所有房间。

      这是匹配开销和阻塞开销的平衡。

    5. 可串行化快照隔离

      可串行化快照隔离(SSI, serializable snapshot isolation)

      和mvcc类似,但是在事务提交时(写入操作),会判断事务期间操作的数据时候已被其他操作修改,如被修改,则事务提交失败

      // 1.事务A查询
      select name from student where id=2;// name='jack'
      // 2.事务B修改
      update student set name='rose' where id=2;
      // 3.事务A再次查询
      select name from student where id=2;// name='jack'
      // 4.事务A修改
      update student set name='张三' where id=2;
      // 5.事务B提交
      // 6.事务A提交,报错。因为事务B修改了数据。
      

      Q:为什么不在第4步的时候就报错,而是等待提交时才检测?

      A:如果事务A是只读事务,即没有第4步的update,则没有写入偏差的风险。

      Q:如果事务B的提交放到第三步之前呢,事务A的再次查询会异常吗???

      A:我猜测会,否则就不是串行化了。实际结果如何,求大神解答

      可串行化快照隔离的性能

      与2PL相比,写不阻塞读,且读取运行在一致性快照上。

      与串行执行相比,事务能在保证可串行化隔离的同时读写多个分区的数据,很好利用了多核cpu的性能。

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

不可靠的网络

  1. 真实世界的网络故障

    主要分3类:

    • 客户端发送途中失败
    • 服务端处理失败(宕机、端口不通等)
    • 服务端处理成功,客户端接收返回失败(返回到半路就挂了)
  2. 检测故障
    • 心跳校验节点存活
    • 主从模式中,主节点失效,从节点选举产生新主节点
    • HBase中,如果节点进程崩溃,但节点的操作系统任在运行,则脚本可以通知其他节点有关该崩溃的信息,以便另一个节点可以快速接管,而无需等待超时到期
  3. 超时与无穷的延迟
    • 网络交换机有出口缓冲,大量的请求会导致部分被交换机丢弃(桶漏算法?)
    • 服务端处理请求时间(响应时间)过长,也会超时
    • 虚拟机等待CPU执行权限
    • 部分情况会限制请求发送速度导致拥堵(发起方)
  4. TCP与UDP
  5. 同步网络与异步网络

    同步:建立一个电路,在两端之间的整个线路分配一个固定的、有保证的带宽量,延迟是固定的。

    以太网和IP是分组交换协议。需排队,延迟不好计算。

不可靠的时钟

  1. 单调钟与日历时钟
    • 日历时钟:根据某个日历,返回日期和时间。与NTP同步时,可能会发生时间回跳。
    • 单调钟:适用于测试持续时间(时间间隔)
  2. 时钟同步与准确性
    • 机器的温度会导致石英钟出现偏差
    • 闰秒导致一分钟有59秒或61秒。NTP可以在一天中逐渐执行闰秒调整。
  3. 依赖同步时钟

    机器上的时钟读数不一定和实际时间一直(有误差),但是大概率在置信区间内。

    分布式系统的事务id无法用时间戳(因为不同机器的时间误差),但是Spanner可以(用的是时间置信区间,不是准确的时间戳)

  4. 进程暂停

    有很多因素导致线程暂停(进程暂停也体现在线程中)

    • jvm的stop the world
    • 虚拟机挂起(有时用于虚拟机从一个主机到另一个主机的实时迁移)
    • 线程上下文切换

    因此时间戳是不安全的,有可能上一刻是10S,下一刻就20S了,但这对机器无感(线程暂停)

知识、真相与谎言

  1. 真相由多数所定义
    • 少数服从多数
    • 防护令牌:分布式锁?
  2. 拜占庭故障

    节点可能撒谎,导致选举出错误的领导。

    此问题更多出现在区块链领域。分布式系统因为节点由用户组织,通常假设没有此问题。

  3. 系统模型与现实

    系统模型是对现实的简化抽象

第九章:一致性与共识

一致性保证

最终一致性属于弱一致性。

强一致性包括:顺序一致性和线性一致性。

线性一致性

线性一致性背后的基本思想很简单:使系统看起来好像只有一个数据副本。

在一个线性一致的系统中,只要一个客户端成功完成写操作,所有客户端从数据库中读取数据必须能够看到刚刚写入的值。

  1. 线性一致性与可串行化

    可串行化:事务的隔离属性。确保事务按照某种顺序依次执行。

    线性一致性:读取和写入寄存器(单个对象)的新鲜度保证。它不会将操作组合为事务

    基于两阶段锁定的可串行化实现或真的串行执行通常是线性一致性的。

  2. 依赖线性一致性与可串行化

    1. 锁定和领导选举

      在单主复制系统中,为确保不出现脑裂,可使用分布式锁。

    2. 约束和唯一性保证

      有唯一性约束时,写入数据需要线性一致性。一个写入,需要所有节点返回成功才算成功?

    3. 跨信道的时序依赖

      例子:在事务中发送MQ,此时事务未提交,为写入数据库,但MQ的接受者已经在处理,导致查不到数据。

  3. 实现线性一致的系统

    • 单主复制(可能线性一致)

      非脑裂情况下,可能线性一致。线性一致性的读取请求从主库读取,而不是从库。

    • 共识算法(线性一致)

    • 多主复制(非线性一致)
    • 无主复制(也许不是线性一致的)
  4. CAP定理没有帮助

    一致性(Consistency)、可用性(Availability)、分区容错性(Partition tolerance)

    CAP三选二有误导性,因为网络分区是一种故障类型,所以不是一个选项:它永远有可能发生。

    多核CPU上的内存甚至都不是线性一致的(CPU高速缓存)。

    牺牲线性一致性的原因是性能,而不是容错。

顺序保证

如果一个系统服从因果关系所规定的顺序,我们说它是因果一致(causally consistent) 的。

  1. 顺序与因果关系
    1. 全序(total order) 允许任意两个元素进行比较,所以如果有两个元素,你总是可以说出哪个更大,哪个更小。

      a和b有因果,c和d有因果,但是{a,b}和{c,d}无因果,无法比较,所以因果顺序不是全序的。

    2. 线性一致性强于因果一致性。线性一致性必定满足因果性,反之,因果性,不一定满足线性一致性

  2. 序列号顺序

    单主复制中,由主库生成序列号,从库始终是因果一致的。

    1. 非因果序列号生成器
      • 一个节点奇数序列,一个节点偶数序列(负载偏斜会导致奇数远远大于偶数,或者偶大于奇)
      • 时间戳
      • 预先分配序列号区块(A:1-1000, B:1001-2000)(A一次性写入2000数据,会不够用)
    2. 兰伯特时间戳

      ddia1-1

      每次请求都携带序列号,且节点也返回序列号,发现序列号低了,就更新到最近的序列号。

      问题:保证了操作的全序,但是数据的全序如何保证?全序广播?

  3. 全序广播

    有点像消息队列(TOPIC模式)

    需要满足两个安全属性:

    • 没有消息丢失,1个节点收到,全部节点也能收到
    • 以相同顺序传递给所有节点

    全序广播能实现线性一致的存储,但因为广播是异步的,不能保证消息何时送达,所以不能保证线性一致的读取。

分布式事务与共识

原子提交的前提是达成共识。

  1. 共识的不可能性

    如果存在节点可能崩溃的风险,则不存在总是能够达成共识的算法。

  2. 原子提交与两阶段提价

    2PC分为协调者与参与者。如果协调者在发送准备请求之前失败,参与者可以安全地中止事务。但是,一旦参与者收到了准备请求并投了“是”,就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。(阻塞)

    参与者互相沟通不属于2PC范畴。

  3. 实践中的分布式事务

    • 异构分布式事务

      参与者是由两种或两种以上的不同技术组成的。

    • XA事务

      跨异构技术实现两阶段提交的标准

    • 从协调者故障中恢复

      当协调者重新启动但丢失了日志,会导致参与者一直持有锁并阻塞。许多XA的实现都有一个叫做启发式决策(heuristic decisions) 的紧急逃生舱口:允许参与者单方面决定放弃或提交一个存疑事务,而无需协调者做出最终决定。(破坏原子性)

  4. 分布式事务的限制

    • 许多协调者实现默认情况下并不是高可用的,或者只有基本的复制支持。
    • 分布式是增加容错,而事务又降低了容错,这两者矛盾。

容错共识

  • 一致同意:没有两个节点的决定不同
  • 完整性:没有节点决定两次
  • 有效性:如果一个节点决定了值v,则v由某个节点所提议
  • 终止:由所有未崩溃的节点来决定最终决定值
  1. 共识算法和全序广播

    问题:全序广播相当于重复进行多轮共识???

  2. 纪元编号和法定人数

    每次领导选举递增一次纪元编号,出现脑裂情况时,以纪元号高的为主。

    如果一个提案的表决通过,则至少得有一个参与投票的节点也必须参加过最近的领导者选举。

  3. 共识的局限性

    网络故障导致频繁选举领导。

成员与协调服务

  • 线性一致性的原子操作:如果多个节点同时尝试执行相同的操作,只有一个节点会成功。
  • 操作的全序排序:可重入锁。(不懂这个的使用场景)
  • 失效检测
  • 变更通知

第三部分

  • 记录系统

    也称为真相源,持有数据的权威版本

  • 衍生数据系统

    通常是另一个系统中的现有数据以某种方式进行转换或处理的结果。如果丢失衍生数据,可以从原始来源重新创建。典型的例子是缓存。

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

第十章:批处理

  • 服务(在线系统)

    响应及时

  • 批处理系统(离线系统)

    一个批处理系统有大量的输入数据,跑一个作业(job) 来处理它,并生成一些输出数据。批量作业通常会定期运行

  • 流处理系统(准实时系统)

使用Unix工具的批处理

Unix管道

MapReduce和分布式文件系统

mapper读取输入 → 排序 → 按分区复制到Reducer → 排序

MapReduce不支持中间态???就是不能像unix的管道一样,一个接一个。

Hadoop与分布式数据库对比

  • 存储多样性:各种文件
  • 处理模型的多样性
  • 针对频繁故障设计

第十一章:流处理

传递事件流

  1. 直接从生产者传递给消费者

    要求低延时,即直接接口请求?RPC或者http?

    ZeroMQ 【9】和nanomsg

  2. 消息代理

    也就是消息队列

    有两种主要的消息传递模式:

    • 负载均衡:每条消息都被传递给消费者之一
    • 扇出:每条消息都被传递给所有消费者。

    确认与重新传递:

    ack以及不保证消息顺序

  3. 分区日志

    传统JMS/AMQP风格的消息队列,消息被消费后就被删除了。

    而基于日志的消息代理(生产者通过将消息追加到日志末尾来发送消息,而消费者通过依次读取日志来接收消息),则能保留历史数据,且不影响性能。(kafka就是基于日志的,blink好像也是。)

    消息处理代价高昂,希望逐条并行处理,以及消息的顺序并没有那么重要的情况下,传统JMS/AMQP风格的消息代理是可取的。另一方面,在消息吞吐量很高,处理迅速,顺序很重要的情况下,基于日志的方法表现得非常好。

数据库与流

  1. 保持数据同步

    异构数据系统中数据同步使用(总不能mysql和oracle使用binlog吧)

  2. 变更数据捕获

    比如解析binlog?

  3. 事件溯源

    事件溯源是DDD领域的,基于事件日志派生出当前状态,关注的是过程,而不是结果。储库使用CQRS模式。

    CQRS — Command Query Responsibility Segregation,故名思义是将 command 与 query 分离的一种模式。核心思想是将这两类不同的操作进行分离,然后在两个独立的「服务」中实现。Command 与 Query 对应的数据源也应该是互相独立的,即更新操作在一个数据源,而查询操作在另一个数据源上。当 command 系统完成数据更新的操作后,会通过「领域事件」的方式通知 query 系统。query 系统在接受到事件之后更新自己的数据源。所有的查询操作都通过 query 系统暴露的接口完成。

    ddia1-2

    事件溯源的哲学是仔细区分事件(event) 和命令(command)。当来自用户的请求刚到达时,它一开始是一个命令:在这个时间点上它仍然可能可能失败,比如,因为违反了一些完整性条件。应用必须首先验证它是否可以执行该命令。如果验证成功并且命令被接受,则它变为一个持久化且不可变的事件。

  4. 状态、流和不变性

    应用状态是事件流对时间求积分得到的结果,而变更流是状态对时间求微分的结果。

    不变的事件日志中分离出可变的状态,可以针对不同的读取方式,从相同的事件日志中衍生出几种不同的表现形式。(多视图)

流处理

  1. 流处理的应用

    考虑流上时间窗口的统计查询、总数据的统计、精确查询

  2. 时间推理

    • 事件时间:如果使用事件时间,无法确定时间什么时候结束,因为消息可能滞留或者堵塞
    • 处理事件:处理时间无法确定实际的时间与顺序(比如电影的上映时间排序,不代表故事发生时间的顺序,前传呢)

    窗口的类型:

    • 滚动窗口:不重叠
    • 跳动窗口:部分重叠
    • 滑动窗口:一直重叠
    • 会话窗口:会话窗口没有固定的持续时间,而定义为:将同一用户出现时间相近的所有事件分组在一起,而当用户一段时间没有活动时(例如,如果30分钟内没有事件)窗口结束。
  3. 流连接
    • 流流连接(窗口连接)
    • 流表连接(流扩充)
      1. 远程查询表来扩充流数据,比如补齐用户信息。
      2. 将数据库副本加载到流处理器中,以便在本地进行查询(需要考虑数据副本的更新)
    • 表表连接(维护物化视图)

      两个输入流都是数据库变更日志。在这种情况下,一侧的每一个变化都与另一侧的最新状态相连接。结果是两表连接所得物化视图的变更流。

  4. 容错

    1. 微批量与存档点

      Spark Streaming:将流分解成小块,并像微型批处理一样处理每个块。

      Apache Flink:使用存档点

    2. 原子提交再现

      确保事件处理的所有输出和副作用当且仅当处理成功时才会生效

    3. 幂等性

      同一个操作执行多次不会影响最终的结果。

    4. 失败后重建状态

      任何窗口聚合(例如计数器,平均值和直方图)以及任何用于连接的表和索引,都必须确保在失败之后能恢复其状态。

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

数据集成

  1. 组合使用衍生数据的工具

    分布式事务使用原子提交来确保变更只生效一次,而基于日志的系统通常基于确定性重试幂等性。

    在没有广泛支持的良好分布式事务协议的情况下,我认为基于日志的衍生数据是集成不同数据系统的最有前途的方法。

    全序的限制:多领导者、多数据中心等

  2. 批处理与流处理

    流处理器在无限数据集上运行,而批处理输入是已知的有限大小。

    流处理用在实时性更高的场景。批处理比流处理有更高的容错。流处理可以使用快速近似算法,而批处理使用较慢的精确算法。

  3. 铁路上的模式迁移

    1. Lambda架构

      Lambda架构的核心思想是通过将不可变事件附加到不断增长的数据集来记录传入数据,这类似于事件溯源。

      在Lambda方法中,流处理器消耗事件并快速生成对视图的近似更新;批处理器稍后将使用同一组事件并生成衍生视图的更正版本。

分拆(chai)数据库

  1. 组合使用数据存储技术
    1. 数据写入,然后同步到索引的行为与数据写入,然后生成衍生数据(比如写入缓存)的行为很相似。思考一下单数据库的架构与分布式异构数据库。
    2. 统一读取,统一写入。所有异构数据库(文件、关系型、nosql等)统一实现接口
    3. 当数据跨越不同技术之间的边界时,我认为具有幂等写入的异步事件日志是一种更加健壮和实用的方法。(更高的容错以及服务划分)
  2. 围绕数据流设计应用

    • 应用代码作为衍生函数
    • 应用代码和状态的分离

      不将应用程序逻辑放入数据库中,也不将持久状态置于应用程序中。

    • 数据流:应用代码与状态变化的交互

      订阅数据库的变更日志

  3. 观察衍生数据状态

    • 物化视图和缓存

      只为一组固定的最常见的查询预先计算搜索结果,以便它们可以快速地服务而不必去走索引。不常见的查询仍然可以通过索引来提供服务。这通常被称为常见查询的缓存(cache),尽管我们也可以称之为物化视图(materialized view)

    • 有状态、可离线的客户端

      常用于移动设备,有本地数据库,离线可使用,上线后再同步。

    • 将状态变更推送给客户端

      消息队列的订阅者?

    • 端到端的事件流

      从请求/响应交互转向发布/订阅数据流,架构问题。广告推送?推流?

    • 读也是事件

      埋点?读取转成事件流的话,响应不够及时啊。

将事情做正确

  1. 数据库的端到端原则

    保证幂等性,防止重复提交(网络超时等情况)

    端到端原则:只有在通信系统两端应用的知识与帮助下,所讨论的功能才能完全地正确地实现。因而将这种被质疑的功能作为通信系统本身的功能是不可能的。 (有时,通信系统可以提供这种功能的不完备版本,可能有助于提高性能。)

    说人话就是,低层级的功能(TCP重复抑制,以太网校验和,WiFi加密)无法单独提供所需的端到端功能,但需更高层级(中间件、业务逻辑等)来实现

  2. 强制约束

    • 唯一性约束需要达成共识:比如多分区的情况下
    • 3个表,3个分区,需要需要原子性提交,可配合日志型消息队列。只要能保证写入消息队列的原子性,就可以保证分区的最终一致性(需要幂等处理)
  3. 及时性与完整性

    完整性比及时性更重要。

    流处理系统可以在无需分布式事务与原子提交协议的情况下保持完整性(无法保证及时性):

    • 将写入操作的内容表示为单条消息,从而可以轻松地被原子写入 —— 与事件溯源搭配效果拔群。
    • 使用与存储过程类似的确定性衍生函数,从这一消息中衍生出所有其他的状态变更
    • 将客户端生成的请求ID传递通过所有的处理层次,从而允许端到端的除重,带来幂等性。
    • 使消息不可变,并允许衍生数据能随时被重新处理,这使从错误中恢复更加容易

    宽松地解释约束:就是补偿机制

  4. 信任但验证

    为可审计性而设计

做正确的事情

  1. 预测性分析

    • 偏见与歧视

      预测性分析系统只是基于过去进行推断;如果过去是歧视性的,它们就会将这种歧视归纳为规律。如果我们希望未来比过去更好,那么就需要道德想象力,而这是只有人类才能提供的东西。数据与模型应该是我们的工具,而不是我们的主人

    • 责任与问责

      当一辆自动驾驶汽车引发事故时,谁来负责?

    • 反馈循环

      越穷的人越没时间提升自己,从而改善生活(负反馈)。也会导致信息茧房

  2. 隐私和追踪

    • 监视

      如果将数据替换成监视一词,再看看生活。

    • 同意与选择的自由

王谷雨

一个苟且偷生的java程序员

文章评论