分布式内容存储和取回的制作方法
分布式内容存储和取回的制作方法
【专利说明】分布式内容存储和取回
[0001] 本申请为题为"分布式内容存储和取回"的中国专利201080041777. 2的分案申 请。
[0002] 其他申请的交叉引用 本申请要求于2009年9月21日提交的美国临时专利申请号61/277,206 (代理案号TRANP006+)、标题为DISTRIBUTEDCONTENTSTORAGEANDRETRIEVAL的优先权，出于所有目 的通过引用将其结合于此。
【背景技术】
[0003] 分布式数据存储系统的设计和实现由于确定数据在何处以及应当存储于何处的 问题而复杂。尽管已经存在将对象名称映射到存储位置的分布式编索引技术，但是它们需 要大量存储。这些技术未提供信息将存储于它将最终被访问的位置附近的保证。现有分布 式存储技术在故障出现时具有大量可用性和性能问题。
【附图说明】
[0004] 在下文详细描述和附图中公开本发明的各种实施例。
[0005]图1是图示分布式内容存储系统的一个实施例的框图。
[0006] 图2是图示用于访问和/或存储内容对象的过程的一个实施例的流程图。
[0007]图3是图示用于收集和分布访问统计的过程的一个实施例的流程图。
[0008] 图4是图示存储节点的一个实施例的框图。
[0009] 图5是图示用于在存储节点维持统计的过程的一个实施例的流程图。
[0010] 图6是图示对对象名称中的对象特征信息编码的过程的一个实施例的流程图。
[0011] 图7是图示用于存储对象的过程的一个实施例的流程图。
[0012] 图8是图示分布式内容存储系统的一个实施例的框图。
[0013] 图9是图示用于访问对象的过程的一个实施例的流程图。
[0014] 图10A是图示用于从分布式内容存储删除对象的过程的一个实施例的流程图。
[0015] 图10B是图示用于可靠地删除对象的负责副本的过程的一个实施例的流程图。
[0016] 图11是图示用于在分布式内容存储中保存改变的过程的一个实施例的流程图。
[0017] 图12是图示用于对存储于分布式内容存储中的对象进行改变的过程的一个实施 例的流程图。
[0018] 图13是图示用于存储对象的过程的一个实施例的流程图。
[0019] 图14A是图示用于访问对象的过程的一个实施例的流程图。
[0020] 图14B是图示用于在分布式内容存储系统中创建对象的过程的一个实施例的流 程图。
[0021]图15是图示用于存储数据库或者其他大文件的过程的一个实施例的流程图。
[0022] 图16是图示用于访问和存储对象的过程的一个实施例的流程图。
[0023] 图17是图示存储装置的一个实施例的框图。
[0024] 图18是图示存储盘的一个实施例的框图。
【具体实施方式】
[0025] 可以用诸多方式(包括如过程；装置；系统；物质组成；在计算机可读存储介质上 包含的计算机程序产品；和/或处理器(诸如如下处理器，该处理器被配置成执行在耦合到 处理器的存储器上存储的和/或该存储器提供的指令)）实现本发明。在本说明书中，这些 实现或者本发明可以采用的任何其他形式可以称为技术。一般而言，可以在本发明的范围 内变更公开的过程的步骤顺序。除非另有明示，描述为被配置成执行任务的部件(诸如处理 器或者存储器）可以实现为暂时被配置成在给定时间执行该任务的一般部件或者制造成执 行该任务的具体部件。如这里所用，术语'处理器'是指被配置成处理数据(诸如计算机程 序指令）的一个或者多个设备、电路和/或处理核。
[0026] 下文与图示本发明原理的附图一起提供对本发明一个或者多个实施例的详细描 述。结合这样的实施例描述本发明，但是本发明并不限于任何实施例。本发明的范围仅由 权利要求书限制，并且本发明涵盖诸多替代、修改和等效物。在下文描述中阐述诸多具体细 节以便提供对本发明的透彻理解。出于示例的目的而提供这些细节，并且无这些具体细节 中的一些或者所有细节仍然可以根据权利要求实现本发明。为求简洁，尚未详细描述在与 本发明有关的技术领域中已知的技术素材，使得未使本发明不必要地变得难以理解。
[0027] 公开用于分布式内容存储和取回的技术。使用多种分布式系统技术，公开的对象 存储跨越全局分散的网络冗余地散布信息。在各种实施例中，对象存储于它们最可能被使 用的位置附近，从而使系统可用性、对地理分散的资源的使用和最终用户性能最大化。系统 经由分布式合意（consensus)机制共享对象访问和存储简档。当尝试取回或者存储对象时， 针对特征扫描对象标识符。使特征相关以估计每个位置访问该对象的频率。针对每个潜在 存储位置，组合网络拓扑信息与这些估计以发现该存储选项的成本。确定性函数组合这一 成本数据与管理员配置的策略以确定数据应当存储于何处以及如何取回对象。函数被构造 成即使添加或者去除存储位置时仍然造成公平和最少对象重新分配。在一些实现中，管理 策略和索引信息存储于全局叠加网络中。该设计受控制系统理论严重影响，因为系统严重 受抑制并且表现对使用和拓扑改变的斜坡响应。
[0028] 如这里所用，术语"特征"是指对象标识符的性质。性质可以是布尔或者可以由在 〇与1之间的置信水平代表。任何对象标识符可以视为拥有特征集合。术语"访问概率矩 阵"是指如下矩阵，该矩阵包含从给定节点进行对具有给定特征的对象的任何给定访问的 概率，其中行代表对象特征而列代表请求位置。"访问计数矩阵"是指除了每个单元包含访 问计数而不是百分比之外具有与访问概率矩阵相同的结构的矩阵。"节点"是分布式系统中 的负责对象存储和对象查询的计算机或者其他设备两者。可以将节点和存储设备组织成层 级。该层级可以包含作为级别节点的存储设备和管理员指定的下级的分组。作为例子，可 以有称为"大陆"的层级级别，该级别包含北美洲、欧洲和亚洲，每个洲包含如下办公室，这 些办公室包含如下节点，这些节点包含存储设备。"位置"是层级中的任何给定实体(例如具 体办公室或者具体存储设备)。
[0029] 使用以下矩阵约定（convention): ?#表示矩阵A的转置 ? 4表示矩阵A的i行j列中的值 ?矩阵等式中的1表示1值填充的适当大小的行或者列lXn或者nXl矩阵。
[0030] ? (^表示矢量C的第j个元素 使用以下概率约定： ?汽剑功表示在给定势3真时J为真的概率。
[0031] ?A表示访问概率矩阵的行i代表的特征存在。
[0032] ? 示访问概率矩阵的列J代表的节点将执行访问。
[0033] ?巧表示除了访问概率矩阵的列J代表的节点之外的节点将执行访问。
[0034]图1是图不分布式内容存储系统的一个实施例的框图。在所不例子中，在所不例 子中由客户端102和104代表的一个或者多个客户端经由因特网(和/或一个或者多个其 他网络）106连接到多个存储节点108。每个节点108被配置成存储如下数据对象(诸如文 件)，这些数据对象包括存储的内容对象体。在各种实施例中，每个节点108本地收集统计， 例如针对一个或者多个特征中的每个特征，已经在节点访问（或者替代地为最近访问）具有 该特征的多少个对象和/或在节点上存储具有该特征的多少个对象。节点108经由分布式 合意机制协作以共享访问和/或存储统计。生成并且向节点分发全局访问概率矩阵，并且 在相应节点使用这些矩阵做出存储和/或对象访问决策。例如，可以在至少部分地由于对 象具有如下特征或者特征集合而选择的节点上存储等于对象的所有其他内容，该特征或者 特征集合造成在作出存储决策（即选择用于将对象存储于其上的一个或者多个节点）的节 点处使用用于相应节点的收集和分发的每个特征的访问概率来确定统计上可能将从所选 节点(或者从在所选节点附近的某处)访问待存储的对象。在各种实施例中，成本信息(诸如 经由在节点A(或者在节点A附近）向对象存储于其上的节点B进行的请求来访问对象的 成本)与访问和/或存储的对象统计一起考虑。在一些实施例中，也实施管理策略并且将这 些策略纳入到节点选择中。例如如果已经选择第一节点A用于存储对象并且管理策略要求 两个副本存储于分离的地理位置，则选择未在与节点A相同的地理位置的第二节点B用于 存储第二副本。
[0035] 图2是图示用于访问和/或存储内容对象的过程的一个实施例的流程图。在所示 例子中，当将存储对象或者希望访问对象时，先前收集的统计(例如每个节点的每个特征的 访问和/或存储对象计数，这些计数被转换成如下访问概率，这些访问概率针对每个节点 指示具有特定特征的对象在该节点处被存储和/或将被访问的可能性）和将存储的或者希 望访问的对象的特征用来针对每个候选节点确定将在该节点访问（和/或在一些实施例中 存储的）对象的概率（202)。确定的访问概率与成本、管理策略和/或其他信息一起用来选 择将在其存储和/或从其尝试访问对象的一个或者多个节点（204)。在一些实施例中，访问 统计用来选择将在其上存储待存储的对象的一个或者多个节点。在一些实施例中，存储的 对象统计用来选择如下一个或者多个节点，将从该节点请求访问待访问的对象。关于存储， 在各种实施例中的方式寻求在如下位置存储对象，这些位置使它们在受制于管理策略的要 求时以最小成本使如下用户的可用性最大，这些用户被确定为统计上最可能访问它们。类 似地，在各种实施例，关于在公开的方式之下的访问，请求者尝试从至少部分地基于共享的 访问和/或存储对象统计以及根据这些统计确定的概率来确定的如下节点取回内容，该节 点可能让对象存储于其上，例如因为存储节点可能将基于相同（或者有关）统计已经选择它 用于存储节点。
[0036] 在各种实施例中，在系统内的每个节点保持每个特征的对包含该特征的对象的访 问在该节点被发起多少次的计数。可以在节点处在分布式存储系统内出于各种原因（例如 代表在节点上运行的过程或者由于该节点接收的来自用户或者客户端计算系统的外部请 求）而发起访问或者其他操作。此外还维持从这一节点访问的对象数量的计数。类似地， 在一些实施例中，每个节点可以保持它的本地存储文件中的多少个文件具有给定特征和存 储的文件总数的计数。当已经预备并且准备好分发新访问和存储简档时，节点经由原子承 诺（commitment)协议关于新简档达成协定。这一协定包括简档本身和简档将变得活跃的 时间两者。通过自动改变为新简档，系统确保节点将总是将一致 信息用于存储和搜索决策。 延迟的激活时间也允许统计简档的多个版本为所有节点已知。这允许搜索、存储和异常列 表处置使用任何或者所有可用版本来做出决策。例如新存储决策可能使用尚未活跃但是不 久将变成活跃的简档。在一个实施例中，系统可以保留最后四个访问简档并且能够针对根 据那些简档存储的任何对象使用那些简档来对对象定位而不求助其他手段。在一个实施例 中，节点保证将在访问简档改变之后需要异常列表条目的所有它们的对象在访问简档改变 生效之前在异常列表中具有这样的条目。
[0037]系统定期聚集来自每个节点的特征访问模式。这可以由系统内的减少信息的单个 动作器、通过全局MapReduce步骤、通过交易协定机制或者通过其他手段来完成。
[0038]图3是图示用于收集和分发访问统计的过程的一个实施例的流程图。以下关键步 骤出现于各种实施例中： 从每个节点收集（302)存储文件和最近访问的每特征计数。可以组合这些计数以形成 每个位置和特征对的相应计数的频率矩阵。在一些实施例中，将访问简档信息存储为矩阵， 其中行对应于特征而列对应于从其出现访问的位置。存储简档将随时间接近访问简档，因 为基于访问简档选择存储位置。存储计数代表系统的实际状态而不是动态趋势，因此它们 在未过滤时最准确。每个节点确切知道如下值，这些值应当填充它的列。
[0039] 组合信息与先前访问简档（304)。经常希望向较新的信息给予较大权重。一种可 以实现此的方式是通过使用认为最近信息比历史数据更重要的低通滤波器(诸如无限冲激 响应滤波器)。替代地，全局优化技术(诸如仿真或者量子退火)也可以用来发现如下新访问 简档，该访问简档在接近最近观测的访问统计时使对象重新定位最小化。随机方法可以用 来确定将最小化的分数；替代地，可以使用如下函数，该函数基于提议的访问简档与最近观 测的访问率和按照特征对当前存储位置的计数有多么好地匹配来计分。这一过程通过比较 重新定位成本与节省的访问成本来区分简档改变的优先次序。从每个节点访问的对象的总 计数可以与整个集群执行的全部访问的数量之和一起由相同流程维持。随着过去观测的权 重减少，过去数据代表的对象访问的计数也按照相同比例减少。对于对计数数据的过滤而 言希望但是未必确保所有单元为非零。这防止贝叶斯推论将任何特征的存在解释为针对任 何位置的绝对的排除确保。
[0040] 计算访问计数矩阵中的所有单元的标量和除以矩阵代表的对象访问的总计数，从 而给出每个访问存在的对象特征的平均数量(即平均特征计数）（305)。
[0041] 通过将访问计数矩阵中的每个值除以矩阵中的所有单元之和以针对特征和节点 的每个配对产生访问概率来形成新访问概率矩阵（308)。换而言之，这一矩阵在每个条目 中存储访问的给定特征将来自与该条目的列对应的节点并且是与该条目的行对应的特征 的概率(受制于朝着滤波器提供的最近数据的偏斜)。这一概率对应于如下访问的预计比例 (该比例是访问频率)，这些访问将针对来自相应位置的具有这些特征的对象。
[0042]针对所得访问概率矩阵中的每个特征行，计算观测的统计显著性（309)。这是通过 首先发现跨越所有特征的访问计数之和代表的空假设分布并且然后计算如与全局访问概 率的空假设分布相比的用于行的P值来执行的。这帮助确定给定行是否是有用的访问位置 预测值（predictor)或者是否纯粹偶然地产生从基线分布的偏斜。这在存在关于特征的访 问模式的很少数据时特别有用。
[0043]向分布式存储系统中的各种节点分发访问概率矩阵、统计显著性矢量和标量平均 特征计数（310)。在其他实施例中，向各种节点分发计数，并且在分发之后节点执行概率计 算。在各种实施例中，也分发每个对象的平均特征数量或者对象总数。
[0044] 图4是图示存储节点的一个实施例的框图。在各种实施例中，存储节点402可以 包括服务器或者其他计算机。在所示例子中，节点402包括经由连接406提供网络连接性 的通信接口 404 (例如网络接口卡)。内容访问和存储引擎408经由通信接口 404和连接 406来与客户端和/或其他节点通信以执行任务(诸如提供对请求内容对象的访问以及例 如在节点402上和/或在对等节点上存储待存储的内容对象)。在一些实施例中，内容访问 和存储引擎408包括在处理器上运行的一个或者多个软件模块。在各种实施例中的内容访 问和存储引擎408被配置成在对象存储410中存储内容对象和/或提供对存储于其中的对 象的访问。在各种实施例中，节点可以具有多个本地"对象存储"（盘/存储位置)。内容访 问和存储引擎408在访问统计和矩阵412中维持和存储每个特征的针对本地访问和/或存 储对象的本地计数。内容访问和存储引擎408定期例如向所有对等节点和/或向一个或者 多个中心位置报告本地计数。在一些实施例中，MapReduce或者其他分布式技术用来收集 数据。在一些实施例中，在重新分发之前通过低通滤波器或者其他抑制（damping)机制变 换计数数据。合意机制可以用来保证所有访问和存储引擎共享共同简档。内容访问和存储 引擎408被配置成经由接口 404接收集中和/或在对等节点基于节点集群(节点402是该 集群的成员）中的相应节点报告的每个特征的计数来确定的访问概率和/或其他矩阵并且 使用矩阵关于特定对象基于它们的相应特征做出存储和/或访问决策。
[0045] 图5是图示用于在存储节点维持统计的过程的一个实施例的流程图。在所示例子 中，每次访问和/或存储对象（502)时，确定访问/存储的对象的特征（504)并且更新每个 特征的适用计数（506)。例如如果访问具有六个被跟踪特征的集合中的特征2、3和5的对 象，则将递增针对特征2、3和5的相应的每个特征访问计数。
[0046] 在一些实施例中，对对象特征编码或者对象特征包含在对象名称中或者通过直接 解释对象的名称可辨认对象特征。当系统尝试访问对象时，它评估关于对象名称的如下函 数，该函数解释对象名称的特性以生成特征集合。特性可以包括对象路径名分量的散列值、 字母和二合字母（digraph)频率测量、其他统计测量或者其任何组合。函数必须针对任何 给定对象名称返回确切相同特征集合。
[0047] 可以在每个节点的基础上维持每个特征的访问和存储计数。替代地，节点可以通 过针对该节点发起的尝试访问的每个特征递增每个盘上的访问计数来针对它的盘维持这 些计数。在该盘上的访问计数统计然后代表已经包含该盘的(一个或多个)节点已经针对包 含特征的对象发起访问的频率。类似地，节点可以在每个盘上维持存储于该盘上的对象计 数。在其他实施例中，可以在存储层级中的除了节点和盘之外的位置维持访问。
[0048] 图6是图示对对象名称中的对象特征信息编码的过程的一个实施例的流程图。在 所示例子中，当保存对象（602)时，例如基于包括对象的数据和/或关于对象的元数据确定 对象的被跟踪特征（604)。确定的特征用来创建(例如在首次保存对象时)或者更新(例如如 果特征从上次访问起已经改变）用来在分布式内容存储系统中知道对象的名称（606)。在 各种实施例中，每个特征由在对象名称中包括的串代表，使得在分布式存储中的任何节点 可以通过解释包括对象名称的数据来确定特征而不必检查全局或者其他索引条目。
[0049] 在一些实施例中，通过分析全局对象名称来确定对象特征。可以将对象名称形成 为层级，并且针对层级的每个部分计算的散列函数可以确定特征。此外，在名称中编码的层 级的名称或者级别还可以点缀有解析器可提取的各种附加属性。这些属性的散列可以提 供用于对象的特征。可以从对象名称提取各种其他隐含特征(诸如二合字母和三合字母频 率)。例如，最频繁三合字母可以视为对象的特征而其他三合字母则不是，或者关于每个三 合字母的频率计算的对数函数可以提供用于每个三合字母特征的置信水平。
[0050] 图7是图示用于存储对象的过程的一个实施例的流程图。在所示例子中，当接收 对存储对象的请求(例如来自客户端系统）（702)时，评估对象的名称以确定包括被跟踪的 特征的集合的哪个或者哪些特征(如果有）与对象关联（704)。针对作为(或者保留为）用于 存储对象的候选的每个节点，访问统计(例如集群范围的访问概率矩阵）用来根据对象的特 征确定待存储的对象将在该节点被访问的预计频率（706)。在一些实施例中，在确定每个节 点的概率之前和/或与之结合，如下文更完全描述的那样调整原始访问概率矩阵以实现存 储对象和/或其副本的更均匀分布。针对每个(保留)候选节点，如果对象存储于该节点，则 确定每个访问的平均成本(例如考虑如例如基于访问概率矩阵确定的在相应节点与可能从 其进行访问请求的可能节点之间的通信成本）（708)。根据适用管理策略评估预计访问频 率和成本信息以选择一个或者多个节点用于存储对象（710)。例如管理策略可以提供对象 的两个副本必须存储于不同地理位置。在一些实施例中，迭代执行706、708和710直至确 定满足适用管理策略的存储节点集合。例如管理策略可以提供对象的两个副本必须存储于 不同地理位置。可以基于访问概率和成本信息选择第一节点。从作为候选的竞争中去除第 一节点和为了服从适用管理策略而必须去除的任何其他节点。在当前例子中，可以从竞争 中例如去除在与第一节点相同的地理位置的其他节点和第一节点本身，并且如在保留节点 之间例如基于访问概率和成本信息确定第二节点（未必在与第一节点相同的地理位置，因 为已经从竞争中去除所有这样的节点)。在(一个或多个)所选节点上存储对象（712)。在一 些实施例中，除了存储对象的副本之外，每个所选节点还存储关于对象的元数据，包括如下 元数据，该元数据指示对象的"负责"副本被存储的其他位置。在一些实施例中，这样的信 息例如在存储位置的故障情况下用来向不受故障影响的节点迀移存储于出故障的位置内 存储的每个对象的副本以便恢复服从指定的冗余策略。在一些实施例中，这样的信息可以 在存储位置的故障情况下用来保证更新异常列表。可以对存储于每个节点上的元数据编索 弓丨，使得可以快速发现也在给定替代位置存储的条目。也可以对存储于每个节点上的元数 据编索引，使得可以快速发现具有给定特征的条目。在特征并非布尔的情况下，可以按照每 个特征内的置信水平对索引排序。
[0051] 图8是图示分布式内容存储系统的一个实施例的框图。在所示例子中，分布式内 容存储系统包括如下集群，该集群包括位于三个分离地理位置(例如企业或者其他实体的 三个地理地点）的三个存储节点集。与第一局域网（LAN) 804关联的节点802、与第二LAN 814关联的节点812和与第三LAN824关联的节 点822经由因特网830互连。在这一例子 中，如在上文结合图7描述的例子(其中管理策略要求第二副本存储于分离地理位置）中那 样，按照地理位置组织节点，从而使得能够在节点和/或地理基础上定义和实施管理策略。 也可以在管理员向在层级的任何级别的任何存储位置(包括但不限于盘、节点和地理位置） 分配的属性方面定义管理策略。
[0052] 图9是图示用于访问对象的过程的一个实施例的流程图。在所示例子中，例如从 客户端计算机接收如下请求，该请求针对访问在请求中命名的内容对象（902)。如上文描 述的那样，根据名称确定对象特征，并且例如基于访问概率、成本信息和管理策略确定预期 请求的对象可能存储于其上的一个或者多个节点的集合（904)。在一些实施例中，为了选 择将从其尝试访问请求的对象的节点，处理访问请求的节点基于访问统计、成本信息和管 理策略确定节点如果被请求这样做则将在何处存储对象。在一些替代实施例中，访问概率 信息用来选择将其上存储对象的节点，但是存储的对象计数和根据这些计数导出的概率信 息用来选择将从其尝试访问请求的对象的节点。在一些实施例中，在使用访问（或者存储对 象）概率和其他信息确定将从其尝试取回请求的对象的节点之前，检查本地索引以确定是 否本地存储对象，并且如果是这样，则从本地存储供应对象并且图9的过程未完成。一旦已 经选择将从其尝试取回请求的对象的节点，就从该节点尝试取回请求的对象（908)。如果 尝试成功（910)(即所选节点具有对象的副本并且提供对对象的访问），则该过程结束。如 果不是，则确定是否任何更多候选节点留待检查（912)。如果是这样，则选择下一候选节点 (914,906)并且尝试从该节点取回对象（908)。如果可用于检查的最后节点没有对象的副本 (912)，则返回如下异常（916)，该异常指示预计具有对象的节点事实上无副本并且图9的 过程结束。在一些实施例中，异常（916)造成检查全局异常索引以查看对象是否已经存储 于在索引中标识的位置/节点中。如果是这样，则从在索引中指示的节点取回对象。如果 不能发现副本，则向请求客户端反回如下错误，该错误指示对象未存在于分布式存储中。
[0053] 在以下例子中： ?J是如结合图3的308在[0040]中描述的访问概率矩阵。
[0054] ?Z是在如上文结合图3的309描述的[0041]中计算的每行的p值矢量。
[0055]?提来自上文结合图3的305描述的[0039]的访问简档矩阵中的所有单元的标 量和除以来自[0039]的访问数量。
[0056] 在一些实施例中，访问计数矩阵具有每个特征的一行和每个访问位置的一列。在 五十次访问之后的用于六个特征和四个位置的例子矩阵是：
利用这一矩阵，发现的共享状态值是：
在这一例子中，第三特征与底层访问群体的差异具有纯粹偶然出现的高概率。所有其 他特征具有高程度显著性，这意味着它们的差异不可能已经纯粹随机出现。
[0057] -旦已经针对对象确定特征集合，就有可能接近对应访问概率。系统在从给定节 点或者位置访问对象的先验概率将与该节点或者位置在全部访问中的份额对应的假设之 下操作。假设对象访问将以某些基本频率发生，每个位置在全部访问中的份额然后与它的 相对始发访问频率对应。又通过将每个特征简单地视为对位置概率的独立观测根据贝叶斯 定理更新这些概率。即使在特征之间的依赖性可能存在，但是如果依赖性在类中均匀分布 或者如果依赖性相互抵消，则这一方法仍然将是最优的。
[0058] 针对每个新的分布值集合，将列和的矢量(代表与每个节点对应的特征访问频率） 计算为：
将行和的矢量(代表与每个特征对应的特征访问频率）计算为：
针对每次尝试发现或者存储对象，初始化预计分布等于全局分布：
针对在给定对象ID中标识的每个特征，执行贝叶斯规则的迭代：
为了计算贝叶斯规则的每次迭代，以下等式用来发现概率(针对每个对象访问将递增 多个特征计数的事实调整)。
[0059] 在贝叶斯规则的每次迭代之后，系统具有先验分布、后验分布和与先前评估的特 征关联的P值。除了采用后验分布作为用于下一次迭代的先验分布之外，系统可以代之以 接受通过使用P值确定的中间值。一种选择中间值的方式是将加权平均值与P值（向先验 分布给予的权重）和1-P值（向后验分布给予的权重）一起使用。由于系统可以关于具有很 少收集数据的特征或者存在于几乎每个对象中的特征做出决定，所以希望防止这些特征的 概率过量影响预测概率分布。通过按照特征的P值对概率改变加权来防止这一过量影响。 在一些实施例中，针对非布尔特征，诸如通过将置信水平与（1-P值)的乘积用于后验分布的 权重并且将1-(后验权重）用于先验分布的权重来在这些计算中包括置信水平。
[0060] 由于统计按照特征提供访问频率和对象群体，所以有可能检测具有不成比例高的 访问率的特征。具有这些特征的对象更可能是证实附加复制合理的热内容。在各种实施例 中，当存储对象时，可以针对在层级中的各种级别处的位置或者其组合的绝对访问频率检 查对象。针对具有比某些阈值量大的绝对访问频率的任何位置以及未禁止存储于该位置的 管理策略，可以精细将附加副本放置于该位置的尝试。类似地，如果任何位置在初始对象存 储之后观测它对某些对象的访问频率超过某些阈值，则附加副本可以存储于该位置以减少 访问成本。因此，系统可以关于对象的额外副本的抢先分布做出决定。可以通过允许取回 对象的任何节点存储本地副本持续有限时间段来获得相似性质。有限时间段确保以后可以 删除对象而无高速缓存的副本拖延。这一高速缓存逻辑可以使用最近最少使用驱逐策略或 者在内容分发网络或者web高速缓存方案中使用的任何其他方法。使用高速缓存供应热内 容造成对文件的反应性而不是前摄（proactive)复制。然而高速缓存倾向于更立即有用的 对象放置。
[0061] 例子。存储具有特征2、3和5的对象而未针对显著性调整，系统首先发现针对对 象访问位置的先验预计。使用来自上例的A值，系统计算C= #l:。
[0063] 针对第一位置，系统计算：
针对每个位置发生计算。在更新所有位置之后(保留更多精度）有新的预计分布
系统针对存在于对象中的其他特征重复这些步骤以提炼预计访问分布。在处理所有三 个特征之后，将最终分布计算为：
所得节点概率与访问率(针对这一对象预测的每个时间段的相对访问数量）有效地对 应。尽管知道相对访问率是有用的，但是它未标识对象的最经济高效放置。当集成预测访 问率与网络成本时，以下系统使用于各种实施例中。
[0064] 在一些实施例中，实验确定并且通过分布式合意偶尔修整成本。考虑资源和辅助 成本(诸如访问延时)。这些成本度量组合实际预算外（outofpocket)成本(例如每吉比 特网络传送成本$1)和间接成本(例如用户等待时间或者带宽争用)两者。甚至对于本地访 问，仍然有基本成本(诸如使用盘I/O通道的机会成本)。
[0065] 成本矩阵的一种解释是每行代表潜在存储位置并且每列代表潜在资源访问位置。 矩阵的单元然后保持每个访问单位的成本度量。基本成本沿着成本矩阵的对角线出现并且 根据与访问关联的本地机器和LAN开支来确定。这一基本成本随着WAN传送成本相关度减 少而增加。
[0066] 将成本矩阵表示为，其中每个元素是从源位置j访问在位置i存储的对象的成 本。将对象特定概率矢量称为&.，其中每个元素是从位置i方问对象的概率。注意概率矢 量/^一些实施例中无需求和为1;相对概率是重要性质。如果对象存储于位置i，则矩阵 乘积給出的矢量5；.给出每次访问的预计平均成本。
[0067] 对于洛杉矶、纽约、伦敦和东京这些位置，例子成本矩阵如下：
使用来自上例的矢量乃
在各种实施例中，在选择任何位置用于存储数据之前查询管理策略。管理策略的所有 方面可以是全局的或者代之以按照对象标识符变化。如果策略禁止存储位置，则去除成本 矩阵中的对应行和列。在这一情况下也去除位置概率矢量中的对应条目。策略可以指定其 他调整(诸如增加与位置关联的概率或者亲和性（affinity))。管理策略也可以指定系统必 须在选择位置和节点时满足的存储冗余要求。在进行所有必需调整并且确定与预计访问简 档关联的成本之后，选择存储位置(如下文描述的那样)。从与在管理策略中指定的冗余要 求一致的所选位置选择节点集合。如果需要更多存储位置，则系统将调整用于下一迭代的 成本矩阵和概率数量、执行新的矩阵乘法并且选择下一存储位置。每当选择存储位置时，管 理策略可以取消其他潜在存储位置的资格。例如，当在两个地理位置中需要三个副本的对 象已经两次存储于相同地理位置时，可以取消相同地理位置中的所有其他潜在存储选择的 资格，以便防止做出如下存储位置集合的选择，这些存储位置集合的选择超过冗余策略所 需冗余量。这一位置和节点选择过程重复直至满足管理策略。可以在所有节点之间复制或 者在可靠全局数据结构(诸如跳图（Skipgraph))中存储管理策略。
[0068] 在描述在各种实施例中存储节点的选择的以下例子中使用以下术语： ?尾是节点的偏置。该偏置为非零并且为正。矢量i?中的所有偏置之和是尽^
[0069] ?尽(〇)是与节点对应的散列函数关联的对象〇的散列。所有散列均匀分布于 相同范围0彡尽(〇)彡尽"中。
[0070] ? 是最大可能散列值。
[0071] ? | |別|表示矢量屈勺矢量范数。
[0072] 在纯粹针对最低访问成本而优化的系统中，对象将总是存储于最低成本的位置。 亲和性是对可以向每个可能存储位置分配的相对有利条件的测量。确切亲和性不相干；仅 它们的相对值有意义。在每个存储位置的成本矢量货合定时，可以通过将每个成本值替换 为它的倒数并且然后将每个值除以所有值之和来完成向分类（categorical)概率分布的转 换。这一将亲和性转换成概率的方式向最低成本的选择分配最多数据而又仍然选择一些更 高成本的位置。因而，当本地化网络故障出现时，多个对象的复制品将存在于网络的更远和 不受影响的区域中。这些复制品针对网络的出故障的部分减少客户端访问具有高亲和性的 数据失败的影响。
[0073] 在位置选择已经发生之后，可以通过将每个节点的亲和性除以在子位置(诸如节 点或者盘）的所有亲和性之和来针对该子位置形成分类概率分布。节点亲和性可以与节点 资源、管理优先或者任何其他一致测量成比例。替代地，可以通过将每个节点亲和性乘以它 的位置的亲和性并且取所得集 合的并集来全局确定节点分类概率分布。这一方式具有更高 算法成本并且可能在退化情况下造成伪（spurious)数据迀移。在一些实施例中，原先可以 针对位置层级的最低级(诸如具体盘）计算亲和性，并且因此避免贯穿子位置的任何迭代。
[0074] 尽管统计方法可以指示一些对象针对一个特定位置具有极端亲和性，但是对于负 载平衡和容错而言希望避免过于强烈的偏置。任何这样的调整不应改变按照优先的位置排 序并且应当总是引向均匀分布。对于引向均匀分布的强度而言希望随着偏置的强度增加。 具有这些性质的一种系统如下： (1)系统将d维概率矢量释为（tM)单形（simplex)中的点。
[0075] (2)(心1)单形的质心是
。这也代表均匀概率分布。
[0076] (3)将优先矢量计算为7? =G矢量球和为0,因而将不由添加的任何倍 数而违反M和为1这一重要性质。如果施]所有项是〇 (也就是说产=0,则未完成缩 放。系统取产=饼且计算完成。
[0077] (4)发现最大k，使得M+汉E所有非负概率的可行区域中。这可以通过发现最 小A使得
来完成。然后
[0078] (5)在k给定时计算最大不公平（unfair)矢量
[0079] (6)在缩放函数0U)(该函数根据不公平度比提供标量系数)给定时，计算最终调 整的概率矢量：
缩放函数Q(x)应当具有域和范围[0，1]。对于低输入，所需输出在1附近，因为很少 鼓励忽略弱偏置。当输入在1附近时，输出根据存在于集群中的节点总数应当更小。在 (对于n个位置的集群）附近的最大输出提供在性能和可靠性的冲突需要之间的恰当平衡。 由于对于更低输入而言希望保持与它们的原始值接近，所以缩放函数应当非线性。一个具 有这些性质的缩放函数是
这一要求然后迫使
[0080] 在来自[0061]的例子中（见[0058]以及下文等等)，如果文件存储于洛杉矶、纽 约、伦敦或者东京的设施之一终，则发现如下亲和性矢量，该矢量指示每次访问的平均成 本：
通过取矢量中的每个元素的倒数并且然后将所得元素除以所有结果之和来发现所得 概率矢量，使得矢量现在求和为1 :
然后调整矢量以求更佳分布：
由于伦敦位置具有最高概率，所以假设已经随机选择它。如果伦敦位置包含三个节点 (应当^的时间选择其中之一并且应当i的时间选择每个其他节点)，则形成用于这些节点的 新概率矢量：
这一过程针对如存在于策略中那样多的层级级别而继续。尽管由设施和节点构成的两 级策略便于说明，但是这一过程可以应用于任意深度的层级。在一个实施例中，存储系统的 管理员定义层级的任意数量的上级，而层级的最低级由盘占用。在另一实施例中，可以在所 有底级存储位置内做出单级概率选择。后一个实施例可以引起对象中的更少翻动（churn) 并且更好地保留底层散列函数的单调性质，而前一个实施例可能对大量存储位置和复杂存 储策略规则更高效。
[0081] 在对象的高速缓存副本与对象的负责副本之间区分是有用的。负责副本在对象改 变时参与合意协议并且认识到高速缓存副本。这创建用于每个对象的在对象修改和删除时 密切涉及到的节点的小群体。对于负责副本数量而言希望为小从而在每次修改中不涉及到 过多数量的节点，但是大到足以使得故障不可能使对象不可用。对象的最长寿命副本是负 责副本，而高速缓存副本用于短暂（ephemeral)存储。关于合意协议的文献经常讨论提议 者、接受者和学习者的角色。在该框架内，负责副本扮演接受者和学习者的角色，而高速缓 存副本可以仅参与学习者的角色以维持高速缓存的新鲜度。在一些实施例中，所有节点可 以作为提议者来参与。在其他实施例中，用于合意目的的提议者角色限于保持负责副本的 节点集合。
[0082] 一致地预测对象将存储于何处消除了对保持全局对象索引的需要。然而不可 预测的情形(诸如资源耗尽或者故障）可能需要在如下节点的存储选择，该节点并非优先 列表中的绝对第一。在这一情况下，对于搜索网络的客户端而言希望具有如下一致回退 (fallback)策略，该回退策略允许它们发现在更少优选的位置存储的几个对象。也将希望 客户端快速和决定性地能够确定对象标识符未存在于系统中的任何地方。对象的每个副本 将具有如下元数据，该元数据标识当前负责对象副本和引用的其他节点。这一元数据对于 快速标识资源的附近副本而言以及对于知心可靠删除操作而言均有用。当怀疑节点已经出 故障时，所有其他节点可以快速搜索它们的本地元数据索引以标识不再满足它们的最少复 制策略的对象。当资源可用时，当前负责对象的节点分发高速缓存副本，并且然后与负责节 点关于高速缓存副本已经变成负责副本达成协定。相似过程出现于放置统计的改变引起用 于某些对象集合的节点优先改变时。系统限制对象迀移使得网络拓扑改变未引起削弱重新 定位水平。
[0083] 图10A是图示用于从分布式内容存储删除对象的过程的一个实施例的流程图。在 所示例子中，接收对删除对象的请求（1002)。例如以与图9中相同的方式发现对象的实例 (1004)。读取并且使用如与对象一起存储于发现实例的节点的与对象关联的元数据对对象 的所有"负责"（与高速缓存的相对）副本（1006)定位，也就是为了满足关于(一个或多个） 存储位置、冗余程度等的管理策略而存储的副本。删除所有负责副本（1008)。在各种实施 例中，例如一旦确定高速缓存对象副本不再与如存储于任何节点中的有效负责副本对应， 就通过正常高速缓存操作清除任何高速缓存副本(如果有的话)。
[0084] 图10B是图示用于可靠删除对象的负责副本的过程的一个实施例的流程图。在一 些实施例中，图10B的过程实现图10A的步骤1008。为了在网络分区的情况下安全删除文 件，在一些实施例中，文件删除请求经过若干阶段继续。在第一阶段中，节点可以擦除对象 的内容、但是必须保留如下元数据，该元数据指示文件与关于删除过程的当前阶段的信息 一起删除（1022)。在一些实施例中，可以使用分布式合意协议来维持删除过程的状态。在 一些实施例中，这一保持的元数据可以跟踪哪些其他节点已经确认将文件标记为删除。替 代地，节点可以针对其他负责节点的删除状态定期查询它们以标识其中所有参与者已经进 入至少第一删除阶段的任何文件。一旦已知所有负责副本已经开始删除过程，第二删除阶 段就可以开始（1024)。在一些实施例中，节点可以选择向所有负责对等节点通知第二阶段 已经开始。在第二阶段中，可以去除用于文件的元数据（1026)。
[0085] 图11是图示用于在分布式内容存储中保存改变的过程的一个实施例的流程图。 在所示例子中，接收用于保存对对象的改变的指示（1102)。更新对象的本地负责副本以反 映改变（1104)。指示其他负责副本的位置的本地存储的元数据用来向其他负责副本传播改 变（1106)。在一些实施例中，一旦接收已经更新所有负责副本以反映待保存的改变的确认， 就向请求客户端/应用通知已经完成保存。如果由于合意协议的失败或者拒绝而在成功完 成之前放弃改变，则还原改变（1108)。替代地，在一些实施例中，不应用改变直至被所有负 责节点接受之后。例如通过正常高速缓存管理处理清除对象的被取代版本的高速缓存副本 (1110)。
[0086] 图12是图示用于对存储于分布式内容存储中的对象进行改变的过程的一个实施 例的流程图。在所示例子中，获得对内容对象的所有权"锁定"（1202)。该锁定向其他节点 通知必须通过保持锁定的节点协调对对象的改变。在各种实施例中，这使节点能够在一段 时间内进行相继改变而不必与存储对象的负责副本的其他节点协调。获得锁定的节点协调 在/由其他节点进行的改变(包括通过仲裁或者否则解决任何冲突)并且对如本地存储的对 象实现在任何节点承诺的改变（1204)。一旦节点完成更新对象（1206)，它就向存储对象的 负责副本的其他节点传播在保持锁定的时间期间在/由任何节点进行的累积改变并且释 放锁定（1208)。
[0087]在各种实施例中，节点通过在包含该对象的负责副本的节点集合内向分布式合意 协议提供改变表示来发起对内容对象的改变。向所有负责节点提供这些改变的表示。分布 式合意协议可以提供用于应用改变的全部或者部分排序。这可以减少为了跨越对象的所有 副本进行改变而需要的网络业务量并且允许在修改内容对象时增加的并行量。
[0088] 在各种实施例中，例如如果例如由于一个或者多个节点不可用等而不能确定用来 以满足所有适用管理策略的方式存储对象的节点的指定数量和混合和/或应当已经造成 成功取回请求的对象的多个访问尝试都已经失败，则异常策略确定如何存储对象和/或从 何处尝试访问它。
[0089] 在任何M中的N异常策略之下，向客户端确保在优先列表中的前M个节点之中，它 们中的至少N个节点将包含对象的副本或者至少包含对可以发现副本的位置的引用。这要 求客户端在回退到全局异常索引之前联络至少#-#+ 1个节点。仅在联络至少，价1个 节点并且检查全局异常索引之后，客户端才可以决定性地认为对象不存在。仍然应当与优 先列表的开始尽可能接近地存储对象以减少为了发现对象而必需的总网络往返。在#=1 特殊情况下，任何M中的1异常策略要求客户端在检查异常列表之前联络所有M个节点。
[0090]在前N个异常策略之下，客户端具有前N个节点必须都具有对象副本或者引用的 更强确保。在前N个节点中的任何节点的故障情况下，客户端将回退到优先列表中的后续 节点。如果所有N个节点不可用，则客户端将引用异常列表。如果任何节点可用并且没有 请求的对象的副本，则客户端将回到检查异常列表。尽管这与任何M中的N策略相比减少 了对异常或者不存在的文件定位而需要的网络往返数量，但是它也增加存储全局异常列表 而必需的存储数量，在#= 1的特殊情况下，优先列表直接用作选择功能。如果对象未存储 于优先列表中的第一节点上，则必须在全局异常索引中列举它。
[0091]图13是图示用于存储对象的过程的一个实施例的流程图。在所示例子中，接收对 存储对象的请求（1302)。例如基于如上所述的访问概率、成本和/或管理策略确定将在其 存储对象的一个或者多个优选节点（1304)。尝试在优选节点存储对象（1306)。确定是否已 经满足适用异常策略（1308)(例如对象是否成功存储于M个优选节点中的至少任何N个节 点中）。如果满足异常策略(即无异常）（1310)，则该过程结束。如果未满足异常策略，则选 择并且使用一个或者多个替代位置(未优选）用于存储对象（1312)并且更新全局异常索引 以反映（附加 ）副本存储于何处（1314)。
[0092]图14A是图示用于访问对象的过程的一个实施例的流程图。在所示例子中，接收 对访问对象的请求（1402)。如上文描述的那样，例如基于对象特征、访问概率等确定将从其 尝试取回对象的节点（1404)。如果成功取回对象（1406)，则该过程结束。如果不是，则确 定目前为止未成功检查的(一个或多个)节点的数量和/或混合是否指示应当执行异常处置 (1408)。例如如果任何M中的N异常策略应用并且已经未成功检查确定的优选M个节点之 中的N个节点，则将确定未满足异常策略。如果（尚）无异常（1408)，则检查下一预测节点 (1410)并且检查相继节点直至取回对象或者确定异常（1410,1406,1408)。如果异常出现 (1408)，则在全局异常索引中查找对象（1412)。如果发现条目（1414)，则从指示的节点取 回对象并且该过程结束。否则，返回指示对象不存在的错误（1416)。
[0093]异常编索引从搜索和存储成本的观点来看应当是高效的。用来预测存储位置的统 计表可以被约束成慢漂移，因而预测存储位置的改变未触发对异常列表的大量或者频繁改 变。一种用于提供这一约束的方式是使所有统计数据穿过低通滤波器。由于全局异常索引 无论对象何时存储于未与异常策略相配的位置都必须增长，所以希望也随时间缩减异常列 表，使得系统可以减少对频繁异常索引查找的需要。如果每个对象在异常列表中的条目以 代表对象的优选节点的标识符为前缀，则可以容易形成将倾向于在对象的优选存储节点上 存储异常的跳图。这允许优选节点将客户端迅速重定向至有效副本并且提供可以本地复制 并且从全局异常列表去除的对象的容易工作列表。在一些实现中，优选节点可以保持如下 元数据而未保持对象的内容，该元数据具有其中当前可以发现对象的存储位置的列表。这 允许在搜索者已知需要回退到异常列表之前快速发现当前负责副本。
[0094]全局异常索引可以存储于任何分布式拓扑(诸如跳图或者LH*数据结构)中而向节 点直接分配桶（bucket)。必需的是分布式数据结构适度处置在网络拓扑中添加新位置或者 其他改变。然而存储它，分布式数据结构本身提供异常在节点之间的分割。每个节点可以 使用它的空余资源标识用于解决它负责的异常的方式。当网络资源可用时，可以进行针对 出现重新定位并且减少异常索引的大小的请求。
[0095] 优选节点也可以通过回应针对它们没有的对象的请求来减少异常列表大小。如 果前1个异常策略就位，则第一节点可以在它接收针对对象的请求的任何时间选择检查异 常索引本身。如果对象存在于异常索引中并且主要节点具有可用的空间，则它可以立即高 速缓存对象的副本并且也可以加入负责节点的列表。一旦优选节点具有对象的副本，则异 常索引空间可以与用于更少优选的副本的存储空间一起释放。当执行第一请求时，节点可 以本地存储对象的高速缓存版本。后续请求可以使节点针对对象发生的改变注册为学习 者。节点也可以将它的副本注册为对象中的全责参与者，因此允许从异常列表去除它。在 一些实施例中，可以通过用于更新对象内容的相同合意协议进行对对象元数据的修改。无 论是学习者还是负责的，所有参与者可以与它们参与的(一个或多个）角色一起列举于元数 据中。在各种实施例中，对元数据的这些修改可以是立即的或者可以延迟它们的激活直至 由某些以后事件(诸如检查点提议或者定时器过期)触发。用某些初始负责成员列表创建对 象，并且在该点之后的每个改变是在提议改变时在负责成员全体之间的合意结果。
[0096] 保证文件创建是原子性的要求分布式系统中的特殊考虑。由于对象可能存储于并 非优选位置的存储位置，所以某些次级原子目录是必需的。一种保证创建是原子性的方法 是通过具有全局共享对象目录并且执行原子承诺协议以修改现有对象的目录。另一方法是 保证异常列表存储于如下数据结构(诸如跳图）中，该数据结构允许原子插入操作在分布式 系统中的平凡实现。在一些实施例中，可以混合两种方法。例如可以在通过合意操作维持 的全局目录中列举所有节点或者所有节点的大部分负责的对象，而存储于更小节点子集上 的对象可以依赖于全局异常索引的原子性质。保证向节点群体的窄子集分配给定分区内的 数据的分布式数据结构(诸如跳图）可以通过要求在相邻节点之间的通信改变分割边界来 维持一致性。在相邻节点不可用的情况下，复原动作(诸如改良图形而省略出故障的节点） 需要一种避免分割问题的原子承诺协议。
[0097] 图14B是图示用于在分布式内容存储系统中创建对象的过程的一个实施例的流 程图。当创建新对象并且依赖于全局异常索引的原子插入性质时，创建节点首先针对待创 建的对象搜索全局异常索引（1442)。在一些实施例中，节点可以实际上首先使用优先列表 来搜寻对象并且然后仅在它已经确认对象未存储于优选位置之后回退到搜索全局异常索 弓丨。如果在全局异常索引中发现对象（1444)，则返回如下结果，该结果如适用的那样指示 对象已经存在或者在创建的过程中（1446)。如果未在全局异常索引中发现对象（1444)， 则向全局异常索引中插入指示这一对象当前正在被创建的占位符（1448)。在占位符条目 在全局异常索引中之后，可以根据上文定义的优先列表和异常策略针对对象执行正常扫 描（1450)。如果在异常策略的约束内发现对象（1452)，则返回指示对象已经存在的结果 (1454)。如果未在异常策略的约束内发现对象（1452)，则创建节点可以将元数据和对象内 容的副本放置于优选节点集合上（1456)。
[0098] 在放置元数据和对象内容之后，创建节点可以去除全局异常索引占位符（1458)。 在一些实施例中，可以去除占位符作为如下正常后台过程的部分，该过程迀移全局异常索 引中的对象并且在可能时去除它们的异常条目。可以用时间和/或始发节点标记异常索引 中的占位符条目，使得它们可以由于超时或者节点故障而以后到期。
[0099]使用这些方法，当使用优先列表和异常策略针对对象执行搜索时，可以将文件分 类为存在、不存在、创建或者删除。如果文件存在，则发现有效当前元数据和内容。如果文 件不存在，则未发现元数据或者异常条目。如果创建文件，则在全局异常索引中发现指示创 建文件的占位符条目。如果删除文件，则发现标记为删除并且无对应内容的元数据条目。
[0100] 在一些实施例中，将大文件或者其他对象(诸如数据库）分割成更为可管理的大小 的单独可存储对象。每个分区如这里描述的那样冗余存储于分布式内容存储系统中。在各 种实施例中，可以基于数据库表中的密钥范围或者基于面向列的数据库中的列范围或者通 过其他手段(包括上述手段的组合）形成分区边界，从而将数据库中的数据划分成分区。基 于分区的特征选择在其上存储分区和/或从其尝试访问的节点。
[0101]图15是图示用于存储数据库或者其他大文件的过程的一个实施例的流程图。接 收对象或者其他大文件（1502)。将文件分割成更为可管理的大小的块（1504)。在各种实施 例中，基于文件特征或者其他特性和/或内容系统条件预先配置、可配置和/或动态确定分 区大小。每个分区存储于基于该分区的特征选择的节点上（1506)。在一些实施例中，对数 据库表的分区命名，使得将表名称、可以配置的任何分配表的所有者和主密钥的部分或者 其散列中的每个表示为唯一特征。这样的方案允许表的子集存储于如下位置，这些位置更 频繁地访问该子集中的记录。
[0102] 图16是图示用于访问和存储对象的过程的一个实施例的流程图。在所示例子中， 在每个节点处保持每个特征的访问计数（1602 )。例如如果访问具有特征2、3和5的对象，贝1J 递增针对三个特征中的每个特征的相应计数。在各种实施例中，计数随时间衰减以向更近 的访问给予更大权重。在各种实施例中，在关于一个或者多个特征检测到访问活动迅速改 变的任何节点处，例如通过减少原始访问计数和/或调整基于该计数确定的概率来抑制改 变率。在每个节点处，确定针对存储于节点上的对象的每个特征的计数（1604)。全局聚合并 且使用访问和存储对象计数以生成并且分发访问概率矩阵和存储对象概率矩阵（1606)。多 种方式可以用来在访问和存储矩阵中提供抑制。之所以需要抑制是因为否则太多对象可能 在访问模式改变之后不再处于它们的最优位置。在一个实施例中，矩阵在向节点分发之前 由低通滤波器(诸如无限冲激响应滤波器）抑制。在其他实施例中，可以通过随机采样对象 群体的部分并且统计上确定可能移动的对象数量来估计将以给定的新简档重新定位的对 象数量。在一个实施例中，这与抑制或者全局优化算法结合用来优化在朝着实际访问简档 的收敛与移动的对象数量之间的折衷。因而，可以控制在节点之间移动对象的速率和向全 局异常列表添加对象的速率，而系统使用的访问和存储概率将随时间接近实际概率。访问 概率矩阵针对每个节点并且关于每个节点针对特征集合中的每个特征指示具有该特征的 对象将在该节点被访问的可能性。存储对象概率矩阵针对每个节点并且关于每个节点针对 特征集合中的每个特征指示具有该特征的对象存储于该节点的可能性。在一些实施例中， 访问概率矩阵矩阵用来选择将在其存储对象的节点，并且存储对象概率矩阵用来选择将从 其访问对象的节点。
[0103] 在一些实施例中，提供具有一个或者多个如下槽的装置，每个槽都能够接收可拆 卸盘驱动器或者其他存储设备。盘或者其他驱动器可以插入于槽中。每个驱动配置有如下 数据，该数据可用来在该装置与之关联的集群中集成该驱动器作为节点。
[0104] 图17是图示存储装置的一个实施例的框图。在所示例子中，装置1702包括多个 槽1704、1706、1708和1710。每个槽能够接收可热交换盘驱动器(诸如盘1712和盘1714)。 每个盘预先配置有处理器1716在驱动器插入于槽1704、1706、1708和1710之一中时读取 的数据(例如配置文件)。处理器1716经由网络接口卡或者其他接口 1718和网络连接1720 来与集群中的其他节点通信以向它们通知已经添加新插入的盘。在一些实施例中，每个盘 包括节点。在一些实施例中，装置1702包括被配置成使用包括存储位置的盘存储内容对象 的节点。
[0105] 图18是图示存储盘的一个实施例的框图。在所示例子中，预先配置的热可交换 盘1712包括被配置成存储内容对象的对象存储1802、被配置成存储每个特征的访问对象 和存储对象计数以及访问和/或存储对象概率矩阵的访问和存储对象统计存储1804以及 可用来在存储于集群集成信息存储1806中的数据中标识的集群中集成盘(例如作为节点） 的配置文件或者其他集群集成信息存储1806。数据存储180 2、1804和1806经由内部总线 1808和底板通信接口 1810连接到装置底板1812,盘1712通过该装置底板连接到装置1702 中的其他盘和处理器1716。无论是内容或者统计或者集群集成信息的各种类型的所有对象 可以在单个文件系统内存储于盘上。在另一实施例中，统计和/或元数据可以存储于与内 容不同的存储设备或者节点上或者驻留于系统存储器内。
[0106] 尽管上文以一些细节描述各种实施例，但是其他方式也是可能的。简化方式可以 用于无需上文描述的完全解决方案的更小节点群体。替代地，可以代之以使用其他方法作 为用于系统的部分的扩充或者替换(包括多变元(multivariate)分析和卷积内核)。
[0107]在另一实施例中，选择存储位置的节点可以基于访问和/或存储统计向外部储存 器(诸如网络附着存储文件管理器或者存储区域网络）发起存储和/或访问请求。替代地， 节点可以基于确定的概率将外部对象请求引向适当设备。在各种实施例中，这些公开的统 计方法和选择策略与现有存储基础设施组合以提供分布式内容存储和取回。
[0108] 对于小节点群体，未存储异常索引可能更简单和更高效。当取回对象时，查询上 文描述的存储频率矩阵，并且使用贝叶斯规则来确定每个可能存储位置的概率。系统然后 向可能存储位置请求对象。在一个实施例中，以可能存储位置的相应概率为序进行对可能 存储位置的请求尝试。搜索可以在发现对象或者已经查询充分节点以确定对象不存在时终 止。例如如果对象需要三个复制品并且已经检验了除了两个潜在位置之外的所有潜在位 置，则系统可以返回对象不存在。
[0109] 多变元分析可以在特征或者位置的预测值重叠时允许维度压缩。两种有用的多 变元分析技术是主分量分析或者对应性分析。通过标识可以在未失去显著预测值时坍缩 (collapse)的特征或者位置来提炼先前描述的系统也可以有帮助。可以通过多变元分析技 术直接传递聚合访问和存储矩阵。如果输出用于来提炼，则可以将最相似特征和位置标识 为在所得空间中具有最接近的主坐标。如果输出纯粹用于对象放置和搜索，则每个潜在存 储节点必须由它自己的在与对象特征的主坐标相同的空间中的点代表。对象然后与通过组 合(诸如通过如下加权平均机制，该机制将用于每个特征的P值用作权重）它的特征的点来 发现的点对应。存储节点优先列表是按照与对象的点的距离的升序分类的存储节点列表。 约束统计输入中的漂移并且因此约束特征的所得主坐标中的漂移以减少对象重新定位率。 存储节点也可以在主坐标空间中慢速移动以改进优先列表选择。节点以如下方式在每次重 新计算统计期间略微移动，该方式倾向于将节点相互移开而又移动它们更接近最近的特征 和具有最大质量的特征。以这一方式，节点位置将随机接近主坐标空间上k均值集群算法 的结果，其中k是可用存储节点的数量。
[0110] 在多数情况下，完全代表与个位置关联的优先需要n-1个维度的空间。然而，在 位置优先不独立的程度上可以实现维度压缩(允许信息存储于更少维度中）。可以扰动或者 卷积这样的压缩多维空间以从优先或者访问率度量空间转换成成本度量空间。尽管这样的 方法可以诸如在拆分位置或者添加附加位置时关于网络拓扑的改变表达更多，但是复杂度 明显增加未证实在实践中使用它们是合理的。
[0111] 虽然为了理解清楚而已经以一些细节描述前述实施例，但是本发明并不限于提供 的细节。有诸多实现本发明的替代方式。公开的实施例为示例而非限制。
【主权项】
1. 一种存储数据的系统，包括： 处理器，其被配置为： 从分布式内容存储系统内的多个存储位置的每个存储位置收集对应的多个访问计数 数据，所述多个访问计数数据对应于多个特征中的相应的特征，其中对应于多个特征中的 相应的特征的多个访问计数数据中的一个表示在具有该特征的存储位置处存储的对象的 数量和在具有该特征的存储位置处访问的对象的数量中的至少一个； 至少部分地根据从每个存储位置收集的对应于多个特征中的相应特征的对应的多个 访问计数数据来确定概率数据，其中，所述概率数据包含这样的数据，其指示相对于每个特 征的每个存储位置而言，将从该存储位置访问具有该特征的对象的概率； 确定与内容对象相关联的特征集合，该内容对象关联于操作，其中，该特征集合包含与 该内容对象相关联的性质集合； 至少利用概率数据，至少为多个存储位置的子集的每个存储位置确定具有关联于该内 容对象的该特征集合中的特征的对象与该存储位置相关联的相应的期望可能性；以及 从多个存储位置中选择存储位置以完成相对于该内容对象而言的操作，该选择至少部 分地基于具有该特征的对象关联于被选择的存储位置的期望可能性；以及 存储器，其与处理器耦合并被配置为向处理器提供指令。2. 根据权利要求1所述的系统，其中所述操作包括在所选择的存储位置内存储内容 对象。3. 根据权利要求1所述的系统，其中所述操作包括尝试访问在所选择的存储位置处的 内容对象。4. 根据权利要求1所述的系统，其中所述操作包括从所选的存储位置尝试取回内容对 象而未首先基于索引或者其他数据确定内容对象事实上存储于所选择的存储位置内。5. 根据权利要求1所述的系统，其中具有特征的对象关联于所选择的存储位置的期望 可能性至少包括所选择的存储位置与未选择的另一位置相比与所述特征关联的相对程度。6. 根据权利要求1所述的系统，其中所选择的存储位置包括地理位置。7. 根据权利要求1所述的系统，其中所选择的存储位置包括节点。8. 根据权利要求1所述的系统，其中所选择的存储位置包括盘。9. 根据权利要求1所述的系统，其中所述特征集合包括关于内容对象为真的一个或者 多个声明。10. 根据权利要求1所述的系统，其中所述概率数据包含访问概率矩阵。11. 根据权利要求1所述的系统，其中所述概率数据包括概率矩阵，所述概率矩阵针对 所述分布式内容存储系统内的多个存储设备中的每个并且相对于每个特征的每个存储设 备而言，指示从包含该存储设备的存储位置处访问具有该特征的对象的频率。12. 根据权利要求1所述的系统，其中所述特征集合包括一个或者多个特征，并且还包 括使用所述概率数据针对所述集合中的每个特征确定多个候选存储位置中的每个位置与 该特征在统计上关联的程度，其中多个存储位置包含多个候选存储位置。13. 根据权利要求12所述的系统，所述处理器还被配置为关于每个候选存储位置确定 与选择在该候选存储位置内包含的节点以执行所述操相关联的预计成本。14. 根据权利要求13所述的系统，其中至少部分地基于确定为与选择相应候选存储位 置以执行所述操作关联的相应预计成本来选择所选择的存储位置。15. 根据权利要求1所述的系统，所述处理器还被配置为应用管理策略以根据具有特 征的对象与所选择的存储位置相关联的预期可能性以及与选择所选择的存储位置关联的 确定的成本来确定所选择的存储位置是合格的和需要选择的之一或两者。16. 根据权利要求1所述的系统，其中概率数据指示将从所选择的存储位置访问具有 特征的对象和选择所选择的存储位置来执行的操作将存储内容对象的预期频率。17. 根据权利要求1所述的系统，其中概率数据指示在所选择的存储位置处存储具有 特征的对象和选择所选择的存储位置来执行的操作将访问内容对象的预期频率。18. 根据权利要求1所述的系统，其中确定与内容对象相关联的特征集合包括： 评估与内容对象相关联的标识符以确定一个或多个特性；以及 从与关联于内容对象的标识符相关联的一个或多个特性获得特征集合。19. 一种存储数据的方法，包括： 从分布式内容存储系统内的多个存储位置的每个存储位置收集对应的多个访问计数 数据，所述多个访问计数数据对应于多个特征中的相应的特征，其中对应于多个特征中的 相应的特征的多个访问计数数据中的一个表示在具有该特征的存储位置处存储的对象的 数量和在具有该特征的存储位置处访问的对象的数量中的至少一个； 至少部分地根据从每个存储位置收集的对应于多个特征中的相应特征的对应的多个 访问计数数据来确定概率数据，其中，所述概率数据包含这样的数据，其指示相对于每个特 征的每个存储位置而言，将从该存储位置访问具有该特征的对象的概率； 确定与内容对象相关联的特征集合，该内容对象关联于操作，其中，该特征集合包含与 该内容对象相关联的性质集合； 至少利用概率数据，至少为多个存储位置的子集的每个存储位置确定具有关联于该内 容对象的该特征集合中的特征的对象与该存储位置相关联的相应的期望可能性；以及 从多个存储位置中选择存储位置以完成相对于该内容对象而言的操作，该选择至少部 分地基于具有该特征的对象关联于被选择的存储位置的期望可能性。20. 根据权利要求19所述的方法，其中所述操作包括从所选的存储位置尝试取回内 容对象而未首先基于索引或者其他数据确定内容对象事实上存储于所选择的存储位置内。21. 根据权利要求19所述的方法，其中所述特征集合包括一个或者多个特征，并且还 包括使用所述概率数据针对所述集合中的每个特征确定多个候选存储位置中的每个位置 与该特征在统计上关联的程度，其中多个存储位置包含多个候选存储位置。22. 根据权利要求21所述的方法，还包含关于每个候选存储位置确定与选择在该候选 存储位置内包含的节点以执行所述操相关联的预计成本。23. 根据权利要求22所述的方法，其中至少部分地基于确定为与选择相应候选存储位 置以执行所述操作关联的相应预计成本来选择所选择的存储位置。24. 根据权利要求19所述的方法，还包含应用管理策略以根据具有特征的对象与所选 择的存储位置相关联的预期可能性以及与选择所选择的存储位置关联的确定的成本来确 定所选择的存储位置是合格的和需要选择的之一或两者。
【专利摘要】公开了分布式内容存储和取回。确定与内容对象关联的特征集合。至少部分地基于概率数据从包括分布式内容存储系统的多个存储位置选择用于关于内容对象执行操作的存储位置，该概率数据指示选择的存储位置与包括特征集合的确定为与内容对象关联的特征在统计上关联的程度。
【IPC分类】G06F17/30, H04L29/08
【公开号】CN104899286
【申请号】CN201510303452
【发明人】R.F.罗斯, M.P.莱尔
【申请人】高通股份有限公司
【公开日】2015年9月9日
【申请日】2010年9月21日
【公告号】CN102640125A, CN102640125B, EP2480974A1, EP2480974A4, US8554993, US20110072206, US20140059290, WO2011034625A1
【专利说明】分布式内容存储和取回
[0001] 本申请为题为"分布式内容存储和取回"的中国专利201080041777. 2的分案申 请。
[0002] 其他申请的交叉引用 本申请要求于2009年9月21日提交的美国临时专利申请号61/277,206 (代理案号TRANP006+)、标题为DISTRIBUTEDCONTENTSTORAGEANDRETRIEVAL的优先权，出于所有目 的通过引用将其结合于此。
【背景技术】
[0003] 分布式数据存储系统的设计和实现由于确定数据在何处以及应当存储于何处的 问题而复杂。尽管已经存在将对象名称映射到存储位置的分布式编索引技术，但是它们需 要大量存储。这些技术未提供信息将存储于它将最终被访问的位置附近的保证。现有分布 式存储技术在故障出现时具有大量可用性和性能问题。
【附图说明】
[0004] 在下文详细描述和附图中公开本发明的各种实施例。
[0005]图1是图示分布式内容存储系统的一个实施例的框图。
[0006] 图2是图示用于访问和/或存储内容对象的过程的一个实施例的流程图。
[0007]图3是图示用于收集和分布访问统计的过程的一个实施例的流程图。
[0008] 图4是图示存储节点的一个实施例的框图。
[0009] 图5是图示用于在存储节点维持统计的过程的一个实施例的流程图。
[0010] 图6是图示对对象名称中的对象特征信息编码的过程的一个实施例的流程图。
[0011] 图7是图示用于存储对象的过程的一个实施例的流程图。
[0012] 图8是图示分布式内容存储系统的一个实施例的框图。
[0013] 图9是图示用于访问对象的过程的一个实施例的流程图。
[0014] 图10A是图示用于从分布式内容存储删除对象的过程的一个实施例的流程图。
[0015] 图10B是图示用于可靠地删除对象的负责副本的过程的一个实施例的流程图。
[0016] 图11是图示用于在分布式内容存储中保存改变的过程的一个实施例的流程图。
[0017] 图12是图示用于对存储于分布式内容存储中的对象进行改变的过程的一个实施 例的流程图。
[0018] 图13是图示用于存储对象的过程的一个实施例的流程图。
[0019] 图14A是图示用于访问对象的过程的一个实施例的流程图。
[0020] 图14B是图示用于在分布式内容存储系统中创建对象的过程的一个实施例的流 程图。
[0021]图15是图示用于存储数据库或者其他大文件的过程的一个实施例的流程图。
[0022] 图16是图示用于访问和存储对象的过程的一个实施例的流程图。
[0023] 图17是图示存储装置的一个实施例的框图。
[0024] 图18是图示存储盘的一个实施例的框图。
【具体实施方式】
[0025] 可以用诸多方式(包括如过程；装置；系统；物质组成；在计算机可读存储介质上 包含的计算机程序产品；和/或处理器(诸如如下处理器，该处理器被配置成执行在耦合到 处理器的存储器上存储的和/或该存储器提供的指令)）实现本发明。在本说明书中，这些 实现或者本发明可以采用的任何其他形式可以称为技术。一般而言，可以在本发明的范围 内变更公开的过程的步骤顺序。除非另有明示，描述为被配置成执行任务的部件(诸如处理 器或者存储器）可以实现为暂时被配置成在给定时间执行该任务的一般部件或者制造成执 行该任务的具体部件。如这里所用，术语'处理器'是指被配置成处理数据(诸如计算机程 序指令）的一个或者多个设备、电路和/或处理核。
[0026] 下文与图示本发明原理的附图一起提供对本发明一个或者多个实施例的详细描 述。结合这样的实施例描述本发明，但是本发明并不限于任何实施例。本发明的范围仅由 权利要求书限制，并且本发明涵盖诸多替代、修改和等效物。在下文描述中阐述诸多具体细 节以便提供对本发明的透彻理解。出于示例的目的而提供这些细节，并且无这些具体细节 中的一些或者所有细节仍然可以根据权利要求实现本发明。为求简洁，尚未详细描述在与 本发明有关的技术领域中已知的技术素材，使得未使本发明不必要地变得难以理解。
[0027] 公开用于分布式内容存储和取回的技术。使用多种分布式系统技术，公开的对象 存储跨越全局分散的网络冗余地散布信息。在各种实施例中，对象存储于它们最可能被使 用的位置附近，从而使系统可用性、对地理分散的资源的使用和最终用户性能最大化。系统 经由分布式合意（consensus)机制共享对象访问和存储简档。当尝试取回或者存储对象时， 针对特征扫描对象标识符。使特征相关以估计每个位置访问该对象的频率。针对每个潜在 存储位置，组合网络拓扑信息与这些估计以发现该存储选项的成本。确定性函数组合这一 成本数据与管理员配置的策略以确定数据应当存储于何处以及如何取回对象。函数被构造 成即使添加或者去除存储位置时仍然造成公平和最少对象重新分配。在一些实现中，管理 策略和索引信息存储于全局叠加网络中。该设计受控制系统理论严重影响，因为系统严重 受抑制并且表现对使用和拓扑改变的斜坡响应。
[0028] 如这里所用，术语"特征"是指对象标识符的性质。性质可以是布尔或者可以由在 〇与1之间的置信水平代表。任何对象标识符可以视为拥有特征集合。术语"访问概率矩 阵"是指如下矩阵，该矩阵包含从给定节点进行对具有给定特征的对象的任何给定访问的 概率，其中行代表对象特征而列代表请求位置。"访问计数矩阵"是指除了每个单元包含访 问计数而不是百分比之外具有与访问概率矩阵相同的结构的矩阵。"节点"是分布式系统中 的负责对象存储和对象查询的计算机或者其他设备两者。可以将节点和存储设备组织成层 级。该层级可以包含作为级别节点的存储设备和管理员指定的下级的分组。作为例子，可 以有称为"大陆"的层级级别，该级别包含北美洲、欧洲和亚洲，每个洲包含如下办公室，这 些办公室包含如下节点，这些节点包含存储设备。"位置"是层级中的任何给定实体(例如具 体办公室或者具体存储设备)。
[0029] 使用以下矩阵约定（convention): ?#表示矩阵A的转置 ? 4表示矩阵A的i行j列中的值 ?矩阵等式中的1表示1值填充的适当大小的行或者列lXn或者nXl矩阵。
[0030] ? (^表示矢量C的第j个元素 使用以下概率约定： ?汽剑功表示在给定势3真时J为真的概率。
[0031] ?A表示访问概率矩阵的行i代表的特征存在。
[0032] ? 示访问概率矩阵的列J代表的节点将执行访问。
[0033] ?巧表示除了访问概率矩阵的列J代表的节点之外的节点将执行访问。
[0034]图1是图不分布式内容存储系统的一个实施例的框图。在所不例子中，在所不例 子中由客户端102和104代表的一个或者多个客户端经由因特网(和/或一个或者多个其 他网络）106连接到多个存储节点108。每个节点108被配置成存储如下数据对象(诸如文 件)，这些数据对象包括存储的内容对象体。在各种实施例中，每个节点108本地收集统计， 例如针对一个或者多个特征中的每个特征，已经在节点访问（或者替代地为最近访问）具有 该特征的多少个对象和/或在节点上存储具有该特征的多少个对象。节点108经由分布式 合意机制协作以共享访问和/或存储统计。生成并且向节点分发全局访问概率矩阵，并且 在相应节点使用这些矩阵做出存储和/或对象访问决策。例如，可以在至少部分地由于对 象具有如下特征或者特征集合而选择的节点上存储等于对象的所有其他内容，该特征或者 特征集合造成在作出存储决策（即选择用于将对象存储于其上的一个或者多个节点）的节 点处使用用于相应节点的收集和分发的每个特征的访问概率来确定统计上可能将从所选 节点(或者从在所选节点附近的某处)访问待存储的对象。在各种实施例中，成本信息(诸如 经由在节点A(或者在节点A附近）向对象存储于其上的节点B进行的请求来访问对象的 成本)与访问和/或存储的对象统计一起考虑。在一些实施例中，也实施管理策略并且将这 些策略纳入到节点选择中。例如如果已经选择第一节点A用于存储对象并且管理策略要求 两个副本存储于分离的地理位置，则选择未在与节点A相同的地理位置的第二节点B用于 存储第二副本。
[0035] 图2是图示用于访问和/或存储内容对象的过程的一个实施例的流程图。在所示 例子中，当将存储对象或者希望访问对象时，先前收集的统计(例如每个节点的每个特征的 访问和/或存储对象计数，这些计数被转换成如下访问概率，这些访问概率针对每个节点 指示具有特定特征的对象在该节点处被存储和/或将被访问的可能性）和将存储的或者希 望访问的对象的特征用来针对每个候选节点确定将在该节点访问（和/或在一些实施例中 存储的）对象的概率（202)。确定的访问概率与成本、管理策略和/或其他信息一起用来选 择将在其存储和/或从其尝试访问对象的一个或者多个节点（204)。在一些实施例中，访问 统计用来选择将在其上存储待存储的对象的一个或者多个节点。在一些实施例中，存储的 对象统计用来选择如下一个或者多个节点，将从该节点请求访问待访问的对象。关于存储， 在各种实施例中的方式寻求在如下位置存储对象，这些位置使它们在受制于管理策略的要 求时以最小成本使如下用户的可用性最大，这些用户被确定为统计上最可能访问它们。类 似地，在各种实施例，关于在公开的方式之下的访问，请求者尝试从至少部分地基于共享的 访问和/或存储对象统计以及根据这些统计确定的概率来确定的如下节点取回内容，该节 点可能让对象存储于其上，例如因为存储节点可能将基于相同（或者有关）统计已经选择它 用于存储节点。
[0036] 在各种实施例中，在系统内的每个节点保持每个特征的对包含该特征的对象的访 问在该节点被发起多少次的计数。可以在节点处在分布式存储系统内出于各种原因（例如 代表在节点上运行的过程或者由于该节点接收的来自用户或者客户端计算系统的外部请 求）而发起访问或者其他操作。此外还维持从这一节点访问的对象数量的计数。类似地， 在一些实施例中，每个节点可以保持它的本地存储文件中的多少个文件具有给定特征和存 储的文件总数的计数。当已经预备并且准备好分发新访问和存储简档时，节点经由原子承 诺（commitment)协议关于新简档达成协定。这一协定包括简档本身和简档将变得活跃的 时间两者。通过自动改变为新简档，系统确保节点将总是将一致 信息用于存储和搜索决策。 延迟的激活时间也允许统计简档的多个版本为所有节点已知。这允许搜索、存储和异常列 表处置使用任何或者所有可用版本来做出决策。例如新存储决策可能使用尚未活跃但是不 久将变成活跃的简档。在一个实施例中，系统可以保留最后四个访问简档并且能够针对根 据那些简档存储的任何对象使用那些简档来对对象定位而不求助其他手段。在一个实施例 中，节点保证将在访问简档改变之后需要异常列表条目的所有它们的对象在访问简档改变 生效之前在异常列表中具有这样的条目。
[0037]系统定期聚集来自每个节点的特征访问模式。这可以由系统内的减少信息的单个 动作器、通过全局MapReduce步骤、通过交易协定机制或者通过其他手段来完成。
[0038]图3是图示用于收集和分发访问统计的过程的一个实施例的流程图。以下关键步 骤出现于各种实施例中： 从每个节点收集（302)存储文件和最近访问的每特征计数。可以组合这些计数以形成 每个位置和特征对的相应计数的频率矩阵。在一些实施例中，将访问简档信息存储为矩阵， 其中行对应于特征而列对应于从其出现访问的位置。存储简档将随时间接近访问简档，因 为基于访问简档选择存储位置。存储计数代表系统的实际状态而不是动态趋势，因此它们 在未过滤时最准确。每个节点确切知道如下值，这些值应当填充它的列。
[0039] 组合信息与先前访问简档（304)。经常希望向较新的信息给予较大权重。一种可 以实现此的方式是通过使用认为最近信息比历史数据更重要的低通滤波器(诸如无限冲激 响应滤波器)。替代地，全局优化技术(诸如仿真或者量子退火)也可以用来发现如下新访问 简档，该访问简档在接近最近观测的访问统计时使对象重新定位最小化。随机方法可以用 来确定将最小化的分数；替代地，可以使用如下函数，该函数基于提议的访问简档与最近观 测的访问率和按照特征对当前存储位置的计数有多么好地匹配来计分。这一过程通过比较 重新定位成本与节省的访问成本来区分简档改变的优先次序。从每个节点访问的对象的总 计数可以与整个集群执行的全部访问的数量之和一起由相同流程维持。随着过去观测的权 重减少，过去数据代表的对象访问的计数也按照相同比例减少。对于对计数数据的过滤而 言希望但是未必确保所有单元为非零。这防止贝叶斯推论将任何特征的存在解释为针对任 何位置的绝对的排除确保。
[0040] 计算访问计数矩阵中的所有单元的标量和除以矩阵代表的对象访问的总计数，从 而给出每个访问存在的对象特征的平均数量(即平均特征计数）（305)。
[0041] 通过将访问计数矩阵中的每个值除以矩阵中的所有单元之和以针对特征和节点 的每个配对产生访问概率来形成新访问概率矩阵（308)。换而言之，这一矩阵在每个条目 中存储访问的给定特征将来自与该条目的列对应的节点并且是与该条目的行对应的特征 的概率(受制于朝着滤波器提供的最近数据的偏斜)。这一概率对应于如下访问的预计比例 (该比例是访问频率)，这些访问将针对来自相应位置的具有这些特征的对象。
[0042]针对所得访问概率矩阵中的每个特征行，计算观测的统计显著性（309)。这是通过 首先发现跨越所有特征的访问计数之和代表的空假设分布并且然后计算如与全局访问概 率的空假设分布相比的用于行的P值来执行的。这帮助确定给定行是否是有用的访问位置 预测值（predictor)或者是否纯粹偶然地产生从基线分布的偏斜。这在存在关于特征的访 问模式的很少数据时特别有用。
[0043]向分布式存储系统中的各种节点分发访问概率矩阵、统计显著性矢量和标量平均 特征计数（310)。在其他实施例中，向各种节点分发计数，并且在分发之后节点执行概率计 算。在各种实施例中，也分发每个对象的平均特征数量或者对象总数。
[0044] 图4是图示存储节点的一个实施例的框图。在各种实施例中，存储节点402可以 包括服务器或者其他计算机。在所示例子中，节点402包括经由连接406提供网络连接性 的通信接口 404 (例如网络接口卡)。内容访问和存储引擎408经由通信接口 404和连接 406来与客户端和/或其他节点通信以执行任务(诸如提供对请求内容对象的访问以及例 如在节点402上和/或在对等节点上存储待存储的内容对象)。在一些实施例中，内容访问 和存储引擎408包括在处理器上运行的一个或者多个软件模块。在各种实施例中的内容访 问和存储引擎408被配置成在对象存储410中存储内容对象和/或提供对存储于其中的对 象的访问。在各种实施例中，节点可以具有多个本地"对象存储"（盘/存储位置)。内容访 问和存储引擎408在访问统计和矩阵412中维持和存储每个特征的针对本地访问和/或存 储对象的本地计数。内容访问和存储引擎408定期例如向所有对等节点和/或向一个或者 多个中心位置报告本地计数。在一些实施例中，MapReduce或者其他分布式技术用来收集 数据。在一些实施例中，在重新分发之前通过低通滤波器或者其他抑制（damping)机制变 换计数数据。合意机制可以用来保证所有访问和存储引擎共享共同简档。内容访问和存储 引擎408被配置成经由接口 404接收集中和/或在对等节点基于节点集群(节点402是该 集群的成员）中的相应节点报告的每个特征的计数来确定的访问概率和/或其他矩阵并且 使用矩阵关于特定对象基于它们的相应特征做出存储和/或访问决策。
[0045] 图5是图示用于在存储节点维持统计的过程的一个实施例的流程图。在所示例子 中，每次访问和/或存储对象（502)时，确定访问/存储的对象的特征（504)并且更新每个 特征的适用计数（506)。例如如果访问具有六个被跟踪特征的集合中的特征2、3和5的对 象，则将递增针对特征2、3和5的相应的每个特征访问计数。
[0046] 在一些实施例中，对对象特征编码或者对象特征包含在对象名称中或者通过直接 解释对象的名称可辨认对象特征。当系统尝试访问对象时，它评估关于对象名称的如下函 数，该函数解释对象名称的特性以生成特征集合。特性可以包括对象路径名分量的散列值、 字母和二合字母（digraph)频率测量、其他统计测量或者其任何组合。函数必须针对任何 给定对象名称返回确切相同特征集合。
[0047] 可以在每个节点的基础上维持每个特征的访问和存储计数。替代地，节点可以通 过针对该节点发起的尝试访问的每个特征递增每个盘上的访问计数来针对它的盘维持这 些计数。在该盘上的访问计数统计然后代表已经包含该盘的(一个或多个)节点已经针对包 含特征的对象发起访问的频率。类似地，节点可以在每个盘上维持存储于该盘上的对象计 数。在其他实施例中，可以在存储层级中的除了节点和盘之外的位置维持访问。
[0048] 图6是图示对对象名称中的对象特征信息编码的过程的一个实施例的流程图。在 所示例子中，当保存对象（602)时，例如基于包括对象的数据和/或关于对象的元数据确定 对象的被跟踪特征（604)。确定的特征用来创建(例如在首次保存对象时)或者更新(例如如 果特征从上次访问起已经改变）用来在分布式内容存储系统中知道对象的名称（606)。在 各种实施例中，每个特征由在对象名称中包括的串代表，使得在分布式存储中的任何节点 可以通过解释包括对象名称的数据来确定特征而不必检查全局或者其他索引条目。
[0049] 在一些实施例中，通过分析全局对象名称来确定对象特征。可以将对象名称形成 为层级，并且针对层级的每个部分计算的散列函数可以确定特征。此外，在名称中编码的层 级的名称或者级别还可以点缀有解析器可提取的各种附加属性。这些属性的散列可以提 供用于对象的特征。可以从对象名称提取各种其他隐含特征(诸如二合字母和三合字母频 率)。例如，最频繁三合字母可以视为对象的特征而其他三合字母则不是，或者关于每个三 合字母的频率计算的对数函数可以提供用于每个三合字母特征的置信水平。
[0050] 图7是图示用于存储对象的过程的一个实施例的流程图。在所示例子中，当接收 对存储对象的请求(例如来自客户端系统）（702)时，评估对象的名称以确定包括被跟踪的 特征的集合的哪个或者哪些特征(如果有）与对象关联（704)。针对作为(或者保留为）用于 存储对象的候选的每个节点，访问统计(例如集群范围的访问概率矩阵）用来根据对象的特 征确定待存储的对象将在该节点被访问的预计频率（706)。在一些实施例中，在确定每个节 点的概率之前和/或与之结合，如下文更完全描述的那样调整原始访问概率矩阵以实现存 储对象和/或其副本的更均匀分布。针对每个(保留)候选节点，如果对象存储于该节点，则 确定每个访问的平均成本(例如考虑如例如基于访问概率矩阵确定的在相应节点与可能从 其进行访问请求的可能节点之间的通信成本）（708)。根据适用管理策略评估预计访问频 率和成本信息以选择一个或者多个节点用于存储对象（710)。例如管理策略可以提供对象 的两个副本必须存储于不同地理位置。在一些实施例中，迭代执行706、708和710直至确 定满足适用管理策略的存储节点集合。例如管理策略可以提供对象的两个副本必须存储于 不同地理位置。可以基于访问概率和成本信息选择第一节点。从作为候选的竞争中去除第 一节点和为了服从适用管理策略而必须去除的任何其他节点。在当前例子中，可以从竞争 中例如去除在与第一节点相同的地理位置的其他节点和第一节点本身，并且如在保留节点 之间例如基于访问概率和成本信息确定第二节点（未必在与第一节点相同的地理位置，因 为已经从竞争中去除所有这样的节点)。在(一个或多个)所选节点上存储对象（712)。在一 些实施例中，除了存储对象的副本之外，每个所选节点还存储关于对象的元数据，包括如下 元数据，该元数据指示对象的"负责"副本被存储的其他位置。在一些实施例中，这样的信 息例如在存储位置的故障情况下用来向不受故障影响的节点迀移存储于出故障的位置内 存储的每个对象的副本以便恢复服从指定的冗余策略。在一些实施例中，这样的信息可以 在存储位置的故障情况下用来保证更新异常列表。可以对存储于每个节点上的元数据编索 弓丨，使得可以快速发现也在给定替代位置存储的条目。也可以对存储于每个节点上的元数 据编索引，使得可以快速发现具有给定特征的条目。在特征并非布尔的情况下，可以按照每 个特征内的置信水平对索引排序。
[0051] 图8是图示分布式内容存储系统的一个实施例的框图。在所示例子中，分布式内 容存储系统包括如下集群，该集群包括位于三个分离地理位置(例如企业或者其他实体的 三个地理地点）的三个存储节点集。与第一局域网（LAN) 804关联的节点802、与第二LAN 814关联的节点812和与第三LAN824关联的节 点822经由因特网830互连。在这一例子 中，如在上文结合图7描述的例子(其中管理策略要求第二副本存储于分离地理位置）中那 样，按照地理位置组织节点，从而使得能够在节点和/或地理基础上定义和实施管理策略。 也可以在管理员向在层级的任何级别的任何存储位置(包括但不限于盘、节点和地理位置） 分配的属性方面定义管理策略。
[0052] 图9是图示用于访问对象的过程的一个实施例的流程图。在所示例子中，例如从 客户端计算机接收如下请求，该请求针对访问在请求中命名的内容对象（902)。如上文描 述的那样，根据名称确定对象特征，并且例如基于访问概率、成本信息和管理策略确定预期 请求的对象可能存储于其上的一个或者多个节点的集合（904)。在一些实施例中，为了选 择将从其尝试访问请求的对象的节点，处理访问请求的节点基于访问统计、成本信息和管 理策略确定节点如果被请求这样做则将在何处存储对象。在一些替代实施例中，访问概率 信息用来选择将其上存储对象的节点，但是存储的对象计数和根据这些计数导出的概率信 息用来选择将从其尝试访问请求的对象的节点。在一些实施例中，在使用访问（或者存储对 象）概率和其他信息确定将从其尝试取回请求的对象的节点之前，检查本地索引以确定是 否本地存储对象，并且如果是这样，则从本地存储供应对象并且图9的过程未完成。一旦已 经选择将从其尝试取回请求的对象的节点，就从该节点尝试取回请求的对象（908)。如果 尝试成功（910)(即所选节点具有对象的副本并且提供对对象的访问），则该过程结束。如 果不是，则确定是否任何更多候选节点留待检查（912)。如果是这样，则选择下一候选节点 (914,906)并且尝试从该节点取回对象（908)。如果可用于检查的最后节点没有对象的副本 (912)，则返回如下异常（916)，该异常指示预计具有对象的节点事实上无副本并且图9的 过程结束。在一些实施例中，异常（916)造成检查全局异常索引以查看对象是否已经存储 于在索引中标识的位置/节点中。如果是这样，则从在索引中指示的节点取回对象。如果 不能发现副本，则向请求客户端反回如下错误，该错误指示对象未存在于分布式存储中。
[0053] 在以下例子中： ?J是如结合图3的308在[0040]中描述的访问概率矩阵。
[0054] ?Z是在如上文结合图3的309描述的[0041]中计算的每行的p值矢量。
[0055]?提来自上文结合图3的305描述的[0039]的访问简档矩阵中的所有单元的标 量和除以来自[0039]的访问数量。
[0056] 在一些实施例中，访问计数矩阵具有每个特征的一行和每个访问位置的一列。在 五十次访问之后的用于六个特征和四个位置的例子矩阵是：
利用这一矩阵，发现的共享状态值是：
在这一例子中，第三特征与底层访问群体的差异具有纯粹偶然出现的高概率。所有其 他特征具有高程度显著性，这意味着它们的差异不可能已经纯粹随机出现。
[0057] -旦已经针对对象确定特征集合，就有可能接近对应访问概率。系统在从给定节 点或者位置访问对象的先验概率将与该节点或者位置在全部访问中的份额对应的假设之 下操作。假设对象访问将以某些基本频率发生，每个位置在全部访问中的份额然后与它的 相对始发访问频率对应。又通过将每个特征简单地视为对位置概率的独立观测根据贝叶斯 定理更新这些概率。即使在特征之间的依赖性可能存在，但是如果依赖性在类中均匀分布 或者如果依赖性相互抵消，则这一方法仍然将是最优的。
[0058] 针对每个新的分布值集合，将列和的矢量(代表与每个节点对应的特征访问频率） 计算为：
将行和的矢量(代表与每个特征对应的特征访问频率）计算为：
针对每次尝试发现或者存储对象，初始化预计分布等于全局分布：
针对在给定对象ID中标识的每个特征，执行贝叶斯规则的迭代：
为了计算贝叶斯规则的每次迭代，以下等式用来发现概率(针对每个对象访问将递增 多个特征计数的事实调整)。
[0059] 在贝叶斯规则的每次迭代之后，系统具有先验分布、后验分布和与先前评估的特 征关联的P值。除了采用后验分布作为用于下一次迭代的先验分布之外，系统可以代之以 接受通过使用P值确定的中间值。一种选择中间值的方式是将加权平均值与P值（向先验 分布给予的权重）和1-P值（向后验分布给予的权重）一起使用。由于系统可以关于具有很 少收集数据的特征或者存在于几乎每个对象中的特征做出决定，所以希望防止这些特征的 概率过量影响预测概率分布。通过按照特征的P值对概率改变加权来防止这一过量影响。 在一些实施例中，针对非布尔特征，诸如通过将置信水平与（1-P值)的乘积用于后验分布的 权重并且将1-(后验权重）用于先验分布的权重来在这些计算中包括置信水平。
[0060] 由于统计按照特征提供访问频率和对象群体，所以有可能检测具有不成比例高的 访问率的特征。具有这些特征的对象更可能是证实附加复制合理的热内容。在各种实施例 中，当存储对象时，可以针对在层级中的各种级别处的位置或者其组合的绝对访问频率检 查对象。针对具有比某些阈值量大的绝对访问频率的任何位置以及未禁止存储于该位置的 管理策略，可以精细将附加副本放置于该位置的尝试。类似地，如果任何位置在初始对象存 储之后观测它对某些对象的访问频率超过某些阈值，则附加副本可以存储于该位置以减少 访问成本。因此，系统可以关于对象的额外副本的抢先分布做出决定。可以通过允许取回 对象的任何节点存储本地副本持续有限时间段来获得相似性质。有限时间段确保以后可以 删除对象而无高速缓存的副本拖延。这一高速缓存逻辑可以使用最近最少使用驱逐策略或 者在内容分发网络或者web高速缓存方案中使用的任何其他方法。使用高速缓存供应热内 容造成对文件的反应性而不是前摄（proactive)复制。然而高速缓存倾向于更立即有用的 对象放置。
[0061] 例子。存储具有特征2、3和5的对象而未针对显著性调整，系统首先发现针对对 象访问位置的先验预计。使用来自上例的A值，系统计算C= #l:。
[0063] 针对第一位置，系统计算：
针对每个位置发生计算。在更新所有位置之后(保留更多精度）有新的预计分布
系统针对存在于对象中的其他特征重复这些步骤以提炼预计访问分布。在处理所有三 个特征之后，将最终分布计算为：
所得节点概率与访问率(针对这一对象预测的每个时间段的相对访问数量）有效地对 应。尽管知道相对访问率是有用的，但是它未标识对象的最经济高效放置。当集成预测访 问率与网络成本时，以下系统使用于各种实施例中。
[0064] 在一些实施例中，实验确定并且通过分布式合意偶尔修整成本。考虑资源和辅助 成本(诸如访问延时)。这些成本度量组合实际预算外（outofpocket)成本(例如每吉比 特网络传送成本$1)和间接成本(例如用户等待时间或者带宽争用)两者。甚至对于本地访 问，仍然有基本成本(诸如使用盘I/O通道的机会成本)。
[0065] 成本矩阵的一种解释是每行代表潜在存储位置并且每列代表潜在资源访问位置。 矩阵的单元然后保持每个访问单位的成本度量。基本成本沿着成本矩阵的对角线出现并且 根据与访问关联的本地机器和LAN开支来确定。这一基本成本随着WAN传送成本相关度减 少而增加。
[0066] 将成本矩阵表示为，其中每个元素是从源位置j访问在位置i存储的对象的成 本。将对象特定概率矢量称为&.，其中每个元素是从位置i方问对象的概率。注意概率矢 量/^一些实施例中无需求和为1;相对概率是重要性质。如果对象存储于位置i，则矩阵 乘积給出的矢量5；.给出每次访问的预计平均成本。
[0067] 对于洛杉矶、纽约、伦敦和东京这些位置，例子成本矩阵如下：
使用来自上例的矢量乃
在各种实施例中，在选择任何位置用于存储数据之前查询管理策略。管理策略的所有 方面可以是全局的或者代之以按照对象标识符变化。如果策略禁止存储位置，则去除成本 矩阵中的对应行和列。在这一情况下也去除位置概率矢量中的对应条目。策略可以指定其 他调整(诸如增加与位置关联的概率或者亲和性（affinity))。管理策略也可以指定系统必 须在选择位置和节点时满足的存储冗余要求。在进行所有必需调整并且确定与预计访问简 档关联的成本之后，选择存储位置(如下文描述的那样)。从与在管理策略中指定的冗余要 求一致的所选位置选择节点集合。如果需要更多存储位置，则系统将调整用于下一迭代的 成本矩阵和概率数量、执行新的矩阵乘法并且选择下一存储位置。每当选择存储位置时，管 理策略可以取消其他潜在存储位置的资格。例如，当在两个地理位置中需要三个副本的对 象已经两次存储于相同地理位置时，可以取消相同地理位置中的所有其他潜在存储选择的 资格，以便防止做出如下存储位置集合的选择，这些存储位置集合的选择超过冗余策略所 需冗余量。这一位置和节点选择过程重复直至满足管理策略。可以在所有节点之间复制或 者在可靠全局数据结构(诸如跳图（Skipgraph))中存储管理策略。
[0068] 在描述在各种实施例中存储节点的选择的以下例子中使用以下术语： ?尾是节点的偏置。该偏置为非零并且为正。矢量i?中的所有偏置之和是尽^
[0069] ?尽(〇)是与节点对应的散列函数关联的对象〇的散列。所有散列均匀分布于 相同范围0彡尽(〇)彡尽"中。
[0070] ? 是最大可能散列值。
[0071] ? | |別|表示矢量屈勺矢量范数。
[0072] 在纯粹针对最低访问成本而优化的系统中，对象将总是存储于最低成本的位置。 亲和性是对可以向每个可能存储位置分配的相对有利条件的测量。确切亲和性不相干；仅 它们的相对值有意义。在每个存储位置的成本矢量货合定时，可以通过将每个成本值替换 为它的倒数并且然后将每个值除以所有值之和来完成向分类（categorical)概率分布的转 换。这一将亲和性转换成概率的方式向最低成本的选择分配最多数据而又仍然选择一些更 高成本的位置。因而，当本地化网络故障出现时，多个对象的复制品将存在于网络的更远和 不受影响的区域中。这些复制品针对网络的出故障的部分减少客户端访问具有高亲和性的 数据失败的影响。
[0073] 在位置选择已经发生之后，可以通过将每个节点的亲和性除以在子位置(诸如节 点或者盘）的所有亲和性之和来针对该子位置形成分类概率分布。节点亲和性可以与节点 资源、管理优先或者任何其他一致测量成比例。替代地，可以通过将每个节点亲和性乘以它 的位置的亲和性并且取所得集 合的并集来全局确定节点分类概率分布。这一方式具有更高 算法成本并且可能在退化情况下造成伪（spurious)数据迀移。在一些实施例中，原先可以 针对位置层级的最低级(诸如具体盘）计算亲和性，并且因此避免贯穿子位置的任何迭代。
[0074] 尽管统计方法可以指示一些对象针对一个特定位置具有极端亲和性，但是对于负 载平衡和容错而言希望避免过于强烈的偏置。任何这样的调整不应改变按照优先的位置排 序并且应当总是引向均匀分布。对于引向均匀分布的强度而言希望随着偏置的强度增加。 具有这些性质的一种系统如下： (1)系统将d维概率矢量释为（tM)单形（simplex)中的点。
[0075] (2)(心1)单形的质心是
。这也代表均匀概率分布。
[0076] (3)将优先矢量计算为7? =G矢量球和为0,因而将不由添加的任何倍 数而违反M和为1这一重要性质。如果施]所有项是〇 (也就是说产=0,则未完成缩 放。系统取产=饼且计算完成。
[0077] (4)发现最大k，使得M+汉E所有非负概率的可行区域中。这可以通过发现最 小A使得
来完成。然后
[0078] (5)在k给定时计算最大不公平（unfair)矢量
[0079] (6)在缩放函数0U)(该函数根据不公平度比提供标量系数)给定时，计算最终调 整的概率矢量：
缩放函数Q(x)应当具有域和范围[0，1]。对于低输入，所需输出在1附近，因为很少 鼓励忽略弱偏置。当输入在1附近时，输出根据存在于集群中的节点总数应当更小。在 (对于n个位置的集群）附近的最大输出提供在性能和可靠性的冲突需要之间的恰当平衡。 由于对于更低输入而言希望保持与它们的原始值接近，所以缩放函数应当非线性。一个具 有这些性质的缩放函数是
这一要求然后迫使
[0080] 在来自[0061]的例子中（见[0058]以及下文等等)，如果文件存储于洛杉矶、纽 约、伦敦或者东京的设施之一终，则发现如下亲和性矢量，该矢量指示每次访问的平均成 本：
通过取矢量中的每个元素的倒数并且然后将所得元素除以所有结果之和来发现所得 概率矢量，使得矢量现在求和为1 :
然后调整矢量以求更佳分布：
由于伦敦位置具有最高概率，所以假设已经随机选择它。如果伦敦位置包含三个节点 (应当^的时间选择其中之一并且应当i的时间选择每个其他节点)，则形成用于这些节点的 新概率矢量：
这一过程针对如存在于策略中那样多的层级级别而继续。尽管由设施和节点构成的两 级策略便于说明，但是这一过程可以应用于任意深度的层级。在一个实施例中，存储系统的 管理员定义层级的任意数量的上级，而层级的最低级由盘占用。在另一实施例中，可以在所 有底级存储位置内做出单级概率选择。后一个实施例可以引起对象中的更少翻动（churn) 并且更好地保留底层散列函数的单调性质，而前一个实施例可能对大量存储位置和复杂存 储策略规则更高效。
[0081] 在对象的高速缓存副本与对象的负责副本之间区分是有用的。负责副本在对象改 变时参与合意协议并且认识到高速缓存副本。这创建用于每个对象的在对象修改和删除时 密切涉及到的节点的小群体。对于负责副本数量而言希望为小从而在每次修改中不涉及到 过多数量的节点，但是大到足以使得故障不可能使对象不可用。对象的最长寿命副本是负 责副本，而高速缓存副本用于短暂（ephemeral)存储。关于合意协议的文献经常讨论提议 者、接受者和学习者的角色。在该框架内，负责副本扮演接受者和学习者的角色，而高速缓 存副本可以仅参与学习者的角色以维持高速缓存的新鲜度。在一些实施例中，所有节点可 以作为提议者来参与。在其他实施例中，用于合意目的的提议者角色限于保持负责副本的 节点集合。
[0082] 一致地预测对象将存储于何处消除了对保持全局对象索引的需要。然而不可 预测的情形(诸如资源耗尽或者故障）可能需要在如下节点的存储选择，该节点并非优先 列表中的绝对第一。在这一情况下，对于搜索网络的客户端而言希望具有如下一致回退 (fallback)策略，该回退策略允许它们发现在更少优选的位置存储的几个对象。也将希望 客户端快速和决定性地能够确定对象标识符未存在于系统中的任何地方。对象的每个副本 将具有如下元数据，该元数据标识当前负责对象副本和引用的其他节点。这一元数据对于 快速标识资源的附近副本而言以及对于知心可靠删除操作而言均有用。当怀疑节点已经出 故障时，所有其他节点可以快速搜索它们的本地元数据索引以标识不再满足它们的最少复 制策略的对象。当资源可用时，当前负责对象的节点分发高速缓存副本，并且然后与负责节 点关于高速缓存副本已经变成负责副本达成协定。相似过程出现于放置统计的改变引起用 于某些对象集合的节点优先改变时。系统限制对象迀移使得网络拓扑改变未引起削弱重新 定位水平。
[0083] 图10A是图示用于从分布式内容存储删除对象的过程的一个实施例的流程图。在 所示例子中，接收对删除对象的请求（1002)。例如以与图9中相同的方式发现对象的实例 (1004)。读取并且使用如与对象一起存储于发现实例的节点的与对象关联的元数据对对象 的所有"负责"（与高速缓存的相对）副本（1006)定位，也就是为了满足关于(一个或多个） 存储位置、冗余程度等的管理策略而存储的副本。删除所有负责副本（1008)。在各种实施 例中，例如一旦确定高速缓存对象副本不再与如存储于任何节点中的有效负责副本对应， 就通过正常高速缓存操作清除任何高速缓存副本(如果有的话)。
[0084] 图10B是图示用于可靠删除对象的负责副本的过程的一个实施例的流程图。在一 些实施例中，图10B的过程实现图10A的步骤1008。为了在网络分区的情况下安全删除文 件，在一些实施例中，文件删除请求经过若干阶段继续。在第一阶段中，节点可以擦除对象 的内容、但是必须保留如下元数据，该元数据指示文件与关于删除过程的当前阶段的信息 一起删除（1022)。在一些实施例中，可以使用分布式合意协议来维持删除过程的状态。在 一些实施例中，这一保持的元数据可以跟踪哪些其他节点已经确认将文件标记为删除。替 代地，节点可以针对其他负责节点的删除状态定期查询它们以标识其中所有参与者已经进 入至少第一删除阶段的任何文件。一旦已知所有负责副本已经开始删除过程，第二删除阶 段就可以开始（1024)。在一些实施例中，节点可以选择向所有负责对等节点通知第二阶段 已经开始。在第二阶段中，可以去除用于文件的元数据（1026)。
[0085] 图11是图示用于在分布式内容存储中保存改变的过程的一个实施例的流程图。 在所示例子中，接收用于保存对对象的改变的指示（1102)。更新对象的本地负责副本以反 映改变（1104)。指示其他负责副本的位置的本地存储的元数据用来向其他负责副本传播改 变（1106)。在一些实施例中，一旦接收已经更新所有负责副本以反映待保存的改变的确认， 就向请求客户端/应用通知已经完成保存。如果由于合意协议的失败或者拒绝而在成功完 成之前放弃改变，则还原改变（1108)。替代地，在一些实施例中，不应用改变直至被所有负 责节点接受之后。例如通过正常高速缓存管理处理清除对象的被取代版本的高速缓存副本 (1110)。
[0086] 图12是图示用于对存储于分布式内容存储中的对象进行改变的过程的一个实施 例的流程图。在所示例子中，获得对内容对象的所有权"锁定"（1202)。该锁定向其他节点 通知必须通过保持锁定的节点协调对对象的改变。在各种实施例中，这使节点能够在一段 时间内进行相继改变而不必与存储对象的负责副本的其他节点协调。获得锁定的节点协调 在/由其他节点进行的改变(包括通过仲裁或者否则解决任何冲突)并且对如本地存储的对 象实现在任何节点承诺的改变（1204)。一旦节点完成更新对象（1206)，它就向存储对象的 负责副本的其他节点传播在保持锁定的时间期间在/由任何节点进行的累积改变并且释 放锁定（1208)。
[0087]在各种实施例中，节点通过在包含该对象的负责副本的节点集合内向分布式合意 协议提供改变表示来发起对内容对象的改变。向所有负责节点提供这些改变的表示。分布 式合意协议可以提供用于应用改变的全部或者部分排序。这可以减少为了跨越对象的所有 副本进行改变而需要的网络业务量并且允许在修改内容对象时增加的并行量。
[0088] 在各种实施例中，例如如果例如由于一个或者多个节点不可用等而不能确定用来 以满足所有适用管理策略的方式存储对象的节点的指定数量和混合和/或应当已经造成 成功取回请求的对象的多个访问尝试都已经失败，则异常策略确定如何存储对象和/或从 何处尝试访问它。
[0089] 在任何M中的N异常策略之下，向客户端确保在优先列表中的前M个节点之中，它 们中的至少N个节点将包含对象的副本或者至少包含对可以发现副本的位置的引用。这要 求客户端在回退到全局异常索引之前联络至少#-#+ 1个节点。仅在联络至少，价1个 节点并且检查全局异常索引之后，客户端才可以决定性地认为对象不存在。仍然应当与优 先列表的开始尽可能接近地存储对象以减少为了发现对象而必需的总网络往返。在#=1 特殊情况下，任何M中的1异常策略要求客户端在检查异常列表之前联络所有M个节点。
[0090]在前N个异常策略之下，客户端具有前N个节点必须都具有对象副本或者引用的 更强确保。在前N个节点中的任何节点的故障情况下，客户端将回退到优先列表中的后续 节点。如果所有N个节点不可用，则客户端将引用异常列表。如果任何节点可用并且没有 请求的对象的副本，则客户端将回到检查异常列表。尽管这与任何M中的N策略相比减少 了对异常或者不存在的文件定位而需要的网络往返数量，但是它也增加存储全局异常列表 而必需的存储数量，在#= 1的特殊情况下，优先列表直接用作选择功能。如果对象未存储 于优先列表中的第一节点上，则必须在全局异常索引中列举它。
[0091]图13是图示用于存储对象的过程的一个实施例的流程图。在所示例子中，接收对 存储对象的请求（1302)。例如基于如上所述的访问概率、成本和/或管理策略确定将在其 存储对象的一个或者多个优选节点（1304)。尝试在优选节点存储对象（1306)。确定是否已 经满足适用异常策略（1308)(例如对象是否成功存储于M个优选节点中的至少任何N个节 点中）。如果满足异常策略(即无异常）（1310)，则该过程结束。如果未满足异常策略，则选 择并且使用一个或者多个替代位置(未优选）用于存储对象（1312)并且更新全局异常索引 以反映（附加 ）副本存储于何处（1314)。
[0092]图14A是图示用于访问对象的过程的一个实施例的流程图。在所示例子中，接收 对访问对象的请求（1402)。如上文描述的那样，例如基于对象特征、访问概率等确定将从其 尝试取回对象的节点（1404)。如果成功取回对象（1406)，则该过程结束。如果不是，则确 定目前为止未成功检查的(一个或多个)节点的数量和/或混合是否指示应当执行异常处置 (1408)。例如如果任何M中的N异常策略应用并且已经未成功检查确定的优选M个节点之 中的N个节点，则将确定未满足异常策略。如果（尚）无异常（1408)，则检查下一预测节点 (1410)并且检查相继节点直至取回对象或者确定异常（1410,1406,1408)。如果异常出现 (1408)，则在全局异常索引中查找对象（1412)。如果发现条目（1414)，则从指示的节点取 回对象并且该过程结束。否则，返回指示对象不存在的错误（1416)。
[0093]异常编索引从搜索和存储成本的观点来看应当是高效的。用来预测存储位置的统 计表可以被约束成慢漂移，因而预测存储位置的改变未触发对异常列表的大量或者频繁改 变。一种用于提供这一约束的方式是使所有统计数据穿过低通滤波器。由于全局异常索引 无论对象何时存储于未与异常策略相配的位置都必须增长，所以希望也随时间缩减异常列 表，使得系统可以减少对频繁异常索引查找的需要。如果每个对象在异常列表中的条目以 代表对象的优选节点的标识符为前缀，则可以容易形成将倾向于在对象的优选存储节点上 存储异常的跳图。这允许优选节点将客户端迅速重定向至有效副本并且提供可以本地复制 并且从全局异常列表去除的对象的容易工作列表。在一些实现中，优选节点可以保持如下 元数据而未保持对象的内容，该元数据具有其中当前可以发现对象的存储位置的列表。这 允许在搜索者已知需要回退到异常列表之前快速发现当前负责副本。
[0094]全局异常索引可以存储于任何分布式拓扑(诸如跳图或者LH*数据结构)中而向节 点直接分配桶（bucket)。必需的是分布式数据结构适度处置在网络拓扑中添加新位置或者 其他改变。然而存储它，分布式数据结构本身提供异常在节点之间的分割。每个节点可以 使用它的空余资源标识用于解决它负责的异常的方式。当网络资源可用时，可以进行针对 出现重新定位并且减少异常索引的大小的请求。
[0095] 优选节点也可以通过回应针对它们没有的对象的请求来减少异常列表大小。如 果前1个异常策略就位，则第一节点可以在它接收针对对象的请求的任何时间选择检查异 常索引本身。如果对象存在于异常索引中并且主要节点具有可用的空间，则它可以立即高 速缓存对象的副本并且也可以加入负责节点的列表。一旦优选节点具有对象的副本，则异 常索引空间可以与用于更少优选的副本的存储空间一起释放。当执行第一请求时，节点可 以本地存储对象的高速缓存版本。后续请求可以使节点针对对象发生的改变注册为学习 者。节点也可以将它的副本注册为对象中的全责参与者，因此允许从异常列表去除它。在 一些实施例中，可以通过用于更新对象内容的相同合意协议进行对对象元数据的修改。无 论是学习者还是负责的，所有参与者可以与它们参与的(一个或多个）角色一起列举于元数 据中。在各种实施例中，对元数据的这些修改可以是立即的或者可以延迟它们的激活直至 由某些以后事件(诸如检查点提议或者定时器过期)触发。用某些初始负责成员列表创建对 象，并且在该点之后的每个改变是在提议改变时在负责成员全体之间的合意结果。
[0096] 保证文件创建是原子性的要求分布式系统中的特殊考虑。由于对象可能存储于并 非优选位置的存储位置，所以某些次级原子目录是必需的。一种保证创建是原子性的方法 是通过具有全局共享对象目录并且执行原子承诺协议以修改现有对象的目录。另一方法是 保证异常列表存储于如下数据结构(诸如跳图）中，该数据结构允许原子插入操作在分布式 系统中的平凡实现。在一些实施例中，可以混合两种方法。例如可以在通过合意操作维持 的全局目录中列举所有节点或者所有节点的大部分负责的对象，而存储于更小节点子集上 的对象可以依赖于全局异常索引的原子性质。保证向节点群体的窄子集分配给定分区内的 数据的分布式数据结构(诸如跳图）可以通过要求在相邻节点之间的通信改变分割边界来 维持一致性。在相邻节点不可用的情况下，复原动作(诸如改良图形而省略出故障的节点） 需要一种避免分割问题的原子承诺协议。
[0097] 图14B是图示用于在分布式内容存储系统中创建对象的过程的一个实施例的流 程图。当创建新对象并且依赖于全局异常索引的原子插入性质时，创建节点首先针对待创 建的对象搜索全局异常索引（1442)。在一些实施例中，节点可以实际上首先使用优先列表 来搜寻对象并且然后仅在它已经确认对象未存储于优选位置之后回退到搜索全局异常索 弓丨。如果在全局异常索引中发现对象（1444)，则返回如下结果，该结果如适用的那样指示 对象已经存在或者在创建的过程中（1446)。如果未在全局异常索引中发现对象（1444)， 则向全局异常索引中插入指示这一对象当前正在被创建的占位符（1448)。在占位符条目 在全局异常索引中之后，可以根据上文定义的优先列表和异常策略针对对象执行正常扫 描（1450)。如果在异常策略的约束内发现对象（1452)，则返回指示对象已经存在的结果 (1454)。如果未在异常策略的约束内发现对象（1452)，则创建节点可以将元数据和对象内 容的副本放置于优选节点集合上（1456)。
[0098] 在放置元数据和对象内容之后，创建节点可以去除全局异常索引占位符（1458)。 在一些实施例中，可以去除占位符作为如下正常后台过程的部分，该过程迀移全局异常索 引中的对象并且在可能时去除它们的异常条目。可以用时间和/或始发节点标记异常索引 中的占位符条目，使得它们可以由于超时或者节点故障而以后到期。
[0099]使用这些方法，当使用优先列表和异常策略针对对象执行搜索时，可以将文件分 类为存在、不存在、创建或者删除。如果文件存在，则发现有效当前元数据和内容。如果文 件不存在，则未发现元数据或者异常条目。如果创建文件，则在全局异常索引中发现指示创 建文件的占位符条目。如果删除文件，则发现标记为删除并且无对应内容的元数据条目。
[0100] 在一些实施例中，将大文件或者其他对象(诸如数据库）分割成更为可管理的大小 的单独可存储对象。每个分区如这里描述的那样冗余存储于分布式内容存储系统中。在各 种实施例中，可以基于数据库表中的密钥范围或者基于面向列的数据库中的列范围或者通 过其他手段(包括上述手段的组合）形成分区边界，从而将数据库中的数据划分成分区。基 于分区的特征选择在其上存储分区和/或从其尝试访问的节点。
[0101]图15是图示用于存储数据库或者其他大文件的过程的一个实施例的流程图。接 收对象或者其他大文件（1502)。将文件分割成更为可管理的大小的块（1504)。在各种实施 例中，基于文件特征或者其他特性和/或内容系统条件预先配置、可配置和/或动态确定分 区大小。每个分区存储于基于该分区的特征选择的节点上（1506)。在一些实施例中，对数 据库表的分区命名，使得将表名称、可以配置的任何分配表的所有者和主密钥的部分或者 其散列中的每个表示为唯一特征。这样的方案允许表的子集存储于如下位置，这些位置更 频繁地访问该子集中的记录。
[0102] 图16是图示用于访问和存储对象的过程的一个实施例的流程图。在所示例子中， 在每个节点处保持每个特征的访问计数（1602 )。例如如果访问具有特征2、3和5的对象，贝1J 递增针对三个特征中的每个特征的相应计数。在各种实施例中，计数随时间衰减以向更近 的访问给予更大权重。在各种实施例中，在关于一个或者多个特征检测到访问活动迅速改 变的任何节点处，例如通过减少原始访问计数和/或调整基于该计数确定的概率来抑制改 变率。在每个节点处，确定针对存储于节点上的对象的每个特征的计数（1604)。全局聚合并 且使用访问和存储对象计数以生成并且分发访问概率矩阵和存储对象概率矩阵（1606)。多 种方式可以用来在访问和存储矩阵中提供抑制。之所以需要抑制是因为否则太多对象可能 在访问模式改变之后不再处于它们的最优位置。在一个实施例中，矩阵在向节点分发之前 由低通滤波器(诸如无限冲激响应滤波器）抑制。在其他实施例中，可以通过随机采样对象 群体的部分并且统计上确定可能移动的对象数量来估计将以给定的新简档重新定位的对 象数量。在一个实施例中，这与抑制或者全局优化算法结合用来优化在朝着实际访问简档 的收敛与移动的对象数量之间的折衷。因而，可以控制在节点之间移动对象的速率和向全 局异常列表添加对象的速率，而系统使用的访问和存储概率将随时间接近实际概率。访问 概率矩阵针对每个节点并且关于每个节点针对特征集合中的每个特征指示具有该特征的 对象将在该节点被访问的可能性。存储对象概率矩阵针对每个节点并且关于每个节点针对 特征集合中的每个特征指示具有该特征的对象存储于该节点的可能性。在一些实施例中， 访问概率矩阵矩阵用来选择将在其存储对象的节点，并且存储对象概率矩阵用来选择将从 其访问对象的节点。
[0103] 在一些实施例中，提供具有一个或者多个如下槽的装置，每个槽都能够接收可拆 卸盘驱动器或者其他存储设备。盘或者其他驱动器可以插入于槽中。每个驱动配置有如下 数据，该数据可用来在该装置与之关联的集群中集成该驱动器作为节点。
[0104] 图17是图示存储装置的一个实施例的框图。在所示例子中，装置1702包括多个 槽1704、1706、1708和1710。每个槽能够接收可热交换盘驱动器(诸如盘1712和盘1714)。 每个盘预先配置有处理器1716在驱动器插入于槽1704、1706、1708和1710之一中时读取 的数据(例如配置文件)。处理器1716经由网络接口卡或者其他接口 1718和网络连接1720 来与集群中的其他节点通信以向它们通知已经添加新插入的盘。在一些实施例中，每个盘 包括节点。在一些实施例中，装置1702包括被配置成使用包括存储位置的盘存储内容对象 的节点。
[0105] 图18是图示存储盘的一个实施例的框图。在所示例子中，预先配置的热可交换 盘1712包括被配置成存储内容对象的对象存储1802、被配置成存储每个特征的访问对象 和存储对象计数以及访问和/或存储对象概率矩阵的访问和存储对象统计存储1804以及 可用来在存储于集群集成信息存储1806中的数据中标识的集群中集成盘(例如作为节点） 的配置文件或者其他集群集成信息存储1806。数据存储180 2、1804和1806经由内部总线 1808和底板通信接口 1810连接到装置底板1812,盘1712通过该装置底板连接到装置1702 中的其他盘和处理器1716。无论是内容或者统计或者集群集成信息的各种类型的所有对象 可以在单个文件系统内存储于盘上。在另一实施例中，统计和/或元数据可以存储于与内 容不同的存储设备或者节点上或者驻留于系统存储器内。
[0106] 尽管上文以一些细节描述各种实施例，但是其他方式也是可能的。简化方式可以 用于无需上文描述的完全解决方案的更小节点群体。替代地，可以代之以使用其他方法作 为用于系统的部分的扩充或者替换(包括多变元(multivariate)分析和卷积内核)。
[0107]在另一实施例中，选择存储位置的节点可以基于访问和/或存储统计向外部储存 器(诸如网络附着存储文件管理器或者存储区域网络）发起存储和/或访问请求。替代地， 节点可以基于确定的概率将外部对象请求引向适当设备。在各种实施例中，这些公开的统 计方法和选择策略与现有存储基础设施组合以提供分布式内容存储和取回。
[0108] 对于小节点群体，未存储异常索引可能更简单和更高效。当取回对象时，查询上 文描述的存储频率矩阵，并且使用贝叶斯规则来确定每个可能存储位置的概率。系统然后 向可能存储位置请求对象。在一个实施例中，以可能存储位置的相应概率为序进行对可能 存储位置的请求尝试。搜索可以在发现对象或者已经查询充分节点以确定对象不存在时终 止。例如如果对象需要三个复制品并且已经检验了除了两个潜在位置之外的所有潜在位 置，则系统可以返回对象不存在。
[0109] 多变元分析可以在特征或者位置的预测值重叠时允许维度压缩。两种有用的多 变元分析技术是主分量分析或者对应性分析。通过标识可以在未失去显著预测值时坍缩 (collapse)的特征或者位置来提炼先前描述的系统也可以有帮助。可以通过多变元分析技 术直接传递聚合访问和存储矩阵。如果输出用于来提炼，则可以将最相似特征和位置标识 为在所得空间中具有最接近的主坐标。如果输出纯粹用于对象放置和搜索，则每个潜在存 储节点必须由它自己的在与对象特征的主坐标相同的空间中的点代表。对象然后与通过组 合(诸如通过如下加权平均机制，该机制将用于每个特征的P值用作权重）它的特征的点来 发现的点对应。存储节点优先列表是按照与对象的点的距离的升序分类的存储节点列表。 约束统计输入中的漂移并且因此约束特征的所得主坐标中的漂移以减少对象重新定位率。 存储节点也可以在主坐标空间中慢速移动以改进优先列表选择。节点以如下方式在每次重 新计算统计期间略微移动，该方式倾向于将节点相互移开而又移动它们更接近最近的特征 和具有最大质量的特征。以这一方式，节点位置将随机接近主坐标空间上k均值集群算法 的结果，其中k是可用存储节点的数量。
[0110] 在多数情况下，完全代表与个位置关联的优先需要n-1个维度的空间。然而，在 位置优先不独立的程度上可以实现维度压缩(允许信息存储于更少维度中）。可以扰动或者 卷积这样的压缩多维空间以从优先或者访问率度量空间转换成成本度量空间。尽管这样的 方法可以诸如在拆分位置或者添加附加位置时关于网络拓扑的改变表达更多，但是复杂度 明显增加未证实在实践中使用它们是合理的。
[0111] 虽然为了理解清楚而已经以一些细节描述前述实施例，但是本发明并不限于提供 的细节。有诸多实现本发明的替代方式。公开的实施例为示例而非限制。
【主权项】
1. 一种存储数据的系统，包括： 处理器，其被配置为： 从分布式内容存储系统内的多个存储位置的每个存储位置收集对应的多个访问计数 数据，所述多个访问计数数据对应于多个特征中的相应的特征，其中对应于多个特征中的 相应的特征的多个访问计数数据中的一个表示在具有该特征的存储位置处存储的对象的 数量和在具有该特征的存储位置处访问的对象的数量中的至少一个； 至少部分地根据从每个存储位置收集的对应于多个特征中的相应特征的对应的多个 访问计数数据来确定概率数据，其中，所述概率数据包含这样的数据，其指示相对于每个特 征的每个存储位置而言，将从该存储位置访问具有该特征的对象的概率； 确定与内容对象相关联的特征集合，该内容对象关联于操作，其中，该特征集合包含与 该内容对象相关联的性质集合； 至少利用概率数据，至少为多个存储位置的子集的每个存储位置确定具有关联于该内 容对象的该特征集合中的特征的对象与该存储位置相关联的相应的期望可能性；以及 从多个存储位置中选择存储位置以完成相对于该内容对象而言的操作，该选择至少部 分地基于具有该特征的对象关联于被选择的存储位置的期望可能性；以及 存储器，其与处理器耦合并被配置为向处理器提供指令。2. 根据权利要求1所述的系统，其中所述操作包括在所选择的存储位置内存储内容 对象。3. 根据权利要求1所述的系统，其中所述操作包括尝试访问在所选择的存储位置处的 内容对象。4. 根据权利要求1所述的系统，其中所述操作包括从所选的存储位置尝试取回内容对 象而未首先基于索引或者其他数据确定内容对象事实上存储于所选择的存储位置内。5. 根据权利要求1所述的系统，其中具有特征的对象关联于所选择的存储位置的期望 可能性至少包括所选择的存储位置与未选择的另一位置相比与所述特征关联的相对程度。6. 根据权利要求1所述的系统，其中所选择的存储位置包括地理位置。7. 根据权利要求1所述的系统，其中所选择的存储位置包括节点。8. 根据权利要求1所述的系统，其中所选择的存储位置包括盘。9. 根据权利要求1所述的系统，其中所述特征集合包括关于内容对象为真的一个或者 多个声明。10. 根据权利要求1所述的系统，其中所述概率数据包含访问概率矩阵。11. 根据权利要求1所述的系统，其中所述概率数据包括概率矩阵，所述概率矩阵针对 所述分布式内容存储系统内的多个存储设备中的每个并且相对于每个特征的每个存储设 备而言，指示从包含该存储设备的存储位置处访问具有该特征的对象的频率。12. 根据权利要求1所述的系统，其中所述特征集合包括一个或者多个特征，并且还包 括使用所述概率数据针对所述集合中的每个特征确定多个候选存储位置中的每个位置与 该特征在统计上关联的程度，其中多个存储位置包含多个候选存储位置。13. 根据权利要求12所述的系统，所述处理器还被配置为关于每个候选存储位置确定 与选择在该候选存储位置内包含的节点以执行所述操相关联的预计成本。14. 根据权利要求13所述的系统，其中至少部分地基于确定为与选择相应候选存储位 置以执行所述操作关联的相应预计成本来选择所选择的存储位置。15. 根据权利要求1所述的系统，所述处理器还被配置为应用管理策略以根据具有特 征的对象与所选择的存储位置相关联的预期可能性以及与选择所选择的存储位置关联的 确定的成本来确定所选择的存储位置是合格的和需要选择的之一或两者。16. 根据权利要求1所述的系统，其中概率数据指示将从所选择的存储位置访问具有 特征的对象和选择所选择的存储位置来执行的操作将存储内容对象的预期频率。17. 根据权利要求1所述的系统，其中概率数据指示在所选择的存储位置处存储具有 特征的对象和选择所选择的存储位置来执行的操作将访问内容对象的预期频率。18. 根据权利要求1所述的系统，其中确定与内容对象相关联的特征集合包括： 评估与内容对象相关联的标识符以确定一个或多个特性；以及 从与关联于内容对象的标识符相关联的一个或多个特性获得特征集合。19. 一种存储数据的方法，包括： 从分布式内容存储系统内的多个存储位置的每个存储位置收集对应的多个访问计数 数据，所述多个访问计数数据对应于多个特征中的相应的特征，其中对应于多个特征中的 相应的特征的多个访问计数数据中的一个表示在具有该特征的存储位置处存储的对象的 数量和在具有该特征的存储位置处访问的对象的数量中的至少一个； 至少部分地根据从每个存储位置收集的对应于多个特征中的相应特征的对应的多个 访问计数数据来确定概率数据，其中，所述概率数据包含这样的数据，其指示相对于每个特 征的每个存储位置而言，将从该存储位置访问具有该特征的对象的概率； 确定与内容对象相关联的特征集合，该内容对象关联于操作，其中，该特征集合包含与 该内容对象相关联的性质集合； 至少利用概率数据，至少为多个存储位置的子集的每个存储位置确定具有关联于该内 容对象的该特征集合中的特征的对象与该存储位置相关联的相应的期望可能性；以及 从多个存储位置中选择存储位置以完成相对于该内容对象而言的操作，该选择至少部 分地基于具有该特征的对象关联于被选择的存储位置的期望可能性。20. 根据权利要求19所述的方法，其中所述操作包括从所选的存储位置尝试取回内 容对象而未首先基于索引或者其他数据确定内容对象事实上存储于所选择的存储位置内。21. 根据权利要求19所述的方法，其中所述特征集合包括一个或者多个特征，并且还 包括使用所述概率数据针对所述集合中的每个特征确定多个候选存储位置中的每个位置 与该特征在统计上关联的程度，其中多个存储位置包含多个候选存储位置。22. 根据权利要求21所述的方法，还包含关于每个候选存储位置确定与选择在该候选 存储位置内包含的节点以执行所述操相关联的预计成本。23. 根据权利要求22所述的方法，其中至少部分地基于确定为与选择相应候选存储位 置以执行所述操作关联的相应预计成本来选择所选择的存储位置。24. 根据权利要求19所述的方法，还包含应用管理策略以根据具有特征的对象与所选 择的存储位置相关联的预期可能性以及与选择所选择的存储位置关联的确定的成本来确 定所选择的存储位置是合格的和需要选择的之一或两者。
【专利摘要】公开了分布式内容存储和取回。确定与内容对象关联的特征集合。至少部分地基于概率数据从包括分布式内容存储系统的多个存储位置选择用于关于内容对象执行操作的存储位置，该概率数据指示选择的存储位置与包括特征集合的确定为与内容对象关联的特征在统计上关联的程度。
【IPC分类】G06F17/30, H04L29/08
【公开号】CN104899286
【申请号】CN201510303452
【发明人】R.F.罗斯, M.P.莱尔
【申请人】高通股份有限公司
【公开日】2015年9月9日
【申请日】2010年9月21日
【公告号】CN102640125A, CN102640125B, EP2480974A1, EP2480974A4, US8554993, US20110072206, US20140059290, WO2011034625A1
最新回复(0)