第一章:可靠性,可扩展性,可维护性
1.1 关于数据系统的思考
单个工具已经不能满足应用系统的需求,总体工作被拆分成一系列能被单个工具高效完成的任务,并通过应用代码将它们缝合起来。比如一个缓存、索引、数据库协作的例子:
一个应用被称为数据密集型的,如果数据是其主要挑战(数据量,数据复杂度、数据变化速度)——与之相对的是计算密集型,即处理器速度是其瓶颈。 软件系统中很重要的三个问题:
- 可靠性(Reliability):系统在困境(硬件故障、软件故障、人为错误)中仍可正常工作
- 可扩展性(Scalability):有合理的办法应对系统的增长(数据量、流量、复杂性)
- 可维护性(Maintainability):许多不同的人在不同的生命周期,都能高效地在系统上工作。
1.2 可靠性
1.2.1 定义
- 造成错误的原因叫做故障(fault),能预料并应对故障的系统特性可称为容错(fault-tolerant)或者韧性(resilient)。讨论容错时,只有讨论特定类型的错误
- 故障(fault)不同于失效(failure):故障指的是一部分状态偏离标准,而失效则是系统作为一个整体停止向用户提供服务。
- 通常倾向于容忍错误(而不是阻止错误),但也有预防胜于治疗的情况(比如安全问题)
1.2.2 硬件故障
- 一般都是增加单个硬件的冗余度
- 云平台的设计是优先考虑灵活性和弹性,而不是单机可靠性。
1.2.3软件错误
- 这类软件故障的bug 通常潜伏很长时间,直到被异常情况触发为止。往往是某个假设出于某种原因最后不在成立了。
- 解决办法:仔细考虑假设和交互;彻底的测试;重启;监控。
1.2.4 人为错误
- 人是不可靠的,运维配置错误是导致服务中断的首要原因。
- 解决办法:最小化犯错机会的方式设计系统;容易犯错的地方解耦;测试;监控;培训。
1.3 可扩展性
1.3.1 定义
- 可扩展性(Scalability)是用来描述系统应对负载增长能力的术语。
1.3.2 描述负载
-
负载可以用负载参数的数字来描述,取决于系统架构
-
推特的发推设计:
a. 推文放在全局推文集合中,查询的时候做 join
b.推文插入到每个关注者的时间线中,「扇出」比较大,当有千万粉丝的大 V 发推压力大
c.推特从方案一变成了方案二,然后变成了两者结合的方式
1.3.3 描述性能
- 当描述好负载以后,问题变成了:
a. 增加负载参数并保持系统资源不变时,系统性能将受到什么影响?
b. 增加负载参数并希望性能不变时,需要增加多少系统资源? - 批处理系统,通常关心吞吐量(throughput);在线系统,通常更关心响应时间(response time)
- 对于系统响应时间而言,最好用百分位点,比如中位数、p99 等标识。
- 测量客户端的响应时间非常重要(而不是服务端),比如会出现头部阻塞、网络延迟等。
- 实践中的百分位点,可以用一个滑动的时间窗口(比如 10 分钟)进行统计。可以对列表进行排序,效率低的话,考虑一下前向衰减,t-digest 等方法近似计算。
1.3.4 应对负载的方法
- 纵向扩展:转向更强大的机器
- 横向扩展:将负载分布到多台小机器上
- 弹性系统:检测到负载增加时自动增加计算资源
- 跨多台机器部署无状态服务比较简单,但是把带状态的数据系统从单节点变成分布式配置则可能引入许多额外复杂度。因此,应该尽量将数据库放在单个节点上。
1.4 可维护性
- 在设计之初就尽量考虑尽可能减少维护期间的痛苦,从而避免自己的软件系统变成遗留系统。
- 三个设计原则:可操作性(Operability)便于运维团队保持系统平稳运行。简单性(Simplicity)从系统中消除尽可能多的复杂度(complexity),使新工程师也能轻松理解系统。(注意这和用户接口的简单性不一样。)可演化性(evolability)使工程师在未来能轻松地对系统进行更改,当需求变化时为新应用场景做适配。也称为可扩展性(extensibility),可修改性(modifiability)或可塑性(plasticity)。
1.4.1 可操作性:人生苦短,关爱运维
● 尽量自动化
1.4.2 简单性:管理复杂度
● 消除额外的(accidental)的复杂度 ● 消除额外复杂度的最好工具之一是抽象(abstraction)
1.4.3 可演化性:拥抱变化
● 敏捷(agile) 工作模式为适应变化提供了一个框架
● 简单易懂的系统通常比复杂系统更容易修改,即可演化性(evolvability)
第二章:数据模型与查询语言
数据模型可能是软件开发中最重要的部分了,因为它们的影响如此深远:不仅仅影响着软件的编写方式,而且影响着我们的解题思路。 一个复杂的应用程序可能会有更多的中间层次,比如基于API的API,不过基本思想仍然是一样的:每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。这些抽象允许不同的人群有效地协作。
2.1 关系模型与文档模型
现在最著名的数据模型可能是SQL。它基于Edgar Codd在1970年提出的关系模型【1】:数据被组织成关系(SQL中称作表),其中每个关系是元组(SQL中称作行)的无序集合。
2.1.1 NoSQL的诞生
- NoSQL:不仅是SQL(Not Only SQL)
- 采用NoSQL数据库的背后有几个驱动因素,其中包括: ○ 需要比关系数据库更好的可扩展性,包括非常大的数据集或非常高的写入吞吐量 ○ 相比商业数据库产品,免费和开源软件更受偏爱。 ○ 关系模型不能很好地支持一些特殊的查询操作 ○ 受挫于关系模型的限制性,渴望一种更具多动态性与表现力的数据模型
- 在可预见的未来,关系数据库似乎可能会继续与各种非关系数据库一起使用 - 这种想法有时也被称为混合持久化(polyglot persistence)
2.1.2 对象关系不匹配
- 应用程序使用面向对象的语言,需要一个转换层,才能转成 SQL 数据模型:被称为阻抗不匹配。
- Hibernate这样的 对象关系映射(ORM object-relational mapping) 框架可以减少这个转换层所需的样板代码的数量,但是它们不能完全隐藏这两个模型之间的差异。
- 对于一份简历而言,关系型模型需要一对多(比如工作经历)。
而表述这样的简历,使用 JSON 是非常合适的。JSON 比多表模式有更好的局部性,可以一次查询出一个用户的所有信息。JSON 其实是一棵树。
2.1.3 多对一和多对多的关系
- 为什么在 SQL 中,地域和公司都以 ID,而不是字符串进行标识呢? ○ ID 对人类没有任何意义,所以永远不需要改变,可以规范化人类的信息。那么就会存在多对一的关系(多个人对应了同一个 ID)。 ○ 在关系数据库 SQL 中,所有使用它的地方可以用 ID 来引用其他表中的行; ○ 但是文档数据库(比如 JSON),对连接支持很弱。
- 如果数据库不支持链接,那么就需要在应用代码中,对数据库执行多个查询进行模拟。执行连接的工作从数据库被转移到应用程序代码上。
哪怕最开始的应用适合无连接的文档模型,但是随着功能添加,数据会变得更加互联,比如对简历修改:
- 组织和学校作为实体:假如组织和学校有主页
- 推荐:给别人做推荐,当别人的信息更改的时候,所有地方要同步更新。
2.1.4 文档数据库是否在重蹈覆辙?
20 世纪 70 年代,最受欢迎的是层次模型(hierarchical model),它与文档数据库使用的JSON模型有一些惊人的相似之处。它将所有数据表示为嵌套在记录中的记录树。虽然能处理一对多的关系,但是很难应对多对多的关系,并且不支持链接。
提出的解决方案:
- 关系模型(relational model)(它变成了SQL,统治了世界)
- 网络模型(network model)(最初很受关注,但最终变得冷门)
2.1.4.1 网络模型
- 支持多对多,每条记录可能有多个父节点。
- 网络模型中记录之间的链接不是外键,而更像编程语言中的指针(同时仍然存储在磁盘上)。访问记录的唯一方法是跟随从根记录起沿这些链路所形成的路径。这被称为访问路径(access path)。
- 最简单的情况下,访问路径类似遍历链表:从列表头开始,每次查看一条记录,直到找到所需的记录。但在多对多关系的情况中,数条不同的路径可以到达相同的记录,网络模型的程序员必须跟踪这些不同的访问路径。
- 缺点:查询和更新数据库很麻烦。
2.1.4.2 关系模型
- 数据:一个 关系(表) 只是一个 元组(行) 的集合,很简单。
- 在关系数据库中,查询优化器自动决定查询的哪些部分以哪个顺序执行,以及使用哪些索引。这些选择实际上是“访问路径”,但最大的区别在于它们是由查询优化器自动生成的,不需要程序猿考虑。
2.1.4.3 与文档数据库相比
但是,在表示多对一和多对多的关系时,关系数据库和文档数据库并没有根本的不同:在这两种情况下,相关项目都被一个唯一的标识符引用,这个标识符在关系模型中被称为外键,在文档模型中称为文档引用。
2.1.5 关系型数据库与文档数据库在今日的对比
● 支持文档数据模型的主要论据是架构灵活性,因局部性而拥有更好的性能,以及对于某些应用程序而言更接近于应用程序使用的数据结构。 ● 关系模型通过为连接提供更好的支持以及支持多对一和多对多的关系来反击。
2.1.5.1 哪个数据模型更方便写代码?
文档模型: ● 优点: ○ 如果应用程序中的数据具有类似文档的结构(即,一对多关系树,通常一次性加载整个树),那么使用文档模型可能是一个好主意。 ● 缺点: ○ 不能直接引用文档中的嵌套的项目,而是需要说“用户251的位置列表中的第二项”(很像分层模型中的访问路径)。但是,只要文件嵌套不太深,这通常不是问题。 ○ 文档数据库对连接的糟糕支持也许或也许不是一个问题,这取决于应用程序。 ○ 如果应用程序使用多对多关系,那么文档模型就没有那么吸引人了。 ○ 对于高度相联的数据,选用文档模型是糟糕的,选用关系模型是可接受的,而选用图形模型是最自然的。
2.1.5.2 文档模型中的架构灵活性
- 文档模型是「读时模式」 ○ 文档数据库有时称为无模式(schemaless),但这具有误导性,因为读取数据的代码通常假定某种结构——即存在隐式模式,但不由数据库强制执行 ○ 一个更精确的术语是读时模式(schema-on-read)(数据的结构是隐含的,只有在数据被读取时才被解释),相应的是写时模式(schema-on-write)(传统的关系数据库方法中,模式明确,且数据库确保所有的数据都符合其模式) ○ 读时模式类似于编程语言中的动态(运行时)类型检查,而写时模式类似于静态(编译时)类型检查。
- 模式变更 ○ 读时模式变更字段很容易,只用改应用代码 ○ 写时模式变更字段速度很慢,而且要求停运。它的这种坏名誉并不是完全应得的:大多数关系数据库系统可在几毫秒内执行ALTER TABLE语句。MySQL是一个值得注意的例外,它执行ALTER TABLE时会复制整个表,这可能意味着在更改一个大型表时会花费几分钟甚至几个小时的停机时间,尽管存在各种工具来解决这个限制。
2.1.5.3 查询的数据局部性
● 文档通常以单个连续字符串形式进行存储,编码为JSON,XML或其二进制变体 ● 读文档: ○ 如果应用程序经常需要访问整个文档(例如,将其渲染至网页),那么存储局部性会带来性能优势。 ○ 局部性仅仅适用于同时需要文档绝大部分内容的情况。 ● 写文档: ○ 更新文档时,通常需要整个重写。只有不改变文档大小的修改才可以容易地原地执行。 ○ 通常建议保持相对小的文档,并避免增加文档大小的写入
2.1.5.4 文档和关系数据库的融合
● MySQL 等逐步增加了对 JSON 和 XML 的支持 ● 关系模型和文档模型的混合是未来数据库一条很好的路线。
2.2 数据查询语言
● 关系模型包含了一种查询数据的新方法:SQL是一种 声明式 查询语言,而IMS和CODASYL使用 命令式 代码来查询数据库。 ● 命令式语言:告诉计算机以特定顺序执行某些操作,比如常见的编程语言。 ● 声明式查询语言(如SQL或关系代数):你只需指定所需数据的模式 - 结果必须符合哪些条件,以及如何将数据转换(例如,排序,分组和集合) - 但不是如何实现这一目标。数据库系统的查询优化器决定使用哪些索引和哪些连接方法,以及以何种顺序执行查询的各个部分。 ○ SQL相当有限的功能性为数据库提供了更多自动优化的空间。 ○ 声明式语言往往适合并行执行。
2.2.1 Web上的声明式查询
● 声明式语言更加泛化,不用关心底层的数据存储变化 ● 在Web浏览器中,使用声明式CSS样式比使用JavaScript命令式地操作样式要好得多。 ● 类似地,在数据库中,使用像SQL这样的声明式查询语言比使用命令式查询API要好得多。
2.2.2 MapReduce查询
● 一些NoSQL数据存储(包括MongoDB和CouchDB)支持有限形式的MapReduce,作为在多个文档中执行只读查询的机制。 ● MapReduce既不是一个声明式的查询语言,也不是一个完全命令式的查询API,而是处于两者之间 ○ 查询的逻辑用代码片断来表示,这些代码片段会被处理框架重复性调用。 ○ 它基于map(也称为collect)和reduce(也称为fold或inject)函数,两个函数存在于许多函数式编程语言中。 ● map和reduce函数在功能上有所限制: ○ 它们必须是纯函数,这意味着它们只使用传递给它们的数据作为输入,它们不能执行额外的数据库查询,也不能有任何副作用。 ○ 这些限制允许数据库以任何顺序运行任何功能,并在失败时重新运行它们。 ○ MapReduce是一个相当底层的编程模型,用于计算机集群上的分布式执行。像SQL这样的更高级的查询语言可以用一系列的MapReduce操作来实现,但是也有很多不使用MapReduce的分布式SQL实现。 ○ MapReduce的一个可用性问题:必须编写两个密切合作的JavaScript函数,这通常比编写单个查询更困难。此外,声明式查询语言为查询优化器提供了更多机会来提高查询的性能。基于这些原因,MongoDB 2.2添加了一种叫做聚合管道的声明式查询语言的支持
2.3 图数据模型
-
多对多关系是不同数据模型之间具有区别性的重要特征。
-
文档模型:适合数据有一对多关系、不存在关系
-
图数据模型:适合多对多关系
-
一个图由两种对象组成: a. 顶点(vertices)(也称为节点(nodes) 或实体(entities)) b. 边(edges)( 也称为关系(relationships)或弧 (arcs) )。
-
举例:社交图谱,网络图谱,公路或铁路网络
-
图数据结构示例(以社交网络为例)
-
存储方式:属性图,三元组
2.3.1 属性图
在属性图模型中,每个顶点(vertex)包括: ● 唯一的标识符 ● 一组 出边(outgoing edges) ● 一组 入边(ingoing edges) ● 一组属性(键值对) 每条 边(edge) 包括: ● 唯一标识符 ● 边的起点/尾部顶点(tail vertex) ● 边的终点/头部顶点(head vertex) ● 描述两个顶点之间关系类型的标签 ● 一组属性(键值对) 使用关系模式来表示属性图
|
|
关于这个模型的一些重要方面是:
- 任何顶点都可以有一条边连接到任何其他顶点。没有模式限制哪种事物可不可以关联。
- 给定任何顶点,可以高效地找到它的入边和出边,从而遍历图,即沿着一系列顶点的路径前后移动。(这就是为什么例2-2在tail_vertex和head_vertex列上都有索引的原因。)
- 通过对不同类型的关系使用不同的标签,可以在一个图中存储几种不同的信息,同时仍然保持一个清晰的数据模型。
2.3.2 Cypher查询语言
- Cypher是属性图的声明式查询语言,为Neo4j图形数据库而发明
- 通常对于声明式查询语言来说,在编写查询语句时,不需要指定执行细节:查询优化程序会自动选择预测效率最高的策略,因此你可以继续编写应用程序的其他部分。
- 查找所有从美国移民到欧洲的人的Cypher查询
|
|
2.3.3 SQL中的图查询
- 用关系数据库表示图数据,那么也可以用SQL,但有些困难。
- 在关系数据库中,你通常会事先知道在查询中需要哪些连接。在图查询中,你可能需要在找到待查找的顶点之前,遍历可变数量的边。也就是说,连接的数量事先并不确定。
- 语法很复杂,
2.3.4 三元组存储和SPARQL
- 在三元组存储中,所有信息都以非常简单的三部分表示形式存储(主语,谓语,宾语)。例如,三元组 (吉姆, 喜欢 ,香蕉) 中,吉姆 是主语,喜欢 是谓语(动词),香蕉 是对象。
- 三元组的主语相当于图中的一个顶点。而宾语是下面两者之一: a. 原始数据类型中的值,例如字符串或数字。在这种情况下,三元组的谓语和宾语相当于主语顶点上的属性的键和值。例如,(lucy, age, 33)就像属性{“age”:33}的顶点lucy。 b. 图中的另一个顶点。在这种情况下,谓语是图中的一条边,主语是其尾部顶点,而宾语是其头部顶点。例如,在(lucy, marriedTo, alain)中主语和宾语lucy和alain都是顶点,并且谓语marriedTo是连接他们的边的标签。
- 当主语一样的时候,可以进行省略写法
|
|
2.3.4.1 语义网络
- 语义网是一个简单且合理的想法:网站已经将信息发布为文字和图片供人类阅读,为什么不将信息作为机器可读的数据也发布给计算机呢?
- 资源描述框架(RDF)的目的是作为不同网站以一致的格式发布数据的一种机制,允许来自不同网站的数据自动合并成一个数据网络 - 一种互联网范围内的“关于一切的数据库“。
- 现在已经凉了。
2.3.5 SPARQL查询语言
- SPARQL是一种用于三元组存储的面向RDF数据模型的查询语言
- 查找从美国转移到欧洲的人
|
|
2.3.6 基础:Datalog
Datalog是比SPARQL或Cypher更古老的语言,在20世纪80年代被学者广泛研究
2.4 本章小结
在历史上,数据最开始被表示为一棵大树(层次数据模型),但是这不利于表示多对多的关系,所以发明了关系模型来解决这个问题。 最近,开发人员发现一些应用程序也不适合采用关系模型。新的非关系型“NoSQL”数据存储在两个主要方向上存在分歧:
- 文档数据库的应用场景是:数据通常是自我包含的,而且文档之间的关系非常稀少。
- 图形数据库用于相反的场景:任意事物都可能与任何事物相关联。 文档数据库和图数据库有一个共同点,那就是它们通常不会为存储的数据强制一个模式,这可以使应用程序更容易适应不断变化的需求。但是应用程序很可能仍会假定数据具有一定的结构;这只是模式是明确的(写入时强制)还是隐含的(读取时处理)的问题。 每个数据模型都具有各自的查询语言或框架,我们讨论了几个例子:SQL,MapReduce,MongoDB的聚合管道,Cypher,SPARQL和Datalog。我们也谈到了CSS和XSL/XPath,它们不是数据库查询语言,而包含有趣的相似之处。
第三章:存储与检索
本章介绍了传统关系型数据库与“NoSQL”数据库的存储引擎。 我们会研究两大类存储引擎:日志结构(log-structured) 的存储引擎,以及面向页面(page-oriented) 的存储引擎(例如B树)。
3.1 驱动数据库的数据结构
世界上最简单的数据库可以用两个Bash函数实现:
|
|
这两个函数实现了键值存储的功能。
麻雀虽小,五脏俱全:
|
|
huhu 底层的存储格式非常简单:
|
|
- 与db_set做的事情类似,许多数据库在内部使用了日志(log),也就是一个 仅追加(append-only) 的数据文件。
- 每次你想查找一个键时,db_get 必须从头到尾扫描整个数据库文件来查找键的出现。
- 用算法的语言来说,查找的开销是 O(n) :如果数据库记录数量 n 翻了一倍,查找时间也要翻一倍。
3.1.1 索引
为了高效查找数据库中特定键的值,我们需要一个数据结构:索引(index)。
3.1.2 哈希索引
假设我们的数据存储只是一个追加写入的文件,最简单的索引策略就是:保留一个内存中的哈希映射,其中每个键都映射到一个数据文件中的字节偏移量,指明了可以找到对应值的位置
也可以把多个段的内容压缩合并到一起。
重要的问题:
- 文件格式
- a. csv 不好,使用二进制格式更快。
- a. 删除一个键,则必须在数据文件(有时称为逻辑删除)中附加一个特殊的删除记录。
- a. 如果数据库重新启动,则内存散列映射将丢失。
- b. 可以根据日志文件重新恢复每个段的哈希映射,但段很大的时候,很费时间。
- c. Bitcask通过存储加速恢复磁盘上每个段的哈希映射的快照,可以更快地加载到内存中。
- a. 数据库可能随时崩溃,包括将记录附加到日志中途。
- b. Bitcask文件包含校验和,允许检测和忽略日志的这些损坏部分。
- a. 写操作是以严格顺序的顺序附加到日志中的,所以常见的方法是只有一个写线程。
- b. 读操作可以有多个线程同时读取。
为什么采用追加模式,而不是不更新文件,用新值覆盖旧值? 原因有几个:
哈希表索引的局限性:
3.1.3 SSTables和LSM树
在之前的存储中,每个日志结构存储段都是一系列键值对。这些对按照它们写入的顺序出现,而不是键值对的顺序。 我们做一个简单的改变:我们要求键值对的序列按键排序。把这个格式称为排序字符串表(Sorted String Table),简称 SSTable。同时,要求每个键只在每个合并的段文件中出现一次(压缩过程已经保证)。
SSTable 与散列索引日志段相比,有几个很大的优势:
- 合并段是简单而高效的,即使文件大于可用内存。方法类似于归并排序。
a. 如果在几个输入段中出现相同的键,该怎么办? ⅰ. 答:保留最近段的值,并丢弃旧段中的值。
- 为了在文件中找到一个特定的键,你不再需要保存内存中所有键的索引。因为是有序的,可以先查找出键所处的范围,然后就找到这个键所在的偏移量的区间。比如可以从 handbag 和 handsome 的偏移量找到 handiwork 的区间。
3.1.3.1 构建和维护SSTables
如何让数据首先被按键排序呢?
存储工作的操作步骤:
如何解决数据库崩溃,则最近的写入(在内存表中,但尚未写入磁盘)将丢失的问题?
3.1.3.2 用SSTables制作LSM树
LSM 树:在 LevelDB 和 RocksDB 使用。
3.1.3.3 性能优化
- 当查找数据库中不存在的键时,LSM树算法可能会很慢:您必须检查内存表,然后将这些段一直回到最老的(可能必须从磁盘读取每一个),然后才能确定键不存在。
3.1.3.4 B树
像SSTables一样,B树保持按键排序的键值对,这允许高效的键值查找和范围查询。 不同:
每个页面都可以使用地址或位置来标识,这允许一个页面引用另一个页面 —— 类似于指针,但在磁盘而不是在内存中。
查找过程: ● 一个页面会被指定为B树的根;在索引中查找一个键时,就从这里开始。 ● 该页面包含几个键和对子页面的引用。 ● 每个子页面负责一段连续范围的键,引用之间的键,指明了引用子页面的键范围。 ● 最后,我们可以看到包含单个键(叶页)的页面,该页面包含每个键的内联值,或者包含对可以找到值的页面的引用。
更新过程: ● 搜索包含该键的叶页,更改该页中的值,并将该页写回到磁盘原来的位置(对该页的任何引用保持有效)
插入过程: ● 找到其范围包含新键的页面,并将其添加到该页面。 ● 如果页面中没有足够的可用空间容纳新键,则将其分成两个半满页面,并更新父页面以解释键范围的新分区。
删除过程: ● 删除一个键(同时保持树平衡)就牵扯很多其他东西了。
深度: ● 该算法确保树保持平衡:具有 n 个键的B树总是具有 $O(log n)$ 的深度。 ● 大多数数据库可以放入一个三到四层的 B 树,所以你不需要遵追踪多页面引用来找到你正在查找的页面。 (分支因子为 500 的 4KB 页面的四级树可以存储多达 256TB 。)
3.1.3.5 让B树更可靠
● B 树的基本底层写操作是用新数据覆盖磁盘上的页面。 ● 假定覆盖不改变页面的位置; ● 而日志结构索引(如LSM树)只附加到文件(并最终删除过时的文件),但从不修改文件。
危险操作: ● 插入导致页面过度而拆分页面,则需要编写已拆分的两个页面,并覆盖其父页面以更新对两个子页面的引用。 ● 这是一个危险的操作,因为如果数据库在仅有一些页面被写入后崩溃,那么最终将导致一个损坏的索引(例如,可能有一个孤儿页面不是任何父项的子项) 。
预写式日志(WAL) ● 为了使数据库对崩溃具有韧性,B树实现通常会带有一个额外的磁盘数据结构:预写式日志(WAL, write-ahead-log)(也称为重做日志(redo log))。 ● 这是一个仅追加的文件,每个B树修改都可以应用到树本身的页面上。 ● 当数据库在崩溃后恢复时,这个日志被用来使B树恢复到一致的状态.
并发访问: ● 更新页面时,如果多个线程要同时访问B树,则需要仔细的并发控制,否则可能会看到树处于不一致的状态。 ● 通过使用锁存器(latches)(轻量级锁)保护树的数据结构来完成 ● 而 LSM 比较简单:在后台完成所有的合并,不干扰查询;通过「原子交换」把旧的分段变为新的分段。
3.1.3.6 B树优化
● LMDB 数据库中使用「写时复制方案 」,而不是不是覆盖页面并维护 WAL 进行崩溃恢复。 ○ 修改的页面被写入到不同的位置,并且树中的父页面的新版本被创建,指向新的位置。 ○ 这种方法对于并发控制也很有用。 ● 保存键的缩略信息,而不是完整的键。 ○ 键只用保存一个区间,而不是具体的数值(类似于 B+树)。 ○ 可以包含更多的键,减少树的层次。 ● 不方便扫描大部分关键词的范围查找。 ○ 许多B树实现尝试布局树,使得叶子页面按顺序出现在磁盘上。 ○ 但是,随着树的增长,维持这个顺序是很困难的。 ○ 相比之下,由于LSM树在合并过程中一次又一次地重写存储的大部分,所以它们更容易使顺序键在磁盘上彼此靠近。 ● 额外的指针已添加到树中。 ○ 例如,每个叶子页面可以在左边和右边具有对其兄弟页面的引用,这允许不跳回父页面就能顺序扫描。 ● B树的变体如分形树借用一些日志结构的思想来减少磁盘寻道(而且它们与分形无关)。
3.1.4 比较B树和LSM树
通常LSM树的写入速度更快,而B树的读取速度更快。 LSM树上的读取通常比较慢,因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。
3.1.4.1 LSM树的优点
● B树索引必须至少两次写入每一段数据:一次写入预先写入日志,一次写入树页面本身(也许再次分页) ● 即使在该页面中只有几个字节发生了变化,也需要一次编写整个页面的开销。 ● 有些存储引擎甚至会覆盖同一个页面两次,以免在电源故障的情况下导致页面部分更新
写放大 ● 反复压缩和合并SSTables,日志结构索引也会重写数据。 ● 在数据库的生命周期中写入数据库导致对磁盘的多次写入 —— 被称为写放大(write amplification)。 ● 存储引擎写入磁盘的次数越多,可用磁盘带宽内的每秒写入次数越少。
LSM树通常能够比B树支持更高的写入吞吐量: ● 部分原因是它们有时具有较低的写放大(尽管这取决于存储引擎配置和工作负载) ● 部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面 ● 这种差异在磁性硬盘驱动器上尤其重要,顺序写入比随机写入快得多。
文件碎片: ● LSM树可以被压缩得更好,因此经常比B树在磁盘上产生更小的文件。 ● B树存储引擎会由于分割而留下一些未使用的磁盘空间 ● 由于LSM树不是面向页面的,并且定期重写SSTables以去除碎片,所以它们具有较低的存储开销,特别是当使用平坦压缩时
3.1.4.2 LSM树的缺点
日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。 B树的行为则相对更具可预测性。
高写入吞吐量: ● 磁盘的有限写入带宽需要在初始写入(记录和刷新内存表到磁盘)和在后台运行的压缩线程之间共享。 ● 写入空数据库时,可以使用全磁盘带宽进行初始写入,但数据库越大,压缩所需的磁盘带宽就越多。
压缩和读取的速度: ● 如果写入吞吐量很高,并且压缩没有仔细配置,压缩跟不上写入速率。 ● 在这种情况下,磁盘上未合并段的数量不断增加,直到磁盘空间用完,读取速度也会减慢,因为它们需要检查更多段文件。
键出现的个数: ● B树的一个优点是每个键只存在于索引中的一个位置,而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。 ● 有利于事务语义。 ● 在许多关系数据库中,事务隔离是通过在键范围上使用锁来实现的,在B树索引中,这些锁可以直接连接到树
3.1.5 其他索引结构
前面讨论的是关键值索引,它们就像关系模型中的主键(primary key) 索引。主键唯一标识关系表中的一行、一个文档、一个顶点。
二级索引 ● 在关系数据库中,您可以使用 CREATE INDEX 命令在同一个表上创建多个二级索引,而且这些索引通常对于有效地执行联接而言至关重要。 ● 一个二级索引可以很容易地从一个键值索引构建,区别是键不是唯一的。实现方式: ○ 通过使索引中的每个值,成为匹配行标识符的列表(如全文索引中的发布列表) ○ 通过向每个索引添加行标识符来使每个关键字唯一 ○ 无论哪种方式,B树和日志结构索引都可以用作辅助索引。
3.1.5.1 将值存储在索引中
索引中的关键字是查询搜索的内容,它属于两种之一: ● 实际行(文档,顶点) ● 对存储在别处的行的引用。此时,行被存储的地方被称为堆文件(heap file),并且存储的数据没有特定的顺序 ○ 堆文件很常见。 ○ 它避免了在存在多个二级索引时复制数据 ○ 新值字节数不大于旧值,原地覆盖; ○ 新值更大,需要移到堆中有足够空间的新位置; ■ 此时,要么所有索引都更新指向新堆位置; ■ 要么在旧堆位置留一个转发指针。
聚集索引 ● 从索引到堆文件的额外跳转性能损失太大,希望可以把索引行直接进存储到索引中。被叫做聚集索引。 ● 在 MySQL 的 InnoDB 存储引擎中,表的主键总是一个聚簇索引,二级索引用主键(而不是堆文件中的位置) ● 在SQL Server中,可以为每个表指定一个聚簇索引。
包含列的索引或覆盖索引 ● 在 聚集索引(clustered index) (在索引中存储所有行数据)和 非聚集索引(nonclustered index) (仅在索引中存储对数据的引用)之间的折衷被称为 包含列的索引(index with included columns)或覆盖索引(covering index),其存储表的一部分在索引内。 ● 允许通过单独使用索引来回答一些查询。 ● 加快了读取速度,但是增加了额外的存储空间,增加了写入开销,还要事务保证。
3.1.5.2 多列索引
上面讨论的都是一个 key 对应一个 value,如果需要同时根据一个表中的多个列(或文档中的多个字段)进行查询,则不行。 ● 连接索引(concatenated index) ○ 将一列的值追加到另一列后面,简单地将多个字段组合成一个键。 ○ 但是这不能做复杂查询。 ● 多维索引(multi-dimensional index) ○ 比如需要根据经纬度做二维范围查询,则 B 树和 LSM 树不能高效; ○ 普遍做法是用特殊化的空间索引,比如 R 树(TODO)。 ○ 多维索引除了地理位置,还可以用于其他很多地方:电子网站、天气数据。
3.1.5.3 全文搜索和模糊索引
上文讨论的索引都是查询确切的值或者确定范围的值,如果搜索类似的键,需要用模糊查询。
全文搜索引擎 ● 允许搜索一个单词以扩展为包括该单词的同义词,忽略单词的语法变体,并且搜索在相同文档中彼此靠近的单词的出现,并且支持各种其他功能取决于文本的语言分析。 ● 为了处理文档或查询中的拼写错误,Lucene能够在一定的编辑距离内搜索文本(编辑距离1意味着添加,删除或替换了一个字母)
Lucene ● 为其词典使用了一个类似于SSTable的结构。 ● 这个结构需要一个小的内存索引,告诉查询在排序文件中哪个偏移量需要查找关键字。 ● 在 LevelDB 中,这个内存中的索引是一些键的稀疏集合。 ● 但在 Lucene 中,内存中的索引是键中字符的有限状态自动机,类似于trie。 ● 这个自动机可以转换成 Levenshtein 自动机,它支持在给定的编辑距离内有效地搜索单词。
3.1.5.4 在内存中存储一切
对于磁盘和SSD,如果要在读取和写入时获得良好性能,则需要仔细地布置磁盘上的数据。 磁盘优点:耐用,成本低。 内存变得便宜,促进了内存数据库发展。
内存数据库 ● 某些内存中的键值存储(如Memcached)仅用于缓存,在重新启动计算机时丢失的数据是可以接受的。 ● 但其他内存数据库的目标是持久性,可以通过特殊的硬件(例如电池供电的RAM),将更改日志写入磁盘,将定时快照写入磁盘或通过复制内存来实现,记忆状态到其他机器。
实现 ● 内存数据库重新启动时,需要从磁盘或通过网络从副本重新加载其状态(除非使用特殊的硬件)。 ● 尽管写入磁盘,它仍然是一个内存数据库,因为磁盘仅用作耐久性附加日志,读取完全由内存提供。 ● 写入磁盘也具有操作优势:磁盘上的文件可以很容易地由外部实用程序进行备份,检查和分析。
常见产品 ● VoltDB,MemSQL和Oracle TimesTen等产品是具有关系模型的内存数据库 ● RAM Cloud是一个开源的内存键值存储器,具有持久性(对存储器中的数据以及磁盘上的数据使用日志结构化方法) ● Redis和Couchbase通过异步写入磁盘提供了较弱的持久性。
内存数据库性能优势到底在哪? ● 内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。 ● 即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取,因为操作系统缓存最近在内存中使用了磁盘块。 ● 相反,它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。
除了性能还有什么优势? ● 提供了难以用基于磁盘的索引实现的数据模型。 ● 例如,Redis为各种数据结构(如优先级队列和集合)提供了类似数据库的接口。因为它将所有数据保存在内存中,所以它的实现相对简单。
内存不够用怎么办? ● 反缓存(anti-caching) 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到磁盘,并在将来再次访问时将其重新加载到内存中。 ● 这与操作系统对虚拟内存和交换文件的操作类似,但数据库可以比操作系统更有效地管理内存,因为它可以按单个记录的粒度工作,而不是整个内存页面。 ● 尽管如此,这种方法仍然需要索引能完全放入内存中。
3.2 事务处理还是分析?
事务处理 ● 早起的业务处理,典型的数据库写入与一笔商业交易(transaction)相对应,以后交易/事务(transaction) 仍留了下来。 ● 事务不一定具有ACID(原子性,一致性,隔离性和持久性)属性。 ● 事务处理只是意味着允许客户端进行低延迟读取和写入 —— 而不是只能定期运行(例如每天一次)的批量处理作业。 ● 数据库仍然常被用作在线事务处理(OLTP, OnLine Transaction Processing) 。
数据分析 ● 数据库也开始越来越多地用于数据分析,需要扫描大量记录; ● 为了将这种使用数据库的模式和事务处理区分开,它被称为在线分析处理(OLAP, OnLine Analytice Processing)
属性 | 事务处理 OLTP | 分析系统 OLAP |
主要读取模式 | 查询少量记录,按键读取 | 在大批量记录上聚合 |
主要写入模式 | 随机访问,写入要求低延时 | 批量导入(ETL),事件流 |
主要用户 | 终端用户,通过Web应用 | 内部数据分析师,决策支持 |
处理的数据 | 数据的最新状态(当前时间点) | 随时间推移的历史事件 |
数据集尺寸 | GB ~ TB | TB ~ PB/td> |
3.2.1 数据仓库
3.2.2 星型和雪花型:分析的模式
3.3 列存储
面向列的存储
3.3.1 列压缩
● 除了仅从磁盘加载查询所需的列以外,我们还可以通过压缩数据来进一步降低对磁盘吞吐量的需求。 ● 面向列的存储通常很适合压缩。
位图编码
3.3.1.1 内存带宽和向量处理
● 需要扫描数百万行的数据仓库查询来说,瓶颈: ○ 是从磁盘获取数据到内存的带宽。 ○ 主存储器带宽到CPU缓存中的带宽,避免CPU指令处理流水线中的分支错误预测和泡沫,以及在现代中使用单指令多数据(SIMD)指令CPU ● 面向列的存储布局: ○ 可以将大量压缩的列数据放在CPU的L1缓存中,然后在紧密的循环中循环(即没有函数调用) ○ 更有利于 CPU 的计算。
3.3.2 列存储中的排序顺序
● 在列存储中,存储行的顺序并不一定很重要。 ● 按插入顺序存储它们是最简单的,因为插入一个新行只需要追加到每个列文件。 ● 每列独自排序是没有意义的,因为那样我们就不会知道列中的哪些项属于同一行 ● 即使按列存储数据,也需要一次对整行进行排序。
好处 ● 速度快:这样数据库的管理员可以根据他们对常用查询的了解来选择表格应该被排序的列。 ● 压缩列:第一个排序键的压缩效果最强。
3.3.2.1 几个不同的排序顺序
● 不同的查询受益于不同的排序顺序,而无论如何,数据需要复制到多台机器, ● 在一个面向列的存储中有多个排序顺序有点类似于在一个面向行的存储中有多个二级索引。
3.3.3 写入列存储
列存储的优点:大部分只用查询;压缩和排序都有助于更快地读取这些查询。 缺点:写入困难。插入必须始终更新所有列。
解决方案:LSM树。 ● 现在内存中存储,添加到一个已排序的结构中,然后准备写入磁盘。
3.3.4 聚合:数据立方体和物化视图
并不是每个数据仓库都必定是一个列存储。列存储在迅速普及。
物化汇总 ● 数据仓库查询通常涉及一个聚合函数,如SQL中的COUNT,SUM,AVG,MIN或MAX。 ● 创建这种缓存的一种方式是物化视图(Materialized View)。
物化数据立方体的优点是某些查询变得非常快,因为它们已经被有效地预先计算了。
3.4 本章小结
优化 事务处理(OLTP) 或 在线分析(OLAP) 。这些用例的访问模式之间有很大的区别: ● OLTP系统通常面向用户,这意味着系统可能会收到大量的请求。为了处理负载,应用程序通常只访问每个查询中的少部分记录。应用程序使用某种键来请求记录,存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是这里的瓶颈。 ● 数据仓库和类似的分析系统会低调一些,因为它们主要由业务分析人员使用,而不是由最终用户使用。它们的查询量要比OLTP系统少得多,但通常每个查询开销高昂,需要在短时间内扫描数百万条记录。磁盘带宽(而不是查找时间)往往是瓶颈,列式存储是这种工作负载越来越流行的解决方案。
在OLTP方面,我们能看到两派主流的存储引擎:
日志结构学派
只允许附加到文件和删除过时的文件,但不会更新已经写入的文件。 Bitcask,SSTables,LSM树,LevelDB,Cassandra,HBase,Lucene等都属于这个类别。
就地更新学派
将磁盘视为一组可以覆写的固定大小的页面。 B树是这种哲学的典范,用在所有主要的关系数据库中和许多非关系型数据库。
日志结构的存储引擎是相对较新的发展。他们的主要想法是,他们系统地将随机访问写入顺序写入磁盘,由于硬盘驱动器和固态硬盘的性能特点,可以实现更高的写入吞吐量。在完成OLTP方面,我们通过一些更复杂的索引结构和为保留所有数据而优化的数据库做了一个简短的介绍。
第四章:数据编码与演化
应用程序总是增增改改。 修改程序大多数情况下也在修改存储的数据。
当数据格式发生改变时,需要代码更改:
新旧版本的代码和数据,可能同时共处。 系统需要双向兼容:
4.1 编码数据的格式
程序通常(至少)使用两种形式的数据:
- 在内存中,数据保存在对象,结构体,列表,数组,哈希表,树等中。 这些数据结构针对CPU的高效访问和操作进行了优化(通常使用指针)。
- 如果要将数据写入文件,或通过网络发送,则必须将其 编码(encode) 为某种自包含的字节序列(例如,JSON文档)。 由于每个进程都有自己独立的地址空间,一个进程中的指针对任何其他进程都没有意义,所以这个字节序列表示会与通常在内存中使用的数据结构完全不同。
所以,需要在两种表示之间进行某种类型的翻译。
4.1.1 语言特定的格式
许多编程语言都内建了将内存对象编码为字节序列的支持。例如,Java有java.io.Serializable ,Ruby有Marshal,Python有pickle .
这些库很方便,但是有深层次问题:
只适合临时使用。
4.1.2 JSON,XML和二进制变体
跨语言的编码:JSON,XML和CSV,属于文本格式,因此具有人类可读性。 除了语法问题外,还有问题:
虽然问题多,但是大家对这些达成了意见一致。
4.1.2.1 二进制编码
当数据很多的时候,数据格式的选择会有很大影响。 JSON比XML简洁,但与二进制格式相比还是太占空间。现在有很多二进制格式的 JSON(MessagePack,BSON,BJSON,UBJSON,BISON和Smile等)。 JSON 字符串是:
|
|
二进制编码长度为66个字节,仅略小于文本JSON编码所取的81个字节(删除了空白)。
4.1.3 Thrift与Protocol Buffers
接口定义语言(IDL) 来描述模式。
|
|
|
|
Thrift 编码格式
BinaryProtocol
– 对上面的信息编码只需要59个字节
CompactProtocol
Protocol Buffers
字段是否为必须?
4.1.3.1 字段标签和模式演变
4.1.3.2 数据类型和模式演变
4.1.4 Avro
举例:
|
|
等价的JSON表示:
|
|
4.1.4.1 Writer模式与Reader模式
4.1.4.2 模式演变规则
4.1.4.3 但Writer模式到底是什么?
对于一段特定的编码数据,Reader如何知道其Writer模式? 答案取决于Avro使用的上下文。举几个例子:
○ Avro的一个常见用途 - 尤其是在Hadoop环境中 - 用于存储包含数百万条记录的大文件,所有记录都使用相同的模式进行编码。可以在文件的开头只包含一次Writer模式。
○ 最简单的解决方案是在每个编码记录的开始处包含一个版本号,并在数据库中保留一个模式版本列表。
4.1.4.4 动态生成的模式
Avro方法的一个优点是架构不包含任何标签号码。
但为什么这很重要?在模式中保留一些数字有什么问题?
- ○ 方便从数据库生成 Avro 模式,导出数据
- ○ 当数据库模式发生变化,直接生成新的 Avro 模式,导出数据。自动兼容。
- ○ 而用 Thrift 或者 PB,需要手动写字段标签。
4.1.4.5 代码生成和动态类型的语言
- 在定义了模式之后,可以使用您选择的编程语言生成实现此模式的代码。
- 这在Java,C ++或C#等静态类型语言中很有用,因为它允许将高效的内存中结构用于解码的数据,并且在编写访问数据结构的程序时允许在IDE中进行类型检查和自动完成。
- 在动态类型编程语言(如JavaScript,Ruby或Python)中,生成代码没有太多意义,因为没有编译时类型检查器来满足。
- Avro为静态类型编程语言提供了可选的代码生成功能,但是它也可以在不生成任何代码的情况下使用。
4.1.5 模式的优点
- 他们的模式语言比XML模式或者JSON模式简单得多,也支持更详细的验证规则。
- 它们可以比各种“二进制JSON”变体更紧凑,因为它们可以省略编码数据中的字段名称。
- 模式是一种有价值的文档形式,因为模式是解码所必需的,所以可以确定它是最新的(而手动维护的文档可能很容易偏离现实)。
- 维护一个模式的数据库允许您在部署任何内容之前检查模式更改的向前和向后兼容性。
- 对于静态类型编程语言的用户来说,从模式生成代码的能力是有用的,因为它可以在编译时进行类型检查。
4.2 数据流的类型
数据在流程之间流动的一些常见的方式:
4.2.1 数据库中的数据流
4.2.1.1 在不同的时间写入不同的值
4.2.1.2 归档存储
4.2.2 服务中的数据流:REST与RPC
4.2.2.1 Web服务
REST
- ● REST不是一个协议,而是一个基于HTTP原则的设计哲学。
- ● 它强调简单的数据格式,使用URL来标识资源,并使用HTTP功能进行缓存控制,身份验证和内容类型协商。
- ● 与SOAP相比,REST已经越来越受欢迎,至少在跨组织服务集成的背景下,并经常与微服务相关。
- ● 根据REST原则设计的API称为RESTful。
SOAP
- SOAP是用于制作网络API请求的基于XML的协议。
- 它最常用于HTTP,但其目的是独立于HTTP,并避免使用大多数HTTP功能。
- SOAP Web服务的API使用称为Web服务描述语言(WSDL)的基于XML的语言来描述。 WSDL支持代码生成,客户端可以使用本地类和方法调用(编码为XML消息并由框架再次解码)访问远程服务。
- 尽管SOAP及其各种扩展表面上是标准化的,但是不同厂商的实现之间的互操作性往往会造成问题。
- 尽管许多大型企业仍然使用SOAP,但在大多数小公司中已经不再受到青睐。
4.2.2.2 远程过程调用(RPC)的问题
RPC模型试图向远程网络服务发出请求,看起来与在同一进程中调用编程语言中的函数或方法相同(这种抽象称为位置透明)。
RPC的缺陷
4.2.2.3 RPC的当前方向
RPC 不会消失。
- ● Thrift和Avro带有RPC支持
- ● gRPC是使用Protocol Buffers的RPC实现
- ● Finagle也使用Thrift
- ● Rest.li使用JSON over HTTP。
当前方向
- REST 使用二进制编码性能更好
- 方便实验和调试
- 能被所有主流的编程语言和平台支持
- 大量可用的工具的生态系统
4.2.2.4 数据编码与RPC的演化
RPC方案的前后向兼容性属性从它使用的编码方式中继承:
服务的提供者无法控制其客户,所以可能无限期保持兼容性。 对于 RESTful API,常用方法是在 URL 或者 HTTP Accept 头部使用版本号。
4.2.3 消息传递中的数据流
与直接RPC相比,使用消息代理(消息队列)有几个优点:
与 PRC 相比,差异在于
- ● 消息传递通常是单向的:发送者通常不期望收到其消息的回复。
- ● 通信模式是异步的:发送者不会等待消息被传递,而只是发送它,然后忘记它。
4.2.3.1 消息代理
- 一个进程将消息发送到指定的队列或主题;
- 代理确保将消息传递给那个队列或主题的一个或多个消费者或订阅者。
- 在同一主题上可以有许多生产者和许多消费者。
4.2.3.2 分布式的Actor框架
分布式Actor框架
位置透明
升级
三个流行的分布式actor框架处理消息编码如下:
4.3 本章小结
结论:前向兼容性和滚动升级在某种程度上是可以实现的。
第五章:数据复制
复制的目的:
● 使得数据与用户在地理上接近(从而减少延迟)
● 即使系统的一部分出现故障,系统也能继续工作(从而提高可用性)
● 伸缩可以接受读请求的机器数量(从而提高读取吞吐量)
如果复制的数据不会随时间而改变,那复制就很简单:复制一次即可。
复制的难点在于复制数据的变更。
三种流行的变更复制算法:
● 单领导者
● 多领导者
● 无领导者
复制时的权衡:使用同步复制还是异步复制?如何处理失败的副本?
5.1 领导者与追随者
● 存储数据库副本的每个节点称为 副本(replica)。
● 多副本的问题:如何确保数据都落在了所有的副本上。
- ○ 每次对数据库的写入都要传播到所有副本上,否则副本就会有不一样的数据。
- ○ 常见的解决方案:基于领导者的复制(主从复制)。
主从复制工作原理:
- 副本之一被指定为领导者(leader,也被称作主库)
- a. 客户端写数据时,要把请求发送给领导者;
- b. 领导者把新输入写入本地存储。
- a. 每当领导者将新数据写入本地存储时,他会把数据变更发送给所有的追随者,称之为复制日志或变更流。
- b. 每个追随者从领导者拉取日志,并相应更新其本地数据库副本,方法是按照领导者处理的相同顺序应用所有写入。
5.1.1 同步复制与异步复制
复制系统的一个重要细节是:复制是 同步(synchronously) 发生还是 异步(asynchronously) 发生。 以用户更新头像为例: ● 从库 1 的复制是同步的 ● 从库 2 的复制是异步的
同步复制: ● 优点:从库保证和主库一直的最新数据副本 ● 缺点:如果从库没有响应(如已崩溃、网络故障),主库就无法处理写入操作。主库必须阻止所有的写入,等待副本再次可用。
半同步:通常使用一个从库与主库是同步的,而其他从库是异步的。这保证了至少两个节点拥有最新的数据副本。
通常情况下,基于领导者的复制都配置为完全异步。注意,主库故障可能导致丢失数据。
5.1.2 设置新从库
有时会增加一个新的从库。
过程:
- 在某个时刻获取主库的一致性快照(如果可能),而不必锁定整个数据库。大多数数据库都具有这个功能,因为它是备份必需的。对于某些场景,可能需要第三方工具,例如MySQL的innobackupex 。
- 将快照复制到新的从库节点。
- 从库连接到主库,并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称:例如,PostgreSQL将其称为 日志序列号(log sequence number, LSN),MySQL将其称为 二进制日志坐标(binlog coordinates)。
- 当从库处理完快照之后积压的数据变更,我们说它 赶上(caught up) 了主库。现在它可以继续处理主库产生的数据变化了。
5.1.3 处理节点宕机
我们的目标:即使个别节点失效,也要能保持整个系统运行,并尽可能控制节点停机带来的影响。
5.1.3.1 从库失效:追赶恢复
● 从库可以从日志知道,在发生故障前处理的最后一个事务。 ● 所以从库可以连接到主库,并拉取断开连接后的所有数据变更。 ● 应用完成所有变更之后,它就赶上了主库,继续接收数据变更流。
5.1.3.2 主库失效:故障切换
● 故障切换:需要把一个从库提升为新的主库,重新配置客户端,其他从库需要开始拉取来自新主库的变更。 ● 故障切换可以手动或者自动进行。
自动故障切换:
- 确认主库失效。有很多事情可能会出错:崩溃,停电,网络问题等等。没有万无一失的方法来检测出现了什么问题,所以大多数系统只是简单使用 超时(Timeout) :节点频繁地相互来回传递消息,并且如果一个节点在一段时间内(例如30秒)没有响应,就认为它挂了(因为计划内维护而故意关闭主库不算)。
- 选择一个新的主库。这可以通过选举过程(主库由剩余副本以多数选举产生)来完成,或者可以由之前选定的控制器节点(controller node) 来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库(最小化数据损失)。让所有的节点同意一个新的领导者,是一个共识问题,将在第九章详细讨论。
- 重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库(将在“请求路由”中讨论这个问题)。如果老领导回来,可能仍然认为自己是主库,没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导,成为一个从库。
故障切换会出现很多大麻烦:
● 如果使用异步复制,则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后,如果老主库重新加入集群,新主库在此期间可能会收到冲突的写入,那这些写入该如何处理?最常见的解决方案是简单丢弃老主库未复制的写入,这很可能打破客户对于数据持久性的期望。
● 如果数据库需要和其他外部存储相协调,那么丢弃写入内容是极其危险的操作。例如在GitHub 【13】的一场事故中,一个过时的MySQL从库被提升为主库。数据库使用自增ID作为主键,因为新主库的计数器落后于老主库的计数器,所以新主库重新分配了一些已经被老主库分配掉的ID作为主键。这些主键也在Redis中使用,主键重用使得MySQL和Redis中数据产生不一致,最后导致一些私有数据泄漏到错误的用户手中。
● 发生某些故障时(见第八章)可能会出现两个节点都以为自己是主库的情况。这种情况称为 脑裂(split brain),非常危险:如果两个主库都可以接受写操作,却没有冲突解决机制(请参阅“多主复制”),那么数据就可能丢失或损坏。一些系统采取了安全防范措施:当检测到两个主库节点同时存在时会关闭其中一个节点[1],但设计粗糙的机制可能最后会导致两个节点都被关闭【14】。
● 主库被宣告死亡之前的正确超时应该怎么配置?在主库失效的情况下,超时时间越长,意味着恢复时间也越长。但是如果超时设置太短,又可能会出现不必要的故障切换。例如,临时负载峰值可能导致节点的响应时间超时,或网络故障可能导致数据包延迟。如果系统已经处于高负载或网络问题的困扰之中,那么不必要的故障切换可能会让情况变得更糟糕。
5.1.4 复制日志的实现
基于主库的复制,底层工作有几种不同的复制方式。
5.1.4.1 基于语句的复制
在最简单的情况下,主库记录下它执行的每个写入请求(语句(statement))并将该语句日志发送给其从库。 问题: ● 任何调用 非确定性函数(nondeterministic) 的语句,可能会在每个副本上生成不同的值。比如 NOW(), RAND()。 ● 如果语句使用了自增列(auto increment),或者依赖于数据库中的现有数据(例如,UPDATE … WHERE <某些条件>),则必须在每个副本上按照完全相同的顺序执行它们,否则可能会产生不同的效果。影响并发。 ● 有副作用的语句(例如,触发器,存储过程,用户定义的函数)可能会在每个副本上产生不同的副作用,除非副作用是绝对确定的。
5.1.4.2 传输预写式日志(WAL)
第三章告诉我们,写操作通常追加到日志中: ● 对于日志结构存储引擎(SSTables 和 LSM 树),日志是主要存储位置。日志段在后台压缩,并进行垃圾回收。 ● 覆盖单个磁盘块的 B 树,每次修改会先写入预写式日志(Write Ahead Log, WAL),以便崩溃后索引可以恢复到一个一致的状态。 所以,日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本:主库把日志发送给从库。 PostgreSQL和Oracle等使用这种复制方法。 缺点: ● 复制与存储引擎紧密耦合。 ● 不可能使主库和从库上运行不同版本的数据库软件。 ● 运维时如果升级软件版本,有可能会要求停机。
5.1.4.3 逻辑日志复制(基于行)
采用逻辑日志,可以把复制与存储逻辑分离。 关系型数据库通常以行作为粒度描述数据库写入的记录序列: ● 对于插入的行,日志包含所有列的新值; ● 对于删除的行,日志包含足够的信息来唯一标识已删除的行。通常是主键,或者所有列的旧值。 ● 对于更新的行,日志包含足够的信息来唯一标识更新的行,以及所有列(至少是更新列)的新值。 优点: ● 逻辑日志与存储引擎分离,方便向后兼容。可以让领导者和跟随者运行不同版本的数据库软件。 ● 对于外部应用,逻辑日志也更容易解析。比如复制到数据仓库,或者自定义索引和缓存。被称为数据变更捕获。
5.1.4.4 基于触发器的复制
● 上述复制都是数据库自己实现的。也可以自定义复制方法:数据库提供了触发器和存储过程。 ● 允许数据库变更时,自动执行应用的程序代码。 ● 开销更大,更容易出错。但更灵活。
5.2 复制延迟问题
● 主从异步同步会有延迟:导致同时对主库和从库的查询,结果可能不同。 ● 因为从库会赶上主库,所以上述效应被称为「最终一致性」。 ● 复制延迟可能超过几秒或者几分钟,下文是 3 个例子。
5.2.1 读己之写
如果用户把数据提交到了主库,但是主从有延迟,用户马上看数据的时候请求的从库,会感觉到数据丢失。
此时需要「读写一致性」,也成为读己之写一致性。 技术: ● 读用户可能已经修改过的内容时,都从主库读;比如读个人资料都从主库读,读别人的资料可以读从库。 ● 如果应用的部分内容都可能被用户编辑,上述方法无效。可以指定更新后的时间窗口,比如上次更新的一分钟内从主库读。 ● 客户端记住最近一次写入的时间戳,从库提供查询时,保证该时间戳前的变更都已经传播到了本从库;否则从另外的从库读,或者等待从库追赶上来。(时间戳可以是逻辑时间戳,如日志序列号;或者要有准确的时间同步) ● 如果副本在多个数据中心,则比较复杂。任何需要从领导者提供服务的请求,都必须路由到包含主库的数据中心。 用户有多个设备时,还要考虑的问题: ● 记录更新时间戳变得更困难; ● 不同设备可能路由到不同的数据中心。如果你的方法需要读主库,就需要把同一用户的请求路由到同一个数据中心。
5.2.2 单调读
用户可能会遇到时光倒流。 第一次请求到从库看到了评论,第二次请求到另外一个从库发现评论消失。
单调读保证了这种异常不会发生。 方法: ● 确保每个用户总是从同一副本来读取。比如基于用户 ID 的散列来选择副本,而不是随机选。 ● 但是如果该副本失败,则需要路由到另一个副本。
5.2.3 一致前缀读
一系列事件可能出现前后顺序不一致问题。比如回答可能在提问之前发生。 这是分区(分片)数据库中的一个特殊问题:不同分区之间独立,不存在全局写入顺序。
需要「一致前缀读」。 方法: ● 任何因果相关的写入都写入相同的分区。
5.2.4 复制延迟的解决方案
● 可以信赖数据库:需要事务。 ● 事务(transaction) 存在的原因:数据库通过事务提供强大的保证,所以应用程序可以更加简单。 ● 单节点事务存在了很长时间,但是分布式数据库中,许多系统放弃了事务。“因为事务的代价太高。” ● 本书的其余部分将继续探讨事务。
5.3 多主复制
● 单个领导者的复制架构是个常见的方法,也有其他架构。 ● 基于领导者复制的主要缺点:只有一个主库,所有的写入都要通过它。 ● 多个领导者的复制:允许多个节点接受写入,复制仍然是转发给所有其他节点。每个领导者也是其他领导者的追随者。
5.3.1 多主复制的应用场景
5.3.1.1 运维多个数据中心
● 多领导配置允许每个数据中心都有自己的主库。 ● 每个数据中心内部使用常规的主从复制; ● 数据中心之间,每个数据中心的主库都会将其更改复制到其他数据中心的主库中。
运维多个数据中心时,单主和多主的适应情况比较:
性能
● 单主配置中,每个写入都得穿过互联网,进入主库所在的数据中心。会增大写入时间。
● 多主配置中,每个写操作都可以在本地数据中心进行处理,与其他数据中心异步复制。感觉到性能更好。
容忍数据中心停机
● 单主配置中,如果主库所在的数据中心发生故障,必须让另一个数据中心的追随者成为主领导者。
● 多主配置中,每个数据中心都可以独立于其他数据中心继续运行。若发生故障的数据中心归队,复制会自动赶上。
容忍网络问题
● 数据中心之间的网络需要通过公共互联网,不如数据中心之内的本地网络可靠。
● 单主配置对网络连接问题非常敏感,因为写是同步的。
● 异步复制的多主配置更好地承受网络问题。
多主复制的缺点: ● 两个数据中心可能会修改相同的内容,写冲突必须解决。
● 多主复制比较危险,应尽可能避免。
5.3.3.2 需要离线操作的客户端
● 多主复制的另一适用场景:应用程序在断网后仍然需要继续工作。
● 在这种情况下,每个设备都有一个充当领导者的本地数据库(它接受写请求),并且在所有设备上的日历副本之间同步时,存在异步的多主复制过程。复制延迟可能是几小时甚至几天,具体取决于何时可以访问互联网。
● 每个设备相当于一个“数据中心”
5.3.3.3 协同编辑
● 协作式编辑不能视为数据库复制问题,但是与离线编辑有许多相似
● 一个用户编辑文档时,所做的更改将立即应用到其本地副本(web 或者客户端),并异步复制到服务器和编辑同一文档的任何其他用户。
● 如果想要不发生编辑冲突,则应用程序需要先将文档锁定,然后用户才能进行编辑;如果另一用户想编辑,必须等待第一个用户提交修改并释放锁定。这种协作模式相当于主从复制模型下在主节点上执行事务操作。
● 但是,为了加速写作,可编辑的粒度需要非常小(例如单个按键,甚至全程无锁)。
● 也会面临所有多主复制都存在的挑战,即如何解决冲突。
5.3.4 处理写入冲突
● 多领导者复制的最大问题是可能发生写冲突,因此需要解决冲突。
● 单主数据库没有这个问题。
● 假如两个用户同时修改标题:
5.3.4.1 同步与异步冲突检测
● 单主数据库:第二个写入被阻塞,并等待第一个写入完成,或被终止;
● 多主配置:两个写入都成功,稍后的时间点仅仅异步地监测到冲突。
● 如果想冲突检测同步-等待被写入到所有的副本,那么丢失了多主复制的优点。
5.3.4.2 避免冲突
● 处理冲突的最简单策略是避免它们:确保特定记录的写入都通过同一个领导者,就不会有冲突。
● 但是,如果更改指定的记录主库——比如数据中心故障,需要把流量重新路由;冲突避免会中断,必须处理不同主库同时写入的可能性。
5.3.4.3 收敛至一致的状态
● 单主数据库按顺序进行写操作:如果同一个字段有多个更新,则最后一个写操作将决定该字段的最终值。
● 在多主配置中,没有明确的写入顺序,所以最终值应该是什么并不清楚。
● 每个复制方案都必须确保数据在所有副本中最终都是相同的。
● 数据库必须以一种 收敛(convergent) 的方式解决冲突,这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。
实现冲突合并解决有多种途径:
● 给每个写入一个唯一的ID(例如,一个时间戳,一个长的随机数,一个UUID或者一个键和值的哈希),挑选最高ID的写入作为胜利者,并丢弃其他写入。
● 为每个副本分配一个唯一的ID,ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
● 以某种方式将这些值合并在一起 - 例如,按字母顺序排序,然后连接它们
● 用一种可保留所有信息的显式数据结构来记录冲突,并编写解决冲突的应用程序代码(也许通过提示用户的方式)。
5.3.4.4 自定义冲突解决逻辑
解决冲突的最合适方法取决于应用程序。
写时执行
● 只要数据库系统检测到复制更改日志中存在冲突,就会调用冲突处理程序。
读时执行
● 当检测到冲突时,所有冲突写入被存储。
● 下一次读取数据时,会将这些多个版本的数据返回给应用程序。
● 应用程序可能会提示用户或自动解决冲突,并将结果写回数据库。
5.3.4.5 自动冲突解决
规则复杂,容易出错。
● 无冲突复制数据类型(Conflict-free replicated datatypes):是可以由多个用户同时编辑的集合,映射,有序列表,计数器等的一系列数据结构,它们以合理的方式自动解决冲突。一些CRDT已经在Riak 2.0中实现
● 可合并的持久数据结构(Mergeable persistent data structures)显式跟踪历史记录,类似于Git版本控制系统,并使用三向合并功能(而CRDT使用双向合并)。
● 可执行的转换(operational transformation)是 Etherpad 和Google Docs 等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的,例如构成文本文档的字符列表。
5.3.4.6 什么是冲突?
● 显而易见的冲突:两个写操作并发地修改了同一条记录中的同一个字段。
● 微秒的冲突:一个房间接受了两个预定。
5.3.5 多主复制拓扑
● 复制拓扑(replication topology)描述写入从一个节点传播到另一个节点的通信路径。
● 只有两个领导者时,只有一个合理的拓扑:互相写入。
● 当有两个以上的领导,拓扑很多样:
● 最普遍的是全部到全部;
● MySQL 仅支持环形拓扑。
防止无限复制循环:
● 圆形和星型拓扑,节点需要转发从其他节点收到的数据更改。
● 防止无限复制循环:每个节点都有唯一的标识符,在复制日志中,每个写入都标记了所有已经过的节点的标识符。
环形和星形拓扑的问题
● 一个节点故障,可能中断其他节点之间的复制消息流。
● 拓扑结构可以重新配置,但是需要手动操作。
● 全部到全部的容错性更好,避免单点故障。
全部到全部拓扑的问题
● 网络问题导致消息顺序错乱
● 写入时添加时间戳是不够的的。
● 解决办法是版本向量技术。
● 有些数据库没有该功能。
5.4 无主复制
● 一些数据库放弃主库的概念,允许任何副本直接接收来自客户端的写入。
● 一些无主配置中,客户端直接写入到几个副本中;
● 另一些情况下,一个协调者节点代表客户端进行写入。
5.4.1 当节点故障时写入数据库
5.4.1.1 读修复和反熵
5.4.1.2 读修复(Read repair)
5.4.1.3 反熵过程(Anti-entropy process)
5.4.1.4 读写的法定人数
计算方式
5.4.2 法定人数一致性的局限性
但是,即使在 $w + r> n$ 的情况下,也可能存在返回陈旧值的边缘情况。
● 如果使用了宽松的法定人数,w 个写入和 r 个读取落在完全不同的节点上。
● 两个写入同时发生,不清楚哪一个先发生。
● 写操作和读操作同时发生,写操作可能仅反映在某些副本上。
● 写操作在某些副本上成功,而在其他节点上失败,在小于w个副本上写入成功。
● 如果携带新值的节点失败,需要读取其他带有旧值的副本。
● 即使一切工作正常,有时也会不幸地出现关于时序(timing) 的边缘情况。
不要把 w 和 r 当做绝对的保证,应该看做是概率。
强有力的保证需要事务和共识。
5.4.2.1 监控陈旧度
● 基于领导者的复制,数据库会会公开复制滞后的度量标准,可以做监控。
● 无领导者复制中,没有固定的写入顺序,监控困难。
● 最终一致性是非常模糊的保证。
5.4.3 宽松的法定人数与提示移交
● 合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障。
● 需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景来说,这些特性使无主复制的数据库很有吸引力。
问题 ● 网络中断导致剩余可用节点可能少于w或r,客户端达不到法定人数。
权衡
● 对于所有无法达到w或r节点法定人数的请求,是否返回错误是更好的?
● 或者我们是否应该接受写入,然后将它们写入一些可达的节点,但不在这些值通常所存在的n个节点上?
宽松的法定人数(sloppy quorum)
● 上述的后者是宽松的法定人数(sloppy quorum)。
● 大型集群中,节点数量明显多于 n 个。
● 写和读仍然需要 w 和 r 个成功的响应,但是不来自指定的 n 个节点中。
提示移交(hinted handoff)
● 网络中断得到解决时,另一个节点临时接收的一个节点的任何写入都被发送到适当的“主”节点。
优点
● 提高了写入可用性:任何 w 个节点可用,数据库就可以接收写入。
缺点
● 即使当$w + r> n$时,也不能确定读取某个键的最新值,因为最新的值可能已经临时写入了n之外的某些节点。
在传统意义上,一个宽松的法定人数实际上不是一个法定人数。
常见使用中,宽松的法定人数是可选的。
5.4.3.1 运维多个数据中心
● 无主复制也适用于多数据中心操作,因为它旨在容忍冲突的并发写入,网络中断和延迟尖峰。
● 无论数据中心如何,每个来自客户端的写入都会发送到所有副本,但客户端通常只等待来自其本地数据中心内的法定节点的确认,从而不会受到跨数据中心链路延迟和中断的影响。
● 对其他数据中心的高延迟写入通常被配置为异步发生,尽管配置有一定的灵活性.
5.4.4 检测并发写入
● 无主复制,允许多个客户端同时写入相同的 key,会冲突。
● 读修复和提示移交期间也可能会发生冲突。
写入顺序问题举例:
5.4.4.1 最后写入胜利(丢弃并发写入)
思路
● 只需要存储最 “最近” 的值,允许 “更旧” 的值被覆盖和抛弃。
● 需要有一种明确的方式来确定哪个写是“最近的”,并且每个写入最终都被复制到每个副本,那么复制最终会收敛到相同的值。
● “最近”的,这个词没有意义,因为是并发的。
方法:最后写入胜利
● 可以为每个写入附加一个时间戳,挑选最 “最近” 的最大时间戳,并丢弃具有较早时间戳的任何写入。
优点
● 实现了最终收敛的目标
缺点
● 以持久性为代价:如果同一个Key有多个并发写入,即使它们报告给客户端的都是成功(因为它们被写入 w 个副本),也只有一个写入将存活,而其他写入将被静默丢弃。
● 甚至可能会删除不是并发的写入
● 如果丢失数据不可接受,那么最后写入胜利是个很烂的选择。
使用场景
● 唯一安全的方法:每一个键只写入一次,然后视为不变,避免并发更新。
“此前发生”的关系和并发
● 只要有两个操作A和B,就有三种可能性:A在B之前发生,或者B在A之前发生,或者A和B并发。
● 我们需要的是一个算法来告诉我们两个操作是否是并发的。
● 如果一个操作发生在另一个操作之前,则后面的操作应该覆盖较早的操作,但是如果这些操作是并发的,则存在需要解决的冲突。
5.4.4.2 捕获"此前发生"关系
一个算法,可以确定两个操作是否是并发的,还是先后关系。 两个客户端同时向一个购物车添加项目,注意版本号:
操作依赖关系:
● 客户端永远不会完全掌握服务器上的数据,因为总是有另一个操作同时进行。
● 但是,旧版本的值最终会被覆盖,并且不会丢失任何写入。
服务器可以通过查看版本号来确定两个操作是否是并发的,算法的原理:
● 服务器为每个键保留一个版本号,每次写入键时都增加版本号,并将新版本号与写入的值一起存储。
● 当客户端读取键时,服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须读取。
● 客户端写入键时,必须包含之前读取的版本号,并且必须将之前读取的所有值合并在一起。 (针对写入请求的响应可以像读取请求一样,返回所有当前值,这使得我们可以像购物车示例那样将多个写入串联起来。)
● 当服务器接收到具有特定版本号的写入时,它可以覆盖该版本号或更低版本的所有值(因为它知道它们已经被合并到新的值中),但是它必须用更高的版本号来保存所有值(因为这些值与随后的写入是并发的)。
当一个写入包含前一次读取的版本号时,它会告诉我们的写入是基于之前的哪一种状态。
5.4.4.3 合并同时写入的值
优点
● 没有数据被无声地丢弃
缺点
● 客户端需要额外工作:客户端必须通过合并并发写入的值来擦屁股。
Riak 称这些并发值为兄弟。
合并兄弟值:
● 与多领导者复制的冲突解决相同的问题。
● 最简单的是根据版本号或者时间戳最后写入胜利,但会丢失数据。
● 对于购物车来说,合理的合并方法是集合求并集。
● 但是如果从购物车中删除东西,那么求并集会出错:一个购物车删除,求并集后,会重新出现在并集终值中。
● 所以删除操作不能简单删除,需要留下有合适版本号的标记,被称为墓碑。
容易出错,所以有了一些数据结构设计出来。
5.4.4.4 版本向量
多个副本,但是没有领导者,该怎么办?
● 每个副本、每个主键都定义一个版本号。
● 每个副本在处理写入时增加自己的版本号,并且跟踪从其他副本中看到的版本号。
● 这个信息指出了要覆盖哪些值,以及保留哪些值作为兄弟。
版本向量
● 所有副本的版本号集合称为版本向量(version vector)。
● 版本向量允许数据库区分覆盖写入和并发写入。
5.5 本章小结
复制可以用于几个目的:
高可用性
即使在一台机器(或多台机器,或整个数据中心)停机的情况下也能保持系统正常运行
断开连接的操作
允许应用程序在网络中断时继续工作
延迟
将数据放置在距离用户较近的地方,以便用户能够更快地与其交互
可伸缩性
能够处理比单个机器更高的读取量可以通过对副本进行读取来处理
我们讨论了复制的三种主要方法:
单主复制
客户端将所有写入操作发送到单个节点(领导者),该节点将数据更改事件流发送到其他副本(追随者)。读取可以在任何副本上执行,但从追随者读取可能是陈旧的。
多主复制
客户端发送每个写入到几个领导节点之一,其中任何一个都可以接受写入。领导者将数据更改事件流发送给彼此以及任何跟随者节点。
无主复制
客户端发送每个写入到几个节点,并从多个节点并行读取,以检测和纠正具有陈旧数据的节点。
我们研究了一些可能由复制滞后引起的奇怪效应,我们也讨论了一些有助于决定应用程序在复制滞后时的行为的一致性模型:
写后读
用户应该总是看到自己提交的数据。
单调读
用户在一个时间点看到数据后,他们不应该在某个更早的时间点看到数据。
一致前缀读
用户应该将数据视为具有因果意义的状态:例如,按照正确的顺序查看问题及其答复。
最后,我们讨论了多领导者和无领导者复制方法所固有的并发问题:因为他们允许多个写入并发发生,这可能会导致冲突。我们研究了一个数据库可能使用的算法来确定一个操作是否发生在另一个操作之前,或者它们是否同时发生。我们还谈到了通过合并并发更新来解决冲突的方法。
第六章: 分区
什么是分区? ● 对于非常大的数据集,或非常高的吞吐量,仅仅进行复制是不够的:我们需要将数据进行分区(partitions),也称为分片(sharding)。 ● 通常情况下,每条数据(每条记录,每行或每个文档)属于且仅属于一个分区。 ● 每个分区都是自己的小型数据库,尽管数据库可能支持同时进行多个分区的操作。
分区的优点? ● 分区主要是为了可伸缩性。 ● 大数据集可以分布在多个磁盘上,并且查询负载可以分布在多个处理器上。 ● 单个分区上运行的查询,每个节点可以独立执行对自己的查询,因此可以通过添加更多的节点来扩大查询吞吐量。 ● 大型、复杂的查询可能会跨越多个节点并行处理,尽管这也带来了新的困难。
本章内容 ● 分割大型数据集的不同方法 ● 索引如何与分区配合 ● 分区再平衡 ● 数据库如何路由到正确的分区
分区与复制
● 分区通常与复制结合使用,使得每个分区的副本存储在多个节点上。 ● 即使每条记录属于同一个分区,但是这个分区仍有多个不同的节点,提高容错。 ● 一个节点有多个分区,如果使用主从复制模型,每个分区领导者被分配给一个节点,追随者被分配个其他节点。 ○ 每个节点可能是某些分区的领导者,同时是其他分区的追随者。
键值数据的分区
● 分区目标是将数据和查询负载均匀分布在各个节点上。 ● 如果每个节点公平分享数据和负载,那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量(暂时忽略复制)。 ● 如果分区不公平,被称为偏斜(skew) ○ 数据偏斜的存在使分区效率下降很多。 ○ 在极端的情况下,所有的负载可能压在一个分区上,其余9个节点空闲的,瓶颈落在这一个繁忙的节点上。 ○ 不均衡导致的高负载的分区被称为热点(hot spot)。
怎么避免热点? ● 避免热点最简单的方法是将记录随机分配给节点。 ● 缺点: ○ 读特定的值时,不知道在哪个节点上,必须并行查所有的节点。
根据键的范围分区
一种分区的方法是为每个分区指定一块连续的键范围(从最小值到最大值),类似纸质的百科全书。
● 可能分布不均匀。 ● 分区边界可以由管理员手动选择,也可以由数据库自动选择 ● 使用该策略的有:Bigtable, HBase,RethinkDB和2.4版本之前的MongoDB
优点: ● 在每个分区中,我们可以按照一定的顺序保存键。 ● 范围扫描非常简单 ● 可以将键作为联合索引来处理,以便在一次查询中获取多个相关记录 ● 比如获取一段时间内的记录。
缺点: ● Key Range分区的缺点是某些特定的访问模式会导致热点。 ● 可一个修改主键:比如传感器名称+时间,避免数据打到同一分区。
根据键的散列分区
● 很多分布式数据存储使用散列函数来分区。 ● 一个好的散列函数可以将偏斜的数据均匀分布。 ● 注意保证同一个键在不同的进程中有相同的哈希值。
优点: ● 这种技术擅长在分区之间公平地分配键。 ● 分区边界可以是均匀间隔的,也可以是伪随机选择的(在这种情况下,该技术有时也被称为一致性哈希(consistent hashing))。
缺点: ● 失去了 高效执行范围查询的能力。 ● 范围查询要么不支持,要么需要查询所有分区。
组合索引: ● 组合索引方法为一对多关系提供了一个优雅的数据模型。 ● 社交网络的一条更新主键被选择为 (user_id, update_timestamp),那么可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。
负载偏斜与热点消除
● 哈希分区可以帮助减少热点。但是,它不能完全避免它们:在极端情况下,所有的读写操作都是针对同一个键的,所有的请求都会被路由到同一个分区。 ● 比如社交网络的大 V 的评论区。 ● 只能靠应用程序解决: ○ 比如,一个主键如果被认为非常火爆,一个简单的方法是在主键的开始或结尾添加一个随机数。 ○ 只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键,从而存储在不同的分区中。 ○ 缺点: ■ 任何读取都要读取 100 个主键,读取数据并合并。 ■ 还要记录哪些键需要被分割
分区与次级索引
● 之前讨论的都是键值数据模型。 ● 次级索引使情况变复杂: ○ 次级索引通常并不能唯一地标识记录,而是一种搜索记录中出现特定值的方式 ● 次级索引是关系型数据库的基础,并且在文档数据库中也很普遍。 ● 许多键值存储(如HBase和Volde-mort)为了减少实现的复杂度而放弃了次级索引; ● 但是一些(如Riak)已经开始添加它们,因为它们对于数据模型实在是太有用了。 ● 并且次级索引也是Solr和Elasticsearch等搜索服务器的基石。
存在的问题: ● 次级索引的问题是它们不能整齐地映射到分区。 ● 有两种用二级索引对数据库进行分区的方法:基于文档的分区(document-based) 和基于关键词(term-based)的分区。
基于文档的二级索引进行分区
● 假如一个销售二手车的网站, 每个列表都有一个唯一的ID——称之为文档ID——并且用文档ID对数据库进行分区 ● 用户搜索汽车,允许他们通过颜色和厂商过滤,所以需要一个在颜色和厂商上的次级索引(文档数据库中这些是字段(field),关系数据库中这些是列(column) )。
特点: ● 分区完全独立:每个分区维护自己的二级索引 ● 只需处理包含您正在编写的文档ID的分区即可 ● 文档分区索引也被称为本地索引(local index)
注意: ● 没有理由把特定颜色或者品牌的汽车放到同一个分区。 ● 查询时需要查询所有的分区,合并所有的结果返回。
缺点: ● 查询分区数据库的方法有时被称为分散/聚集(scatter/gather); ● 可能使二级索引的查询代价高。 ● 即使并行查询分区,分散/聚集也容易导致尾部延迟放大。
然而被广泛使用:MongoDB,Riak ,Cassandra ,Elasticsearch ,SolrCloud 和VoltDB 【19】都使用文档分区二级索引。
基于关键词(Term)的二级索引进行分区
● 可以构建一个覆盖所有分区数据的全局索引,而不是给每个分区创建自己的次级索引(本地索引)。 ● 但是,我们不能只把这个索引存储在一个节点上,因为它可能会成为瓶颈,违背了分区的目的。 ● 全局索引也必须进行分区,但可以采用与主键不同的分区方式。 ● 下图是对二级索引按照首字母是否在 “[a, r]” 之间分区。
● 这种分区叫做关键词分区。 ● 以通过关键词本身或者它的散列进行索引分区。 ○ 根据关键词本身来分区对于范围扫描非常有用:比如数值类的属性。 ○ 对关键词的哈希分区提供了负载均衡的能力。 优点: ● 读取更有效率:不需要分散/收集所有分区,客户端只需要向包含关键词的分区发出请求。
缺点: ● 写入速度较慢且较为复杂,因为写入单个文档现在可能会影响索引的多个分区(文档中的每个关键词可能位于不同的分区或者不同的节点上) 。 ● 需要跨分区的分布式事务,并不是所有数据库都支持。 ● 在实践中,对全局二级索引的更新通常是异步的。
分区再平衡
随着时间的推移,数据库会有各种变化:
● 查询吞吐量增加,所以您想要添加更多的CPU来处理负载。 ● 数据集大小增加,所以您想添加更多的磁盘和RAM来存储它。 ● 机器出现故障,其他机器需要接管故障机器的责任。
所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡(rebalancing)。
无论使用哪种分区方案,再平衡通常都要满足一些最低要求:
● 再平衡之后,负载(数据存储,读取和写入请求)应该在集群中的节点之间公平地共享。 ● 再平衡发生时,数据库应该继续接受读取和写入。 ● 节点之间只移动必须的数据,以便快速再平衡,并减少网络和磁盘I/O负载。
再平衡策略
反面教材:hash mod N
● 前面已经讲了,最好将可能的散列分成不同的范围,给每个范围分配一个分区。 ● 取模 mod 运算可以给每个键分配一个节点 问题 ● 当节点数目变化时,使得再平衡过于昂贵。
固定数量的分区
● 简单的解决方案:创建比节点更多的分区,并为每个节点分配多个分区。 ● 仍然是取模,但是新增节点之后,总节点数变成了 5 个,只需要把取模 = 4 的部分放到 node 4。
优点 ● 只有分区在节点中移动。 ● 分区总数不变 ● 键所在的分区也不会改变 ● 唯一改变的是分区所在的节点 ● 变更不是及时的:在传输过程中,原有分区仍然接受读写操作。 ● 甚至可以解决硬件不匹配问题:更强大的节点分配更多的分区。 ● Riak ,Elasticsearch ,Couchbase 和Voldemort 中使用了这种再平衡的方法。
特点 ● 分区的数量通常在数据库第一次建立时确定,之后不会改变。 ● 一开始配置的分区数就是您可以拥有的最大节点数量,所以您需要选择足够多的分区以适应未来的增长。 ● 但是,每个分区也有管理开销,所以选择太大的数字会适得其反。
缺点 ● 当数据集的总大小难以预估,选择正确的分区数很难。
动态分区
采用关键字区间分区的数据库,如果边界设置有问题,可能导致数据倾斜到一个分区中。 ● 按键的范围进行分区的数据库(如HBase和RethinkDB)会动态创建分区。 ● 当分区增长到超过配置的大小时(在HBase上,默认值是10GB),会被分成两个分区,每个分区约占一半的数据。 ● 与之相反,如果大量数据被删除并且分区缩小到某个阈值以下,则可以将其与相邻分区合并。此过程与B树顶层发生的过程类似。
特点: ● 每个分区分配给一个节点,每个节点可以处理多个分区,就像固定数量的分区一样。 ● 大型分区拆分后,可以将其中的一半转移到另一个节点,以平衡负载。 ● 在HBase中,分区文件的传输通过HDFS(底层使用的分布式文件系统)来实现。
优点: ● 分区数量适应总数据量。
缺点: ● 空数据库从一个分区开始,导致所有写入都必须单个节点处理,其他节点空闲。
解决方法: ● HBase和MongoDB允许在一个空的数据库上配置一组初始分区(这被称为预分割(pre-splitting))。 ● 在键范围分区的情况中,预分割需要提前知道键是如何进行分配的。
适用情况: ● 动态分区不仅适用于数据的范围分区,而且也适用于散列分区。
按节点比例分区
● 动态分区和固定数量的分区,分区数量都与节点数量无关。 ● Cassandra和Ketama使用的第三种方法是使分区数与节点数成正比:每个节点有固定数量的分区。 ○ 当节点数不变,分区大小与数据集大小成比例增长; ○ 当节点数改变,分区大小将变小。
操作方式: ● 当一个新节点加入集群时,它随机选择固定数量的现有分区进行拆分,然后占有这些拆分分区中每个分区的一半,同时将每个分区的另一半留在原地。 ● 随机化可能会产生不公平的分割,但是平均在更大数量的分区上时,新节点最终从现有节点获得公平的负载份额。 ● 随机选择分区边界要求使用基于散列的分区(可以从散列函数产生的数字范围中挑选边界)。实际上,这种方法最符合一致性哈希的原始定义。
运维:手动还是自动再平衡
重要问题:自动还是手动进行? ● 完全自动重新平衡和完全手动之间有一个过渡阶段:自动生成建议的分区分配,需要管理员提交才能生效。
完全自动重新平衡的缺点: ● 虽然很方便,但是结果不可预测。 ● 再平衡的代价昂贵,因为它需要重新路由请求并将大量数据从一个节点移动到另一个节点。 ● 如果没有做好,这个过程可能会使网络或节点负载过重,降低其他请求的性能。 ○ 如果全自动重新平衡遇到了自动故障检测:系统判断一个节点过载,然后重新自动平衡,导致情况更糟。
请求路由
服务发现(service discovery) ● 确定客户发出请求时,知道要连接哪个节点进行读取
概括来说,这个问题有几种不同的方案(如图6-7所示):
- 允许客户联系任何节点(例如,通过循环策略的负载均衡(Round-Robin Load Balancer))。如果该节点恰巧拥有请求的分区,则它可以直接处理该请求;否则,它将请求转发到适当的节点,接收回复并传递给客户端。
- 首先将所有来自客户端的请求发送到路由层,它决定了应该处理请求的节点,并相应地转发。此路由层本身不处理任何请求;它仅负责分区的负载均衡。
- 要求客户端知道分区和节点的分配。在这种情况下,客户端可以直接连接到适当的节点,而不需要任何中介
关键问题: ● 如何了解分区-节点之间的分配关系变化? ● 解决方法:所有参与者达成共识。 ○ 分布式系统中有达成共识的协议,但很难被正确实现。
常见实现 ZooKeeper: ● 依赖于一个独立的协调服务,比如ZooKeeper来跟踪集群元数据 ● 每个节点在ZooKeeper中注册自己,ZooKeeper维护分区到节点的可靠映射。 ● 其他参与者(如路由层或分区感知客户端)可以在ZooKeeper中订阅此信息。 ● 只要分区分配发生了改变,或者集群中添加或删除了一个节点,ZooKeeper就会通知路由层使路由信息保持最新状态。
应用:
- 使用 ZooKeeper ○ LinkedIn的Espresso使用Helix 【31】进行集群管理(依靠ZooKeeper) ○ HBase,SolrCloud和Kafka也使用ZooKeeper来跟踪分区分配。 ○ MongoDB具有类似的体系结构,但它依赖于自己的配置服务器(config server) 实现和mongos守护进程作为路由层。
- 使用流言协议(gossip protocol) ○ Cassandra和Riak使用流言协议来传播集群状态的变化 ○ 请求可以发送到任意节点,该节点会转发到包含所请求的分区的适当节点 ○ 增加了更多的复杂性,但是避免了对像ZooKeeper这样的外部协调服务的依赖。
- 不自动重新平衡 ○ Couchbase,简化了设计 ○ 它配置了一个名为moxi的路由层,它会从集群节点了解路由变化
执行并行查询
● 目前,我们只关注读取或写入单个键的非常简单的查询(加上基于文档分区的二级索引场景下的分散/聚集查询)。也是大多数 NoSQL 分布式数据存储所支持的访问层级。 ● 通常用于分析的大规模并行处理(MPP, Massively parallel processing) 关系型数据库产品在其支持的查询类型方面要复杂得多。 ● 把多个连接,过滤,分组和聚合操作分解成多个执行阶段和分区,分布式并行执行。 ● 见第十章。
本章小结
● 数据量非常大的时候,在单台机器上存储和处理不再可行,而分区则十分必要。 ● 分区的目标是在多台机器上均匀分布数据和查询负载,避免出现热点(负载不成比例的节点)。 ● 这需要选择适合于您的数据的分区方案,并在将节点添加到集群或从集群删除时进行分区再平衡。
两种主要的分区方法:
- 键范围分区 ○ 其中键是有序的,并且分区拥有从某个最小值到某个最大值的所有键。 ○ 排序的优势在于可以进行有效的范围查询,但是如果应用程序经常访问相邻的键,则存在热点的风险。 ○ 在这种方法中,当分区变得太大时,通常将分区分成两个子分区,动态地再平衡分区。
- 散列分区 ○ 散列函数应用于每个键,分区拥有一定范围的散列。 ○ 这种方法破坏了键的排序,使得范围查询效率低下,但可以更均匀地分配负载。 ○ 通过散列进行分区时,通常先提前创建固定数量的分区,为每个节点分配多个分区,并在添加或删除节点时将整个分区从一个节点移动到另一个节点。也可以使用动态分区。
两种方法搭配使用也是可行的,例如使用复合主键: ● 使用键的一部分来标识分区,而使用另一部分作为排序顺序。
我们还讨论了分区和二级索引之间的相互作用。 次级索引也需要分区,有两种方法: ● 基于文档分区(本地索引),其中二级索引存储在与主键和值相同的分区中。 ○ 这意味着只有一个分区需要在写入时更新 ○ 但是读取二级索引需要在所有分区之间进行分散/收集。 ● 基于关键词分区(全局索引),其中二级索引存在不同的分区中。 ○ 辅助索引中的条目可以包括来自主键的所有分区的记录。 ○ 当文档写入时,需要更新多个分区中的二级索引; ○ 但是可以从单个分区中进行读取。 最后,我们讨论了将查询路由到适当的分区的技术,从简单的分区负载平衡到复杂的并行查询执行引擎。
第七章:事务
为什么有事务? ● 分布式数据系统,可能会出各种错误。 ● 实现容错机制工作量巨大。需要仔细考虑所有可能出错的事情,并进行大量的测试,以确保解决方案真正管用。 ● 数十年来,事务(transaction) 一直是简化这些问题的首选机制。
什么是事务? ● 事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。 ● 从概念上讲,事务中的所有读写操作被视作单个操作来执行: ○ 整个事务要么成功(提交(commit))要么失败(中止(abort),回滚(rollback))。 ○ 如果失败,应用程序可以安全地重试。 ○ 对于事务来说,应用程序的错误处理变得简单多了,因为它不用再担心部分失败的情况了,即某些操作成功,某些失败(无论出于何种原因)。
事务是天然存在的吗? ● 不是天然存在,是为了简化应用编程模型而创建的。 ● 给应用程序提供了安全保证。
事务必须存在吗? ● 不是所有应用都要有事务 ● 有时候弱化事务保证、或完全放弃事务也是有好处的(例如,为了获得更高性能或更高可用性)。 ● 一些安全属性也可以在没有事务的情况下实现。
怎样知道你是否需要事务? ● 首先需要确切理解事务可以提供的安全保障,以及它们的代价。 ● 尽管乍看事务似乎很简单,但实际上有许多微妙但重要的细节在起作用。
事务的棘手概念
● 几乎所有的关系型数据库和一些非关系数据库都支持事务。 ● 2000 年以后,非关系(NoSQL)数据库开始普及。很多新一代数据库放弃了或者弱化了事务。 ● 事务是一种权衡。
ACID的含义
● 原子性(Atomicity) ● 一致性(Consistency) ● 隔离性(Isolation) ● 持久性(Durability)
不同数据库的ACID实现并不相同。
原子性
原子是指不能分解成小部分的东西。
多线程编程 ● 如果一个线程执行一个原子操作,这意味着另一个线程无法看到该操作的一半结果。 ● 系统只能看到操作前或者操作后的状态,而不能看到中间状态。
ACID 的原子性 ● ACID的原子性并不是关于 并发(concurrent) 的。 ○ 隔离性 I 才是关于并发的。 ● ACID 的原子性是 能够在错误时中止事务,丢弃该事务进行的所有写入变更的能力。
原子性的用途 ● 原子性描述了当客户想进行多次写入,但在一些写操作处理完之后出现故障的情况 ● 如果这些写操作被分组到一个原子事务中,并且该事务由于错误而不能完成(提交),则该事务将被中止,并且数据库必须丢弃或撤消该事务中迄今为止所做的任何写入。
为什么要有原子性? ● 如果没有原子性,在多处更改进行到一半时发生错误,很难知道哪些更改已经生效,哪些没有生效。该应用程序可以再试一次,但冒着进行两次相同变更的风险,可能会导致数据重复或错误的数据。 ● 原子性简化了这个问题:如果事务被中止(abort),应用程序可以确定它没有改变任何东西,所以可以安全地重试。
一致性
● ACID一致性的概念是,对数据的一组特定约束必须始终成立。即不变量(invariants)。 ○ 例如在会计系统中,所有账户整体上必须借贷相抵。 ● 如果一个事务开始于一个满足这些不变量的有效数据库,且在事务处理期间的任何写入操作都保持这种有效性,那么可以确定,不变量总是满足的。一致性不属于数据库的属性。 ● 一致性取决于应用程序对不变量的理解,应用程序负责正确定义它的事务,并保持一致性。 ● 这并不是数据库可以保证的事情:如果你写入违反不变量的脏数据,数据库也无法阻止你。—— 数据库只管存储。 ● 原子性,隔离性和持久性是数据库的属性,而一致性(在ACID意义上)是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性,但这并不仅取决于数据库。因此,字母C不属于ACID。
隔离性
● 多个客户端同时访问相同的数据库记录,可能会遇到并发问题。 ● ACID意义上的隔离性意味着,同时执行的事务是相互隔离的:它们不能相互冒犯。 ● 传统的数据库教科书将隔离性形式化为可串行化(Serializability),这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。 ● 数据库确保当多个事务被提交时,结果与它们串行运行(一个接一个)是一样的,尽管实际上它们可能是并发运行的
持久性
● 持久性 是一个承诺,即一旦事务成功完成,即使发生硬件故障或数据库崩溃,写入的任何数据也不会丢失。
在单节点数据库中 ● 持久性通常意味着数据已被写入非易失性存储设备,如硬盘或SSD。 ● 它通常还包括预写日志或类似的文件(请参阅“让B树更可靠”),以便在磁盘上的数据结构损坏时进行恢复。
在带复制的数据库中 ● 持久性可能意味着数据已成功复制到一些节点。
如何做到持久性? ● 为了提供持久性保证,数据库必须等到这些写入或复制完成后,才能报告事务成功提交。 ● 完美的持久性是不存在的:万一所有硬盘和备份同时被销毁。
单对象和多对象操作
客户端在同一事务中执行多次写入时,数据库应该做的事: 原子性 ○ 不会部分失败——保证 all-or-nothing 隔离性 ○ 同时运行的事务不应该互相干扰。 ■ 事务如果多次写入,要么事务看到全部写入结果,要么什么都看不到。
通常需要多对象事务(multi-object transaction) 来保持多个数据对象的同步。
一个邮件应用的例子: ● 执行以下查询来显示用户未读邮件数量:
|
|
● 如果邮件太多,觉得查询太慢,于是用了单独的字段存储未读邮件的数量。现在每当一个新消息写入时,必须也增长未读计数器,每当一个消息被标记为已读时,也必须减少未读计数器。 ● 异常情况: ○ 邮件列表里显示有未读消息,但计数器显示为零未读消息,因为计数器增长还没有发生
为了满足原子性:插入邮件和更新未读邮件数目需要状态一致,要么都成功,要么都失败(回滚):
多对象事务写入方法? ● 需要某种方式来确定哪些读写操作属于同一个事务。 ● 在关系型数据库中,通常基于客户端与数据库服务器的TCP连接:在任何特定连接上,BEGIN TRANSACTION 和 COMMIT 语句之间的所有内容,被认为是同一事务的一部分(不完美)。 ● 许多非关系数据库,并没有将这些操作组合在一起的方法。所以可能让数据库处于部分更新的状态。
单对象写入
● 当单个对象发生改变时,原子性和隔离性也是适用的。 ● 存储引擎一个几乎普遍的目标是:对单节点上的单个对象(例如键值对)上提供原子性和隔离性。
实现方法 ● 原子性可以通过使用日志来实现崩溃恢复 ● 可以使用每个对象上的锁来实现隔离(每次只允许一个线程访问对象)
更高级的原子操作 ● 1. 自增操作。 ● 2. 比较和设置(CAS, compare-and-set) 操作,仅当值没有被其他并发修改过时,才允许执行写操作。 ● 上面两种对但对象操作有用,但不是通常意义上的事务。 ● 事务通常被理解为,将多个对象上的多个操作合并为一个执行单元的机制。
多对象事务的必要性
为什么许多分布式数据存储已经放弃了多对象事务? ● 多对象事务很难跨分区实现; ● 而且在需要高可用性或高性能的情况下,它们可能会碍事。
问题: 我们是否需要多对象事务?是否有可能只用键值数据模型和单对象操作来实现任何应用程序?
需要协调写入几个不同对象的场景: ● 关系数据模型中,一个表中的行通常具有对另一个表中的行的外键引用。 ● 在文档数据模型中,需要一起更新的字段通常在同一个文档中,这被视为单个对象——更新单个文档时不需要多对象事务。但是,当需要更新非规范化的信息时,需要一次更新多个文档。比如上面邮件未读数目的例子。 ● 在具有二级索引的数据库中(除了纯粹的键值存储以外几乎都有),每次更改值时都需要更新索引。
没有原子性,错误处理就要复杂得多,缺乏隔离性,就会导致并发问题。
处理错误和中止
● 事务的一个关键特性是,如果发生错误,它可以中止并安全地重试。 ● ACID数据库基于这样的哲学:如果数据库有违反其原子性,隔离性或持久性的危险,则宁愿完全放弃事务,而不是留下半成品。 ● 但并不是所有的系统都遵循这个哲学。特别是具有无主复制的数据存储,主要是在“尽力而为”的基础上进行工作。——所以,从错误中恢复是应用程序的责任。
重试一个中止的事务并不完美: ● 如果事务实际上成功了,但是在服务器试图向客户端确认提交成功时网络发生故障,那么重试事务导致事务执行了两次——除非有额外的应用级除重机制。 ● 如果错误是由于负载过大造成的,则重试事务将使问题变得更糟,而不是更好。需要限制重试次数、采用指数退避算法。 ● 仅在临时性错误(例如,由于死锁,异常情况,临时性网络中断和故障切换)后才值得重试。在发生永久性错误(例如,违反约束)之后重试是毫无意义的。 ● 如果事务在数据库之外也有副作用,即使事务被中止,也可能发生这些副作用。比如更新操作后附带发送电子邮件。(如果想让多个不同的系统同时提交或者放弃,需要两阶段提交。) ● 如果客户端在重试过程中也失败了,并且没有其他人负责重试,那么数据就会丢失。
弱隔离级别
并发问题发生的条件: ● 如果两个事务不触及相同的数据,那么可以安全的并行执行。 ● 只有两个事务中一读一写或者同时写,才会出现并发问题。
并发问题很难测试、推理、复现。
事务隔离(transaction isolation) ● 数据库试图通过事务隔离来解决并发问题 ● 理论上讲,隔离可以假装没有并发,让数据库保证事务的执行结果与串行相同。
实际上的事务隔离 ● 由于串行隔离会有性能损失,许多数据库不愿意牺牲性能。 ● 因此,系统通常使用较弱的隔离级别来防止一部分,而不是全部的并发问题。 ● 这些隔离级别难以理解,并且会导致微妙的错误,但是它们仍然在实践中被使用
弱事务隔离级别导致的问题 ● 弱事务隔离级别造成了很多的资金损失,耗费了财务审计人员的调查,并导致客户数据被破坏。 ● 即使是很多流行的关系型数据库系统(通常被认为是“ACID”)也使用弱隔离级别,所以它们也不一定能防止这些错误的发生。
那到底怎么解决并发问题? ● 比起盲目地依赖工具,我们应该对存在的并发问题的种类,以及如何防止这些问题有深入的理解。 ● 然后就可以使用我们所掌握的工具来构建可靠和正确的应用程序。
读已提交
最基本的事务隔离级别是读已提交(Read Committed),它提供了两个保证:
- 从数据库读时,只能看到已提交的数据(没有脏读(dirty reads))。
- 写入数据库时,只会覆盖已经写入的数据(没有脏写(dirty writes))。 没有脏读 什么是脏读? ● 设想一个事务已经将部分数据写入数据库,但事务还没有提交或中止。另一个事务可以看到未提交的数据吗?如果是的话,那就叫做脏读(dirty reads)。 ● 在读已提交隔离级别运行的事务必须防止脏读。这意味着事务的任何写入操作只有在该事务成功提交后,才能被其他人看到(并且所有的写入操作都会立即变得可见)。 ○ 比如 user1 设置了 x=3, 但是直到 user1 的事务提交前, user2 的 get x 依然返回旧值 2,
为什么要防止脏读? ● 如果事务需要更新多个对象,脏读取意味着另一个事务可能会只看到一部分更新。比如上文中电子邮件的未读数目的例子。 ● 如果事务中止,则所有写入操作都需要回滚。脏读导致其他事务看到稍后需要回滚的数据。
没有脏写 什么是脏写? ● 两个事务同时更新数据库的相同对象,通常是后面的写入覆盖前面的。但如果先前的写入是尚未提交事务的一部分,后面的写入会覆盖一个尚未提交的值?如果是,这被称作脏写(dirty write)。 ● 在读已提交的隔离级别上运行的事务必须防止脏写,通常是延迟第二次写入,直到第一次写入事务提交或中止为止。
为什么要防止脏写? ● 如果事务更新多个对象,脏写会导致非预期的错误结果。 ○ Alice 和 Bob 同事购买一辆车,买车需要两次数据库写入:商品列表更新、开发票。 ○ 下图中,Alice 先更新了商品列表,但是被 Bob 覆盖了商品列表;Bob 先更新了开发票,但是被 Alice 覆盖。
● 但是,读已提交不能防止本章第一个图中的两个计数器增量之间的竞争状态。第二次写入在第一个事务提交后,所以它不是一个脏写。但结果仍然不正确。后文中“防止更新丢失”中将探讨如何使这种计数器安全递增。
实现读已提交
● 读已提交是一个非常流行的隔离级别。这是Oracle 11g,PostgreSQL,SQL Server 2012,MemSQL和其他许多数据库的默认设置
怎么实现读已提交? ● 最常见的情况是,数据库通过使用行锁(row-level lock) 来防止脏写: ○ 当事务想要修改特定对象(行或文档)时,它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。 ○ 一次只有一个事务可持有任何给定对象的锁; ○ 如果另一个事务要写入同一个对象,则必须等到第一个事务提交或中止后,才能获取该锁并继续。 ○ 这种锁定是读已提交模式(或更强的隔离级别)的数据库自动完成的。
如何防止脏读? ● 一种选择是读写使用相同的锁,并要求任何想要读取对象的事务来简单地获取该锁,然后在读取之后立即再次释放该锁。 ● 这能确保在读取进行时,对象不会在脏的、有未提交的值的状态(因为在那段时间锁会被写入该对象的事务持有)。
读锁的缺点? ● 读锁在实际上并不可行。 ● 一个长时间运行的写入事务会迫使许多只读事务等到这个慢写入事务完成。 ● 因为等待锁,应用某个部分的迟缓可能由于连锁效应,导致其他部分出现问题。
实际方法 ● 大多数数据库使用图 7-4 的方法防止脏读 ● 对于写入的每个对象,数据库都会记住旧的已提交值,和由当前持有写入锁的事务设置的新值。 ● 当事务正在进行时,任何其他读取对象的事务都会拿到旧值。 ● 只有当新值提交后,事务才会切换到读取新值。
快照隔离和可重复读
读已提交隔离级别的表现: ● 它允许中止(原子性的要求); ● 它防止读取不完整的事务结果,并且防止并发写入造成的混乱。
但,仍然有问题可能导致并发错误:
● 图7-6 读取偏差:Alice观察数据库处于不一致的状态
○ Alice 有 1000 美元,分为两个账户 ○ 先查了账户 1,发现有 500 块 ○ 一个事务把账户 2 的钱转了 100 到账户 1 ○ 再查了账户 2,发现只有 400 块 ○ 导致 Alice 误以为总的只有 900 块 ● 这种异常被称为不可重复读(nonrepeatable read) 或读取偏差(read skew) ○ Alice 再次查询账户 1 的时候,会看到与之前不同的值 ○ 在读已提交的隔离条件下,不可重复读被认为是可接受的:Alice看到的帐户余额确实是当时的最新值。
有些情况不可以接受上述暂时的不一致: 备份 ● 大型数据库备份会几个小时才能完成,如果备份时数据库仍然接受写入操作,那么备份就可能有一些新的部分和旧的部分。 ● 从这样的备份中恢复,那么数据不一致会变成永久的。 分析查询和完整性检查 ● 一个分析需要查询数据库的大部分内容,如果不同时间点的查询结果不一样,那就没意义。
快照隔离(snapshot isolation) ● 解决上述问题的最常见方案 ● 想法是,每个事务都从数据库的一致快照(consistent snapshot) 中读取。——也就是说,事务可以看到事务开始时在数据库中提交的所有数据。 ● 即使这些数据随后被另一个事务更改,每个事务也只能看到该特定时间点的旧数据。 ● 优点: ○ 快照隔离对长时间运行的只读查询(如备份和分析)非常有用。 ○ 如果查询的数据在查询执行的同时发生变化,则很难理解查询的含义。有快照理解起来就容易了。 ● 快照隔离是一个流行的功能:PostgreSQL,使用InnoDB引擎的MySQL,Oracle,SQL Server等都支持
实现快照隔离
思路 ● 与读取提交的隔离类似,快照隔离的实现通常使用写锁来防止脏写。 ● 这意味着进行写入的事务会阻止另一个事务修改同一个对象。 ● 但是读取不需要任何锁定。 ● 从性能的角度来看,快照隔离的一个关键原则是:读不阻塞写,写不阻塞读。 ● 这允许数据库在处理一致性快照上的长时间查询时,可以正常地同时处理写入操作。且两者间没有任何锁定争用。
实现 ● 通常使用防止图 7-4 的脏读 ● 数据库必须可能保留一个对象的几个不同的提交版本,因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。 ● 因为它同时维护着单个对象的多个版本,所以这种技术被称为多版本并发控制(MVCC, multi-version concurrency control)。
保留几个版本的快照? ● 如果一个数据库只需要提供读已提交的隔离级别,而不提供快照隔离,那么保留一个对象的两个版本就足够了:提交的版本和被覆盖但尚未提交的版本。 ● 支持快照隔离的存储引擎通常也使用MVCC来实现读已提交隔离级别。一种典型的方法是读已提交为每个查询使用单独的快照,而快照隔离对整个事务使用相同的快照。
举个例子 ● 下图是 PostgreSQL中实现基于MVCC的快照隔离(其他实现类似) ● 当一个事务开始时,它被赋予一个唯一的,永远增长的事务ID(txid)。 ● 每当事务向数据库写入任何内容时,它所写入的数据都会被标记上写入者的事务ID。
● 说明: ○ 表中的每一行都有一个 created_by 字段,其中包含将该行插入到表中的的事务ID。 ○ 此外,每行都有一个 deleted_by 字段,最初是空的。 ○ 如果某个事务删除了一行,那么该行实际上并未从数据库中删除,而是通过将 deleted_by 字段设置为请求删除的事务的ID来标记为删除。 ○ 在稍后的时间,当确定没有事务可以再访问已删除的数据时,数据库中的垃圾收集过程会将所有带有删除标记的行移除,并释放其空间。 ○ UPDATE 操作在内部翻译为 DELETE 和 INSERT 。
观察一致性快照的可见性规则
对于一个事务 ID,哪些对象时可见的? ● 当一个事务从数据库中读取时,事务ID用于决定它可以看见哪些对象,看不见哪些对象。通过仔细定义可见性规则,数据库可以向应用程序呈现一致的数据库快照。 ● 工作如下: ○ 在每次事务开始时,数据库列出当时所有其他(尚未提交或尚未中止)的事务清单,即使之后提交了,这些事务已执行的任何写入也都会被忽略。 ○ 被中止事务所执行的任何写入都将被忽略。 ○ 由具有较晚事务ID(即,在当前事务开始之后开始的)的事务所做的任何写入都被忽略,而不管这些事务是否已经提交。 ○ 所有其他写入,对应用都是可见的。 ● 这些规则适用于创建和删除对象。 ● 换句话说,如果以下两个条件都成立,则可见一个对象: ○ 读事务开始时,创建该对象的事务已经提交。 ○ 对象未被标记为删除,或如果被标记为删除,请求删除的事务在读事务开始时尚未提交。
长时间运行的事务看到的记录是新的还是旧的? ● 长时间运行的事务可能会长时间使用快照,并继续读取(从其他事务的角度来看)早已被覆盖或删除的值。 ● 由于从来不原地更新值,而是每次值改变时创建一个新的版本,数据库可以在提供一致快照的同时只产生很小的额外开销。
索引和快照隔离
索引如何在多版本数据库中工作? ● 一种选择是使索引简单地指向对象的所有版本,并且需要索引查询来过滤掉当前事务不可见的任何对象版本。 ● 当垃圾收集删除任何事务不再可见的旧对象版本时,相应的索引条目也可以被删除。
实践中的索引实现细节决定了多版本并发控制的性能。 ● 如果同一对象的不同版本可以放入同一个页面中,PostgreSQL的优化可以避免更新索引。 ● 在CouchDB,Datomic和LMDB中使用另一种方法。虽然它们也使用B树,但它们使用的是一种仅追加/写时拷贝(append-only/copy-on-write) 的变体,它们在更新时不覆盖树的页面,而为每个修改页面创建一份副本。从父页面直到树根都会级联更新,以指向它们子页面的新版本。任何不受写入影响的页面都不需要被复制,并且保持不变。 ● 使用仅追加的B树,每个写入事务(或一批事务)都会创建一颗新的B树。当创建时,从该特定树根生长的树就是数据库的一个一致性快照。没必要根据事务ID过滤掉对象,因为后续写入不能修改现有的B树;它们只能创建新的树根。但这种方法也需要一个负责压缩和垃圾收集的后台进程。
可重复读与命名混淆
● 快照隔离是一个有用的隔离级别,特别对于只读事务而言。 ● 但是,许多数据库实现了它,却用不同的名字来称呼。 ○ 在Oracle中称为可串行化(Serializable) 的 ○ 在PostgreSQL和MySQL中称为可重复读(repeatable read) ● 这种命名混淆的原因是SQL标准没有快照隔离的概念,因为标准是基于System R 1975年定义的隔离级别,那时候快照隔离尚未发明。相反,它定义了可重复读,表面上看起来与快照隔离很相似。 ● 后续虽然有可重复度的正式定义,但是结果现在命名混乱了。
防止丢失更新
● 上文讨论了读已提交和快照隔离级别,主要保证了只读事务在并发写入时可以看到什么,另外一个重要的事务并发场景是脏写。 ● 并发事务还有丢失更新(lost update) 问题,如图7-1所示。
什么情况下会发生丢失更新问题? ● 从数据库中读取一些值,修改它并写回修改的值(读取-修改-写入序列),则可能会发生丢失更新的问题。 ● 如果两个事务同时执行,则其中一个的修改可能会丢失,因为第二个写入的内容并没有包括第一个事务的修改(有时会说后面写入狠揍(clobber) 了前面的写入)。
下面是解决方案。
原子写
● 很多数据库提供了原子更新操作,从而消除在应用程序代码中执行读取-修改-写入序列的需要。 ● 这通常是最好的解决方案。
举例,下面的指令在大多数关系数据库中是并发安全的:
|
|
原子写的实现方法 ● 原子操作通常通过在读取对象时,获取其上的排它锁来实现。 ○ 使得更新完成之前,没有其他事务可以读取它。 ○ 这种技术有时被称为游标稳定性(cursor stability) ● 另一个选择是简单地强制所有的原子操作在单一线程上执行
使用时请注意 ● ORM框架很容易意外地执行不安全的读取-修改-写入序列,而不是使用数据库提供的原子操作。 ● 经常产出很难测出来的微妙 bug
显式锁定
● 如果数据库不支持内置原子操作,另一种防止更新丢失的方法是有应用程序显式地锁定将要更新的对象。 ● 然后应用程序可以执行读取-修改-写入序列,如果任何其他事务尝试同时读取同一个对象,则强制等待,直到第一个读取-修改-写入序列完成。
举例:多人棋子游戏 ● 多个玩家可以同时移动相同的棋子。 ● 一个原子操作可能是不够的,因为应用程序还需要确保玩家的移动符合游戏规则 ● 可以使用锁来防止两名玩家同时移动相同的棋子
|
|
● FOR UPDATE 子句告诉数据库应该对该查询返回的所有行加锁。 这是有效的,但要做对,你需要仔细考虑应用逻辑。忘记在代码某处加锁很容易引入竞争条件。
自动检测丢失的更新
● 原子操作和锁是通过强制读取-修改-写入序列按顺序发生,来防止丢失更新的方法。 ● 还可以允许并发执行,如果事务管理器检测到丢失更新,则中止事务并强制它们重试其读取-修改-写入序列。
优点 ● 数据库可以结合快照隔离高效地执行此检查。 ○ PostgreSQL的可重复读,Oracle的可串行化和SQL Server的快照隔离级别,都会自动检测到丢失更新,并中止惹麻烦的事务。 ○ 但是,MySQL/InnoDB的可重复读并不会检测丢失更新。导致有人认为 MySQL 不提供快照隔离。 ● 数据库自动检查!应用代码不需要任何操作就能使用丢失更新检测。很棒!
比较并设置(CAS)
● 有些不提供事务的数据库中,提供了一种原子操作:比较并设置(CAS, Compare And Set) ● 此操作的目的是为了避免丢失更新: ○ 只有当前值从上次读取时一直未改变,才允许更新发生。 ○ 如果当前值与先前读取的值不匹配,则更新不起作用,且必须重试读取-修改-写入序列。
举例: 为了防止两个用户同时更新同一个wiki页面,可以尝试类似这样的方式,只有当页面从上次读取之后没有发生变化时,才会发生更新:
|
|
注意 ● 如果更新失败,需要应用层重试。 ● 如果数据库的 WHERE子句从旧快照中读取,则此语句可能无法防止丢失更新,因为即使发生了另一个并发写入,WHERE条件也可能为真。在依赖数据库的CAS操作前要检查其安全运行条件。
冲突解决和复制
● 在复制数据库中,防止丢失的更新需要考虑另一个维度:由于在多个节点上存在数据副本,并且在不同节点上的数据可能被并发地修改,因此需要采取一些额外的步骤来防止丢失更新。
锁和CAS操作的缺点 ● 锁和CAS操作假定只有一个最新的数据副本。 ● 但是多主或无主复制的数据库通常允许多个写入并发执行,并异步复制到副本上,因此无法保证只有一个最新数据的副本。 ● 所以基于锁或CAS操作的技术不适用于这种情况。
复制数据库解决冲突的常用方法 ● 复制数据库中的一种常见方法是允许并发写入创建多个冲突版本的值(也称为兄弟),并使用应用代码或特殊数据结构在事实发生之后解决和合并这些版本。
原子操作的适用条件 ● 原子操作可以在复制的上下文中很好地工作,尤其当它们具有可交换性时(即,可以在不同的副本上以不同的顺序应用它们,且仍然可以得到相同的结果)。
最后写入胜利(LWW)的缺点 ● 最后写入胜利(LWW)的冲突解决方法很容易丢失更新。 ● 不幸的是,LWW是许多复制数据库中的默认方案。
写入偏斜与幻读
● 前面讨论的脏写和丢失更新,都是不同事务并发地尝试写入相同的对象时,会出现这两种竞争条件。 ● 除此之外,还有其他场景的并发问题,比如修改不同的对象。
一个医生轮班管理程序的例子 ● 背景:医院通常会同时要求几位医生待命,但底线是至少有一位医生在待命。医生可以放弃他们的班次(例如,如果他们自己生病了),只要至少有一个同事在这一班中继续工作。 ● 场景:Alice和Bob是两位值班医生,同时请假:
○ 应用首先检查是否有两个或以上的医生正在值班; ■ 如果是的话,它就假定一名医生可以安全地休班。由于数据库使用快照隔离,两次检查都返回 2 ,所以两个事务都进入下一个阶段。 ■ Alice更新自己的记录休班了,而Bob也做了一样的事情。 ■ 两个事务都成功提交了,现在没有医生值班了。 ■ 违反了至少有一名医生在值班的要求。
写偏差的特征
● 这种异常称为写偏差。它既不是脏写,也不是丢失更新,因为这两个事务正在更新两个不同的对象(Alice和Bob各自的待命记录)。
问题一般化: ● 如果两个事务读取相同的对象,然后更新其中一些对象(不同的事务可能更新不同的对象),则可能发生写入偏差。 ● 在多个事务更新同一个对象的特殊情况下,就会发生脏写或丢失更新(取决于时序)。
处理写偏差,我们能用的方法很少,原因: ● 由于涉及多个对象,单对象的原子操作不起作用。 ● 不幸的是,在一些快照隔离的实现中,自动检测丢失更新对此并没有帮助。目前的可重复读、快照隔离级别中,都不会自动检测写入偏差。自动防止写入偏差需要真正的可串行化隔离 ● 某些数据库允许配置约束,然后由数据库强制执行(例如,唯一性,外键约束或特定值限制)。但是为了指定至少有一名医生必须在线,需要一个涉及多个对象的约束。大多数数据库没有内置对这种约束的支持,但是你可以使用触发器,或者物化视图来实现它们,这取决于不同的数据库
解决办法: ● 如果无法使用可串行化的隔离级别,则此情况下的次优选项可能是显式锁定事务所依赖的行。
|
|
● 和以前一样,FOR UPDATE告诉数据库锁定返回的所有行以用于更新。
写偏差的更多例子 会议室预订系统 ● 防止会议室被同一个会议室多次预定,需要检查时间是否有重叠。 ● 快照级别隔离不安全的 SQL:
|
|
快照隔离并不能防止另一个用户同时插入冲突的会议。为了确保不会遇到调度冲突,你又需要可串行化的隔离级别了。
多人游戏 ● 可以用锁防止丢失更新(也就是确保两个玩家不能同时移动同一个棋子)。 ● 但是锁定并不妨碍玩家将两个不同的棋子移动到棋盘上的相同位置,或者采取其他违反游戏规则的行为。 ● 按照您正在执行的规则类型,也许可以使用唯一约束(unique constraint),否则您很容易发生写入偏差。
抢注用户名 ● 在每个用户拥有唯一用户名的网站上,两个用户可能会尝试同时创建具有相同用户名的帐户。 ● 快照隔离下这是不安全的。 ● 幸运的是,唯一约束是一个简单的解决办法(第二个事务在提交时会因为违反用户名唯一约束而被中止)。
防止双重开支 ● 允许用户花钱或积分的服务,需要检查用户的支付数额不超过其余额。 ● 可以通过在用户的帐户中插入一个试探性的消费项目来实现这一点。 ● 有了写入偏差,可能会发生两个支出项目同时插入,一起导致余额变为负值。但这两个事务各自都不超额。 导致写入偏差的幻读 上述所有例子遵循类似的模式: ● 一个SELECT查询找出符合条件的行,并检查是否符合一些要求。 ● 按照第一个查询的结果,应用代码决定是否继续。 ● 如果应用决定继续操作,就执行写入(插入、更新或删除),并提交事务。 ○ 这个写入的效果改变了步骤2 中的先决条件。换句话说,如果在提交写入后,重复执行一次步骤1 的SELECT查询,将会得到不同的结果。
解决方法: ● 医生值班的例子中,在步骤3中修改的行,是步骤1中返回的行之一,所以我们可以通过锁定步骤1 中的行(SELECT FOR UPDATE)来使事务安全并避免写入偏差。 ● 但是其他四个例子是不同的:它们检查是否不存在某些满足条件的行,写入会添加一个匹配相同条件的行。如果步骤1中的查询没有返回任何行,则SELECT FOR UPDATE锁不了任何东西。
幻读 ● 一个事务中的写入改变另一个事务的搜索查询的结果,被称为幻读。 ● 快照隔离避免了只读查询中幻读,但是在像我们讨论的例子那样的读写事务中,幻读会导致特别棘手的写入偏差情况。
物化冲突 ● 如果幻读的问题是没有对象可以加锁,也许可以人为地在数据库中引入一个锁对象? ● 例如,在会议室预订的场景中,可以想象创建一个关于时间槽和房间的表。 ● 要创建预订的事务可以锁定(SELECT FOR UPDATE)表中与所需房间和时间段对应的行。在获得锁定之后,它可以检查重叠的预订并像以前一样插入新的预订。 ● 这种方法被称为物化冲突(materializing conflicts),因为它将幻读变为数据库中一组具体行上的锁冲突
缺点: ● 弄清楚如何物化冲突可能很难,也很容易出错,而让并发控制机制泄漏到应用数据模型是很丑陋的做法 ● 出于这些原因,如果没有其他办法可以实现,物化冲突应被视为最后的手段。
在大多数情况下。可串行化(Serializable) 的隔离级别是更可取的。
可串行化
读已提交和快照隔离级别会阻止某些竞争条件,但并非对所有情况都有效。我们遇到了一些特别棘手的例子,写入偏差和幻读。面临的挑战: ● 隔离级别难以理解,并且在不同的数据库中实现的不一致 ● 光检查应用代码很难判断在特定的隔离级别运行是否安全。 特别是在大型应用程序中,您可能并不知道并发发生的所有事情。 ● 没有检测竞争条件的好工具。并发问题的测试是很难的,因为它们通常是非确定性的 —— 只有在倒霉的时序下才会出现问题。
研究人员给出的答案: ● 使用可串行化(serializable) 的隔离级别!
可串行化(Serializability) ● 可串行化(Serializability) 隔离通常被认为是最强的隔离级别。 ● 它保证即使事务可以并行执行,最终的结果也是一样的,就好像它们没有任何并发性,连续挨个执行一样。 ● 因此数据库保证,如果事务在单独运行时正常运行,则它们在并发运行时继续保持正确 —— 换句话说,数据库可以防止所有可能的竞争条件。
本章介绍可串行化技术: ● 字面意义上地串行顺序执行事务 ● 两阶段锁定(2PL, two-phase locking),几十年来唯一可行的选择 ● 乐观并发控制技术,例如可串行化快照隔离(serializable snapshot isolation)
真的串行执行
● 避免并发问题的最简单方法就是完全不要并发:在单个线程上按顺序一次只执行一个事务。 ● 但数据库设计人员在2007年左右才决定,单线程循环执行事务是可行的。 ● 原因: ○ RAM足够便宜了,许多场景现在都可以将完整的活跃数据集保存在内存中。 ○ 数据库设计人员意识到OLTP事务通常很短,而且只进行少量的读写操作。而长时间运行的分析查询通常是只读的,因此它们可以在串行执行循环之外的一致快照(使用快照隔离)上运行。 ● 串行执行事务的方法在VoltDB/H-Store,Redis和Datomic中实现
优点: ● 设计用于单线程执行的系统有时可以比支持并发的系统更好,因为它可以避免锁的协调开销。 缺点: ● 但是其吞吐量仅限于单个CPU核的吞吐量。 ● 为了充分利用单一线程,需要与传统形式的事务不同的结构。
在存储过程中封装事务
● 不能把人类做出决定和回应的多个流程操作封装成一个事务(比如搜路线、选机票、付款),因为人类太慢。 ● 交互式的事务中,为了提高吞吐量,必须允许数据库并发处理。 ● 采用单线程串行事务处理的系统不允许交互式的多语句事务。这就要求应用程序必须提前将整个事务代码作为存储过程提交给数据库。 ● 下图表示 交互式事务和存储过程之间的区别(使用图7-8的示例事务)
存储过程的优点和缺点
存储过程名声不好的原因: ● 每个数据库厂商都有自己的存储过程语言,而不是通用语言如 Java。 ● 数据库代码管理困难,调试困难,版本控制困难。 ● 数据库通常比应用服务器对性能敏感的多,数据库中一个写得不好的存储过程(例如,占用大量内存或CPU时间)会比在应用服务器中相同的代码造成更多的麻烦。
克服方法: ● 现代的存储过程实现放弃了PL/SQL,而是使用现有的通用编程语言:Java 和 Lua 等。
单线程执行事务变得可行: ● 存储过程与内存存储,使得在单个线程上执行所有事务变得可行。由于不需要等待I/O,且避免了并发控制机制的开销,它们可以在单个线程上实现相当好的吞吐量。 ● VoltDB还使用存储过程进行复制
分区 ● 顺序执行导致写入吞吐比较高的应用,单线程事务处理器可能成为一个严重的瓶颈。
解决方法: ● 分区,每个分区就可以拥有自己独立运行的事务处理线程。
缺点: ● 需要访问多个分区的任何事务,数据库必须在触及的所有分区之间协调事务。 ● 存储过程需要跨越所有分区锁定执行,以确保整个系统的可串行性。 ● 跨分区事务比单分区事务慢得多! ● 事务能否分区取决于应用数据的结构:kv 存储容易分区,但是多个二级索引的数据不方便分区。
串行执行小结 特定情况下,真的串行执行事务,已经成为一种实现可串行化隔离等级的可行办法。 使用条件: ● 每个事务都必须小而快,只要有一个缓慢的事务,就会拖慢所有事务处理。 ● 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘,但如果需要在单线程执行的事务中访问,系统就会变得非常慢。 ● 写入吞吐量必须低到能在单个CPU核上处理,否则需要分区,但最好没有跨分区事务。 ● 跨分区事务也可以支持,但是占比必须小。
两阶段锁定
● 大约30年来,在数据库中只有一种广泛使用的串行化算法:两阶段锁定(2PL,two-phase locking) ● 之前我们看到锁通常用于防止脏写; ● 两阶段锁定类似,但是锁的要求更强得多。 ○ 只要没有写入,就允许多个事务同时读取同一个对象。 ○ 但对象只要有写入(修改或删除),就需要独占访问(exclusive access) 权限: ■ 如果事务A读取了一个对象,并且事务B想要写入该对象,那么B必须等到A提交或中止才能继续。 (这确保B不能在A底下意外地改变对象。) ■ 如果事务A写入了一个对象,并且事务B想要读取该对象,则B必须等到A提交或中止才能继续。 (像图7-1那样读取旧版本的对象在2PL下是不可接受的。)
特点 ● 在2PL中,写入不仅会阻塞其他写入,也会阻塞读,反之亦然。快照隔离使得读不阻塞写,写也不阻塞读,这是2PL和快照隔离之间的关键区别。 ● 另一方面,因为2PL提供了可串行化的性质,它可以防止早先讨论的所有竞争条件,包括丢失更新和写入偏差。
实现两阶段锁
使用场景 2PL用于MySQL(InnoDB)和SQL Server中的可串行化隔离级别,以及DB2中的可重复读隔离级别 实现方式 读与写的阻塞是通过为数据库中每个对象添加锁来实现的。 锁可以处于共享模式(shared mode) 或独占模式(exclusive mode)。 锁使用如下:(同一个锁有两种模式:共享模式和独占模式,独占模式优先级大于共享模式) 若事务要读取对象,则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有独占锁,则这些事务必须等待。 若事务要写入一个对象,它必须首先以独占模式获取该锁。不允许其他事务可以同时持有该锁(无论是共享模式还是独占模式)。换言之,如果对象上存在任何锁,则修改事务必须等待。 如果事务先读取再写入对象,则它可能会将其共享锁升级为独占锁。升级锁的工作等价于直接获得独占锁。 事务获得锁之后,必须继续持有锁直到事务结束(提交或中止)。这就是“两阶段”这个名字的来源:第一阶段(当事务正在执行时)获取锁,第二阶段(在事务结束时)释放所有的锁。 可能会发生死锁: 数据库会自动检测事务之间的死锁,并中止其中一个,以便另一个继续执行。 被中止的事务需要由应用程序重试。 两阶段锁定的性能 两阶段锁定的巨大缺点:性能问题 两阶段锁定下的事务吞吐量与查询响应时间要比弱隔离级别下要差得多。 性能差的原因: 这一部分是由于获取和释放所有这些锁的开销,但更重要的是由于并发性的降低。 按照设计,如果两个并发事务试图做任何可能导致竞争条件的事情,那么必须等待另一个完成。 性能差的表现: 运行2PL的数据库可能具有相当不稳定的延迟,如果在工作负载中存在争用,那么可能高百分位点处的响应会非常的慢 可能只需要一个缓慢的事务,或者一个访问大量数据并获取许多锁的事务,就能把系统的其他部分拖慢,甚至迫使系统停机。当需要稳健的操作时,这种不稳定性是有问题的。 死锁导致的问题: 基于2PL实现的可串行化隔离级别中,死锁会出现的频繁的多(取决于事务的访问模式)。 死锁发生时,需要把事务中止并被重试。这导致额外的性能问题。 谓词锁 具有可串行化隔离级别的数据库必须防止幻读。 如何防止会议室重复预定(即如果一个事务在某个时间窗口内搜索了一个房间的现有预定,则另一个事务不能同时插入或者更新同一个时间窗口内、同一房间的另一个约定) 实现方式 我们需要一个谓词锁(predicate lock)。它类似于前面描述的共享/排它锁,但不属于特定的对象(例如,表中的一行),它属于所有符合某些搜索条件的对象,如:
|
|
谓词锁限制访问的方式: ● 如果事务A想要读取匹配某些条件的对象,就像在这个 SELECT 查询中那样,它必须获取查询条件上的共享谓词锁(shared-mode predicate lock)。如果另一个事务B持有任何满足这一查询条件对象的排它锁,那么A必须等到B释放它的锁之后才允许进行查询。 ● 如果事务A想要插入,更新或删除任何对象,则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务B持有匹配的谓词锁,那么A必须等到B已经提交或中止后才能继续。
关键思想 ● 谓词锁甚至适用于数据库中尚不存在,但将来可能会添加的对象(幻象)。 ● 如果两阶段锁定包含谓词锁,则数据库将阻止所有形式的写入偏差和其他竞争条件,因此其隔离实现了可串行化。
索引范围锁
● 谓词锁性能不佳:如果活跃事务持有很多锁,检查匹配的锁会非常耗时。 ● 大多数使用2PL的数据库实际上实现了索引范围锁(也称为间隙锁(next-key locking)),这是一个简化的近似版谓词锁。
索引范围锁: ● 对查询对象的索引加锁。 ● 比如,room_id列上有一个索引,并且/或者在start_time 和 end_time上有索引;那么在查询的时候,在查询时,将某个具体对象的索引加上锁,比如给 room_id =123的索引加锁,那么其他事务就没法获取到此索引的锁,导致无法插入、更新、删除。
优点: ● 这种方法能够有效防止幻读和写入偏差。 ● 虽然索引范围锁并不像谓词锁那样精确(它们可能会锁定更大范围的对象,而不是维持可串行化所必需的范围),但是由于它们的开销较低,所以是一个很好的折衷。
如果没有索引,怎么加索引范围锁? ● 退化到整个表上的共享锁 ● 对性能不利,但是比较安全。
可串行化快照隔离
本章讨论了关于数据库的并发控制的黯淡画面: ● 一方面,我们实现了性能不好(2PL)或者伸缩性不好(串行执行)的可串行化隔离级别。 ● 另一方面,我们有性能良好的弱隔离级别,但容易出现各种竞争条件(丢失更新,写入偏差,幻读等)。
串行化的隔离级别和高性能是从根本上相互矛盾的吗? ● 也许不是:一个称为可串行化快照隔离(SSI, serializable snapshot isolation) 的算法是非常有前途的。
可串行化快照隔离 ● 它提供了完整的可串行化隔离级别,但与快照隔离相比只有很小的性能损失。 ● SSI是相当新的:它在2008年首次被提出。 ● 既用于单节点数据库(PostgreSQL9.1 以后的可串行化隔离级别)和分布式数据库(FoundationDB使用类似的算法)。
悲观与乐观的并发控制
● 两阶段锁是一种所谓的悲观并发控制机制(pessimistic) :它是基于这样的原则:如果有事情可能出错(如另一个事务所持有的锁所表示的),最好等到情况安全后再做任何事情。 ● 串行化快照隔离是一种乐观(optimistic) 的并发控制技术。 ○ 乐观意味着,如果存在潜在的危险也不阻止事务,而是继续执行事务,希望一切都会好起来。 ○ 当一个事务想要提交时,数据库检查是否有什么不好的事情发生(即隔离是否被违反);如果是的话,事务将被中止,并且必须重试。只有可串行化的事务才被允许提交。
适用场景的思考: ● 如果存在很多争用(contention)(很多事务试图访问相同的对象),则表现不佳,因为这会导致很大一部分事务需要中止。 ● 但是,如果有足够的备用容量,并且事务之间的争用不是太高,乐观的并发控制技术往往比悲观的要好。
与早期的乐观并发控制技术的主要区别: ● SSI基于快照隔离——也就是说,事务中的所有读取都是来自数据库的一致性快照。 ● 在快照隔离的基础上,SSI添加了一种算法来检测写入之间的串行化冲突,并确定要中止哪些事务
基于过时前提的决策 ● 前文讨论的快照隔离中的写入偏差,是由于事务基于一个前提(premise) 采取行动,之后当事务要提交时,原始数据可能已经改变——前提可能不再成立。 ● 更好的办法是由数据库进行判断,而不是应用程序来判断。 ● 数据库如何知道查询结果是否可能已经改变?有两种情况需要考虑: ○ 检测对旧MVCC对象版本的读取(读之前存在未提交的写入) ○ 检测影响先前读取的写入(读之后发生写入)
检测旧MVCC读取 快照隔离出现写入偏差的原因: ● 快照隔离通常是通过多版本并发控制(MVCC;见图7-10)来实现的。当一个事务从MVCC数据库中的一致快照读时,它将忽略取快照时尚未提交的任何其他事务所做的写入。 ● 图7-10 检测事务何时从MVCC快照读取过时的值(关于医生值班请假的例子)
如何避免? ● 数据库需要跟踪一个事务由于MVCC可见性规则而忽略另一个事务的写入。当事务想要提交时,数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样,事务必须中止。
为什么等到提交时才检查和中止,而不是检测到读取陈旧数据就中止事务 43? ● 如果事务43 是只读事务,则不需要中止,因为没有写入偏差的风险。
检测影响之前读取的写入 第二种情况要考虑的是另一个事务在读取数据之后修改数据。 ● 图7-11 在可串行化快照隔离中,检测一个事务何时修改另一个事务的读取。
实现方法 ● SSI 采用和索引范围锁类似的技术,除了SSI锁不会阻塞其他事务。 ● 事务42 和43 都在班次1234 查找值班医生。如果在shift_id上有索引,则数据库可以使用索引项1234 来记录事务42 和43 读取这个数据的事实。此信息保留到所有事务处理完成即可。 ● 当事务写入数据库时,它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁,但锁并不会阻塞事务指导其他读事务完成,而是像警戒线一样只是简单通知其他事务:你们读过的数据可能不是最新的啦。 ● 当事务 43 想要提交时,发现来自事务42 的冲突写入已经被提交,所以事务43 必须中止。
可串行化快照隔离的性能 与两阶段锁定相比,可串行化快照隔离的优点: ● 一个事务不需要阻塞等待另一个事务所持有的锁。就像在快照隔离下一样,写不会阻塞读,反之亦然。 ● 这种设计原则使得查询延迟更可预测,变量更少。特别是,只读查询可以运行在一致快照上,而不需要任何锁定,这对于读取繁重的工作负载非常有吸引力。
与串行执行相比,可串行化快照隔离的优点: ● 并不局限于单个CPU核的吞吐量:FoundationDB将检测到的串行化冲突分布在多台机器上,允许扩展到很高的吞吐量。 ● 即使数据可能跨多台机器进行分区,事务也可以在保证可串行化隔离等级的同时读写多个分区中的数据。
使用场景 ● 中止率显著影响SSI的整体表现。例如,长时间读取和写入数据的事务很可能会发生冲突并中止,因此SSI要求同时读写的事务尽量短(只读的长事务可能没问题)。 ● SSI可能比两阶段锁定或串行执行更能容忍慢事务。
本章小结
事务的好处? ● 事务是一个抽象层,允许应用程序假装某些并发问题和某些类型的硬件和软件故障不存在。各式各样的错误被简化为一种简单情况:事务中止(transaction abort),而应用需要的仅仅是重试。
什么时候需要事务? ● 具有非常简单访问模式的应用(例如每次读写单条记录)可能无需事务管理。 ● 但是对于更复杂的访问模式,事务可以大大减少需要考虑的潜在错误情景数量。
本章讨论了什么? ● 本章深入讨论了并发控制的话题。 ● 我们讨论了几个广泛使用的隔离级别,特别是读已提交,快照隔离(有时称为可重复读)和可串行化。
竞争条件的例子 脏读 一个客户端读取到另一个客户端尚未提交的写入。读已提交或更强的隔离级别可以防止脏读。 脏写 一个客户端覆盖写入了另一个客户端尚未提交的写入。几乎所有的事务实现都可以防止脏写。 读取偏差(不可重复读) 在同一个事务中,客户端在不同的时间点会看见数据库的不同状态。快照隔离经常用于解决这个问题,它允许事务从一个特定时间点的一致性快照中读取数据。快照隔离通常使用多版本并发控制(MVCC) 来实现。 更新丢失 两个客户端同时执行读取-修改-写入序列。其中一个写操作,在没有合并另一个写入变更情况下,直接覆盖了另一个写操作的结果。所以导致数据丢失。快照隔离的一些实现可以自动防止这种异常,而另一些实现则需要手动锁定(SELECT FOR UPDATE)。 写偏差 一个事务读取一些东西,根据它所看到的值作出决定,并将该决定写入数据库。但是,写入时,该决定的前提不再是真实的。只有可串行化的隔离才能防止这种异常。 幻读 事务读取符合某些搜索条件的对象。另一个客户端进行写入,影响搜索结果。快照隔离可以防止直接的幻像读取,但是写入偏差上下文中的幻读需要特殊处理,例如索引范围锁定。
弱隔离级别可以防止其中一些异常情况,但要求你,也就是应用程序开发人员手动处理剩余那些(例如,使用显式锁定)。只有可串行化的隔离才能防范所有这些问题。我们讨论了实现可串行化事务的三种不同方法: 字面意义上的串行执行 如果每个事务的执行速度非常快,并且事务吞吐量足够低,足以在单个CPU核上处理,这是一个简单而有效的选择。 两阶段锁定 数十年来,两阶段锁定一直是实现可串行化的标准方式,但是许多应用出于性能问题的考虑避免使用它。 可串行化快照隔离(SSI) 一个相当新的算法,避免了先前方法的大部分缺点。它使用乐观的方法,允许事务执行而无需阻塞。当一个事务想要提交时,它会进行检查,如果执行不可串行化,事务就会被中止。
第八章: 分布式系统的挑战
分布式系统面临哪些挑战? ● 前面几章讨论的副本故障切换、复制延迟、事务控制; ● 本章讨论的不可靠网络、时钟和时序问题等等; ● 我们的假设:任何可能出错的东西都会出错。
故障与部分失效
● 单机上的软件比较稳定,要么功能完好,要么整个系统故障,而不是介于两者之间。 ● 分布式系统中,尽管系统的其他部分工作正常,但系统的某些部分可能会以某种不可预知的方式被破坏。这被称为部分失效(partial failure)。难点在于部分失效是不确定性的(nonderterministic)。
云计算与超级计算机
构建大型计算系统的方式: ● 一个极端是高性能计算(HPC)领域,具有数千个CPU的超级计算机通常用于计算密集型科学计算任务,比如天气预报; ● 另一个极端是云计算(cloud computing),通过很多主机相连接; ● 传统企业数据中心位于这两个极端之间。
超级计算机怎么处理故障? ● 超级计算机中,作业通常会不时地将计算存盘到持久存储中; ● 如果发生部分故障,那么通过修复、重启、重新加载继续计算的方式。 ● 类似于一个单节点计算机。
互联网服务的系统与超级计算机系统的区别?
互联网服务的系统 | 互联网服务的系统 超级计算机 |
---|---|
在线的,低延迟,不可重启 | 离线的,批处理,可以重启 |
基于 IP 和以太网 | 专门的网络拓扑 |
故障频发,需要很快的处理故障 | 可以花较多的时间从错误中恢复 |
普通硬件,较低成本,较高故障率 | 专用硬件,节点可靠,节点通过共享内存和远程直接内存访问(RDMA)进行通信 |
可以容忍发生故障的节点 | 不能容忍故障节点 |
地理位置分布发散,通信通过互联网,通信缓慢且不可靠 | 所有节点都靠近一起 |
构建分布式系统的思路? ● 接受部分故障的可能性,并在软件中建立容错机制。
不可靠的网络
怎么处理网络错误? ● 通常方法是超时(Timeout):在一段时间之后放弃等待,并且认为响应不会到达。 ● 但是,当发生超时时,你仍然不知道远程节点是否收到了请求(如果请求仍然在某个地方排队,那么即使发送者已经放弃了该请求,仍然可能会将其发送给接收者)。
真实世界的网络故障
● 真实世界很复杂,啥样的网络故障都可能发生。 ○ 机器损坏 ○ 人为操作错误
检测故障
为什么需要自动检测故障节点? ● 负载平衡器需要停止向已死亡的节点转发请求(即从移出轮询列表(out of rotation))。 ● 在单主复制功能的分布式数据库中,如果主库失效,则需要将从库之一升级为新主库
怎么判断一个节点是否工作? ● 网络的不确定性导致很难判断。 ● 特定场景下,故障节点可能有反馈信息: ○ 没有进程正在监听目标端口,操作系统将发送 FIN 或者 RST 关闭并重用 TCP 连接 ○ 节点进程崩溃,但操作系统仍在运行,脚本可以通知其他节点有关该崩溃的信息 ○ 通过数据中心网络交换机的管理界面,检测硬件级别的链路故障 ○ 路由器发现尝试连接的IP地址不可用,则可能会使用ICMP目标不可达数据包回复您。 ● 你不能指望这些信息,必须假设出错时得不到任何回应 ● 通过超时来检测
超时与无穷的延迟
超时应该得到多久? ● 没有答案
过短的超时可以吗? ● 如果一个节点实际上活着,另一个节点接管,可能造成动作执行了两次 ● 如果因为高负载导致响应缓慢,将其负载转移到其他节点可能会导致级联失效。
虚构的系统中,合理的超时时间? ● 假设数据包的最大延迟为 $d$,即要么在 $d$ 内完成交付,要么丢失 ● 假设非故障节点在 $r$ 时间内完成请求处理 ● 在这种情况下,您可以保证每个成功的请求在$2d + r$时间内都能收到响应。 ● $2d + r$ 会是一个合理的超时设置。
实际上,大多数系统都没有这些保证。
网络拥塞和排队
计算机网络上数据包延迟的可变性通常是由于排队:
怎么解决多租户数据中心的网络拥塞问题?
同步网络与异步网络
为什么我们不能在硬件层面上解决这个问题,使网络可靠,使软件不必担心呢?
以非常可靠的传统固定电话网络为例:
网络延迟可以预测吗?
● 电话网络的电路和 TCP 连接很不同: ○ 电路是固定数量的预留带宽 ○ TCP连接的数据包机会性地使用任何可用的网络带宽。 ○ 以太网和 IP 是分组交换协议,不得不忍受排队,以及其导致的无线延迟。 ■ 优点是可以应对不同速率的流量,也最大程度利用网络资源。 ● 当前部署的技术不允许我们对网络的延迟或可靠性作出任何保证:我们必须假设网络拥塞,排队和无限的延迟总是会发生。 ● 因此,超时时间没有“正确”的值——它需要通过实验来确定。
不可靠的时钟
时钟和时间很重要。应用程序以各种方式依赖于时钟来回答以下问题:
- 这个请求是否超时了?
- 这项服务的第99百分位响应时间是多少?
- 在过去五分钟内,该服务平均每秒处理多少个查询?
- 用户在我们的网站上花了多长时间?
- 这篇文章在何时发布?
- 在什么时间发送提醒邮件?
- 这个缓存条目何时到期?
- 日志文件中此错误消息的时间戳是什么?
时钟为什么不可靠?
● 分布式系统中,时间很棘手,因为通信不是即时的:网络延迟,并且不知道晚了多少时间,导致不知道事件发生的顺序。 ● 每个机器都有自己的时钟,是个硬件设备:石英晶体振荡器。但是该硬件不可靠,需要通过服务器进行同步。
单调钟与日历时钟
计算机至少有两种目的不一样的时钟: ● 日历时钟(time-of-day clock) ● 单调钟(monotonic clock)
日历时钟
日历时钟是什么? ● 直观了解时钟的依据:它根据某个日历(也称为挂钟时间(wall-clock time))返回当前日期和时间。 ● 例如 Linux上的clock_gettime(CLOCK_REALTIME) 和 Java中的System.currentTimeMillis() ● 通常与网络时间协议(NTP)同步
缺点: ● 不包括闰秒,所以不能测量 经过时间(elapsed time) ● 可能会被强制重置(比如与 NTP 时间差别很大的时候)
单调钟
是什么? ● 单调钟适用于测量持续时间(时间间隔) ● 例如超时或服务的响应时间:Linux上的clock_gettime(CLOCK_MONOTONIC),和Java中的System.nanoTime()都是单调时钟。 ● 名字来源:单调钟保证总是往前走的事实(而日历时钟可以往回跳)
怎么用? ● 计算时间差,即测量 经过时间(elapsed time) ● 单调钟的绝对值毫无意义:可能是任意值。
会修改吗? ● NTP 检测到计算机的本地石英钟比NTP服务器要更快或更慢,则可以调整单调钟向前走的频率(这称为偏移(skewing) 时钟)。 ● NTP允许时钟速率增加或减慢最高至0.05%,但NTP不能使单调时钟向前或向后跳转。
精确度? ● 分辨率很高,很精确 ● 几微秒或者更短的时间内测量时间间隔
在分布式系统中的作用? ● 在分布式系统中,使用单调钟测量经过时间(elapsed time)(比如超时)通常很好,因为它不假定不同节点的时钟之间存在任何同步,并且对测量的轻微不准确性不敏感。
时钟同步与准确性
● 单调钟不需要同步 ● 日历时钟需要通过 NTP 或者其他外部时间进行同步,但是!获取时钟的方法并不可靠和准确。
举例: ● 计算机中的石英钟不够精确:它会漂移(drifts)(运行速度快于或慢于预期)。时钟漂移取决于机器的温度。Google 假设如果机器一天同步一次时钟,漂移为 17 秒。 ● 如果计算机的时钟与NTP服务器的时钟差别太大,可能会拒绝同步,或者本地时钟将被强制重置。导致观察重置前后时间的应用程序傻眼了。 ● 如果与 NTP 服务器链接失败(比如防火墙),那么可能很长时间没有留意到错误配置最终导致同步失败。 ● NTP 服务器故障或出现配置错误。 ● 闰秒导致服务器崩溃了。处理闰秒的推荐方法是:NTP 把闰秒摊平均匀分布到一天。 ● 虚拟机中,突然卡了。导致时钟跳跃。 ● 用户故意调整硬件时钟,以规避游戏的时间限制。
依赖同步时钟
时钟导致的问题: ● 日历时钟可能会前后跳跃
处理方法: ● 需要健壮的软件来处理不正确的时钟 ● 时钟问题很难被发现:因此仔细监控所有机器之间的时钟偏移,把偏移太远的机器移除。
有序事件的时间戳
● 当依赖时钟对多个节点事件排序时,时钟尤其主要。 ● 下图显示了在具有多领导者复制的数据库中对时钟的危险使用:客户端B的写入比客户端A的写入要晚,但是B的写入具有较早的时间戳。
最后写入胜利(LWW) ● 上述冲突叫做最后写入胜利 ● 时间戳导致的问题: ○ 数据库写入可能会神秘地消失:被滞后时钟节点的数据覆盖了 ○ LWW无法区分高频顺序写入和真正并发写入。需要额外的因果关系跟踪机制(例如版本向量),以防止违背因果关系。 ○ 两个节点很可能独立地生成具有相同时间戳的写入,特别是在时钟仅具有毫秒分辨率的情况下。所以,需要一个额外的决胜值(tiebreaker)(可以简单地是一个大随机数),但这种方法也可能会导致违背因果关系。
能不能用NTP 同步避免不正确的排序? ● 不能 ● 精度问题,石英钟漂移,网络时延。
怎么避免时钟问题呢? ● 逻辑时钟(logic clock)是基于递增计数器而不是振荡石英晶体,对于排序事件来说是更安全的选择。 ● 逻辑时钟不测量一天中的时间或经过的秒数,而仅测量事件的相对顺序(无论一个事件发生在另一个事件之前还是之后)。 ● 相反,用来测量实际经过时间的日历时钟和单调钟也被称为物理时钟(physical clock)。 ● 将在「顺序保证」章节讨论。
时钟读数存在置信区间
● NTP 同步可能有几毫秒到 100 毫秒的偏移。 ● 时钟读数更像是个置信区间:一个系统可能以95%的置信度认为当前时间处于本分钟内的第10.3秒和10.5秒之间,它可能没法比这更精确了。 ● 但是大多数系统不告诉你误差范围查询的接口,你不知道时间的误差是多少! ● 不过 Spanner中的Google TrueTime API 明确地报告了本地时钟的置信区间:[最早,最晚]。
全局快照的同步时钟
● 「快照隔离和可重复读」章节中,讨论了快照隔离。它允许只读事务看到特定时间点的处于一致状态的数据库,且不会锁定和干扰读写事务。 ● 快照隔离最常见的实现需要单调递增的事务ID。如果写入比快照晚(即,写入具有比快照更大的事务ID),则该写入对于快照事务是不可见的。在单节点数据库上,一个简单的计数器就足以生成事务ID。 ● 但是当数据库分布在许多机器上,也许可能在多个数据中心中时,由于需要协调,(跨所有分区)全局单调递增的事务ID会很难生成。
可以使用同步时钟的时间戳作为事务ID吗? ● 理论上可以,实际上问题在于时钟精度的不确定性 ● Spanner以这种方式实现跨数据中心的快照隔离,它使用的是时间的置信区间。 ● 除此之外,没有主流数据库在分布式语义中使用时钟同步。
进程暂停
设想一个单领导者的分布式数据库,一个节点怎么知道自己仍然是领导者? ● 一种选择是领导者从其他节点获得一个租约(lease),类似一个带超时的锁。 ● 任一时刻只有一个节点可以持有租约——因此,当一个节点获得一个租约时,它知道它在某段时间内自己是领导者,直到租约到期。 ● 为了保持领导地位,节点必须周期性地在租约过期前续期。 ● 如果节点发生故障,就会停止续期,所以当租约过期时,另一个节点可以接管。
使用租约的问题在哪?
- 它依赖于同步时钟
- 程序执行过程卡顿,导致错过了续租约的时间,并继续处理了一些不安全的请求。而另一个节点接管了领导。
线程为什么会暂停很长时间? ● 垃圾回收(GC) ● 虚拟机被挂起 ● 用户关闭笔记本电脑盖子 ● 操作系统上下文切换到另一个线程时 ● 应用程序同步读取磁盘,等待 IO ● 页面交换的时候,可能导致页面错误,要求将磁盘的页面装入内存。线程暂停。 ● 可以通过发送SIGSTOP信号来暂停Unix进程,例如通过在shell中按下Ctrl-Z。
线程暂停的后果? ● 上述事件都可以随时抢占(preempt) 正在运行的线程,并在稍后的时间恢复运行,而线程甚至不会注意到这一点。 ● 在单机上编码时,可以实现线程安全:互斥量,信号量,原子计数器,无锁数据结构,阻塞队列等等。 ● 不幸的是,这些工具并不能直接转化为分布式系统操作,因为分布式系统没有共享内存,只有通过不可靠网络发送的消息。 ● 分布式系统中的节点,必须假定其执行可能在任意时刻暂停相当长的时间,即使是在一个函数的中间。 ● 在暂停期间,世界的其它部分在继续运转,甚至可能因为该节点没有响应,而宣告暂停节点的死亡。最终暂停的节点可能会继续运行,在再次检查自己的时钟之前,甚至可能不会意识到自己进入了睡眠。
响应时间保证
如何做到在特定事件响应的保证? ● 飞机、火箭、机器人、骑车等系统中的软件件必须有一个特定的截止时间(deadline),如果截止时间不满足,可能会导致整个系统的故障。这就是所谓的硬实时(hard real-time) 系统。 ● 实现实时保证需要各级软件的支持: ○ 一个实时操作系统(RTOS),允许在指定的时间间隔内保证CPU时间的分配。 ○ 库函数必须申明最坏情况下的执行时间; ○ 动态内存分配可能受到限制或完全不允许(实时垃圾收集器存在,但是应用程序仍然必须确保它不会给GC太多的负担); ○ 必须进行大量的测试和测量,以确保达到保证。 ● 实时系统太贵! ● 因此大多数服务器端数据处理系统,必须承受非实时环境中运行的暂停和时钟不稳定性。
限制垃圾收集的影响
怎么降低垃圾回收带来的影响? ● 一种想法是在即将 GC 前发出警告,应用程序停止向该节点发出新的请求;等待其恢复后,再继续处理请求。 ● 另一种想法是垃圾回收处理短命对象(可以快速收集),并定期在积累大量长寿对象(因此需要完整GC)之前重新启动进程。重启时把节点的流量移走。
知识、真相与谎言
何为真假?感知和测量不可靠,我们怎么确定信息的可靠性?这是个哲学问题。
真相由多数所定义
真相到底是什么? ● 节点不能根据自己的信息来判断自身的状态。 ● 因为节点可能随时失效,可能会暂停-假死,可能最终都无法恢复。 ● 相反,许多分布式算法都依赖于法定人数,即在节点之间进行投票:决策需要来自多个节点的最小投票数,以减少对于某个特定节点的依赖。 ● 个体哪怕没死,当被法定数量的节点宣告死亡时,它也必须被认定为死的。个体必须遵守法定决定并下台。
最常见的法定人数是超过一半的绝对多数(尽管其他类型的法定人数也是可能的)。 第九章将继续讨论共识算法。
领导者和锁
通常,一些东西在一个系统中只能有一个。如: ● 数据库分区的领导者只能有一个节点,以避免脑裂(split brain) ● 特定资源的锁或对象只允许一个事务/客户端持有,以防同时写入和损坏。 ● 一个特定的用户名只能被一个用户所注册,因为用户名必须唯一标识一个用户。
分布式系统可能出现「唯一的节点」不止一个! ● 一个节点认为自己是「唯一的节点」,但是有可能它以前是主节点,但是其他节点宣布它死亡了,此时已经出现了另外一个主节点。 ● 当该节点继续表现为『唯一的节点』,那么可能导致系统异常。
图8-4 分布式锁的实现不正确:客户端1认为它仍然具有有效的租约,即使它已经过期,从而破坏了存储中的文件
防护令牌
确保一个被误认为自己是「唯一的节点」,不能扰乱系统的其它部分。实现这一目标的一个相当简单的技术就是防护(fencing)。 图8-5 只允许以增加防护令牌的顺序进行写操作,从而保证存储安全
具体做法: ● 每次锁定服务器授予锁或租约时,它还会返回一个防护令牌(fencing token),这个数字在每次授予锁定时都会增加。 ● 然后,我们可以要求客户端每次向存储服务发送写入请求时,都必须包含当前的防护令牌。 ● 当防护令牌已经过期了,那么就拒绝其写入。 ● 如果将ZooKeeper用作锁定服务,则可将事务标识zxid或节点版本cversion用作防护令牌。由于它们保证单调递增,因此它们具有所需的属性
防护令牌需要注意? ● 要求资源本身在检查令牌方面发挥积极作用,而不能仅仅依靠客户端检查自己的锁状态。 ● 需要在服务端进行检查令牌。
防护令牌是缺点还是好事? ● 好事 ● 服务不能假设客户总是守规矩并且明智的。
拜占庭故障
防护令牌一定可靠吗? ● 不一定 ● 果节点有意破坏系统的保证,则可以通过使用假防护令牌发送消息来轻松完成此操作。 ● 上文中都是假设节点是不可靠但诚实的。
节点会撒谎吗? ● 这种行为被称为拜占庭故障(Byzantine fault),在不信任的环境中达成共识的问题被称为拜占庭将军问题。 ● 当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作,称之为拜占庭容错(Byzantine fault-tolerant)
什么情况下会出现拜占庭容错? ● 在航空航天环境中,计算机内存或CPU寄存器中的数据可能被辐射破坏,导致其以任意不可预知的方式响应其他节点。 ● 在多个参与组织的系统中,一些参与者可能会试图欺骗或欺骗他人。
我的系统需要考虑拜占庭故障吗? ● 一般不需要。 ● 代价昂贵。
为什么一般不需要考虑拜占庭故障? ● Web 系统是中心化的,服务器决定客户端的行为。 ● 软件的 bug 可能被认为是拜占庭错误,但是拜占庭算法帮不了你:拜占庭算法要求超过 2/3 的节点正常工作。 ● 大多数系统中,如果攻击者可以渗透进一个节点,那么可能会渗透所有的节点,因为运行着相同的软件。因此,传统机制(认证,访问控制,加密,防火墙等)仍然是抵御攻击者的主要保护措施。
弱谎言形式 什么是弱谎言? ● 尽管我们假设节点通常是诚实的,但值得向软件中添加防止“撒谎”弱形式的机制。 ● 例如,由硬件问题导致的无效消息,软件错误和错误配置。 ● 这些保护机制虽然不能抵挡决心坚定的对手,但它们仍然是简单而实用的步骤,以提高可靠性。
常见的弱谎言以及怎么处理? ● 由于硬件问题或操作系统、驱动程序、路由器等中的错误,网络数据包有时会受到损坏。 ○ 解决办法: ■ TCP和UDP中的校验和所俘获 ■ 应用程序级协议中的校验和。 ● 可公开访问的应用程序必须仔细清理来自用户的任何输入 ○ 解决办法: ■ 检查值是否在合理的范围内 ■ 限制字符串的大小以防止通过大内存分配的拒绝服务 ● 一个配置错误的NTP服务器报告错误的时间 ○ 解决办法: ■ NTP客户端可以配置多个服务器地址 ■ 客户端联系所有的服务器,估计它们的误差,并检查大多数服务器是否对某个时间范围达成一致
系统模型与现实
分布式系统问题要求我们以某种方式将我们期望在系统中发生的错误形式化——模型。
关于时序假设,三种系统模型是常用的: 同步模型 ● 同步模型(synchronous model) 假设网络延迟、进程暂停和和时钟误差都是受限的。 ○ 这并不意味着完全同步的时钟或零网络延迟; ○ 这只意味着你知道网络延迟、暂停和时钟漂移将永远不会超过某个固定的上限。 ○ 同步模型并不是大多数实际系统的现实模型,因为(如本章所讨论的)无限延迟和暂停确实会发生。 部分同步模型 ● 部分同步(partial synchronous) 意味着一个系统在大多数情况下像一个同步系统一样运行,但有时候会超出网络延迟,进程暂停和时钟漂移的界限。 ○ 这是很多系统的现实模型:大多数情况下,网络和进程表现良好,否则我们永远无法完成任何事情。 ○ 但是我们必须承认,在任何时刻都存在时序假设偶然被破坏的事实。发生这种情况时,网络延迟、暂停和时钟错误可能会变得相当大。 异步模型 ● 在这个模型中,一个算法不允许对时序做任何假设——事实上它甚至没有时钟(所以它不能使用超时)。 ○ 一些算法被设计为可用于异步模型,但非常受限。
除了时序问题,我们还要考虑节点失效。三种最常见的节点系统模型是: 崩溃-停止故障 ● 在崩溃停止(crash-stop) 模型中,算法可能会假设一个节点只能以一种方式失效,即通过崩溃。 ○ 这意味着节点可能在任意时刻突然停止响应,此后该节点永远消失——它永远不会回来。 崩溃-恢复故障 ● 我们假设节点可能会在任何时候崩溃,但也许会在未知的时间之后再次开始响应。 ○ 在崩溃-恢复(crash-recovery) 模型中,假设节点具有稳定的存储(即,非易失性磁盘存储)且会在崩溃中保留,而内存中的状态会丢失。 拜占庭(任意)故障 ● 节点可以做(绝对意义上的)任何事情,包括试图戏弄和欺骗其他节点,如上一节所述。
对于真实系统的建模,具有崩溃-恢复故障(crash-recovery) 的部分同步模型(partial synchronous) 通常是最有用的模型。
分布式算法如何应对这种模型?
算法的正确性
怎么判断算法是正确的? ● 为了定义算法是正确的,我们可以描述它的属性。 ● 我们可以写下我们想要的分布式算法的属性来定义它的正确含义。
例如,如果我们正在为一个锁生成防护令牌,我们可能要求算法具有以下属性: 唯一性(uniqueness) ● 没有两个防护令牌请求返回相同的值。 单调序列(monotonic sequence) ● 如果请求 $x$ 返回了令牌 $t_x$,并且请求$y$返回了令牌$t_y$,并且 $x$ 在 $y$ 开始之前已经完成,那么$t_x <t_y$。 可用性(availability) ● 请求防护令牌并且不会崩溃的节点,最终会收到响应。
如果一个系统模型中的算法总是满足它在所有我们假设可能发生的情况下的性质,那么这个算法是正确的。
但是如果所有节点都挂了,可用性还有意义吗?
安全性和活性
有必要区分两种不同的属性:安全(safety)属性和活性(liveness)属性。 ● 刚才的例子中,唯一性和单调序列是安全属性,而可用性是活性属性。
两种性质的通俗理解/区别? ● 思路:活性属性通常在定义中通常包括“最终”一词。 (是的,你猜对了——最终一致性是一个活性属性。) ● 安全通常被非正式地定义为:没有坏事发生 ● 活性通常就类似:最终好事发生。 ● 最好不要过度阅读非正式的定义,因为好和坏是主观的。
安全和活性的实际定义是精确的和数学的: ● 如果安全属性被违反,我们可以指向一个特定的安全属性被破坏的时间点 ○ 例如,如果违反了唯一性属性,我们可以确定重复的防护令牌被返回的特定操作。违反安全属性后,违规行为不能被撤销——损失已经发生。 ● 活性属性反过来:在某个时间点(例如,一个节点可能发送了一个请求,但还没有收到响应),它可能不成立,但总是希望在未来能成立(即通过接受答复)。
为什么要区分安全属性和活性属性? ● 可以帮助我们处理困难的系统模型。 ● 对于分布式算法,在系统模型的所有可能情况下,要求始终保持安全属性是常见的。 ○ 也就是说,即使所有节点崩溃,或者整个网络出现故障,算法仍然必须确保它不会返回错误的结果(即保证安全属性得到满足)。 ● 但是,对于活性属性,我们可以提出一些注意事项: ○ 例如,只有在大多数节点没有崩溃的情况下,只有当网络最终从中断中恢复时,我们才可以说请求需要接收响应。 ○ 部分同步模型的定义要求系统最终返回到同步状态——即任何网络中断的时间段只会持续一段有限的时间,然后进行修复。
将系统模型映射到现实世界
证明算法正确,那么现实系统中一定正确吗? ● 虽然,安全属性和活性属性以及系统模型对于推理分布式算法的正确性非常有用。 ● 但是,现实的混乱事实再一次地让你咬牙切齿。 ● 很明显系统模型是对现实的简化抽象。
那么,理论上抽象的系统模型是毫无价值的吗? ● 恰恰相反。它很有价值。 ● 它们对于将实际系统的复杂性提取成一个个我们可以推理的可处理的错误类型是非常有帮助的,以便我们能够理解这个问题,并试图系统地解决这个问题。 ● 我们可以证明算法是正确的,通过表明它们的属性在某个系统模型中总是成立的。
实际上该怎么办? ● 因为理论分析可以发现算法中的问题,这种问题可能会在现实系统中长期潜伏,直到你的假设(例如,时序)因为不寻常的情况被打破。 ● 理论分析与经验测试同样重要。
本章小结
在本章中,我们讨论了分布式系统中可能发生的各种问题,包括: ● 当您尝试通过网络发送数据包时,数据包可能会丢失或任意延迟。同样,答复可能会丢失或延迟,所以如果你没有得到答复,你不知道消息是否发送成功了。 ● 节点的时钟可能会与其他节点显著不同步(尽管您尽最大努力设置NTP),它可能会突然跳转或跳回,依靠它是很危险的,因为您很可能没有好的方法来测量你的时钟的错误间隔。 ● 一个进程可能会在其执行的任何时候暂停一段相当长的时间(可能是因为停止所有处理的垃圾收集器),被其他节点宣告死亡,然后再次复活,却没有意识到它被暂停了。
这类部分失效(partial failure) 可能发生的事实是分布式系统的决定性特征。每当软件试图做任何涉及其他节点的事情时,偶尔就有可能会失败,或者随机变慢,或者根本没有响应(最终超时)。在分布式系统中,我们试图在软件中建立部分失效的容错机制,这样整个系统在即使某些组成部分被破坏的情况下,也可以继续运行。
怎么处理错误? 为了容忍错误,第一步是检测它们,但即使这样也很难。大多数系统没有检测节点是否发生故障的准确机制,所以大多数分布式算法依靠超时来确定远程节点是否仍然可用。但是,超时无法区分网络失效和节点失效,并且可变的网络延迟有时会导致节点被错误地怀疑发生故障。此外,有时一个节点可能处于降级状态:例如,由于驱动程序错误,千兆网卡可能突然下降到1 Kb/s的吞吐量。这样一个“跛行”而不是死掉的节点可能比一个干净的失效节点更难处理。 一旦检测到故障,使系统容忍它也并不容易:没有全局变量,没有共享内存,没有共同的知识,或机器之间任何其他种类的共享状态。节点甚至不能就现在是什么时间达成一致,就不用说更深奥的了。信息从一个节点流向另一个节点的唯一方法是通过不可靠的网络发送信息。重大决策不能由一个节点安全地完成,因此我们需要一个能从其他节点获得帮助的协议,并争取达到法定人数以达成一致。
但是,正如在第二部分的介绍中所讨论的那样,可伸缩性并不是使用分布式系统的唯一原因。容错和低延迟(通过将数据放置在距离用户较近的地方)是同等重要的目标,而这些不能用单个节点实现。
在本章中,我们也转换了几次话题,探讨了网络、时钟和进程的不可靠性是否是不可避免的自然规律。我们看到这并不是:有可能给网络提供硬实时的响应保证和有限的延迟,但是这样做非常昂贵,且导致硬件资源的利用率降低。大多数非安全关键系统会选择便宜而不可靠,而不是昂贵和可靠。
我们还谈到了超级计算机,它们采用可靠的组件,因此当组件发生故障时必须完全停止并重新启动。相比之下,分布式系统可以永久运行而不会在服务层面中断,因为所有的错误和维护都可以在节点级别进行处理——至少在理论上是如此。 (实际上,如果一个错误的配置变更被应用到所有的节点,仍然会使分布式系统瘫痪)。
第九章:一致性与共识
构建容错系统的最好方法,是找到一些带有实用保证的通用抽象,实现一次,然后让应用依赖这些保证。比如事务。 我们需要了解系统能力的边界:哪些可行,哪些不可行。
一致性保证
分布式系统的时序问题:
除了最终一致性,有没有更强的一致性模型?
线性一致性
线性一致性的想法?
线性一致性提供了什么保证?
图9-1 这个系统是非线性一致的,导致了球迷的困惑
如何使得系统线性一致?
第十章:批处理
本书的前九章,讨论的都是请求、查询,以及相应的响应和结果。是在线系统,关注响应时间。 三种不同类型的系统: 服务(在线系统) 处理客户的请求或指令。衡量指标:响应时间,可用性。 批处理系统(离线系统) 跑一个作业,处理大量的输入数据,定时运行。衡量指标:吞吐量。 流处理系统(准实时系统) 介于在线系统和离线系统之间。消费输入并产生输出(不需要响应请求),在事件发生不久就对事件进行操作。
本章讨论批处理系统。
使用Unix工具的批处理
从一个例子开始。 Web 服务器,每次处理请求,在日志中附加一行。使用nginx默认的访问日志格式。
|
|
|
|
简单日志分析
想在你的网站上找到五个最受欢迎的网页:
|
|
输出结果:
|
|
特点:简单且强大。几分钟内完成许多数据分析,性能非常好。
命令链与自定义程序
除了上述的 Unix 命令链。也可以用程序实现,例如在Ruby中:
|
|
特点:不简洁,但可读性强。性能较差。
排序 VS 内存中的聚合
上述两种做法的区别
哪个好?
Unix哲学
Unix管道的发明者道格·麦克罗伊(Doug McIlroy)在1964年说:让数据像水管一样流动。
- 让每个程序都做好一件事。要做一件新的工作,写一个新程序,而不是通过添加“功能”让老程序复杂化。
- 期待每个程序的输出成为另一个程序的输入。不要将无关信息混入输出。避免使用严格的列数据或二进制输入格式。不要坚持交互式输入。
- 设计和构建软件时,即使是操作系统,也让它们能够尽早地被试用,最好在几周内完成。不要犹豫,扔掉笨拙的部分,重建它们。
- 优先使用工具来减轻编程任务,即使必须曲线救国编写工具,且在用完后很可能要扔掉大部分。 这种方法 —— 自动化,快速原型设计,增量式迭代,对实验友好,将大型项目分解成可管理的块 —— 听起来非常像今天的敏捷开发和DevOps运动。奇怪的是,四十年来变化不大。
Unix 怎么实现命令的可组合性?
统一的接口
为什么要统一的接口? ● 一个程序的输出作为另外一个程序的输入,那么必然要统一。
怎么实现统一的接口?
● 在Unix中,这种接口是一个文件(file)(更准确地说,是一个文件描述符)。 ● 一个文件只是一串有序的字节序列。 ● 这是一个非常简单的接口,所以可以使用相同的接口来表示许多不同的东西: ○ 文件系统上的真实文件, ○ 另一个进程(Unix套接字,stdin,stdout)的通信通道 ○ 设备驱动程序(比如/dev/audio或/dev/lp0) ○ 表示TCP连接的套接字等等。
每个程序怎么操作? ● 按照惯例,许多(但不是全部)Unix程序将这个字节序列视为ASCII文本。 ● 将它们的输入文件视为由\n(换行符,ASCII 0x0A)字符分隔的记录列表。 ● 每条记录(即一行输入)的解析则更加模糊。 Unix工具通常通过空白或制表符将行分割成字段,但也使用CSV(逗号分隔),管道分隔和其他编码。
今天,像Unix工具一样流畅地运行程序是一种例外,而不是规范。
逻辑与布线相分离
Unix 怎么做输入输出: ● Unix工具的另一个特点是使用标准输入(stdin)和标准输出(stdout)。 ○ 如果你运行一个程序,而不指定任何其他的东西,标准输入来自键盘,标准输出指向屏幕。 ○ 但是,你也可以从文件输入和/或将输出重定向到文件。 ○ 管道允许你将一个进程的标准输出附加到另一个进程的标准输入(有个小内存缓冲区,而不需要将整个中间数据流写入磁盘)。 ● 将输入/输出布线与程序逻辑分开,可以将小工具组合成更大的系统。
Unix 输入输出的缺点: ● 需要多个输入或输出的程序虽然可能,却非常棘手。 ● 你没法将程序的输出管道连接至网络连接中。 ● 如果程序直接打开文件进行读取和写入,或者将另一个程序作为子进程启动,或者打开网络连接,那么I/O的布线就取决于程序本身了。 ● 它仍然可以被配置(例如通过命令行选项),但在Shell中对输入和输出进行布线的灵活性就少了。
透明度和实验
使Unix工具如此成功的部分原因是,它们使查看正在发生的事情变得非常容易: ● Unix命令的输入文件通常被视为不可变的。这意味着你可以随意运行命令,尝试各种命令行选项,而不会损坏输入文件。 ● 你可以在任何时候结束管道,将管道输出到less,然后查看它是否具有预期的形式。这种检查能力对调试非常有用。 ● 你可以将一个流水线阶段的输出写入文件,并将该文件用作下一阶段的输入。这使你可以重新启动后面的阶段,而无需重新运行整个管道。
优点: ● 与关系数据库的查询优化器相比,即使Unix工具非常简单,但仍然非常有用,特别是对于实验而言。 缺点: ● Unix工具的最大局限在于它们只能在一台机器上运行 —— 而Hadoop这样的工具即应运而生
MapReduce和分布式文件系统
MapReduce 是什么? ● 有点像 Unix 工具,不过分布在数千台机器上。 ● 简单、易用 ● 通常不会修改输入,除了生成输出外没有任何副作用。 ● 输出文件以连续的方式一次性写入(一旦写入文件,不会修改任何现有的文件部分)。 ● 读写的是 HDFS 等分布式文件系统。 ○ 基于无共享的原则。 ○ 不需要特殊的硬件。 ○ 每台机器运行了一个守护进程,对外暴露网络服务; ○ 名为 NameNode的中央处理器跟踪哪个文件块存储在哪台机器上; ○ 为了容忍机器故障,文件块会被复制到多台机器上; ○ 可伸缩性很好:上万台机器,PB 级别存储。
MapReduce作业执行
MapReduce 怎么运行的? 以上文中的 Web 服务器日志分析为例。
- 读取一组输入文件,并将其分解成记录(records)。在Web服务器日志示例中,每条记录都是日志中的一行(即\n是记录分隔符)。
- 调用Mapper函数,从每条输入记录中提取一对键值。在前面的例子中,Mapper函数是awk ‘{print $7}’:它提取URL($7)作为键,并将值留空。
- 按键排序所有的键值对。在日志的例子中,这由第一个sort命令完成。
- 调用Reducer函数遍历排序后的键值对。如果同一个键出现多次,排序使它们在列表中相邻,所以很容易组合这些值而不必在内存中保留很多状态。在前面的例子中,Reducer是由uniq -c命令实现的,该命令使用相同的键来统计相邻记录的数量。 步骤 2(Map)和步骤 4 (Reduce)需要自己编程写代码。 步骤 1 由输入格式解析器处理; 步骤 3 隐含在 MapReduce 中——因为Mapper的输出始终在送往Reducer之前进行排序。
如何自定义 Mapper 和 Reducer? Mapper ● Mapper 会在每条输入记录上调用一次,其工作是从输入记录中提取键值。 ● 对于每个输入,它可以生成任意数量的键值对(包括None)。 ● 它不会保留从一个输入记录到下一个记录的任何状态,因此每个记录都是独立处理的。 Reducer ● MapReduce 框架拉取由 Mapper 生成的键值对,收集属于同一个键的所有值,并在这组值上迭代调用 Reducer。 ● Reducer 可以产生输出记录(例如相同URL的出现次数)。
如果 reduce 之后还需要再排序怎么办? ● 再编写第二个 MapReduce 作业并将第一个作业的输出用作第二个作业的输入来实现它。
分布式执行MapReduce
MapReduce 和 Unix 管道的主要区别? ● MapReduce 在多个机器上并行执行计算,而无需编写代码来显式处理并行问题。 ● Mapper和Reducer一次只能处理一条记录;它们不需要知道它们的输入来自哪里,或者输出去往什么地方,所以框架可以处理在机器之间移动数据的复杂性。
Hadoop MapReduce作业中的数据流
如上图
Mapper 的分区?
● 并行化基于分区:作业的输入通常是HDFS中的一个目录,输入目录中的每个文件或文件块都被认为是一个单独的分区,可以单独处理map任务 ● 每个输入文件的大小通常是数百兆字节。 ● MapReduce调度器(图中未显示)试图在其中一台存储输入文件副本的机器上运行每个Mapper,只要该机器有足够的备用RAM和CPU资源来运行Mapper任务。 ● 这个原则被称为将计算放在数据附近:它节省了通过网络复制输入文件的开销,减少网络负载并增加局部性。
Mapper 任务的代码在运行它的机器上还不存在咋办? ● MapReduce框架首先将代码(例如Java程序中的JAR文件)复制到适当的机器。 ● 然后启动Map任务并开始读取输入文件,一次将一条记录传入Mapper回调函数。 ● Mapper的输出由键值对组成。
Reducer 的分区? ● 计算的Reduce端也被分区。 ● 虽然Map任务的数量由输入文件块的数量决定,但Reducer的任务的数量是由作业作者配置的(它可以不同于Map任务的数量)。 ● 为了确保具有相同键的所有键值对最终落在相同的Reducer处,框架使用键的散列值来确定哪个Reduce任务应该接收到特定的键值对。
排序怎么做的? ● 键值对必须进行排序,但数据集可能太大,无法在单台机器上使用常规排序算法进行排序。 ● 相反,分类是分阶段进行的。首先每个Map任务都按照Reducer对输出进行分区。每个分区都被写入Mapper程序的本地磁盘,使用的技术与我们在“SSTables与LSM树”中讨论的类似。 ● 只要当Mapper读取完输入文件,并写完排序后的输出文件,MapReduce调度器就会通知Reducer可以从该Mapper开始获取输出文件。 ● Reducer连接到每个Mapper,并下载自己相应分区的有序键值对文件。按Reducer分区,排序,从Mapper向Reducer复制分区数据,这一整个过程被称为混洗(shuffle)。(一个容易混淆的术语 —— 不像洗牌,在MapReduce中的混洗没有随机性)。
Reduce 做了什么? ● Reduce任务从Mapper获取文件,并将它们合并在一起,并保留有序特性。 ● 因此,如果不同的Mapper生成了键相同的记录,则在Reducer的输入中,这些记录将会相邻。 ● Reducer调用时会收到一个键,和一个迭代器作为参数,迭代器会顺序地扫过所有具有该键的记录(因为在某些情况可能无法完全放入内存中)。 ● Reducer可以使用任意逻辑来处理这些记录,并且可以生成任意数量的输出记录。这些输出记录会写入分布式文件系统上的文件中(通常是在跑Reducer的机器本地磁盘上留一份,并在其他机器上留几份副本)。
MapReduce工作流
单个MapReduce 的局限? ● 单个MapReduce作业可以解决的问题范围很有限。 ● 以日志分析为例,单个MapReduce作业可以确定每个URL的页面浏览次数,但无法确定最常见的URL,因为这需要第二轮排序。 ● 因此将MapReduce作业链接成为工作流(workflow) 中是极为常见的
Hadoop MapReduce 怎么实现工作流? ● Hadoop MapReduce框架对工作流没有特殊支持,所以这个链是通过目录名隐式实现的: ○ 第一个作业必须将其输出配置为HDFS中的指定目录; ○ 第二个作业必须将其输入配置为从同一个目录。 ● 从MapReduce框架的角度来看,这是两个独立的作业。 ● 被链接的MapReduce作业并没有那么像Unix命令管道(它直接将一个进程的输出作为另一个进程的输入,仅用一个很小的内存缓冲区)。 ● 它更像是一系列命令,其中每个命令的输出写入临时文件,下一个命令从临时文件中读取。 ● 这种设计有利也有弊,我们将在“物化中间状态”中讨论。
如何处理工作流中不同作业之间的依赖? ● 只有当作业成功完成后,批处理作业的输出才会被视为有效的(MapReduce会丢弃失败作业的部分输出)。 ● 因此,工作流中的一项作业只有在先前的作业(即生产其输入的作业)成功完成后才能开始。 ● 为了处理这些作业之间的依赖,有很多针对Hadoop的工作流调度器被开发出来,包括Oozie,Azkaban,Luigi,Airflow和Pinball ● 在维护大量批处理作业时非常有用。在构建推荐系统时,由50到100个MapReduce作业组成的工作流是常见的;大型组织中,许多不同的团队可能运行不同的作业来读取彼此的输出。
Reduce侧Join与分组
第二章讨论过数据数据模型和查询语言的Join(连接),这里讨论它是如何实现的。
两条记录存在关联是很常见的: ● 关系模型中的外键,文档模型中的文档引用或图模型中的边。 ● 当你需要同时访问这一关联的两侧(持有引用的记录与被引用的记录)时,join 就是必须的。
MapReduce 可以通过索引来关联数据吗? ● 在数据库中,如果执行只涉及少量记录的查询,数据库通常会使用索引来快速定位感兴趣的记录。如果查询涉及到join ,则可能涉及到查找多个索引。 ● 然而MapReduce没有索引的概念 —— 至少在通常意义上没有。
MapReduce 作业怎么找到想要读的部分数据? ● 它读取所有这些文件的全部内容;(数据库中称之为全表扫描) ● 如果你只想读取少量的记录,则全表扫描与索引查询相比,代价非常高昂。 ● 但通常是需要计算大量记录的聚合。在这种情况下,特别是如果能在多台机器上并行处理时,扫描整个输入可能是相当合理的事情。 ● 因此,我们在批处理语义中讨论链接时,一般是同时处理所有用户的数据,而非某个特定用户的数据。
示例:用户活动事件分析
一个批处理作业中join 的典型例子。左侧是事件日志,描述登录用户在网站上做的事情(称为活动事件(activity events) 或点击流数据(clickstream data)),右侧是用户数据库。
分析任务需要将用户活动与用户档案信息相关联:例如,如果档案包含用户的年龄或出生日期,系统就可以确定哪些页面更受哪些年龄段的用户欢迎。
有什么简单方法实现上述任务? ● 逐个遍历活动事件,并为每个遇到的用户ID查询用户数据库(在远程服务器上)。 ○ 缺点:性能很差,吞吐量低,可能压垮数据库。
为什么批处理任务不用上面的方法? ● 为了在批处理过程中实现良好的吞吐量,计算必须(尽可能)在单台机器上进行(而不是访问外部数据,如数据库)。 ● 为待处理的每条记录发起随机访问的网络请求实在是太慢了。 ● 查询远程数据库意味着批处理作业变为非确定的(nondeterministic),因为远程数据库中的数据可能会改变。
批处理任务中,更好的实现方法是什么? ● 更好的方法是获取用户数据库的副本(ETL,数据仓库),并将它和用户行为日志放入同一个分布式文件系统中,如 HDFS。 ● 然后用MapReduce将所有相关记录集中到同一个地方进行高效处理。
排序合并连接
join 过程中 Mapper 的工作? Mapper的目的是从每个输入记录中提取一对键值,在上面 hadoop的 map reduce 的情况下,这个键就是用户ID: ● 一组Mapper会扫过活动事件(提取用户ID作为键,活动事件作为值) ● 而另一组Mapper将会扫过用户数据库(提取用户ID作为键,用户的出生日期作为值)。
过程如下所示:
join 过程中怎么做分区? ● 当MapReduce框架通过键对Mapper输出进行分区,然后对键值对进行排序时,效果是具有相同ID的所有活动事件和用户记录在Reducer输入中彼此相邻。(在上图中,三个104分区到了parition 1,173 和 103 分到 partition 2) ● Map-Reduce作业甚至可以也让这些记录排序,使Reducer总能先看到来自用户数据库的记录,紧接着是按「出生日期」排序的活动事件 —— 这种技术被称为二次排序(secondary sort)。
join 过程中 reducer 的工作? ● Reducer可以容易地执行实际的join 逻辑:每个用户ID都会被调用一次Reducer函数,且因为二次排序,第一个值应该是来自用户数据库的「出生日期」记录。 ● Reducer将「出生日期」存储在局部变量中,然后使用相同的用户ID遍历活动事件,输出已观看网址和观看者年龄的结果对。随后的Map-Reduce作业可以计算每个URL的查看者年龄分布,并按年龄段进行聚集。
为什么叫做排序合并连接? ● 由于Reducer一次处理一个特定用户ID的所有记录,因此一次只需要将一条用户记录保存在内存中,而不需要通过网络发出任何请求。 ● 这个算法被称为排序合并连接(sort-merge join),因为Mapper的输出是按键排序的,然后Reducer将来自join 两侧的有序记录列表合并在一起.
把相关数据放在一起
为什么需要把相关数据放在一起? ● 在排序合并join 中,Mapper和排序过程确保了所有对特定用户ID执行join 操作的必须数据都被放在同一个地方:单次调用Reducer的地方。 ● 预先排好了所有需要的数据,Reducer可以是相当简单的单线程代码,能够以高吞吐量和与低内存开销扫过这些记录。
为什么可以看做“消息”传递? ● Mapper将“消息”发送给Reducer。 ● 当一个Mapper发出一个「键值对」时,这个「键」的作用就像值应该传递到的目标地址。 ● 即使「键」只是一个任意的字符串(不是像IP地址和端口号那样的实际的网络地址),它表现的就像一个地址:所有具有相同键的键值对将被传递到相同的目标(一次Reducer的调用)。
MapReduce 编程模型中用户需要考虑网络通信吗? ● 不用 ● 使用MapReduce编程模型,能将计算的物理网络通信层面(从正确的机器获取数据)从应用逻辑中剥离出来(获取数据后执行处理)。 ● 这种分离与数据库的典型用法形成了鲜明对比,从数据库中获取数据的请求经常出现在应用代码内部。 ● 由于MapReduce处理了所有的网络通信,因此它也避免了让应用代码去担心部分故障,例如另一个节点的崩溃:MapReduce在不影响应用逻辑的情况下能透明地重试失败的任务。
分组
除了 join(连接) 之外,还有什么“把相关数据放在一起”的方法? ● 常见的还有:按某个键对记录分组(如SQL中的GROUP BY子句)。 ● 所有带有相同键的记录构成一个组,而下一步往往是在每个组内进行某种聚合操作。比如: ○ 统计每个组中记录的数量(例如在统计PV的例子中,在SQL中表示为COUNT(*)聚合) ○ 对某个特定字段求和(SQL中的SUM(fieldname)) ○ 按某种分级函数取出排名前k条记录。
MapReduce实现这种「分组」操作? ● 最简单方法是设置Mapper,以便它们生成的键值对使用所需的分组键。 ● 然后分区和排序过程将所有具有相同分区键的记录导向同一个Reducer。 ● 因此在MapReduce之上实现分组和join 看上去非常相似。
分组还有什么应用? ● 分组的另一个常见用途是整理特定用户会话的所有活动事件,以找出用户进行的一系列操作(称为会话化(sessionization))。 ● 例如: ○ 可以使用这种分析来确定显示新版网站的用户是否比那些显示旧版本的用户更有购买欲(A/B测试) ○ 或者计算某个营销活动是否有效。
当有多个 web 服务器,特定用户活动事件分散在多个不同机器上怎么办? ● 可以通过使用会话cookie,用户ID或类似的标识符作为分组键,以将特定用户的所有活动事件放在一起来实现会话化 ● 与此同时,不同用户的事件仍然散布在不同的分区中
处理偏斜
什么是热键? ● 如果存在与单个键关联的大量数据,则“将具有相同键的所有记录放到相同的位置”这种模式就被破坏了。 ● 这种不成比例的活动数据库记录被称为关键对象(linchpin object)【38】或热键(hot key)。
什么是倾斜? ● 在单个Reducer中收集与某个名人相关的所有活动(例如他们发布内容的回复)可能导致严重的偏斜(也称为热点(hot spot))—— 也就是说,一个Reducer必须比其他Reducer处理更多的记录。 ● 由于MapReduce作业只有在所有Mapper和Reducer都完成时才完成,所有后续作业必须等待最慢的Reducer才能启动。
怎么解决数据倾斜? ● 如果join 的输入存在热键,可以使用一些算法进行补偿。
以 Pig 中解决数据倾斜为例: ● 例如,Pig中的偏斜连接(skewed join) 方法首先运行一个抽样作业(Sampling Job)来确定哪些键是热键。 ● join 实际执行时,Mapper会将热键的关联记录随机(相对于传统MapReduce基于键散列的确定性方法)发送到几个Reducer之一。 ● 对于另外一侧的 join 输入,与热键相关的记录需要被复制到所有处理该键的Reducer上。 ● 这种技术将处理热键的工作分散到多个Reducer上,这样可以使其更好地并行化,代价是需要将 join 另一侧的输入记录复制到多个Reducer上。 ○ 优点:将处理热键的工作分散到多个Reducer上,这样可以使其更好地并行化 ○ 缺点:代价是需要将 join 另一侧的输入记录复制到多个Reducer上。
Crunch处理数据倾斜: ● Crunch中的分片连接(sharded join) 方法与之类似,但需要显式指定热键而不是使用抽样作业。
Hive 处理数据倾斜: ● Hive 偏斜 join 优化采取了另一种方法,它需要在表格元数据中显式指定热键,并将与这些键相关的记录单独存放,与其它文件分开。 ● 当在该表上执行 join 时,对于热键,它会使用Map端 join (请参阅下一节) ● 当按照热键进行分组并聚合时,可以将分组分两个阶段进行: ○ 第一个MapReduce阶段将记录发送到随机Reducer,以便每个Reducer只对热键的子集执行分组,为每个键输出一个更紧凑的中间聚合结果。 ○ 然后,第二个MapReduce作业将所有来自第一阶段Reducer的中间聚合结果合并为每个键一个值。
Map侧 join
怎么理解上文是 Reducer 侧 join : ● 上一节中的链接算法都是在 Reducer 中执行的,所以被称为 reduce 侧 join。 ● Mapper 扮演数据预处理的角色,从每个输入记录中提取键值,将键值分配给 Reducer 分区,并按键排序。 ○ 优点:不用对输入数据做任何假设:不用管属性和结构,Mapper 都可以做预处理以备 Join ○ 缺点:排序,复制到 Reducer,合并 Reducer 输入,这些操作可能开销巨大。数据可能要落盘好几次,取决于可用的内存缓冲区。
Map 侧 Join: ● 如果你能对数据做出某些假设,就可以用 Map 侧 Join来加快速度。 ● 省掉了 Reducer 与排序的 MapReduce 作业,每个 mapper 都是简单的从分布式文件系统中读取一个输入,然后输出到文件系统,仅此而已。
广播散列连接
广播散列连接(broadcast hash join): ● 一个最简单场景是大数据集与小数据集连接的情况。要点在于小数据集需要足够小,以便可以将其全部加载到每个Mapper的内存中。 ● 每个 Mapper 在扫描「大数据集」时,简单地从内存散列表中查找每个『小数据集』的数据。 ● 广播:每个 join 较大输入端分区的 Mapper 都会将较小输入端数据集整个读入内存中(所以较小输入实际上“广播”到较大数据的所有分区上) ● 散列:反映了它使用一个散列表。 ● Pig, Hive, Cascading和Crunch 都支持这种 join 。 ● 此外,还可以将较小输入存储在本地磁盘中,索引在内存中。
分区散列连接
● 如果Map侧 join 的输入以相同的方式进行分区,则散列连接方法可以独立应用于每个分区。 ● 每个Mapper只需要从输入两端各读取一个分区就足够了。 ● 好处是每个Mapper都可以在内存散列表中少放点数据。 ● 适用场景:这种方法只有当连接两端输入有相同的分区数,且两侧的记录都是使用相同的键与相同的哈希函数做分区时才适用。如果输入是由之前执行过这种分组的MapReduce作业生成的,那么这可能是一个合理的假设。
Map侧合并连接
● 如果数据集以相同的方式进行分区、还基于相同的键进行排序,那么还可以用 Map 侧连接的变体。 ● 输入是否小到能放到内存不重要。 ● 因为这时候Mapper同样可以执行归并操作(通常由Reducer执行):按键递增的顺序依次读取两个输入文件,将具有相同键的记录配对。
MapReduce工作流与Map侧连接
影响到输出: ● 当下游作业使用MapReduce join 的输出时,Map侧连接或Reduce侧 join 的不同选择会影响输出的结构。 ● Reduce侧连接的输出是按照连接键进行分区和排序的; ● Map端连接的输出则按照与「大数据集」相同的方式进行分区和排序;
对输入有假设: ● Map侧连接也对输入数据集的大小,有序性和分区方式做出了更多假设。 ● 你必须了解数据按哪些键做的分区和排序,以及分区数量等。
批处理工作流的输出
一个疑问:MapReduce处理完成之后的最终结果是什么?我们最开始为什么要跑这些作业?
在数据库查询的场景中,我们将事务处理(OLTP)与分析两种目的区分开来: ● OLTP查询通常根据键查找少量记录,使用索引,并将其呈现给用户(比如在网页上)。 ● 分析查询通常会扫描大量记录,执行分组与聚合,输出通常有着报告的形式:显示某个指标随时间变化的图表,或按照某种排位取前10项,或将一些数字细化为子类。这种报告的消费者通常是需要做出商业决策的分析师或经理。
批处理放哪里合适? ● 它不属于事务处理,也不是分析。 ● 它和分析比较接近,因为批处理通常会扫过输入数据集的绝大部分。 ● 但批处理过程的输出通常不是报表,而是一些其他类型的结构。
建立搜索索引
MapReduce诞生的背景 ● Google 最初使用 MapReduce 是为其搜索引擎建立索引 ● Hadoop MapReduce 仍然是为 Lucene/Solr 构建索引的好方法
Lucene这样的全文搜索索引是如何工作的? ● 它是一个文件(关键词字典),你可以在其中高效地查找特定关键字,并找到包含该关键字的所有文档ID列表(文章列表)。
如何用 MapReduce 构建索引? ● Mapper根据需要对文档集合进行分区,每个Reducer构建该分区的索引,并将索引文件写入分布式文件系统。 ● 构建这样的文档分区索引并行处理效果拔群。
索引怎么更新? ● 由于按关键字查询搜索索引是只读操作,因而这些索引文件一旦创建就是不可变的。 ● 如果索引的文档集合发生更改 ○ 一种选择是定期重跑整个索引工作流,并在完成后用新的索引文件批量替换以前的索引文件。 ■ 如果只有少量的文档发生了变化,这种方法的计算成本可能会很高。 ■ 优点:是索引过程很容易理解:文档进,索引出。 ○ 另一种选择是增量建立索引。如果需要索引中添加,删除或更新文档,Lucene会写新的段文件,并在后台异步合并压缩段文件。
键值存储作为批处理输出
除了建立搜索索引之外,批处理还有什么用途? ● 构建机器学习系统,例如分类器(比如垃圾邮件过滤器,异常检测,图像识别)与推荐系统
机器学习系统的批处理输出到哪里? ● 通常是某种数据库,例如可以通过给定 ID 查询其推荐好友的数据库
这些数据库怎么用? ● 通常需要被 Web 服务所查询。
批处理过程的输出到Web应用可以查询的数据库中呢? ● 一条条插入到数据库
为什么一条条插入数据库不是好主意呢? ● 每条记录发起一个网络请求,比批处理的吞吐慢了几个量级 ● 数据库可能被压垮,导致线上故障 ● 当批任务重试的时候,得操心数据库的情况
如果不一条条插入数据库,还有什么好主意? ● 在批处理作业内创建一个全新的数据库,并将其作为文件写入分布式文件系统中作业的输出目录,就像上节中的搜索索引一样。 ● 这些数据文件一旦写入就是不可变的,可以批量加载到处理只读查询的服务器中。 ● 不少键值存储都支持在MapReduce作业中构建数据库文件,包括Voldemort ,Terrapin ,ElephantDB 和 HBase 批量加载。
这么做的优点? ● 因为文件只读(不再修改),所以数据结构很简单,不用预写式日志(WAL) ● 在Voldemort加载数据时,使用旧文件继续提供服务,当加载完成自动将查询切换到新文件。如果出现问题,则回滚。
批处理输出的哲学
Unix哲学鼓励以显式指明数据流的方式进行实验:程序读取输入并写入输出。 ● 输入保持不变;没有副作用;可以随意改动或调试;
MapReduce作业的输出处理遵循同样的原理。 ● 如果代码错误或者输出损坏,可以回滚代码,然后重跑。输出就会被修正。 ○ 数据库没有这个属性:回滚代码无法修复数据库中的数据 ○ 能够从错误代码中恢复的概念被称为人类容错(human fault tolerance) ● 由于回滚容易,可以容忍错误。这种最小化不可逆性(minimizing irreversibility) 的原则有利于敏捷软件开发。 ● 如果Map或Reduce任务失败,MapReduce框架将自动重新调度,并在同样的输入上再次运行它。 ○ 如果是代码错误,那么几次重试后将失败; ○ 如果是临时问题导致的,那么故障被容忍; ○ 由于输入不可变,所以重试是安全的。 ● 同一组文件可用作各种不同作业的输入 ● 与Unix工具类似,MapReduce作业将逻辑与布线(配置输入和输出目录)分离,这使得关注点分离,可以重用代码:一个团队可以专注实现一个做好一件事的作业;而其他团队可以决定何时何地运行这项作业。
Unix 与 Hadoop 的不同: ● 大多数 Unix 工具都假设输入输出是无类型文本文件,所以它们必须做大量的输入解析工作(本章开头的日志分析示例使用 {print $7} 来提取URL)。 ● 在 Hadoop 上可以通过使用更结构化的文件格式消除一些低价值的语法转换:比如 Avro(请参阅“Avro”)和 Parquet(请参阅“列存储”)经常使用,因为它们提供了基于模式的高效编码,并允许模式随时间推移而演进(见第四章)。
Hadoop与分布式数据库的对比
MapReduce 与 大规模并行处理(MPP, massively parallel processing)的区别? ● MPP数据库专注于在一组机器上并行执行分析SQL查询 ● 而MapReduce和分布式文件系统的组合则更像是一个可以运行任意程序的通用操作系统。
存储多样性 分布式文件系统与数据库的区别? ● 数据库要求你根据特定的模型(例如关系或文档)来构造数据 ● 而分布式文件系统中的文件只是字节序列,可以使用任何数据模型和编码来编写。
使用原始格式保存数据的优点? ● 实践经验表明,简单地使数据快速可用 —— 即使它很古怪,难以使用,使用原始格式 —— 也通常要比事先决定理想数据模型要更有价值 ● 以原始形式收集数据,稍后再操心模式的设计,能使数据收集速度加快(有时被称为“数据湖(data lake)”或“企业数据中心(enterprise data hub)” ● 转移了解释数据的负担:数据的解释成为消费者的问题(读时模式),有利于跨团队合作。 ● 这种方法被称为寿司原则(sushi principle):“原始数据更好”
处理模型的多样性
MPP 数据库和 MapReduce 在处理模型上的区别? ● MPP 数据库是单体的,紧密集成的软件,负责磁盘上的存储布局,查询计划,调度和执行。 ○ 优点:可以针对数据库特定调优;可以用 SQL 查询语言表达查询,无需代码。 ○ 缺点:并非所有类型的处理都可以合理地表达为SQL查询(如索引、推荐系统)。 ● MapReduce 能够轻松地在大型数据集上运行自己的代码。 ○ 优点: ■ 语法上:可以建立一个SQL查询执行引擎,如 Hive 项目;也可以编写代码;还可以编写其他模型; ■ 运行上:分布式。
针对频繁故障设计
MPP 数据库和 MapReduce 在处理故障上的区别? ● 与在线系统相比,批处理系统对故障不敏感。 ● MPP 数据库: ○ 如果有一个节点执行查询时失败,MPP 数据库会中止整个查询,并让用户重试。 ○ 查询通常在几分钟内,因此这种重试可以接受。 ○ 倾向于内存中保留尽可能多的数据,以避免磁盘读取的开销 ● MapReduce: ○ 可以容忍单个Map或Reduce任务的失败,而不会影响作业的整体,通过以单个任务的粒度重试工作。 ○ 它也会非常急切地将数据写入磁盘,一方面是为了容错,另一部分是因为假设数据集太大而不能适应内存。
MapReduce 在处理故障上的优点? ● 更适合大的作业(任务多,易失败) ● 不是因为硬件很不可靠,而是因为任意终止进程的自由有利于提高计算集群中的资源利用率。 ○ 场景:如果优先级较高的任务需要更多的资源,则可以终止(抢占)同一台机器上较低优先级的任务以释放资源。从而提高资源利用率。 ○ 在谷歌,运行一个小时的MapReduce任务有大约有5%的风险被终止,为了给更高优先级的进程挪地方。
MapReduce之后
MapReduce 是简单,但导致复杂任务从头编写任务繁重。 很多高级编程模型被创造,如 Pig,Hive,Cascading,Crunch; MapReuce 是非常稳健,但其他工具可能快上几个量级。
物化中间状态
什么是物化中间状态? ● 每个MapReduce作业都独立于其他任何作业,跨团队合作时,分布式系统的文件只是简单的中间状态(intermediate state) ● 将这个中间状态写入文件的过程称为物化(materialization)。
MapReduce完全物化中间状态与 Unix 管道的比较? ● Unix管道将一个命令的输出与另一个命令的输入连接起来。管道并没有完全物化中间状态,而是只使用一个小的内存缓冲区,将输出增量地流(stream) 向输入。 ● MapReduce完全物化中间状态的不足: ○ 慢:MapReduce作业只有在前驱作业(生成其输入)中的所有任务都完成时才能启动(慢节点拖慢整个工作流程),而由Unix管道连接的进程会同时启动,输出一旦生成就会被消费。 ○ Mapper通常是多余的:它们仅仅是读取刚刚由Reducer写入的同样文件,为下一个阶段的分区和排序做准备。 ■ 在许多情况下,Mapper代码可能是前驱Reducer的一部分:如果Reducer和Mapper的输出有着相同的分区与排序方式,那么Reducer就可以直接串在一起,而不用与Mapper相互交织。 ○ 复制很浪费:将中间状态存储在分布式文件系统中意味着这些文件被复制到多个节点,对这些临时数据这么搞就比较过分了。
数据流引擎
为了解决上述问题,开发了数据流引擎:Spark, Tez, Flink。
数据流引擎与 MapReduce 的区别? ● 数据流引擎的共同点:把整个工作流作为单个作业来处理,而不是把它分解为独立的子作业。 ● 像MapReduce一样,它们在一条线上通过反复调用用户定义的函数来一次处理一条记录,它们通过输入分区来并行化载荷,它们通过网络将一个函数的输出复制到另一个函数的输入。 ● 与MapReduce不同,这些函数不需要严格扮演交织的Map与Reduce的角色,而是可以以更灵活的方式进行组合。我们称这些函数为算子(operators)
数据流引擎提供了哪些不同的选项来将一个算子的输出连接到另一个算子的输入? ● 一种选项是对记录按键重新分区并排序,就像在MapReduce的混洗阶段一样。 ● 另一种可能是接受多个输入,并以相同的方式进行分区,但跳过排序。当记录的分区重要但顺序无关紧要时,这省去了分区散列连接的工作,因为构建散列表还是会把顺序随机打乱。 ● 对于广播散列连接,可以将一个算子的输出,发送到连接算子的所有分区。
与MapReduce模型相比,数据流引擎有什么优点? ● 排序等昂贵的工作只需要在实际需要的地方执行,而不是默认地在每个Map和Reduce阶段之间出现。 ● 没有不必要的Map任务,因为Mapper所做的工作通常可以合并到前面的Reduce算子中(因为Mapper不会更改数据集的分区)。 ● 调度程序能够利用局部性进行优化,比如消费数据任务与生成数据的任务放在相同的机器上。 ● 算子间的中间状态足以保存在内存中或写入本地磁盘,这比写入HDFS需要更少的I/O(必须将其复制到多台机器,并将每个副本写入磁盘)。 ● 算子可以在输入就绪后立即开始执行;后续阶段无需等待前驱阶段整个完成后再开始。 ● 与MapReduce(为每个任务启动一个新的JVM)相比,现有Java虚拟机(JVM)进程可以重用来运行新算子,从而减少启动开销。
使用数据流引擎执行与MapReduce工作流同样的计算,通常执行速度要明显快得多。
容错
完全物化中间状态至 HDFS 的优点? ● 具有持久性,这使得MapReduce中的容错相当容易,任务失败时可以在另一台机器上重启。
Spark,Flink和Tez没有将中间状态写入HDFS,怎么容错? ● 它们采取了不同的方法来容错:如果一台机器发生故障,并且该机器上的中间状态丢失,则它会从其他仍然可用的数据重新计算(在可行的情况下是先前的中间状态,要么就只能是原始输入数据,通常在HDFS上)。 ● 为了实现这种重新计算,框架必须跟踪一个给定的数据是如何计算的 —— 使用了哪些输入分区?应用了哪些算子? Spark使用弹性分布式数据集(RDD,Resilient Distributed Dataset) 的抽象来跟踪数据的谱系,而Flink对算子状态存档,允许恢复运行在执行过程中遇到错误的算子。
重新计算数据时,计算有不确定行怎么办? ● 在重新计算数据时,重要的是要知道计算是否是确定性的(相同的输入数据,算子是否始终有相同的输出?)。对于不确定性算子来说,解决方案通常是杀死下游算子,然后再重跑新数据。 ● 为了避免这种级联故障,最好让算子具有确定性。 ○ 但是非确定性行为,很容易溜进来。比如哈希表的迭代、随机数。 ○ 最好消除掉上述行为,比如随机数设定固定的种子。
重新计算一定是最佳选择吗? ● 不是 ● 如果中间状态比原始数据小得多,或者计算量大,那么物化中间状态更好。
关于物化的讨论
流引擎的输入和输出与物化。 ● 排序算子必须消费全部的输入后才能输出,因子需要排序的算子都需要至少暂时累积状态。 ● 使用数据流引擎时,HDFS 上的物化数据集通常仍是作业的输入和输出。 ● 比起 MapReduce 的改进是,不用自己把中间状态写入文件了。
图与迭代处理
批处理中为什么会处理图? ● 目标是在整个图上执行某种离线处理或分析 ● 这种需求经常出现在机器学习应用(如推荐引擎)或排序系统中。如,PageRank。
Spark, Flink 等流处理引擎,把算子作为有向无环图(DAG)的一部分安排在作业中。 而图处理中,数据本身具有图的性质。
许多图算法是通过 BFS/DFS 实现的,MapReduce 实现它很低效,因为 MapReduce 是一条条处理的。
Pregel处理模型
针对图批处理的优化 —— 批量同步并行(BSP,Bulk Synchronous Parallel) 计算模型已经开始流行起来。 ● 其中,Apache Giraph ,Spark的GraphX API和Flink的Gelly API 实现了它。 ● 它也被称为Pregel模型,因为Google的Pregel论文推广了这种处理图的方法。
Pregel 是怎么处理图的?(每个顶点是一个处理) ● 在MapReduce中,Mapper在概念上向Reducer的特定调用“发送消息”,因为框架将所有具有相同键的Mapper输出集中在一起。 ● Pregel背后有一个类似的想法:一个顶点可以向另一个顶点“发送消息”,通常这些消息是沿着图的边发送的。 ● 在每次迭代中,为每个顶点调用一个函数,将所有发送给它的消息传递给它 —— 就像调用Reducer一样。 ● 与MapReduce的不同之处在于,在Pregel模型中,顶点在一次迭代到下一次迭代的过程中会记住它的状态,所以这个函数只需要处理新的传入消息。如果图的某个部分没有被发送消息,那里就不需要做任何工作。
容错
Pregel作业怎么容错? ● 消息批处理,且等待通信的次数减少了;每次迭代中发送的消息处理完成才能处理下一轮迭代。 ● 网络丢失、重复、延迟消息时,Pregel 能保证消息在其目标顶点恰好处理一次。 ● 迭代结束时,定期存档所有顶点的状态,持久化存储。
并行执行
● 图的分区取决于框架——比如顶点运行在哪台机器上,怎么通过网络通信。 ○ 理想情况下,大量通信的顶点最好放在同一台机器上。 ○ 实践上很难做到,因为图通常按照任意分配的 ID 分区。 ● 图通常有跨机器的额外开销,中间状态(节点之间发送的消息)往往比原始图大。网络发送消息的开销,会显著拖慢分布式图算法的速度。 ○ 如果图能放在单机内存中处理,单机算法很可能超过分布式处理。 ○ 分布式处理图的并行算法是一个进行中的研究领域。
高级API和语言
目前大规模处理的能力已经具备,在研究的是改进编程模型,提高处理效率,扩大这些技术可以解决的问题集。 ● Hive, Pig, Spark, Flink 等都有自己的高级数据流 API,很方便简单高效。
向声明式查询语言的转变 ● MapReduce 可以自由执行任意代码,但是用户自定义的 UDF 使用起来不方便。 ● 数据流处理引擎发现还是声明式(类 SQL)语言更好,因为内部可以做 join 的优化,列存储,向量化执行等。 ● 批处理框架越来越像 MPP 数据库了(性能也可以媲美)。
专业化的不同领域 ● 传统上,MPP数据库满足了商业智能分析和业务报表的需求 ● 而现在,随着批处理系统获得各种内置功能以及高级声明式算子,且随着MPP数据库变得更加灵活和易于编程,两者开始看起来相似了:最终,它们都只是存储和处理数据的系统。
本章小结
输入输出 ● 在Unix世界中,允许程序与程序组合的统一接口是文件与管道; ● 在MapReduce中,该接口是一个分布式文件系统。 ● 数据流引擎添加了自己的管道式数据传输机制,以避免将中间状态物化至分布式文件系统,但作业的初始输入和最终输出通常仍是HDFS。
分布式批处理框架需要解决的两个主要问题是: 分区 ● 在MapReduce中,Mapper根据输入文件块进行分区。Mapper的输出被重新分区、排序并合并到可配置数量的Reducer分区中。这一过程的目的是把所有的相关数据(例如带有相同键的所有记录)都放在同一个地方。 ● 后MapReduce时代的数据流引擎若非必要会尽量避免排序,但它们也采取了大致类似的分区方法。 容错 ● MapReduce经常写入磁盘,这使得从单个失败的任务恢复很轻松,无需重新启动整个作业,但在无故障的情况下减慢了执行速度。 ● 数据流引擎更多地将中间状态保存在内存中,更少地物化中间状态,这意味着如果节点发生故障,则需要重算更多的数据。 ● 确定性算子减少了需要重算的数据量。
讨论了几种MapReduce的连接算法: 排序合并连接 每个参与连接的输入都通过一个提取连接键的Mapper。通过分区、排序和合并,具有相同键的所有记录最终都会进入相同的Reducer调用。这个函数能输出连接好的记录。 广播散列连接 两个连接输入之一很小,所以它并没有分区,而且能被完全加载进一个哈希表中。因此,你可以为连接输入大端的每个分区启动一个Mapper,将输入小端的散列表加载到每个Mapper中,然后扫描大端,一次一条记录,并为每条记录查询散列表。 分区散列连接 如果两个连接输入以相同的方式分区(使用相同的键,相同的散列函数和相同数量的分区),则可以独立地对每个分区应用散列表方法。
批处理作业的显著特点是,它读取一些输入数据并产生一些输出数据,但不修改输入—— 换句话说,输出是从输入衍生出的。最关键的是,输入数据是有界的(bounded):它有一个已知的,固定的大小(例如,它包含一些时间点的日志文件或数据库内容的快照)。因为它是有界的,一个作业知道自己什么时候完成了整个输入的读取,所以一个工作在做完后,最终总是会完成的。