心理学::被讨厌的勇气

被讨厌的勇气 我们的不幸是谁的错 如果我们一直依赖原因论,就会永远止步不前。 任何经历本身并不是成功或者失败的原因。我们并非因为自身经历中的刺激——所谓的心理创伤——而痛苦,事实上我们会从经历中发现符合自己目的的因素。决定我们自身的不是过去的经历,而是我们自己赋予经历的意义。 我们大家都是在为了某种“目的”而活着。这就是目的论。 所谓愤怒其实只是可放可收的一种“手段”而已。 答案不应该是从别人那里得到,而应该是自己亲自找出来。 重要的不是被给予了什么,而是如何去利用被给予的东西。 无视现实的是你。一味执著于“被给予了什么”,现实就会改变?我们不是可以更换的机械。我们需要的不是更换而是更新。 比如现在你感觉不到幸福。有时还会觉得活得很痛苦,甚至想要变成别人。但是,现在的你之所以不幸正是因为你自己亲手选择了“不幸”,而不是因为生来就不幸。 行为之恶的确有很多。但无论什么样的犯罪者,都没有因为纯粹想要作恶而去干坏事的,所有的犯罪者都有其犯罪的内在的“相应理由”。假设有人因为金钱纠纷而杀了人。即使如此,对其本人来说也是有“相应理由”的行为,换句话说就是“善”的行动。当然,这不是指道德意义上的善,而是指“利己”这一意义上的善。 你在人生的某个阶段里选择了“不幸”。这既不是因为你生在了不幸的环境中,也不是因为你陷入了不幸的境地中,而是因为你认为“不幸”对你自身而言是一种“善”。 人时常在选择着自己的生活方式,即使像现在这样促膝而谈的瞬间也在进行着选择。你把自己说成不幸的人,还说想要马上改变,甚至说想要变成别人。尽管如此还是没能改变,这是为什么呢?那是因为你在不断地下着不改变自己生活方式的决心。 如果选择新的生活方式,那就既不知道新的自己会遇到什么问题,也不知道应该如何应对眼前的事情。未来难以预测,生活就会充满不安,也可能有更加痛苦、更加不幸的生活在等着自己。也就是说,即使人们有各种不满,但还是认为保持现状更加轻松、更能安心。 阿德勒心理学就是勇气心理学。你之所以不幸并不是因为过去或者环境,更不是因为能力不足,你只不过是缺乏“勇气”,可以说是缺乏“获得幸福的勇气”。 的确。你现在首先应该做的是什么呢?那就是要有“摈弃现在的生活方式”的决心。 无论之前的人生发生过什么,都对今后的人生如何度过没有影响。”决定自己人生的是活在“此时此刻”的你自己。 一切烦恼都来自人际关系 你为什么讨厌自己呢?为什么只盯着缺点就是不肯去喜欢自己呢?那是因为你太害怕被他人讨厌、害怕在人际关系中受伤。 那么,如何实现这种目的呢?答案很简单。只要变成一个只看自己的缺点、极其厌恶自我、尽量不涉入人际关系的人就可以了。如此一来,只要躲在自己的壳里就可以不与任何人发生关联,而且万一遭到别人的拒绝,还可以以此为理由来安慰自己。心里就会想:因为我有这样的缺点才会遭人拒绝,只要我没有这个缺点也会很讨人喜欢。 但是,请你不要忘记,在人际关系中根本不可能不受伤。只要涉入人际关系就会或大或小地受伤,也会伤害别人。 一切烦恼都是人际关系的烦恼 困扰我们的自卑感不是“客观性的事实”而是“主观性的解释”? 我们无法改变客观事实,但可以任意改变主观解释。并且,我们都活在主观世界中。 也就是说,价值必须建立在社会意义之上。即使 1 美元纸币所承载的价值是一种常识(共通感觉),那它也不是客观意义上的价值。如果从印刷成本考虑的话,它根本不等于 1 美元。 自卑感本身并不是坏事。这一点你能够理解吧?就像阿德勒说过的那样,自卑感也可以成为促成努力和进步的契机。例如,虽然对学历抱有自卑感,但若是正因为如此,才下定“我学历低所以更要付出加倍的努力”之类的决心,那反而成了好事。而另一方面,自卑情结是指把自己的自卑感当作某种借口使用的状态。具体就像“我因为学历低所以无法成功”或者“我因为长得不漂亮所以结不了婚”之类的想法。像这样在日常生活中大肆宣扬“因为有 A 所以才做不到 B”这样的理论,这已经超出了自卑感的范畴,它是一种自卑情结。 简单地说就是害怕向前迈进或者是不想真正地努力。不愿意为了改变自我而牺牲目前所享受的乐趣——比如玩乐或休闲时间。也就是拿不出改变生活方式的“勇气”,即使有些不满或者不自由,也还是更愿意维持现状。 如果真正地拥有自信,就不会自大。正因为有强烈的自卑感才会骄傲自大,那其实是想要故意炫耀自己很优秀。担心如果不那么做的话,就会得不到周围的认可。这完全是一种优越情结。这是一种通过把自卑感尖锐化来实现异常优越感的模式。具体就是指夸耀不幸。 以自己的不幸为武器来支配对方。通过诉说自己如何不幸、如何痛苦来让周围的人——比如家人或朋友——担心或束缚支配其言行。刚开始提到的那些闭门不出者就常常沉浸在以不幸为武器的优越感中。阿德勒甚至指出:“在我们的文化中,弱势其实非常强大而且具有特权。 不与任何人竞争,只要自己不断前进即可 健全的自卑感不是来自与别人的比较,而是来自与“理想的自己”的比较。 好吧,我们都不一样。性别、年龄、知识、经验、外貌,没有完全一样的人。我们应该积极地看待自己与别人的差异。但是,我们“虽然不同但是平等”。 不是。无论是走在前面还是走在后面都没有关系,我们都走在一个并不存在纵轴的水平面上,我们不断向前迈进并不是为了与谁竞争。价值在于不断超越自我。 这与竞争有关。请你记住。如果在人际关系中存在“竞争”,那人就不可能摆脱人际关系带来的烦恼,也就不可能摆脱不幸。 竞争的可怕之处就在于此。即便不是败者、即便一直立于不败之地,处于竞争之中的人也会一刻不得安心、不想成为败者。而为了不成为败者就必须一直获胜、不能相信他人。之所以有很多人虽然取得了社会性的成功,但却感觉不到幸福,就是因为他们活在竞争之中。因为他们眼中的世界是敌人遍布的危险所在。 把他人的幸福看作“我的失败”,所以才无法给予祝福。 如果能够体会到“人人都是我的伙伴”,那么对世界的看法也会截然不同。不再把世界当成危险的所在,也不再活在不必要的猜忌之中,你眼中的世界就会成为一个安全舒适的地方。人际关系的烦恼也会大大减少。 这种情况下,对方的目的是什么呢?是纯粹想要讨论政治吗?不是。对方只是想要责难挑衅你,通过权力之争来达到让不顺眼的你屈服的目的。这个时候你如果发怒的话,那就是正中其下怀,关系会急剧转入权力之争。所以,我们不能上任何挑衅的当。 不是不能发怒,而是“没必要依赖发怒这一工具”。 那就是无论认为自己多么正确,也不要以此为理由去责难对方。这是很多人都容易陷落进去的人际关系圈套。 原本主张的对错与胜负毫无关系。如果你认为自己正确的话,那么无论对方持什么意见都应该无所谓。但是,很多人都会陷入权力之争,试图让对方屈服。正因为如此,才会认为“承认自己的错误”就等于“承认失败”。 承认错误、赔礼道歉、退出权力之争,这些都不是“失败”。 那么你为什么把别人看成是“敌人”而不能认为是“伙伴”呢?那是因为勇气受挫的你在逃避“人生的课题”。 行为方面的目标有以下两点: 自立。 与社会和谐共处。 而且,支撑这种行为的心理方面的目标也有以下两点: “我有能力”的意识。 “人人都是我的伙伴”的意识。 阿德勒心理学不是改变他人的心理学,而是追求自我改变的心理学。不能等着别人发生变化,也不要等着状况有所改变,而是由你自己勇敢迈出第一步。 当人能够感觉到“与这个人在一起可以无拘无束”的时候,才能够体会到爱。既没有自卑感也不必炫耀优越性,能够保持一种平静而自然的状态。真正的爱应该是这样的。 现阶段能说的就是不能够逃避。无论多么困难的关系都不可以选择逃避,必须勇敢去面对。即使最终发展成用剪刀剪断,也要首先选择面对。最不可取的就是在“这样”的状态下止步不前。 人就是这么任性而自私的生物,一旦产生这种想法,无论怎样都能发现对方的缺点。即使对方是圣人君子一样的人物,也能够轻而易举地找到对方值得讨厌的理由。正因为如此,世界才随时可能变成危险的所在,人们也就有可能把所有他人都看成“敌人”。 让干涉你生活的人见鬼去 阿德勒心理学否定寻求他人的认可。 你不是为了满足别人的期待而活着,我也不是为了满足别人的期待而活着。我们没必要去满足别人的期待。 如果一味寻求别人的认可、在意别人的评价,那最终就会活在别人的人生中。 基本上,一切人际关系矛盾都起因于对别人的课题妄加干涉或者自己的课题被别人妄加干涉。 辨别究竟是谁的课题的方法非常简单,只需要考虑一下“某种选择所带来的结果最终要由谁来承担?” 这一点需要注意。阿德勒心理学并不是推崇放任主义。放任是一种不知道也不想知道孩子在做什么的态度。而阿德勒心理学的主张不是如此,而是在了解孩子干什么的基础上对其加以守护。如果就学习而言,告诉孩子这是他自己的课题,在他想学习的时候父母要随时准备给予帮助,但绝不对孩子的课题妄加干涉。在孩子没有向你求助的时候不可以指手画脚。 接受心理咨询辅导之后,被辅导者下什么样的决心、是否改变生活方式,这都是被辅导者本人的课题,辅导顾问不能干涉。 可以把马带到水边,但不能强迫其喝水 能够改变自己的只有自己。 ...

2021 Mar 28 · 1 min

数据密集型应用系统设计::派生数据

