代码人生

设计数据密集型应用程序

代码人生 http://www.she9.com 2019-08-28 13:46 出处:网络 编辑:@技术狂热粉
这本书对我来说有很多东西要学,所以我总结了每一章的要点,特别强调了我觉得最有趣的地方。本书分为三个部分:数据系统基础(第1-4章)、分布式数据(第5-9章)和派生数据(第10-12章)。每章结尾都有大量的参考文献(30到1

这本书对我来说有很多东西要学,所以我总结了每一章的要点,特别强调了我觉得最有趣的地方。


本书分为三个部分:数据系统基础(第1 - 4章)、分布式数据(第5 - 9章)和派生数据(第10 - 12章)。每章结尾都有大量的参考文献(30到110篇)。我真的很喜欢各种各样的参考资料——有些是上世纪70年代及以后的计算机科学论文,还有许多是各种各样的博客文章。


1. 数据系统基础


定义可靠性、可伸缩性和可维护性的介绍性章节。我特别喜欢Twitter向关注者发送推文方式的演变。关于响应时间也有一个很好的观点:当最终用户需要多个后端调用时,许多用户可能会遇到延迟,即使单个请求中只有一小部分很慢(尾部延迟放大)。


2. 数据模型和查询语言


本章讨论众所周知的关系模型和文档模型(NoSQL)。有一个很好的例子说明了如何将LinkedIn个人资料表示为JSON文档——个人资料的树状结构非常适合用JSON表示。然而,随着数据在文档之间的联系越来越紧密,可能会出现一些问题(在LinkedIn的例子中:对公司和大学的引用,用户之间的推荐)。在文档模型中,连接从数据库转移到应用程序。


文档数据库有时被称为无模式数据库。这是不正确的,因为有一个隐式模式。更好的理解方法是写时模式(数据库在存储值时强制执行模式)和读时模式(模式是隐式的,只有在读取数据时才解释)。这类似于编程语言中的静态类型和动态类型。


接下来,我们将讨论查询语言,并给出一个很好的示例,对比命令式查询(编程语言中的循环)和声明式查询(SQL中的SELECT语句)。最后,讨论了类似于图形的数据模型(例如Neo4J使用的数据模型)和该模型的各种查询语言。


3.存储和检索


这是我最喜欢的章节之一。我之前上过一门关于数据库的MOOC课程,但是它并没有过多地讨论数据库的内部。本章首先解释lsm -tree和b -tree是如何工作的。


LSM-trees


Kleppmann首先用两行bash代码创建一个简单的数据库。键和值是通过在文件中附加一行(键后面跟着值)来存储的。要检索给定键的值,可以通过文件进行grep,如果找到键,则获取该值。对现有键的写入仅仅意味着将新行附加到文件中。带有键和值的旧行留在文件中。但是get函数只返回为给定键找到的最后一个值,所以文件中保留原来的行并不重要。


这里的关键(哈哈)思想是,只追加到文件中是快速的(与更改文件中的值相反)。然而,扫描整个文件以检索键值的速度很慢。一个加速方法是保持一个单独的散列,其中有一个指向文件中每个键开始位置的指针。然后,读取操作首先查找要使用的偏移量,然后从文件中的该位置开始读取。


接下来,我们假设文件中的所有行都按键排序。这些文件称为字符串排序表,缩写为SSTables。如果我们有许多这样的文件,在不同的时间创建,那么一个给定的键可以出现在许多文件中。然而,键的最新值是惟一的有效值——所有其他值都已过时(被新值取代)。我们可以将这些文件合并到一个文件中,同时删除所有过时的行。这叫做压缩,由于所有的文件都是按键排序的,所以可以像合并排序一样有效地进行压缩。


首先,如何创建已排序的文件?您维护一个内存中的树结构(如红黑树或AVL树),称为memtable。这样就保持了数据的排序,一旦树达到一定的大小(几兆字节),它就被写成一个新的SSTable。添加或更改键的值只意味着将其添加到memtable(如果已经存在,则可能覆盖它)。要查找键的值,首先在memtable中搜索,然后在最近的SSTable中搜索,然后在下一个较老的SSTable中搜索,等等。


这种类型的存储结构称为日志结构的合并树(LSM-tree),例如Cassandra中就使用了这种结构。


b树


b树是最广泛使用的索引结构(在传统的SQL数据库中使用),与lsm树有很大的不同。b树还保留按键排序的键值对,以允许快速查找。然而,数据以固定大小的块(也称为页)存储在磁盘上,传统上大小为4 KB。要更改一个块中的值,需要编写整个块。通过使用指向子块的指针创建树,其中键范围变得越来越具体,直到找到包含所需值的叶子块为止。分支因子描述父节点可以有多少个子节点。


大多数数据库都可以放入三到四层深的b树中——四层树包含4 KB块,分支系数为500,最多可以存储256 TB。波音公司的鲁道夫·拜尔和爱德华·麦克赖特于1970年引进了b型树结构。目前还不清楚B代表什么——根据维基百科,波音、balance、broad、bushy和拜耳都被推荐了。


lsm -树通常写得更快,而b -树读得更快。然而,有几个因素影响性能,这些将在下一章中讨论。本文描述了不同类型的优化,以及处理崩溃的策略,比如使用写前日志(WAL,也称为重做日志)。


事务和分析


当数据库首次出现时,它们通常用于商业交易,例如销售或支付工资。即使数据库开始用于其他任务,事务这个术语仍然存在。


有两大类用途:在线事务处理(OLTP)和在线分析处理(OLAP)。OLTP通常用于面向最终用户,并且事务通常很小。OLAP更多地用于数据仓库上下文中,其中查询可能聚合来自数百万条记录的值。OLAP的数据库通常以星型模式组织。


有时,面向列的存储用于OLAP用例。当处理来自一列的大量值时(例如求和或平均),这可能更有效。本章有一个很好的例子,说明如何使用位图和运行长度编码压缩存储值。


这一章很长,但很好。我在工作中使用过MySQL和Cassandra,了解内部存储模型的差异非常有帮助。


4. 编码和演化


向后兼容性——新代码可以读取由旧代码编写的数据。正向兼容性——旧代码可以读取由新代码编写的数据。两者都是需要的。当程序中的数据需要保存到文件中或通过网络发送时,需要对其进行某种格式的编码。


本文介绍了三种类型的数据编码。第一种类型是特定于语言的格式,例如java.io。可序列化的Java,或pickle的Python。使用这种格式有很多问题:安全性、版本控制、性能,以及它们与特定编程语言绑定的事实。


接下来,还有标准化的文本编码,如XML、JSON和CSV。他们也有自己的问题。例如,它们不支持二进制字符串(没有字符编码的字节序列)。JSON不区分整数和浮点数,也不指定精度。CSV是一种非常模糊的格式。例如,如何处理逗号和换行?


最后,详细描述了几种二进制编码格式:Thrift(最初来自Facebook)、Protocol Buffers(最初来自谷歌)和Avro(最初来自Hadoop项目)。它们都有模式,并使用一些聪明的技巧使编码紧凑。


5. 复制


这是分布式数据部分的第一章。复制意味着相同的数据存储在多台机器上。复制的一些原因是:即使系统的某些部分失败了,也要继续工作(提高可用性),在地理上保持数据与用户的距离(减少延迟),以及通过提供来自许多机器的相同数据来提高读取吞吐量。


本文介绍了三种不同的模型:单领导模型、多领导模型和无领导模型。复制可以是同步的,也可以是异步的。如果它是同步的,那么领导者和所有的追随者会在写的内容返回给用户之前确认它。如果任何追随者的速度很慢或失败了,这将阻塞所有的写操作。因此,异步复制更为常见。


复制有许多棘手的方面。首先是建立一个新的追随者。由于领导者中的数据是不断变化的,通常您会获取领导者数据库的一致快照,并将其复制到新的追随者。然后,您需要处理复制过程中发生的更改的backlog。


如果跟随者失败了,它需要在恢复之后赶上来。这意味着它需要跟踪它在失败之前已经处理过的leader的哪些事务。如果领导者失败,则需要选择一个新的领导者。这称为故障转移。在这里,很多事情都可能出错。如果使用异步复制,则新领导可能没有收到所有写操作。如果在选择了新leader之后,前leader重新回到集群中,那么那些没有复制的写会发生什么?


执行复制也很棘手。如果使用NOW()或RAND(),简单地重复SQL语句就会导致问题。还有许多其他的边缘情况,所以通常不使用这种方法。相反,使用的是数据库内部预写日志。这是一个只追加的字节序列,包含对数据库的所有写操作。


复制延迟


当您使用异步复制时,您将获得最终的一致性。即使复制延迟通常很小,一系列因素(例如网络问题或高负载)也可能导致延迟变为几秒甚至几分钟。当您有复制延迟时,可能会出现几个问题:如果您提交数据然后重新加载页面,如果重新加载的读取是在与接收到的写入不同的服务器上完成的,那么您可能看不到刚刚编写的数据。有几种可能的解决方案可以保证您阅读自己的编写。对于跨设备读取(从笔记本电脑更新,然后从手机读取),这可能更加棘手。


另一种反常现象是,当它出现的时候,时间似乎在倒退。第一个read返回用户X最近做的注释。当刷新页面时,read来自另一个(滞后的)服务器,而用户X的注释还没有做。单调读取是避免这种情况的一种方法,例如,将所有读取路由到同一服务器。如果最终一致性太弱,可以使用分布式事务。


Multi-Leader复制


在多数据中心操作中,使用多领导复制是有意义的。它有几个优点:性能(写操作不需要经过一个领导者)、数据中心中断的容忍度和网络问题的容忍度(临时问题不会阻止写操作)。


然而,对于多个领导者,存在写冲突的风险。有几种方法可以处理这些问题:Last write wins(基于时间戳或惟一id)、自动合并这些值,或者保留冲突的值,让用户选择要保留的值。


群龙无首的复制


迪纳摩、卡桑德拉、里亚克和伏地魔都使用无头复制。为了确保没有写操作丢失,也没有读操作返回过时的值,使用了quorum读操作和写操作。如果有n个副本,那么每次写操作都必须经过w节点的确认才能成功,并且每次读操作都必须查询至少r个节点。只要w + r > n,我们希望在读取时得到最新的值。在最简单的情况下,n=3 w=2 r=2。但是,仍然可能存在边缘情况——例如,如果写与读并发,那么写可能只出现在某些副本中,并且不清楚应该为读返回新值还是旧值。


如果一个节点已经宕机,并且具有过时的值,那么在从该节点读取值时可以检测到该节点。这可以启动修复。还可以在后台运行一个反熵过程,该过程查找不一致并启动修复。


本章最后给出了一个很好的例子,说明如何使用版本向量来跟踪并发事件之间的因果依赖关系。


6. 分片


将数据分成分区(也称为分片)的原因是可伸缩性。注意,可以同时进行分区和复制——每个分区可以复制到多个节点。每个数据块都属于一个分区。分区可以在键范围上执行,也可以通过散列键来执行。如果某些分区受到的攻击比其他分区(倾斜的工作负载)更多,那么分区的优势可能会丧失。使用分区数据库时,辅助索引可能比较棘手。处理这种情况的一种方法是分散/收集。


随着数据的增长和变化,可能需要重新平衡——将负载从一个节点移动到另一个节点。您不应该移动不必要的数据。例如,简单地使用hash mod N会导致太多的更改。更好的方法是使用比节点更多的分区,并且只在节点之间移动整个分区。如果自动进行再平衡,则存在级联失败的风险。因此,只手动操作可能更好。请求路由到正确分区通常由单独的协调服务(如Zookeeper)处理。

7.事务


本章讨论单台机器上的事务。事务组将写入和读取到一个逻辑单元中。整个事务要么成功(提交),要么失败(中止、回滚)。这使应用程序开发人员不必处理许多不同的潜在问题:与数据库的连接丢失、数据库或应用程序在所有数据写入之前崩溃、多个客户机可能相互覆盖数据等等。


ACID代表原子性、一致性、隔离性和耐久性。原子性与并发性无关(与隔离有关)。相反,它意味着要么所有的写都成功,要么没有。没有部分写入的数据。一致性意味着不变量必须在事务之前和之后始终为真。例如,所有账户的贷方和借方总是平衡的。数据库可以检查一些不变量,如外键约束和惟一性约束。但是一般来说,只有应用程序才能定义什么是有效的或无效的数据——数据库只存储数据。


隔离意味着并发执行的事务不会相互干扰。其余章节的大部分内容都与此相关。最后,持久性意味着成功编写的数据不会丢失。然而,即使数据被写入磁盘,也有很多方法会丢失数据:磁盘可能会损坏,固件错误可能会停止读取,即使磁盘上的数据很好,机器也可能死机,无法访问数据。


隔离级别


当多个客户机同时读取和更新数据时,会出现大量的陷阱。为了避免这种情况,有几个隔离级别来防止出现问题。


最基本的级别是读取提交。这意味着在读取时,您将只看到提交的数据,而不是正在写入但尚未提交的数据。在写入数据库时,您将只覆盖已提交的数据。这也被称为无脏读和无脏写。


快照隔离处理不同部分之间的一致性。如果您有两个帐户,每个帐户中都有500美元,并且您从第一个帐户读取余额,然后从第二个帐户读取余额(两个帐户都在同一个事务中读取),那么它们的总和应该是1000美元。然而,在第一次和第二次读取之间,可能有一个并发事务将$100从第二个帐户移动到第一个帐户。因此,第一次读取可以得到500美元,而第二次读取返回400美元(因为这里已经减去了100美元)。如果我们再次重复读取相同的帐户,第一个帐户将得到600美元,第二个帐户将得到400美元,所以现在它们的和为1000美元。如果避免了更改和的问题,则称为快照隔离,也称为可重复读取。


问题是,我们希望在给定时间点在数据库中看到的内容是一致的。在上面的例子中,我们不想看到总数只有900美元的情况。这一点很重要,例如在进行备份时。备份可能需要几个小时,而且数据一直在变化,但是我们希望备份中存储的内容是一致的。对于长时间运行的查询也是如此——我们希望它们在一致的快照上执行。对此的一个常见解决方案是使用多版本并发控制(MVCC)。数据库可以保存一个对象的多个不同提交版本,因为各种正在进行的事务可能需要在不同的时间点查看数据库的状态。


当两个事务都写数据时,就有丢失更新的风险。例如,如果两个用户同时读取计数器、增加计数器的值并回写结果,那么最终的计数器值可能只更新了一个,而不是两个。如果事务读取一些信息,根据这些信息做出决策,并写入结果,则可能存在写倾斜。这意味着在编写结果时,它所基于的前提已经不再正确。例如,会议室预订系统试图避免重复预订。


Serializable事务


避免问题的一种可靠方法是,所有事务都按顺序执行。然而,往往表现受到太多的影响。在某些情况下,实际上可以串行地执行所有事务。您需要将整个数据集存储在内存中,并使用存储过程来避免事务期间的网络往返,并且吞吐量必须足够低,足以由单个CPU处理。


在大约30年的时间里,唯一广泛使用的串行化算法是两阶段锁定(2PL)。广泛的锁定意味着吞吐量会受到影响。您还可以很容易地获得死锁。与2PL使用的悲观并发控制相比,一种称为可序列化快照隔离(serializable snapshot isolation, SSI)的新算法也可以提供串行性,但是由于乐观并发控制,它具有更好的性能。



8. 分布式系统碰到的麻烦


这是我在书中最喜欢的另一章(连同第三章,存储和检索)。尽管我长期从事分布式系统和并发问题的工作,但这一章确实让我大开眼界,了解了所有可能出错的方式。


不可靠的网络。节点之间的连接可能会以各种方式失败。除了正常的故障模式外,还列出了一些不寻常的故障模式:交换机的软件升级导致所有网络数据包延迟超过一分钟,鲨鱼咬伤和损坏海底电缆,所有入站数据包被丢弃,但出站数据包被成功发送。即使在受控的环境中,例如一个数据中心,网络问题也是常见的。一项研究显示,每月有12起网络故障。检测网络问题的唯一解决方案是超时。


不可靠的时钟。时钟根据日历返回当前的日期和时间。它们通常与NTP同步。因为机器上的本地时钟可能会漂移,它可能会超过NTP时间,重置可以让它看起来回到时间。单调时钟更适合测量经过的时间——它们保证总是向前移动。


即使NTP用于同步不同的机器,也存在许多可能的问题。由于有来自NTP服务器的网络延迟,时钟的精确度是有限制的。闰秒也造成了许多大的中断。这些问题和其他问题意味着一天可能没有确切的86400秒,时钟可以向后移动,一个节点上的时间可能与另一个节点上的时间有很大的不同。此外,不正确的时钟很容易被忽视。


依赖于时间戳来排序事件,例如Cassandra中的Last Write Wins,可能会导致意想不到的结果。谷歌扳手使用的一个解决方案是为时间戳设置置信区间,并确保在排序事件时没有重叠。


过程的停顿。与时间相关的另一个问题是进程暂停。检查当前时间,然后执行某些操作的代码在执行操作之前可能已经暂停了许多秒。发生这种情况的方式有很多:垃圾收集、从代码中不明显的同步磁盘访问(Java类加载器延迟加载类文件)、操作系统交换到磁盘(分页),等等。


为了在分布式系统中处理这些不同的问题,大多数人定义了真相(下一章将详细介绍)。这里描述的可能问题可能会导致一些非常棘手的情况。更糟糕的是,如果参与节点故意试图引起问题。这就是所谓的拜占庭断层,但这本书没有涉及。通过控制所有涉及的服务器,可以避免此类问题。


本章以定义安全和活力结束。安全性意味着没有发生不好的事情(例如,没有向数据库写入错误的数据),而活性意味着最终会发生一些好的事情(例如,在leader节点失败之后,最终会选出一个新的leader)。


9. 意见和共识


分布式一致性主要是在面对延迟和故障时协调副本的状态。


Linearizability


线性化意味着,复制的数据可以显示为只有一个数据副本,并且所有操作看起来都像是对数据进行原子操作(您不会看到值在新值和旧值之间切换)。它使数据库的行为像单线程程序中的变量。问题是它很慢,特别是当存在较大的网络延迟时。


CAP定理有时表示为一致性、可用性、分区容限:从3个选项中选择2个。但是网络分区是一个错误,所以你没有选择,它会发生。Kleppmann认为这个定理更好的表述为:一致的或者是可分割的。他还指出,CAP定理只讨论分区,对其他故障(如网络延迟或死节点)只字不提。所以CAP定理不是很有用。


轮转保证


总的顺序允许对任意两个元素进行比较,您总是可以确定哪个更大。一个线性化的系统有一个总阶。如果两个事件同时发生,则不能确定哪个事件先发生。这导致因果关系的一致性模型较弱。它定义了一个偏序:有些操作是相对于其他操作排序的,但有些操作是不可比较的(并发的)。


Lamport时间戳提供了与因果关系一致的总顺序。然而,这对于确保所选用户名是惟一的(如果两个用户同时尝试选择相同的用户名,我们将只知道这两个用户中谁获得了相同的用户名)等问题来说是不够的。这将导致总订单广播。它要求不丢失任何消息;如果消息被传递到一个节点,那么它将被传递到所有节点。它还要求以相同的顺序将消息传递到每个节点。拥有总订单广播支持正确的数据库复制。


分布式事务和共识


对于分布式事务,可以使用两阶段提交(2PC)。它需要一个协调器。首先,它向每个节点发送一条prepare消息。节点检查是否能够执行写操作,如果是,则回答yes。如果所有节点都回答yes,则下一条消息是提交。然后,每个节点必须执行写操作。


使用单个leader数据库,所有决策都由leader做出,因此,您可以拥有可线性化的操作、惟一性约束、完全有序的复制日志等等(这些属性都可以简化为共识)。如果leader失败或网络问题使您无法访问它,有三个选项:等待它恢复,让人工选择新leader来手动故障转移,或者使用算法自动选择新leader。动物园管理员和其他工具可以帮助解决这个问题。


然而,并非所有的制度都需要共识。无领导和多领导复制系统通常不需要。相反,他们必须处理发生的冲突。对我来说,这是最难理解的一章(我甚至不确定我是否完全理解),尤其是对共识如何被归结为这些其他性质的解释。


请关注公众号:程序你好
0

上一篇:

没有了 :下一篇

精彩评论

暂无评论...
验证码 换一张
取 消