• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 20
    • 下载费用:30 金币  

    重庆时时彩倾家荡产: 对分布式存储器系统中的数据的原子多重修改.pdf

    关 键 词:
    分布式 存储器 系统 中的 数据 原子 多重 修改
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN200980142635.2

    申请日:

    2009.10.15

    公开号:

    CN102197365A

    公开日:

    2011.09.21

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 专利权的转移IPC(主分类):G06F 9/06变更事项:专利权人变更前权利人:微软公司变更后权利人:微软技术许可有限责任公司变更事项:地址变更前权利人:美国华盛顿州变更后权利人:美国华盛顿州登记生效日:20150424|||授权|||实质审查的生效IPC(主分类):G06F 9/06申请日:20091015|||公开
    IPC分类号: G06F9/06; G06F15/16 主分类号: G06F9/06
    申请人: 微软公司
    发明人: S·J·麦凯尔维; B·G·卡尔德; J·王; X·吴
    地址: 美国华盛顿州
    优先权: 2008.10.24 US 12/258,025
    专利代理机构: 上海专利商标事务所有限公司 31100 代理人: 杨洁
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN200980142635.2

    授权公告号:

    |||102197365B||||||

    法律状态公告日:

    2015.05.13|||2014.03.05|||2011.11.23|||2011.09.21

    法律状态类型:

    专利申请权、专利权的转移|||授权|||实质审查的生效|||公开

    摘要

    提供了对流的原子多重修改。选择流,以便应用原子多重修改。在与流相关联的元数据上获取锁。将每一流从其名称分离。对所选流应用多重修改。在执行修改之后,名称被耦合到流。释放与每一流相关联的元数据上的锁。

    权利要求书

    1.存储了计算机可执行指令的一个或多个计算机可读介质,所述计算机可执行指令用于执行对一个或多个流作为单一原子单位的多重修改的方法,所述方法包括:选择(601)一个或多个流用于作为一个或多个选定流来进行修改;获取(602)与所述一个或多个选定流相关联的一个或多个元数据上的锁;从与每一流相关联的一个或多个名称解耦(603)所述一个或多个选定流中的每一个;对所述一个或多个选定流执行(604,605)多重修改;将所述一个或多个选定流中的每一个耦合(606)到与每一流相关联的至少一个名称;以及释放(607)所述一个或多个选定流的所述一个或多个元数据上的所述锁。2.如权利要求1所述的介质,其特征在于,所述一个或多个流是只加流。3.如权利要求1所述的介质,其特征在于,所述解耦包括维护临时映射,所述临时映射存储了所述一个或多个选定流中的每一个从与每一流相关联的所述名称的原始耦合。4.如权利要求3所述的介质,其特征在于,所述临时映射基于所述一个或多个流中的每一个的GUID。5.如权利要求1所述的介质,其特征在于,所述多重修改包括以下一个或多个:创建新的流,附加到现有流,创建现有流的副本,删除流,重命名流,更新流的所述元数据,以及将流的范围的子集复制到第二流。6.如权利要求1所述的介质,其特征在于,所述重新耦合包括将所述一个或多个选定流中的一个或多个GUID与所述一个或多个名称相关联。7.如权利要求6所述的介质,其特征在于,所述重新耦合包括在标识流的一个或多个GUID和一个或多个名称之间使用临时映射。8.如权利要求1所述的介质,其特征在于,所述多个修改通过改变指向范围的一个或多个指针而不移动所述一个或多个范围的数据,来影响所述一个或多个选定流。9.存储了计算机可执行指令的一个或多个计算机可读介质,所述计算机可执行指令用于执行对一个或多个流作为单一原子单位的多重修改的方法,所述方法包括:选择(701)一个或多个流用于作为一个或多个选定流来进行修改;获取(702)与所述一个或多个选定流相关联的一个或多个元数据上的锁;从与每一流相关联的名称解耦(703)所述一个或多个选定流中的每一个;对所述一个或多个选定流执行(704)多重修改中的第一修改;确定(705)对所述一个或多个选定流的多重修改中的第二修改将产生不一致性;逆转(706)对所述一个或多个选定流的多重修改中的所述第一修改;将所述一个或多个选定流中的每一个耦合(707)到与每一流相关联的至少一个名称;以及释放(708)所述一个或多个选定流的所述一个或多个元数据上的所述锁。10.如权利要求9所述的介质,其特征在于,所述一个或多个流是只加的。11.如权利要求9所述的介质,其特征在于,所述解耦包括维护临时映射,所述临时耦合存储了所述一个或多个选定流中的每一个从与每一流相关联的所述名称的原始耦合。12.如权利要求11所述的介质,其特征在于,所述多个修改影响所述临时映射中的一个或多个变化。13.如权利要求11所述的介质,其特征在于,所述多重修改中的每一个产生所述临时映射的新副本,在应用与所述临时映射的所述新副本相关联的所述多重修改中的一次修改之后,每一副本指出所述一个或多个选定流的快照。14.如权利要求11所述的介质,其特征在于,所述逆转多重修改中的所述第一修改包括逆转对所述选定流中的每一个的更改。15.如权利要求11所述的介质,其特征在于,所述重新耦合使用存储所述原始耦合的所述临时映射来将所述一个或多个选定流中的每一个重新耦合到与每一流相关联的所述名称。16.如权利要求9所述的介质,其特征在于,所述多重修改包括以下一个或多个:创建新的流,附加到现有流,创建现有流的副本,删除流,重命名流,更新流的所述元数据,以及将流的范围的子集复制到第二流。17.如权利要求9所述的介质,其特征在于,所述多个修改通过改变指向范围的一个或多个指针而不移动所述一个或多个范围的数据,来影响所述一个或多个选定流。18.存储了计算机可执行指令的一个或多个计算机可读介质,所述计算机可执行指令用于执行对一个或多个流作为单一原子单位的多重修改的方法,所述方法包括:选择(801)一个或多个只加流用于作为一个或多个选定流来进行修改;获取(802)与所述一个或多个选定流相关联的一个或多个元数据上的锁,其中获取所述锁包括将带有预定的名称的流修改为锁流;从与每一流相关联的一个或多个名称解耦(803)所述一个或多个选定流中的每一个;对所述一个或多个选定流执行(804)多重修改中的第一修改;确定(805)对所述一个或多个选定流的多重修改中的第二修改是否将产生不一致性;如果多重修改中的所述第二修改将产生不一致性,则逆转(807)对所述一个或多个选定流的多重修改中的所述第一修改;如果多重修改中的所述第二修改将不会产生不一致性,则执行(806)对所述一个或多个选定流的多重修改中的第二修改;将所述一个或多个选定流中的每一个耦合(808)到与每一流相关联的至少一个名称;以及释放(809)所述一个或多个选定流的所述一个或多个元数据上的所述锁。19.如权利要求18所述的介质,其特征在于,所述多个修改通过改变指向范围的一个或多个指针而不移动所述一个或多个范围的数据,来影响所述一个或多个选定流。20.如权利要求18所述的介质,其特征在于,所述多重修改包括以下一个或多个:创建新的流,附加到现有流,创建现有流的副本,删除流,重命名流,更新流的所述元数据,以及将流的范围的子集复制到第二流。

    说明书

    对分布式存储器系统中的数据的原子多重修改

    背景

    分布式系统,包括服务器场、web服务,以及分布式,网络附属存储系统,已经变得越来越普遍,提供大量的计算和存储资源。分布式存储系统使用整个广域网中的多个节点中的存储空间。用于访问存储在分布式存储系统中的节点上的数据的数据访问例程必须管理要求同时访问的多个客户机会话。然而,为维护数据的一致视图,修改访问必须一次仅限于一台主机。另外,执行多重修改的客户机会话必须在应用多重修改期间维护数据一致性。

    概述

    本发明的各实施例由下面的权利要求书进行定义,而不由本概述进行定义。因此,这里提供了本发明的各个方面的高级别的概述,以提供本发明的概述,并介绍将在以下详细描述部分进一步描述的一些概念。本概述不旨在标识所要求?;さ闹魈獾墓丶卣骰虮匾卣?,也不旨在用于帮助确定所要求?;さ闹魈獾姆段?。

    本发明的各实施例涉及执行称为原子多重修改的对一个或多个流作为单一原子单位的多重修改。在某些实施例中,如果多重修改中的一个不成功(例如,如果不满足前提条件),则成功地应用了的修改被反向,将流返回到开始原子多重修改之前的它们的原始状态。

    附图简述

    下面将参考附图详细描述本发明的说明性实施例,在附图中:

    图1描绘适用于实现本发明的各实施方式的示例性网络环境的图;

    图2描绘适用于实现本发明的示例性计算设备的框图;

    图3呈现了根据本发明的一实施例的示例性流的框图;

    图4呈现了根据本发明的一个实施例的示例性元数据块的框图;

    图5呈现了根据本发明的一实施例的示例性多重修改的框图;

    图6示出了根据本发明的一实施例的用于执行对一个或多个流作为单一原子单位的多重修改的方法的流程图;

    图7示出了根据本发明的一实施例的如果确定在一个或多个选定流中第二修改会失败,逆转成功的修改的方法的流程图;

    图8示出了根据本发明的一实施例的用于执行对一个或多个流作为单一原子单位的多重修改的方法的流程图,包括确定多重修改中的一个是否将导致不一致性或失败;以及

    图9示出了根据本发明的一实施例的多重修改的示例。

    详细描述

    此处用具体细节描述本发明的主题以满足法定要求。然而,描述本身并不旨在限制本专利的范围。相反,发明人设想,所要求?;さ闹魈饣箍山岷掀渌鼻盎蛭蠢醇际醢凑掌渌绞嚼淳咛寤?,以包括不同的步骤或类似于本文中所描述的步骤的步骤组合。此外,虽然此处可以使用术语“步骤”和/或“框”来指示所使用的方法的不同元素,但是除非而且仅当明确描述了各个步骤的顺序时,这些术语不应该被解释为意味着此处所公开的各步骤之间的任何特定顺序。

    本发明的各实施例涉及对以分布式方式存储在存储节点网络中的数据进行多重修改。在由分布在大型网络中的多个节点组成的网络中,每一数据单位都可以潜在地同时地被多个客户机会话访问。此外,还在网络中的不同的数据片段之间维护一致性。为了在访问数据的所有客户机会话之间维护数据的一致视图,对数据的修改需要协调。若没有对于对数据的修改的协调,两个客户机会话有可能以不一致的方式修改两段数据,导致不可预测的结果。此外,若没有多重相互依赖的修改的原子应用,执行修改的客户机会话的失败有可能会使数据处于不一致的状态,或者第二客户机会话有可能读取表示中间的不一致状态的数据。

    为防止这些类型的不一致性,需要基本操作来协调对数据的修改。具体而言,当独立应用单个修改将产生临时的不一致的状态时,需要具有作为原子事务对一个或多个数据片段应用多个相互依赖的修改的能力,从而防止分布式网络中的其他客户机会话中的数据视图中的不一致性。此外,还希望如果多重修改中的一个或多个无法被成功地应用,能够取消整组多重修改,从而防止由部分地成功的事务所产生的数据视图的不一致性。另外,还希望能够指定在可以成功地应用特定修改之前必须满足的一个或多个预期的前提条件,从而允许客户机会话以“乐观的”方式协调独立的,潜在地相互冲突的事务的应用,而不需要使用分布式的锁。

    作为示例,客户机会话X和客户机会话Y两者都在执行一种算法,该算法要求它们读取数据A的值,并计算数据A和数据B的新值,新值基于数据A的前面的值及由相应的客户机会话确定的其他外部数据(客户机会话X的数据Cx,客户机会话Y的数据Cy)。然后,可以作为原子操作,写入A和B的新值。然而,由于在读取数据A的值和写入数据A和数据B的新值之间无锁,因此,客户机会话X和客户机会话Y两者有可能同时读取数据A,然后,独立地为数据A和数据B计算新值。首先是客户机会话X以及然后是客户机会话Y将使用原子修改事务,尝试写入数据A和数据B的它们的各自的新值,两者都将成功。然而,由客户机会话X应用的修改的影响被由客户机会话Y应用的修改有效地撤消,导致相对于外部数据的潜在不一致性。为防止这种情况发生,许多传统的基于网络的文件系统将要求客户机会话声明一个跨对数据A的读取到对数据A和数据B的写入的分布式锁,从而在客户机会话X完成更新数据A和数据B之前,防止客户机会话Y读取数据A的值。然而,使用分布式锁产生大量的开销,并导致更不稳定的分布式系统;例如,如果客户机会话X未能释放锁,那么,会无限期地妨碍客户机会话Y取得进展。本发明通过允许客户机会话X和客户机会话Y指定当它们尝试写入数据A和数据B的新值时必须满足的前提条件,避免了显式的分布式锁的必要性。在此示例中,客户机会话X和客户机会话Y两者都要求,在数据A和数据B可以被替换之前,数据A的值自从它被读取以来必须没有更改??突Щ峄癥将在其更新方面成功,因为在读取数据A和写入数据A和数据B之间没有发生修改。然而,客户机会话X在更新任何数据时将不会成功,因为数据A的值在读取数据A和尝试更新之间发生了变化??突Щ峄癤可随意放弃操作,或者通过再次读取数据A来重新启动整个序列。在任何情况下,所有数据在内部和外部状态都保持一致。

    存储在网络中的特定数据可以有许多不同的形式。常见形式包括文件和类似的文件分组。根据本发明的某些实施例,数据被组织成流,其中,每一流都是由各种流元数据属性(例如,流名称、访问控制策略、失效时间等等)组成的数据实体,以及对范围的引用的有序序列。每一范围都由附加块的相邻的有序序列组成。每一附加块都是不可改变的,并由字节值相邻的有序序列组成??梢越碌姆段б酶郊拥搅鞯哪┪?,但是一旦附加,就无法从流中删除范围引用。一个以上的流包含对同一个范围的引用,或者甚至单一流包含对同一个范围的多个引用,都是有可能的??梢越赂郊涌楦郊拥揭桓龇段?,直到该范围变得封闭,此后,该范围变得不可改变。一旦一个范围被封闭,它将无法被解封。不管范围是否被封闭,附加块都无法被修改,或者从范围中删除。因此,流和范围只能在大小方面增长。

    根据本发明的一个实施例,通过将范围数据存储在大的独立的,松散耦合的范围服务器组,并将描述每一流的元数据存储在集中式服务器上或小的紧密耦合的服务器组中,将流组织在文件系统中。为将数据附加到一个范围,客户机会话与正确的独立范围服务器进行交互;因此,附加到范围是高度可缩放的,但是,不会促进向不同的范围的附加的协调。相反,在集中式服务器上维护了所有相关的流的元数据,因此对于对流元数据的更新的有效的协调是可能的。

    作为示例,与每一流相关联的元数据都可包括诸如当前流名称、全局唯一标识符(GUID)、访问控制策略、失效时间,以及对构成流的范围的引用的有序列表之类的信息。这种组织的一个优点是可以将范围引用从一个流复制到另一个流,无需移动网络中的任何数据。相反,只有引用列表在存储在集中式服务器上的元数据中改变。因为重复操作只影响流元数据,所以它们可以有效地被包括为原子多重修改的一部分。在本发明的其他实施例中,可以将元数据本身分布到网络中的多个节点中。本领域的技术人员将认识到,本发明可以应用于除流以外的数据格式。

    根据某些实施例,本发明提供将多个流前提条件约束和变异操作批处理为操作列表,并让它们作为一个原子多重修改来执行。操作包括:流元数据前提条件约束、流创建、流删除、流重命名、从其他流中复制现有范围引用,以及设置诸如失效时间、只读标记、访问控制信息,以及复制策略之类的各种流属性。另外,本发明的一些实施例提供以对同一个多重修改内的其他修改操作的引用来表达跨流操作的能力。例如,在一多重修改内,可能有由该多重修改所创建的应用于流的额外的操作。类似地,在一多重修改内,可能有由该多重修改删除或重命名的应用于流的额外的操作。通过将多重修改中记录的每一单个操作与目标流标识相关联,并通过在跨流操作中按照被执行的多重修改中的它们各自的记录索引来引用源流,可以在多重修改的过程中的任何时间,引用在多重修改过程中其标识被创建或其名称被更改的流。例如,如果在要执行的操作的列表中有5个记录,那么,如果第三操作正在创建一个新的流,则其他操作中的任何一个都可以引用该流作为操作3中的流。

    根据一个实施例,本发明提供将非修改前提条件约束表达为多重修改中的操作的能力。这些操作本身不导致流的状态的任何变化;然而,如果不满足前提条件,则它们会导致整个多重修改失败。这允许多个客户机实现对流状态的协调的操纵,而不要求使用外部锁或其他同步机制??梢灾付ǖ那疤崽跫氖纠ǎ毫鞔嬖?、流名称、流标识(重命名后保留的,但在删除/重新创建后会改变的唯一ID),流版本号、流失效时间,以及范围引用计数。

    根据再一个实施例,本发明提供了作为原子多重修改的一部分以将流内容的某些部分有效地复制到新的流中的能力。流可以被建模为对分布在存储节点的网络中的相邻的数据块(范围)的引用的有序序列。通过简单地读取其内容并写入带有相同数据的新流(但是在新范围中),可以复制流。然而,从一个范围将大量的数据复制到另一范围不仅是涉及多个网络节点的非常消耗网络/磁盘的活动,而且,一个以上的流可以引用相同的范围??梢约虻サ赝ü粗品段?,将一个流的非常大的部分有效地复制到不同的流(可能不同的位置);此动作是轻型的,不需要复制实际流数据内容。此外,还可以由中心元数据服务器来维护执行这种复制所要操纵的所有状态。此模型的结果是,将流内容的潜在大部分从一个流复制到另一个流可以作为原子多重修改的一部分来执行,而不要求锁保留较长时间??突Щ梢晕矶嗄康氖褂么斯δ?,包括流级联、垃圾回收、日志/日记截断、单实例化,以及创建别名。另外,可以将大量的不相关的操作批处理为原子多重修改,以减少完成一定量工作所需的事务的数量。由于元数据修改是耐久的事务,因此,它们必须被冗余地提交永久性存储器才能视为完成。耐久的存储器(磁盘)提交操作的延迟/性能可以是事务处理系统的可缩放性/性能中的主要限制因素,将许多操作组合为单一提交的能力是有利的。同样,由于服务器能够在应用任何更改之前检查所有操作,因此,可以实现否则将不可能的优化。

    根据一些实施例,本发明促进表达“全或无”语义和“同时操作”?!叭蛭蕖庇镆灞Vち?,如果多重修改中的任何操作失败,那么,整个多重修改就失败,被选择用于修改的流的状态将保持在开始多重修改之前的状态。这可使客户机依赖于状态的一致性以及多重修改的原子性。多重修改系统中的同时操作可使某些修改集合在单一原子多重修改中发生,如果操作严格地按顺序执行,将是困难的或者效率低。作为示例,可以在同一个多重修改中利用一个操作将流“A”重命名为“B”,在另一操作中将流“B”重命名为“A”(即,利用两个操作在名称空间中调换两个流)。如果按顺序执行,这两个操作将不会成功,因为第一操作由于名称空间冲突将失败。按顺序执行调换将要求三个操作并引入临时流名称(即,将“A”重命名为“C”,将“B”重命名为“A”,将“C”重命名为“B”)。如果在其他操作成功之后一个操作失败,将使“逆转”部分地完成的多重修改的过程复杂化(全或无语义)。将原子多重修改视为都同时应用的操作的无序集,消除了客户机表达中间一致状态的必要性,可使服务器优化原子多重修改的实现。

    根据本发明的进一步的实施例,本发明提供使用原子多重修改实现简单客户机可访问的分布式锁和分布式租约的能力。流元数据包括失效时间属性,除非延长了失效时间,该属性可以被用来导致流在指定时间间隔之后自动被删除。通过与原子多重修改结合使用失效时间,一组客户机可以通过尝试创建带有商定的名称的新的流,来为租约或锁竞争,并可以通过延长成功地创建的流上的失效时间来延长租约??梢酝ü晕掖唇ǖ淖庠剂鞯拇嬖谝约捌涠孕痰拿瞥中涤凶魑钔獾那疤崽跫砑拥蕉嘀匦薷闹?,有效地将租约/锁的所有权作为前提条件添加到任何其他流元数据原子多重修改。如果一个客户机在持有租约/锁时失败,则当其失效时间到达时,可以自动删除租约或锁文件,允许另一客户机声明租约。由于租约或锁被表示成普通流,可用于流的工具和机制(例如,名称空间组织、访问控制、浏览/查看等等)也固有地可用于租约和锁。

    因此,本发明的一个实施例涉及体现了用于执行作为单一原子单位执行对一个或多个流的多重修改的方法的计算机可执行指令的计算机可读取的存储介质。选择用于修改的一个或多个流,作为选定流。在与所选流流相关联的一个或多个元数据上获取锁。从所选流解耦与选定流相关联的名称。对所选流执行多个修改。将与所选流相关联的名称重新耦合到所选流。释放与一个或多个选定流相关联的元数据上的锁。

    根据另一实施例,本发明涉及体现了用于执行作为单一原子单位执行对一个或多个流的多重修改的方法的计算机可执行指令的计算机可读取的存储介质。选择用于修改的一个或多个流,作为选定流。在与所选流流相关联的元数据上获取锁。从所选流分离与每一个选定流相关联的名称。对所选流执行第一修改。确定如果执行,第二修改会产生不一致性。逆转对所选流的第一修改。将与所选流相关联的名称重新耦合到所选流。释放与所选流相关联的元数据上的锁。

    根据再一个实施例,本发明涉及存储了作为单一原子单位执行对一个或多个流的多重修改的方法的计算机可执行指令的计算机可读介质。选择用于修改的一个或多个只加流,作为选定流。在与所选流相关联的元数据上获取锁,其中,获取锁包括将带有预定名称的流修改为锁流。从其相关联的选定流,解耦与每一选定流相关联的名称。对所选流应用第一修改。确定如果应用,第二修改是否会产生不一致性。如果该修改将产生不一致性,那么,逆转对所选流的第一修改。如果第二修改将不会产生不一致性,那么,对所选流应用第二修改。将与所选流相关联的名称重新耦合到所选流。释放与所选流相关联的元数据上的锁。

    已经描述了本发明的各实施方式的概要,下面将描述其中可以实现本发明的各实施方式的示例性操作环境,以便为本发明的各个方面提供一般上下文。首先具体参考图1,典型的网络拓扑100包括多个互联的网络段101、102、103、104,每一段都连接到更大的网络115。网络段101具有参与数据存储的主机106和两个节点105,107。网络段102具有参与数据存储的两个节点108,109。网络段103具有参与数据存储的主机111和两个节点110,112。最后,网络段104具有参与数据存储的两个节点113,114。

    作为示例,网络上的任何一个节点都可以充当描述存储在网络中的流的元数据的位置,包括每一流中的范围引用的列表,以及保留每一范围的节点集。主机111和主机106上的客户机会话可能同时希望对具有存储在节点112和节点109上的范围实例的流执行原子多重修改。节点110可能充当元数据控制器。在此情况下,主机111和106两者将同时向节点110发送对所希望的流的元数据进行更改的请求,将发生赛跑。通过规定适当的前提条件约束,无论哪一个节点始发了将被节点110成功地处理的第一请求,其将被允许修改与流相关联的元数据。第二节点的请求将失败,要求第二节点通过例如,放弃操作或从一致点重新启动来处理前提条件失败。这是乐观的并行性模型中所希望的行为。如果第一和第二节点需要协调涉及多个不同的事务的更加复杂的活动,则它们可以建立锁和租约,包括对它们的多重修改请求中的专用锁/租用流的前提条件和操纵,要求失败的节点等到锁被释放才能执行其修改。

    现在参考图2,示出了示例性节点,并一般性地表示为计算设备200。计算设备200只是合适的计算环境的一个示例,而非旨在对本发明的使用范围或功能提出任何限制。计算设备200也不应被解释成对于所示出的任一组件或其组合有任何依赖或要求。

    本发明可以在计算机代码或机器可使用指令(包括由计算机或诸如个人数据助理或其他手持式设备之类的其他机器执行的诸如程序??橹嗟募扑慊芍葱兄噶?的一般上下文中来描述。一般而言,包括例程、程序、对象、组件、数据结构等等的程序??槭侵钢葱刑囟ㄈ挝窕蚴迪痔囟ǔ橄笫堇嘈偷拇?。本发明可以在各种系统配置中实施,包括手持式设备、消费电子产品、通用计算机、更专用计算设备等等。本发明也可以在其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实施。

    参考图2,计算设备200包括直接地或间接地耦合以下设备的总线201:网络设备202、CPU?203、存储器204、存储205,以及输入/输出(I/O)设备206。总线201表示一个或多个总线(诸如地址总线、数据总线或其组合)。虽然为了清楚起见利用线条示出了图2的各框,但是实际上,各组件的轮廓并不是那样清楚,并且比喻性地来说,线条更精确地将是灰色的和模糊的。例如,许多处理器具有存储器。我们认识到这是本领域的特性,并重申,图2的图示只是例示可以结合本发明的一个或多个实施例来使用的示例性计算设备。在诸如“工作站”、“服务器”、“膝上型计算机”、“手持式设备”等等之类的类别之间不进行区别,因为所有这些都在图2的范围内并都被称作“计算设备”或“节点”。

    计算设备200通常包括各种计算机可读介质。计算机可读介质可以是可以被计算设备200访问的任何可用的介质,并包括易失性和非易失性介质,可移动的和不可移动的介质。作为示例而非限制,计算机可读介质可以包括计算机存储介质和通信介质。计算机存储介质可以包括以任何方法或技术实现的,用于存储诸如计算机可读的指令、数据结构、程序??橹嗟男畔⒒蚱渌莸囊资院头且资缘?,可移动和不可移动的介质。计算机存储介质包括,但不仅限于,RAM、ROM、EEPROM、闪存或其他存储技术,CD-ROM、数字多功能盘(DVD)或其他光盘存储,磁带盒、磁带、磁盘存储或其他磁存储设备,或可以用来存储所需信息并可由计算设备200访问的任何其他介质。

    存储器204包括易失性存储器形式的计算机存储介质。示例性硬件设备包括诸如RAM之类的固态存储器。存储205包括非易失性存储器形式的计算机存储介质。存储器可以是可移动的,不可移动的,或两者的组合。示例性硬件设备包括固态存储器、硬盘驱动器、光盘驱动器等等。计算设备100包括从诸如存储器204、存储205或I/O???06之类的各种实体读取数据的一个或多个处理器(CPU)203。I/O设备206允许计算设备200在逻辑上耦合到包括输入组件和输出组件在内的其他设备,其中一些可以是内置的。说明性组件包括话筒、操纵杆、游戏垫、碟形卫星天线、扫描仪、打印机、无线设备等等。计算设备200包括促进与其他网络设备进行通信的网络设备202。网络设备202充当额外的I/O设备。

    本领域的技术人员将认识到,可以以许多方式格式化存储在叫做“节点”或存储器节点的网络中的数据。作为示例,诸如音乐文件、视频文件、字处理文档等等之类的独立数据文件以分布式方式存储是常见的。根据本发明的一个实施例,数据被建模为流的集合,可以将流集合组织成常规分层名称空间。图3将流300描绘为用于进行数据存储的示例性数据格式,根据本发明的一些实施例,可以对其进行原子多重修改。流300是在逻辑上相关联的数据集合。根据本发明的某些实施例,流300是只加的,其大小可以非常大,可能超过网络节点的单个存储容量的许多倍。通过句柄或名称来访问流300,诸如流300之类的每一流都具有保留和访问策略。根据本发明的某些实施例,每一流还具有相关联的全局唯一标识符(GUID),该GUID在流的寿命内是无法改变的(即,与名称不同,名称是可以修改的,GUID永久地标识其相关联的流)。流300可以被视为,例如,字节的序列。流300由范围301、302、303的有序序列组成。范围301、302、303是流300的分配单元。范围301、302、303也是只加的,每一范围301、302、303都以全局唯一标识符(GUID)来进行标识??梢越段?01、302、303分布到网络中的许多节点。范围301,302,303通常被复制,并可以将范围301,302,303的副本分布到网络中的许多节点。范围301,302,303具有大小限制(例如,2GB),并且是用于许多目的的分区单位。范围301,302,303的大小有时是受限制的,以便将流分割为可以并行地处理的块,以便故障恢复、负载平衡、复制、搜索和/或数据挖掘。范围的大小还可受存储系统的故障恢复模式的限制。

    根据本发明的某些实施例,流300存储对每一范围和/或每一范围的副本的位置的引用。例如,范围301的副本存储在节点304上,范围302和303的实例两者都存储在节点305上。应该注意,范围是可以复制的。在这些情况下,可以在多个位置访问范围数据,位置是其副本的位置。范围的GUID将不会变化,但是,其副本的号码和位置可以随着时间而变化。为简明起见,此示例只说明了范围不被复制的情况。存储引用的一个优点是,可以将范围引用添加到流中,而不复制或移动与范围相关联的任何数据。作为示例,如果将范围301的另一副本添加到流300中,则不需要改变或复制节点304上的数据。相反,将额外的范围引用添加到已经在流300中的范围引用的列表中。

    根据本发明的一实施例的,通过元数据来表示流,元数据本身可以分布在网络中,或存储在集中式服务器中。现在参考图4,作为图示,元数据400是包含有关流的信息的数据集合。根据本发明的某些实施例,与流相关联的元数据400包括当前与流401相关联的名称。流的名称定位访问数据的客户机所使用的目录结构中的流。名称可以随着流被移动和修改而改变。根据本发明的某些实施例,主机通过名称401来访问流。元数据400还包括GUID?402,它是全局唯一的,是永久地,排他地与流相关联的标识符(即,流的GUID?402决不会改变,并且没有两个流共享同一个GUID)。与流相关联的元数据400还包含构成流的范围引用403的列表。每一范围引用403都标识特定范围,并允许客户机或服务器定位网络中的范围的所有副本,提供对实际数据的物理访问。

    原子多重修改涉及对一个或多个流执行多次修改。作为示例,修改包括创建新的流、删除流、重命名流、级联两个或更多流,创建现有流的副本,以及将一个流的范围的子集复制到第二流。本领域的技术人员将认识到,有许多可以组合使用的其他可能的修改,以构成原子多重修改。现在转向图5,考虑原子多重修改的一个示例。指令503的多重修改集包括将流501从“A”重命名为“B”,以及将流502从“B”重命名为“A”。本领域的技术人员将认识到,使用标准数据复制方法将要求临时存储区来执行这样的修改,将在从故障恢复时产生复杂性,因为在发生错误的情况下恢复逻辑将需要清理临时存储区,将进一步需要确保两个流501和流502在从故障恢复之后到达全局性一致的状态。然而,根据本发明的一个实施例,好像一个步骤地执行原子多重修改,从而简化恢复逻辑,因为两个流501和流502面临故障时处于一致状态,而没有临时存储区需要清理。作为示例,首先从它们的元数据中删除流501和流502的名称(分别是“A”和“B”),以便两个流变为无名的。这将从流名称空间解耦流,允许多重修改发生。

    执行修改集503中的第一修改509。在此情况下,流501将被重命名为“B”。为此,将流501的名称设置为“B”,并将流501附加到流名称空间。这会成功,而不会产生名称空间冲突,因为当流502与流名称空间分离时,名称“B”变得可用?;怪葱行薷募?03中的第二修改512。在此情况下,流502将被重命名为“A”。为此,将流502的名称设置为“A”,并将流502附加到流名称空间。这会成功,而不会产生名称空间冲突,因为当流501与流名称空间分离时,名称“A”变得可用。

    现在参考图6,提供了示出了根据本发明的一个实施例的用于对一个或多个选定流执行原子多重修改的方法600的流程图。选择用于修改的一个或多个流,如框601所示。本领域的技术人员将认识到,选择流来进行修改的方式有多种。作为示例,应用程序可以提供流的列表,每一流都通过其当前名称或者GUID引用,这些流将被包括为选择用于进行修改的流。使用名称和/或GUID的列表来查找每一个流的元数据,包括与流相关联的范围引用的列表。根据本发明的某些实施例,还基于元数据中的信息,定位每一流的物理位置。

    在与选择用于进行修改的一个或多个流中的每一个相关联的元数据上获取锁,以及被多重修改涵盖的流名称空间,如框602所示。一旦获取了锁,从它们的相应的名称分离用于删除或重命名的所选流,如框603所示。根据本发明的某些实施例,以这样一种方式促进应用多次修改,修改影响流就好像修改是同时发生的那样。作为示例,流从相关联的名称的解耦是通过创建存储了流GUID与每一个选定流的名称的原始耦合的临时映射来完成的。

    多重修改可以作为原子多重修改来进行。虽然在图6中示出了两个修改,但是,本领域技术人员将认识到,可以将许多修改结合起来,以形成作用于一个或多个选定流的单一原子多重修改。对一个或多个流执行第一修改,如框604所示,并执行第二修改,如框605所示。根据本发明的某些实施例,进行这些修改,以便它们看起来好像是同时发生的,而不是按顺序发生的。作为示例,修改包括创建新的流、删除流、重命名流、更新流的元数据,创建现有流的副本,级联两个或更多流,以及将一个流的范围的子集复制到第二流。

    一旦完成了原子多重修改中的所有修改,就将流重新耦合到名称,如框606所示。根据本发明的某些实施例,基于由应用于对应的流的每一个修改对临时映射作出的更改,将流名称耦合到流。流的GUID被用来跟踪这些变化,并影响重新耦合。释放与一个或多个选定流中的每一个相关联的元数据上的锁,以及由多重修改涵盖的流名称空间,如框607所示。

    现在转向图7,提供了示出了根据本发明的一个实施例的用于对一个或多个选定流执行原子多重修改的方法700,其中,多重修改中的一修改不能成功地完成。在执行构成原子多重修改的多个修改的过程中,多个修改中的一个不能成功地完成是有可能的。作为示例,多重修改中的两个修改都可能尝试产生带有相同名称的流(例如,通过流创建或重命名)。因此,如果多重修改被允许成功,则所产生的状态将取决于执行修改的顺序,没有办法好像同时的那样执行它们。一旦发现了这样的情况,就逆转到目前作为原子多重修改的一部分执行的所有修改,并将流元数据复位到开始原子多重修改之前的状态。类似于图6的方法600,选择一个或多个流,以便对它们应用原子多重修改,如框701所示,在与每一个选定流相关联的元数据上获取锁,如框702所示。

    将每一选定流从其相关联的名称解耦,如框703所示,对一个或多个选定流应用第一修改,如框704所示,类似于图6的框603和604。作出对所选流的第二修改将不会成功地完成的确定,如框705所示。本领域技术人员将认识到,有许多方式可以进行这样的确定。根据本发明的某些实施例,使用临时可逆变异的历史来另外提供用于逆转执行原子多重修改过程中的任何步骤的机制。

    一旦确定将在应用原子多重修改中产生失败,就逆转应用的修改,如框706所示。在逆转对所选流进行的任何修改之后,将流与它们的相应的原始名称重新耦合,删除新创建的流,如框707所示。一旦逆转了修改,将流与它们的原始名称重新耦合,并删除新创建的流,就释放锁,如框708所示,类似于图6中的框607。

    根据本发明的一些实施例,在图8的流程图中描绘了用于对一个或多个选定流执行原子多重修改的方法。如果检测到构成原子多重修改的多个修改中的一个将失败,则中止原子多重修改,并将流返回到开始原子多重修改之前的状态。选择用于修改的一个或多个流,如框801所示,获取与所选流相关联的元数据上的锁,如框802所示,类似于图6的框601和602。

    从其相关联的名称解耦用于删除或重命名的每一流,如框803所示,并执行第一修改,如框804所示,类似于图6的框603和604。然后,确定应用第二修改是否将不能成功地完成,如框805所示??梢砸岳嗨朴谕?的框705的确定方式进行此确定。例如,如果应用第二修改会将一个流与已经通过第一修改或者在前面的事务中与另一流相关联的名称相关联,则确定第二修改将不会成功地完成。

    如果确定第二修改可以成功地执行,然后,执行第二修改,如框806所示,将流重新耦合到它们的最后的相关联的名称,如框808所示,释放与被选择用于修改的流相关联的元数据上的锁,以及流名称空间,如框809所示??梢苑直鹄嗨朴谕?的步骤605、606,以及607执行这些步骤中的每一个。

    然而,如果确定第二修改将失败,那么,逆转第一修改,如框807所示,将流重新耦合到它们的原始相关联的名称,如框808所示,删除任何新创建的流,释放与选择用于修改的流相关联的元数据上的锁,以及流名称空间,如框809所示??梢苑直鹄嗨朴谕?的步骤706、707,以及708执行这些步骤中的每一个。

    作为图示,图9示出了执行多重修改的一个示例。图9的示例包括描绘系统中的状态的“校验点+日志”系统的实现。在这样的系统中,系统状态通过包含叫做“校验点”的完全状态信息的快照以及包含自从最后已知的校验点以来作出的更改的各种较小的增量来表示。日志包含这些增量的列表。为到达系统的当前状态,客户机将对最后的快照应用日志中的最后的快照之后发生的所有增量。最近的快照之前发生的快照和增量都旧了,并且不再需要;因此,垃圾回收过程可以周期性地删除旧的快照和增量。本领域技术人员将认识到,原子多重修改有许多其他系统应用。

    例如,考虑存储了相册的系统,其中,该相册利用三个流来表示:ALBUM.CHECKPOINTS?901,ALBUM.DELTA?902,以及ALBUM.DATA?903。ALBUM.CHECKPOINTS?901存储所有照片的完整列表,以及相册中的特定时间点的注释。照片的删除和添加存储在ALBUM.DELTA?902中。实际照片存储在ALBUM.DATA?903中。此相册可以被成千上万客户机同时访问,每一客户机都添加新的照片、编辑和替换照片,删除照片,重命名照片,注解照片等等。周期性地,ALBUM.DELTA?902文件变得非常大,并导致客户机遇到长的加载时间。同样,ALBUM.DATA?903中的范围可能不再具有从任何最近校验点以来的任何引用,或者增量(例如,那些范围中的照片已经被删除)。

    成千上万的客户机中的每一个都可以访问这些流中的每一个。垃圾回收过程可以最终决定从流中删除不需要的项。例如,假设ALBUM.CHECKPOINTS?901包括两个范围,第一范围带有旧校验点904,第二范围带有最新的校验点905??梢陨境尚Q榈?,因为新的校验点包含完整的系统快照。ALBUM.DELTA?902还包括多个范围。对于此示例,假设自从当前校验点905以来的相关增量都在ALBULM.DELTA的最后一个范围906中。ALBUM.DATA?903包含许多范围,在它们之间分散着没有引用流的范围;换言之,可以被删除的范围。例如,只有带有ID?R、S、Y?Z(912,913,914,915)的范围将被保留ALBUM.DATA流中。为清理不需要的范围,垃圾回收过程可以执行下面的修改:从ALBUM.CHECKPOINTS?901删除旧的范围,从ALBUM.DELTA?902删除旧的范围,并删除ALBUM.DATA?903中的在ALBUM.CHECKPOINTS?901和ALBUM.DELTA?902中的剩余范围中没有被引用的任何范围。垃圾回收过程可以使用原子多重修改来完成这些修改。

    垃圾回收过程可以使用的原子多重修改的示例包含下面的修改。修改1:创建名为ALBUM.CHECKPOINTS?907的新的流,删除带有STREAM_ID?ABCD?901的流,并将EXTENT_ID?B?910附加到被指定了ID?QRST的新的流。修改2:创建名为ALBUM.DELTA?908的新的流,删除带有STREAM_ID?AFDE?902的流,并将EXTENT_ID?L?911附加到被指定了STREAM_IDVCDE的新的流。修改3:创建名为ALBUM.DATA?909的新的流,删除带有STREAM_ID?DEFF?903的流,并将EXTENT_ID?R?912、EXTENT_ID?S?913、EXTENT_ID?Y?914以及EXTENT_ID?Z?915附加到被指定了ID?RSTV的新的流。因为所有修改都是以原子方式执行的,客户机决不会具有相册的不一致的视图。在此特定示例中,在单独的多重修改事务中修改这些流中的每一个在逻辑上也是正确的。由于效率原因(减少事务的数量),在单一多重修改事务中修改这些流。但是本领域的技术人员将认识到有多个流必须在一个原子事务中修改的情况,以确保这些流之间的一致性,在这些情况下可以使用多重修改支持。

    在不偏离本发明的精神和范围的情况下,所描绘的各种组件的许多不同的布局,以及未示出的组件也是可以的。所描述的本发明的各实施例旨在是说明性的而非限制性的。不偏离其范围的备选实施例对于本领域的技术人员是显而易见的。在不偏离本发明的范围的情况下,精通技术的人员可以开发用于实现如前所述的改进的备选装置。

    可以理解,某些特征和子组合是有用的,并且可以在不参考其他特征和子组合的情况下使用,它们都在权利要求书的范围内。并非各种图形中所列出的所有步骤都需要按所描述的特定的顺序执行。

    关于本文
    本文标题:对分布式存储器系统中的数据的原子多重修改.pdf
    链接地址://www.4mum.com.cn/p-5875370.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 刘伯温六肖六合稳赚网 视频彩票技巧规律 飞艇赛车pk10直播 重庆时时历史开奖记 幸运飞艇6码2期免费计划 pk10极速开奖直播现场 秒速时时两面技巧 pk10模拟投注软件 太子中心六肖中特 福彩3d独胆什么意思 大乐透最新期预测 pk10真的可以稳赚吗 后二直选复式每天稳赚技巧 11选5稳赚钱一技巧 幸运飞艇7码怎么搞 dnf挣钱快的方法