派生数据 记录系统 一个记录系统也被称为真实数据系统,拥有数据的权威版本 如果另一个系统与记录系统之间存在任何差异,那么以记录系统中的数据值为准 派生数据系统 派生数据系统中的数据则是从另一个系统中获取已有数据并以某种方式进行转换或处理的结果 如果派生数据丢失,用户可以从原始数据源进行重建 例如缓存 批处理系统 在线服务 服务等待客户请求或指令的到达。当收到请求或指令时,服务试图尽可能快地处理它,并发回一个响应。 响应时间通常是服务性能的主要衡量指标,而可用性同样非常重要 批处理系统 批处理系统接收大量的输入数据,运行一个作业来处理数据,并产生输出数据 批处理作业的主要性能衡量标准通常是吞吐量 流处理系统 流处理介于在线与离线/批处理之间(所以有时称为近实时或近线处理)。与批处理系统类似,流处理系统处理输入并产生输出 流式作业在事件发生后不久即可对事件进行处理,而批处理作业则使用固定的一组输入数据进行操作。这种差异使得流处理系统比批处理系统具有更低的延迟。 使用 UNIX 工具进行批处理 使用 awk, sed, grep, sort , uniq 和 xargs 的组合 ,可以在几分钟内完成许多数据分析任务 UNIX 设计哲学 每个程序做好一件事。如果要做新的工作,则建立一个全新的程序,而不是通过增加新“特征”使旧程序变得更加复杂。 期待每个程序的输出成为另一个尚未确定的程序的输入。不要将输出与无关信息混淆在一起。避免使用严格的表格状或二进制输入格式。不要使用交互式输入 尽早尝试设计和构建软件,甚至是操作系统,最好在几周内完成。需要扔掉那些笨拙的部分时不要犹豫,并立即进行重建 优先使用工具来减轻编程任务,即使你不得不额外花费时间去构建工具,并且预期在使用完成后会将其中一些工具扔掉 统一接口 如果希望某个程序的输出成为另一个程序的输入,也就意味着这些程序必须使用相同的数据格式,换句话说,需要兼容的接口,在 UNIX 中,这个接口就是文件(更准确地出,是文件描述符) 逻辑与布线分离 UNIX 工具的另一个特点是使用标准输入(stdin)和标准输出(stdout) 这允许 shell 用户以任何他们想要的方式连接输入和输出:程序并不知道也不关心输入来自哪里以及输出到哪里。 将输入/输出的布线连接与程序逻辑分开,可以更容易地将小工具组合成更大的系统 透明与测试 UNIX 命令的输入文件通常被视为是不可变的。这意味着可以随意运行命令,尝试各种命令行选项,而不会损坏输入文件。 可以在任何时候结束流水线,将输出管道输送到 less ,然后查看它是否具有预期的形式。这种检查能力对调试非常有用。 可以将流水线某个阶段的输出写入文件,并将该文件用作下一阶段的输入。这使得用户可以重新启动后面的阶段,而无需重新运行整个流水线。 MapReduce 与分布式文件系统 MapReduce 有点像分布在数千台机器上的 UNIX 工具 不修改输入,无副作用,在分布式文件系统上读写文件 分布式文件系统 GFS HDFS Amazon S3 Azure Blob OpenStack Swift HDFS 包含一个在每台机器上运行的守护进程,并会开放一个网络服务以允许其他节点访问存储在该机器上的文件 容错 多个机器上的相同数据的多个副本 纠错码方案 MapReduce 作业执行 MapReduce 是一个编程框架,可以使用它编写代码来处理 HDFS 等分布式文件系统中的大型数据集 处理模式 读取一组输入文件,并将其分解成记录 调用 mapper 函数从每个输入记录中提取一个键值对 按关键字将所有的键值对排序 调用 reducer 函数遍历排序后的键值对 Mapper 每个输入记录都会调用一次 mapper 程序,其任务是从输入记录中提取关键字和值。对于每个输入,它可以生成任意数量的健值对(包括空记录)。它不会保留从一个输入记录到下一个记录的任何状态,因此每个记录都是独立处理的。 Reducer MapReduce 框架使用由 mapper 生成的键值对,收集属于同一个关键字的所有值,并使用迭代器调用 reducer 以使用该值的集合。Reducer 可以生成输出记录 MapReduce 的分布式执行 作业的输入通常是 HDFS 中的一个目录,且输入目录中的每个文件或文件块都被视为一个单独的分区,可以由一个单独的 map 任务来处理 让靠近数据的机器就近执行 mapper 任务,减少网络传输的负载,提高了访问局部性 map 任务的数量与 reduce 任务的数量不需要一致 为了使相同值的 mapper 输出交给同一个 reduce 处理,采用了关键字哈希分区 键值对必须排序。map 任务基于关键字哈希,按照 reducer 对输出进行分块。每个分区都被写入 mapper 程序所在文件磁盘上的已排序文件。 当 mapper 完成文件输出后,MP 调度器通知 reducer 从 mapper 中获取输出文件。reduce 从 mapper 中获取文件后把他们合并在一起,同时保持数据的排序。 Reduce 端的 join 与分组 在批处理的背景下讨论 join 时,我们主要是解决数据集内存在关联的所有事件 join 最简单的实现是遍历所有记录,并在远程服务器中查找对应的记录。 更好的方法是获取用户数据库的副本,并将其放入与用户活动事件日志相同的分布式文件系统。然后,可以将用户数据库放在 HDFS 中的一组文件中,并将用户活动记录放在另一组文件中,使用 MapReduce 将所有相关记录集中到一起,从而有效地处理它们。 排序-合并 join mapper 和排序过程确保将执行特定用户 ID join 操作的所有必要数据都放在一起,这样就只需要一次 reducer 调用。因为所有需要的数据已经预先排列好,所以 reducer 是一段相当简单的单线程代码,以高吞吐量和低内存开销来处理记录。 分组 在 mapper 阶段,使其生成的键值对使用所需的分组关键字。然后,分区和排序过程将相同 reducer 中所有具有相同关键字的记录集合在一起 处理数据倾斜 如果 join 输入中存在热键,则可以使用算法进行补偿。在真正开始执行 join 时,mapper 将任何与热键有关的记录发送到随机选择的若干个 reducer 中的一个,对于 join 的其他输入,与热键相关的记录需要被复制到所有处理该关键字的 reducer 中,这种技术将处理热键的工作分散到多个 reducer 上,可以更好地实现并行处理,代价是不得不将 join 的其他输入复制到多个 reducer 使用热键对记录进行分组并汇总时,可以分两个阶段进行分组。第一个 MapReduce 阶段将记录随机发送到 reducer,以便每个 reducer 对热键的记录子集执行分组,并为每个键输出更紧凑的聚合值。然后第二个 MapReduce 作业将来自所有第一阶段 reducer 的值合并为每个键的单一值 Map 端的 join 操作 广播哈希 join 实现 map 端 join 的最简单方住特别适合大数据集与小数据集 join,尤其是小数据集能够全部加载到每个 mapper 的内存中 当 mapper 程序执行时,它可以首先将用户数据库从分布式文件系统读取到内存的哈希表中。然后,mapper 程序扫描用户活动事件,并简单地查找哈希表中每个事件的用户 ID Map 任务依然可以有多个: 大数据集的每个文件块对应一个 mapper。每个 mapper 还负责将小数据集全部加载到内存中。 也可以存在磁盘中,由于缓存和索引的原因,和内存查找差不多快。 分区哈希 join 如果以相同方式对 map 端 join 的输入进行分区,则哈希 join 方法可以独立作用于每个分区 批处理工作流的输出 生成搜索索引 批处理输出键值 批处理输出的哲学 如果在代码中引入了漏洞,输出错误或者损坏,那么可以简单地回读到先前版本,然后重新运行该作业,将再次生成正确的输出; 或者更简单的办法是将旧的输出保存在不同的目录中,然后切换回原来的目录 与发生错误即意味着不可挽回的损害相比 ,易于回滚的特性更有利于快速开发新功能。这种使不可逆性最小化的原则对于敏捷开发是有益的 如果 map 或 reduce 任务失败, MapReduce 框架会自动重新安排作业并在同一个输入上再次运行,失败任务的输出则被 MapReduce 框架丢弃 对比 Hadoop 与分布式数据库 存储多样性 分布式文件系统中的文件只是字节序列,可以使用任何数据模型和编码来编写 来自事务处理 系统的数据以某种原始形式转储到分布式文件系统中,然后编写 MapReduce 作业进行数据清理,将其转换为关系表单,并将其导入 MPP 数据仓库以进行分析。数据建模仍然会发生,但它位于一个单独步骤中,与数据收集是分离的。由于分布式文件系统支持以任何格式编码的数据,所以这种解相是可行的。 处理模型多样性 并非所有类型的处理都可以合理地表达为 SQL 查询 由于 Hadoop 平台的开放性,可以在上面实施更多的处理模型 针对频繁故障的设计 MapReduce 可以容忍 map 或者 reduce 任务失败,单个失败可以重试。 MapReduce 容忍任意失败是为了更好的利用集群资源,允许高优先级任务抢占资源 超越 MapReduce MapReduce 很强大,但依然有些问题 对于某些类型的任务,其他工具可能要快几个数量级 中间状态实体化 MapReduce 会把中间结果写入文件,这个过程称为实体化 UNIX 管道不存在实体化,输出可以立即成为下一个的输入 几个问题 输出不会立马被利用,任务耗时会比预计的久 mapper 冗余,它们只是读取刚刚由 reducer 写入的同一个文件,并为下一个分区和排序阶段做准备。在许多情况下,mapper 代码可能是之前 reducer 的一部分:如果 reducer 的输出被分区和排序的方式与 mapper 输出相同,那么不同阶段的 reducer 可以直接链接在一起,而不需要与 mapper 阶段交错。 把中间状态文件存储在分布式系统中意味着这些文件被复制都多个节点了,对于这样的临时数据来说通常是大材小用了 数据流引擎 为了解决 MapReduce 的这些问题,开发了用于分布式批处理的新的执行引擎 Spark,Tez,Flink 它们把整个工作流作为一个作业来处理,而不是把它分解成独立的子作业 通过若干个处理阶段明确地建模数据流,所以这些系统被称为数据流引擎。像 MapReduce 一样,它们通过反复调用用户定义的函数来在单个线程上一次处理一条记录。它们通过对输入进行分区来并行工作,并将一个功能的输出复制到网络上,成为另一个功能的输入 。 流处理引擎可以以更加灵活的方式组装各种函数 对比 MapReduce 模型的几个优点 排序等计算代价昂贵的任务只在实际需要的地方进行,而不是在每个 map 和 reduce 阶段之间默认发生 没有不必要的 map 任务,因为 mapper 所做的工作通常可以合并到前面的 reduce 运算符中 由于工作流中的所有 join 和数据依赖性都是明确声明的,因此调度器知道哪些数据在哪里是必需的,因此它可以进行本地优化 将运算符之间的中间状态保存在内存中或写入本地磁盘通常就足够了 运算符可以在输入准备就绪后立即开始执行,在下一个开始之前不需要等待前个阶段全部完成。 现有的 Java 虚拟机进程可以被重用来运行新的运算符,从而减少启动开销。 容错 将中间状态完全实体化到分布式文件系统的一个优点是持久化,这使得在 MapReduce 中实现容错变得相当容易 Spark, Flink 和 Tez 避免将中间状态写入 HDFS,所以它们采用不同的方法来容忍错误: 如果机器发生故障,并且该机器上的中间状态、丢失,则利用其他可用的数据重新计算 为了实现重新计算,框架必须追踪给定数据是如何计算的,使用了哪个输入分区,以及应用了哪个运算符。 关于实体化的讨论 数据流对 MapReduce 的改进是,不需要自己将所有中间状态写入文件系统。 图与迭代处理 在批处理环境中查看图也很有趣,其目标是在整个图上执行某种离线处理或分析。这种需求经常出现在机器学习应用程序或排名系统中 Pregel 处理模型 作为对图数据的批处理优化,计算的批量同步并行模型 一个顶点可以“发送消息”到另一个顶点,通常这些消息沿着图的边被发送。 顶点状态和顶点之间的消息具有容错性和持久性,并且通信以固定的方式进行:每一轮迭代中,框架会将前一次迭代中的所有消息都发送出去。 Actor model 通常没有这样的时序保证。 容错 由于 Pregel 集型保证在一次迭代中发送的所有消息都会在下一次迭代中被发送,所以先前的迭代必须全部完成,而且所有的消息必须在下一次迭代 开始之前复制到网络中。 即使底层网络可能会丢弃、重复或任意延迟消息,但 Pregel 的实现可以保证在后续迭代中消息在目标顶点只会被处理一次。像 MapReduce 一样,该框架透明地从故障中恢复,以简化 Pregel 顶层算陆的编程模型。 这种容错方式是通过在迭代结束时定期快照所有顶点的状态来实现的,即将其全部状态写入持久存储。如果某个节点发生故障并且其内存中状态丢失,则最简单的解决方也是将整个图计算回攘到上一个检查点,然后重新开始计算。如果算法是确定性的, 并且记录了消息,那么也可以选择性地只恢复丢失的分区 并行执行 顶点不需要知道它运行在哪台物理机器上。当它发送消息到其他顶点时,只需要将消息发送至一个顶点 ID。框架对图进行分区,即确定哪个顶点运行在哪个机器上,以及如何通过网络路由消息,以便它们都能到达正确的位置。 高级 API 与语言 由于手工编写 MapReduc 巳作业太过耗时费力,因此 Hive、Pig、Cascading 和 Crunch 等高级语言和 API 变得非常流行。随着 Tez 的出现, 这些高级语言还能够移植到新的数据流执行引擎,而无需重写作业代码。Spark 和 Flink 也包含他们自己的高级数据流 API 这些高级接口不仅使提高了系统利用率,而且提高了机器级别的作业执行效率。 转向声明式查询语言 通过将声明式特征与高级 API 结合,使查询优化器在执行期间可以利用这些优化方法,批处理框架看起来就更像 MPP 数据库了,井且能够实现性能相当。同时,通过具有运行任意代码和读取任意格式数据的可扩展性,它们依然保持了灵活性的优势。 不同领域的专业化 要实现可重用的通用构建模块 可重复使用统计和数值算法 流处理系统 我们将把事件流视为一种数据管理机制: 一种无界的、持续增量处理的方式 发送事件流 在流处理的上下文中,记录通常被称为事件 本质上是一回事:一个小的、独立的、不可变的对象,该对象包含某个时间点发生的事情的细节。每个事件通常包含一个时间戳,用于指示事件发生的墙上时间 案例 服务器的每一行日志 用户的下单或者浏览 格式 文本 JSON 二进制 生成一次,读取多次 在流系统中,相关的时间通常被组合成主题或流 传统数据库无法支持实时的消息通知 消息系统 向消费者通知新事件的常见方法是使用消息系统:生产者发送包含事件的消息,然后该消息被推送给一个或多个消费者 当生产者发送消息比消费者处理快 系统丢弃消息 将消息存储在队列中 激活背压,也称流量控制,组织生产者发送过多消息 如果节点崩溃或者离线,是否会有消息丢失 持久化需要写入磁盘,需要成本,在可以接收消息丢失的系统上,在同样的硬件上可以将获得更高的吞吐量和更低的延迟 是否接收消息丢失取决于应用程序 生产者与消费者之间的直接消息传递 UDP 组播广泛应用与金融行业,例如股票市场等低延迟场景 无代理的消息库,过 TCP 或 IP 多播实现发布/订阅消息传递。 使用不可靠的 UDP 消息传递 消费者在网络上公开服务,则生产者可以直接发出 HTTP 或 RPC 请求以将消息推送给消费者 缺点 有限容错,消息丢失 生产者和消费者都需要保持在线 消息代理 它作为服务器运行,生产者和消费者作为客户端连接到它。 生产者将消息写入代理,消费者通过从消息代理那里读取消息来接收消息 消息代理与数据库对比 而大多数消息代理在消息成功传递给消费者时就自动删除消息。这样的消息代理不适合长期的数据存储。 消息代理的工作集很小,如果消费慢了就会占用很多内存,整体吞吐降低 数据库支持二级索引和各种搜索数据的方式,消息代理采用订阅匹配特定模式的主题 数据库查询基于数据快照,消息代理不支持查询 多个消费者 负载均衡式 每一条消息都只被传递给其中一个消费者,所以消费者可以共享主题中处理消息的工作。代理可以任意分配消息给消费者。 扇出式 每条消息都被传递给所有的消费者。扇出允许几个独立的消费者各自“收听”相同的消息广播,而不会相互影响,流相当于多个读取相同输入文件的不同批处理作业 确认和重新传递 消费者随时可能崩溃,消费者消费完事件后需要显式告知消息代理,消息代理才会从队列中删除 消息代理重试时间导致事件发生顺序改变,如果消息之间存在因果关系会导致问题。 分区日志 将数据库的持久存储方居与消息传递的低延迟功能相结合 基于日志的消息存储 日志是磁盘上一个仅支持追加式修改记录的序列,我们可以使用相同的结构来实现消息代理:生产者通过将消息追加到日志的末尾来发消息,消费者通过依次读取日志来接收消息。如果消费者读到日志的末尾,它就开始等待新消息被追加的通知。 为了突破单个磁盘所能提供的带宽吞吐的上限,可以对日志进行分区。不同的节点负责不同的分区,使每个分区成为一个单独的日志,并且可以独立于其他分区读取和写入。然后可以将主题定义为一组分区,他们都携带相同类型的消息 在每个分区中,代理为每个消息分配一个单调递增的序列号或偏移量。这样的序列号是非常有意义,因为分区只能追加,所以分区内的消息是完全有序的。不同分区之间则没有顺序保证。 对比日志与传统消息系统 都支持扇出式消息传递 因为同一分区内的消息将被传递到同一节点,所以消费一个主题的节点数最多等于该主题中的日志分区数 如果单个消息处理缓慢,则会阻碍该分区中的后续消息的处理 消费者偏移量 顺序读取一个分区可以很容易地判断哪些消息已经被处理,代理不需要跟踪每条消息的确认,只需要定期记录消费者的偏移量 磁盘空间使用 如果持续不断地追加日志,磁盘空间最终将被耗尽。为了回收磁盘空间,日志实际上是被分割成段,并且不时地将旧段删除或归档保存。 如果一个消费者的速度慢到难以跟上消息产生的速度,并且远远落后以至于消费者偏移量指向了已经被删除的片段,那么消费者将会错过一些消息。实际上,日志实现了一个有限大小的缓冲区,当缓冲区变搞时,旧的消息就被丢弃,该缓冲区也被称为循环缓冲区或环形 缓冲区。由于该缓冲区在磁盘上,因此它可以非常大。 当消费者跟不上生产者时 基于日志的方法是一种缓冲形式,它具有比较大的缓冲区 当消费者明显落后消息时发出警报,让操作员有时间修复 重新处理信息 可以用旧的偏移量重新开启一个消费队列,并将输出写到不同的位置,以便重新处理最后一段时间的消息,通过改变处理代码可以多次重复此操作。 数据库与流 保持数据同步 多数据系统数据一致性 变更数据捕获 捕获数据库中的更改并不断将相同的更改应用于搜索索引。如果以相同顺序应用于更改日志,那么可以预期搜索索引中的数据与数据库中的数据匹配。搜索索引和任何其他派生的数据系统只是变更流的消费者 实现变更数据捕获 我们可以调用日志消费者的派生数据,变更数据捕获机制可以确保对记录系统所做的所有更改都反映在派生数据系统中,以便派生系统具有数据的准确副本,从本质上讲,变更数据捕获使得一个数据库成为主节点,井将其他变成从节点。由于基于日志的消息代理保留了消息的排序,因此它非常适合从原数据库传输更改事件 原始快照 如果有了数据库所有更改的日志,就可以通过 replay 日志来重建数据库的整个状态。构建新的全文索引需要整个数据库的完整副本,仅仅应用最近更改的日志还不够,因为它会丢失最近未更新的项目。因此,如果没有完整的日志历史记录,则需要从一致的快照开始,数据库的快照必须与更改日志中的已知位置或偏移量相对应,以便在快照处理完成后,知道在哪一点开始应用更改。 日志压缩 存储引擎定期查找具有相同 key 的日志记录,丢弃所有的重复项,井且只保留每个 key 的最新的更新。这个压缩和合并的过程是在后台运行的。 对变更流的 API 支持 数据库将关系数据模型中的输出流表示为表,该表支持事务插入元组,但不支持查询。输出流包含了向该特殊表提交写事务的元组日志,并严格按照事务提交顺序排序。外部消费者可以异步使用此日志并使用它来更新派生数据系统。 时间溯源 在变更捕获中,CDC 记录了操作发生的顺序 时间溯源中,应用程序逻辑基于写入事件日志的不可变事件构成。 从事件日志导出当前状态 使用事件溯源的应用程序需要记录事件的日志,井将其转换为适合向用户显示的状态 。这种转换可以使用任意的逻辑,但它应该是确定性的,以便可以再次运行它并从事件日志中派生相同的应用程序状态。 用于更新记录的 CDC 事件通常包含记录的全部新版本,因此 key 的当前值完全由该 key 的最近事件确定,井且日志压缩可以丢弃相同 key 之前的事件 使用事件溯源在更高的层次上对事件建模: 事件通常用来表达用户行为的意图,而不是一种对行为结果进行相应状态更新的机制 命令和事件 事件溯源的哲学是小心的区分事件和命令。当来自用户的请求第一次到达时,它最初是一个命令:此时它可能仍然会失败,例如因为违反了某些完整性条件。应用程序必须首先验证它是否可以执行该命令。如果验证成功并且命令被接受,它将变成一个持久且不可变的事件。 状态,流与不可变 事务日志记录了对数据库所做的所有更改。高速追加是更改日志的唯一方位。从这个角度来看,数据库的内容保存了日志中最新记录值的缓存。日志是事实。数据库是日志子集的缓存。该缓存子集恰好是来自日志的每个记录和索引值的最新值。 日志压缩则是链接日志与数据库区别的一种方式。它仅保留每条记录的最新版本,井丢弃被覆盖的版本。 不变事件的优势 恢复历史数据 记录历史操作 相同的事件日志中派生出多个视图 通过从不变事件日志中分离可变状态,可以从相同的事件日志派生出多个面向读取的表示方式 并发控制 事件捕获和变更数据捕获的最大缺点是事件日志的消费者通常是异步的,所以用户可能会写入日志,然后从日志派生的视图中读取,却发现这些写操作还没有反映在读取视图中 一种解决方案是同步执行读取视图的更新,并将事件追加到日志中。这需要一个事务来将写入操作合并到一个原子单元中,所以要么需要将事件日志和读取视图保存在同一个存储系统中,要么需要跨不同系统的分布式事务。 另一方面,从事件日志导出当前状态也简化了并发控制。对于多对象事务的大部分需求源自单个用户需要在不同地方改变数据的操作。通过事件溯源,可以设计一个事件,使其成为用户操作的独立描述。用户操作只需要在一个地方进行一次写操作,即将事件追加到日志中,这很容易使其原子化。 不变形的限制 隐私,彻底删除数据 流处理 三种处理 可以将事件中的数据写入数据库、缓存、搜索索引或者类似的存储系统,然后被其他客户端查询 可以通过某种方式将事件推送给用户 可以处理一个或多个输入流以产生一个或多个输出流。数据流可能会先经过由几个这样的处理阶段组成的流水线,最终在输出端结束 流处理的适用场景 监控目的的流应用 信用风控 金融交易监控 机器状态监控 军事情报系统报警 复杂事件处理 在流中搜索特定模式的事件 流分析 测量某种类型事件的速率 计算一段时间内某个值的波动平均值 将当前的统计数据与以前的时间间隔进行比较 维护物化视图 使用数据库更改流来保持派生数据系统与源数据库之间的同步,可以将这些示例视为一种维护物化视图的例子: 对某个数据集导出一个特定的试图以便高效查询,并在底层数据更改时自动更新该导出视图。 在流上搜索 需要基于一些复杂条件来搜索单个事件, 搜索流是把查询条件先保存下来,所有文档流过查询条件,筛选出结果。 消息传递和 RPC 流的时间问题 流处理系统经常需要和时间打交道,尤其是在用于分析目的时,这些分析通常使用时间窗口 事件延迟处理会引发流处理各种问题,需要有介入处理这种问题 混淆事件时间与处理时间会导致错误的结果,重启流处理系统倒是的事件积压,出现处理高峰 什么时候准备就绪 无法确定是否完全收到特定窗口内所有的事件 忽略滞后的事件,丢失大量数据时报警 发布一个更新,针对滞后事件的一个更新值。可能还需要收回以前的输出 用一个特殊值来触发窗口处理 你用谁的钟 为了调整不正确的设备时钟,一种是方法是记录三个时间戳 根据设备的时钟,记录事件发生的时间。 根据设备的时钟,记录将事件发送到服务器的时间。 根据服务器时钟,记录服务器收到事件的时间。 窗口类型 轮转窗口 翻滚窗口长度固定,每个事件都属于一个窗口 跳跃窗口 窗口长度固定,窗口之间有重叠以提供平滑过渡 滑动窗口 滑动窗口包含在彼此的某个间隔内发生的所有事件, 滑动窗口可以通过保留按时间排序的事件缓冲区井且在从窗口过期时移除旧事件来实现 会话窗口 与其他窗口类型不同,会话窗口没有固定的持续时间。相反,它是通过将同一用户在时间上紧密相关的所有事件分组在一起而定义的,一旦用户在一段时间内处于非活动状态,则窗口结束。会话分析是网站分析中常见的一种需求 流式 join 流和流 join 搜索事件和点击事件 流和表 join 流处理提前加载表的内容,在流处理时匹配相关 ID 表和表 join 流视图和流视图的 join,每当视图更新刷新 join 结果 join 的时间依赖性 不同流和分区之间的事件,顺序是如何确定的 通常的做法是,当数据发生变化后赋予一个新的关联 ID 流处理的容错 批处理容错方法可以确保批处理作业的输出与没有出错时的最终结果相同 微批处理和校验点 将流分解成多个小块,并像小型批处理一样处理每个块。这种方法被称为微批处理 Apache Flink 中使用了该方法的一个变体,它定期生成状态滚动检查点并将其写入持久化存储。如果流操作发生崩溃,它可以从最近的检查点重新启动,并丢弃在上一个检查点和崩溃之间生成的所有输出 重新审视原子提交 在出现故障时,为了看起来实现恰好处理了一次,我们需要确保当且仅当处理成功时,所有输出和副作用才会生效. 幕等性 容等操作是可以多次执行的操作,并且它与只执行一次操作具有相同的效果 故障后重建状态 任何需要状态的流处理,比如基于窗口的聚合以及表和索引的 join 操作,都必须确保在故障发生后状态可以恢复 一种选择是将状态保存在远程存储中井采取复制,然而为每个消息去查询远程数据库可能会很慢。另一种方也是将状态在本地保存,并定期进行复制。之后,当流处理器从故障中恢复时,新任务可以读取副本的状态、井且在不丢失数据的情况下恢复处理。 在某些情况下,甚至可能不需要复制状态,而是从输入流开始重建 数据系统的未来 每一个软件,即使是所谓的“通用”数据库,也都是针对特定的使用模式而设计的, 第一个挑战就是弄清楚软件产品与他们适合运行环境之间的对应关系 在复杂的应用程序中,数据通常以多种不同的方式被使用。不太可能存在适用于所有不同环境的软件,因此你不可避免地要将几个不同的软件组合在一起,以提供应用程序的功能性。 数据集成 采用派生数据来组合工具 许多应用程序需要结合两种或以上不同的工具来满足所有需求。 数据集成的需求通常只有在缩小井考虑整个组织框架内数据流时才会变得更加凸显 为何需要数据流 通过单个系统来决定所有输入的写入顺序,那么以相同的顺序处理写操作就可以更容易地派生出数据的其他表示形式 无论是使用变更数据捕获还是事件获取日志,都不如简化总体顺序的原则重要 根据事件日志来更新一个派生数据系统通常会比较好实现,并且可以实现确定性和幂等性 派生数据与分布式事务 分布式事务通过使用锁机制进行互斥来决定写操作的顺序 CDC 和事件源使用日志进行排序 分布式事务使用原子提交来确保更改只生效一次 基于日志的系统通常基于确定性重试和幕等性 事务系统通常提供线性化,保证读自己的写一致性 派生数据系统通常是异步更新的,所以默认情况下它们无法提供类似级别保证。 作者认为基于日志的派生数据是集成不同数据系统的最有前途的方法 全局的局限 完全有序的日志需要一个主节点来决定排序,随着系统变大,越来越复杂时,瓶颈就开始出现了 事件吞吐量大于单台的可处理上限时,需要分区到多个节点,不同分区之间的事件顺序难以保证 如果服务器在不在的数据中心,数据同步效率效率低,通常每个数据中心都有自己的主节点,两个不同数据中心的事件顺序不确定。 无状态的微服务之间不共享状态,两个事件来自不同的服务时,这些事件没有清楚的顺序。 网络延迟甚至离线导致的数据不一致问题。 设计突破单节点吞吐量甚至在广域地理环境分布的共识算能仍然是一个有待研究的开放性问题 排序事件以捕获因果关系 逻辑时间戳可以在无协调者情况下提供的全序关系,所以当全序关系广播不可行时可以用得上,但是,它们仍然需要接收者 去处理那些乱序事件,井且需要额外的元数据 如果可以记录一条事件来标记用户在做决定以前所看到系统状态,并给该事件一个唯一的标识符,那么任何后续的事件都可以通过引用该事件标识符来记录因果关系 冲突解决算法,可以处理异常顺序的事件。 批处理和流处理集成 数据整合的目标是确保数据在所有正确的地方以正确的形式结束 批处理的数据是已知的有限大小 流处理运行在无界的数据集上 一种类型的处理可以通过另一种类型来模拟,尽管性能特征有所不同。 保持派生状态 批处理 倡导确定性 纯函数操作,输出仅依赖输入 输出不可变 追加式输出结果 流处理 除了批处理的特征 扩展了操作来支持可管理的,容错的状态 拥有良好定义的输入和输出的确定性函数原理上不仅有利用容错,还简化了组织中数据流的推理 从数据管道的角度来看,对于从一个事物派生出另一个事物,通过功能应用程序代码推动一个系统中的状态更改以及将这种效果应用到派生系统,都是有帮助的。 为应用程序演化而重新处理数据 为维护系统提供了一个良好的机制,平滑支持新功能以及多变的需求 通过重新处理,可以将数据集重组为一个完全不同的模型,以便更好地满足新要求。 派生视图可以逐步演变,知道所有用户迁移到新视图,如果有风险,总有一个工作系统可以回退 Lambda 架构 Lambda 体系结构的核心思想是进来的数据以不可变事件形式追加写到不断增长的数据集,类似于事件源。基于这些总事件,可以派生出读优化的视图。 统一批处理和流处理 支持以相同的处理引擎来处理最新事件和处理历史回放事件。 支持只处理一次语义 支持依据事件发生时间而不是处理时间进行窗口化 分拆数据库 编排多种数据存储技术 创建一个索引 数据库必须扫描表的一致性快照,挑选出所有被索引的字段值,对它们进行排序,然后得到索引。接下来,必须处理从一致性快照创建以来所累计的写入操作,完成后,只要有事务写入表中,数据库就必须持续保持索引处于最新状态。 索引是现有数据的一个视图 元数据库 联合数据库:统一端读 可以为各种各样的底层存储引擎和处理方法提供一个统一的查询接口:一种称为联合数据库或聚合存储的方法 分离式数据库:统一写端 在构建跨多个存储系统的数据库时,我们同样需要确保所有数据更改都会体现在所有正确的位置上,即使中间发生了某些故障。多个存储系统可以可靠地连接在一起 分离式如何工作 基于日志的集成的一大优势是各个组件之间的松耦合,这体现在两个方面 在系统级别,异步事件流使整个系统在应对各个组件的中断或性能下降时表现更加稳健,日志可以慢慢消费且不会丢失。 在人员角度看,分离式数据系统使得不同的团队可以独立的开发、改进和维护不同的软件组件和服务。专业化使得每个团队都可以专注于做好一件事情,且与其他系统维护清晰明确的接口,事件日志提供了一个足够强大的接口,不但能捕获相当强的一致性,同时也普遍适用于几乎任何类型的数据。 分离式与集成式系统 目前形式的数据库不会被取代 维护流处理器中的状态仍然需要数据库 专门的查询引擎对于特定的工作负载仍然很重要 运行多个不同的基础架构所带来的复杂性可能确是一个问题 不同的学习曲线 不同的配置 不同的操作习惯 单个集成的软件产品有可能确实在其针对的负载上表现更好,性能更可预测 分离的目标是让你可以将多个不同的数据库组合起来,以便在更广泛的工作负载范围内实现比单一软件更好的性能 当没有单一的软件能满足所有需求时,分离和组合的优势才会显现出来 围绕数据流设计应用系统 应用程序代码作为派生函数 当某个数据集从另一个数据集派生而来时,它一定会经历某种转换函数 二级索引是一种派生的数据集,它具有一个简单的转换函数:对于主表中的每一行或者一个文档,挑选那些索引到的列或者字段值,并且按照值进行排序 通过各种自然语言处理函数创建全文搜索索引,然后构建用于高效查找的数据结构 在机器学习系统中,可以考虑通过应用各种特征提取和统计分析功能从训练数据中导出模型。 缓存通常包含那些即将显式在用户界面的聚合数据 应用程序代码与状态分离 作者认为系统的某部分专注于持久性数据存储,同时有另外一部分专门负责运行应用程序代码是有道理的。这两部会有交互,但是各自仍保持独立运行。 数据库充当一种可以通过网络同步访问的可变共享变量。应用程序可以读取或更新变量,数据库负责持久性,提供一些井发控制和容错功能。 数据流: 状态变化和应用程序代码之间的相互影晌 当维护报生数据时,状态更改的顺序通常很重要,如果从事件日志中派生出了多个视图,每个试图都需要按照相同的顺序来处理这些事件,以使它们互相保持一致。 容错性是派生数据的关键: 丢失哪怕单个消息都会导致派生数据集永远无法与数据源同步。消息传递和派生状态更新都必须可靠。 流式处理与服务 面向服务的结构优于单体应用程序之处在于松相合所带来的组织伸缩性: 不同的团队可以在不同的服务上工作,这减少了团队之间的协调工作 数据流系统与微服务理念有很多相似的特征。但是,底层的通信机制差异很大:前者是单向、异步的消息流,而不是同步的请求/响应交互 最快和最可靠的网络请求就是根本没有网络请求 订阅变化的流,而不是在需要时去查询状态,使我们更接近类似电子表格那样的计算模型: 当某些数据发生更改时,依赖于此的所有派生数据都可以快速更新 观察派生状态 写路径和读路径涵盖了数据的整个过程,从数据收集到数据使用 写路径可以看作是预计算的一部分,即一旦数据进入,即刻完成,无论是否有人要求访问它。 过程中的读路径则只有当明确有人要求访问时才会发生。 实体化视图与缓存 全文索引:写路径构建了索引,读路径不需要扫描全部文档 缓存:对常见查询进行预计算,使这部分查询可以快速响应,其他的依然依靠索引,当添加新的数据时,视图也要随之更新 它们主要是调整读、写路径之间的边界。通过预先计算结果,写路径上承担了更多的工作,而读路径则可以简化加速 有状态,可离线客户端 SPA 应用支持很多有状态的功能,移动 app 也可以在本地保存很多状态,很多交互不需要和服务器通信。 我们可以将设备上的状态视为服务器上的状态缓存。屏幕上的呈现是一种客户端对象模型的实体化视图;而客户端的对象模型则是远程数据中心在本地的状态副本 状态更改推送至客户端 更新的 HTTP 协议支持从服务端推送事件到客户端,从而缩小两者之间状态的滞后程度 端到端的事件流 状态变化可以通过端到端的写路径流动:某个设备上交互行为触发了状态变化,通过事件日志、派生数据系统和流式处理等,一直到另一台设备上用户观察到状态。这些状态变化传播的延迟可以做到很低的水平,例如端到端只需一秒。 为了将写路径扩展到最终用户,我们需要从根本上重新思考构建这些系统的方式:从请求/响应交互转向发布/订阅数据流 更具晌应性的用户界面和更好的离线支持 读也是事件 当写入和读取都被表示为事件,并且被路由到相同的 stream operator 统一处理时,我们实际上是在查询流和数据库之间执行 stream-table join 操作。读事件需要发送到保存数据的数据库分区节点上 以日志方式记录读事件可能还可以帮助跟踪系统级别的事件因果关系和数据源: 它可以重建用户在做出某个决定之前看到的内容 多数据分区处理 对于仅涉及单个分区的查询,通过流来发送查询并收集响应事件流可能显得有些大材小用 。然而 ,这种方怯却开启了 一种分布式执行复杂查询的可能性,这需要合并来自多个分区的数据,并很好地借助底层流处理系统所提供的消息路由、分区和 join 功能。 端到端的正确性 数据库的端到端争论 仅仅因为应用程序使用了具有较强安全属性的数据系统,并不能意味着应用程序一定保证没有数据丢失或损坏,应用程序的 bug 或从数据库删除数据 Exactly-once 执行操作 使操作满足幂等性 维护额外的元数据确保节点丢失和切换中必要的 fencing 措施。 重复消除 许多模式都需要重复消除 TCP 采用序列号检测包丢失或重复,井最终确保数据包以正确的顺序接受,丢失的数据包都会被重新发送,并且在将数据交给应用程序之前,TCP 堆栈将负责删除重复的数据包。 网络不佳的情况下,客户端和服务端之间的事件可能会丢失,客户端上再次操作会导致事件重复提交 标识操作符 可以为每个事件生成一个唯一的标识符号,确保在服务端每个事件只被执行一次 端到端的争论 底层的可靠性功能本身不足以确保端到端的正确性。 在数据系统中采用端到端的思路 即使应用程序所使用的数据系统提供了比较强的安全属性,也并不意味着应用程序就一定没有数据丢失或损坏,应用程序本身也需要采取端到端的措施,例如重复消除。 事务处理的代价很高,特别是在楼及异构存储技术时 大多数的应用程序级别的容错机制无法正常工作导致了数据丢失或者损坏 探索更好的容错抽象是很有必要的 强制约束 唯一性约束需要达成共识 基于主节点做出所有的决策,就能够达成共识 无法支持异步的多主节点复制,发生写冲突,无法保证值的唯一性 单点失败,扩展性问题 基于日志的消息传递唯一性 日志机制可以确保所有消费者以相同的顺序查看消息,这种保证在形式上被称为全序关系广播,它等价于共识问题 在基于日志的消息传递的分离式数据库系统中,我们可以采用非常类似的方法来保证唯一性约束 任何可能冲突的写人都被路由到特定的分区并按顺序处理, 在每个分区内事件有唯一顺序 多分区请求处理 通过将多分区事务划分为两个不同分区的处理阶段,并使用端到端的请求 ID,实现了同样的正确性 实效性与完整性 实效性 时效性意味着确保用户观察到系统的最新状态 完整性 完整性意味着避免数据损坏,即没有数据丢失,也没有互相矛盾或错误的数据。尤其是,如果将某些派生数据集作为基础数据的视图来进行维护,派生必须做到正确, 如果完整性受到破坏, 这种不一致将是永久性的 数据流系统的正确性 可靠的流处理系统可以在不需要分布式事务和原子提交协议的情况下保持完整性 将写入操作的内容表示为单条消息,可以轻松地采用原子方式编写,这种方法非常适合事件源 使用确定性派生函数从该条消息报生所有其他状态的更新操作 通过所有这些级别的处理来传递客户端生成的请求 ID,实现端到端重复消除和容等性。 消息不可变,并支持多次重新处理派生数据,从而使错误恢复变得更容易 宽松的约束 传统的需要达成唯一性约束需要通过单节点汇聚所有分区事件实现 很多应用程序采取了弱一致性 如果万一两个人同时注册了相同的用户名或预订了同一个座位,则可以向其中一个发送道歉消息,并要求他们选择另一个,这种纠正错误的措施被称为补偿性事务 如果客户订购的商品超出当前库存,则可以追加补充库存,但需要为延误发货向客户道歉,并为他们提供折扣 很多场景中,实际上可以接受违反约束,通过后续的事务补偿来恢复最终的完整性 无需协调的数据系统 两种观察 数据流系统可以保证派生数据的完整性,无需原子提交,线性化或跨分区的同步协调。 唯一性约束要求时效性和协调性,但是只要整体上保证完整性,即使发生暂时约束破坏,可以事后进行修复,因此许多应用实际上采用宽松式的约束并没有问题。 数据流系统可以为应用提供数据管理服务而不需要协调,同时仍然提供强大的完整性保证。这种避免协调的数据系统具有很大的吸引力:与需要执行同步协调的系统相比,可以实现更好的性能和容错能力 跨数据中心多主节点异步复制系统,任何一个节点都可以独立运行,实效性弱,完整性强 同步协调只在有必要的时候使用 另一种理解协调和约束的方毡是:它们减少了由于不一致而引发的道歉数量,但是也可能降低系统的性能与可用性,并由此可能增加由于业务中断而引发的道歉数量 。你不能将道歉减少到零,但是你可以根据自己的需求找到最佳的折中方案:选择一个合适点使得既不能有太多不一致,也不能出现太多可用性问题。 信任,但要确认 总会有一些违反假设的事情发生,硬件和软件,我们不能假设依赖的基础设施不会出错 软件缺陷时的完整性 软件存在的 bug,无法通过校验和来捕获,一旦发现会造成数据的破坏,需要在设计,测试,代码检查方面经过大量的努力。 不要盲目信任承诺 硬件和软件并不能总是处于理想状态,数据损坏迟似乎只是迟早的事情而无也避免。因此,我们至少需要有办桂来查明数据是否已经损坏,以便之后修复这些数据,并试图找出错误的根掘。检查数据的完整性也被称为审计 。 成熟的系统同样会考虑不太可能的事情出错的可能性,并且主动管理这种风险。 如果想确保你的数据仍然在那,只能不断地去读取和检查。大多数情况下,情况一切正常,但万一发现异常,则越早发现问题越好。基于此,今早尝试从备份来恢复数据,否则当你丢失数据 ,你会发现连备份也已经破坏,那时将为时已晚。千万不要盲目地相信系统总是正常工作。 验证的文化 许多人认为正确性的保证是绝对的,而没有为少见但可能的数据损坏而有所准备,作者希望将来会有更多的自我验证或自我审计系统,不断的检查自身的完整性,而不是依赖盲目的信任。 可审计性的设计 基于事件的系统可以提供更好的可审计性。在事件源方法中,用户对系统中的输入都被表示为一个单一的不可变事件,并且任何结果状态的更新都是依据该事件派生而来。派生可以很确定性的执行并且是可重复的,所以通过相同版本的派生代码来处理相同的事件日志将产生相同的状态更新。 清楚地控制数据流可以使数据的来源管理更加清晰,从而使完整性检查更加可行 对于事件日志,我们可以使用哈希校验来检查存储层是否发生数据破坏 对于派生状态,我们可以重新运行对相同的事件日志执行的批处理和流处理,以检查是否得到相同的结果,甚至是并行运行一个冗余派生系统。 确定的和定义清晰数据流也有助于系统调试和跟踪系统的操作,从而确定为什么发生了某些事情。如果中间发生了意外事件,可以提供诊断能力来重现导致意外事件的相同环境,这种精准复现历史时刻的调试能力将非常有价值。 端到端论点的再讨论 检查数据系统的完整性最好以端到端的方式进行:在完整性检查中所包含的系统部件越多,则过程中某些阶段发生无告警的数据破坏的概率就越少。如果我们可以检查整个派生系统流水线是端到端正确的,那么路径中的任何磁盘、网络、服务和算法已经全部囊括在内了。 持续的端到端完整性检查可以提高你对系统正确性的信心,从而使你的发展速度更快 审计数据系统的工具 目前,将可审计性列为高优先级别关注的数据系统井不多。有些应用程序实现了内部的审计机制,例如将所有更改记录到单独的审计表中,但是保证审计日志的完整性和数据库状态仍然有些困难 做正确的事 每个系统的都有其构建目的,我们所采取的每一个行动都会产生有意或无意的后果。目的可能像赚钱一样简单,但对世界带来的影响可能远远超出我们的初衷。建立这些系统的工程师有责任仔细考虑这些后果,井有意识地决定我们想要生活在什么样的世界。 许多数据集都是关于人的: 他们的行为、他们的兴趣和他们的身份。我们必须以人性和尊重来对待这些数据。用户也是人,人的尊严是最重要的。 作者认为软件工程师如果只专注于技术而忽视其后果是不够的,道德责任也是我们要担起的责任。评判道德总是困难的,但它太重要了以至无论如何不能被忽视。 预测性分析 通过大数据算法预测一个人的犯罪倾向,自动化的系统则有可能系统地、任意地排除某个人参与社会活动,而且是在这个人没有任何犯罪证据的情况下,井且对他/她来说几乎没有上诉的机会。 偏见和歧视 算法做出的决定不一定比人类做得更好或更糟 如果在算法的输入中存在系统性偏见,那么系统很可能吸收并在最终输出中放大这种偏见 预测分析系统只是基于过去而推断,如果过去是有偏见的,它们就会把这种偏见编码下来。如果我们希望未来比过去更好,那么就需要道德想象力,而这只有人类才具备。数据和模型只应该是我们的工具,而不是我们的主人。 责任与问责 基于机器学习的评分算法通常使用更广泛的输入范围,而且更加不透明,更难理解某个特定决策是如何发生的,以及是否有人受到不公正的对待 盲目地相信数据至高无上不仅是误解的,而且是非常危险的 。随着数据驱动的决策变得越来越普遍,我们需要弄清楚如何使算陆更负责任和透明,如何避免强化现有的偏见,以及如何在错误不可避免时加以修复。 我们还需要弄清楚如何防止数据被滥用,井努力发挥数据的正面作用 反馈环路 当预测分析影响人们的生活时,特别是由于自我强化反馈环路而出现一些有害问题。由于不合适的假设,产生了这样一个隐藏在数学严谨性和数据的伪装背后的下降旋涡。 我们不是总能预测什么时候发生这样的反馈环路。然而,通过思考整个系统可以预测许多后果,这是一种被称为系统思维 的方法。我们可以尝试理解一个数据分析系统是如何响应不同的行为、结构和特征。系统是否强化和扩大了人们之间存在的差异?还是试图打击不公平性? 即使有最好的意图,我们也必须小心意外的后果 数据隐私与追踪 跟踪行为数据对于许多面向用户的在线服务变得越来越重要, 这些功能需要一定量的用户行为跟踪,井且用户也可以从中受益。但是,根据公司的商业模式,追踪往往不止于此。如果服务是通过广告获得资助的,那么广告主就是实际的客户,而用户的利益则是次要的。跟踪数据会更加详细,分析变得更加深入,数据也会被保留很长时间,以便为营销目去建立每个人的详细资 料。现在,公司和被收集数据的用户之间的关系开始变得和以往大不一样了。用户得到免费的服务,并尽可能地被引诱参与到服务中。对用户的追踪不再是服务与个人,而是服务于资助广告客户的需求。我认为这种关系可以用一个更阴暗的词来描述 : 监视。 监视 当监控被用来确定生活中重要的事情,例如保险或就业等方面的东西时,它就开始变得不那么亲切了。此外,数据分析可以揭示出令人惊讶的侵入性的事情 赞成与选择的自由 用户几乎不知道什么样的个人数据会进入到数据库,或者数据是如何保留和处理的,大多数隐私政策的条款也极尽所能地搞得含混不清。不清楚他们的数据会发生什么,用户就不能给予任何有意义的认同。通常,来自用户的数据还被用到了不是该服务的用户身上,并且该用户根本就没有同意数据收集的任何条款。 数据是通过单向过程从用户提取而来,而不是通过真正的互惠关系,也不是公平的价值交换。没有对话,用户无战选择提供多少数据以及他们会收到什么样的服务 :服务与用户之间的关系是非常不对称的 :这些条款是由服务提供商所设置,而不是由用户 由于担心服务跟踪用户而决定拒绝使用,这只对极少数拥有足够的时间和知识来充分了解隐私政策的人群可以称得上是一种选择,并且他们可以不需要担心由此可能会失去某些机会而被迫参与这些服务。然而,对于处境较差的人来说,选择自由没有意义:对他们来说,被监视变得不可避免。 数据隐私和使用 拥有隐私并不意味着一切事情都要保密:它意味着你可以自由选择向谁展示,并展示哪些东西,要公开什么,以及要保密什么。隐私权是一个决定权:每个人都能够决定在各种情况下如何在保密和透明之间取舍。这事关个人的自由和自主。 这些公司最终选择对大部分数据继续保持私密,因为泄露数据会引起可怕的后果,井且会损害它们的商业模式。关于用户的隐私信息通常是间接地被泄露,例如借助数据分析,将广告投放给特定人群 互联网服务使得在没有用户同意的情况下积累大量敏感信息更加容易,并且在用户不知情相关后果的前提下大规模地使用它。 数据作为资产和权力 数据中介公司的存在也印证了个人数据是宝贵资产的说法,这个数据中间商是一个秘密行业,从事采购、汇总、分析、推 断和兜售侵入性个人数据,主要是为了营销目的。很多初创公司主要靠它们的用户量来估价。 收集数据时,一定要综合考量 此外,审视他人但避免自我审查是最重要的权力形式之一。尽管今天的科技公司并没有公开地寻求某些权力,但是它们所积累的数据和知识给了它们很大的控制权力,而且很多是在私下进行,不在公众监督之内。 记住工业革命 数据是信息时代的关键性特征。互联网,数据存储,处理器和软件驱动的自动化正在对全球经济和人类社会产生重大影响。由此不由得联想到工业革命, 但工业革命也带来了注入环境污染,工人处境恶劣等一系列问题。 正如工业革命存在需要被管理的黑暗面一样,向信息时代的过搜也有需要面对和解决的重大问题。作者相信收集和使用数据就是其中一个 立法与自律 数据保护法可能有助于维护个人的权利 从根本上说,我认为需要对针对个人数据的技术领域有观念上转变。我们应该停止过度以用户为衡量指标,牢记用户值得尊重。我们应该主动调整数据收集和处理流程,建立和维持与那些依赖我们软件的人们之间的信任关系。我们应该主动向用户介绍他们的数据如何使用,而不是让他们蒙在鼓里全然不知 我们应该允许每个人维护自己的隐私,即控制自己的数据而不是通过监视来窃取他们的控制权 我们不应该永远保留数据,一且不再需要,就尽快清除它们 一个很有前途的方陆是通过加密协议来实施访问控制,而不仅仅是通过策略 总的来说,观念与态度的变化都是必要的。

