导图社区 数据密集型应用系统设计
- 90
- 2
- 0
- 举报
数据密集型应用系统设计
数据密集型应用系统设计：第一部分: 数据系统基础、第二部分: 分布式数据系统、第三部分: 派生数据。等
编辑于2022-03-20 10:04:41- 相似推荐
- 大纲
数据密集型应用系统设计
第二部分: 分布式数据系统
前言
需要在多台机器上分布数据的目的
扩展性: 当数据量或者读写负载巨大, 严重超出了单台机器的处理上限, 需要将负载分散到多台机器上
容错与高可用性: 当单台机器(或者多台, 以及网络甚至整个数据中心)出现故障, 还希望应用系统可以继续工作, 这时需要采用多台机器提供冗余
延迟考虑: 如果客户端遍布世界各地, 通常需要考虑在全球范围内部署服务, 以方便用户就近访问最近的数据中心所提供的服务, 从而避免数据请求跨越了半个地球才能到达目标
系统扩展能力
共享内存架构的问题在于, 成本增长过快甚至超过了线性, 并且存在性能瓶颈, 两倍的硬件不一定能够处理两倍的负载
共享内存架构能够提供有限的容错能力
无共享结构(水平扩展)
复制与分区
将数据分布在多节点时有两种常见的方式:
复制
在多个节点上保存相同的数据的副本, 每个副本具体的存储位置可能不尽相同. 复制方法提供冗余: 如果某些节点发生不可用, 则可以通过其他节点继续提供数据访问服务. 复制也可以帮助提高系统性能
分区
将一个大块头的数据库拆分成多个较小的子集即分区, 不同的分区分配给不同的节点(也称为分片)
第5章: 数据复制
主节点和从节点
每个爆粗数据库完整数据集的节点称之为副本, 当有了多副本, 不可避免地会引入一个问题: 如何确保所有副本之间的数据是一致的
对于每一笔数据写入, 所有副本都需要随之更新, 否则, 某些副本将出现不一致, 最常见的解决方案是基于主节点的复制(也称为主动/被动, 或主从复制)
主从复制的工作原理如下
1. 指定一个副本为主副本(或称为主节点), 当客户写数据库时, 必须将写请求首先发送给主副本, 主副本首先将新数据写入本地存储
2. 其他副本则全部称为从副本(或称为从节点), 主副本把新数据写入本地存储后, 然后将数据更改作为复制的日志或更改流发送给所有从副本, 每个从副本获得更改日志之后将其应用到本地, 且严格保持与主副本相同的写入顺序
3. 客户端从数据库中读数据时, 可以在主副本或这从副本上执行查询, 只有主副本可以接受写请求, 从客户端角度, 从副本都是只读的
同步复制与异步复制
复制非常重要的一个设计选项是同步复制还是异步复制, 对于关系型数据库系统, 同步或异步通常是一个可配置的选项, 而其他系统则可能是硬性指定或者只能二选一
同步复制的优点是, 一旦向用户确认, 从节点可以明确保证完成了与主节点的更新同步, 数据已经处于最新版本, 万一主节点发生故障, 总是可以在从节点继续访问最新数据; 缺点则是, 如果同步的从节点无法完成确认(例如由于从节点发生崩溃, 或者网络故障, 或任何其他原因), 写入就不能视为成功, 主节点会阻塞其后所有的写操作, 直到同步副本确认完成
主从复制还经常会被配置为全异步模式, 此时如果主节点发生失败且不可恢复, 则所有尚未复制到从节点的写请求都会丢失. 但是全异步配置的优点则是, 不管从节点的数据多么滞后, 主节点总是可以继续响应写请求, 系统的吞吐性能更好
配置新的从节点
如果需要增加副本数以提高容错能力, 或者替换失败的副本, 就需要考虑增加新的从节点, 新增从节点需要确保从节点和主节点保持数据一致
1. 在某个时间点对主节点的数据副本产生一个一致性快照, 这样避免长时间锁定整个数据库
2. 将此快照拷贝到新的从节点
3. 从节点连接到主节点并请求快照点之后所发生的数据更改日志, 因为第一步创建快照时, 快照与系统复制日志的某个确定位置相关联, 这个位置信息在不同的系统有不同的称呼, 如PostgreSQL将其称为(log sequence number)
4. 获得日志后, 从节点来应用这些快照点之后所有数据变更, 这个过程称之为追赶, 接下来,, 它可以继续处理主节点上新的数据变化
处理节点失效
从节点失效: 追赶式恢复
从节点的本地磁盘上都保存了副本收到的数据变更日志
主节点失效: 节点切换
选择某个从节点将其提升为主节点, 客户端也需要更新, 这样之后的写请求会发送给新的主节点, 然后其他从节点要接受来自新的主节点上的变更数据, 这一过程称之为切换
故障切换可以手动进行, 例如通知管理元主节点发生失效, 采取必要的步骤来撞见新的主节点, 或者以自动方式进行
自动切换的步骤通常如下
1. 确认主节点失效, 有很多种出错可能性, 没有万无一失的方法能够确切地检测究竟问题出在哪里, 所以大多数系统都采用了基于超时的机制: 节点间频繁地互相发送心跳存活信息, 如果发现某节点在一段比较长时间内没有响应, 即认为该节点发生失效
2. 选举新的主节点. 可以通过选举的方式(超过多数节点达成共识)来选举新的主节点, 或者由之前选定的某控制节点来指定新的主节点. 候选节点最好与原主节点的数据差异最小, 这样可以最小化数据丢失的风险. 让所有节点同意新的主节点是个典型的共识问题
3. 重新配置系统使新主节点生效. 客户端现在需要将写请求发送给新的主节点. 如果原主节点之后重新上线, 可能仍自认为是主节点, 而没有意识到其他节点已经达成共识迫使其下台, 这时系统要确保原主节点降级为从节点, 并认可新的主节点
然而, 上述切换过程依然充满了很多变数
如果使用异步复制, 且失效之前, 新的主节点并未收到原主节点的所有数据, 在选举之后, 原主节点很快又重新上线并加入到集群, 接下来的写操作会发生什么? 新的主节点很可能会收到冲突的写请求, 这是因为原主节点未意识的角色变化, 还会尝试同步其他从节点, 但是其中一个现在已经接管为现任主节点, 常见的解决方案是, 原主节点上未完成复制的写请求就此丢弃, 但这可能会违背数据更新持久化的承诺
如果数据库之外有其他系统以来与数据库的内容并在一起协同使用, 丢弃数据的方案就特别危险
在某些故障情况下, 可能会发生两个节点同时都自认为是主节点, 这种情况被称为脑裂, 非常危险.
如何设置合适的超时来检测主节点失效
复制日志的实现
基于语句的复制
主节点记录所执行的每个写请求(操作语句)并将操作语句作为日志发送给从节点
问题
任何调用非确定性函数的语句, 如NOW(), RAND(), 可能会在不同的副本上产生不同的值
如果语句中使用了自增列, 或者以来与数据库的现有数据, 则所有副本必须按照完全相同的顺序执行, 否则可能会带来不同的结果, 进而, 如果存在多个同时并发执行的事务时, 会有很大的限制
由副作用的语句(如触发器, 存储过程, 用户定义的函数等), 可能会在每个副本上产生不同的副作用
基于预写日志(WAL)传输
所有对数据库写入的字节序列都被记入日志, 因此可以使用完全相同的日志在另一个节点上构建副本: 除了将日志写入磁盘之外, 主节点还可以通过网络将其发送给从节点
主要缺点是日志描述的数据结果非常底层: 一个WAL包含了哪些磁盘块的哪些字节发生改变, 诸如此类细节, 这使得复制方案和存储引擎紧密耦合, 如果数据库的存储格式从一个版本改为另一个版本, 那么系统通常无法支持主从节点上运行不同版本的软件
基于行的逻辑日志复制
另一种方法是复制和存储引擎采用不同的日志格式, 这样复制与存储逻辑剥离, 这种复制日志称为逻辑日志, 以区分物理引擎的数据表示
关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求
对于行插入, 日志包含所有相关列的新值
对于行删除, 日志里有足够的信息来唯一标识已删除的行, 通常是靠主键, 但如果表上没有定义主键, 就需要记录所有列的旧值
对于行更新, 日志包含足够的信息来唯一标识更新的行, 以及所有列的新值(或至少包含所有已更新列的新值)
由于逻辑日志与存储引擎逻辑解耦, 因此可以更容易地保持向后兼容, 从而使主从节点能够运行不同版本地软件甚至使不同地存储引擎
对于外部应用程序来说, 逻辑日志格式也更容易解析, 如果要将数据库的内容发送到外部系统(如用于离线分析的数据仓库), 或构建自定义索引和缓存等, 基于逻辑日志的复制更有优势, 该技术也被称为变更数据捕获
基于触发器的复制
基于触发器的复制通常比其他复制方式开销更高, 也比数据库内置复制更容易出错, 或者暴露一些限制, 然而, 其高度灵活性仍有用武之地
复制滞后问题
读自己的写
需要"写后读一致性", 也成为读写一致性, 该机制保证如果用户重新加载页面, 他们总能看到自己最近提交的更新, 但对于其他用户则没有任何保证, 这些用户可能会在稍后才能刷新看到
如果用户访问可能会被修改的内容, 从主节点读取, 否则, 在从节点读取, 这背后就要求有一些方法在实际执行查询前, 就已经知道内容是否可能会被修改
如果应用的大部分内容都可能被所有用户修改, 会导致大部分内容都必须经由主节点, 这就丧失了读操作的扩展性, 此时需要其他方案来判断是否从主节点读取, 例如跟踪最近更新的时间, 如果更新后一分钟之内, 则总在主节点读取
客户端还可以记住最近更新时的时间戳, 并附带等待在读请求中, 据此信息, 系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新, 如果不够新, 要么交由另一个副本来处理, 要么等待知道副本接收到了最近的更新
如果副本分布在多数据中心(考虑与用户的地理接近, 以及高可用性), 情况会更复杂些
单调读
一个比强一致性弱, 但比最终一致性强的保证, 当读取数据时, 单调读保证, 如果某个用户依次进行多次读取, 则他绝不会看到回滚现象, 即在读取较新值之后又发生读旧值的情况
实现单调读的一种方式是, 确保每个用户总是从固定的同一副本执行读取(而不同的用户可以从不同的副本读取), 例如, 基于用户ID的哈希方法而不是随机选择副本, 但如果该副本发生失效, 则用户的查询必须重新路由到另一个副本
前缀一致读
对于一系列按照某个顺序发生的写请求, 那么读取这些内容时也会按照当时写入的顺序
一个解决方案是确保任何具有因果关系的写入都交给一个分区来完成, 但该方案真是实现效率会大打折扣
复制滞后的解决方案
事务
多主节点复制
首先主从复制存在一个明显的缺点: 系统只有一个主节点, 而所有写入都必须经由主节点, 如果由于某种原因, 例如与主节点之间的网络中断而导致主节点无法连接, 主从复制方案就会影响所有的写入操作
对主从复制模型进行自然的扩展, 则可以配置多个节点, 每个主节点都可以接受写操作, 后面复制的流程类似: 处理写的每个主节点都必须将该数据更改转发到所有其他节点, 这就是多主节点(也称为主-主, 或主动/主动)复制, 此时, 每个主节点还同时扮演其他主节点的从节点
适用场景
多数据中心
为了容忍整个数据中心级别故障或更接近用户, 可以把数据库的副本横跨多个数据中心, 而如果使用常规的基于主从的复制模型, 主节点势必只能放在其中的某一个数据中心, 而所有写请求都必须经过该数据中心, 有了多主节点复制模型, 则可以在每个数据中心都配置主节点. 在每个数据中心内, 采用常规的主从复制方案, 而在数据中心之间, 由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换更新
对比在多数据中心环境下, 部署但主节点的主从复制方案与多主复制方案之间的差异
性能
对于主从复制, 每个写请求都必须经由广域网传送至主节点所在的数据中心, 这会大大增加写入延迟, 并基本偏离了采用多数据中心的初衷(即就近访问), 而在多主节点模型中, 每个写操作都可以在本地数据中心快速响应, 然后采用异步复制方式将变化同步到其他数据中心. 因此, 对上层应用有效屏蔽了数据中心之间的网络延迟, 使得终端用户所体验到的性能更好
容忍数据中心失效
对于主从复制, 如果主节点所在的数据中心发生故障, 必须切换至另一个数据中心, 将其中一个从节点提升为主节点, 在多主节点模型中, 每个数据中心则可以独立于其他数据中心继续运行, 发生故障的数据中心在恢复之后更新到最新状态
容忍网络问题
数据中心之间的通信通常经由广域网, 它往往不如数据中心内的本地网络可靠, 对于主从复制模型, 由于写请求是同步操作, 对数据中心之间的网络性能和稳定性等更加依赖, 多主节点模型则通常采用异步复制, 可以更好地容忍此类问题, 例如临时网络闪断不会妨碍写请求最终成功
缺点
不同数据中心可能会同时修改相同的数据, 因而必须解决潜在的写冲突
由于多主复制在许多数据库中还只是新增的高级功能, 所以可能存在配置方面的细小缺陷; 在与其他数据库功能(例如自增主键, 触发器和完整性约束等)交互时有时会出现意想不到的副作用
离线客户端操作
另一种多主复制比较适合的场景是, 应用在与网络断开后还需要继续工作
从架构层面来看, 上述设置基本上等同于数据中心之间的多主复制, 只不过是个极端情况, 即一个设备就是数据中心, 而且它们之间的网络连接非常不可靠, 多个设备同步日志的例子表明, 多主节点可以得到想要的结果, 但中间过程依然有很多未知数
协作编辑
实时协作编辑应用程序允许多个用户同时编辑文档, 通常不会将写作编辑完全等价于数据库复制问题, 但二者确实有很多相似之处, 当一个用户编辑文档时, 所做的更改会立即应用到本地副本(web浏览器或客户端应用程序), 然后异步复制到服务器以及编辑同意文档的其他用户
如果要确保不会发生编辑冲突, 则应用程序必须先将文档锁定, 然后才能对其进行编辑, 如果另一个用户想要编辑同一个文档, 首先必须等到第一个用户提交修改并释放锁, 这种协作模式相当于主从复制模型下在主节点上执行事务操作
为了加快协作编辑的效率, 可编辑的粒度需要非常小, 例如单个按键甚至是全程无锁, 然而另一方面, 也会面临所有多主复制都存在的挑战, 即如何解决冲突
处理写冲突
多主复制的最大问题是可能发生写冲突, 这意味着必须有方案来解决冲突
同步和异步冲突检测
如果是主从给复制数据库, 第二个请求要么会被阻塞直到第一个写完成, 要么被终止(用户必须重试), 然而在多主节点的复制模型下, 这两个写请求都是成功的, 并且只能在稍后的时间上才能异步检测到冲突, 那时在要求用户层来解决冲突为时已晚
避免冲突
处理冲突最理想的策略是避免发生冲突
收敛于一致状态
对于主从复制模型, 数据更新符合顺序性原则, 即如果同一个字段有多个更新, 则最后一个写操作将决定该字段的最终值. 对于多主节点复制模型, 由于不存在这样的写入顺序, 所以最终值将处于不一致状态, 因此 数据库必须一种收敛趋同的方式来解决冲突, 这也意味着当所有更改最终被复制, 同步之后, 所有副本的最终值是相同的
解决的可能方式
给每个写入分配唯一的ID, 例如时间戳, 挑选最高的ID的写入作为胜利者, 并将其他写入丢弃, 这种技术被称为最后写入者获胜, 这种方法很流行, 但是很容易造成数据丢失
为每个副本分配一个为唯一的ID, 并制定规则, 例如序号高的副本写入始终优先于序号低的副本, 这种方法也可能会导致数据丢失
以某种方式将这些值合并在一起, 例如按照字母顺序排序, 然后拼接在一起
利用预定义好的格式来记录和保留冲突相关的所有信息, 然后依靠应用层逻辑, 事后解决冲突
自定义冲突解决逻辑
解决冲突最合适的方式可能还是依靠应用层, 所以大多数多主节点复制模型都有工具来让用户编写应用代码来解决冲突, 可以在写入或读取时执行这些代码逻辑
在写入时执行
只要数据库系统在复制变更日志时检测到冲突, 就会调用应用层的冲突处理程序
在读取时执行
当检测到冲突时, 所有冲突写入值都会暂时保存下来, 下一次读取数据时, 会将数据的多个版本读返回给应用层, 应用层可能会提示用户来自动解决冲突, 并将最后的结果返回到数据库
冲突解决通常用于单个行或文档, 而不是整个事务. 因此, 如果有一个原子事务包含多个不同写请求, 每个写请求仍然是分开考虑来解决冲突
什么是冲突
拓扑结构
复制的拓扑结构描述了写请求从一个节点的传播到其他节点的通信路径
环形和星型拓扑的问题是, 如果某一个节点发生了故障, 在修复之前, 会影响其他节点之间复制日志的转发
全链接拓扑也存在一些自身的问题, 主要是存在某些网络链路比其他链路更快的情况(例如由于不同的网络阻塞), 从而导致复制日志之间的覆盖
无主节点复制
一些数据存储系统采用了不同的设计思路: 选择放弃主节点, 允许任何副本直接接受来自客户端的写请求
节点失效时写入数据库
当一个客户端从数据库中读取数据时, , 它不是向一个副本发送请求, 而是并行地发送到多个副本, 客户端可能会得到不同节点的不同响应, 包括某些节点的新值和某些节点的旧值, 可以采用版本号技术确定那个值更新
读修复与反熵
复制模型应确保所有数据最终复制到所有的副本, 当一个失效节点重新上线后, 如何赶上错过的写请求
读修复
当客户端并行读取多个副本时, 可以检测到过期的返回值, 客户端可以判断一个过期值, 然后将新值写入到该副本, 这种方法主要适合那些被频繁读取的场景
反熵过程
此外, 一些数据存储有后台进程不断查找副本之间数据的差异, 将任何缺少的数据从一个副本复制到另一个副本, 与基于主节点复制的复制日志不同, 此反熵过程并不保证以特定的顺序复制写入, 并且会引入明显的同步滞后
并不是所有系统都实现了上述两种方案, 当缺少反熵过程的支持时, 由于读时修复只在发生读取时才可能执行修复, 那些很少访问的数据有可能在某些副本中已经丢失而无法检测到, 从而降低了写的持久性
读写quorum
如果有n个副本, 写入需要w个节点确认, 读取必须至少查询r个节点, 则只要w+r>n, 读取的节点中一定会包含最新值. 满足上述这些r, w值的读/写操作称之为法定票数读(或仲裁读)或法定票数写(或仲裁写), 也可以认为r和w时用于判定读, 写是否有效的最低票数
集群中可能存在多于n个节点, 但是数据只会保存在所设定的n个节点上, 我们可以对数据集进行分区, 从而支持比节点容纳上线更大的数据集
Quorum一致性的局限性
可以将w和r设置为较小的数字, 从而w+r<=n(即不满足仲裁条件). 这时, 读取和写入操作仍会被发送到n个节点, 但只需要等待更少的节点回应即可返回, 但是由于w和r配置的节点数较小, 读取请求当中可能恰好没有包含新值的节点, 因此最终可能会返回一个过期的旧值, 好的一方面是, 这种配置可以获得更低的延迟和更高的可用性, 例如网络中断, 许多副本变得无法访问, 相比而言有更高的概率继续处理读取和写入, 只有当可用的副本数已经低于w或r时, 数据库才会变得无法读/写, 即处于不可用状态
即使w+r>n的情况下, 也可能存在返回旧值的边界条件, 这主要取决于具体实现, 可能的情况包括
如果采用了sloppy quorum, 写操作的w节点和读取的r节点可能完全不同, 因此无法保证读写请求一定存在重叠的节点
如果两个写操作同时发生, 则无法明确先后顺序, 这种情况下, 唯一安全的解决方案时合并并发写入
如果写操作与读操作同时发生, 写操作可能仅在一部分副本上完成, 此时, 读取时返回旧值还是新值存在不确定性
如果某些副本上已经写入成功, 而其他一些副本发生写入失败, 且总的成功副本数少于w, 那些成功的副本上不会做回滚, 这意味着尽管这样的写操作被视为失败, 后续的读操作仍可能返回新值
如果具有新值的节点后来发生失效, 但恢复数据来自某个旧值, 则总的新值副本数会低于w, 这就打破了之前的判定条件
即使一切工作正常, 也会出现一些边界情况, "可线性化与quorum"
因此, 虽然quorum设计上似乎可以保证读取最新值, 但是现实情况往往更加复杂, 建议不要把参数w和r视为绝对的保证, 而是一种灵活可调的读取新值的概率
监控旧值
最终一致性是个非常模糊的保证, 从可操作性上讲, 量化究竟何为"最终"很有实际价值
宽松的quorum与数据回传
放松的仲裁: 当客户在网络中断期间可以连接到某些数据库节点, 但是这些节点又不是能够满足数据仲裁的那些节点, 此时数据库设计者就面临着选择, 如果选择接受该写请求, 只是将他们暂时写入一些可访问的节点中(这些节点并不在n个节点集合中), 这种方案称之为放松的仲裁
写入和读取仍然需要w和r个成功的响应, 但包含了那些并不在先前指定的n个节点
sloppy qurorum对于提高写入可用性特别有用: 只要有w个节点可用, 数据库就可以接受新的写入, 但是着意味着, 即使满足w+r>n, 也不能保证在读取某个键时, 一定能读到最新值, 因为新值可能被临时写入n之外的某些节点且尚未回传过来
多数据中心操作
检测并发写
最后写入者获胜(丢弃并发写入)
一种实现最终收敛的方法是, 每个副本总是保存最新值, 允许覆盖并丢弃旧值, 那么, 假定每个写请求都最终同步到所有副本, 只要我们有一个明确的方法来确定哪一个写入是最新的, 则副本可以最终收敛于相同的值
关键点在与如何定义"最新"
即使无法确定写请求的"自然顺序", 我们可以强制对其排序, 例如, 为每个写请求附加一个时间戳, 然后选择最新即最大的时间戳, 丢弃较早时间戳的写入, 这个冲突写入算法被称为最后写入者获胜(last write wins, LWW)
LWW可以实现最终收敛的目标, 但是以牺牲数据持久性为代价
要确保LWW安全无副作用的唯一方法是, 值写入一次然后写入值视为不可变, 这样就避免了对同一个主键的并发(覆盖)写
Happens-before关系和并发
如何判断两个操作是否是并发
如果B知道A, 或者依赖于A, 或者以某种方式在A基础上构建, 则称操作A在操作B之前发生, 这是定义何为并发的关键, 事实上, 我们也可以简单地说, 如果两个操作都不在另一个之前发生, 那么操作是并发的(或者两者都不知道对方)
确定前后关系
一个确定操作并发性的算法
流程
服务器为每个主键维护一个版本号, 每当主键新值写入时递增版本号, 并将新版本号与写入的值一起保存
当客户端读取主键时, 服务器将返回所有(未被覆盖的)当前值以及最新的版本号. 且要求写之前, 客户必须先发送读请求
客户端写主键, 写请求必须包含之前读到的版本号, 读到的值和新值合并后的集合. 写请求的响应可以像读操作一样, 会返回所有当前值, 这样就可以一步步链接起多个写入的值
当服务器收到带有特定版本号的写入时, 覆盖该版本号或更低版本的所有值(因为知道这些值已经被合并到新传入的值集合中), 但必须保存更高版本号的所有值(因为这些值与当前的写操作属于并发)
如果一个写请求没有包含版本号, 他将与所有其他写入同时进行, 不会覆盖任何已有的值, 其传入的值将包含在后续读请求的返回值列表当中
合并同时写入的值
上述算法可以保证不会发生数据丢弃, 但是客户端需要做一些额外的工作, 如果多个操作并发发生, 则客户端必须通过合并并发写入的值来继承旧值
书中提到union配合删除标记, 是否存在问题
版本矢量
小结
复制的目的
高可用性
即使某台机器出现故障, 系统也能保持正常运行
连接断开与容错
允许应用程序在出现网络中断时继续工作
低延迟
将数据防止在距离用户较近的地方, 从而实现更快的交互
可扩展性
采用副本读取, 大幅提高系统读操作的吞吐量
三种多副本方案
主从复制
多节点复制
无主节点复制
一致性模型
写后读一致性
保证用户总能看到自己所提交的最新数据
单调读
用户在某个时间点读到数据之后, 保证此后不会出现比该时间点更早的数据
前缀一致性
保证数据之间的因果关系, 例如, 总是以正确的顺序先读取问题, 然后看到回答
第6章: 数据分区
面对一些海量数据集或非常高的查询压力, 复制技术还不够, 我们还需要将数据拆分成分区, 也称为分片
分区通常是这样定义的, 即每一条数据(或者每条记录, 每行或每个文档)只属于某个特定分区
采用数据分区的主要目的是提高扩展性, 不同的分区可以放在一个无共享集群的不同节点上, 这样一个大数据集可以分散在更多的磁盘上, 查询负载也随之分布到更多的处理器上
数据分区与数据复制
分区通常与复制结合使用, 即每个分区在多个节点都存有副本, 一个节点上可能存储了多个分区
键值数据的分区
分区的主要目标是将数据和查询负载均匀分布在所有节点上
如果分区不均匀, 则会出现某些分区节点比其他分区承担更多的数据量或查询负载, 称之为倾斜, 倾斜会导致分区效率严重下降, 负载严重不成比例的分区即称为系统热点
避免热点最简单的方法是将记录随机分配给所有节点上, 这种方法可以比较均匀地分布数据, 但是有一个很大的缺点: 当试图读取特定的数据时, 没有办法知道数据保存在哪个节点上, 所以不得不并行查询所有节点
基于关键字区间分区
一种分区方式是为每个分区分配一段连续的关键字或者关键字区间范围
关键字的区间段不一定要均匀分布, 这主要是因为数据本身可能就不均匀
每个分区内可以按照关键字排序保存(SSTable和 LSM-Trees), 然而基于关键字的区间分区的缺点是某些访问模式会导致热点
未避免该问题, 需要使用时间戳以外的其他内容作为关键字的第一项, 例如, 可以在时间戳前面加上传感器名称作为前缀, 这样首先由传感器名称, 然后按时间进行分区
基于关键字哈希值分区
一个好的哈希函数可以处理数据倾斜并使其均匀分布
然而, 通过关键字哈希进行分区, 我们丧失了良好的区间查询特性
组合索引, 多列组成复合主键, 一部分进行哈希分区, 另一部分基于关键字区间分区
负载倾斜与热点
分区与二级索引
基于文档分区的二级索引
这种查询分区数据库的方法有时也被称为分散/聚集
基于词条的二级索引分区
我们可以对所有的数据构建全局索引, 而不是每个分区维护自己的本地索引, 全局索引也进行分区, 且可以与数据关键字采用不同的分区策略
我们将这种索引方案称为词条分区, 它以待查找的关键字本身作为索引
这种全局的词条分区相比于文档分区索引的主要优点是, 它的读取更为高效, 但是写入速度较慢且非常复杂
分区再平衡
动态再平衡的策略
为什么不用取模
节点数变化后, 很多关键字需要迁移
固定数量的分区
创建远超实际节点数的分区数, 然后为每个节点分配多个分区
动态分区
分区自动根据数据量大小来创建或合并
按节点比例分区
分区数和集群节点数成正比关系
自动和手动再平衡
全自动的再平衡(由系统自动决定何时将分区从一个节点迁移到另一个节点)
纯手动方式(分区到节点的映射由管理员来显示配置)
自动生成一个分区分配的建议方案, 需要管理员确认才能生效
请求路由
当客户端需要发送请求时, 如何知道应该连接哪个节点
属于一类典型的服务发现问题, 服务发现并不限于数据库, 任何通过网络访问的系统都有这样的需求, 尤其是当服务目标支持高可用时(在多台机器上有冗余配置)
处理策略
1. 允许客户端连接任意的节点, (例如, 采用循环式的负载均衡器), 如果某节点恰好拥有所请求的分区, 则直接处理该请求, 否则, 将请求转发到下一个合适的节点, 接收答复, 并将答复返回给客户端
2. 将所有客户端的请求都发送到一个路由层, 由后者负责将请求转发到对应的分区节点上, 路由层本身不处理任何请求, 它仅充当一个分区感知的负载均衡器
3. 客户端感知分区和节点分配关系, 此时客户端可以直接连接到目标节点, 而不需要任何中介
无论哪种方法, 核心问题: 作出路由决策的组件, 如何知道分区与节点的对应关系以及其变化情况
独立的协调服务(如ZooKeeper)
节点间协议来同步集群状态变化(如gossip)
并行查询执行
小结
数据量如果太大, 单台机器进行存储和处理就会称为瓶颈, 因此需要引入数据分区机制, 分区的目的时通过多台机器均匀分布数据和查询负载, 避免出现热点
分区方法
基于关键字区间的分区
哈希分区
二级索引分区
基于文档来分区二级索引(本地索引)
基于词条来分区二级索引(全局索引)
第7章: 事务
深入理解事务
ACID的含义
原子性(Atomicity)
特征: 在出错时中止事务, 并将部分完成的写入全部丢弃, 可中止性可能原子性更为准确
一致性(Consistency)
主要指对数据由特定的预期状态, 任何数据更改必须满足这些状态约束
更多的是应用层的属性
隔离性(Isolation)
并发执行的多个事务相互隔离, 它们不能相互交叉, 经典教材把隔离定义为可串行化
持久性(Durability)
保证一旦事务提交成功, 即使存在硬件故障或数据库崩溃, 事务所写入的任何数据也不会消失
单对象与多对象事务操作
单对象写入
存储引擎几乎必备的设计就是在单节点, 单个对象层面上提供原子性和隔离性, 例如, 出现宕机时, 基于日志恢复来实现原子性, 对每个对象采用加锁的方式(每次只允许一个线程访问对象)来实现隔离
多对象事务的必要性
要求写入多个不同对象并进行协调的情况
关系型数据模型, 表中的某行是另一个表中的外键
文档数据模型, 出现非规范化数据时
带有二级索引的数据库
处理错误与中止
重试中止的事务是一个简单有效的错误处理机制, 但是存在问题
如果事务已经执行成功, 但是返回给客户端的消息在网络传输时发生意外, 重试将导致重复执行
如果错误是由于系统超负荷所致, 重试事务将使情况更遭
临时性故障所导致的问题需要重试, 但是永久性故障的重试没有意义
如果在数据库之外, 事务有其他副作用, 即使事务中止, 这些副作用仍可能生效
如果客户端进程在重试过程中也发生失败, 没有其他人负责重试, 则待写入的数据可能会因此而丢失
弱隔离级别
读-提交
只提供两个保证, 防止脏读, 脏写
防止脏读
脏读, 假定某个事务已经完成部分数据的写入, 但事务尚未提交(或中止), 此时另一个事务如果可以看到尚未提交的数据, 就是脏读
需要防止脏读的需求
事务需要更新多个对象
如果事务发生中止, 所有写入操作都需要回滚
防止脏写
如果两个事务同时尝试更新相同的对象, 先前的写入是尚未提交事务的一部分, 但仍然被覆盖掉, 那就是脏写
实现读提交
数据库通常采用行级锁来防止脏写: 当事务想修改某个对象(例如行或文档)时, 它必须首先获得该对象的锁, 然后一直持有锁直到事务提交(或中止),
快照级别隔离与可重复读
不可重复读(nonrepeatable read)或读倾斜(read skew)
存在一些场景无法容忍这种暂时的不一致
备份场景
分析查询与完成性检查场景
快照级别隔离是解决上述问题的常用手段, 总体想法: 每个事务都从数据库的一致性快照中读取, 事务一开始所看到的是最近提交的数据, 即使数据随后可能被其他事务修改, 但是保证每个事务都只能看到该特定时间点的旧数据
快照级别隔离对于长时间运行的只读查询(如备份和分析)十分有用
实现快照级别隔离
一致性快照的可见性规则
索引与快照级别隔离
可重复读与命名混淆
防止更新丢失
原子写操作
原子操作通常采用对读取对象加独占锁的方式来实现, 这样在更新被提交之前就不会有其他事务可以读它, 这种技术有时被称为游标稳定性. 另一种实现方式是强制所有的原子操作都在单线程上执行
显式加锁
如果数据库不支持内置原子操作, 另一种防止更新丢失的方法是由应用程序显式锁定待更新的对象
自动检测更新丢失
原子操作和锁都是通过强制"读-修改-写回"操作序列串行执行来防止丢失更新, 另一种思路是先让他们并发执行, 但如果事务管理器检测到了更新丢失风险, 则会终止事务, 并强制退回到安全的"读-修改-写回"方式
原子比较和设置
冲突解决与复制
写倾斜与幻读
定义写倾斜
可以将写倾斜定义为一种广义的更新丢失问题, 即如果两个事务读取相同的一组对象, 然后更新其中一部分: 不同的事务可能更新不同的对象, 则可能发生写倾斜; 而不同的事务如果更新的是同一个对象, 则可能发生脏写或更新丢失
涉及多个对象, 单对象的原子操作不起作用
基于快照级别隔离来实现更新丢失自动检测也有问题, 自动防止写倾斜要求真正的可串行化隔离
自定义约束条件需要数据库支持, 多个对象的约束需要更加特殊的支持
更多写倾斜的例子
为何产生写倾斜
模式
1. 查询满足条件的行
2. 根据查询结果来决定下一步操作
3. 如果继续执行, 将发起数据库写入, 并提交事务
这种在一个事务中的写入改变了另一个事务查询结果的现象, 称为幻读
实体化冲突
把幻读问题转变为针对数据库中一组具体行的锁冲突问题
串行化
实际串行执行
解决并发问题最直接的方法是避免并发: 即在一个线程上按顺序方式每次只执行一个事务
采用存储过程封装事务
在数据库的早期阶段, 采用事务机制是希望能囊括用户的所有操作序列
存储过程的优缺点
缺点
存储过程语言过时
数据库中的代码难以管理
设计不好的存储过程影响性能
缺点可以克服
存储过程与内存式数据存储使得单线程上执行所有事务变得可行
分区
串行执行所有事务使得并发控制更加简单, 但是数据库的吞吐量被限制在单机单个CPU核, 虽然只读事务可以在单独的快照上执行, 但是对于那些高写入需求的应用程序, 单线程事务处理很容易称为严重的瓶颈
对于跨分区的事务, 数据库必须在涉及的所有分区之间协调事务
串行执行小结
可以实现串行化隔离的串行执行事务, 需要满足的约束条件
事务必须简短而高效, 否则一个缓慢的事务会影响到所有其他事务的执行性能
仅限于活动数据集完全可以加载到内存的场景. 有些很少访问的数据可能会被移动到磁盘, 但万一单线程事务需要访问它, 就会严重拖累性能
两阶段加锁
近三十年, 数据库只有一种被广泛使用的串行化算法, 那就是两阶段加锁(two-phase locking, 2PL)
两阶段加锁方法: 多个事务可以同时读取同一对象, 但只要出现任何写操作(包括修改或删除), 则必须加锁以独占访问
2PL不仅在并发写操作之间互斥, 读取也会和修改产生互斥, 这是与快照级别隔离("读写互不干扰"))的关键区别
2PL提供了串行化, 所以可以防止前面的所有竞争条件, 包括更新丢失和写倾斜
实现两阶段加锁
数据库中每个对象都有一个读写锁来隔离读写操作, 即锁可以处于共享模式或独占模式
两阶段: 第一阶段即事务执行之前要获取锁, 第二阶段即事务结束时释放锁
由于使用了很多锁机制, 很容易出现死锁现象, 数据库系统需要自动检测事务之间的死锁情况, 并强行终止其中一个来打破僵局
两阶段加锁的性能
其事务吞吐量和查询响应时间相比与其他弱隔离级别下降非常多
部分原因在与锁的获取和释放本身的开销, 更重要的是其降低了事务的并发性
谓词锁
作用类似于之前描述的共享/独占锁, 而区别在于, 它不属于某个特定的对象(如表的某一行), 而是作用于满足某些搜索条件的所有查询对象
谓词锁甚至可以保护数据库中那些尚不存在但可能马上会被插入的对象(幻读). 将两阶段加锁与谓词锁结合使用, 数据库可以防止所有形式的写倾斜以及其他竞争条件, 隔离变得真正串行化
索引区间锁
谓词锁性能不佳, 如果活动事务中存在许多锁, 那么检查匹配这些锁就变得非常耗时, 因此大多数使用2PL的数据库实际使用的是索引区间锁(next-key locking), 本质上是它对谓词锁的简化或近似
简化谓词锁的方式是将其保护的对象扩大化, 锁定更大范围的对象, 超出串行化所要求的部分, 但是由于开销低很多, 可以认为是一种很好的折中方案
可串行化的快照隔离
两阶段加锁虽然可以保证串行化, 但性能差强人意且无法扩展(由于串行执行), 弱级别隔离虽然性能不错, 但容易引发各种边界条件(如更新丢失, 写倾斜, 幻读等), 但串行化隔离和性能并不是从根本上相互冲突而无法兼得
最近出现一种称为可串行化的快照隔离(Serializable Snapshot Isolation, SSI)算法
悲观与乐观的并发控制
两阶段加锁是一种典型的悲观并发控制机制: 它基于这样的设计原则: 如果某些操作可能出错, 那么直接放弃, 采用等待方式直到绝对安全
某种意义上讲, 串行执行是种极端悲观的选择: 事务执行期间, 等价于事务对整个数据库(或数据库的一个分区)持有互斥锁
可串行化的快照隔离则是一种乐观并发控制, 在这种情况下, 如果可能发生潜在冲突, 事务会继续执行而不是中止, 寄希望于一切相安无事, 而当事务提交时, 数据库会检查是否确实发生了冲突, 如果是, 中止事务并接下来重试
基于过期的条件做决定
查询和写事务之间可能存在因果依赖关系, 为了提供可串行化的隔离, 数据库必须检测事务是否会修改其他事务的查询结果, 并在此情况下中止写事务
如何知道查询结果是否发生了改变
读取是否作用于一个(即将)过期的MVCC对象(读取之前已经有未提交的写入)
检查写入是否影响即将完成的读取(读取之后, 又有新的写入)
检测是否读取了过期的MVCC对象
数据库需要跟踪那些由于MVCC可见性规则而被忽略的写操作, 当事务提交时, 数据库会检查是否存在一些当初被忽略的写操作现在已经完成了提交, 如果是则必须终止当前事务
等到事务提交时, 为了减少不必要的中止
检测是否影响了之前的读
当一个事务尝试修改时, 它首先检查索引, 从而确定是否最近存在一些读目标数据的其他事务, 类似于写锁, 但是不会阻塞读取, 而是知道读事务提交时才进一步通知他们, 所读到的数据现在发生了变化
可串行化快照隔离的性能
与两阶段加锁相比, 可串行化快照隔离的一大优点是事务不需要等待其他事务所持有的锁, 这和快照隔离一样, 读写通常不会相互阻塞, 这样的设计使得查询延迟更加稳定, 可预测
与串行执行相比, 可串行化快照隔离可以突破单个CPU核的限制
事务中止的比例会显著影响SSI的性能表现, SSI要求读-写型事务要简短
小结
第8章: 分布式系统的挑战
故障与部分失效
云计算和超算
如何构建大规模计算系统
规模的一个极端是高性能计算(high-performance computing, HPC), 包含成千上万个CPU的超级计算机构成一个庞大的集群, 通常用于计算密集型的科学计算任务
另一个极端是云计算, 定义并非明确, 但是通常具有以下特征: 多租户数据中心, 通用计算机, 用IP以太网链接, 弹性/按需资源分配, 并按需计费
传统企业数据中心则位于以上两个极端之间
不可靠的网络
分布式无共享系统, 即通过网络连接的多个节点. 无共享并不是构建集群系统的唯一方式, 但它却是构建互联网服务的主流方式, 主要原因: 不需要专门的硬件因此成本相对低廉, 可以采用通用的商品化硬件, 可以采用跨区域的多数据中心来实现高可靠性
现实中的网络故障
检测故障
超时与无限期的延迟
网络拥塞与排队
同步与异步网络
同步网络: 即使数据中间经过了多个路由器, 空间已经在网络中得到预留, 不会受排队影响, 由于没有排队, 网络的最大端到端延迟是固定的, 我们称之为有界延迟
网络延迟是否可预测
不可靠的时钟
可以在一定程度上同步机器之间的时钟, 最常用的方法是网络事件协议(Network Time Protocol, NTP)
单调时钟与墙上时钟
墙上时钟
墙上时钟根据某个日志(也成为墙上时间)返回当前的日期与时间
墙上时钟可以与NTP同步
单调时钟
单调时钟更适合测量持续时间段(时间间隔), 例如超时或服务的响应时间. 单调时钟的名字来源于它们保证总是向前(而不会出现墙上时钟的回拨现象)
单调时钟的绝对值并没有任何意义
如果服务器有多路CPU, 则每个CPU可能有单独的计时器, 且不与其他CPU进行同步
如果NTP检测到本地石英比时间服务器上更快或更慢, NTP会调整本地石英的震动频率(这被称为摆动)
时钟同步与准确性
依赖同步的时钟
时间戳与事件顺序
最后写入获胜(LWW)
问题
数据库写入可能会奇怪地丢失: 后续发生地写操作没法覆盖另一个较早的值
LWW无法区分连续快速发生的连续写操作和并发写入(每个写操作都不依赖于其他写). 需要额外的因果关系跟踪机制来防止因果冲突
由于时钟精度的限制, 两个节点可能各自独立产生了完全相同的时间戳, 为了解决这样的冲突, 需要一个额外的仲裁值(可以简单地引入一个大的随机数), 但该方法还是无法区分因果关系
时钟的置信区间
全局快照的同步时钟
进程暂停
进程暂停很长时间的原因
许多编程语言的垃圾收集器(GC), 有时运行期间会暂停所有正在运行的线程, 有时甚至会暂停数分钟
在虚拟化环境中, 可能会暂停虚拟机(暂停所有执行进程并将内存状态保存到磁盘)然后继续(从内存中加载数据然后继续执行)
运行在终端用户设备时, 执行也可能发生暂停, 例如用户关闭了电脑或休眠
当操作系统执行线程上下文切换时, 或者虚拟机管理程序切换到另一个虚拟机时. 在虚拟机环境中, 这种被其他虚拟机中断的CPU时间称为窃取时间
如果应用程序执行同步磁盘操作, 则线程可能暂停并等待磁盘I/O完成
如果操作系统配置了基于磁盘的内存交换分区, 内存访问可能触发缺页中断, 进而需要从磁盘中加载内存页
通过发送SIGSTOP信号来暂停UNIX进程, 例如在shell中按下Ctrl-Z
响应时间保证
提供实时保证需要来自软件栈的多个层面的支持: 首先是一个实时操作系统(realtime operating system, RTOS), 保证进程在给定的时间间隔内完成CPU时间片的调度分配, 其次, 库函数也必须考虑最坏的执行时间; 然后, 动态内存分配很可能要受限或者完全被禁止(如果存在实时垃圾收集器, 确保GC不能处理太多任务); 最终还需要大量, 充分的测试和验证, 以确保满足要求
调整垃圾回收的影响
一个较新的想法时把GC暂停视为节点的一个计划内的临时离线, 当节点启动垃圾回收时, 通知其他节点来接管客户端的请求
该方法的一个变种, 只对短期对象(可以快速回收)执行垃圾回收, 然后在其变成长期存活对象前, 采用定期重启的策略从而避免对长期存活对象执行全面回收
知识, 真相与谎言
真相由多数决定
许多分布式算法都依靠法定票数, 即在节点之间进行投票(读写quorum), 任何决策都需要来自多个节点的最小投票数, 从而减少对特定节点的依赖
主节点与锁
很多情况, 我们需要在系统范围内只能有一个实例
只允许一个节点作为数据库分区的主节点, 以防止出现脑裂
只允许一个事务或客户端持有特定资源的锁, 以防止同时写入从而导致数据破坏
只允许一个用户来使用特定的用户名, 从而确保用户名可以唯一标识用户
在分布式系统的实现时需要额外注意: 即使某个节点自认为它是"唯一的那个", 但不一定获得了系统法定票数的同意
Fencing令牌
当使用锁和租约机制来保护资源的并发访问时, 必须确保过期的"唯一的那个"节点不能影响其他正常部分, 要实现这一目标, 可以采用一种相当简单的技术fencing
在服务器端检查令牌可能看起来有些复杂, 但是是推荐的正确做法, 系统服务不能假定所有的客户端都表现符合预期, , 事实上客户端通常是由权限级别相对较低的人来操作运行, 因此存在一定的误用, 滥用风险, 从安全角度讲, 服务端必须防范这种来自客户端的滥用
拜占庭故障
fencing令牌可以检测并阻止那些无意的操作(例如节点没有发现其租约已经过期), 但是如果有节点故意试图破坏系统, 在发送消息时可以简单地伪造令牌即可
如果节点存在"撒谎"的情况(即故意发送错误的或破坏性的响应), 那么分布式系统处理的难度就上了一个台阶. 这种行为称为拜占庭故障, 在这样不信任的环境中需要达成共识的问题也被称为拜占庭将军问题
如果某个系统中即使发生部分节点故障, 甚至不遵从协议, 或者恶意攻击, 干扰网络, 但仍可继续正常运行, 那么我们称之为拜占庭式容错系统
航空航天领域, 计算机内存或CPU寄存器中的数据可能会被辐射而发生故障
比特币和其他区块链一样的点对点网络
弱的谎言形式
需要增加必要的机制来防范一些不那么恶意的"谎言"
理论系统模型与现实
分布式系统的算法需要容忍本章所讨论的各种故障
算法的实现不能过分依赖特定的硬件和软件配置, 这就要求我们需要对预期的系统错误进行形式化的描述, 我们通过定义一些系统模型来形式化描述算法的前提条件
计时方面的系统模型
同步模型
同步模型假定有上界的网络延迟, 有上界的进程暂停和有上界的时钟误差
部分同步模型
部分同步意味着系统在大多数情况下像一个同步系统一样运行, 但有时候会超出网络延迟, 进程暂停和时钟漂移的预期上界
异步模型
在这个模型中, 一个算法不会对时机做任何的假设, 甚至里面根本没有时钟
节点失效的系统模型
崩溃-中止模型
算法假设一个节点只能以一种方式发生故障, 即遭遇系统崩溃
崩溃-恢复模型
节点可能会在任何时候发生崩溃, 且可能会在一段时间之后得到恢复并再次响应
拜占庭(任意)失效模型
节点可能发生任何事情
算法的正确性
为了定义算法的正确性, 我们可以描述他的属性信息
例如, 对于锁服务的fencing令牌生成算法, 要求算法具有以下属性
唯一性
两个令牌不能获得相同的值
单调递增
如果请求x返回了令牌tx, 请求y返回了令牌ty, 且x在y之前先完成, 那么tx<ty
可用性
请求令牌的节点如果不发生崩溃则最终一定会收到响应
如果针对某个系统模型的算法在各种情况下都能满足定义好的属性要求, 那么我们称这个算法是正确的
安全与活性
在上面的例子中, 唯一性和单调递增属于安全属性, 而可用性属于活性
活性的定义通常会包括暗示"最终"
安全性通常可以理解为"没有发生意外", 而活性则类似"预期的事情最终一定会发生"
如果违反了安全属性, 我们可以明确指向发生的特定的时间点, 且一旦违反安全属性, 违规行为无法撤销, 破坏已实际发生
活性反过来: 可能无法明确某个具体的时间点, 但总是希望在未来的某个时间点可以满足要求
将系统模型映射到现实世界
证明算法正确并不意味这真是系统上的某个具体实现一定是正确的
理论性分析与实证性检验对最终的成功同等重要
小结
第9章: 一致性与共识
错误的活着, 还是正确地挂掉?
为了构建容错系统, 最好先建立一套通用的抽象机制和与之对应的技术保证, 这样就只需要实现一次, 其上的各种应用程序都可以安全地信赖底层的保证. 沿着这个思路, 尝试建立可以让分布式应用忽略内部各种问题的抽象机制
一致性保证
分布式一致模型与事务隔离级别
事务隔离主要是为了处理并发执行事务时的各种临界条件
分布式一致性则主要是针对延迟和故障等问题来协调副本之间的状态
首先介绍线性化, 这是最强的一致性模型, 考察其优缺点
然后探讨分布式系统中事件顺序问题, 特别是因果关系和全局顺序
最后"分布式事务与共识", 我们将探索如何自动提交分布式事务, 并最终解决共识问题
可线性化
基本想法就是让一个系统看起来好像只有一个数据副本, 且所有操作都是原子的
如何达到线性化
一旦某个读操作返回了新值, 之后所有的读(包括相同或不同的客户端)都必须返回新值
可线性化(Linearizability)非常容易与可串行化(Serializability)发生混淆
可串行化是事务的隔离属性, 其中每个事务可以读写多个对象(行, 文档, 记录等), 它用来确保事务执行的结果与串行执行(即每次执行一个事务)的结果完全相同, 即使串行执行的顺序可能与事务实际执行顺序不同
可线性化是读写寄存器(单个对象)的最新值保证
数据库可以同时支持可串行化与线性化, 这种组合又被称为严格的可串行化或者强的单副本可串行化(strong one-copy serializability, strong-1SR)
基于两阶段加锁或者实际以串行执行都是典型的可线性化
线性化的依赖条件
加锁与主节点选举
主从复制的系统需要确保有且只有一个主节点, 否则会产生脑裂, 选举新的主节点常用的方法是使用锁: 即每个启动的节点都试图获得锁, 其中只有一个可以成功即成为主节点
不管锁的具体实现如何, 它必须满足可线性化
线性化存储服务是所有这些协调服务的基础
约束与唯一性保证
跨通道的事件依赖
实现线性化系统
复制方案
主从复制
部分支持可线性化
共识算法
可线性化
多主复制
不可线性化
无主复制
可能不可线性化
线性化与quorum
线性化的代价
CAP理论
CAP理论有时也代表一致性, 可用性, 分区容错性, 系统只能支持其中两个特性, 但这种理解存在误导性, 网络分区是一种故障, 不管喜欢不喜欢, 它都有可能发生, 所以无法选择或逃避分区的问题. 围绕CAP有太多的误解与困扰, 最后反而无法帮助我们更好地理解系统
可线性化与网络延迟
虽然线性化是个很有用的保证, 但实际上很少有系统真正满足线性化
例如, 现代多核CPU上的内存甚至就是非线性化: 如果某个CPU核上运行的线程修改一个内存地址, 紧接着另一个CPU核上的线程尝试读取, 则系统无法保证可以读到刚刚写入的值, 除非使用了内存屏障或fence指令
首先, CAP理论不适用于当今的多核-内存一致性模型: 在计算机内部, 我们通常假设通信是可靠的, 例如我们不会假定一个CPU核在与其他核断开之后还能安然工作, 之所以放弃线性化的原因就是性能, 而不是为了容错
顺序保证
顺序与因果关系
顺序, 有助于保持因果关系
事务一致性快照, "一致性", 意味着与因果关系一致: 如果快照中包含了答案, 那么它必须包含所提的问题
因果关系对所发生的事件施加了某种排序: 发送消息先于收到消息; 问题出现在答案之前等
因果顺序并非全序
全序关系支持任何两个元素之间进行比较, 即对于任意两个元素, 总是可以指出哪个更大, 哪个更小
有些集合不符合全序, 无法直接比较它们, 我们称之为不可比较, 数据集合只能是偏序
全序和偏序的差异也会体现在不同的数据库一致性模型中:
可线性化
全序: 对于任何两个操作, 总可以指出那个在前
因果关系
如果两个操作都没有发生在对方之前, 那么这两个操作是并发关系
可线性化强于因果一致性
可线性化一定意味着因果关系: 任何可线性化的系统都将正确地保证因果关系
线性化会显著降低性能和可用性, 尤其是在严重网络延迟的情况下
线性化并非是保证因果关系的唯一途径, 还有其他方法使得系统可以满足因果一致性而免于线性化所带来的性能问题, 事实上, 因果一致性可以认为是, 不会由于网络延迟而显著影响性能, 又能对网络故障提供容错的最强的一致性模型
捕获因果依赖关系
序列号排序
非因果序列发生器
lamport时间戳
时间戳排序依然不够
全序关系广播
全序关系广播通常指节点之间交换消息的某种协议, 下面是一个非正式的定义, 它要求满足两个基本安全属性
可靠发送: 没有消息丢失, 如果消息发送到了某一个节点, 则它一定要发送到所有节点
严格有序: 消息总是以相同的顺序发送给每个节点
使用全序关系广播
全序关系广播正式数据库复制所需要的: 如果每条消息代表数据库写请求, 并且每个副本都按相同的顺序处理这些写请求, 那么所有副本可以保持一致(或许有些滞后), 该原则也被称为状态机复制
理解全序关系广播的另一种方式是将其视为日志(如复制日志, 事务日志或预写日志). 传递消息就像追加方式更新日志, 由于所有节点必须以相同的顺序发送消息, 因此所有节点都可以读取日志并看到相同的消息序列
采用全序关系广播实现线性化存储
全序关系广播是基于异步模型: 保证消息以固定的顺序可靠地发送, 但是不保证消息何时发送成功(因此某个接收者可能明显落后于其他接收者), 而可线性化则强调就近性: 读取时保证能够看到最新的写入值
可以通过全序广播以追加日志的方式来实现线性化的原子比较-设置操作
1. 在日志中追加一条消息, 并指明想要的用户名
2. 读取日志, 将其广播给所有节点, 并等待回复
3. 检查是否有任何消息生成该用户名已被占用
此过程可以确保可线性化写入, 但无法保证线性化读取, 即从一部日志更新的存储中读取数据时, 可能是旧值, 具体来说, 这里只提供了顺序一致性, 有时也称为时间线一致性, 它弱于线性化保证
为了同时满足线性化读取, 有几种方案
可以采用追加的方式把读请求排序, 广播, 然后各个节点获取该日志, 当本节点收到消息时才执行真正的读操作, 消息在日志中的位置已经决定了读取发生的时间点
如果可以以线性化的方式获取当前最新日志中消息的位置, 则查询位置, 等待直到该位置之前的所有条目都已经发送给你, 接下来再执行读取
可以从同步更新的副本上进行读取, 这样确保总是读取最新值, 这种技术可以用于链式复制
采用线性化存储实现全序关系广播
假定已有了线性化的存储, 在其上构建全序关系广播
最简单的方法是假设有一个线性化的寄存器来存储一个计数, 然后十七支持原子自增-读取操作或者原子比较-设置操作
算法思路很简单: 对于每个要通过全序关系广播的消息, 原子递增并读取该线性化的计数, 然后将其作为序列号附加到消息中, 接下来将消息广播到所有节点(如果发生丢失, 则重新发送), 而接受者也严格按照序列化来发送回复消息
分布式事务与共识
共识问题是分布式计算中最重要也是最基本的问题之一
有很多重要的场景都需要集群节点达成某种一致, 例如
主节点选举
对于主从复制的数据库, 所有节点需要就谁来充当主节点达成一致
原子事务提交
对于支持跨节点或跨分区事务的数据库, 会面临这样的问题: 某个事务可能在一些节点上执行成功, 但在其他节点却不幸发生了失败, 为了维护事务的原子性, 所有节点必须对事务的结果达成一致: 要么全部成功提交, 要么中止/回滚, 这个共识的例子被称为原子提交问题
共识的不可能性
FLP结论: 如果节点存在可能崩溃的风险, 则不存在总是能够达成共识的稳定算法
但该结论有其局限性, 它假定确定性算法都不能使用任何时钟或超时机制
原子提交与两阶段提交
原子性可以为上层应用提供非常简单的语义: 事务的结果要么是成功提交, 要么是中止. 原子性可以防止失败的事务破坏系统, 避免形成部分成功夹杂着部分失败
从单节点到分布式的原子提交
在单节点上， 原子性通常由存储引擎来负责
两阶段提交
(two-phase commit, 2PC)是一种在多节点之间实现事务原子提交的算法, 用来确保所有系欸但要么全部提交, 要么全部中止
系统的承诺
2PC过程
1. 应用程序启动一个分布式事务, 首先想协调者请求事务ID, 该ID全局唯一
2. 应用程序在每个参与节点上执行单节点事务, 并将全局唯一事务ID附加到事务上
3. 当应用程序准备提交时, 协调者向所有参与者发送准备请求, 并附带全局事务ID, 如果准备请求有任何一个发生失败或者超时, 则协调者会通知所有参与者放弃事务
4. 参与者在收到准备请求后, 确保在任何情况下都可以提交事务, 包括安全地将事务数据写入磁盘(不能以任何借口稍后拒绝提交, 包括系统崩溃, 电源故障或磁盘空间不足等), 并检查是否存在冲突或约束违规. 一旦向协调者回答"是", 节点就会承诺提交事务
5. 当协调者收到所有准备请求地答复时, 就是否提交(或放弃)事务要做出明确的决定(即只有所有参与者都投赞成票时才会提交). 协调者把最后的决定写入到磁盘的事务日志中, 防止稍后系统崩溃, 并可以恢复之前的决定. 这个时刻称为提交点
6. 协调者的决定写入磁盘之后, 接下来向所有参与者发送提交(或放弃)请求. 如果此请求出现失败或超时, 则协调者必须一直重试, 直到成功为止. 此时, 所有节点不允许有任何反悔: 一旦做了决定, 就必须贯彻执行, 即使需要很多次重试
该协议有两个不归路, 这两个决定确保了2PC的原子性
当参与者投票"是", 它做出了肯定提交的承诺
协调者做出了提交(或放弃)的决定
协调者发生故障
如果协调者在发送准备请求之前就已失败, 则参与者可以安全地中止交易.
如果协调者在参与者等待协调者决定时出现崩溃或网络故障, 则参与者只能等待, 此时参与者处在一种不确定的状态
三阶段提交
两阶段提交也被称为阻塞式原子提交协议, 因为2PC可能在等待协调者恢复时卡住, 理论上, 可以使其改进为非阻塞式从而避免这种情况
作为2PC的替代方案, 目前也有三阶段提交算法, 然而3PC假定一个有界的网络延迟和节点在规定时间内响应, 考虑到目前大多数具有无限网络延迟和进程暂停的实际情况, 它无法保证原子性
实践中的分布式事务
分布式事务, 尤其是那些通过两阶段提交所实现的事务, 声誉混杂, 一方面, 他们被看作是提供了一个其他方案难以企及的重要的安全保证, 另一方面, 他们由于操作上的缺陷, 性能问题, 承诺不可靠等问题而遭受诟病
exactly-once消息处理
异构的分布式事务旨在无缝集成多种不同的系统
xa交易
X/Open XA(eXtended Architecture, XA)是异构环境下实施两阶段提交的一个工业标准. XA不是网络协议, 而是一个与事务协调者进行通信的C API, 当前, 它也支持其他语言的API绑定
停顿时仍持有锁
陷入停顿的参与者节点(即不确定应该提交还是中止), 难道不能选择忽略并清理这些节点吗? 问题的关键在于锁, 数据库事务通常持有待修改行的行级独占锁, 用来防止脏写, 此外, 如果要使用可串行化的隔离, 则两阶段锁的数据库还会对事务曾经读取的行持有读-共享锁, 在事务提交(或中止)之前, 数据库都不会释放这些锁. 因此在两阶段提交时, 事务在整个停顿期间一直持有锁
从协调者故障中恢复
对于悬而未决的事务, 即使重启处于停顿状态的数据库节点也无法解决, 唯一的出路时让管理员手动决定究竟是提交还是回滚
许多XA的实现都支持某种紧急避险措施称之为启发式决策: 这样参与者节点可以在紧急情况下单方面做出决定, 放弃或者继续那些停顿的事务, 而不需要等到协调者发出指令. (这里的启发式其实是可能破坏原子性的委婉说法)
分布式事务的限制
XA事务解决了多个参与者之间如何达成一致这样一个非常现实而重要的问题, 但正如上面所看到的, 也引入了不少操作方面的限制, 特别是, 核心的事务协调者本身就是一种数据库(用于存储事务的投票结果), 因此需要和其他重要的数据库一样格外小心
支持容错的共识
通俗理解, 共识是让几个节点就某项提议达成一致; 共识问题通常形式化描述如下: 一个或多个节点可以提议某些值, 由共识算法来决定最终值
在这个描述中, 共识算法必须满足以下性质:
协商一致性(Uniform agreement)
所有的节点都接受相同的决议
诚实性(Integrity)
所有节点不能反悔, 即对一项提议不能由两次决定
合法性(Validity)
如果决定了值v, 则v一定是由某个节点所提议的
可终止性(Termination)
节点如果不崩溃则最终一定可以达成决议
共识算法与全序广播
全序关系广播相当于持续的多轮共识(每一轮共识的决定对应于一条消息):
由于协商一致性, 所有系欸但决定以相同的顺序发送相同的消息
由于诚实性, 消息不能重复
由于合法性, 消息不会被破坏, 也不是凭空捏造的
由于可终止性, 消息不会丢失
主从复制与共识
Epoch和Quorum
目前讨论的所有共识协议中都采用了一种弱化的保证: 协议定义了一个世代编号(epoch number), 对应于Paxos中的ballot number, raft中的term number, 并保证在每个世代里, 主节点是唯一确定的
共识的局限性
共识算法为一切不确定的系统带来了明确的安全属性(一致性, 完整性和有效性), 此外它还可以支持容错(只要大多数节点还在工作和服务可达). 共识可以提供全序关系广播, 以容错的方式实现线性化的原子操作
很多系统还是采用异步复制, 存在某些已提交数据在故障切换时丢失的风险
共识体系需要严格的多数节点才能运行
多数共识算法假定一组固定参与投票的节点集, 这意味着不饿能动态添加或删除节点
共识系统通常依靠超时机制来检测节点失效
共识算法往往对网络问题特别敏感
成员与协调服务
zookeeper
一些特性
线性化的原子操作
操作全序
故障检测
更改通知
适用场景
节点任务分配
服务发现
成员服务
小结
第三部分: 派生数据
记录系统与派生数据系统
存储与处理数据的系统按照高层次分类
记录系统
一个记录系统也被称为真实数据系统, 拥有数据的权威版本. 当新数据进入时, 首先被写入记录系统, 每个记录在系统中只表示一次(通常为规范化表示), 如果另一个系统与记录系统之间存在任何差异, 那么以记录系统中的数据值为准
派生数据系统
派生数据系统则时从另一个系统中获取已有数据并以某种方式进行转换或处理的结果
第10章: 批处理系统
前言
一个系统如果收到个人的应先给太大, 这个系统就可能成功, 一旦最初的设计完成并且足够健壮, 那么真正的测试就开始于许多持不同观点的人进行他们各自的实验
三种不同类型的系统
在线服务(或称在线系统)
服务等待客户请求或指令的到达, 当收到请求或指令时, 服务试图尽可能快地处理它, 并发回一个响应. 响应事件通常是服务性能的主要衡量指标, 而可用性同样非常重要
批处理系统(或称离线系统)
批处理系统接受大量的输入数据, 运行一个作业来处理数据, 并产生输出数据, 批处理作业的主要性能衡量标准通常是吞吐量(处理一定大小的数据集所需要的时间)
流处理系统(或称近实时系统)
流处理介于在线与离线之间
使用UNIX工具进行批处理
简单日志分析
命令链与自定义程序
排序与内存中聚合
UNIX设计哲学
管道类比
1. 每个程序做好一件事, 如果要做新的工作, 则建立一个全新的程序, 而不是通过增加新"特征"使旧程序变得更加复杂
2. 期待每个程序的输出称为另一个尚未确定的程序的输入, 不要将输出与无关信息混淆在一起, 避免使用严格的表格状或二进制输入格式, 不要使用交互式输入
3. 尽早尝试设计和构建软件, 甚至使操作系统, 最好在几周内完成, 需要扔掉那些笨拙的部分时不要由于, 并立即进行重建
4. 优先使用工具来减轻编程任务, 即使你不得不额外花费时间去构建工具, 并且预期在使用完成后将其中一些工具扔掉
统一接口
逻辑与布线分离
透明与测试
MapReduce与分布式文件系统
MapReduce作业执行
MapReduce中的数据处理模式
1. 读取一组输入文件, 并将其分解成记录
2. 调用mapper函数从每个输入记录中提取一个键值对
3. 按关键字将所有的键值对排序
4. 调用reducer函数遍历排序后的键值对
这四个步骤可以由一个MapReduce作业执行, 步骤2(map), 步骤4(reduce)是用户编写自定义数据处理的代码. 步骤1(将文件分解为记录)由输入格式解析器处理, 步骤3中的排序步骤sort隐含在MapReducing中, 无需用户编写, mapper的输出始终会在排序之后再传递给reducer
要创建Mapreduce作业, 需要实现两个回调函数. mapper和reducer
mapper
每个输入记录都会调用一次mapper程序, 其任务是从输入记录中提取关键字和值. 对于每个输入, 它可以生成任意数量的键值对(包括空记录). 他不会保留从要给输入记录到下一个记录的任何状态, 因此每个记录都是独立处理的
Reducer
MapReduce框架使用由mapper生成的键值对, 收集属于同一个关键字的所有值, 并使用迭代器调用reducer以使用该值的集合
MapReduce的分布式执行
MapReduce工作流
MapReduce的join与分组
排序-合并join
将相关数据放在一起
分组
处理数据倾斜
map端join操作
广播哈希join
分区哈希join
map端合并join
具有map端join的MapReduce工作流
批处理工作流的输出
生成搜索索引
生成搜索索引
批处理输出键值
批处理输出的哲学
对比Hadoop与分布式数据库
存储多样性
处理模型的多样性
针对频繁故障的设计
超越MapReduce
中间状态实体化
数据流引擎
为了解决MapReduce的这些问题, 开发了用于分布式批处理的新的执行引擎, 其中最著名的是Spark, Tez和Flink
由于通过若干个处理阶段明确地建模数据流, 所以这些系统被称为数据流引擎
容错
Spark使用弹性分布式数据集(Resilient Distributed Dataset, RDD) 抽象来追踪数据的祖先, 而Flink对运算符状态建立检查点, 从而允许将执行过程中遇到故障的运算符恢复执行
关于实体化的讨论
图与迭代处理
Pregel处理模型
容错
并行执行
高级API和语言
转向声明式查询语言
不同领域的专业化
第11章: 流处理系统
一个可用的复杂系统总是从可用的简单系统演进而来.
一般来说, "流"是指随着时间的推移而持续可用的数据
本章, 我们将把事件流视为一种数据管理机制: 一种无界的, 持续增量处理的方式, 对应于上章所介绍的批处理处理方式
发送事件流
消息系统
向消费者通知新事件的常见方法时使用消息系统: 生产者发送包含事件的消息, 然后该消息被推送给一个或多个消费者
如果生产者发送消息的速度比消费者所能处理的快, 会发生什么
系统丢弃消息
将消息缓存在队列中
激活背压, 也称流量控制(即阻止生产者发送更多的消息)
如果节点崩溃或者暂时离线, 是否有消息丢失
与数据库一样, 持久性可能需要写入磁盘和/或结合复制方案, 而这都是有成本的
生产者与消费者之间的直接消息传递
许多消息系统将生产者直接连接到消费者, 而不通过中间节点
但通常要求应用程序代码意识消息丢失的可能性
消息代理
一种广泛使用的替代方法是通过消息代理(也称消息队列)发送消息, 消息代理实质上是一种针对处理消息流而优化的数据库, 他作为服务器运行, 生产者和消费者作为客户端连接到它, 生产者将消息写入代理, 消费者通过从消息代理那里读取消息来接收消息
消息代理与数据库对比
消息代理和数据库之间存在重要的实际差异
数据库通常保留数据知道明确要求删除, 大多数消息代理在消息成功传递后就自动删除
多数消息系统会假定当前工作集相当小, 即队列很短
数据库通常支持二级索引和各种搜索数据的方式
查询数据库时, 结果通常基于数据的时间点快照
多个消费者
多个消费者读取同一个主题中的消息时, 有两种主要的消息传递模式
负载均衡模式
每一条消息都制备传递给其中一个消费者, 所以消费者可以共享主题中处理消息的工作
扇出式
每条消息都被传递给所有消费者
确认和重新传送
分区日志
基于日志的消息存储
日志是磁盘上一个仅支持追加式修改记录的序列
对比日志与传统消息系统
消费者偏移量
磁盘空间使用
日志实现了一个有限大小的缓冲区, 当缓冲区变满时, 旧的消息就丢失, 该缓冲区也被称为循环缓冲区或环形缓冲区, 由于该缓冲区在磁盘上, 因此它可以非常大
当消费者跟不上生产者
即使消费者确实落后太多, 并且开始丢失消息, 也只有该消费者收到影响; 它不会中断其他消费者的服务
重新处理信息
基于日志的消息代理中, 使用消息更像是从该文件读取, 只读操作, 不会更改日志
数据库与流
保持系统同步
变更数据捕获
(Change Data Capture, CDC)
实现变更数据捕获
存储在搜索索引和数据仓库中的数据知识记录系统中数据的另一个视图
变更数据捕获机制可以确保对记录系统所做的所有更改都反映在派生数据系统中, 以便派生系统具有数据的准确副本
从本质上将, 变更数据捕获使得一个数据库成为主节点(从中捕获变化的数据库), 并将其他变成从节点. 由于基于日志的消息代理保留了消息的排序, 因此它非常适合从源数据库传输更改事件
像消息代理一样, 变更数据捕获通常是异步的: 记录数据库系统不会在提交更改之前等待应用与消费者, 这种设计具有的操作上的优势是, 添加缓慢的消费者不会对记录系统造成太大影响, 但是他的缺点是所有复制滞后导致的问题在这里全部适用
初始快照
日志压缩
通过日志压缩来获取数据库内容的完整副本
对变更流的API支持
事件溯源
与变更数据捕获类似, 事件溯源涉及到将所有对应用程序状态的更改保存为更改事件的日志, 最大的区别在于事件溯源在不同的抽象层次上应用了这个想法
在变更数据捕获中, 应用程序以数据可变方式来操纵数据库. 从数据库中提取较低级别的变更日志, 从而确保从数据库提取的写入顺序与实际写入的顺序相匹配, 从而避免图11-4中的竞争条件. 写入数据库的应用程序不需要知道CDC正在发生
在事件溯源中, 应用程序逻辑是基于写入事件日志的不可变事件构建的. 在这种情况下, 事件存储仅支持追加, 不鼓励甚至禁止更新或删除操作, 事件旨在反映在应用程序级所发生的事情, 而不是低级别的状态更改
从事件日志导出当前状态
事件日志本身并不是很有用, 因为用户通常期望看到系统的当前状态, 而不是修改的历史记录
因此, 使用事件溯源的应用程序需要记录事件的日志(表示写入系统的数据), 并将其转换为适合用户显示的状态(从系统读取数据的方式), 这种转换可以使用任意的逻辑, 但它应该是确定性的, 以便可以再次运行它并从事件日志中派生相同的应用程序状态
replay事件日志能够重建系统的当前状态, 但是日志压缩需要以不同的方式处理
使用事件溯源在更高的层次上对事件建模: 事件通常用来表达用户行为的意图, 而不是一种对行为结果进行相应状态更新的机制
使用事件溯源的应用程序通常有一些机制来保存导出的当前状态的快照, 因此它们不需要重复处理全部的日志
命令和事件
事件溯源的哲学是小心区分事件和命令
命令是意图, 事件是事实
不允许事件流的消费者拒绝事件
状态, 流与不可变性
批处理受益于其输入文件的不变性, 所以可以在现有的输入文件上运行实验处理作业, 而不用担心损坏它们. 这种不变性原则也是使得事件溯源和变更数据捕获如此强大的原因
我们通常将数据库看成是用来存储应用程序当前状态的, 这种表示法针对读取进行了优化, 并且通常对于查询服务来说是最方便的. 状态的本质是他会发生变化, 所以数据库支持更新, 删除以及插入数据.
每当状态改变, 该状态就反应了随事件推移而变化的事件的结果.
无论状态如何变化, 总会有一系列事件导致这些变化. 不管事件已经结束或者尚在进行中, 事件发生是不争的事实. 关键的思路是可变状态和不变事件的追加日志不相互矛盾: 他们是同一枚硬币的两面. 所有变化的日志, 更新日志, 代表了随时间的推移状态的演变
事务日志记录了对数据库所做的所有更改. 高速追加是更改日志的唯一方法. 从这个角度来看, 数据库的内容保存了日志中最新记录值的缓存. 日志是事实. 数据库是日志子集的缓存. 该缓存子集恰好是来自日志的每个记录和索引值的最新值
不变事件的优势
金融审计
不可变事件可以携带更多信息
相同的事件日志派生多个视图
并发控制
事件捕获和变更数据捕获的最大缺点是事件日志的消费者通常是异步的, 所以用户可能会写入日志, 然后从日志派生的视图中读取, 却发现这些写操作还没有反映在读取视图中
一种解决方案是同步执行读取视图的更新, 并将事件追加到日志中
不变性的限制
在多大程度上, 永远保存所有变化的历史记录是可行的? 取决于数据集的变化情况
流处理
有了流以后, 可以用来做什么
1. 可以将事件中的数据写入数据库, 缓存, 搜索索引或者类似的存储系统, 然后被其他客户端查询
2. 可以通过某种方式将事件推送给用户, 例如发送电子邮件警报或推送通知
3. 可以处理一个或多个输入流以产生一个或多个输出流
流处理的适用场景
流处理长期以来一直被用于监控的目的, 即希望在发生某些特定事件时收到警报
复杂事件处理(Complex Event Processing, CEP)
CEP系统通常使用像SQL这样的高级声明式语言或图形用户界面, 来描述应该检测到的事件模式. 这些查询提交给一个处理引擎, 该引擎使用输入流并在内部维护匹配所需的状态机. 当发现匹配时, 引擎产生一个复杂的事件, 这个事件包括检测到的事件模式的细节信息
流分析
使用流的另一个领域是对流进行分析
维护物化视图
在流上搜索
CEP通常搜索包含多个事件的特定模式, 除了CEP, 有时还需要基于一些复杂条件(例如全文搜索查询)来搜索单个事件
消息传递和RPC
流的时间问题
事件时间与处理时间
了解什么时候准备就绪
如果基于事件发生事件而定义窗口, 面临一个棘手的问题是, 无法确定什么时候能收到特定窗口内的所有事件, 或者是否还有一些事件尚未到来
例如, 将时间分组成一分钟的窗口, 以便可以统计每分钟的请求数, 已经计算了一些事件, 这些事件的时间戳在一小时的第37分钟, 时间继续向前移动, 现在大部分事件都到了第38分钟和第39分钟, 什么时候可以宣布完成了第37分钟窗口的处理, 输出计数值呢
可能因为网络中断而延迟, 进而出现滞后事件, 处理方法
忽略滞后事件
针对滞后事件发布更新值
用谁的时钟
为了调整不正确的设备时钟, 一种方法是记录三个时间戳
根据设备的时钟, 记录事件发生的时间t1
根据设备的时钟, 记录将事件发送到服务器的时间t2
根据服务器时钟, 记录服务器收到事件的时间t3
t3-t2, 来估算偏移量, 再根据t1估算事件发生的真实时间
窗口类型
一旦明确了如何确定事件的时间戳, 下一步就是决定如何定义时间段即窗口了, 然后窗口就可以用于聚合分析
窗口类型
轮转窗口
轮转窗口的长度是固定的, 每个事件都属于一个窗口
10:03:00-10:03:59. 10:04:00-10:04:59
跳跃窗口
跳跃窗口也具有固定长度, 但允许窗口重叠以提供一些平滑过渡
10:03:00-10:07:59. 10:04:00-10:08:59
滑动窗口
滑动窗口包含在彼此的某个间隔内发生的所有事件, 滑动窗口可以通过保留按时间排序的事件缓冲区并且在从窗口过期时移除旧事件来实现
会话窗口
没有固定的持续时间, 通过将同一用户在时间上紧密相关的所有事件分组在一起而定义的, 一旦用户在一段时间内处于非活动状态, 则窗口结束
流式join
流和流join(窗口join)
流和表join
流和表join实际上非常类似流和流join, 他们最大的区别在于, 对于表的更新日志流, join使用一个可以回溯到"开始时间"(一个在概念上是无限的窗口)的窗口, 而新版本的记录会覆盖旧的记录, 对于流输入, join可能根本无法维护这样一个窗口
表和表join(物化视图维护)
join的时间依赖性
上述三种流式join都需要流处理系统根据一个join输入来维护某些状态, 并在来自另一个join输入的消息上查询该状态, 维持这个状态的事件的顺序非常重要
流处理的容错
在使输出结果可见之前等待某个任务完成是不可行的, 由于流是无限的, 因此几乎永远无法完成这个任务
为批处理和校验点
一种处理方案是将流分解成多个小块, 并像小型批处理一样处理每个块, 这种方法被称为微批处理
Apache Flink使用了该方法的一个变体, 它定期生成状态滚动检查点并将其写入持久化存储, 如果流操作发生崩溃, 它可以从最近的检查点重新启动, 并丢弃在上一个检查点和崩溃之间生成的所有输出. 检查点类似于微批处理之间的边界, 但不强制特定的窗口大小
重新审视原子提交
幂等性
我们的目标是丢弃任何失败任务的部分输出, 以便它们可以安全地重试而不会发生两次生效. 分布式事务是实现这一目标的一种方式, 而另一种方式则是依赖幂等性
幂等操作是可以多次执行的操作, 并且它与只执行一次操作具有相同的效果
故障后重建状态
任何需要状态的流处理, 比如基于窗口的聚合(诸如计数器, 平均值和直方图)以及表和索引的join操作, 都必须确保在故障发生后状态可以恢复
一种选择是将状态保存在远程存储中并采取复制, 然而为每个消息去查询远程数据库可能会很慢, 另一种方法是将状态保存在本地, 并定期进行复制, 之后, 当流处理器从故障中恢复时, 新任务可以读取副本的状态并且在不丢失数据的情况下恢复处理
小结
第12章: 数据系统的未来
如果船长的最高目标是保住他的船, 那么他只能永远待在港口
数据集成
采用派生数据来组合工具
为何需要数据流
派生数据与分布式事务
全序的局限
排序事件以捕获因果关系
批处理和流处理集成
保持派生状态
为应用程序演化而重新处理数据
模式迁移
Lambda架构
lambda体系结构的核心思想是进来的数据以不可变事件形式追加写到不断增长的数据集， 类似于事件源
统一批处理和流处理
分拆数据库
从最抽象的层面上理解, 数据库, hadoop和操作系统都提供了相同的功能: 它们保存某些数据, 并支持处理和查询数据.
编排多种数据存储技术
创建一个索引
数据库必须扫描表的一致性快照, 挑选出所有被索引的字段值, 对他们进行排序, 然后得到索引, 接下来必须处理从一致性快照创建以来所累计的写入操作(假设表在创建索引时未被锁定, 所以写操作可能会继续), 完成后, 只要有事务写入表中, 数据库就必须持续保持索引处于最新状态
这个过程和配置新的从节点副本非常相似, 也非常类似于流处理系统中的初始变更数据捕获
元数据库
分离式如何工作
分离式与集成式系统
遗漏了什么
围绕数据流设计应用系统
应用程序代码作为派生函数
应用程序代码与状态分离
数据流: 状态变化和应用程序代码之间的相互影响
流式处理与服务
观察派生状态
实体化视图和缓存
有状态, 可离线的客户端
状态更改推送至客户端
端到端的事件流
订阅更改
读也是事件
多分区数据处理
端到端的正确性
数据库的端到端争论
Exactly-once执行操作
重复消除
操作标识符
端到端的争论
在数据系统中采用端到端的思路
强制约束
唯一性约束需要达成共识
采用分区方案可以提高唯一性检查的扩展性, 即基于要求唯一性的字段进行分区, 但是, 他无法支持异步的多主节点复制
基于日志的消息传递唯一性
多分区请求处理
时效性和完整性
数据流系统的正确性
宽松的约束
无需协调的数据系统
信任, 但要确认
软件缺陷时的完整性
不要盲目相信承诺
验证的文化
在NoSQL下, 弱一致性称为新常态; 底层存储技术并非那么成熟可靠但却普遍使用, 然而数据审计机制尚未形成
可审计性的设计
端到端论点的再讨论
审计数据系统的工具
做正确的事
预测性分析
偏见与歧视
责任与问责
盲目相信数据至高无上不仅是误解的, 而且是非常危险的
反馈环路
数据隐私与追踪
监控
赞成与选择的自由
数据隐私和使用
数据作为资产和权力
记住工业革命
立法与自律
小结
我们有责任为我们赖以生存的世界而努力: 一个以人性和尊重来对待人的世界.
第一部分: 数据系统基础
第一章: 可靠, 可扩展与可维护的应用系统
认识数据系统
影响数据系统设计的因素有很多, 这里专注与对于大多数软件系统都极为重要的三个
可靠性(Reliability)
可扩展性(Scalability)
可维护性(Maintainability)
可靠性
即使发生了某些故障, 系统仍可以继续正常工作
硬件故障
软件错误
人为失误
假定人是不可靠的, 该如何保证系统的可靠性
以最小出错的方式来设计系统
想办法分离最容易出错的地方, 容易引发故障的接口
充分的测试: 从各单元测试到全系统集成测试以及手动测试
当出现认为事务时, 提供快速的恢复机制以尽量减少故障影响
如滚动发布新代码, 提供校验数据的工具
设置详细而清晰的监控子系统, 包括性能指标和错误率
其他行业称为遥测(Telemetry)
推行管理流程并加以培训
可靠性的重要性
可扩展性
可扩展性是用来描述系统应对负载增加能力的术语
描述负载
负载可以用称为负载参数的若干数字来描述, 参数的最佳选择取决于系统的体系结构
描述性能
吞吐量(throughput)
每秒可处理的记录条数, 或者在某指定数据集上运行作业所需的总时间
响应时间(response time)
客户端从发送请求到接收响应之间的间隔
延迟(latency): 请求花费在处理上的时间
经常考察的是服务请求的平均响应时间, 中位数指标, 百分位数(95%, 99%, 99.9%)
采用较高的响应时间百分位数(tail latencies, 尾部延迟或长尾效应)很重要, 因为它们直接影响用户的总体服务体验
排队延迟往往在高百分数响应时间中影响很大, 由于服务器并行处理的请求有限(例如, CPU内核数的限制), 正在处理的少数请求可能会阻挡后续请求, 这中情况有时被称为队头阻塞
应对负载增加的方法
长尾效应
即使只有很小百分比的请求缓慢, 如果某用户总是频繁产生这种调用, 最终总体变慢的概率就会增加(长尾效应在响应时间概念上的描述)
可维护性
软件系统设计的三个原则
可运维性
方便运营团队来保持系统平稳运行
简单性
简化系统复杂性, 使新工程师能够轻松理解系统
可演化性
后续工程师能够轻松地对系统进行改进, 并根据需求变化将其适配到非典型场景, 也成为可延申性, 易修改性或可塑性
可运维性: 运维更轻松
优秀的运营团队通常至少负责以下内容
监视系统的健康状况, 并在服务出现异常状态时快速恢复服务
追踪问题的原因, 例如系统故障或性能下降
保持软件和平台至最新状态, 例如安全补丁方面
了解不同系统如何相互影响, 避免执行带有破坏性的操作
预测未来可能的问题, 并在问题发生之前及时解决(例如容量规划)
建立用于部署, 配置管理等良好的实践规范和工具包
执行复杂的维护任务, 例如将应用程序从一个平台迁移到另一个平台
当配置更改时, 维护系统的安全稳健
指定流程来规范操作行为, 并保持生产环境稳定
保持相关知识的传承(如对系统的理解)
简单性: 简化复杂度
简化系统该设计主要意味这消除意外方面的复杂性
消除意外复杂性的最好手段之一是抽象
可演化性: 易于改变
小结
第二章: 数据模型与查询语言
关系模型和文档模型
现在最著名的数据模型可能是SQL, 它基于一种关系模型: 数据被组织成关系(relations), 在SQL中称为表(table), 其中每个关系都是元组(tuples)的无序集合(在SQL中称为行)
NoSQL的诞生
采用NoSQL数据库有这样几个驱动因素
比关系数据库更好的扩展性需求, 包括支持超大数据集或超高写入吞吐量
普遍偏爱免费和开源软件而不是商业数据库产品
关系模型不能很好地支持一些特定地查询操作
对关系模式一些限制性感到沮丧, 渴望更具动态和表达力的数据模型
对象-关系不匹配
现在大多数应用开发都次啊用面向对象的编程语言, 由于兼容性问题, 普遍对SQL数据模型存在抱怨: 如果数据存储在关系表中, 那么应用层代码中的对象与表, 行和列的数据库模型之间需要一个笨拙的转换层. 模型之间的脱离有时被称为阻抗失谐
多对一与多对多的关系
文档数据库是否在重演历史
网络模型
也被称为CODASYL模型, 是层次模型的推广, 在层次模型的树结构中, 每个记录只有一个父结点, 而在网络模型中, 一个记录可能有多个父结点
在网络模型中, 记录之间的连接不是外键, 而更像编程语言中的指针, 访问记录的唯一方法是选择一条始于根记录的路径, 并沿着相关链接依次访问, 这条链接链条也因此被称为访问路径
关系模型
相比之下, 关系模型所做的则是定义了所有数据的格式: 关系(表)只是元组(行)的集合. 仅此而已
文档数据库的比较
关系数据库与文档数据库现状
哪种数据模型的应用代码更简单
主要取决于数据项之间的关系类型
文档模型中的模式灵活性
大多数文档数据库, 以及关系数据库中的JSON支持, 都不会对文档中的数据强制执行任何模式
读时模式(数据的结构是隐式的, 只有在读取时才解释)
写时模式(关系数据库的一种传统方法, 模式是显式的, 并且数据库确保数据写入时都必须遵循)
查询的数据局部性
局部性优势仅适用需要同时访问文档大部分内容的场景
文档数据库与关系数据库的融合
数据查询语言
SQL是一种声明式的查询语言
命令式语言告诉计算机以特定顺序执行某些操作, 而对于声明式查询语言(如sql或关系代数), 则只需指定所需的数据模式, 结果需满足什么条件, 以及如何转换数据(例如, 排序, 分组和聚合), 而不需指明如何实现这一目标
声明式语言通常适合于并行执行
Web上的声明式查询
MapReduce查询
MapReduce是一种编程模型, 用于在许多机器上批量处理海量数据
(NoSQL系统可能会发现自己意外地重新发明了SQL, 尽管是伪装的)
图状数据模型
多对多关系是不同数据模型之间的重要区别特征
数据大多是一对多关系(树结构数据)或者记录之间没有关系, 那么文档模型是最适合的
如果多对多关系在数据中很常见, 关系模型能够处理简单的多对多关系
随着数据之间的关联越来越复杂, 将数据建模转化为图模型会更加自然
图由两种对象组成: 顶点(也成为结点或实体)和边(也称为关系或弧)
属性图
属性图模型
顶点
唯一的标识符
出边的集合
入边的集合
属性的集合(键-值对)
边
唯一的标识符
边开始的顶点(尾部顶点)
边结束的顶点(头部顶点)
描述两个顶点间关系类型的标签
属性的集合(键-值对)
图模型的注意点
任何顶点都可以连接到其他任何顶点, 没有模式限制哪种事物可以或不可以关联
给定某个顶点, 可以高效地得到它的所有入边和出边, 从而遍历图
通过对不同类型的关系使用不同的标签, 可以在单个图中存储多种不同类型的信息, 同时仍然保持整洁的数据模型
图有利于演化: 向应用程序添加功能时, 图可以容易地扩展以适应数据结构的不断变化
Cypher查询语言
Cypher是一种用于属性图的声明式查询语言, 最早为Neo4j图形数据库而创建
SQL中的图查询
可以做, 但相比起来显得很笨拙
三元存储与SPARQL
三元存储模式几乎等同于属性图模式, 只是使用不同的名词描述了相同的思想
在三元存储中, 所有信息都以非常简单的三部分形式存储(主体, 谓语, 客体)
三元组的主体相当于图中的顶点, 而客体是以下两种
1. 原始数据类型中的值, 如字符串或数字. 这种情况下, 三元组的谓语和客体分别相当于主体(顶点)属性中的键和值. 例, (lucy, age, 33)
2. 图中的另一个顶点. 此时谓语是图中的边, 主体是尾部顶点, 而客体是头部顶点, 例(lucy, marriedTo, alain)
语义网
语义网从本质上讲源于一个简单而合理的想法: 网站通常将信息以文字和图片方式发布给人类阅读, 那为什么不把信息发布为机器可读的格式给计算机阅读呢, 资源描述框架(Resource Description Framework, RDF)就是这样一种机制
RDF数据模型
SPARQL查询语言
SPARQLS是一种采用RDF数据模型地三元存储查询语言
Datalog基础
小结
第三章: 数据存储与检索
数据库核心: 数据结构
哈希索引
重要问题
文件格式
删除记录
崩溃恢复
部分写入的记录
并发控制
追加式的设计
优点
追加和分段合并主要是顺序写, 通常比随机写入快得多, 特别是在旋转式磁盘上
如果段文件是追加的或不可变的, 则并发和崩溃恢复要简单得多
合并旧段可以避免随着时间的推移数据文件出现碎片化的问题
哈希表索引的局限性
哈希表必须全部放入内存, 所以如果有大量的键, 就没那么幸运了, 在磁盘上维护hash map表现不好(需要大量随机I/O, 哈希变满时, 继续增长代价昂贵, 哈希冲突时需要复杂的处理逻辑
区间查询的效率不高
SSTables和LSM-Tree
SSTable
要求key-value对的顺序按键排序, 这种格式称为排序字符串表, 或简称为SSTable, 它要求每个键在每个合并的段文件中只能出现一次(压缩过程已经确保了)
相比与哈希索引的日志段的优点
合并段更加简单高效, 即使文件大于可用内存
在文件中查找特定的键时, 不再需要再内存中保存所有键的索引
由于读请求往往需要扫描请求范围内的多个key-value对, 可以考虑将这些记录保存到一个块中并在写磁盘之前将其压缩, 然后稀疏内存索引的每个条目指向压缩块的开头, 除了节省磁盘空间, 压缩还减少了I/O带宽的占用
构建和维护SSTables
需要将数据按键排序, 在磁盘上维护排序结构时可行的, 不过, 将其保存在内存中更容易
存储引擎的基本工作流程如下
当写入时, 将其添加到内存中的平衡树数据结构中(例如红黑树),这个内存中的树有时被称为内存表
当内存表大于某个阈值(通常为几兆字节)时, 将其作为SSTable文件写入磁盘
为了处理读请求, 首先尝试在内存表中查找键, 然后是最新的磁盘段文件, 接下来是次新的磁盘段文件, 以此类推, 直到找到目标(或为空)
后台进程周期性地执行段合并与压缩过程, 以合并多个段文件, 并丢弃那些已被覆盖或删除的值
上述方案可以很好的工作, 但是还存在一个问题, 如果数据库崩溃, 最近的写入(在内存表中但尚未写入磁盘)将会丢失, 为了避免该问题, 可以在磁盘上保留单独的日志, 每个写入都会立即追加到该日志, 这个日志文件不需要按键排序, 这并不重要, 因为它的唯一目的是在崩溃后恢复内存表, 每当将内存表写入SSTable时, 相应的日志可以被丢弃
从SSTable到LSM-Tree
性能优化
存储引擎通常使用额外的布隆过滤器(布隆过滤器是内存高效的数据结构, 用于近似的计算集合的内容, 如果数据库中不存在某个键, 它能够很快告诉你结果, 从而节省了很多对于不存在的键的不必要的磁盘读取)
不同的策略会影响甚至决定SSTables压缩和合并时的具体顺序和实际, 最常见的方式是大小分级和分层压缩
大小分级
在大小分级的压缩中, 较新的和较小的SSTables被连续合并到较旧和较大的SSTables
分层压缩
在分层压缩中, 键的范围分裂成多个更小的SSRTables, 旧数据被移动到单独的"层级", 这样压缩可以逐步进行并节省磁盘空间
B-trees
像SSTable一样, B-Tree保留按键排序的key-value对, 这样可以实现高效的key-value查找和区间查询
B-tree将数据库分解为固定大小的块或页, 传统上大小为4kb, 页是内部读/写的最小单元, 这种设计更接近底层硬件, 因为磁盘也是以固定大小的块排列
每个页面都可以使用地址或位置进行标识, 这样可以让一个页面引用另一个页面, 类似指针, 不过是指向磁盘地址, 而不是内存, 可以使用这些页面引用来构造一个树状页面
b-tree中一个页所包含的子页引用数量称为分支因子, 在实际中, 分支因素取决于存储页面引用和范围边界所需的空间总量, 通常为几百个
如果要更新B-tree中现有键的值, 首先搜索包含该键的叶子页, 更改该页的值, 并将页写回到磁盘(对该页的任何引用仍然有效)
如果要添加新键, 则需要找到其范围包含新键的页, 并将其添加到该页, 如果页中没有足够的可用空间来容纳新键, 则将其分裂为两个半满的页, 并且父页也需要更新以包含分裂之后的新的键范围
使B-tree可靠
B-tree底层的基本写操作是使用新数据覆盖磁盘上的旧页, 它假设不会改变页的磁盘存储位置, 也就是说, 当页被覆盖时, 对该页的所有引用保持不变
为了能使数据库能从崩溃中恢复, 常见的B-tree的实现需要支持磁盘上的额外的数据结构: 预写日志(write-ahead log, WAL), 也成为重做日志, 这是一个仅支持追加修改的文件, 每个B-tree的修改必须先更新WAL然后再修改树本身的页, 当数据库再崩溃后需要恢复时, 该日志用于将B-tree恢复到最近一致的状态
原地更新页的另一个复杂因素是, 如果多个线程要同时访问B-tree, 则需要注意并发控制, 否则线程可能会看到树处于不一致的状态
优化B-tree
一些数据库(如LMDB)不使用覆盖页和维护WAL来进行崩溃恢复, 而是使用写时复制方案, 修改的页被写入不同的位置, 树中父页的新版本被创建, 并指向新的位置, 这种方法对于并发控制页很有帮助
保存键的缩略信息, 而不是完整的键, 这样可以节省页空间
一般来说, 页可以放在磁盘上的任何位置; 没有要求相邻的页需要放在磁盘的相邻位置. 许多B-tree的实现尝试对树进行布局, 以便相邻叶子页可以按顺序保存再磁盘上
添加额外的指针到树中
B-tree的变体, 如分形树
对比B-tree和LSM-tree
根据经验, LSM_tree通常对于写入更快, 而B-tree被认为对于读取更快
LSM-tree的优点
B-tree索引必须至少写两次数据: 一次写入预写日志, 一次写入树的页本身(还可能发生页分裂), 即使该页中只有几个字节更改, 也必须承受写整个页的开销, 一些存储引擎甚至覆盖相同的页两次, 以避免在电源故障的情况下最终出现部分更新的页
由于反复压缩和SSTable的合并, 日志结构索引也会重写数据多次, 这种影响(在数据库内, 由于一次数据库写入请求导致的多次磁盘写)称为写放大, 对于大量写密集的应用程序, 性能瓶颈很可能在于数据库写入磁盘的速率, 在这种情况下, 写放大具有直接的性能成本: 存储引擎写入磁盘的次数越多, 可用磁盘带宽中每秒可以处理的写入越少
通常LSM-tree能够承受比B-tree更高的写入吞吐量, 部分是因为它们有时具有较低的写放大(尽管这取决于存储引擎的配置和工作负载), 部分原因是它们以顺序方式写入紧凑的SSTable文件, 而不必重写书中的多个页, 这种差异对于磁盘驱动器尤为重要, 原因是磁盘的顺序写比随机写要快得多
LSM-tree可以支持更好地压缩, 碎片少, 有较低地存储开销, 特别是使用分层压缩时
LSM-tree的缺点
压缩过程有时会干扰正在进行的读写操作
高写入吞吐量时, 压缩的另一个问题就会冒出来: 磁盘的有限写入带宽需要在初始写入(记录并刷新内存表到磁盘)和后台运行的压缩线程之间所共享
其他索引结构
在索引中存储值
索引中的键是查询搜索的对象, 而值则可以是以下两类之一: 它可能是上述的实际行(文档, 顶点), 也可以是对其他地方存储的行的引用. 在后一种情况下, 存储行的具体位置被称为堆文件, 并且它不以特定的顺序存储数据(它可以是追加的, 或者记录删掉的行以便用新数据在之后覆盖它们)
堆文件方法比较常见, 这样当存在多个二级索引时, 它可以避免复制数据, 即每个索引只引用堆文件中的位置信息, 实际数据仍保存在一个位置
在某些情况下, 从索引到堆文件的额外跳转对于读取来说意味着太多的性能损失, 因此可能希望将索引行直接存储在索引中, 这被称为聚集索引
聚集索引(在索引中直接保存行数据)和非聚集索引(仅存储索引中的数据的引用)之间有一种折中设计被称为覆盖索引或包含列的索引, 它在索引中保存一些表的列值, 它可以支持只通过索引即可回答某些简单查询(在这种情况下, 称索引覆盖了查询)
与任何类型的数据冗余一样, 聚集和覆盖索引可以加快读取速度, 但是它们需要额外的存储, 并且会增加写入的开销, 此外数据库还需要更多的工作来保证事务性
多列索引
最常见的多列索引称为级联索引, 它通过将一列追加到另一列, 讲几个字段简单地组合成一个键(索引的定义指定字段连接的顺序)
多维索引时更普遍的一次查询多列的方法, 这对地理空间数据尤为重要
标准B-tree或LSM-tree索引无法高效地应对这种查询
一种选择是使用空格填充曲线将二维位置转换为单个数字, 然后使用常规的B-tree索引, 更常见的是使用专门的空间索引, 如R树
全文搜索和模糊索引
在内存中保存所有内容
内存数据库可以更快, 是因为它们避免使用写磁盘的格式对内存数据结构编码的开销
除性能外, 内存数据库的另外一个有意思的地方是, 它提供了基于磁盘索引难以实现的某些数据模型
事务处理与分析处理
在线事务处理(online transaction processing , OLTP)
在线分析处理(online analytic processing, OLAP)
数据仓库
数据仓库是单独的数据库, 分析人员可以在不影响OLTP操作的情况下尽情地使用
使用单独的数据仓库而不是直接查询OLTP系统进行分析, 很大的有时在于数据仓库可以针对分析访问模式进行优化
OLTP数据库和数据仓库之间的差异
数据仓库的数据模型最常见的是关系型, 因为SQL通常适合分析查询
星型与雪花型分析模式
许多数据仓库都相当公式化地使用了星型模式, 也称为维度建模
模式的中心是一个所谓的事实表, 事实表的每一行表示在特定时间发生的事件
名称"星型模式"来源于当表关系可视化时, 事实表位于中间, 被一系列维度表包围; 这些表的连接就像星星的光芒, 该模式的一个变体称为雪花模式, 其中维度进一步细分为子空间
列式存储
列压缩
在数据仓库中特别有效的一种技术是位图编码
内存带宽和矢量化处理
列存储中的排序
在列存储中, 行的存储顺序不太重要, 但页需要一次排序整行
排序的优点是可以帮助进一步压缩列
几种不同的排序
列存储的写操作
LSM-tree
聚合:数据立方体与物化视图
物化视图是查询结果的实际副本, 并被写到磁盘
物化视图常见的一种特殊情况称为数据立方体或OLAP立方体, 它是由不同维度分组的聚合网格
物化数据立方体的优点是某些查询会非常快, 缺点是数据立方体缺乏像查询原始数据那样的灵活性
小结
第四章: 数据编码与演化
代码更迭
对于服务端程序, 可能需要滚动升级(也被称为分阶段发布)
新旧代码可能同时在系统内共存, 所以为了是系统继续顺利运行, 需要保持双向的兼容性
向后兼容
新读旧
向前兼容
旧读新
数据编码格式
程序通常使用(至少) 两种不同的数据表示形式
在内存中, 数据保存在对象, 结构体, 列表, 数组, 哈希表和树等结构中, 这些数据结构针对CPU的高效访问和操作进行了优化(通常使用指针)
将数据写入文件或通过网络发送时, 必须将其编码为某种自包含的字节序列(例如JSON文档)
因此, 在这两种表示之间需要进行类型的转化, 从内存中的表示到字节序列的转化称为编码(或序列化等), 相反的过程称为解码(或解析, 反序列化)
语言的特定格式
JSON, XML与二进制变体
除了表面的语法问题外, 存在一些微妙的问题
数字编码由很多模糊之处, xml和csv无法区分数字和数字组成的字符串, json区分字符串和数字, 但不区分整数和浮点数, 并且不指定精度
json和xml对Unicode字符串(即人类可读文本)有很好的支持, 但是它们不支持二进制字符串(没有字符编码的字节序列)
xml和json都有可选的模式支持
csv没有任何模式, 因此应用程序需要定义每行和每列的含义
二进制编码
Thrift与Protocol Buffers
Apache Thrift和Protocol Buffers时基于相同原理的两种二进制编码库
字段标签和模式演化
数据类型和模式演化
Avro
Avro使用模式来指定编码的数据结构, 有两种模式语言: 一种(Avro IDL)用于人工编辑, 另一种(基于JSON)更易于机器读取
写模式与读模式
当应用程序想要对某些数据进行编码时, 它使用所知道的模式的任何版本来编码数据, 例如, 可以编译到应用程序中的模式, 这被称为写模式
当应用程序想要解码某些数据时, 它期望数据符合某个模式, 即读模式
关键思想时写模式和读模式不必是完全一模一样, 它们只需保持兼容
模式演化规则
write模式是什么
动态生成的模式
代码生成和动态类型的语言
模式的优点
基于模式的二进制编码的优点
它们可以比各种"二进制JSON"变体更紧凑, 可以省略编码数据中的字段名称
模式是一种有价值的文档形式, 因为模式是解码所必须的, 所以可以确定它是最新的
模式数据库允许在部署任何内容前检查模式更改的向前和向后兼容性
对于静态类型变成语言的用户来说, 从模式生成代码的能力是有用的, 它能够在编译时进行类型检查
总之, 通过演化支持与无模式/读时模式的JSON数据库相同的灵活性, 同时还提供了有关数据和工具方面更好的保障
数据流格式
基于数据库的数据流
额外的障碍: 假设在记录模式中添加了一个字段, 并且较新的代码将该字段的值写入数据库, 随后, 旧版本的代码(尚不知道该新字段)将读取, 更新记录并将其写回, 在这种情况下, 理想的行为通常是旧代码保持新字段不变, 即使它无法解释
不同时间写入不同的值
数据比代码更长久
旧版本应用程序更新新版本程序所写入的数据时, 需要小心, 可能丢失数据
模式演化支持整个数据库看起来像是采用单个模式编码, 即使底层存储可能包含各个版本模式所编码的记录
归档存储
基于服务的数据流: REST和RPC
对于需要通过网络进行通信的进程, 有多种不同的通信方式
最常见的是有两个角色: 客户端和服务器.
服务器通过网络公开API, 客户端可以连接到服务器以向该API发出请求, 服务器公开的API称为服务
Web的工作方式是: 客户端(Web浏览器)向Web服务器发出请求, 发出GET请求来下载HTML, CSS, Javascript, 图像等, 发出post请求提交数据到服务器, API包含一组标准的协议和数据格式(HTTP, URL, SSL/TLS, HTML等)
服务器本身可以是另一项服务的客户端, 克重方法通常用于将大型应用程序按照功能区域分解为较小的服务, 这样当一个服务需要另一个服务的某些功能或数据时, 就会向另一个服务发出请求, 这种构建应用程序的方式传统上被称为面向服务的体系结构(service-oriented architecture, SOA), 最近更名为为服务体系结构(microservices architecture)
面向服务/微服务体系结构的一个关键设计目标是, 通过式服务可独立部署和演化, 让应用程序更易于更改和维护
网络服务
当HTTP被用作于服务通信的底层协议时, 它被称为Web服务, 但Web服务不仅在Web上使用, 而且在几个不同的上下文中使用
1, 运行在用户设备上的客户端应用程序, 通过HTTP向服务发出请求, 这些请求通常通过公共互联网进行
2. 一种服务向同一组织拥有的另一项服务提出请求, 这些服务通常位于同一数据中心内, 作为面向服务/微型架构的一部分, 支持着这种用例的软件有时被称为中间件
3. 一种服务向不同组织所拥有的服务提出请求, 经常需通过互联网, 这用于不同组织后端系统之间的数据交换, 此类别包括由在线服务(如信用卡处理系统)提供的公共API, 或用于共享访问用户数据的OAuth
两种流行的Web服务方法: REST和SOAP
REST不是一种协议, 而是一个基于HTTP原则的设计理念, 它强调简单的数据格式, 使用URL来标识资源, 并使用HTTP功能进行缓存控制, 身份验证和内容类型协商, 与SOAP相比, REST已经越来越受欢迎, 至少在跨组织服务集成的背景下, 并经常与微服务相关联, 根据REST原则设计的API称为RESTful
SOAP是一种基于XML的协议, 用于发出网络API请求, 虽然它最常用于HTTP, 但其目的时独立于HTTP, 并避免使用大多数HTTP功能, SOAPWeb服务的API使用被称为WSDL(Web Services Description Language, 一种基于XML的语言)来描述
远程过程调用(RPC)的问题
RPC模型试图使向远程网络服务发出请求看起来于在统一进程中调用变成语言中的函数或方法相同(这种抽象称为位置透明), 虽然RPC起初看起来很方便, 但这种方法在根本上时有缺陷的, 网络请求与本地函数调用非常不同:
本地函数调用是可预测的, 并且成功或失败仅取决于控制的参数, 网络请求是不可预测的: 请求或响应可能由于网络问题而丢失, 或者远程计算机可能速度慢或不可用, 这些问题完全不在控制范围之内, 网络问题很常见, 因此必须有所准备
本地函数调用要么返回一个结果, 要么抛出一个异常, 或者永远不会返回(因为进入无限循环或进程崩溃), 网络请求有另一个可能的结果: 由于超时, 他返回时没有结果
如果重试失败的网络请求, 可能会发生请求实际上已经完成, 只是响应丢失的情况
每次调用本地函数时, 通常需要大致相同的时间来执行
调用本地函数时, 可以高效地引用(指针)传递给本地内存中的对象
客户端和服务可以用不用的编程语言来实现, 所以RPC矿建必须将数据类型从一种语言换成另一种语言
RPC的发展方向
REST似乎是公共API的主流风格, RPC框架主要侧重于统一组织内多项服务之间的请求, 通常发生在同一数据中心内
RPC的数据编码和演化
对于演化性, 重要的是可以独立地更改和部署RPC客户端和服务器
基于消息传递的数据流
RPC和数据库之间的异步消息传递系统, 他们与RPC的相似之处在于, 客户端的请求以低延迟传递到另一个进程; 他们与数据库的相似之处在于, 不是通过直接的网络连接发送消息, 而是通过称为消息代理(也称为消息队列, 或面向消息的中间件)的中介发送的, 该中介会暂存消息
使用消息代理的优点
如果接收方不可用或过载, 它可以充当缓冲区, 从而提高系统的可靠性
它可以自动将消息重新发送到崩溃的进程, 从而防止消息丢失
它避免了发送方需要知道接收方的IP地址和端口号(这在虚拟机经常容易起起停停的云部署中特别有用)
它支持将一条消息发送给多个接收方
它在逻辑上将发送方与接收方分离
消息代理
分布式Actor框架
Actor模型是用于单个进程中并发的编程模型
分布式的Actor框架实质上是将消息代理和Actor编程模型集成到单个框架中, 但是如果要对基于Actor的应用程序执行滚动升级, 仍需担心向前和向后兼容性问题
小结
前言
数据密集型应用(Data-Intensive Applications)
对于一个应用系统, 如果"数据"是其成败决定性因素, 包括数据的规模, 数据的复杂度或者数据产生与变化的速率等, 我们就可以称为"数据密集型应用系统"
计算密集型(Compute-Intensive)
CPU主频往往是最大的制约瓶颈
序
技术是推动社会进步的强大动力。数据，软件和通信等，可能会被别有用心的人所用，保护既得利益。 技术需要善加利用：让弱小者的声音得到倾听，让每个人都有参与的机会，让世界免于灾难之苦。 谨以本书献给那些追逐梦想的人们。