Disign Data-Intensive Application,大名鼎鼎的 DDIA,中文名就是设计数据密集型应用。这本书我买的时间是去年的6月18号,大约一个多星期之前,终于是读完啦,算是整整一年吧。买的是影印版,英文,应该是第一次读完一整本的比较厚的英文技术书籍。

读书的进度也比较奇怪,在去年9月份左右,前两个部分就读完了,当时一直有一种就是想读的感觉。之后又突然懈怠了,停滞了许久。知道今年上半年陆续读了一些,终于在最近达成目标。

做服务端开发,如果想要深入,有些技术就必然绕不过去,就比如本书所涉及的数据存储、数据处理以及分布式系统。之前也想深入了解一下分布式系统,看了些相关文章、博客,但是并没有系统的学习,因此理解层次比较浅,缺乏全局的认识,也容易看过就丢。而这本书,虽然并不是着眼于分布式系统,却从数据的角度,讲了分布式系统涉及的概念和理论。

本书从应用的可靠性、扩展性、可维护性开始,到大数据应用的伦理结束,分为三个部分共十二章。

Part 1. Foundations of Data System

第一个部分是数据系统的基础,包括 4 章,分别是关于数据系统的数据定义以及关注点、数据模型、存储引擎、序列化。

数据系统的三大问题

一个典型的数据系统(Data System)可以由几个基本块构成,

  • 存储数据,因而之后自己或者其他应用可以找到这些数据(数据库)
  • 记住高代价操作的结果,从而可以加速读取(缓存)
  • 允许用户通过关键字搜索,或者其他方式过滤数据(索引)
  • 向其他应用发消息,从而异步处理(流处理)
  • 定期处理大量数据(批处理)

而数据数据系统最关注的三个问题,则是

  • Reliablity,可靠性:即使在故障(adversity)情况(软硬件故障)甚至人为失误的情况下,系统依然能正确地(correctly) 工作(在期望的性能下,正确的执行功能)
  • Scalabiity,扩展性:在系统逐渐庞大(grows)(数据量、流量或者复杂性)的过程中,有合理的方式解决这个过程中出现的问题
  • Maintainability,可维护性:系统的生命周期中,对系统的修改,包括维护当前功能或者增加新功能,都可以高效地()productively)完成。

数据的存储、获取、传输

数据模型不仅仅关系到一个应用如何实现,还表明了我们对问题的思考方式。通常,数据模型都是一层叠一层,上层的数据模型依赖于下一层的数据模型。比如,

  • 通常会有应用模型,使用接口和类表示,用于描述领域问题
  • 这些模型在存储时,可能是 json 或者关系型数据库表、图数据库的图等
  • 底层的存储引擎,则会把这些数据转变为 bytes
  • 在更底层还涉及硬件

数据模型

在第二章,主要涉及的是其中的第二项。

目前,关系模型是使用最广泛的数据模型。然而,关系模型不能和领域级别的抽象一一对应。通常,领域模型使用对象进行描述,而对象和关系模型的表、行、列,并不是一一对应的。对象之间的关联关系,映射到关系模型,就会产生不同的关系,如一对一、多对一、多对多等。这种映射并不直观。很久之前就出现过其他的数据模型,比如网络模型(network model),每个记录之间存在链接,表示相互关系。但是网络模型的查询太复杂,所以败给了关系模型。文档模型又是另外的一种,和网络模型有些类似,都会把嵌套的记录放到父记录中而不是另起一张表,不过文档记录在处理前文的多对一、多对多关系时,存储的 document reference 更像是外键。

文档模型和关系模型的一大区别在于,关系模型的模式(schema)是确定的,而文档模型的 schema 则更灵活,有时被称为 schemaless。实际上,文档模型只是在写入是不强制必须是统一的 schema,在读数据时,会认为数据具有某种特定的结构。与编程语言里的鸭子类型相似。这种模式,称为 schema-on-read,而传统的关系数据库,则时 schmea-on-write。