2021 Mar 22 · 5 min

数据密集型应用系统设计::分布式数据系统

分布式数据系统 扩展性 容错与高性能 延迟考虑 系统扩展能力 共享内存架构 成本增长过快 无异地容错能力 共享磁盘架构 适用于数仓 资源竞争和锁开销限制扩展 无共享结构 水平扩展 扩展更加简单 复制与分区 复制 在多个节点保存相同的数据 分区 将一个大块头的数据库拆分成多个较小的子集 数据复制 目的 使数据在地理位置上更接近用户,从而降低访问延迟 当部分组件出现位障,系统依然可以继续工作,从而提高可用性 扩展至多台机器以同时提供数据访问服务,从而提高读吞吐量 三种复制方案 主从复制 工作原理 指定某一个副本为主副本(或称为主节点)。当客户写数据库时,必须将写请求首先发送给主副本,主副本首先将新数据写入本地存储 其他副本全部称为从副本或称为从节点。主副本把新数据写入本地存储后,然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本获得更改日志之后将其应用到本地,且严格保持与主副本相同的写入顺序。 客户端从数据库中读数据时,可以在主副本或者从副本上执行查询。再次强调,只有主副本才可以接受写请求,从客户端的角度来看,从副本都是只读的。 同步复制与异步复制 同步复制数据强一致性,但是会阻塞后续的写操作 异步响应速度快 实践中把一个副节点设置为同步复制,其他副节点设置为异步复制,当主节点不可用时,提升另一个副节点到主节点 全异步复制吞吐高,存在数据丢失问题,复制滞后问题 配置新的从节点 在某个时间点对主节点的数据副本产生一个一致性快照,这样避免长时间锁定整个数据库 将此快照拷贝到新的从节点 从节点连接到主节点并请求快照点之后所发生的数据更改日志 获得日志之后,从节点来应用这些快照点之后所有数据变更,这个过程称之为追赶。接下来,它可以继续处理主节点上新的数据变化 处理节点失效 从节点失效 从节点根据复制日志,知道故障之前最后一笔事务,然后连接到主节点,请求那笔事务后面所有的数据变更。 主节点失效 确认主节点失效,心跳检测 选举出新的主节点,共识算法 重新配置系统使得新节点生效,原主节点重新上线后要降级成从节点 变数 使用异步复制丢失数据,主从切换过程中丢失数据 其他依赖数据库的内容在一起使用 集群脑裂 不合适的超时检测 复制日志的实现 基于语句的复制 主节点记录所执行的每个写请求(操作语句)并将该操作语句作为日志发送给从节点 问题 调用 date(),rand()等函数会在从节点产生不一样的值 并发事务限制 有副作用的语句会在不同的节点产生不同的副作用 基于 WAL 传输 从节点收到日志进行处理,建立与主节点内容完全相同的数据副本 问题 复制方案和存储引擎紧密耦合 基于行的逻辑日志复制 关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求 对于行插入,日志包含所有相关列的新值。 对于行删除,日志里有足够的信息来唯一标识已删除的行,通常是靠主键,但如果表上没有定义主键,就需要记录所有列的旧值。 对于行更新,日志包含足够的信息来唯一标识更新的行,以及所有列的新值(或至少包含所有已更新列的新值)。 优势 与存储引擎结耦,更容易向后兼容 容易解析,可以发送到外部数据源 基于触发器的复制 触发器支持注册自己的应用层代码,使得当数据库系统发生数据更改(写事务)时自动执行上述自定义代码。通过触发器技术,可以将数据更改记录到一个单独的表中,然后外部处理逻辑访问该表,实施必要的自定义应用层逻辑,例如将数据更改复制到另一个系统。 问题 开销大 容易出错,有很多限制 复制滞后问题 主从复制要求所有写请求经过主节点,而任何副节点只能接收只读查询。 当从节点变多时,可以提高读请求的服务吞吐量,但是写请求吞吐变低 副节点落后与主节点,读到过期数据,一段时间后达成最终一致性 解决复制滞后的问题 写后读一致性 如果用户访问可能会被修改的内容,从主节点读取;否则,在从节点读取 客户端还可以记住最近更新时的时间戳 ,并附带在读请求中,据此信息,系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新 。如果不够新,要么交由另一个副本来处理,要么等待直到副本接收到了最近的更新。 时间戳可以是逻辑时间戳或实际系统时钟 如果副本分布在多数据中心,情况会更复杂些。必须先把请求路由到主节点所在的数据中心 跟踪最近更新的时间,如果更新后一分钟之内,则总是在主节点读取;并监控从节点的复制滞后程度,避免从那些滞后时 间超过一分钟的从节点读取 需要考虑的问题 记住用户上次更新时间戳的方法实现起来会比较困难,因为在一台设备上运行的代码完全无法知道在其他设备上发生了什么。此时,元数据必须做到全局共享 如果副本分布在多数据中心, 无法保证来自不同设备的连接经过路由之后都到达同一个数据中心,需要想办法确保将来自不同设备的请求路由到同一个数据中心 单调读 一个比强一致性弱,但比最终一致性强的保证。当读取数据时,单调读保证,如果某个用户依次进行多次读取,则他绝 不会看到回滚现象,即在读取较新值之后又发生读旧值的情况 一种实现方法是每个用户总是从同一副本执行读取 前缀一致读 保证是说,对于一系列按照某个顺序发生的写请求,那么读取这些内容时也会按照当时写入的顺序 一个解决方案是确保任何具有因果顺序关系的写入都交给一个分区来完成 多主节点复制 单节点单点失败问题 适用场景 多数据中心 在每个数据中心都配置主节点 每个数据中心内,采用常规的主从复制方案 数据中心之间,由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新 与单节点的主从复制方案的区别 就近访问,降低写入延迟,异步同步到其他数据中心 容忍数据中心失效,每个数据中心的主节点独立运行,失效主节点恢复后可以重新从其他主节点获取最新数据 容忍网络问题,主从模式写入是同步操作,需要更可靠的网络性能,多主节点是异步复制,可以更好容忍不可靠的网络 离线客户端操作 应用在离线后还需要继续工作的 日历,笔记 协作编辑 当一个用户编辑文档时,所做的更改会立即应用到本地副本,然后异步复制到服务器以及编辑同一文档的其他用户。 如果要确保不会发生编辑冲突,则应用程序必须先将文档锁定,然后才能对其进行编辑。如果另一个用户想要编辑同一个文档,首先必须等到第一个用户提交修改并释放锁。这种协作模式相当于主从复制模型下在主节点上执行事务操作。 为了加快协作编辑的效率,可编辑的粒度需要非常小。 处理写冲突 在不同的数据中心修改统一记录,在数据中心内部完成写入,在跨数据中心同步的时候出现写冲突 同步与异步冲突检测 同步冲突检测 等待写请求完成对所有副本的同步 丧失多主的优势 避免冲突 在应用层保证对同一记录的写请求只通过同一个主节点 由于主节点失效或者客户端漫游因为转到其他数据中心,此方法不再有效 收敛于一致状态的几个方案 给每个写入分配唯一的 ID,例如,一个时间戳,二个足够长的随机数,一个 UUID 或者一个基于键-值的哈希,挑选最高 ID 的写入作为胜利者,并将其他写入丢弃。如果基于时间戳,这种技术被称为最后写入者获胜。虽然这种方法很流行,但是很容易造成数据丢失。 为每个副本分配一个唯一的 ID,并制定规则,例如序号高的副本写入始终优先于序号低的副本 。这种方法也可能会导致数据丢失。 以某种方式将这些值合并在一起 利用预定义好的格式来记录和保留冲突相关的所有信息,然后依靠应用层的逻辑,事后解决冲突 自定义冲突解决逻辑 在写入时执行 只要数据库系统在复制变更日志时检测到冲突,就会调用应用层的冲突处理程序 在读取时执行 当检测到冲突时,所有冲突写入值都会暂时保存下来。下一次读取数据时,会将数据的多个版本读返回给应用层。应用层可能会提示用户或自动解决冲突,并将最后的结果返回到数据库。 自动冲突解决 无冲突的数据结构 可合并的持久数据结构,三向合并功能 操作转换,为可同时编辑的有序列表设计 拓扑结构 复制的拓扑结构描述了写请求从一个节点传播到其他节点的通信路径。 多个主节点存在多个可能的同步的拓扑结构。 环形拓扑结构 星型拓扑结构 全部-至-全部型拓扑结构 环形和星形拓扑的问题是,如果某一个节点发生了故障,在修复之前,会影响其他节点之间复制日志的转发。 全链接拓扑也存在一些自身的问题。主要是存在某些网络链路比其他链路更快的情况,从而导致复制日志之间的覆盖 为了使得日志消息正确有序,可以使用一种称为版本向量的技术 无主节点复制 选择放弃主节点,允许任何副本直接接受来自客户端的请求 节点失效时写入数据库 半数写入确认即可认为写入成功,读取时从多个副本同时读取,按照版本号确定那个值是最新的 读修复与反熵 失效节点上线后如何恢复错过的请求 读修复 当客户端并行读取多个副本时,可以检测到过期的返回值,然后将新值写入到该副本。这种方怯主要适合那些被频繁读取的场景。 反熵过程 数据存储用后台进程不断寻找副本之间的差异,将缺少的数据复制过去。如果没有反熵过程的存储系统只有在读的时候可以修复数据 读写 quorum 如果有 n 个副本,写人需要 w 个节点确认,读取必须至少查询 r 个节点, 则只要 w + r > n ,读取的节点中一定会包含最新值,一个常见的选择是设置 n 为某奇数(通常为 3 或 5), w = r = (n + 1) / 2 仲裁条件 w + r > n 定义了系统可容忍的失效节点数,如下所示: 当 w < n,如果一个节点不可用,仍然可以处理写入。 当 r < n,如果一个节点不可用,仍然可以处理读取。 假定 n=3, w=2, r=2,则可以容忍一个不可用的节点。 假定 n=5, w=3, r=3,则可以容忍两个不可用的节点 通常,读取和写入操作总是并行发送到所有的 n 个副本。参数 w 和参数 r 只是决定要等待的节点数。即有多少个节点需要返回结果,我们才能判断出结果的正确性。 Quorum 一致性的局限性 w + r > n 一定可以读到最新值,但是不一定要多数,只要读写之间有重叠就可以,可以等待更少的时间就可以返回。 即使 w + r > n 也可能读到旧值: 如果采用了 sloppy quorum,写操作的 w 节点和读取的 r 节点可能完全不同,因此无法保证读写请求一定存在重叠的节点 如果两个写操作同时发生,则无法明确先后顺序,需要根据时间戳来确定胜者,但由于时钟偏差问题,某些写入可能会被错误的抛弃 如果写操作与读操作同时发生 ,写操作可能仅在一部分副本上完成。此时,读取时返回旧值还是新值存在不确定性。 如果某些副本上已经写入成功,而其他一些副本发生写入失败,且总的成功副本数少于 w,那些已成功的副本上不会做回滚。这意味着尽管这样的写操作被视为失败,后续的读操作仍可能返回新值。 如果具有新值的节点后来发生失效,但恢复数据来自某个旧值, 则总的新值副本数会低于 w,这就打破了之前的判定条件 即使一切正常工作,也会出现一些边界情况。 监控旧值 即使应用可以容忍旧值,也需要了解复制当前的运行状态,如果出现了明显的滞后,它就是个重要的信号提醒我们需要采取必要的措施来排查原因。 对于主从复制的系统,由于主节点和从节点上写人都遵从相同的顺序,而每个节点都维护了复制日志执行的当前偏移量。通过对比主节点和从节点当前偏移量的差值,即可衡量该从节点落后于主节点的程度 对于无主节点的系统,还没有一个可用的方案。 宽松的 quorum 与数据回传 当客户端连不上存储节点时,把数据写入一个可访问的节点,这个节点不在 n 的结合中,等到恢复后,把这个数据的节点回传到 n 原始节点中。 多数据中心操作 副本的数量 n 是包含所有数据中心的节点总数。配置时,可以指定每个数据中心各有多少副本。每个客户端的写入都会发送到所有副本,但客户端通常只会等待来自本地数据中心内的 quorum 节点数的确认,这样避免了高延迟和跨数据中心可能的网络异常。尽管可以灵活配置,但对远程数据中心的写入由于延迟很高,通常都被配置为异步方式 检测并发写 最后写入者获胜 数据带上时间戳,丢弃较早的写入,牺牲了数据持久性,如果不能接收丢失数据的话,可以为每一次写入分配 UUID 主键 Happen-before 关系和并发 如果一个操作无能意识到另一个操作,那么旧可以称他们时并发操作 确定前后关系 服务器为每个主键维护一个版本号,每当主键新值写入时递增版本号,并将新版本号与写入的值一起保存。 当客户端读取主键时,服务器将返回所有当前值以及最新的版本号。且要求写之前,客户必须先发送读请求。 客户端写主键,写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样,会返回所有当前值,这样就可以像购物车例子那样一步步链接起多个写入的值。 当服务器收到带有特定版本号的写入时,覆盖该版本号或更低版本的所有值,但必须保存更高版本号的所有值。 合并同时写入的值 一个简单的方法是基于版本号或时间戳来选择其中的一个值,但这意味着会丢失部分数据。所以,需要在应用程序代码中额外做些工作。 考虑到在应用代码中合并非常复杂且容易出错,因此可以设计一些专门的数据结构来自动执行合并,例如, Riak 支持称为 CRDT 一系列数据结构,以合理的方式高效自动合并,包括支持删除标记。 版本矢量 当多个副本同时接受写入时,我们需要为每个副本和每个主键均定义一个版本号。每个副本在处理写入时增加自己的版本号,并且跟踪从其他副本看到的版本号。通过这些信息来指示要覆盖哪些值、该保留哪些并发值。 数据分区 面对一些海量数据集或非常高的查询压力,复制技术还不够,我们还需要将数据拆分成为分区,也称为分片 分区通常是这样定义的,即每一条数据(或者每条记录,每行或每个文档)只属于某个特定分区 采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上。这样一个大数据集可以分散在更多的磁盘上,查询负载也随之分布到更多的处理器上。 对单个分区进行查询时,每个节点对自己所在分区可以独立执行查询操作,因此添加更多的节点可以提高查询吞吐量。超大而复杂的查询尽管比较困难,但也可能做到跨节点的并行处理。 数据分区与数据复制 分区通常与复制结合使用,即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区,而同样的内容会保存在不同的节点上以提高系统的容错性。 一个节点可能即是某些分区的主副本,同时又是其他分区的从副本 键-值数据的分区 分区的主要目标是将数据和查询负载均匀分布在所有节点上 分区不均匀,则会出现某些分区节点比其他分区承担更多的数据量或查询负载,称之为倾斜。 负载严重不成比例的分区即成为系统热点 基于关键字区间分区 为每个分区分配一段连续的关键字或者关键宇区间范围,如果知道关键字区间的上下限,就可以轻松确定那个分区包含这些关键字。如果还知道哪个分区分配在哪个节点,就可以直接向该节点发出请求 为了更均匀地分布数据,分区边界理应适配数据本身的分布特征 每个分区内可以按照关键字排序保存,这样可以轻松支持区间查询,即将关键字作为一个拼接起来的索引项从而一次查询得到多个相关记录 分区热点问题 基于关键字哈希值分区 一个好的哈希函数可以处理数据倾斜并使其均匀分布 丧失了良好的区间查询特性 Cassandra 中的表可以声明为由多个列组成的复合主键。复合主键只有第一部分可用于哈希分区,而其他列则用作组合索引来对 Cassandra SSTable 中的数据进行排序 基于哈希的分区方法可以减轻热点,但是无法做到完全避免。 一个简单的解决方法是对这小部分热点数据添加随机数再次分区,缺点是查询时需要查询所有分区再做合并。 分区与二级索引 基于文档的二级索引 每个列表都有一个唯一的文档 ID,用此 ID 对数据库进行分区 每个分区完全独立,各自维护自己的二级索引 二级索引的查询代价高昂,容易导致读延迟显著放大 基于此条的二级索引分区 对所有的数据构建全局索引,而不是每个分区维护自己的本地索引 全局索引也必须进行分区,且可以与数据关键字采用不同的分区策略 分区再平衡 查询压力增加,因此需要更多的 CPU 来处理负载 数据规模增加,因此需要更多的磁盘和内存来存储数据 节点可能出现故障,因此需要其他机器来接管失效的节点 所有这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再平衡 需求 平衡之后,负载、数据存储、读写请求等应该在集群范围更均匀地分布。 再平衡执行过程中,数据库应该可以继续正常提供读写服务。 避免不必要的负载迁移,以加快动态再平衡,并尽量减少网络和磁盘 I/O 影响。 动态再平衡策略 节点增加时,取模再平衡导致频繁的数据迁移 固定数量的分区 首先创建远超实际节点数的分区数,然后为每个节点分配多个分区。 接下来,如果集群中添加了一个新节点,该新节点可以从每个现有的节点上匀走几个分区,直到分区再次达到全局平衡 分区的数量再创建数据库时就确定好,原则上可以拆分和合并 需要分区规模和数据规模相适应 动态分区 每个分区总是分配给一个节点,而每个节点可以承载多个分区,这点与固定数量的分区一样。当一个大的分区发生分裂之后,可以将其中的一半转移到其他某节点以平衡负载。 分区数量可以自动适配数据总量 少量的数据,少量的分区就足够了 大量的数据,每个分区的大小则被限制在一个可配的最大值 按节点比例分区 每个节点具有固定数量的分区。此时,当节点数不变时,每个分区的大小与数据集大小保持正比的增长关系;当节点数增加时,分区则会调整变得更小。较大的数据量通常需要大量的节点来存储,因此这种方式也使每个分区大小保持稳定。 全自动的平衡会出现难以预测的结果,将自动平衡与自动故障相结合也可能存在一定风险,让管理员介入再平衡是个更好的选择 请求路由 允许客户端链接任意的节点。如果某节点恰好拥有所请求的分区,则直接处理该请求:否则,将请求转发到下一个合适的节点,接收答复,并将答复返回给客户端。 将所有客户端的请求都发送到一个路由层,由后者负责将请求转发到对应的分区节点上 客户端感知分区和节点分配关系 并行查询执行 典型的数据仓库查询包含多个联合、过滤、分组和聚合操作。MPP 查询优化器会将复杂的查询分解成许多执行阶段和分区,以便在集群的不同节点上并行执行。尤其是涉及全表扫描这样的查询操作,可以通过并行执行获益颇多。 事务 出错 数据库软件或硬件可能会随时失效(包括正在执行写操作的过程中)。 应用程序可能随时崩溃(包括一系列操作执行到中间某一步)。 应用与数据库节点之间的链接可能随时会中断,数据库节点之间也存在同样问题。 多个客户端可能同时写入数据库 ,导致数据覆盖。 客户端可能读到一些无意义的、部分更新的数据。 客户端之间由于边界条件竞争所引入的各种奇怪问题。 深入理解事务 ACID 原子性(Atomicity) 在出错时中止事务,并将部分完成的写入全部丢弃。 一致性(Consistency) 指对数据有特定的预期状态,任何数据更改必须满足这些状态约束(或者恒等条件) 如果某事务从一个有效的状态开始,并且事务中任何更新操作都没有违背约束,那么最后的结果依然符合有效状态。 隔离性(Isolation) 并发执行的多个事务相互隔离,它们不能互相交叉,数据库系统要确保当事务提交时,其结果与串行执行完全相同 持久性(Durability) 提供一个安全可靠的地方来存储数据而不用担心数据丢失,一且事务提交成功,即使存在硬件故障或数据库崩溃,事务所写入的任何数据也不会消失 单对象和多对象事务操作 单对象写入 基于日志恢复实现原子性,对每个对象采取加锁的方式来实现隔离 通常意义上的事务针对的是多个对象,将多个操作聚合为一个逻辑执行单元 多对象事务的必要性 当出现跨分区时,多对象事务非常难以正确实现,同时在高可用或者极致性能的场景下也会带来很多负面影响 没有原子性保证时,错误处理就会异常复杂,而缺乏隔离性则容易出现并发性方面的各种奇怪问题 处理错误与中止 如果存在违反原子性、隔离性或持久性的风险,则完全放弃整个事务,而不是部分放弃。 支持安全的重试机制才是中止流程的重点 弱隔离级别 某个事务修改数据而另一个事务同时要读取该数据,或者两个事务同时修改相同数据时,才会引发并发问题 可串行化的隔离会严重影响性能,而许多数据库却不愿意牺牲性能,因而更多倾向于采用较弱的隔离级别,它可以防止某些但并非全部的并发问题 RC 读数据库时,只能看到已成功提交的数据 写数据库时,只会覆盖已成功提交的数据 脏读 一个事物写入部分数据,但是没有提交,另一个事务可以看到尚未提交的数据,意味着出现了脏读 防止脏读 如果事务需要更新多个对象,脏读意味着另一个事物可能会看到部分实现 事务中止,所有写入操作需要回滚,脏读导致另一个事务读取到需要被回滚的数据 防止脏写 后面的事务覆盖前面事务对同一个值的修改,RC 隔离级别可以防止脏写,通常的方法是推迟第二个写请求,知道前面的事务完成提交。 实现 RC 数据库通常采用行级锁来防止脏写:当事务想修改某个对象时,它必须首先获得该对象的锁;然后一直持有锁直到事务提交(或中止) 同样采用行锁来防止脏读:所有试图读取该对象的事务必须先申请锁,事务完成后释放锁。从而确保不会发生读取一个脏的、未提交的值 快照隔离级别与 RR RC 存在不可重复读的问题,在同一事物的多次读取中读到不同的值 场景 备份 分析查询与完整性检查场景 总体想法 每个事务都从数据库的一致性快照中读取,事务一开始所看到是最近提交的数据,即使数据随后可能被另一个事务更改,但保证每个事务都只看到该特定时间点的旧数据。 快照级别隔离对于长时间运行的只读查询(如备份和分析)非常有用。如果数据在执行查询的同时还在发生变化,那么查询结果对应的物理含义就难以理清。而如果查询的是数据库在某时刻点所冻结的一致性快照,则查询结果的含义非常明确。 实现快照级别隔离 与读-提交隔离类似,快照级别隔离的实现通常采用写锁来防止脏写,这意味着正在进行写操作的事务会阻止同一对象上的其他事务 读取时不需要加锁,这使得数据库在写入的同时不会影响长时间的只读查询。 多版本并发控制 考虑到多个正在进行的事务可能会在不同的时间点查看数据库状态,所以数据库保留了对象多个不同的提交版本 实现快照级别隔离 事务开始时,首先赋予一个唯一的、单调递增的事务 ID(txid)。每当事务向数据库写入新内容时,所写的数据都会被标记写入者的事务 ID。表中的每一行都有一个 created_by 字段,其中包含了创建该行的事务 ID。每一行还有一个 deleted_by 字段,初始为空。如果事务要删除某行,主行实际上并未从数据库中删除,而只是将 deleted_by 字段设置为请求删除的事务 ID 。事后,当确定没有其他事务引用该标记删除的行时,数据库的垃圾回收进程才去真正删除并释放存储空间。 一致性快照的可见性规则 每笔事务开始时,数据库列出所有当时尚在进行中的其他事务,然后忽略这些事务完成的部分写入,即不可见。 所有中止事务所做的修改全部不可见 较晚事务 ID 所做的任何修改不可见,不管这些事务是否完成了提交。 除此之外,其他所有的写入都对应用查询可见 可见性条件 事务开始的时刻,创建该对象的事务已经完成了提交 对象没有被标记为删除; 或者即使标记了,但删除事务在当前事务开始时还没有完成提交 索引与快照隔离级别 一种方案是索引直接指向对象的所有版本,然后想办法过滤对当前事务不可见的那些版本。当后台的垃圾回收进程决定删除某个旧对象版本时,对应的索引条目也需要随之删除 另一种追加/写时复制的技术,当需要更新时,不会修改现有的页面,而总是创建一个新的修改副本,拷贝必要的内容,然后让父结点,或者递归向上直到树的 root 结点都指向新创建的结点。那些不受更新影响的页面都不需要复制,保持不变并被父结点所指向 可重复读与命名混淆 快照级别隔离对于只读事务特别有效。但是,具体到实现,许多数据库却对它有着不同的命名。Oracle 称之为可串行化,PostgreSQL 和 MySQL 则称为可重复读 SQL 标准对隔离级别的定义还是存在一些缺陷,某些定义模棱两可,不够精确,且不能做到与实现无关。尽管有几个数据库实现了可重复读,表面上看符合标准,但它们实际所提供的保证却大相径庭 防止更新丢失 应用程序从数据库读取某些值,根据应用逻辑做出修改,然后写回新值。 当有两个事务在同样的数 据对象上执行类似操作时,由于隔离性,第二个写操作并不包括第一个事务修改后的值,最终会导致第一个事务的修改值可能会丢失 几种解决方案 原子写操作 原子操作通常采用对读取对象加独占锁的方式来实现,这样在更新被提交之前不会其他事务可以读它。这种技术有时被称为游标稳定性。另一种实现方式是强制所有的原子操作都在单线程上执行。 显示加锁 FOR UPDATE 指令指示数据库对返回的所有结果行要加锁 自动检测更新丢失 先让他们并发执行,但如果事务管理器检测到了更新丢失风险,则会中止当前事务,并强制回退到安全的“读-修改-写回”方式 原子比较与设置 UPDATE wiki_pages SET content = ’new content’ WHERE id = 1234 AND content = ‘old content’ 冲突解决与复制 对于多副本数据库,加锁和原子不再有效,通常采用异步的方式来更新,目前许多多副本数据库采用 LWW 策略,但是容易丢失更新 写倾斜与幻读 即如果两个事务读取相同的一组对象,然后更新其中一部分: 不同的事务可能更新不同的对象,则可能发生写倾斜; 而不同的事务如果更新的是同一个对象,则可能发生脏写或更新丢失 先前方案的限制 单对象的原子操作无效 自动检测不支持检测写倾斜 数据库不支持此约束 一个较优的选择是显示对依赖的数据加锁 在一个事务中的写入改变了另一个事务查询结果的现象,称为幻读 快照级别隔离可以避免只读查询时的幻读,但是对于我们上面所讨论那些读-写事务,它却无法解决棘手的写倾斜问题。 实体化冲突 如果查询结果没有对象可以加锁,人为引入一些可以加锁的对象 串行化 实际串行执行 解决并发问题最直接的方法是避免并发 可行性 内存越来越便直,现在讲多应用可以将整个活动数据集都加载到内存中。当事务所需的所有数据都在内存中时,事务的执行速度要比等待磁盘 I/O 快得多。 数据库设计人员意识到 OLTP 事务通常执行很快,只产生少量的读写操作。相比之下,运行时间较长的分析查询则通常是只读的,可以在一致性快照上运行,而不需要运行在串行主循环里。 采用存储过程封装事务 数据库设计者认为,如果整个过程是一个事务,那么就可以方便地原子化执行。 采用单线程串行执行的系统往往不支持交互式的多语句事务 优缺点 语言并没有跟上通用编程语言的发展,语义都相当丑陋、过时,而且缺乏如今大多数编程语言所常用的函数库。 在数据库中运行代码难以管理 数据库中一个设计不好的存储过程要比同样低效的应用服务器代码带来更大的麻烦 分区 为了扩展到多个 CPU 核和多节点,可以对数据进行分区 对于跨分区的事务,数据库必须在涉及的所有分区之间协调事务。存储过程需要跨越所有分区加锁执行,以确保整个系统的可串行化。 由于跨分区事务具有额外的协调开销,其性能比单分区内要慢得多 串行执行约束条件 事务必须简短而高效,否则一个缓慢的事务会影响到所有其他事务的执行性能 仅限于活动数据集完全可以加载到内存的场景 写入吞吐量必须足够低,才能在单个 CPU 核上处理; 否则就需要采用分区,最好没有跨分区事务。 跨分区事务虽然也可以支持,但是占比必须很小。 两段式加锁 多个事务可以同时读取同一对象,但只要出现任何写操作,则必须加锁以独占访问 如果事务 A 已经读取了某个对象,此时事务 B 想要写入该对象,那么 B 必须等到 A 提交或中止之才能继续。以确保 B 不会在事务 A 执行的过程中间去修改对象。 如果事务 A 已经修改了对象,此时事务 B 想要读取该对象,则 B 必须等到 A 提交或中止之后才能继续。对于 2PL,不会出现读到旧值的情况 实现 如果事务要读取对象,必须先以共享模式获得锁。可以有多个事务同时获得一个对象的共享锁,但是如果某个事务已经获得了对象的独占锁,则所有其他事务必须等待。 如果事务要修改对象,必须以独占模式获取锁。不允许多个事务同时持有该锁(包括共享或独占模式),换言之,如果对象上已被加锁,则修改事务必须等待。 如果事务首先读取对象,然后尝试写入对象,则需要将共享锁升级为独占锁。升级锁的流程等价于直接获得独占锁。 事务获得锁之后,一直持有锁直到事务结束(包括提交或中止)。这也是名字“两阶段”的来由,在第一阶段即事务执行之前要获取锁,第二阶段(即事务结束时)则释放锁。 由于使用了这么多的锁机制,所以很容易出现死锁现象,数据库系统会自动检测事务之间的死锁情况,并强行中止其中的一个以打破僵局,这样另一个可以继续向前执行。而被中止的事务需要由应用层来重试。 性能 降低了事务的并发性 2PL 模式下数据库的访问延迟具有非常大的不确定性 谓词锁 它的作用类似于之前描述的共享/独占锁,而区别在于,它并不属于某个特定的对象(如表的某一行),而是作用于满足某些搜索条件的所有查询对象 如果事务 A 想要读取某些搞足匹配条件的对象,例如采用 SELECT 查询,它必须以共享模式获得查询条件的谓词锁。如果另一个事务 B 正持有任何一个匹配对象的互斥锁,那么 A 必须等到 B 释放锁之后才能继续执行查询。 如果事务 A 想要插入、更新或删除任何对象,则必须首先检查所有旧值和新值是否与现有的任何谓词锁匹配(即冲突)。如果事务 B 持有这样的谓词锁,那么 A 必须等到 B 完成提交(或中止)后才能继续。 索引区间锁 谓词锁性能不佳 :如果活动事务中存在许多锁,那么检查匹配这些锁就变得非常耗时 大多数使用 2PL 的数据库实际上实现的是索引区间锁(或者 next­ key locking) ,本质上它是对谓词锁的简化或者近似 索引区间锁扩大了锁定了对象的范围,但是开销低了很多 如果没有合适的索引可以施加区间锁,数据库退回到添加表锁 可串行化的快照隔离 悲观与乐观的并发控制 可串行化的快照隔离是一种乐观并发控制 当事务提交时 (只有可串行化的事务被允许提交),数据库会检查是否确实发生了冲突(即违反了隔离性原则),如果是的话,中止事务并接下来重试。 基于过期的条件做决定 读取之前已经有未提交的写入 读取之后,又有新的写入 检测是否读取了过期的 MVCC 对象 当事务提交时,数据库会检查是否存在一些当初被忽略的写操作现在已经完成了提交,如果是则必须中止当前事务。 检测写是否影响了之前的读 当另一个事务尝试修改时,它首先检查索引,从而确定是否最近存在一些读目标数据的其他事务。这个过程类似于在受影响的宇段范围上获取写锁,但它并不会阻塞读取,而是直到读事务提交时才进一步通知他们 :所读到的数据现在已经发生了变化。 可串行化快照隔离的性能 可串行化快照隔离的一大优点是事务不需要等待其他事务所持有的锁 可串行化快照隔离可以突破单个 CPU 核的限制。 分布式系统的挑战 即使系统面临各种出错可能,也需要完成预定工作 故障与部分失效 单节点:要么工作,要么出错 分布式系统:部分失效和不确定性 云计算和超算 超算:定时备份任务状态,然后保存在持久存储上,当某节点出现故障,停止整个集群的任务,修复后从最近的检查点开始运行。 云计算 都是在线服务,无法容忍完全不可用 普通硬件,故障率较高 基于 IP 和以太网通信 总是会有部分组建故障 容忍系统部分失败 网络慢且不可靠 我们需要依靠软件提供容错,在不可靠系统上构建可靠的系统 需要知道在发生故障时,系统的预期行为是什么 不可靠的网络 系统的可靠性取决于最不可靠的组件 常见出错场景 请求可能已经丢失 请求还在队列,无法马上发送 请求接收方已经宕机 远程接收节点暂时无法响应 消息在回复过程中丢失 远程接收方已经处理请求,但回复却被延迟处理 现实中的网络故障 人为错误是故障的主要原因 冗余硬件不见得降低故障率 检测故障 负载均衡器需要避免向己失效的节点继续分发请求 对于主从复制的分布式数据库,如果主节点失败,需要将某个从节点提升为主节点,不过由于网络的不确定性很难判断节点是否确实失效。 然而不幸的是,由于网络的不确定性使得判断节点是否失效非常困难;而只有在某些特定场景下,或许你可以明确知道哪里出错了 假设可以登录节点,但发现服务进程没有侦听目标端口,那么操作系统会返回 RST 或 FIN 标志的数据包来辅助关闭或拒绝 TCP 连接。但是,如果节点在处理请求的过程中发生了崩溃,则很难知道该节点实际处理了多少数据 如果服务进程崩溃,但操作系统仍正常运行,可以通过脚本通知其他节点,以便新节点来快速接管而跳过等待超时。 如果有权访问数据中心网络交换机,则可以通过管理接口查询是否存在硬件级别的链路故障 如果路由器已经确认目标节点不可访问,则会返回 ICMP “目标不可达”数据包来回复请求 超时和无限期的延迟 较长的超时时间意味着更长时间的等待,才能宣告节点失败。 较短的时间可以快速帮助检测,但是可能出现误判,导致同一操作在不同节点执行了两次。 当一个节点故障,其承担的职责需要交给其他节点,这个过程会给其他节点和网络带来压力,特别是系统此时处于高负荷状态。转移负载会导致失效扩散,从而造成所有节点崩溃,服务完全不可用。 网络拥塞与排队 当多个不同节点同时发送数据包到相同的目标节点时,网络交换机会出现排队,然后依次将数据包转发到目标网络。如果网络负载过重,数据包可能必须等待一段时间才能获得发送机会。如果数据量太大,交换机队列塞满,之后的数据包则会被丢弃,网络还在运转,但会引发大量数据包重传。 当数据包到达目标机器后,如果所有 CPU 核都处于繁忙状态,则网络数据包请求会被操作系统排队,直到应用程序能够处理。根据机器的配置和负载情况,这里也会引人一段不确定的等待时间 在虚拟化环境下,CPU 核会切换虚拟机,从而导致正在运行的操作系统会突然暂停几十毫秒。在这段时间,客户虚机无屈从网络中接收任何数据,入向的包会被虚拟机管理器排队缓冲,进一步增加了网络延迟的不确定性 TCP 执行流量控制时,节点会主动限制自己的发送 速率以避免加重网络链路或接收节点负载。这意味着数据甚至在进入网络之前,已经在发送方开始了排队。 如采延迟或丢弃的数据价值不大, UDP 是个不错的选择 超时设置并不是一个不变的常量,而是持续测量响应时间及其变化,然后根据最新的响应时间分布来自动调整 同步和异步网络 固定电话有持续端到端的低延迟和足够的带宽来传输音频文件。 当通过电话网络拨打电话时,系统会动态建立一条电路:在整个线路上为呼叫分配一个固定的、带宽有保证通信链路,该电路一直维持到通话结束 这种网络本质是同步的:即使数据中间经过了多个路由器,16bit 空间在电路建立时已经在网络中得到预留,不会受到排队的影响。由于没有排队,网络最大的端到端延迟是固定的。我们称之为有界延迟。 网络 固定电话独占一段连接,网络连接则是尽可能使用所有带宽。 基于分组交换协议的网络注定收到排队的影响 TCP 动态调整传输速率则可以充分利用所有可用的网络容量 当前广泛部署的技术无法为我们提供延迟或可靠性方面的硬件级保证,我们必须假设会出现网络拥塞,排队和无上限的延迟 不可靠的时钟 但是由于网络的不确定延迟,精确测量面临着很多挑战。这些情况使得多节点通信时很难确定事情发生的先后顺序。 通过 NTP 服务器同步机器时间的时钟 单调时钟和墙上时钟 墙上时钟 与 NPT 同步,可以回退到过去,时间精度较为粗糙。 单调时钟 保证时间单调往前 不同的 CPU 有不同过得单调时间,任务在不同 CPU 调度时需要调整之间偏差。 精度高,可以计算微秒甚至更短的间隔。 时钟同步与准确性 计算机中的石英钟不够准确 如果与 NTP 服务器的时钟差别过大,可能会出现拒绝同步,或者本地时间将被强制重置 与 NTP 服务器同步失败 网络延迟导致的 NTP 服务器延迟 NTP 服务器故障,或者配置错误 闰秒处理,在一天的周期内逐步调整闰秒 虚拟机中的时钟会突然因为切换出现暂停,然后突然向前发生了跳跃 不信任不可控设备上的时钟 依赖同步的时钟 如果应用需要精确同步的时钟,最好仔细监控所有节点上的时钟偏差。如果某个节点的时钟漂移超出上限,应将其宣告为失效,并从集群中移除。这样的监控的目的是确保在造成重大影响之前尽早发现并处理问题 时间戳与事件顺序 多主节点复制的分布式数据库依赖墙上时钟,导致在 LWW 中,错误写入旧值 时钟的置信区间 时间存在误差,因此,我们不应该将时钟读数视为一个精确的时间点,而更应该视为带有置信区间的时间范围。 大多数系统不提供置信区间的信息,所以无法知道误差范围 全局快照的同步时钟 当数据库分布在多台机器上时,由于需要复杂的协调以产生全局的单调递增的事务 ID 进程暂停 其他节点该如何确信该主节点没有被宣告失效,可以安全地写入 定时从其他节点获取租约,只要租约不过期它就是主节点 进程暂停导致租约过期,被其他节点接管 GC 虚拟机暂停 终端休眠 上下文切换 磁盘 I/O 和网络 I/O 内存访问出现缺页异常 使用 SIGSTOP 暂停进程 保证响应时间 实时操作系统 内存分配收到严格限制或被禁止 需要大量测试验证 调整 GC 的影响 把 GC 暂停视为节点的一个计划内的临时离线,当节点启动垃圾回收时,通知其他节点来接管客户端的请求。此外 ,系统可以提前为前端应用发出预警,应用会等待当前请求完成,但停止向该节点发送新的请求,这样垃圾回收可以在无干扰的情况下更加高效运行。这个技巧以某种方式对客户端隐藏垃圾回收,降低负面影响 只对短期对象执行垃圾回收,然后在其变成长期存活对象之前,采取定期重启的策略从而避免对长期存活对象执行全面回收。每次选悻一个节点重新启动,在重启之前,重新平衡节点之间的流量,思路与读动升级类似 知识,真相与谎言 当节点不通时,无法判断是网络原因还是节点原因 真相由多数决定 超过一半的节点收不到某节点的回复则视为失败 节点不能判断自身的状态,需要依靠多数投票 主节点与锁 只允许一个节点作为数据库分区的主节点,以防止出现脑裂 只允许一个事务或客户端持有特定资源的锁,以防止同时写入从而导致数据破坏。 只允许一个用户来使用特定的用户名,从而确保用户名可以唯一标识用户 出错 节点的唯一锁失效之后认为自己还持有锁导致导致多个客户端同时写入出错 Fencing 令牌 我们假设每次锁服务在授予锁或租约时,还会同时返回一个 fencing 令牌,该令牌(数字)每授授予一次就会递增(列如,由锁服务增加)。然后,要求客户端每次向存储系统发送写请求时,都必须包含所持有的 fencing 令牌. 靠客户端自己检查锁状态是不够的,这种机制要求资掘本身必须主动检查所持令牌信息,如果发现已经处理过更高令牌的请求,要拒绝持有低令牌的所有写请求 服务端不能假设所有客户端都表现异常 拜占庭故障 节点返回了错误信息 节点发生故障 不遵从协议 恶意攻击 干扰网络 弱的谎言形式 网络丢包,包损坏 在应用层添加校验 客户端的输入 进行基本的安全检查 NTP 配置多个服务器得出正确的时间 理论系统模型与现实 计时模型 同步模型 同步模型假定有上界的网络延迟,有上界的进程暂停和有上界的时钟误差 部分同步模型 部分同步意味着系统在大多数情况下像一个同步系统一样运行,但有时候会超出网络延迟,进程暂停和时钟漂移的预期上界 异步模型 在这个模型中,一个算法不会对时机做任何的假设,甚至里面根本没有时钟 失效模型 崩溃-中止模型 在崩溃-中止模型中,算在去假设一个节点只能以一种方式发生故障,即遭遇系统崩溃。这意味着节点可能在任何时候突然停止响应,且该节点以后永远消失,无法恢复。 崩溃-恢复模型 节点可能会在任何时候发生崩溃,且可能会在一段(未知的)时间之后得到恢复并再次响应。在崩溃-恢复模型中,节点上持久性存储(即非易失性存储)的数据会在崩溃之后得以保存,而内存中状态可能会丢失。 拜占庭(任意)失效模型 节点可能发生任何事情,包括试图作弊和欺骗其他节点 算法的正确性 唯一性 两个令牌请求不能获得相同的值。 单调递增 如果请求 x 返回了令牌 tx,请求 y 返回了令牌 ty,且 x 在 y 开始之前先完成,那么 tx<ty 可用性 请求令牌的节点如果不发生崩溃则最终一定会收到响应 安全与活性 唯一性和单调递增属于安全属性,而可用性则属于活性。 安全性通常可以理解为“没有发生意外”,而活性则类似“预期的事情最终一定会发生” 如果违反了安全属性,我们可以明确指向发生的特定的时间点,且一旦违反安全属性,违规行为无法撤销,破坏已实际发生。 活性则反过来:可能无法明确某个具体的时间点,但总是希望在未来某个时间点可以满足要求 将系统模型映射到现实世界 现实远比理论复杂,系统需要现实大量验证,理论性分析与实证性检验对最终的成功同等重要。 一致性与共识 分布式系统最重要的抽象之一就是共识 一致性保证 大多数多副本的数据库至少提供了最终一致性,不写入的情况下,经过足够长的时间,预期所有的副本会收敛到相同的值。 在最终一致性之前,系统可能会在多次请求中读到不一致的值 更强的一致性模型 分布式一致性主要是针对延迟和故障等问题来协调副本之间的状态 线性化 时间顺序问题,因果顺序和全局顺序 自动提交事务达成共识 可线性化 让每个客户端都拥有相同的数据视图,而不必担心复制滞后 a.k.a 原子一致性,强一致性 在一个可线性化的系统中,一旦某个客户端成功提交写请求,所有客户端的读请求一定都能看到刚刚写入的值 如何达成线性化 基本思想:使系统看起来只有一个数据副本 约束:一旦某个读操作返回了新值,那么后续的写操作都必须返回新值 线性化的依赖条件 加锁与主节点选举 主从复制的系统需要确保有且只有一个主节点,否则会产生脑裂 选举新的主节点常见的方住是使用锁: 即每个启动的节点都试图获得锁,其中只有一个可以成功即成为主节点 提供协调者服务的系统如 Apache ZooKeeper 和 etcd 等通常用来实现分布式锁和主节点选举 线性化存储服务是所有这些协调服务的基础 约束与唯一性保证 唯一性约束在数据库中很常见, 用户名或电子邮件地址必须唯一, 这种情况本质上与加锁非常类似: 用户注册等同于试图对用户名进行加锁操作。该操作也类似于原子比较和设置: 如果当前用户名尚未被使用,就设置用户名与客户 ID 进行关联 唯一性约束需要线性化保证 跨通道的时间依赖 线性化违例之所以被注意到,是因为系统中存在其他的通信渠道 图片服务器的例子,发送消息比存储更快导致图片处理模块读不到图片 实现线性化系统 主从复制 部分支持可线性化 从主节点或者同步更新的节点读取满足线性化需要 节点失效重连后依然认为自己是主节点对外服务违反线性化 共识算法 可线性化 ZK 和 etcd 等系统用共识算法保证线性化 多主复制 不可线性化 无主复制 可能不可线性化 取决于 w + r > n 的配置 线性化与 quorum 严格遵从 quorum 可实现可线性化 同步读损失性能 线性化的代价 网络中断后无法实现可线性化 不要求线性化,服务可用 CAP CAP 有时也代表一致性,可用性,分区容错性,系统只能支持其中两个特性 分区是一种故障,当网络通常的时候可以满足 CAP,当网络出现的问题的时候需要在 CP 和 AP 中取舍 可线性化与网络延迟 实际上很少有系统真正满足线性化 现代多核 CPU 的内存屏障或者 fence 指令 多数系统不选择可线性化是为了性能而不是容错,无论是否有网络故障,可线性化对性能的影响都是巨大的 顺序保证 顺序与因果关系 果关系的依赖链条定义了系统中的因果页序,即某件事应该发生另一件事情之前 如果系统服从因果关系所规定的顺序,我们称之为因果一致性 因果关系并非全序 可线性化 在一个可线性化的系统中,存在全序操作关系。系统的行为就好像只有一个数据副本,且每个操作都是原子的,这意味着对于任何两个操作,我们总是可以指出哪个操作在先 因果关系 如果两个操作都没有发生在对方之前,那么这两个操作是并发关系。换言之,如果两个事件是因果关系,那么这两个事件可以被排序;而并发的事件则无法排序比较。这表明因果关系至少可以定义为偏序,而非全序。 可线性化系统里不存在并发操作,一定有一个时间线可以把所有操作都全序执行。 并发意味着时间线出现分支和合并,而不同分支上的操作无法直接比较 可线性化强于因果一致性 可线性化一定意味着因果关系 线性化并非是保证因果关系的唯一途径 捕获因果依赖关系 为保持因果关系,需要知道哪个操作发生在前 为了确定请求的因果依赖关系,我们需要一些手段来描述系统中节点所知道的“知识”。如果节点在写入 Y 时已经看到 X 值,则 X 和 Y 可能是属于因果关系。 序列号排序 使用序列号或时间戳来排序事件 它可以只是一个逻辑时钟,例如采用算法来产生一个数字序列用以识别操作,通常是递增的计数器。 序列号很紧凑,但是他们保证了全序关系,总是可以通过比较来确定大小。 非因果序列发生器 如果系统不存在这样唯一的主节点, 如何产生序列号就不是那么简单了 每个节点都独立产生自己的一组序列号 可以把墙上时间戳信息附加到每个操作上,LLW 采用这种方式。 可以预先分配序列号的区间范围 相比于把所有请求全部压给唯一的主节点具有更好的扩展性 所产生的序列号与因果关系并不严格一致 每个节点可能有不同的处理速度 物理时钟的时间戳会受到时钟偏移的影响 对于欲分配区间,操作被路由到不同分区 Lamport 时间戳 首先每个节点都有一个唯一的标识符,且每个节点都有一个计数器来记录各自已处理的请求总数。 Lamport 时间戳是一个值对(计数器,节点 ID)。两个节点可能会有相同的计数器值,但时间戳中还包含节点 ID 信息,因此可以确保每个时间戳都是唯一的。 给定两个 Lamport 时间戳,计数器较大那个时间戳大;如计数器值正好相同,则节点 ID 越大,时间戳越大。 每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值,并在每个请求中附带该最大计数器值。当节点收到某个请求(或者回复)时,如果发现请求内嵌的最大计数器值大于节点自身的计数器值,则它立即把自己的计数器修改为该最大值 只要把最大计数器值嵌入到每一个请求中,该方案可以确保 Lamport 时间戳与因果关系一致,而请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。 时间戳排序依然不够 对于唯一性约束依然需要全序关系来保证。 全序关系广播 如何扩展系统的吞吐量使之突破单一主节点的限制,以及如何处理主节点失效时的故障切换,在分布式系统研究文献中,这些问题被称为全序关系广播或者原子广播 全序关系广播通常指节点之间交换消息的某种协议 可靠发送 没有消息丢失,如果消息发送到了某一个节点,则它一定要发送到所有节点 严格有序 消息总是以相同的顺序发送给每个节点 全序关系广播正是数据库复制所需要的: 如果每条消息代表数据库写请求,并且每个副本都按相同的顺序处理这些写请求,那么所有副本可以保持 一致 可以使用全序关系广播来实现可串行化事务 全序关系广播的另一个要点是顺序在发送消息时已确定 采用全序广播实现线性化存储 全序关系广播是基于异步模型: 保证消息以固定的顺序可靠地发送,但是不保证消息何时发送成功 可线性化则强调就近性:读取时保证能够看到最新的写入值。 步骤 在日志中追加一条消息 广播给所有节点,等待回复 如果全都成功,那么返回给客户端成功的消息,否则失败 满足写顺序化,不满足读取顺序话 可以采用追加的方式把读请求排序、广播,然后各个节点获取该日志,当本节点收到消息时才执行真正的读操作 如果可以以线性化的方式获取当前最新日志中消息的位置,则查询位置,等待直到该位置之前的所有条目都已经发送给你,接下来再执行读取。 可以从同步更新的副本上进行读取,这样确保总是读取最新值。 采用线性化存储实现全序广播 假设有一个线性化的寄存器来存储一个计数,然后使其支持原子自增-读取操作或者原子比较-设置操作 对于每个要通过全序关系广播的消息,原子递增并读取该线性化的计数,然后将其作为序列号附加到消息中。接下来,将消息广播到所有节点,而接受者也严格按照序列化来发送回复消息 难点在于处理节点的网络中断,以及节点失效时如何恢复该值 分布式事务与共识 主节点选举 对于基于主从复制的数据库,由于网络问题出现节点之间无法通信,容易出争议。共识算法对于避免错误的故障切换非常重要。如果存在两个主节点,会导致数据不一致甚至丢失。 原子事务提交 对于支持跨节点跨区事务的数据库,事务在部分节点成功了,为了维护原子性,要么全部成功要么全部回退。 原子提交与两段式提交 单节点的原子提交 当客户端请求数据库节点提交事务时,数据库首先使事务的写入持久化,然后把提交记录追加写入到磁盘的日志文件中。如果数据库在该过程中间发生了崩溃,那么当节点重启后,事务可以从日志中恢复: 如果在崩溃之前提交记录已成功写入磁盘,则认为事务己安全提交;否则,回滚该事务的所有写入。 两阶段提交是一种在多节点之间实现事务原子提交的算法,用来确保所有节点要么全部提交,要么全部中止 当应用程序启动一个分布式事务时,它首先向协调者请求事务 ID。该 ID 全局唯一。 应用程序在每个参与节点上执行单节点事务,并将全局唯一事务 ID 附加到事务上。此时,读写都是在单节点内完成。如果在这个阶段出现问题,则协调者和其他参与者都可以安全中止。 当应用程序准备提交时 ,协调者向所有参与者发送准备请求 ,并附带全局事务 ID。如果准备请求有任何一个发生失败或者超时,则协调者会通知所有参与者放弃事务。 参与者在收到准备请求之后 ,确保在任何情况下都可以提交事务 ,包括安全地将事务数据写入磁盘,并检查是否存在冲突或约束违规。 一且向协调者回答“是”,节点就承诺会提交事务。换句话说,尽管还没有真正提交,但参与者已表态此后不会行使放弃事务的权利。 当协调者收到所有准备请求的答复肘,就是否提交或放弃事务要做出明确的决定。协调者把最后的决定写入到磁盘的事务日志中,防止稍后系统崩愤,并可以恢复之前的决定。这个时刻称为提交点。 协调者的决定写入磁盘之后 ,接下来向所有参与者发送提交或放弃请求。如果此请求出现失败或超时,则协调者必须一直重试,直到成功为止。此时,所有节点不允许有任何反悔:开弓没有回头箭,一旦做了决定,就必须贯彻执行,即使需要很多次重试。而如果有参与者在此期间出现故障,在其恢复之后,也必须继续执行。这是因为之前参与者都投票选择了“是”,对于做出的承诺同样没有反悔的余地。 参与者发生故障 在第一阶段,任何一个准备请求发生了失败或者超时,那么协调者就会决定中止事务 在第二阶段发生提交或中止请求失败,则协调者将无限期重试 协调者发生故障 如果协调者在发送准备请求之前就已失败,则参与者可以安全地中止事务 如果参与者接受了请求并做了投票是,它只能无限期等待协调者的决定。 部分节点没有接收到提交确认请求,在超时过后决定丢弃,导致数据不一致。 2PC 能够顺利完成的唯一方法就是等待协调者恢复。 实践中的分布式事务 数据库内部的分布式事务 某些分布式数据库支持跨数据库节点的内部事务 异构分布式事务 在异构分布式事务中,存在两种或两种以上不同的参与者实现技术。例如来自不同供应商的数据库,甚至是非数据库系统 Exactly-once 消息处理 异构的分布式事务旨在无缝集成多种不同的系统 当且仅当数据库中处理消息的事务成功提交,消息队列才会标记该消息已处理完毕 这个过程是通过自动提交消息确认和数据库写入来实现的。即使消息系统和数据库两种不同的技术运行在不同的节点上,采用分布式事务也能达到上述目标。 如果消息发送或数据库事务任何一个发生失败,则两者都须中止,消息队列可以在稍后再次重传消息。 只有在所有受影响的系统都使用相同的原子提交协议的前提下,这种分布式事务才是可行 XA 事务 异构环境下实施两阶段提交的一个工业标准 协调所有实现 API 的参与者进行同一的提交或者回滚 停顿时仍持有锁 在与协调者失去连接的时间内,参与者持有的锁将不会释放,这可能导致部分上层服务崩溃 从协调者故障中恢复 协调者崩溃恢复有各种不确定情况 允许参与者节点可以在紧急情况下单方面做出决定,放弃或者继续那些停顿的事务,而不需要等到协调者发出指令 分布式事务的限制 协调者不支持数据复制,单点故障 协调者不是无状态 XA 需要和各种数据系统兼容,无法深入不同系统的死锁条件 2PC 事务失败有扩大事务失败的风险 支持容错的共识 共识算法必须满足一下性质 协商一致性, 所有的节点都接受相同的决议。 诚实性,即对同一提议不能有两次决定 合法性,如果决定了值 v,则 v 一定是由某个节点所提议的 可中止性,节点不崩溃则最终一定可以达成决议 共识算法与全序广播 VSR,Paxos,Raft,Zab 全序关系广播 由于协商一致性,所有节点决定以相同的顺序发送相同的消息 由于诚实性,消息不能重复 由于合法性,消息不会被破坏,也不是凭空捏造的 由于可终止性,消息不会丢失 VSR,Raft 和 Zab 采用了全序关系广播,Paxos 的对应优化版本为 Multi-Paxos 主从复制和共识 一些数据库支持自动选举主节点和故障切换,通过选举把某个从节点者提升为新的主节点 所有的节点都需要同意主节点,否则两个主节点会导致数据库出现不一致。因此,我们需要共识算在去选出一位主节点 Epoch 和 Quorum 目前所讨论的所有共识协议在其内部都使用了某种形式的主节点,虽然主节点并不是固定的。相反,他们都采用了一种弱化的保证 : 协议定义了一个世代编号(epoch number,对应于 Paxos 中的 ballot number,VSP 中 view number,以及 Raft 中的 term number),并保证在每个世代里,主节点是唯一确定的。 如果当前主节点失效,节点就开始议论投票选举新的主节点。选举会赋予一个单调自增的 epoch 号。如果出现了两个不同的主节点对应不同 epoch 号码,具有更好 epoch 号码的主节点将获胜。 在主节点做出任何决定之前,它必须首先检查是否存在比它更高的 epoch 号码,否则就会产生冲突的决定 它必须从 quorum 节点中收集投票,主节点如果想要做出某个决定,须将提议发送给其他所有节点,等待 quorum 节点的响应。quorum 通常由多数节点组成。并且,只有当没有发现更高 epoch 主节点存在时,节点才会对当前的提议进行投票。 两轮投票 首先是投票决定谁是主节点,然后是对主节点的提议进行投票 如果某个提议获得通过,那么其中参与投票的节点中必须至少有一个也参加了最近一次的主节点选举 换言之,如果在针对提议的投票中没有出现更高 epoch 号码,那么可以得出这样的结论:因为没有发生更高 epoch 的主节点选举,当前的主节点地位没有改变,所以可以安全地就提议进行投票。 共识的局限性 在达成一致性决议之前,节点投票的过程是一个同步复制过程 共识体系需要严格的多数节点才能运行。这意味着需要至少三个节点才能容忍一个节点发生故障 多数共识算在是假定一组固定参与投票的节点集,这意味着不能动态、添加或删除节点 共识系统通常依靠超时机制来检测节点失效。在网络延迟高度不确定的环境中,特别是那些跨区域分布的系统,经常由于网络延迟的原因,导致节点错误地认为主节点发生了故障。虽然这种误判并不会损害安全属性,但频繁的主节点选举显著降低了性能,系统最终会花费更多的时间和资晾在选举主节点上而不是原本的服务任务 共识算法往往对网络问题特别敏感,可能导致主节点频繁切换 成员与协调服务 ZK 和 etcd 通常被成为分布式键值存储或者协调与服务配置。 ZooKeeper 和 etcd 主要针对保存少量、可完全载入内存的数据而设计。 特性 线性化的原子操作 多个节点同时加锁,只有一个会成功 操作全序 对每个操作都赋予了一个单调递增的事务 ID 故障检测 通过心跳检测对话,长时间不响应则释放锁 更改通知 客户端可以知道其他客户端何时加入以及是否发生故障 使用场景 节点任务分配 检测到新节点加入时,将任务调度到新节点 服务发现 把服务和 ip 注册到 ZK 服务发现是否需要共识存在争论,可以起到复制作用 成员服务 成员服务用来确定当前哪些节点处于活动状态并属于集群的有效成员

