荷塘网站建设,如何做网站免费推广,毕设做的网站可以用模板改吗,电商设计和ui设计哪个前景比较好戳蓝字“CSDN云计算”关注我们哦#xff01;时光机#xff1a;搭载这部时光机#xff0c;带您回顾《程序员》大量优秀文章#xff0c;重温经典技术干货#xff0c;我们发现硬核技术永不过时#xff0c;对于get要点、solve难题、提高自我#xff0c;仍有非凡意义。作者时光机搭载这部时光机带您回顾《程序员》大量优秀文章重温经典技术干货我们发现硬核技术永不过时对于get要点、solve难题、提高自我仍有非凡意义。作者Richy Ho一名软件架构师热衷于分布式及并行计算、机器学习和数据挖掘、SaaS和云计算。先后在Cisco、eBay、Adobe等公司工作。博客为horicky.blogspot.com。 导读过去一些用于存储大规模数据的数据存储机制逐渐成形它们与RDBMS模型相去甚远被统称为NoSQL。提炼出各种NoSQL方案背后共通的技术原理有助于更深刻地理解它们对应用程序设计的内在影响。过去 一 些 用 于 存 储大规模数据的数据存储机制逐渐成形。这些存储方案与RDBMS模型相去甚远被统称为NoSQL。其中引人注目的主要角色有● Google BigTable, HBase, Hypertable● Amazon Dynamo, Voldemort, Cassendra, Riak● Redis● CouchDB, MongoDB上面列举的方案具有这样一些共同的特点● 键/值存储● 系统运行在数量巨大的普通机器上● 数经过分区和复制散布在大量的机器上放松了对数据一致性的约束。因为CAP理论证明一致性、可用性和分布不可能三者兼得。本文意在提炼出以上方案背后共通的技术原理以图更深刻地理解它们对应用程序设计的内在影响。 API模型 底层的数据模型可以看作一个巨大的Hashtable键/值存储。访问Hashtable的API基本形式如下getkey给定一个键取得对应的值。putkey, value新建一个键/值对或者更新给定的键对应的值。deletekey移除一个键及其对应的值。 通过更高级的API还可以在服务器环境中执行用户定义的函数。executekey, operation, parameters通过给定的键对特定的值调用某操作该值可以具有特殊的数据结构如List、Set、Map……。mapreducekeyList, mapFunc, reduceFunc对给定范围的键调用Map/Reduce函数。 机器布局 整套硬件设施由大量数百台、数千台……便宜的、普通的、不可靠的机器通过网络连接而成。每台机器称为一个物理节点PN。每个PN上的软件配置是相同的但CPU数量、内存、磁盘等硬件能力可能不同。在每个PN上依据其硬件能力运行着数量不等的虚拟节点VN。 数据分区 一致性散列由于整个散列表分散在许多VN上我们需要找一种方法将每个键映射到相应的VN。其中一种办法是用以下式子确定分区位置分区 键 mod总VN数量。这种方案的劣势在于当VN数量变化的时候现有键的所有权即位于哪个VN上会发生极大的变化全部数据都要重新分配到所有VN。因此多数大规模的存储都采用一种“一致性散列”的技巧去最小化所有权变更的数量。 在 一 致 性 散 列 方 案 中 键 空间是有限的且落在一个圆周上。虚拟节点的ID也从同一个键空间中分配。对于任意键如果从该键开始沿着圆周顺时针走遇到的第一个虚拟节点就是它所属的节点。如果某个节点崩溃了它所属的所有键都被移交到顺时针方向的相邻节点。因此键的重新分配只发生在崩溃节点的邻居身上其他节点仍然保留原有键不变。 数据复制 为了用单个来说并不可靠的资源提供更高的可靠性我们需要复制数据分区。复制Replication不仅提高了数据的整体可靠性还由于将工作负载分散到多个副本Replica而对性能有所帮助。只 读 请 求 可 以 分 发 到 任 意 的副本而更新请求的处理则较为困难我们必须小心地协调各副本的更新。 成员变更 请注意虚拟节点可在任意时刻加入或离开网络而不影响这个环的运作。当新节点加入到网络1新加入的节点公告自身存在将ID告知若干重要节点或者简单地广播到所有节点。2左右两侧的相邻节点调整键的所有权以及副本成员信息。这步骤通常是同步完成的。3新加入的节点开始从它的相邻节点并行、异步地批量复制数据。4副本成员的变更信息异步地传播到其他节点。注意其他节点可能尚未更新其副本成员信息因而继续向旧的节点转发请求。而因为旧节点即新加入节点的邻居已经掌握新节点的信息第2步它们会将请求转发给新加节点。 另一方面新加节点可能还处于下载数据的状态尚不能提供服务。我们用“矢量时钟”见后文去确定新加节点是否已准备好处理请求否则客户可以联系其他副本成员。 当现有节点离开网络比如当节点崩溃的时候 1崩溃的节点不再响应Gossip消息因此它的邻居发现这一情况。2邻居更新成员信息并异步地复制数据。 节点崩溃我们尚未提及虚拟节点如何映射到物理节点。实际的方案有很多主要目标是不让相同副本的各个虚拟节点落在同一个物理节点上。其中一种简单的方案是随机地将虚拟节点分配到物理节点但增加一重检查保证物理节点上不存在拥有相同键范围的副本。 请注意由于机器崩溃发生在物理节点的层次意味着上面运行的许多虚拟节点一同崩溃。当这种情况发生的时候多个虚拟节点的负载由很多台物理机器分担。因此由于物理节点崩溃而增加的负载被均匀地均衡掉了。 客户端的一致性 当我们拥有同一数据的多份副本就有必要操心如何同步它们才能使得在客户端看来数据是一致的。有很多种客户端一致性模型1严格一致性语义上相当于只存在一份数据副本。任何更新看上去都是即时发生的。2“读己之所写”一致性客户端可立即看到自己所作的更新且客户端可在不同请求之间切换服务器但不能立即看到其他客户端所作的更新。3会话Session一致性对于客户端在同一会话作用域中发起的请求通常绑定到同一台服务器提供“读己之所写”一致性。4单调读一致性保证时间上的单调性保证客户端在未来的请求中只会读到比当前更为新的数据。5最终一致性这是最弱的一种保证。在更新的过程中客户端将看到一幅不一致的视图。当并发访问同一数据几率非常小的时候此模型效果良好。 客户端需要等待一段时间才能看到自己先前所作的更新。取决于采用何种一致性模型需要安排两种机制客户端请求如何分发到副本。副本如何传播及执行更新。围绕着如何实现这两方面出现了许多模型各有不同的权衡取舍。 主从或单主模型 在此模型下每个数据分区都有一个主节点和多个从节点。所有更新请求都必须发给主节点主节点执行更新后再异步地传播给从节点。如果主节点在将更新传播给任何从节点之前发生崩溃就会出现一个丢失数据的时间窗口。因此有的系统会选择同步等待到更新传播到至少一个从节点为止。 如果客户端能容忍某种程度的旧数据读请求可以分发到任何副本。负载因此可以分散到多个副本上。如果对于某些数据客户端不能容忍取得非最新的数据那就必须向主节点请求。请注意此模型并不意味着某个物理节点扮演主节点的角色。主从关系发生在虚拟节点的层次。每个物理节点上既有充当某分区主节点的虚拟节点也有扮演其他分区从节点的虚拟节点。因此写负载也被分散到不同的物理节点上只不过这是由于分区的结果而非复制的结果。当一个物理节点崩溃时将会失去特定分区的主节点。此时一般将更新最及时的从节点选为新的主节点。当应用的读/写比很高的时候主从模型效果显著当更新涉及的键范围分布均匀的时候它的效果也很好。因为这些因素大多数数据复制方案都选择了主从模型。 更新由主节点传播到从节点有两种方式传状态和传操作。如果是传状态主节点将它的最新状态传递给从节点然后从节点用得到的最新状态替换掉自己的当前状态。如果是传操作主节点传递一系列操作给从节点然后从节点对自己的本地状态执行操作。传状态模型更能抵御消息丢失的情况因为只要后续的更新消息能正确抵达副本仍然能成功更新到最新的状态。 即使在传状态模型里我们也不希望发送完整的对象给其他副本因为通常修改的只是对象的一小部分。发送对象未变的部分等于浪费带宽。我们需要一种机制去检查并发送更新的部分。常见的做法是将对象打散成小块并且计算出对象中各小块的一棵散列树。于是副本通过比较各自的散列树就能知道对象中的哪些小块改动过了只发送改动过的小块即可。 一般来说传操作模型需要通过网络发送的数据量较少。然而传操作模型需要一种可靠的消息机制去保证消息的传递顺序。 多主或无主模型如果某些键范围存在热点写请求比较密集主从模型没办法很好地将负载均匀地分散掉。多主模型允许将更新请求发送给任何副本可能称之为无主模型更合适。如果任意客户端可向任意服务器发出任意请求那么我们如何同步状态才能保持客户端的一致性同时使所有副本最终都能达到相同的状态下文将介绍几种办法。 基于多数决的两段式提交 为了实现“严格一致性”我们可以采用传统的两段式提交2PC协议。假设某数据有N个副本。当更新数据的时候有一个“预备”阶段由协调者询问所有副本是否已准备好执行各个更新。然后每个副本将数据写入日志文件成功后通知协调者。收到所有副本的成功消息之后协调者发起第二阶段——“提交”阶段要求所有副本都完成提交此时每个副本写入另一条日志条目确认更新。请注意这里存在一些可伸缩性的问题因为协调者需要“同步地”等待很多轮网络消息来回还要等待磁盘I/O完成。 另一方面如果某个副本崩溃了更新将会失败。当副本的数量越多其中之一发生问题的几率也越大。因此数据复制反而损害了系统的可用性。所以传统的2PC在高吞吐量的事务系统中间并不流行。基 于 q u o r u m 的 2 P C 如PAXOS效率更高一些。在此模型中协调者只需要同步更新W个副本而非全部N个副本。 协调者仍旧写入全部N个副本但只等待其中任意W个副本确认写入成功。站在概率的角度看这种做法具有更高的效率。然而由于并非全部副本都完成了更新我们在读取数据的时候需要小心地保证读到的节点中至少有一个是成功更新过的。 当读取数据的时候我们需要读取R个副本并返回其中时间戳最新的一个结果。为了保证“严格一致性”只要保证读的集合与写的集合有重叠即可也就是W R N。你可能也想到了基于多数决的2PC可以看作是2PC协议的一般化推广传统的2PC是当W N和R 1时的特例。一般化之后的模型使我们可以根据读写负载的比率权衡选择不同的W和R。如果用户不能承受选取足够大的W和R即当W R N的时候那么客户端的一致性模型就要放宽到较弱的类型。 如果客户端可以容忍较宽松的一致性模型那么我们没必要采用上述的2PC提交或者基于多数决的协议。后文将介绍一种传言Gossip模型通过异步的传言消息交换传播更新使所有副本最终都达到最新的状态。 矢量时钟 矢量时钟是一种时间戳机制透过它我们可以推导更新之间的因果关系。首先每个副本都持有矢量时钟。假设副本i的时钟是Vi。Vi[i]是副本根据特定规则更新其矢量时钟之后的逻辑时钟。当副本i执行了一则内部操作副本i的时钟加一。当副本i向副本j发送一则消息副本i首先把自己的时钟Vi[i]加一并将自己的矢量时钟Vi附加到消息中发送出去。当副本j收到来自副本i的消息它首先自增其时钟Vj[j]然后合并其时钟及消息所附的时钟Vm。即Vj[k] maxVj[k], Vm[k]。 于是可定义偏序关系Vi Vj当且仅当对于所有的kV i [ k ] Vj[k]。根据这样的偏序关系我们就可以推导出更新之间的因果关系。背后的原理是这样的内部操作的效果可在同一节点上立即看到。 接收到消息之后接收节点得知发送节点在消息发送之时的情况。情况不仅包括了发送节点上发生的事情还包括了发送节点所知的所有其他节点上发生的事情。换言之Vi[i]反映了节点i上发生最后一次内部操作的时间。Vi[k] 6意味着副本i已经知道副本k在它的逻辑时钟6的时刻的情况。请注意这里是在一种抽象的意义上使用“情况situation”一词。取决于消息中传递何种信息“情况”有不同的具体含义。情况的具体含义会影响如何增加矢量时钟。下文介绍的“传状态模型”和“传操作模型”在消息中传递的信息不一样它们矢量时钟如何增加也因此不同。 由于状态总是从副本流向客户端绝不会反过来所以客户端不占矢量时钟的条目。矢量时钟里每个副本占一条。不过客户端可以持有它最后联系的副本的矢量时钟这对于实现我们先前讨论的客户端一致性甚为关键。例如为了支持单调读一致性副本可以保证附在数据上的矢量时钟大于客户端在查询时提交的矢量时钟。 传言传状态模型 在传状态模型里每个副本都维护着一个矢量时钟和一个状态的版本树版本树中的状态无法通过比较矢量时钟得出状态之间的“大于”或“小于”关系。换言之状态版本树包含了所有存在冲突的更新。在查询的时候客户端将它的矢量时钟一并提交副本将状态树中早于客户端时钟的子集发回给客户端这就实现了单调读一致性。然后客户端通过合并所有的版本增加其时钟。这意味着客户端要负责解决所有的版本冲突因为当客户端稍后发送更新的时候它的矢量时钟会早于所有的版本。 在更新的时候客户端发送它的矢量时钟副本检查客户端的状态是否早于任意现有版本如果是副本将丢弃客户端的更新。各个副本还可以在后台互相传言尝试将各自的版本树合并起来。 在传操作方式下执行操作的次序非常重要至少需要保证因果序causal order。因为次序的关系只要之前的操作还没执行完副本就不得不推迟任何新的操作。因此副本需要将操作请求保存到一个日志文件并彼此交换日志通过统一合并日志推导出正确的操作序列才能相应地更新各自的本地存储。 “ 因 果 序 ” 意 味 着 每 个 副 本要 先 完 成 对 “ 因 ” 的 修 改 才 能 执行对“果”的修改。“全序totalorder”则要求每个副本都执行同一个序列中的操作。在此模型中每个副本持有一个矢量时钟列表。Vi为副本自身的矢量时钟Vj为副本i接收到副本j传言消息时的矢量时钟。V-state代表最后更新状态的矢量时钟。 当客户端提交查询的时候它会一并发送客户端的矢量时钟这个时钟代表了客户端的视图。副本检查自己所知的状态是否迟于客户端所知的状态。 当收到更新操作副本会将操作缓冲起来直到可以将之应用到本地状态。每个提交的操作都会带上两个时间戳V-client标明客户端在其发出更新请求时的视图。V-receive标明副本在收到请求时的视图。 更新操作的请求会留在队列里直到副本收到该请求所依赖的所有其他请求。这个条件反映在矢量时钟Vi上即当Vi大于V-client时条件满足。更新传操作模型 在后台各个副本交换它们记录的更新队列日志并更新彼此的矢量时钟。在日志交换之后副本检查特定的操作是否可以执行当所有依赖操作都已收到然后完成操作。请注意在同一时刻有可能存在多个操作准备好执行此时副本将按照因果序通过比较矢量时钟排列各操作依次执行。还有可能发生不同副本上的并发更新问题。也就是说可能存在多个合法的操作序列为了使不同副本以相同次序执行并发的更新我们需要一种“全序”机制。 其中一种方法是设立一个单调增加的序列号不管哪个更新先执行都好序列号先到先得。另一方面如果操作本身是可以互换的那么操作的执行次序也就无关紧要了。执行更新之后更新操作还不能立即从队列中删除因为更新可能还没有交换到到所有的副本。我们继续检查每次日志交换后每个副本的矢量时钟直到确认所有副本都已收到更新才可以将它从队列中删除。 Map Reduce的执行过程 分布式的存储架构也适合分布式的处理。例如对一个键列表执行Map/Reduce操作的情况。系统将Map和Reduce函数推送给所有的节点即将处理逻辑向数据靠拢。Map函数分布到键所属的各个副本上去处理然后Map函数的输出被转交给Reduce函数去执行聚合操作。 对删除的处理在多主复制系统中我们用矢量时钟时间戳去判定因果序我们需要非常小心地处理“删除”的情况以免丢失掉删除对象关联的时间戳信息否则我们根本无法推导何时执行删除。 因此我们通常将删除当作一种特殊的更新来处理把对象标记为删除但仍然保留其元数据、时间戳信息。当经过足够长的时间我们确信所有节点都已经将该对象标记为删除之后我们才通过垃圾收集回收已删除对象的空间。 福利扫描添加小编微信备注“姓名公司职位”加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读VMware竟然出了一款防火墙技术头条你的 AI 老师已上岗要成为年薪百万的技术大牛必经历这5个阶段, 收好这份超实用的技术进阶指南 | 技术头条助力 Android 抗衡 iOS华为发布方舟编译器程序员的黑砖窑东南亚博彩骗局详解售价910元周志华等人英文新书《演化学习》出炉真香朕在看了