数据存储在硬盘上,目的是为了日后可以读。而根据不同的应用场景,可能需要数据的不同部分。这就涉及了数据的查询。

数据查询的语言和编程语言类似,可以分为命令时和声明式。常用的编程语言基本都是命令式,需要告诉计算机怎么做。SQL 就是一种声明式的查询语言,只需要表明要干什,不需要说明怎么做。在 Web 开发中,css 选择器以及 xml 的 xpath 选择器,也都是生命式语言。使用这类语言,最大的好处就是不需要关系实现的细节,交给语言的解释器去做优化即可。MongoDB 是文档模型的数据库,支持使用 MapReduce 模式的查询。MapReduce 可以认为是介于命令式和声明式两者之间,因为 map 和 reduce 方法的实现式命令式,而 map 和 reduce 的实现是不会暴露给用户的,对于用户而言,可以认为是声明式。

图模型是区别以上数据模型的一种模型,擅长处理多对多关系。比如社交网络、交通路网等,都可以用图模型很好的描述。

存储和读取

第三章是关闭于存储和读取,重点涉及上面所述的数据在磁盘中的存放。

数据库对于数据的处理需要同时考虑读和写,一般而言,读和写的性能不能同时达到最优,必须由均衡取舍。

最简单的数据库,就是所有数据存到一个文件,写则追加数据,读则从头开始扫。但是很显然,读性能及其糟糕,作为一个数据库,这个方案是不能接受的。

以 key-value 数据库为例。为了优化,可以在内存中记录 key 在文件中的 offset,读数据时,根据 offset 取数据即可,称为哈希表(hash table)。这就是哈希索引。为了防止数据文件过大,一般会把数据文件分段存储。这种模型下,修改和删除数据都是在文件尾部追加数据,造成很大的冗余。因此可以在后台起一个线程,压缩合并数据段文件,只保留 key 在文件中的最后一次出现。这种实现很高效,因为顺序写磁盘非常快。而索引在内存中,读数据也并不是很慢。缺点在于哈希表必须在内存中,否则写道磁盘上,会有随机IO,性能很不好。此外,对于范围查询,则只能对范围内的 key 一个个查询,性能完全不行。

LSM-Tree 是对上述模型的改进。在上述模型中,保证每个数据段文件中,key 是有序的,并且每个 key 在一个数据段文件中只出现一次。这种结构称为 SSTable(Sorted-String Table)。如此,则不需要在内存中存储所有的 key。有 SSTable 组成的存储,就称为 LSM-Tree(Log-structrured Merge-Tree)。由于 SSTable 中 key 有序,则需要在内存中执行写请求,内存中的结构称为 memtable。在 memtable 的大小达到一定阈值,刷盘。再刷盘的同时,新的请求写道新的 memtable。为了防止数据在刷盘之前丢失,需要在每次写数据时,先追加写道日志文件,在数据刷盘后删除。读数据时,则先查内存,再从信道旧,依次查询 SSTable。如果 key 不存在,查询就会比较慢,因此可以使用 bloom filter 来进行优化。

B-Tree 则是和以上方案的路子都不同。读写都是以 page 作为最小单元,并进行原地更新。为了防止丢失,需要写 redo log,相当于上述的 append only log。

数据库基本有两类使用场景,OLTP(online transaction processing)和 OLAP(online analytic processing)。OLTP,基本上是对数据库中的少量数据的操作,可能会与用户数据有交互。OLAP 则是注重数据分析,是对大批量的数据进行统计,以获得对于据的统计性的认知。由于使用场景的巨大不同,其底层存储也有差别。

编码与演进

数据结构在存储时,都需要编码为 bytes。而编码不仅仅影响性能,同时会影响应用的结构以及部署方式。

编码方式有很多,有和特定语言相关的,比如 Java 的 Serializable;有文本方式的编码,比如 json、xml;还有各种二进制编码。