2021 Mar 21 · 6 min

数据密集型应用系统设计::数据系统基础

数据系统基础 可靠、可扩展与可维护的应用系统 数据密集型应用通常基于标准模块构建而成,每个模块负责单一的常用功能 数据库:用以存储数据,这样之后应用可以再次访问 高速缓存:缓存那些复杂或操作代价昂贵的结果,以加快下一次访问 索引:用户可以按关键字搜索数据并支持各种过滤 流式处理:持续发送消息至另一个进程,处理采用异步方式 批处理:定期处理大最的累积数据 可靠性 当出现意外情况如硬件、软件故障、人为失误等,系统应可以继续正常运转 对软件典型的期望 应用程序执行用户所期望的功能 可以容忍用户出现错误或者不正确的软件使用方法 性能可以应对典型场景、 合理负载压力和数据量 系统可防止任何未经授权的访问和滥用 可能出错的事情称为错误(faults)或故障 系统可应对错误则称为容错(fault­ tolerant)或者弹性(resilient) 容错总是指特定类型的故障,这样的系统才更有实际意义 故障通常被定义为组件偏离其正常规格 失效意味系统作为一个整体停止,无法向用户提供所需的服务。 通过故意引发故障的方式,来持续检验、测试系统的容错机制,增加对真实发生故障时应对的信心 硬件故障 采用硬件冗余方案对于大多数应用场景还是足够的 多机冗余则只对少最的关键应用更有意义,对于这些应用,高可用性是绝对必要的 通过软件容错的方式来容忍多机失效成为新的手段,或者至少成为硬件容错的有力补充 软件错误 因为节点之间是由软件关联的,因而往往会导致更多的系统故障 避免软件故障需要考虑很多细节 认真检查依赖 的假设条件与系统之间交互 进行全面的测试 进程隔离 允许进程崩溃并自动重启 反复评估,监控并分析生产环节的行为表现 等 人为失误 人是不可靠的,该如何保证系统的可靠性呢 以最小出错的方式来设计系统。 想办法分离最容易出错的地方、容易引发故障的接口 充分的测试: 从各单元测试到全系统集成测试以及手动测试 当出现人为失误时,提供快速的恢复机制以尽最减少故障影响 设置详细而清晰的监控子系统,包括性能指标和错误率 推行管理流程并加以培训 等 可靠性的重要性 导致商誉下降,影响效率,营收损失 即使在所谓 “非关键“ 应用中我们也应秉持对用户负责的态度 可扩展性 可扩展性是用来描述系统应对负载增加能力的术语 随着规模的增长, 例如数据量、 流量或复杂性,系统应以合理的方式来匹配这种增长 描述负载 负载可以用称为负载参数的若干数字来描述 Web 服务器的每秒请求处理次数 数据库中写入的比例 聊天室的同时活动用户数量 缓存命中率 等 描述性能 负载增加,但系统资源(如 CPU、内存、网络带宽等)保持不变,系统性能会发生什么变化 负载增加,如果要保持性能不变,需要增加多少资源 延迟与响应时间 响应时间是客户端看到的:除了处理请求时间(服务时间,service time)外,还包括来回网络延迟和各种排队延迟 延迟则是请求花费在处理上的时间 不要将响应时间视为一个固定的数字,而是可度量的一种数值分布 影响响应时间的因素 上下文切换和进程调度 网络数据包丢失和 TCP 重传 垃圾回收暂停 缺页中断和磁盘 I/O 服务器机架的机械振动 我们经常考察的是服务请求的平均响应时间 中位数指标非常适合描述多少用户需要等待多长时间 采用较高的响应时间百分位数(tail latencies, 尾部延迟或长尾效应)很重要, 因为它们直接影响用户的总体服务体验 系统响应时间取决于最慢的那个服务 垂直扩展(升级到更强大的机器) 水平扩展(将负载分布到多个更小的机器) 最近通常的做法一直是,将数据库运行在一个节点上,直到高扩展性或高可用性的要求迫使不得不做水平扩展。 超大规模的系统往往针对特定应用而高度定制,架构取决于多种因素 读取量、写入量 待存储的数据量 数据的复杂程度 响应时间要求 访问模式 等 对于早期的初创公司或者尚未定型的产品,快速迭代推出产品功能往往比投入精力来应对不可知的扩展性更为重要。 可维护性 软件的大部分成本在于整个生命周期的持续投入 开发阶段 维护与缺陷修复 监控系统来保持正常运行 故障排查 适配新平台 搭配新场景 技术缺陷的完善 增加新功能 等 可运维性 监视系统的健康状况,并在服务出现异常状态时快速恢复服务 追踪问题的原因,例如系统故障或性能下降 保持软件和平台至最新状态,例如安全补丁方面 了解不同系统如何相互影响,避免执行带有破坏性的操作 预测未来可能的问题,并在问题发生之前即使解决(例如容量规划) 建立用于部署、配置管理等良好的实践规范和工具包 执行复杂的维护任务,例如将应用程序从一个平台迁移到另一个平台 当配置更改时,维护系统的安全稳健 制定流程来规范操作行为,并保持生产环境稳定 保持相关知识的传承 简单性 复杂性有各种各样的表现方式 状态空间的脖胀 模块紧耦合 令入纠结的相互依赖关系 不一致的命名和术语 为了性能而采取的特殊处理 为解决某特定问题而引入的特殊框架 消除意外复杂性最好手段之一是抽象 一个好的设计抽象可用于各种不同的应用程序 也带来更高质量的软件 设计好的抽象还是很有挑战性 可演化性 一成不变的系统需求几乎没有,想法和目标经常在不断变化 组织流程方面,敏捷开发模式为适应变化提供了很好的参考 数据模型与查询语言 数据模型可能是开发软件最重要的部分 复杂的应用程序可能会有更多的中间层 每层都通过提供一个简洁的数据模型来隐藏下层的复杂性 关系模型 数据被组织成关系 每个关系都是元组(tuples)的无序集合(在 SQL 中称为行) 如果数据存储在关系表中,那么应用层代码中的对象与表、行和列的数据库模型之间需要一个笨拙的转换层 查询优化器自动决定以何种顺序执行查询,以及使用哪些索引 只需构建一次查询优化器,然后使用该数据库的所有应用程序都可以从中受益 网络模型 它也被称为 CODASYL 模型 网络模型中,一个记录可能有多个父结点 在网络模型中,记录之间的链接不是外键,而更像是编程语言中的指针 访问记录的唯一方法是选择一条始于根记录的路径,并沿着相关链接依次访问。 查询和更新数据库变得异常复杂而没有灵活性 文档模型 无强制模式 数据的结构是隐式的,只有在读取时才解释 文档通常存储为编码为 JSON、XML 或其二进制变体的连续字符串 存储局部性具有性能优势 局部性优势仅适用需要同时访问文档大部分内容的场景 NoSQL Not Only SQL 比关系数据库更好的扩展性需求,包括支持超大数据集或超高写入吞吐量 普遍偏爱免费和开源软件而不是商业数据库产品 关系模型不能很好地支持一些特定的查询操作 对关系模式一些限制性感到沮丧,渴望更具动态和表达力的数据模型 在可预见的将来,关系数据库可能仍将继续与各种非关系数据存储一起使用,这种思路有时也被称为混合持久化 文档数据库的比较 在表示多对一和多对多的关系时,关系数据库和文档数据库并没有根本的不同 相关项都由唯一的标识符引用 在关系模型中被称为外键 文档模型中被称为文档引用 支持文档数据模型的主要论点是模式灵活性, 由于局部性而带来较好的性能 关系模型则强在联结操作、多对一和多对多关系更简洁的表达上,与文档模型抗衡 对于高度关联的数据,文档模型不太适合,关系模型可以胜任,而图模型则是最为自然的 融合关系模型与文档模型是未来数据库发展的一条很好的途径 数据存储与检索 哈希索引 Bitcask 默认存储引擎 提供高性能的读和写,只要所有的 key 可以放入内存 只需一次磁盘寻址 只追加到文件末尾,不做原地更新 适合每个键的值频繁更新的场景 执行压缩的同时将多个段合并在一起以节省空间 优点 追加和分段合并主要是顺序写,它通常比随机写入快得多 如果段文件是追加的或不可变的,则并发和崩溃恢复要简单得多 合并旧段可以避免随着时间的推移数据文件出现碎片化的问题 局限性 hash 表必须全部放入内存,磁盘表现难以良好 区间查询查询效率低 SSTables 要求 key-value 对按照 key 排序 每个键在每个合并的段文件中只能出现一次 合并段更加简单高效 在文件中查找特定的键时,不再需要在内存中保存所有键的索引 在压缩块开头保存稀疏索引 构建和维护 SSTables 当写入时,将其添加到内存中的平衡树数据结构中(例如如红黑树)。这个内存中的树有时被称为内存表。 当内存表大于某个闹值(通常为几兆字节)时,将其作为 SSTable 文件写入磁盘。由于树已经维护了按键排序的 key-value 对,写磁盘可以比较高效。新的 SSTable 文件成为数据库的最新部分。当 SSTable 写磁盘的同时 ,写入可以继续添加到一个新的内存表实例 为了处理读请求,首先尝试在内存表中查找键,然后是最新的磁盘段文件,接下来是次新的磁盘段文件,以此类推,直到找到目标(或为空) 后台进程周期性地执行段合并与压缩过程,以合并多个段文件,并丢弃那些已被覆盖或删除的值 崩溃处理 - 在磁盘上保留单独的日志,每个写入都会立即追加到该日志,每当将内存表写入 SSTable 时,相应的日志可以被丢弃 LSM-tree Log-Structured Merge-Tree 确定键不存在之前,必须先检查内存表,然后将段一直回溯访问到最旧的段文件 为了优化这种访问,存储引擎通常使用额外的布隆过滤器 可以支持非常高的写入吞吐量。 B-trees 经受了长久的时间考验 是几乎所有关系数据库中的标准索引实现 B-tree 将数据库分解成固定大小的块或页, 这种设计更接近底层硬件,因为磁盘也是以固定大小的块排列 查找索引中的一个键时, 从根开始。 孩子都负责一个连续范围内的键,相邻引用之间的键可以指示这些范围之间的边界。 大多数数据库可以适合 3~4 层的 B-tree 使 B-tree 可靠 B-tree 底层的基本写操作是使用新数据覆盖磁盘上的旧页, 对该页的所有引用保持不变 从崩溃中恢复, 预写日志(write-ahead log, WAL),也称为重做日志 每个 B-tree 的修改必 须先更新 WAL 然后再修改树本身的页 多个线程要同时访问 B-tree , 注意并发控制 ,否则线程可能会看到树处于不一致的状态。通常使用锁存器(轻量级的锁)保护树的数据结构来完成 优化 B-tree 利用 COW 来做并发控制 保存键的缩略信息,而不是完整的键,这样可以节省页空间 对树进行布局,以便相邻叶子页可以按顺序保存在磁盘上 添加额外的指针到树中。 例如,每个叶子页面可能会向左和向右引用其同级的兄弟页,这样可以顺序扫描键,而不用跳回到 父页 分形树 对比 B-tree 和 LSM-tree B-tree 的 实现比 LSM-tree 的实现更为成熟 LSM-tree 通常对于写快 而 B-tree 被认为对于读取更快。读取通常在 LSM-tree 上较慢 LSM-tree 的优点 LSM-tree 通常能够承受比 B-tree 更高的写入吞吐量 它们有时具有较低的写放大 它们以顺序方式写入紧凑的 SSTable 文件 磁盘的顺序写比随机写要快得多 LSM-tree 可以支持更好地压缩,因此通常磁盘上的文件比 B-tree 小很多 更少的碎片 LSM-tree 的缺点 压缩过程有时会干扰正在进行的读写操作 压缩和写入共享带宽, 数据库的数据量越大,压缩所需的磁盘带宽就越多 写入高并且压缩没有仔细配置,随着未合并段的不断增加,读取会变慢 其他索引结构 二级索引 索引中的键是查询搜索的对象 实际存储的行 对其他地方存储的行的引用 存储行的具体文件被称为堆文件 避免数据复制,实际数据只存在一个地方 当新值大于旧值时,需要将数据移动到新空间,在原地保存一个指向新地址的指针 将索引行直接存储在索引中,聚簇索引 在某些数据库中,表的主键始终是聚簇索引,表的二级索引引用主键索引 索引覆盖 索引中保存了一些表的列值,刚好满足查询条件 加快读取速度,更大的写开销和事物开销 多列索引 将几个字段按照顺序组成一个键 专门的空间索引,R 树 全文索引 Lucene 采用了类似 SSTable 的索引结构 内存中的索引是键中的字符序列的有限状态自动机 在内存中保存所有内容 用于缓存的内存数据库可以容忍丢失 不能丢失的可以持久化到磁盘或者冗余到其他机器 关系型数据库的数据也可以完全存在数据库 使用磁盘格式的编码开销大于 KV 结构的数据库 基于内存的数据库可以提供更多的数据结构 更容易水平扩展 NVM 技术的发展 事务处理与分析处理 ACID(原子性、一致性、隔离性和持久性) OLTP 和 OLAP 对比 属性 OLTP OLAP 主要读特征 基于键,每次查询返回少量的记录 对大量记录进行汇总 主要写特征 随机访问,低延迟写入用户的输入 批量导入( ETL)或事件流 典型使用场景 终端用户,通过网络应用程序 内部分析师,为决策提供支持 数据表征 最新的数据状态(当前时间点) 随着时间而变化的所有事件历史 数据规模 GB 到 TB TB 到 PB OLTP 存储引擎 日志结构 原地更新 SQL 可以同时胜任 OLAP 和 OLTP 数据仓库 在线的数据分析影响 LATP 性能 数据仓库可以针对分析访问模式进行优化 星型和雪花型分析模式 星型模型 模式的中心是一个所谓的事实表,事实表的每一行表示特定时间发生的事件 其他列可能会引用其他表的外键,称为维度表 事实表中的每一行都代表一个事件,维度通常代表事件的对象(who)、什么(what)、地点(where)、时间(when)、方法(how)以及原因(why) 雪花模型 在星型模型的基础上维度进一步细分为子空间 在典型的数仓中,表的列非常宽,有时有几百列 列式存储 访问的数据通常只有少数列 来自表的一列的所有值相邻存储 列压缩 位图编码 内存带宽和矢量化处理 CPU 缓存 SIMD 列存储中的排序 行的存储顺序并不太重要 第一列排序出现相同值时,可以指定第二列继续进行排序 面向列的存储具有多个排序顺序,这有些类似在面向行的存储中具有多个二级索引 列存储的写操作 LSM-Tree 物化聚合 物化视图,内容是一些查询的结果 从虚拟视图查询时,SQL 引擎将其动态扩展到视图的底层查询,然后处理扩展查询 OLAP 立方体,由不同唯独分组的聚合网格 数据立方体缺乏像查询原始数据那样的灵活性 数据编码与演化 双向的兼容性 较新的代码可以读取由旧代码编写的数据 较旧的代码可以读取由新代码编写的数据 数据编码格式 在内存中,数据保存在对象、结构体、列表、数组、哈希表和树等结构中。这些数据结构针对 CPU 的高效访问和操作进行了优化 将数据写入文件或通过网络发送时,必须将其编码为某种自包含的字节序列 语言特定的格式 语言绑定 安全问题 兼容性问题 性能问题 JSON,XML,CSV 数字编码有很多模糊之处。在 XML 和 csv 中,无怯区分数字和碰巧由数字组成的字符串 JSON 区分字符串和数字,但不区分整数和浮点数,并且不指定精度。 JSON 和 XML 对 Unicode 字符串(即人类可读文本)有很好的支持,但是它们不支持二进制字符串(没有字符编码的字节序列) XML 和 JSON 都有可选的模式支持 CSV 没有任何模式,因此应用程序需要定义每行和每列的含义 二进制变体 大数据集收益明显 MessagePack 一种 JSON 的二进制编码 Thrift 与 Protocol Buffers 需要模式来编码任意的数据 Thrift 与使用 Thrift 接口定义语言来描述模式 Protocol Buffers 使用类似模式 没有字段名 如果字段设置了 required,但字段未填充,则运行时检查将出现失败 字段标签和模式演化 字段标签(field tag)对编码数据的含义至关重要。编码永远不直接引用字段名称 可以添加新的字段到模式,只要给每个字段一个新的标记号码。如果旧的代码(不知道添加的新标记号码)试图读取新代码写入的数据,包括一个它不能识别的标记号码中新的字段,则它可以简单地忽略该字段 只要每个字段都有一个唯一的标记号码,新的代码总是可以读取旧的数据,因为标记号码仍然具有相同的含义 为了保持向后兼容性,在模式的初始部署之后添加的每个字段都必须是可选的或具有默认值 Avro 二进制编码格式 Avro IDL 用于人工编辑 另一种(基于 JSON)更易于机器读取 只有当读取数据的代码使用与写入数据的代码完全相同的模式肘,才能正确解码二进制数据。读和写的模式如果有任何不匹配 都将无法解码数据 模式演化 在不同的上下文环境中保存单一的模式 模式的优点 它们可以比各种“二进制 JSON”变体更紧凑,可以省略编码数据中的宇段名称。 模式是一种有价值的文档形式,因为模式是解码所必需的,所以可以确定它是最新的 模式数据库允许在部署任何内容之前检查模式更改的向前和向后兼容 对于静态类型编程语言的用户来说,从模式生成代码的能力是有用的,它能够在编译时进行类型检查 数据流模式 进程间数据流动的方式 通过数据库 通过服务调用 通过异步消息传递 基于数据库的数据流 服务版本不一致 向前兼容,旧版本的代码不处理新版本加入的值 不同时间写入不同的值导致字段丢失 创建归档时使用统一的编码 基于服务的数据流 REST 和 RPC 服务器公开的 API 称为服务 服务器和客户端使用的数据编码必须在不同版本的服务 API 之间兼容 网络服务 运行在用户设备上的客户端应用程序,通过 HTTP 向服务发出请求, 这些请求通常通过公共互联网进行 一种服务向同一组织拥有的另一项服务提出请求,这些服务通常位于同一数据中心内 ,作为面向服务/微型架构的一部分。支持这种用例的软件有时被称为中间件 一种服务向不同组织所拥有的服务提出请求,经常需通过互联网 。这用于不同组织后端系统之间的数据交换。此类别包括由在线服务(如信用卡处理系统)提供的公共 API,或用于共享访问用户数据的 OAuth 有两种流行的 Web 服务方方法 : REST 和 SOAP REST 它强调简单的数据格式,使用 URL 来标识资源,并使用 HTTP 功能进行缓存控制、身份验证和内容类型协商 SOAP 基于 XML 的协议,用于发出网络 API 请求 SOAP Web 服务的 API 使用被称为 WSDL 过于复杂, 无法手动构建,SOAP 用户严重依赖工具支持、代码生成和 IDE 远程过程调用(RPC)的问题 结果不可预测 服务幂等 网络波动 大对象编码解析 不同的语言的支持问题 RPC 的发展方向 封装可能失败的异步操作 并行请求多项服务 服务发现 RPC 方案的向后和向前兼容性属性取决于它所使用的具体编码技术 基于消息传递的数据流 如果接收方不可用或过载,它可以充当缓冲区,从而提高系统的可靠性。 它可以自动将消息重新发送到崩溃的进程,从而防止消息丢失。 它支持将一条消息发送给多个接收方 它在逻辑上将发送方与接收方分离 消息代理 一个进程向指定的队列或主题发送消息,并且代理确保消息被传递给队列或主题的一个或多个消费者或订阅者 在同一主题上可以有许多生产者和许多消费者 主题只提供单向数据流 消息代理通常不会强制任何特定的数据模型 分布式 Actor 框架 Actor 模型是用于单个进程中并发的编程模型 逻辑被封装在 Actor 中,而不是直接处理线程 每个 Actor 通常代表一个客户端或实体,它可能具有某些本地状态(不与其他任何 Actor 共享) 它通过发送和接收异步消息与其他 Actor 通信。 不保证消息传送: 在某些错误情况下,消息将丢失。 由于每个 Actor 一次只处理一条消息,因此不需要担心线程,每个 Actor 都可以由框架独立调度。 三种流行的分布式 Actor 框架处理消息编码的方式 默认情况下,Akka 使用 Java 的内置序列化,它不提供向前或向后兼容性。但是,可以用类似 Protocol Buffers 的东西替代它,从而获得滚动升级的能力 默认情况下, Orleans 使用不支持滚动升级部署的自定义数据编码格式:要部署新版本的应用程序,需要建立一个新的集群,将流量从旧集群导入到新集群,然后关闭旧集群。像 Akka 一样,也可以使用自定义序列化插件。 在 Erlang OTP 中,很难对记录模式进行更改, 滚动升级在技术上是可能的,但要求仔细规划。

