详细介绍Amazon亚马逊的网站数据存储架构

一、系统概述1、Amazon平台概述      Amazon平台是一个面向服务的架构，由数百个服务组成。它坚持高度分散、松散耦合和完全分布的原则。具体结构见下图。在这种环境下，Dynamo诞生了，特别是需要一个可用的存储系统。2、Dynamo概述Dynamo是Amazon提供的一种高度可用的分布式Key-Value存储系统，它满足了可扩展性、可用性和可靠性。满足CAP原理：通过一致性哈希满足P，复制满足A，对象版本和向量时钟满足C。用牺牲C来满足高可用性的A，但最终会一致。但是，是牺牲C满足A，还是牺牲A满足C，可以根据NWR模型进行分配，以实现收入成本平衡。Dynamo内部有三个层次的概念：Key-Value：Key唯一识别数据对象，Value识别数据对象实体，通过对Key完成数据对象的读写操作。节点node：节点是指物理主机。每个节点将有三个必要的组件：请求协调器（requestcoordination）、成员和失败测试，本地持久引擎（localpersistenceengine），Java实现了所有这些组件。本地持久引擎支持不同的存储引擎。最重要的引擎是BerkeleyDatabasetansactionaldatastore(更适合存储数百K的对象)，还有BDBJavaedtion。、MySQL和一致性内存Cache。本地持久发动机组件是一种可插拔的持久组件。应用程序可以根据需要选择最合适的存储发动机。例如，如果存储对象通常是数千字节，则可以选择BDB。如果尺寸更大，可以选择MySQL。在生产中，Dynamo通常使用BDB事物数据存储。instance实例：从应用的角度来看，它是一种提供IO功能的服务。每个例子由一组节点组成，可能位于不同的IDC中，因此IDC问题不会导致数据丢失，从而具有更好的灾难容忍和可靠性。二、背景条件1、基于Key-Value模型的系统假设和要求(1)查询模型，而不是SQL即关系模型。存储对象相对较小，通常小于1MB。(2)在传统的ACID属性关系数据库中，ACID(A原子、C一致性、I隔离、D持久性)用于保证事务，往往在保证ACID的前提下可用性差。Dynamo采用弱一致性C实现高可用性，不提供数据隔离I，只允许单Key更新。(3)效率在廉价机器上满足SLA，通过配置满足延迟和吞吐量的要求。因此，必须权衡性能、成本、可用性和耐久性。(4)其他假设Dynamo仅用于Amazon内部，因此认为其使用环境是可靠的。2、服务水平协议（SLA）       所谓服务水平协议，是指客户端与服务端在某些指标上达成协议，通常包括客户端请求API的速率和服务端的预期延迟。例如，当客户端每秒500个请求负载高峰时，99.9%的响应时间是300毫秒。       在一般行业中，这种面向性能的SLA采用平均数（average）、中值（median）和预期变化（expectedvariance）。       一般行业，对于这种面向性能的SLA采用平均数（average）、中值（median）和预期变化（expectedvariance）。但这些指标只能给大多数客户带来良好的体验，而不是全部。Dynamo用99.9%的百分位代替这些指标来解决这个问题。3、考虑到传统的数据复制算法（复制数据），当出现故障时，为了确保数据的一致性，被迫牺牲可用性，即使数据不能使用，直到数据绝对正确，而不是确定数据是否正确。然而，一个高度灵活的系统应该能够让用户知道在什么情况下可以达到什么属性，Dynamo就是这样。对于故障是正常的系统，乐观的复制技术可以提供系统的可用性，但问题是需要检测和协调解决冲突，协调解决冲突的过程包括两个问题，即什么时候协调谁协调。Dynamo的设计是数据存储的最终一致性，即所有更新操作最终到达所有副本。(1)何时协调只有两种情况:写作或阅读时协调冲突。传统的数据存储在写作中协调冲突，即如果数据在给定的时间内不能满足所需的所有或大部分副本，则可能会被拒绝。Amazon认为，拒绝客户的更新操作将导致不良的用户体验。典型的应用程序是购物车服务。即使出现故障，客户仍然可以向购物车添加或删除项目。在此基础上，Dynamo的目标是“永远可以写”（alwayswritable）也就是说，数据存储的“写”是高度可用的。也就是说，Dynamo在阅读时协调冲突，以确保“写作”永远不会被拒绝。(2)谁协调无非是两种情况:数据存储本身或客户端应用程序协调。如果数据存储本身是协调的，则只能使用简单的策略来协调冲突的更新操作，如：“最后一次写入胜利”（lastwritewins）。如果客户端应用程序协调，应用程序可以根据业务需要选择最合适的协调冲突的方法。Dynamo选择后者，典型的应用或购物车服务，返回所有数据对象的版本，最后选择合并冲突的版本。作为一种分布式系统的典型代表，Dynamo的许多关键技术都给它带来了一系列的优势，详见下表：1、数据分区Hash算法：用MD5对Key进行Hash，以产生128位的标记符，以确定Key的存储节点。Dynamo采用一致性哈希来完成数据分区，以达到增量可伸缩性的目的。在一致性哈希中，哈希函数的输出范围是一个环，如图2所示，系统中的每个节点映射到环中的某个位置，Key也被Hash到环中的某个位置。Key开始沿顺时针方向找到第一个位置大于其的节点作为存储节点。换句话说，每个系统节点负责从其映射位置到逆时针方向的第一个系统节点之间的区域。一致性哈希最大的优点是节点的扩展和缩减，只影响其直接的邻居节点，而不影响其他节点。这似乎很完美，但亚马逊并没有停止脚本，这是它的伟大之处，事实上，还有两个问题：节点数据分布不均匀，忽略了节点性能的异质性。为了解决这两个问题，Dynamo改进了一致性哈希，并引入了虚拟节点，即每个节点在逻辑上分为多个虚拟节点，每个虚拟节点在逻辑上看起来像一个真实节点，因此每个节点被分配到多个点，而不是一个单点。2、为了实现高可用性，Dynamo将每一个数据复制到N台主机上，其中N就是每一个例子（per-instance）推荐值为3的配置参数。每个Key都被分配到协调器中（coordinator）节点，协调器节点管理其负责范围内的复制数据项。除了在本地存储其责任范围内的每个Key外，它还将这些Key复制到顺时针方向的N-1后续节点。这样，系统中的每个节点都负责从自己的位置到N个前驱节点之间的区域。具体逻辑见图2。除了本地存储键K外，节点B还在节点C和D处复制键K，使节点D将存储在范围内(A,B]、(B,C]和(C,D]所有键：特定键有首选节点列表。由于虚拟节点的存在，为了解决节点故障的问题，在构建第一个节点列表时，会跳过环上的某些位置，使这些节点位于不同的物理节点上，确保高可用性。Dynamo采用类似Quorum系统的一致性协议，以确保复制时数据副本的一致性。这里涉及三个关键参数(N,R,W)，其中，N是指数据对象复制到N个主机，协调器负责将数据复制到N-1个节点。亚马逊建议N配置为3，R代表成功读取操作中最小参与节点的数量，W代表成功写作操作中最小参与节点的数量。这里涉及三个关键参数(N,R,W)，其中，N是指数据对象复制到N个主机，协调器负责将数据复制到N-1个节点。亚马逊建议N配置为3，R代表成功读取操作中最小参与节点的数量，W代表成功写作操作中最小参与节点的数量。R W>N，会产生类似Quorum的效果。在这个模型中，读(写)延迟由最慢的R延迟(W)复制副本决定R和W通常配置在N以下，以获得相对较小的延迟。亚马逊建议(N,R,W)考虑性能和可用性，设置为(3、2、2)。R和W直接影响性能、可扩展性和一致性。如果W设置为1，只要一个节点可用，就不会影响写作操作。如果R设置为1，只要有一个节点可用，读取请求就不会受到影响。R和W值过小会影响一致性，过大会影响可用性。因此，R和W之间需要平衡，这也是Dynamo的亮点之一。3、从上面可以看出，Dynamo为了保证高可用性，复制了多份(建议3份)每个数据。在数据被异步复制到所有副本之前，如果有得到操作，将获得不一致的数据，但Dynamo提供最终一致性。在亚马逊平台上，购物车是这种情况的典型应用，为了确保购物车永远可用，任何副本任何更改操作结果将作为数据版本存储，所以当用户得到多个版本时，所以你需要做数据版本合并。Dynamo将合并工作推给应用程序，这里是购物车获取时处理。Dynamo用向量时钟来识别不同节点上多个副本之间的因果关系。向量时钟实际上是一个列表，每个节点都是一个列表(node,counter)是的，列表(节点，计数器)。数据版本之间的关系要么是因果关系，要么是平行关系，关系判断取决于计数器值的大小，如果第一个时钟对象的计数器小于或等于所有其他时钟对象的计数器是因果关系，那么因果的祖先可以被视为旧数据，否则是平行关系，那么数据版本就有冲突，需要协调和合并。在Dynamo中，当客户端更新一个对象时，必须指定哪个版本的数据更新，这取决于早期获取操作时获得的向量时钟。上图3显示了向量时钟的使用过程，具体流程分析如下：在客户端上写一个新对象。节点Sx处理了这个请求，处理了key的写作:序列号增加，数据的向量时钟创建，从而在节点上生成对象D1和向量时钟[(Sx,1)]。客户端更新对象。假设该请求由Sx处理，即同一节点，因为该节点有D1和向量时钟[(Sx,1)更新对象后，在节点上生成对象D2和向量时钟[(Sx,2)]D2继承自D1，即D2覆写D1，计数器增加1，但其他节点可能是D1或D2，这取决于网络和节点的状态。假设同一客户端更新对象，但由不同的服务器处理。如果节点Sy处理此请求，则在更新对象后，在节点上生成对象D3和向量时钟[(Sx,2),(Sy,1)]。假设另一个客户端读取D2并尝试更新D2，但被另一个不同的服务器处理。该请求由节点Sz处理，然后在节点上生成对象D4和向量时钟[(Sx,2),(Sz,1)]。节点数据版本回收。现在有四个版本的数据存在并在每个节点之间传输。当节点收到D3或D4时，D1和D2将根据向量时钟回收，因为它们是D3和D4的祖先。然而，当收到D3和D4的节点时，根据向量时钟发现它们是平行的，保留它们，并在客户端获得它们时将它们提交给客户端，以协调和合并版本。假设客户端读取数据，D3和D4将根据两者的向量时钟合并为D5和向量时钟[(Sx,2),(Sy,1),(Sz,1)节点Sx协调编写操作，更新对象和向量时钟。从以上过程可以看出，当节点较多且情况极端时，向量时钟列表会增加，Dynamo采用时钟截断方案来解决这个问题，即(node,counter)当数量达到阈值(如:10)时，将最早的一对从向量时钟中删除。4、故障检测(1)当RingMembership每个节点启动时，将自己的映射信息存储在环上并持续存储在磁盘上，然后每隔一秒随机选择一个对等节点，通过Gossip协议传输节点的映射信息。最后，每个节点都知道对等节点的处理范围，即每个节点可以直接将key的读写转发到正确的数据集节点。不需要穿过中间路由或跳跃。(2)如果ExternalDiscovery手动将节点A和B添加到Dynamo环中，RingMembership不会立即检测到这一变化，而Dynamo环(A和B都认为自己在环中，但不知道对方存在)会出现暂时的逻辑分裂。Dynamo利用ExternalDiscovery来解决这个问题，即一些Dynamo节点作为种子节点，在非种子节点中配置种子节点IP，所有非种子节点都与种子节点协调成员关系。(3)Failuredetectiondynamo采用类Gossip协议实现分散的故障检测，使系统中的每个节点都能了解其他节点