不同的编码方式,对 schema 要求也不同。json 编解码就不需要 schema,因为信息在编码后的数据中都存在。而 ProtoBuf 就需要 schema,因为其编码使用了数字作为 tag,但是编码后的数据中,并不存在某个数字对应的属性的名字、类型等信息,必须通过 schema 才能拿到,因此必须借助 schema 才能解码。

不同的编码方式,还会影响到应用的升级兼容。如果新增、删除、修改字段,会导致只认识旧的 schema 的应用崩溃,那么这种方式就很难进行兼容升级,会给开发带来比较大困难。

Part 2. Distributed Data

第二部分是本书的重头戏,关注数据在多台机器上的存储以及获取。之所以需要考虑在多台机器上保存数据,由三个原因:

  • 扩展性。单机容量不能满足需求
  • 容错性、高可用:单机故障时,不影响整体的可用性
  • 时延:可以靠近用户部署,从而减小访问数据的时间

Replication

同一份数据通过网络保存在多台机器上,就是 Replication(不知道怎么翻译好),存储数据的节点称为 replca。需要数据 replication 的理由是:

  • 可以在地理上靠近用户
  • 部分系统故障时,系统可以工作
  • 允许多台机器处理请求,从而增加吞吐量

单 leader

多个 replica 之间,由 leader/follower,或者 master/salve 之分,其中 leader 处理写请求,follower 只能处理读请求。因此需要 leader 需要把数据复制到其他的节点。

leader 向其他节点复制数据,就存在一个同步异步的问题。leader 处理请求后,什么时候才认为数据已经成功写入。是在 leader 保存后即认为成功,还是所有 follower 都确认才算是成功。

  • 全同步复制:其他所有节点都确认,才返回。会导致严重的不可用,因为任何一个节点失效,都会导致无法写入数据。
  • 半同步:在 n 个节点确认后,认为写入成功。其他的节点异步复制。
  • 全异步:leader 成功即认为写入成功。会导致数据不一致,因为 leader 有可能在自己成功而没有其他节点确认时崩溃,这个数据就不会被其他节点承认。

单 leader 模式下,还必须要处理 leader 不可用的异常,必须进行 failover。此时,可能会导致丢数据(具体要看是同步复制还是异步复制)。

数据怎节点之间的同步,一般时通过复制日志。分为三种

Statement-based。最简单的方式,leader 把其执行的所有写请求(statement)写到日志,并把日志发送给所有 follower。存在几个问题:

  • 必须时确定性的,不能由 random、now 这样的不确定性函数
  • 如果请求依赖数据中的其他内容,或者以来自增ID,那么请求的处理必须保持有序
  • 如果请求由副作用,那么副作用也必须时确定性的

Write-ahread log。leader 把所有对数据的写操作写到日志,然后把日志发送给所有 follower。follower 根据日志恢复数据。这种方式的问题在于,日志里的内容时底层数据,更接近存储引擎。leader 和 follower 必须使用相同的数据格式,也因此在数据格式改变时,leader 和 follower 必须同时升级。这就导致在升级时,会有一段时间不可用。

Logical(row-based) log。使用一种与存储引擎不同的数据格式来写日志,通常时逻辑上的记录。比如新增一行,则记录下一行内所有列的数据。MySQL 的 binlog 就是这种方式。

既然需要从 leader 复制到 follower,就必然存在延迟(lag),继而应该考虑一下几点:

  • 写后读。自己写入的数据,自己也应该能够读出来。
  • 单调读。曾经读过的数据,之后也应该能够读出来。
  • consisent prefix reads。具有因果性的数据,不能读到的顺序也因果相反。比如,问答中,问题一定先于回答先读到。

多 leader

单 leader 的问题在于,如果和 leader 的连接出现问题,那么就没有办法写入。并且 leader 也可能会成为系统的性能瓶颈。

一个自然而然的解决方法就是,允许有多个 leader 同时存在,这也就是多 leader 的模式。多 leader 行能会更好,可以容忍网络问题以及单个机房的宕机。