2021 Mar 20 · 3 min

系统设计::设计谷歌硬盘

设计谷歌硬盘 近年来,Google Drive、Dropbox、微软 OneDrive 和苹果 iCloud 等云存储服务已经变得非常流行。在本章中,你被要求设计 Google Drive。 在进入设计之前,让我们花点时间来了解一下 Google Drive。Google Drive 是一个文件存储和同步服务,帮助你在云端存储文档、照片、视频和其他文件。你可以从任何电脑、智能手机和平板电脑访问你的文件。你可以轻松地与朋友、家人和同事分享这些文件[1]。图 15-1 和 15-2 分别显示了谷歌硬盘在浏览器和移动应用程序上的样子。 理解问题并确定设计范围 设计谷歌硬盘是一个大项目,因此,提出问题以缩小范围是很重要的。 应聘者:最重要的功能是什么? 面试官:上传和下载文件,文件同步,以及通知。 应聘者:这是一个移动应用,一个网络应用,还是两者都有? 面试官:都是。 应聘者:支持的文件格式有哪些? 面试官:任何文件类型。 应聘者:文件是否需要加密? 面试官:是的。是的,存储中的文件必须是加密的。 应聘者:文件大小有限制吗? 面试官:有,文件必须是 10GB 或更小。 应聘者:该产品有多少用户? 面试官:10M DAU。 在本章中,我们将重点介绍以下功能。 添加文件。添加文件的最简单方法是将文件拖放到 Google Drive 中。 下载文件。 在多个设备上同步文件。当一个文件被添加到一个设备上时,它将自动同步到其他设备。 查看文件修订情况。 与你的朋友、家人和同事分享文件 当一个文件被编辑、删除或与你分享时,发送通知。本章未讨论的功能包括。 谷歌文档的编辑和协作。Google doc 允许多个人同时编辑同一个文件。这不在我们的设计范围之内。 除了澄清需求之外,了解非功能需求也很重要。 可靠性。可靠性对于一个存储系统是极其重要的。数据丢失是不可接受的。 快速的同步速度。如果文件同步需要太多时间,用户会变得不耐烦并放弃该产品。 带宽使用。如果一个产品需要大量不必要的网络带宽,用户就会不高兴,特别是当他们使用移动数据计划时。 可扩展性。系统应该能够处理大量的流量。 高可用性。当一些服务器离线、速度减慢或出现意外的网络错误时,用户仍应能使用该系统。 粗略估计 假设该应用程序有 5000 万注册用户和 1000 万 DAU。 用户得到 10GB 的免费空间。 假设用户每天上传 2 个文件。平均文件大小为 500KB。 读写比为 1:1。 分配的总空间。5000 万 * 10 GB = 500 Petabyte 上传 API 的 QPS:1000 万 * 2 峰值 QPS = QPS * 2 = 480 提出高水平的设计并获得认同 我们不从一开始就展示高层次的设计图,而是采用一种稍微不同的方法。我们将从简单的东西开始:在一个单一的服务器中建立所有的东西。然后,逐渐扩大规模,支持数百万用户。通过做这个练习,它将刷新你对书中涉及的一些重要话题的记忆。 ...

