数据密集型应用系统设计(DDIA)读书笔记
前言
读书笔记不会写的特别细,仅仅是把自己觉得重要的内容和自己的思考进行记录方便回顾。如果想了解完整的知识,建议自行阅读完整内容。
第一部分:数据系统基础
第一章:可靠、可扩展、可维护
理解数据系统的概念
数据库、缓存、消息系统等都可以统称为数据系统。涉及数据的处理的其实都可以概括的称之为数据系统。
Realiability
可靠性可以从功能、性能、安全、可用性这几个角度来说明。功能需要符合预期包括接受错误输入;性能要满足承诺的性能指标;安全上需要组织恶意破坏、未授权的使用等;提供符合要求的可用性标准。注意区分fault和failure。我们需要设计fault-tolerant和resilient的系统,前者强调容错,resilient强调遇到异常时自动恢复的能力。
以下方面都可能导致可靠性问题:
- 硬件故障:这个可以考虑做多副本,例如多路供电、双网络、RAID等等
- 软件故障:处理好异常输入、避免BUG
- 人为故障:书里面的一些其实归类到软件故障比较合理,软件以外的人为错误导致的故障可以认为是人为故障,比如不规范的操作导致系统crash
Scalability
能够随着负载伸缩,这种弹性对应系统能力也很重要。像云原生的基础设施为应用的scalability带来了很大的益处。系统设计时也要考虑scalability,书中就有个twitter发推文的例子,讲的是用户关注的其他用户发推文时,该用户采用怎样的方式来感知推文,一种是主动触发,另外一种是被动更新。被动的异步更新用户体验更好,但是针对粉丝多的大V广播推文的开销太大,如下图所示(1个用户有75个关注者)。
如果采用主动触发,则大V发的推放到一个数据库里面集中存储,他的粉丝查看的时候主动拉取即可。推特最后采用的时两者结合的方式。基本上一个好的系统架构最终都是会分情况去选择最合适的实现。当然项目初期还是要避免过度设计。
设计一个scalability良好的系统要学会:
- 描述负载:不同数据规模系统设计和实现都不同
- 描述性能: 关注吞吐量还是延迟以及响应时间,策略则会有所不同。延迟和响应时间一般是正相关的,一般可以用p95,p99的响应时间来衡量。这个例如用ab做接口测试的时候,大家都会看到类似的数字。
- 应对负载: scale out、stateless、automatically是努力的方向
Maintainbility
系统简洁、低耦合、良好的扩展性和可修改性都会影响可维护性的好坏。设计一个可维护性好的系统包括:
- 可运维性:尽量文档化、工具化。当你经常重复一件事情的时候,可以考虑用代码自动化了
- 简洁性:黑客与画家这本书的精髓就是告诉我们:好的系统设计一定是简单的。在不违反类似SOLID这样原则的情况下,尽量使用简单的、符合直觉的系统设计
- 可演化性:永远不变的就是变化。尽量遵循SOLID原则可以方便我们设计面向修改、可扩展的系统。
第二章:数据模型和查询语言
数据模型
数据模型提供了一个抽象层,将现实世界中的实体、概念和关系转化为计算机系统中的数据结构和操作。它定义了数据的组织方式、数据之间的关系以及数据的操作方式。例如关系模型将数据抽象成表格来表达大数据和关系。图模型将数据组织成节点和边描述数据和数据间的关系。
文中提到了关系模型和文档模型。不同的数据模型分别也代表了不同的数据库实现。关系模型发展最成熟,历史悠久,处理TP、AP等场景都有非常重要应用。文档模型是schema on read的,并且擅长一对多的关系。文档模型注意不是schema less的,准确来说是schema on read。像文件系统这种接受任何类型结构数据的可以说是schmaless的。数据库一般都是有schema的。
数据查询语言
主要通过声明式和命令式两个维度来划分。声明式抽象程度高、易于使用。命令式更偏底层,自定义和灵活能力更强。
图模型
具有复杂网络拓扑关系的适合用图模型。例如图数据库Neo4J还实现了自己的图查询语言Cypher,和SQL比较类似,但是专门用户图数据库的查询和操作。下图是Cypher的查询示例,可以看到定义了节点,以及边的关系(within和born_in)
语义网、Triple-stores和SPARQL
语义网是为了提供一种统一方式结构化所有网络中的资源。存储上可以使用triple-sotres(2个节点1个边的基础存储单元),查询可以使用SPARQL查询语言。这块的实践可以参考Apache jena。
主要在知识图谱这块应用比较多,不过语义网这个领域现在实在是火不起来。结构化网络上的资源基本已经通过基于json的API来达成了。API简单、低成本。JSON的问题就是不支持语义,但是现在也有JSON-LD这样的工具来提供语义化JSON规范了。
第三章:存储与查询
第二章描述的是high level的数据模型和查询语言。这节就相对更加low-level一些,设计具体的数据结构和实现设计等。
数据结构
选择何种索引数据结构和数据存储结构取决于具体应用场景,TP/AP,侧重读还是写,点查、范围查等等。现代数据库基本都采用分层的理念,融合了多种数据结构实现来匹配不同的场景,掌握这些基础数据结构对于了解现代化数据库实现很重要。下面是数据系统中会涉及的数据结构:
- 哈希索引:如果只是点查、精确匹配的场景可以用hash索引有最好的性能。例如bitcask这个kv系统虽然基于append log实现,但是内存就维护了一个hash index来索引file,加速数据查找。这块加深理解可以看下pingcap的tablent-plan里面有让你自己实现一个bitcask的kv存储
- SSTables和LSM-tree:三驾马车bigtable中提出的数据结构,现在主流的分布式数据库核心的存储结构基本都涉及他们。我之前也写了一篇文章专门探讨,可以参考:sstable存储结构与LSM。这两个数据结构核心是顺序写、分层merge。现代数据库基本上是LSM配合内存索引构建起存储体系的。
- B树:用于数据库索引非常成熟的数据结构,是很多单机数据库实现中主要的存储数据结构。相比LSM来说有更好的查询性能(适合读多写少)、查询的性能比较稳定(没有后台的compaction)、易于加范围锁、实现上也相对简单些。书中提到了B+树从提出以来的很多优化,例如KEY压缩编码、使用SSD等。
- 其他索引结构:例如全文索引结构、全内存数据结构。
TP、AP
这个主要是让你了解下TP、AP场景以及数据仓库的一些基本概念。
列存
列存的主要好处是很容易做压缩,然后面向列查询的场景。这里注意区分下基于列簇实现的bigtable、hbase、cassandra,严格意义上应该上可以称之为列簇数据库,而不是列存数据库。列簇数据库有点介于行存、列存之间,如果一个列簇包含所有列其实就退化成行存了。
一些列存的优化手段:
- 压缩和cache friendly: 做数据压缩,尽量留在cache中,有更好的性能
- SIMD做向量化:相同类型的数据看成一个向量更加容易做向量化处理
- 不同副本、不同排序:分布式存储会做数据冗余,可以不同的副本用不同的排序列,来改善不同列上的查询性能。
数据立方和物化视图
物化视图:物化视图适用于自定义视图上的频繁查询,本质是缓存预计算的结果来加速查询。是一种通用的数据库优化手段。
数据立方体:也是采用预计算的思路,不过是主要面向多维分析的,一般用于多维数据模型像星型或雪花模型等。预计算主要指的是预聚合,用于OLAP数据库中加速查询。
编码和演进
数据编码格式
编码格式需要考虑下兼容历史版本。书中大体介绍了下protobuf、thrift、avro编码演进上的处理。从2023年的角度来,protobuf凭借gRPC在云与安生的统治地位,相信会发展的更好,建议多了解下protobuf即可。
几种数据流模型
将数据流分成了几种模型:
- 经过数据库的数据流:
- 经过服务的数据流:
- 经过消息的数据流;
第二部分:分布式数据
第五章:数据复制/冗余
replication的好处
应为是replication,会更加准确一点。通过多副本会带来如下好处:
- 高可用:可以容忍节点crash
- 可伸缩:增加副本来提升并发读取能力
- 低延迟:可以做data locality
replication方式
现在主流复制副本的方式基本上是paxos/raft这种共识协议来达成高效一致性写入多副本的。
复制的方式一般分为:
- 同步
- 异步
- 半同步:有一些副本为同步,另一些副本为异步。例如MySQL的半同步复制
异步replication的问题与处理
- 读取的内容不是自己写入的:确保读写一致性(read-after write consistenct)的一致性保证。比如只从主副本读取,或者最近有更新的从主副本读取。
- 不可重复读:重复读会读到旧数据。这里可以确保一种新的一致性保证:单调读
- 违反因果关系:因为因和果分布在不同的分区上。推荐的方式可以考虑让存在因果关系的事件路由到一个分区
上面的问题其实听下来一般都会有感觉,本质就是处理分布式系统上非事务并发写入的问题。所以可以考虑直接引入分布式事务。当然直接采用同步的原子一致性写入也可以。
几种复制架构
数据副本之间的关系可以定义如下:
- 主从(leader-follower):有主从就会涉及主从复制。写的话都是先写主副本,然后更新到其他从副本。典型的例如基于raft协议实现的分布式数据库,都有主从副本的概念。
- 多主模式:这个一般多指的是跨AZ的数据库之间的副本复制
- 无主模式:比较典型的就是dynamoDB,自己实现了数据分区配合多版本和vector clocks等手段来达成最终一致性
从现在主流玩法来看,基于raft的强一致性协议不仅可以保证强一致,并且也有很好的性能。
第六章:分区
分布式系统涉及数据的分散存储,因此对数据进行分区是必不可少的。分区的步骤主要:
- 对数据集按照逻辑划分
- 将分片数据集映射到物理节点
键值对集合的分片
常见的逻辑分区方式有:
- Hash分区
- 按照key range分区,例如按照时间
一致性hash(逻辑分区+物理调度)
一致性hash是分布式系统做hash分区普遍采用的方式。通过提前在hash环上预设slot配合虚拟节点映射物理节点的方式可以很好的解决hash分区不易扩展以及数据倾斜的问题。主流的分布式系统像MongoDB、Redis、Cassandra都有使用。
均衡策略
- 静态分区数:分区数固定(一般建议大于节点数一个数量级),需要建立分区和物理节点的映射。优点简单,缺点是不太灵活,固定分区数难以调整。
- 动态分区数:即数据量少分区数就少、数据量多分区数就多。这种方式现在比较主流,注意为了避免初始1个分区时,写并发降低,可以配合预分区(初始化时按照key起始值多初始化几个分区)技术一起使用。
请求路由(服务发现)
一般有以下几种方式:
- 统一路由层管理
- 所有节点维护一份一致性路由表,可以转发请求
- 客户端包含路由信息
当前主流手段来保持分布式的一致性路由信息主要就是依靠共识协议。当然实现共识协议的组件可以是:
- 外部依赖: 比如etcd
- 内部元数据中心:例如Tidb placement driver
- 节点点对点同步:dynamo、cassandra、riak的gossip protocol
第七章:事务
ACID
这里主要注意下ACID中的一致性不要和别的地方的一致性弄混。例如CAP的一致性是指的线性一致性,讲的是客户端看到线性、顺序的数据。ACID中的C强调的是事务操作前后数据库数据总是保持一致。数据库中C主要靠隔离性来实现。
ACID的实现方式:
- A: 依靠事务机制和undo log(事务失败回滚)
- C:主要依靠隔离性,通过隔离级别来确保事务执行前后的数据一致性
- I: 主要是事务实现的方式,可以利用锁、MVCC、2PC、transaction flow
- D: 避免宕机时数据丢失,一般是采用undo log和redo log。例如下图中MySQL中redo和undo配合2PC来确保数据持久性。
单对象与多对象
主要指一次操作中包含的对象数。单对象处理主要是原子性单位,多对象处理主要是考虑引入事务的复杂性。
隔离级别
关于事务隔离级别以及对应处置可以参考我的另外一篇总结文章:事务隔离级别回顾
索引与快照隔离
多版本数据的时候建立索引可以考虑:
- 索引对象指向所有版本
- 树根代表一个版本:每次修改相当于生成新树根,代表一个版本。类似的实现有CouchDB、Datomic和LMDB
锁
实现事务中必然需要配合锁来做好隔离性以及避免一些并发事务执行引发的问题:
- 谓词锁:类似mysql gap锁,锁住一个谓词集合
- 索引范围锁(next-key locking): 属于谓词锁的简化,锁住多个条件
一般而言,锁的设计trade-off就是在锁粒度上调整来权衡锁的能力和性能。
可串行的快照隔离-SSI
这个是08年Mechael Cahill博士论文中提出的新型可串行化方案。SSI隔离级别采用更严格的数据快照在满足串行化隔离级别的标准上提升性能。虽然很多分布式数据库还是延用ANSI标准设置隔离级别,不过他们可能在RR隔离级别上已经实现了近似SSI的能力,例如google spanner或者tidb
第八章:分布式系统中的麻烦事
故障与部分失效
分布式系统多个节点时,一部分异常的情况即“部分故障”
不可靠网络
分布式系统需要考虑网络不可靠的多种情况,包括但不限于:
- 请求可能丢失。
- 请求在某个队列里等待,无法马上发送。
- 远程节点因为崩溃、宕机等原因已经失效。
- 远程节点因为某些原因暂时无法响应。
- 远程节点接收并且处理了请求,但是回复却丢失了。
- 远程节点已经完成了请求,但是回复被延迟了。
检测网络故障
虽然有系统通知、IP不可达等众多方法确认网络故障,但是仍然不是足够可靠。因此,应用层仍然需要设置合理的超时和重试次数。
超时和无界延迟
无界延迟就是指延迟无法保证的场景。另外书中提到了理想网络系统中(实际网络基本不提供这种理想保证)给出超时间隔的方法:设有一个理想的网络系统,能够保证所有的网络通信延迟不超过 d:所有的网络包要么在 d 时间内送达对端、要么就会丢失,即不可能在超过 d 的时限后才到。如果网络能提供此种保证,则应用层可大为简化:假设我们预估出单个请求最大处理时间 r,则 2d+r 是一个很好超时间隔。
同步网络和异步网络
电话线路是同步网络,现代互联网都是异步网络,主要是因为需要网络带宽共享提升效率。网络资源共享在提升效率的同时自然也引发了竞态资源导致的问题,例如延迟就不可靠了。
不可靠时钟
时钟分类:
- 墙上时钟
- 单调时钟:适合用于不关心具体墙上时钟的时间,关注持续时间间隔的场景
注意时钟的不可靠,强依赖时需要仔细评估,例如选主的时候依赖本地时间,可能产生2个主。例如分布式系统TSO或者依赖true time API的时候需要分配单调递增全局唯一时间戳可以采用如下实现方式:
- 高精度时间装置:例如可以使用原子钟提供纳秒级时间精度,例如google true time API。由于存在精度,一般都配合置信区间来工作。比如,系统有95%的置信度认为目前时间在[10.3,10.5]秒之间。Google Spanner中的TrueTime API,在查询当前时间时,会得到两个值:[不早于,不晚于]分别代表误差的最大偏差范围。
- 单点软件组件分配:例如现在很多分布式数据库系统的实现,利用TSO组件分配说件戳。多节点TSO组件可以授权多节点不相交的时间戳区间,每个节点维护自己的计数器,这样确保每个节点本地生成和全局生成的时间戳都是单调递增的
知识、真相和谎言
书中有些写的过于文绉绉了,这里主要讲了多数派决定真相、以及时间相关的系统模型。主要注意下多数派中可能存在恶意节点的问题,这种也称之为拜占庭错误。后续提到的共识算法会涉及处理拜占庭错误的处理。
第九章:一致性与共识
一致性保证
理解最终一致性即可
线性一致性
也被称之为强一致性、外部一致性。强调外部对这个系统中的数据像处理单机上单个副本一样,是原子的、顺序的。本质是数据的新鲜度保证,不要和数据库隔离级别的可串行化弄混,可串行化是针对事务的。数据库可以同时支持可串行化与可线性化,这种组合又被称为严格的可串行化或者强的单副本可串行化(strong one-copy Serializability)
**实现线性化系统的方式:**现在主流是采用共识算法,不过共识算法侧重CP,选主的时候系统可用性会受到一些影响。
顺序保证
前置知识-全序、偏序关系
全序和偏序是在集合中元素之间的一种比较关系。全序指的是集合中的每个元素都能够被比较出大小关系,而且这些元素之间的比较是唯一的。也就是说,给定集合中的任意两个元素,可以比较出它们的大小,其中一个一定是比另一个大或者小。例如,自然数集合{1, 2, 3, …}就是一个具有全序关系的集合。
偏序指的是集合中的元素之间的大小关系不一定都能够比较出来,只有一部分元素之间有大小关系,而且这些元素之间的比较也不一定是唯一的。例如,人们的身高就是一个具有偏序关系的集合,因为两个人的身高大小关系可能无法比较,或者比较出来的结果是相等。换句话说,偏序关系比全序关系更加宽松。
顺序和因果
因果关系是一种偏序关系,不是严格的全序关系。利用因果关系排序来提升并发是常用的性能优化技巧。如果系统满足因果关系所规定的顺序,称之为“因果一致性(causally consistent)”。之前开发数据集成做CDC的时候设计UK冲突感知的并发模型时有应用因果一致性,有兴趣可以了解下。
序列号定序
生成满足因果一致性的序列号对事件定序可以用:
- 版本向量:每个副本的键都引入版本号,对于同一个键来说,不同副本的版本会构成版本向量(version vector)。用于检测操作的并发和因果依赖。缺点是存储成本随着版本增加而变高。
- lamport时间戳:可以提供全序保证,利用自身机制,将事件、交互双方(client、server)都纳入机制内来追踪因果关系。
Lamport 时间戳不依赖于物理时钟,但可以提供全序保证,对于任意两个 Lamport 时间戳:
- 具有较大 counter 的时间戳较大
- counter 相同,具有较大 node ID 的时间戳较大
让 Lamport 时间戳能够满足因果一致性的核心点在于:每个节点和客户端都会让 counter 追踪当前所看到(包括本机的和通信的)的最大值。当节点看到请求或者回复中携带的 counter 值比自己大,就会立即用其值设置本地 counter。
全序关系广播
在一个分布式系统中,让所有节点就所有操作的某个确定的全局序列达成一致可以采用全序关系广播。主要做法就是复制日志,追加日志内容。这样所有节点读取日志的时候都是同样的消息序列。可以利用支持全序关系广播的算法来构建线性一致性系统。
分布式事务和共识协议
- 区分2PL和2PC: 2PC是为了做原子提交,2PL是为了做基于锁的并发控制。
- 了解共识算法的局限:共识算法也不是银弹,会有如下问题,总结就是系统复杂度提升、选举投票带来一些开销。不过相信随着共识算法的不断改进,这些缺点都会慢慢弱化的。
第三部分:派生数据
- 记录系统:有数据的权威版本,数据的真实、原始来源
- 派生数据系统:从另一个系统中获取的
第十章:批处理系统
从UNIX设计哲学到MapReduce
书中先描述了UNIX一次只做好一件事的设计哲学,在讲到MR本质上可以理解成一个由分布在大量机器上的UNIX工具构建起来的系统,每个机器上的mapper、reducer就单纯的处理一条记录的输入和输出,他们具备明确的输入流和输出流,处理过程无副作用。这使得MR能够处理复杂的跨机器数据处理。有一种计算存储分离的美感,数据其实和节点处理是完全解耦的。
MR不可变输入、无副作用、存储计算分离的模型值得我们学习。
超越MapReduce
MR实体化中间状态是主要弊端(中间结果很重)。所以后来产生了SPARK、Flink等把工作流作为一个作业来处理的系统,而不是把工作流分解成独立运作的子作业。
第十一章:流处理系统
无界的输入,持续的输入与输出。这里涉及消息系统、流处理引擎以及CDC系统。流处理的场景主要是一些实时分析场景。可以通过Flink的一些学习资料加深时间窗口、状态管理相关的内容。
第十二章:数据系统的未来
主要介绍了如何利用流、批处理系统以及我们学到的相关知识来合理的设计系统处理派生数据。相关的模式包括lambda架构、分拆数据库等。