多个 leader 同时支持写入,就存在数据冲突的可能,从而需要解决数据冲突,而这是非常困难。如果可能,应该尽量避免数据冲突,比如对特定数据的写,都路由到同一个 leader。另外一种方式,是各 leader 的写入都能达到最终一致,方式可以为:

  • 每个写入都有一个唯一的 ID,冲突的写入,选择 ID 大的作为最终的胜者,丢弃其他数据。ID 可以是时间戳,甚至是随机数。如果使用时间戳,就是所谓的 last write wins
  • 每个节点有一个 ID,当数据冲突时,ID 最大的节点的写入作为胜者,丢弃其他数据
  • 合并多个写入
  • 记录下所有冲突的值,以待日后解决(有可能最后就是给最终用户一个提示)

多 leader 之间存在拓扑结构,因为一个 leader 收到的写请求,也发送给其他的 leader。可以分为三类:环形、星型、全连接。

无 leader(leaderless)

前两种模式下,客户端只能向 leader 发送写请求,由 leader 决定写入的顺序,而在 leaderless 模式下,则没有这个限制。最典型的系统时 Amazon 的 DynamoDB,写入时,客户端同时想多个节点发送写请求。读也是同时向多个节点发送读请求。

leaderless 下,由 quorum 的概念:

  • 数据存储在 n 个节点中,称为 home node
  • 需要向 w 个节点写入成功,才算写入成功
  • 读数据时需要同时读 r 个节点的数据
  • 要求 w + r > n,从而保证客户端读到的数据中,一定由最新的数据

即便如此,quorum 仍然存在一致性问题:

  • sloppy quorum
  • 并发写仍然会有顺序问题
  • 并发的读和写,无法确认读到的值是新是旧
  • 写入时,如果部分节点写入失败,从而少于 w 个节点成功,写入成功的节点并不会回滚。那么对于后续的读,不能确认是否会读到这次失败的写入。
  • 有新数据的节点宕机,恢复数据时从一个有旧数据的节点恢复,就可能会导致存有新数据的节点数目不足 w
  • 时序问题

sloppy quorum是指这样的一种情况,在超过 n 个节点的集群中,客户端无法和某些节点通信,在写入时无法保证 w 个写入成功,此时有两种选择:

  1. 写失败
  2. 向不是 home node 的节点写数据

第二种选择即 sloppy quorum,会导致数据不一致。因为客户端认为写入成功了,但是实际上,w + r > n 可并不满足,因为不在 n 中的节点被算在 w 里。但是 sloppy quorum 可以提高写的可用性。

因为允许并发写,因而即使时严格的 quorum,也可能存在冲突。如果每个节点都是简单的覆盖原先的值,肯定会导致数据的永久不一致,这对于一个数据系统来说时不可接受的。即使不能实现强一致性,也至少要保证最终一致性。各个节点最终会得到一致的值。

  • last write wins,丢弃并发写。这里的 LWW 并不一定时真实的最后,因为写操作式并发的,无法确定最后。但是可以人为确定一个最后。显然可以保证最终一致性,但是对于客户端而言,写入成功的数据也可能会丢失,丧失了持久性。在不能接受数据丢失的场景,这个方案不可行

  • happens-before

    • 两个事件 A 和 B 的关系只有三种
    • A happens-before B
    • B happens-before A
    • A、B 并发
    • 对于并发,需要 merge 并发写的值
      • Version vector,用于追踪事件的偏序关系(或者叫做因果关系),但是 version vector 随着写的增多,会呈指数级增长1

结语

这篇文章从 6.26 开始写(所以文章开头都是基于 6.26 的),到现在两周。大约是全书的三分之一吧,文章内容基本是书中内容的重复性复述。原本是想要写全书的,奈何内容确实很多,而我虽然已经把书读了一般,但是书中所讲并没有完全吃透。因而必须要循着读书时记得一些笔记,并且翻书重看,才能进行下去,也的确耗时。书中余下的内容,应该会有续篇。