2021 Feb 15 · 3 min

系统设计::设计YOUTUBE

设计 YOUTUBE 在本章中,你被要求设计 YouTube。这个问题的解决方案可以应用于其他面试问题,如设计一个视频共享平台,如 Netflix 和 Hulu。图 14-1 显示了 YouTube 的主页。 YouTube 看起来很简单:内容创作者上传视频,观众点击播放。它真的那么简单吗?并非如此。在简单的背后有很多复杂的技术。让我们看看 2020 年 YouTube 的一些令人印象深刻的统计数据、人口统计学和有趣的事实[1] [2]。 每月活跃用户总数:20 亿。 每天观看的视频数量。50 亿。 73%的美国成年人使用 YouTube。 YouTube 上有 5000 万创作者。 2019 年全年,YouTube 的广告收入为 151 亿美元,比 2018 年增长 36%。 YouTube 占所有移动互联网流量的 37%。 YouTube 有 80 种不同的语言。 从这些统计数据中,我们知道 YouTube 是巨大的,全球性的,并且赚了很多钱。 理解问题,确立设计范围 如图 14-1 所示,除了观看视频,你还可以在 YouTube 上做很多事情。例如,评论、分享或喜欢一个视频,将一个视频保存到播放列表中,订阅一个频道等等。在 45 或 60 分钟的采访中,不可能设计所有内容。因此,提出问题以缩小范围是很重要的。 应聘者:哪些功能是重要的? 面试官:上传视频和观看视频的能力。 应聘者:我们需要支持哪些客户? 面试官:移动应用、网络浏览器和智能电视。 应聘者:我们有多少日活跃用户? 面试官:500 万 应聘者:每天花在产品上的平均时间是多少? 面试官:30 分钟。 应聘者:我们需要支持国际用户吗? 面试官:是的,很大比例的用户是国际用户。 应聘者:支持的视频分辨率是多少? 面试官:系统可以接受大部分的视频分辨率和格式。 应聘者:是否需要加密? 面试官:是的 应聘者:对视频的文件大小有要求吗? 面试官:是的。我们的平台专注于小型和中型的视频。允许的最大视频尺寸是 1GB。 应聘者:我们能否利用亚马逊、谷歌或微软提供的一些现有云计算基础设施? 面试官:这是个好问题。对于大多数公司来说,从头开始建立一切是不现实的,建议利用一些现有的云服务。 ...

2021 Feb 14 · 3 min

系统设计::设计一个搜索自动补全系统

设计一个搜索自动补全系统 在谷歌上搜索或在亚马逊购物时,当你在搜索框中输入时,会有一个或多个与搜索词相匹配的内容呈现给你。这一功能被称为自动补全、提前输入、边输入边搜索或增量搜索。图 13-1 是谷歌搜索的一个例子,当在搜索框中输"dinner"时,显示了一个自动补全的结果列表。搜索自动补全是许多产品的一个重要功能。这就把我们引向了面试问题:设计一个搜索自动补全系统,也"设计 top k"“设计 top k 最多人搜索的查询”。 理解问题并确定设计范围 处理任何系统设计面试问题的第一步是提出足够的问题来澄清需求。下面是一个应聘者与面试官互动的例子。 应聘者:是否只支持在搜索查询的开始阶段进行匹配,还是在中间也支持? 面试官:只有在搜索查询的开始阶段。 应聘者:系统应该返回多少个自动补全的建议? 面试官:5 应聘者:系统如何知道要返回哪 5 条建议? 面试官:这是由受欢迎程度决定的,由历史查询频率决定。 应聘者:系统是否支持拼写检查? 面试官:不,不支持拼写检查或自动更正。 应聘者:搜索查询是用英语吗? 面试官:是的。如果最后时间允许,我们可以讨论多语言支持。 应聘者:我们是否允许大写字母和特殊字符? 面试官:不,我们假设所有的搜索查询都是小写字母。 应聘者:有多少用户使用该产品? 面试官:1000 万 DAU。 以下是需求的摘要。 快速响应时间。当用户输入搜索查询时,自动补全的建议必须足够快地显示出来。一篇关于 Facebook 自动补全系统的文章[1]显示,该系统需要在 100 毫秒内返回结果。否则会造成卡顿。 相关性。自动补全的建议应该与搜索词相关。 排序。系统返回的结果必须按照流行度或其他排名模式进行排序。 可扩展性。系统可以处理高流量。 高可用性。当系统的一部分脱机、速度减慢或遇到意外的网络错误时,系统应保持可用和可访问。 粗略估计 假设有 1000 万日活跃用户(DAU)。 一个人平均每天进行 10 次搜索。 每个查询字符串有 20 个字节的数据。 假设我们使用 ASCII 字符编码。1 个字符 = 1 个字节 假设一个查询包含 4 个词,每个词平均包含 5 个字符。 那就是每个查询有 4 x 5 = 20 字节。 对于在搜索框中输入的每一个字符,客户端都会向后台发送一个自动补全建议的请求。平均来说,每个搜索查询会发送 20 个请求。例如,在你输入完"dinner"时,以下 6 个请求被发送到后端。 search?q=d search?q=di search?q=din search?q=dinn search?q=dinne search?q=dinner ~24,000 次/秒(QPS)= 10,000,000 用户 * 10 次/天 * 20 个字符/24 小时/3600 秒。 峰值 QPS = QPS * 2 = ~48,000 假设每天的查询中有 20% 是新的。1000 万 * 10 次查询/天 * 每次查询 20 字节 * 20% = 0.4GB。这意味着每天有 0.4GB 的新数据被添加到存储中。 提出高层次的设计并获得认同 在高层次上,该系统被分解成两个。 ...

2021 Feb 13 · 3 min

系统设计::设计一个聊天系统

设计一个聊天系统 在这一章中,我们探讨了一个聊天系统的设计。几乎每个人都在使用一个聊天应用程序。图 12-1 显示了市场上一些最流行的应用程序。 聊天应用程序对不同的人执行不同的功能。敲定确切的要求是极其重要的。例如,当面试官想到一对一的聊天时,您不希望设计一个专注于群组聊天的系统。探索功能要求是很重要的。 理解问题并确定设计范围 就要设计的聊天应用程序的类型达成一致是至关重要的。在市场上,有像 Facebook Messenger、微信和 WhatsApp 这样一对一的聊天应用,也有像 Slack 这样专注于群组聊天的办公聊天应用,或者像 Discord 这样专注于大型群组互动和低语音聊天延迟的游戏聊天应用。 第一组澄清问题应该明确面试官要求你设计一个聊天系统时,她心里想的到底是什么。至少要弄清楚你是应该专注于一对一的聊天还是群组聊天应用。你可以问以下一些问题。 应聘者:我们应该设计什么样的聊天应用程序?一对一还是基于群组? 面试官:它应该同时支持 1 对 1 和群组聊天。 应聘者:这是一个移动应用吗?还是网络应用?或者两者都是? 面试官:都是。 应聘者:这个应用程序的规模是多少?是创业公司的应用还是大规模的? 面试官:它应该支持 5000 万日活跃用户(DAU)。 应聘者:对于群组聊天,群组成员的限制是什么? 面试官:最多 100 人 应聘者:聊天软件的哪些功能很重要?能否支持附件? 面试官:1 对 1 聊天,群聊,在线指标。系统只支持文字信息。 应聘者:信息大小有限制吗? 面试官:是的。是的,文本长度应小于 10 万个字符。 应聘者:是否需要端对端加密? 面试官:不需要。目前不需要,但如果时间允许,我们会讨论这个问题。 应聘者:我们应将聊天记录保存多长时间? 面试官:永远。 在这一章中,我们将重点设计一个类似于 Facebook messenger 的聊天应用,并强调以下特点。 一对一的聊天,传递延迟低 小型群组聊天(最多 100 人)。 显示在线 支持多种设备。同一账户可以同时登录多个账户。 推送通知 就设计规模达成一致也很重要。我们将设计一个支持 5000 万 DAU 的系统。 提出高层次的设计并获得认同 为了开发一个高质量的设计,我们应该对客户和服务器的通信方式有一个基本的了解。在一个聊天系统中,客户端可以是移动应用程序或 Web 应用程序。客户端之间并不直接交流。相反,每个客户端都连接到一个聊天服务,它支持上面提到的所有功能。让我们专注于基本操作。聊天服务必须支持以下功能。 接收来自其他客户的消息。 为每条消息寻找合适的收件人,并将消息转发给收件人。 如果收件人不在线,在服务器上保留该收件人的消息,直到她在线。 图 12-2 显示了客户端(发送者和接收者)和聊天服务之间的关系。 ...

2021 Feb 12 · 3 min

系统设计::设计一个新闻源系统

设计一个新闻源系统 在本章中,你被要求设计一个新闻源系统。什么是新闻源?根据 Facebook 的帮助页面,“新闻源是在你的主页中间不断更新的故事列表。新闻提要包括状态更新、照片、视频、链接、应用活动,以及你在 Facebook 上关注的人、网页和团体的喜欢”[1]。这是一个流行的面试问题。经常被问到的类似问题有:设计 Facebook 的新闻提要,Instagram 的提要,Twitter 的时间线,等等。 理解问题并确定设计范围 第一组澄清问题是为了了解当面试官要求你设计一个新闻源系统时,她的想法是什么。最起码,你应该弄清楚要支持哪些功能。下面是一个应聘者与面试官互动的例子。 应聘者:这是一个移动应用程序吗?还是一个网络应用?或者两者都是? 面试官:都是 应聘者:有哪些重要的功能? 面试官:用户可以发布帖子,并在新闻源页面上看到她朋友的帖子。 应聘者:新闻源是按照逆时针顺序还是任何特定的顺序排序的,比如话题得分?比如说,你的亲密朋友的帖子得分更高。 面试官:为了简单起见,我们假设新闻源是按逆时针顺序排序的。 应聘者:一个用户可以有多少个朋友? 面试官:5000 应聘者:流量是多少? 面试官:1000 万 DAU 应聘者:新闻源可以包含图片、视频,还是只有文字? 面试官:可以。它可以包含媒体文件,包括图片和视频。 现在你已经收集了需求,我们把重点放在设计系统上。 提出高层次的设计并获得认同 该设计分为两个流程:新闻发布和新闻源构建。 新闻发布:当一个用户发布了一个帖子,相应的数据被写入缓存和数据库。一个帖子被填充到她朋友的新闻源中。 新闻源构建:为简单起见,我们假设新闻源是通过将朋友的帖子按逆时针顺序聚合而构建的。 新闻源 API 新闻源 API 是客户端与服务器通信的主要方式。这些 API 是基于 HTTP 的,允许客户端执行操作,其中包括发布状态、检索新闻源、添加朋友等。我们讨论两个最重要的 API:Feed publishing API 和 News Feed retrieval API。 Feed publishing API 要发布一个帖子,将向服务器发送一个 HTTP POST 请求。该 API 显示如下。 POST /v1/me/feed Params: content:内容是帖子的文本。 auth_token:它用于验证 API 请求。 新闻提要检索 API 检索新闻提要的 API 如下所示。 GET /v1/me/feed ...

2021 Feb 11 · 2 min

系统设计::设计一个推送系统

设计一个推送系统 近年来,通知系统已经成为许多应用程序的一个非常流行的功能。通知会提醒用户一些重要的信息,如突发新闻、产品更新、事件、产品等。它已经成为我们日常生活中不可缺少的一部分。在本章中,你被要求设计一个通知系统。 一个通知不仅仅是移动推送通知。三种类型的通知格式是:移动推送通知、SMS 消息和电子邮件。图 10-1 显示了这些通知中的每一种的例子。 理解问题并确定设计范围 构建一个每天发送数百万条通知的可扩展系统并不是一件容易的事。它需要对通知生态系统有深刻的理解。面试问题被特意设计成开放式和模糊不清的,你有责任提出问题来澄清需求。 应聘者:系统支持哪些类型的通知?面试官。推送通知,短信,和电子邮件。 应聘者:这是一个实时系统吗? 面试官:让我们说这是一个软实时系统。我们希望用户能尽快收到通知。但是,如果系统处于高负荷工作状态,稍有延迟是可以接受的。 应聘者:支持的设备有哪些? 面试官:iOS 设备,安卓设备,以及笔记本/台式机。 应聘者:什么会触发通知? 面试官:通知可以由客户端应用程序触发。也可以在服务器端安排。 应聘者:用户是否可以选择退出? 面试官:是的,选择退出的用户将不会再收到通知。 应聘者:每天有多少通知被发送出去? 面试官:1000 万条移动推送通知,100 万条短信,500 万封电子邮件。 提出高层次的设计并获得认同 本节展示了支持各种通知类型的高层设计:iOS 推送通知、Android 推送通知、SMS 消息和电子邮件。它的结构如下。 不同类型的通知 联系信息收集流程 通知的发送/接收流程 不同类型的通知 我们首先看一下每种通知类型在高层次上是如何工作的。 iOS 推送通知 我们主要需要三个组件来发送一个 iOS 推送通知。 提供者。提供者构建并向苹果推送通知服务(APNS)发送通知请求。为了构建一个推送通知,提供者提供以下数据。 设备令牌。这是一个用于发送推送通知的唯一标识符。 有效载荷。这是一个 JSON 字典,包含通知的有效载荷。下面是一个例子。 APNS:这是苹果提供的一个远程服务,用于向 iOS 设备传播推送通知。 iOS 设备。它是终端客户,接收推送通知。 Android 推送通知 Android 也采用了类似的通知流程。通常不使用 APN,而是使用 Firebase Cloud Messaging(FCM)来向安卓设备发送推送通知。 SMS 消息 对于 SMS 消息,通常使用第三方 SMS 服务,如 Twilio[1]、Nexmo[2]和其他许多服务。它们中的大多数是商业服务。 电子邮件 虽然公司可以建立自己的电子邮件服务器,但许多公司选择了商业电子邮件服务。Sendgrid[3]和 Mailchimp[4]是最受欢迎的电子邮件服务之一,它们提供了更好的发送率和数据分析。 图 10-6 显示了包括所有第三方服务后的设计。 ...

2021 Feb 10 · 2 min